//===-- 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/ADT/Statistic.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugProgramInstruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/CommandLine.h"

#include "LLVMContextImpl.h"

using namespace llvm;

#define DEBUG_TYPE "ir"
STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");

cl::opt<bool>
    UseNewDbgInfoFormat("experimental-debuginfo-iterators",
                        cl::desc("Enable communicating debuginfo positions "
                                 "through iterators, eliminating intrinsics"),
                        cl::init(false));

DPMarker *BasicBlock::createMarker(Instruction *I) {
  assert(IsNewDbgInfoFormat &&
         "Tried to create a marker in a non new debug-info block!");
  if (I->DbgMarker)
    return I->DbgMarker;
  DPMarker *Marker = new DPMarker();
  Marker->MarkedInstr = I;
  I->DbgMarker = Marker;
  return Marker;
}

DPMarker *BasicBlock::createMarker(InstListType::iterator It) {
  assert(IsNewDbgInfoFormat &&
         "Tried to create a marker in a non new debug-info block!");
  if (It != end())
    return createMarker(&*It);
  DPMarker *DPM = getTrailingDPValues();
  if (DPM)
    return DPM;
  DPM = new DPMarker();
  setTrailingDPValues(DPM);
  return DPM;
}

void BasicBlock::convertToNewDbgValues() {
  // Is the command line option set?
  if (!UseNewDbgInfoFormat)
    return;

  IsNewDbgInfoFormat = true;

  // Iterate over all instructions in the instruction list, collecting dbg.value
  // instructions and converting them to DPValues. Once we find a "real"
  // instruction, attach all those DPValues to a DPMarker in that instruction.
  SmallVector<DPValue *, 4> DPVals;
  for (Instruction &I : make_early_inc_range(InstList)) {
    assert(!I.DbgMarker && "DbgMarker already set on old-format instrs?");
    if (DbgVariableIntrinsic *DVI = dyn_cast<DbgVariableIntrinsic>(&I)) {
      // Convert this dbg.value to a DPValue.
      DPValue *Value = new DPValue(DVI);
      DPVals.push_back(Value);
      DVI->eraseFromParent();
      continue;
    }

    // Create a marker to store DPValues in. Technically we don't need to store
    // one marker per instruction, but that's a future optimisation.
    createMarker(&I);
    DPMarker *Marker = I.DbgMarker;

    for (DPValue *DPV : DPVals)
      Marker->insertDPValue(DPV, false);

    DPVals.clear();
  }
}

void BasicBlock::convertFromNewDbgValues() {
  invalidateOrders();
  IsNewDbgInfoFormat = false;

  // Iterate over the block, finding instructions annotated with DPMarkers.
  // Convert any attached DPValues to dbg.values and insert ahead of the
  // instruction.
  for (auto &Inst : *this) {
    if (!Inst.DbgMarker)
      continue;

    DPMarker &Marker = *Inst.DbgMarker;
    for (DPValue &DPV : Marker.getDbgValueRange())
      InstList.insert(Inst.getIterator(),
                      DPV.createDebugIntrinsic(getModule(), nullptr));

    Marker.eraseFromParent();
  };

  // Assume no trailing DPValues: we could technically create them at the end
  // of the block, after a terminator, but this would be non-cannonical and
  // indicates that something else is broken somewhere.
  assert(!getTrailingDPValues());
}

