/*
   Alias Analysis:

   See doc/alias-analysis.txt for a high-level description of the
   algorithm.

   We associate with each allocation expression or String literal an
   abstract value unique within the method. We associate with each local
   variable a list of POSSIBLE abstract values for that variable. Each
   abstract value is in turn associated with a record (ValueInfo) of
   things associated with that value: if it is an Object, the possible
   values of its fields; if it's an array, the possible values of its
   elements. For example, in the following:
  
   1. a = new int[];
   2. b = a;
   3. a[i] = c;
   4. c = m[j];
   5. a = obj.outSideField;
  
   After (1), 'a' would be mapped to a list consisting only of an
   anonymous abstract value with its arrayValues set to the a list
   containing the null abstract value, meaning a[???] has no possible
   values but 'null'. After (2), b would be mapped to a copy of the values
   of a. After (3), the arrayValues field associated with every value's
   record in the values-list of a (in this case only the anonymous value
   created by 'new') would have the values-list of c appended to its
   values-list. After (4), the values-list of c will be a concatenation of
   the arrayValues of each value in the values-list of m. After (5), a's
   values-list will be a singleton list consisting of nothing but 'the
   external abstract value'.

   Values-lists are represented by Bitsets. The only types of possible
   known values are: allocations, String literals, null, 'this', and an
   external value representing arbitrary values from the outside.
  
   An AliasInfo gives complete information about what is known about any
   variables at a particular point in the program. It has a mapping of
   local variable declarations to lists of possible values (Bitsets), and
   a mapping of abstract values (ints) to ValueInfos. Only method calls
   and assignments affect AliasInfos.
  
   Some examples: 
  
   1. a = b; The Bitset of a becomes a copy of the Bitset of b.
  
   2. a = b[i]; The Bitset of a becomes a concatenation of the arrayValues
   of every possible value of b.
  
   3. a[i] = b; The arrayValues of EVERY value record in the Bitset of a
   is unioned with the Bitset of b.
  
   4. a[i] = b[i]; The arrayValues of EVERY value in the Bitset of a is
   unioned with the arrayValues of every Value in the Bitset of b.
   
   5. a.x = b[i]; The Bitset corresponding to the decl of x in every value
   in the Bitset of a becomes a copy of the Bitset of b[i].
  
   7. xxx = some.method(v1, ..., vn); xxx's appropriate Bitset gets
   unioned/replaced with a list of every possible value of v1, ..., vn,
   every possible sub-value thereof, AND the EXTERNALVALUE. Every
   sub-value of v1, ..., vn gets joined with every other sub-value of v1,
   ..., vn, and the EXTERNALVALUE. Furthermore, we have to go erase
   everything we know about any object's fields in our own method.
  
   (The EXTERNALVALUE is used to denote that the variable may be an
   external value.)
  
   Note that, currently, any list of values is only a POSSIBLE list. Just
   because a certain variable has a singleton list doesn't mean it
   definitely has that value. This comes mainly from the field/arrayaccess
   assignment of multiply-valued local variables.

   One day we might find something more efficient than Bitsets.

   */

   

#include "AST.h"
#include "cfg.h"
#include "code-aa.h"
#include "compiler.h"
#include "MethodSet.h"

extern bool alias_anal;
extern bool aaDebugOn;
extern bool aaSuperDebugOn;

// Used during setup of each method to use the TraverseBblocks(...)
// procedures.. yuck
static AliasInfos *incomingAliasInfos;

// the current method being analyzed.
static MethodStatics *currentMethodStatics;
// static Bitset *currentSpecialValues;

// don't use this, it's not what you think it is. it's only for debugging
static AliasInfos *methodAliases;



//////////////////////////////// ANALYSIS UTILS //////////////////////////

bool isInterestingNode(TreeNode *t) {
  return (isMethodCallNode(t) || isAssignNode(t) || isAllocateNode(t));
}


void leak(AliasInfos *ai, int value)
{
  assert(isInMap(value, ai->valueToValueInfoMap));
  ai->leaksSet->set(value);
  currentMethodStatics->leaksValues->set(value);
}


void leak(AliasInfos *ai, Bitset *values)
{
  ai->leaksSet->un(values);
  currentMethodStatics->leaksValues->un(values);  
}





