Static Value-Flow Analysis
Loading...
Searching...
No Matches
AndersenSFR.cpp
Go to the documentation of this file.
1//===- AndersenSFR.cpp -- SFR based field-sensitive Andersen's analysis-------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2017> <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 * AndersenSFR.cpp
25 *
26 * Created on: 09, Feb, 2019
27 * Author: Yuxiang Lei
28 */
29
30#include "WPA/AndersenPWC.h"
32
33using namespace SVF;
34using namespace SVFUtil;
35using namespace std;
36
38
43{
45 setDetectPWC(false); // SCC will detect only copy edges
46
47 if (!csc)
48 csc = new CSC(_graph, scc.get());
49
53}
54
55
60{
62 csc->find(getSCCDetector()->topoNodeStack());
63}
64
65
70{
71 ConstraintNode* node = consCG->getConstraintNode(nodeId);
72 if (!node->strides.empty())
73 {
74 ConstraintNode* newRepNode = consCG->getConstraintNode(newRepId);
75 newRepNode->strides |= node->strides;
76 }
77 return Andersen::mergeSrcToTgt(nodeId, newRepId);
78}
79
80
84bool AndersenSFR::processGepPts(const PointsTo& pts, const GepCGEdge* edge)
85{
86 ConstraintNode* dst = edge->getDstNode();
87 NodeID dstId = dst->getId();
88
89 if (!dst->strides.empty() && SVFUtil::isa<NormalGepCGEdge>(edge)) // dst is in pwc
90 {
91 PointsTo tmpDstPts;
92 PointsTo srcInits = pts - getPts(dstId);
93
94 if (!srcInits.empty())
95 {
96 NodeSet sortSrcInits;
97 for (NodeID ptd : srcInits)
98 sortSrcInits.insert(ptd);
99
100 APOffset offset = SVFUtil::dyn_cast<NormalGepCGEdge>(edge)->getConstantFieldIdx();
101 fieldExpand(sortSrcInits, offset, dst->strides, tmpDstPts);
102 }
103
104 if (unionPts(dstId, tmpDstPts))
105 {
106 pushIntoWorklist(dstId);
107 return true;
108 }
109 else
110 return false;
111 }
112 else
113 return Andersen::processGepPts(pts, edge);
114}
115
116
120void AndersenSFR::fieldExpand(NodeSet& initials, APOffset offset, NodeBS& strides, PointsTo& expandPts)
121{
123
124 while (!initials.empty())
125 {
126 NodeID init = *initials.begin();
127 initials.erase(init);
128
129 if (consCG->isBlkObjOrConstantObj(init))
130 expandPts.set(init);
131 else
132 {
133 PAGNode* initPN = pag->getGNode(init);
134 // ABTest
135 const BaseObjVar* baseObj = pag->getBaseObject(init);
136
137 const u32_t maxLimit = baseObj->getMaxFieldOffsetLimit();
138 APOffset initOffset;
139 if (GepObjVar *gepNode = SVFUtil::dyn_cast<GepObjVar>(initPN))
140 initOffset = gepNode->getConstantFieldIdx();
142 initOffset = 0;
143 else
144 {
145 assert(false && "Not an object node!!");
146 abort();
147 }
148
149 Set<APOffset> offsets;
150 offsets.insert(offset);
151
152 // calculate offsets
153 bool loopFlag = true;
154 while (loopFlag)
155 {
156 loopFlag = false;
157 for (auto _f : offsets)
158 for (auto _s : strides)
159 {
160 APOffset _f1 = _f + _s;
161 loopFlag = (offsets.find(_f1) == offsets.end()) && ( (u32_t)(initOffset + _f1) < maxLimit);
162 if (loopFlag)
163 offsets.insert(_f1);
164 }
165 }
166
167 // get gep objs
168 for (APOffset _f : offsets)
169 {
170 NodeID gepId = consCG->getGepObjVar(init, _f);
171 initials.erase(gepId); // gep id in initials should be removed to avoid redundant derivation
172 expandPts.set(gepId);
173 }
174 }
175 }
176}
buffer offset
Definition cJSON.cpp:1113
static u32_t numOfFieldExpand
Definition Andersen.h:166
ConstraintGraph * consCG
Constraint Graph.
Definition Andersen.h:181
virtual void PWCDetect()
void initialize()
Initialize analysis.
bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
void fieldExpand(NodeSet &initials, APOffset offset, NodeBS &strides, PointsTo &expandPts)
static AndersenSFR * sfrAndersen
bool mergeSrcToTgt(NodeID nodeId, NodeID newRepId)
void setDetectPWC(bool flag)
Definition Andersen.h:273
virtual bool unionPts(NodeID id, const PointsTo &target)
Definition Andersen.h:246
virtual const PointsTo & getPts(NodeID id)
Operation of points-to set.
Definition Andersen.h:242
virtual bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
Definition Andersen.cpp:644
void mergeSccCycle()
Definition Andersen.cpp:732
virtual bool mergeSrcToTgt(NodeID srcId, NodeID tgtId)
Definition Andersen.cpp:876
u32_t getMaxFieldOffsetLimit() const
Get max field offset limit.
Definition CSC.h:50
NodeBS strides
For stride-based field representation.
Definition ConsGNode.h:71
NodeType * getDstNode() const
virtual void initialize()
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
static SVFIR * pag
SVFIR.
bool empty() const
Returns true if set is empty.
Definition PointsTo.cpp:110
void set(u32_t n)
Inserts n in the set.
Definition PointsTo.cpp:169
void find(void)
Definition SCC.h:331
NodeID getId() const
Get ID.
Definition SVFValue.h:158
std::unique_ptr< SCC > scc
Definition WPASolver.h:194
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:157
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
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
Set< NodeID > NodeSet
Definition GeneralType.h:87
u32_t NodeID
Definition GeneralType.h:76
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
s64_t APOffset
Definition GeneralType.h:80
SVFVar PAGNode
Definition IRGraph.h:40
SparseBitVector NodeBS
Definition GeneralType.h:82
unsigned u32_t
Definition GeneralType.h:67