//===------EscapeAnalysis.cpp - Simple LLVM escape analysis ---------------===//
//
//                     The VMKit project
//
// This file is distributed under the University of Illinois Open Source 
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//


#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

#include <cstddef>
#include <map>

#include "VmkitGC.h"

using namespace llvm;

namespace {

  class EscapeAnalysis : public FunctionPass {
  public:
    static char ID;
    uint64_t pageSize;
    EscapeAnalysis() : FunctionPass(ID) {
      pageSize = getpagesize();
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<LoopInfo>();
    }

    virtual bool runOnFunction(Function &F);

  private:
    bool processMalloc(Instruction* I, Value* Size, Value* VT, Loop* CurLoop);
  };

  char EscapeAnalysis::ID = 0;
  RegisterPass<EscapeAnalysis> X("EscapeAnalysis", "Escape Analysis Pass");

bool EscapeAnalysis::runOnFunction(Function& F) {
  bool Changed = false;
  Function* Allocator = F.getParent()->getFunction("VTgcmalloc");
  if (!Allocator) return Changed;

  LoopInfo* LI = &getAnalysis<LoopInfo>();

  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; BI++) { 
    BasicBlock *Cur = BI;
   
    // Get the parent loop if there is one. If the allocation happens in a loop
    // we must make sure that the allocated value is not used outside of
    // the loop. If the allocation does not escape and it is only used inside
    // the loop, we will hoist the allocation in the pre-header of the loop.
    Loop* CurLoop = LI->getLoopFor(Cur);
    if (CurLoop) {
      Loop* NextLoop = CurLoop->getParentLoop();
      while (NextLoop) {
        CurLoop = NextLoop;
        NextLoop = CurLoop->getParentLoop();
      }
    }

    for (BasicBlock::iterator II = Cur->begin(), IE = Cur->end(); II != IE;) {
      Instruction *I = II;
      II++;
      if (I->getOpcode() != Instruction::Call &&
          I->getOpcode() != Instruction::Invoke) {
        continue;
      }
      CallSite Call(I);
      if (Call.getCalledValue() == Allocator) {
        if (CurLoop) {
          bool escapesLoop = false;
          for (Value::use_iterator U = I->use_begin(), E = I->use_end();
               U != E; ++U) {
            if (Instruction* II = dyn_cast<Instruction>(*U)) {
              BasicBlock* BBU = II->getParent();
              if (!CurLoop->contains(BBU)) {
                escapesLoop = true;
                break;
              }
            }
          }

          if (escapesLoop) continue;
        }

        if (CallInst *CI = dyn_cast<CallInst>(I)) {
          Changed |= processMalloc(CI, CI->getArgOperand(0), CI->getArgOperand(1),
                                   CurLoop);
        } else if (InvokeInst *CI = dyn_cast<InvokeInst>(I)) {
          Changed |= processMalloc(CI, CI->getArgOperand(0), CI->getArgOperand(1),
                                   CurLoop);
        }
      }
    }
  }
  return Changed;
}


static bool escapes(Value* Ins, std::map<Instruction*, bool>& visited) {
  for (Value::use_iterator I = Ins->use_begin(), E = Ins->use_end(); 
       I != E; ++I) {
    if (Instruction* II = dyn_cast<Instruction>(*I)) {
      if (II->getOpcode() == Instruction::Call || 
          II->getOpcode() == Instruction::Invoke) {
        
        CallSite CS(II);
        if (!CS.onlyReadsMemory()) return true;
        
        CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
        for (CallSite::arg_iterator A = B; A != E; ++A) {
          if (A->get() == Ins && 
              !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) {
            return true;
          }
        }
       
        // We must also consider the value returned by the function.
        if (II->getType() == Ins->getType()) {
          if (escapes(II, visited)) return true;
        }

      } else if (dyn_cast<BitCastInst>(II)) {
        if (escapes(II, visited)) return true;
      } else if (StoreInst* SI = dyn_cast<StoreInst>(II)) {
        if (AllocaInst * AI = dyn_cast<AllocaInst>(SI->getOperand(1))) {
          if (!visited[AI]) {
            visited[AI] = true;
            if (escapes(AI, visited)) return true;
          }
        } else if (SI->getOperand(0) == Ins) {
          return true;
        }
      } else if (dyn_cast<LoadInst>(II)) {
        if (isa<PointerType>(II->getType())) {
          if (escapes(II, visited)) return true; // allocas
        }
      } else if (dyn_cast<GetElementPtrInst>(II)) {
        if (escapes(II, visited)) return true;
      } else if (dyn_cast<ReturnInst>(II)) {
        return true;
      } else if (dyn_cast<PHINode>(II)) {
        if (!visited[II]) {
          visited[II] = true;
          if (escapes(II, visited)) return true;
        }
      }
    } else {
      return true;
    }
  }
  return false;
}

