#include <iomanip>
#include "AST.h"
#include "MethodDecl.h"
#include "UniqueId.h"
#include "compiler.h"
#include "decls.h"
#include "delimit.h"
#include "st-field.h"
#include "optimize.h"
#include "code-util.h"
#include "cfg.h"

extern bool test_sr;
extern bool bounds_checking;

////////////////////////////////////
// Various and sundry utilities.  //
////////////////////////////////////

NodeStorage *NodeStorage::current = NULL;

vector<CfgNode*> CfgNode::validNodes (1);

CfgNode* CfgNode::node (int id) 
{
  assert ((unsigned int) id < validNodes.size ());
  return validNodes[id];
}

CfgNode::CfgNode (TreeNode *node)
  : ast_node(node),
    _succ(0),
    _pred(0),
    visited(0),
    NSE(new CFGset),
    numPred(0),
    numSucc(0),
    bblock(0)
{
  assert(!node->isTypeNode()); // DOB: never allow TypeNodes to appear in 
  // CFG, because they may be shared and therefore cause
  // difficulties when determining scope (isNodeInScope()).
  // If you see this assertion fail, makeCfg is probably 
  // broken for a parent node.
  _nodeId = validNodes.size ();
  validNodes.push_back (this);
}

void *CfgNode::operator new(size_t size)
{
    assert(size == sizeof(CfgNode));
      return NodeStorage::current->cfgHeap.alloc();
}

void CfgNode::operator delete(void *buffer, size_t size)
{
    assert(size == sizeof(CfgNode));
      NodeStorage::current->cfgHeap.release(buffer);
}

void *Bblock::operator new(size_t size)
{
    assert(size == sizeof(Bblock));
      return NodeStorage::current->bblockHeap.alloc();
}

void Bblock::operator delete(void *buffer, size_t size)
{
    assert(size == sizeof(Bblock));
      NodeStorage::current->bblockHeap.release(buffer);
}

void shortCFGnode(ostream &os, const CfgNode *n)
{
  os << "<" << n->nodeId () << ">";
}

static void shortCFGPredList(ostream &os, ListIterator<CfgNode *> s,
			     CfgNode* to)
{
  bool first = true;
  for (; !s.isDone(); s.next()) {
    if (first)
      first = false;
    else
      os << ' ';
    shortCFGnode(os, *s);
    if (to != NULL && to->isNSE (*s))
      os << '*';
  }
}

static void shortCFGSuccList(ostream &os, ListIterator<CfgNode *> s,
			     CfgNode* from)
{
  bool first = true;
  for (; !s.isDone(); s.next()) {
    if (first)
      first = false;
    else
      os << ' ';
    shortCFGnode(os, *s);
    if (from != NULL && (*s)->isNSE (from))
      os << '*';
  }
}

void shortCFGlist(ostream &os, ListIterator<CfgNode *> s)
{
  shortCFGSuccList (os, s, NULL);
}

void shortCFGset(CFGset *s, ostream &os)
{
  llist<CfgNode *> *l = NULL;
  for (CFGset::iterator i = s->begin(); i != s->end(); ++i)
    l = cons(*i, l);
  shortCFGlist(os, ListIterator<CfgNode *>(l));
  free_all(l);
}

void shortCFGuset(const CFGuset *s, ostream &os)
{
  os << "[CFGuset]"; // bug
}

static void summarizeCFGnode(CfgNode *n, ostream &os, bool withEdges = true)
{
  shortCFGnode(os, n);
  if (n->astNode()->isExprNode() || isNameNode(n->astNode()))
    PLCODE2(os, n->astNode());
  else
    POPER2(os, n->astNode());
  os << endl;
  os << "preds: ";
  shortCFGPredList(os, n->predIter(), n);
  os << endl;
  os << "succs: ";
  shortCFGSuccList(os, n->succIter(), n);
  os << endl;
}

// Find a statement corresponding to a node in l, if any.
/* unused
static TreeNode *findStmt(llist<CfgNode *> *l)
{
  while (l != NULL)
    if (l->front()->astNode()->isStatementNode())
      return l->front()->astNode();
    else
      l = l->tail();
  return NULL;
}
*/

// Find an expr corresponding to a node in l, if any.
static TreeNode *findExpr(llist<CfgNode *> *l)
{
  while (l != NULL)
    if (l->front()->astNode()->isExprNode())
      return l->front()->astNode();
    else
      l = l->tail();
  return NULL;
}

void summarizeStraightLine(CfgNode *n, ostream &os,
			   set< CfgNode *> &done)
{
  llist<CfgNode *> *line = NULL;
  while (n->hasOneSuccessor()) {
    line = cons(n, line);
    done.insert(n);
    n = *(n->succIter());
  }
  done.insert(n);
  line = cons(n, line);
  int len = line->size();
  if (len > 1) {
    CfgNode *end = line->front();
    TreeNode *endt = findExpr(line);
    line = dreverse(line);
    CfgNode *start = line->front();
    TreeNode *startt = findExpr(line);
    os << "Straight line code of length " << len <<
      " cfg nodes from " << QCFG(start) << " to " << QCFG(end) << endl;
    os << "First expr: "; SAFEPLCODE2(os, startt); os << endl;
    if (startt != endt) {
      os << "Last expr: "; SAFEPLCODE2(os, endt); os << endl;
    }
    os << endl;
  }
  summarizeCFGnode(n, os);
  os << endl;
}

void summarizeStraightLines(llist<CfgNode *> * l, ostream &os)
{
  llist<CfgNode *> *todo = copylist(l);
  set< CfgNode * > done;
  while (todo != NULL) {
    CfgNode *n = todo->front();
    todo = todo->free();
    if (done.count(n) == 0) {
      summarizeStraightLine(n, os, done);
      done.insert(n);
    }
  }
}

void summarizeCFG(llist<CfgNode *> * l, ostream &os)
{
  llist<CfgNode *> *todo = copylist(l);
  set< CfgNode * > done;
  while (todo != NULL) {
    CfgNode *n = todo->front();
    todo = todo->free();
    if (done.count(n) == 0) {
      summarizeCFGnode(n, os);
      done.insert(n);
      ListIterator<CfgNode *> preds = n->predIter();
      for (; !preds.isDone(); preds.next()) {
	CfgNode *z = *preds;
	if (done.count(z) == 0)
	  todo = cons(z, todo);
      }    
      ListIterator<CfgNode *> succs = n->succIter();
      for (; !succs.isDone(); succs.next()) {
	CfgNode *z = *succs;
	if (done.count(z) == 0)
	  todo = cons(z, todo);
      }    
    }
  }
  summarizeStraightLines(l, os);
}

llist<CfgNode *> * reachableCFGnodes(CfgNode *n)
{
  llist<CfgNode *> *todo = cons(n);
  set< CfgNode * > done;
  llist<CfgNode *> *reachable = NULL;
  while (todo != NULL) {
    CfgNode *n = todo->front();
    todo = todo->free();
    if (done.count(n) == 0) {
      done.insert(n);
      push(reachable, n);
      ListIterator<CfgNode *> preds = n->predIter();
      for (; !preds.isDone(); preds.next()) {
	CfgNode *z = *preds;
	if (done.count(z) == 0)
	  todo = cons(z, todo);
      }    
      ListIterator<CfgNode *> succs = n->succIter();
      for (; !succs.isDone(); succs.next()) {
	CfgNode *z = *succs;
	if (done.count(z) == 0)
	  todo = cons(z, todo);
      }    
    }
  }
  return dreverse(reachable);
}

