VariableRenaming.h

Go to the documentation of this file.

//Author: Justin Frye

#ifndef SSAANALYSIS_H
#define SSAANALYSIS_H

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <ostream>
#include <fstream>
#include <sstream>
#include <boost/foreach.hpp>
#include "filteredCFG.h"
#include <boost/unordered_map.hpp>

class VarUniqueName : public AstAttribute
{
private:

    std::vector<SgInitializedName*> key;

    bool usesThis; // this pointer??

public:
    VarUniqueName() : key(), usesThis(false)
    {
    }

    VarUniqueName(SgInitializedName* thisNode):usesThis(false)
    {
        key.push_back(thisNode);
    }

    VarUniqueName(const std::vector<SgInitializedName*>& prefix, SgInitializedName* thisNode):usesThis(false)
    {
        key.assign(prefix.begin(),prefix.end());
        key.push_back(thisNode);
    }

    VarUniqueName(const VarUniqueName& other): AstAttribute(other), usesThis(false)
    {
        key.assign(other.key.begin(), other.key.end());
    }

    VarUniqueName* copy()
    {
        VarUniqueName* newName = new VarUniqueName(*this);
        return newName;
    }

    std::vector<SgInitializedName*>& getKey() { return key; }

    void setKey(const std::vector<SgInitializedName*>& newKey) { key.assign(newKey.begin(),newKey.end()); }

    bool getUsesThis() { return usesThis; }
    void setUsesThis(bool uses) { usesThis = uses; }

    std::string getNameString()
    {
        std::string name = "";
        std::vector<SgInitializedName*>::iterator iter;
        if(usesThis)
            name += "this->";
        for(iter = key.begin(); iter != key.end(); ++iter)
        {
            if(iter != key.begin())
            {
                name += ":"; // why ":" instead of "." ??
            }
            name += (*iter)->get_name().getString();
        }

        return name;
    }
};
struct IsDefUseFilter
{
        bool operator() (CFGNode cfgn) const
        {
                SgNode *node = cfgn.getNode();

                //If it is the last node in a function call, keep it
                if (isSgFunctionCallExp(node) && cfgn == node->cfgForEnd())
                        return true;

                //The begin edges of basic blocks are not considered interesting, but we would like to keep them
                //This is so we can propagate reachable defs to the top of a basic block
                if (isSgBasicBlock(node) && cfgn == node->cfgForBeginning())
                        return true;

                if (isSgExprStatement(node))
                        return (cfgn == node->cfgForBeginning());

                if (isSgCommaOpExp(node))
                        return (cfgn == node->cfgForBeginning());

                //Remove all non-interesting nodes 
                //putting this if-statement here may shadow the rest statements, by Liao
                //TODO this may be a bug, it should be moved to the end
                if (!cfgn.isInteresting())
                        return false;

                //Remove all non-end nodes for initNames
                if (isSgInitializedName(node) && cfgn != node->cfgForEnd())
                        return false;

                //Remove non-beginning nodes for try statements
                if (isSgTryStmt(node) && cfgn != node->cfgForBeginning())
                        return false;

                //Use the last node of binary operators
                if (isSgAndOp(node) || isSgOrOp(node))
                {
                        if (cfgn != node->cfgForEnd())
                                return false;
                }

                //We only want the middle appearance of the teritatry operator - after its conditional expression
                //and before the true and false bodies. This makes it behave as an if statement for data flow
                //purposes
                if (isSgConditionalExp(node))
                {
                        return cfgn.getIndex() == 1;
                }

                return true;
        }
};

class VariableRenaming
{
private:
    SgProject* project;
    bool DEBUG_MODE;
    bool DEBUG_MODE_EXTRA;

public:
    typedef std::vector<SgNode*> NodeVec;
    typedef std::vector<SgInitializedName*> VarName;
    typedef std::map<VarName, NodeVec> TableEntry;
    typedef boost::unordered_map<SgNode*, TableEntry> DefUseTable;
    typedef boost::unordered_map<VarName, SgNode*> FirstDefTable;

    typedef std::vector<SgInitializedName*> InitNameVec;
    typedef FilteredCFGNode<IsDefUseFilter> cfgNode;
    typedef FilteredCFGEdge<IsDefUseFilter> cfgEdge;
    typedef std::vector<cfgNode> cfgNodeVec;
    typedef std::vector<cfgEdge> cfgEdgeVec;
    typedef std::map<SgNode*, int> NodeNumRenameEntry;
    typedef boost::unordered_map<VarName, NodeNumRenameEntry> NodeNumRenameTable;
    typedef std::map<int, SgNode*> NumNodeRenameEntry;
    typedef boost::unordered_map<VarName, NumNodeRenameEntry> NumNodeRenameTable;


private:
    //Private member variables

