ROSE  0.9.10.75
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
StaticSingleAssignment Class Reference

Description

Static single assignment analysis.

Contains all the functionality to implement variable renaming on a given program. For this class, we do not actually transform the AST directly, rather we perform the analysis and add attributes to the AST nodes so that later optimizations can access the results of this analysis while still preserving the original AST.

Definition at line 100 of file staticSingleAssignment.h.

#include <staticSingleAssignment.h>

Collaboration diagram for StaticSingleAssignment:
Collaboration graph
[legend]

Public Types

typedef std::vector< SgInitializedName * > VarName
 A compound variable name as used by the variable renaming. More...
 
typedef boost::unordered_map< SgNode *, std::set< VarName > > LocalDefUseTable
 Describes the defs or uses at each node. More...
 
typedef FilteredCFGNode< ssa_private::DataflowCfgFilterFilteredCfgNode
 A filtered CFGNode that is used for DefUse traversal. More...
 
typedef FilteredCFGEdge< ssa_private::DataflowCfgFilterFilteredCfgEdge
 A filtered CFGEdge that is used for DefUse traversal. More...
 
typedef boost::shared_ptr< ReachingDefReachingDefPtr
 
typedef std::map< VarName, ReachingDefPtr > NodeReachingDefTable
 A map from each variable to its reaching definitions at the current node. More...
 
typedef boost::unordered_map< SgNode *, std::pair< NodeReachingDefTable, NodeReachingDefTable > > GlobalReachingDefTable
 The first table is the IN table. More...
 
typedef boost::unordered_map< SgNode *, NodeReachingDefTableUseTable
 Map from each node to the variables used at that node and their reaching definitions. More...
 

Public Member Functions

 StaticSingleAssignment (SgProject *proj)
 
void run (bool interprocedural, bool treatPointersAsStructures)
 Run the analysis. More...
 
void toDOT (const std::string fileName)
 Print the CFG with any UniqueNames and Def/Use information visible. More...
 
void toFilteredDOT (const std::string fileName)
 Print the CFG with any UniqueNames and Def/Use information visible. More...
 
void printOriginalDefs (SgNode *node)
 
void printOriginalDefTable ()
 
LocalDefUseTablegetOriginalDefTable ()
 Get the table of definitions for every node. More...
 
LocalDefUseTablegetLocalUsesTable ()
 
const NodeReachingDefTablegetOutgoingDefsAtNode (SgNode *node) const
 Returns the definitions of all the variables right after the given node has executed. More...
 
const NodeReachingDefTablegetReachingDefsAtNode_ (SgNode *node) const
 Returns the definitions of all the variables immediately before the given node has executed. More...
 
const NodeReachingDefTablegetUsesAtNode (SgNode *node) const
 Returns a list of all the variables used at this node. More...
 
const NodeReachingDefTablegetDefsAtNode (SgNode *node) const
 Returns a list of all the variables defined at the given node. More...
 
std::set< VarNamegetVarsUsedInSubtree (SgNode *root) const
 Returns a set of all the variables names that have uses in the subtree. More...
 
std::set< VarNamegetVarsDefinedInSubtree (SgNode *root) const
 Given a node, traverses all its children in the AST and collects all the variable names that have definitions in the subtree. More...
 
std::set< VarNamegetOriginalVarsDefinedInSubtree (SgNode *root) const
 Given a node, traverses all its children in the AST and collects all the variable names that have original definitions in the subtree. More...
 
NodeReachingDefTable getLastVersions (SgFunctionDeclaration *func) const
 Returns the last encountered definition of every variable. More...
 

Static Public Member Functions

static bool getDebug ()
 
static bool getDebugExtra ()
 
static bool isPrefixOfName (VarName name, VarName prefix)
 Find if the given prefix is a prefix of the given name. More...
 
static ssa_private::VarUniqueNamegetUniqueName (SgNode *node)
 Get the uniqueName attribute for the given node. More...
 
static const VarNamegetVarName (SgNode *node)
 Get the variable name of the given node. More...
 
static const VarNamegetVarForExpression (SgNode *node)
 If an expression evaluates to a reference of a variable, returns that variable. More...
 
static SgExpressionbuildVariableReference (const VarName &var, SgScopeStatement *scope=NULL)
 Get an AST fragment containing the appropriate varRefs and Dot/Arrow ops to access the given variable. More...
 
static bool isVarInScope (const VarName &var, SgNode *scope)
 Finds the scope of the given node, and returns true if the given variable is accessible there. More...
 
static std::string varnameToString (const VarName &vec)
 Get a string representation of a varName. More...
 
static void printLocalDefUseTable (const LocalDefUseTable &table)
 

Static Public Attributes

static VarName emptyName
 

Member Typedef Documentation

A compound variable name as used by the variable renaming.

Definition at line 109 of file staticSingleAssignment.h.

typedef boost::unordered_map<SgNode*, std::set<VarName> > StaticSingleAssignment::LocalDefUseTable

Describes the defs or uses at each node.

This is for local, rather than propagated, information.

Definition at line 112 of file staticSingleAssignment.h.

A filtered CFGNode that is used for DefUse traversal.

Definition at line 115 of file staticSingleAssignment.h.

A filtered CFGEdge that is used for DefUse traversal.

Definition at line 118 of file staticSingleAssignment.h.

typedef std::map<VarName, ReachingDefPtr> StaticSingleAssignment::NodeReachingDefTable

