/*
  code-defs.cc

  Performs Def/Use analysis.  The first part of the file contains utilities,
  then we have the code for uses, then the code for defs.

  */

/* 
   In this text, the term "variable" means "a thing which has an lval",
   i.e. an object, a field of an object, a field of a type, or an array
   element.

   The objects and methods manipulated herein form a package that is used to
   support def/use construction. It shouldn't be needed by an optimization
   phase; such a phase should use the def/use edges hooked up directly to
   variables. 

   A Defs object stores information about which variables are defined
   in a given section of code. In the general D-U analysis, this
   section of code is always a method; hence, every method has one
   Defs object. The purpose of a Defs object is twofold. First, it provides
   a one-to-one mapping between all the unique variable definitions that 
   occur within a method, and a set of unique integers which allow the
   definitions to be represented collectively by bitvectors. The second
   purpose of the Defs object is to calculate the kills and defs created
   by a given variable definition.
   
   Definitions are represented by DefNode objects, which are simply TreeNodes
   glued to their representative bitvector indices.

    Current level of conservatism in the def-use analysis:

    * Java objects are essentially always considered to be aliased when their types 
    are compatible, thus a def for the field of an object is also def for the same 
    field in all visible objects of compatible type 

    * Arrays are handled similarly - a def of one element is a def for all elements 
    in all arrays of compatible type 

    * Calls to methods which are not known to be side-effect free create defs for all 
    aliasable quantities 

    * Primitive local variables and parameters (i.e. variables with non-aliasable 
    types like int and double) - we keep very precise info about these, the only 
    conservatism comes from  path merging in the reaching analysis.

    * Immutables can't be aliased, so we provide more accurate information about 
    their fields - each field of each immutable is essentially treated as an independent 
    (primitive) local variable, but we're careful to also maintain the def-use info 
    for the entire immutable instance values

    If the results of a separate alias analysis are available, we try and use them 
    to remove some false defs while building the use-def links

   Written by CJ Lin
   Modified by Dan Bonachea, 11/2000
*/
   

#include <cassert>
#include <fstream>
#include <iomanip>
#include <iostream>
#include "AST.h"
#include "bitset.h"
#include "code-defs.h"
#include "code-grid.h"
#include "code-util.h"
#include "code.h"
#include "decls.h"
#include "FieldDecl.h"
#include "errors.h"
#include "interface.h"
#include "utils.h"
#include "optimize.h"
#include "template.h"

extern bool debug_defs;
extern bool test_sr;
extern bool bounds_checking;

// static field definitions for Defs class
Decl *Defs::fakeThisDecl = new FormalParameterDecl(intern("$fakeThisDecl$"), NULL, NULL, true);

/* forward decls */
bool aaFilter(TreeNode *assign, TreeNode *expr);
static bool typesMayBeAliased(TreeNode *assign, TreeNode *expr);

// Return a canonical representation of the type t with no modifiers.
xtype type2xtype(TypeNode *t)
{
  // strictly speaking, we should probably also strip the modifiers off
  // all the nested element types for array types, but it turns out that
  // with the current set of type modifiers legal for array elements,
  // two otherwise identical array types can't become aliased at the top level 
  // unless all element/sub-array type modifiers are identical

  static map<string, xtype> xtype_cache;

  if (xtype_cache.count(t->decl()->fullName()) > 0) {
    return xtype_cache[t->decl()->fullName()];
  }
  else {
  if (t->isTitaniumArrayType()) {
    // we may have grid pointers with different dimensionality type
    // aliased to the same data area (e.g. after a .slice() operation)
    // handle this by stripping top-level arity information when filing grid accesses
    TypeNode *elemtype = static_cast<TitaniumArrayTypeNode *>(t)->elementType();
    TypeNode *c = elemtype->withModifiers((Common::Modifiers) 0);
    xtype s = (xtype) (string("tiArray<?>_of_") + c->decl()->fullName());
    xtype_cache[t->decl()->fullName()] = s;
    return s;
  }
  else {
    TypeNode *c = t->withModifiers((Common::Modifiers) 0);
    xtype s = (xtype) c->decl()->fullName();
    xtype_cache[t->decl()->fullName()] = s;
    return s;
  }
  }
}

//---------------------------------------------------------------------------
// debug dumps
//---------------------------------------------------------------------------

static void dump_list(ostream &os, llist<DefNode *> *l, int indent)
{
  foreach (f, llist<DefNode *>, *l) {
    (*f)->t->print(os, indent);
    os << '\n';
  }
}


static string plural(int n, const string& s)
{
  return (n == 1) ? "1 " + s : (int2string(n) + ' ' + s + 's');
}