bool BasicBlock::validateDbgValues(bool Assert, bool Msg, raw_ostream *OS) {
  bool RetVal = false;
  if (!OS)
    OS = &errs();

  // Helper lambda for reporting failures: via assertion, printing, and return
  // value.
  auto TestFailure = [Assert, Msg, &RetVal, OS](bool Val, const char *Text) {
    // Did the test fail?
    if (Val)
      return;

    // If we're asserting, then fire off an assertion.
    if (Assert)
      llvm_unreachable(Text);

    if (Msg)
      *OS << Text << "\n";
    RetVal = true;
  };

  // We should have the same debug-format as the parent function.
  TestFailure(getParent()->IsNewDbgInfoFormat == IsNewDbgInfoFormat,
              "Parent function doesn't have the same debug-info format");

  // Only validate if we are using the new format.
  if (!IsNewDbgInfoFormat)
    return RetVal;

  // Match every DPMarker to every Instruction and vice versa, and
  // verify that there are no invalid DPValues.
  for (auto It = begin(); It != end(); ++It) {
    if (!It->DbgMarker)
      continue;

    // Validate DebugProgramMarkers.
    DPMarker *CurrentDebugMarker = It->DbgMarker;

    // If this is a marker, it should match the instruction and vice versa.
    TestFailure(CurrentDebugMarker->MarkedInstr == &*It,
                "Debug Marker points to incorrect instruction?");

    // Now validate any DPValues in the marker.
    for (DPValue &DPV : CurrentDebugMarker->getDbgValueRange()) {
      // Validate DebugProgramValues.
      TestFailure(DPV.getMarker() == CurrentDebugMarker,
                  "Not pointing at correct next marker!");

      // Verify that no DbgValues appear prior to PHIs.
      TestFailure(
          !isa<PHINode>(It),
          "DebugProgramValues must not appear before PHI nodes in a block!");
    }
  }

  // Except transiently when removing + re-inserting the block terminator, there
  // should be no trailing DPValues.
  TestFailure(!getTrailingDPValues(), "Trailing DPValues in block");
  return RetVal;
}

#ifndef NDEBUG
void BasicBlock::dumpDbgValues() const {
  for (auto &Inst : *this) {
    if (!Inst.DbgMarker)
      continue;

    dbgs() << "@ " << Inst.DbgMarker << " ";
    Inst.DbgMarker->dump();
  };
}
#endif

void BasicBlock::setIsNewDbgInfoFormat(bool NewFlag) {
  if (NewFlag && !IsNewDbgInfoFormat)
    convertToNewDbgValues();
  else if (!NewFlag && IsNewDbgInfoFormat)
    convertFromNewDbgValues();
}

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,
                                           ilist_iterator_bits<true>>;

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

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

  setName(Name);
  if (NewParent)
    setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
}

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

  if (InsertBefore)
    NewParent->insert(InsertBefore->getIterator(), this);
  else
    NewParent->insert(NewParent->end(), this);

  setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
}

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();
  for (auto &Inst : *this) {
    if (!Inst.DbgMarker)
      continue;
    Inst.DbgMarker->eraseFromParent();
  }
  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(SymbolTableList<BasicBlock>::iterator MovePos) {
  getParent()->splice(MovePos, getParent(), getIterator());
}

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

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

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::getFirstMayFaultInst() const {
  if (InstList.empty())
    return nullptr;
  for (const Instruction &I : *this)
    if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallBase>(I))
      return &I;
  return nullptr;
}

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

BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const {
  const Instruction *I = getFirstNonPHI();
  BasicBlock::const_iterator It = I->getIterator();
  // Set the head-inclusive bit to indicate that this iterator includes
  // any debug-info at the start of the block. This is a no-op unless the
  // appropriate CMake flag is set.
  It.setHeadBit(true);
  return It;
}

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;
  // Set the head-inclusive bit to indicate that this iterator includes
  // any debug-info at the start of the block. This is a no-op unless the
  // appropriate CMake flag is set.
  InsertPt.setHeadBit(true);
  return InsertPt;
}

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

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

  if (isEntryBlock()) {
    const_iterator End = end();
    while (InsertPt != End &&
           (isa<AllocaInst>(*InsertPt) || isa<DbgInfoIntrinsic>(*InsertPt) ||
            isa<PseudoProbeInst>(*InsertPt))) {
      if (const AllocaInst *AI = dyn_cast<AllocaInst>(&*InsertPt)) {
        if (!AI->isStaticAlloca())
          break;
      }
      ++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 special terminators, which may
  // have side effects or return values.
  return !Term->isSpecialTerminator();
}

bool BasicBlock::isEntryBlock() const {
  const Function *F = getParent();
  assert(F && "Block must have a parent function to use this API");
  return this == &F->getEntryBlock();
}

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->getStableDebugLoc();
  // Move all of the specified instructions from the original basic block into
  // the new basic block.
  New->splice(New->end(), this, 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->splice(New->end(), this, 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.
  // Save predecessors to separate vector before modifying them.
  SmallVector<BasicBlock *, 4> Predecessors;
  for (BasicBlock *Pred : predecessors(this))
    Predecessors.push_back(Pred);
  for (BasicBlock *Pred : Predecessors) {
    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;
}

BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt,
                                       BasicBlock::iterator ToIt) {
  return InstList.erase(FromIt, ToIt);
}

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 (Instruction &I : *this) {
    PHINode *PN = dyn_cast<PHINode>(&I);
    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());
}

std::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 std::optional<uint64_t>(CI->getValue().getZExtValue());
    }
  }
  return std::nullopt;
}

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);

  NumInstrRenumberings++;
}