/* A big nasty print. */
/*
void printAllAliasesBblock(Bblock *b) {
  cout << "Full results on bblock #" << b->number << endl;      
  ListIterator<CfgNode *> cfgIt = b->cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();
    if (isHandled(t)) {
      t->print(cout); cout << endl;
      cout << "------------" << endl;
      ListIterator<CfgNode *> cfgIt2 = b->cfgIter();    
      for (; !cfgIt2.isDone(); cfgIt2.next()) {
	CfgNode *cfg2 = *cfgIt2;
	TreeNode *t2 = cfg2->astNode();
	if (isHandled(t2)) {
	  t2->print(cout); cout << endl;
	  cout << methodAliases->checkAliases(t, t2) << endl;
	  cout << "--" << endl;
	}
      }
    }
    cout << "============" << endl;
  }
}
*/


// Sets up the map with the local parameters. The values are numbered as
// follows: system values go up to AA_FIRSTVALUE - 1, parameters (if any)
// start at AA_FIRSTVALUE, and then local values. 
AliasInfos *createInitialAliasInfos(TreeNode *t, int size)
{
  AliasInfos *ai = new AliasInfos(size, t);

  TreeListNode *params = t->params();
  for (int i = 0; i < params->arity(); i++) {
    if (isAliasable(params->child(i)->dtype())) {
      int slot = AA_FIRSTVALUE + i;            

      // here, to simplify our calculations (so that they fit in the
      // mechanisms), I'm going to make argument values have themselves as
      // subvalues, and make their types theNullType instead of
      // params->child(i)->dtype(). Some day we can make it more precise
      // by doing more work.
      ai->setupValueInfo(slot, theNullType);
      Bitset *b = new Bitset(size);
      b->set(slot);
      ai->declToBitsetMap[params->child(i)->simpName()->decl()] = b;
      ai->valueToValueInfoMap[slot]->arrayValues = copyBitset(b);
      ai->valueToValueInfoMap[slot]->unknownFieldValue = slot;
    }
  }
  return ai;
}


/* Merge the given bblock's aliases into the global one. */
void mergeAliasesBblock(Bblock *b)
{
  methodAliases->merge(b->aliasesOut());
}

static Bitset *makeComparable(AliasInfos *ai, Bitset *b)
{
  if (!b->disjoint(currentMethodStatics->specialValues))
    b->set(AA_EXTERNALVALUE);
  if (b->test(AA_EXTERNALVALUE))
    b->un(ai->leaksSet);
  return b;
}


/* Lame way to make sure all nodes that may have a field/array access
   (e.g. ObjectNodes, ThisNode) have comparable values sets after the
   analysis. */
static void setupValueForObjects(AliasInfos *ai, TreeNode *t)
{
  if ((isObjectNode(t) || isThisNode(t)) && isAliasable(t->type())) {
    Bitset *b = copyBitset(t->getValues(ai));
    t->setAbstractValues(makeComparable(ai, b));
    if (aaDebugOn || aaSuperDebugOn) {
      cout << "Object "; t->pseudoprint(cout, 0);
      cout << " has values "; printBitset(t->getAbstractValues(), cout);
      cout << endl;
    }
  }
}



void clearAliasesIn(Bblock *b)
{
  delete b->aliasesIn();
  b->setAliasesIn(NULL);
}


void printFinalStats(TreeNode *t)
{
  cout << "*********************************" << endl;
  cout << "Final statistics for method ";
  cout << *t->simpName()->ident() <<  " in ";
  t->decl()->container()->print(cout);
  cout << endl << endl;
  cout << "Status = " << currentMethodStatics->status << endl;
  cout << "Is sideEffectFree? " << currentMethodStatics->isSideEffectFree();
  cout << endl;
  cout << "Modifies the values: ";
  printBitset(currentMethodStatics->modifiesValues, cout);
  cout << endl;
  cout << "Leaks the values: ";
  printBitset(currentMethodStatics->leaksValues, cout);
  cout << endl;    
  cout << "Returns the values: ";
  printBitset(currentMethodStatics->returnsValues, cout);
  cout << endl;    
  
  methodAliases = new AliasInfos(t->getBblockRoot()->aliasesOut()->size,
				 currentMethodStatics->method);
  TraverseBblocks(t->getBblockRoot(), mergeAliasesBblock);
  
  cout << "APPROXIMATE ALIASINFOS:" << endl;
  
  methodAliases->println(cout);
  cout << "*********************************" << endl;
  //      methodAliases->printAliases(cout);
  //      cout << endl;
  
    //    TraverseBblocks(t->getBblockRoot(), printAllAliasesBblock);    
  methodAliases = NULL;
}



//////////////////////////////// ANALYSIS CODE //////////////////////////



