newCDG.h

Go to the documentation of this file.

#ifndef ___________CDG_H__________
#define ___________CDG_H__________

#include "cong_staticCFG.h"
using namespace StaticCFG;

namespace SDG
{


struct CDGEdge
{
    ControlFlowGraph::Edge cfgEdge;
    
    VirtualCFG::EdgeConditionKind condition;

    SgExpression* caseLabel;
    
    std::string toString() const 
    {
        switch (condition) 
        {
        case eckTrue:
            return "T";
        case eckFalse:
            return "F";
        case eckCaseLabel:
            return "case" + caseLabel->unparseToString();
        case eckDefault:
            return "default";
        default: 
            break;
        }
        return "";
    }
};


class ControlDependenceGraph : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
                CFGNodePtr, CDGEdge>
{
public:    
    typedef boost::graph_traits<ControlDependenceGraph> GraphTraits;
        typedef GraphTraits::vertex_descriptor Vertex;
        typedef GraphTraits::edge_descriptor   Edge;


    struct ControlDependence 
    {
        ControlDependence(const CDGEdge& edge, SgNode* node)
        : cdEdge(edge), cdNode(node) {}

        CDGEdge cdEdge;

        //CDGNode cdNode;

        SgNode* cdNode;
    };

    typedef std::vector<ControlDependence> ControlDependences;

        ControlDependenceGraph() {}

        ControlDependenceGraph(const ControlFlowGraph& cfg)
        { build(cfg); }

        void build(const ControlFlowGraph& cfg);
    
    ControlDependences getControlDependences(CFGNodePtr cfgNode);
    
    ControlDependences getControlDependences(SgNode* astNode);
    
    Vertex getCDGVertex(SgNode* astNode);

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

        static void writeGraphEdge(std::ostream& out, const CDGEdge& edge);
        
protected:

        typedef std::map<
                ControlFlowGraph::Vertex,
                std::map<ControlFlowGraph::Vertex, 
                                std::vector<ControlFlowGraph::Edge> > >
        DominanceFrontiersT;
        
        bool checkCycle(const ControlFlowGraph& cfg);

        void writeGraphNode(std::ostream& out, const Vertex& node) const
        {
                writeCFGNode(out, *(*this)[node]);
        }

        void writeGraphEdge(std::ostream& out, const Edge& edge) const
        {
                writeGraphEdge(out, (*this)[edge]);
        }

        void appendSuccessors(
                Vertex v,
                std::vector<Vertex>& vertices,
                const std::map<Vertex, std::set<Vertex> >& iSucc);

        DominanceFrontiersT     buildDominanceFrontiers(
                const std::map<ControlFlowGraph::Vertex, ControlFlowGraph::Vertex>& iDom, const ControlFlowGraph& cfg);    
};


} // end of namespace

#endif  /* ___________CDG_H__________ */