// This module creates use-def def-use chains for a given method. 
// Call setupUdMethod() with your favorite method to kick it off. 

// Interface/Usage:
//
// After calling setupUdMethod, the AST will become annotated with use<->def
// info. Each ObjectNode, FieldAccessNode, and ArrayAccessNode will have a 
// def chain attached to it, which points to all the locations where the node
// has a definition that reaches down to it.
//
// Each ObjectNode, FieldAccessNode, ArrayAccessNode, and ParameterNode that
// occurs in a store (definition) context will have a use chain attached to 
// it, which points out all the locations where the definition reaches.
//
// The def and use chains are weak with respect to aliasing, which means that
// they will point out all the defs and uses which may affect the node in
// question. A quick example:
//
//   a.i = 5
//   b.i = 6
//   foo()
//   x = a.i
//
// The a.i in the last statement will have a use chain that will point to the
// AssignmentNode in the first statement, the AssignmentNode in the second 
// statement, and the MethodCallNode in the third statement, since the value
// of a.i could have originated from any of these. The analysis checks that
// that b.i has the same type and field name as a.i, that "foo()" is not
// known to be a harmless library call, and of course, that these definitions
// reach the use of a.i through some CF path.
//
// Unaliasable entities (ObjectNodes) have strong (precise) use-def chains.
//
// Use and def chains are accessed by calling the getDefs() and getUses() 
// methods of a node in question, which both return an llist<TreeNode *>.
//
// The def chains (but not the use chains, right now) are printed out when
// the -dumpast switch is thrown. The phase name of this output (for the
// -dumpphase switch) is "usedef".

// How It Works:
// It's the classical method. First, the defs, kills, ins and outs are 
// calculated for each bblock. These are defined as follows:
//   defs: All the variable definitions in a single bblock.
//   kills: All the kills that you know *must* happen in a single bblock.
//          Hence passing an object to a function does not put a kill for its
//          field access in the kill set.
//   outs: All the definitions that are generated by a bblock unioned with
//         the definitions that flowed through the bblock from previous 
//         ones without being killed.
//   ins: The union of the outs of the bblocks that precede a bblock.
// The CFG is traversed multiple times to generate this information. The 
// CFG code in cfg.cc contains the algorithm that does the actual traverse in
// what is hoped to be a somewhat efficient manner.
//
// After the various bitsets are calculated, the CFG is traversed a final time
// to get all the use<->def edges hooked up, by starting with the ins of a 
// given bblock and propagating it TreeNode by TreeNode through the bblock,
// calculating the defs and kills (again) as they are seen and hooking up 
// the use<->def edges as uses and defs are seen.

#include "utils.h"
#include "AST.h"
#include "bitset.h"
#include "cfg.h"
#include "code-util.h"
#include "code-defs.h"
#include "code-deps.h"
#include "compiler.h"
#include "decls.h"

static void printUsesBblock(Bblock *b);
static bool debugOn = false;

// Accessors for the def and use chains

void ObjectNode::setDefs(llist<TreeNode *> *defs) { _deflist = defs; }
void ObjectNode::setUses(llist<TreeNode *> *uses) { _uselist = uses; }
llist<TreeNode *> *ObjectNode::getUses(void) const { return _uselist; }
llist<TreeNode *> *ObjectNode::getDefs(void) const { return _deflist; }

void ArrayAccessNode::setDefs(llist<TreeNode *> *defs) { _deflist = defs; }
void ArrayAccessNode::setUses(llist<TreeNode *> *uses) { _uselist = uses; }
llist<TreeNode *> *ArrayAccessNode::getUses(void) const { return _uselist; }
llist<TreeNode *> *ArrayAccessNode::getDefs(void) const { return _deflist; }

void FieldAccessNode::setDefs(llist<TreeNode *> *defs) { _deflist = defs; }
void FieldAccessNode::setUses(llist<TreeNode *> *uses) { _uselist = uses; }
llist<TreeNode *> *FieldAccessNode::getUses(void) const { return _uselist; }
llist<TreeNode *> *FieldAccessNode::getDefs(void) const { return _deflist; }

void ThisNode::setDefs(llist<TreeNode *> *defs) { _deflist = defs; }
void ThisNode::setUses(llist<TreeNode *> *uses) { _uselist = uses; }
llist<TreeNode *> *ThisNode::getUses(void) const { return _uselist; }
llist<TreeNode *> *ThisNode::getDefs(void) const { return _deflist; }

