NestedSCR.cpp

Go to the documentation of this file.

//************************** System Include Files ***************************

#include <iostream>
using std::cout;
#include <algorithm> // for max
#include <map>
#include <list>

#ifdef NO_STD_CHEADERS
# include <string.h>
# include <stdio.h>
# include <limits.h>
#else
# include <cstring>
# include <cstdio>
# include <climits>
using namespace std; // For compatibility with non-std C headers
#endif

#include <unistd.h>

//*************************** User Include Files ****************************

#include <OpenAnalysis/Utils/NestedSCR.hpp>

//*************************** Forward Declarations **************************

const OA::NestedSCR::DFNUM_t DFNUM_ROOT = 0;
const OA::NestedSCR::DFNUM_t DFNUM_NIL = UINT_MAX;

//*************************** Forward Declarations **************************

namespace OA {

//------------------------------------------------------------------------
// TarjWork: There will be an array of TarjWorks, one for each node.
// These are indexed by the DFS number of the node. This way, there
// is no dependence on the node numbering of the underlying graph.
//------------------------------------------------------------------------

class TarjWork {
public:
 TarjWork();
 ~TarjWork();

 RIFG::NodeId wk_vertex; // map from DFS# of vertex to RIFGNodeId
 OA::NestedSCR::DFNUM_t wk_last; // DFS # of vertex's last descendant
 OA::NestedSCR::DFNUM_t wk_header; // header of the vertex's interval - HIGHPT
 OA::NestedSCR::DFNUM_t wk_nextP; // next member of P set == reachunder
 OA::NestedSCR::DFNUM_t wk_nextQ; // next member of Q set == worklist
 bool wk_inP; // test for membership in P == reachunder
 bool wk_isCyclic; // has backedges -- to id singles
 bool wk_reducible; // true if cyclic scr is reducible
 std::list<int> backPreds; // List of preds that are backedges.
 std::list<int> nonBackPreds; // List of preds that are non-backedges.
};


TarjWork::TarjWork() 
{
 wk_vertex = RIFG::NIL;
 wk_last = DFNUM_NIL;
 wk_header = DFNUM_ROOT;
 wk_nextP = DFNUM_NIL;
 wk_nextQ = DFNUM_NIL;
 wk_inP = false;
 wk_isCyclic = false;
 wk_reducible = true;
}


TarjWork::~TarjWork() 
{
 backPreds.clear();
 nonBackPreds.clear();
}


//------------------------------------------------------------------------
// Interval tree will consist of an array of TarjTreeNodes. These
// are indexed (internally) by the DFS number of the node. This way,
// there is no dependence on the node numbering of the underlying graph. 
//
// There is also a map from RIFGNodeIds to DFS numbers, so
// that tree nodes can be accessed (by the client) through their
// node ids. 
//------------------------------------------------------------------------

class TarjTreeNode {
public:
 TarjTreeNode();
 RIFG::NodeId nodeid; // Associated RIFG::NodeId.
 short level; // nesting depth -- outermost loop is 1 
 NestedSCR::Node_t type; // acyclic, interval or irreducible 
 OA::NestedSCR::DFNUM_t outer; // DFS number of header of containing interval
 OA::NestedSCR::DFNUM_t inners; // DFS number of header of first nested interval
 OA::NestedSCR::DFNUM_t next; // DFS number of next nested header
 int prenum; // preorder number
 OA::NestedSCR::DFNUM_t last; // number of last descendent
 RIFG::NodeId last_id; // id of last descendent
 short loopIndex; // unique id for intervals
};


TarjTreeNode::TarjTreeNode()
{
 nodeid = RIFG::NIL;
 level = 0;
 type = NestedSCR::NODE_ACYCLIC;
 outer = DFNUM_NIL;
 inners = DFNUM_NIL;
 next = DFNUM_NIL;
 prenum = -1;
 last = DFNUM_NIL; 
 last_id = RIFG::NIL;
 loopIndex = -1;
}

} // end of namespace OA



//***************************************************************************
// NestedSCR
//***************************************************************************

namespace OA {
 
