staticSingleAssignment.h

Go to the documentation of this file.

//Author: George Vulov <georgevulov@hotmail.com>
//Based on work by Justin Frye <jafrye@tamu.edu>

#pragma once

#include <rose.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>
#include "reachingDef.h"
#include "dataflowCfgFilter.h"
#include "CallGraph.h"
#include "uniqueNameTraversal.h"

namespace ssa_private
{

    struct FunctionFilter
    {

        bool operator()(SgFunctionDeclaration * funcDecl)
        {
            ROSE_ASSERT(funcDecl != NULL);

            //Don't process any built-in functions
            std::string filename = funcDecl->get_file_info()->get_filename();
            if (filename.find("include") != std::string::npos)
                return false;

            //Exclude compiler generated functions, but keep template instantiations
            if (funcDecl->get_file_info()->isCompilerGenerated() && !isSgTemplateInstantiationFunctionDecl(funcDecl)
                    && !isSgTemplateInstantiationMemberFunctionDecl(funcDecl))
                return false;

            //We don't process functions that don't have definitions
            if (funcDecl->get_definingDeclaration() == NULL)
                return false;

            return true;
        }
    };

} //namespace ssa_private

class ROSE_DLL_API StaticSingleAssignment
{
private:
    SgProject* project;

public:

    typedef std::vector<SgInitializedName*> VarName;

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

    typedef FilteredCFGNode<ssa_private::DataflowCfgFilter> FilteredCfgNode;

    typedef FilteredCFGEdge<ssa_private::DataflowCfgFilter> FilteredCfgEdge;

    typedef boost::shared_ptr<ReachingDef> ReachingDefPtr;

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

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

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

private:
    //Private member variables

    LocalDefUseTable originalDefTable;

    LocalDefUseTable expandedDefTable;

    GlobalReachingDefTable reachingDefsTable;

    LocalDefUseTable localUsesTable;

    UseTable useTable;

    boost::unordered_map<SgNode*, NodeReachingDefTable> ssaLocalDefTable;

public:

    StaticSingleAssignment(SgProject* proj) : project(proj)
    {
    }

    ~StaticSingleAssignment()
    {
    }

    void run(bool interprocedural, bool treatPointersAsStructures);

    static bool getDebug()
    {
        return SgProject::get_verbose() > 0;
    }

    static bool getDebugExtra()
    {
        return SgProject::get_verbose() > 1;
    }

private:
    void runDefUseDataFlow(SgFunctionDefinition* func);

    static bool isBuiltinVar(const VarName& var);

    void expandParentMemberDefinitions(SgFunctionDeclaration* function);

    void expandParentMemberUses(SgFunctionDeclaration* function);

    void insertDefsForChildMemberUses(SgFunctionDeclaration* function);

    void insertDefsForExternalVariables(SgFunctionDeclaration* function);

    std::multimap< FilteredCfgNode, std::pair<FilteredCfgNode, FilteredCfgEdge> > insertPhiFunctions(SgFunctionDefinition* function,
            const std::vector<FilteredCfgNode>& cfgNodesInPostOrder);

    void populateLocalDefsTable(SgFunctionDeclaration* function);

    void renumberAllDefinitions(SgFunctionDefinition* func, const std::vector<FilteredCfgNode>& cfgNodesInPostOrder);

    void updateIncomingPropagatedDefs(FilteredCfgNode cfgNode);

    bool propagateDefs(FilteredCfgNode cfgNode);

    void buildUseTable(const std::vector<FilteredCfgNode>& cfgNodes);

    static std::vector<FilteredCfgNode> getCfgNodesInPostorder(SgFunctionDefinition* func);

    //------------ INTERPROCEDURAL ANALYSIS FUNCTIONS ------------ //

    void interproceduralDefPropagation(const boost::unordered_set<SgFunctionDefinition*>& interestingFunctions);

    std::vector<SgFunctionDefinition*> calculateInterproceduralProcessingOrder(
            const boost::unordered_set<SgFunctionDefinition*>& interestingFunctions);

    void processCalleesThenFunction(SgFunctionDefinition* targetFunction, SgIncidenceDirectedGraph* callGraph,
            const boost::unordered_map<SgFunctionDefinition*, SgGraphNode*>& graphNodeToFunction,
            std::vector<SgFunctionDefinition*> &processingOrder, std::set<SgFunctionDefinition*> visited);

    bool insertInterproceduralDefs(SgFunctionDefinition* funcDef, const boost::unordered_set<SgFunctionDefinition*>& processed,
            ClassHierarchyWrapper* classHierarchy);

    void processOneCallSite(SgExpression* callSite, SgFunctionDeclaration* callee,
            const boost::unordered_set<SgFunctionDefinition*>& processed, ClassHierarchyWrapper* classHierarchy);

    static bool isVarAccessibleFromCaller(const VarName& var, SgExpression* callSite, SgFunctionDeclaration* callee);

    static bool varRequiresThisPointer(const VarName& var);

    static bool isThisPointerSameInCallee(SgFunctionCallExp* callSite, SgMemberFunctionDeclaration* callee);

    static bool isThisPointer(SgExpression* expression);

    static bool isDeepConstPointer(SgType* type);

    static bool isPointerToDeepConst(SgType* type);

    static bool isArgumentNonConstReferenceOrPointer(SgInitializedName* formalArgument);

    //------------ GRAPH OUTPUT FUNCTIONS ------------ //

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

public:
    //External static helper functions/variables

    static VarName emptyName;

    /*
     *  Printing functions.
     */

    void toDOT(const std::string fileName);

    void toFilteredDOT(const std::string fileName);

    void printOriginalDefs(SgNode* node);
    void printOriginalDefTable();


    //------------ DEF/USE TABLE ACCESS FUNCTIONS ------------ //

    LocalDefUseTable& getOriginalDefTable()
    {
        return originalDefTable;
    }

    LocalDefUseTable& getLocalUsesTable()
    {
        return localUsesTable;
    }

    const NodeReachingDefTable& getOutgoingDefsAtNode(SgNode* node) const;

    const NodeReachingDefTable& getReachingDefsAtNode_(SgNode* node) const;

    const NodeReachingDefTable& getUsesAtNode(SgNode* node) const;

    const NodeReachingDefTable& getDefsAtNode(SgNode* node) const;

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

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

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

    NodeReachingDefTable getLastVersions(SgFunctionDeclaration* func) const;

    //------------ STATIC UTILITY FUNCTIONS FUNCTIONS ------------ //


    static bool isPrefixOfName(VarName name, VarName prefix);

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

    static const VarName& getVarName(SgNode* node);

    static const VarName& getVarForExpression(SgNode* node);

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

    static bool isVarInScope(const VarName& var, SgNode* scope);

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

    static void printLocalDefUseTable(const LocalDefUseTable& table);
};