// 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);
}

// 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;
  }

  // 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 (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);
}
*/