// Analyse one method. Don't call directly.
void analyzeMethod(TreeNode *t)
{
  
  if (aaDebugOn || aaSuperDebugOn) {
    cout << "Doing analysis on "; t->simpName()->pseudoprint(cout, 0); cout << endl;
  }

  assert(t->getBblockRoot() != NULL);
  assert(t->methodStatics() != NULL);
  
  currentMethodStatics = t->methodStatics();
  currentMethodStatics->status = 1;  
  incomingAliasInfos = createInitialAliasInfos(t, t->methodStatics()->numValues());

  if (t->getBblockRoot()->aliasesIn() != NULL)
    TraverseBblocks(t->getBblockRoot(), clearAliasesIn);

  // do the actual alias analysis
  TraverseBblocksIter(t->getBblockRoot(), setupAliasesBblock);

  TraverseBblocks(t->getBblockRoot(), finalPassAliasesBblock);

  if (aaDebugOn || aaSuperDebugOn)
    printFinalStats(t);    
}



    
// alias analysis on one bblock
bool setupAliasesBblock(Bblock *b)
{

  AliasInfos *nextAliasesIn =
    new AliasInfos(currentMethodStatics->numValues(), currentMethodStatics->method);

  // take in the method arguments if it's the root block
  if (incomingAliasInfos != NULL) {
    nextAliasesIn->merge(incomingAliasInfos);
    incomingAliasInfos = NULL;
  }

  // merge with the incoming ones..
  ListIterator<Bblock *> bbIt = b->predIter();
  for (; !bbIt.isDone(); bbIt.next()) {
    Bblock *bb = *bbIt;
    if (bb->aliasesIn() != NULL) {
      nextAliasesIn->merge(bb->aliasesOut());
    }
  }

  // check if it's the same as last time, if so just quit
  if (b->aliasesIn() != NULL && b->aliasesIn()->equivalent(nextAliasesIn))
    return false;

  // save it for next check
  b->setAliasesIn(nextAliasesIn);
  
  // keep a running total to calculate the out-set
  AliasInfos *aliasesOut = new AliasInfos(nextAliasesIn->size, currentMethodStatics->method);
  aliasesOut->merge(b->aliasesIn());
  
  ListIterator<CfgNode *> cfgIt = b->cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();

    if (aaSuperDebugOn && isInterestingNode(t)) {
      cout << "----------------"; t->pseudoprint(cout, 0); cout << endl;
    }

    aliasesOut->process(t);

    if (aaSuperDebugOn && isInterestingNode(t)) {
      cout << "Current aliases info: " << endl;
      aliasesOut->println(cout);
      cout << "Current method statics: " << endl;
      currentMethodStatics->println(cout);
    }    
  }

  b->setAliasesOut(aliasesOut);
  return true;
}



// Leave residual info for later stages. duplicates above to get
// intro-bblock info. 
void finalPassAliasesBblock(Bblock *b)
{  
  AliasInfos *aliasesOut = new AliasInfos(b->aliasesIn()->size, currentMethodStatics->method);
  aliasesOut->merge(b->aliasesIn());
  
  ListIterator<CfgNode *> cfgIt = b->cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();

    setupValueForObjects(aliasesOut, t);
    aliasesOut->process(t);
  }

  // very subtle: doing it again MAY change something only if we're
  // pending our OWN result, but it's OK in that case we'll be redoing
  // this whole method yet again anyway so none of this stuff matters..
  // if (currentMethodStatics->status != 3)
  //    assert(b->aliasesOut()->equivalent(aliasesOut));
}













// accumulates into bs this value and every sub-value (recursive) that any
// sub anything can have. 
void accumulateValues(int value, Bitset *bs, AliasInfos *ai)
{
  
  if (bs->test(value))
    return;

  bs->set(value);
  
  assert(isInMap(value, ai->valueToValueInfoMap));
  ValueInfo *vi = ai->valueToValueInfoMap[value];

  bool isArray = vi->valueType->isArrayType() || vi->valueType->isNullType();
  bool isObj = !vi->valueType->isArrayType() || vi->valueType->isNullType();

  if (isArray) {
    for (int i = 0; i < vi->arrayValues->size(); i++) {
      if (vi->arrayValues->test(i) && !bs->test(i))
	accumulateValues(i, bs, ai);
    }
  }

  if (isObj) {
    for (DeclToBitsetMap::const_iterator v = vi->fieldToBitsetMap.begin();
	 v != vi->fieldToBitsetMap.end();
	 v++) {
      Bitset *fieldBitset = (*v).second;
      for (int i = 0; i < fieldBitset->size(); i++) {
	if (fieldBitset->test(i) && !bs->test(i))
	  accumulateValues(i, bs, ai);
      }
    }

    accumulateValues(vi->unknownFieldValue, bs, ai);
  }
  
}


  