void BasicBlock::flushTerminatorDbgValues() {
  // If we erase the terminator in a block, any DPValues will sink and "fall
  // off the end", existing after any terminator that gets inserted. With
  // dbg.value intrinsics we would just insert the terminator at end() and
  // the dbg.values would come before the terminator. With DPValues, we must
  // do this manually.
  // To get out of this unfortunate form, whenever we insert a terminator,
  // check whether there's anything trailing at the end and move those DPValues
  // in front of the terminator.

  // Do nothing if we're not in new debug-info format.
  if (!IsNewDbgInfoFormat)
    return;

  // If there's no terminator, there's nothing to do.
  Instruction *Term = getTerminator();
  if (!Term)
    return;

  // Are there any dangling DPValues?
  DPMarker *TrailingDPValues = getTrailingDPValues();
  if (!TrailingDPValues)
    return;

  // Transfer DPValues from the trailing position onto the terminator.
  Term->DbgMarker->absorbDebugValues(*TrailingDPValues, false);
  TrailingDPValues->eraseFromParent();
  deleteTrailingDPValues();
}

void BasicBlock::spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest,
                                           BasicBlock *Src,
                                           BasicBlock::iterator First,
                                           BasicBlock::iterator Last) {
  // Imagine the folowing:
  //
  //   bb1:
  //     dbg.value(...
  //     ret i32 0
  //
  // If an optimisation pass attempts to splice the contents of the block from
  // BB1->begin() to BB1->getTerminator(), then the dbg.value will be
  // transferred to the destination.
  // However, in the "new" DPValue format for debug-info, that range is empty:
  // begin() returns an iterator to the terminator, as there will only be a
  // single instruction in the block. We must piece together from the bits set
  // in the iterators whether there was the intention to transfer any debug
  // info.

  // If we're not in "new" debug-info format, do nothing.
  if (!IsNewDbgInfoFormat)
    return;

  assert(First == Last);
  bool InsertAtHead = Dest.getHeadBit();
  bool ReadFromHead = First.getHeadBit();

  // If the source block is completely empty, including no terminator, then
  // transfer any trailing DPValues that are still hanging around. This can
  // occur when a block is optimised away and the terminator has been moved
  // somewhere else.
  if (Src->empty()) {
    assert(Dest != end() &&
           "Transferring trailing DPValues to another trailing position");
    DPMarker *SrcTrailingDPValues = Src->getTrailingDPValues();
    if (!SrcTrailingDPValues)
      return;

    DPMarker *M = Dest->DbgMarker;
    M->absorbDebugValues(*SrcTrailingDPValues, InsertAtHead);
    SrcTrailingDPValues->eraseFromParent();
    Src->deleteTrailingDPValues();
    return;
  }

  // There are instructions in this block; if the First iterator was
  // with begin() / getFirstInsertionPt() then the caller intended debug-info
  // at the start of the block to be transferred. Return otherwise.
  if (Src->empty() || First != Src->begin() || !ReadFromHead)
    return;

  // Is there actually anything to transfer?
  if (!First->hasDbgValues())
    return;

  createMarker(Dest)->absorbDebugValues(*First->DbgMarker, InsertAtHead);

  return;
}