bool EscapeAnalysis::processMalloc(Instruction* I, Value* Size, Value* VT,
                                   Loop* CurLoop) {
  Instruction* Alloc = I;
  LLVMContext& Context = Alloc->getParent()->getContext();

  ConstantInt* CI = dyn_cast<ConstantInt>(Size);
  bool hasFinalizer = true;
  
  if (CI) {
    if (ConstantExpr* CE = dyn_cast<ConstantExpr>(VT)) {
      if (ConstantInt* C = dyn_cast<ConstantInt>(CE->getOperand(0))) {
        VirtualTable* Table = (VirtualTable*)C->getZExtValue();
        hasFinalizer = (((void**)Table)[0] != 0);
      } else {
        GlobalVariable* GV = dyn_cast<GlobalVariable>(CE->getOperand(0));
        if (GV->hasInitializer()) {
          Constant* Init = GV->getInitializer();
          if (ConstantArray* CA = dyn_cast<ConstantArray>(Init)) {
            Constant* V = CA->getOperand(0);
            hasFinalizer = !V->isNullValue();
          }
        }
      }
    }
  } else {
    return false;
  }

  // The object does not have a finalizer and is never used. Remove the
  // allocation as it will not have side effects.
  if (!hasFinalizer && !Alloc->getNumUses()) {
    //DEBUG(errs() << "Escape analysis removes instruction " << *Alloc << ": ");
    Alloc->eraseFromParent();
    return true;
  }
  
  uint64_t NSize = CI->getZExtValue();
  // If the class has a finalize method, do not stack allocate the object.
  if (NSize < pageSize && !hasFinalizer) {
    std::map<Instruction*, bool> visited;
    bool esc = escapes(Alloc, visited);
    if (!esc) {

      if (CurLoop) {
        // The object does not escape and is only used in the loop where it
        // is allocated. We hoist the allocation in the pre-header so that
        // we don't end up with tons of allocations on the stack.
        BasicBlock* BB = CurLoop->getLoopPreheader();
        assert(BB && "No Preheader!");
      //DEBUG(errs() << "Escape analysis hoisting to " << BB->getName().str());
        //DEBUG(errs() << ": ");
        //DEBUG(errs() << *Alloc);
        Alloc->removeFromParent();
        BB->getInstList().insert(BB->getTerminator(), Alloc);
      }

      AllocaInst* AI = new AllocaInst(Type::getInt8Ty(Context), Size, "",
                                      Alloc);
      BitCastInst* BI = new BitCastInst(AI, Alloc->getType(), "", Alloc);
      //DEBUG(errs() << "escape");
      //DEBUG(errs() << Alloc->getParent()->getParent()->getName().str() << "\n");
      Alloc->replaceAllUsesWith(BI);
      // If it's an invoke, replace the invoke with a direct branch.
      if (InvokeInst *CI = dyn_cast<InvokeInst>(Alloc)) {
        BranchInst::Create(CI->getNormalDest(), Alloc);
      }
      Alloc->eraseFromParent();
      return true;
    }
  }
  return false;
}
}

namespace vmkit {
FunctionPass* createEscapeAnalysisPass() {
  return new EscapeAnalysis();
}

}