/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
/// old header into the preheader.  If there were uses of the values produced by
/// these instruction that were outside of the loop, we have to insert PHI nodes
/// to merge the two values.  Do this now.
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                            BasicBlock *OrigPreheader,
                                            ValueToValueMapTy &ValueMap) {
  // Remove PHI node entries that are no longer live.
  BasicBlock::iterator I, E = OrigHeader->end();
  for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
    PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));

  // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
  // as necessary.
  SSAUpdater SSA;
  for (I = OrigHeader->begin(); I != E; ++I) {
    Value *OrigHeaderVal = I;

    // If there are no uses of the value (e.g. because it returns void), there
    // is nothing to rewrite.
    if (OrigHeaderVal->use_empty())
      continue;

    Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal];

    // The value now exits in two versions: the initial value in the preheader
    // and the loop "next" value in the original header.
    SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
    SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
    SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);

    // Visit each use of the OrigHeader instruction.
    for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
         UE = OrigHeaderVal->use_end(); UI != UE; ) {
      // Grab the use before incrementing the iterator.
      Use &U = UI.getUse();

      // Increment the iterator before removing the use from the list.
      ++UI;

      // SSAUpdater can't handle a non-PHI use in the same block as an
      // earlier def. We can easily handle those cases manually.
      Instruction *UserInst = cast<Instruction>(U.getUser());
      if (!isa<PHINode>(UserInst)) {
        BasicBlock *UserBB = UserInst->getParent();

        // The original users in the OrigHeader are already using the
        // original definitions.
        if (UserBB == OrigHeader)
          continue;

        // Users in the OrigPreHeader need to use the value to which the
        // original definitions are mapped.
        if (UserBB == OrigPreheader) {
          U = OrigPreHeaderVal;
          continue;
        }
      }

      // Anything else can be handled by SSAUpdater.
      SSA.RewriteUse(U);
    }
  }
}

/// If there's a single exit block, sink any loop-invariant values that
/// were defined in the preheader but not used inside the loop into the
/// exit block to reduce register pressure in the loop.
void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
  BasicBlock *ExitBlock = L->getExitBlock();
  if (!ExitBlock) return;

  BasicBlock *Preheader = L->getLoopPreheader();
  if (!Preheader) return;

  Instruction *InsertPt = ExitBlock->getFirstNonPHI();
  BasicBlock::iterator I = Preheader->getTerminator();
  while (I != Preheader->begin()) {
    --I;
    // New instructions were inserted at the end of the preheader.
    if (isa<PHINode>(I))
      break;
    // Don't move instructions which might have side effects, since the side
    // effects need to complete before instructions inside the loop.  Also
    // don't move instructions which might read memory, since the loop may
    // modify memory. Note that it's okay if the instruction might have
    // undefined behavior: LoopSimplify guarantees that the preheader
    // dominates the exit block.
    if (I->mayHaveSideEffects() || I->mayReadFromMemory())
      continue;
    // Don't sink static AllocaInsts out of the entry block, which would
    // turn them into dynamic allocas!
    if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
      if (AI->isStaticAlloca())
        continue;
    // Determine if there is a use in or before the loop (direct or
    // otherwise).
    bool UsedInLoop = false;
    for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
         UI != UE; ++UI) {
      BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
      if (PHINode *P = dyn_cast<PHINode>(UI)) {
        unsigned i =
          PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
        UseBB = P->getIncomingBlock(i);
      }
      if (UseBB == Preheader || L->contains(UseBB)) {
        UsedInLoop = true;
        break;
      }
    }
    // If there is, the def must remain in the preheader.
    if (UsedInLoop)
      continue;
    // Otherwise, sink it to the exit block.
    Instruction *ToMove = I;
    bool Done = false;
    if (I != Preheader->begin())
      --I;
    else
      Done = true;
    ToMove->moveBefore(InsertPt);
    if (Done)
      break;
    InsertPt = ToMove;
  }
}

