/* This file is for dominators and related information.  Dominators are
   computed over the CfgNodes, but being able to ask if CfgNode x
   dominates CfgNode y turns out to be not what was most useful.  So
   we convert that dominator info to a form that allows us to ask what
   each TreeNode dominates.
*/

#include "AST.h"
#include "cfg.h"
#include "optimize.h"
#include "OrderlySet.h"
#include "dominator.h"

static bool debug_dom, debug_domv;

typedef ListIterator<CfgNode*> CfgListIter;

typedef OrderlySet<TreeNode *> TreeSetFactory;
typedef TreeSetFactory::set OrderlyTreeSet;
typedef map< TreeNode *, OrderlyTreeSet > map_tree_to_OrderlyTreeSet;
typedef map< TreeNode *, map_tree_to_OrderlyTreeSet > 
    map_tree_tree_to_OrderlyTreeSet;
typedef map< TreeNode *, TreeSetFactory * > map_loop_to_Factory;

typedef OrderlySet<CfgNode *> CfgSetFactory;
typedef CfgSetFactory::set CfgSet;
typedef map< CfgNode *, CfgSet > map_cfgnode_to_cfgset;
typedef map< CfgSet, OrderlyTreeSet > map_cfgset_to_OrderlyTreeSet;

typedef vector<int>::iterator ints;

/* dominators[loop][t] = set of nodes that are dominators of t */
static map_tree_tree_to_OrderlyTreeSet dominators;
static map_tree_to_OrderlyTreeSet loopExits, everyIter;
static map_loop_to_Factory o;

static bool dominated2 (treeSet* s, TreeNode* t, TreeNode* WRTloop);
static void printDominatorTree (ostream&, const vector<int> &, 
				const vector<bool>&);


void
freeDomInfo(TreeNode *l)
{
  /* cout << "Freeing dom info for foreach at " <<
     l->position().asString() << endl; */

  delete o[l];

  dominators.erase(l);
  loopExits.erase(l);
  everyIter.erase(l);
  o.erase(l);

  /*  cout << "done freeing dom info for foreach at " <<
      l->position().asString() << endl; */
}

static void
printTreeSet (treeSet *s, ostream &os, int m)
{
  if (s->empty ()) {
    os << "empty" << endl;
  } else 
    for (treeSet::const_iterator i = s->begin (); i != s->end (); ++i) {
      indent (os, m);
      os << PLCODE2(os, *i) << endl;
    }
}

static void
printOrderlyTreeSet(TreeSetFactory &F,
		    OrderlyTreeSet s, ostream &os, int m)
{
  if (F.isEmpty(s)) {
    os << "empty" << endl;
  } else
    for (TreeSetFactory::set_iterator i = F.begin(s); i != F.end(s); ++i) {
      indent(os, m);
      os << PLCODE2(os, *i) << endl;
    }
}

static OrderlyTreeSet 
convert_cfgset(TreeSetFactory &F, CfgSetFactory &G, CfgSet s,
	       map_cfgset_to_OrderlyTreeSet &memo)
{
  // cout << "convert_cfgset()" << endl;
  OrderlyTreeSet &r = memo[s], tmp;
  if (r) {
    if (DEBUG_ORDERLY)
      cout << "memo hit" << endl;
    return r;
  }
  if (s != G.empty() && (tmp = memo[G.tail(s)])) {
    if (DEBUG_ORDERLY)
      cout << "memo tail hit" << endl;
    return (r = F.adjoin(G.head(s)->astNode(), tmp));
  }
  TreeSetFactory::lazyset result;
  for (CfgSetFactory::set_iterator i = G.begin(s);
       i != G.end(s);
       ++i)
    result.adjoin((*i)->astNode());
  return (r = F.makeset(result));
}

static OrderlyTreeSet
convert_treeset_to_OrderlyTreeSet(TreeSetFactory &F, const treeSet *s)
{
  OrderlyTreeSet result = F.empty();
  for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i)
    result = F.adjoin((TreeNode *) *i, result);
  return result;
}

void
assertAppearsOnEveryIter(const TreeNode *ee, const TreeNode *ll)
{
  TreeNode *e = const_cast<TreeNode *>(ee);
  TreeNode *l = const_cast<TreeNode *>(ll);
  debug_domv = DEBUG_DOM_VERBOSE;
  debug_dom = debug_domv || DEBUG_DOM;
  o[l]->adjoin(e, everyIter[l]);
}

