ROSE  0.9.9.139
filteredCFGImpl.h
1 //#include <rose.h>
2 #include "filteredCFG.h"
3 #include <sstream>
4 #include <iomanip>
5 #include <stdint.h>
6 #include <set>
7 
8 #define SgNULL_FILE Sg_File_Info::generateDefaultFileInfoForTransformationNode()
9 
10 namespace VirtualCFG
11 {
12  /* Documented by Liao, May not be entirely accurate. 2/14/2012
13  *
14  * Filtered CFG is handled internally when FilteredCFGNode <T>::inEdges() and ::outEdges() are requested
15  * Take FilteredCFGNode < FilterFunction >::outEdges() as an example, here is how it works:
16  * Each raw outgoing virtual CFG edge is a candidate, and converted to a CFGPath each.
17  * For each candidate CFGPath, check the target Node (the node pointed to by the last edge of the path)
18  * - if the target node is an interesting node according to the filter function, then the path is good, the edge can be returned as it is mostly.
19  * - if the target node is a CFG node to be filtered out, then the original path is extended to include all successors
20  * By following raw outEdges of the target node, we now have N candidate CFGPaths if there are N raw outEdges of target
21  * - Recursively handle all the new N CFGPaths until a path has a target node which is not being filtered out (interesting)
22  */
23 
24  template < typename FindSuccessors, // a function to obtain successor edges of a node
25  typename FindEnd, // obtain the final node of a CFG path
26  typename DontAddChildren, // filter function (functor)
27  typename Join, // merge two paths into one path
28  typename FilteredEdge >
29  struct MakeClosure // a template struct to make raw input edges closure (filter out unnecessary edges)
30  {
31  std::set < CFGNode > visitedNodes;
32  std::vector < CFGPath > visitedPaths;
33  const FindSuccessors & findSuccessors;
34  const FindEnd & findEnd;
35  const DontAddChildren & dontAddChildren;
36  const Join & join;
37 
38  MakeClosure(const FindSuccessors & findSuccessors,
39  const FindEnd & findEnd,
40  const DontAddChildren & dontAddChildren,
41  const Join & join) :
42  findSuccessors(findSuccessors), findEnd(findEnd),
43  dontAddChildren(dontAddChildren), join(join)
44  {
45  }
46 
48  void go(const CFGPath & p)
49  {
50  CFGNode end = findEnd(p);// obtain the final node of the path
51 
52  // skip visited end CFGNode, the corresponding successor paths of the end node are processed already
53  if (visitedNodes.find(end) != visitedNodes.end())
54  return;
55  visitedNodes.insert(end); //bookkeeping
56  visitedPaths.push_back(p);
57  // Reach an end CFG node which should be not filtered out. The path is valid already (ending with an interesting node).
58  if (dontAddChildren(end))
59  return;
60  // The end Node is one which will be filtered out, look further down the successors:outEdges() or inEdges()
61  // to find an interesting node as the new end
62  std::vector < CFGEdge > edges = findSuccessors(end);
63  for (unsigned int i = 0; i < edges.size(); ++i)
64  {
65  go(join(p, edges[i])); // connect the current path to successors, for each connected path,
66  //do the same processing (make sure end node is interesting)
67  }
68  }
70  std::vector < FilteredEdge > filter() const
71  {
72  std::vector < FilteredEdge > edges;
73  // for each valid paths
74  for (std::vector < CFGPath >::const_iterator i = visitedPaths.begin(); i != visitedPaths.end(); ++i)
75  {
76  const CFGPath & p = *i;
77  if (dontAddChildren(findEnd(p))) // if the end edge of a current path should not filtered out (interesting path)
78  edges.push_back(FilteredEdge(*i));
79  }
80  return edges;
81  }
82  };
83  // a template function to instantiate MakeClosure
84  template < typename FilteredEdge,
85  typename FindSuccessors,
86  typename FindEnd,
87  typename AddChildren, // CFG Filter function
88  typename Join >
89  std::vector < FilteredEdge > makeClosure(const std::vector < CFGPath > &p, // a vector of CFGPath be be made closure, in of out edges
90  const FindSuccessors & findSuccessors,
91  const FindEnd & findEnd,
92  const AddChildren & addChildren, // filter functor
93  const Join & join)
94  {
95  MakeClosure < FindSuccessors, FindEnd, AddChildren, Join, FilteredEdge >
96  mc(findSuccessors, findEnd, addChildren, join);
97  for (unsigned int i = 0; i < p.size(); ++i)
98  mc.go(p[i]);
99  return mc.filter();
100  }
101 
102  // internal function: make a set of raw edges closure
103  template < typename FilteredEdge, typename Filter >
104  std::vector < FilteredEdge > makeClosure(const std::vector < CFGEdge > &orig, // input raw edges
105  std::vector < CFGEdge > (CFGNode::*closure) ()const, // FindSuccessors operator: CFGNode::outEdges() in fact
106  CFGNode(CFGPath::*otherSide) ()const, //FindEnd operator: CFGPath::target()
107  CFGPath(*merge) (const CFGPath &, const CFGPath &), // Join operator: VirtualCFG::mergePaths()
108  const Filter & filter) // the filter function
109  {
110  std::vector < CFGPath > paths(orig.begin(), orig.end()); // convert each raw edges into a path: 1-to-1 conversion for now
111  return makeClosure < FilteredEdge > (paths,
112  std::mem_fun_ref(closure),
113  std::mem_fun_ref(otherSide),
114  filter,
115  merge);
116  }
117 
118 
119  // Class Impl: user-level interface function for outEdges for FilteredCFGNode <T>, Only FilterFunction is needed
120  // The returned edges already make the filtered CFG closure (internally and transparently)
121  template < typename FilterFunction >
122  std::vector < FilteredCFGEdge < FilterFunction > > FilteredCFGNode < FilterFunction >::outEdges()const
123  {
124  return makeClosure < FilteredCFGEdge < FilterFunction > >(n.outEdges(), // start with raw CFGNode's outEdges
125  &CFGNode::outEdges, //FindSuccessors operator
126  &CFGPath::target, //FindEnd operator, the target node the path leads to
127  &mergePaths, // merge/join operator: VirtualCFG::mergePaths(), defined in virtualCFG.h
128  filter); // the FilterFunction member of FilteredCFGNode
129  }
130  // Class Impl: user-level interface function for inEdges() of FilteredCFGNnode <T>
131  template < typename FilterFunction >
132  std::vector < FilteredCFGEdge < FilterFunction > > FilteredCFGNode < FilterFunction >::inEdges() const
133  {
134  return makeClosure < FilteredCFGEdge < FilterFunction > >(n.inEdges(),
136  &CFGPath::source,
137  &mergePathsReversed,
138  filter);
139  }
140  // ---------------------------------------------
141  // DOT OUT IMPL
142  template < typename NodeT, typename EdgeT ,bool Debug> /*Filtered Node Type, Filtered CFG Type*/
144  {
145  std::multimap < SgNode *, NodeT > exploredNodes;
146  std::set < SgNode * >nodesPrinted;
147  std::ostream & o;
148 
149  public:
150  CfgToDotImpl(std::ostream & o) :
151  exploredNodes(), nodesPrinted(), o(o)
152  {
153  }
154  void processNodes(NodeT n);
155  };
156 
158  template < typename NodeT >
159  inline void printNode(std::ostream & o, const NodeT & n)
160  {
161  std::string id = n.id();
162  std::string nodeColor = "black";
163 
164  if (isSgStatement(n.getNode()))
165  nodeColor = "blue";
166  else if (isSgExpression(n.getNode()))
167  nodeColor = "green";
168  else if (isSgInitializedName(n.getNode()))
169  nodeColor = "red";
170 
171  o << id << " [label=\"" << escapeString(n.toString()) << "\", color=\"" << nodeColor <<
172  "\", style=\"" << (n.isInteresting()? "solid" : "dotted") << "\"];\n";
173  }
175  template < typename EdgeT >
176  inline void printEdge(std::ostream & o, const EdgeT & e, bool isInEdge)
177  {
178  o << e.source().id() << " -> " << e.target().id() << " [label=\"" <<
179  escapeString(e.toString()) << "\", style=\"" << (isInEdge ? "dotted" : "solid") << "\"];\n";
180  }
181 
183  template < typename NodeT, typename EdgeT >
184  void printNodePlusEdges(std::ostream & o,NodeT n);
185 
186  /* Internal template function handles the details*/
187  template < typename NodeT, typename EdgeT ,bool Debug>
188  void CfgToDotImpl < NodeT, EdgeT, Debug >::processNodes(NodeT n)
189  {
190  ROSE_ASSERT(n.getNode());
191  std::pair < typename std::multimap < SgNode *, NodeT >::const_iterator,
192  typename std::multimap < SgNode *, NodeT >::const_iterator > ip =
193  exploredNodes.equal_range(n.getNode());
194  for (typename std::multimap < SgNode *, NodeT >::const_iterator i = ip.first;
195  i != ip.second; ++i)
196  {
197  if (i->second == n)
198  return;
199  }
200  exploredNodes.insert(std::make_pair(n.getNode(), n));
201  printNodePlusEdges<NodeT, EdgeT>(o, n);
202  std::vector < EdgeT > outEdges = n.outEdges();
203  for (unsigned int i = 0; i < outEdges.size(); ++i)
204  {
205  ROSE_ASSERT(outEdges[i].source() == n);
206  processNodes(outEdges[i].target());
207  }
208  std::vector < EdgeT > inEdges = n.inEdges();
209  for (unsigned int i = 0; i < inEdges.size(); ++i)
210  {
211  ROSE_ASSERT(inEdges[i].target() == n);
212  processNodes(inEdges[i].source());
213  }
214  }
215 
217  template < typename NodeT, typename EdgeT >
218  void printNodePlusEdges(std::ostream & o, NodeT n)
219  {
220  printNode(o, n);
221  std::vector < EdgeT > outEdges = n.outEdges();
222  for (unsigned int i = 0; i < outEdges.size(); ++i)
223  {
224  printEdge(o, outEdges[i], false);
225  }
226  #ifdef DEBUG
227  std::vector < EdgeT > inEdges = n.inEdges();
228  for (unsigned int i = 0; i < inEdges.size(); ++i)
229  {
230  printEdge(o, inEdges[i], true);
231  }
232  #endif
233  }
234 #if 0
235  template < typename NodeT, typename EdgeT >
236  void CfgToDotImpl < NodeT, EdgeT >::processNodes(SgNode *)
237  {
238  for (typename std::multimap < SgNode *, NodeT >::const_iterator it =
239  exploredNodes.begin(); it != exploredNodes.end(); ++it)
240  {
241  printNodePlusEdges < NodeT, EdgeT > (o, it->second);
242  }
243  }
244 #endif
245 
246  /*User-level interface template function */
247  template < typename FilterFunction >
248  std::ostream & cfgToDot(std::ostream & o, /* output stream*/
249  std::string graphName, /* graph name*/
250  FilteredCFGNode < FilterFunction > start) /* start filtered CFG Node */
251  {
252  o << "digraph " << graphName << " {\n";
253  CfgToDotImpl < FilteredCFGNode < FilterFunction >,
254  FilteredCFGEdge < FilterFunction > ,
255  false> impl(o);
256  impl.processNodes(start);
257  o << "}\n";
258  return o;
259  }
260 }
std::vector< CFGEdge > inEdges() const
Incoming control flow edges to this node.
A node in the control flow graph.
Definition: virtualCFG.h:67
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
void go(const CFGPath &p)
Process one CFGPath at a time: make sure the end edge is an interesting one (should not be filtered o...
std::vector< CFGEdge > outEdges() const
Outgoing control flow edges from this node.
std::vector< FilteredEdge > filter() const
Process visited CFGPaths: convert them into edges.