/* Display the CFG for an entire method. */
void summarizeCFG(const TreeNode *m, ostream &os)
{
  m = enclosingMethod(m)->body();
  llist<CfgNode *> *r =
    reachableCFGnodes(const_cast<TreeNode *>(m)->getCfgExtent().entry);
  summarizeCFG(r, os);
  free_all(r);
}

static void print_cfglist_asts(llist<CfgNode *> const * l, ostream &os)
{
  bool first = true; 
  foreach_const (p, llist<CfgNode *>, *l) {
    if (first)
      first = false;
    else
      os << " ? ";
    PLCODE2(os, (*p)->astNode());
    shortCFGnode(os, *p);
  }
}

void CfgNode::reset () 
{
  validNodes.resize (1);
}

int CfgNode::maxId ()
{
  return validNodes.size ()-1;
}


void CfgNode::print(ostream &os) const
{
  ((CfgNode *) this)->astNode()->pseudoprint(os, 2);
  shortCFGnode(os, this);
  os << endl << " pred:";
  print_cfglist_asts(_pred, os);
  os << endl << " succ:";
  print_cfglist_asts(_succ, os);
  os << endl;
}

// Returns the statement that should get executed first in the given
// tree.
static StatementNode *findFirstStmt(TreeNode *t) {
  const int childCount = t->arity();
  TreeNode *first;

  if (t->isStatementNode() && !isBlockNode(t)) {
    return (StatementNode *)t;
  }

  for (int sweep = 0; sweep < childCount; sweep++) {
    first = findFirstStmt(t->child(sweep));
    if (first) {
      return (StatementNode *)first;
    }
  }
  return NULL;
}

static bool isFunc(TreeNode *t) {
  return (isMethodDeclNode(t) || isConstructorDeclNode(t));
}

/* Returns whether s contains any ast nodes corresponding to the
   given cfgnodes. */
static bool containsAnyOf(treeSet *s, ListIterator<CfgNode *> i)
{
  while (!i.isDone())
    if (contains(s, (*i)->astNode()))
      return true;
    else
      i.next();

  return false;
}

llist<CfgNode *> *CfgNodesWithinSubtree(const llist<CfgNode *> *l, TreeNode *t)
{
  Worklist W(t);
  treeSet *s = list_to_set(W.asList());
  llist<CfgNode *> *result = NULL;
  foreach_const (p, llist<CfgNode *>, *l) {
    CfgNode *n = *p;
    if (contains(s, n->astNode()) ||
	containsAnyOf(s, n->predIter()) ||
	containsAnyOf(s, n->succIter()))
      result = cons(n, result);
    if (DEBUG_DOM) {
      const char *j = NULL; 
      if (contains(s, n->astNode()))
	j = "in";
      else if (containsAnyOf(s, n->predIter()))
	j = "has pred in";
      else if (containsAnyOf(s, n->succIter()))
	j = "has succ in";
      cout << ((j == NULL) ?
	       "Discarding: " :
	       (string("Keeping because ") + j + " loop: "));
      summarizeCFGnode(n, cout, false);
      cout << endl;
    }
  }
  if (DEBUG_DOM)
    cout << "Trimming cfg from " << l->size() << " nodes to " <<
      result->size() << " nodes (AST: " << s->size() << " nodes)." << endl;
  return dreverse(result);
}

/* Print the statements in path, in reverse order. */
static void dumppath(ostream &os, llist<CfgNode *> *path)
{
  path = dreverse(path);
  TreeNode *last = NULL;
  int i = 0;
  foreach_const (p, llist<CfgNode *>, *path) {
    TreeNode *t = (*p)->astNode();
    if (t != NULL && t->isStatementNode())
      os << i++ << pseudocode(last = t) << '\n';
  }
  path = dreverse(path);
}

/* Helper for pathsfrom(). */
static void pathsfrom2(ostream &os, CfgNode *n, const treeSet *s, 
		       llist<CfgNode *> *path)
{
  ListIterator<CfgNode *> succs = n->succIter();
  for (; !succs.isDone(); succs.next()) {
    CfgNode *z = *succs;
    if (contains(path, z)) {
      os << "begin self-intersecting path\n";
      dumppath(os, path);
      os << "end self-intersecting path\n\n";
    } else if (s != NULL && !z->astNode()->absent() &&
	       !contains(s, z->astNode())) {
      os << "begin path\n";
      push(path, z);
      dumppath(os, path);
      path = path->free();
      os << "end path\n\n";
    } else {
      push(path, z);
      pathsfrom2(os, z, s, path);
      path = path->free();
    }
  }
}

/* If s is NULL, print all CFG paths from n. */
/* If s is not NULL, print all CFG paths from n to something outside of s,
   plus all self-intersecting paths from n that don't leave s. */
/* Intended for use in debugging. */
void pathsfrom(ostream &os, CfgNode *n, const treeSet *s)
{
  os << "Showing paths from " << pseudocode(n->astNode()) << "\n\n";
  pathsfrom2(os, n, s, NULL);
  os << "Done showing paths\n";
}

/* Helper for hasSelfPath(). */
static bool hasSelfPath2(CfgNode *n, const treeSet *s, llist<CfgNode *> *path,
			 CfgNode *start)
{
  push(path, n);
  ListIterator<CfgNode *> succs = n->succIter();
  for (; !succs.isDone(); succs.next()) {
    CfgNode *z = *succs;
    if (contains(path, z)) {
      // if (enclosingStmt(z->astNode()) == enclosingStmt(start->astNode()))
      if (z == start) {
#if 0
	cout << "start self path for statement at " <<
	  enclosingStmt(start->astNode())->position().asString() << endl <<
	  pseudocode(enclosingStmt(start->astNode())) << endl;
	dumppath(cout, path);
	cout << "end self path\n\n";
#endif
	goto YES;
      }
    } else if ((s == NULL ||
		z->astNode()->absent() || contains(s, z->astNode())) &&
	       hasSelfPath2(z, s, path, start))
      goto YES;
  }
  /*  NO: */
  path = path->free();
  return false;
 YES:
  path = path->free();
  return true;
}

/* If s is NULL, true iff a CFG path from n leads back to n. */
/* If s is not NULL, true iff a CFG path from n leads back to n
   without leaving s. */
bool hasSelfPath(CfgNode *n, const treeSet *s)
{
  return hasSelfPath2(n, s, NULL, n);
}
////////////////////////////////////////////////////////////
// 
// BASIC BLOCK ABSTRACTION
//
//    This code arranges expression-level CFG nodes into 
//    basic blocks, which speeds up dataflow calculations.
//
////////////////////////////////////////////////////////////

void setupBblocksMethod(TreeNode *t);

static int Bblock_number = 0;

