• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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"
29 using namespace clang;
30 using namespace CodeGen;
31 
CodeGenTBAA(ASTContext & Ctx,llvm::LLVMContext & VMContext,const CodeGenOptions & CGO,const LangOptions & Features,MangleContext & MContext)32 CodeGenTBAA::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(nullptr), Char(nullptr) {
37 }
38 
~CodeGenTBAA()39 CodeGenTBAA::~CodeGenTBAA() {
40 }
41 
getRoot()42 llvm::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 both scalar TBAA and struct-path aware TBAA, the scalar type has the
54 // same format: name, parent node, and offset.
createTBAAScalarType(StringRef Name,llvm::MDNode * Parent)55 llvm::MDNode *CodeGenTBAA::createTBAAScalarType(StringRef Name,
56                                                 llvm::MDNode *Parent) {
57   return MDHelper.createTBAAScalarTypeNode(Name, Parent);
58 }
59 
getChar()60 llvm::MDNode *CodeGenTBAA::getChar() {
61   // Define the root of the tree for user-accessible memory. C and C++
62   // give special powers to char and certain similar types. However,
63   // these special powers only cover user-accessible memory, and doesn't
64   // include things like vtables.
65   if (!Char)
66     Char = createTBAAScalarType("omnipotent char", getRoot());
67 
68   return Char;
69 }
70 
TypeHasMayAlias(QualType QTy)71 static bool TypeHasMayAlias(QualType QTy) {
72   // Tagged types have declarations, and therefore may have attributes.
73   if (const TagType *TTy = dyn_cast<TagType>(QTy))
74     return TTy->getDecl()->hasAttr<MayAliasAttr>();
75 
76   // Typedef types have declarations, and therefore may have attributes.
77   if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) {
78     if (TTy->getDecl()->hasAttr<MayAliasAttr>())
79       return true;
80     // Also, their underlying types may have relevant attributes.
81     return TypeHasMayAlias(TTy->desugar());
82   }
83 
84   return false;
85 }
86 
87 llvm::MDNode *
getTBAAInfo(QualType QTy)88 CodeGenTBAA::getTBAAInfo(QualType QTy) {
89   // At -O0 or relaxed aliasing, TBAA is not emitted for regular types.
90   if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
91     return nullptr;
92 
93   // If the type has the may_alias attribute (even on a typedef), it is
94   // effectively in the general char alias class.
95   if (TypeHasMayAlias(QTy))
96     return getChar();
97 
98   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
99 
100   if (llvm::MDNode *N = MetadataCache[Ty])
101     return N;
102 
103   // Handle builtin types.
104   if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
105     switch (BTy->getKind()) {
106     // Character types are special and can alias anything.
107     // In C++, this technically only includes "char" and "unsigned char",
108     // and not "signed char". In C, it includes all three. For now,
109     // the risk of exploiting this detail in C++ seems likely to outweigh
110     // the benefit.
111     case BuiltinType::Char_U:
112     case BuiltinType::Char_S:
113     case BuiltinType::UChar:
114     case BuiltinType::SChar:
115       return getChar();
116 
117     // Unsigned types can alias their corresponding signed types.
118     case BuiltinType::UShort:
119       return getTBAAInfo(Context.ShortTy);
120     case BuiltinType::UInt:
121       return getTBAAInfo(Context.IntTy);
122     case BuiltinType::ULong:
123       return getTBAAInfo(Context.LongTy);
124     case BuiltinType::ULongLong:
125       return getTBAAInfo(Context.LongLongTy);
126     case BuiltinType::UInt128:
127       return getTBAAInfo(Context.Int128Ty);
128 
129     // Treat all other builtin types as distinct types. This includes
130     // treating wchar_t, char16_t, and char32_t as distinct from their
131     // "underlying types".
132     default:
133       return MetadataCache[Ty] =
134         createTBAAScalarType(BTy->getName(Features), getChar());
135     }
136   }
137 
138   // Handle pointers.
139   // TODO: Implement C++'s type "similarity" and consider dis-"similar"
140   // pointers distinct.
141   if (Ty->isPointerType())
142     return MetadataCache[Ty] = createTBAAScalarType("any pointer",
143                                                     getChar());
144 
145   // Enum types are distinct types. In C++ they have "underlying types",
146   // however they aren't related for TBAA.
147   if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
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 || !ETy->getDecl()->isExternallyVisible())
153       return MetadataCache[Ty] = getChar();
154 
155     SmallString<256> OutName;
156     llvm::raw_svector_ostream Out(OutName);
157     MContext.mangleTypeName(QualType(ETy, 0), Out);
158     return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar());
159   }
160 
161   // For now, handle any other kind of type conservatively.
162   return MetadataCache[Ty] = getChar();
163 }
164 
getTBAAInfoForVTablePtr()165 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
166   return createTBAAScalarType("vtable pointer", getRoot());
167 }
168 
169 bool
CollectFields(uint64_t BaseOffset,QualType QTy,SmallVectorImpl<llvm::MDBuilder::TBAAStructField> & Fields,bool MayAlias)170 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
171                            QualType QTy,
172                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
173                              Fields,
174                            bool MayAlias) {
175   /* Things not handled yet include: C++ base classes, bitfields, */
176 
177   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
178     const RecordDecl *RD = TTy->getDecl()->getDefinition();
179     if (RD->hasFlexibleArrayMember())
180       return false;
181 
182     // TODO: Handle C++ base classes.
183     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
184       if (Decl->bases_begin() != Decl->bases_end())
185         return false;
186 
187     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
188 
189     unsigned idx = 0;
190     for (RecordDecl::field_iterator i = RD->field_begin(),
191          e = RD->field_end(); i != e; ++i, ++idx) {
192       uint64_t Offset = BaseOffset +
193                         Layout.getFieldOffset(idx) / Context.getCharWidth();
194       QualType FieldQTy = i->getType();
195       if (!CollectFields(Offset, FieldQTy, Fields,
196                          MayAlias || TypeHasMayAlias(FieldQTy)))
197         return false;
198     }
199     return true;
200   }
201 
202   /* Otherwise, treat whatever it is as a field. */
203   uint64_t Offset = BaseOffset;
204   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
205   llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy);
206   llvm::MDNode *TBAATag = getTBAAScalarTagInfo(TBAAInfo);
207   Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
208   return true;
209 }
210 
211 llvm::MDNode *
getTBAAStructInfo(QualType QTy)212 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
213   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
214 
215   if (llvm::MDNode *N = StructMetadataCache[Ty])
216     return N;
217 
218   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
219   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
220     return MDHelper.createTBAAStructNode(Fields);
221 
222   // For now, handle any other kind of type conservatively.
223   return StructMetadataCache[Ty] = nullptr;
224 }
225 
226 /// Check if the given type can be handled by path-aware TBAA.
isTBAAPathStruct(QualType QTy)227 static bool isTBAAPathStruct(QualType QTy) {
228   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
229     const RecordDecl *RD = TTy->getDecl()->getDefinition();
230     if (RD->hasFlexibleArrayMember())
231       return false;
232     // RD can be struct, union, class, interface or enum.
233     // For now, we only handle struct and class.
234     if (RD->isStruct() || RD->isClass())
235       return true;
236   }
237   return false;
238 }
239 
240 llvm::MDNode *
getTBAAStructTypeInfo(QualType QTy)241 CodeGenTBAA::getTBAAStructTypeInfo(QualType QTy) {
242   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
243   assert(isTBAAPathStruct(QTy));
244 
245   if (llvm::MDNode *N = StructTypeMetadataCache[Ty])
246     return N;
247 
248   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
249     const RecordDecl *RD = TTy->getDecl()->getDefinition();
250 
251     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
252     SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields;
253     unsigned idx = 0;
254     for (RecordDecl::field_iterator i = RD->field_begin(),
255          e = RD->field_end(); i != e; ++i, ++idx) {
256       QualType FieldQTy = i->getType();
257       llvm::MDNode *FieldNode;
258       if (isTBAAPathStruct(FieldQTy))
259         FieldNode = getTBAAStructTypeInfo(FieldQTy);
260       else
261         FieldNode = getTBAAInfo(FieldQTy);
262       if (!FieldNode)
263         return StructTypeMetadataCache[Ty] = nullptr;
264       Fields.push_back(std::make_pair(
265           FieldNode, Layout.getFieldOffset(idx) / Context.getCharWidth()));
266     }
267 
268     SmallString<256> OutName;
269     if (Features.CPlusPlus) {
270       // Don't use the mangler for C code.
271       llvm::raw_svector_ostream Out(OutName);
272       MContext.mangleTypeName(QualType(Ty, 0), Out);
273     } else {
274       OutName = RD->getName();
275     }
276     // Create the struct type node with a vector of pairs (offset, type).
277     return StructTypeMetadataCache[Ty] =
278       MDHelper.createTBAAStructTypeNode(OutName, Fields);
279   }
280 
281   return StructMetadataCache[Ty] = nullptr;
282 }
283 
284 /// Return a TBAA tag node for both scalar TBAA and struct-path aware TBAA.
285 llvm::MDNode *
getTBAAStructTagInfo(QualType BaseQTy,llvm::MDNode * AccessNode,uint64_t Offset)286 CodeGenTBAA::getTBAAStructTagInfo(QualType BaseQTy, llvm::MDNode *AccessNode,
287                                   uint64_t Offset) {
288   if (!AccessNode)
289     return nullptr;
290 
291   if (!CodeGenOpts.StructPathTBAA)
292     return getTBAAScalarTagInfo(AccessNode);
293 
294   const Type *BTy = Context.getCanonicalType(BaseQTy).getTypePtr();
295   TBAAPathTag PathTag = TBAAPathTag(BTy, AccessNode, Offset);
296   if (llvm::MDNode *N = StructTagMetadataCache[PathTag])
297     return N;
298 
299   llvm::MDNode *BNode = nullptr;
300   if (isTBAAPathStruct(BaseQTy))
301     BNode  = getTBAAStructTypeInfo(BaseQTy);
302   if (!BNode)
303     return StructTagMetadataCache[PathTag] =
304        MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
305 
306   return StructTagMetadataCache[PathTag] =
307     MDHelper.createTBAAStructTagNode(BNode, AccessNode, Offset);
308 }
309 
310 llvm::MDNode *
getTBAAScalarTagInfo(llvm::MDNode * AccessNode)311 CodeGenTBAA::getTBAAScalarTagInfo(llvm::MDNode *AccessNode) {
312   if (!AccessNode)
313     return nullptr;
314   if (llvm::MDNode *N = ScalarTagMetadataCache[AccessNode])
315     return N;
316 
317   return ScalarTagMetadataCache[AccessNode] =
318     MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
319 }
320