static Value::use_iterator skipToNextUser(Value::use_iterator I,
                                          Value::use_iterator End) {
  User *CurUser = I->getUser();
  ++I;

  while (I != End && I->getUser() == CurUser)
    ++I;

  return I;
}

void detail::PtrUseVisitorBase::enqueueUsers(Instruction &I) {
  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
       UI != UE; ++UI) {
    if (VisitedUses.insert(&UI.getUse())) {
      UseToVisit NewU = {
        UseToVisit::UseAndIsOffsetKnownPair(&UI.getUse(), IsOffsetKnown),
        Offset
      };
      Worklist.push_back(llvm_move(NewU));
    }
  }
}

/// WriteThunk - Replace G with a simple tail call to bitcast(F). Also replace
/// direct uses of G with bitcast(F). Deletes G.
void MergeFunctions::WriteThunk(Function *F, Function *G) const {
  if (!G->mayBeOverridden()) {
    // Redirect direct callers of G to F.
    Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
    for (Value::use_iterator UI = G->use_begin(), UE = G->use_end();
         UI != UE;) {
      Value::use_iterator TheIter = UI;
      ++UI;
      CallSite CS(*TheIter);
      if (CS && CS.isCallee(TheIter))
        TheIter.getUse().set(BitcastF);
    }
  }

  // If G was internal then we may have replaced all uses of G with F. If so,
  // stop here and delete G. There's no need for a thunk.
  if (G->hasLocalLinkage() && G->use_empty()) {
    G->eraseFromParent();
    return;
  }

  Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
                                    G->getParent());
  BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
  IRBuilder<false> Builder(BB);

  SmallVector<Value *, 16> Args;
  unsigned i = 0;
  const FunctionType *FFTy = F->getFunctionType();
  for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
       AI != AE; ++AI) {
    Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i)));
    ++i;
  }

  CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end());
  CI->setTailCall();
  CI->setCallingConv(F->getCallingConv());
  if (NewG->getReturnType()->isVoidTy()) {
    Builder.CreateRetVoid();
  } else {
    Builder.CreateRet(Builder.CreateBitCast(CI, NewG->getReturnType()));
  }

  NewG->copyAttributesFrom(G);
  NewG->takeName(G);
  G->replaceAllUsesWith(NewG);
  G->eraseFromParent();

  DEBUG(dbgs() << "WriteThunk: " << NewG->getName() << '\n');
  ++NumThunksWritten;
}

// Replace direct callers of Old with New.
void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
  Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
  for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
       UI != UE;) {
    Value::use_iterator TheIter = UI;
    ++UI;
    CallSite CS(*TheIter);
    if (CS && CS.isCallee(TheIter)) {
      remove(CS.getInstruction()->getParent()->getParent());
      TheIter.getUse().set(BitcastNew);
    }
  }
}

/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce
/// the number of virtual registers that must be created and coalesced.  This is
/// a clear win except on targets with multiple condition code registers
///  (PowerPC), where it might lose; some adjustment may be wanted there.
///
/// Return true if any changes are made.
static bool OptimizeCmpExpression(CmpInst *CI) {
  BasicBlock *DefBB = CI->getParent();

  /// InsertedCmp - Only insert a cmp in each block once.
  DenseMap<BasicBlock*, CmpInst*> InsertedCmps;

  bool MadeChange = false;
  for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
       UI != E; ) {
    Use &TheUse = UI.getUse();
    Instruction *User = cast<Instruction>(*UI);

    // Preincrement use iterator so we don't invalidate it.
    ++UI;

    // Don't bother for PHI nodes.
    if (isa<PHINode>(User))
      continue;

    // Figure out which BB this cmp is used in.
    BasicBlock *UserBB = User->getParent();

    // If this user is in the same block as the cmp, don't change the cmp.
    if (UserBB == DefBB) continue;

    // If we have already inserted a cmp into this block, use it.
    CmpInst *&InsertedCmp = InsertedCmps[UserBB];

    if (!InsertedCmp) {
      BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI();

      InsertedCmp =
        CmpInst::Create(CI->getOpcode(),
                        CI->getPredicate(),  CI->getOperand(0),
                        CI->getOperand(1), "", InsertPt);
      MadeChange = true;
    }

    // Replace a use of the cmp with a use of the new cmp.
    TheUse = InsertedCmp;
    ++NumCmpUses;
  }

  // If we removed all uses, nuke the cmp.
  if (CI->use_empty())
    CI->eraseFromParent();

  return MadeChange;
}