void ParameterNode::setUses(llist<TreeNode *> *uses) { _uselist = uses; }
llist<TreeNode *> *ParameterNode::getUses(void) const { return _uselist; }

// The big bag of defs for the current method.
static Defs *methodDefs;

// Calculates reaching in, reaching out, and the flow function for the block.
// These are accessed as b->defs(), b->defsIn(), and b->defsThis(), 
// respectively.
bool setupDefsBblock(Bblock *b) {
  // Traverse the bblock, setting up defs for all the non-stmt nodes.
  // The stmt nodes should not be traversed because their children are already
  // represented in the CFG. We might have the same problem with children of
  // any node at all, but the lowering of the graph by temporary creation 
  // will prevent defs from appearing as children of non-stmt nodes.

  if (debugOn) {
    cout << "Processing bblock#" << b->number << endl;
  }

  // Calculate the union of the predecessor defs.
  Bitset *ins = new Bitset(methodDefs->size());
  ListIterator<Bblock *> bbIt = b->predIter();
  for (; !bbIt.isDone(); bbIt.next()) {
    Bblock *bb = *bbIt;
    if (bb->defsOut()) {
      ins->un(bb->defsOut());
    }
  }
  
  // If the ins are the same as last time, we don't need to process this
  // block any further.
  if (b->defsIn()) {
    if (b->defsIn()->equal(ins)) {
      delete ins;
      return false;
    }
    else {
      delete b->defsIn();
    }
  }
  b->setDefsIn(ins);

  // If we don't know what the flow function is for this block, figure it out.
  if (!b->defs()) {
    Bitset *defs = new Bitset(methodDefs->size());
    Bitset *kills = new Bitset(methodDefs->size());
    ListIterator<CfgNode *> cfgIt = b->cfgIter();
    for (; !cfgIt.isDone(); cfgIt.next()) {
      CfgNode *cfg = *cfgIt;
      TreeNode *t = cfg->astNode();
      // Delete old u/d info.
      if (t->hasLval()) {
	free_all(t->getDefs());
	t->setDefs(NULL);
	free_all(t->getUses());
	t->setUses(NULL);
      }
      methodDefs->merge(t, defs, kills);
    }
    b->setDefs(defs);
    b->setKills(kills);
  }

  // Determine the defs reaching out: (ins U defs) - kills
  Bitset *outs = new Bitset(methodDefs->size());
  outs->un(ins);
  outs->un(b->defs());
  outs->subtract(b->kills());
  delete b->defsOut();
  b->setDefsOut(outs);
  return true;
}


// Sets up u->d edges for the uses in this bblock. 
void setupUdBblock(Bblock *b) {
  Bitset *reaching = new Bitset(methodDefs->size());

  reaching->un(b->defsIn());
  // Traverse the CFG list for this block, hooking up u->d edges for each
  // node we see that has an lval. We also need to mirror the dataflow 
  // calculations that we already did for this bblock, to allow for def-use 
  // pairs within the bblock.

  ListIterator<CfgNode *> cfgIt = b->cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();
    methodDefs->reaching(t, reaching);
    if (t->hasLval()) {
      methodDefs->connect(t, reaching);
    }
  }  
  delete reaching;
  if (debugOn) {
    printUsesBblock(b);
  }
}

// An action for the bblock traversal.
void printBlock(Bblock *b) {
  b->print(cout);
}

void removeUdBblock(Bblock *b) {
  delete b->defs();
  b->setDefs(NULL);
  delete b->kills();
  b->setKills(NULL);
  delete b->defsIn();
  b->setDefsIn(NULL);
  delete b->defsOut();
  b->setDefsOut(NULL);
}
void init_location_set(TreeNode *t){
  t->location_set = NULL;
  for (int i = 0; i < t->arity(); i++){
    init_location_set(t->child(i));
  }
}

void free_bitset(TreeNode *t){
  if (t->location_set != NULL){
    delete t->location_set;
    t->location_set = NULL;
  }
  for (int i = 0; i < t->arity(); i++){
    free_bitset(t->child(i));
  }
}