Bblock::Bblock()
  : _preds(NULL),
    _succs(NULL),
    _cfglist(NULL),
    visited(0),
    _defsOut(NULL),
    _defsIn(NULL),
    _defs(NULL),
    _kills(NULL),
    _aliasesIn(NULL),
    _aliasesOut(NULL),
    number(Bblock_number++),
    defsize(0)
{
}

void printSimple(ostream &os, TreeNode *t) {
  if (isNameNode(t)) {
    os << *(((NameNode *)t)->ident());
  }
  else if (isPrimitiveLitNode(t)) {
    os << ((PrimitiveLitNode *)t)->literal().asString();
  }
  else {
    os << "-*-";
  }
}

void Bblock::print(ostream &os) {
  os << endl << "BBLOCK #" << number << ":\n";
  os << "PREDS:";
  ListIterator<Bblock *>bbIt = predIter();
  for (; !bbIt.isDone(); bbIt.next()) {
    Bblock *succ = *bbIt;
    os << " " << succ->number;
  }
  os << "\nSUCCS:";
  bbIt = succIter();
  for (; !bbIt.isDone(); bbIt.next()) {
    Bblock *succ = *bbIt;
    os << " " << succ->number;
  }
  os << endl;
  ListIterator<CfgNode *> cfgIt = cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();

    os << t->oper_name() << " (";
    os << setbase (16) << t << setbase(10) << ")";
    os << "\tvalue: ";
    printSimple(os, t);
    os << "\tposn: <" << t->position().asString() << '>';
    os << endl;
  }
}


Bblock *MethodDeclNode::getBblockRoot() {
  return bblockRoot;
}

Bblock *ConstructorDeclNode::getBblockRoot() {
  return bblockRoot;
}

void MethodDeclNode::setBblockRoot(Bblock *bblock) {
  bblockRoot = bblock;
}

void ConstructorDeclNode::setBblockRoot(Bblock *bblock) {
  bblockRoot = bblock;
}

// Print "action" to fed to TraverseBblocks.
void PrintBblockAction(Bblock *b) {
  b->print(cout);
}

CfgExtent append_cfg(CfgExtent c1, CfgNode *c2);

NodeStorage *node_heap = NULL;

void MethodDeclNode::setNodeStorage(NodeStorage *ns) {
  nodeStorage = ns;
}

NodeStorage *MethodDeclNode::getNodeStorage(void) {
  return nodeStorage;
}

void ConstructorDeclNode::setNodeStorage(NodeStorage *ns) {
  nodeStorage = ns;
}

NodeStorage *ConstructorDeclNode::getNodeStorage(void) {
  return nodeStorage;
}

// See cfg.h for the explanation of this code.
static void initCfgStorage(TreeNode *t) {
  // MethodDeclNode *method = (MethodDeclNode *)t; // DOB: this cast is an error because t may be a ConstructorDeclNode
  if (!t->getNodeStorage()) {
    t->setNodeStorage(new NodeStorage());
  }
  else {
    t->getNodeStorage()->reset();
  }
  // This tells the pseudoconstructors where to get storage from.
  NodeStorage::current = t->getNodeStorage();
}    

static void MakeCfg(TreeNode *t);

// Creates the CFG for a single method, and attaches the first bblock to the
// bblockRoot field in the MethodDeclNode.
void setupBblocksMethod(TreeNode *t) {

  CfgNode *cfg;
  Bblock *firstBblock;
  
  cfg = NULL;
  assert(isFunc(t));

  initCfgStorage(t);

  /*
  cout << "After initialization:\n";
  cout << "CFG uselist: " << NodeStorage::current->cfgHeap->usedSize() << " used, " << NodeStorage::current->cfgHeap->freeSize() << " free.\n";
  cout << "Bblock uselist: " << NodeStorage::current->bblockHeap->usedSize() << " used, " << NodeStorage::current->bblockHeap->freeSize() << " free.\n";
  */

  TreeNode *body = t->body();

  if (isOmittedNode(body)) {
    return;
  } else if (isLazyOptimizeNode(body)) {
    t->body(body->body());
    setupBblocksMethod(t);
    t->body(body);
    return;
  }

  MakeCfg(body);
  if (isBlockNode(body) || isReorderNode(body))
    cfg = body->getCfgExtent().entry;
  else
    fatal_error("");

  assert(cfg != NULL);

  cfg = append_cfg(t->params()->makeCfg(), cfg).entry;

  Bblock_number = 0;
  firstBblock = new Bblock;
  t->setBblockRoot(firstBblock);
  traverseCfgBblock(cfg, firstBblock, LastMethodNode(t));
  UnmarkBblocks(firstBblock);

  /*
  cout << "After building CFG:\n";
  cout << "CFG uselist: " << NodeStorage::current->cfgHeap->usedSize() << " used, " << NodeStorage::current->cfgHeap->freeSize() << " free.\n";
  cout << "Bblock uselist: " << NodeStorage::current->bblockHeap->usedSize() << " used, " << NodeStorage::current->bblockHeap->freeSize() << " free.\n";
  */

  string myName = *(t->simpName()->ident());
  if (DEBUG_PHASE_ENABLED("cfg", currentFilename))
    {
      cout << "\nCFG for " << myName << " : " << endl; 
      TraverseBblocks(firstBblock, PrintBblockAction); 
      cout << endl; 
      UnmarkBblocks(firstBblock);
    }

  NodeStorage::current = NULL; // catch attempts to allocate Bblocks and CfgNodes to a random NodeStorage
}

// Does a DFO traversal of the CFG, collecting components with single
// predecessors and successors into single bblocks.
void traverseCfgBblock(CfgNode *c, Bblock *currBblock, CfgNode *lastCfg) {

restart:

  assert(!c->bblock);
  currBblock->addCfg(c);
  if (c == lastCfg) {
    return;
  }
  for (ListIterator<CfgNode *> succs = c->succIter(); !succs.isDone(); succs.next()) {
    CfgNode *child = *succs;
    if (child->bblock) {
      currBblock->addSucc(child->bblock);
      child->bblock->addPred(currBblock);
    }
    else if (c->numSucc > 1 || child->numPred > 1) {
      Bblock *newBblock = new Bblock;
      traverseCfgBblock(child, newBblock, lastCfg);
      currBblock->addSucc(newBblock);
      newBblock->addPred(currBblock);
    }
    else {
      /* DOB: This leads to unacceptably deep recursions with large method bodies */
      /* traverseCfgBblock(child, currBblock, lastCfg); */

      /* instead, simulate the tail-recursive call */
      assert(c->numSucc == 1);
      c = child;
      goto restart;
    }
  }
}

////////////////////////////////////////
//                                    //
//   GRAPH TRAVERSAL UTILITIES        //
//                                    //
////////////////////////////////////////

static int nextCfgColor = 1;
static int nextBblockColor = 1;

static inline bool colored(Bblock *b) {
  return b->nodeStatus() == nextBblockColor;
}

static inline bool colored(CfgNode *cfg) {
  return cfg->nodeStatus() == nextCfgColor;
}

static inline void color(Bblock *b) {
  b->nodeStatus(nextBblockColor);
}

static inline void color(CfgNode *cfg) {
  cfg->nodeStatus(nextCfgColor);
}



