/// See comments in Cloning.h.
BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
                                  ValueToValueMapTy &VMap,
                                  const Twine &NameSuffix, Function *F,
                                  ClonedCodeInfo *CodeInfo) {
  BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
  if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);

  bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  
  // Loop over all instructions, and copy them over.
  for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
       II != IE; ++II) {
    Instruction *NewInst = II->clone();
    if (II->hasName())
      NewInst->setName(II->getName()+NameSuffix);
    NewBB->getInstList().push_back(NewInst);
    VMap[&*II] = NewInst; // Add instruction map to value.

    hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
    if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
      if (isa<ConstantInt>(AI->getArraySize()))
        hasStaticAllocas = true;
      else
        hasDynamicAllocas = true;
    }
  }
  
  if (CodeInfo) {
    CodeInfo->ContainsCalls          |= hasCalls;
    CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
    CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
                                        BB != &BB->getParent()->getEntryBlock();
  }
  return NewBB;
}

  /// findStopPoint - Find the stoppoint coressponding to this instruction, that
  /// is the stoppoint that dominates this instruction.
  const DbgStopPointInst *findStopPoint(const Instruction *Inst) {
    if (const DbgStopPointInst *DSI = dyn_cast<DbgStopPointInst>(Inst))
      return DSI;

    const BasicBlock *BB = Inst->getParent();
    BasicBlock::const_iterator I = Inst, B;
    while (BB) {
      B = BB->begin();

      // A BB consisting only of a terminator can't have a stoppoint.
      while (I != B) {
        --I;
        if (const DbgStopPointInst *DSI = dyn_cast<DbgStopPointInst>(I))
          return DSI;
      }

      // This BB didn't have a stoppoint: if there is only one predecessor, look
      // for a stoppoint there. We could use getIDom(), but that would require
      // dominator info.
      BB = I->getParent()->getUniquePredecessor();
      if (BB)
        I = BB->getTerminator();
    }

    return 0;
  }

void ExampleFunctionPrinter(raw_ostream& O, const Function& F) {
  for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
    const BasicBlock* block = FI;
    O << block->getName() << ":\n";
    PrintInstructionOps(O, NULL);
    for (BasicBlock::const_iterator BI = block->begin(), BE = block->end();
        BI != BE; ++BI) {
      BI->print(O);
      PrintInstructionOps(O, &(*BI));
    }
  }
}

void NaClValueEnumerator::incorporateFunction(const Function &F) {
  InstructionCount = 0;
  NumModuleValues = Values.size();

  // Make sure no insertions outside of a function.
  assert(FnForwardTypeRefs.empty());

  // Adding function arguments to the value table.
  for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
       I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (const SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
        // Handle switch instruction specially, so that we don't write
        // out unnecessary vector/array constants used to model case selectors.
        if (isa<Constant>(SI->getCondition())) {
          EnumerateValue(SI->getCondition());
        }
      } else {
        for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
             OI != E; ++OI) {
          if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
              isa<InlineAsm>(*OI))
            EnumerateValue(*OI);
        }
      }
    }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  FirstInstID = Values.size();

  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (!I->getType()->isVoidTy())
        EnumerateValue(I);
    }
  }
}

/**
 * Print the given basic block.
 * 
 * @param block  the basic block
 */
void JVMWriter::printBasicBlock(const BasicBlock *block) {
    printLabel(getLabelName(block));
    if (trace) {
        if (block->hasName()) {
            std::string n = block->getName();
            printTrc(n + ":");
        }
    }
    for(BasicBlock::const_iterator i = block->begin(), e = block->end();
        i != e; i++) {
        instNum++;
        
        if (trace)
            printSimpleInstruction(".line", utostr(trcLineNum+1));
        else if(debug >= 1)
            printSimpleInstruction(".line", utostr(instNum));
            
        if(debug >= 3 || trace) {
            // print current instruction as comment
            // note that this block of code significantly increases
            // code generation time
            std::string str;
            raw_string_ostream ss(str); ss << *i;
            ss.flush();
            if (trace)
                printTrc(str);
            if (debug >= 3) {
                std::string::size_type pos = 0;
                while((pos = str.find("\n", pos)) != std::string::npos)
                    str.replace(pos++, 1, "\n;");
                out << ';' << str << '\n';
            }
        }
        
        if(i->getOpcode() == Instruction::PHI)
            // don't handle phi instruction in current block
            continue;
        printInstruction(i);
        if(i->getType() != Type::getVoidTy(block->getContext())
        && i->getOpcode() != Instruction::Invoke)
            // instruction doesn't return anything, or is an invoke instruction
            // which handles storing the return value itself
            printValueStore(i);
    }
}

// Test whether two basic blocks have equivalent behaviour.
int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
                                       const BasicBlock *BBR) const {
  BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
  BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();

  do {
    bool needToCmpOperands = true;
    if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
      return Res;
    if (needToCmpOperands) {
      assert(InstL->getNumOperands() == InstR->getNumOperands());

      for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
        Value *OpL = InstL->getOperand(i);
        Value *OpR = InstR->getOperand(i);
        if (int Res = cmpValues(OpL, OpR))
          return Res;
        // cmpValues should ensure this is true.
        assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
      }
    }

    ++InstL;
    ++InstR;
  } while (InstL != InstLE && InstR != InstRE);

  if (InstL != InstLE && InstR == InstRE)
    return 1;
  if (InstL == InstLE && InstR != InstRE)
    return -1;
  return 0;
}

bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
  // This can be computed either by scanning the instructions in BB, or by
  // scanning the use list of this Value. Both lists can be very long, but
  // usually one is quite short.
  //
  // Scan both lists simultaneously until one is exhausted. This limits the
  // search to the shorter list.
  BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
  const_user_iterator UI = user_begin(), UE = user_end();
  for (; BI != BE && UI != UE; ++BI, ++UI) {
    // Scan basic block: Check if this Value is used by the instruction at BI.
    if (is_contained(BI->operands(), this))
      return true;
    // Scan use list: Check if the use at UI is in BB.
    const auto *User = dyn_cast<Instruction>(*UI);
    if (User && User->getParent() == BB)
      return true;
  }
  return false;
}

void HeterotbbTransform::copy_function (Function* NF, Function* F) {
    DenseMap<const Value*, Value *> ValueMap;
    // Get the names of the parameters for old function
    for(Function::arg_iterator FI = F->arg_begin(), FE=F->arg_end(), DI=NF->arg_begin(); FE!=FI; ++FI,++DI) {
        DI->setName(FI->getName());
        ValueMap[FI]=DI;
    }

    for (Function::const_iterator BI=F->begin(),BE = F->end(); BI != BE; ++BI) {
        const BasicBlock &FBB = *BI;
        BasicBlock *NFBB = BasicBlock::Create(FBB.getContext(), "", NF);
        ValueMap[&FBB] = NFBB;
        if (FBB.hasName()) {
            NFBB->setName(FBB.getName());
            //DEBUG(dbgs()<<NFBB->getName()<<"\n");
        }
        for (BasicBlock::const_iterator II = FBB.begin(), IE = FBB.end(); II != IE; ++II) {
            Instruction *NFInst = II->clone(/*F->getContext()*/);
            if (II->hasName()) NFInst->setName(II->getName());
            const Instruction *FInst = &(*II);
            rewrite_instruction((Instruction *)FInst, NFInst, ValueMap);
            NFBB->getInstList().push_back(NFInst);
            ValueMap[II] = NFInst;
        }
    }
    // Remap the instructions again to take care of forward jumps
    for (Function::iterator BB = NF->begin(), BE=NF->end(); BB != BE; ++ BB) {
        for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) {
            int opIdx = 0;
            //DEBUG(dbgs()<<*II<<"\n");
            for (User::op_iterator i = II->op_begin(), e = II->op_end(); i != e; ++i, opIdx++) {
                Value *V = *i;
                if (ValueMap[V] != NULL) {
                    II->setOperand(opIdx, ValueMap[V]);
                }
            }
        }
    }
    //NF->dump();

}