// like the above, but only those values possibly returned/leaked/whatever
// as given in rv
Bitset *getMatchedFormalSubvalues(TreeNode *t, AliasInfos *ai, Bitset *rv)
{

  TreeListNode *args = t->args();
  Bitset *accumulator = new Bitset(ai->size);

  for (int i = 0; i < args->arity(); i++) {    
    if (rv->test(i + AA_FIRSTVALUE)) {
      TreeNode *nextParam = args->child(i);      
      Bitset *values = nextParam->getValues(ai);
      for (int j = 0; j < values->size(); j++) {
	if (values->test(j))
	  accumulateValues(j, accumulator, ai);
      }
    }
  }

  return accumulator;
}


// get all values and subvalues of the arguments, and of the object too if
// objectValues is not NULL
Bitset *getMatchedObjectFormalSubvalues(TreeNode *t, AliasInfos *ai,
					Bitset *rv, Bitset *objectValues)
{

  //TreeListNode *args = t->args();
  Bitset *accumulator = new Bitset(ai->size);

  // if it's a.method(...), and a is an object (and not a type), then we
  // gotta get all values and subvalues of a.
  if (objectValues != NULL && rv->test(AA_THISVALUE)) {
    for (int i = 0; i < objectValues->size(); i++) {
      if (objectValues->test(i))
	accumulateValues(i, accumulator, ai);
    }
  }

  accumulator->un(getMatchedFormalSubvalues(t, ai, rv));

  return accumulator;
}


// clobbers all subvalues of the given value
void clobberSubvalues(int value, Bitset *incomingValues,
		      Bitset *casualty, AliasInfos *ai)
{
  if (casualty->test(value))
    return;

  casualty->set(value);
  
  ValueInfo *vi = ai->valueToValueInfoMap[value];

  for (int i = 0; i < vi->arrayValues->size(); i++) {
    if (vi->arrayValues->test(i) && !casualty->test(i))
      clobberSubvalues(i, incomingValues, casualty, ai);
  }

  // no longer know anything about any fields
  vi->fieldToBitsetMap.clear();

  // we do here a more careful union. We only pick out the ones that could
  // possibly be assigned to my dtype if i'm an array
  if (vi->valueType->isArrayType()) {
    TypeNode *eltType = vi->valueType->elementType();
    for (int i = 0; i < incomingValues->size(); i++) {
      if (incomingValues->test(i) &&
	  eltType->isCastableFrom(ai->valueToValueInfoMap[i]->valueType))
	vi->arrayValues->set(i);
    }
  }
}


// clobber all subvalues with those given.
void clobberMatchedFormalSubvalues(TreeNode *t, Bitset *subValues,
				   Bitset *casualty,AliasInfos *ai,
				   Bitset *rv)
{

  for (int i = 0; i < t->args()->arity(); i++) {
    if (rv->test(i + AA_FIRSTVALUE)) {
      Bitset *values = t->args()->child(i)->getValues(ai);
      for (int j = 0; j < values->size(); j++) {
	if (values->test(j))
	  clobberSubvalues(j, subValues, casualty, ai);
      }
    }
  }
}


// clobber formal values and subvalues of procedure call t (if they're in
// rv) with the specified subValues, and also for the objectValues if it's
// not NULL. returns casualty
Bitset *clobberMatchedObjectFormalSubvalues(TreeNode *t, Bitset *subValues,
					    AliasInfos *ai, Bitset *rv,
					    Bitset *objectValues)
{
  Bitset *casualty = new Bitset(ai->size);

  // if it's a.method(...), and a is an object (and not a type), then we
  // gotta clobber subvalues of a.
  if (objectValues != NULL && rv->test(AA_THISVALUE)) {
    for (int i = 0; i < objectValues->size(); i++) {
      if (objectValues->test(i))
	clobberSubvalues(i, subValues, casualty, ai);
    }
  }

  clobberMatchedFormalSubvalues(t, subValues, casualty, ai, rv);
  
  return casualty;
}


void collectValues(AliasInfos *ai, Bitset *casualty, Bitset *values);

void collectValueAndSubvalues(int value, AliasInfos *ai, Bitset *casualty)
{

  casualty->set(value);
  ValueInfo *vi = ai->valueToValueInfoMap[value];
  collectValues(ai, casualty, vi->arrayValues);
  for (DeclToBitsetMap::const_iterator v = vi->fieldToBitsetMap.begin();
       v != vi->fieldToBitsetMap.end();
       v++)
    {
      Bitset *bs = (*v).second;      
      collectValues(ai, casualty, bs);
    }
}

  
void collectValues(AliasInfos *ai, Bitset *casualty, Bitset *values)
{
  for (int i = 0; i < values->size(); i++) {
    if (!casualty->test(i) && values->test(i))
      collectValueAndSubvalues(i, ai, casualty);
  }
}
    

