Static Value-Flow Analysis
|
Solver Utilize Hybrid Representation of Graph. More...
#include <CFLSolver.h>
Classes | |
struct | TreeNode |
Public Member Functions | |
bool | hasInd_h (NodeID src, NodeID dst) |
TreeNode * | addInd_h (NodeID src, NodeID dst) |
Add a node dst to tree(src) More... | |
TreeNode * | getNode_h (NodeID src, NodeID dst) |
Get the node dst in tree(src) More... | |
void | insertEdge_h (TreeNode *u, TreeNode *v) |
add v into desc(x) as a child of u More... | |
void | addArc_h (NodeID src, NodeID dst) |
void | meld_h (NodeID x, TreeNode *uNode, TreeNode *vNode) |
POCRHybridSolver (CFLGraph *_graph, CFGrammar *_grammar) | |
virtual | ~POCRHybridSolver () |
Destructor. More... | |
virtual void | processCFLEdge (const CFLEdge *Y_edge) |
Process CFLEdge. More... | |
virtual void | initialize () |
Initialize worklist. More... | |
void | addArc (NodeID src, NodeID dst) |
void | meld (NodeID x, TreeNode *uNode, TreeNode *vNode) |
Public Member Functions inherited from SVF::POCRSolver | |
virtual void | clear () |
const_iterator | begin () const |
const_iterator | end () const |
iterator | begin () |
iterator | end () |
DataMap & | getSuccMap () |
DataMap & | getPredMap () |
TypeMap & | getSuccMap (const NodeID key) |
TypeMap & | getPredMap (const NodeID key) |
NodeBS & | getSuccs (const NodeID key, const Label ty) |
NodeBS & | getPreds (const NodeID key, const Label ty) |
bool | addEdge (const NodeID src, const NodeID dst, const Label ty) |
NodeBS | addEdges (const NodeID src, const NodeBS &dstData, const Label ty) |
add edges and return the set of added edges (dst) for src More... | |
NodeBS | addEdges (const NodeBS &srcData, const NodeID dst, const Label ty) |
add edges and return the set of added edges (src) for dst More... | |
bool | hasEdge (const NodeID src, const NodeID dst, const Label ty) |
find src -> find src[ty] -> find dst in set More... | |
void | clearEdges (const NodeID key) |
POCRSolver (CFLGraph *_graph, CFGrammar *_grammar) | |
virtual | ~POCRSolver () |
Destructor. More... | |
virtual void | buildCFLData () |
Init CFLData. More... | |
Public Member Functions inherited from SVF::CFLSolver | |
CFLSolver (CFLGraph *_graph, CFGrammar *_grammar) | |
virtual | ~CFLSolver () |
virtual void | solve () |
Start solving. More... | |
const CFLGraph * | getGraph () const |
Return CFL Graph. More... | |
const CFGrammar * | getGrammar () const |
Return CFL Grammar. More... | |
virtual bool | pushIntoWorklist (const CFLEdge *item) |
virtual bool | isWorklistEmpty () |
Public Attributes | |
Map< NodeID, std::unordered_map< NodeID, TreeNode * > > | indMap |
Additional Inherited Members | |
Public Types inherited from SVF::POCRSolver | |
typedef std::map< const Label, NodeBS > | TypeMap |
typedef std::unordered_map< NodeID, TypeMap > | DataMap |
typedef DataMap::iterator | iterator |
typedef DataMap::const_iterator | const_iterator |
Public Types inherited from SVF::CFLSolver | |
typedef FIFOWorkList< const CFLEdge * > | WorkList |
Define worklist. More... | |
typedef CFGrammar::Production | Production |
typedef CFGrammar::Symbol | Symbol |
Static Public Attributes inherited from SVF::CFLSolver | |
static double | numOfChecks = 0 |
Protected Member Functions inherited from SVF::POCRSolver | |
bool | addPred (const NodeID key, const NodeID src, const Label ty) |
bool | addSucc (const NodeID key, const NodeID dst, const Label ty) |
bool | addPreds (const NodeID key, const NodeBS &data, const Label ty) |
bool | addSuccs (const NodeID key, const NodeBS &data, const Label ty) |
Protected Member Functions inherited from SVF::CFLSolver | |
const CFLEdge * | popFromWorklist () |
Worklist operations. More... | |
bool | isInWorklist (const CFLEdge *item) |
Protected Attributes inherited from SVF::POCRSolver | |
DataMap | succMap |
DataMap | predMap |
const NodeBS | emptyData |
NodeBS | diff |
Protected Attributes inherited from SVF::CFLSolver | |
CFLGraph * | graph |
CFGrammar * | grammar |
WorkList | worklist |
Worklist for resolution. More... | |
Solver Utilize Hybrid Representation of Graph.
Hybrid graph representation for transitive relations The implementation is based on Yuxiang Lei, Yulei Sui, Shuo Ding, and Qirun Zhang. Taming Transitive Redundancy for Context-Free Language Reachability. ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications
Definition at line 294 of file CFLSolver.h.
Definition at line 347 of file CFLSolver.h.
|
inlinevirtual |
Destructor.
Definition at line 351 of file CFLSolver.h.
Definition at line 314 of file CFLSolver.cpp.
Definition at line 359 of file CFLSolver.cpp.
POCRHybridSolver::TreeNode * POCRHybridSolver::addInd_h | ( | NodeID | src, |
NodeID | dst | ||
) |
Get the node dst in tree(src)
Definition at line 331 of file CFLSolver.h.
Definition at line 341 of file CFLSolver.cpp.
|
virtual |
Initialize worklist.
add X(i,i) if not exist to E and to worklist
Foreach production X -> epsilon add X(i,i) if not exist to E and to worklist
Foreach production X -> epsilon add X(i,i) if not exist to E and to worklist
Reimplemented from SVF::POCRSolver.
Definition at line 284 of file CFLSolver.cpp.
add v into desc(x) as a child of u
Definition at line 337 of file CFLSolver.h.
Definition at line 326 of file CFLSolver.cpp.
Definition at line 370 of file CFLSolver.cpp.
|
virtual |
Process CFLEdge.
For each production X -> Y add X(i,j) if not exist to E and to worklist
For each production X -> Y Z Foreach outgoing edge Z(j,k) from node j do add X(i,k) if not exist to E and to worklist
For each production X -> Z Y Foreach incoming edge Z(k,i) to node i do add X(k,j) if not exist to E and to worklist
Reimplemented from SVF::POCRSolver.
Definition at line 216 of file CFLSolver.cpp.
Definition at line 323 of file CFLSolver.h.