dominanceAnalysis/DominatorTree.h

Go to the documentation of this file.

#ifndef _DOMINATORTREE_H_
#define _DOMINATORTREE_H_

#include <GraphDotOutput.h>
#include <map>
#include "filteredCFG.h"
// #include "rose.h"
namespace DominatorTreesAndDominanceFrontiers
{
        /* ! \class TemplatedDominatorTree
                 This class constructs either a dominator or a post-dominator tree for a control-flow-graph.  */

        typedef enum Dir_ection
        {
                PRE_DOMINATOR,          /* !< This indicates that we are building a
                                                                                                                         dominator tree */
                POST_DOMINATOR          /* !< This indicates that we are building a
                                                                                                                         post-dominator tree */
        } Direction;
        template < typename CFGFilterFunction > class DominatorForwardBackwardWrapperClass
        {
                public:
                        // ! Constructor for the DominatorForwardBackwardWrapperClass
                        DominatorForwardBackwardWrapperClass(Direction dir):treeDirection(dir)
                        {
                        };

                        // ! returns whether this is a dominator tree (PRE) or a
                        // post-dominator tree (POST)
                        Direction getDirection()
                        {
                                return treeDirection;
                        }
                        
                protected:
                        std::vector < VirtualCFG::FilteredCFGEdge < CFGFilterFunction > > getDirectionModifiedOutEdges(VirtualCFG::FilteredCFGNode < CFGFilterFunction >
                                                current)
                                {
                                        if (treeDirection == PRE_DOMINATOR)
                                                return current.outEdges();
                                        else
                                                return current.inEdges();
                                }
                        std::vector < VirtualCFG::FilteredCFGEdge < CFGFilterFunction > > getDirectionModifiedInEdges(VirtualCFG::FilteredCFGNode < CFGFilterFunction >
                                                current)
                                {
                                        if (treeDirection == PRE_DOMINATOR)
                                                return current.inEdges();
                                        else
                                                return current.outEdges();
                                }

                        VirtualCFG::FilteredCFGNode < CFGFilterFunction > target(VirtualCFG::FilteredCFGEdge <
                                        CFGFilterFunction > outedge)
                        {
                                if (treeDirection == PRE_DOMINATOR)
                                        return outedge.target();
                                else
                                        return outedge.source();
                        }
                        
                        VirtualCFG::FilteredCFGNode < CFGFilterFunction > source(VirtualCFG::FilteredCFGEdge <
                                        CFGFilterFunction > outedge)
                        {
                                if (treeDirection == PRE_DOMINATOR)
                                        return outedge.source();
                                else
                                        return outedge.target();
                        }
                        
                        // ! treeDirection stores the traversal direction and indicates construction of a dominator or post-dominator tree
                        Direction treeDirection;
        };

