ROSE  0.9.9.139
staticSingleAssignment.h
1 //Author: George Vulov <georgevulov@hotmail.com>
2 //Based on work by Justin Frye <jafrye@tamu.edu>
3 
4 #pragma once
5 
6 // DQ (10/5/2014): This is more strict now that we include rose_config.h in the sage3basic.h.
7 // #include "rose.h"
8 // rose.h and sage3basic.h should not be included in librose header files. [Robb P. Matzke 2014-10-15]
9 // #include "sage3basic.h"
10 
11 #include <string>
12 #include <iostream>
13 #include <map>
14 #include <vector>
15 #include <algorithm>
16 #include <ostream>
17 #include <fstream>
18 #include <sstream>
19 #include <boost/foreach.hpp>
20 #include <filteredCFG.h>
21 #include <boost/unordered_map.hpp>
22 #include "reachingDef.h"
23 #include "dataflowCfgFilter.h"
24 #include "CallGraph.h"
25 #include "uniqueNameTraversal.h"
26 
27 namespace ssa_private
28 {
29 
32  {
33 
34 #define DEBUG_SSA_FILTER 0
35 
36  bool operator()(SgFunctionDeclaration * funcDecl)
37  {
38  ROSE_ASSERT(funcDecl != NULL);
39 
40  // DQ (8/30/2016): Reorganize this to allow it to be more easily debugged.
41  bool returnValue = true;
42 
43  // Don't process any built-in functions
44  std::string filename = funcDecl->get_file_info()->get_filename();
45 #if DEBUG_SSA_FILTER
46  printf ("In FunctionFilter::operator():funcDecl = %p = %s name = %s: filename = %s \n",funcDecl,funcDecl->class_name().c_str(),funcDecl->get_name().str(),filename.c_str());
47 #endif
48  if (filename.find("include") != std::string::npos)
49  {
50  returnValue = false;
51  }
52 
53  // DQ (8/30/2016): Don't allow template functions.
54  // if (isSgTemplateFunctionDeclaration(funcDecl) || isSgTemplateMemberFunctionDeclaration(funcDecl))
55  // if (returnValue == true && funcDecl->get_file_info()->isCompilerGenerated() && !isSgTemplateInstantiationFunctionDecl(funcDecl)
56  // && !isSgTemplateInstantiationMemberFunctionDecl(funcDecl))
57  SgFunctionDeclaration* definingFunction = isSgFunctionDeclaration(funcDecl->get_definingDeclaration());
58  bool functionDefinitionIsCompilerGenerated = definingFunction != NULL ? definingFunction->isCompilerGenerated() : false;
59 
60 #if DEBUG_SSA_FILTER
61  printf ("definingFunction = %p functionDefinitionIsCompilerGenerated = %s \n",definingFunction,functionDefinitionIsCompilerGenerated ? "true" : "false");
62 #endif
63 
64  if (returnValue == true && functionDefinitionIsCompilerGenerated && !isSgTemplateInstantiationFunctionDecl(funcDecl)
65  && !isSgTemplateInstantiationMemberFunctionDecl(funcDecl))
66  {
67 #if DEBUG_SSA_FILTER
68  printf ("In FunctionFilter::operator(): compiler generated and is NOT a template instantiation function or member function: setting returnValue == false \n");
69 #endif
70  returnValue = false;
71  }
72 
73  // We don't process functions that don't have definitions
74  if (returnValue == true && funcDecl->get_definingDeclaration() == NULL)
75  {
76 #if DEBUG_SSA_FILTER
77  printf ("In FunctionFilter::operator(): funcDecl->get_definingDeclaration() == NULL: setting returnValue == false \n");
78 #endif
79  returnValue = false;
80  }
81 
82 #if DEBUG_SSA_FILTER
83  printf ("Leaving FunctionFilter::operator(): funcDecl = %p = %s name = %s returnValue = %s \n",funcDecl,funcDecl->class_name().c_str(),funcDecl->get_name().str(),returnValue ? "true" : "false");
84 #endif
85 
86  return returnValue;
87  }
88  };
89 
90 } //namespace ssa_private
91 
100 class ROSE_DLL_API StaticSingleAssignment
101 {
102 private:
104  SgProject* project;
105 
106 public:
107 
109  typedef std::vector<SgInitializedName*> VarName;
110 
112  typedef boost::unordered_map<SgNode*, std::set<VarName> > LocalDefUseTable;
113 
115  typedef FilteredCFGNode<ssa_private::DataflowCfgFilter> FilteredCfgNode;
116 
118  typedef FilteredCFGEdge<ssa_private::DataflowCfgFilter> FilteredCfgEdge;
119 
120  typedef boost::shared_ptr<ReachingDef> ReachingDefPtr;
121 
123  typedef std::map<VarName, ReachingDefPtr> NodeReachingDefTable;
124 
126  typedef boost::unordered_map<SgNode*, std::pair<NodeReachingDefTable, NodeReachingDefTable> > GlobalReachingDefTable;
127 
129  typedef boost::unordered_map<SgNode*, NodeReachingDefTable> UseTable;
130 
131 private:
132  //Private member variables
133 
138  LocalDefUseTable originalDefTable;
139 
144  LocalDefUseTable expandedDefTable;
145 
149  GlobalReachingDefTable reachingDefsTable;
150 
157  LocalDefUseTable localUsesTable;
158 
160  UseTable useTable;
161 
165  boost::unordered_map<SgNode*, NodeReachingDefTable> ssaLocalDefTable;
166 
167 public:
168 
169  StaticSingleAssignment(SgProject* proj) : project(proj)
170  {
171  }
172 
174  {
175  }
176 
181  void run(bool interprocedural, bool treatPointersAsStructures);
182 
183  static bool getDebug()
184  {
185  return SgProject::get_verbose() > 0;
186  }
187 
188  static bool getDebugExtra()
189  {
190  return SgProject::get_verbose() > 1;
191  }
192 
193 private:
196  void runDefUseDataFlow(SgFunctionDefinition* func);
197 
199  static bool isBuiltinVar(const VarName& var);
200 
214  void expandParentMemberDefinitions(SgFunctionDeclaration* function);
215 
232  void expandParentMemberUses(SgFunctionDeclaration* function);
233 
238  void insertDefsForChildMemberUses(SgFunctionDeclaration* function);
239 
241  void insertDefsForExternalVariables(SgFunctionDeclaration* function);
242 
248  std::multimap< FilteredCfgNode, std::pair<FilteredCfgNode, FilteredCfgEdge> > insertPhiFunctions(SgFunctionDefinition* function,
249  const std::vector<FilteredCfgNode>& cfgNodesInPostOrder);
250 
252  void populateLocalDefsTable(SgFunctionDeclaration* function);
253 
258  void renumberAllDefinitions(SgFunctionDefinition* func, const std::vector<FilteredCfgNode>& cfgNodesInPostOrder);
259 
262  void updateIncomingPropagatedDefs(FilteredCfgNode cfgNode);
263 
266  bool propagateDefs(FilteredCfgNode cfgNode);
267 
271  void buildUseTable(const std::vector<FilteredCfgNode>& cfgNodes);
272 
275  static std::vector<FilteredCfgNode> getCfgNodesInPostorder(SgFunctionDefinition* func);
276 
277  //------------ INTERPROCEDURAL ANALYSIS FUNCTIONS ------------ //
278 
282  void interproceduralDefPropagation(const boost::unordered_set<SgFunctionDefinition*>& interestingFunctions);
283 
287  std::vector<SgFunctionDefinition*> calculateInterproceduralProcessingOrder(
288  const boost::unordered_set<SgFunctionDefinition*>& interestingFunctions);
289 
292  void processCalleesThenFunction(SgFunctionDefinition* targetFunction, SgIncidenceDirectedGraph* callGraph,
293  const boost::unordered_map<SgFunctionDefinition*, SgGraphNode*>& graphNodeToFunction,
294  std::vector<SgFunctionDefinition*> &processingOrder, std::set<SgFunctionDefinition*> visited);
295 
302  bool insertInterproceduralDefs(SgFunctionDefinition* funcDef, const boost::unordered_set<SgFunctionDefinition*>& processed,
303  ClassHierarchyWrapper* classHierarchy);
304 
309  void processOneCallSite(SgExpression* callSite, SgFunctionDeclaration* callee,
310  const boost::unordered_set<SgFunctionDefinition*>& processed, ClassHierarchyWrapper* classHierarchy);
311 
314  static bool isVarAccessibleFromCaller(const VarName& var, SgExpression* callSite, SgFunctionDeclaration* callee);
315 
318  static bool varRequiresThisPointer(const VarName& var);
319 
321  static bool isThisPointerSameInCallee(SgFunctionCallExp* callSite, SgMemberFunctionDeclaration* callee);
322 
326  static bool isThisPointer(SgExpression* expression);
327 
330  static bool isDeepConstPointer(SgType* type);
331 
334  static bool isPointerToDeepConst(SgType* type);
335 
338  static bool isArgumentNonConstReferenceOrPointer(SgInitializedName* formalArgument);
339 
340  //------------ GRAPH OUTPUT FUNCTIONS ------------ //
341 
342  void printToDOT(SgSourceFile* file, std::ofstream &outFile);
343  void printToFilteredDOT(SgSourceFile* file, std::ofstream &outFile);
344 
345 public:
346  //External static helper functions/variables
347 
348  static VarName emptyName;
349 
350  /*
351  * Printing functions.
352  */
353 
358  void toDOT(const std::string fileName);
359 
367  void toFilteredDOT(const std::string fileName);
368 
369  void printOriginalDefs(SgNode* node);
370  void printOriginalDefTable();
371 
372 
373  //------------ DEF/USE TABLE ACCESS FUNCTIONS ------------ //
374 
380  LocalDefUseTable& getOriginalDefTable()
381  {
382  return originalDefTable;
383  }
384 
385  LocalDefUseTable& getLocalUsesTable()
386  {
387  return localUsesTable;
388  }
389 
393  const NodeReachingDefTable& getOutgoingDefsAtNode(SgNode* node) const;
394 
397  const NodeReachingDefTable& getReachingDefsAtNode_(SgNode* node) const;
398 
401  const NodeReachingDefTable& getUsesAtNode(SgNode* node) const;
402 
405  const NodeReachingDefTable& getDefsAtNode(SgNode* node) const;
406 
408  std::set<VarName> getVarsUsedInSubtree(SgNode* root) const;
409 
412  std::set<VarName> getVarsDefinedInSubtree(SgNode* root) const;
413 
416  std::set<VarName> getOriginalVarsDefinedInSubtree(SgNode* root) const;
417 
420  NodeReachingDefTable getLastVersions(SgFunctionDeclaration* func) const;
421 
422  //------------ STATIC UTILITY FUNCTIONS FUNCTIONS ------------ //
423 
424 
435  static bool isPrefixOfName(VarName name, VarName prefix);
436 
442  static ssa_private::VarUniqueName* getUniqueName(SgNode* node);
443 
449  static const VarName& getVarName(SgNode* node);
450 
454  static const VarName& getVarForExpression(SgNode* node);
455 
462  static SgExpression* buildVariableReference(const VarName& var, SgScopeStatement* scope = NULL);
463 
466  static bool isVarInScope(const VarName& var, SgNode* scope);
467 
473  static std::string varnameToString(const VarName& vec);
474 
475  static void printLocalDefUseTable(const LocalDefUseTable& table);
476 };
477 
478 
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).
const char * get_filename() const ROSE_DEPRECATED_FUNCTION
Returns filename of source code associated with IR node.
boost::unordered_map< SgNode *, std::pair< NodeReachingDefTable, NodeReachingDefTable > > GlobalReachingDefTable
The first table is the IN table.
virtual Sg_File_Info * get_file_info() const ROSE_OVERRIDE
Interface function to implement original SAGE interface to SgFile_Info objects.
This class represents the base class for all types.
This class represents the notion of a declared variable.
This class represents the concept of a member function declaration statement.
This class represents the concept of a function declaration statement.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).
boost::unordered_map< SgNode *, std::set< VarName > > LocalDefUseTable
Describes the defs or uses at each node.
FilteredCFGEdge< ssa_private::DataflowCfgFilter > FilteredCfgEdge
A filtered CFGEdge that is used for DefUse traversal.
boost::unordered_map< SgNode *, NodeReachingDefTable > UseTable
Map from each node to the variables used at that node and their reaching definitions.
This filter determines which function declarations get processed in the analysis. ...
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.
std::map< VarName, ReachingDefPtr > NodeReachingDefTable
A map from each variable to its reaching definitions at the current node.
Static single assignment analysis.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
std::vector< SgInitializedName * > VarName
A compound variable name as used by the variable renaming.
SgDeclarationStatement * get_definingDeclaration() const
This is an access function for the SgDeclarationStatement::p_definingDeclaration data member (see tha...
FilteredCFGNode< ssa_private::DataflowCfgFilter > FilteredCfgNode
A filtered CFGNode that is used for DefUse traversal.
virtual std::string class_name() const ROSE_OVERRIDE
returns a string representing the class name
static int get_verbose(void)
DQ: Modified to accept a value on the command line (no longer a boolean variable) value of 0 means qu...
This class represents a source project, with a list of SgFile objects and global information about th...
Class holding a unique name for a variable.
LocalDefUseTable & getOriginalDefTable()
Get the table of definitions for every node.
bool isCompilerGenerated() const
Simple test for if this is a compiler generated node.
This class represents the concept of a C++ function call (which is an expression).