bool
appearsOnEveryIter(const TreeNode *ee, const TreeNode *ll)
{
  TreeNode *e = const_cast<TreeNode *>(ee);
  TreeNode *l = const_cast<TreeNode *>(ll);
  debug_domv = DEBUG_DOM_VERBOSE;
  debug_dom = debug_domv || DEBUG_DOM;
  bool result = o[l]->contains(everyIter[l], e);
  if (debug_domv) {
    POPER2 (cout, ee); 
    if (result)
      cout << " appears";
    else
      cout << " does not appear";
    cout << " on every iteration of ";
    POPER2 (cout, ll); 
    cout << endl;
  }
  return result;
}

// is everything in s dominated by t?
static bool
dominated(OrderlyTreeSet s, TreeNode *t, TreeNode *WRTloop)
{
  map_tree_to_OrderlyTreeSet &d = dominators[WRTloop];
  TreeSetFactory &F = *o[WRTloop];
  for (TreeSetFactory::set_iterator i = F.begin(s); i != F.end(s); ++i)
    if (!F.contains(d[*i], t)) {
      if (debug_domv) {
	cout << PLCODE(t); cout << " does not dominate "; cout << PLCODE(*i) << endl;
      }
      return false;
    }

  return true;
}

bool
dominated(treeSet *s, TreeNode *t, TreeNode *WRTloop)
{
  bool result;

  debug_domv = DEBUG_DOM_VERBOSE;
  debug_dom = debug_domv || DEBUG_DOM;
  if (opt_use_new_dom) 
    result = dominated2 (s, t, WRTloop);
  else
    result = dominated(convert_treeset_to_OrderlyTreeSet(*o[WRTloop], s),
		       t, WRTloop);
  if (debug_domv) {
    POPER2 (cout, t);
    if (result)
      cout << " dominates";
    else
      cout << " does not dominate";
    cout << " all of the following nodes:" << endl;
    printTreeSet (s, cout, 4);
    cout << "with respect to loop ";
    POPER2 (cout, WRTloop);
    cout << endl;
  }
  return result;
}

static void
addToList(CfgNode *x, void* listp0)
{
  llist<CfgNode *>** listp = (llist<CfgNode*>**) listp0;
  if (debug_domv) {
    cout << "loop includes ";
    shortCFGnode (cout, x);
    cout << endl;
  }
  *listp = cons(x, *listp);
}

static map_tree_to_OrderlyTreeSet *
convert_cfgmap_to_astmap(TreeSetFactory &F, CfgSetFactory &G,
			 map_cfgnode_to_cfgset * r)
{
  // cout << "convert_cfgmap_to_astmap()" << endl;
  map_cfgset_to_OrderlyTreeSet memo;
  map_tree_to_OrderlyTreeSet *result = new map_tree_to_OrderlyTreeSet;
  for (map_cfgnode_to_cfgset::iterator i = r->begin(); i != r->end(); ++i) {
    OrderlyTreeSet &s = (*result)[(*i).first->astNode()],   
      t = convert_cfgset(F, G, (*i).second, memo);
#if 0
    size_t old_s_size = s->size();
#endif
    s = F.merge(s, t);
#if 0
    if (true || old_s_size != 0)
      cout << "Merge sets of size " << old_s_size << " and " << t->size() <<
	": " << s->size() << endl;
#endif
  }
  delete r;
  return result;
}

static CfgSet
list_to_CfgSet(CfgSetFactory &U, const llist<CfgNode *> *l)
{
  CfgSet s = U.empty();
  foreach_const (p, llist<CfgNode *>, *l)
    s = U.adjoin(*p, s);
  return s;
}