 // Refers to members in TarjTreeNode
#define TARJ_nodeid(name) (tarj[name].nodeid)
#define TARJ_outer(name) (tarj[name].outer)
#define TARJ_inners(name) (tarj[name].inners)
#define TARJ_next(name) (tarj[name].next)
#define TARJ_level(name) (tarj[name].level)
#define TARJ_type(name) (tarj[name].type)
#define TARJ_last(name) (tarj[name].last)
#define TARJ_last_id(name) (tarj[name].last_id)
#define TARJ_loopIndex(name) (tarj[name].loopIndex)
#define TARJ_contains(a,b) \
 ( ( tarj[a].prenum <= tarj[b].prenum ) && \
 ( tarj[b].prenum <= tarj[tarj[a].last].prenum ) \
 )

 // Refers to members in TarjWork
#define vertex(x) (wk[x].wk_vertex)
#define TLast(x) (wk[x].wk_last)
#define header(x) (wk[x].wk_header)
#define nextP(x) (wk[x].wk_nextP)
#define nextQ(x) (wk[x].wk_nextQ)
#define inP(x) (wk[x].wk_inP)
#define isCyclic(x) (wk[x].wk_isCyclic)
#define reducible(x) (wk[x].wk_reducible)
#define backPreds(x) (wk[x].backPreds)
#define nonBackPreds(x) (wk[x].nonBackPreds)

static int n; // next DFS preorder number
static int last_id; // RIFG::NodeId whose DFS preorder number is n

//
// is_backedge(a,b) returns true if a is a descendant of b in DFST
// (a and b are the DFS numbers of the corresponding vertices). 
//
// Note that this is in the local structures; corresponds somewhat
// to Contains(tarj,b,a) for the public structures.
//
//
#define is_backedge(a,b) ((b <= a) & (a <= TLast(b)))

#define dfnum(v) (nodeid_to_dfnum_map[v])


NestedSCR::NestedSCR(OA::OA_ptr<OA::RIFG> rifg_)
 : rifg(rifg_)
{
 Create();
}


NestedSCR::~NestedSCR()
{
 if (tarj)
 delete[] tarj;
 if (uf)
 delete uf;
 if (wk)
 delete[] wk;
 rev_top_list.clear();
 nodeid_to_dfnum_map.clear();
}


// Construct tree of Tarjan intervals for the graph
void 
NestedSCR::Create()
{
 RIFG::NodeId root = rifg->getSource();
 
 Init();
 DFS(root);
 FillPredLists();
 GetTarjans();
 Build();
 Sort();
 ComputeIntervalIndex();
 FreeWork();
}


//
// Sort the Tarjan Tree in topological ordering
//
// Feb. 2002 (jle) - Removed the call to GetTopologicalMap which computes
// a (breadth-first) topological ordering of the CFG. This is completely
// unnecessary (and wasteful) since by virtue of performing a DFS as part of
// interval building, we have a topological ordering available as a by-product.
// Further, the breadth-first version in GetTopologicalMap is clumsy (in this
// context) since it has to make call-backs to the tarjan code to determine
// if the current edge being examined is a back-edge (to avoid cycling).
//
void 
NestedSCR::Sort()
{
 RIFG::NodeId gId;
 int parent; // Tarj parent (loop header)

 // Now disconnect all "next" fields for all tarj nodes

 OA_ptr<RIFG::NodesIterator> ni = rifg->getNodesIterator();
 for ( ; (ni->isValid()); ++(*ni)) {
 gId = ni->current();
 int gdfn = dfnum(gId);
 // gdfn will be invalid if the node gId was unreachable.
 if (gdfn != DFNUM_NIL) {
 TARJ_inners(gdfn) = DFNUM_NIL;
 TARJ_next(gdfn) = DFNUM_NIL;
 }
 }

 // The list is sorted in reverse topological order since each child
 // in the loop below is prepended to the list of children.
 std::list<RIFG::NodeId>::iterator i;
 for (i = rev_top_list.begin(); i != rev_top_list.end(); i++) {
 gId = *i;
 if (gId != RIFG::NIL) {
 // Add new kid
 int gdfn = dfnum(gId);
 parent = TARJ_outer(gdfn);
 if (parent != DFNUM_NIL) {
 TARJ_next(gdfn) = TARJ_inners(parent);
 TARJ_inners(parent) = gdfn;
 }
 }
 }

 Renumber();
} // end of tarj_sort()


TarjTreeNode* 
NestedSCR::getTree()
{
 return tarj;
}



//
// Allocate and initialize structures for algorithm, and UNION-FIND
//
void 
NestedSCR::Init()
{
 unsigned int g_size = rifg->getHighWaterMarkNodeId() + 1;

 n = DFNUM_ROOT;

 //
 // Local work space
 //
 wk = new TarjWork[g_size];
 uf = new UnionFindUniverse(g_size);
 tarj = new TarjTreeNode[g_size];
 InitArrays();
}


//
// Initialize only nodes in current instance g
//
void 
NestedSCR::InitArrays()
{
 OA_ptr<RIFG::NodesIterator> ni = rifg->getNodesIterator();
 for ( ; ni->isValid(); ++(*ni)) {
 int nid = ni->current();
 dfnum(nid) = DFNUM_NIL;
 }
}


//
// Do depth first search on control flow graph to 
// initialize vertex[], dfnum[], last[]
//
void 
NestedSCR::DFS(RIFG::NodeId v)
{
 vertex(n) = v;
 dfnum(v) = n++;
 
 RIFG::EdgeId succ;
 OA_ptr<RIFG::OutgoingEdgesIterator> ei = rifg->getOutgoingEdgesIterator(v);
 for (; (ei->isValid()); ++(*ei)) {
 succ = ei->current();
 int son = rifg->getEdgeSink(succ);
 if (dfnum(son) == DFNUM_NIL)
 DFS(son);
 }

 //
 // Equivalent to # of descendants -- number of last descendant
 //
 TLast(dfnum(v)) = n-1;
 rev_top_list.push_back(v);
}


// Fill in the backPreds and nonBackPreds lists for each node.
void 
NestedSCR::FillPredLists()
{
 for (int i = DFNUM_ROOT; i < n; i++) {
 OA_ptr<RIFG::IncomingEdgesIterator> ei = 
 rifg->getIncomingEdgesIterator(vertex(i) );
 for ( ; (ei->isValid()); ++(*ei)) {
 int prednum = dfnum(rifg->getEdgeSrc(ei->current()));
 if (is_backedge(prednum, i)) {
 backPreds(i).push_back(prednum); 
 } else {
 nonBackPreds(i).push_back(prednum); 
 }
 } // for preds
 } // for nodes
}


//
// In bottom-up traversal of depth-first spanning tree, 
// determine nested strongly connected regions and flag irreducible regions.
// phh, 4 Mar 91
//
void 
NestedSCR::GetTarjans()
{
 int w; // DFS number of current vertex
 DFNUM_t firstP, firstQ; // set and worklist

 //
 // Following loop should skip root (prenumbered as 0)
 //
 for (w = n - 1; w != DFNUM_ROOT; w--) // loop c
 //
 // skip any nodes freed or not reachable
 //
 if (w != DFNUM_NIL && rifg->isValid(vertex(w))) {
 firstP = firstQ = DFNUM_NIL;
 //
 // Add sources of cycle arcs to P -- and to worklist Q
 //
 std::list<int>::iterator prednum; 
 for (prednum = backPreds(w).begin(); prednum != backPreds(w).end();
 prednum++) { // loop d
 int u,v; // vertex names
 v = *prednum;
 // ignore predecessors not reachable
 if (v != DFNUM_NIL)
 {
 if (v == w) {
 //
 // Don't add w to its own P and Q sets
 //
 isCyclic(w) = true;
 } else {
 //
 // Add FIND(v) to P and Q
 //
 u = FIND(v);
 if (!inP(u)) {
 nextP(u) = nextQ(u) = firstP;
 firstP = firstQ = u;
 inP(u) = true;
 } // if (!inP(u))
 } // if (v == w)
 } // if 
 } // for preds

 //
 // P nonempty -> w is header of a loop
 //
 if (firstP != DFNUM_NIL)
 isCyclic(w) = true;

 while (firstQ != DFNUM_NIL) {
 int x, y, yy; // DFS nums of vertices

 x = firstQ;
 firstQ = nextQ(x); // remove x from worklist

 //
 // Now look at non-cycle arcs
 //
 std::list<int>::iterator prednum;
 for (prednum = nonBackPreds(x).begin();
 prednum != nonBackPreds(x).end();
 prednum++) { // loop d
 y = *prednum;

 //
 // ignore predecessors not reachable
 //
 if (y != DFNUM_NIL)
 {
 //
 // Add FIND(y) to P and Q
 //
 yy = FIND(y);

 if (is_backedge(yy, w)) {
 if ((!inP(yy)) & (yy != w)) {
 nextP(yy) = firstP;
 nextQ(yy) = firstQ;
 firstP = firstQ = yy;
 inP(yy) = true;
 }
 //
 // Slight change to published alg'm...
 // moved setting of header (HIGHPT)
 // from here to after the union.
 //
 } else {
 //
 // Irreducible region!
 //
 reducible(w) = false;
#if 1
 // FIXME: The DSystem version of the code did not have the
 // following line. However, this line IS in the 1997 article,
 // and I believe it is necessary (jle, 03-02-2002).
 nonBackPreds(w).push_back(yy);
#endif
 }
 }
 }
 }
 //
 // now P = P(w) as in Tarjan's paper
 //
 while (firstP != DFNUM_NIL) {
 //
 // First line is a change to published algorithm;
 // Want sources of cycle edges to have header w
 // and w itself not to have header w.
 //
 if ((header(firstP) == DFNUM_ROOT) & (firstP != w))
 header(firstP) = w;
 UNION(firstP, w, w);
 inP(firstP) = false;
 firstP = nextP(firstP);
 } // while
 } // if
}


//
// Traverse df spanning tree, building tree of Tarjan intervals
//
void 
NestedSCR::Build()
{
 int w; // DFS number of current vertex
 int outer; // DFS number header of surrounding loop

 TARJ_nodeid(DFNUM_ROOT) = rifg->getSource();
 //
 // Let the root of the tree be the root of the instance...
 // Following loop can skip the root (prenumbered 0)
 //
 for (w = DFNUM_ROOT + 1; w < n; w++) {
 RIFG::NodeId wnode = vertex(w);
 //
 // skip any nodes not in current instance g
 //
 if (wnode != RIFG::NIL) {
 outer = header(w);
 TARJ_outer(w) = outer;
 TARJ_nodeid(w) = wnode;
 //
 // tarj[w].inners = DFNUM_NIL; % done in InitArrays
 //
 if (isCyclic(w)) {
 //
 // Level is deeper than outer if this is a loop
 //
 if (reducible(w)) {
 TARJ_type(w) = NODE_INTERVAL;
 TARJ_level(w) = TARJ_level(outer) + 1;
 } else {
 TARJ_type(w) = NODE_IRREDUCIBLE;
 TARJ_level(w) = TARJ_level(outer);
 }
 } else {
 //
 // tarj[w].type = RI_TARJ_ACYCLIC; % done in InitArrays
 //
 TARJ_level(w) = TARJ_level(outer);
 }
 TARJ_next(w) = TARJ_inners(outer);
 TARJ_inners(outer) = w;
 }
 }
 n = 0;
 Prenumber(DFNUM_ROOT);
}


void 
NestedSCR::Prenumber(int v)
{
 int inner;

 tarj[v].prenum = ++n;
 last_id = TARJ_nodeid(v);
 
 for (inner = TARJ_inners(v); inner != DFNUM_NIL; 
 inner = TARJ_next(inner)) {
 Prenumber(inner);
 }

 /* tarj[v].last = n; // 3/18/93 RvH: switch to RIFG::NodeId last_id */
 tarj[v].last_id = last_id;
 tarj[v].last = dfnum(last_id);
}


void 
NestedSCR::Renumber()
{
 tarj = tarj;
 n = 0;
 Prenumber(DFNUM_ROOT);
}


// Free all space used in computation of 
// Tarjan interval tree (but not tree itself)
void 
NestedSCR::FreeWork()
{
 delete[] wk;
 wk = 0;

 delete uf;
 uf = 0;
}


static int loopIndex;
void 
NestedSCR::ComputeIntervalIndexSubTree(int node, int value)
{
 int kid, valKid;
 
 TARJ_loopIndex(node) = value;
 if (TARJ_inners(node) != DFNUM_NIL)
 valKid = ++loopIndex;

 for (kid = TARJ_inners(node); kid != DFNUM_NIL; kid = TARJ_next(kid))
 ComputeIntervalIndexSubTree(kid, valKid);
}


void 
NestedSCR::ComputeIntervalIndex()
{
 loopIndex = 0;
 ComputeIntervalIndexSubTree(DFNUM_ROOT, loopIndex);
}


void 
NestedSCR::dump(std::ostream& os)
{
 printf("Tarjan interval tree: <node id>(level,type)::IntervalIndex\n");
 DumpSubTree(os, DFNUM_ROOT, 0 /* Indent */);
}


//
// Feb. 2002 (jle): Got rid of all the silly concatenating of blank
// strings. The %*s format specifier is far simpler for creating indentations.
//
void 
NestedSCR::DumpSubTree(std::ostream& os, int node, int indent)
{
 static const char *NodeType[] = {"NOTHING", "Acyclic",
 "Interval", "Irreducible"};
 //
 // Indent by three
 //
 if (indent < 72)
 indent += 3;
 
 printf("%*s%d(%d,%s)::%d\n", indent, " ",
 TARJ_nodeid(node), TARJ_level(node),
 NodeType[(int) (TARJ_type(node))], TARJ_loopIndex(node));
 
 for (int kid = TARJ_inners(node); kid != DFNUM_NIL; 
 kid = TARJ_next(kid)) {
 DumpSubTree(os, kid, indent);
 }
 
 //
 // Unindent
 //
 if (indent >= 3)
 indent -= 3;
}


int 
NestedSCR::FIND(int v)
{
 return uf->Find(v);
}


void 
NestedSCR::UNION(int i, int j, int k)
{
 uf->Union(i,j,k);
}


//
// Return number of loops exited in traversing g edge from src to sink
// (0 is normal).
//
int 
NestedSCR::getExits(RIFG::NodeId src, RIFG::NodeId sink)
{
 RIFG::NodeId lca = LCA(src, sink);
 if (lca == RIFG::NIL)
 return 0;

 int dfn_src = dfnum(src);
 int dfn_lca = dfnum(lca);
 return std::max(0, TARJ_level(dfn_src) - TARJ_level(dfn_lca));
}


//
// Return outermost loop exited in traversing g edge from src to sink
// (RIFG::NIL if no loops exited).
//
RIFG::NodeId 
NestedSCR::getLoopExited(RIFG::NodeId src, RIFG::NodeId sink)
{
 RIFG::NodeId lca = LCA(src, sink);
 if (lca == RIFG::NIL)
 return RIFG::NIL;

 if (lca == src)
 return RIFG::NIL;

 int dfn_src = dfnum(src);
 while (!Contains(TARJ_nodeid(TARJ_outer(dfn_src)), sink))
 dfn_src = TARJ_outer(dfn_src);
 
 if (TARJ_type(dfn_src) == NODE_INTERVAL
 || TARJ_type(dfn_src) == NODE_IRREDUCIBLE)
 return TARJ_nodeid(dfn_src);

 return RIFG::NIL;
}


//
// Return type of g edge from src to sink, one of
// RI_TARJ_NORMAL
// RI_TARJ_LOOP_ENTRY
// RI_TARJ_IRRED_ENTRY
// RI_TARJ_ITERATE (back edge)
//
NestedSCR::Edge_t 
NestedSCR::getEdgeType(RIFG::NodeId src, RIFG::NodeId sink)
{
 RIFG::NodeId anc = LCA(src, sink);
 int dfn_sink = dfnum(sink);
 int dfn_anc = dfnum(anc);

 if (dfn_anc == dfn_sink) {
 return EDGE_ITERATE;
 } 
 else if (TARJ_outer(dfn_sink) != DFNUM_NIL
 && (TARJ_type(TARJ_outer(dfn_sink)) == NODE_IRREDUCIBLE)
 && (dfn_anc != TARJ_outer(dfn_sink))) {
 //
 // Entering irreducible region not through the "header"
 //
 return EDGE_IRRED_ENTRY;
 } 
 else {
 switch (TARJ_type(dfn_sink)) {
 case NODE_INTERVAL:
 return EDGE_LOOP_ENTRY;
 case NODE_IRREDUCIBLE:
 //
 // Entering irreducible region through the "header"
 //
 return EDGE_IRRED_ENTRY;
 case NODE_ACYCLIC:
 case NODE_NOTHING:
 default:
 return EDGE_NORMAL;
 }
 }
}


//
// LCA = least common ancestor
//
RIFG::NodeId 
NestedSCR::LCA(RIFG::NodeId a, RIFG::NodeId b)
{
 if ((a == RIFG::NIL) || (b == RIFG::NIL))
 return RIFG::NIL;

 if (Contains(a,b))
 return a;

 int dfn_b = dfnum(b);
 while ((dfn_b != DFNUM_NIL) && !Contains(b,a)) {
 dfn_b = TARJ_outer(dfn_b);
 b = TARJ_nodeid(dfn_b);
 }

 return b;
}


//
// Return true if the CFG edge passed in is an backedge.
//
// Precondition: Tarjan tree must be built already.
//
bool 
NestedSCR::isBackEdge(RIFG::EdgeId edgeId)
{
 RIFG::NodeId src, dest;
 src = rifg->getEdgeSrc(edgeId);
 dest = rifg->getEdgeSink(edgeId);
 return is_backedge(dfnum(src), dfnum(dest));
} 


RIFG::NodeId 
NestedSCR::getInners(RIFG::NodeId id)
{
 int dfn_inners = TARJ_inners(dfnum(id));
 return dfn_inners == DFNUM_NIL ? RIFG::NIL : TARJ_nodeid(dfn_inners);
}


RIFG::NodeId 
NestedSCR::getInnersLast(RIFG::NodeId id)
{
 int dfn_last_id = TARJ_last_id(dfnum(id));
 return TARJ_nodeid(dfn_last_id);
}


RIFG::NodeId
NestedSCR::getOuter(RIFG::NodeId id)
{
 int dfn_outer = TARJ_outer(dfnum(id));
 return dfn_outer == DFNUM_NIL ? RIFG::NIL : TARJ_nodeid(dfn_outer);
}


RIFG::NodeId 
NestedSCR::getNext(RIFG::NodeId id)
{
 int dfn_next = TARJ_next(dfnum(id));
 return dfn_next == DFNUM_NIL ? RIFG::NIL : TARJ_nodeid(dfn_next);
}



bool 
NestedSCR::isHeader(RIFG::NodeId id)
{
 return (getInners(dfnum(id)) != DFNUM_NIL);
}


bool 
NestedSCR::isFirst(RIFG::NodeId id)
{
 int dfn_id = dfnum(id);

 if (getOuter(dfn_id) == DFNUM_NIL)
 return true;

 return (getInners(getOuter(dfn_id)) == dfn_id);
}


bool 
NestedSCR::isLast(RIFG::NodeId id)
{
 return (getNext(dfnum(id)) == DFNUM_NIL);
}


int 
NestedSCR::getLevel(RIFG::NodeId id)
{
 return TARJ_level(dfnum(id));
}


NestedSCR::Node_t 
NestedSCR::getNodeType(RIFG::NodeId id)
{
 return TARJ_type(dfnum(id));
}


bool 
NestedSCR::Contains(RIFG::NodeId a, RIFG::NodeId b)
{
 return (TARJ_contains(dfnum(a), dfnum(b)));
}


int 
NestedSCR::getLoopIndex(RIFG::NodeId id)
{
 return TARJ_loopIndex(dfnum(id));
}


} // end of namespace OA