void Defs::print(ostream &os, int indent)
{
  int j;

  for (j = 0; j < indent; j++) os << ' ';
  os << "varDefs:";
  j = 0;
  for (map_decl_to_deflist::const_iterator v = _varDefs.begin();
       v != _varDefs.end();
       v++) {
    os << ' ' << *((*v).first)->name();
    j++;
  }
  if (j == 0) os << " none";
  os << '\n';

  for (j = 0; j < indent; j++) os << ' ';
  os << "fieldDefs:";
  for (map_decl_to_deflist::const_iterator b = _fieldDefs.begin();
       b != _fieldDefs.end();
       b++) {
    os << *(*b).first->container()->name() << "." << *(*b).first->name() << ": " << endl;
    dump_list(os, (*b).second, indent+10);
  }

  for (j = 0; j < indent; j++) os << ' ';
  os << "IIFDefs:";
  for (map_decl_field_to_deflist::const_iterator b = _IIFDefs.begin();
       b != _IIFDefs.end();
       b++) {
      for (map_string_to_deflist::const_iterator v = b->second.begin();
           v != b->second.end();
           v++) {
        os << *(*b).first->name() << "." << (*v).first << ": " << endl;
        dump_list(os, (*v).second, indent+10);
         }
  }

  for (map_type_to_deflist::const_iterator d = _arrayDefs.begin();
       d != _arrayDefs.end();
       d++) {
    for (j = 0; j < indent; j++) os << ' ';
    int count = (*d).second->size();
    os << "array type " << xtype2str((*d).first)
      << " has " << plural(count, "arrayDef");
    os << '\n';
  }

  os << "unknownMethods: " << (unknownMethods ? "yes" : "no") << '\n';
}

void Defs::printVardefs(ostream &os, int indent) {
  for (int j = 0; j < indent; j++) os << ' ';
  for (map_decl_to_deflist::const_iterator v = _varDefs.begin();
       v != _varDefs.end();
       v++) {
    os << (*v).first->name()->c_str() << ": ";
    dump_list(os, (*v).second, 0);
    os << endl;
  }
}

void Defs::printBitset(Bitset *bs, ostream &os, int indent) {
  // this should probably be modified to print the other def types as well
  for (map_decl_to_deflist::const_iterator v = _varDefs.begin();
       v != _varDefs.end();
       v++) {
    ListIterator<DefNode *>iter = (*v).second;
    for (; !iter.isDone(); iter.next()) {
      DefNode *def = *iter;
      if (bs->test(def->index)) {
	def->t->print(os, indent);
	os << endl;
      }
    }
  }
}


/////////////////////////////////////////////////////////////////////////////
// Defs
/////////////////////////////////////////////////////////////////////////////

bool ObjectNode::hasLval() const { return true; }
bool FieldAccessNode::hasLval() const { return true; }
bool ArrayAccessNode::hasLval() const { return true; }
bool ThisNode::hasLval() const { return theClass()->decl()->asType()->isImmutable(); }



// If this expression defines a variable, the subtree of that variable is returned.
// Otherwise the return value is NULL.
// MethodCallNodes also return NULL
// Note that the returned subtree may correspond to several DefNode's 
// (e.g. assigning to an immutable var)
TreeNode *getDefVar(TreeNode *t) {
  if (isAssignNode(t)) {
    return t->child(0);
  }
  else if (isForEachPairNode(t)) {
    return t->simpName();
  }
  else if (isParameterNode(t)) {
    return t->simpName();
  }
  else if (isVarDeclNode(t)) {
    return t->simpName();
  }
  return NULL;
}

// Returns a list of all the spots where a variable is defined.
// doesn't compute anything or update state - just returns cached answers
llist<DefNode *> *Defs::getAllDefs(TreeNode *t) {
  if (isObjectNode(t)) {
    assert(isNameNode(t->child(0)));
    return getAllDefs(t->child(0));
  } 
  else if (isThisNode(t)) {
    return varDefs(fakeThisDecl);
  }
  else if (isStaticFAN(t)) {
    // field accesses are filed under the class that declared them (see addTypeFieldDef)
    return fieldDefs(t->simpName()->decl());
  }
  else if (isIIFAN(t)) {
    return IIFDefs(getIIFANObjectDecl(t), getIIFANFieldID(t));
  }
  else if (isOFAN(t)) {
    // field accesses are filed under the class that declared them (see addTypeFieldDef)
    return fieldDefs(t->simpName()->decl());
  }
  else if (t->isArrayAccessNode()) {
    return arrayDefs(t->array()->type()); 
  }
  else if (isNameNode(t)) {
    return varDefs(t->decl());
  }
  else {
    cout << "Unknown def: " << endl;
    t->print(cout,0);
    cout << endl;
    abort();
    return NULL;
  }
}
//---------------------------------------------------------------------------
// reaching analysis and d-u/u-d chain construction
//---------------------------------------------------------------------------