static bool isNodeInScope(CfgNode *n, TreeNode *construct);

static void TraverseBblocksExtent(Bblock *from, Bblock *to, TreeNode *scope,
				  void action(Bblock *b)) {
  action(from);
  color(from);
  if (from == to) {
    return;
  }
  ListIterator<Bblock *>succs = from->succIter();
  for (; !succs.isDone(); succs.next()) {
    Bblock *child = *succs;

    // Figure out if the child bblock is in scope by looking at a 
    // representative node. We must skip past any null nodes in the bblock.
    // because they are assumed to be in scope and are not representative.
    ListIterator<CfgNode *> cfgIt = child->cfgIter();
    CfgNode *firstCfg = NULL;
    for (; !cfgIt.isDone(); cfgIt.next()) {
      firstCfg = *cfgIt;
      if (firstCfg->astNode() != TreeNode::omitted) {
	break;
      }
    }
    if (!colored(child) && isNodeInScope(firstCfg, scope)) {
      TraverseBblocksExtent(child, to, scope, action);
    }
  }
}

// Calls "action" on all the bblocks that exist within the lexical scope
// of the given TreeNode. Only works for ForEachStmtNodes right now.
void TraverseBblocksScope(TreeNode *scope, void action(Bblock *b)) {
  assert(isForEachStmtNode(scope));

  CfgExtent extent = scope->getCfgExtent();
  CfgNode *start = extent.entry, *end = extent.exit;
  TraverseBblocksExtent(start->bblock, end->bblock, scope, action);
  nextBblockColor++;
}

// Utility for UnmarkBblocks.
static void markBblocks(Bblock *b, int mark) {
  b->nodeStatus(mark);
  ListIterator<Bblock *> succs = b->succIter();
  for (; !succs.isDone(); succs.next()) {
    Bblock *child = *succs;
    if (child->nodeStatus() != mark) {
      markBblocks(child, mark);
    }
  }
}

// Unmarks all the bblocks in the graph. Resets the marking color back to 1.
void UnmarkBblocks(Bblock *b) {
  /* Use two coats of paint to make sure the mark routine doesn't miss any
     nodes. The alternative is to use an additional field in the CFG nodes
     which keeps track of the "visited" state for a node. */
  markBblocks(b, -1);
  markBblocks(b, 0);
  nextBblockColor = 1;
} 

static llist<Bblock *> *worklist;

// Recursion utility for setupWorklist().
static void traverseRevPost(Bblock *b) {
  color(b);
  ListIterator<Bblock *>succs = b->succIter();
  for (; !succs.isDone(); succs.next()) {
    Bblock *child = *succs;
    if (!colored(child)) {
      traverseRevPost(child);
    }
  }
  worklist = cons(b, worklist);
}

// Sets up the global worklist in reverse postorder.
static void setupWorklist(Bblock *b) {
  worklist = NULL;
  traverseRevPost(b);
}  

// Calls "action" on each bblock in the graph until nothing changes.
// "action" should return true if it changed the bblock, false otherwise.
void TraverseBblocksIter(Bblock *b, bool action(Bblock *b))
{
  setupWorklist(b);
  // The nodes on the list, and only those, will be colored with the current
  // color. All other nodes will have some other color.
  while (worklist) {
    // pull a node off the worklist, call the action on it, and uncolor it.
    Bblock *current = worklist->front();
    bool changed = action(current);
    current->nodeStatus(nextBblockColor-1);  // uncolor
    worklist = worklist->free();

    // If the node was changed, put its uncolored succs on the list
    if (changed) {
      ListIterator<Bblock *>succs = current->succIter();
      for (; !succs.isDone(); succs.next()) {
	Bblock *child = *succs;
	if (!colored(child))  {
	  color(child);
	  worklist = extend(worklist, cons(child));
	}
      }
    }
  }
  nextBblockColor++;
}

// Recursion utility for TraverseBblocks().
static void dfoBblocks(Bblock *b, void action(Bblock *b)) {
  color(b);
  action(b);
  ListIterator<Bblock *> succs = b->succIter();
  for (; !succs.isDone(); succs.next()) {
    Bblock *child = *succs;
    if (!colored(child)) {
      dfoBblocks(child, action);
    }
  }
}

// Calls "action" on each bblock once, in DFO. 
void TraverseBblocks(Bblock *b, void action(Bblock *b)) {
  dfoBblocks(b, action);
  nextBblockColor++;
}
  

static void markCfgExts(CfgNode *from, CfgNode *to, int mark) {
  from->nodeStatus(mark);
  if (from != to) {
    ListIterator<CfgNode *> succs = from->succIter();
    for (; !succs.isDone(); succs.next()) {
      CfgNode *child = *succs;
      if (child->nodeStatus() != mark) {
	UnmarkCfgExts(child, to);
      }
    }
  }
}

// Unmarks the extent of the CFG which lies between "from" and "to", 
// inclusive.
void UnmarkCfgExts(CfgNode *from, CfgNode *to) {
  /* Use two coats of paint to make sure the mark routine doesn't miss any
     nodes. The alternative is to use an additional field in the CFG nodes
     which keeps track of the "visited" state for a node. */
  markCfgExts(from, to, -1);
  markCfgExts(from, to, 0);
  nextCfgColor = 1;
}

static bool isNodeInScope(CfgNode *cfg, TreeNode *construct) {
  TreeNode *n = cfg->astNode();
  // We'll assume that omitted nodes are in scope. But the bblock scope
  // traverser must understand that because of this, omitted nodes are *not*
  // representative of the bblock they exist in.
  if (n == TreeNode::omitted)
    return true;
  while (n != NULL && n != construct)
    n = n->parent();
  return (n == construct);
}

bool childCanEscape(CfgNode *cfg) {
  TreeNode *n = cfg->astNode();
  return (cfg->numSucc > 1) || isGotoNode(n) || isReturnNode(n) || (n == TreeNode::omitted);
}

// Recursive engine for TraverseCfgExtents().
static void traverseCfgExtentsRec(CfgNode *from, CfgNode *to, 
				  void action(CfgNode *, void*), 
				  void* data) {
  color(from);
  action(from, data);
  if (from != to) {
    ListIterator<CfgNode *> succs = from->succIter();
    for (; !succs.isDone(); succs.next()) {
      CfgNode *child = *succs;

      if (isForEachStmtNode(to->astNode()) && childCanEscape(from) 
      	  && !isNodeInScope(child, to->astNode())) {
	continue;
      }
      if (colored(child)) {
	continue;
      }
      traverseCfgExtentsRec(child, to, action, data);
    }
  }    
}

// Traverses through the CF nodes between the given extents, calling "action"
// on each node.   Returns the nodeStatus with which the nodes were colored.
int TraverseCfgExtents(CfgNode *from, CfgNode *to, 
			void action(CfgNode *, void*), void* data) {
  traverseCfgExtentsRec(from, to, action, data);
  nextCfgColor++;
  return nextCfgColor-1;
}