void BasicBlock::spliceDebugInfo(BasicBlock::iterator Dest, BasicBlock *Src,
                                 BasicBlock::iterator First,
                                 BasicBlock::iterator Last) {
  /* Do a quick normalisation before calling the real splice implementation. We
     might be operating on a degenerate basic block that has no instructions
     in it, a legitimate transient state. In that case, Dest will be end() and
     any DPValues temporarily stored in the TrailingDPValues map in LLVMContext.
     We might illustrate it thus:

                         Dest
                           |
     this-block:    ~~~~~~~~
      Src-block:            ++++B---B---B---B:::C
                                |               |
                               First           Last

     However: does the caller expect the "~" DPValues to end up before or after
     the spliced segment? This is communciated in the "Head" bit of Dest, which
     signals whether the caller called begin() or end() on this block.

     If the head bit is set, then all is well, we leave DPValues trailing just
     like how dbg.value instructions would trail after instructions spliced to
     the beginning of this block.

     If the head bit isn't set, then try to jam the "~" DPValues onto the front
     of the First instruction, then splice like normal, which joins the "~"
     DPValues with the "+" DPValues. However if the "+" DPValues are supposed to
     be left behind in Src, then:
      * detach the "+" DPValues,
      * move the "~" DPValues onto First,
      * splice like normal,
      * replace the "+" DPValues onto the Last position.
     Complicated, but gets the job done. */

  // If we're inserting at end(), and not in front of dangling DPValues, then
  // move the DPValues onto "First". They'll then be moved naturally in the
  // splice process.
  DPMarker *MoreDanglingDPValues = nullptr;
  DPMarker *OurTrailingDPValues = getTrailingDPValues();
  if (Dest == end() && !Dest.getHeadBit() && OurTrailingDPValues) {
    // Are the "+" DPValues not supposed to move? If so, detach them
    // temporarily.
    if (!First.getHeadBit() && First->hasDbgValues()) {
      MoreDanglingDPValues = Src->getMarker(First);
      MoreDanglingDPValues->removeFromParent();
    }

    if (First->hasDbgValues()) {
      DPMarker *CurMarker = Src->getMarker(First);
      // Place them at the front, it would look like this:
      //            Dest
      //              |
      // this-block:
      // Src-block: ~~~~~~~~++++B---B---B---B:::C
      //                        |               |
      //                       First           Last
      CurMarker->absorbDebugValues(*OurTrailingDPValues, true);
      OurTrailingDPValues->eraseFromParent();
    } else {
      // No current marker, create one and absorb in. (FIXME: we can avoid an
      // allocation in the future).
      DPMarker *CurMarker = Src->createMarker(&*First);
      CurMarker->absorbDebugValues(*OurTrailingDPValues, false);
      OurTrailingDPValues->eraseFromParent();
    }
    deleteTrailingDPValues();
    First.setHeadBit(true);
  }

  // Call the main debug-info-splicing implementation.
  spliceDebugInfoImpl(Dest, Src, First, Last);

  // Do we have some "+" DPValues hanging around that weren't supposed to move,
  // and we detached to make things easier?
  if (!MoreDanglingDPValues)
    return;

  // FIXME: we could avoid an allocation here sometimes.
  DPMarker *LastMarker = Src->createMarker(Last);
  LastMarker->absorbDebugValues(*MoreDanglingDPValues, true);
  MoreDanglingDPValues->eraseFromParent();
}

