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
25using namespace clang;
26using namespace infer_alloc;
27
28static bool
29typeContainsPointer(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.
85static 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///
111static 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///
147static 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///
163static 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
173QualType 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.
199static 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
210namespace {
211/// Implements collectPlacementNewTypes(). A variable qualifies if every
212/// reference to it other than its initializer is an lvalue-to-rvalue read.
213class PlacementNewCollector : public ConstDynamicRecursiveASTVisitor {
214public:
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
269private:
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
287llvm::DenseMap<const CallExpr *, QualType>
288infer_alloc::collectPlacementNewTypes(const Stmt *Body) {
289 PlacementNewCollector Collector;
290 if (Body)
291 Collector.TraverseStmt(S: Body);
292 return std::move(Collector).finish();
293}
294
295std::optional<llvm::AllocTokenMetadata>
296infer_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