int array_index(llist <NameNode *> *list, TreeNode *t){
  NameNode **array = llist_to_array(list);
  for (int i = 0; i < list->size(); i++){
    if (array[i]->compare(t)){
      return i;
    }
  }
  //this happens when Titanium programmers write bogus overlap annotation, which is allowed
  return -1000;
}
bool propagate_assignment(TreeNode *t, int bitsetsize){
  bool change = false;
  int i;

  if (isAssignNode(t)){
    if (isObjectNode(t->child(0)) && isObjectNode(t->child(1))){
      //now make sure they both have type Titanium array
      ObjectNode *lhs = (ObjectNode *) t->child(0);
      ObjectNode *rhs = (ObjectNode *) t->child(1);
      TypeNode *lhs_type = lhs->type();
      TypeNode *rhs_type = rhs->type();
      if (lhs_type->isTitaniumArrayType() && rhs_type->isTitaniumArrayType()){
	if (rhs->location_set != NULL){
	  if (t->location_set == NULL){
	    t->location_set = new Bitset(bitsetsize);
	    t->location_set->un(rhs->location_set);
	    assert(t->location_set->equal(rhs->location_set));
	    change = true;
	  }
	  else if (t->location_set->equal(rhs->location_set) == false){
	    delete t->location_set;
	    t->location_set = new Bitset(bitsetsize);
	    t->location_set->un(rhs->location_set);
	    assert(t->location_set->equal(rhs->location_set));
	    change = true;
	  }
	}
      }
    }
  }

  for (i = 0; i < t->arity(); i++){
    change = change | propagate_assignment(t->child(i), bitsetsize);
  }

  return change;
}
//check for translate, restrict, slice, inject, permute
bool isGridOperation(NameNode *methodname){
  string method_name = *(methodname->ident());
  if ((method_name == "translate") || (method_name == "restrict") || (method_name == "slice") || (method_name == "inject") || (method_name == "permute")){
    return true;
  }
  else{
    return false;
  }
}
bool propagate_grid_operation(TreeNode *t, int bitsetsize){
  bool change = false;
  int i;

  if (isAssignNode(t)){
    if (isObjectNode(t->child(0)) && isMethodCallNode(t->child(1))){
      //now make sure the lhs has type Titanium array
      ObjectNode *lhs = (ObjectNode *) t->child(0);
      TypeNode *lhs_type = lhs->type();
      if (lhs_type->isTitaniumArrayType()){
	//check if the rhs is one of the grid operations
	MethodCallNode *methodcall = (MethodCallNode *) t->child(1);
	if (isObjectFieldAccessNode(methodcall->child(0))){
	  ObjectNode *object = (ObjectNode *) methodcall->child(0)->child(0);
	  NameNode *methodname = (NameNode *) methodcall->child(0)->child(1);
	  //make sure the object has type Titanium array and the method call is to a grid operation
	  if (object->type()->isTitaniumArrayType() && isGridOperation(methodname)){
	    if (object->location_set != NULL){
	      if (t->location_set == NULL){
		t->location_set = new Bitset(bitsetsize);
		t->location_set->un(object->location_set);
		change = true;
	      }
	      else if (t->location_set->equal(object->location_set) == false){
		delete t->location_set;
		t->location_set = new Bitset(bitsetsize);
		t->location_set->un(object->location_set);
		change = true;
	      }
	    }
	  }
	}
      }
    }
  }

  for (i = 0; i < t->arity(); i++){
    change = change | propagate_grid_operation(t->child(i), bitsetsize);
  }

  return change;
}
bool propagate_cast(TreeNode *t, int bitsetsize){
  bool change = false;
  int i;

  if (isAssignNode(t)){
    if (isObjectNode(t->child(0)) && isCastNode(t->child(1))){
      //now make sure the lhs has type Titanium array
      ObjectNode *lhs = (ObjectNode *) t->child(0);
      TypeNode *lhs_type = lhs->type();
      if (lhs_type->isTitaniumArrayType()){
	//check if the rhs is one of the grid operations
	CastNode *cast = (CastNode *) t->child(1);
	if (isObjectNode(cast->child(0))){
	  ObjectNode *object = (ObjectNode *) cast->child(0);
	  //make sure the object has type Titanium array and the method call is to a grid operation
	  if (object->type()->isTitaniumArrayType()){
	    if (object->location_set != NULL){
	      if (t->location_set == NULL){
		t->location_set = new Bitset(bitsetsize);
		t->location_set->un(object->location_set);
		change = true;
	      }
	      else if (t->location_set->equal(object->location_set) == false){
		delete t->location_set;
		t->location_set = new Bitset(bitsetsize);
		t->location_set->un(object->location_set);
		change = true;
	      }
	    }
	  }
	}
      }
    }
  }

  for (i = 0; i < t->arity(); i++){
    change = change | propagate_cast(t->child(i), bitsetsize);
  }

  return change;
}
bool propagate_allocation(TreeNode *t, int bitsetsize){
  bool change = false;
  int i;

  if (isAssignNode(t)){
    if (isObjectNode(t->child(0)) && isAllocateArrayNode(t->child(1))){
      //now make sure the lhs has type Titanium array
      ObjectNode *lhs = (ObjectNode *) t->child(0);
      TypeNode *lhs_type = lhs->type();
      if (lhs_type->isTitaniumArrayType()){
	TreeNode *allocate_node = t->child(1);
	//it is known that the location_set of the AllocationArrayNode is non-null here, so no need to check
	if (t->location_set == NULL){
	  t->location_set = new Bitset(bitsetsize);
	  t->location_set->un(allocate_node->location_set);
	  change = true;
	}
	else if (t->location_set->equal(allocate_node->location_set) == false){
	  delete t->location_set;
	  t->location_set = new Bitset(bitsetsize);
	  t->location_set->un(allocate_node->location_set);
	  change = true;
	}
      }
    }
  }

  for (i = 0; i < t->arity(); i++){
    change = change | propagate_allocation(t->child(i), bitsetsize);
  }

  return change;
}
bool propagate_objectnode(TreeNode *t, int bitsetsize){
  bool change = false;
  int i;

  if (isObjectNode(t)){
    llist <TreeNode *> *defs = t->getDefs();
    TreeNode **defs_array = llist_to_array(defs);
    bool all_non_null = true;

    //check all defs have non-null location sets
    for (i = 0; i < defs->size(); i++){
      if (defs_array[i]->location_set == NULL){
	all_non_null = false;
	break;
      }
    }

    if (defs->size() == 0){
      all_non_null = false;
    }

    if (all_non_null){
      Bitset *union_set = new Bitset(bitsetsize);

      //take the union of the location_set for all defs
      for (i = 0; i < defs->size(); i++){
	union_set->un(defs_array[i]->location_set);
      }
      if (t->location_set == NULL){
	t->location_set = union_set;
	change = true;
      }
      else if (t->location_set->equal(union_set) == false){
	delete t->location_set;
	t->location_set = union_set;
	change = true;
      }
    }
  }

  for (i = 0; i < t->arity(); i++){
    change = change | propagate_objectnode(t->child(i), bitsetsize);
  }

  return change;
}

