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(0), Char(0) {
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 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.
createTBAAScalarType(StringRef Name,llvm::MDNode * Parent)57 llvm::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
getChar()65 llvm::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
TypeHasMayAlias(QualType QTy)76 static 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
92 llvm::MDNode *
getTBAAInfo(QualType QTy)93 CodeGenTBAA::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
getTBAAInfoForVTablePtr()173 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
174 return createTBAAScalarType("vtable pointer", getRoot());
175 }
176
177 bool
CollectFields(uint64_t BaseOffset,QualType QTy,SmallVectorImpl<llvm::MDBuilder::TBAAStructField> & Fields,bool MayAlias)178 CodeGenTBAA::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
220 llvm::MDNode *
getTBAAStructInfo(QualType QTy)221 CodeGenTBAA::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.
isTBAAPathStruct(QualType QTy)236 static 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
249 llvm::MDNode *
getTBAAStructTypeInfo(QualType QTy)250 CodeGenTBAA::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
291 llvm::MDNode *
getTBAAStructTagInfo(QualType BaseQTy,llvm::MDNode * AccessNode,uint64_t Offset)292 CodeGenTBAA::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
313 llvm::MDNode *
getTBAAScalarTagInfo(llvm::MDNode * AccessNode)314 CodeGenTBAA::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