//  $Archive:: /Ti/inline/inline.cc                                       $
//     $Date: Sat, 02 Apr 2005 23:42:07 -0800 $
// $Revision: 1.19.1.5.1.14 $
// Description: framework for method inlining
// Copyright 2000, Dan Bonachea <bonachea@cs.berkeley.edu>

#include "AST.h"
#include "code-util.h"
#include "inline.h"
#include "lower.h"
#include "osstream.h"
#include "llist.h"

TreeNode * const inlineStrategy::DONTCARE = (TreeNode*)0;
TreeNode * const inlineStrategy::NOMORE = (TreeNode*)-1;
extern int compile_verbose_level;

//------------------------------------------------------------------------------------
TreeNode *depthFirstSearch(TreeNode *t, bool (*filter)(const TreeNode *t), 
                    TreeNode * preorderaction(TreeNode *t), TreeNode * postorderaction(TreeNode *t), 
                    bool pruneSearchAtMatch) {
  // framework for a depth-first search
  // filter decides (on initial visit) whether this node should get passed to pre and post order actions
  // pre and port order actions may return a modified subtree to replace current node, or NULL for no change
  // search may itself return a modified subtree
  const bool match = filter(t);
  bool didreplace = false;
  if (match) {
    if (preorderaction) {
      TreeNode* retval = preorderaction(t);
      if (retval) { t = retval; didreplace = true; }
      }
    } 

  if (!(match && pruneSearchAtMatch)) {
    const int childCount = t->arity();
    for (int sweep = 0; sweep < childCount; sweep++) { 
	    TreeNode *retval = depthFirstSearch(t->child(sweep), filter, preorderaction, postorderaction, pruneSearchAtMatch);
      if (retval) t->child(sweep, retval); // set new child
      } 
    }

  if (postorderaction) {
    TreeNode* retval = postorderaction(t);
    if (retval) { t = retval; didreplace = true; }
    }
  if (didreplace) return t;
  else return NULL;
  }   


//------------------------------------------------------------------------------------
// helpers for run()
static llist<TreeNode *> *siteList; 
static TreeNode* buildSiteList(TreeNode *t) { 
  siteList = cons(t, siteList);
  return NULL;
  }
static TreeNode *printFullName(TreeNode *t) { cout << t->decl()->fullName() << " "; return NULL; }
//------------------------------------------------------------------------------------
void inlineStrategy::run() {
  initializeStrategy();
  policy->initializePolicy();

  // build a list of methods that we're going to codegen
  llist<TreeNode *>* methodList = buildMethodList(true);

  while (methodList) {
    // get the next method
    TreeNode *method = nextMethod();
    if (method == NOMORE) break;
    else if (method == DONTCARE) {
      method = methodList->front();
      methodList = methodList->free();
      }
    else {
      llist<TreeNode *>* newlist = remove(method, methodList);
      if (newlist == (llist<TreeNode *>*)-1) { 
        // not found in remaining list - we already processed this method
        if (nextMethodChecked) {
          fatal_error("*** ERROR: inlineStrategy.nextMethod() tried to revisit a method,"
                  " or visit a method not selected for codegen"); 
          }
        }
      else methodList = newlist;
      }

    // sanity check
    method->checkIF(true);

    if (inlineDebug) {
      cout << "*** Method: " << method->decl()->fullName() << endl;
      cout << "Calls: ";
      depthFirstSearch(method, isProcedureCallNode, printFullName);
      cout << endl;
      //method->print();

      #if 1
	method->fixParent();
        checkAliasing(method);
      #else
	method->fixParent();
        int check = method->fixParent();
        if (check != 0) {
          cout << "*** Aliasing detected in AST before inline.." << check << " unfixable parents." << endl;
          }
      #endif
      }

    // if we ever move to arbitrarily ordered site processing,
    // this must be moved to a place where it's kept throughout entire computation
    map< TreeNode *, int > sitedepth; 

    siteList = NULL;
    depthFirstSearch(method, isProcedureCallSite, buildSiteList);
    llist<TreeNode *> *callSites = siteList;
    if (maxInliningDepth) // need to track site depth
      for (llist<TreeNode *>*p=siteList;p;p=p->tail()) sitedepth[p->front()] = 0;
    siteList = NULL;
    bool inlinedSomething = false;
    while (callSites != NULL) {
      TreeNode* site = callSites->front();
      callSites = callSites->free();

      if (maxInliningDepth && sitedepth[site] >= maxInliningDepth) {
        if (inlineDebug) 
          cout << "*** Exceeded maxInliningDepth " << maxInliningDepth << 
                  ", truncating inlining operation to prevent non-termination." << endl;
        numSitesRejectedByDepth++;
        }
      else if (policy->shouldInline(site)) {
        // perform inlining
        TreeNode* newcode = inlineCallSite(site); 
        inlinedSomething = true;

        // substitute the replacement code for the call site
        TreeNode *parent = site->parent();
        assert(parent != NULL);
        int childidx = -1;
        for (int i = parent->arity()-1; i >= 0; i--) {
          if (parent->child(i) == site) {
            childidx = i;
            break;
            }
          }
        assert(childidx >= 0);
        parent->child(childidx, newcode);

        // tell policy what we did
        policy->update(site, newcode); 

        if (considerSitesCreatedByInlining) {
          siteList = NULL;
          depthFirstSearch(newcode, isProcedureCallSite, buildSiteList); // add newly created sites
          if (maxInliningDepth) { // need to track site depth
            int callerdepth = sitedepth[site];
            for (llist<TreeNode *>*p=siteList;p;p=p->tail()) sitedepth[p->front()] = callerdepth + 1;
            }
          if (siteList) callSites = extend(callSites, siteList);
          siteList = NULL;
          }

        // TODO: delete site subtree

        numSitesInlined++;
        }
      numSitesConsidered++;
      } 

    // do AST fixup
    if (inlinedSomething) fixupMethodAfterInline(method);

    // sanity check
    method->checkIF(true);
    } // while methods

  if (inlineDebug || compile_verbose_level) {
    compile_status(0, string(" inlined ") + int2string(numSitesInlined)
      + " method call sites, out of " 
      + int2string(numSitesConsidered) + " sites considered.");
    if (numSitesRejectedByDepth) {
      compile_status(0, string(" ") + int2string(numSitesRejectedByDepth)
           + " sites rejected due to exceeding maxInliningDepth");
    }
  }

  policy->finalizePolicy();
  finalizeStrategy();
  }
