// Propagate existing explicit probabilities from either profile data or
// 'expect' intrinsic processing.
bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
  TerminatorInst *TI = BB->getTerminator();
  if (TI->getNumSuccessors() == 1)
    return false;
  if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
    return false;

  MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
  if (!WeightsNode)
    return false;

  // Ensure there are weights for all of the successors. Note that the first
  // operand to the metadata node is a name, not a weight.
  if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
    return false;

  // Build up the final weights that will be used in a temporary buffer, but
  // don't add them until all weihts are present. Each weight value is clamped
  // to [1, getMaxWeightFor(BB)].
  uint32_t WeightLimit = getMaxWeightFor(BB);
  SmallVector<uint32_t, 2> Weights;
  Weights.reserve(TI->getNumSuccessors());
  for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
    ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i));
    if (!Weight)
      return false;
    Weights.push_back(
      std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit)));
  }
  assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
    setEdgeWeight(BB, TI->getSuccessor(i), Weights[i]);

  return true;
}

///////////////////
// NEW begin
///////////////////
// check dynamic pair satisfy anti-dependency
bool idenRegion::isAntiDepPair(LoadInst *Load, StoreInst *Store) {
    // perform a DFS to check if store is after load
    typedef std::pair<BasicBlock *, BasicBlock::iterator> WorkItem;
    SmallVector<WorkItem, 8> Worklist;
    SmallPtrSet<BasicBlock *, 32> Visited;

    BasicBlock *LoadBB = Load->getParent();
    Worklist.push_back(WorkItem(LoadBB, Load));

    do {
        BasicBlock *BB;
        BasicBlock::iterator I, E;
        tie(BB, I) = Worklist.pop_back_val();

        errs() << "... On BB " << BB->getName() << "\n";
        
        // If we revisited LoadBB, we scan to Load to complete cycle
        // Otherwise we end at BB->end()
        E = (BB == LoadBB && I == BB->begin()) ? Load : BB->end();
        // errs() << "... Last instruction on current BB is " << getLocator(*E) << "\n";

        // iterate throught BB to check if Load instruction exist in the BB
        while (I != E) {
            // errs() << "...... Inst: " << getLocator(*I) << "\n";
            if (isa<StoreInst>(I) && dyn_cast<StoreInst>(I) == Store) {
                return true;
            }
            ++I;
        }
        
        // get current BB's succesor
        TerminatorInst* ti = BB->getTerminator();
        int numSuccesor = ti->getNumSuccessors();
        for (int i = 0; i < numSuccesor; i++) {
            BasicBlock* nextSuc = ti->getSuccessor(i);
            // don't count backedge
            if (Visited.insert(nextSuc) && !DT->dominates(nextSuc, BB)) {
                Worklist.push_back(WorkItem(nextSuc, nextSuc->begin()));
            }
        }
    } while(!Worklist.empty());

    return false;
}

// Propagate existing explicit probabilities from either profile data or
// 'expect' intrinsic processing.
bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) {
    TerminatorInst *TI = BB->getTerminator();
    if (TI->getNumSuccessors() == 1)
        return false;
    if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
        return false;

    MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
    if (!WeightsNode)
        return false;

    // Check that the number of successors is manageable.
    assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");

    // Ensure there are weights for all of the successors. Note that the first
    // operand to the metadata node is a name, not a weight.
    if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
        return false;

    // Build up the final weights that will be used in a temporary buffer.
    // Compute the sum of all weights to later decide whether they need to
    // be scaled to fit in 32 bits.
    uint64_t WeightSum = 0;
    SmallVector<uint32_t, 2> Weights;
    Weights.reserve(TI->getNumSuccessors());
    for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
        ConstantInt *Weight =
            mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
        if (!Weight)
            return false;
        assert(Weight->getValue().getActiveBits() <= 32 &&
               "Too many bits for uint32_t");
        Weights.push_back(Weight->getZExtValue());
        WeightSum += Weights.back();
    }
    assert(Weights.size() == TI->getNumSuccessors() && "Checked above");

    // If the sum of weights does not fit in 32 bits, scale every weight down
    // accordingly.
    uint64_t ScalingFactor =
        (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;

    WeightSum = 0;
    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
        uint32_t W = Weights[i] / ScalingFactor;
        WeightSum += W;
        setEdgeWeight(BB, i, W);
    }
    assert(WeightSum <= UINT32_MAX &&
           "Expected weights to scale down to 32 bits");

    return true;
}

