SDG.h

Go to the documentation of this file.

/* 
 * File:   SDG.h
 * Author: Cong Hou [hou_cong@gatech.edu]
 */

#ifndef _______SDG_H_______
#define _______SDG_H_______

#include "PDG.h"
#include <boost/function.hpp>
#include <boost/unordered_map.hpp>

namespace SDG
{

typedef std::vector<SgInitializedName*> VarName;
typedef std::map<SgNode*, std::set<SgNode*> > DefUseChains;

struct SDGNode
{
    enum NodeType
    {
        Entry,
        ASTNode,
        FunctionCall,
        ActualIn,
        ActualOut,
        FormalIn,
        FormalOut
    };

    SDGNode(NodeType t) : type(t), astNode(NULL) {}

    NodeType type;

    //CFGNodePtr cfgNode;

    SgNode* astNode;

    //SgFunctionDefinition* funcDef;

};

struct SDGEdge
{
    enum EdgeType
    {
        ControlDependence,
        DataDependence,
        ParameterIn,
        ParameterOut,
        Call,
        Summary
    };

    enum ControlDependenceType
    {
        cdTrue,
        cdFalse,
        cdCase,
        cdDefault
    };

    SDGEdge(EdgeType t) : type(t) {}

    EdgeType type;

    //============================================================================//
    // Control dependence
    void setTrue()  { condition = cdTrue; }
    void setFalse() { condition = cdFalse; }
    void setCondition(VirtualCFG::EdgeConditionKind cond, SgExpression* expr = NULL);

    ControlDependenceType condition;

    SgExpression* caseLabel;


    //============================================================================//
    // Data dependence

    std::set<VarName> varNames;
};



class SystemDependenceGraph : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
SDGNode*, SDGEdge*>
{
    public:
        typedef boost::graph_traits<SystemDependenceGraph>::vertex_descriptor Vertex;
        typedef boost::graph_traits<SystemDependenceGraph>::edge_descriptor   Edge;

    protected:
        typedef StaticCFG::ControlFlowGraph CFG;
        typedef CFG::Vertex                 CFGVertex;
        typedef CFG::Edge                   CFGEdge;

        typedef boost::function<void(SgProject*, DefUseChains&)> DefUseChainsGen;
        //typedef std::vector<DefUseChain> DefUseChains;

    protected:

        SgProject* project_;

        StaticCFG::CFGNodeFilter cfgNodefilter_;

        std::map<SgFunctionDeclaration*, CFG*> functionsToCFGs_;

        std::map<SgFunctionDeclaration*, Vertex> functionsToEntries_;

        boost::function<void(SgProject*, DefUseChains&)> defUseChainGenerator_;


        struct CallSiteInfo
        {
            CallSiteInfo() : funcCall(NULL), isVoid(true) {}
            typedef SystemDependenceGraph::Vertex Vertex;

            SgFunctionCallExp* funcCall;
            Vertex vertex;
            std::vector<Vertex> inPara;
            std::vector<Vertex> outPara;
            // If the called function returns anything.
            bool isVoid;
            Vertex returned;
        };

    public:
        SystemDependenceGraph(SgProject* project, StaticCFG::CFGNodeFilter filter)
            : project_(project), cfgNodefilter_(filter)
        {}

        void build();

        void setCFGNodeFilter(StaticCFG::CFGNodeFilter filter)
        { cfgNodefilter_ = filter; }

        void setDefUseChainsGenerator(const DefUseChainsGen& defUseChainsGen)
        { defUseChainGenerator_ = defUseChainsGen; }


        void toDot(const std::string& filename) const;

    protected:
        Vertex addVertex(SDGNode* sdgNode) 
        { 
            Vertex newVertex = boost::add_vertex(*this);
            (*this)[newVertex] = sdgNode;
            return newVertex;
        }

        Edge addEdge(Vertex src, Vertex tgt, SDGEdge* sdgEdge)
        {
            Edge newEdge = boost::add_edge(src, tgt, *this).first;
            (*this)[newEdge] = sdgEdge;
            return newEdge;
        }

        void addTrueCDEdge(Vertex src, Vertex tgt);

        void addControlDependenceEdges(
                const boost::unordered_map<CFGVertex, Vertex>& cfgVerticesToSdgVertices,
                const CFG& cfg, Vertex entry);

        void addDataDependenceEdges(
                const boost::unordered_map<SgNode*, Vertex>& astNodesToSdgVertices,
                const std::vector<CallSiteInfo>& callSiteInfo,
                const std::map<SgNode*, Vertex>& formalOutPara);

        void writeGraphNode(std::ostream& out, const Vertex& vertex) const;

        void writeGraphEdge(std::ostream& out, const Edge& edge) const;

        void writeGraphProperty(std::ostream& out) const;

};

} // end of Backstroke

#endif /* _______SDG_H_______ */