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 <midend/programAnalysis/staticSingleAssignment/staticSingleAssignment.h>

Collaboration diagram for StaticSingleAssignment:

[legend]

Public Types
typedef std::vector< SgInitializedName * >	VarName
	A compound variable name as used by the variable renaming.

typedef boost::unordered_map< SgNode *, std::set< VarName > >	LocalDefUseTable
	Describes the defs or uses at each node.

typedef FilteredCFGNode< ssa_private::DataflowCfgFilter >	FilteredCfgNode
	A filtered CFGNode that is used for DefUse traversal.

typedef FilteredCFGEdge< ssa_private::DataflowCfgFilter >	FilteredCfgEdge
	A filtered CFGEdge that is used for DefUse traversal.

typedef boost::shared_ptr< ReachingDef >	ReachingDefPtr

typedef std::map< VarName, ReachingDefPtr >	NodeReachingDefTable
	A map from each variable to its reaching definitions at the current node.

typedef boost::unordered_map< SgNode *, std::pair< NodeReachingDefTable, NodeReachingDefTable > >	GlobalReachingDefTable
	The first table is the IN table.

typedef boost::unordered_map< SgNode *, NodeReachingDefTable >	UseTable
	Map from each node to the variables used at that node and their reaching definitions.

Public Member Functions
	StaticSingleAssignment (SgProject *proj)

void	run (bool interprocedural, bool treatPointersAsStructures)
	Run the analysis.

void	toDOT (const std::string fileName)
	Print the CFG with any UniqueNames and Def/Use information visible.

void	toFilteredDOT (const std::string fileName)
	Print the CFG with any UniqueNames and Def/Use information visible.

void	printOriginalDefs (SgNode *node)

void	printOriginalDefTable ()

LocalDefUseTable &	getOriginalDefTable ()
	Get the table of definitions for every node.

LocalDefUseTable &	getLocalUsesTable ()

const NodeReachingDefTable &	getOutgoingDefsAtNode (SgNode *node) const
	Returns the definitions of all the variables right after the given node has executed.

const NodeReachingDefTable &	getReachingDefsAtNode_ (SgNode *node) const
	Returns the definitions of all the variables immediately before the given node has executed.

const NodeReachingDefTable &	getUsesAtNode (SgNode *node) const
	Returns a list of all the variables used at this node.

const NodeReachingDefTable &	getDefsAtNode (SgNode *node) const
	Returns a list of all the variables defined at the given node.

std::set< VarName >	getVarsUsedInSubtree (SgNode *root) const
	Returns a set of all the variables names that have uses in the subtree.

std::set< VarName >	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 >	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.

NodeReachingDefTable	getLastVersions (SgFunctionDeclaration *func) const
	Returns the last encountered definition of every variable.

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.

static ssa_private::VarUniqueName *	getUniqueName (SgNode *node)
	Get the uniqueName attribute for the given node.

static const VarName &	getVarName (SgNode *node)
	Get the variable name of the given node.

static const VarName &	getVarForExpression (SgNode *node)
	If an expression evaluates to a reference of a variable, returns that variable.

static SgExpression *	buildVariableReference (const VarName &var, SgScopeStatement *scope=NULL)
	Get an AST fragment containing the appropriate varRefs and Dot/Arrow ops to access the given variable.

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.

static std::string	varnameToString (const VarName &vec)
	Get a string representation of a varName.

static void	printLocalDefUseTable (const LocalDefUseTable &table)

Static Public Attributes
static VarName	emptyName

Member Typedef Documentation

◆ VarName

typedef std::vector<SgInitializedName*> StaticSingleAssignment::VarName

A compound variable name as used by the variable renaming.

Definition at line 109 of file staticSingleAssignment.h.

◆ LocalDefUseTable

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.

◆ FilteredCfgNode

typedef FilteredCFGNode<ssa_private::DataflowCfgFilter> StaticSingleAssignment::FilteredCfgNode

A filtered CFGNode that is used for DefUse traversal.

Definition at line 115 of file staticSingleAssignment.h.

◆ FilteredCfgEdge

typedef FilteredCFGEdge<ssa_private::DataflowCfgFilter> StaticSingleAssignment::FilteredCfgEdge

A filtered CFGEdge that is used for DefUse traversal.

Definition at line 118 of file staticSingleAssignment.h.

◆ ReachingDefPtr

typedef boost::shared_ptr<ReachingDef> StaticSingleAssignment::ReachingDefPtr

Definition at line 120 of file staticSingleAssignment.h.