        // CI (01/23/2007): Implemented the DT for the VirtualCFG interface with
        // the Lingauer-Tarjan algorithm
        template < typename CFGFilterFunction > class TemplatedDominatorTree:public DominatorForwardBackwardWrapperClass <CFGFilterFunction >
        {
                public:
                        void writeDot(char *filename);

                        //Direction determines Pre/Post-Dominator construction
#ifdef _MSC_VER
                        TemplatedDominatorTree( SgNode * head, Direction d =    PRE_DOMINATOR );
#else
                        TemplatedDominatorTree(SgNode * head, Direction d =     DominatorForwardBackwardWrapperClass <CFGFilterFunction>::PRE_DOMINATOR);
#endif
                        // TemplatedDominatorTree(VirtualCFG::FilteredCFGNode<CFGFilterFunction> 
                        // cfg , Direction d = PRE);

                        // ! get the CFG the dominator tree is built from
                        // ControlFlowGraph * getCFG() {return _cfg;}
                        // ! returns the corresponding direction for the numbering of the CFG.
                        // ControlFlowGraph::ID_dir getCFGDirection() {return _iddir;}
                        
                        // ! returns the number of nodes in the tree
                        int getSize()
                        {
                                return idom.size();
                        }

                        std::set<int> getDirectDominatedSet(int nodeID)
                        {
                                std::set<int> dds;
                                for (unsigned int i=0;i<idom.size();i++)
                                {
                                        if (idom[i]==nodeID)    dds.insert(i);
                                }
                                return dds;
                        }
/*
                        int isDomintated(int a, int b)
                        {
                                // a node dominates itself
                                if (a == b)
                                        return true;
                                int tmp = b;

                                while (tmp > 0 && tmp < a)
                                {
                                        tmp = getImDomID(tmp);
                                        if (tmp == a)
                                                return true;
                                }
                                return false;
                        }
*/
                        // ! for a given nodeID, return the id of its immediate dominator
                        int getImDomID(int i)
                        {
                                return idom[i];
                        }

                        int getImDomID(VirtualCFG::FilteredCFGNode < CFGFilterFunction > node)
                        {
                                int id = getID(node);

                                if (id < 0)
                                        return -1;
                                else
                                        return getImDomID(id);
                        }

                        bool dominates(int a,int b)
                        {
                                if (a==0) return true;
                                int i=b;
                                while(i>0)
                                {
                                        i=getImDomID(i);
                                        if (i==a) return true;                                  
                                }
                                return false;
                        }
                        
                        bool dominates(VirtualCFG::FilteredCFGNode < CFGFilterFunction > a,VirtualCFG::FilteredCFGNode < CFGFilterFunction > b)
                        {
                                return dominates(getID(a),getID(b));
                        }

                        // !for an ID return the corresponing CFGNode
                        VirtualCFG::FilteredCFGNode < CFGFilterFunction > getCFGNodeFromID(unsigned int id)
                        {
                                if ( /* id >= 0 && */ id < idToNode.size())
                                        return idToNode[id];
                                ROSE_ASSERT(false);
                                return cfgRoot;
                        }
                        // ! for an CFG Node, return the corresponding id
                        int getID(VirtualCFG::FilteredCFGNode < CFGFilterFunction > node)
                        {
                                if (nodeToIdMap.count(node) == 0)
                                {
                                        return -1;
                                }
                                else
                                {
                                        return nodeToIdMap[node];
                                }
                        }
                private:
                        // ! this is the cfg-root for dominator construction, for pre this is
                        // the source, for post this is the sink of the cfg
                        VirtualCFG::FilteredCFGNode < CFGFilterFunction > cfgRoot;

                        // use a vector for mapping id's to nodes, since all ids are consecutive
                        std::vector < VirtualCFG::FilteredCFGNode < CFGFilterFunction > >idToNode;
                        // a map for mapping nodes to id's,since this might be a sparse set
                        std::map < VirtualCFG::FilteredCFGNode < CFGFilterFunction >, int >nodeToIdMap;

                        void init();
                        void depthFirstSearch();
                        void calculateImmediateDominators();
                        int eval(int);
                        void link(int source, int target);
                        std::vector < int >semi, idom, ancestor, dfsParent;
                        std::vector < std::set < int > > buckets;

                        void printInfo()
                        {
                                std::cout <<"dfs#\tanc \tsemi\tidom\tbucket"<<std::endl;
                                for(unsigned int i=0;i<idToNode.size();i++)
                                {       
                                        std::cout <<i<<"\t"<<ancestor[i]<<"\t"<<semi[i]<<"\t"<<idom[i]<<"\t"<<buckets[i]<<std::endl;
                                }
                        }
        };

        struct DefaultBasicDominatorTreeIsStatementFilter
        {
                bool operator() (VirtualCFG::CFGNode cfgn) const
                {
                        // get rid of all beginning nodes
                        if (!cfgn.isInteresting())
                                return false;
                        SgNode *n = cfgn.getNode();
                        if (isSgStatement(n))
                                return true;
                        return false;
                }
        };

        typedef TemplatedDominatorTree < DefaultBasicDominatorTreeIsStatementFilter > DominatorTree;

        // end of namespace: DominatorTreesAndDominanceFrontiers
};

#include "DominatorTreeImpl.h"
#endif