// Traverses through the CF nodes that occur in the lexical scope of the
// given node, and calls action() on each one. Only works for foreach nodes
// right now.  Returns the nodeStatus with which the nodes were colored.
int TraverseCfgScope(TreeNode *scope, void action(CfgNode *, void*),
		      void* data) {
  assert(isForEachStmtNode(scope));
  CfgExtent extents = scope->getCfgExtent();
  return TraverseCfgExtents(extents.entry, extents.exit, action, data);
}

static void TraverseCfgRec(CfgNode *c, void action(CfgNode *))
{
  color(c);
  action(c);
  ListIterator<CfgNode *> succs = c->succIter();
  for (; !succs.isDone(); succs.next()) {
    CfgNode *t = *succs;
    if (!colored(t)) {
      TraverseCfg(t,action);
    }
  }
}

// Traverses through the CFG rooted at "c", calling "action" on each node.
int TraverseCfg(CfgNode *c, void action(CfgNode *))
{
  TraverseCfgRec(c, action);
  nextCfgColor++;
  return nextCfgColor - 1;
}



////////////////////////////////////////////////////////////
//                                                        //
// EXPRESSION-LEVEL CONTROL FLOW GRAPH                    //
//                                                        //
// Documented in cfg.txt, in the titanium-doc repository. //
////////////////////////////////////////////////////////////

bool CfgNode::straightLineCodeToOutside(const CFGset *l,
					CFGset *seen) const
{
  return ((ast_node != NULL && isReturnNode(ast_node)) ||
	  !contains(l, this) ||
	  (!contains(seen, this) &&
	   _succ != NULL &&
	   _succ->tail() == NULL &&
	   _succ->front()->straightLineCodeToOutside(l, adjoin(seen, this))));
}

bool CfgNode::straightLineCodeToOutside(const CFGset *l) const
{
  CFGset s;
  return straightLineCodeToOutside(l, &s);
}

static inline bool isReturn(const CfgNode *n)
{
  const TreeNode *t = n->astNode();
  return (t != NULL && isReturnNode(t));
}

llist<CfgNode *> *CfgNode::filterNSE(const CFGset *l, bool *ignoredAny)
{
  int j = 0;
  bool debug_dmp = DEBUG_OPT || DEBUG_DOM_VERBOSE;
  llist<CfgNode *> *result = NULL;
  for (ListIterator<CfgNode *> i(_pred); !i.isDone(); i.next(), j++) {
    if (contains(NSE, *i)) {
      if (debug_dmp)
	cout << "Predecessor " << j << " might be a non-standard exit" << endl;
      if (contains(l, *i) &&
	  (isReturn(*i) || straightLineCodeToOutside(l))) {
	if (ignoredAny != NULL)
	  *ignoredAny = true;
	if (debug_dmp) {
	  cout << "Removed predecessor " << j << "(";
	  shortCFGnode (cout, *i);
	  cout << ") of node ";
	  shortCFGnode (cout, this);
	  cout << endl;
	}
	continue;
      }
    }
    result = cons(*i, result);
  }
  return dreverse(result);
}


static llist<TreeNode *> *gotoList = NULL; 
static void cfgFixupGotos();

// Creates the expression-level CFG for the given tree. Called by
// setupBblocksMethod(), which is what the client should call.
static void MakeCfg(TreeNode *t) {
  assert(!gotoList);
  t->makeCfg();
  cfgFixupGotos();
  free_all(gotoList);
  gotoList = NULL;
}

// handy helper for constructing CfgExtent structs
static inline CfgExtent makeExtent(CfgNode *entry, CfgNode *exit) {
  CfgExtent extent;
  extent.entry = entry;
  extent.exit = exit;
  return extent;
}

CfgExtent TreeNode::getCfgExtent()
{
    undefined( "getCfgExtent" );
    return makeExtent(NULL,NULL);
}

CfgExtent StatementNode::getCfgExtent()
{
  return makeExtent(_cfgBeg, _cfgEnd);
}

StatementNode::StatementNode() : _cfgBeg(NULL), _cfgEnd(NULL) {}

/* unused
static bool emptyCfgP(CfgExtent cfg) {
  return !(cfg.entry || cfg.exit);
}
*/

      
/* We handle gotos by putting them on a list as we see them on the tree
   traversal (treating them as normal StatementNodes otherwise), and fixing 
   up their CF edges here. */
static void cfgFixupGotos() {
  // Go through all the GotoNodes we've found.
  ListIterator<TreeNode *> gotoIter = ListIterator<TreeNode *>(gotoList);
  for (; !gotoIter.isDone(); gotoIter.next()) {
    TreeNode *g = *gotoIter;
    // Get the CFG node at the tail of the GotoNode's extent.
    CfgNode *gotoTail = g->getCfgExtent().exit;
    // Unlink this node from all of its successors.
    ListIterator<CfgNode *> succIter = gotoTail->succIter();
    for (; !succIter.isDone(); succIter.next()) {
      (*succIter)->delPred(gotoTail);
    }
    gotoTail->delAllSucc();
    // Add the only correct successor, the goto target.
    CfgNode *destHead = g->destination()->getCfgExtent().entry;
    assert(destHead != NULL);
    gotoTail->addSucc(destHead);
    destHead->addPredNSE(gotoTail);
  }
}

CfgNode *TreeNode::getContinueTarget()
{
    undefined( "getContinueTarget" );
    return NULL;
}

CfgNode *IterationNode::getContinueTarget()
{
    return _cfgContinueNode;
}

CfgExtent TreeNode::getExceptionCfg()
{
    undefined( "getExceptionCfg" );
    return makeExtent(NULL, NULL);
}

CfgExtent TryStmtNode::getExceptionCfg()
{
    return makeExtent(_cfgCatch, _cfgFinally);
}

#define GOOD_CHILD(t) ((t) != NULL && !(t)->absent() && !(t)->isTypeNode())
// A post-order traversal CFG of the AST nodes
CfgExtent post_generic(TreeNode *n)
{
#if 0
  cout << "post_generic() called on: " << pseudocode(n) << endl;
#endif

    // DOB: written carefully to prevent adding any TypeNode children to CFG
    // Skip absent nodes as well.
    const int arity = n->arity();
    int childCount = 0;
    int firstGoodChild = -1;

    for (int i = 0; i < arity; i++) { // count how many aren't TypeNodes
      if (GOOD_CHILD(n->child(i))) {
        childCount++;
        if (firstGoodChild == -1) firstGoodChild = i;
      }
    }

    if (childCount == 0) {
	CfgNode *t = new CfgNode(n);
	return makeExtent(t, t);
    }
    
    CfgExtent c = n->child(firstGoodChild)->makeCfg();
    CfgNode *c_beg = c.entry;
    CfgNode *c_end = c.exit;
    for (int sweep = firstGoodChild+1; sweep < arity; sweep++) {
      TreeNode *child = n->child(sweep);
      if (GOOD_CHILD(child)) {
	CfgExtent next = child->makeCfg();
	CfgNode *next_beg = next.entry;
	CfgNode *next_end = next.exit;
	c_end->addSucc(next_beg);
	next_beg->addPred(c_end);
	c_end = next_end;
      }
    }
    CfgNode *t = new CfgNode(n);
    c_end->addSucc(t);
    t->addPred(c_end);
    return makeExtent(c_beg, t);
}
#undef GOOD_CHILD