// Defs::merge and Defs::reaching have nearly identical logic - this implements both
// takes the treenode to operate on, and functions to call which set and kill a 
// particular def by its index
void Defs::reachingAnal(TreeNode *t, void (*deffn)(int), void (*killfn)(int)) {

  llist<DefNode *> *deflist;
  llist<DefNode *> *tempdeflist = NULL; // list that gets deleted at end of block
  TreeNode *defvar = NULL;

  // If this expression defines a var, get the list of existing definitions
  // for that var (which will include this one).
  if (isMethodCallNode(t)) {
    deflist = callDefs(t);
  }
  else {
    defvar = getDefVar(t);
    if (!defvar) {
      return;
    }
    deflist = getAllDefs(defvar);

    // immutables need special attention, because their tree nodes 
    // may have more than one defnode attached
    if (isImmutableVar(defvar)) {
      // for immutable vars, we also need to consider the defs of all fields
      tempdeflist = copylist(deflist);
      Decl *objectDecl = getImmutableVarDecl(defvar);
      for (llist <string>* fields = immutableIFields(getImmutableVarType(defvar)); 
            fields; fields = fields->tail()) {
          tempdeflist = extend(tempdeflist, copylist(IIFDefs(objectDecl, fields->front())));
         }
      deflist = tempdeflist;
    }
    else if (isIIFAN(defvar)) {
      // for immutable fields, we also need to consider the defs of the immutable value
      tempdeflist = copylist(deflist);
      tempdeflist = extend(tempdeflist, 
                           copylist(varDefs(getIIFANObjectDecl(defvar)))); 
      deflist = tempdeflist;
    }
  }

  if (!deflist) {
    return;
  }

  // Go through the list of definitions and kill or def each one as 
  // appropriate. For example, if the var is not aliasable, then all defs
  // of it except this one should be killed.
  ListIterator<DefNode *> iter = deflist;
  for (; !iter.isDone(); iter.next()) {
    DefNode *defnode = *iter;
    if (defnode->t == t) {
      (*deffn)(defnode->index);
    }
    else {
      // Every DefNode hooked up to a MethodCallNode ought to have the SAME 
      // MethodCallNode as its definition point. The bitset indices are what
      // differentiate two DefNodes in a MethodCallNode.
      assert(!isMethodCallNode(t));

      // If the var is aliasable, then deflist contains the list of all the
      // defs that may also be defs of this var; we don't know for sure. The 
      // kill set is currently defined as a "must kill", so we can't kill 
      // any of them.

      if ((isObjectNode(defvar)) && (isDummyNode(t->parent()) == false)) {
	// isDummyNode check is related to PR499, it makes sure that
	// assignment within a dummy node does not kill actual defs
        // assignment target is a local primitive or immutable 
        // kill any other defs of this value
        // for immutable vars, also kills any immutable instance field defs
        (*killfn)(defnode->index);
      }

      else if ((isIIFAN(defvar)) && (isDummyNode(t->parent()) == false)) {
	// isDummyNode check is related to PR499, it makes sure that
	// assignment within a dummy node does not kill actual defs
        // assignment target is the field of an immutable - kind of tricky
        // kills any other defs of this same field, which could be generated by an IIFAN or immutable var def
        // (but doesn't kill the entire immutable var, since it only defs one component of the immutable value)
        Decl *objectDecl = getIIFANObjectDecl(defvar);
        string fieldID = getIIFANFieldID(defvar);
        TreeNode *otherdef = getDefVar(defnode->t); 
        assert(otherdef != NULL);
        if (isIIFAN(otherdef) && getIIFANFieldID(otherdef) == fieldID) {
          // otherdef is an IIFAN def for same field of same immutable var
          assert(getIIFANObjectDecl(otherdef) == objectDecl);
          (*killfn)(defnode->index);
        }
        else if (isImmutableVar(otherdef)) {
          //  or a def for the same entire immutable var
          assert(getImmutableVarDecl(otherdef) == objectDecl);
          if (find(defnode, IIFDefs(objectDecl, fieldID))) // kill it if it's a field def created by a var def
            (*killfn)(defnode->index);
        }
        else {
          // last possibility is a field def for a different field - do nothing
          // (these show up because we added in defs of the immutable value)
          assert(isIIFAN(otherdef) && getIIFANFieldID(otherdef) != fieldID);
        }
      }
    }
  }
  free_all(tempdeflist); // free immutable list we allocated, if necessary
}

// If t defines a variable, then the def and kill sets given are updated
// accordingly. These def and kill sets are "running totals" for the current
// bblock.
static Bitset *_mergedefs = NULL;
static Bitset *_mergekills = NULL;
static void mergedef(int idx) {
  assert(_mergedefs && _mergekills);
  _mergedefs->set(idx);
  _mergekills->clear(idx);
  }
static void mergekill(int idx) {
  assert(_mergedefs && _mergekills);
  _mergekills->set(idx);
  }
void Defs::merge(TreeNode *t, Bitset *defs, Bitset *kills) {
  _mergedefs = defs;
  _mergekills = kills;
  reachingAnal(t, mergedef, mergekill);
  _mergedefs = _mergekills = NULL;
  }

// If t defines a variable, then existing defs of that variable in the
// reaching set are killed and the appropriate def is set. The reaching
// set is used within a bblock to say which defs reach a particular
// TreeNode. This set is temporary and only used while walking through a
// Bblock to hook up UD edges. This routine is pretty much the same logic
// as Defs::merge. The reason why we are doing it is because we lost the
// intra-bblock def/kill info when we did Defs::merge---that method is used
// to compute inter-bblock def/kill info. Memoizing to avoid redundancy would
// be a Good Idea.
static Bitset *_reachingbitset = NULL;
static void reachingdef(int idx) {
  assert(_reachingbitset != NULL);
  _reachingbitset->set(idx);
  }
