| 1 | //===--- InferAlloc.cpp - Allocation type inference -----------------------===// |
| 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 file implements allocation-related type inference. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "clang/AST/InferAlloc.h" |
| 14 | #include "clang/AST/ASTContext.h" |
| 15 | #include "clang/AST/Decl.h" |
| 16 | #include "clang/AST/DeclCXX.h" |
| 17 | #include "clang/AST/DynamicRecursiveASTVisitor.h" |
| 18 | #include "clang/AST/Expr.h" |
| 19 | #include "clang/AST/ExprCXX.h" |
| 20 | #include "clang/AST/Type.h" |
| 21 | #include "clang/Basic/IdentifierTable.h" |
| 22 | #include "llvm/ADT/SmallPtrSet.h" |
| 23 | #include "llvm/ADT/SmallVector.h" |
| 24 | |
| 25 | using namespace clang; |
| 26 | using namespace infer_alloc; |
| 27 | |
| 28 | static bool |
| 29 | typeContainsPointer(QualType T, |
| 30 | llvm::SmallPtrSet<const RecordDecl *, 4> &VisitedRD, |
| 31 | bool &IncompleteType) { |
| 32 | QualType CanonicalType = T.getCanonicalType(); |
| 33 | if (CanonicalType->isAnyPointerType() || CanonicalType->isReferenceType() || |
| 34 | CanonicalType->isMemberFunctionPointerType() || |
| 35 | CanonicalType->isBlockPointerType()) |
| 36 | return true; // base case |
| 37 | |
| 38 | // Look through typedef chain to check for special types. |
| 39 | for (QualType CurrentT = T; const auto *TT = CurrentT->getAs<TypedefType>(); |
| 40 | CurrentT = TT->getDecl()->getUnderlyingType()) { |
| 41 | const IdentifierInfo *II = TT->getDecl()->getIdentifier(); |
| 42 | // Special Case: Syntactically uintptr_t is not a pointer; semantically, |
| 43 | // however, very likely used as such. Therefore, classify uintptr_t as a |
| 44 | // pointer, too. |
| 45 | if (II && II->isStr(Str: "uintptr_t" )) |
| 46 | return true; |
| 47 | } |
| 48 | |
| 49 | // The type is an array; check the element type. |
| 50 | if (const ArrayType *AT = dyn_cast<ArrayType>(Val&: CanonicalType)) |
| 51 | return typeContainsPointer(T: AT->getElementType(), VisitedRD, IncompleteType); |
| 52 | |
| 53 | // The type is an atomic type. |
| 54 | if (const AtomicType *AT = dyn_cast<AtomicType>(Val&: CanonicalType)) |
| 55 | return typeContainsPointer(T: AT->getValueType(), VisitedRD, IncompleteType); |
| 56 | |
| 57 | // The type is a struct, class, or union. |
| 58 | if (const RecordDecl *RD = CanonicalType->getAsRecordDecl()) { |
| 59 | if (!RD->isCompleteDefinition()) { |
| 60 | IncompleteType = true; |
| 61 | return false; |
| 62 | } |
| 63 | if (!VisitedRD.insert(Ptr: RD).second) |
| 64 | return false; // already visited |
| 65 | // Check all fields. |
| 66 | for (const FieldDecl *Field : RD->fields()) { |
| 67 | if (typeContainsPointer(T: Field->getType(), VisitedRD, IncompleteType)) |
| 68 | return true; |
| 69 | } |
| 70 | // For C++ classes, also check base classes. |
| 71 | if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(Val: RD)) { |
| 72 | // Polymorphic types require a vptr. |
| 73 | if (CXXRD->isDynamicClass()) |
| 74 | return true; |
| 75 | for (const CXXBaseSpecifier &Base : CXXRD->bases()) { |
| 76 | if (typeContainsPointer(T: Base.getType(), VisitedRD, IncompleteType)) |
| 77 | return true; |
| 78 | } |
| 79 | } |
| 80 | } |
| 81 | return false; |
| 82 | } |
| 83 | |
| 84 | /// Infer type from a simple sizeof expression. |
| 85 | static QualType inferTypeFromSizeofExpr(const Expr *E) { |
| 86 | const Expr *Arg = E->IgnoreParenImpCasts(); |
| 87 | if (const auto *UET = dyn_cast<UnaryExprOrTypeTraitExpr>(Val: Arg)) { |
| 88 | if (UET->getKind() == UETT_SizeOf) { |
| 89 | if (UET->isArgumentType()) |
| 90 | return UET->getArgumentTypeInfo()->getType(); |
| 91 | else |
| 92 | return UET->getArgumentExpr()->getType(); |
| 93 | } |
| 94 | } |
| 95 | return QualType(); |
| 96 | } |
| 97 | |
| 98 | /// Infer type from an arithmetic expression involving a sizeof. For example: |
| 99 | /// |
| 100 | /// malloc(sizeof(MyType) + padding); // infers 'MyType' |
| 101 | /// malloc(sizeof(MyType) * 32); // infers 'MyType' |
| 102 | /// malloc(32 * sizeof(MyType)); // infers 'MyType' |
| 103 | /// malloc(sizeof(MyType) << 1); // infers 'MyType' |
| 104 | /// ... |
| 105 | /// |
| 106 | /// More complex arithmetic expressions are supported, but are a heuristic, e.g. |
| 107 | /// when considering allocations for structs with flexible array members: |
| 108 | /// |
| 109 | /// malloc(sizeof(HasFlexArray) + sizeof(int) * 32); // infers 'HasFlexArray' |
| 110 | /// |
| 111 | static QualType inferPossibleTypeFromArithSizeofExpr(const Expr *E) { |
| 112 | const Expr *Arg = E->IgnoreParenImpCasts(); |
| 113 | // The argument is a lone sizeof expression. |
| 114 | if (QualType T = inferTypeFromSizeofExpr(E: Arg); !T.isNull()) |
| 115 | return T; |
| 116 | if (const auto *BO = dyn_cast<BinaryOperator>(Val: Arg)) { |
| 117 | // Argument is an arithmetic expression. Cover common arithmetic patterns |
| 118 | // involving sizeof. |
| 119 | switch (BO->getOpcode()) { |
| 120 | case BO_Add: |
| 121 | case BO_Div: |
| 122 | case BO_Mul: |
| 123 | case BO_Shl: |
| 124 | case BO_Shr: |
| 125 | case BO_Sub: |
| 126 | if (QualType T = inferPossibleTypeFromArithSizeofExpr(E: BO->getLHS()); |
| 127 | !T.isNull()) |
| 128 | return T; |
| 129 | if (QualType T = inferPossibleTypeFromArithSizeofExpr(E: BO->getRHS()); |
| 130 | !T.isNull()) |
| 131 | return T; |
| 132 | break; |
| 133 | default: |
| 134 | break; |
| 135 | } |
| 136 | } |
| 137 | return QualType(); |
| 138 | } |
| 139 | |
| 140 | /// If the expression E is a reference to a variable, infer the type from a |
| 141 | /// variable's initializer if it contains a sizeof. Beware, this is a heuristic |
| 142 | /// and ignores if a variable is later reassigned. For example: |
| 143 | /// |
| 144 | /// size_t my_size = sizeof(MyType); |
| 145 | /// void *x = malloc(my_size); // infers 'MyType' |
| 146 | /// |
| 147 | static QualType inferPossibleTypeFromVarInitSizeofExpr(const Expr *E) { |
| 148 | const Expr *Arg = E->IgnoreParenImpCasts(); |
| 149 | if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Arg)) { |
| 150 | if (const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) { |
| 151 | if (const Expr *Init = VD->getInit()) |
| 152 | return inferPossibleTypeFromArithSizeofExpr(E: Init); |
| 153 | } |
| 154 | } |
| 155 | return QualType(); |
| 156 | } |
| 157 | |
| 158 | /// Deduces the allocated type by checking if the allocation call's result |
| 159 | /// is immediately used in a cast expression. For example: |
| 160 | /// |
| 161 | /// MyType *x = (MyType *)malloc(4096); // infers 'MyType' |
| 162 | /// |
| 163 | static QualType inferPossibleTypeFromCastExpr(const CallExpr *CallE, |
| 164 | const CastExpr *CastE) { |
| 165 | if (!CastE) |
| 166 | return QualType(); |
| 167 | QualType PtrType = CastE->getType(); |
| 168 | if (PtrType->isPointerType()) |
| 169 | return PtrType->getPointeeType(); |
| 170 | return QualType(); |
| 171 | } |
| 172 | |
| 173 | QualType infer_alloc::inferPossibleType( |
| 174 | const CallExpr *E, const ASTContext &Ctx, const CastExpr *CastE, |
| 175 | llvm::function_ref<QualType(const CallExpr *)> PlacementNewType) { |
| 176 | QualType AllocType; |
| 177 | // First check arguments: a sizeof states what the allocation was sized for. |
| 178 | for (const Expr *Arg : E->arguments()) { |
| 179 | AllocType = inferPossibleTypeFromArithSizeofExpr(E: Arg); |
| 180 | if (AllocType.isNull()) |
| 181 | AllocType = inferPossibleTypeFromVarInitSizeofExpr(E: Arg); |
| 182 | if (!AllocType.isNull()) |
| 183 | break; |
| 184 | } |
| 185 | // Then check for a placement new into the result, which names the object |
| 186 | // constructed there and is stronger evidence than a cast of the result. |
| 187 | if (AllocType.isNull() && PlacementNewType) |
| 188 | AllocType = PlacementNewType(E); |
| 189 | // Then check later casts. |
| 190 | if (AllocType.isNull()) |
| 191 | AllocType = inferPossibleTypeFromCastExpr(CallE: E, CastE); |
| 192 | return AllocType; |
| 193 | } |
| 194 | |
| 195 | /// Strips parentheses and non-static field accesses of a by-value object |
| 196 | /// (e.g. the pointer member of a size-returning allocation result) from an |
| 197 | /// lvalue, down to the expression naming the object. Indirect member accesses |
| 198 | /// (`->`) name other storage and stop the walk. |
| 199 | static const Expr *stripFields(const Expr *E) { |
| 200 | E = E->IgnoreParens(); |
| 201 | while (const auto *ME = dyn_cast<MemberExpr>(Val: E)) { |
| 202 | if (ME->isArrow() || !isa<FieldDecl>(Val: ME->getMemberDecl())) |
| 203 | break; |
| 204 | // The base of a member of a temporary is a MaterializeTemporaryExpr. |
| 205 | E = ME->getBase()->IgnoreParenImpCasts(); |
| 206 | } |
| 207 | return E; |
| 208 | } |
| 209 | |
| 210 | namespace { |
| 211 | /// Implements collectPlacementNewTypes(). A variable qualifies if every |
| 212 | /// reference to it other than its initializer is an lvalue-to-rvalue read. |
| 213 | class PlacementNewCollector : public ConstDynamicRecursiveASTVisitor { |
| 214 | public: |
| 215 | // Resolved after the traversal: a use that is not a read may follow the |
| 216 | // placement new and still disqualify the variable. |
| 217 | llvm::DenseMap<const CallExpr *, QualType> finish() && { |
| 218 | for (const auto &[VD, T] : Uses) |
| 219 | if (const CallExpr *CE = Defs.lookup(Val: VD)) |
| 220 | record(CE, T); |
| 221 | return std::move(CallTypes); |
| 222 | } |
| 223 | |
| 224 | bool VisitVarDecl(const VarDecl *VD) override { |
| 225 | const Expr *Init = VD->getInit(); |
| 226 | if (Init && VD->hasLocalStorage() && !isa<ParmVarDecl>(Val: VD)) |
| 227 | if (const auto *CE = |
| 228 | dyn_cast<CallExpr>(Val: Init->IgnoreImplicit()->IgnoreParenCasts())) |
| 229 | Defs.try_emplace(Key: VD, Args&: CE); |
| 230 | return true; |
| 231 | } |
| 232 | |
| 233 | // A read of the variable or of one of its fields. Traversal is pre-order, |
| 234 | // so the conversion is seen before the DeclRefExpr below it. |
| 235 | bool VisitImplicitCastExpr(const ImplicitCastExpr *ICE) override { |
| 236 | if (ICE->getCastKind() == CK_LValueToRValue) |
| 237 | if (const auto *DRE = |
| 238 | dyn_cast<DeclRefExpr>(Val: stripFields(E: ICE->getSubExpr()))) |
| 239 | Reads.insert(Ptr: DRE); |
| 240 | return true; |
| 241 | } |
| 242 | |
| 243 | // Any other reference may modify the variable. |
| 244 | bool VisitDeclRefExpr(const DeclRefExpr *DRE) override { |
| 245 | if (!Reads.contains(Ptr: DRE)) |
| 246 | if (const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) |
| 247 | Defs.erase(Val: VD); |
| 248 | return true; |
| 249 | } |
| 250 | |
| 251 | bool VisitCXXNewExpr(const CXXNewExpr *NE) override { |
| 252 | // Only the reserved placement form is known to construct into its |
| 253 | // argument; dependent new-expressions have no operator new yet. |
| 254 | const FunctionDecl *OperatorNew = NE->getOperatorNew(); |
| 255 | if (NE->getNumPlacementArgs() != 1 || !OperatorNew || |
| 256 | !OperatorNew->isReservedGlobalPlacementOperator()) |
| 257 | return true; |
| 258 | const Expr *Source = |
| 259 | stripFields(E: NE->getPlacementArg(I: 0)->IgnoreParenCasts()); |
| 260 | QualType T = NE->getAllocatedType(); |
| 261 | if (const auto *CE = dyn_cast<CallExpr>(Val: Source)) |
| 262 | record(CE, T); |
| 263 | else if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Source)) |
| 264 | if (const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) |
| 265 | Uses.emplace_back(Args&: VD, Args&: T); |
| 266 | return true; |
| 267 | } |
| 268 | |
| 269 | private: |
| 270 | void record(const CallExpr *CE, QualType T) { |
| 271 | auto [It, Inserted] = CallTypes.try_emplace(Key: CE, Args&: T); |
| 272 | // Different types constructed into the same storage: ambiguous. |
| 273 | if (!Inserted && !It->second.isNull() && |
| 274 | It->second.getCanonicalType() != T.getCanonicalType()) |
| 275 | It->second = QualType(); |
| 276 | } |
| 277 | |
| 278 | llvm::DenseMap<const CallExpr *, QualType> CallTypes; |
| 279 | // Variable -> the allocation call initializing it; erased on any use that |
| 280 | // is not a read. |
| 281 | llvm::DenseMap<const VarDecl *, const CallExpr *> Defs; |
| 282 | llvm::SmallPtrSet<const DeclRefExpr *, 16> Reads; |
| 283 | llvm::SmallVector<std::pair<const VarDecl *, QualType>> Uses; |
| 284 | }; |
| 285 | } // namespace |
| 286 | |
| 287 | llvm::DenseMap<const CallExpr *, QualType> |
| 288 | infer_alloc::collectPlacementNewTypes(const Stmt *Body) { |
| 289 | PlacementNewCollector Collector; |
| 290 | if (Body) |
| 291 | Collector.TraverseStmt(S: Body); |
| 292 | return std::move(Collector).finish(); |
| 293 | } |
| 294 | |
| 295 | std::optional<llvm::AllocTokenMetadata> |
| 296 | infer_alloc::getAllocTokenMetadata(QualType T, const ASTContext &Ctx) { |
| 297 | llvm::AllocTokenMetadata ATMD; |
| 298 | |
| 299 | // Get unique type name. |
| 300 | PrintingPolicy Policy(Ctx.getLangOpts()); |
| 301 | Policy.SuppressTagKeyword = true; |
| 302 | Policy.FullyQualifiedName = true; |
| 303 | llvm::raw_svector_ostream TypeNameOS(ATMD.TypeName); |
| 304 | T.getCanonicalType().print(OS&: TypeNameOS, Policy); |
| 305 | |
| 306 | // Check if QualType contains a pointer. Implements a simple DFS to |
| 307 | // recursively check if a type contains a pointer type. |
| 308 | llvm::SmallPtrSet<const RecordDecl *, 4> VisitedRD; |
| 309 | bool IncompleteType = false; |
| 310 | ATMD.ContainsPointer = typeContainsPointer(T, VisitedRD, IncompleteType); |
| 311 | if (!ATMD.ContainsPointer && IncompleteType) |
| 312 | return std::nullopt; |
| 313 | |
| 314 | return ATMD; |
| 315 | } |
| 316 | |