1 //===-- CodeGenTBAA.cpp - TBAA information for LLVM CodeGen ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This is the code that manages TBAA information and defines the TBAA policy 10 // for the optimizer to use. Relevant standards text includes: 11 // 12 // C99 6.5p7 13 // C++ [basic.lval] (p10 in n3126, p15 in some earlier versions) 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "CodeGenTBAA.h" 18 #include "clang/AST/ASTContext.h" 19 #include "clang/AST/Attr.h" 20 #include "clang/AST/Mangle.h" 21 #include "clang/AST/RecordLayout.h" 22 #include "clang/Basic/CodeGenOptions.h" 23 #include "llvm/ADT/SmallSet.h" 24 #include "llvm/IR/Constants.h" 25 #include "llvm/IR/LLVMContext.h" 26 #include "llvm/IR/Metadata.h" 27 #include "llvm/IR/Module.h" 28 #include "llvm/IR/Type.h" 29 using namespace clang; 30 using namespace CodeGen; 31 32 CodeGenTBAA::CodeGenTBAA(ASTContext &Ctx, llvm::Module &M, 33 const CodeGenOptions &CGO, 34 const LangOptions &Features, MangleContext &MContext) 35 : Context(Ctx), Module(M), CodeGenOpts(CGO), 36 Features(Features), MContext(MContext), MDHelper(M.getContext()), 37 Root(nullptr), Char(nullptr) 38 {} 39 40 CodeGenTBAA::~CodeGenTBAA() { 41 } 42 43 llvm::MDNode *CodeGenTBAA::getRoot() { 44 // Define the root of the tree. This identifies the tree, so that 45 // if our LLVM IR is linked with LLVM IR from a different front-end 46 // (or a different version of this front-end), their TBAA trees will 47 // remain distinct, and the optimizer will treat them conservatively. 48 if (!Root) { 49 if (Features.CPlusPlus) 50 Root = MDHelper.createTBAARoot("Simple C++ TBAA"); 51 else 52 Root = MDHelper.createTBAARoot("Simple C/C++ TBAA"); 53 } 54 55 return Root; 56 } 57 58 llvm::MDNode *CodeGenTBAA::createScalarTypeNode(StringRef Name, 59 llvm::MDNode *Parent, 60 uint64_t Size) { 61 if (CodeGenOpts.NewStructPathTBAA) { 62 llvm::Metadata *Id = MDHelper.createString(Name); 63 return MDHelper.createTBAATypeNode(Parent, Size, Id); 64 } 65 return MDHelper.createTBAAScalarTypeNode(Name, Parent); 66 } 67 68 llvm::MDNode *CodeGenTBAA::getChar() { 69 // Define the root of the tree for user-accessible memory. C and C++ 70 // give special powers to char and certain similar types. However, 71 // these special powers only cover user-accessible memory, and doesn't 72 // include things like vtables. 73 if (!Char) 74 Char = createScalarTypeNode("omnipotent char", getRoot(), /* Size= */ 1); 75 76 return Char; 77 } 78 79 static bool TypeHasMayAlias(QualType QTy) { 80 // Tagged types have declarations, and therefore may have attributes. 81 if (const TagType *TTy = dyn_cast<TagType>(QTy)) 82 return TTy->getDecl()->hasAttr<MayAliasAttr>(); 83 84 // Typedef types have declarations, and therefore may have attributes. 85 if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) { 86 if (TTy->getDecl()->hasAttr<MayAliasAttr>()) 87 return true; 88 // Also, their underlying types may have relevant attributes. 89 return TypeHasMayAlias(TTy->desugar()); 90 } 91 92 return false; 93 } 94 95 /// Check if the given type is a valid base type to be used in access tags. 96 static bool isValidBaseType(QualType QTy) { 97 if (QTy->isReferenceType()) 98 return false; 99 if (const RecordType *TTy = QTy->getAs<RecordType>()) { 100 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 101 // Incomplete types are not valid base access types. 102 if (!RD) 103 return false; 104 if (RD->hasFlexibleArrayMember()) 105 return false; 106 // RD can be struct, union, class, interface or enum. 107 // For now, we only handle struct and class. 108 if (RD->isStruct() || RD->isClass()) 109 return true; 110 } 111 return false; 112 } 113 114 llvm::MDNode *CodeGenTBAA::getTypeInfoHelper(const Type *Ty) { 115 uint64_t Size = Context.getTypeSizeInChars(Ty).getQuantity(); 116 117 // Handle builtin types. 118 if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) { 119 switch (BTy->getKind()) { 120 // Character types are special and can alias anything. 121 // In C++, this technically only includes "char" and "unsigned char", 122 // and not "signed char". In C, it includes all three. For now, 123 // the risk of exploiting this detail in C++ seems likely to outweigh 124 // the benefit. 125 case BuiltinType::Char_U: 126 case BuiltinType::Char_S: 127 case BuiltinType::UChar: 128 case BuiltinType::SChar: 129 return getChar(); 130 131 // Unsigned types can alias their corresponding signed types. 132 case BuiltinType::UShort: 133 return getTypeInfo(Context.ShortTy); 134 case BuiltinType::UInt: 135 return getTypeInfo(Context.IntTy); 136 case BuiltinType::ULong: 137 return getTypeInfo(Context.LongTy); 138 case BuiltinType::ULongLong: 139 return getTypeInfo(Context.LongLongTy); 140 case BuiltinType::UInt128: 141 return getTypeInfo(Context.Int128Ty); 142 143 // Treat all other builtin types as distinct types. This includes 144 // treating wchar_t, char16_t, and char32_t as distinct from their 145 // "underlying types". 146 default: 147 return createScalarTypeNode(BTy->getName(Features), getChar(), Size); 148 } 149 } 150 151 // C++1z [basic.lval]p10: "If a program attempts to access the stored value of 152 // an object through a glvalue of other than one of the following types the 153 // behavior is undefined: [...] a char, unsigned char, or std::byte type." 154 if (Ty->isStdByteType()) 155 return getChar(); 156 157 // Handle pointers and references. 158 // TODO: Implement C++'s type "similarity" and consider dis-"similar" 159 // pointers distinct. 160 if (Ty->isPointerType() || Ty->isReferenceType()) 161 return createScalarTypeNode("any pointer", getChar(), Size); 162 163 // Accesses to arrays are accesses to objects of their element types. 164 if (CodeGenOpts.NewStructPathTBAA && Ty->isArrayType()) 165 return getTypeInfo(cast<ArrayType>(Ty)->getElementType()); 166 167 // Enum types are distinct types. In C++ they have "underlying types", 168 // however they aren't related for TBAA. 169 if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) { 170 // In C++ mode, types have linkage, so we can rely on the ODR and 171 // on their mangled names, if they're external. 172 // TODO: Is there a way to get a program-wide unique name for a 173 // decl with local linkage or no linkage? 174 if (!Features.CPlusPlus || !ETy->getDecl()->isExternallyVisible()) 175 return getChar(); 176 177 SmallString<256> OutName; 178 llvm::raw_svector_ostream Out(OutName); 179 MContext.mangleTypeName(QualType(ETy, 0), Out); 180 return createScalarTypeNode(OutName, getChar(), Size); 181 } 182 183 // For now, handle any other kind of type conservatively. 184 return getChar(); 185 } 186 187 llvm::MDNode *CodeGenTBAA::getTypeInfo(QualType QTy) { 188 // At -O0 or relaxed aliasing, TBAA is not emitted for regular types. 189 if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing) 190 return nullptr; 191 192 // If the type has the may_alias attribute (even on a typedef), it is 193 // effectively in the general char alias class. 194 if (TypeHasMayAlias(QTy)) 195 return getChar(); 196 197 // We need this function to not fall back to returning the "omnipotent char" 198 // type node for aggregate and union types. Otherwise, any dereference of an 199 // aggregate will result into the may-alias access descriptor, meaning all 200 // subsequent accesses to direct and indirect members of that aggregate will 201 // be considered may-alias too. 202 // TODO: Combine getTypeInfo() and getBaseTypeInfo() into a single function. 203 if (isValidBaseType(QTy)) 204 return getBaseTypeInfo(QTy); 205 206 const Type *Ty = Context.getCanonicalType(QTy).getTypePtr(); 207 if (llvm::MDNode *N = MetadataCache[Ty]) 208 return N; 209 210 // Note that the following helper call is allowed to add new nodes to the 211 // cache, which invalidates all its previously obtained iterators. So we 212 // first generate the node for the type and then add that node to the cache. 213 llvm::MDNode *TypeNode = getTypeInfoHelper(Ty); 214 return MetadataCache[Ty] = TypeNode; 215 } 216 217 TBAAAccessInfo CodeGenTBAA::getAccessInfo(QualType AccessType) { 218 // Pointee values may have incomplete types, but they shall never be 219 // dereferenced. 220 if (AccessType->isIncompleteType()) 221 return TBAAAccessInfo::getIncompleteInfo(); 222 223 if (TypeHasMayAlias(AccessType)) 224 return TBAAAccessInfo::getMayAliasInfo(); 225 226 uint64_t Size = Context.getTypeSizeInChars(AccessType).getQuantity(); 227 return TBAAAccessInfo(getTypeInfo(AccessType), Size); 228 } 229 230 TBAAAccessInfo CodeGenTBAA::getVTablePtrAccessInfo(llvm::Type *VTablePtrType) { 231 llvm::DataLayout DL(&Module); 232 unsigned Size = DL.getPointerTypeSize(VTablePtrType); 233 return TBAAAccessInfo(createScalarTypeNode("vtable pointer", getRoot(), Size), 234 Size); 235 } 236 237 bool 238 CodeGenTBAA::CollectFields(uint64_t BaseOffset, 239 QualType QTy, 240 SmallVectorImpl<llvm::MDBuilder::TBAAStructField> & 241 Fields, 242 bool MayAlias) { 243 /* Things not handled yet include: C++ base classes, bitfields, */ 244 245 if (const RecordType *TTy = QTy->getAs<RecordType>()) { 246 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 247 if (RD->hasFlexibleArrayMember()) 248 return false; 249 250 // TODO: Handle C++ base classes. 251 if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD)) 252 if (Decl->bases_begin() != Decl->bases_end()) 253 return false; 254 255 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 256 257 unsigned idx = 0; 258 for (RecordDecl::field_iterator i = RD->field_begin(), 259 e = RD->field_end(); i != e; ++i, ++idx) { 260 if ((*i)->isZeroSize(Context) || (*i)->isUnnamedBitfield()) 261 continue; 262 uint64_t Offset = BaseOffset + 263 Layout.getFieldOffset(idx) / Context.getCharWidth(); 264 QualType FieldQTy = i->getType(); 265 if (!CollectFields(Offset, FieldQTy, Fields, 266 MayAlias || TypeHasMayAlias(FieldQTy))) 267 return false; 268 } 269 return true; 270 } 271 272 /* Otherwise, treat whatever it is as a field. */ 273 uint64_t Offset = BaseOffset; 274 uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity(); 275 llvm::MDNode *TBAAType = MayAlias ? getChar() : getTypeInfo(QTy); 276 llvm::MDNode *TBAATag = getAccessTagInfo(TBAAAccessInfo(TBAAType, Size)); 277 Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag)); 278 return true; 279 } 280 281 llvm::MDNode * 282 CodeGenTBAA::getTBAAStructInfo(QualType QTy) { 283 const Type *Ty = Context.getCanonicalType(QTy).getTypePtr(); 284 285 if (llvm::MDNode *N = StructMetadataCache[Ty]) 286 return N; 287 288 SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields; 289 if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy))) 290 return MDHelper.createTBAAStructNode(Fields); 291 292 // For now, handle any other kind of type conservatively. 293 return StructMetadataCache[Ty] = nullptr; 294 } 295 296 llvm::MDNode *CodeGenTBAA::getBaseTypeInfoHelper(const Type *Ty) { 297 if (auto *TTy = dyn_cast<RecordType>(Ty)) { 298 const RecordDecl *RD = TTy->getDecl()->getDefinition(); 299 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 300 SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields; 301 for (FieldDecl *Field : RD->fields()) { 302 if (Field->isZeroSize(Context) || Field->isUnnamedBitfield()) 303 continue; 304 QualType FieldQTy = Field->getType(); 305 llvm::MDNode *TypeNode = isValidBaseType(FieldQTy) ? 306 getBaseTypeInfo(FieldQTy) : getTypeInfo(FieldQTy); 307 if (!TypeNode) 308 return BaseTypeMetadataCache[Ty] = nullptr; 309 310 uint64_t BitOffset = Layout.getFieldOffset(Field->getFieldIndex()); 311 uint64_t Offset = Context.toCharUnitsFromBits(BitOffset).getQuantity(); 312 uint64_t Size = Context.getTypeSizeInChars(FieldQTy).getQuantity(); 313 Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, 314 TypeNode)); 315 } 316 317 SmallString<256> OutName; 318 if (Features.CPlusPlus) { 319 // Don't use the mangler for C code. 320 llvm::raw_svector_ostream Out(OutName); 321 MContext.mangleTypeName(QualType(Ty, 0), Out); 322 } else { 323 OutName = RD->getName(); 324 } 325 326 if (CodeGenOpts.NewStructPathTBAA) { 327 llvm::MDNode *Parent = getChar(); 328 uint64_t Size = Context.getTypeSizeInChars(Ty).getQuantity(); 329 llvm::Metadata *Id = MDHelper.createString(OutName); 330 return MDHelper.createTBAATypeNode(Parent, Size, Id, Fields); 331 } 332 333 // Create the struct type node with a vector of pairs (offset, type). 334 SmallVector<std::pair<llvm::MDNode*, uint64_t>, 4> OffsetsAndTypes; 335 for (const auto &Field : Fields) 336 OffsetsAndTypes.push_back(std::make_pair(Field.Type, Field.Offset)); 337 return MDHelper.createTBAAStructTypeNode(OutName, OffsetsAndTypes); 338 } 339 340 return nullptr; 341 } 342 343 llvm::MDNode *CodeGenTBAA::getBaseTypeInfo(QualType QTy) { 344 if (!isValidBaseType(QTy)) 345 return nullptr; 346 347 const Type *Ty = Context.getCanonicalType(QTy).getTypePtr(); 348 if (llvm::MDNode *N = BaseTypeMetadataCache[Ty]) 349 return N; 350 351 // Note that the following helper call is allowed to add new nodes to the 352 // cache, which invalidates all its previously obtained iterators. So we 353 // first generate the node for the type and then add that node to the cache. 354 llvm::MDNode *TypeNode = getBaseTypeInfoHelper(Ty); 355 return BaseTypeMetadataCache[Ty] = TypeNode; 356 } 357 358 llvm::MDNode *CodeGenTBAA::getAccessTagInfo(TBAAAccessInfo Info) { 359 assert(!Info.isIncomplete() && "Access to an object of an incomplete type!"); 360 361 if (Info.isMayAlias()) 362 Info = TBAAAccessInfo(getChar(), Info.Size); 363 364 if (!Info.AccessType) 365 return nullptr; 366 367 if (!CodeGenOpts.StructPathTBAA) 368 Info = TBAAAccessInfo(Info.AccessType, Info.Size); 369 370 llvm::MDNode *&N = AccessTagMetadataCache[Info]; 371 if (N) 372 return N; 373 374 if (!Info.BaseType) { 375 Info.BaseType = Info.AccessType; 376 assert(!Info.Offset && "Nonzero offset for an access with no base type!"); 377 } 378 if (CodeGenOpts.NewStructPathTBAA) { 379 return N = MDHelper.createTBAAAccessTag(Info.BaseType, Info.AccessType, 380 Info.Offset, Info.Size); 381 } 382 return N = MDHelper.createTBAAStructTagNode(Info.BaseType, Info.AccessType, 383 Info.Offset); 384 } 385 386 TBAAAccessInfo CodeGenTBAA::mergeTBAAInfoForCast(TBAAAccessInfo SourceInfo, 387 TBAAAccessInfo TargetInfo) { 388 if (SourceInfo.isMayAlias() || TargetInfo.isMayAlias()) 389 return TBAAAccessInfo::getMayAliasInfo(); 390 return TargetInfo; 391 } 392 393 TBAAAccessInfo 394 CodeGenTBAA::mergeTBAAInfoForConditionalOperator(TBAAAccessInfo InfoA, 395 TBAAAccessInfo InfoB) { 396 if (InfoA == InfoB) 397 return InfoA; 398 399 if (!InfoA || !InfoB) 400 return TBAAAccessInfo(); 401 402 if (InfoA.isMayAlias() || InfoB.isMayAlias()) 403 return TBAAAccessInfo::getMayAliasInfo(); 404 405 // TODO: Implement the rest of the logic here. For example, two accesses 406 // with same final access types result in an access to an object of that final 407 // access type regardless of their base types. 408 return TBAAAccessInfo::getMayAliasInfo(); 409 } 410 411 TBAAAccessInfo 412 CodeGenTBAA::mergeTBAAInfoForMemoryTransfer(TBAAAccessInfo DestInfo, 413 TBAAAccessInfo SrcInfo) { 414 if (DestInfo == SrcInfo) 415 return DestInfo; 416 417 if (!DestInfo || !SrcInfo) 418 return TBAAAccessInfo(); 419 420 if (DestInfo.isMayAlias() || SrcInfo.isMayAlias()) 421 return TBAAAccessInfo::getMayAliasInfo(); 422 423 // TODO: Implement the rest of the logic here. For example, two accesses 424 // with same final access types result in an access to an object of that final 425 // access type regardless of their base types. 426 return TBAAAccessInfo::getMayAliasInfo(); 427 } 428