// hasLifetimeMarkers - Check whether the given alloca already has
// lifetime.start or lifetime.end intrinsics.
static bool hasLifetimeMarkers(AllocaInst *AI) {
  Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext());
  if (AI->getType() == Int8PtrTy)
    return isUsedByLifetimeMarker(AI);

  // Do a scan to find all the casts to i8*.
  for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); I != E;
       ++I) {
    if (I->getType() != Int8PtrTy) continue;
    if (I->stripPointerCasts() != AI) continue;
    if (isUsedByLifetimeMarker(*I))
      return true;
  }
  return false;
}

void BBCloner::UpdateSSA(Function &F) {
  DominatorTree &DT = getAnalysis<DominatorTree>();
  // The function has been greatly modified since the beginning.
  DT.runOnFunction(F);

  vector<pair<Instruction *, Use *> > ToResolve;
  for (ValueToValueMapTy::iterator I = CloneMap.begin();
       I != CloneMap.end();
       ++I) {
    Value *Key = const_cast<Value *>(I->first);
    if (Instruction *OldIns = dyn_cast<Instruction>(Key)) {
      for (Value::use_iterator UI = OldIns->use_begin();
           UI != OldIns->use_end();
           ++UI) {
        if (Instruction *User = dyn_cast<Instruction>(*UI)) {
          if (!DT.dominates(OldIns, User))
            ToResolve.push_back(make_pair(OldIns, &UI.getUse()));
        }
      }
      Instruction *NewIns = cast<Instruction>(I->second);
      for (Value::use_iterator UI = NewIns->use_begin();
           UI != NewIns->use_end();
           ++UI) {
        if (Instruction *User = dyn_cast<Instruction>(*UI)) {
          if (!DT.dominates(NewIns, User)) {
            // Use OldIns intentionally.
            ToResolve.push_back(make_pair(OldIns, &UI.getUse()));
          }
        }
      }
    }
  }

  for (size_t i = 0; i < ToResolve.size(); ) {
    Instruction *OldIns = ToResolve[i].first;
    Instruction *NewIns = cast<Instruction>(CloneMap.lookup(OldIns));
    SSAUpdater SU;
    SU.Initialize(OldIns->getType(), OldIns->getName());
    SU.AddAvailableValue(OldIns->getParent(), OldIns);
    SU.AddAvailableValue(NewIns->getParent(), NewIns);
    size_t j = i;
    while (j < ToResolve.size() && ToResolve[j].first == ToResolve[i].first) {
      SU.RewriteUse(*ToResolve[j].second);
      ++j;
    }
    i = j;
  }
}

/// FindAllMemoryUses - Recursively walk all the uses of I until we find a
/// memory use.  If we find an obviously non-foldable instruction, return true.
/// Add the ultimately found memory instructions to MemoryUses.
static bool FindAllMemoryUses(Instruction *I,
                SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
                              SmallPtrSet<Instruction*, 16> &ConsideredInsts,
                              const TargetLowering &TLI) {
  // If we already considered this instruction, we're done.
  if (!ConsideredInsts.insert(I))
    return false;
  
  // If this is an obviously unfoldable instruction, bail out.
  if (!MightBeFoldableInst(I))
    return true;

  // Loop over all the uses, recursively processing them.
  for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
       UI != E; ++UI) {
    User *U = *UI;

    if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
      MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo()));
      continue;
    }
    
    if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
      unsigned opNo = UI.getOperandNo();
      if (opNo == 0) return true; // Storing addr, not into addr.
      MemoryUses.push_back(std::make_pair(SI, opNo));
      continue;
    }
    
    if (CallInst *CI = dyn_cast<CallInst>(U)) {
      InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
      if (!IA) return true;
      
      // If this is a memory operand, we're cool, otherwise bail out.
      if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
        return true;
      continue;
    }
    
    if (FindAllMemoryUses(cast<Instruction>(U), MemoryUses, ConsideredInsts,
                          TLI))
      return true;
  }

  return false;
}