◆ NodeReachingDefTable

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.

◆ GlobalReachingDefTable

typedef boost::unordered_map<SgNode*, std::pair<NodeReachingDefTable, NodeReachingDefTable> > StaticSingleAssignment::GlobalReachingDefTable

The first table is the IN table.

The second table is the OUT table.

Definition at line 126 of file staticSingleAssignment.h.

◆ UseTable

typedef boost::unordered_map<SgNode*, NodeReachingDefTable> StaticSingleAssignment::UseTable

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

Definition at line 129 of file staticSingleAssignment.h.

Constructor & Destructor Documentation

◆ StaticSingleAssignment()

StaticSingleAssignment::StaticSingleAssignment ( SgProject * proj )

inline

Definition at line 169 of file staticSingleAssignment.h.

◆ ~StaticSingleAssignment()

StaticSingleAssignment::~StaticSingleAssignment ( )

inline

Definition at line 173 of file staticSingleAssignment.h.

Member Function Documentation

◆ run()

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

interprocedural	true to enable interprocedural analysis, false to perform no interprocedural analysis.
treatPointersAsStructures	if true, p->x is versioned as if it were the variable p.x.

◆ getDebug()

static bool StaticSingleAssignment::getDebug ( )

inlinestatic

Definition at line 183 of file staticSingleAssignment.h.

◆ getDebugExtra()

static bool StaticSingleAssignment::getDebugExtra ( )

inlinestatic

Definition at line 188 of file staticSingleAssignment.h.

◆ toDOT()

void StaticSingleAssignment::toDOT ( const std::string fileName )

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

Parameters

fileName The filename to save graph as. Filenames will be prepended.

◆ toFilteredDOT()

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

fileName The filename to save graph as. Filenames will be prepended.

◆ getOriginalDefTable()

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.

◆ getLocalUsesTable()

LocalDefUseTable & StaticSingleAssignment::getLocalUsesTable ( )

inline

Definition at line 385 of file staticSingleAssignment.h.

◆ getOutgoingDefsAtNode()

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.

◆ getReachingDefsAtNode_()

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.

◆ getUsesAtNode()

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.

◆ getDefsAtNode()

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.

◆ getOriginalVarsDefinedInSubtree()

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.

◆ getLastVersions()

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.

◆ isPrefixOfName()

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

name	The name to search.
prefix	The prefix to search for.

Returns: Whether or not the prefix is in this name.

◆ getUniqueName()

static ssa_private::VarUniqueName * StaticSingleAssignment::getUniqueName ( SgNode * node )

static

Get the uniqueName attribute for the given node.

Parameters

node	Node to get the attribute from.

Returns: The attribute, or NULL.

◆ getVarName()

static const VarName & StaticSingleAssignment::getVarName ( SgNode * node )

static

Get the variable name of the given node.

Parameters

node	The node to get the name for.

Returns: The name, or empty name.

◆ getVarForExpression()

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.

◆ buildVariableReference()

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

var	The variable to construct access for.
scope	The scope within which to construct the access.

Returns: An expression that access the given variable in the given scope.

◆ isVarInScope()

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.

◆ varnameToString()

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

static

Get a string representation of a varName.

Parameters

vec	varName to get string for.

Returns: String for given varName.

Member Data Documentation

◆ emptyName

VarName StaticSingleAssignment::emptyName

static

Definition at line 348 of file staticSingleAssignment.h.

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

staticSingleAssignment.h

Description

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Member Typedef Documentation

◆ VarName

◆ LocalDefUseTable

◆ FilteredCfgNode

◆ FilteredCfgEdge

◆ ReachingDefPtr

◆ NodeReachingDefTable

◆ GlobalReachingDefTable

◆ UseTable

Constructor & Destructor Documentation

◆ StaticSingleAssignment()

◆ ~StaticSingleAssignment()

Member Function Documentation

◆ run()

◆ getDebug()

◆ getDebugExtra()

◆ toDOT()

◆ toFilteredDOT()

◆ getOriginalDefTable()

◆ getLocalUsesTable()

◆ getOutgoingDefsAtNode()

◆ getReachingDefsAtNode_()

◆ getUsesAtNode()

◆ getDefsAtNode()

◆ getOriginalVarsDefinedInSubtree()

◆ getLastVersions()

◆ isPrefixOfName()

◆ getUniqueName()

◆ getVarName()

◆ getVarForExpression()

◆ buildVariableReference()

◆ isVarInScope()

◆ varnameToString()

Member Data Documentation

◆ emptyName