void propagate_nooverlap(TreeNode *t, int bitsetsize){
  bool change;

  do{
    change = false;

    //propagate using def/use on objectnodes
    change = change | propagate_objectnode(t, bitsetsize);

    //propagate on assignments of the form array1 = array2
    change = change | propagate_assignment(t, bitsetsize);

    //propagate on assignment of the form array1 = array2.slice ...
    change = change | propagate_grid_operation(t, bitsetsize);

    //propagate through case nodes
    change = change | propagate_cast(t, bitsetsize);

    //propagate through array alloction
    change = change | propagate_allocation(t, bitsetsize);
  }
  while (change == true);
}

llist <TreeNode *> *find_allocation_sites(TreeNode *t, llist <TreeNode *> *list){
  if (isAllocateArrayNode(t)){
    if (t->type()->isTitaniumArrayType()){
      list = cons(t, list);
    }
  }
  for (int i = 0; i < t->arity(); i++){
    list = find_allocation_sites(t->child(i), list);
  }
  return list;
}

// Sets up the UD stuff for a method (MethodDeclNode or ConstructorDeclNode).
// If computeDeps is true, compute deps as well.
void computeNoOverLap(TreeNode *t){
    //initialize all location_set to null
    init_location_set(t);

    if (isMethodDeclNode(t)){
	MethodDeclNode *method = (MethodDeclNode *) t;
	TreeListNode *overlap_pairs = method->overlaps();
	TreeListNode *formal_params = method->params();
	
	int i;
	ParameterNode *param;
	int array_count = 0;
	llist <NameNode *> *array_list = NULL;
	
	for (i = 0; i < formal_params->arity(); i++){
	    param = (ParameterNode *) formal_params->child(i);
	    if (isTitaniumArrayTypeNode(param->child(0))){
		array_count++;
		array_list = cons((NameNode *) param->child(1), array_list);
	    }
	}
	
	llist <TreeNode *> *allocation_list = find_allocation_sites(t, NULL);
	int start_index = array_count;
	array_count += allocation_list->size();
	
	if (array_count > 1){
	    for (i = 0; i < formal_params->arity(); i++){
		param = (ParameterNode *) formal_params->child(i);
		if (isTitaniumArrayTypeNode(param->child(0))){
		    param->location_set = new Bitset(array_count);
		    int index = array_index(array_list, param->child(1));
		    param->location_set->set(index);
		    for (int j = 0; j < overlap_pairs->arity(); j++){
			OverlapNode *overlap_ = (OverlapNode *) overlap_pairs->child(j);
			TreeNode *array1;
			TreeNode *array2;
			array1 = overlap_->child(0);
			array2 = overlap_->child(1);
			if (((NameNode *) param->child(1))->compare(array1)){
			    index = array_index(array_list, array2);
			    //first check is for bogus overlap annotation, the second check is for duplicate overlap annotation
			    if ((index >= 0) && (param->location_set->test(index) == false)){
				param->location_set->set(index);
			    }
			}
			if (((NameNode *) param->child(1))->compare(array2)){
			    index = array_index(array_list, array1);
			    //first check is for bogus overlap annotation, the second check is for duplicate overlap annotation
			    if ((index >= 0) && (param->location_set->test(index) == false)){
				param->location_set->set(index);
			    }
			}
		    }
		}
	    }
	    
	    TreeNode **allocation_site_array = llist_to_array(allocation_list);
	    
	    for (i = 0; i < allocation_list->size(); i++){
		allocation_site_array[i]->location_set = new Bitset(array_count);
		allocation_site_array[i]->location_set->set(start_index);
		start_index++;
	    }
	}

	if (array_count > 1){
	    propagate_nooverlap(t, array_count);
	}
	return;
    }
}
// Sets up the UD stuff for a method (MethodDeclNode or ConstructorDeclNode).
// If computeDeps is true, compute deps as well.
void setupUdMethod(TreeNode *t, bool computeDeps) {

  // Methods without stmts don't have CFGs.
  if (!t->getBblockRoot()) {
    return;
  }

  if (infer_nooverlap){
    //initialize all location_set to null
    init_location_set(t);
  }

  // Traverse the bblock graph, removing old bit vectors.
  // The use-def chains will get removed during the pass that identifies
  // defs.
  TraverseBblocks(t->getBblockRoot(), removeUdBblock);

  DEBUG_PHASE("usedef", currentFilename, debugOn = true);

  // First, create a global bitvector map for all the defs in this method.
  assert(methodDefs == NULL);
  methodDefs = new Defs;
  t->findDefs(methodDefs);

  // Add in the defs for all the calls. This is done separately because calls
  // can def any aliasable entity, and we don't know which ones these are until
  // we've gone through all of them.
  methodDefs->addCallDefs();
  
  // Calculate the reaching def sets for all the bblocks in the method.
  TraverseBblocksIter(t->getBblockRoot(), setupDefsBblock);

  // Then go through each block again and hook up the u->d edges.
  TraverseBblocks(t->getBblockRoot(), setupUdBblock);

  if (infer_nooverlap){
    computeNoOverLap(t);

    //connect the use def edges again using no overlap info
    TraverseBblocks(t->getBblockRoot(), setupUdBblock);

    //free memory for the bitsets
    if (isMethodDeclNode(t)){
      free_bitset(t);
    }
  }

  if (computeDeps)
    setupDepsMethod(t);

  // Free the global map.
  delete methodDefs;
  methodDefs = NULL;

  debugOn = false;
}

void printDefList(llist<TreeNode *> *deflist) {
  ListIterator<TreeNode *>listIt = ListIterator<TreeNode *>(deflist);

  for (; !listIt.isDone(); listIt.next()) {
    TreeNode *t = *listIt;
    t->print(cout,1);
    cout << endl;
  }
}

static void printUsesBblock(Bblock *b) {
  printf("-----------------------\n");
  printf("Uses for bblock #%d\n", b->number);
  ListIterator<CfgNode *> cfgIt = b->cfgIter();
  for (; !cfgIt.isDone(); cfgIt.next()) {  
    CfgNode *cfg = *cfgIt;
    TreeNode *t = cfg->astNode();
    if (t->hasLval()) {
      cout << "USE: " << endl;
      t->print(cout,1);
      cout << endl << "DEFS: " << endl;
      llist<TreeNode *> *defList= t->getDefs();
      printDefList(defList);
      cout << endl;
    }
  }
}

/* unused
static void printDefsBblock(Bblock *b) {
  Bitset *outs = b->defsOut();
  printf("-----------------------\n");
  printf("Defs reaching out of bblock #%d\n", b->number);
  methodDefs->printBitset(outs, cout, 0);
}
*/