void ARM64PromoteConstant::
  computeInsertionPoints(Constant *Val,
                         InsertionPointsPerFunc &InsPtsPerFunc) {
    DEBUG(dbgs() << "** Compute insertion points **\n");
  for (Value::use_iterator UseIt = Val->use_begin(), EndUseIt = Val->use_end();
       UseIt != EndUseIt; ++UseIt) {
    // If the user is not an Instruction, we cannot modify it
    if (!isa<Instruction>(*UseIt))
      continue;
    
    // Filter out uses that should not be converted
    if (!shouldConvertUse(Val, cast<Instruction>(*UseIt), UseIt.getOperandNo()))
      continue;
    
    DEBUG(dbgs() << "Considered use, opidx " << UseIt.getOperandNo() << ":\n");
    DEBUG(UseIt->print(dbgs()));
    DEBUG(dbgs() << '\n');
    
    Instruction *InsertionPoint = findInsertionPoint(UseIt);
    
    DEBUG(dbgs() << "Considered insertion point:\n");
    DEBUG(InsertionPoint->print(dbgs()));
    DEBUG(dbgs() << '\n');

    // Check if the current insertion point is useless, i.e., it is dominated
    // by another one.
    InsertionPoints &InsertPts =
      InsPtsPerFunc[InsertionPoint->getParent()->getParent()];
    if (isDominated(InsertionPoint, UseIt, InsertPts))
      continue;
    // This insertion point is useful, check if we can merge some insertion
    // point in a common dominator or if NewPt dominates an existing one.
    if (tryAndMerge(InsertionPoint, UseIt, InsertPts))
      continue;
    
    DEBUG(dbgs() << "Keep considered insertion point\n");
    
    // It is definitely useful by its own
    InsertPts[InsertionPoint].push_back(UseIt);
  }
}

// For each instruction used by the value, remove() the function that contains
// the instruction. This should happen right before a call to RAUW.
void MergeFunctions::removeUsers(Value *V) {
  std::vector<Value *> Worklist;
  Worklist.push_back(V);
  while (!Worklist.empty()) {
    Value *V = Worklist.back();
    Worklist.pop_back();

    for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
         UI != UE; ++UI) {
      Use &U = UI.getUse();
      if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
        remove(I->getParent()->getParent());
      } else if (isa<GlobalValue>(U.getUser())) {
        // do nothing
      } else if (Constant *C = dyn_cast<Constant>(U.getUser())) {
        for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end();
             CUI != CUE; ++CUI)
          Worklist.push_back(*CUI);
      }
    }
  }
}

bool HeterotbbTransform::runOnModule(Module &M) {

    bool localChange = true;
    TD = getAnalysisIfAvailable<DataLayout>();
    //hetero_f_const = NULL;
    rewrite_CPP(M);

#if 0
    Function *offload_func = M.getFunction("offload");
    for (Value::use_iterator i = offload_func->use_begin(), e = offload_func->use_end(); i != e; ++i) {
        Instruction *call;
        DEBUG(dbgs() << "Next _offload function:");
        i->dump();
        if ((call = dyn_cast<InvokeInst>(*i)) || (call = dyn_cast<CallInst>(*i))) {
            CallSite CI(cast<Instruction>(call));
            CI->dump();
        }
    }
#endif
    //M.dump();
    return localChange;
}

