controlDependence.h

#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 <map>
#include <utility>
#include "staticSingleAssignment.h"
#include <boost/foreach.hpp>
 
namespace ssa_private
{
#if 1
  // using namespace boost;
  // using namespace std;
 
    template<class CfgNodeT, class CfgEdgeT>
    std::multimap< CfgNodeT, std::pair<CfgNodeT, CfgEdgeT> > calculateControlDependence(SgFunctionDefinition* function, const std::map<CfgNodeT, CfgNodeT>& iPostDominatorMap);
#else
    using namespace boost;
    using namespace std;
 
  // DQ (1/7/2018): Move this from the header file to the source code file (staticSingleAssignmentCalculation.C).
    template<class CfgNodeT, class CfgEdgeT>
    multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> >
    calculateControlDependence(SgFunctionDefinition* function, const map<CfgNodeT, CfgNodeT>& iPostDominatorMap)
    {
        //Map from each node to the nodes it's control dependent on (and corresponding edges)
        multimap< CfgNodeT, pair<CfgNodeT, CfgEdgeT> > controlDepdendences;
 
        //Let's iterate the control flow graph and stop every time we hit an edge with a condition
        set<CfgNodeT> visited;
        set<CfgNodeT> worklist;
 
        CfgNodeT sourceNode = function->cfgForBeginning();
        worklist.insert(sourceNode);
 
        while (!worklist.empty())
        {
            //Get the node to work on
            sourceNode = *worklist.begin();
            worklist.erase(worklist.begin());
            visited.insert(sourceNode);
 
            //For every edge, add it to the worklist 
 
            BOOST_FOREACH(const CfgEdgeT& edge, sourceNode.outEdges())
            {
                CfgNodeT targetNode = edge.target();
 
                //Insert the child in the worklist if the it hasn't been visited yet
                if (visited.count(targetNode) == 0)
                {
                    worklist.insert(targetNode);
                }
 
                //Check if we need to process this edge in control dependence calculation
                if (edge.condition() == VirtualCFG::eckUnconditional)
                    continue;
 
                //We traverse from nextNode up in the postdominator tree until we reach the parent of currNode.
                CfgNodeT parent;
                typename map<CfgNodeT, CfgNodeT>::const_iterator parentIter = iPostDominatorMap.find(sourceNode);
 
                ROSE_ASSERT(parentIter != iPostDominatorMap.end());
 
                parent = parentIter->second;
 
                //This is the node that we'll be marking as control dependent
                CfgNodeT currNode = targetNode;
 
                while (true)
                {
                    //If we reach the parent of the source, stop
                    if (currNode == parent)
                    {
                        break;
                    }
 
                    //Add a control dependence from the source to the new node
                    controlDepdendences.insert(make_pair(currNode, make_pair(sourceNode, edge)));
 
                    if (StaticSingleAssignment::getDebugExtra())
                    {
                        printf("%s is control-dependent on %s - %s \n", currNode.toStringForDebugging().c_str(),
                                sourceNode.toStringForDebugging().c_str(), edge.condition() == VirtualCFG::eckTrue ? "true" : "false");
                    }
 
                    //Move to the parent of the current node
                    parentIter = iPostDominatorMap.find(currNode);
                    ROSE_ASSERT(parentIter != iPostDominatorMap.end());
                    currNode = parentIter->second;
                }
            }
        }
 
        return controlDepdendences;
    }
#endif
 
}