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