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 Out.flush(); 159 return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar()); 160 } 161 162 // For now, handle any other kind of type conservatively. 163 return MetadataCache[Ty] = getChar(); 164 } 165 166 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() { 167 return createTBAAScalarType("vtable pointer", getRoot()); 168 } 169 170 bool 171 CodeGenTBAA::CollectFields(uint64_t BaseOffset, 172 QualType QTy, 173 SmallVectorImpl<llvm::MDBuilder::TBAAStructField> & 174 Fields, 175 bool MayAlias) { 176 /* Things not handled yet include: C++ base classes, bitfields, */ 177 178 if (const RecordType *TTy = QTy->getAs<RecordType>()) { 179 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 180 if (RD->hasFlexibleArrayMember()) 181 return false; 182 183 // TODO: Handle C++ base classes. 184 if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD)) 185 if (Decl->bases_begin() != Decl->bases_end()) 186 return false; 187 188 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 189 190 unsigned idx = 0; 191 for (RecordDecl::field_iterator i = RD->field_begin(), 192 e = RD->field_end(); i != e; ++i, ++idx) { 193 uint64_t Offset = BaseOffset + 194 Layout.getFieldOffset(idx) / Context.getCharWidth(); 195 QualType FieldQTy = i->getType(); 196 if (!CollectFields(Offset, FieldQTy, Fields, 197 MayAlias || TypeHasMayAlias(FieldQTy))) 198 return false; 199 } 200 return true; 201 } 202 203 /* Otherwise, treat whatever it is as a field. */ 204 uint64_t Offset = BaseOffset; 205 uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity(); 206 llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy); 207 llvm::MDNode *TBAATag = getTBAAScalarTagInfo(TBAAInfo); 208 Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag)); 209 return true; 210 } 211 212 llvm::MDNode * 213 CodeGenTBAA::getTBAAStructInfo(QualType QTy) { 214 const Type *Ty = Context.getCanonicalType(QTy).getTypePtr(); 215 216 if (llvm::MDNode *N = StructMetadataCache[Ty]) 217 return N; 218 219 SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields; 220 if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy))) 221 return MDHelper.createTBAAStructNode(Fields); 222 223 // For now, handle any other kind of type conservatively. 224 return StructMetadataCache[Ty] = nullptr; 225 } 226 227 /// Check if the given type can be handled by path-aware TBAA. 228 static bool isTBAAPathStruct(QualType QTy) { 229 if (const RecordType *TTy = QTy->getAs<RecordType>()) { 230 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 231 if (RD->hasFlexibleArrayMember()) 232 return false; 233 // RD can be struct, union, class, interface or enum. 234 // For now, we only handle struct and class. 235 if (RD->isStruct() || RD->isClass()) 236 return true; 237 } 238 return false; 239 } 240 241 llvm::MDNode * 242 CodeGenTBAA::getTBAAStructTypeInfo(QualType QTy) { 243 const Type *Ty = Context.getCanonicalType(QTy).getTypePtr(); 244 assert(isTBAAPathStruct(QTy)); 245 246 if (llvm::MDNode *N = StructTypeMetadataCache[Ty]) 247 return N; 248 249 if (const RecordType *TTy = QTy->getAs<RecordType>()) { 250 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 251 252 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 253 SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields; 254 unsigned idx = 0; 255 for (RecordDecl::field_iterator i = RD->field_begin(), 256 e = RD->field_end(); i != e; ++i, ++idx) { 257 QualType FieldQTy = i->getType(); 258 llvm::MDNode *FieldNode; 259 if (isTBAAPathStruct(FieldQTy)) 260 FieldNode = getTBAAStructTypeInfo(FieldQTy); 261 else 262 FieldNode = getTBAAInfo(FieldQTy); 263 if (!FieldNode) 264 return StructTypeMetadataCache[Ty] = nullptr; 265 Fields.push_back(std::make_pair( 266 FieldNode, Layout.getFieldOffset(idx) / Context.getCharWidth())); 267 } 268 269 SmallString<256> OutName; 270 if (Features.CPlusPlus) { 271 // Don't use the mangler for C code. 272 llvm::raw_svector_ostream Out(OutName); 273 MContext.mangleTypeName(QualType(Ty, 0), Out); 274 Out.flush(); 275 } else { 276 OutName = RD->getName(); 277 } 278 // Create the struct type node with a vector of pairs (offset, type). 279 return StructTypeMetadataCache[Ty] = 280 MDHelper.createTBAAStructTypeNode(OutName, Fields); 281 } 282 283 return StructMetadataCache[Ty] = nullptr; 284 } 285 286 /// Return a TBAA tag node for both scalar TBAA and struct-path aware TBAA. 287 llvm::MDNode * 288 CodeGenTBAA::getTBAAStructTagInfo(QualType BaseQTy, llvm::MDNode *AccessNode, 289 uint64_t Offset) { 290 if (!AccessNode) 291 return nullptr; 292 293 if (!CodeGenOpts.StructPathTBAA) 294 return getTBAAScalarTagInfo(AccessNode); 295 296 const Type *BTy = Context.getCanonicalType(BaseQTy).getTypePtr(); 297 TBAAPathTag PathTag = TBAAPathTag(BTy, AccessNode, Offset); 298 if (llvm::MDNode *N = StructTagMetadataCache[PathTag]) 299 return N; 300 301 llvm::MDNode *BNode = nullptr; 302 if (isTBAAPathStruct(BaseQTy)) 303 BNode = getTBAAStructTypeInfo(BaseQTy); 304 if (!BNode) 305 return StructTagMetadataCache[PathTag] = 306 MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0); 307 308 return StructTagMetadataCache[PathTag] = 309 MDHelper.createTBAAStructTagNode(BNode, AccessNode, Offset); 310 } 311 312 llvm::MDNode * 313 CodeGenTBAA::getTBAAScalarTagInfo(llvm::MDNode *AccessNode) { 314 if (!AccessNode) 315 return nullptr; 316 if (llvm::MDNode *N = ScalarTagMetadataCache[AccessNode]) 317 return N; 318 319 return ScalarTagMetadataCache[AccessNode] = 320 MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0); 321 } 322