static void reachingkill(int idx) {
  assert(_reachingbitset != NULL);
  _reachingbitset->clear(idx);
  }

void Defs::reaching(TreeNode *t, Bitset *reaching) {
  _reachingbitset = reaching;
  reachingAnal(t, reachingdef, reachingkill);
  _reachingbitset = NULL;
  }

 /* An SRArrayAccessNode or an OSRArrayAccessNode should not
   necessarily have as many def/use edges as other ArrayAccessNodes. */
static bool isOptimizedAway(TreeNode *t)
{
  if (!test_sr) {
    ForEachStmtNode *loop = NULL;
    if (isSRArrayAccessNode(t))
      loop = ((ForEachStmtNode *)
            static_cast<SRArrayAccessNode *>(t)->WRTloop());
    else if (isOSRArrayAccessNode(t))
      loop = ((ForEachStmtNode *)
            static_cast<OSRArrayAccessNode *>(t)->WRTloop());
    if (loop != NULL && (!bounds_checking || !loop->partialDomain()))
      return true;
  }
  return false;
}

// Finds the instance of the defining variable in a given defining expression,
// and hooks up a d->u edge to the given use.
void connectDuEdge(TreeNode *defExpr, TreeNode *use) {
  if (isMethodCallNode(defExpr)) // don't keep use lists for MethodCallNodes
    return;

  // Has use been optimized away?
  if (isOptimizedAway(use->parent()))
      return;

  TreeNode *defVar = getDefVar(defExpr);
  assert(defVar != NULL);

  if (DEBUG_PHASE_ENABLED("usedef", currentFilename))
    {
    cout << "connectDuEdge(";
    PCODE(defExpr);
    cout << ", ";
    PCODE(use);
    cout << "), defVar=";
    defVar->pseudoprint(cout, 0);
    cout << endl;
  }

  defVar->setUses(cons(use, defVar->getUses()));
}

//---------------------------------------------------------------------------

// Given the reaching bitset for a given use, connect u->d edges. 
void Defs::connect(TreeNode *var, Bitset *reaching) {
  llist<DefNode *> *deflist = getAllDefs(var);
  llist<DefNode *> *tempdeflist = NULL; // list that gets deleted at end of block

  // array element inheritance aliasing is handled at def lookup time
  if (isArrayAccessNode(var)) {
      // arrays whose elements have reference type may be aliased by any array whose
      // elements are an ancestor or descendent type of our element type
      llist<TypeNode*>* aliasedTypes = aliasableArrayTypes(var->array()->type());
      while (aliasedTypes) { // add defs for compatible types
        tempdeflist = extend(tempdeflist, copylist(arrayDefs(aliasedTypes->front())));
        aliasedTypes = aliasedTypes->tail();
      }
      if (tempdeflist) { // add our defs (or just keep ours if there's no others)
        tempdeflist = extend(copylist(deflist), tempdeflist);
        deflist = tempdeflist;
      }
    }

  if (!deflist) {
    return;
  }

  // make sure we don't ask alias analysis about inaliasable quantities
  // (quantities whose value can only change via a single "access-path")
  // we already have the best info possible about those
  bool notAliasable = isImmutableVar(var) || isIIFAN(var) || isThisNode(var) || 
                      isObjectNode(var) || isNameNode(var) || isStaticFAN(var);

  llist<TreeNode *> *udlist = NULL;
  ListIterator<DefNode *> iter = deflist;
  for (; !iter.isDone(); iter.next()) {
    DefNode *defnode = *iter;
    if (reaching->test(defnode->index) && 
        (notAliasable || 
         (typesMayBeAliased(defnode->t,var) && aaFilter(defnode->t, var))
         )) {

      #if 0
        cout << "add to defs (";
        PCODE(var);
        cout << ", ";
        PCODE(defnode->t);
        cout << ")" << endl;
      #endif

      udlist = cons(defnode->t, udlist);
      connectDuEdge(defnode->t, var);
    }
  }
  var->setDefs(udlist);

  free_all(tempdeflist); // free temporary list we allocated, if necessary
}

//---------------------------------------------------------------------------
// alias analysis support

/* The possible values of the object if expr is an ArrayAccessNode or
   ObjectFieldAccessNode, or NULL otherwise. */
Bitset *getObjectAbstractValues(TreeNode *expr)
{
  if (isOFAN(expr))
    return expr->object()->getAbstractValues();
  if (isArrayAccessNode(expr))
    return expr->array()->getAbstractValues();
  return NULL;
}

/* The possible values modified by the given MethodCallNode, or AssignNode
   into an ArrayAccessNode or ObjectFieldAccessNode. */
Bitset *getModifiedObjectValues(TreeNode *assign)
{
  if (isAssignNode(assign))
    return getObjectAbstractValues(assign->opnd0());
  if (isMethodCallNode(assign))
    return assign->modifiesValues();
  return NULL;
}

/* assign is an AssignNode or MethodCallNode, expr is an ExprNode with an
   l-value. Returns false if the assignment cannot possibly have defined
   expr (from aliasing info). */