/// AllUsesDominatedByBlock - Return true if all uses of the specified value
/// occur in blocks dominated by the specified block.
bool Sinking::AllUsesDominatedByBlock(Instruction *Inst,
                                      BasicBlock *BB) const {
  // Ignoring debug uses is necessary so debug info doesn't affect the code.
  // This may leave a referencing dbg_value in the original block, before
  // the definition of the vreg.  Dwarf generator handles this although the
  // user might not get the right info at runtime.
  for (Value::use_iterator I = Inst->use_begin(),
       E = Inst->use_end(); I != E; ++I) {
    // Determine the block of the use.
    Instruction *UseInst = cast<Instruction>(*I);
    BasicBlock *UseBlock = UseInst->getParent();
    if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
      // PHI nodes use the operand in the predecessor block, not the block with
      // the PHI.
      unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo());
      UseBlock = PN->getIncomingBlock(Num);
    }
    // Check that it dominates.
    if (!DT->dominates(BB, UseBlock))
      return false;
  }
  return true;
}

/// scanForInterest - This function decides which arguments would be worth
/// specializing on.
void PartSpec::scanForInterest(Function& F, InterestingArgVector& args) {
  for(Function::arg_iterator ii = F.arg_begin(), ee = F.arg_end();
      ii != ee; ++ii) {
    for(Value::use_iterator ui = ii->use_begin(), ue = ii->use_end();
        ui != ue; ++ui) {

      bool interesting = false;
      User *U = *ui;
      if (isa<CmpInst>(U)) interesting = true;
      else if (isa<CallInst>(U))
        interesting = ui->getOperand(0) == ii;
      else if (isa<InvokeInst>(U))
        interesting = ui->getOperand(0) == ii;
      else if (isa<SwitchInst>(U)) interesting = true;
      else if (isa<BranchInst>(U)) interesting = true;

      if (interesting) {
        args.push_back(std::distance(F.arg_begin(), ii));
        break;
      }
    }
  }
}

/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
/// sink it into user blocks to reduce the number of virtual
/// registers that must be created and coalesced.
///
/// Return true if any changes are made.
///
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI) {
    // If this is a noop copy,
    EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
    EVT DstVT = TLI.getValueType(CI->getType());

    // This is an fp<->int conversion?
    if (SrcVT.isInteger() != DstVT.isInteger())
        return false;

    // If this is an extension, it will be a zero or sign extension, which
    // isn't a noop.
    if (SrcVT.bitsLT(DstVT)) return false;

    // If these values will be promoted, find out what they will be promoted
    // to.  This helps us consider truncates on PPC as noop copies when they
    // are.
    if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
            TargetLowering::TypePromoteInteger)
        SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
    if (TLI.getTypeAction(CI->getContext(), DstVT) ==
            TargetLowering::TypePromoteInteger)
        DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);

    // If, after promotion, these are the same types, this is a noop copy.
    if (SrcVT != DstVT)
        return false;

    BasicBlock *DefBB = CI->getParent();

    /// InsertedCasts - Only insert a cast in each block once.
    DenseMap<BasicBlock*, CastInst*> InsertedCasts;

    bool MadeChange = false;
    for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
            UI != E; ) {
        Use &TheUse = UI.getUse();
        Instruction *User = cast<Instruction>(*UI);

        // Figure out which BB this cast is used in.  For PHI's this is the
        // appropriate predecessor block.
        BasicBlock *UserBB = User->getParent();
        if (PHINode *PN = dyn_cast<PHINode>(User)) {
            UserBB = PN->getIncomingBlock(UI);
        }

        // Preincrement use iterator so we don't invalidate it.
        ++UI;

        // If this user is in the same block as the cast, don't change the cast.
        if (UserBB == DefBB) continue;

        // If we have already inserted a cast into this block, use it.
        CastInst *&InsertedCast = InsertedCasts[UserBB];

        if (!InsertedCast) {
            BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
            InsertedCast =
                CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
                                 InsertPt);
            MadeChange = true;
        }

        // Replace a use of the cast with a use of the new cast.
        TheUse = InsertedCast;
        ++NumCastUses;
    }

    // If we removed all uses, nuke the cast.
    if (CI->use_empty()) {
        CI->eraseFromParent();
        MadeChange = true;
    }

    return MadeChange;
}

bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
    BasicBlock *DefBB = I->getParent();

    // If the result of a {s|z}ext and its source are both live out, rewrite all
    // other uses of the source with result of extension.
    Value *Src = I->getOperand(0);
    if (Src->hasOneUse())
        return false;

    // Only do this xform if truncating is free.
    if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
        return false;

    // Only safe to perform the optimization if the source is also defined in
    // this block.
    if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
        return false;

    bool DefIsLiveOut = false;
    for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
            UI != E; ++UI) {
        Instruction *User = cast<Instruction>(*UI);

        // Figure out which BB this ext is used in.
        BasicBlock *UserBB = User->getParent();
        if (UserBB == DefBB) continue;
        DefIsLiveOut = true;
        break;
    }
    if (!DefIsLiveOut)
        return false;

    // Make sure non of the uses are PHI nodes.
    for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
            UI != E; ++UI) {
        Instruction *User = cast<Instruction>(*UI);
        BasicBlock *UserBB = User->getParent();
        if (UserBB == DefBB) continue;
        // Be conservative. We don't want this xform to end up introducing
        // reloads just before load / store instructions.
        if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User))
            return false;
    }

    // InsertedTruncs - Only insert one trunc in each block once.
    DenseMap<BasicBlock*, Instruction*> InsertedTruncs;

    bool MadeChange = false;
    for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
            UI != E; ++UI) {
        Use &TheUse = UI.getUse();
        Instruction *User = cast<Instruction>(*UI);

        // Figure out which BB this ext is used in.
        BasicBlock *UserBB = User->getParent();
        if (UserBB == DefBB) continue;

        // Both src and def are live in this block. Rewrite the use.
        Instruction *&InsertedTrunc = InsertedTruncs[UserBB];

        if (!InsertedTrunc) {
            BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
            InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
        }

        // Replace a use of the {s|z}ext source with a use of the result.
        TheUse = InsertedTrunc;
        ++NumExtUses;
        MadeChange = true;
    }

    return MadeChange;
}

