Brief Overview of Algorithm: More...
#include <boost/regex.hpp>#include <iostream>#include <fstream>#include <string>#include <assert.h>#include <staticCFG.h>#include <boost/graph/adjacency_list.hpp>#include <boost/bind.hpp>#include <boost/foreach.hpp>#include <boost/tuple/tuple.hpp>#include <boost/graph/graphviz.hpp>#include <boost/graph/dominator_tree.hpp>#include <boost/graph/reverse_graph.hpp>#include <boost/graph/transpose_graph.hpp>#include <boost/algorithm/string.hpp>#include <vector>#include <algorithm>#include <utility>#include <sys/time.h>#include <sys/resource.h>
Go to the source code of this file.
Classes | |
| class | SgGraphTraversal< CFG > |
Macros | |
| #define | LP 1 |
| #define | PERFDEBUG 0 |
Detailed Description
Brief Overview of Algorithm:
Current Implementation
This implementation uses BOOSTs graph structure to analyze the paths of the graph
The path analyzer sends the user paths to be evaluated by the "analyzePath" function that is user defined
Further Improvements: TODO
Contact Info
Finally, blame can be assigned to and questions can be forwarded to the author, though response is not guaranteed
if I'm still at Lawrence hoffman34 AT llnl DOT gov
Current Implementation
The idea behind the algorithm here is to decompose the given Control Flow Graph into a Tree structure (still stored as a Control Flow Graph, though it may be possible to change this). This tree splits on children of a graph node, but does not connect in the case of multiple parents of a single node. In this we refer to out nodes as "children" and in nodes as "parents". However, we do this from the end node to the start node. This is best because then you get one value on the end node, and that value is the only one we want (however, the function takes a pointer to an empty SgIncidenceDirectedGraph as an argument, this can then be analyzed post traversal if that is wanted.
Also, following the algorithm explained above, one must realize that the tree has one leaf for EACH path. Thus small programs can lead from a small-ish graph to a VERY large tree. For example, a program with 20 if else statements would end with 2^20 paths, which means the number of nodes in the tree is greater than this. Thus with 32 or 64 you can overflow a 32 or 64 bit integer.
However, this can be partially resolved by setting the deleteTree boolean to true. This is set to false as the default, however if you don't need the tree then deleteTree will allow you to deal with much larger trees and thus much larger original graphs.
Realize that because of the potentially massive growth rate of path number, that in large cases path enumeration and counting is extremely prohibitive, as it is not difficult to create a program which has more paths than 2^64, thus an unsigned (signed?) 64 bit integer could not store the number.
Further, this is still a relatively compact method. You could just as easily force enumeration of paths, which could in some cases drastically increase the number of nodes necessary to store all the information.
The advantage of the tree structure is two-fold. First it relieves the algorithm of having to keep even more in memory than it has to at the moment, and if you want to deal with GoTo statements, one case can develop that cannot be solved otherwise, e.g.
Consider the four node tree with nodes a, b, c, d, and edges atb, atc, btc, ctb, btd, ctd. There are FOUR legitimate paths here (a, b, d; a, b, c, d; a, c, d; a, c, b, d), and any other method would recognize this as a loop and, without a special algorithm for loop behavior, this would be ignored.
The tree structure also allows for very strong parallelization, currently implemented in openMP. This is because depth has meaning in terms of a tree (it doesn't in terms of a general graph) and that you know you can evaluate all nodes at a certain depth if you have solved all the nodes at depth + 1.
Further Improvements: TODO
Contact Info
Finally, blame can be assigned to and questions can be forwarded to the author, though response is not guaranteed
archangel DOT associate AT gmail DOT com or, if I'm still at Lawrence hoffman34 AT llnl DOT gov
Definition in file graphProcessing.h.