void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
  TerminatorInst *TI = getTerminator();
  if (!TI)
    // Cope with being called on a BasicBlock that doesn't have a terminator
    // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
    return;
  for (BasicBlock *Succ : TI->successors()) {
    // N.B. Succ might not be a complete BasicBlock, so don't assume
    // that it ends with a non-phi instruction.
    for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
      PHINode *PN = dyn_cast<PHINode>(II);
      if (!PN)
        break;
      int i;
      while ((i = PN->getBasicBlockIndex(this)) >= 0)
        PN->setIncomingBlock(i, New);
    }
  }
}

void Loop::setLoopID(MDNode *LoopID) const {
  assert(LoopID && "Loop ID should not be null");
  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");

  if (isLoopSimplifyForm()) {
    getLoopLatch()->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
    return;
  }

  BasicBlock *H = getHeader();
  for (BasicBlock *BB : this->blocks()) {
    TerminatorInst *TI = BB->getTerminator();
    for (BasicBlock *Successor : TI->successors()) {
      if (Successor == H)
        TI->setMetadata(LLVMContext::MD_loop, LoopID);
    }
  }
}

/// MatchLoopHeaderHeuristic - Predict a successor that is a loop header or
/// a loop pre-header and does not post-dominate will be taken.
/// @returns a Prediction that is a pair in which the first element is the
/// successor taken, and the second the successor not taken.
Prediction BranchHeuristicsInfo::MatchLoopHeaderHeuristic(BasicBlock *root)
                                                          const {
  bool matched = false;
  Prediction pred;

  // Last instruction of basic block.
  TerminatorInst *TI = root->getTerminator();

  // Basic block successors. True and False branches.
  BasicBlock *trueSuccessor = TI->getSuccessor(0);
  BasicBlock *falseSuccessor = TI->getSuccessor(1);

  // Get the most inner loop in which the true successor basic block is in.
  Loop *loop = LI->getLoopFor(trueSuccessor);

  // Check if exists a loop, the true branch successor is a loop header or a
  // loop pre-header, and does not post dominate.
  if (loop && (trueSuccessor == loop->getHeader() ||
      trueSuccessor == loop->getLoopPreheader()) &&
      !PDT->dominates(trueSuccessor, root)) {
    matched = true;
    pred = std::make_pair(trueSuccessor, falseSuccessor);
  }

  // Get the most inner loop in which the false successor basic block is in.
  loop = LI->getLoopFor(falseSuccessor);

  // Check if exists a loop,
  // the false branch successor is a loop header or a loop pre-header, and
  // does not post dominate.
  if (loop && (falseSuccessor == loop->getHeader() ||
      falseSuccessor == loop->getLoopPreheader()) &&
      !PDT->dominates(falseSuccessor, root)) {
    // If the heuristic matches both branches, predict none.
    if (matched)
      return empty;

    matched = true;
    pred = std::make_pair(falseSuccessor, trueSuccessor);
  }

  return (matched ? pred : empty);
}

