Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::AEWTO Class Reference

#include <AEWTO.h>

Public Types

typedef SCCDetection< CallGraph * > CallGraphSCC

Public Member Functions

 AEWTO (SVFIR *pag, ICFG *icfg)
virtual ~AEWTO ()
AndersenWaveDiff * getPointerAnalysis () const
 Accessors for Andersen's results.
CallGraph * getCallGraph () const
CallGraphSCC * getCallGraphSCC () const
void initWTO ()
 Build WTO for each function using call graph SCC.
const Map< const FunObjVar *, const ICFGWTO * > & getFuncToWTO () const
 Accessors for WTO data.
void initCycleValVars ()
const Set< const ValVar * > getCycleValVars (const ICFGCycleWTO *cycle) const

Private Attributes

SVFIR * svfir
ICFG * icfg
AndersenWaveDiff * pta
CallGraph * callGraph
CallGraphSCC * callGraphSCC
Map< const FunObjVar *, const ICFGWTO * > funcToWTO
Map< const ICFGCycleWTO *, Set< const ValVar * > > cycleToValVars

Detailed Description

Definition at line 47 of file AEWTO.h.

Member Typedef Documentation

◆ CallGraphSCC

Definition at line 50 of file AEWTO.h.

Constructor & Destructor Documentation

◆ AEWTO()

AEWTO::AEWTO ( SVFIR * pag,
ICFG * icfg )

Definition at line 37 of file AEWTO.cpp.

38 : svfir(pag), icfg(icfg), pta(nullptr), callGraph(nullptr), callGraphSCC(nullptr)
39{
41 callGraph = pta->getCallGraph();
42 callGraphSCC = pta->getCallGraphSCC();
43}
ICFG * icfg
Definition AEWTO.h:91
SVFIR * svfir
Definition AEWTO.h:90
AndersenWaveDiff * pta
Definition AEWTO.h:92
CallGraph * callGraph
Definition AEWTO.h:93
CallGraphSCC * callGraphSCC
Definition AEWTO.h:94
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
Definition Andersen.h:430

◆ ~AEWTO()

AEWTO::~AEWTO ( )
virtual

Definition at line 45 of file AEWTO.cpp.

46{
47 for (auto& [func, wto] : funcToWTO)
48 delete wto;
49}
Map< const FunObjVar *, const ICFGWTO * > funcToWTO
Definition AEWTO.h:96

Member Function Documentation

◆ getCallGraph()

CallGraph * SVF::AEWTO::getCallGraph ( ) const
inline

Definition at line 60 of file AEWTO.h.

61 {
62 return callGraph;
63 }

◆ getCallGraphSCC()

CallGraphSCC * SVF::AEWTO::getCallGraphSCC ( ) const
inline

Definition at line 64 of file AEWTO.h.

65 {
66 return callGraphSCC;
67 }

◆ getCycleValVars()

const Set< const ValVar * > SVF::AEWTO::getCycleValVars ( const ICFGCycleWTO * cycle) const
inline

Look up the ValVar id set of a WTO cycle. Returns nullptr if the cycle is unknown (e.g. dense mode, where the map is never built).

Definition at line 83 of file AEWTO.h.

84 {
85 auto it = cycleToValVars.find(cycle);
86 return it == cycleToValVars.end() ? Set<const ValVar*>() : it->second;
87 }
Map< const ICFGCycleWTO *, Set< const ValVar * > > cycleToValVars
Definition AEWTO.h:101
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51

◆ getFuncToWTO()

const Map< const FunObjVar *, const ICFGWTO * > & SVF::AEWTO::getFuncToWTO ( ) const
inline

Accessors for WTO data.

Definition at line 72 of file AEWTO.h.

73 {
74 return funcToWTO;
75 }

◆ getPointerAnalysis()

AndersenWaveDiff * SVF::AEWTO::getPointerAnalysis ( ) const
inline

Accessors for Andersen's results.

Definition at line 56 of file AEWTO.h.

57 {
58 return pta;
59 }

◆ initCycleValVars()

void AEWTO::initCycleValVars ( )

Walk every function's WTO and populate cycleToValVars bottom-up. Called once right after initWTO(). No-op in dense mode.

Definition at line 125 of file AEWTO.cpp.

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.
187 if (const FunEntryICFGNode* fe = SVFUtil::dyn_cast<FunEntryICFGNode>(node))
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
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
WTOCycle< ICFG > ICFGCycleWTO
Definition ICFGWTO.h:49
WTONode< ICFG > ICFGSingletonWTO
Definition ICFGWTO.h:48
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
WTOComponent< ICFG > ICFGWTOComp
Definition ICFGWTO.h:47

◆ initWTO()

void AEWTO::initWTO ( )

Build WTO for each function using call graph SCC.

Definition at line 51 of file AEWTO.cpp.

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}
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
u32_t NodeID
Definition GeneralType.h:76
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Definition GeneralType.h:56

Member Data Documentation

◆ callGraph

CallGraph* SVF::AEWTO::callGraph
private

Definition at line 93 of file AEWTO.h.

◆ callGraphSCC

CallGraphSCC* SVF::AEWTO::callGraphSCC
private

Definition at line 94 of file AEWTO.h.

◆ cycleToValVars

Map<const ICFGCycleWTO*, Set<const ValVar*> > SVF::AEWTO::cycleToValVars
private

Pre-computed (semi-sparse only) map from a WTO cycle to the IDs of every ValVar whose def-site is inside that cycle, including all nested sub-cycles. Empty in dense mode.

Definition at line 101 of file AEWTO.h.

◆ funcToWTO

Map<const FunObjVar*, const ICFGWTO*> SVF::AEWTO::funcToWTO
private

Definition at line 96 of file AEWTO.h.

◆ icfg

ICFG* SVF::AEWTO::icfg
private

Definition at line 91 of file AEWTO.h.

◆ pta

AndersenWaveDiff* SVF::AEWTO::pta
private

Definition at line 92 of file AEWTO.h.

◆ svfir

SVFIR* SVF::AEWTO::svfir
private

Definition at line 90 of file AEWTO.h.


The documentation for this class was generated from the following files: