1 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements the BasicBlock class for the IR library.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/IR/BasicBlock.h"
14 #include "SymbolTableListTraitsImpl.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/IR/CFG.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/Type.h"
26 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
27 if (Function *F = getParent())
28 return F->getValueSymbolTable();
32 LLVMContext &BasicBlock::getContext() const {
33 return getType()->getContext();
36 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
37 BB->invalidateOrders();
40 // Explicit instantiation of SymbolTableListTraits since some of the methods
41 // are not in the public header file...
42 template class llvm::SymbolTableListTraits<Instruction>;
44 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
45 BasicBlock *InsertBefore)
46 : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
49 insertInto(NewParent, InsertBefore);
51 assert(!InsertBefore &&
52 "Cannot insert block before another block with no function!");
57 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
58 assert(NewParent && "Expected a parent");
59 assert(!Parent && "Already has a parent");
62 NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
64 NewParent->getBasicBlockList().push_back(this);
67 BasicBlock::~BasicBlock() {
68 validateInstrOrdering();
70 // If the address of the block is taken and it is being deleted (e.g. because
71 // it is dead), this means that there is either a dangling constant expr
72 // hanging off the block, or an undefined use of the block (source code
73 // expecting the address of a label to keep the block alive even though there
74 // is no indirect branch). Handle these cases by zapping the BlockAddress
75 // nodes. There are no other possible uses at this point.
76 if (hasAddressTaken()) {
77 assert(!use_empty() && "There should be at least one blockaddress!");
78 Constant *Replacement =
79 ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
80 while (!use_empty()) {
81 BlockAddress *BA = cast<BlockAddress>(user_back());
82 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
84 BA->destroyConstant();
88 assert(getParent() == nullptr && "BasicBlock still linked into the program!");
93 void BasicBlock::setParent(Function *parent) {
94 // Set Parent=parent, updating instruction symtab entries as appropriate.
95 InstList.setSymTabObject(&Parent, parent);
98 iterator_range<filter_iterator<BasicBlock::const_iterator,
99 std::function<bool(const Instruction &)>>>
100 BasicBlock::instructionsWithoutDebug() const {
101 std::function<bool(const Instruction &)> Fn = [](const Instruction &I) {
102 return !isa<DbgInfoIntrinsic>(I);
104 return make_filter_range(*this, Fn);
107 iterator_range<filter_iterator<BasicBlock::iterator,
108 std::function<bool(Instruction &)>>>
109 BasicBlock::instructionsWithoutDebug() {
110 std::function<bool(Instruction &)> Fn = [](Instruction &I) {
111 return !isa<DbgInfoIntrinsic>(I);
113 return make_filter_range(*this, Fn);
116 filter_iterator<BasicBlock::const_iterator,
117 std::function<bool(const Instruction &)>>::difference_type
118 BasicBlock::sizeWithoutDebug() const {
119 return std::distance(instructionsWithoutDebug().begin(),
120 instructionsWithoutDebug().end());
123 void BasicBlock::removeFromParent() {
124 getParent()->getBasicBlockList().remove(getIterator());
127 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
128 return getParent()->getBasicBlockList().erase(getIterator());
131 /// Unlink this basic block from its current function and
132 /// insert it into the function that MovePos lives in, right before MovePos.
133 void BasicBlock::moveBefore(BasicBlock *MovePos) {
134 MovePos->getParent()->getBasicBlockList().splice(
135 MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
138 /// Unlink this basic block from its current function and
139 /// insert it into the function that MovePos lives in, right after MovePos.
140 void BasicBlock::moveAfter(BasicBlock *MovePos) {
141 MovePos->getParent()->getBasicBlockList().splice(
142 ++MovePos->getIterator(), getParent()->getBasicBlockList(),
146 const Module *BasicBlock::getModule() const {
147 return getParent()->getParent();
150 const Instruction *BasicBlock::getTerminator() const {
151 if (InstList.empty() || !InstList.back().isTerminator())
153 return &InstList.back();
156 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
157 if (InstList.empty())
159 const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
160 if (!RI || RI == &InstList.front())
163 const Instruction *Prev = RI->getPrevNode();
167 if (Value *RV = RI->getReturnValue()) {
171 // Look through the optional bitcast.
172 if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
173 RV = BI->getOperand(0);
174 Prev = BI->getPrevNode();
175 if (!Prev || RV != Prev)
180 if (auto *CI = dyn_cast<CallInst>(Prev)) {
181 if (CI->isMustTailCall())
187 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
188 if (InstList.empty())
190 auto *RI = dyn_cast<ReturnInst>(&InstList.back());
191 if (!RI || RI == &InstList.front())
194 if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
195 if (Function *F = CI->getCalledFunction())
196 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
202 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
203 const BasicBlock* BB = this;
204 SmallPtrSet<const BasicBlock *, 8> Visited;
206 while (auto *Succ = BB->getUniqueSuccessor()) {
207 if (!Visited.insert(Succ).second)
211 return BB->getTerminatingDeoptimizeCall();
214 const Instruction* BasicBlock::getFirstNonPHI() const {
215 for (const Instruction &I : *this)
216 if (!isa<PHINode>(I))
221 const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
222 for (const Instruction &I : *this)
223 if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
228 const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
229 for (const Instruction &I : *this) {
230 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
233 if (I.isLifetimeStartOrEnd())
241 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
242 const Instruction *FirstNonPHI = getFirstNonPHI();
246 const_iterator InsertPt = FirstNonPHI->getIterator();
247 if (InsertPt->isEHPad()) ++InsertPt;
251 void BasicBlock::dropAllReferences() {
252 for (Instruction &I : *this)
253 I.dropAllReferences();
256 /// If this basic block has a single predecessor block,
257 /// return the block, otherwise return a null pointer.
258 const BasicBlock *BasicBlock::getSinglePredecessor() const {
259 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
260 if (PI == E) return nullptr; // No preds.
261 const BasicBlock *ThePred = *PI;
263 return (PI == E) ? ThePred : nullptr /*multiple preds*/;
266 /// If this basic block has a unique predecessor block,
267 /// return the block, otherwise return a null pointer.
268 /// Note that unique predecessor doesn't mean single edge, there can be
269 /// multiple edges from the unique predecessor to this block (for example
270 /// a switch statement with multiple cases having the same destination).
271 const BasicBlock *BasicBlock::getUniquePredecessor() const {
272 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
273 if (PI == E) return nullptr; // No preds.
274 const BasicBlock *PredBB = *PI;
276 for (;PI != E; ++PI) {
279 // The same predecessor appears multiple times in the predecessor list.
285 bool BasicBlock::hasNPredecessors(unsigned N) const {
286 return hasNItems(pred_begin(this), pred_end(this), N);
289 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
290 return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
293 const BasicBlock *BasicBlock::getSingleSuccessor() const {
294 const_succ_iterator SI = succ_begin(this), E = succ_end(this);
295 if (SI == E) return nullptr; // no successors
296 const BasicBlock *TheSucc = *SI;
298 return (SI == E) ? TheSucc : nullptr /* multiple successors */;
301 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
302 const_succ_iterator SI = succ_begin(this), E = succ_end(this);
303 if (SI == E) return nullptr; // No successors
304 const BasicBlock *SuccBB = *SI;
306 for (;SI != E; ++SI) {
309 // The same successor appears multiple times in the successor list.
315 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
316 PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
317 return make_range<phi_iterator>(P, nullptr);
320 /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
321 /// Note that this function does not actually remove the predecessor.
323 /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
324 /// zero or one incoming values, and don't simplify PHIs with all incoming
326 void BasicBlock::removePredecessor(BasicBlock *Pred,
327 bool KeepOneInputPHIs) {
328 // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
329 assert((hasNUsesOrMore(16) ||
330 find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
331 "Pred is not a predecessor!");
333 // Return early if there are no PHI nodes to update.
334 if (!isa<PHINode>(begin()))
336 unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
338 // Update all PHI nodes.
339 for (iterator II = begin(); isa<PHINode>(II);) {
340 PHINode *PN = cast<PHINode>(II++);
341 PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
342 if (!KeepOneInputPHIs) {
343 // If we have a single predecessor, removeIncomingValue erased the PHI
346 if (Value *PNV = PN->hasConstantValue()) {
347 // Replace the PHI node with its constant value.
348 PN->replaceAllUsesWith(PNV);
349 PN->eraseFromParent();
356 bool BasicBlock::canSplitPredecessors() const {
357 const Instruction *FirstNonPHI = getFirstNonPHI();
358 if (isa<LandingPadInst>(FirstNonPHI))
360 // This is perhaps a little conservative because constructs like
361 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
362 // cannot handle such things just yet.
363 if (FirstNonPHI->isEHPad())
368 bool BasicBlock::isLegalToHoistInto() const {
369 auto *Term = getTerminator();
370 // No terminator means the block is under construction.
374 // If the block has no successors, there can be no instructions to hoist.
375 assert(Term->getNumSuccessors() > 0);
377 // Instructions should not be hoisted across exception handling boundaries.
378 return !Term->isExceptionalTerminator();
381 /// This splits a basic block into two at the specified
382 /// instruction. Note that all instructions BEFORE the specified iterator stay
383 /// as part of the original basic block, an unconditional branch is added to
384 /// the new BB, and the rest of the instructions in the BB are moved to the new
385 /// BB, including the old terminator. This invalidates the iterator.
387 /// Note that this only works on well formed basic blocks (must have a
388 /// terminator), and 'I' must not be the end of instruction list (which would
389 /// cause a degenerate basic block to be formed, having a terminator inside of
390 /// the basic block).
392 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
393 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
394 assert(I != InstList.end() &&
395 "Trying to get me to create degenerate basic block!");
397 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
398 this->getNextNode());
400 // Save DebugLoc of split point before invalidating iterator.
401 DebugLoc Loc = I->getDebugLoc();
402 // Move all of the specified instructions from the original basic block into
403 // the new basic block.
404 New->getInstList().splice(New->end(), this->getInstList(), I, end());
406 // Add a branch instruction to the newly formed basic block.
407 BranchInst *BI = BranchInst::Create(New, this);
408 BI->setDebugLoc(Loc);
410 // Now we must loop through all of the successors of the New block (which
411 // _were_ the successors of the 'this' block), and update any PHI nodes in
412 // successors. If there were PHI nodes in the successors, then they need to
413 // know that incoming branches will be from New, not from Old (this).
415 New->replaceSuccessorsPhiUsesWith(this, New);
419 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
420 // N.B. This might not be a complete BasicBlock, so don't assume
421 // that it ends with a non-phi instruction.
422 for (iterator II = begin(), IE = end(); II != IE; ++II) {
423 PHINode *PN = dyn_cast<PHINode>(II);
426 PN->replaceIncomingBlockWith(Old, New);
430 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
432 Instruction *TI = getTerminator();
434 // Cope with being called on a BasicBlock that doesn't have a terminator
435 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
437 llvm::for_each(successors(TI), [Old, New](BasicBlock *Succ) {
438 Succ->replacePhiUsesWith(Old, New);
442 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
443 this->replaceSuccessorsPhiUsesWith(this, New);
446 /// Return true if this basic block is a landing pad. I.e., it's
447 /// the destination of the 'unwind' edge of an invoke instruction.
448 bool BasicBlock::isLandingPad() const {
449 return isa<LandingPadInst>(getFirstNonPHI());
452 /// Return the landingpad instruction associated with the landing pad.
453 const LandingPadInst *BasicBlock::getLandingPadInst() const {
454 return dyn_cast<LandingPadInst>(getFirstNonPHI());
457 Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
458 const Instruction *TI = getTerminator();
459 if (MDNode *MDIrrLoopHeader =
460 TI->getMetadata(LLVMContext::MD_irr_loop)) {
461 MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
462 if (MDName->getString().equals("loop_header_weight")) {
463 auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
464 return Optional<uint64_t>(CI->getValue().getZExtValue());
467 return Optional<uint64_t>();
470 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
471 while (isa<DbgInfoIntrinsic>(It))
476 void BasicBlock::renumberInstructions() {
478 for (Instruction &I : *this)
481 // Set the bit to indicate that the instruction order valid and cached.
482 BasicBlockBits Bits = getBasicBlockBits();
483 Bits.InstrOrderValid = true;
484 setBasicBlockBits(Bits);
488 /// In asserts builds, this checks the numbering. In non-asserts builds, it
489 /// is defined as a no-op inline function in BasicBlock.h.
490 void BasicBlock::validateInstrOrdering() const {
491 if (!isInstrOrderValid())
493 const Instruction *Prev = nullptr;
494 for (const Instruction &I : *this) {
495 assert((!Prev || Prev->comesBefore(&I)) &&
496 "cached instruction ordering is incorrect");