bool aaFilter(TreeNode *assign, TreeNode *expr)
{
  Bitset *modValues = getModifiedObjectValues(assign);
  Bitset *objectValues = getObjectAbstractValues(expr);
  if (modValues != NULL && objectValues != NULL) {
    bool r = modValues->disjoint(objectValues);
    bool debug = DEBUG_PHASE_ENABLED("usedef", currentFilename);
    if (r && debug) {
      assign->pseudoprint(cout, 1);
      cout << " cannot possibly have defined ";
      expr->pseudoprint(cout, 0);
      cout << endl;
    }
    return !r;
  }
  return true;
}
static bool noOverLap(ArrayAccessNode *def, ArrayAccessNode *use){
  //make sure the array accesses are to Titanium array, I don't deal with Java arrays right now
  TypeNode *def_type = def->array()->type();
  TypeNode *use_type = use->array()->type();

  if ((def_type->isTitaniumArrayType() == false) || (use_type->isTitaniumArrayType() == false)){
    return false;
  }

  Bitset *def_location_set = def->array()->location_set;
  Bitset *use_location_set = use->array()->location_set;
  if ((def_location_set != NULL) && (use_location_set != NULL)){
    if (def_location_set->disjoint(use_location_set)){
      return true;
    }
    else{
      return false;
    }
  }
  else{
    return false;
  }
}
/* assign is an AssignNode or MethodCallNode, expr is an ExprNode with an
   l-value. Returns false if the assignment cannot possibly have defined
   expr (from type info). This is a useful cleanup method for expressing 
   type-based constraints that aren't easily encoded in the def-use tables
   to remove a few more extraneous def-use edges
*/
static bool typesMayBeAliased(TreeNode *assign, TreeNode *expr) {
  if (isMethodCallNode(assign)) return true; // method call may define anything aliasable
  assert(isAssignNode(assign));
  TreeNode *destexpr = assign->opnd0();
  if (infer_nooverlap){
    if (isArrayAccessNode(destexpr)) {
      assert(isArrayAccessNode(expr)); 
      if (noOverLap((ArrayAccessNode *) destexpr, (ArrayAccessNode *) expr)){
	return false;
      }
    }
  }
  TypeNode* deftype=NULL, *usetype=NULL;

  if (isOFAN(destexpr)) {
    deftype = destexpr->object()->type(); // defing a field
    assert(isOFAN(expr));
    usetype = expr->object()->type();
  }
  else if (isArrayAccessNode(destexpr)) {
    deftype = destexpr->array()->type(); // defing an array elem
    assert(isArrayAccessNode(expr)); 
    usetype = expr->array()->type();
  }
  else {
    cout << "Internal def-use error: this should never happen" << endl;
    cout << "destexpr= ";
    destexpr->pseudoprint(cout, 0);
    cout << endl;
    cout << "expr= ";
    expr->pseudoprint(cout, 0);
    cout << endl;
    abort(); // should never happen (ObjectNodes, etc. aren't aliasable)
  }

  if (deftype->sharing() == Shared &&  usetype->sharing() == Nonshared ||
      deftype->sharing() == Nonshared &&  usetype->sharing() == Shared) {
    if (debug_defs) {
      assign->pseudoprint(cout, 1);
      cout << " cannot possibly have defined ";
      expr->pseudoprint(cout, 0);
      cout << "  (due to sharing information)" << endl;
    }
    return false;
  }

  return true; // be conservative for everything else
}
//---------------------------------------------------------------------------
// Def creation
//---------------------------------------------------------------------------
// Makes the given node a def of everything aliasable.
void Defs::defAllAliasable(TreeNode *t) {
  
  // def all the object fields we def or use
  map_decl_to_bool::iterator fieldIter; 
  for (fieldIter = _aliasableFields.begin(); 
       fieldIter != _aliasableFields.end(); 
       fieldIter++) {
      DefNode *newDef = new DefNode(t, nextindex++);
      // Add the new DefNode to the list of defs that the call makes.
      // We will use this when calculating bitsets.
      llist<DefNode *> *&l = callDefs(t);
      l = cons(newDef, l);

      // Add the new DefNode to the list of defs for the variable it defines.
      // We will use this when connecting ud edges.
      llist<DefNode *> *&fl = fieldDefs(fieldIter->first);
      fl = cons(newDef, fl);
  }

  // def all the array types whose elements we def or use
  map_type_to_bool::iterator arrIter;
  for (arrIter = _aliasableArrays.begin();
       arrIter != _aliasableArrays.end();
       arrIter++) {
    // Add the new DefNode to the list of defs that the call makes.
    // We will use this when calculating bitsets.
    DefNode *newDef = new DefNode(t, nextindex++);
    llist<DefNode *> *&l = callDefs(t);
    l = cons(newDef, l);

    // Add the new DefNode to the list of defs for the variable it defines.
    // We will use this when connecting ud edges.
    llist<DefNode *> *&al = _arrayDefs[arrIter->first]; // small hack: we have an xtype here
    al = cons(newDef, al);
  }
}