CfgExtent append_cfg(CfgExtent c1, CfgExtent c2)
{
    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;
    c1_end->addSucc(c2_beg);
    c2_beg->addPred(c1_end);
    return makeExtent(c1_beg, c2_end);
}

CfgExtent append_cfg(CfgNode *c1, CfgExtent c2)
{
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;
    c1->addSucc(c2_beg);
    c2_beg->addPred(c1);
    return makeExtent(c1, c2_end);
}

CfgExtent append_cfg(CfgNode *c1, CfgNode *c2)
{
    c1->addSucc(c2);
    c2->addPred(c1);
    return makeExtent(c1, c2);
}

CfgExtent append_cfg(CfgExtent c1, CfgNode *c2)
{
    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    c1_end->addSucc(c2);
    c2->addPred(c1_end);
    return makeExtent(c1_beg, c2);
}

CfgExtent explicit_1(TreeNode *node, TreeNode *child)
{
    CfgNode *t = new CfgNode(node);
    CfgExtent c1 = makeExtent(t, t);
    CfgExtent c2 = child->makeCfg();
    return append_cfg(c2, c1);
}

CfgExtent explicit_2(TreeNode *node, TreeNode *child1, TreeNode *child2)
{
    CfgNode *t = new CfgNode(node);
    CfgExtent c1 = makeExtent(t, t);
    CfgExtent c2 = child1->makeCfg();
    CfgExtent c3 = child2->makeCfg();
    return append_cfg(append_cfg(c2, c3), c1);
}

CfgExtent explicit_3(TreeNode *node, TreeNode *child1,
			     TreeNode *child2, TreeNode *child3)
{
    CfgNode *t = new CfgNode(node);
    CfgExtent c1 = makeExtent(t, t);
    CfgExtent c2 = child1->makeCfg();
    CfgExtent c3 = child2->makeCfg();
    CfgExtent c4 = child3->makeCfg();
    return append_cfg(append_cfg(c2, append_cfg(c3, c4)), c1);
}

CfgExtent TreeNode::makeCfg()
{
    return post_generic(this);
}

CfgExtent StatementNode::makeCfg()
{
  // we require an explicit makeCfg() for each StatementNode, 
  // to prevent errors due to an incorrect default
  // see examples below
  cerr << "*** Internal Error: makeCfg() missing for this StatementNode:" << endl;
  print(cerr, 0);
  abort();
  return makeExtent(NULL,NULL);
}

CfgExtent TypeNode::makeCfg()
{
  abort(); // DOB: we never include TypeNodes in CFG (see cfg.h)
  return makeExtent(NULL,NULL);
}

CfgExtent ContinueNode::makeCfg()
{
    _cfgBeg = new CfgNode(this);
    _cfgEnd = new CfgNode(TreeNode::omitted);
    CfgNode *target = destination()->getContinueTarget();
    append_cfg(_cfgBeg, target);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent GotoNode::makeCfg() 
{
  _cfgBeg = new CfgNode(TreeNode::omitted);
  _cfgEnd = new CfgNode(this);

  // append, not cons, because we may be traversing this list right now.
  gotoList = extend(gotoList, static_cast<TreeNode *>(this));
  return append_cfg(_cfgBeg, _cfgEnd);
}

/* Should be same as DummyNode::makeCfg(). */
CfgExtent ExpressionStmtNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent c = expr()->makeCfg();
    return append_cfg(_cfgBeg, append_cfg(c, _cfgEnd));
}

/* Should be same as ExpressionStmtNode::makeCfg(). */
CfgExtent DummyNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent c = expr()->makeCfg();
    return append_cfg(_cfgBeg, append_cfg(c, _cfgEnd));
}

CfgExtent VarDeclNode::makeCfg()
{
  return explicit_1(this, initExpr());
}

CfgNode *LastMethodNode(TreeNode *p)
{
    while (  (strcmp(p->oper_name(), "MethodDeclNode") != 0)
	   && (strcmp(p->oper_name(), "ConstructorDeclNode") != 0))
	p = p->parent();
    CfgExtent t;
    t = p->body()->getCfgExtent();
    CfgNode *dest = t.exit;
    return dest;
}

static CfgNode *ReturnTarget(TreeNode *p);

CfgExtent ReturnNode::makeCfg()
{
  CfgNode *myCfg = new CfgNode(this);
  CfgNode *target = ReturnTarget(this);
  myCfg->addSucc(target);
  target->addPredNSE(myCfg);

  // AK -- old version below ignores finally nodes
  //CfgNode *myMethod = LastMethodNode(this);
  //myCfg->addSucc(myMethod);
  //myMethod->addPredNSE(myCfg);

  if (expr() != TreeNode::omitted) {
    CfgExtent exprCfg = expr()->makeCfg();
    append_cfg(exprCfg, myCfg);
    _cfgBeg = exprCfg.entry;
  }
  else {
    _cfgBeg = myCfg;
  }
  _cfgEnd = new CfgNode(TreeNode::omitted);
  return makeExtent(_cfgBeg, _cfgEnd);
}

void UnmarkCfg(CfgNode *c)
{
    c->nodeStatus(0);
    ListIterator<CfgNode *> succs = c->succIter();
    for (; !succs.isDone(); succs.next()) {
	CfgNode *t = *succs;
	if (t->nodeStatus())
	    UnmarkCfg(t);
    }
}


CfgExtent MethodDeclNode::makeCfg()
{
  CfgExtent argCfg = params()->makeCfg();
  CfgExtent bodyCfg = body()->makeCfg();
  return append_cfg(argCfg, bodyCfg);
}

CfgExtent ConstructorDeclNode::makeCfg()
{
  CfgExtent argCfg = params()->makeCfg();  
  CfgExtent b = body()->makeCfg();
  CfgExtent c = constructorCall()->makeCfg();
  return append_cfg(argCfg, append_cfg(c, b));
}

CfgExtent FieldDeclNode::makeCfg()
{
    CfgNode *t = new CfgNode(this);
    return makeExtent(t, t);
}

CfgExtent ObjectFieldAccessNode::makeCfg()
{
    return explicit_1(this, object());
}

CfgExtent TypeFieldAccessNode::makeCfg()
{
    CfgNode *t = new CfgNode(this);
    return makeExtent(t, t);
}

CfgExtent ThisFieldAccessNode::makeCfg()
{
    CfgNode *t = new CfgNode(this);
    return makeExtent(t, t);
}

CfgExtent SuperFieldAccessNode::makeCfg()
{
  return post_generic(this);
  /*
  CfgNode *t = new CfgNode(this);
  return cons(t, cons(t));
  */
}

CfgExtent SRArrayAccessNode::makeCfg()
{
  if (test_sr ||
      (bounds_checking && ((ForEachStmtNode *) WRTloop())->partialDomain()))
    return ArrayAccessNode::makeCfg();
  CfgNode *t = new CfgNode(this);
  return makeExtent(t, t);
}

