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

#include <CSC.h>

Public Types

typedef Map< NodeID, NodeID > IdToIdMap
typedef FILOWorkList< NodeID > WorkStack
typedef IdToIdMap::iterator iterator

Public Member Functions

 CSC (ConstraintGraph *g, CGSCC *c)
void find (NodeStack &candidates)
void visit (NodeID nodeId, s32_t _w)
void clear ()
bool isVisited (NodeID nId)
void setVisited (NodeID nId)

Private Attributes

ConstraintGraph * _consG
CGSCC * _scc
NodeID _I
IdToIdMap _D
NodeStack _S
NodeSet _visited

Detailed Description

class CSC: cycle stride calculation

Definition at line 49 of file CSC.h.

Member Typedef Documentation

◆ IdToIdMap

Definition at line 52 of file CSC.h.

◆ iterator

typedef IdToIdMap::iterator SVF::CSC::iterator

Definition at line 54 of file CSC.h.

◆ WorkStack

Definition at line 53 of file CSC.h.

Constructor & Destructor Documentation

◆ CSC()

SVF::CSC::CSC ( ConstraintGraph * g,
CGSCC * c )
inline

Definition at line 68 of file CSC.h.

69 : _consG(g), _scc(c), _I(0) {}
ConstraintGraph * _consG
Definition CSC.h:57
CGSCC * _scc
Definition CSC.h:58
NodeID _I
Definition CSC.h:60

Member Function Documentation

◆ clear()

void CSC::clear ( )

Definition at line 41 of file CSC.cpp.

42{
43 _I = 0;
44 _D.clear();
45}
IdToIdMap _D
Definition CSC.h:61

◆ find()

void CSC::find ( NodeStack & candidates)

Definition at line 51 of file CSC.cpp.

52{
53 clear();
54
55 NodeStack revCandidates;
56 while (!candidates.empty())
57 {
58 NodeID nId = candidates.top();
59 revCandidates.push(nId);
60 candidates.pop();
61
62 if (_scc->subNodes(nId).count()>1 && !isVisited(nId)) // node is actually in a cycle
63 visit(nId, 0);
64 }
65
66 while (!revCandidates.empty())
67 {
68 NodeID nId = revCandidates.top();
69 candidates.push(nId);
70 revCandidates.pop();
71 }
72}
void visit(NodeID nodeId, s32_t _w)
Definition CSC.cpp:78
bool isVisited(NodeID nId)
Definition CSC.h:75
void clear()
Definition CSC.cpp:41
std::stack< NodeID > NodeStack
Definition GeneralType.h:92
u32_t NodeID
Definition GeneralType.h:76

◆ isVisited()

bool SVF::CSC::isVisited ( NodeID nId)
inline

Definition at line 75 of file CSC.h.

76 {
77 return _visited.find(nId) != _visited.end();
78 }
NodeSet _visited
Definition CSC.h:63

◆ setVisited()

void SVF::CSC::setVisited ( NodeID nId)
inline

Definition at line 80 of file CSC.h.

81 {
82 _visited.insert(nId);
83 }

◆ visit()

void CSC::visit ( NodeID nodeId,
s32_t _w )

Definition at line 78 of file CSC.cpp.

79{
80// pwcReps[nodeId] = _scc->repNode(nodeId);
81 setVisited(nodeId);
82
83 _I += _w;
84 _D[nodeId] = _I;
85 _S.push(nodeId);
86
87 ConstraintNode* node = _consG->getConstraintNode(nodeId);
88 for (ConstraintNode::const_iterator eit = node->directOutEdgeBegin(); eit != node->directOutEdgeEnd(); ++eit)
89 {
91 if (NormalGepCGEdge* gepCGEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(*eit))
92 offset = gepCGEdge->getConstantFieldIdx();
93 else
94 offset = 0;
95 NodeID dstId = (*eit)->getDstID();
96 if (_scc->repNode(nodeId) == _scc->repNode(dstId) && !isVisited(dstId))
97 visit(dstId, offset);
98 }
99
100 NodeStack _revS;
101 NodeSet _C;
102
103 while (!_S.empty())
104 {
105 NodeID backNodeId = _S.top();
106 _S.pop();
107 _revS.push(backNodeId);
108 ConstraintNode* backNode = _consG->getConstraintNode(backNodeId);
109 if (_consG->hasEdge(node, backNode, ConstraintEdge::NormalGep))
110 {
111 NormalGepCGEdge* normalGep = SVFUtil::dyn_cast<NormalGepCGEdge>(_consG->getEdge(node, backNode, ConstraintEdge::NormalGep));
112 s32_t _w = normalGep->getConstantFieldIdx();
113 s32_t _l = _D[nodeId] +_w - _D[backNodeId];
114 backNode->strides.set(_l);
115 for (auto cNodeId : _C)
116 _consG->getConstraintNode(cNodeId)->strides.set(_l);
117 }
118 else if (_consG->hasEdge(node, backNode, ConstraintEdge::VariantGep) ||
119 _consG->hasEdge(node, backNode, ConstraintEdge::Copy))
120 {
121 s32_t _l = _D[nodeId] - _D[backNodeId];
122 backNode->strides.set(_l);
123 for (auto cNodeId : _C)
124 _consG->getConstraintNode(cNodeId)->strides.set(_l);
125 }
126 _C.insert(backNodeId);
127 }
128
129 while (!_revS.empty())
130 {
131 NodeID backedId = _revS.top();
132 _S.push(backedId);
133 _revS.pop();
134 }
135
136 _S.pop(); // after checking all the edges of the top node of _S, remove the node
137}
buffer offset
Definition cJSON.cpp:1113
NodeStack _S
Definition CSC.h:62
void setVisited(NodeID nId)
Definition CSC.h:80
NodeBS strides
For stride-based field representation.
Definition ConsGNode.h:71
iterator directOutEdgeEnd()
Definition ConsG.cpp:678
ConstraintEdge::ConstraintEdgeSetTy::const_iterator const_iterator
Definition ConsGNode.h:45
iterator directOutEdgeBegin()
Iterators.
Definition ConsG.cpp:670
APOffset getConstantFieldIdx() const
Get location set of the gep edge.
Definition ConsGEdge.h:309
void set(unsigned Idx)
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
Set< NodeID > NodeSet
Definition GeneralType.h:87
signed s32_t
Definition GeneralType.h:68

Member Data Documentation

◆ _consG

ConstraintGraph* SVF::CSC::_consG
private

Definition at line 57 of file CSC.h.

◆ _D

IdToIdMap SVF::CSC::_D
private

Definition at line 61 of file CSC.h.

◆ _I

NodeID SVF::CSC::_I
private

Definition at line 60 of file CSC.h.

◆ _S

NodeStack SVF::CSC::_S
private

Definition at line 62 of file CSC.h.

◆ _scc

CGSCC* SVF::CSC::_scc
private

Definition at line 58 of file CSC.h.

◆ _visited

NodeSet SVF::CSC::_visited
private

Definition at line 63 of file CSC.h.


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