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/Expr.h"
18#include "clang/AST/Type.h"
19#include "clang/Basic/IdentifierTable.h"
20#include "llvm/ADT/SmallPtrSet.h"
21
22using namespace clang;
23using namespace infer_alloc;
24
25static bool
26typeContainsPointer(QualType T,
27 llvm::SmallPtrSet<const RecordDecl *, 4> &VisitedRD,
28 bool &IncompleteType) {
29 QualType CanonicalType = T.getCanonicalType();
30 if (CanonicalType->isAnyPointerType() || CanonicalType->isReferenceType() ||
31 CanonicalType->isMemberFunctionPointerType() ||
32 CanonicalType->isBlockPointerType())
33 return true; // base case
34
35 // Look through typedef chain to check for special types.
36 for (QualType CurrentT = T; const auto *TT = CurrentT->getAs<TypedefType>();
37 CurrentT = TT->getDecl()->getUnderlyingType()) {
38 const IdentifierInfo *II = TT->getDecl()->getIdentifier();
39 // Special Case: Syntactically uintptr_t is not a pointer; semantically,
40 // however, very likely used as such. Therefore, classify uintptr_t as a
41 // pointer, too.
42 if (II && II->isStr(Str: "uintptr_t"))
43 return true;
44 }
45
46 // The type is an array; check the element type.
47 if (const ArrayType *AT = dyn_cast<ArrayType>(Val&: CanonicalType))
48 return typeContainsPointer(T: AT->getElementType(), VisitedRD, IncompleteType);
49
50 // The type is an atomic type.
51 if (const AtomicType *AT = dyn_cast<AtomicType>(Val&: CanonicalType))
52 return typeContainsPointer(T: AT->getValueType(), VisitedRD, IncompleteType);
53
54 // The type is a struct, class, or union.
55 if (const RecordDecl *RD = CanonicalType->getAsRecordDecl()) {
56 if (!RD->isCompleteDefinition()) {
57 IncompleteType = true;
58 return false;
59 }
60 if (!VisitedRD.insert(Ptr: RD).second)
61 return false; // already visited
62 // Check all fields.
63 for (const FieldDecl *Field : RD->fields()) {
64 if (typeContainsPointer(T: Field->getType(), VisitedRD, IncompleteType))
65 return true;
66 }
67 // For C++ classes, also check base classes.
68 if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(Val: RD)) {
69 // Polymorphic types require a vptr.
70 if (CXXRD->isDynamicClass())
71 return true;
72 for (const CXXBaseSpecifier &Base : CXXRD->bases()) {
73 if (typeContainsPointer(T: Base.getType(), VisitedRD, IncompleteType))
74 return true;
75 }
76 }
77 }
78 return false;
79}
80
81/// Infer type from a simple sizeof expression.
82static QualType inferTypeFromSizeofExpr(const Expr *E) {
83 const Expr *Arg = E->IgnoreParenImpCasts();
84 if (const auto *UET = dyn_cast<UnaryExprOrTypeTraitExpr>(Val: Arg)) {
85 if (UET->getKind() == UETT_SizeOf) {
86 if (UET->isArgumentType())
87 return UET->getArgumentTypeInfo()->getType();
88 else
89 return UET->getArgumentExpr()->getType();
90 }
91 }
92 return QualType();
93}
94
95/// Infer type from an arithmetic expression involving a sizeof. For example:
96///
97/// malloc(sizeof(MyType) + padding); // infers 'MyType'
98/// malloc(sizeof(MyType) * 32); // infers 'MyType'
99/// malloc(32 * sizeof(MyType)); // infers 'MyType'
100/// malloc(sizeof(MyType) << 1); // infers 'MyType'
101/// ...
102///
103/// More complex arithmetic expressions are supported, but are a heuristic, e.g.
104/// when considering allocations for structs with flexible array members:
105///
106/// malloc(sizeof(HasFlexArray) + sizeof(int) * 32); // infers 'HasFlexArray'
107///
108static QualType inferPossibleTypeFromArithSizeofExpr(const Expr *E) {
109 const Expr *Arg = E->IgnoreParenImpCasts();
110 // The argument is a lone sizeof expression.
111 if (QualType T = inferTypeFromSizeofExpr(E: Arg); !T.isNull())
112 return T;
113 if (const auto *BO = dyn_cast<BinaryOperator>(Val: Arg)) {
114 // Argument is an arithmetic expression. Cover common arithmetic patterns
115 // involving sizeof.
116 switch (BO->getOpcode()) {
117 case BO_Add:
118 case BO_Div:
119 case BO_Mul:
120 case BO_Shl:
121 case BO_Shr:
122 case BO_Sub:
123 if (QualType T = inferPossibleTypeFromArithSizeofExpr(E: BO->getLHS());
124 !T.isNull())
125 return T;
126 if (QualType T = inferPossibleTypeFromArithSizeofExpr(E: BO->getRHS());
127 !T.isNull())
128 return T;
129 break;
130 default:
131 break;
132 }
133 }
134 return QualType();
135}
136
137/// If the expression E is a reference to a variable, infer the type from a
138/// variable's initializer if it contains a sizeof. Beware, this is a heuristic
139/// and ignores if a variable is later reassigned. For example:
140///
141/// size_t my_size = sizeof(MyType);
142/// void *x = malloc(my_size); // infers 'MyType'
143///
144static QualType inferPossibleTypeFromVarInitSizeofExpr(const Expr *E) {
145 const Expr *Arg = E->IgnoreParenImpCasts();
146 if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Arg)) {
147 if (const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) {
148 if (const Expr *Init = VD->getInit())
149 return inferPossibleTypeFromArithSizeofExpr(E: Init);
150 }
151 }
152 return QualType();
153}
154
155/// Deduces the allocated type by checking if the allocation call's result
156/// is immediately used in a cast expression. For example:
157///
158/// MyType *x = (MyType *)malloc(4096); // infers 'MyType'
159///
160static QualType inferPossibleTypeFromCastExpr(const CallExpr *CallE,
161 const CastExpr *CastE) {
162 if (!CastE)
163 return QualType();
164 QualType PtrType = CastE->getType();
165 if (PtrType->isPointerType())
166 return PtrType->getPointeeType();
167 return QualType();
168}
169
170QualType infer_alloc::inferPossibleType(const CallExpr *E,
171 const ASTContext &Ctx,
172 const CastExpr *CastE) {
173 QualType AllocType;
174 // First check arguments.
175 for (const Expr *Arg : E->arguments()) {
176 AllocType = inferPossibleTypeFromArithSizeofExpr(E: Arg);
177 if (AllocType.isNull())
178 AllocType = inferPossibleTypeFromVarInitSizeofExpr(E: Arg);
179 if (!AllocType.isNull())
180 break;
181 }
182 // Then check later casts.
183 if (AllocType.isNull())
184 AllocType = inferPossibleTypeFromCastExpr(CallE: E, CastE);
185 return AllocType;
186}
187
188std::optional<llvm::AllocTokenMetadata>
189infer_alloc::getAllocTokenMetadata(QualType T, const ASTContext &Ctx) {
190 llvm::AllocTokenMetadata ATMD;
191
192 // Get unique type name.
193 PrintingPolicy Policy(Ctx.getLangOpts());
194 Policy.SuppressTagKeyword = true;
195 Policy.FullyQualifiedName = true;
196 llvm::raw_svector_ostream TypeNameOS(ATMD.TypeName);
197 T.getCanonicalType().print(OS&: TypeNameOS, Policy);
198
199 // Check if QualType contains a pointer. Implements a simple DFS to
200 // recursively check if a type contains a pointer type.
201 llvm::SmallPtrSet<const RecordDecl *, 4> VisitedRD;
202 bool IncompleteType = false;
203 ATMD.ContainsPointer = typeContainsPointer(T, VisitedRD, IncompleteType);
204 if (!ATMD.ContainsPointer && IncompleteType)
205 return std::nullopt;
206
207 return ATMD;
208}
209