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(nullptr), Char(nullptr) { 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 both scalar TBAA and struct-path aware TBAA, the scalar type has the 54 // same format: name, parent node, and offset. 55 llvm::MDNode *CodeGenTBAA::createTBAAScalarType(StringRef Name, 56 llvm::MDNode *Parent) { 57 return MDHelper.createTBAAScalarTypeNode(Name, Parent); 58 } 59 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 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 * 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 165 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() { 166 return createTBAAScalarType("vtable pointer", getRoot()); 167 } 168 169 bool 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 * 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. 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 * 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 * 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 * 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