// Uses the algorithm from the Dragon book (Aho, Sethi, and Ullman) to
// compute dominators of a loop whose nodes are in l, assuming start
// node n0.  Returns a mapping from each node in l to a set of nodes
// in l that dominate it.  If ignoreNSE is set then edges marked NSE
// in the CFG are ignored.  This code could be improved by using bit
// vectors to represent sets, by leaking less memory, and by switching
// to a better algorithm (e.g., Tarjan and Lengauer's).
static map_tree_to_OrderlyTreeSet *
computeDominators(TreeSetFactory &F, llist<CfgNode *> *l, const CFGset *ls,
		  CfgNode *n0, bool ignoreNSE, bool *ignored)
{
  // cout << "computeDominators()" << endl;
  CfgSetFactory U;
  map_cfgnode_to_cfgset & result = *(new map_cfgnode_to_cfgset);

  // Initialization:
  //   D(n0) = n0
  //   D(n) = N   for n != n0, where N is the set of all nodes (handled below)
  result[n0] = U.singleton(n0);
  
  CfgSet everything = U.adjoin(n0, list_to_CfgSet(U, l));

  // Iteration:
  //  D(n) = n + intersection over predecessors p of n of D(p)
  int k = 0, count = 0, oldcount = -1;
  while (count != oldcount) {
    if (debug_dom) {
      cout << "Dom loop " << ++k << ", count = " << count <<
	  ", ignoreNSE = " << ignoreNSE << endl;
      if (k == 1 && debug_domv) {
	cout << endl << "summary of CFG:" << endl << endl;
	summarizeCFG(l, cout);
	cout << endl << "end of summary of CFG." << endl << endl;
      }
    }
    oldcount = count;
    count = 0;
    int p = 0, cfgsize = l->size();
    foreach (n, llist<CfgNode *>, *l) {
      CfgNode *a = *n;
      if (a == n0) {
	if (debug_domv) {
	  cout << "(" << ++p << " of " << cfgsize << ")"
	    " dominators for " << QCFG(n0) << ": self" << endl;
	}
      } else {
	if (debug_domv) {
	  cout << "(" << ++p << " of " << cfgsize << ")"
	    " working on dominators for " << QCFG(a) << endl;
	}
	ListIterator<CfgNode *> m = a->predIter(ignoreNSE, ls, ignored);
	if (m.isDone())
	  continue;
	CfgSet u = result[*m];
	if (u == NULL) {
	  u = result[*m] = everything;
	  if (debug_domv)
	    cout << "  doms are EVERYTHING" << endl;
	} else if (debug_domv) {
	  cout << "  doms are ";
	  // shortCfgSet(u, cout);
	  cout << endl;
	}
	m.next();
	for ( ; !m.isDone(); m.next()) {
	  if (result[*m] != NULL)
	    u = U.intersect(u, result[*m]);
	  if (debug_domv) {
	    cout << "  doms are ";
	    // shortCfgSet(u, cout);
	    cout << endl;
	  }
	}
	u = U.adjoin(a, u);
	result[a] = u;
	int size = u->size();
	if (debug_domv)
	  cout << int2string(size) << " dominators for " << QCFG(a) <<
	    " at " << a->astNode()->position().asString() << endl;
	count += size;
      }
    }
  }

  delete ls;
  return convert_cfgmap_to_astmap(F, U, &result);
}

static llist<TreeNode *> * 
cfglist_to_treelist(const llist<CfgNode *> *l)
{
  if (l == NULL)
    return NULL;
  llist<TreeNode *> * result = NULL;
  l = dreverse((llist<CfgNode *> *) l);
  foreach_const (p, llist<CfgNode *>, *l)
    result = cons((*p)->astNode(), result);
  l = dreverse((llist<CfgNode *> *) l);
  return result;
}

/* Return a set of nodes that are loop exits.  t is the loop.  l is
   the loop contents.  l plus t->stmt() is the list of nodes we should
   check.  For each element of l, if any successors are outside of l,
   then include that element in the result. */