//
// Method: runOnModule()
//
// Description:
//  Entry point for this LLVM pass.  Search for functions which could be called
//  indirectly and create clones for them which are only called by direct
//  calls.
//
// Inputs:
//  M - A reference to the LLVM module to transform.
//
// Outputs:
//  M - The transformed LLVM module.
//
// Return value:
//  true  - The module was modified.
//  false - The module was not modified.
//
bool
IndClone::runOnModule(Module& M) {
  // Set of functions to clone
  std::vector<Function*> toClone;

  //
  // Check all of the functions in the module.  If the function could be called
  // by an indirect function call, add it to our worklist of functions to
  // clone.
  //
  for (Module::iterator I = M.begin(); I != M.end(); ++I) {
    // Flag whether the function should be cloned
    bool pleaseCloneTheFunction = false;

    //
    // Only clone functions which are defined and cannot be replaced by another
    // function by the linker.
    //
    if (!I->isDeclaration() && !I->mayBeOverridden()) {
      for (Value::use_iterator ui = I->use_begin(), ue = I->use_end();
          ui != ue; ++ui) {
        if (!isa<CallInst>(*ui) && !isa<InvokeInst>(*ui)) {
          if(!ui->use_empty())
          //
          // If this function is used for anything other than a direct function
          // call, then we want to clone it.
          //
          pleaseCloneTheFunction = true;
        } else {
          //
          // This is a call instruction, but hold up ranger!  We need to make
          // sure that the function isn't passed as an argument to *another*
          // function.  That would make the function usable in an indirect
          // function call.
          //
          for (unsigned index = 1; index < ui->getNumOperands(); ++index) {
            if (ui->getOperand(index)->stripPointerCasts() == I) {
              pleaseCloneTheFunction = true;
              break;
            }
          }
        }

        //
        // If we've discovered that the function could be used by an indirect
        // call site, schedule it for cloning.
        //
        if (pleaseCloneTheFunction) {
          toClone.push_back(I);
          break;
        }
      }
    }
  }

  //
  // Update the statistics on the number of functions we'll be cloning.
  // We only update the statistic if we want to clone one or more functions;
  // due to the magic of how statistics work, avoiding assignment prevents it
  // from needlessly showing up.
  //
  if (toClone.size())
    numCloned += toClone.size();

  //
  // Go through the worklist and clone each function.  After cloning a
  // function, change all direct calls to use the clone instead of using the
  // original function.
  //
  for (unsigned index = 0; index < toClone.size(); ++index) {
    //
    // Clone the function and give it a name indicating that it is a clone to
    // be used for direct function calls.
    //
    Function * Original = toClone[index];
    Function* DirectF = CloneFunction(Original);
    DirectF->setName(Original->getName() + "_DIRECT");

    //
    // Make the clone internal; external code can use the original function.
    //
    DirectF->setLinkage(GlobalValue::InternalLinkage);
//.........这里部分代码省略.........

/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
/// split the critical edge.  This will update DominatorTree and
/// DominatorFrontier information if it is available, thus calling this pass
/// will not invalidate either of them. This returns the new block if the edge
/// was split, null otherwise.
///
/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
/// specified successor will be merged into the same critical edge block.  
/// This is most commonly interesting with switch instructions, which may 
/// have many edges to any one destination.  This ensures that all edges to that
/// dest go to one block instead of each going to a different block, but isn't 
/// the standard definition of a "critical edge".
///
/// It is invalid to call this function on a critical edge that starts at an
/// IndirectBrInst.  Splitting these edges will almost always create an invalid
/// program because the address of the new block won't be the one that is jumped
/// to.
///
BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
                                    Pass *P, bool MergeIdenticalEdges) {
  if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
  
  assert(!isa<IndirectBrInst>(TI) &&
         "Cannot split critical edge from IndirectBrInst");
  
  BasicBlock *TIBB = TI->getParent();
  BasicBlock *DestBB = TI->getSuccessor(SuccNum);

  // Create a new basic block, linking it into the CFG.
  BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
                      TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
  // Create our unconditional branch.
  BranchInst::Create(DestBB, NewBB);

  // Branch to the new block, breaking the edge.
  TI->setSuccessor(SuccNum, NewBB);

  // Insert the block into the function... right after the block TI lives in.
  Function &F = *TIBB->getParent();
  Function::iterator FBBI = TIBB;
  F.getBasicBlockList().insert(++FBBI, NewBB);
  
  // If there are any PHI nodes in DestBB, we need to update them so that they
  // merge incoming values from NewBB instead of from TIBB.
  if (PHINode *APHI = dyn_cast<PHINode>(DestBB->begin())) {
    // This conceptually does:
    //  foreach (PHINode *PN in DestBB)
    //    PN->setIncomingBlock(PN->getIncomingBlock(TIBB), NewBB);
    // but is optimized for two cases.
    
    if (APHI->getNumIncomingValues() <= 8) {  // Small # preds case.
      unsigned BBIdx = 0;
      for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
        // We no longer enter through TIBB, now we come in through NewBB.
        // Revector exactly one entry in the PHI node that used to come from
        // TIBB to come from NewBB.
        PHINode *PN = cast<PHINode>(I);
        
        // Reuse the previous value of BBIdx if it lines up.  In cases where we
        // have multiple phi nodes with *lots* of predecessors, this is a speed
        // win because we don't have to scan the PHI looking for TIBB.  This
        // happens because the BB list of PHI nodes are usually in the same
        // order.
        if (PN->getIncomingBlock(BBIdx) != TIBB)
          BBIdx = PN->getBasicBlockIndex(TIBB);
        PN->setIncomingBlock(BBIdx, NewBB);
      }
    } else {
      // However, the foreach loop is slow for blocks with lots of predecessors
      // because PHINode::getIncomingBlock is O(n) in # preds.  Instead, walk
      // the user list of TIBB to find the PHI nodes.
      SmallPtrSet<PHINode*, 16> UpdatedPHIs;
    
      for (Value::use_iterator UI = TIBB->use_begin(), E = TIBB->use_end();
           UI != E; ) {
        Value::use_iterator Use = UI++;
        if (PHINode *PN = dyn_cast<PHINode>(Use)) {
          // Remove one entry from each PHI.
          if (PN->getParent() == DestBB && UpdatedPHIs.insert(PN))
            PN->setOperand(Use.getOperandNo(), NewBB);
        }
      }
    }
  }
   
  // If there are any other edges from TIBB to DestBB, update those to go
  // through the split block, making those edges non-critical as well (and
  // reducing the number of phi entries in the DestBB if relevant).
  if (MergeIdenticalEdges) {
    for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
      if (TI->getSuccessor(i) != DestBB) continue;
      
      // Remove an entry for TIBB from DestBB phi nodes.
      DestBB->removePredecessor(TIBB);
      
      // We found another edge to DestBB, go to NewBB instead.
      TI->setSuccessor(i, NewBB);
    }
  }
  
