//===-- 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; 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(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>> BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const { std::function Fn = [=](const Instruction &I) { return !isa(I) && !(SkipPseudoOp && isa(I)); }; return make_filter_range(*this, Fn); } iterator_range< filter_iterator>> BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) { std::function Fn = [=](Instruction &I) { return !isa(I) && !(SkipPseudoOp && isa(I)); }; return make_filter_range(*this, Fn); } filter_iterator>::difference_type BasicBlock::sizeWithoutDebug() const { return std::distance(instructionsWithoutDebug().begin(), instructionsWithoutDebug().end()); } void BasicBlock::removeFromParent() { getParent()->getBasicBlockList().remove(getIterator()); } iplist::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(&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(Prev)) { RV = BI->getOperand(0); Prev = BI->getPrevNode(); if (!Prev || RV != Prev) return nullptr; } } if (auto *CI = dyn_cast(Prev)) { if (CI->isMustTailCall()) return CI; } return nullptr; } const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const { if (InstList.empty()) return nullptr; auto *RI = dyn_cast(&InstList.back()); if (!RI || RI == &InstList.front()) return nullptr; if (auto *CI = dyn_cast_or_null(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 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(I)) return &I; return nullptr; } const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const { for (const Instruction &I : *this) { if (isa(I) || isa(I)) continue; if (SkipPseudoOp && isa(I)) continue; return &I; } return nullptr; } const Instruction * BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const { for (const Instruction &I : *this) { if (isa(I) || isa(I)) continue; if (I.isLifetimeStartOrEnd()) continue; if (SkipPseudoOp && isa(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::phis() { PHINode *P = empty() ? nullptr : dyn_cast(&*begin()); return make_range(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(begin())) return; unsigned NumPreds = cast(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(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->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(*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 (Instruction &I : *this) { PHINode *PN = dyn_cast(&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(getFirstNonPHI()); } const LandingPadInst *BasicBlock::getLandingPadInst() const { return dyn_cast(getFirstNonPHI()); } Optional BasicBlock::getIrrLoopHeaderWeight() const { const Instruction *TI = getTerminator(); if (MDNode *MDIrrLoopHeader = TI->getMetadata(LLVMContext::MD_irr_loop)) { MDString *MDName = cast(MDIrrLoopHeader->getOperand(0)); if (MDName->getString().equals("loop_header_weight")) { auto *CI = mdconst::extract(MDIrrLoopHeader->getOperand(1)); return Optional(CI->getValue().getZExtValue()); } } return Optional(); } BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) { while (isa(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