CfgExtent OSRArrayAccessNode::makeCfg()
{
  if (test_sr ||
      (bounds_checking && ((ForEachStmtNode *) WRTloop())->partialDomain()))
    return ArrayAccessNode::makeCfg();
  CfgNode *t = new CfgNode(this);
  return makeExtent(t, t);
}

CfgExtent EmptyStmtNode::makeCfg()
{
    CfgNode *t = new CfgNode(this);
    _cfgBeg = _cfgEnd = t;
    return makeExtent(t, t);
}

CfgExtent CodeLiteralNode::makeCfg()
{
    // we must assume the literal code does not branch to outside places
    // and that it does not def or use any AST-visible data
    CfgNode *t = new CfgNode(this);
    _cfgBeg = _cfgEnd = t;
    return makeExtent(t, t);
}

CfgExtent PragmaNode::makeCfg()
{
  if (isPragma(Pragma::noCFG)) {
    CfgNode *t = new CfgNode(this);
    _cfgBeg = _cfgEnd = t;
    return makeExtent(t, t);
  } else
    return stmt()->makeCfg();
}

static CfgNode *ReturnTarget(TreeNode *p)
{
    TreeNode *par = p->parent();
    while (  (strcmp(par->oper_name(), "MethodDeclNode") != 0)
	     && (strcmp(par->oper_name(), "ConstructorDeclNode") != 0)
	     && (strcmp(par->oper_name(), "StaticInitNode") != 0) ) {
	if (strcmp(par->oper_name(), "TryStmtNode") == 0) {
	  if (!isFinallyNode(p)) {
	    return par->getExceptionCfg().exit;
	  }
	}
	p = par;
	par = par->parent();
    }
    if (strcmp(par->oper_name(), "StaticInitNode") == 0) {
      return NULL;
    }
    else {
      /*
      if (DEBUG_OPT)
	cout << "Using end of enclosing " << par->oper_name() <<
	  " as return target\n";
      */
      return par->body()->getCfgExtent().exit;
    }
}

static CfgNode *ExceptionTarget(TreeNode *p)
{
    CfgNode *dest;
    TreeNode *par = p->parent();
    while (  (strcmp(par->oper_name(), "MethodDeclNode") != 0)
	     && (strcmp(par->oper_name(), "ConstructorDeclNode") != 0)
	     && (strcmp(par->oper_name(), "StaticInitNode") != 0) ) {
	if (strcmp(par->oper_name(), "TryStmtNode") == 0) {
	    if (strcmp(p->oper_name(), "TryNode") == 0)
	      return par->getExceptionCfg().entry;
	    else if (!strcmp(p->oper_name(), "FinallyNode"))
	      return par->getExceptionCfg().exit;
	}
	p = par;
	par = par->parent();
    }
    if (strcmp(par->oper_name(), "StaticInitNode") == 0) {
      dest = NULL;
    }
    else {
      /*
      if (DEBUG_OPT)
	cout << "Using end of enclosing " << par->oper_name() <<
	  " as exception target\n";
      */
      dest = par->body()->getCfgExtent().exit;
    }
    return dest;
}

CfgExtent TryStmtNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    _cfgCatch = new CfgNode(TreeNode::omitted);
    _cfgFinally = new CfgNode(TreeNode::omitted);

    CfgExtent c1 = block()->makeCfg();
    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    append_cfg(_cfgBeg, c1_beg);

    CfgExtent c2 = catches()->makeCfg();
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;
    append_cfg(_cfgCatch, c2_beg);

    CfgExtent c3 = finally()->makeCfg();
    CfgNode *c3_beg = c3.entry;
    CfgNode *c3_end = c3.exit;
    append_cfg(c1_end, c3_beg);

    // AK -- exception may not be caught by the catch clauses
    append_cfg(c2_beg, c3_beg); 

    append_cfg(c2_end, c3_beg);
    append_cfg(c3_end, _cfgEnd);
    append_cfg(_cfgFinally, c3_beg);

    CfgNode *c4 = ExceptionTarget(this);
    if (c4) {
	append_cfg(c3_end, c4);
	c4->markNSE(c3_end);
    }
	
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent CatchListNode::makeCfg()
{
    CfgNode *catchBeg = new CfgNode(TreeNode::omitted);
    CfgNode *catchEnd = new CfgNode(this);

    const int childCount = arity();
    for (int sweep=0; sweep<childCount; sweep++) {
	CfgExtent c = child(sweep)->makeCfg();
	CfgNode *c_beg = c.entry;
	CfgNode *c_end = c.exit;
	append_cfg(catchBeg, c_beg);
	append_cfg(c_end, catchEnd);
    }
	
    return makeExtent(catchBeg, catchEnd);
}

CfgExtent ForEachStmtNode::makeCfg()
{
    bool canBeEmpty = (cannotBeEmpty() == NULL);
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent c1 = vars()->makeCfg();
    CfgExtent c2 = stmt()->makeCfg();

    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;

    set<TreeNode *> startup;
    startup.insert(lo());
    startup.insert(hi());
    startup.insert(stride());
    for (set<TreeNode *>::const_iterator i = startup.begin();
	 i != startup.end(); ++i)
        if (*i != NULL && !(*i)->absent()) {
	    CfgExtent next = (*i)->makeCfg();
	    append_cfg(c1_end, next.entry);
	    c1_end = next.exit;
	}

    append_cfg(_cfgBeg, c1_beg);
    append_cfg(c1_end, c2_beg);
    if (canBeEmpty)
      append_cfg(c1_end, _cfgEnd);
    append_cfg(c2_end, c2_beg);
    append_cfg(c2_end, _cfgEnd);
    return makeExtent(_cfgBeg, _cfgEnd);    
}

/* Attach the children in sequential order, but don't attach the TreeListNode
   itself. */
CfgExtent TreeListNode::makeCfg()
{
  const int childCount = arity();

  if (childCount == 0) {
    CfgNode *terminal = new CfgNode(this);
    return makeExtent(terminal, terminal);
  }
  else {
    CfgNode *c_beg, *c_end;
    CfgExtent c = child(0)->makeCfg();
    c_beg = c.entry;
    c_end = c.exit;
    for (int sweep = 1; sweep < childCount; sweep++) {
      CfgExtent next = child(sweep)->makeCfg();
      CfgNode *next_beg = next.entry;
      CfgNode *next_end = next.exit;
      c_end->addSucc(next_beg);
      next_beg->addPred(c_end);
      c_end = next_end;
    }
    return makeExtent(c_beg, c_end);
  }
}  


CfgExtent BlockNode::makeCfg()
{
  // These nodes just clutter up the graph; we only need the outermost
  // one.
  if (isFunc(parent())) {
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent c = stmts()->makeCfg();
    return append_cfg(_cfgBeg, append_cfg(c, _cfgEnd));
  }
  else {
    CfgExtent c = stmts()->makeCfg();
    _cfgBeg = c.entry;
    _cfgEnd = c.exit;
    return c;
  }
}

CfgExtent ReorderNode::makeCfg()
{
  _cfgBeg = new CfgNode(TreeNode::omitted);
  _cfgEnd = new CfgNode(this);
  CfgExtent t = stmt()->makeCfg();
  return append_cfg(_cfgBeg, append_cfg(t, _cfgEnd));
}