/// MatchPointerHeuristic - Predict that a comparison of a pointer against
/// null or of two pointers will fail.
/// @returns a Prediction that is a pair in which the first element is the
/// successor taken, and the second the successor not taken.
Prediction BranchHeuristicsInfo::MatchPointerHeuristic(BasicBlock *root) const {
  // Last instruction of basic block.
  TerminatorInst *TI = root->getTerminator();

  // Basic block successors. True and False branches.
  BasicBlock *trueSuccessor = TI->getSuccessor(0);
  BasicBlock *falseSuccessor = TI->getSuccessor(1);

  // Is the last instruction a Branch Instruction?
  BranchInst *BI = dyn_cast<BranchInst>(TI);
  if (!BI || !BI->isConditional())
    return empty;

  // Conditional instruction.
  Value *cond = BI->getCondition();

  // Pointer comparisons are integer comparisons.
  ICmpInst *II = dyn_cast<ICmpInst>(cond);
  if (!II)
    return empty;

  // An integer comparison has always two operands.
  Value *operand1 = II->getOperand(0);
  Value *operand2 = II->getOperand(1);

  // Obtain the type of comparison.
  enum ICmpInst::Predicate signedPred = II->getSignedPredicate();

  // The heuristic states that it must be compared against null,
  // but in LLVM, null is also a PointerType, so it only requires
  // to test if there is a comparison between two pointers.
  if (signedPred == ICmpInst::ICMP_EQ &&
      isa<PointerType>(operand1->getType()) && // NULL is a pointer type too
      isa<PointerType>(operand2->getType())) { // NULL is a pointer type too
    return std::make_pair(falseSuccessor, trueSuccessor);
  } else if (signedPred != ICmpInst::ICMP_EQ &&
             isa<PointerType>(operand1->getType()) &&
             isa<PointerType>(operand2->getType())) {
    return std::make_pair(trueSuccessor, falseSuccessor);
  }

  return empty;
}

void Loop::setLoopID(MDNode *LoopID) const {
  assert(LoopID && "Loop ID should not be null");
  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");

  if (isLoopSimplifyForm()) {
    getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID);
    return;
  }

  BasicBlock *H = getHeader();
  for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) {
    TerminatorInst *TI = (*I)->getTerminator();
    for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) {
      if (TI->getSuccessor(i) == H)
        TI->setMetadata(LoopMDName, LoopID);
    }
  }
}

TerminatorInst *
llvm::SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
                                bool Unreachable, MDNode *BranchWeights,
                                DominatorTree *DT, LoopInfo *LI) {
  BasicBlock *Head = SplitBefore->getParent();
  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
  TerminatorInst *HeadOldTerm = Head->getTerminator();
  LLVMContext &C = Head->getContext();
  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
  TerminatorInst *CheckTerm;
  if (Unreachable)
    CheckTerm = new UnreachableInst(C, ThenBlock);
  else
    CheckTerm = BranchInst::Create(Tail, ThenBlock);
  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
  BranchInst *HeadNewTerm =
    BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);

  if (DT) {
    if (DomTreeNode *OldNode = DT->getNode(Head)) {
      std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());

      DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
      for (DomTreeNode *Child : Children)
        DT->changeImmediateDominator(Child, NewNode);

      // Head dominates ThenBlock.
      DT->addNewBlock(ThenBlock, Head);
    }
  }

  if (LI) {
    if (Loop *L = LI->getLoopFor(Head)) {
      L->addBasicBlockToLoop(ThenBlock, *LI);
      L->addBasicBlockToLoop(Tail, *LI);
    }
  }

  return CheckTerm;
}

/// matchEdges - Link every profile counter with an edge.
unsigned ProfileMetadataLoaderPass::matchEdges(Module &M, ProfileData &PB,
                                               ArrayRef<unsigned> Counters) {
  if (Counters.size() == 0) return 0;

  unsigned ReadCount = 0;

  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
    if (F->isDeclaration()) continue;
    DEBUG(dbgs() << "Loading edges in '" << F->getName() << "'\n");
    readEdge(ReadCount++, PB, PB.getEdge(0, &F->getEntryBlock()), Counters);
    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
      TerminatorInst *TI = BB->getTerminator();
      for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
        readEdge(ReadCount++, PB, PB.getEdge(BB,TI->getSuccessor(s)),
                 Counters);
      }
    }
  }

  return ReadCount;
}

void hammock::findIR (BasicBlock *bBOring, BasicBlock *bBSuss, PostDominatorTree &PD) {

	TerminatorInst *ti = bBSuss->getTerminator();


	if (bBlocks.count(bBSuss)>0) {
		return;
	}

	//Mark BasicBlock
	bBlocks.insert(bBSuss);

	//If the basic block is a posdominator and is not the start basic block, just return
	if (PD.dominates(bBSuss, bBOring) && bBSuss != bBOring) {
		return;
	}else { //Advance the flooding
		//If there is successor, go there
		for (unsigned int i=0; i<ti->getNumSuccessors(); i++) {
			findIR (bBOring, ti->getSuccessor(i), PD);
		}
	}

}