    DefUseTable originalDefTable;

    DefUseTable expandedDefTable;

    DefUseTable defTable;

    DefUseTable useTable;

    FirstDefTable firstDefList;

    NodeNumRenameTable nodeRenameTable;

    NumNodeRenameTable numRenameTable;

public:
    VariableRenaming(SgProject* proj): project(proj), DEBUG_MODE(SgProject::get_verbose() > 0), DEBUG_MODE_EXTRA(SgProject::get_verbose() > 1){}

    ~VariableRenaming(){}
    
    void run();

    bool getDebug() const { return DEBUG_MODE; }
    bool getDebugExtra() const { return DEBUG_MODE_EXTRA; }
    
private:
    void runDefUse(SgFunctionDefinition* func);
    bool defUse(cfgNode node, bool *memberRefInserted, NodeVec &changedNodes);

    int addRenameNumberForNode(const VarName& var, SgNode* node);

    bool isBuiltinVar(const VarName& var);

    bool mergeDefs(cfgNode curNode, bool *memberRefInserted, NodeVec &changedNodes);

    bool resolveUses(cfgNode curNode, bool *memberRefInserted, NodeVec &changedNodes);

    void aggregatePreviousDefs(cfgNode curNode, TableEntry& results);

    bool expandMemberDefinitions(cfgNode curNode);

    bool insertExpandedDefsForUse(cfgNode curNode, VarName name, NodeVec &changedNodes);

    bool expandMemberUses(cfgNode curNode);

        void insertDefsForExternalVariables(SgFunctionDeclaration* function);

        std::set<VarName> getVarsUsedInSubtree(SgNode* root);

    void printToDOT(SgSourceFile* file, std::ofstream &outFile);
    void printToFilteredDOT(SgSourceFile* file, std::ofstream &outFile);

    void printUses(const TableEntry& table);
    void printDefs(const TableEntry& table);
    
public:
    //External static helper functions/variables
    static std::string varKeyTag;

    static SgInitializedName* thisDecl;

    static VarName emptyName;

    static NumNodeRenameTable emptyRenameTable;

    static NumNodeRenameEntry emptyRenameEntry;


    /*
     *  Printing functions.
     */

    void toDOT(const std::string fileName);
    
    void toFilteredDOT(const std::string fileName);

    static std::string keyToString(const VarName& vec);
    
    void printDefs(SgNode* node);

    void printOriginalDefs(SgNode* node);

    void printOriginalDefTable();

    void printUses(SgNode* node);

    void printRenameTable();

    void printRenameTable(const VarName& var);

    static void printRenameTable(const NodeNumRenameTable& table);

    static void printRenameTable(const NumNodeRenameTable& table);

    static void printRenameEntry(const NodeNumRenameEntry& entry);
    
    static void printRenameEntry(const NumNodeRenameEntry& entry);



    /*
     *   Def/Use Table Access Functions
     */

    DefUseTable& getDefTable(){ return originalDefTable; }

    const DefUseTable& getDefTable() const { return originalDefTable; }

    DefUseTable& getPropDefTable(){ return defTable; }

    const DefUseTable& getPropDefTable() const { return defTable; }

    DefUseTable& getUseTable(){ return useTable; }

    const DefUseTable& getUseTable() const { return useTable; }



    /*
     *   Rename Table Access Functions
     */

    int getRenameNumberForNode(const VarName& var, SgNode* node) const;

    SgNode* getNodeForRenameNumber(const VarName& var, int num) const;

    int getMaxRenameNumberForName(const VarName& var) const;



    /*
     *   Variable Renaming Access Functions
     */

    NodeVec getAllUsesForDef(const VarName& var, int num);

    template<typename T> inline std::vector<T*> getAllUsesForDef(const VarName& var, int num)
    {
        NodeVec vec = getAllUsesForDef(var, num);
        std::vector<T*> res;
        T* temp = NULL;

        BOOST_FOREACH(NodeVec::value_type& val, vec)
        {
            temp = dynamic_cast<T*>(val);
            if(temp != NULL)
            {
                //Push back if it casts correctly.
                res.push_back(temp);
            }
        }

        return res;
    }

    NumNodeRenameTable getReachingDefsAtNode(SgNode* node);

    NumNodeRenameEntry getReachingDefsAtNodeForName(SgNode* node, const VarName& var);

    NumNodeRenameTable getReachingDefsAtScopeEnd(SgScopeStatement* scope);

    NumNodeRenameTable getReachingDefsAtFunctionEnd(SgFunctionDefinition* node);

    NumNodeRenameEntry getReachingDefsAtFunctionEndForName(SgFunctionDefinition* node, const VarName& var);