/// Test if the given instruction is in a position to be optimized
/// with a tail-call. This roughly means that it's in a block with
/// a return and there's nothing that needs to be scheduled
/// between it and the return.
///
/// This function only tests target-independent requirements.
bool llvm::isInTailCallPosition(ImmutableCallSite CS, const TargetMachine &TM) {
  const Instruction *I = CS.getInstruction();
  const BasicBlock *ExitBB = I->getParent();
  const Instruction *Term = ExitBB->getTerminator();
  const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);

  // The block must end in a return statement or unreachable.
  //
  // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
  // an unreachable, for now. The way tailcall optimization is currently
  // implemented means it will add an epilogue followed by a jump. That is
  // not profitable. Also, if the callee is a special function (e.g.
  // longjmp on x86), it can end up causing miscompilation that has not
  // been fully understood.
  if (!Ret &&
      (!TM.Options.GuaranteedTailCallOpt || !isa<UnreachableInst>(Term)))
    return false;

  // If I will have a chain, make sure no other instruction that will have a
  // chain interposes between I and the return.
  if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
      !isSafeToSpeculativelyExecute(I))
    for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
      if (&*BBI == I)
        break;
      // Debug info intrinsics do not get in the way of tail call optimization.
      if (isa<DbgInfoIntrinsic>(BBI))
        continue;
      // A lifetime end intrinsic should not stop tail call optimization.
      if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
        if (II->getIntrinsicID() == Intrinsic::lifetime_end)
          continue;
      if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
          !isSafeToSpeculativelyExecute(&*BBI))
        return false;
    }

  const Function *F = ExitBB->getParent();
  return returnTypeIsEligibleForTailCall(
      F, I, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering());
}

/// isUsedInBasicBlock - Return true if this value is used in the specified
/// basic block.
bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
  // Start by scanning over the instructions looking for a use before we start
  // the expensive use iteration.
  unsigned MaxBlockSize = 3;
  for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
    if (std::find(I->op_begin(), I->op_end(), this) != I->op_end())
      return true;
    if (MaxBlockSize-- == 0) // If the block is larger fall back to use_iterator
      break;
  }

  if (MaxBlockSize != 0) // We scanned the entire block and found no use.
    return false;

  for (const_use_iterator I = use_begin(), E = use_end(); I != E; ++I) {
    const Instruction *User = dyn_cast<Instruction>(*I);
    if (User && User->getParent() == BB)
      return true;
  }
  return false;
}

void ValueEnumerator::incorporateFunction(const Function &F) {
  NumModuleValues = Values.size();

  // Adding function arguments to the value table.
  for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
      I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
            isa<InlineAsm>(*OI))
          EnumerateValue(*OI);
      }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  // Add the function's parameter attributes so they are available for use in
  // the function's instruction.
  EnumerateAttributes(F.getAttributes());

  FirstInstID = Values.size();

  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (I->getType() != Type::getVoidTy(F.getContext()))
        EnumerateValue(I);
    }
  }
}

void ValueEnumerator::incorporateFunction(const Function &F) {
  InstructionCount = 0;
  NumModuleValues = Values.size();
  NumModuleMDs = MDs.size();

  // Adding function arguments to the value table.
  for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
       I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
            isa<InlineAsm>(*OI))
          EnumerateValue(*OI);
      }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  // Add the function's parameter attributes so they are available for use in
  // the function's instruction.
  EnumerateAttributes(F.getAttributes());

  FirstInstID = Values.size();

  SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if (auto *MD = dyn_cast<MetadataAsValue>(&*OI))
          if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
            // Enumerate metadata after the instructions they might refer to.
            FnLocalMDVector.push_back(Local);
      }

      if (!I->getType()->isVoidTy())
        EnumerateValue(I);
    }
  }

  // Add all of the function-local metadata.
  for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
    EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
}

