1//===- PointerFlowExtractor.cpp -------------------------------------------===//
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 "SSAFAnalysesCommon.h"
10#include "clang/AST/ASTContext.h"
11#include "clang/AST/ASTTypeTraits.h"
12#include "clang/AST/Decl.h"
13#include "clang/AST/DeclCXX.h"
14#include "clang/AST/Expr.h"
15#include "clang/AST/ExprCXX.h"
16#include "clang/AST/Stmt.h"
17#include "clang/AST/TypeBase.h"
18#include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h"
19#include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlow.h"
20#include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h"
21#include "clang/ScalableStaticAnalysis/Core/TUSummary/ExtractorRegistry.h"
22#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryBuilder.h"
23#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/STLFunctionalExtras.h"
26#include "llvm/Support/Error.h"
27#include <memory>
28
29namespace clang::ssaf {
30extern PointerFlowEntitySummary buildPointerFlowEntitySummary(EdgeSet Edges);
31} // namespace clang::ssaf
32
33namespace {
34using namespace clang;
35using namespace ssaf;
36
37class PointerFlowMatcher {
38public:
39 EdgeSet Results;
40 ASTContext &Ctx;
41 TUSummaryExtractor &Extractor;
42
43 PointerFlowMatcher(ASTContext &Ctx, TUSummaryExtractor &Extractor)
44 : Ctx(Ctx), Extractor(Extractor) {}
45
46 llvm::Error matches(const DynTypedNode &DynNode, const NamedDecl *RootDecl);
47
48 llvm::Error matchesInitializerList(const ValueDecl *Base,
49 const Expr *InitExpr,
50 unsigned ArrayElementIndirectLevel = 0);
51
52 llvm::Error matchesStmt(const Stmt *S, const NamedDecl *RootDecl);
53
54 llvm::Error matchesDecl(const Decl *D, const NamedDecl *RootDecl);
55
56private:
57 llvm::Error addEdges(Expected<DeclPointerLevelVec> &&LHS,
58 Expected<DeclPointerLevelVec> &&RHS);
59
60 Expected<DeclPointerLevelVec> toDPL(const Expr *N) const {
61 return translateDeclPointerLevel(E: N, Ctx, Extractor);
62 }
63
64 static DeclPointerLevel toDPL(const NamedDecl *N, bool IsRet = false) {
65 return createDeclPointerLevel(ND: N, IsFunRet: IsRet);
66 }
67
68 template <typename ParmsProvider, typename ArgsProvider>
69 llvm::Error matchesArgsWithParams(unsigned ArgIdxStart, ParmsProvider *PP,
70 ArgsProvider *AP) {
71 unsigned ArgIdx = ArgIdxStart;
72
73 for (unsigned ParmIdx = 0;
74 ParmIdx < PP->getNumParams() && ArgIdx < AP->getNumArgs();
75 ++ArgIdx, ++ParmIdx) {
76 if (const ParmVarDecl *PD = PP->getParamDecl(ParmIdx);
77 PD && hasPtrOrArrType(D: PD)) {
78 if (auto Err = addEdges(LHS: DeclPointerLevelVec{toDPL(N: PD)},
79 RHS: toDPL(AP->getArg(ArgIdx))))
80 return Err;
81 }
82 }
83 return llvm::Error::success();
84 }
85};
86
87llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevelVec> &&LHS,
88 Expected<DeclPointerLevelVec> &&RHS) {
89 if (!LHS && !RHS)
90 return llvm::joinErrors(E1: LHS.takeError(), E2: RHS.takeError());
91 if (!LHS)
92 return LHS.takeError();
93 if (!RHS)
94 return RHS.takeError();
95 if (RHS->empty())
96 return llvm::Error::success();
97
98 std::vector<DeclPointerLevelVec> LVecs, RVecs;
99
100 LVecs.reserve(n: LHS->size());
101 for (const auto &L : *LHS)
102 LVecs.push_back(x: elaborateHigherDeclPointerLevels(DPL: L));
103 RVecs.reserve(n: RHS->size());
104 for (const auto &R : *RHS)
105 RVecs.push_back(x: elaborateHigherDeclPointerLevels(DPL: R));
106
107 // Imagine an assignment from pointer q to p: 'p = q'. It encodes that if 'p'
108 // has some property, so must 'q'; moreover, if '*p/p[i]' has some property,
109 // so must '*q/q[i]' and so on. Therefore, for each edge '(a, n) -> (b, m)'
110 // that represents an explicitly spelled place in the source code, we also add
111 // '(a, n + 1) -> (b, m + 1)',
112 // '(a, n + 2) -> (b, m + 2)', ... continuing until either 'a' or 'b' reaches
113 // its maximum pointer level, whichever happens first.
114 //
115 // Note that type checking ensures that 'p' and 'q' have
116 // identical pointer levels, but '(a, n)' and '(b, m)' may have different
117 // upper bounds on their pointer levels, when, for example, 'q' is a
118 // reinterpret-cast expression, which can have different pointer level than
119 // its sub-expression.
120
121 for (const DeclPointerLevelVec &L : LVecs)
122 for (const DeclPointerLevelVec &R : RVecs)
123 for (const auto &[LDPL, RDPL] : llvm::zip(t: L, u: R)) {
124 auto LEPL = toEntityPointerLevel(DPL: LDPL, Ctx, Extractor);
125 if (!LEPL)
126 return LEPL.takeError();
127 auto REPL = toEntityPointerLevel(DPL: RDPL, Ctx, Extractor);
128 if (!REPL)
129 return REPL.takeError();
130 Results[*LEPL].insert(x: *REPL);
131 }
132 return llvm::Error::success();
133}
134
135/// Match and extract pointer flow.
136/// The extraction function 'XF' can be described by the following rules:
137///
138/// XF(l = r) := addEdges(toDPL(l), toDPL(r))
139/// XF(foo(a, b, ...)) := XF(Param_1 = a), XF(Param_2 = b), ...
140/// XF(return e;) := XF(FunRet = e), where 'FunRet' is the return
141/// entity of the enclosing
142/// function
143/// XF(ctor(a, ...) : x1(y1), ... {...})
144/// := XF(Param_1 = a), ...,
145/// XF(x1 = y1), ...,
146/// ctor's body will be visited separately.
147/// XF(T var = e) := XF(var = e)
148/// XF(T var = init-list) := see \ref
149/// PointerFlowMatcher::matchesInitializerList
150llvm::Error PointerFlowMatcher::matches(const DynTypedNode &DynNode,
151 const NamedDecl *RootDecl) {
152 if (const Stmt *S = DynNode.get<Stmt>())
153 return matchesStmt(S, RootDecl);
154 if (const Decl *D = DynNode.get<Decl>())
155 return matchesDecl(D, RootDecl);
156 return llvm::Error::success();
157}
158
159llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S,
160 const NamedDecl *RootDecl) {
161 // Match 'p = q' whenever it has pointer or array type:
162 if (const auto *BO = dyn_cast<BinaryOperator>(Val: S);
163 BO && BO->getOpcode() == BO_Assign && hasPtrOrArrType(E: BO)) {
164 return addEdges(LHS: toDPL(N: BO->getLHS()), RHS: toDPL(N: BO->getRHS()));
165 }
166
167 // Match arg-to-param passing (in CallExpr) for any pointer type argument:
168 if (const auto *CE = dyn_cast<CallExpr>(Val: S)) {
169 const FunctionDecl *FD = CE->getDirectCallee();
170
171 if (!FD)
172 return llvm::Error::success();
173
174 unsigned ArgIdx = 0;
175
176 if (isa<CXXOperatorCallExpr>(Val: CE))
177 if (auto *MD = dyn_cast<CXXMethodDecl>(Val: FD);
178 MD && !MD->isExplicitObjectMemberFunction())
179 ArgIdx = 1;
180 return matchesArgsWithParams(ArgIdxStart: ArgIdx, PP: FD, AP: CE);
181 }
182 // Match arg-to-param passing (in CXXConstructExpr) for any pointer type
183 // argument:
184 if (const auto *CCE = dyn_cast<CXXConstructExpr>(Val: S)) {
185 return matchesArgsWithParams(/*ArgIdxStart=*/0, PP: CCE->getConstructor(), AP: CCE);
186 }
187 if (const auto *RS = dyn_cast<ReturnStmt>(Val: S)) {
188 const Expr *RetExpr = RS->getRetValue();
189 if (!RetExpr || !hasPtrOrArrType(E: RetExpr))
190 return llvm::Error::success();
191 return addEdges(LHS: DeclPointerLevelVec{toDPL(N: RootDecl, IsRet: true)}, RHS: toDPL(N: RetExpr));
192 }
193 return llvm::Error::success();
194}
195
196llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D,
197 const NamedDecl *RootDecl) {
198 const Expr *InitExpr = nullptr;
199
200 if (const auto *VD = dyn_cast<ValueDecl>(Val: D)) {
201 if (const auto *Var = dyn_cast<VarDecl>(Val: VD))
202 InitExpr = Var->getInit();
203 if (const auto *Fd = dyn_cast<FieldDecl>(Val: VD))
204 InitExpr = Fd->getInClassInitializer();
205
206 // Match initializer-list:
207 if (auto *InitLst = dyn_cast_or_null<InitListExpr>(Val: InitExpr))
208 return matchesInitializerList(Base: VD, InitExpr: InitLst);
209
210 // Match initializers to variables/fields of a pointer type:
211 if (InitExpr && hasPtrOrArrType(D: VD))
212 return addEdges(LHS: DeclPointerLevelVec{toDPL(N: VD)}, RHS: toDPL(N: InitExpr));
213 }
214
215 // Match C++ constructor member-initializers:
216 if (const auto *CtorD = dyn_cast<CXXConstructorDecl>(Val: D)) {
217 for (auto *E : CtorD->inits()) {
218 if (E->isDelegatingInitializer())
219 return matches(DynNode: DynTypedNode::create(Node: *E->getInit()), RootDecl);
220 if (const FieldDecl *FD = E->getMember(); FD && hasPtrOrArrType(D: FD)) {
221 if (auto Err = addEdges(LHS: DeclPointerLevelVec{toDPL(N: E->getMember())},
222 RHS: toDPL(N: E->getInit())))
223 return Err;
224 }
225 }
226 }
227 return llvm::Error::success();
228}
229
230// Helper function for matchesInitializerList that handles record:
231llvm::Error matchInitializerListForRecordDecl(PointerFlowMatcher &Matcher,
232 const RecordDecl *RecordTy,
233 const InitListExpr *ILE) {
234 if (auto *CXXRD = dyn_cast<CXXRecordDecl>(Val: RecordTy))
235 if (CXXRD->getNumBases() != 0) {
236 // FIXME: support this:
237 return makeErrAtNode(
238 Ctx&: Matcher.Ctx, N: ILE,
239 Fmt: "attempt to create pointer assignment edges between "
240 "CXXRecordDecls with base classes and initializer-lists");
241 }
242 // Handle union:
243 if (RecordTy->isUnion()) {
244 auto *InitField = ILE->getInitializedFieldInUnion();
245
246 if (!InitField || ILE->inits().empty())
247 return llvm::Error::success();
248 return Matcher.matchesInitializerList(Base: InitField, InitExpr: ILE->getInit(Init: 0));
249 }
250 // Handle struct/class:
251 ILE = ILE->isSemanticForm() ? ILE : ILE->getSemanticForm();
252
253 auto FieldIter = RecordTy->field_begin();
254
255 assert(RecordTy->getNumFields() >= ILE->getNumInits());
256 for (auto *Init : ILE->inits())
257 if (auto Err = Matcher.matchesInitializerList(Base: *(FieldIter++), InitExpr: Init))
258 return Err;
259 return llvm::Error::success();
260}
261
262// Helper function for matchesInitializerList that handles array:
263llvm::Error matchInitializerListForArray(PointerFlowMatcher &Matcher,
264 const ValueDecl *Array,
265 const InitListExpr *ILE,
266 unsigned ArrayIndirectLevel = 0) {
267 for (auto *E : ILE->inits())
268 if (auto Err =
269 Matcher.matchesInitializerList(Base: Array, InitExpr: E, ArrayElementIndirectLevel: ArrayIndirectLevel + 1))
270 return Err;
271 return llvm::Error::success();
272}
273
274/// Match initializer lists of the form 'Var = {a, b, c, ...}':
275///
276/// If 'Var' is a struct/union:
277/// XF(Var = {a, b, c, ...}) := XF(Var.field_1 = a)
278/// XF(Var.field_2 = b)
279/// ...
280/// If 'Var' is an array:
281/// XF(Var = {a, b, c, ...}) := XF(*Var = a)
282/// XF(*Var = b)
283/// ...
284///
285/// The process is recursive: 'a', 'b', 'c', ... may themselves be
286/// initializer lists. We therefore use \p ArrayElementIndirectLevel to keep
287/// track of the pointer level of the left-hand side.
288llvm::Error
289PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base,
290 const Expr *InitExpr,
291 unsigned ArrayElementIndirectLevel) {
292 const InitListExpr *ILE = dyn_cast<InitListExpr>(Val: InitExpr);
293
294 if (!ILE) {
295 if (!hasPtrOrArrType(E: InitExpr))
296 return llvm::Error::success();
297
298 auto BaseDPL = toDPL(N: Base);
299 // Apply ArrayElementIndirectLevel to BaseDPL
300 BaseDPL.PointerLevel += ArrayElementIndirectLevel;
301 return addEdges(LHS: DeclPointerLevelVec{BaseDPL}, RHS: toDPL(N: InitExpr));
302 }
303 // Note that `Base`'s type is NOT the real LHS type when
304 // ArrayElementIndirectLevel > 0:
305 QualType Type = InitExpr->getType();
306
307 if (auto *RD = Type->getAsRecordDecl())
308 return matchInitializerListForRecordDecl(Matcher&: *this, RecordTy: RD, ILE);
309 if (Type->isArrayType())
310 return matchInitializerListForArray(Matcher&: *this, Array: Base, ILE,
311 ArrayIndirectLevel: ArrayElementIndirectLevel);
312
313 // Must be the case of using a initializer-list for a scalar.
314 // The initializer-list can be either singleton or empty:
315 if (ILE->getNumInits() == 0)
316 return llvm::Error::success();
317 return matchesInitializerList(Base, InitExpr: ILE->getInit(Init: 0));
318}
319
320class PointerFlowTUSummaryExtractor : public TUSummaryExtractor {
321public:
322 using TUSummaryExtractor::TUSummaryExtractor;
323
324 /// \return a non-null unique pointer to a PointerFlowEntitySummary
325 std::unique_ptr<PointerFlowEntitySummary>
326 extractEntitySummary(const std::vector<const NamedDecl *> &ContributorDecls,
327 ASTContext &Ctx, TUSummaryExtractor &Extractor) {
328 PointerFlowMatcher Matcher(Ctx, Extractor);
329
330 for (const auto *Contrib : ContributorDecls) {
331 auto MatchAction = [&Matcher, Contrib](const DynTypedNode &Node) {
332 if (auto Err = Matcher.matches(DynNode: Node, RootDecl: Contrib))
333 logWarningFromError(Err: std::move(Err));
334 };
335
336 findMatchesIn(Contributor: Contrib, MatchActionRef: MatchAction);
337 }
338 return std::make_unique<PointerFlowEntitySummary>(
339 args: buildPointerFlowEntitySummary(Edges: std::move(Matcher.Results)));
340 }
341
342 void HandleTranslationUnit(ASTContext &Ctx) override {
343 extractAndAddSummaries(
344 Extractor&: *this, Builder&: SummaryBuilder, Ctx,
345 ExtractFn: [&](const std::vector<const NamedDecl *> &Decls) {
346 return extractEntitySummary(ContributorDecls: Decls, Ctx, Extractor&: *this);
347 },
348 ExtractorName: "PointerFlow");
349 }
350};
351} // namespace
352
353namespace clang::ssaf {
354// NOLINTNEXTLINE(misc-use-internal-linkage)
355volatile int PointerFlowExtractorAnchorSource = 0;
356} // namespace clang::ssaf
357
358static TUSummaryExtractorRegistry::Add<PointerFlowTUSummaryExtractor>
359 RegisterExtractor(PointerFlowEntitySummary::Name,
360 "Extract pointer flow information");
361