1//===- EntityPointerLevel.cpp -----------------------------------*- C++ -*-===//
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#include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h"
10#include "SSAFAnalysesCommon.h"
11#include "clang/AST/ASTContext.h"
12#include "clang/AST/Decl.h"
13#include "clang/AST/Expr.h"
14#include "clang/AST/ExprCXX.h"
15#include "clang/AST/StmtVisitor.h"
16#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h"
17#include <optional>
18
19using namespace clang;
20using namespace ssaf;
21
22namespace clang::ssaf {
23// Translate a pointer type expression 'E' to a (set of) EntityPointerLevel(s)
24// associated with the declared type of the base address of `E`. If the base
25// address of `E` is not associated with an entity, the translation result is an
26// empty set.
27//
28// The translation is a process of traversing into the pointer 'E' until its
29// base address can be represented by an entity, with the number of dereferences
30// tracked by incrementing the pointer level. Naturally, taking address of, as
31// the inverse operation of dereference, is tracked by decrementing the pointer
32// level.
33//
34// For example, suppose there are pointers and arrays declared as
35// int *ptr, **p1, **p2;
36// int arr[10][10];
37// , the translation of expressions involving these base addresses will be:
38// Translate(ptr + 5) -> {(ptr, 1)}
39// Translate(arr[5]) -> {(arr, 2)}
40// Translate(cond ? p1[5] : p2) -> {(p1, 2), (p2, 1)}
41// Translate(&arr[5]) -> {(arr, 1)}
42class EntityPointerLevelTranslator
43 : ConstStmtVisitor<EntityPointerLevelTranslator,
44 Expected<EntityPointerLevelSet>> {
45 friend class StmtVisitorBase;
46
47 // Fallback method for all unsupported expression kind:
48 Expected<EntityPointerLevelSet> fallback(const Stmt *S) {
49 // Report an error/warning (at least in debug mode) for any unsupported kind
50 // of pointer/array typed expression, because we want to understand every
51 // pointer/array expression. But for non-pointer/array typed expressions, we
52 // could silently ignore unsupported kinds. This translator visits
53 // non-pointer/array typed expressions because of address-of expressions.
54 if (const Expr *E = dyn_cast<Expr>(Val: S); E && hasPtrOrArrType(E))
55 return makeErrAtNode(Ctx, N: E,
56 Fmt: "attempt to translate %s to EntityPointerLevels",
57 Args: E->getStmtClassName());
58 return EntityPointerLevelSet{};
59 }
60
61 Expected<EntityPointerLevel>
62 createEntityPointerLevelFor(const NamedDecl *ND) {
63 std::optional<EntityId> Id = Extractor.addEntity(D: ND);
64 if (!Id)
65 return makeErrAtNode(Ctx, N: ND, Fmt: "failed to create EntityId for %s",
66 Args: ND->getDeclKindName());
67 return EntityPointerLevel{buildEntityPointerLevel(*Id, 1)};
68 }
69
70 Expected<EntityPointerLevel>
71 createEntityPointerLevelForReturn(const FunctionDecl *FD) {
72 std::optional<EntityId> Id = Extractor.addEntityForReturn(FD);
73 if (!Id) {
74 return makeErrAtNode(Ctx, N: FD, Fmt: "failed to create EntityId for function %s",
75 Args: cast<NamedDecl>(Val: FD)->getNameAsString().c_str());
76 }
77 return EntityPointerLevel{buildEntityPointerLevel(*Id, 1)};
78 }
79
80 // The common helper function for Translate(*base):
81 // Translate(*base) -> Translate(base) with .pointerLevel + 1
82 Expected<EntityPointerLevelSet> translateDereferencePointer(const Expr *Ptr) {
83 assert(hasPtrOrArrType(Ptr));
84
85 Expected<EntityPointerLevelSet> SubResult = Visit(S: Ptr);
86 if (!SubResult)
87 return SubResult.takeError();
88
89 auto Incremented = llvm::map_range(C&: *SubResult, F: incrementPointerLevel);
90 return EntityPointerLevelSet{Incremented.begin(), Incremented.end()};
91 }
92
93 TUSummaryExtractor &Extractor;
94 ASTContext &Ctx;
95
96public:
97 EntityPointerLevelTranslator(TUSummaryExtractor &Extractor, ASTContext &Ctx)
98 : Extractor(Extractor), Ctx(Ctx) {}
99
100 Expected<EntityPointerLevelSet> translate(const Expr *E) { return Visit(S: E); }
101 Expected<EntityPointerLevel> translate(const NamedDecl *D, bool IsRet) {
102 if (!IsRet)
103 return createEntityPointerLevelFor(ND: D);
104
105 if (const auto *FD = dyn_cast<FunctionDecl>(Val: D))
106 return createEntityPointerLevelForReturn(FD);
107
108 return makeErrAtNode(Ctx, N: D, Fmt: "attempt to get entity for return of %s",
109 Args: D->getDeclKindName());
110 }
111
112 static EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E) {
113 return EntityPointerLevel({E.getEntity(), E.getPointerLevel() + 1});
114 }
115
116 static EntityPointerLevel decrementPointerLevel(const EntityPointerLevel &E) {
117 assert(E.getPointerLevel() > 0);
118 return EntityPointerLevel({E.getEntity(), E.getPointerLevel() - 1});
119 }
120
121private:
122 Expected<EntityPointerLevelSet> VisitStmt(const Stmt *E) {
123 return fallback(S: E);
124 }
125
126 // Translate(base + x) -> Translate(base)
127 // Translate(x + base) -> Translate(base)
128 // Translate(base - x) -> Translate(base)
129 // Translate(base {+=, -=, =} x) -> Translate(base)
130 // Translate(x, base) -> Translate(base)
131 Expected<EntityPointerLevelSet> VisitBinaryOperator(const BinaryOperator *E) {
132 switch (E->getOpcode()) {
133 case clang::BO_Add:
134 if (hasPtrOrArrType(E: E->getLHS()))
135 return Visit(S: E->getLHS());
136 return Visit(S: E->getRHS());
137 case clang::BO_Sub:
138 case clang::BO_AddAssign:
139 case clang::BO_SubAssign:
140 case clang::BO_Assign:
141 return Visit(S: E->getLHS());
142 case clang::BO_Comma:
143 return Visit(S: E->getRHS());
144 default:
145 return fallback(S: E);
146 }
147 }
148
149 // Translate({++, --}base) -> Translate(base)
150 // Translate(base{++, --}) -> Translate(base)
151 // Translate(*base) -> Translate(base) with .pointerLevel += 1
152 // Translate(&base) -> {}, if Translate(base) is {}
153 // -> Translate(base) with .pointerLevel -= 1
154 // Translate(+base) -> Translate(base)
155 Expected<EntityPointerLevelSet> VisitUnaryOperator(const UnaryOperator *E) {
156 switch (E->getOpcode()) {
157 case clang::UO_PostInc:
158 case clang::UO_PostDec:
159 case clang::UO_PreInc:
160 case clang::UO_PreDec:
161 return Visit(S: E->getSubExpr());
162 case clang::UO_AddrOf: {
163 Expected<EntityPointerLevelSet> SubResult = Visit(S: E->getSubExpr());
164 if (!SubResult)
165 return SubResult.takeError();
166
167 auto Decremented = llvm::map_range(C&: *SubResult, F: decrementPointerLevel);
168 return EntityPointerLevelSet{Decremented.begin(), Decremented.end()};
169 }
170 case clang::UO_Deref:
171 return translateDereferencePointer(Ptr: E->getSubExpr());
172 case clang::UO_Plus:
173 return Visit(S: E->getSubExpr());
174 default:
175 return fallback(S: E);
176 }
177 }
178
179 // Translate((T*)base) -> Translate(base) if base has pointer type
180 // -> {} otherwise
181 Expected<EntityPointerLevelSet> VisitCastExpr(const CastExpr *E) {
182 if (hasPtrOrArrType(E: E->getSubExpr()))
183 return Visit(S: E->getSubExpr());
184 return EntityPointerLevelSet{};
185 }
186
187 // Translate(f(...)) -> {} if it is an indirect call
188 // -> {(f_return, 1)}, otherwise
189 Expected<EntityPointerLevelSet> VisitCallExpr(const CallExpr *E) {
190 if (auto *FD = E->getDirectCallee()) {
191 if (auto ReturnId = Extractor.addEntityForReturn(FD))
192 return EntityPointerLevelSet{buildEntityPointerLevel(*ReturnId, 1)};
193 }
194 return EntityPointerLevelSet{};
195 }
196
197 // Translate(base[x]) -> Translate(*base)
198 Expected<EntityPointerLevelSet>
199 VisitArraySubscriptExpr(const ArraySubscriptExpr *E) {
200 return translateDereferencePointer(Ptr: E->getBase());
201 }
202
203 // Translate(cond ? base1 : base2) := Translate(base1) U Translate(base2)
204 Expected<EntityPointerLevelSet>
205 VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
206 Expected<EntityPointerLevelSet> ReT = Visit(S: E->getTrueExpr());
207 Expected<EntityPointerLevelSet> ReF = Visit(S: E->getFalseExpr());
208
209 if (ReT && ReF) {
210 ReT->insert(first: ReF->begin(), last: ReF->end());
211 return ReT;
212 }
213 if (!ReF && !ReT)
214 return llvm::joinErrors(E1: ReT.takeError(), E2: ReF.takeError());
215 if (!ReF)
216 return ReF.takeError();
217 return ReT.takeError();
218 }
219
220 Expected<EntityPointerLevelSet> VisitParenExpr(const ParenExpr *E) {
221 return Visit(S: E->getSubExpr());
222 }
223
224 // Translate("string-literal") -> {} // no entity involved
225 Expected<EntityPointerLevelSet> VisitStringLiteral(const StringLiteral *E) {
226 return EntityPointerLevelSet{};
227 }
228
229 // Translate(predefined-expr) -> {} // treated the same as string literals
230 Expected<EntityPointerLevelSet> VisitPredefinedExpr(const PredefinedExpr *E) {
231 return EntityPointerLevelSet{};
232 }
233
234 // Translate(integer-literal) -> {} // no entity involved
235 Expected<EntityPointerLevelSet> VisitIntegerLiteral(const IntegerLiteral *E) {
236 return EntityPointerLevelSet{};
237 }
238
239 // Translate(DRE) -> {(Decl, 1)}
240 Expected<EntityPointerLevelSet> VisitDeclRefExpr(const DeclRefExpr *E) {
241 auto Res = createEntityPointerLevelFor(ND: E->getDecl());
242 if (!Res)
243 return Res.takeError();
244 return EntityPointerLevelSet{*Res};
245 }
246
247 // Translate({., ->}f) -> {(MemberDecl, 1)}
248 Expected<EntityPointerLevelSet> VisitMemberExpr(const MemberExpr *E) {
249 auto Res = createEntityPointerLevelFor(ND: E->getMemberDecl());
250 if (!Res)
251 return Res.takeError();
252 return EntityPointerLevelSet{*Res};
253 }
254
255 // Unwrap CXXDefaultArgExpr
256 Expected<EntityPointerLevelSet>
257 VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E) {
258 return Visit(S: E->getExpr());
259 }
260
261 // Unwrap OpaqueValueExpr
262 Expected<EntityPointerLevelSet>
263 VisitOpaqueValueExpr(const OpaqueValueExpr *S) {
264 return Visit(S: S->getSourceExpr());
265 }
266
267 // Unwrap ExprWithCleanups
268 Expected<EntityPointerLevelSet>
269 VisitExprWithCleanups(const ExprWithCleanups *S) {
270 return Visit(S: S->getSubExpr());
271 }
272
273 // Unwrap MaterializeTemporaryExpr
274 Expected<EntityPointerLevelSet>
275 VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
276 return Visit(S: S->getSubExpr());
277 }
278
279 // Unwrap CXXDefaultInitExpr
280 Expected<EntityPointerLevelSet>
281 VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E) {
282 return Visit(S: E->getExpr());
283 }
284
285 // Translate(`nullptr`) -> {}
286 Expected<EntityPointerLevelSet>
287 VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *S) {
288 return EntityPointerLevelSet{};
289 }
290
291 // Translate(`this`) -> {}
292 Expected<EntityPointerLevelSet> VisitCXXThisExpr(const CXXThisExpr *S) {
293 return EntityPointerLevelSet{};
294 }
295
296 // Translate(`new`/`new [*]`) -> {}
297 Expected<EntityPointerLevelSet> VisitCXXNewExpr(const CXXNewExpr *S) {
298 return EntityPointerLevelSet{};
299 }
300
301 // ImplicitValueInitExpr, for raw pointer type,
302 // evaluates to a compile-time constant zero (or null). So no EPL in the
303 // result.
304 Expected<EntityPointerLevelSet>
305 VisitImplicitValueInitExpr(const ImplicitValueInitExpr *S) {
306 return EntityPointerLevelSet{};
307 }
308
309 // The InitListExpr must be an empty or singleton list that
310 // initializes a pointer scalar. Other cases are unexpected thus an error.
311 Expected<EntityPointerLevelSet> VisitInitListExpr(const InitListExpr *E) {
312 if (E->getNumInits() < 1)
313 return EntityPointerLevelSet{};
314 if (E->getType()->isPointerType())
315 return Visit(S: E->getInit(Init: 0));
316 return llvm::createStringError(
317 Fmt: "Cannot translate an InitListExpr to EntityPointerLevels if it is not "
318 "an empty or singleton list that initializes a pointer scalar");
319 }
320
321 // Clang may default initializes an array with a CXXConstructExpr. Fallback on
322 // other cases, if they exist.
323 // When a CXXConstructExpr has an array type, clang is initializing an array
324 // of class-type objects with default values. In this case, no entity is
325 // associated with the initializer.
326 Expected<EntityPointerLevelSet>
327 VisitCXXConstructExpr(const CXXConstructExpr *E) {
328 if (E->getType()->isArrayType()) {
329 return EntityPointerLevelSet{};
330 }
331 return fallback(S: E);
332 }
333
334 // No entity is associated with a CXXScalarValueInitExpr:
335 Expected<EntityPointerLevelSet>
336 VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E) {
337 return EntityPointerLevelSet{};
338 }
339};
340} // namespace clang::ssaf
341
342Expected<EntityPointerLevelSet>
343clang::ssaf::translateEntityPointerLevel(const Expr *E, ASTContext &Ctx,
344 TUSummaryExtractor &Extractor) {
345 EntityPointerLevelTranslator Translator(Extractor, Ctx);
346
347 return Translator.translate(E);
348}
349
350/// Create an EntityPointerLevel from a ValueDecl of a pointer type.
351Expected<EntityPointerLevel> clang::ssaf::createEntityPointerLevel(
352 const NamedDecl *ND, TUSummaryExtractor &Extractor, bool IsFunRet) {
353 EntityPointerLevelTranslator Translator(Extractor, ND->getASTContext());
354
355 return Translator.translate(D: ND, IsRet: IsFunRet);
356}
357
358EntityPointerLevel
359clang::ssaf::incrementPointerLevel(const EntityPointerLevel &E) {
360 return EntityPointerLevelTranslator::incrementPointerLevel(E);
361}
362
363EntityPointerLevel clang::ssaf::buildEntityPointerLevel(EntityId Id,
364 unsigned PtrLv) {
365 return EntityPointerLevel({Id, PtrLv});
366}
367