// Takes all the unknown method calls we saved in methodCalls and makes all
// of them defs of every aliasable entity.
void Defs::addCallDefs(void) {
  ListIterator<TreeNode *> iter = methodCalls;
  for (; !iter.isDone(); iter.next()) {
    defAllAliasable(*iter);
  }
}

void Defs::addTypeFieldDef(Decl* fieldDecl, TreeNode *assignment)
{
  assert(!isIIFAN(getDefVar(assignment))); // immutables use addIIFDef
  // make sure we file field accesses under their "owning" type
  // (the class which declared the field, which may be different than the class
  // we're currently using to access this (possibly inherited) field)
  // this way, we correctly detect "inheritance aliasing"
  // where the same field is accessed from pointers of a type and a subtype
  llist<DefNode *> *&l = fieldDefs(fieldDecl);
  l = cons(new DefNode(assignment, nextindex++), l);
  if (debug_defs) {
    cout << "fieldDef < " << fieldDecl->container()->asType()->decl()->fullName() << ", ";
    cout << fieldDecl->name() << " > at "
	       << assignment->position().asString() << ":\n";
    assignment->print(cout, 4);
    cout << '\n';
  }
}  

void Defs::addArrayDef(TreeNode *assignment, TypeNode *t)
{
  assert(t->isArrayType());
  llist<DefNode *> *&l = arrayDefs(t); 
  l = cons(new DefNode(assignment, nextindex++), l);

  if (debug_defs) {
    cout << "arrayDef at " << assignment->position().asString() << ":\n";
    assignment->print(cout, 4);
    cout << '\n';
  }
}

/* Note (in this) that the variable specified by d is modified at t. */
void Defs::addVarDef(TreeNode *t, Decl *d)
{
  assert(d == fakeThisDecl || !d->type()->isImmutable()); // immutables use addImmutableVarDef
  llist<DefNode *> *&l = varDefs(d);
  l = cons(new DefNode(t, nextindex++), l);
  if (debug_defs) {
    cout << "varDef at " << t->position().asString() << ":\n";
    t->print(cout, 4);
    cout << '\n';
  }
}

/* Note (in this) that the given field of the given immutable is modified at t. 
   This also constitutes a modification of the overall immutable value */
void Defs::addIIFDef(TreeNode *t, TreeNode *immutableVar, const string& field) {
  assert(isImmutableVar(immutableVar));

  Decl *objectDecl = getImmutableVarDecl(immutableVar);
  llist<DefNode *> *&l = IIFDefs(objectDecl, field);
  l = cons(new DefNode(t, nextindex++), l);
  if (debug_defs) {
    cout << "immutable instance fieldDef < " << *objectDecl->name() << ", " << field << " > at "
	 << t->position().asString() << ":\n";
    t->print(cout, 4);
    cout << '\n';
  }

  // a def of an immutable field is also a def for the immutable variable
  addImmutableVarDef(t, immutableVar, false); // (but not the other fields)
}  

/* Note (in this) that the overall value of the given immutable is modified at t. 
   This usually also constitutes a modification of each of the fields of the immutable value */
void Defs::addImmutableVarDef(TreeNode *t, TreeNode *immutableVar, bool deffields) {
  // a def of an immutable var is also a def for all its instance fields
  assert(isImmutableVar(immutableVar));

  Decl *objectDecl = getImmutableVarDecl(immutableVar);
  llist<DefNode *> *&l = varDefs(objectDecl);
  l = cons(new DefNode(t, nextindex++), l);
  if (debug_defs) {
    cout << "immutable varDef < " << *objectDecl->name() << " > at " << t->position().asString() << ":\n";
    t->print(cout, 4);
    cout << '\n';
  }

  if (deffields) {
    for (llist <string>* fields = immutableIFields(getImmutableVarType(immutableVar)); 
          fields; fields = fields->tail()) {
       addIIFDef(t, immutableVar, fields->front());
    }
  }
}

void Defs::assignment(TreeNode *t)
{
  TreeNode *lhs = t->child(0);
  
  if (lhs->isArrayAccessNode()) 
    addArrayDef(t, lhs->array()->type());
  else if (isStaticFAN(lhs))
    addTypeFieldDef(lhs->simpName()->decl(), t);
  else if (isIIFAN(lhs)) 
    addIIFDef(t, lhs->object(), getIIFANFieldID(lhs));
  else if (isOFAN(lhs))
    addTypeFieldDef(lhs->simpName()->decl(), t);
  else if (isImmutableVar(lhs))
    addImmutableVarDef(t, lhs);
  else if (isObjectNode(lhs)) {
    assert(isNameNode(lhs->child(0)) && lhs->child(0)->decl() != NULL);
    addVarDef(t, lhs->child(0)->decl());
  }
  else if (isThisNode(lhs))
    addVarDef(t, fakeThisDecl); 
  else {
    cerr << "Unknown type of assignment (!):\n";
    t->print(cerr, 4);
    cerr << '\n';
    Error() << "Defs analysis can't handle unknown type of assignment." << endl;
    fatal_error("");
  }
}

