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);
};