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/IR/Constants.h"
25 #include "llvm/IR/LLVMContext.h"
26 #include "llvm/IR/Metadata.h"
27 #include "llvm/IR/Type.h"
28 using namespace clang;
29 using namespace CodeGen;
30 
31 CodeGenTBAA::CodeGenTBAA(ASTContext &Ctx, llvm::LLVMContext& VMContext,
32                          const CodeGenOptions &CGO,
33                          const LangOptions &Features, MangleContext &MContext)
34   : Context(Ctx), CodeGenOpts(CGO), Features(Features), MContext(MContext),
35     MDHelper(VMContext), Root(0), Char(0) {
36 }
37 
38 CodeGenTBAA::~CodeGenTBAA() {
39 }
40 
41 llvm::MDNode *CodeGenTBAA::getRoot() {
42   // Define the root of the tree. This identifies the tree, so that
43   // if our LLVM IR is linked with LLVM IR from a different front-end
44   // (or a different version of this front-end), their TBAA trees will
45   // remain distinct, and the optimizer will treat them conservatively.
46   if (!Root)
47     Root = MDHelper.createTBAARoot("Simple C/C++ TBAA");
48 
49   return Root;
50 }
51 
52 llvm::MDNode *CodeGenTBAA::getChar() {
53   // Define the root of the tree for user-accessible memory. C and C++
54   // give special powers to char and certain similar types. However,
55   // these special powers only cover user-accessible memory, and doesn't
56   // include things like vtables.
57   if (!Char)
58     Char = MDHelper.createTBAANode("omnipotent char", getRoot());
59 
60   return Char;
61 }
62 
63 static bool TypeHasMayAlias(QualType QTy) {
64   // Tagged types have declarations, and therefore may have attributes.
65   if (const TagType *TTy = dyn_cast<TagType>(QTy))
66     return TTy->getDecl()->hasAttr<MayAliasAttr>();
67 
68   // Typedef types have declarations, and therefore may have attributes.
69   if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) {
70     if (TTy->getDecl()->hasAttr<MayAliasAttr>())
71       return true;
72     // Also, their underlying types may have relevant attributes.
73     return TypeHasMayAlias(TTy->desugar());
74   }
75 
76   return false;
77 }
78 
79 llvm::MDNode *
80 CodeGenTBAA::getTBAAInfo(QualType QTy) {
81   // At -O0 TBAA is not emitted for regular types.
82   if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
83     return NULL;
84 
85   // If the type has the may_alias attribute (even on a typedef), it is
86   // effectively in the general char alias class.
87   if (TypeHasMayAlias(QTy))
88     return getChar();
89 
90   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
91 
92   if (llvm::MDNode *N = MetadataCache[Ty])
93     return N;
94 
95   // Handle builtin types.
96   if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
97     switch (BTy->getKind()) {
98     // Character types are special and can alias anything.
99     // In C++, this technically only includes "char" and "unsigned char",
100     // and not "signed char". In C, it includes all three. For now,
101     // the risk of exploiting this detail in C++ seems likely to outweigh
102     // the benefit.
103     case BuiltinType::Char_U:
104     case BuiltinType::Char_S:
105     case BuiltinType::UChar:
106     case BuiltinType::SChar:
107       return getChar();
108 
109     // Unsigned types can alias their corresponding signed types.
110     case BuiltinType::UShort:
111       return getTBAAInfo(Context.ShortTy);
112     case BuiltinType::UInt:
113       return getTBAAInfo(Context.IntTy);
114     case BuiltinType::ULong:
115       return getTBAAInfo(Context.LongTy);
116     case BuiltinType::ULongLong:
117       return getTBAAInfo(Context.LongLongTy);
118     case BuiltinType::UInt128:
119       return getTBAAInfo(Context.Int128Ty);
120 
121     // Treat all other builtin types as distinct types. This includes
122     // treating wchar_t, char16_t, and char32_t as distinct from their
123     // "underlying types".
124     default:
125       return MetadataCache[Ty] =
126         MDHelper.createTBAANode(BTy->getName(Features), getChar());
127     }
128   }
129 
130   // Handle pointers.
131   // TODO: Implement C++'s type "similarity" and consider dis-"similar"
132   // pointers distinct.
133   if (Ty->isPointerType())
134     return MetadataCache[Ty] = MDHelper.createTBAANode("any pointer",
135                                                        getChar());
136 
137   // Enum types are distinct types. In C++ they have "underlying types",
138   // however they aren't related for TBAA.
139   if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
140     // In C mode, two anonymous enums are compatible iff their members
141     // are the same -- see C99 6.2.7p1. For now, be conservative. We could
142     // theoretically implement this by combining information about all the
143     // members into a single identifying MDNode.
144     if (!Features.CPlusPlus &&
145         ETy->getDecl()->getTypedefNameForAnonDecl())
146       return MetadataCache[Ty] = getChar();
147 
148     // In C++ mode, types have linkage, so we can rely on the ODR and
149     // on their mangled names, if they're external.
150     // TODO: Is there a way to get a program-wide unique name for a
151     // decl with local linkage or no linkage?
152     if (Features.CPlusPlus &&
153         ETy->getDecl()->getLinkage() != ExternalLinkage)
154       return MetadataCache[Ty] = getChar();
155 
156     // TODO: This is using the RTTI name. Is there a better way to get
157     // a unique string for a type?
158     SmallString<256> OutName;
159     llvm::raw_svector_ostream Out(OutName);
160     MContext.mangleCXXRTTIName(QualType(ETy, 0), Out);
161     Out.flush();
162     return MetadataCache[Ty] = MDHelper.createTBAANode(OutName, getChar());
163   }
164 
165   // For now, handle any other kind of type conservatively.
166   return MetadataCache[Ty] = getChar();
167 }
168 
169 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
170   return MDHelper.createTBAANode("vtable pointer", getRoot());
171 }
172 
173 bool
174 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
175                            QualType QTy,
176                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
177                              Fields,
178                            bool MayAlias) {
179   /* Things not handled yet include: C++ base classes, bitfields, */
180 
181   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
182     const RecordDecl *RD = TTy->getDecl()->getDefinition();
183     if (RD->hasFlexibleArrayMember())
184       return false;
185 
186     // TODO: Handle C++ base classes.
187     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
188       if (Decl->bases_begin() != Decl->bases_end())
189         return false;
190 
191     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
192 
193     unsigned idx = 0;
194     for (RecordDecl::field_iterator i = RD->field_begin(),
195          e = RD->field_end(); i != e; ++i, ++idx) {
196       uint64_t Offset = BaseOffset +
197                         Layout.getFieldOffset(idx) / Context.getCharWidth();
198       QualType FieldQTy = i->getType();
199       if (!CollectFields(Offset, FieldQTy, Fields,
200                          MayAlias || TypeHasMayAlias(FieldQTy)))
201         return false;
202     }
203     return true;
204   }
205 
206   /* Otherwise, treat whatever it is as a field. */
207   uint64_t Offset = BaseOffset;
208   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
209   llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy);
210   Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAAInfo));
211   return true;
212 }
213 
214 llvm::MDNode *
215 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
216   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
217 
218   if (llvm::MDNode *N = StructMetadataCache[Ty])
219     return N;
220 
221   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
222   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
223     return MDHelper.createTBAAStructNode(Fields);
224 
225   // For now, handle any other kind of type conservatively.
226   return StructMetadataCache[Ty] = NULL;
227 }
228