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