// Print instruction location, falls back to printing function location,
// (and LLVM instruction if specified).
void printLocation(const llvm::Instruction *I, bool fallback) {
  const BasicBlock *BB = I->getParent();
  bool approx = false;
  BasicBlock::const_iterator It = I;
  do {
    BasicBlock::const_iterator ItB = BB->begin();
    while (It != ItB) {
      if (MDNode *N = It->getMetadata("dbg")) {
        DILocation Loc(N);
        errs() << /*Loc.getDirectory() << "/" <<*/ Loc.getFilename()
          << ":" << Loc.getLineNumber();
        if (unsigned Col = Loc.getColumnNumber()) {
          errs() << ":" << Col;
        }
        if (approx)
          errs() << "(?)";
        errs() << ": ";
        DIScope Scope = Loc.getScope();
        while (Scope.isLexicalBlock()) {
          DILexicalBlock LB(Scope.getNode());
          Scope = LB.getContext();
        }
        if (Scope.isSubprogram()) {
          DISubprogram SP(Scope.getNode());
          errs() << "in function '" << SP.getDisplayName() << "': ";
        }
        return;
      }
      approx = true;
      --It;
    }
    BB = BB->getUniquePredecessor();
    if (BB)
      It = BB->end();
  } while (BB);
  printLocation(I->getParent()->getParent());
  if (fallback)
    errs() << *I << ":\n";
}

/// WriteFunction - Emit a function body to the module stream.
static void WriteFunction(const Function &F, NaClValueEnumerator &VE,
                          NaClBitstreamWriter &Stream) {
  Stream.EnterSubblock(naclbitc::FUNCTION_BLOCK_ID);
  VE.incorporateFunction(F);

  SmallVector<unsigned, 64> Vals;

  // Emit the number of basic blocks, so the reader can create them ahead of
  // time.
  Vals.push_back(VE.getBasicBlocks().size());
  Stream.EmitRecord(naclbitc::FUNC_CODE_DECLAREBLOCKS, Vals);
  Vals.clear();

  // If there are function-local constants, emit them now.
  unsigned CstStart, CstEnd;
  VE.getFunctionConstantRange(CstStart, CstEnd);
  WriteConstants(CstStart, CstEnd, VE, Stream);

  // Keep a running idea of what the instruction ID is.
  unsigned InstID = CstEnd;

  // Finally, emit all the instructions, in order.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
         I != E; ++I) {
      if (WriteInstruction(*I, InstID, VE, Stream, Vals) &&
          !I->getType()->isVoidTy())
        ++InstID;
    }

  // Emit names for instructions etc.
  if (PNaClAllowLocalSymbolTables)
    WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);

  VE.purgeFunction();
  Stream.ExitBlock();
}

/// NaClValueEnumerator - Enumerate module-level information.
NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
  // Create map for counting frequency of types, and set field
  // TypeCountMap accordingly.  Note: Pointer field TypeCountMap is
  // used to deal with the fact that types are added through various
  // method calls in this routine. Rather than pass it as an argument,
  // we use a field. The field is a pointer so that the memory
  // footprint of count_map can be garbage collected when this
  // constructor completes.
  TypeCountMapType count_map;
  TypeCountMap = &count_map;

  IntPtrType = IntegerType::get(M->getContext(), PNaClIntPtrTypeBitSize);

  // Enumerate the functions. Note: We do this before global
  // variables, so that global variable initializations can refer to
  // the functions without a forward reference.
  for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
    EnumerateValue(I);
  }

  // Enumerate the global variables.
  FirstGlobalVarID = Values.size();
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    EnumerateValue(I);
  NumGlobalVarIDs = Values.size() - FirstGlobalVarID;

  // Enumerate the aliases.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I);

  // Remember what is the cutoff between globalvalue's and other constants.
  unsigned FirstConstant = Values.size();

  // Skip global variable initializers since they are handled within
  // WriteGlobalVars of file NaClBitcodeWriter.cpp.

  // Enumerate the aliasees.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I->getAliasee());

  // Insert constants that are named at module level into the slot
  // pool so that the module symbol table can refer to them...
  EnumerateValueSymbolTable(M->getValueSymbolTable());

  // Enumerate types used by function bodies and argument lists.
  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {

    for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
         I != E; ++I)
      EnumerateType(I->getType());

    for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
      for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
        // Don't generate types for elided pointer casts!
        if (IsElidedCast(I))
          continue;

        if (const SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
          // Handle switch instruction specially, so that we don't
          // write out unnecessary vector/array types used to model case
          // selectors.
          EnumerateOperandType(SI->getCondition());
        } else {
          for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
               OI != E; ++OI) {
            EnumerateOperandType(*OI);
          }
        }
        EnumerateType(I->getType());
      }
  }

  // Optimized type indicies to put "common" expected types in with small
  // indices.
  OptimizeTypes(M);
  TypeCountMap = NULL;

  // Optimize constant ordering.
  OptimizeConstants(FirstConstant, Values.size());
}

/// Test if the given instruction is in a position to be optimized
/// with a tail-call. This roughly means that it's in a block with
/// a return and there's nothing that needs to be scheduled
/// between it and the return.
///
/// This function only tests target-independent requirements.
bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attribute CalleeRetAttr,
                                const TargetLowering &TLI) {
  const Instruction *I = CS.getInstruction();
  const BasicBlock *ExitBB = I->getParent();
  const TerminatorInst *Term = ExitBB->getTerminator();
  const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);

  // The block must end in a return statement or unreachable.
  //
  // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
  // an unreachable, for now. The way tailcall optimization is currently
  // implemented means it will add an epilogue followed by a jump. That is
  // not profitable. Also, if the callee is a special function (e.g.
  // longjmp on x86), it can end up causing miscompilation that has not
  // been fully understood.
  if (!Ret &&
      (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt ||
       !isa<UnreachableInst>(Term)))
    return false;

  // If I will have a chain, make sure no other instruction that will have a
  // chain interposes between I and the return.
  if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
      !isSafeToSpeculativelyExecute(I))
    for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ;
         --BBI) {
      if (&*BBI == I)
        break;
      // Debug info intrinsics do not get in the way of tail call optimization.
      if (isa<DbgInfoIntrinsic>(BBI))
        continue;
      if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
          !isSafeToSpeculativelyExecute(BBI))
        return false;
    }

  // If the block ends with a void return or unreachable, it doesn't matter
  // what the call's return type is.
  if (!Ret || Ret->getNumOperands() == 0) return true;

  // If the return value is undef, it doesn't matter what the call's
  // return type is.
  if (isa<UndefValue>(Ret->getOperand(0))) return true;

  // Conservatively require the attributes of the call to match those of
  // the return. Ignore noalias because it doesn't affect the call sequence.
  const Function *F = ExitBB->getParent();
  Attribute CallerRetAttr = F->getAttributes().getRetAttributes();
  if (AttrBuilder(CalleeRetAttr).removeAttribute(Attribute::NoAlias) !=
      AttrBuilder(CallerRetAttr).removeAttribute(Attribute::NoAlias))
    return false;

  // It's not safe to eliminate the sign / zero extension of the return value.
  if (CallerRetAttr.hasAttribute(Attribute::ZExt) ||
      CallerRetAttr.hasAttribute(Attribute::SExt))
    return false;

  // Otherwise, make sure the unmodified return value of I is the return value.
  // We handle two cases: multiple return values + scalars.
  Value *RetVal = Ret->getOperand(0);
  if (!isa<InsertValueInst>(RetVal) || !isa<StructType>(RetVal->getType()))
    // Handle scalars first.
    return getNoopInput(Ret->getOperand(0), TLI) == I;
  
  // If this is an aggregate return, look through the insert/extract values and
  // see if each is transparent.
  for (unsigned i = 0, e =cast<StructType>(RetVal->getType())->getNumElements();
       i != e; ++i) {
    const Value *InScalar = FindInsertedValue(RetVal, i);
    if (InScalar == 0) return false;
    InScalar = getNoopInput(InScalar, TLI);
    
    // If the scalar value being inserted is an extractvalue of the right index
    // from the call, then everything is good.
    const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(InScalar);
    if (EVI == 0 || EVI->getOperand(0) != I || EVI->getNumIndices() != 1 ||
        EVI->getIndices()[0] != i)
      return false;
  }
  
  return true;
}