bool containsDirty(Bitset *b, AliasInfos *ai)
{
  if (!b->disjoint(ai->leaksSet))
    return true;
  if (b->test(AA_THISVALUE))
    return true;
  for (int i = 0; i < currentMethodStatics->method->params()->arity(); i++)
    if (b->test(i + AA_FIRSTVALUE))
      return true;
  return false;
}
  

// values should be NULL if it's not an aliasable type on the right side.
void checkStaticsObjectAccessAssignment(AliasInfos *ai,	Bitset *objectValues, Bitset *values)
{

  currentMethodStatics->modifiesValues->un(objectValues);
  
  // if you get asigned to a dirty object's field, you get leaked!
  if (values != NULL && containsDirty(objectValues, ai)) {
    Bitset *casualty = new Bitset(ai->size);
    collectValues(ai, casualty, values);
    leak(ai, casualty);
  }
      
}


MethodStatics *lookupStatics(TreeNode *methodCall, TreeNode *md);

llist<MethodWaiter *> *filterWaiters(TreeNode *m, llist<MethodWaiter*> *callBackList)
{
  if (callBackList == NULL)
    return callBackList;
  if (callBackList->front()->waiter != m) {
    callBackList->tail() = filterWaiters(m, callBackList->tail());
    return callBackList;
  }
  else
    return filterWaiters(m, callBackList->free());
}


// will look up and set the methodStatics if not available
MethodStatics *getMethodDeclStatics(TreeNode *methodDecl)
{
  if (methodDecl->methodStatics() == NULL) {
    MethodStatics *ms = lookupStatics(methodDecl);
    if (ms == NULL)
      ms = fullMethodStatics(methodDecl);
    methodDecl->setMethodStatics(ms);
    if (isKnownSideEffectFree(methodDecl)) {
      MethodStatics *ms = methodDecl->methodStatics();
      ms->modifiesValues = new Bitset(methodDecl->methodStatics()->numValues());
      ms->leaksValues = ms->modifiesValues;
    }
  }
  
  // if it's not done, i'm pending a result (this one, in particular)
  if (methodDecl->methodStatics()->status != 2) {
    currentMethodStatics->status = 3;
    MethodWaiter *me = new MethodWaiter;
    me->waiter = currentMethodStatics->method;
    me->ms = methodDecl->methodStatics()->emptyCopy();
    methodDecl->methodStatics()->callBackList =    
      cons(me, filterWaiters(me->waiter, methodDecl->methodStatics()->callBackList));
  }

  return methodDecl->methodStatics();
}


void mergeOverriders(MethodStatics *ms, Decl *d)
{
  MethodSet *overriders = d->overriders();
  for (MethodSet::const_iterator method = overriders->begin();
       method != overriders->end();
       method++) {
    ms->merge(getMethodDeclStatics((*method)->source()));
    mergeOverriders(ms, *method);
  }
}
  

MethodStatics *getMethodCallStatics(TreeNode *methodCall)
{
  TreeNode *methodDecl = methodCall->decl()->source();
  MethodStatics *ms = getMethodDeclStatics(methodDecl)->emptyCopy();
  // only method calls may be overridden
  if (isMethodCallNode(methodCall)) {
    mergeOverriders(ms, methodCall->decl());
  }
  return ms;
}


Bitset *getObjectValues(AliasInfos *ai, TreeNode *t)
{
  // the value of 'this' inside the method
  if (isMethodCallNode(t) && isOFAN(t->method()))
    return t->method()->object()->getValues(ai);
  else if (isAllocateNode(t))
    return t->getValues(ai);
  else if (isConstructorCallNode(t))
    return currentMethodStatics->myThisValueBitset();
  
  return NULL;
}  


