1//===--- CodeGenTypes.cpp - TBAA information for LLVM CodeGen -------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This is the code that manages TBAA information and defines the TBAA policy
11// for the optimizer to use. Relevant standards text includes:
12//
13//   C99 6.5p7
14//   C++ [basic.lval] (p10 in n3126, p15 in some earlier versions)
15//
16//===----------------------------------------------------------------------===//
17
18#include "CodeGenTBAA.h"
19#include "clang/AST/ASTContext.h"
20#include "clang/AST/Attr.h"
21#include "clang/AST/Mangle.h"
22#include "clang/AST/RecordLayout.h"
23#include "clang/Frontend/CodeGenOptions.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/LLVMContext.h"
27#include "llvm/IR/Metadata.h"
28#include "llvm/IR/Type.h"
29using namespace clang;
30using namespace CodeGen;
31
32CodeGenTBAA::CodeGenTBAA(ASTContext &Ctx, llvm::LLVMContext& VMContext,
33                         const CodeGenOptions &CGO,
34                         const LangOptions &Features, MangleContext &MContext)
35  : Context(Ctx), CodeGenOpts(CGO), Features(Features), MContext(MContext),
36    MDHelper(VMContext), Root(0), Char(0) {
37}
38
39CodeGenTBAA::~CodeGenTBAA() {
40}
41
42llvm::MDNode *CodeGenTBAA::getRoot() {
43  // Define the root of the tree. This identifies the tree, so that
44  // if our LLVM IR is linked with LLVM IR from a different front-end
45  // (or a different version of this front-end), their TBAA trees will
46  // remain distinct, and the optimizer will treat them conservatively.
47  if (!Root)
48    Root = MDHelper.createTBAARoot("Simple C/C++ TBAA");
49
50  return Root;
51}
52
53// For struct-path aware TBAA, the scalar type has the same format as
54// the struct type: name, offset, pointer to another node in the type DAG.
55// For scalar TBAA, the scalar type is the same as the scalar tag:
56// name and a parent pointer.
57llvm::MDNode *CodeGenTBAA::createTBAAScalarType(StringRef Name,
58                                                llvm::MDNode *Parent) {
59  if (CodeGenOpts.StructPathTBAA)
60    return MDHelper.createTBAAScalarTypeNode(Name, Parent);
61  else
62    return MDHelper.createTBAANode(Name, Parent);
63}
64
65llvm::MDNode *CodeGenTBAA::getChar() {
66  // Define the root of the tree for user-accessible memory. C and C++
67  // give special powers to char and certain similar types. However,
68  // these special powers only cover user-accessible memory, and doesn't
69  // include things like vtables.
70  if (!Char)
71    Char = createTBAAScalarType("omnipotent char", getRoot());
72
73  return Char;
74}
75
76static bool TypeHasMayAlias(QualType QTy) {
77  // Tagged types have declarations, and therefore may have attributes.
78  if (const TagType *TTy = dyn_cast<TagType>(QTy))
79    return TTy->getDecl()->hasAttr<MayAliasAttr>();
80
81  // Typedef types have declarations, and therefore may have attributes.
82  if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) {
83    if (TTy->getDecl()->hasAttr<MayAliasAttr>())
84      return true;
85    // Also, their underlying types may have relevant attributes.
86    return TypeHasMayAlias(TTy->desugar());
87  }
88
89  return false;
90}
91
92llvm::MDNode *
93CodeGenTBAA::getTBAAInfo(QualType QTy) {
94  // At -O0 TBAA is not emitted for regular types.
95  if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
96    return NULL;
97
98  // If the type has the may_alias attribute (even on a typedef), it is
99  // effectively in the general char alias class.
100  if (TypeHasMayAlias(QTy))
101    return getChar();
102
103  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
104
105  if (llvm::MDNode *N = MetadataCache[Ty])
106    return N;
107
108  // Handle builtin types.
109  if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
110    switch (BTy->getKind()) {
111    // Character types are special and can alias anything.
112    // In C++, this technically only includes "char" and "unsigned char",
113    // and not "signed char". In C, it includes all three. For now,
114    // the risk of exploiting this detail in C++ seems likely to outweigh
115    // the benefit.
116    case BuiltinType::Char_U:
117    case BuiltinType::Char_S:
118    case BuiltinType::UChar:
119    case BuiltinType::SChar:
120      return getChar();
121
122    // Unsigned types can alias their corresponding signed types.
123    case BuiltinType::UShort:
124      return getTBAAInfo(Context.ShortTy);
125    case BuiltinType::UInt:
126      return getTBAAInfo(Context.IntTy);
127    case BuiltinType::ULong:
128      return getTBAAInfo(Context.LongTy);
129    case BuiltinType::ULongLong:
130      return getTBAAInfo(Context.LongLongTy);
131    case BuiltinType::UInt128:
132      return getTBAAInfo(Context.Int128Ty);
133
134    // Treat all other builtin types as distinct types. This includes
135    // treating wchar_t, char16_t, and char32_t as distinct from their
136    // "underlying types".
137    default:
138      return MetadataCache[Ty] =
139        createTBAAScalarType(BTy->getName(Features), getChar());
140    }
141  }
142
143  // Handle pointers.
144  // TODO: Implement C++'s type "similarity" and consider dis-"similar"
145  // pointers distinct.
146  if (Ty->isPointerType())
147    return MetadataCache[Ty] = createTBAAScalarType("any pointer",
148                                                    getChar());
149
150  // Enum types are distinct types. In C++ they have "underlying types",
151  // however they aren't related for TBAA.
152  if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
153    // In C++ mode, types have linkage, so we can rely on the ODR and
154    // on their mangled names, if they're external.
155    // TODO: Is there a way to get a program-wide unique name for a
156    // decl with local linkage or no linkage?
157    if (!Features.CPlusPlus || !ETy->getDecl()->isExternallyVisible())
158      return MetadataCache[Ty] = getChar();
159
160    // TODO: This is using the RTTI name. Is there a better way to get
161    // a unique string for a type?
162    SmallString<256> OutName;
163    llvm::raw_svector_ostream Out(OutName);
164    MContext.mangleCXXRTTIName(QualType(ETy, 0), Out);
165    Out.flush();
166    return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar());
167  }
168
169  // For now, handle any other kind of type conservatively.
170  return MetadataCache[Ty] = getChar();
171}
172
173llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
174  return createTBAAScalarType("vtable pointer", getRoot());
175}
176
177bool
178CodeGenTBAA::CollectFields(uint64_t BaseOffset,
179                           QualType QTy,
180                           SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
181                             Fields,
182                           bool MayAlias) {
183  /* Things not handled yet include: C++ base classes, bitfields, */
184
185  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
186    const RecordDecl *RD = TTy->getDecl()->getDefinition();
187    if (RD->hasFlexibleArrayMember())
188      return false;
189
190    // TODO: Handle C++ base classes.
191    if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
192      if (Decl->bases_begin() != Decl->bases_end())
193        return false;
194
195    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
196
197    unsigned idx = 0;
198    for (RecordDecl::field_iterator i = RD->field_begin(),
199         e = RD->field_end(); i != e; ++i, ++idx) {
200      uint64_t Offset = BaseOffset +
201                        Layout.getFieldOffset(idx) / Context.getCharWidth();
202      QualType FieldQTy = i->getType();
203      if (!CollectFields(Offset, FieldQTy, Fields,
204                         MayAlias || TypeHasMayAlias(FieldQTy)))
205        return false;
206    }
207    return true;
208  }
209
210  /* Otherwise, treat whatever it is as a field. */
211  uint64_t Offset = BaseOffset;
212  uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
213  llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy);
214  llvm::MDNode *TBAATag = CodeGenOpts.StructPathTBAA ?
215                          getTBAAScalarTagInfo(TBAAInfo) : TBAAInfo;
216  Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
217  return true;
218}
219
220llvm::MDNode *
221CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
222  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
223
224  if (llvm::MDNode *N = StructMetadataCache[Ty])
225    return N;
226
227  SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
228  if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
229    return MDHelper.createTBAAStructNode(Fields);
230
231  // For now, handle any other kind of type conservatively.
232  return StructMetadataCache[Ty] = NULL;
233}
234
235/// Check if the given type can be handled by path-aware TBAA.
236static bool isTBAAPathStruct(QualType QTy) {
237  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
238    const RecordDecl *RD = TTy->getDecl()->getDefinition();
239    if (RD->hasFlexibleArrayMember())
240      return false;
241    // RD can be struct, union, class, interface or enum.
242    // For now, we only handle struct and class.
243    if (RD->isStruct() || RD->isClass())
244      return true;
245  }
246  return false;
247}
248
249llvm::MDNode *
250CodeGenTBAA::getTBAAStructTypeInfo(QualType QTy) {
251  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
252  assert(isTBAAPathStruct(QTy));
253
254  if (llvm::MDNode *N = StructTypeMetadataCache[Ty])
255    return N;
256
257  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
258    const RecordDecl *RD = TTy->getDecl()->getDefinition();
259
260    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
261    SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields;
262    unsigned idx = 0;
263    for (RecordDecl::field_iterator i = RD->field_begin(),
264         e = RD->field_end(); i != e; ++i, ++idx) {
265      QualType FieldQTy = i->getType();
266      llvm::MDNode *FieldNode;
267      if (isTBAAPathStruct(FieldQTy))
268        FieldNode = getTBAAStructTypeInfo(FieldQTy);
269      else
270        FieldNode = getTBAAInfo(FieldQTy);
271      if (!FieldNode)
272        return StructTypeMetadataCache[Ty] = NULL;
273      Fields.push_back(std::make_pair(
274          FieldNode, Layout.getFieldOffset(idx) / Context.getCharWidth()));
275    }
276
277    // TODO: This is using the RTTI name. Is there a better way to get
278    // a unique string for a type?
279    SmallString<256> OutName;
280    llvm::raw_svector_ostream Out(OutName);
281    MContext.mangleCXXRTTIName(QualType(Ty, 0), Out);
282    Out.flush();
283    // Create the struct type node with a vector of pairs (offset, type).
284    return StructTypeMetadataCache[Ty] =
285      MDHelper.createTBAAStructTypeNode(OutName, Fields);
286  }
287
288  return StructMetadataCache[Ty] = NULL;
289}
290
291llvm::MDNode *
292CodeGenTBAA::getTBAAStructTagInfo(QualType BaseQTy, llvm::MDNode *AccessNode,
293                                  uint64_t Offset) {
294  if (!CodeGenOpts.StructPathTBAA)
295    return AccessNode;
296
297  const Type *BTy = Context.getCanonicalType(BaseQTy).getTypePtr();
298  TBAAPathTag PathTag = TBAAPathTag(BTy, AccessNode, Offset);
299  if (llvm::MDNode *N = StructTagMetadataCache[PathTag])
300    return N;
301
302  llvm::MDNode *BNode = 0;
303  if (isTBAAPathStruct(BaseQTy))
304    BNode  = getTBAAStructTypeInfo(BaseQTy);
305  if (!BNode)
306    return StructTagMetadataCache[PathTag] =
307       MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
308
309  return StructTagMetadataCache[PathTag] =
310    MDHelper.createTBAAStructTagNode(BNode, AccessNode, Offset);
311}
312
313llvm::MDNode *
314CodeGenTBAA::getTBAAScalarTagInfo(llvm::MDNode *AccessNode) {
315  if (llvm::MDNode *N = ScalarTagMetadataCache[AccessNode])
316    return N;
317
318  return ScalarTagMetadataCache[AccessNode] =
319    MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
320}
321