static OrderlyTreeSet 
computeLoopExits(TreeSetFactory &F, llist<CfgNode *> *l,
		 TreeNode *t, bool ignoreNSE,
		 bool *ignored)
{
  OrderlyTreeSet lc = F.makeset(cfglist_to_treelist(l));
  // Assume t->stmt() is in the result.  The cfg is always built that way.
  OrderlyTreeSet result = F.singleton(t->stmt());

  ListIterator<CfgNode *> w;

  foreach (p, llist<CfgNode *>, *l) {
    if ((*p)->astNode () == t->stmt ()) {
      if (debug_domv) {
	cout << "Found loop exit: ";
	(*p)->print(cout);
	cout << " (loop's statement node)" <<  endl;
      }
    } else if ((*p)->astNode() != t)
      for (w = (*p)->succIter(); !w.isDone(); w.next()) {
	if (debug_domv) {
	  cout << "(";
	  shortCFGnode (cout, *p);
	  cout << "'s succ ";
	  shortCFGnode (cout, *w);
	  cout << ") checking if loop contains " <<
	    pseudocode((*w)->astNode()) << ": " <<
	    (F.contains(lc, (*w)->astNode()) ? "yes" : "no") << endl; 
	}
	if (!F.contains(lc, (*w)->astNode()))
	  if (ignoreNSE && (*w)->isNSE(*p)) {
	    *ignored = true;
	    if (debug_domv) {
	      cout << "Ignored loop exit from ";
	      shortCFGnode (cout, *p);
	      cout << ": ";
	      shortCFGnode (cout, *w);
	      cout << endl;
	    }
	  } else {
	    result = F.adjoin((*p)->astNode(), result);
	    if (debug_domv) {
	      cout << "Found loop exit: ";
	      (*p)->print(cout);
	      cout << " which is dominated by:" << endl;
	      printOrderlyTreeSet(F, dominators[t][(*p)->astNode()], cout, 2);
	    }
	    break;
	  }
      }
  }
  return result;
}

static bool
exprnode(TreeNode *t)
{
  return isExprNode(t);
}

/* A node in l appears on every iteration if it dominates every exit
   from the loop. */
static OrderlyTreeSet
computeEveryIter(TreeSetFactory &F,
		 llist<CfgNode *> *l,
		 OrderlyTreeSet exits,
		 map_tree_to_OrderlyTreeSet &dom,
		 const string &where)
{
  llist<TreeNode *> *exprnodes = filter(exprnode, cfglist_to_treelist(l));
  OrderlyTreeSet result = F.makeset(exprnodes);

  for (TreeSetFactory::set_iterator i = F.begin(exits); i != F.end(exits); ++i)
    result = F.intersect(result, dom[(TreeNode *) *i]);
  
  if (debug_dom) {
    cout << "Every Iter (loop at " << where << "):" << endl;
    printOrderlyTreeSet(F, result, cout, 2);
    cout << endl;
  }

  return result;
}

void
TreeNode::computeForeachDominators(bool ignoreNSE, int level)
{
  for (int i = arity(); i-- > 0; )
    child(i)->computeForeachDominators(ignoreNSE, level);
}

				/* Dominator data structure */

/* Dominator trees are represented as vectors of pointers to CFG
 * nodes (actually, vectors of indices into an array of CFG-node 
 * pointers) for immediate dominators, indexed by the loop depth (code for
 * an outer-level loop is stored at index 0).  The dominator trees
 * differ at different loop depths because the non-standard exits
 * (NSEs) are in general different at different depths.  For example,
 * an edge introduced by a 'try' statement may exit from one loop
 * body, but not that of an enclosing loop body.
 *
 * Because the immediate-dominator vectors reside in TreeNodes but
 * point to CFG nodes, one can extract dominator information for
 * either one, using the astNode () pointers in the CFG nodes. 
 */

static vector< vector<int> > immedDom;
static map<const TreeNode*, CfgNode*> cfg_for_ast;
static map<const TreeNode*, int> loopDepth;

/* This class encapsulates the Tarjan Lenguaer dominator algorithm.
 * The code is essentially transcribed from their article:
 * "A fast algorithm for finding dominators in a flowgraph", 
 * ACM TOPLAS, Vol. 1, No. 1, July 1979, pp. 121-141. */
template <class Successors, class Enumerator>
class DominatorTree {

private:

  Successors& E;
  int n;
  vector<int> parent, ancestor, child, vertex, label, semi, size;
  vector< vector<int> > pred, bucket;

  struct State {
    State (int v, Enumerator wp) 
      : v (v), wp (wp) {}
    int v;
    Enumerator wp;
  };

  void DFS(int v, vector<bool>& visited)
  {
    vector<State> stack;

    visited[v] = true;
    semi[v] = n = n + 1; 
    vertex[n] = label[v] = v; 
    ancestor[v] = child[v] = 0;
    size[v] = 1;
    stack.push_back (State (v, E.begin (v)));
    while (! stack.empty ()) {
      State& st = stack.back ();
      if (st.wp.isDone ())
	stack.pop_back ();
      else {
	int w = *st.wp;
	st.wp.next ();
	pred[w].push_back (st.v);
	if (semi[w] == 0 ) { 
	  parent[w] = st.v; 
	  visited[w] = true;
	  semi[w] = n = n+1;
	  vertex[n] = label[w] = w;
	  ancestor[w] = child[w] = 0;
	  size[w] = 1;
	  stack.push_back (State (w, E.begin (w)));
	}
      }
    }
  }