void BasicBlock::spliceDebugInfoImpl(BasicBlock::iterator Dest, BasicBlock *Src,
                                     BasicBlock::iterator First,
                                     BasicBlock::iterator Last) {
  // Find out where to _place_ these dbg.values; if InsertAtHead is specified,
  // this will be at the start of Dest's debug value range, otherwise this is
  // just Dest's marker.
  bool InsertAtHead = Dest.getHeadBit();
  bool ReadFromHead = First.getHeadBit();
  // Use this flag to signal the abnormal case, where we don't want to copy the
  // DPValues ahead of the "Last" position.
  bool ReadFromTail = !Last.getTailBit();
  bool LastIsEnd = (Last == Src->end());

  /*
    Here's an illustration of what we're about to do. We have two blocks, this
    and Src, and two segments of list. Each instruction is marked by a capital
    while potential DPValue debug-info is marked out by "-" characters and a few
    other special characters (+:=) where I want to highlight what's going on.

                                                 Dest
                                                   |
     this-block:    A----A----A                ====A----A----A----A---A---A
      Src-block                ++++B---B---B---B:::C
                                   |               |
                                  First           Last

    The splice method is going to take all the instructions from First up to
    (but not including) Last and insert them in _front_ of Dest, forming one
    long list. All the DPValues attached to instructions _between_ First and
    Last need no maintenence. However, we have to do special things with the
    DPValues marked with the +:= characters. We only have three positions:
    should the "+" DPValues be transferred, and if so to where? Do we move the
    ":" DPValues? Would they go in front of the "=" DPValues, or should the "="
    DPValues go before "+" DPValues?

    We're told which way it should be by the bits carried in the iterators. The
    "Head" bit indicates whether the specified position is supposed to be at the
    front of the attached DPValues (true) or not (false). The Tail bit is true
    on the other end of a range: is the range intended to include DPValues up to
    the end (false) or not (true).

    FIXME: the tail bit doesn't need to be distinct from the head bit, we could
    combine them.

    Here are some examples of different configurations:

      Dest.Head = true, First.Head = true, Last.Tail = false

      this-block:    A----A----A++++B---B---B---B:::====A----A----A----A---A---A
                                    |                   |
                                  First                Dest

    Wheras if we didn't want to read from the Src list,

      Dest.Head = true, First.Head = false, Last.Tail = false

      this-block:    A----A----AB---B---B---B:::====A----A----A----A---A---A
                                |                   |
                              First                Dest

    Or if we didn't want to insert at the head of Dest:

      Dest.Head = false, First.Head = false, Last.Tail = false

      this-block:    A----A----A====B---B---B---B:::A----A----A----A---A---A
                                    |               |
                                  First            Dest

    Tests for these various configurations can be found in the unit test file
    BasicBlockDbgInfoTest.cpp.

   */

  // Detach the marker at Dest -- this lets us move the "====" DPValues around.
  DPMarker *DestMarker = nullptr;
  if (Dest != end()) {
    DestMarker = getMarker(Dest);
    DestMarker->removeFromParent();
    createMarker(&*Dest);
  }

  // If we're moving the tail range of DPValues (":::"), absorb them into the
  // front of the DPValues at Dest.
  if (ReadFromTail && Src->getMarker(Last)) {
    DPMarker *OntoDest = getMarker(Dest);
    DPMarker *FromLast = Src->getMarker(Last);
    OntoDest->absorbDebugValues(*FromLast, true);
    if (LastIsEnd) {
      FromLast->eraseFromParent();
      Src->deleteTrailingDPValues();
    }
  }

  // If we're _not_ reading from the head of First, i.e. the "++++" DPValues,
  // move their markers onto Last. They remain in the Src block. No action
  // needed.
  if (!ReadFromHead && First->hasDbgValues()) {
    DPMarker *OntoLast = Src->createMarker(Last);
    DPMarker *FromFirst = Src->createMarker(First);
    OntoLast->absorbDebugValues(*FromFirst,
                                true); // Always insert at head of it.
  }

  // Finally, do something with the "====" DPValues we detached.
  if (DestMarker) {
    if (InsertAtHead) {
      // Insert them at the end of the DPValues at Dest. The "::::" DPValues
      // might be in front of them.
      DPMarker *NewDestMarker = getMarker(Dest);
      NewDestMarker->absorbDebugValues(*DestMarker, false);
    } else {
      // Insert them right at the start of the range we moved, ahead of First
      // and the "++++" DPValues.
      DPMarker *FirstMarker = getMarker(First);
      FirstMarker->absorbDebugValues(*DestMarker, true);
    }
    DestMarker->eraseFromParent();
  } else if (Dest == end() && !InsertAtHead) {
    // In the rare circumstance where we insert at end(), and we did not
    // generate the iterator with begin() / getFirstInsertionPt(), it means
    // any trailing debug-info at the end of the block would "normally" have
    // been pushed in front of "First". Move it there now.
    DPMarker *FirstMarker = getMarker(First);
    DPMarker *TrailingDPValues = getTrailingDPValues();
    if (TrailingDPValues) {
      FirstMarker->absorbDebugValues(*TrailingDPValues, true);
      TrailingDPValues->eraseFromParent();
      deleteTrailingDPValues();
    }
  }
}