//------------------------------------------------------------------------------------
TreeNode *getSiteCaller(TreeNode *callsite) {
  // return the method that contains this call site, or NULL for error
  if (!callsite || !isProcedureCallSite(callsite)) return NULL;
  TreeNode *tmp = callsite;
  while (tmp) {
    if (isMethodDeclNode(tmp) || isConstructorDeclNode(tmp)) return tmp;
    tmp = tmp->parent();
    }
  return NULL; // didn't find
  }
//------------------------------------------------------------------------------------
static llist<ClassDecl*> *getSuperTypeDecls(ClassDecl *d) {
  // return a list of ClassDecls representing all the supertypes of the
  // class or interface represented by d (including d itself)
  if (!d) return NULL;
  llist<ClassDecl*> * result = cons(d);
  result = extend(result, getSuperTypeDecls(d->superClass()));
  for (llist<Decl*>*inf = d->interfaces(); inf; inf = inf->tail()) {
    result = extend(result, getSuperTypeDecls((ClassDecl *)inf->front()));
  }
  return result;
}
bool isSuperclassDecl(Decl *sup, Decl *sub) {
  // return true iff both Decls represent classes and sup is a superclass of sub (or equal to)
  if (!sup || sup->category() != Decl::Class || 
      !sub || sub->category() != Decl::Class) 
    return false;
  else if (sup == sub) return true;
  else if (sub == ObjectDecl) return false;
  else return isSuperclassDecl(sup, sub->superClass());
}
bool isSupertypeDecl(Decl *sup, Decl *sub) {
  // return true iff both Decls represent classes or interfaces, 
  // and sup is a supertype of sub (or equal to)
  if (!sup || (sup->category() != Decl::Class && sup->category() != Decl::Interface) ||
      !sub || (sub->category() != Decl::Class && sub->category() != Decl::Interface)) 
    return false;
  else if (sup == sub) return true;
  else if (sub == ObjectDecl) return false;
  else { // climb the class & interface hierarchy
    if (isSupertypeDecl(sup, sub->superClass())) return true;
    else {
      for (llist<Decl*>*inf = sub->interfaces(); inf; inf = inf->tail()) {
        if (isSupertypeDecl(sup, inf->front())) return true;
      }
      return false;
    }
  }
}
llist<TreeNode*> *getPossibleMethodTargets(Decl *md, ClassDecl *targetObjectClassDecl) {
  // given a MethodDecl and a targetObjectClassDecl (or NULL for ignore it)
  // returns a list of all MethodDeclNodes which override that Decl,
  // (possibly including the one attached to the given Decl)
  // which are possible targets for the method call
  // MethodSignatureNodes from interfaces are screened out
  // if targetObjectType is provided, the overrides returned will be further filtered to
  // only include those declared in subtypes of the targetObjectType 
  // (the real possible targets of the method call)
  // this distinction only matters when the method is inherited from
  // a supertype of the targetObjectType, in which case the MethodDecl is
  // actually attached to the supertype and may have some irrelevant overriders
  assert(md->category() == Decl::Method || md->category() == Decl::Constructor);

  if (isConstructorDeclNode(md->source())) return cons(md->source());

  llist<TreeNode*> *temp = NULL;
  if (isMethodDeclNode(md->source()) && !(md->modifiers() & Common::Abstract)) {
    assert(md->container()->category() == Decl::Class);
    temp = cons(md->source(),temp);
  }
  MethodSet *overriders = md->overriders();
  for (MethodSet::const_iterator method = overriders->begin();
       method != overriders->end();
       method++) {
    // need to check if the given override is actually a possible target
    // (which it might not be if the method called is inherited)
    bool targetPossible = false;
    if ((*method)->modifiers() & Common::Abstract) targetPossible = false;
    else if (targetObjectClassDecl == NULL || 
             targetObjectClassDecl == md->container()) targetPossible = true;
    else {
      if (targetObjectClassDecl->category() == Decl::Class) {
        // suffices to check whether overrider is attached to a subclass
        if (isSuperclassDecl(targetObjectClassDecl, (*method)->container()))
          targetPossible = true;
      }
      else {
        // dispatched to an interface, need to check all subtypes
        if (isSupertypeDecl(targetObjectClassDecl, (*method)->container())) 
          // method override is declared in a subtype of the target object type
          targetPossible = true;
      }
    }
    if (targetPossible) { // only need to recurse on possible targets 
      temp = extend(temp, getPossibleMethodTargets((*method), targetObjectClassDecl));
    }
  }
  return temp;
}
//------------------------------------------------------------------------------------
llist<TreeNode *>* getSiteCallees(TreeNode *callsite) {
  // return a newly allocated list of methods that may be called this call site, or NULL for error
  // this list might be incomplete if we're not compiling main (partial program analysis)
  if (!callsite || !isProcedureCallSite(callsite)) return NULL;

  TreeNode *callNode = getSiteCallNode(callsite);
  TreeNode *fan = callNode->method();
  TreeNode *callee = fan->simpName()->decl()->source();

  // super.method() must be treated specially because the method itself may have overriders,
  // but we know statically by the object type exactly which override is being called
  if (isSuperThisCallSite(callsite)) {
    //cout << " getSiteCallees superThisCallSite callee: " << getMethodFullName(callee) << endl;
    return cons(callee);
    }
  else if (isTypeFAN(fan) || (isOFAN(fan) && (fan->decl()->modifiers() & Common::Static))) {
    // static method calls always statically bound to a single callee
    return cons(callee);
    }
  else {
    assert(isOFAN(fan));
    // possible callees are the method identified by name resolution (if it resides in a class)
    // and all overrides which are declared by subtypes of the target object
    llist<TreeNode *>* callees = getPossibleMethodTargets(callNode->decl(), 
                                (ClassDecl*)fan->accessedObjectType()->decl());
    return callees;
    }
  }