// In this pass we look for GEP and cast instructions that are used
// across basic blocks and rewrite them to improve basic-block-at-a-time
// selection.
bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) {
  bool MadeChange = false;

  // Split all critical edges where the dest block has a PHI.
  if (CriticalEdgeSplit) {
    TerminatorInst *BBTI = BB.getTerminator();
    if (BBTI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(BBTI)) {
      for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) {
        BasicBlock *SuccBB = BBTI->getSuccessor(i);
        if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true))
          SplitEdgeNicely(BBTI, i, BackEdges, this);
      }
    }
  }

  SunkAddrs.clear();

  CurInstIterator = BB.begin();
  for (BasicBlock::iterator E = BB.end(); CurInstIterator != E; )
    MadeChange |= OptimizeInst(CurInstIterator++);

  return MadeChange;
}

void AddressSanitizer::instrumentAddress(AsanFunctionContext &AFC,
                                         Instruction *OrigIns,
                                         IRBuilder<> &IRB, Value *Addr,
                                         uint32_t TypeSize, bool IsWrite) {
  Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);

  Type *ShadowTy  = IntegerType::get(
      *C, std::max(8U, TypeSize >> MappingScale));
  Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);
  Value *ShadowPtr = memToShadow(AddrLong, IRB);
  Value *CmpVal = Constant::getNullValue(ShadowTy);
  Value *ShadowValue = IRB.CreateLoad(
      IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy));

  Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal);
  size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
  size_t Granularity = 1 << MappingScale;
  TerminatorInst *CrashTerm = 0;

  if (ClAlwaysSlowPath || (TypeSize < 8 * Granularity)) {
    TerminatorInst *CheckTerm = splitBlockAndInsertIfThen(Cmp, false);
    assert(dyn_cast<BranchInst>(CheckTerm)->isUnconditional());
    BasicBlock *NextBB = CheckTerm->getSuccessor(0);
    IRB.SetInsertPoint(CheckTerm);
    Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize);
    BasicBlock *CrashBlock = BasicBlock::Create(*C, "", &AFC.F, NextBB);
    CrashTerm = new UnreachableInst(*C, CrashBlock);
    BranchInst *NewTerm = BranchInst::Create(CrashBlock, NextBB, Cmp2);
    ReplaceInstWithInst(CheckTerm, NewTerm);
  } else {
    CrashTerm = splitBlockAndInsertIfThen(Cmp, true);
  }

  Instruction *Crash =
      generateCrashCode(CrashTerm, AddrLong, IsWrite, AccessSizeIndex);
  Crash->setDebugLoc(OrigIns->getDebugLoc());
}

/// MatchLoopBranchHeuristic - Predict as taken an edge back to a loop's
/// head. Predict as not taken an edge exiting a loop.
/// @returns a Prediction that is a pair in which the first element is the
/// successor taken, and the second the successor not taken.
Prediction BranchHeuristicsInfo::MatchLoopBranchHeuristic(BasicBlock *root)
                                                          const {
  bool matched = false;
  Prediction pred;

  // Last instruction of basic block.
  TerminatorInst *TI = root->getTerminator();

  // Basic block successors. True and False branches.
  BasicBlock *trueSuccessor = TI->getSuccessor(0);
  BasicBlock *falseSuccessor = TI->getSuccessor(1);

  // True and false branch edges.
  Edge trueEdge = std::make_pair(root, trueSuccessor);
  Edge falseEdge = std::make_pair(root, falseSuccessor);

  // If the true branch is a back edge to a loop's head or the false branch is
  // an exit edge, match the heuristic.
  if ((BPI->isBackEdge(trueEdge) && LI->isLoopHeader(trueSuccessor)) ||
      BPI->isExitEdge(falseEdge)) {
    matched = true;
    pred = std::make_pair(trueSuccessor, falseSuccessor);
  }

  // Check the opposite situation, the other branch.
  if ((BPI->isBackEdge(falseEdge) && LI->isLoopHeader(falseSuccessor)) ||
      BPI->isExitEdge(trueEdge)) {
    // If the heuristic matches both branches, predict none.
    if (matched)
      return empty;

    matched = true;
    pred = std::make_pair(falseSuccessor, trueSuccessor);
  }

  return (matched ? pred : empty);
}

