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