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