//------------------------------------------------------------------------------------
TreeNode *getSiteCallee(TreeNode *callsite) { // get the one-and-only callee for this site
  llist<TreeNode *>* callees = getSiteCallees(callsite);
  assert(callees->size() == 1); 
  TreeNode* callee = callees->front();
  free_all(callees);
  return callee;
  }
//------------------------------------------------------------------------------------
TreeNode *getSiteCallNode(const TreeNode *callsite) {
  // given the call site stmt, return the actual call node
  assert(callsite != NULL);
  if (isCallAssignSite(callsite)) 
    return callsite->child(0)->child(1);
  if (isSimpleCallSite(callsite))
    return callsite->child(0);
  fatal_error("");
  return NULL;
  }
//------------------------------------------------------------------------------------
bool isProcedure(const TreeNode *t) { 
  //return isMethodDeclNode(t); 
  return (isMethodDeclNode(t) || isConstructorDeclNode(t)); 
  }
bool isProcedureCallNode(const TreeNode *t) { 
  return (isMethodCallNode(t));
  //|| isMethodCallAssignNode(t) || isThisConstructorCallNode(t) || isSuperConstructorCallNode(t) || isAllocateNode(t)); 
  }
bool isCallAssignSite(const TreeNode *t) { 
  // CallAssignSite looks like: (ExprStmtNode (AssignNode (dest) (MethodCallNode ...
  bool val = (isExpressionStmtNode(t) &&
          ( isAssignNode(t->child(0)) && isMethodCallNode(t->child(0)->child(1))));
  #if 0
  if (val) { // this might not hold for immutable constructor calls
      Decl * dcl = t->child(0)->child(1)->method()->simpName()->decl();
      assert(dcl->type()->returnType()->kind() != Common::VoidKind);
      }
  #endif
  return val;
  }
