1 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the BasicBlock class for the IR library.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/IR/BasicBlock.h"
15 #include "SymbolTableListTraitsImpl.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/IR/CFG.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/IntrinsicInst.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Type.h"
27 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
28 if (Function *F = getParent())
29 return F->getValueSymbolTable();
33 LLVMContext &BasicBlock::getContext() const {
34 return getType()->getContext();
37 // Explicit instantiation of SymbolTableListTraits since some of the methods
38 // are not in the public header file...
39 template class llvm::SymbolTableListTraits<Instruction>;
41 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
42 BasicBlock *InsertBefore)
43 : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
46 insertInto(NewParent, InsertBefore);
48 assert(!InsertBefore &&
49 "Cannot insert block before another block with no function!");
54 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
55 assert(NewParent && "Expected a parent");
56 assert(!Parent && "Already has a parent");
59 NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
61 NewParent->getBasicBlockList().push_back(this);
64 BasicBlock::~BasicBlock() {
65 // If the address of the block is taken and it is being deleted (e.g. because
66 // it is dead), this means that there is either a dangling constant expr
67 // hanging off the block, or an undefined use of the block (source code
68 // expecting the address of a label to keep the block alive even though there
69 // is no indirect branch). Handle these cases by zapping the BlockAddress
70 // nodes. There are no other possible uses at this point.
71 if (hasAddressTaken()) {
72 assert(!use_empty() && "There should be at least one blockaddress!");
73 Constant *Replacement =
74 ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
75 while (!use_empty()) {
76 BlockAddress *BA = cast<BlockAddress>(user_back());
77 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
79 BA->destroyConstant();
83 assert(getParent() == nullptr && "BasicBlock still linked into the program!");
88 void BasicBlock::setParent(Function *parent) {
89 // Set Parent=parent, updating instruction symtab entries as appropriate.
90 InstList.setSymTabObject(&Parent, parent);
93 void BasicBlock::removeFromParent() {
94 getParent()->getBasicBlockList().remove(getIterator());
97 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
98 return getParent()->getBasicBlockList().erase(getIterator());
101 /// Unlink this basic block from its current function and
102 /// insert it into the function that MovePos lives in, right before MovePos.
103 void BasicBlock::moveBefore(BasicBlock *MovePos) {
104 MovePos->getParent()->getBasicBlockList().splice(
105 MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
108 /// Unlink this basic block from its current function and
109 /// insert it into the function that MovePos lives in, right after MovePos.
110 void BasicBlock::moveAfter(BasicBlock *MovePos) {
111 MovePos->getParent()->getBasicBlockList().splice(
112 ++MovePos->getIterator(), getParent()->getBasicBlockList(),
116 const Module *BasicBlock::getModule() const {
117 return getParent()->getParent();
120 const TerminatorInst *BasicBlock::getTerminator() const {
121 if (InstList.empty()) return nullptr;
122 return dyn_cast<TerminatorInst>(&InstList.back());
125 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
126 if (InstList.empty())
128 const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
129 if (!RI || RI == &InstList.front())
132 const Instruction *Prev = RI->getPrevNode();
136 if (Value *RV = RI->getReturnValue()) {
140 // Look through the optional bitcast.
141 if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
142 RV = BI->getOperand(0);
143 Prev = BI->getPrevNode();
144 if (!Prev || RV != Prev)
149 if (auto *CI = dyn_cast<CallInst>(Prev)) {
150 if (CI->isMustTailCall())
156 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
157 if (InstList.empty())
159 auto *RI = dyn_cast<ReturnInst>(&InstList.back());
160 if (!RI || RI == &InstList.front())
163 if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
164 if (Function *F = CI->getCalledFunction())
165 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
171 const Instruction* BasicBlock::getFirstNonPHI() const {
172 for (const Instruction &I : *this)
173 if (!isa<PHINode>(I))
178 const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
179 for (const Instruction &I : *this)
180 if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
185 const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
186 for (const Instruction &I : *this) {
187 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
190 if (auto *II = dyn_cast<IntrinsicInst>(&I))
191 if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
192 II->getIntrinsicID() == Intrinsic::lifetime_end)
200 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
201 const Instruction *FirstNonPHI = getFirstNonPHI();
205 const_iterator InsertPt = FirstNonPHI->getIterator();
206 if (InsertPt->isEHPad()) ++InsertPt;
210 void BasicBlock::dropAllReferences() {
211 for (Instruction &I : *this)
212 I.dropAllReferences();
215 /// If this basic block has a single predecessor block,
216 /// return the block, otherwise return a null pointer.
217 const BasicBlock *BasicBlock::getSinglePredecessor() const {
218 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
219 if (PI == E) return nullptr; // No preds.
220 const BasicBlock *ThePred = *PI;
222 return (PI == E) ? ThePred : nullptr /*multiple preds*/;
225 /// If this basic block has a unique predecessor block,
226 /// return the block, otherwise return a null pointer.
227 /// Note that unique predecessor doesn't mean single edge, there can be
228 /// multiple edges from the unique predecessor to this block (for example
229 /// a switch statement with multiple cases having the same destination).
230 const BasicBlock *BasicBlock::getUniquePredecessor() const {
231 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
232 if (PI == E) return nullptr; // No preds.
233 const BasicBlock *PredBB = *PI;
235 for (;PI != E; ++PI) {
238 // The same predecessor appears multiple times in the predecessor list.
244 const BasicBlock *BasicBlock::getSingleSuccessor() const {
245 succ_const_iterator SI = succ_begin(this), E = succ_end(this);
246 if (SI == E) return nullptr; // no successors
247 const BasicBlock *TheSucc = *SI;
249 return (SI == E) ? TheSucc : nullptr /* multiple successors */;
252 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
253 succ_const_iterator SI = succ_begin(this), E = succ_end(this);
254 if (SI == E) return nullptr; // No successors
255 const BasicBlock *SuccBB = *SI;
257 for (;SI != E; ++SI) {
260 // The same successor appears multiple times in the successor list.
266 /// This method is used to notify a BasicBlock that the
267 /// specified Predecessor of the block is no longer able to reach it. This is
268 /// actually not used to update the Predecessor list, but is actually used to
269 /// update the PHI nodes that reside in the block. Note that this should be
270 /// called while the predecessor still refers to this block.
272 void BasicBlock::removePredecessor(BasicBlock *Pred,
273 bool DontDeleteUselessPHIs) {
274 assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
275 find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
276 "removePredecessor: BB is not a predecessor!");
278 if (InstList.empty()) return;
279 PHINode *APN = dyn_cast<PHINode>(&front());
280 if (!APN) return; // Quick exit.
282 // If there are exactly two predecessors, then we want to nuke the PHI nodes
283 // altogether. However, we cannot do this, if this in this case:
286 // %x = phi [X, Loop]
287 // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1
288 // br Loop ;; %x2 does not dominate all uses
290 // This is because the PHI node input is actually taken from the predecessor
291 // basic block. The only case this can happen is with a self loop, so we
292 // check for this case explicitly now.
294 unsigned max_idx = APN->getNumIncomingValues();
295 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
297 BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
299 // Disable PHI elimination!
300 if (this == Other) max_idx = 3;
303 // <= Two predecessors BEFORE I remove one?
304 if (max_idx <= 2 && !DontDeleteUselessPHIs) {
305 // Yup, loop through and nuke the PHI nodes
306 while (PHINode *PN = dyn_cast<PHINode>(&front())) {
307 // Remove the predecessor first.
308 PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
310 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
312 if (PN->getIncomingValue(0) != PN)
313 PN->replaceAllUsesWith(PN->getIncomingValue(0));
315 // We are left with an infinite loop with no entries: kill the PHI.
316 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
317 getInstList().pop_front(); // Remove the PHI node
320 // If the PHI node already only had one entry, it got deleted by
321 // removeIncomingValue.
324 // Okay, now we know that we need to remove predecessor #pred_idx from all
325 // PHI nodes. Iterate over each PHI node fixing them up
327 for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
329 PN->removeIncomingValue(Pred, false);
330 // If all incoming values to the Phi are the same, we can replace the Phi
332 Value* PNV = nullptr;
333 if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
335 PN->replaceAllUsesWith(PNV);
336 PN->eraseFromParent();
342 bool BasicBlock::canSplitPredecessors() const {
343 const Instruction *FirstNonPHI = getFirstNonPHI();
344 if (isa<LandingPadInst>(FirstNonPHI))
346 // This is perhaps a little conservative because constructs like
347 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
348 // cannot handle such things just yet.
349 if (FirstNonPHI->isEHPad())
354 /// This splits a basic block into two at the specified
355 /// instruction. Note that all instructions BEFORE the specified iterator stay
356 /// as part of the original basic block, an unconditional branch is added to
357 /// the new BB, and the rest of the instructions in the BB are moved to the new
358 /// BB, including the old terminator. This invalidates the iterator.
360 /// Note that this only works on well formed basic blocks (must have a
361 /// terminator), and 'I' must not be the end of instruction list (which would
362 /// cause a degenerate basic block to be formed, having a terminator inside of
363 /// the basic block).
365 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
366 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
367 assert(I != InstList.end() &&
368 "Trying to get me to create degenerate basic block!");
370 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
371 this->getNextNode());
373 // Save DebugLoc of split point before invalidating iterator.
374 DebugLoc Loc = I->getDebugLoc();
375 // Move all of the specified instructions from the original basic block into
376 // the new basic block.
377 New->getInstList().splice(New->end(), this->getInstList(), I, end());
379 // Add a branch instruction to the newly formed basic block.
380 BranchInst *BI = BranchInst::Create(New, this);
381 BI->setDebugLoc(Loc);
383 // Now we must loop through all of the successors of the New block (which
384 // _were_ the successors of the 'this' block), and update any PHI nodes in
385 // successors. If there were PHI nodes in the successors, then they need to
386 // know that incoming branches will be from New, not from Old.
388 for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
389 // Loop over any phi nodes in the basic block, updating the BB field of
390 // incoming values...
391 BasicBlock *Successor = *I;
393 for (BasicBlock::iterator II = Successor->begin();
394 (PN = dyn_cast<PHINode>(II)); ++II) {
395 int IDX = PN->getBasicBlockIndex(this);
397 PN->setIncomingBlock((unsigned)IDX, New);
398 IDX = PN->getBasicBlockIndex(this);
405 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
406 TerminatorInst *TI = getTerminator();
408 // Cope with being called on a BasicBlock that doesn't have a terminator
409 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
411 for (BasicBlock *Succ : TI->successors()) {
412 // N.B. Succ might not be a complete BasicBlock, so don't assume
413 // that it ends with a non-phi instruction.
414 for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
415 PHINode *PN = dyn_cast<PHINode>(II);
419 while ((i = PN->getBasicBlockIndex(this)) >= 0)
420 PN->setIncomingBlock(i, New);
425 /// Return true if this basic block is a landing pad. I.e., it's
426 /// the destination of the 'unwind' edge of an invoke instruction.
427 bool BasicBlock::isLandingPad() const {
428 return isa<LandingPadInst>(getFirstNonPHI());
431 /// Return the landingpad instruction associated with the landing pad.
432 const LandingPadInst *BasicBlock::getLandingPadInst() const {
433 return dyn_cast<LandingPadInst>(getFirstNonPHI());