1 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the BasicBlock class for the IR library.
10 //
11 //===----------------------------------------------------------------------===//
12
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"
22 #include <algorithm>
23
24 using namespace llvm;
25
getValueSymbolTable()26 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
27 if (Function *F = getParent())
28 return F->getValueSymbolTable();
29 return nullptr;
30 }
31
getContext() const32 LLVMContext &BasicBlock::getContext() const {
33 return getType()->getContext();
34 }
35
invalidateParentIListOrdering(BasicBlock * BB)36 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
37 BB->invalidateOrders();
38 }
39
40 // Explicit instantiation of SymbolTableListTraits since some of the methods
41 // are not in the public header file...
42 template class llvm::SymbolTableListTraits<Instruction>;
43
BasicBlock(LLVMContext & C,const Twine & Name,Function * NewParent,BasicBlock * InsertBefore)44 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
45 BasicBlock *InsertBefore)
46 : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
47
48 if (NewParent)
49 insertInto(NewParent, InsertBefore);
50 else
51 assert(!InsertBefore &&
52 "Cannot insert block before another block with no function!");
53
54 setName(Name);
55 }
56
insertInto(Function * NewParent,BasicBlock * InsertBefore)57 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
58 assert(NewParent && "Expected a parent");
59 assert(!Parent && "Already has a parent");
60
61 if (InsertBefore)
62 NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
63 else
64 NewParent->getBasicBlockList().push_back(this);
65 }
66
~BasicBlock()67 BasicBlock::~BasicBlock() {
68 validateInstrOrdering();
69
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,
83 BA->getType()));
84 BA->destroyConstant();
85 }
86 }
87
88 assert(getParent() == nullptr && "BasicBlock still linked into the program!");
89 dropAllReferences();
90 InstList.clear();
91 }
92
setParent(Function * parent)93 void BasicBlock::setParent(Function *parent) {
94 // Set Parent=parent, updating instruction symtab entries as appropriate.
95 InstList.setSymTabObject(&Parent, parent);
96 }
97
98 iterator_range<filter_iterator<BasicBlock::const_iterator,
99 std::function<bool(const Instruction &)>>>
instructionsWithoutDebug(bool SkipPseudoOp) const100 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
101 std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
102 return !isa<DbgInfoIntrinsic>(I) &&
103 !(SkipPseudoOp && isa<PseudoProbeInst>(I));
104 };
105 return make_filter_range(*this, Fn);
106 }
107
108 iterator_range<
109 filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
instructionsWithoutDebug(bool SkipPseudoOp)110 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
111 std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
112 return !isa<DbgInfoIntrinsic>(I) &&
113 !(SkipPseudoOp && isa<PseudoProbeInst>(I));
114 };
115 return make_filter_range(*this, Fn);
116 }
117
118 filter_iterator<BasicBlock::const_iterator,
119 std::function<bool(const Instruction &)>>::difference_type
sizeWithoutDebug() const120 BasicBlock::sizeWithoutDebug() const {
121 return std::distance(instructionsWithoutDebug().begin(),
122 instructionsWithoutDebug().end());
123 }
124
removeFromParent()125 void BasicBlock::removeFromParent() {
126 getParent()->getBasicBlockList().remove(getIterator());
127 }
128
eraseFromParent()129 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
130 return getParent()->getBasicBlockList().erase(getIterator());
131 }
132
moveBefore(BasicBlock * MovePos)133 void BasicBlock::moveBefore(BasicBlock *MovePos) {
134 MovePos->getParent()->getBasicBlockList().splice(
135 MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
136 }
137
moveAfter(BasicBlock * MovePos)138 void BasicBlock::moveAfter(BasicBlock *MovePos) {
139 MovePos->getParent()->getBasicBlockList().splice(
140 ++MovePos->getIterator(), getParent()->getBasicBlockList(),
141 getIterator());
142 }
143
getModule() const144 const Module *BasicBlock::getModule() const {
145 return getParent()->getParent();
146 }
147
getTerminator() const148 const Instruction *BasicBlock::getTerminator() const {
149 if (InstList.empty() || !InstList.back().isTerminator())
150 return nullptr;
151 return &InstList.back();
152 }
153
getTerminatingMustTailCall() const154 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
155 if (InstList.empty())
156 return nullptr;
157 const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
158 if (!RI || RI == &InstList.front())
159 return nullptr;
160
161 const Instruction *Prev = RI->getPrevNode();
162 if (!Prev)
163 return nullptr;
164
165 if (Value *RV = RI->getReturnValue()) {
166 if (RV != Prev)
167 return nullptr;
168
169 // Look through the optional bitcast.
170 if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
171 RV = BI->getOperand(0);
172 Prev = BI->getPrevNode();
173 if (!Prev || RV != Prev)
174 return nullptr;
175 }
176 }
177
178 if (auto *CI = dyn_cast<CallInst>(Prev)) {
179 if (CI->isMustTailCall())
180 return CI;
181 }
182 return nullptr;
183 }
184
getTerminatingDeoptimizeCall() const185 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
186 if (InstList.empty())
187 return nullptr;
188 auto *RI = dyn_cast<ReturnInst>(&InstList.back());
189 if (!RI || RI == &InstList.front())
190 return nullptr;
191
192 if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
193 if (Function *F = CI->getCalledFunction())
194 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
195 return CI;
196
197 return nullptr;
198 }
199
getPostdominatingDeoptimizeCall() const200 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
201 const BasicBlock* BB = this;
202 SmallPtrSet<const BasicBlock *, 8> Visited;
203 Visited.insert(BB);
204 while (auto *Succ = BB->getUniqueSuccessor()) {
205 if (!Visited.insert(Succ).second)
206 return nullptr;
207 BB = Succ;
208 }
209 return BB->getTerminatingDeoptimizeCall();
210 }
211
getFirstNonPHI() const212 const Instruction* BasicBlock::getFirstNonPHI() const {
213 for (const Instruction &I : *this)
214 if (!isa<PHINode>(I))
215 return &I;
216 return nullptr;
217 }
218
getFirstNonPHIOrDbg(bool SkipPseudoOp) const219 const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
220 for (const Instruction &I : *this) {
221 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
222 continue;
223
224 if (SkipPseudoOp && isa<PseudoProbeInst>(I))
225 continue;
226
227 return &I;
228 }
229 return nullptr;
230 }
231
232 const Instruction *
getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const233 BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
234 for (const Instruction &I : *this) {
235 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
236 continue;
237
238 if (I.isLifetimeStartOrEnd())
239 continue;
240
241 if (SkipPseudoOp && isa<PseudoProbeInst>(I))
242 continue;
243
244 return &I;
245 }
246 return nullptr;
247 }
248
getFirstInsertionPt() const249 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
250 const Instruction *FirstNonPHI = getFirstNonPHI();
251 if (!FirstNonPHI)
252 return end();
253
254 const_iterator InsertPt = FirstNonPHI->getIterator();
255 if (InsertPt->isEHPad()) ++InsertPt;
256 return InsertPt;
257 }
258
dropAllReferences()259 void BasicBlock::dropAllReferences() {
260 for (Instruction &I : *this)
261 I.dropAllReferences();
262 }
263
getSinglePredecessor() const264 const BasicBlock *BasicBlock::getSinglePredecessor() const {
265 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
266 if (PI == E) return nullptr; // No preds.
267 const BasicBlock *ThePred = *PI;
268 ++PI;
269 return (PI == E) ? ThePred : nullptr /*multiple preds*/;
270 }
271
getUniquePredecessor() const272 const BasicBlock *BasicBlock::getUniquePredecessor() const {
273 const_pred_iterator PI = pred_begin(this), E = pred_end(this);
274 if (PI == E) return nullptr; // No preds.
275 const BasicBlock *PredBB = *PI;
276 ++PI;
277 for (;PI != E; ++PI) {
278 if (*PI != PredBB)
279 return nullptr;
280 // The same predecessor appears multiple times in the predecessor list.
281 // This is OK.
282 }
283 return PredBB;
284 }
285
hasNPredecessors(unsigned N) const286 bool BasicBlock::hasNPredecessors(unsigned N) const {
287 return hasNItems(pred_begin(this), pred_end(this), N);
288 }
289
hasNPredecessorsOrMore(unsigned N) const290 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
291 return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
292 }
293
getSingleSuccessor() const294 const BasicBlock *BasicBlock::getSingleSuccessor() const {
295 const_succ_iterator SI = succ_begin(this), E = succ_end(this);
296 if (SI == E) return nullptr; // no successors
297 const BasicBlock *TheSucc = *SI;
298 ++SI;
299 return (SI == E) ? TheSucc : nullptr /* multiple successors */;
300 }
301
getUniqueSuccessor() const302 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
303 const_succ_iterator SI = succ_begin(this), E = succ_end(this);
304 if (SI == E) return nullptr; // No successors
305 const BasicBlock *SuccBB = *SI;
306 ++SI;
307 for (;SI != E; ++SI) {
308 if (*SI != SuccBB)
309 return nullptr;
310 // The same successor appears multiple times in the successor list.
311 // This is OK.
312 }
313 return SuccBB;
314 }
315
phis()316 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
317 PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
318 return make_range<phi_iterator>(P, nullptr);
319 }
320
removePredecessor(BasicBlock * Pred,bool KeepOneInputPHIs)321 void BasicBlock::removePredecessor(BasicBlock *Pred,
322 bool KeepOneInputPHIs) {
323 // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
324 assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
325 "Pred is not a predecessor!");
326
327 // Return early if there are no PHI nodes to update.
328 if (empty() || !isa<PHINode>(begin()))
329 return;
330
331 unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
332 for (PHINode &Phi : make_early_inc_range(phis())) {
333 Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
334 if (KeepOneInputPHIs)
335 continue;
336
337 // If we have a single predecessor, removeIncomingValue may have erased the
338 // PHI node itself.
339 if (NumPreds == 1)
340 continue;
341
342 // Try to replace the PHI node with a constant value.
343 if (Value *PhiConstant = Phi.hasConstantValue()) {
344 Phi.replaceAllUsesWith(PhiConstant);
345 Phi.eraseFromParent();
346 }
347 }
348 }
349
canSplitPredecessors() const350 bool BasicBlock::canSplitPredecessors() const {
351 const Instruction *FirstNonPHI = getFirstNonPHI();
352 if (isa<LandingPadInst>(FirstNonPHI))
353 return true;
354 // This is perhaps a little conservative because constructs like
355 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
356 // cannot handle such things just yet.
357 if (FirstNonPHI->isEHPad())
358 return false;
359 return true;
360 }
361
isLegalToHoistInto() const362 bool BasicBlock::isLegalToHoistInto() const {
363 auto *Term = getTerminator();
364 // No terminator means the block is under construction.
365 if (!Term)
366 return true;
367
368 // If the block has no successors, there can be no instructions to hoist.
369 assert(Term->getNumSuccessors() > 0);
370
371 // Instructions should not be hoisted across exception handling boundaries.
372 return !Term->isExceptionalTerminator();
373 }
374
isEntryBlock() const375 bool BasicBlock::isEntryBlock() const {
376 const Function *F = getParent();
377 assert(F && "Block must have a parent function to use this API");
378 return this == &F->getEntryBlock();
379 }
380
splitBasicBlock(iterator I,const Twine & BBName,bool Before)381 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
382 bool Before) {
383 if (Before)
384 return splitBasicBlockBefore(I, BBName);
385
386 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
387 assert(I != InstList.end() &&
388 "Trying to get me to create degenerate basic block!");
389
390 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
391 this->getNextNode());
392
393 // Save DebugLoc of split point before invalidating iterator.
394 DebugLoc Loc = I->getDebugLoc();
395 // Move all of the specified instructions from the original basic block into
396 // the new basic block.
397 New->getInstList().splice(New->end(), this->getInstList(), I, end());
398
399 // Add a branch instruction to the newly formed basic block.
400 BranchInst *BI = BranchInst::Create(New, this);
401 BI->setDebugLoc(Loc);
402
403 // Now we must loop through all of the successors of the New block (which
404 // _were_ the successors of the 'this' block), and update any PHI nodes in
405 // successors. If there were PHI nodes in the successors, then they need to
406 // know that incoming branches will be from New, not from Old (this).
407 //
408 New->replaceSuccessorsPhiUsesWith(this, New);
409 return New;
410 }
411
splitBasicBlockBefore(iterator I,const Twine & BBName)412 BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
413 assert(getTerminator() &&
414 "Can't use splitBasicBlockBefore on degenerate BB!");
415 assert(I != InstList.end() &&
416 "Trying to get me to create degenerate basic block!");
417
418 assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
419 "cannot split on multi incoming phis");
420
421 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this);
422 // Save DebugLoc of split point before invalidating iterator.
423 DebugLoc Loc = I->getDebugLoc();
424 // Move all of the specified instructions from the original basic block into
425 // the new basic block.
426 New->getInstList().splice(New->end(), this->getInstList(), begin(), I);
427
428 // Loop through all of the predecessors of the 'this' block (which will be the
429 // predecessors of the New block), replace the specified successor 'this'
430 // block to point at the New block and update any PHI nodes in 'this' block.
431 // If there were PHI nodes in 'this' block, the PHI nodes are updated
432 // to reflect that the incoming branches will be from the New block and not
433 // from predecessors of the 'this' block.
434 for (BasicBlock *Pred : predecessors(this)) {
435 Instruction *TI = Pred->getTerminator();
436 TI->replaceSuccessorWith(this, New);
437 this->replacePhiUsesWith(Pred, New);
438 }
439 // Add a branch instruction from "New" to "this" Block.
440 BranchInst *BI = BranchInst::Create(this, New);
441 BI->setDebugLoc(Loc);
442
443 return New;
444 }
445
replacePhiUsesWith(BasicBlock * Old,BasicBlock * New)446 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
447 // N.B. This might not be a complete BasicBlock, so don't assume
448 // that it ends with a non-phi instruction.
449 for (iterator II = begin(), IE = end(); II != IE; ++II) {
450 PHINode *PN = dyn_cast<PHINode>(II);
451 if (!PN)
452 break;
453 PN->replaceIncomingBlockWith(Old, New);
454 }
455 }
456
replaceSuccessorsPhiUsesWith(BasicBlock * Old,BasicBlock * New)457 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
458 BasicBlock *New) {
459 Instruction *TI = getTerminator();
460 if (!TI)
461 // Cope with being called on a BasicBlock that doesn't have a terminator
462 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
463 return;
464 for (BasicBlock *Succ : successors(TI))
465 Succ->replacePhiUsesWith(Old, New);
466 }
467
replaceSuccessorsPhiUsesWith(BasicBlock * New)468 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
469 this->replaceSuccessorsPhiUsesWith(this, New);
470 }
471
isLandingPad() const472 bool BasicBlock::isLandingPad() const {
473 return isa<LandingPadInst>(getFirstNonPHI());
474 }
475
getLandingPadInst() const476 const LandingPadInst *BasicBlock::getLandingPadInst() const {
477 return dyn_cast<LandingPadInst>(getFirstNonPHI());
478 }
479
getIrrLoopHeaderWeight() const480 Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
481 const Instruction *TI = getTerminator();
482 if (MDNode *MDIrrLoopHeader =
483 TI->getMetadata(LLVMContext::MD_irr_loop)) {
484 MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
485 if (MDName->getString().equals("loop_header_weight")) {
486 auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
487 return Optional<uint64_t>(CI->getValue().getZExtValue());
488 }
489 }
490 return Optional<uint64_t>();
491 }
492
skipDebugIntrinsics(BasicBlock::iterator It)493 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
494 while (isa<DbgInfoIntrinsic>(It))
495 ++It;
496 return It;
497 }
498
renumberInstructions()499 void BasicBlock::renumberInstructions() {
500 unsigned Order = 0;
501 for (Instruction &I : *this)
502 I.Order = Order++;
503
504 // Set the bit to indicate that the instruction order valid and cached.
505 BasicBlockBits Bits = getBasicBlockBits();
506 Bits.InstrOrderValid = true;
507 setBasicBlockBits(Bits);
508 }
509
510 #ifndef NDEBUG
511 /// In asserts builds, this checks the numbering. In non-asserts builds, it
512 /// is defined as a no-op inline function in BasicBlock.h.
validateInstrOrdering() const513 void BasicBlock::validateInstrOrdering() const {
514 if (!isInstrOrderValid())
515 return;
516 const Instruction *Prev = nullptr;
517 for (const Instruction &I : *this) {
518 assert((!Prev || Prev->comesBefore(&I)) &&
519 "cached instruction ordering is incorrect");
520 Prev = &I;
521 }
522 }
523 #endif
524