A map from each variable to its reaching definitions at the current node.

Definition at line 123 of file staticSingleAssignment.h.

The first table is the IN table.

The second table is the OUT table.

Definition at line 126 of file staticSingleAssignment.h.

Map from each node to the variables used at that node and their reaching definitions.

Definition at line 129 of file staticSingleAssignment.h.

Member Function Documentation

void StaticSingleAssignment::run ( bool  interprocedural,
bool  treatPointersAsStructures 
)

Run the analysis.

If interprocedural analysis is not enabled, functionc all expressions (SgFunctionCallExp) will not count as definitions of any variables.

Parameters
interproceduraltrue to enable interprocedural analysis, false to perform no interprocedural analysis.
treatPointersAsStructuresif true, p->x is versioned as if it were the variable p.x.
void StaticSingleAssignment::toDOT ( const std::string  fileName)

Print the CFG with any UniqueNames and Def/Use information visible.

Parameters
fileNameThe filename to save graph as. Filenames will be prepended.
void StaticSingleAssignment::toFilteredDOT ( const std::string  fileName)

Print the CFG with any UniqueNames and Def/Use information visible.

This will only print the nodes that are of interest to the filter function used by the def/use traversal.

Parameters
fileNameThe filename to save graph as. Filenames will be prepended.
LocalDefUseTable& StaticSingleAssignment::getOriginalDefTable ( )
inline

Get the table of definitions for every node.

These definitions are NOT propagated.

Returns
Definition table.

Definition at line 380 of file staticSingleAssignment.h.

const NodeReachingDefTable& StaticSingleAssignment::getOutgoingDefsAtNode ( SgNode node) const

Returns the definitions of all the variables right after the given node has executed.

This function does not work correctly for "container" nodes such as SgBasicBlock, SgCommaOp, SgExprStmt. If there is a definition at the node itself, e.g. SgAssignOp, it is included in the outgoing defs.

const NodeReachingDefTable& StaticSingleAssignment::getReachingDefsAtNode_ ( SgNode node) const

Returns the definitions of all the variables immediately before the given node has executed.

If there is a definition at the node itself, e.g. SgAssignOp, it is not included in the reaching defs.

const NodeReachingDefTable& StaticSingleAssignment::getUsesAtNode ( SgNode node) const

Returns a list of all the variables used at this node.

Note that uses don't propagate past an SgStatement. Each use is mapped to the reaching definition to which the use corresponds.

const NodeReachingDefTable& StaticSingleAssignment::getDefsAtNode ( SgNode node) const

Returns a list of all the variables defined at the given node.

Note that this will return an empty collections for nodes that do not modify any variables. Compare this function to getReachingDefsAtNode.

std::set<VarName> StaticSingleAssignment::getVarsUsedInSubtree ( SgNode root) const

Returns a set of all the variables names that have uses in the subtree.

std::set<VarName> StaticSingleAssignment::getVarsDefinedInSubtree ( SgNode root) const

Given a node, traverses all its children in the AST and collects all the variable names that have definitions in the subtree.

std::set<VarName> StaticSingleAssignment::getOriginalVarsDefinedInSubtree ( SgNode root) const

Given a node, traverses all its children in the AST and collects all the variable names that have original definitions in the subtree.

Expanded definitions are not included - for example if p.x is defined, p is not included.

NodeReachingDefTable StaticSingleAssignment::getLastVersions ( SgFunctionDeclaration func) const

Returns the last encountered definition of every variable.

Variables go out of scope, so quering for reaching definitions at the end of a function doesn't return the last versions of all variables.

static bool StaticSingleAssignment::isPrefixOfName ( VarName  name,
VarName  prefix 
)
static

Find if the given prefix is a prefix of the given name.

This will return whether the given name has the given prefix inside it.

ex. a.b.c has prefix a.b, but not a.c

Parameters
nameThe name to search.
prefixThe prefix to search for.
Returns
Whether or not the prefix is in this name.
static ssa_private::VarUniqueName* StaticSingleAssignment::getUniqueName ( SgNode node)
static

Get the uniqueName attribute for the given node.

Parameters
nodeNode to get the attribute from.
Returns
The attribute, or NULL.
static const VarName& StaticSingleAssignment::getVarName ( SgNode node)
static

Get the variable name of the given node.

Parameters
nodeThe node to get the name for.
Returns
The name, or empty name.
static const VarName& StaticSingleAssignment::getVarForExpression ( SgNode node)
static

If an expression evaluates to a reference of a variable, returns that variable.

Handles casts, comma ops, address of ops, etc. For example, Given the expression (...., &a), this method would return the VarName for a.

static SgExpression* StaticSingleAssignment::buildVariableReference ( const VarName var,
SgScopeStatement scope = NULL 
)
static

Get an AST fragment containing the appropriate varRefs and Dot/Arrow ops to access the given variable.

Parameters
varThe variable to construct access for.
scopeThe scope within which to construct the access.
Returns
An expression that access the given variable in the given scope.
static bool StaticSingleAssignment::isVarInScope ( const VarName var,
SgNode scope 
)
static

Finds the scope of the given node, and returns true if the given variable is accessible there.

False if the variable is not accessible.

static std::string StaticSingleAssignment::varnameToString ( const VarName vec)
static

Get a string representation of a varName.

Parameters
vecvarName to get string for.
Returns
String for given varName.

The documentation for this class was generated from the following file: