123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566 |
- //===-- 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/Instructions.h"
- #include "llvm/IR/IntrinsicInst.h"
- #include "llvm/IR/LLVMContext.h"
- #include "llvm/IR/Type.h"
- using namespace llvm;
- #define DEBUG_TYPE "ir"
- STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");
- 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->insert(InsertBefore->getIterator(), this);
- else
- NewParent->insert(NewParent->end(), 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()->splice(MovePos->getIterator(), 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::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;
- }
- 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 exception handling boundaries.
- return !Term->isExceptionalTerminator();
- }
- 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->getDebugLoc();
- // 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;
- }
- void BasicBlock::splice(BasicBlock::iterator ToIt, BasicBlock *FromBB,
- BasicBlock::iterator FromBeginIt,
- BasicBlock::iterator FromEndIt) {
- #ifdef EXPENSIVE_CHECKS
- // Check that FromBeginIt is befor FromEndIt.
- auto FromBBEnd = FromBB->end();
- for (auto It = FromBeginIt; It != FromEndIt; ++It)
- assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
- #endif // EXPENSIVE_CHECKS
- getInstList().splice(ToIt, FromBB->getInstList(), FromBeginIt, FromEndIt);
- }
- 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++;
- }
- #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
|