void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) {
  assert((pred_begin(BB) == pred_end(BB) ||
         // Can delete self loop.
         BB->getSinglePredecessor() == BB) && "Block is not dead!");
  TerminatorInst *BBTerm = BB->getTerminator();
  std::vector<DominatorTree::UpdateType> Updates;

  // Loop through all of our successors and make sure they know that one
  // of their predecessors is going away.
  if (DDT)
    Updates.reserve(BBTerm->getNumSuccessors());
  for (BasicBlock *Succ : BBTerm->successors()) {
    Succ->removePredecessor(BB);
    if (DDT)
      Updates.push_back({DominatorTree::Delete, BB, Succ});
  }

  // Zap all the instructions in the block.
  while (!BB->empty()) {
    Instruction &I = BB->back();
    // If this instruction is used, replace uses with an arbitrary value.
    // Because control flow can't get here, we don't care what we replace the
    // value with.  Note that since this block is unreachable, and all values
    // contained within it must dominate their uses, that all uses will
    // eventually be removed (they are themselves dead).
    if (!I.use_empty())
      I.replaceAllUsesWith(UndefValue::get(I.getType()));
    BB->getInstList().pop_back();
  }

  if (DDT) {
    DDT->applyUpdates(Updates);
    DDT->deleteBB(BB); // Deferred deletion of BB.
  } else {
    BB->eraseFromParent(); // Zap the block!
  }
}

void CheckInserter::insertCycleChecks(Function &F) {
  IdentifyBackEdges &IBE = getAnalysis<IdentifyBackEdges>();

  for (Function::iterator B1 = F.begin(); B1 != F.end(); ++B1) {
    TerminatorInst *TI = B1->getTerminator();
    for (unsigned j = 0; j < TI->getNumSuccessors(); ++j) {
      BasicBlock *B2 = TI->getSuccessor(j);
      unsigned BackEdgeID = IBE.getID(B1, B2);
      if (BackEdgeID != (unsigned)-1) {
        assert(BackEdgeID < MaxNumBackEdges);
        BasicBlock *BackEdgeBlock = BasicBlock::Create(
            F.getContext(),
            "backedge_" + B1->getName() + "_" + B2->getName(),
            &F);
        CallInst::Create(CycleCheck,
                         ConstantInt::get(IntType, BackEdgeID),
                         "",
                         BackEdgeBlock);
        // BackEdgeBlock -> B2
        // Fix the PHINodes in B2.
        BranchInst::Create(B2, BackEdgeBlock);
        for (BasicBlock::iterator I = B2->begin();
             B2->getFirstNonPHI() != I;
             ++I) {
          PHINode *PHI = cast<PHINode>(I);
          // Note: If B2 has multiple incoming edges from B1 (e.g. B1 terminates
          // with a SelectInst), its PHINodes must also have multiple incoming
          // edges from B1. However, after adding BackEdgeBlock and essentially
          // merging the multiple incoming edges from B1, there will be only one
          // edge from BackEdgeBlock to B2. Therefore, we need to remove the
          // redundant incoming edges from B2's PHINodes.
          bool FirstIncomingFromB1 = true;
          for (unsigned k = 0; k < PHI->getNumIncomingValues(); ++k) {
            if (PHI->getIncomingBlock(k) == B1) {
              if (FirstIncomingFromB1) {
                FirstIncomingFromB1 = false;
                PHI->setIncomingBlock(k, BackEdgeBlock);
              } else {
                PHI->removeIncomingValue(k, false);
                --k;
              }
            }
          }
        }
        // B1 -> BackEdgeBlock
        // There might be multiple back edges from B1 to B2. Need to replace
        // them all.
        for (unsigned j2 = j; j2 < TI->getNumSuccessors(); ++j2) {
          if (TI->getSuccessor(j2) == B2) {
            TI->setSuccessor(j2, BackEdgeBlock);
          }
        }
      }
    }
  }
}

