Static Value-Flow Analysis
Loading...
Searching...
No Matches
AEWTO.cpp
Go to the documentation of this file.
1//===- AEWTO.cpp -- WTO + pointer-analysis prep for Abstract Interpretation ---//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===----------------------------------------------------------------------===//
22
23/*
24 * AEWTO.cpp
25 *
26 * Created on: Feb 25, 2026
27 * Author: Jiawei Wang
28 */
29
30#include "AE/Svfexe/AEWTO.h"
32#include "Util/Options.h"
33#include "Util/WorkList.h"
34
35using namespace SVF;
36
38 : svfir(pag), icfg(icfg), pta(nullptr), callGraph(nullptr), callGraphSCC(nullptr)
39{
41 callGraph = pta->getCallGraph();
42 callGraphSCC = pta->getCallGraphSCC();
43}
44
46{
47 for (auto& [func, wto] : funcToWTO)
48 delete wto;
49}
50
52{
53 callGraphSCC->find();
54
55 // In no-main mode, an SCC with no outside caller is an analysis entry.
56 // Choose one function per SCC, preferring main when it is present.
58 Set<NodeID> nonRootSCCs;
59 for (auto it = callGraph->begin(); it != callGraph->end(); ++it)
60 {
61 const CallGraphNode* node = it->second;
62 const FunObjVar* fun = node->getFunction();
63 if (fun->isDeclaration())
64 continue;
65 const NodeID rep = callGraphSCC->repNode(node->getId());
66 if (!rootEntry.count(rep) || SVFUtil::isProgEntryFunction(fun))
67 rootEntry[rep] = fun;
68 for (const auto* edge : node->getInEdges())
69 {
70 if (callGraphSCC->repNode(edge->getSrcID()) != rep)
71 nonRootSCCs.insert(rep);
72 }
73 }
74
75 for (auto it = callGraph->begin(); it != callGraph->end(); it++)
76 {
77 const FunObjVar *fun = it->second->getFunction();
78 if (fun->isDeclaration())
79 continue;
80
81 NodeID repNodeId = callGraphSCC->repNode(it->second->getId());
82 auto cgSCCNodes = callGraphSCC->subNodes(repNodeId);
83
84 bool isEntry = false;
85 if (it->second->getInEdges().empty())
86 isEntry = true;
87 for (auto inEdge: it->second->getInEdges())
88 {
89 NodeID srcNodeId = inEdge->getSrcID();
90 if (!cgSCCNodes.test(srcNodeId))
91 isEntry = true;
92 }
93 // A root recursive SCC (e.g. nDPI's bt_decode in no-main mode) has
94 // internal callers but no outside caller, so neither check above
95 // selects an entry. Build its WTO too, or handleFunction will fail
96 // with "Missing WTO for function". In contrast, main -> foo with
97 // foo -> foo is already covered by the outside call from main.
98 if (!nonRootSCCs.count(repNodeId) && rootEntry[repNodeId] == fun)
99 isEntry = true;
100
101 if (isEntry)
102 {
103 Set<const FunObjVar*> funcScc;
104 for (const auto& node: cgSCCNodes)
105 {
106 funcScc.insert(callGraph->getGNode(node)->getFunction());
107 }
108 ICFGWTO* iwto = new ICFGWTO(icfg->getFunEntryICFGNode(fun), funcScc);
109 iwto->init();
110 funcToWTO[it->second->getFunction()] = iwto;
111 }
112 }
113
114}
115
116// ---------------------------------------------------------------------------
117// Semi-sparse cycle ValVar set precomputation
118// ---------------------------------------------------------------------------
119//
120// In semi-sparse mode, ValVars live at their def-sites and do not flow
121// through the cycle-head merge. handleLoopOrRecursion uses the cycle's
122// ValVar set to gather/scatter ValVars around each widening iteration.
123// We precompute the set once per cycle here so the main loop does no work.
124
126{
127 // Step 1: Collect all cycles in top-down order using a stack-based DFS,
128 // then reverse to get bottom-up order (inner cycles before outer ones).
129 std::vector<const ICFGCycleWTO*> cycles;
130 {
131 std::vector<const ICFGWTOComp*> stack;
132 for (const auto& kv : funcToWTO)
133 {
134 if (!kv.second) continue;
135 for (const ICFGWTOComp* comp : kv.second->getWTOComponents())
136 stack.push_back(comp);
137 }
138 while (!stack.empty())
139 {
140 const ICFGWTOComp* comp = stack.back();
141 stack.pop_back();
142 if (const ICFGCycleWTO* cycle = SVFUtil::dyn_cast<ICFGCycleWTO>(comp))
143 {
144 for (const ICFGWTOComp* sub : cycle->getWTOComponents())
145 stack.push_back(sub);
146 cycles.push_back(cycle);
147 }
148 }
149 std::reverse(cycles.begin(), cycles.end());
150 }
151
152 // Step 2: Build ValVar sets bottom-up. Inner cycles are already in the
153 // map when we reach their enclosing cycle.
154 for (const ICFGCycleWTO* cycle : cycles)
155 {
157
158 // Gather every ICFG node in this cycle (head + body singletons).
159 // For nested sub-cycles, merge their already-computed sets instead.
160 std::vector<const ICFGNode*> nodes;
161 nodes.push_back(cycle->head()->getICFGNode());
162 for (const ICFGWTOComp* comp : cycle->getWTOComponents())
163 {
165 nodes.push_back(s->getICFGNode());
166 else if (const ICFGCycleWTO* sub = SVFUtil::dyn_cast<ICFGCycleWTO>(comp))
167 out.insert(cycleToValVars[sub].begin(), cycleToValVars[sub].end());
168 }
169
170 // For each node, collect LHS ValVar IDs from its statements.
171 for (const ICFGNode* node : nodes)
172 {
173 for (const SVFStmt* stmt : node->getSVFStmts())
174 {
175 const ValVar* lhs = nullptr;
176 if (const AssignStmt* a = SVFUtil::dyn_cast<AssignStmt>(stmt))
177 lhs = SVFUtil::dyn_cast<ValVar>(a->getLHSVar());
178 else if (const MultiOpndStmt* m = SVFUtil::dyn_cast<MultiOpndStmt>(stmt))
179 lhs = m->getRes();
180 if (lhs)
181 out.insert(lhs);
182 }
183 // FunEntryICFGNode owns ArgValVars (formal parameters) that have
184 // no defining stmt at the entry — the CallPE lives on the caller
185 // side. For recursive cycles whose head is a FunEntry, we need
186 // these IDs so widening/narrowing observes them across iterations.
188 {
189 for (const SVFVar* fp : fe->getFormalParms())
190 if (const ValVar* v = SVFUtil::dyn_cast<ValVar>(fp))
191 out.insert(v);
192 }
193 }
194 }
195}
PRIVATE Xlinker stack
cJSON * a
Definition cJSON.cpp:2560
ICFG * icfg
Definition AEWTO.h:91
AEWTO(SVFIR *pag, ICFG *icfg)
Definition AEWTO.cpp:37
void initCycleValVars()
Definition AEWTO.cpp:125
SVFIR * svfir
Definition AEWTO.h:90
AndersenWaveDiff * pta
Definition AEWTO.h:92
virtual ~AEWTO()
Definition AEWTO.cpp:45
CallGraph * callGraph
Definition AEWTO.h:93
Map< const ICFGCycleWTO *, Set< const ValVar * > > cycleToValVars
Definition AEWTO.h:101
CallGraphSCC * callGraphSCC
Definition AEWTO.h:94
Map< const FunObjVar *, const ICFGWTO * > funcToWTO
Definition AEWTO.h:96
void initWTO()
Build WTO for each function using call graph SCC.
Definition AEWTO.cpp:51
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
Definition Andersen.h:430
const FunObjVar * getFunction() const
Get function of this call node.
Definition CallGraph.h:191
virtual const FunObjVar * getFunction() const
Get containing function, or null for globals/constants.
bool isDeclaration() const
const GEdgeSetTy & getInEdges() const
NodeID getId() const
Get ID.
Definition SVFValue.h:158
void init()
Definition WTO.h:672
bool isProgEntryFunction(const FunObjVar *)
Program entry function e.g. main.
Definition SVFUtil.cpp:531
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405
for isBitcode
Definition BasicTypes.h:70
WTOCycle< ICFG > ICFGCycleWTO
Definition ICFGWTO.h:49
u32_t NodeID
Definition GeneralType.h:76
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
WTONode< ICFG > ICFGSingletonWTO
Definition ICFGWTO.h:48
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Definition GeneralType.h:56
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
WTOComponent< ICFG > ICFGWTOComp
Definition ICFGWTO.h:47