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 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 39 CodeGenTBAA::~CodeGenTBAA() { 40 } 41 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. 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 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 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 * 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 173 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() { 174 return createTBAAScalarType("vtable pointer", getRoot()); 175 } 176 177 bool 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 * 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. 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 * 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 * 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 * 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