// update the various method statics due to "procedure"CallNode t. 
void checkStaticsProcedureCall(AliasInfos *ai, TreeNode *t)
{
  MethodStatics *ms = getMethodCallStatics(t);
  Bitset *objectValues = getObjectValues(ai, t);
  
  // since any value that clobbers another argument (or 'this') would be
  // considered leaked, we can restrict to leaked values...
  Bitset *Restrict = ms->leaksValues;
  Bitset *argsLeaked = getMatchedObjectFormalSubvalues(t, ai, Restrict, objectValues);

  if (Restrict->test(AA_EXTERNALVALUE))
    argsLeaked->un(ai->leaksSet);

  // clobbers the modified arguments with the leaked arguments. technical
  // note: it is enough just to always clobber them with only the external
  // value, since we make the leaked values dirty anyway, but this is more
  // precise in the case where they don't clobber external values
  Bitset *modified = clobberMatchedObjectFormalSubvalues(t,
							 argsLeaked,
							 ai,
							 ms->modifiesValues,
							 objectValues);

  // leave residual info for use-def
  t->setModifiesValues(makeComparable(ai, copyBitset(modified)));

  if (aaSuperDebugOn) {
    cout << "He modifies values: "; printBitset(ms->modifiesValues, cout); cout << endl;
    cout << "...that's to us: "; printBitset(modified, cout); cout << endl;    
    cout << "Leaked (to us): "; printBitset(argsLeaked, cout); cout << endl;    
  }
    
  // if he modified ext, then also clobber the dirty values with the
  // leaked values -- but we can restrict to leaked+EXT instead of dirty
  // (see doc).
  if (ms->modifiesValues->test(AA_EXTERNALVALUE)) {
    for (int i = 0; i < ai->leaksSet->size(); i++) {
      if (ai->leaksSet->test(i))
	clobberSubvalues(i, argsLeaked, modified, ai);
    }
  }
  
  currentMethodStatics->modifiesValues->un(modified);

  // if they leaked it, we leaked it
  leak(ai, argsLeaked);
  if (isMethodCallNode(t) && isAliasable(t->type())) {
    if (!ms->returnsValues->disjoint(ms->leaksValues)) {
      ai->setupValueInfo(currentMethodStatics->ASTValueMap[t], t->type());
      leak(ai, currentMethodStatics->ASTValueMap[t]);
    }
  }
}


  

  













////////////////////////// ::getValues and ::handleAssignment ////////////////
// Be very careful about "aliasing" of the returned Bitset. 


// NOTE: a getValues on an AllocateNode does NOT clobbers its arguments.
// see comments for methodcallNode
Bitset *AllocateNode::getValues(AliasInfos *ai)
{
  int value = currentMethodStatics->ASTValueMap[this];
  ai->setupValueInfo(value, dtype());
  
  //  this never changes -- can be cached
  if (_abstractValues != NULL)
    return _abstractValues;
  else {    
    Bitset *temp = new Bitset(ai->size);
    temp->set(value);
    setAbstractValues(temp);
    return temp;
  }
}




Bitset *AllocateArrayNode::getValues(AliasInfos *ai)
{
  int value = currentMethodStatics->ASTValueMap[this];
  ai->setupValueInfo(value, type());

  // this never changes -- can be cached
  if (_abstractValues != NULL)
    return _abstractValues;

  Bitset *temp = new Bitset(ai->size);
  temp->set(value);

  setAbstractValues(temp);  
  return temp;
}


Bitset *StringLitNode::getValues(AliasInfos *ai)
{
  int value = currentMethodStatics->ASTValueMap[this];
  ai->setupValueInfo(value, type());

  //  this never changes -- can be cached
  if (_abstractValues != NULL)
    return _abstractValues;
  
  Bitset *temp = new Bitset(ai->size);
  temp->set(value);

  setAbstractValues(temp);  
  return temp;
}



Bitset *ArrayInitNode::getValues(AliasInfos *ai)
{
  int value = currentMethodStatics->ASTValueMap[this];
  ai->setupValueInfo(value, type());

  // this never changes -- can be cached
  if (_abstractValues != NULL)
    return _abstractValues;
  
  
  Bitset *temp = new Bitset(ai->size);
  temp->set(value);

  setAbstractValues(temp);
  return temp;
}


// return remote values too.
Bitset *IBroadcastNode::getValues(AliasInfos *ai)
{
  Bitset *values = expr()->getValues(ai);
  return values;
}


Bitset *CastNode::getValues(AliasInfos *ai)
{
  Bitset *values = opnd0()->getValues(ai);
  return values;
}


Bitset *ObjectNode::getValues(AliasInfos *ai)
{
  // local variables MAY NOT have been initialized in Titanium. it
  // doesn't check. 
  Bitset *result;
  Decl *decl = name()->decl();
  if (isInMap(decl, ai->declToBitsetMap))
    result = copyBitset(ai->declToBitsetMap[decl]); 
  else {
    result = currentMethodStatics->myNullValueBitset();
  }
  return result;
}


Bitset *ThisNode::getValues(AliasInfos *ai)
{
  return currentMethodStatics->myThisValueBitset();
}