//.........这里部分代码省略.........

//.........这里部分代码省略.........
      CurAST->deleteValue(&I);
      // If I has users in unreachable blocks, eliminate.
      // If I is not void type then replaceAllUsesWith undef.
      // This allows ValueHandlers and custom metadata to adjust itself.
      if (!I.use_empty())
        I.replaceAllUsesWith(UndefValue::get(I.getType()));
      I.eraseFromParent();
    } else {
      // Move the instruction to the start of the exit block, after any PHI
      // nodes in it.
      I.moveBefore(ExitBlocks[0]->getFirstInsertionPt());

      // This instruction is no longer in the AST for the current loop, because
      // we just sunk it out of the loop.  If we just sunk it into an outer
      // loop, we will rediscover the operation when we process it.
      CurAST->deleteValue(&I);
    }
    return;
  }

  if (ExitBlocks.empty()) {
    // The instruction is actually dead if there ARE NO exit blocks.
    CurAST->deleteValue(&I);
    // If I has users in unreachable blocks, eliminate.
    // If I is not void type then replaceAllUsesWith undef.
    // This allows ValueHandlers and custom metadata to adjust itself.
    if (!I.use_empty())
      I.replaceAllUsesWith(UndefValue::get(I.getType()));
    I.eraseFromParent();
    return;
  }

  // Otherwise, if we have multiple exits, use the SSAUpdater to do all of the
  // hard work of inserting PHI nodes as necessary.
  SmallVector<PHINode*, 8> NewPHIs;
  SSAUpdater SSA(&NewPHIs);

  if (!I.use_empty())
    SSA.Initialize(I.getType(), I.getName());

  // Insert a copy of the instruction in each exit block of the loop that is
  // dominated by the instruction.  Each exit block is known to only be in the
  // ExitBlocks list once.
  BasicBlock *InstOrigBB = I.getParent();
  unsigned NumInserted = 0;

  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
    BasicBlock *ExitBlock = ExitBlocks[i];

    if (!DT->dominates(InstOrigBB, ExitBlock))
      continue;

    // Insert the code after the last PHI node.
    BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();

    // If this is the first exit block processed, just move the original
    // instruction, otherwise clone the original instruction and insert
    // the copy.
    Instruction *New;
    if (NumInserted++ == 0) {
      I.moveBefore(InsertPt);
      New = &I;
    } else {
      New = I.clone();
      if (!I.getName().empty())
        New->setName(I.getName()+".le");
      ExitBlock->getInstList().insert(InsertPt, New);
    }

    // Now that we have inserted the instruction, inform SSAUpdater.
    if (!I.use_empty())
      SSA.AddAvailableValue(ExitBlock, New);
  }

  // If the instruction doesn't dominate any exit blocks, it must be dead.
  if (NumInserted == 0) {
    CurAST->deleteValue(&I);
    if (!I.use_empty())
      I.replaceAllUsesWith(UndefValue::get(I.getType()));
    I.eraseFromParent();
    return;
  }

  // Next, rewrite uses of the instruction, inserting PHI nodes as needed.
  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ) {
    // Grab the use before incrementing the iterator.
    Use &U = UI.getUse();
    // Increment the itera