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