  void COMPRESS(int v) 
  {
    vector<int> stack;
    while (ancestor[ancestor[v]] != 0) {
      stack.push_back (v);
      v = ancestor[v];
    }

    while (! stack.empty ()) {
      int v = stack.back ();
      stack.pop_back ();
      if (semi[label[ancestor[v]]] < semi[label[v]] ) { 
	label[v] = label[ancestor[v]]; 
      }
      ancestor[v] = ancestor[ancestor[v]]; 
    }
  }

  int EVAL(int v) {
    if (ancestor[v] == 0) 
      return label[v]; 
    else { 
      COMPRESS(v); 
      return (semi[label[ancestor[v]]] >= semi[label[v]])
	? label[v] : label[ancestor[v]];
    } 
  }

  void LINK(int v, int w)
  {
    int s; 
    s = w; 
    while (semi[label[w]] < semi[label[child[s]]]) { 
      if (size[s] + size[child[child[s]]] >= 2 * size[child[s]]) {
	ancestor[child[s]] = s; 
	child[s] = child[child[s]];
      } else { 
	size[child[s]] = size[s]; 
	s = ancestor[s] = child[s]; 
      } 
    }
    label[s] = label[w]; 
    size[v] = size[v] + size[w]; 
    if (size[v] < 2*size[w] ) { 
      int t = s; s = child[v]; child[v] = t;
    } 
    while (s != 0) { ancestor[s] = v; s = child[s]; } 
  }
  
public: 
  DominatorTree (Successors& E, int n)
    : E (E), n (n), 
      parent (n+1), ancestor (n+1), child (n+1), 
      vertex (n+1), label (n+1), semi (n+1),
      size (n+1), pred (n+1), bucket (n+1) { }

  /** Set DOM[v] to the index of the immediate dominator of the node
   *  whose index is v for all nodes reachable from R.  Also sets
   *  VISITED[v] to true for each such node. */
  void DOMINATORS (int r, vector<int>& dom, vector<bool>& visited)
  {
    int u;

    dom.resize (n+1);

// step1: 
    for (int v = 1; v <= n; v += 1) { 
      pred[v].clear ();
      bucket[v].clear ();
      semi[v] = 0; 
    }
    n = 0;
    DFS(r, visited);
    size[0] = label[0] = semi[0] = 0;
    for (int i = n; i >= 2; i -= 1) { 
      int w = vertex[i];

//  step2:
      for (ints vp = pred[w].begin (), ve = pred[w].end (); vp != ve; vp++) { 
	int v = *vp;
	u = EVAL(v);
	if (semi[u] < semi[w]) semi[w] = semi[u]; 
      }
      bucket[vertex[semi[w]]].push_back (w);
      LINK(parent[w], w);

//  step3:
      {
	vector<int>& S = bucket[parent[w]];
	while (! S.empty ()) {
	  int v = S.back ();
	  S.pop_back ();
	  u = EVAL(v);
	  dom[v] = (semi[u] < semi[v]) ? u : parent[w]; 
	} 
      }
    } 
//step4: 
    for (int i = 2; i <= n; i += 1) { 
      int w = vertex[i]; 
      if (dom[w] != vertex[semi[w]] ) { 
	dom[w] = dom[dom[w]]; 
      }
    } 
    dom[r] = 0;
  }
};

static void
addToLoop (CfgNode* x, void* vect0)
{
  vector<bool>* vect = (vector<bool>*) vect0;
  (*vect)[x->nodeId ()] = true;
  if (x->astNode () != NULL && ! x->astNode ()->absent ()) {
    if (cfg_for_ast[x->astNode ()] != NULL 
	&& cfg_for_ast[x->astNode ()] != x) {
      cout << "ERROR: cfg_for_ast[AST node " << x->astNode ()
	   << "] = ";
      shortCFGnode (cout, cfg_for_ast[x->astNode ()]);
      cout << ", conflicting with ";
      shortCFGnode (cout, x);
      cout << endl;
    }
    cfg_for_ast[x->astNode ()] = x;
  }
}