bool isSimpleCallSite(const TreeNode *t) { 
  // SimpleCallSite looks like: (ExprStmtNode (MethodCallNode ...
  bool val = (isExpressionStmtNode(t) && isMethodCallNode(t->child(0)));
  if (val) {
    Decl * dcl = t->child(0)->method()->simpName()->decl();
    if (!(dcl->type()->returnType()->kind() == Common::VoidKind ||
           isConstructorDeclNode(dcl->source()))) {
      t->print();
      fatal_error("Call to non-void method is missing a return target");
      }
    }
  return val;
  }
bool isProcedureCallSite(const TreeNode *t) { 
  // detect the enclosing stmt for a procedure call 
  return (isCallAssignSite(t) || isSimpleCallSite(t));
  }

bool isSuperThisCallSite(const TreeNode *callsite) { // a call of the form super.method()  (which is always statically bound)
  if (!isProcedureCallSite(callsite)) return false;
  TreeNode *callnode = getSiteCallNode(callsite);
  TreeNode *fan = callnode->method();
  if (!isOFAN(fan)) return false;
  ObjectFieldAccessNode *ofan = static_cast<ObjectFieldAccessNode *>(fan);
  return ofan->isRewrittenSFAN(); // call of the form: super.methodName(), always statically bound 
  }

extern bool opt_finalize;

bool canCallStatically(TreeNode *callsite) {
  assert(isProcedureCallSite(callsite));
  bool result = false;

  TreeNode *callnode = getSiteCallNode(callsite);
  TreeNode *fan = callnode->method();
  
  if (isTypeFAN(fan) || (isOFAN(fan) && (fan->decl()->modifiers() & Common::Static)))
    result = true; // call to a static method always statically bound

  else if (isOFAN(fan)) { // call on an object
    // call of the form: super.methodName(), always statically bound 
    if (isSuperThisCallSite(callsite)) result = true; 
    else { // regular non-static method call
      ObjectFieldAccessNode *ofan = static_cast<ObjectFieldAccessNode *>(fan);
      MethodDecl *junk;
      result = ofan->canCallStatically(junk); // check other known cases
      // (constructors, methods that are final, private or static, no visible overrides)
    }
  } else fatal_error(""); // all other field access nodes should have been removed by lowering by now

  if (result) { // double-check that we don't see any overrides (sanity check)
    llist <TreeNode *>* l = getSiteCallees(callsite);
    if (l->size() != 1) {
      cout << "Override error in canCallStatically() at this site:" << endl;
      callsite->pseudoprint(cout); cout << endl;
      callsite->print();
      fatal_error("");
      }
    free_all(l);
    }

  return result;
  }

