1 #include <featureTests.h>
7 #include "genericDataflowCommon.h"
8 #include "VirtualCFGIterator.h"
9 #include "cfgUtils.h"
10 #include "CallGraphTraverse.h"
11 #include "analysisCommon.h"
12 #include "analysis.h"
13 #include "dataflow.h"
14 #include "latticeFull.h"
15 #include "printAnalysisStates.h"
17 extern int dominatorAnalysisDebugLevel;
19 // Lattice that stores the DataflowNodes that are dominated by or post-dominated by a given DataflowNode
21 {
22  public:
23  typedef enum { uninitialized=0, initialized } domLevel;
24  domLevel level;
25  set<DataflowNode> domNodes;
26  DataflowNode n;
28  public:
29  //DominatorLattice();
31  DominatorLattice(const DataflowNode& n, const DataflowNode& nodes);
32  DominatorLattice(const DataflowNode& n, const set<DataflowNode>& nodes);
35  // Initializes this Lattice to its default state, if it is not already initialized
36  void initialize();
38  // Returns a copy of this lattice
39  Lattice* copy() const;
41  // Overwrites the state of this Lattice with that of that Lattice
42  void copy(Lattice* that);
44  // Overwrites the state of this Lattice with that of that Lattice.
45  // Returns true if this causes this Lattice to chance and false otherwise.
46  bool copyFrom(DominatorLattice* domLat, string indent="");
48  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
49  // information on a per-variable basis, these per-variable mappings must be converted from
50  // the current set of variables to another set. This may be needed during function calls,
51  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
52  // We do not force child classes to define their own versions of this function since not all
53  // Lattices have per-variable information.
54  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
55  // old variable and pair->second is the new variable
56  // func - the function that the copy Lattice will now be associated with
57  void remapVars(const map<varID, varID>& varNameMap, const Function& newFunc);
59  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
60  // that contains data for a set of variables and incorporateVars must overwrite the state of just
61  // those variables, while leaving its state for other variables alone.
62  // We do not force child classes to define their own versions of this function since not all
63  // Lattices have per-variable information.
64  void incorporateVars(Lattice* that_arg);
66  // Returns a Lattice that describes the information known within this lattice
67  // about the given expression. By default this could be the entire lattice or any portion of it.
68  // For example, a lattice that maintains lattices for different known variables and expression will
69  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
70  // on values of variables and expressions will return the portion of the lattice that relates to
71  // the given expression.
72  // It it legal for this function to return NULL if no information is available.
73  // The function's caller is responsible for deallocating the returned object
74  Lattice* project(SgExpression* expr);
76  // The inverse of project(). The call is provided with an expression and a Lattice that describes
77  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
78  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
79  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
80  // Returns true if this causes this to change and false otherwise.
81  bool unProject(SgExpression* expr, Lattice* exprState);
83  // computes the meet of this and that and saves the result in this
84  // returns true if this causes this to change and false otherwise
85  bool meetUpdate(Lattice* that_arg);
87  bool operator==(Lattice* that);
89  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
90  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
91  // an expression or variable is dead).
92  // It is assumed that a newly-added variable has not been added before and that a variable that is being
93  // removed was previously added
94  // Returns true if this causes the lattice to change and false otherwise.
95  bool addNode(const DataflowNode& n, string indent="");
96  bool remNode(const DataflowNode& n, string indent="");
98  // Returns true if the given node dominates / post-dominates the node associated with this lattice
99  bool isDominator(const DataflowNode& n, string indent="");
101  // The string that represents this object
102  // If indent!="", every line of this string must be prefixed by indent
103  // The last character of the returned string should not be '\n', even if it is a multi-line string.
104  string str(string indent="");
105 };
107 /* Computes the set of DataflowNodes that dominate a given DataflowNode. */
109 {
110  protected:
111  const set<DataflowNode>& allNodes;
113  public:
114  DominatorAnalysis(const set<DataflowNode>& allNodes, string indent="");
116  // Generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
117  void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
118  vector<Lattice*>& initLattices, vector<NodeFact*>& initFacts);
120  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const vector<Lattice*>& dfInfo);
121 };
123 /* Computes the set of all DataflowNodes within a given function */
125 {
126  public:
127  const Function& func;
128  set<DataflowNode> allNodes;
130  FindAllNodesAnalysis(const Function& func, string indent="");
131  void visit(const Function& func, const DataflowNode& n, NodeState& state);
132 };
134 // Returns the set of DataflowNodes that dominate the given node
135 const set<DataflowNode>& getDominators(SgProject* project, const Function& func, const DataflowNode& n, string indent="");
137 // Returns true if node a dominates node b and false otherwise
138 bool dominates(const DataflowNode& a, const DataflowNode& b, string indent="");
140 // prints the Lattices set by the given LiveDeadVarsAnalysis
141 void printDominatorAnalysisStates(DominatorAnalysis* da, string indent="");
143 #endif
144 #endif
This class represents the notion of an expression. Expressions are derived from SgLocatedNodes, since similar to statement, expressions have a concrete location within the user's source code.
This class represents a source project, with a list of SgFile objects and global information about th...