class CfgLoopInfo {
public:
  /** The list of all exits from THIS: those that have a
   *  successor that is outside cfg. */
  vector<CfgNode*> exits;
  /** leadsOut[v] is true iff there is a path containing no branches
   *  from v out of CFG (i.e., ending at a Return or a branch to a
   *  node not in cfg. */
  vector<bool> leadsOut;
  vector<bool> reachable;
   
  TreeNode* loop;
  bool ignored; 
  bool ignoreNSE;

  CfgLoopInfo (TreeNode* loop, bool ignoreNSE)
    : loop (loop), ignoreNSE (ignoreNSE) {
    this->loop = loop;
    ignored = false;

    _inGraph.resize (cfgSize ());
    /* Find all nodes under LOOP and mark as in graph. */
    TraverseCfgScope (loop, addToLoop, &_inGraph);

    leadsOut.resize (cfgSize ());
    initExitInfo ();
    initLeadsOutInfo ();
  }

  size_t cfgSize () const {
    return CfgNode::maxId () + 1;
  }

  CfgNode* operator[] (int i) const {
    return CfgNode::node (i);
  }

  /** True iff CFG node #I is in the graph for this loop. */
  vector<bool> _inGraph;
  bool inGraph (const CfgNode* node) const {
    return _inGraph[node->nodeId ()];
  }

  /** An enumerator in the style of ListIterator for CFG successors. */
  struct SuccessorIterator {
    void skip () {
      while (! iter.isDone ()) {
	if (G->inGraph (*iter)) {
	  if (ignoreNSE && (*iter)->isNSE ((*G)[node])
	      && G->leadsOut[(*iter)->nodeId ()]) 
	    {
	      *ignored = true;
	      if (debug_domv) {
		cout << "Removed successor of node ";
		shortCFGnode (cout, (*G)[node]);
		cout << ": ";
		shortCFGnode (cout, (*iter));
		cout << endl;
	      }
	    }
	  else
	    break;
	}
	iter.next ();
      }
    }

    /** An enumerator for the non-suppressed successors node #NODE 
     *  of G that reside in G.  If ignoreNSE, then ignores edges 
     *  that lead (by a chain of single-exit nodes) to "non-standard
     *  exits". */
    SuccessorIterator (CfgLoopInfo& G, int node, bool ignoreNSE, 
		       bool& ignored)
      : G (&G), node (node), ignoreNSE (ignoreNSE), 
	iter (G[node]->succIter ()), ignored (&ignored) {
      skip ();
    }

    void next () {
      iter.next ();
      skip ();
    }

    bool isDone () {
      return iter.isDone ();
    }

    int operator* () const { return (*iter)->nodeId (); }

    CfgLoopInfo* G;
    int node;
    bool ignoreNSE;
    ListIterator<CfgNode*> iter;
    bool* ignored;
  };

  /** An enumerator of the successors of node V in THIS. */
  SuccessorIterator begin (int v) {
    return SuccessorIterator (*this, v, ignoreNSE, ignored);
  }

  /** Set DOM[v] to the immediate dominator of each node with index v in
   *  THIS, for entrance node ENTER.  Set VISITED[v] to true for each
   *  node reachable from ENTER. 
   *  Ignore non-standard exits (NSEs) from G if IGNORENSE and set 
   *  IGNORED iff any edges are ignored for this reason.  IGNORED is
   *  unchanged if ! IGNORENSE. */
  void computeDominators (CfgNode *enter, 
			  bool ignoreNSE, bool& ignored,
			  vector<int>& dom, vector<bool>& visited)
  {
    DominatorTree<CfgLoopInfo,CfgLoopInfo::SuccessorIterator> 
      domInfo (*this, cfgSize ()-1);
    domInfo.DOMINATORS (enter->nodeId (), dom, visited);
    if (ignoreNSE)
      ignored = this->ignored;
  }

private:
  void initExitInfo () {
    for (unsigned int i = 1; i < cfgSize (); i += 1) {
      CfgNode* node = (*this)[i];
      if (! inGraph (node))
	continue;
      if (node->astNode () == loop->stmt ())
	exits.push_back (node);
      else if (node->astNode () != loop) {
	for (CfgListIter w = node->succIter(); ! w.isDone (); w.next ()) {
	  if (!inGraph (*w)) {
	    if (ignoreNSE && (*w)->isNSE (node)) {
	      ignored = true;
	      if (debug_domv) {
		cout << "Ignored loop exit from ";
		shortCFGnode (cout, node);
		cout << ": ";
		shortCFGnode (cout, *w);
		cout << endl;
	      }
	    } else {
	      exits.push_back (node);
	      break;
	    }
	  }
	}
      }
    }
  }

