lib/IR/BasicBlock.cpp - llvm-project/llvm - Git at Google

 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the BasicBlock class for the IR library.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/IR/BasicBlock.h"
 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
 #include <algorithm>

 using namespace llvm;

 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
   if (Function *F = getParent())
     return F->getValueSymbolTable();
   return nullptr;
 }

 LLVMContext &BasicBlock::getContext() const {
   return getType()->getContext();
 }

 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
   BB->invalidateOrders();
 }

 // Explicit instantiation of SymbolTableListTraits since some of the methods
 // are not in the public header file...
 template class llvm::SymbolTableListTraits<Instruction>;

 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
                        BasicBlock *InsertBefore)
   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {

   if (NewParent)
     insertInto(NewParent, InsertBefore);
   else
     assert(!InsertBefore &&
            "Cannot insert block before another block with no function!");

   setName(Name);
 }

 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
   assert(NewParent && "Expected a parent");
   assert(!Parent && "Already has a parent");

   if (InsertBefore)
     NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
   else
     NewParent->getBasicBlockList().push_back(this);
 }

 BasicBlock::~BasicBlock() {
   validateInstrOrdering();

   // If the address of the block is taken and it is being deleted (e.g. because
   // it is dead), this means that there is either a dangling constant expr
   // hanging off the block, or an undefined use of the block (source code
   // expecting the address of a label to keep the block alive even though there
   // is no indirect branch).  Handle these cases by zapping the BlockAddress
   // nodes.  There are no other possible uses at this point.
   if (hasAddressTaken()) {
     assert(!use_empty() && "There should be at least one blockaddress!");
     Constant *Replacement =
       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
     while (!use_empty()) {
       BlockAddress *BA = cast<BlockAddress>(user_back());
       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
                                                        BA->getType()));
       BA->destroyConstant();
     }
   }

   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
   dropAllReferences();
   InstList.clear();
 }

 void BasicBlock::setParent(Function *parent) {
   // Set Parent=parent, updating instruction symtab entries as appropriate.
   InstList.setSymTabObject(&Parent, parent);
 }

 iterator_range<filter_iterator<BasicBlock::const_iterator,
                                std::function<bool(const Instruction &)>>>
 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
   std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
     return !isa<DbgInfoIntrinsic>(I) &&
            !(SkipPseudoOp && isa<PseudoProbeInst>(I));
   };
   return make_filter_range(*this, Fn);
 }

 iterator_range<
     filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
   std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
     return !isa<DbgInfoIntrinsic>(I) &&
            !(SkipPseudoOp && isa<PseudoProbeInst>(I));
   };
   return make_filter_range(*this, Fn);
 }

 filter_iterator<BasicBlock::const_iterator,
                 std::function<bool(const Instruction &)>>::difference_type
 BasicBlock::sizeWithoutDebug() const {
   return std::distance(instructionsWithoutDebug().begin(),
                        instructionsWithoutDebug().end());
 }

 void BasicBlock::removeFromParent() {
   getParent()->getBasicBlockList().remove(getIterator());
 }

 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
   return getParent()->getBasicBlockList().erase(getIterator());
 }

 void BasicBlock::moveBefore(BasicBlock *MovePos) {
   MovePos->getParent()->getBasicBlockList().splice(
       MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
 }

 void BasicBlock::moveAfter(BasicBlock *MovePos) {
   MovePos->getParent()->getBasicBlockList().splice(
       ++MovePos->getIterator(), getParent()->getBasicBlockList(),
       getIterator());
 }

 const Module *BasicBlock::getModule() const {
   return getParent()->getParent();
 }

 const Instruction *BasicBlock::getTerminator() const {
   if (InstList.empty() || !InstList.back().isTerminator())
     return nullptr;
   return &InstList.back();
 }

 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
   if (InstList.empty())
     return nullptr;
   const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
   if (!RI || RI == &InstList.front())
     return nullptr;

   const Instruction *Prev = RI->getPrevNode();
   if (!Prev)
     return nullptr;

   if (Value *RV = RI->getReturnValue()) {
     if (RV != Prev)
       return nullptr;

     // Look through the optional bitcast.
     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
       RV = BI->getOperand(0);
       Prev = BI->getPrevNode();
       if (!Prev || RV != Prev)
         return nullptr;
     }
   }

   if (auto *CI = dyn_cast<CallInst>(Prev)) {
     if (CI->isMustTailCall())
       return CI;
   }
   return nullptr;
 }

 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
   if (InstList.empty())
     return nullptr;
   auto *RI = dyn_cast<ReturnInst>(&InstList.back());
   if (!RI || RI == &InstList.front())
     return nullptr;

   if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
     if (Function *F = CI->getCalledFunction())
       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
         return CI;

   return nullptr;
 }

 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
   const BasicBlock* BB = this;
   SmallPtrSet<const BasicBlock *, 8> Visited;
   Visited.insert(BB);
   while (auto *Succ = BB->getUniqueSuccessor()) {
     if (!Visited.insert(Succ).second)
       return nullptr;
     BB = Succ;
   }
   return BB->getTerminatingDeoptimizeCall();
 }

 const Instruction* BasicBlock::getFirstNonPHI() const {
   for (const Instruction &I : *this)
     if (!isa<PHINode>(I))
       return &I;
   return nullptr;
 }

 const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
   for (const Instruction &I : *this) {
     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
       continue;

     if (SkipPseudoOp && isa<PseudoProbeInst>(I))
       continue;

     return &I;
   }
   return nullptr;
 }

 const Instruction *
 BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
   for (const Instruction &I : *this) {
     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
       continue;

     if (I.isLifetimeStartOrEnd())
       continue;

     if (SkipPseudoOp && isa<PseudoProbeInst>(I))
       continue;

     return &I;
   }
   return nullptr;
 }

 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (!FirstNonPHI)
     return end();

   const_iterator InsertPt = FirstNonPHI->getIterator();
   if (InsertPt->isEHPad()) ++InsertPt;
   return InsertPt;
 }

 void BasicBlock::dropAllReferences() {
   for (Instruction &I : *this)
     I.dropAllReferences();
 }

 const BasicBlock *BasicBlock::getSinglePredecessor() const {
   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
   if (PI == E) return nullptr;         // No preds.
   const BasicBlock *ThePred = *PI;
   ++PI;
   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
 }

 const BasicBlock *BasicBlock::getUniquePredecessor() const {
   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
   if (PI == E) return nullptr; // No preds.
   const BasicBlock *PredBB = *PI;
   ++PI;
   for (;PI != E; ++PI) {
     if (*PI != PredBB)
       return nullptr;
     // The same predecessor appears multiple times in the predecessor list.
     // This is OK.
   }
   return PredBB;
 }

 bool BasicBlock::hasNPredecessors(unsigned N) const {
   return hasNItems(pred_begin(this), pred_end(this), N);
 }

 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
   return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
 }

 const BasicBlock *BasicBlock::getSingleSuccessor() const {
   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
   if (SI == E) return nullptr; // no successors
   const BasicBlock *TheSucc = *SI;
   ++SI;
   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
 }

 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
   if (SI == E) return nullptr; // No successors
   const BasicBlock *SuccBB = *SI;
   ++SI;
   for (;SI != E; ++SI) {
     if (*SI != SuccBB)
       return nullptr;
     // The same successor appears multiple times in the successor list.
     // This is OK.
   }
   return SuccBB;
 }

 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
   return make_range<phi_iterator>(P, nullptr);
 }

 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool KeepOneInputPHIs) {
   // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
   assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
          "Pred is not a predecessor!");

   // Return early if there are no PHI nodes to update.
   if (empty() || !isa<PHINode>(begin()))
     return;

   unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
   for (PHINode &Phi : make_early_inc_range(phis())) {
     Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
     if (KeepOneInputPHIs)
       continue;

     // If we have a single predecessor, removeIncomingValue may have erased the
     // PHI node itself.
     if (NumPreds == 1)
       continue;

     // Try to replace the PHI node with a constant value.
     if (Value *PhiConstant = Phi.hasConstantValue()) {
       Phi.replaceAllUsesWith(PhiConstant);
       Phi.eraseFromParent();
     }
   }
 }

 bool BasicBlock::canSplitPredecessors() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (isa<LandingPadInst>(FirstNonPHI))
     return true;
   // This is perhaps a little conservative because constructs like
   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
   // cannot handle such things just yet.
   if (FirstNonPHI->isEHPad())
     return false;
   return true;
 }

 bool BasicBlock::isLegalToHoistInto() const {
   auto *Term = getTerminator();
   // No terminator means the block is under construction.
   if (!Term)
     return true;

   // If the block has no successors, there can be no instructions to hoist.
   assert(Term->getNumSuccessors() > 0);

   // Instructions should not be hoisted across exception handling boundaries.
   return !Term->isExceptionalTerminator();
 }

 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
                                         bool Before) {
   if (Before)
     return splitBasicBlockBefore(I, BBName);

   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
   assert(I != InstList.end() &&
          "Trying to get me to create degenerate basic block!");

   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
                                        this->getNextNode());

   // Save DebugLoc of split point before invalidating iterator.
   DebugLoc Loc = I->getDebugLoc();
   // Move all of the specified instructions from the original basic block into
   // the new basic block.
   New->getInstList().splice(New->end(), this->getInstList(), I, end());

   // Add a branch instruction to the newly formed basic block.
   BranchInst *BI = BranchInst::Create(New, this);
   BI->setDebugLoc(Loc);

   // Now we must loop through all of the successors of the New block (which
   // _were_ the successors of the 'this' block), and update any PHI nodes in
   // successors.  If there were PHI nodes in the successors, then they need to
   // know that incoming branches will be from New, not from Old (this).
   //
   New->replaceSuccessorsPhiUsesWith(this, New);
   return New;
 }

 BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
   assert(getTerminator() &&
          "Can't use splitBasicBlockBefore on degenerate BB!");
   assert(I != InstList.end() &&
          "Trying to get me to create degenerate basic block!");

   assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
          "cannot split on multi incoming phis");

   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this);
   // Save DebugLoc of split point before invalidating iterator.
   DebugLoc Loc = I->getDebugLoc();
   // Move all of the specified instructions from the original basic block into
   // the new basic block.
   New->getInstList().splice(New->end(), this->getInstList(), begin(), I);

   // Loop through all of the predecessors of the 'this' block (which will be the
   // predecessors of the New block), replace the specified successor 'this'
   // block to point at the New block and update any PHI nodes in 'this' block.
   // If there were PHI nodes in 'this' block, the PHI nodes are updated
   // to reflect that the incoming branches will be from the New block and not
   // from predecessors of the 'this' block.
   for (BasicBlock *Pred : predecessors(this)) {
     Instruction *TI = Pred->getTerminator();
     TI->replaceSuccessorWith(this, New);
     this->replacePhiUsesWith(Pred, New);
   }
   // Add a branch instruction from  "New" to "this" Block.
   BranchInst *BI = BranchInst::Create(this, New);
   BI->setDebugLoc(Loc);

   return New;
 }

 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
   // N.B. This might not be a complete BasicBlock, so don't assume
   // that it ends with a non-phi instruction.
   for (iterator II = begin(), IE = end(); II != IE; ++II) {
     PHINode *PN = dyn_cast<PHINode>(II);
     if (!PN)
       break;
     PN->replaceIncomingBlockWith(Old, New);
   }
 }

 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
                                               BasicBlock *New) {
   Instruction *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 : successors(TI))
     Succ->replacePhiUsesWith(Old, New);
 }

 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
   this->replaceSuccessorsPhiUsesWith(this, New);
 }

 bool BasicBlock::isLandingPad() const {
   return isa<LandingPadInst>(getFirstNonPHI());
 }

 const LandingPadInst *BasicBlock::getLandingPadInst() const {
   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 }

 Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
   const Instruction *TI = getTerminator();
   if (MDNode *MDIrrLoopHeader =
       TI->getMetadata(LLVMContext::MD_irr_loop)) {
     MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
     if (MDName->getString().equals("loop_header_weight")) {
       auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
       return Optional<uint64_t>(CI->getValue().getZExtValue());
     }
   }
   return Optional<uint64_t>();
 }

 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
   while (isa<DbgInfoIntrinsic>(It))
     ++It;
   return It;
 }

 void BasicBlock::renumberInstructions() {
   unsigned Order = 0;
   for (Instruction &I : *this)
     I.Order = Order++;

   // Set the bit to indicate that the instruction order valid and cached.
   BasicBlockBits Bits = getBasicBlockBits();
   Bits.InstrOrderValid = true;
   setBasicBlockBits(Bits);
 }

 #ifndef NDEBUG
 /// In asserts builds, this checks the numbering. In non-asserts builds, it
 /// is defined as a no-op inline function in BasicBlock.h.
 void BasicBlock::validateInstrOrdering() const {
   if (!isInstrOrderValid())
     return;
   const Instruction *Prev = nullptr;
   for (const Instruction &I : *this) {
     assert((!Prev || Prev->comesBefore(&I)) &&
            "cached instruction ordering is incorrect");
     Prev = &I;
   }
 }
 #endif
	//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// This file implements the BasicBlock class for the IR library.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/IR/BasicBlock.h"
	#include "SymbolTableListTraitsImpl.h"
	#include "llvm/ADT/STLExtras.h"
	#include "llvm/IR/CFG.h"
	#include "llvm/IR/Constants.h"
	#include "llvm/IR/Instructions.h"
	#include "llvm/IR/IntrinsicInst.h"
	#include "llvm/IR/LLVMContext.h"
	#include "llvm/IR/Type.h"
	#include <algorithm>

	using namespace llvm;

	ValueSymbolTable *BasicBlock::getValueSymbolTable() {
	if (Function *F = getParent())
	return F->getValueSymbolTable();
	return nullptr;
	}

	LLVMContext &BasicBlock::getContext() const {
	return getType()->getContext();
	}

	template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
	BB->invalidateOrders();
	}

	// Explicit instantiation of SymbolTableListTraits since some of the methods
	// are not in the public header file...
	template class llvm::SymbolTableListTraits<Instruction>;

	BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
	BasicBlock *InsertBefore)
	: Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {

	if (NewParent)
	insertInto(NewParent, InsertBefore);
	else
	assert(!InsertBefore &&
	"Cannot insert block before another block with no function!");

	setName(Name);
	}

	void BasicBlock::insertInto(Function NewParent, BasicBlock InsertBefore) {
	assert(NewParent && "Expected a parent");
	assert(!Parent && "Already has a parent");

	if (InsertBefore)
	NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
	else
	NewParent->getBasicBlockList().push_back(this);
	}

	BasicBlock::~BasicBlock() {
	validateInstrOrdering();

	// If the address of the block is taken and it is being deleted (e.g. because
	// it is dead), this means that there is either a dangling constant expr
	// hanging off the block, or an undefined use of the block (source code
	// expecting the address of a label to keep the block alive even though there
	// is no indirect branch). Handle these cases by zapping the BlockAddress
	// nodes. There are no other possible uses at this point.
	if (hasAddressTaken()) {
	assert(!use_empty() && "There should be at least one blockaddress!");
	Constant *Replacement =
	ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
	while (!use_empty()) {
	BlockAddress *BA = cast<BlockAddress>(user_back());
	BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
	BA->getType()));
	BA->destroyConstant();
	}
	}

	assert(getParent() == nullptr && "BasicBlock still linked into the program!");
	dropAllReferences();
	InstList.clear();
	}

	void BasicBlock::setParent(Function *parent) {
	// Set Parent=parent, updating instruction symtab entries as appropriate.
	InstList.setSymTabObject(&Parent, parent);
	}

	iterator_range<filter_iterator<BasicBlock::const_iterator,
	std::function<bool(const Instruction &)>>>
	BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
	std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
	return !isa<DbgInfoIntrinsic>(I) &&
	!(SkipPseudoOp && isa<PseudoProbeInst>(I));
	};
	return make_filter_range(*this, Fn);
	}

	iterator_range<
	filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
	BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
	std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
	return !isa<DbgInfoIntrinsic>(I) &&
	!(SkipPseudoOp && isa<PseudoProbeInst>(I));
	};
	return make_filter_range(*this, Fn);
	}

	filter_iterator<BasicBlock::const_iterator,
	std::function<bool(const Instruction &)>>::difference_type
	BasicBlock::sizeWithoutDebug() const {
	return std::distance(instructionsWithoutDebug().begin(),
	instructionsWithoutDebug().end());
	}

	void BasicBlock::removeFromParent() {
	getParent()->getBasicBlockList().remove(getIterator());
	}

	iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
	return getParent()->getBasicBlockList().erase(getIterator());
	}

	void BasicBlock::moveBefore(BasicBlock *MovePos) {
	MovePos->getParent()->getBasicBlockList().splice(
	MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
	}

	void BasicBlock::moveAfter(BasicBlock *MovePos) {
	MovePos->getParent()->getBasicBlockList().splice(
	++MovePos->getIterator(), getParent()->getBasicBlockList(),
	getIterator());
	}

	const Module *BasicBlock::getModule() const {
	return getParent()->getParent();
	}

	const Instruction *BasicBlock::getTerminator() const {
	if (InstList.empty() \|\| !InstList.back().isTerminator())
	return nullptr;
	return &InstList.back();
	}

	const CallInst *BasicBlock::getTerminatingMustTailCall() const {
	if (InstList.empty())
	return nullptr;
	const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
	if (!RI \|\| RI == &InstList.front())
	return nullptr;

	const Instruction *Prev = RI->getPrevNode();
	if (!Prev)
	return nullptr;

	if (Value *RV = RI->getReturnValue()) {
	if (RV != Prev)
	return nullptr;

	// Look through the optional bitcast.
	if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
	RV = BI->getOperand(0);
	Prev = BI->getPrevNode();
	if (!Prev \|\| RV != Prev)
	return nullptr;
	}
	}

	if (auto *CI = dyn_cast<CallInst>(Prev)) {
	if (CI->isMustTailCall())
	return CI;
	}
	return nullptr;
	}

	const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
	if (InstList.empty())
	return nullptr;
	auto *RI = dyn_cast<ReturnInst>(&InstList.back());
	if (!RI \|\| RI == &InstList.front())
	return nullptr;

	if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
	if (Function *F = CI->getCalledFunction())
	if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
	return CI;

	return nullptr;
	}

	const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
	const BasicBlock* BB = this;
	SmallPtrSet<const BasicBlock *, 8> Visited;
	Visited.insert(BB);
	while (auto *Succ = BB->getUniqueSuccessor()) {
	if (!Visited.insert(Succ).second)
	return nullptr;
	BB = Succ;
	}
	return BB->getTerminatingDeoptimizeCall();
	}

	const Instruction* BasicBlock::getFirstNonPHI() const {
	for (const Instruction &I : *this)
	if (!isa<PHINode>(I))
	return &I;
	return nullptr;
	}

	const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
	for (const Instruction &I : *this) {
	if (isa<PHINode>(I) \|\| isa<DbgInfoIntrinsic>(I))
	continue;

	if (SkipPseudoOp && isa<PseudoProbeInst>(I))
	continue;

	return &I;
	}
	return nullptr;
	}

	const Instruction *
	BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
	for (const Instruction &I : *this) {
	if (isa<PHINode>(I) \|\| isa<DbgInfoIntrinsic>(I))
	continue;

	if (I.isLifetimeStartOrEnd())
	continue;

	if (SkipPseudoOp && isa<PseudoProbeInst>(I))
	continue;

	return &I;
	}
	return nullptr;
	}

	BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
	const Instruction *FirstNonPHI = getFirstNonPHI();
	if (!FirstNonPHI)
	return end();

	const_iterator InsertPt = FirstNonPHI->getIterator();
	if (InsertPt->isEHPad()) ++InsertPt;
	return InsertPt;
	}

	void BasicBlock::dropAllReferences() {
	for (Instruction &I : *this)
	I.dropAllReferences();
	}

	const BasicBlock *BasicBlock::getSinglePredecessor() const {
	const_pred_iterator PI = pred_begin(this), E = pred_end(this);
	if (PI == E) return nullptr; // No preds.
	const BasicBlock ThePred = PI;
	++PI;
	return (PI == E) ? ThePred : nullptr /multiple preds/;
	}

	const BasicBlock *BasicBlock::getUniquePredecessor() const {
	const_pred_iterator PI = pred_begin(this), E = pred_end(this);
	if (PI == E) return nullptr; // No preds.
	const BasicBlock PredBB = PI;
	++PI;
	for (;PI != E; ++PI) {
	if (*PI != PredBB)
	return nullptr;
	// The same predecessor appears multiple times in the predecessor list.
	// This is OK.
	}
	return PredBB;
	}

	bool BasicBlock::hasNPredecessors(unsigned N) const {
	return hasNItems(pred_begin(this), pred_end(this), N);
	}

	bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
	return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
	}

	const BasicBlock *BasicBlock::getSingleSuccessor() const {
	const_succ_iterator SI = succ_begin(this), E = succ_end(this);
	if (SI == E) return nullptr; // no successors
	const BasicBlock TheSucc = SI;
	++SI;
	return (SI == E) ? TheSucc : nullptr /* multiple successors */;
	}

	const BasicBlock *BasicBlock::getUniqueSuccessor() const {
	const_succ_iterator SI = succ_begin(this), E = succ_end(this);
	if (SI == E) return nullptr; // No successors
	const BasicBlock SuccBB = SI;
	++SI;
	for (;SI != E; ++SI) {
	if (*SI != SuccBB)
	return nullptr;
	// The same successor appears multiple times in the successor list.
	// This is OK.
	}
	return SuccBB;
	}

	iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
	PHINode P = empty() ? nullptr : dyn_cast<PHINode>(&begin());
	return make_range<phi_iterator>(P, nullptr);
	}

	void BasicBlock::removePredecessor(BasicBlock *Pred,
	bool KeepOneInputPHIs) {
	// Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
	assert((hasNUsesOrMore(16) \|\| llvm::is_contained(predecessors(this), Pred)) &&
	"Pred is not a predecessor!");

	// Return early if there are no PHI nodes to update.
	if (empty() \|\| !isa<PHINode>(begin()))
	return;

	unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
	for (PHINode &Phi : make_early_inc_range(phis())) {
	Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
	if (KeepOneInputPHIs)
	continue;

	// If we have a single predecessor, removeIncomingValue may have erased the
	// PHI node itself.
	if (NumPreds == 1)
	continue;

	// Try to replace the PHI node with a constant value.
	if (Value *PhiConstant = Phi.hasConstantValue()) {
	Phi.replaceAllUsesWith(PhiConstant);
	Phi.eraseFromParent();
	}
	}
	}

	bool BasicBlock::canSplitPredecessors() const {
	const Instruction *FirstNonPHI = getFirstNonPHI();
	if (isa<LandingPadInst>(FirstNonPHI))
	return true;
	// This is perhaps a little conservative because constructs like
	// CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
	// cannot handle such things just yet.
	if (FirstNonPHI->isEHPad())
	return false;
	return true;
	}

	bool BasicBlock::isLegalToHoistInto() const {
	auto *Term = getTerminator();
	// No terminator means the block is under construction.
	if (!Term)
	return true;

	// If the block has no successors, there can be no instructions to hoist.
	assert(Term->getNumSuccessors() > 0);

	// Instructions should not be hoisted across exception handling boundaries.
	return !Term->isExceptionalTerminator();
	}

	BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
	bool Before) {
	if (Before)
	return splitBasicBlockBefore(I, BBName);

	assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
	assert(I != InstList.end() &&
	"Trying to get me to create degenerate basic block!");

	BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
	this->getNextNode());

	// Save DebugLoc of split point before invalidating iterator.
	DebugLoc Loc = I->getDebugLoc();
	// Move all of the specified instructions from the original basic block into
	// the new basic block.
	New->getInstList().splice(New->end(), this->getInstList(), I, end());

	// Add a branch instruction to the newly formed basic block.
	BranchInst *BI = BranchInst::Create(New, this);
	BI->setDebugLoc(Loc);

	// Now we must loop through all of the successors of the New block (which
	// _were_ the successors of the 'this' block), and update any PHI nodes in
	// successors. If there were PHI nodes in the successors, then they need to
	// know that incoming branches will be from New, not from Old (this).
	//
	New->replaceSuccessorsPhiUsesWith(this, New);
	return New;
	}

	BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
	assert(getTerminator() &&
	"Can't use splitBasicBlockBefore on degenerate BB!");
	assert(I != InstList.end() &&
	"Trying to get me to create degenerate basic block!");

	assert((!isa<PHINode>(*I) \|\| getSinglePredecessor()) &&
	"cannot split on multi incoming phis");

	BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this);
	// Save DebugLoc of split point before invalidating iterator.
	DebugLoc Loc = I->getDebugLoc();
	// Move all of the specified instructions from the original basic block into
	// the new basic block.
	New->getInstList().splice(New->end(), this->getInstList(), begin(), I);

	// Loop through all of the predecessors of the 'this' block (which will be the
	// predecessors of the New block), replace the specified successor 'this'
	// block to point at the New block and update any PHI nodes in 'this' block.
	// If there were PHI nodes in 'this' block, the PHI nodes are updated
	// to reflect that the incoming branches will be from the New block and not
	// from predecessors of the 'this' block.
	for (BasicBlock *Pred : predecessors(this)) {
	Instruction *TI = Pred->getTerminator();
	TI->replaceSuccessorWith(this, New);
	this->replacePhiUsesWith(Pred, New);
	}
	// Add a branch instruction from "New" to "this" Block.
	BranchInst *BI = BranchInst::Create(this, New);
	BI->setDebugLoc(Loc);

	return New;
	}

	void BasicBlock::replacePhiUsesWith(BasicBlock Old, BasicBlock New) {
	// N.B. This might not be a complete BasicBlock, so don't assume
	// that it ends with a non-phi instruction.
	for (iterator II = begin(), IE = end(); II != IE; ++II) {
	PHINode *PN = dyn_cast<PHINode>(II);
	if (!PN)
	break;
	PN->replaceIncomingBlockWith(Old, New);
	}
	}

	void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
	BasicBlock *New) {
	Instruction *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 : successors(TI))
	Succ->replacePhiUsesWith(Old, New);
	}

	void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
	this->replaceSuccessorsPhiUsesWith(this, New);
	}

	bool BasicBlock::isLandingPad() const {
	return isa<LandingPadInst>(getFirstNonPHI());
	}

	const LandingPadInst *BasicBlock::getLandingPadInst() const {
	return dyn_cast<LandingPadInst>(getFirstNonPHI());
	}

	Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
	const Instruction *TI = getTerminator();
	if (MDNode *MDIrrLoopHeader =
	TI->getMetadata(LLVMContext::MD_irr_loop)) {
	MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
	if (MDName->getString().equals("loop_header_weight")) {
	auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
	return Optional<uint64_t>(CI->getValue().getZExtValue());
	}
	}
	return Optional<uint64_t>();
	}

	BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
	while (isa<DbgInfoIntrinsic>(It))
	++It;
	return It;
	}

	void BasicBlock::renumberInstructions() {
	unsigned Order = 0;
	for (Instruction &I : *this)
	I.Order = Order++;

	// Set the bit to indicate that the instruction order valid and cached.
	BasicBlockBits Bits = getBasicBlockBits();
	Bits.InstrOrderValid = true;
	setBasicBlockBits(Bits);
	}

	#ifndef NDEBUG
	/// In asserts builds, this checks the numbering. In non-asserts builds, it
	/// is defined as a no-op inline function in BasicBlock.h.
	void BasicBlock::validateInstrOrdering() const {
	if (!isInstrOrderValid())
	return;
	const Instruction *Prev = nullptr;
	for (const Instruction &I : *this) {
	assert((!Prev \|\| Prev->comesBefore(&I)) &&
	"cached instruction ordering is incorrect");
	Prev = &I;
	}
	}
	#endif