Bitset *NullPntrNode::getValues(AliasInfos *ai)
{
  return currentMethodStatics->myNullValueBitset();
}

/* This is only needed because of templates producing weirdness on method
   parameter dtypes. */
Bitset *PrimitiveLitNode::getValues(AliasInfos *ai)
{
  return currentMethodStatics->myNullValueBitset();
}


Bitset *ObjectFieldAccessNode::getValues(AliasInfos *ai)
{

  if (decl()->isStatic())
    return currentMethodStatics->myExtValueBitset();
  
  // NOTE: we have to take care of the case of a chain of immutables.
  // a.i1...ik.b. Hold your horses.
  
  // get the possible values for the object
  Bitset *bs = object()->getValues(ai);
  Bitset *result = new Bitset(bs->size());
  // iterate over those possible values
  Decl *fieldDecl = simpName()->decl();
  for (int i = 0; i < bs->size(); i++) {
    if (bs->test(i)) {
      assert(isInMap(i, ai->valueToValueInfoMap));
      
      if (isInMap(fieldDecl, ai->valueToValueInfoMap[i]->fieldToBitsetMap))
	result->un(ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl]);
      else
	result->set(ai->valueToValueInfoMap[i]->unknownFieldValue);
    }
  }

  return result;
}



Bitset *TypeFieldAccessNode::getValues(AliasInfos *ai)
{
  return currentMethodStatics->myExtValueBitset();
}





// NOTE: a getValues on a MethodCallNode does NOT clobber its arguments.
// This is because this would see it 2 times in an assign method call
Bitset *MethodCallNode::getValues(AliasInfos *ai) {  

  MethodStatics *ms = decl()->source()->methodStatics();

  Bitset *objectValues = isOFAN(method()) ? method()->object()->getValues(ai) : NULL;
  Bitset *returnedValues = ms->returnsValues;

  Bitset *subValues = getMatchedObjectFormalSubvalues(this, ai, returnedValues, objectValues);

  if (aaSuperDebugOn) {
    cout << "He returns: "; printBitset (returnedValues, cout); cout << endl;    
    cout << "That's to us: "; printBitset (subValues, cout); cout << endl;
  }

  if (returnedValues->test(AA_EXTERNALVALUE)) {
    subValues->set(AA_EXTERNALVALUE);        
    subValues->un(ai->leaksSet);
  }
  
  // this sort of represents a possible value new'ed in the called method.
  // this is only for consistency and doesn't really mean anything.
  int value = currentMethodStatics->ASTValueMap[this];
  ai->setupValueInfo(value, type());
  subValues->set(value);
  
  // now filter out subValues that are unreasonable. 
  if (type()->kind() != Common::VoidKind) {
    for (int i = 0; i < subValues->size(); i++) {
      if (subValues->test(i) &&
	  !type()->isCastableFrom(ai->valueToValueInfoMap[i]->valueType))
	subValues->clear(i);
    }
  }

  return subValues;
}


Bitset *ArrayAccessNode::getValues(AliasInfos *ai)
{
  Bitset *objectBitset = ai->lookupDecl(array()->name()->decl());
  Bitset *temp = new Bitset(ai->size);
  
  for (int i = 0; i < objectBitset->size(); i++) {
    if (objectBitset->test(i)) {
      temp->un(ai->valueToValueInfoMap[i]->arrayValues);
    }
  }

  return temp;
}
  






bool ObjectNode::handleAssignment(AliasInfos *ai, Bitset* values)
{
  Decl *decl = name()->decl();
  ai->declToBitsetMap[decl] = copyBitset(values);
  return true;
}



bool ObjectFieldAccessNode::handleAssignment(AliasInfos *ai, Bitset* values)
{
  // NOTE: we have to take care of the case of a chain of immutables.
  // a.i1...ik.b. Hold your horses. I think the lowered AST is still
  // separating out chains into temporaries.

  if (decl()->isStatic()) {
    checkStaticsObjectAccessAssignment(ai, currentMethodStatics->myExtValueBitset(), values);
    return true;
  }

  Bitset *bs = object()->getValues(ai);


  // do the static info's checking. notice we get our own values BEFORE
  // assignment for the purposes of checking for this stuff..
  checkStaticsObjectAccessAssignment(ai, bs, values);
      
  
  // iterate over those possible values. if more than one, we need to
  // union instead of copy
  bool exactlyOne = false;
  int first = -1;
  
  Decl *fieldDecl = simpName()->decl();
  for (int i = 0; i < bs->size(); i++) {
    if (bs->test(i)) {
      assert(isInMap(i, ai->valueToValueInfoMap));
      if (first == -1) {
	first = i;
	exactlyOne = true;
      }
      else if (exactlyOne)
	exactlyOne = false;
      if (isInMap(fieldDecl, ai->valueToValueInfoMap[i]->fieldToBitsetMap))
	ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl]->un(values);
      else
	ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl] = copyBitset(values);
    }
  }
  if (exactlyOne && first != AA_NULLVALUE && first != AA_EXTERNALVALUE)
    ai->valueToValueInfoMap[first]->fieldToBitsetMap[fieldDecl] = copyBitset(values);
  
  return true;
}