  void markLeadsOutChain (CfgNode* node) {
    int n = node->nodeId ();
    if (! leadsOut[n] && node->hasOneSuccessor ()) {
      leadsOut[n] = true;
      for (ListIterator<CfgNode*> p = node->predIter (); !p.isDone ();
	   p.next ())
	markLeadsOutChain (*p);
    }
  }

  void initLeadsOutInfo () {
    for (unsigned int i = 1; i < cfgSize (); i += 1) {
      CfgNode* node = (*this)[i];
      if (! inGraph (node))
	continue;
      TreeNode* t = node->astNode ();
      if (! leadsOut[i] 
	  && ((t != NULL && isReturnNode (t))
	      || (node->hasOneSuccessor () && !inGraph (*node->succIter ()))))
	{
	  leadsOut[i] = true;
	  for (ListIterator<CfgNode*> p = node->predIter (); !p.isDone ();
	       p.next ())
	    markLeadsOutChain (*p);
	}
    }
  }

};

void 
computeMethodDominators (TreeNode* body, bool ignoreNSE)
{
  if (opt_use_new_dom) {
    immedDom.clear ();
    cfg_for_ast.clear ();
  }
}

static void 
computeEveryIter(CfgLoopInfo& G, TreeSetFactory &F, 
		 const vector<int>& immedDom, 
		 const vector<bool>& reachable,
		 OrderlyTreeSet& output) {
  llist<TreeNode*>* result;
  int num_reachable_exits;
  num_reachable_exits = G.exits.size ();
  vector<int> exits_dominated (G.cfgSize ());
  vector<int> candidates;

  result = NULL;
  for (int i = G.exits.size ()-1; i >= 0; i -= 1) {
    if (reachable[G.exits[i]->nodeId ()]) {
      if (candidates.size () == 0)
	for (int n = G.exits[i]->nodeId (); n != 0; n = immedDom[n]) {
	  candidates.push_back (n);
	  exits_dominated[n] += 1;
	}
      else
	for (int n = G.exits[i]->nodeId (); n != 0; n = immedDom[n])
	  exits_dominated[n] += 1;
    } else
      num_reachable_exits -= 1;
  }

  for (int i = 0; i < (int) candidates.size (); i += 1) {
    int n = candidates[i];
    if (exits_dominated[n] == num_reachable_exits) {
      TreeNode* t = G[n]->astNode ();
      if (t != NULL && isExprNode (t))
	result = cons (t, result);
    }
  }

  output = F.makeset (result);
}
 
static void 
computeForeachDominators2 (TreeNode* loop, bool ignoreNSE, int level,
			   bool& ignored, CfgLoopInfo*& G_ptr,
			   vector<bool>& reachable)
{
  G_ptr = new CfgLoopInfo (loop, ignoreNSE);
  CfgLoopInfo& G = *G_ptr;
  reachable.clear ();
  reachable.resize (G.cfgSize ());
  
  loopDepth[loop] = level;
  if ((int) immedDom.size () <= level)
    immedDom.resize (level+1);

  if (debug_dom) {
    cout << "Computing dominators of level " << level << " loop ";
    POPER2 (cout, loop);
    cout << ", ignoreNSE = " << ignoreNSE << endl;
    if (debug_domv) {
	cout << endl << "Summary of CFG:" << endl << endl;
	summarizeLoopCFG(loop, cout);
	cout << "Exit nodes:";
	for (unsigned int k = 0; k < G.exits.size (); k += 1) {
	  cout << " ";
	  shortCFGnode (cout, G.exits[k]);
	}
	cout << endl << "end of summary of CFG." << endl << endl;
    }
  }

  G.computeDominators (loop->stmt ()->getCfgExtent ().entry, ignoreNSE, ignored,
		       immedDom[level], reachable);
  if (debug_domv) {
    if (ignored) 
      cout << "Edges were ignored." << endl;
    cout << "Immediate dominator tree:" << endl;
    printDominatorTree (cout, immedDom[level], reachable);
    cout << endl;
  }
}