//Return true if the subgraph denoted by bBlocks set attribute is a hammock graph
bool hammock::checkHammock (Function &F) {
	//For each basicBlock
	for (Function::iterator Fit = F.begin(), Fend = F.end(); Fit != Fend; ++Fit) {
		TerminatorInst *ti = Fit->getTerminator();

		if (bBlocks.count(Fit)==0) { //If it is out of subgraph
			//Check if some respective successor is marked
			for (unsigned int i=0; i<ti->getNumSuccessors(); i++) {
				if (bBlocks.count(ti->getSuccessor(i))>0) {
					return false;
				}
			}
		}else { /*//If it is in subgrah
			//Check if some respective successor is NOT marked
			for (unsigned int i=0; i<ti->getNumSuccessors(); i++) {
				if (bBlocks.count(ti->getSuccessor(i))==0) {
					return false;
				}
			}*/
		}
	}

	return true;
}

// visitCallInst - This converts all LLVM call instructions into invoke
// instructions. The except part of the invoke goes to the "LongJmpBlkPre"
// that grabs the exception and proceeds to determine if it's a longjmp
// exception or not.
void LowerSetJmp::visitCallInst(CallInst& CI)
{
  if (CI.getCalledFunction())
    if (!IsTransformableFunction(CI.getCalledFunction()->getName()) ||
        CI.getCalledFunction()->isIntrinsic()) return;

  BasicBlock* OldBB = CI.getParent();

  // If not reachable from a setjmp call, don't transform.
  if (!DFSBlocks.count(OldBB)) return;

  BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
  assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
  DFSBlocks.insert(NewBB);
  NewBB->setName("Call2Invoke");

  Function* Func = OldBB->getParent();

  // Construct the new "invoke" instruction.
  TerminatorInst* Term = OldBB->getTerminator();
  CallSite CS(&CI);
  std::vector<Value*> Params(CS.arg_begin(), CS.arg_end());
  InvokeInst* II =
    InvokeInst::Create(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
                       Params.begin(), Params.end(), CI.getName(), Term);
  II->setCallingConv(CI.getCallingConv());
  II->setAttributes(CI.getAttributes());

  // Replace the old call inst with the invoke inst and remove the call.
  CI.replaceAllUsesWith(II);
  CI.eraseFromParent();

  // The old terminator is useless now that we have the invoke inst.
  Term->eraseFromParent();
  ++CallsTransformed;
}

/// SplitEdge -  Split the edge connecting specified block. Pass P must
/// not be NULL.
BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
  unsigned SuccNum = GetSuccessorNumber(BB, Succ);

  // If this is a critical edge, let SplitCriticalEdge do it.
  TerminatorInst *LatchTerm = BB->getTerminator();
  if (SplitCriticalEdge(LatchTerm, SuccNum, P))
    return LatchTerm->getSuccessor(SuccNum);

  // If the edge isn't critical, then BB has a single successor or Succ has a
  // single pred.  Split the block.
  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
    // If the successor only has a single pred, split the top of the successor
    // block.
    assert(SP == BB && "CFG broken");
    SP = NULL;
    return SplitBlock(Succ, Succ->begin(), P);
  }

  // Otherwise, if BB has a single successor, split it at the bottom of the
  // block.
  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
         "Should have a single succ!");
  return SplitBlock(BB, BB->getTerminator(), P);
}

// Cleanly removes a terminator instruction.
void GNUstep::removeTerminator(BasicBlock *BB) {
    TerminatorInst *BBTerm = BB->getTerminator();

    // Remove the BB as a predecessor from all of  successors
    for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
        BBTerm->getSuccessor(i)->removePredecessor(BB);
    }

    BBTerm->replaceAllUsesWith(UndefValue::get(BBTerm->getType()));
    // Remove the terminator instruction itself.
    BBTerm->eraseFromParent();
}