/// analyzeFunction - Fill in the current structure with information gleaned
/// from the specified function.
void InlineCostAnalyzer::FunctionInfo::analyzeFunction(Function *F) {
  unsigned NumInsts = 0, NumBlocks = 0, NumVectorInsts = 0;

  // Look at the size of the callee.  Each basic block counts as 20 units, and
  // each instruction counts as 5.
  for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator II = BB->begin(), E = BB->end();
         II != E; ++II) {
      if (isa<PHINode>(II)) continue;           // PHI nodes don't count.

      // Special handling for calls.
      if (isa<CallInst>(II) || isa<InvokeInst>(II)) {
        if (isa<DbgInfoIntrinsic>(II))
          continue;  // Debug intrinsics don't count as size.
        
        CallSite CS = CallSite::get(const_cast<Instruction*>(&*II));
        
        // If this function contains a call to setjmp or _setjmp, never inline
        // it.  This is a hack because we depend on the user marking their local
        // variables as volatile if they are live across a setjmp call, and they
        // probably won't do this in callers.
        if (Function *F = CS.getCalledFunction())
          if (F->isDeclaration() && 
              (F->isName("setjmp") || F->isName("_setjmp"))) {
            NeverInline = true;
            return;
          }

        // Calls often compile into many machine instructions.  Bump up their
        // cost to reflect this.
        if (!isa<IntrinsicInst>(II))
          NumInsts += 5;
      }
      
      if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
        if (!AI->isStaticAlloca())
          this->usesDynamicAlloca = true;
      }

      if (isa<ExtractElementInst>(II) || isa<VectorType>(II->getType()))
        ++NumVectorInsts; 
      
      // Noop casts, including ptr <-> int,  don't count.
      if (const CastInst *CI = dyn_cast<CastInst>(II)) {
        if (CI->isLosslessCast() || isa<IntToPtrInst>(CI) || 
            isa<PtrToIntInst>(CI))
          continue;
      } else if (const GetElementPtrInst *GEPI =
                 dyn_cast<GetElementPtrInst>(II)) {
        // If a GEP has all constant indices, it will probably be folded with
        // a load/store.
        bool AllConstant = true;
        for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
          if (!isa<ConstantInt>(GEPI->getOperand(i))) {
            AllConstant = false;
            break;
          }
        if (AllConstant) continue;
      }
      
      ++NumInsts;
    }

    ++NumBlocks;
  }

  this->NumBlocks      = NumBlocks;
  this->NumInsts       = NumInsts;
  this->NumVectorInsts = NumVectorInsts;

  // Check out all of the arguments to the function, figuring out how much
  // code can be eliminated if one of the arguments is a constant.
  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
    ArgumentWeights.push_back(ArgInfo(CountCodeReductionForConstant(I),
                                      CountCodeReductionForAlloca(I)));
}

/// Test if the given instruction is in a position to be optimized
/// with a tail-call. This roughly means that it's in a block with
/// a return and there's nothing that needs to be scheduled
/// between it and the return.
///
/// This function only tests target-independent requirements.
bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr,
                                const TargetLowering &TLI) {
  const Instruction *I = CS.getInstruction();
  const BasicBlock *ExitBB = I->getParent();
  const TerminatorInst *Term = ExitBB->getTerminator();
  const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);

  // The block must end in a return statement or unreachable.
  //
  // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
  // an unreachable, for now. The way tailcall optimization is currently
  // implemented means it will add an epilogue followed by a jump. That is
  // not profitable. Also, if the callee is a special function (e.g.
  // longjmp on x86), it can end up causing miscompilation that has not
  // been fully understood.
  if (!Ret &&
      (!GuaranteedTailCallOpt || !isa<UnreachableInst>(Term))) return false;

  // If I will have a chain, make sure no other instruction that will have a
  // chain interposes between I and the return.
  if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
      !I->isSafeToSpeculativelyExecute())
    for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ;
         --BBI) {
      if (&*BBI == I)
        break;
      // Debug info intrinsics do not get in the way of tail call optimization.
      if (isa<DbgInfoIntrinsic>(BBI))
        continue;
      if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
          !BBI->isSafeToSpeculativelyExecute())
        return false;
    }

  // If the block ends with a void return or unreachable, it doesn't matter
  // what the call's return type is.
  if (!Ret || Ret->getNumOperands() == 0) return true;

  // If the return value is undef, it doesn't matter what the call's
  // return type is.
  if (isa<UndefValue>(Ret->getOperand(0))) return true;

  // Conservatively require the attributes of the call to match those of
  // the return. Ignore noalias because it doesn't affect the call sequence.
  const Function *F = ExitBB->getParent();
  unsigned CallerRetAttr = F->getAttributes().getRetAttributes();
  if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias)
    return false;

  // It's not safe to eliminate the sign / zero extension of the return value.
  if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt))
    return false;

  // Otherwise, make sure the unmodified return value of I is the return value.
  for (const Instruction *U = dyn_cast<Instruction>(Ret->getOperand(0)); ;
       U = dyn_cast<Instruction>(U->getOperand(0))) {
    if (!U)
      return false;
    if (!U->hasOneUse())
      return false;
    if (U == I)
      break;
    // Check for a truly no-op truncate.
    if (isa<TruncInst>(U) &&
        TLI.isTruncateFree(U->getOperand(0)->getType(), U->getType()))
      continue;
    // Check for a truly no-op bitcast.
    if (isa<BitCastInst>(U) &&
        (U->getOperand(0)->getType() == U->getType() ||
         (U->getOperand(0)->getType()->isPointerTy() &&
          U->getType()->isPointerTy())))
      continue;
    // Otherwise it's not a true no-op.
    return false;
  }

  return true;
}