void BasicBlock::splice(iterator Dest, BasicBlock *Src, iterator First,
                        iterator Last) {
  assert(Src->IsNewDbgInfoFormat == IsNewDbgInfoFormat);

#ifdef EXPENSIVE_CHECKS
  // Check that First is before Last.
  auto FromBBEnd = Src->end();
  for (auto It = First; It != Last; ++It)
    assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
#endif // EXPENSIVE_CHECKS

  // Lots of horrible special casing for empty transfers: the dbg.values between
  // two positions could be spliced in dbg.value mode.
  if (First == Last) {
    spliceDebugInfoEmptyBlock(Dest, Src, First, Last);
    return;
  }

  // Handle non-instr debug-info specific juggling.
  if (IsNewDbgInfoFormat)
    spliceDebugInfo(Dest, Src, First, Last);

  // And move the instructions.
  getInstList().splice(Dest, Src->getInstList(), First, Last);

  flushTerminatorDbgValues();
}

void BasicBlock::insertDPValueAfter(DPValue *DPV, Instruction *I) {
  assert(IsNewDbgInfoFormat);
  assert(I->getParent() == this);

  iterator NextIt = std::next(I->getIterator());
  DPMarker *NextMarker = getMarker(NextIt);
  if (!NextMarker)
    NextMarker = createMarker(NextIt);
  NextMarker->insertDPValue(DPV, true);
}

void BasicBlock::insertDPValueBefore(DPValue *DPV,
                                     InstListType::iterator Where) {
  // We should never directly insert at the end of the block, new DPValues
  // shouldn't be generated at times when there's no terminator.
  assert(Where != end());
  assert(Where->getParent() == this);
  if (!Where->DbgMarker)
    createMarker(Where);
  bool InsertAtHead = Where.getHeadBit();
  Where->DbgMarker->insertDPValue(DPV, InsertAtHead);
}

DPMarker *BasicBlock::getNextMarker(Instruction *I) {
  return getMarker(std::next(I->getIterator()));
}

DPMarker *BasicBlock::getMarker(InstListType::iterator It) {
  if (It == end()) {
    DPMarker *DPM = getTrailingDPValues();
    return DPM;
  }
  return It->DbgMarker;
}

void BasicBlock::reinsertInstInDPValues(
    Instruction *I, std::optional<DPValue::self_iterator> Pos) {
  // "I" was originally removed from a position where it was
  // immediately in front of Pos. Any DPValues on that position then "fell down"
  // onto Pos. "I" has been re-inserted at the front of that wedge of DPValues,
  // shuffle them around to represent the original positioning. To illustrate:
  //
  //   Instructions:  I1---I---I0
  //       DPValues:    DDD DDD
  //
  // Instruction "I" removed,
  //
  //   Instructions:  I1------I0
  //       DPValues:    DDDDDD
  //                       ^Pos
  //
  // Instruction "I" re-inserted (now):
  //
  //   Instructions:  I1---I------I0
  //       DPValues:        DDDDDD
  //                           ^Pos
  //
  // After this method completes:
  //
  //   Instructions:  I1---I---I0
  //       DPValues:    DDD DDD

  // This happens if there were no DPValues on I0. Are there now DPValues there?
  if (!Pos) {
    DPMarker *NextMarker = getNextMarker(I);
    if (!NextMarker)
      return;
    if (NextMarker->StoredDPValues.empty())
      return;
    // There are DPMarkers there now -- they fell down from "I".
    DPMarker *ThisMarker = createMarker(I);
    ThisMarker->absorbDebugValues(*NextMarker, false);
    return;
  }

  // Is there even a range of DPValues to move?
  DPMarker *DPM = (*Pos)->getMarker();
  auto Range = make_range(DPM->StoredDPValues.begin(), (*Pos));
  if (Range.begin() == Range.end())
    return;

  // Otherwise: splice.
  DPMarker *ThisMarker = createMarker(I);
  assert(ThisMarker->StoredDPValues.empty());
  ThisMarker->absorbDebugValues(Range, *DPM, true);
}

#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

void BasicBlock::setTrailingDPValues(DPMarker *foo) {
  getContext().pImpl->setTrailingDPValues(this, foo);
}

DPMarker *BasicBlock::getTrailingDPValues() {
  return getContext().pImpl->getTrailingDPValues(this);
}

void BasicBlock::deleteTrailingDPValues() {
  getContext().pImpl->deleteTrailingDPValues(this);
}