//  $Archive:: /Ti/inline/inline-heuristic.h                              $
//     $Date: Sun, 09 Feb 2003 16:57:58 -0800 $
// $Revision: 1.9 $
// Description: heuristics for method inlining
// Copyright 2000, Dan Bonachea <bonachea@cs.berkeley.edu>

#ifndef _INLINE_HEURISTIC_H
#define _INLINE_HEURISTIC_H

#include "bitset.h"
#include "inline.h"
#include "InstancePool.h"

//------------------------------------------------------------------------------------
// a simple inlining heuristic

class manualHeuristic : public inlinePolicy, public inlineStrategy {
  public:
    manualHeuristic() : inlineStrategy(this) {}
    virtual void initializePolicy() { 
      considerSitesCreatedByInlining = true; 
        // we ensure termination by never inlining a directly recursive method 
        // (this handles mutual recursion too because we update info as we go)
      maxInliningDepth = opt_inline_maxdepth;
        // we also need an absolute limit for the rare programs that can 
        // still cause non-termination (Kaser 93)
      }
    virtual bool shouldInline(TreeNode *callsite);
  protected:
    // used to drive analysis (lazily detect direct recursion)
    bool isDirectlyRecursive(TreeNode *method);
    void updateInfo(TreeNode *method);
    virtual void update(TreeNode *callSiteInlined, TreeNode *replacementCode);
  };

//------------------------------------------------------------------------------------
// a more sophisticated inlining heuristic

class complexHeuristicInlineInfo {
public:
  // methods this method might reach (only includes this one in the presence of recursion)
  Bitset* callReaches; // this is the result of our flow-insensitive interprocedural DFA
  int reachIdx; // my index in above Bitset

  // useful local info, used while calculating the above
  llist<TreeNode *> *directCallSites; // list of direct call sites from this method
  llist<TreeNode *> *directCallerSites; // list of call sites directly to this method (may include some extras)
  llist<TreeNode *> *callees; // list of methods directly called by this method (may include some extras)
  llist<TreeNode *> *callers; // list of methods which directly call this method (may include some extras)

  // size estimates
  int codeSize;

  // misc
  int visited; // reserved for buildCGPostOrder (build call graph)
  bool willBeCodeGenned; // is a user method, or a library and we're generating libraries

  complexHeuristicInlineInfo() {
    callReaches = NULL;
    directCallSites = NULL;
    directCallerSites = NULL;
    callees = NULL;
    callers = NULL;
    codeSize = 0;
    visited = 0;
    willBeCodeGenned = false;
  }

  ~complexHeuristicInlineInfo() {
    delete callReaches;
    free_all(directCallSites);
    free_all(directCallerSites);
    free_all(callees);
    free_all(callers);
    }

  // region-based allocation for inlineInfo objects
  static void resetHeap();
  void *operator new(size_t size);
  void operator delete(void *buffer, size_t size);
};

#define ii(x) ((complexHeuristic::inlineInfo *)((x)->inlineInfo()))
void initMethodInfo(TreeNode *method);
TreeNode *initSiteInfo(TreeNode *callsite);
TreeNode *processNewSites(TreeNode *callsite);
extern bool opt_DME;

class complexHeuristic : public inlinePolicy, public inlineStrategy {
 public:
  // tuning parameters
  float maxCodeBloat; // max code bloat to allow
  bool performDME;    // do dead-method elimination
  bool maxChildPostOrdering; // during traversal, consider methods with more sites first

 protected:
  llist<TreeNode *> *methodList; // methods remaining to be considered
  MethodDeclNode** reachNode; // Bitset idx => MethodDecl
  int bitMaskWidth; // number of bits in callReaches

  typedef complexHeuristicInlineInfo inlineInfo;

  long totalCodeSizeInitial; // used to track bloat
  long totalCodeSize; 

  bool hasUserNativeMethods;

  MethodDeclNode* SystemEntry; // single node that calls all entry points

  // stats about why heuristic made decisions
  map<string, int> rejectReason;
  map<string, int> acceptReason;

  static const int smallMethodSize; // tiny methods - empty or just a single statement

  //------------------------------------------------------------------------------------
  void processWorklist(llist<TreeNode *> *worklist);
    // destructively consume worklist to solve backward DFA

  llist<TreeNode *> *buildCGRevPostOrder(TreeNode *method, int visitedidx);
  llist<TreeNode *> *buildCGPostOrder(TreeNode *rootMethod);

  // these called recursively by depthFirstSearch (so cannot be an instance method)
  friend void initMethodInfo(TreeNode *method);
  friend TreeNode *initSiteInfo(TreeNode *callsite);
  friend TreeNode *processNewSites(TreeNode *callsite);

  static int sizeEstimate(TreeNode *t);
    // return an estimate of the executable size that will result from the subtree rooted at t
  void outputMethodInfo(TreeNode *method);
  //------------------------------------------------------------------------------------
 public:
  complexHeuristic() : inlineStrategy(this) {
    maxCodeBloat = 0.50;
    performDME = opt_DME;
    hasUserNativeMethods = false;
    maxChildPostOrdering = true;
    }
  //------------------------------------------------------------------------------------
  static inline bool isLeafMethod(TreeNode *md) {
    return (ii(md)->directCallSites == NULL);
    }
  //------------------------------------------------------------------------------------
  static inline bool isNonLeafMethod(TreeNode *md) {
    return !isLeafMethod(md);
    }
  //------------------------------------------------------------------------------------
  static inline bool isRecursive(TreeNode *md) { // method participates in a recursive cycle in call graph
    inlineInfo *ii = ii(md);
    return ii->callReaches->test(ii->reachIdx);
    }
  //------------------------------------------------------------------------------------
  static inline bool isRecursiveSite(TreeNode *callsite) { // site participates in a recursive cycle in call graph
    inlineInfo *callerii = ii(getSiteCaller(callsite));
    llist<TreeNode*>* callees = getSiteCallees(callsite);
    bool result = false;
    foreach(callee, llist<TreeNode *>, *callees) {
      inlineInfo *calleeii = ii(*callee);
      if(calleeii->callReaches->test(callerii->reachIdx)) {
        result = true;
        break;
      }
    }
    free_all(callees);
    return result;
    }
  //------------------------------------------------------------------------------------
  static inline bool isDirectlyRecursive(TreeNode *md) { // method directly calls itself
    return !!find(md, ii(md)->callees);
    }
  //------------------------------------------------------------------------------------
  // true iff there is a path in the call graph from parent to child
  static inline bool isTransitivelyCalledBy(TreeNode *mdchild, TreeNode *mdparent) {
    inlineInfo *parentii = ii(mdparent);
    inlineInfo *childii = ii(mdchild);
    return parentii->callReaches->test(childii->reachIdx);
  }
  //------------------------------------------------------------------------------------
  virtual void initializePolicy();
  virtual void initializeStrategy();
  virtual bool shouldInline(TreeNode *callsite);
  virtual void update(TreeNode *callSiteInlined, TreeNode *replacementCode);
  virtual void finalizePolicy();
  virtual void finalizeStrategy();
 protected:
  virtual TreeNode * nextMethod();
    // decide the next method to be processed
    // use post-order traversal on call graph
  };
//------------------------------------------------------------------------------------

#endif