/// CloneBlock - The specified block is found to be reachable, clone it and
/// anything that it can reach.
void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
                                       std::vector<const BasicBlock*> &ToClone){
  TrackingVH<Value> &BBEntry = VMap[BB];

  // Have we already cloned this block?
  if (BBEntry) return;
  
  // Nope, clone it now.
  BasicBlock *NewBB;
  BBEntry = NewBB = BasicBlock::Create(BB->getContext());
  if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);

  bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  
  // Loop over all instructions, and copy them over, DCE'ing as we go.  This
  // loop doesn't include the terminator.
  for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
       II != IE; ++II) {
    // If this instruction constant folds, don't bother cloning the instruction,
    // instead, just add the constant to the value map.
    if (Constant *C = ConstantFoldMappedInstruction(II)) {
      VMap[II] = C;
      continue;
    }

    Instruction *NewInst = II->clone();
    if (II->hasName())
      NewInst->setName(II->getName()+NameSuffix);
    NewBB->getInstList().push_back(NewInst);
    VMap[II] = NewInst;                // Add instruction map to value.
    
    hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
    if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
      if (isa<ConstantInt>(AI->getArraySize()))
        hasStaticAllocas = true;
      else
        hasDynamicAllocas = true;
    }
  }
  
  // Finally, clone over the terminator.
  const TerminatorInst *OldTI = BB->getTerminator();
  bool TerminatorDone = false;
  if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
    if (BI->isConditional()) {
      // If the condition was a known constant in the callee...
      ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
      // Or is a known constant in the caller...
      if (Cond == 0) {
        Value *V = VMap[BI->getCondition()];
        Cond = dyn_cast_or_null<ConstantInt>(V);
      }

      // Constant fold to uncond branch!
      if (Cond) {
        BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
        VMap[OldTI] = BranchInst::Create(Dest, NewBB);
        ToClone.push_back(Dest);
        TerminatorDone = true;
      }
    }
  } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
    // If switching on a value known constant in the caller.
    ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
    if (Cond == 0) { // Or known constant after constant prop in the callee...
      Value *V = VMap[SI->getCondition()];
      Cond = dyn_cast_or_null<ConstantInt>(V);
    }
    if (Cond) {     // Constant fold to uncond branch!
      BasicBlock *Dest = SI->getSuccessor(SI->findCaseValue(Cond));
      VMap[OldTI] = BranchInst::Create(Dest, NewBB);
      ToClone.push_back(Dest);
      TerminatorDone = true;
    }
  }
  
  if (!TerminatorDone) {
    Instruction *NewInst = OldTI->clone();
    if (OldTI->hasName())
      NewInst->setName(OldTI->getName()+NameSuffix);
    NewBB->getInstList().push_back(NewInst);
    VMap[OldTI] = NewInst;             // Add instruction map to value.
    
    // Recursively clone any reachable successor blocks.
    const TerminatorInst *TI = BB->getTerminator();
    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
      ToClone.push_back(TI->getSuccessor(i));
  }
  
  if (CodeInfo) {
    CodeInfo->ContainsCalls          |= hasCalls;
    CodeInfo->ContainsUnwinds        |= isa<UnwindInst>(OldTI);
    CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
    CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas && 
      BB != &BB->getParent()->front();
  }
  
  if (ReturnInst *RI = dyn_cast<ReturnInst>(NewBB->