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