//------------------------------------------------------------------------------------
static void printlist(const TreeNode *t, ostream &os)
{
  if (!t->absent()) {
    int i = 0, a = t->arity();
    bool first = true;
    while (i < a) {
      if (!first) os << ", ";
      else first = false;
      t->child(i)->pseudoprint(os, 0);
      i++;
    }
  }
}
//------------------------------------------------------------------------------------
string getMethodFullName(TreeNode *method) {
  ostringstream os;
  if (isMethodDeclNode(method)) {
    MethodDeclNode *mdn = static_cast<MethodDeclNode *>(method);
    os << "Method " << stringifyModifiers(mdn->flags()) << ' '
       << mdn->returnType()->typeName() << ' '
       << mdn->decl()->fullName() << '(';
    printlist(mdn->params(), os);
    os << ')';
    if (!mdn->throws()->absent() && mdn->throws()->arity()) {
      os << " throws ";
      mdn->throws()->pseudoprint(os, 0);
      }
    if (!mdn->overlaps()->absent() && mdn->overlaps()->arity()) {
      os << " overlaps ";
      mdn->overlaps()->pseudoprint(os, 0);
      }
    }
  else if (isConstructorDeclNode(method)) {
    ConstructorDeclNode *mdn = static_cast<ConstructorDeclNode *>(method);
    os << "Constructor " << stringifyModifiers(mdn->flags()) << ' '
       << mdn->returnType()->typeName() << ' '
       << mdn->decl()->fullName() << '(';
    printlist(mdn->params(), os);
    os << ')';
    if (!mdn->throws()->absent() && mdn->throws()->arity()) {
      os << " throws ";
      mdn->throws()->pseudoprint(os, 0);
      }
    }
  else fatal_error("");
  return os.str();
  }
//------------------------------------------------------------------------------------
string getMethodShortName(TreeNode *method) {
  ostringstream os;
  Decl &decl = *method->decl();
  os << decl.container()->fullName() + ".";
  method->simpName()->pseudoprint(os, 0);
  os << "()";
  return os.str();
  }
//------------------------------------------------------------------------------------
string printMethodList(llist<TreeNode *> *methodlist) {
  ostringstream os;
  while (methodlist) {
    os << getMethodShortName(methodlist->front());
    methodlist = methodlist->tail();
    if (methodlist) os << ", ";
  }
  return os.str();
}
//------------------------------------------------------------------------------------
static llist<TreeNode *> *prvMethodList; 
static TreeNode* buildMList(TreeNode *t) { 
  if (!find(t, prvMethodList))
    prvMethodList = cons(t, prvMethodList);
  return NULL;
  }
llist<TreeNode *> *buildMethodList(bool onlyThoseSelectedForCodegen) { 
  // build a list of method decls in random order
  prvMethodList = NULL;
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    if ( (onlyThoseSelectedForCodegen && (*f)->selectedForCodeGen(false)) 
         || !onlyThoseSelectedForCodegen)
      foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
        if (isClassDeclNode((*type))) // ignore interfaces + uninstantiated templates
          depthFirstSearch(*type, isProcedure, buildMList);
  
  llist<TreeNode*>* tmp = prvMethodList;
  prvMethodList = NULL;
  return tmp;
  }
//------------------------------------------------------------------------------------
llist<TreeNode *> *getSystemEntryPoints() { // return list of all system execution entry points
  // main
  // static initializers & static field initializers
  // things that can be ccalled from native methods
  // if !codeGen_main, then all methods except private, protected or package methods
  // beware: when walking tree, constructors should also walk instance initializers
  fatal_error("");
  return NULL;
  }
//------------------------------------------------------------------------------------
// New TreeNode inlineInfo methods

// we added a new pointer reserved for use by the inlinePolicy and inlineStrategy
// objects during inline inter-procedural analysis:
//void *_inlineInfo;

void *MethodDeclNode::inlineInfo() const {  return _inlineInfo;  }

void MethodDeclNode::inlineInfo(void *ii) { _inlineInfo = ii;  }

void *ConstructorDeclNode::inlineInfo() const {  return _inlineInfo;  }

void ConstructorDeclNode::inlineInfo(void *ii) {  _inlineInfo = ii;  }

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

#include "inline-heuristic.h"

bool inlineDebug = false;
bool inline2Debug = false;
bool inlineStats = false;
extern int opt_inline_level;

void doMethodInlining() {

  DEBUG_PHASE("inlinetrans", currentFilename, inlineDebug = true);
  DEBUG_PHASE("inline2", currentFilename, inline2Debug = true);
  DEBUG_PHASE("inlinestats", currentFilename, inlineStats = true);
  
  inlineStrategy *currentStrategy = NULL;
  switch (opt_inline_level) {
    case 1:
      currentStrategy = new manualHeuristic();
      break;
    case 2:
      //cout << "*** Warning: Inline level-2 is still under development and may be unstable." << endl;
      currentStrategy = new complexHeuristic();
      break;
    default:
      fatal_error("");
    }
  currentStrategy->run();

  delete currentStrategy;
  }
//------------------------------------------------------------------------------------