staticSingleAssignment.h

//Author: George Vulov <georgevulov@hotmail.com>
//Based on work by Justin Frye <jafrye@tamu.edu>
 
#pragma once
 
// DQ (10/5/2014): This is more strict now that we include rose_config.h in the sage3basic.h.
// #include "rose.h"
// rose.h and sage3basic.h should not be included in librose header files. [Robb P. Matzke 2014-10-15]
// #include "sage3basic.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
    {
 
#define DEBUG_SSA_FILTER 0
 
        bool operator()(SgFunctionDeclaration * funcDecl)
        {
            ROSE_ASSERT(funcDecl != NULL);
 
         // DQ (8/30/2016): Reorganize this to allow it to be more easily debugged.
            bool returnValue = true;
 
         // Don't process any built-in functions
            std::string filename = funcDecl->get_file_info()->get_filename();
#if DEBUG_SSA_FILTER
            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());
#endif
            if (filename.find("include") != std::string::npos)
              {
                returnValue = false;
              }
 
         // DQ (8/30/2016): Don't allow template functions.
         // if (isSgTemplateFunctionDeclaration(funcDecl) || isSgTemplateMemberFunctionDeclaration(funcDecl))
         // if (returnValue == true && funcDecl->get_file_info()->isCompilerGenerated() && !isSgTemplateInstantiationFunctionDecl(funcDecl)
         //         && !isSgTemplateInstantiationMemberFunctionDecl(funcDecl))
            SgFunctionDeclaration* definingFunction = isSgFunctionDeclaration(funcDecl->get_definingDeclaration());
            bool functionDefinitionIsCompilerGenerated = definingFunction != NULL ? definingFunction->isCompilerGenerated() : false;
 
#if DEBUG_SSA_FILTER
            printf ("definingFunction = %p functionDefinitionIsCompilerGenerated = %s \n",definingFunction,functionDefinitionIsCompilerGenerated ? "true" : "false");
#endif
 
            if (returnValue == true && functionDefinitionIsCompilerGenerated && !isSgTemplateInstantiationFunctionDecl(funcDecl)
                    && !isSgTemplateInstantiationMemberFunctionDecl(funcDecl))
              {
#if DEBUG_SSA_FILTER
                printf ("In FunctionFilter::operator(): compiler generated and is NOT a template instantiation function or member function: setting returnValue == false \n");
#endif
                returnValue = false;
              }
 
         // We don't process functions that don't have definitions
            if (returnValue == true && funcDecl->get_definingDeclaration() == NULL)
              {
#if DEBUG_SSA_FILTER
                printf ("In FunctionFilter::operator(): funcDecl->get_definingDeclaration() == NULL: setting returnValue == false \n");
#endif
                returnValue = false;
              }
 
#if DEBUG_SSA_FILTER
            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");
#endif
 
            return returnValue;
        }
    };
 
} //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);
};