//---------------------------------------------------------------------------
// Defs-related methods in other classes
//---------------------------------------------------------------------------

Defs *TreeNode::defs()
{
  undefined("defs");
  return 0;
}

Defs *ForEachStmtNode::defs()
{
  return _defs;
}

void TreeNode::findDefs(Defs *d)
{
  foriter (p, allChildren(), ChildIter)
    (*p)->findDefs(d);
}

void PragmaNode::findDefs(Defs *d)
{
  if (!isPragma(Pragma::noDefs))
    TreeNode::findDefs(d);
}

void VarDeclNode::findDefs(Defs *d)
{
  if (Defs::isImmutableVar(simpName())) d->addImmutableVarDef(this, simpName());
  else d->addVarDef(this, decl());

  TreeNode::findDefs(d);
}

void ForEachPairNode::findDefs(Defs *d)
{
  if (Defs::isImmutableVar(simpName())) d->addImmutableVarDef(this, simpName());
  else d->addVarDef(this, simpName()->decl());

  TreeNode::findDefs(d);
}

void ParameterNode::findDefs(Defs *d)
{
  if (Defs::isImmutableVar(simpName())) d->addImmutableVarDef(this, simpName());
  else d->addVarDef(this, simpName()->decl());

  TreeNode::findDefs(d);
}

void AssignNode::findDefs(Defs *d)	
{					
  d->assignment(this);			

  TreeNode::findDefs(d);
}

/* Do findDefs() in all children.  Set d->unknownMethods if
   the method is not known to be side effect free. */
void MethodCallNode::findDefs(Defs *d)
{

  TreeNode::findDefs(d);

  if (isSideEffectFree()) return;

  if (debug_defs) {
    cout << "`unknown' method at " << position().asString() << ":\n";
    print(cout, 4);
    cout << "\n";
  }

  d->methodCalls = cons((TreeNode *)this, d->methodCalls);
  d->unknownMethods = true;
}

void FieldAccessNode::findDefs(Defs *d)	
{					
  if (!isIIFAN(this) && 
      isFieldDeclNode(simpName()->decl()->source())) { // aliasable object field reference
    d->aliasableFields(simpName()->decl()) = true;
    }

  TreeNode::findDefs(d);
}

void ArrayAccessNode::findDefs(Defs *d)	
{					
  // aliasable array element reference
  d->aliasableArrays(array()->type()) = true;

  TreeNode::findDefs(d);
}


//---------------------------------------------------------------------------
// helpers for def analysis on immutables
// IIFAN = "Immutable Instance Field Access Node"
//---------------------------------------------------------------------------

bool Defs::isImmutableVar(TreeNode *t) {
  // return true if t is an immutable variable
  return ( ((isObjectNode(t) || isNameNode(t)) && t->decl()->type()->isImmutable())
         || (isThisNode(t) && t->type()->isImmutable()) );
  }

Decl *Defs::getImmutableVarDecl(TreeNode *t) {
  // get the decl node corresponding to this immutable variable
  assert(isImmutableVar(t));
  if (isThisNode(t)) return fakeThisDecl;
  else return t->decl();
  }

TypeNode *Defs::getImmutableVarType(TreeNode *t) {
  assert(isImmutableVar(t));
  if (isNameNode(t)) return t->decl()->type(); // NameNodes don't directly have correct type
  else return t->type();
  }

string Defs::getIIFANFieldID(TreeNode *iifan) {
  // return the field name being accessed by this IIFAN
  assert(isIIFAN(iifan));
  return (*iifan->simpName()->ident());
  }

Decl *Defs::getIIFANObjectDecl(TreeNode *iifan) {
  // return the decl for the immutable object var being accessed in this IIFAN
  assert(isIIFAN(iifan));
  return (getImmutableVarDecl(iifan->object()));
  }

llist<string>* Defs::immutableIFields(TypeNode *t) {
  static map_type_to_fieldlist _immutableIFields; // memoize
  assert(t->isImmutable());
  // cache the answers
  llist <string>*& l = _immutableIFields[type2xtype(t)];
  if (l == NULL) {
    ClassDeclNode *cdn = dynamic_cast<ClassDeclNode*>(t->decl()->source());
    TreeListNode *members = cdn->members();
    for (int i=0; i < members->arity(); i++) {
      if (isFieldDeclNode(members->child(i)) && 
	      !(members->child(i)->flags() & Common::Static)) 
	      l = cons( *members->child(i)->simpName()->ident(), l);
    }
  }
  return l;
}
//---------------------------------------------------------------------------
// helpers for typeAD
//---------------------------------------------------------------------------
//  provide an efficient way to walk down the inheritance hierarchy
// this may be useful to make available elsewhere, but we need to make sure it 
// never gets built until the class hierarchy is complete
static llist<TypeNode *>* getSubTypes(TypeNode *t) {
  static map<xtype, llist<TypeNode *>*> _SubTypeMap; // memoize
  static bool _SubTypeMapInitialized = false;
  if (!_SubTypeMapInitialized) {
    // build a list of all class types (including pseudo-template instantiations)
    llist<TreeNode*>* typelist = templateEnv.allInstances();
    foreach (f, llist<CompileUnitNode *>, *allFiles)
      foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
        if (isInterfaceDeclNode((*type)) || isClassDeclNode((*type))) // ignore templates
          typelist = cons(*type, typelist);
    
    // process the type list, integrating info into our map
    while (typelist) {
      ClassDecl *cd = dynamic_cast<ClassDecl *>(typelist->front()->simpName()->decl());
      assert(cd != NULL);
      if (cd != ObjectDecl) {
        if (cd->superClass()) { // has a super class
          llist<TypeNode *>* &l = _SubTypeMap[type2xtype(cd->superClass()->asType())];
          l = cons(cd->asType(), l);
          }
        if (cd->interfaces()) { // implements some interfaces
          foreach(idecl, llist<Decl *>, *cd->interfaces()) {
            llist<TypeNode *>* &l = _SubTypeMap[type2xtype((*idecl)->asType())];
            l = cons(cd->asType(), l);
            }
          }
        }
      typelist = typelist->free();
      } 
    _SubTypeMapInitialized = true;
    }
  return _SubTypeMap[type2xtype(t)];
  }