CfgExtent LabeledStmtNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent t = stmt()->makeCfg();
    return append_cfg(_cfgBeg, append_cfg(t, _cfgEnd));
}

CfgExtent IfStmtNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);

    CfgExtent c1 = condition()->makeCfg();
    CfgExtent c2 = thenPart()->makeCfg();
    CfgExtent c3 = elsePart()->makeCfg();

    append_cfg(c1, c2);
    append_cfg(c1, c3);
    append_cfg(_cfgBeg, c1);
    append_cfg(c2, _cfgEnd);
    append_cfg(c3, _cfgEnd);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent WhileNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    _cfgContinueNode = _cfgBeg;

    CfgExtent c1 = test()->makeCfg();
    CfgExtent c2 = stmt()->makeCfg();

    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;

    append_cfg(_cfgBeg, c1_beg);
    append_cfg(c1_end, c2_beg);
    append_cfg(c1_end, _cfgEnd);
    append_cfg(c2_end, _cfgBeg);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent DoNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);

    CfgExtent c1 = test()->makeCfg();
    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    _cfgContinueNode = c1_beg;

    CfgExtent c2 = stmt()->makeCfg();
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;

    append_cfg(_cfgBeg, c2_beg);
    append_cfg(c2_end, c1_beg);
    append_cfg(c1_end, c2_beg);
    append_cfg(c1_end, _cfgEnd);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent ForNode::makeCfg()
{
    abort(); // ForNodes should all be lowered away and never reach Cfg build phase

    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);

    CfgExtent c1 = init()->makeCfg();
    CfgNode *c1_beg = c1.entry;
    CfgNode *c1_end = c1.exit;
    append_cfg(_cfgBeg, c1_beg);

    CfgExtent c2 = test()->makeCfg();
    CfgNode *c2_beg = c2.entry;
    CfgNode *c2_end = c2.exit;
    append_cfg(c1_end, c2_beg);
    append_cfg(c2_end, _cfgEnd);
    _cfgContinueNode = c2_beg;

    CfgExtent c3 = stmt()->makeCfg();
    CfgNode *c3_beg = c3.entry;
    CfgNode *c3_end = c3.exit;
    append_cfg(c2_end, c3_beg);

    CfgExtent c4 = update()->makeCfg();
    CfgNode *c4_beg = c4.entry;
    CfgNode *c4_end = c4.exit;
    append_cfg(c3_end, c4_beg);
    append_cfg(c4_end, c2_beg);
    return makeExtent(_cfgBeg, _cfgEnd);
}


CfgExtent SwitchNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent c1 = expr()->makeCfg();
    append_cfg(_cfgBeg, c1);

    TreeListNode *swB = switchBlocks();
    int c = swB->arity();
    CfgNode *prev = NULL;
    for (int i=0; i<c; i++) {
	CfgExtent t = swB->child(i)->makeCfg();
	append_cfg(c1, t);
	if (i != 0) {
	    append_cfg(prev, t);
	}
	prev = t.exit;
    }
    if (prev != NULL)
	append_cfg(prev, _cfgEnd);
    append_cfg(c1, _cfgEnd);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent BreakNode::makeCfg()
{
    _cfgBeg = new CfgNode(this);
    _cfgEnd = new CfgNode(TreeNode::omitted);
    CfgExtent t = destination()->getCfgExtent();
    CfgNode *target = t.exit;
    append_cfg(_cfgBeg, target);
    return makeExtent(_cfgBeg, _cfgEnd);
}

CfgExtent ThrowNode::makeCfg()
{
    _cfgBeg = new CfgNode(this);
    _cfgEnd = new CfgNode(TreeNode::omitted);

    CfgExtent c = expr()->makeCfg();
    CfgNode *c_beg = c.entry;
    CfgNode *c_end = c.exit;
    append_cfg(_cfgBeg, c_beg);
    
    CfgNode *dest = ExceptionTarget(this);
    assert(dest != NULL);
    append_cfg(c_end, dest);
    dest->markNSE(c_end);
    return makeExtent(_cfgBeg, _cfgEnd);    
}

CfgExtent CheckNullNode::makeCfg()
{
    _cfgBeg = new CfgNode(TreeNode::omitted);
    _cfgEnd = new CfgNode(this);
    CfgExtent t = expr()->makeCfg();
    return append_cfg(_cfgBeg, append_cfg(t, _cfgEnd));
}

CfgExtent MonitorFetchNode::makeCfg()
{
    CfgExtent t = append_cfg(new CfgNode(TreeNode::omitted), post_generic(this));
    _cfgBeg = t.entry;
    _cfgEnd = t.exit;
    return t;
} 

CfgExtent MonitorUseNode::makeCfg()
{
    CfgExtent t = append_cfg(new CfgNode(TreeNode::omitted), post_generic(this));
    _cfgBeg = t.entry;
    _cfgEnd = t.exit;
    return t;
}

CfgExtent ExprNode::makeCfg()
{
    return post_generic(this);
}

CfgExtent MethodCallNode::makeCfg()
{
    MethodDecl *d = (MethodDecl *)method()->simpName()->decl();
    TreeNode *declNode = d->source();
    bool u = false;
    if (!isOmittedNode(declNode) &&
	(declNode->throws()->arity() ||
	 (u = !isMethodCallWhereinNoExceptionsCanBeThrown(this)))) {
	CfgExtent c = post_generic(this);
	//CfgNode *c_beg = c.entry;
	CfgNode *c_end = c.exit;
	/*
	if (u && DEBUG_OPT)
	  cout << "Finding exception target for " << pseudocode(this) << endl;
	*/
	CfgNode *c_exc = ExceptionTarget(this);
	append_cfg(c_end, c_exc);
	c_exc->markNSE(c_end);
	return c;
    } else
	return post_generic(this);
}

CfgExtent NameNode::makeCfg()
{
    CfgNode *t = new CfgNode(this);
    return makeExtent(t, t);
}

//////////////////////////////////////////////////////////////////////////

/* Return true iff all CFG predecessors of t are in s. */
bool must_come_from(const StatementNode *t, const treeSet &s)
{
  CfgExtent extent = const_cast<StatementNode *>(t)->getCfgExtent();
  CfgNode *from = extent.entry;
  ListIterator<CfgNode *> preds = from->predIter();
  for (; !preds.isDone(); preds.next()) {
    const TreeNode *n = (*preds)->astNode();
    if (!n->absent() && !contains(s, n)) {
      cout << "must_come_from() failed:" << endl <<
	pseudocode(t) << endl << "has predecessor" << endl <<
	pseudocode(n) << endl;
      return false;
    }
  }
  return true;
}

static void summarizeLoopCFGNode (CfgNode* node, void* os0)
{
  summarizeCFGnode (node, *(ostream*) os0);
}

void summarizeLoopCFG (TreeNode* loop, ostream& os)
{
  TraverseCfgScope (loop, summarizeLoopCFGNode, &os);
}

				/* Debugging functions */

void dbg_cfg_print (CfgNode* cfg) 
{
  if (cfg == NULL)
    cout << "*null*" << endl;
  cfg->print (cout);
  cout << endl;
}