        NumNodeRenameTable getReachingDefsAtStatementStart(SgStatement* statement);

    NumNodeRenameTable getReachingDefsAtFunctionStart(SgFunctionDefinition* node);

    NumNodeRenameEntry getReachingDefsAtFunctionStartForName(SgFunctionDefinition* node, const VarName& var);

    NumNodeRenameTable getUsesAtNode(SgNode* node);

    NumNodeRenameTable getOriginalUsesAtNode(SgNode* node);

    NumNodeRenameEntry getUsesAtNodeForName(SgNode* node, const VarName& var);

    NumNodeRenameTable getDefsAtNode(SgNode* node);

    NumNodeRenameEntry getDefsAtNodeForName(SgNode* node, const VarName& var);

    NumNodeRenameTable getOriginalDefsAtNode(SgNode* node);

    NumNodeRenameEntry getOriginalDefsAtNodeForName(SgNode* node, const VarName& var);

    NumNodeRenameTable getExpandedDefsAtNode(SgNode* node);

    NumNodeRenameEntry getExpandedDefsAtNodeForName(SgNode* node, const VarName& var);

    NumNodeRenameTable getDefsForSubtree(SgNode* node);

    NumNodeRenameTable getOriginalDefsForSubtree(SgNode* node);

    /*
     *   Static Utility Functions
     */

    static bool isPrefixOfName(VarName name, VarName prefix);

    static VarUniqueName* getUniqueName(SgNode* node);

    static VarName getVarName(SgNode* node);

    static bool isFromLibrary(SgFunctionDeclaration* node);

    static SgExpression* buildVariableReference(const VarName& var, SgScopeStatement* scope = NULL);

private:

    class VarRefSynthAttr
    {
    private:
        std::vector<SgNode*> refs;

    public:
        VarRefSynthAttr():refs(){}

        VarRefSynthAttr(SgNode* thisNode)
        {
            refs.push_back(thisNode);
        }

        VarRefSynthAttr(const std::vector<SgNode*>& subtree, SgNode* thisNode)
        {
            refs.assign(subtree.begin(), subtree.end());
            refs.push_back(thisNode);
        }

        VarRefSynthAttr(const std::vector<SgNode*>& subtree)
        {
            refs.assign(subtree.begin(), subtree.end());
        }

        const std::vector<SgNode*>& getRefs() { return refs; }

        void setRefs(const std::vector<SgNode*>& newRefs) { refs.assign(newRefs.begin(), newRefs.end()); }
    };

    class UniqueNameTraversal : public AstBottomUpProcessing<VariableRenaming::VarRefSynthAttr>
    {
        VariableRenaming* varRename;
                
                std::vector<SgInitializedName*> allInitNames;

                SgInitializedName* resolveTemporaryInitNames(SgInitializedName* name);

    public:
        UniqueNameTraversal(VariableRenaming* varRenaming, const std::vector<SgInitializedName*>& allNames):
                        varRename(varRenaming), allInitNames(allNames)
                {
                }

        virtual VariableRenaming::VarRefSynthAttr evaluateSynthesizedAttribute(SgNode* node, SynthesizedAttributesList attrs);
    };

        class ChildUses
        {
        private:
                SgVarRefExp* currentVar;

                std::vector<SgNode*> uses;

        public:

                ChildUses() : currentVar(NULL)
                { }

                ChildUses(SgNode* useNode, SgVarRefExp* var)
                {
                        uses.push_back(useNode);
                        currentVar = var;
                }

                ChildUses(const std::vector<SgNode*>& useTree, SgVarRefExp* var = NULL)
                {
                        if (useTree.size() > 0)
                                uses.assign(useTree.begin(), useTree.end());
                        currentVar = var;
                }

                std::vector<SgNode*>& getUses()
                {
                        return uses;
                }

                void setUses(const std::vector<SgNode*>& newUses)
                {
                        uses.assign(newUses.begin(), newUses.end());
                }

                SgVarRefExp* getCurrentVar() const
                {
                        return currentVar;
                }
        };

        class DefsAndUsesTraversal : public AstBottomUpProcessing<ChildUses>
        {
                VariableRenaming* ssa;

        public:

                DefsAndUsesTraversal(VariableRenaming* ssa) : ssa(ssa) { }

                virtual ChildUses evaluateSynthesizedAttribute(SgNode* node, SynthesizedAttributesList attrs);

        private:

                void addUsesToNode(SgNode* node, std::vector<SgNode*> uses);

                void addDefForVarAtNode(SgVarRefExp* currentVar, SgNode* defNode);
        };

};

#endif  /* SSAANALYSIS_H */