// crawl up the inheritance hierarchy adding superclasses and everything implemented and superinterfaces
static llist<TypeNode *>* crawlup(TypeNode *t) {
  llist<TypeNode *>* l = NULL;
  // classes
  ClassDecl *d = dynamic_cast<ClassDecl *>(t->decl());
  assert(d != NULL);
  if (d != ObjectDecl && d->superClass()) {
    l = cons(d->superClass()->asType(), l);
    l = extend(l, crawlup(d->superClass()->asType()));
    }
  
  // interfaces
  foreach(idecl, llist<Decl *>, *d->interfaces()) {
    TypeNode *itype = (*idecl)->asType();
    l = cons(itype, l);
    l = extend(l, crawlup(itype));
    }
  return l;
  }

// crawl down the extends and implements edges from this type
static llist<TypeNode *>* crawldown(TypeNode *t) {
  llist<TypeNode *>* l = NULL;
  foreach(subtype, llist<TypeNode *>, *getSubTypes(t)) {
    l = cons((*subtype), l);
    l = extend(l, crawldown((*subtype)));
    }
  return l;
  }

/* destructively remove duplicates from a list */
template <class T> llist<T> * removeDuplicates(llist<T> *l) {
  if (l == NULL) return NULL;
  set<T> s;
  foreach(e, TYPENAME llist<T>, *l) {
    s.insert(*e);
    }
  free_all(l);
  l = NULL;
  foreach_const(e, TYPENAME set<T>, s) {
    l = cons((T) *e, l);
    }
  return l;
  }

llist<TypeNode *>* emptyList = (llist<TypeNode *>*)-1;

llist<TypeNode *>* Defs::typeAD(TypeNode *t) {
  static map_type_to_typelist _typeAD;  // memoize
  if (!t->isReference()) return NULL;
  llist<TypeNode *>* &l = _typeAD[type2xtype(t)];
  if (l == emptyList) return NULL; // cached as empty
  if (l == NULL) {
    l = extend(l, crawlup(t)); // crawl up the interface/inheritance hierarchy
    l = extend(l, crawldown(t)); // crawl down the interface/inheritance hierarchy

    l = removeDuplicates(l); // we may reach the same interfaces more than once

    if (l == NULL) l = emptyList; // mark it as empty so we don't search again
    if (debug_defs) {
      cout << "typeAD(" << t->decl()->fullName() << ") = ";
      foreach(type, llist<TypeNode *>, *l) 
        cout << (*type)->decl()->fullName() << "  "; 
      cout << endl;
      }
    }
  return l;
  }

//---------------------------------------------------------------------------
llist<TypeNode *>* Defs::aliasableArrayTypes(TypeNode *t) {
  // returns the list of array xtypes whose top-level elements 
  // may be aliased with the top-level elements of this array (not including this type)
  // does not include cross-dimensionality aliasing of grids (that's handled in type2xtype)
  // user should not alter this list

  if (t->isTitaniumArrayType()) return NULL; // no inheritance aliasing below a grid
  else if (t->isJavaArrayType()) {
    static map_type_to_typelist _aliasableJavaArrayTypes; // memoize to save time & memory
    llist<TypeNode *>*& retval = _aliasableJavaArrayTypes[type2xtype(t)];
    if (!retval) {
      TypeNode *elementType = t->elementType();
      llist<TypeNode *>* elemAliases = aliasableArrayTypes(elementType);
      while (elemAliases) {
        // maintain the element modifiers since we currently include those when disambiguating potential array aliases
        retval = cons(static_cast<TypeNode*>(new JavaArrayTypeNode(elemAliases->front()->withModifiers(elementType->modifiers()))), retval);
        elemAliases = elemAliases->tail();
        }
      retval = extend(retval, typeAD(t)); // get inheritance aliases at this level
      }
    return retval;
    }
  else if (t->isReference()) { 
    return typeAD(t);
    }
  else return NULL; // non-reference type, no inheritance types
  }
//---------------------------------------------------------------------------