/** True iff T1 dominates T2 in loop level LEVEL */
static bool
dominates (const CfgNode* c1, const CfgNode* c2, int level)
{
  if (c1 == NULL || c2 == NULL) {
    cout << "Dominates called with a null CFG node." << endl;
    return false;
  }

  int c1i = c1->nodeId ();
  for (int c2i = c2->nodeId (); c2i != 0; c2i = immedDom[level][c2i])
    if (c2i == c1i)
      return true;
  return false;
}

/** True iff T dominates all members of S at loop depth LEVEL. */
static bool
dominated (treeSet* s, TreeNode* t, int level) 
{
  CfgNode* t_node = cfg_for_ast[t];
  for (treeSet::iterator i = s->begin (); i != s->end (); i++) {
    if (! dominates (t_node, cfg_for_ast[*i], level)) {
      if (debug_domv) {
	cout << PLCODE(t); cout << " does not dominate "; 
	cout << PLCODE(*i) << endl;
      }
      return false;
    }
  }
  return true;
}

static bool
dominated2 (treeSet* s, TreeNode* t, TreeNode* WRTloop) {
  return dominated (s, t, loopDepth[WRTloop]);
}


void
ForEachStmtNode::computeForeachDominators(bool ignoreNSE, int level)
{
  TreeNode::computeForeachDominators(ignoreNSE, level+1);

  CfgLoopInfo* G;
  vector<bool> reachable;
  debug_domv = DEBUG_DOM_VERBOSE;
  debug_dom = debug_domv || DEBUG_DOM;

  // Erase previously computed dominator info, if any.
  if (o[this] != NULL)
    freeDomInfo(this);

  TreeSetFactory &F = *(o[this] = new TreeSetFactory);

  if (opt_use_new_dom) {
    computeForeachDominators2 (this, ignoreNSE, level,
			       _partialDomain, G, reachable);
    computeEveryIter (*G, F, immedDom[level], reachable, everyIter[this]);
    delete G;
    if (debug_domv) {
      cout << "Computed dominators for "; 
      POPER2 (cout, this);
      cout << " (level " << level << ") with ignoreNSE = " << ignoreNSE
	   << "; _partialDomain = " << _partialDomain << endl;
    }
    return;
  }    

  llist<CfgNode *> *l;
  CfgExtent extent = getCfgExtent();
  CfgNode *from = extent.entry;
  CfgNode *to = extent.exit;

  l = NULL;
  TraverseCfgScope(this, addToList, &l);
  l = dreverse(l);

  if (debug_domv) {
    cout << "Computing dominators for foreach at " <<
      position().asString() << " (cfg size=" << l->size() << ")" << endl;
    cout << "Extents:" << endl;
    from->print(cout);
    to->print(cout);
    cout << endl << "Entire loop:" << endl << pseudocode(stmt()) << endl;
    int i = 0;
    foreach (p, llist<CfgNode *>, *l) {
      cout << i++ << ':' << endl;
      (*p)->print(cout);
    }
    cout << endl;
  } else if (debug_dom)
    cout << "Computing dominators(" << ignoreNSE << ") for" << endl <<
      pseudocode(this) << endl << endl;
  
  if (ignoreNSE)
    _partialDomain = false;
  const CFGset *ls = list_to_CFGset(l);

  dominators[this] = *computeDominators(F, l, ls, from, ignoreNSE, 
					&_partialDomain);
  if (debug_domv && _partialDomain) 
    cout << "Edges were ignored." << endl; 
  loopExits[this] = computeLoopExits(F, l, this, ignoreNSE, &_partialDomain);
  everyIter[this] = computeEveryIter(F, l, loopExits[this], dominators[this],
				     position().asString());

  free_all (l);
  if (debug_domv) {
    cout << "Computed dominators for "; 
    POPER2 (cout, this);
    cout << " (level " << level << ") with ignoreNSE = " << ignoreNSE
	 << "; _partialDomain = " << _partialDomain << endl;
  }
}

static void
printDominatorTree (ostream& os, const vector<int> & dom_tree, 
		    const vector<bool>& reachable)
{
  for (int i = 0; i < (int) dom_tree.size (); i += 1) {
    if (reachable[i]) 
      os << "  " << i << " --> " << dom_tree[i] << endl;
  }
}