bool TypeFieldAccessNode::handleAssignment(AliasInfos *ai, Bitset* values)
{
  checkStaticsObjectAccessAssignment(ai, currentMethodStatics->myExtValueBitset(), values);
  return true;
}

  

bool ArrayAccessNode::handleAssignment(AliasInfos *ai, Bitset* values)
{
  Bitset *varValues = array()->getValues(ai);

  // do the static info's checking. notice we get our own values BEFORE
  // assignment for the purposes of checking for this stuff..
  checkStaticsObjectAccessAssignment(ai, varValues, values);
  
  // every array value gets modified. in an array, we UNION, we never
  // delete values.
  for (int i = 0; i < varValues->size(); i++) {
    if (varValues->test(i)) {
      assert(isInMap(i, ai->valueToValueInfoMap));
      ai->valueToValueInfoMap[i]->arrayValues->un(values);
    }
  }
  return true;    
}






void AliasInfos::process(TreeNode *t)
{
  if (isMethodCallNode(t) || isAllocateNode(t) || isConstructorCallNode(t))
    checkStaticsProcedureCall(this, t);
  else if (isAssignNode(t))
    processAssignment(t->child(0), t->child(1));
  else if (isReturnNode(t)) { 
    if (!isOmittedNode(t->expr()) && isAliasable(t->expr()->type())) {
      Bitset *bs = t->expr()->getValues(this);
      currentMethodStatics->returnsValues->un(bs);
    }
  }
}





bool AliasInfos::processAssignment(TreeNode *leftSide, TreeNode *rightSide)
{
  // we check if it's an aliasable type. if it is we keep track of
  // aliasing, but even if it isn't, if it's an object/array/type field
  // access then we still need to check for side effects
  if (isAliasable(rightSide->type())) {
    Bitset *rightSideValues = rightSide->getValues(this);
    leftSide->handleAssignment(this, rightSideValues);
    return true;
  }
  else {
    Bitset *b = NULL;
    if (isTypeFAN(leftSide))
      b = leftSide->getValues(this); 
    else {
      if (leftSide->isArrayAccessNode())
	b = leftSide->array()->getValues(this);
      else if (isOFAN(leftSide))
	b = leftSide->object()->getValues(this);
    }

    if (b != NULL)
      checkStaticsObjectAccessAssignment(this, b, NULL);
    return true;
  }

  return true;
    
}




/////////////////////////// other stuff ////////////////

Bitset *ExprNode::getAbstractValues()
{
  /*
  // shouldn't be null because you should only use this after AA
  if (alias_anal && _abstractValues == NULL) {
    // this is put here because use-def treats immutables as aliasable
    // (and therefore bothers asking). it shouldn't.
    assert(type()->isImmutable());
  }
  */
  return _abstractValues;
}

void ExprNode::setAbstractValues(Bitset *b)
{
  _abstractValues = b;
}

Bitset *TreeNode::getAbstractValues()
{
  undefined("getAbstractValues");
  return NULL;
}

void TreeNode::setAbstractValues(Bitset *b)
{
  undefined("setAbstractValues");
}


Bitset *MethodCallNode::modifiesValues()
{
  return _modifiesValues;
}

Bitset *AllocateNode::modifiesValues()
{
  return _modifiesValues;
}

void MethodCallNode::setModifiesValues(Bitset *b)
{
  _modifiesValues = b;
}

void AllocateNode::setModifiesValues(Bitset *b)
{
  _modifiesValues = b;
}

void TreeNode::setModifiesValues(Bitset *b)
{
  undefined("setModifiesValues");
}

Bitset *TreeNode::modifiesValues()
{
  undefined("modifiesValues");  
  return NULL;
}

bool TreeNode::handleAssignment(AliasInfos *ai, Bitset* values)
{
  undefined("handleAssignment");
  return false;
}

Bitset *TreeNode::getValues(AliasInfos *ai)
{
  undefined("getValues");
  return NULL;
}