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/ADT/Statistic.h"
17#include "llvm/IR/CFG.h"
18#include "llvm/IR/Constants.h"
19#include "llvm/IR/DebugProgramInstruction.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/IntrinsicInst.h"
22#include "llvm/IR/LLVMContext.h"
23#include "llvm/IR/Type.h"
24#include "llvm/Support/CommandLine.h"
25
26#include "LLVMContextImpl.h"
27
28using namespace llvm;
29
30#define DEBUG_TYPE "ir"
31STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");
32
33cl::opt<bool> UseNewDbgInfoFormat(
34 "experimental-debuginfo-iterators",
35 cl::desc("Enable communicating debuginfo positions through iterators, "
36 "eliminating intrinsics. Has no effect if "
37 "--preserve-input-debuginfo-format=true."),
38 cl::init(Val: true));
39cl::opt<cl::boolOrDefault> PreserveInputDbgFormat(
40 "preserve-input-debuginfo-format", cl::Hidden,
41 cl::desc("When set to true, IR files will be processed and printed in "
42 "their current debug info format, regardless of default behaviour "
43 "or other flags passed. Has no effect if input IR does not "
44 "contain debug records or intrinsics. Ignored in llvm-link, "
45 "llvm-lto, and llvm-lto2."));
46
47bool WriteNewDbgInfoFormatToBitcode /*set default value in cl::init() below*/;
48cl::opt<bool, true> WriteNewDbgInfoFormatToBitcode2(
49 "write-experimental-debuginfo-iterators-to-bitcode", cl::Hidden,
50 cl::location(L&: WriteNewDbgInfoFormatToBitcode), cl::init(Val: true));
51
52DbgMarker *BasicBlock::createMarker(Instruction *I) {
53 assert(IsNewDbgInfoFormat &&
54 "Tried to create a marker in a non new debug-info block!");
55 if (I->DebugMarker)
56 return I->DebugMarker;
57 DbgMarker *Marker = new DbgMarker();
58 Marker->MarkedInstr = I;
59 I->DebugMarker = Marker;
60 return Marker;
61}
62
63DbgMarker *BasicBlock::createMarker(InstListType::iterator It) {
64 assert(IsNewDbgInfoFormat &&
65 "Tried to create a marker in a non new debug-info block!");
66 if (It != end())
67 return createMarker(I: &*It);
68 DbgMarker *DM = getTrailingDbgRecords();
69 if (DM)
70 return DM;
71 DM = new DbgMarker();
72 setTrailingDbgRecords(DM);
73 return DM;
74}
75
76void BasicBlock::convertToNewDbgValues() {
77 IsNewDbgInfoFormat = true;
78
79 // Iterate over all instructions in the instruction list, collecting debug
80 // info intrinsics and converting them to DbgRecords. Once we find a "real"
81 // instruction, attach all those DbgRecords to a DbgMarker in that
82 // instruction.
83 SmallVector<DbgRecord *, 4> DbgVarRecs;
84 for (Instruction &I : make_early_inc_range(Range&: InstList)) {
85 assert(!I.DebugMarker && "DebugMarker already set on old-format instrs?");
86 if (DbgVariableIntrinsic *DVI = dyn_cast<DbgVariableIntrinsic>(Val: &I)) {
87 // Convert this dbg.value to a DbgVariableRecord.
88 DbgVariableRecord *Value = new DbgVariableRecord(DVI);
89 DbgVarRecs.push_back(Elt: Value);
90 DVI->eraseFromParent();
91 continue;
92 }
93
94 if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(Val: &I)) {
95 DbgVarRecs.push_back(
96 Elt: new DbgLabelRecord(DLI->getLabel(), DLI->getDebugLoc()));
97 DLI->eraseFromParent();
98 continue;
99 }
100
101 if (DbgVarRecs.empty())
102 continue;
103
104 // Create a marker to store DbgRecords in.
105 createMarker(I: &I);
106 DbgMarker *Marker = I.DebugMarker;
107
108 for (DbgRecord *DVR : DbgVarRecs)
109 Marker->insertDbgRecord(New: DVR, InsertAtHead: false);
110
111 DbgVarRecs.clear();
112 }
113}
114
115void BasicBlock::convertFromNewDbgValues() {
116 invalidateOrders();
117 IsNewDbgInfoFormat = false;
118
119 // Iterate over the block, finding instructions annotated with DbgMarkers.
120 // Convert any attached DbgRecords to debug intrinsics and insert ahead of the
121 // instruction.
122 for (auto &Inst : *this) {
123 if (!Inst.DebugMarker)
124 continue;
125
126 DbgMarker &Marker = *Inst.DebugMarker;
127 for (DbgRecord &DR : Marker.getDbgRecordRange())
128 InstList.insert(where: Inst.getIterator(),
129 New: DR.createDebugIntrinsic(M: getModule(), InsertBefore: nullptr));
130
131 Marker.eraseFromParent();
132 }
133
134 // Assume no trailing DbgRecords: we could technically create them at the end
135 // of the block, after a terminator, but this would be non-cannonical and
136 // indicates that something else is broken somewhere.
137 assert(!getTrailingDbgRecords());
138}
139
140#ifndef NDEBUG
141void BasicBlock::dumpDbgValues() const {
142 for (auto &Inst : *this) {
143 if (!Inst.DebugMarker)
144 continue;
145
146 dbgs() << "@ " << Inst.DebugMarker << " ";
147 Inst.DebugMarker->dump();
148 };
149}
150#endif
151
152void BasicBlock::setIsNewDbgInfoFormat(bool NewFlag) {
153 if (NewFlag && !IsNewDbgInfoFormat)
154 convertToNewDbgValues();
155 else if (!NewFlag && IsNewDbgInfoFormat)
156 convertFromNewDbgValues();
157}
158void BasicBlock::setNewDbgInfoFormatFlag(bool NewFlag) {
159 IsNewDbgInfoFormat = NewFlag;
160}
161
162ValueSymbolTable *BasicBlock::getValueSymbolTable() {
163 if (Function *F = getParent())
164 return F->getValueSymbolTable();
165 return nullptr;
166}
167
168LLVMContext &BasicBlock::getContext() const {
169 return getType()->getContext();
170}
171
172template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
173 BB->invalidateOrders();
174}
175
176// Explicit instantiation of SymbolTableListTraits since some of the methods
177// are not in the public header file...
178template class llvm::SymbolTableListTraits<
179 Instruction, ilist_iterator_bits<true>, ilist_parent<BasicBlock>>;
180
181BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
182 BasicBlock *InsertBefore)
183 : Value(Type::getLabelTy(C), Value::BasicBlockVal),
184 IsNewDbgInfoFormat(UseNewDbgInfoFormat), Parent(nullptr) {
185
186 if (NewParent)
187 insertInto(Parent: NewParent, InsertBefore);
188 else
189 assert(!InsertBefore &&
190 "Cannot insert block before another block with no function!");
191
192 end().getNodePtr()->setParent(this);
193 setName(Name);
194 if (NewParent)
195 setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
196}
197
198void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
199 assert(NewParent && "Expected a parent");
200 assert(!Parent && "Already has a parent");
201
202 if (InsertBefore)
203 NewParent->insert(Position: InsertBefore->getIterator(), BB: this);
204 else
205 NewParent->insert(Position: NewParent->end(), BB: this);
206
207 setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
208}
209
210BasicBlock::~BasicBlock() {
211 validateInstrOrdering();
212
213 // If the address of the block is taken and it is being deleted (e.g. because
214 // it is dead), this means that there is either a dangling constant expr
215 // hanging off the block, or an undefined use of the block (source code
216 // expecting the address of a label to keep the block alive even though there
217 // is no indirect branch). Handle these cases by zapping the BlockAddress
218 // nodes. There are no other possible uses at this point.
219 if (hasAddressTaken()) {
220 assert(!use_empty() && "There should be at least one blockaddress!");
221 Constant *Replacement =
222 ConstantInt::get(Ty: llvm::Type::getInt32Ty(C&: getContext()), V: 1);
223 while (!use_empty()) {
224 BlockAddress *BA = cast<BlockAddress>(Val: user_back());
225 BA->replaceAllUsesWith(V: ConstantExpr::getIntToPtr(C: Replacement,
226 Ty: BA->getType()));
227 BA->destroyConstant();
228 }
229 }
230
231 assert(getParent() == nullptr && "BasicBlock still linked into the program!");
232 dropAllReferences();
233 for (auto &Inst : *this) {
234 if (!Inst.DebugMarker)
235 continue;
236 Inst.DebugMarker->eraseFromParent();
237 }
238 InstList.clear();
239}
240
241void BasicBlock::setParent(Function *parent) {
242 // Set Parent=parent, updating instruction symtab entries as appropriate.
243 InstList.setSymTabObject(&Parent, parent);
244}
245
246iterator_range<filter_iterator<BasicBlock::const_iterator,
247 std::function<bool(const Instruction &)>>>
248BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
249 std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
250 return !isa<DbgInfoIntrinsic>(Val: I) &&
251 !(SkipPseudoOp && isa<PseudoProbeInst>(Val: I));
252 };
253 return make_filter_range(Range: *this, Pred: Fn);
254}
255
256iterator_range<
257 filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
258BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
259 std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
260 return !isa<DbgInfoIntrinsic>(Val: I) &&
261 !(SkipPseudoOp && isa<PseudoProbeInst>(Val: I));
262 };
263 return make_filter_range(Range&: *this, Pred: Fn);
264}
265
266filter_iterator<BasicBlock::const_iterator,
267 std::function<bool(const Instruction &)>>::difference_type
268BasicBlock::sizeWithoutDebug() const {
269 return std::distance(first: instructionsWithoutDebug().begin(),
270 last: instructionsWithoutDebug().end());
271}
272
273void BasicBlock::removeFromParent() {
274 getParent()->getBasicBlockList().remove(IT: getIterator());
275}
276
277iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
278 return getParent()->getBasicBlockList().erase(where: getIterator());
279}
280
281void BasicBlock::moveBefore(SymbolTableList<BasicBlock>::iterator MovePos) {
282 getParent()->splice(ToIt: MovePos, FromF: getParent(), FromIt: getIterator());
283}
284
285void BasicBlock::moveAfter(BasicBlock *MovePos) {
286 MovePos->getParent()->splice(ToIt: ++MovePos->getIterator(), FromF: getParent(),
287 FromIt: getIterator());
288}
289
290const Module *BasicBlock::getModule() const {
291 return getParent()->getParent();
292}
293
294const DataLayout &BasicBlock::getDataLayout() const {
295 return getModule()->getDataLayout();
296}
297
298const CallInst *BasicBlock::getTerminatingMustTailCall() const {
299 if (InstList.empty())
300 return nullptr;
301 const ReturnInst *RI = dyn_cast<ReturnInst>(Val: &InstList.back());
302 if (!RI || RI == &InstList.front())
303 return nullptr;
304
305 const Instruction *Prev = RI->getPrevNode();
306 if (!Prev)
307 return nullptr;
308
309 if (Value *RV = RI->getReturnValue()) {
310 if (RV != Prev)
311 return nullptr;
312
313 // Look through the optional bitcast.
314 if (auto *BI = dyn_cast<BitCastInst>(Val: Prev)) {
315 RV = BI->getOperand(i_nocapture: 0);
316 Prev = BI->getPrevNode();
317 if (!Prev || RV != Prev)
318 return nullptr;
319 }
320 }
321
322 if (auto *CI = dyn_cast<CallInst>(Val: Prev)) {
323 if (CI->isMustTailCall())
324 return CI;
325 }
326 return nullptr;
327}
328
329const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
330 if (InstList.empty())
331 return nullptr;
332 auto *RI = dyn_cast<ReturnInst>(Val: &InstList.back());
333 if (!RI || RI == &InstList.front())
334 return nullptr;
335
336 if (auto *CI = dyn_cast_or_null<CallInst>(Val: RI->getPrevNode()))
337 if (Function *F = CI->getCalledFunction())
338 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
339 return CI;
340
341 return nullptr;
342}
343
344const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
345 const BasicBlock* BB = this;
346 SmallPtrSet<const BasicBlock *, 8> Visited;
347 Visited.insert(Ptr: BB);
348 while (auto *Succ = BB->getUniqueSuccessor()) {
349 if (!Visited.insert(Ptr: Succ).second)
350 return nullptr;
351 BB = Succ;
352 }
353 return BB->getTerminatingDeoptimizeCall();
354}
355
356const Instruction *BasicBlock::getFirstMayFaultInst() const {
357 if (InstList.empty())
358 return nullptr;
359 for (const Instruction &I : *this)
360 if (isa<LoadInst>(Val: I) || isa<StoreInst>(Val: I) || isa<CallBase>(Val: I))
361 return &I;
362 return nullptr;
363}
364
365const Instruction* BasicBlock::getFirstNonPHI() const {
366 for (const Instruction &I : *this)
367 if (!isa<PHINode>(Val: I))
368 return &I;
369 return nullptr;
370}
371
372BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const {
373 const Instruction *I = getFirstNonPHI();
374 if (!I)
375 return end();
376 BasicBlock::const_iterator It = I->getIterator();
377 // Set the head-inclusive bit to indicate that this iterator includes
378 // any debug-info at the start of the block. This is a no-op unless the
379 // appropriate CMake flag is set.
380 It.setHeadBit(true);
381 return It;
382}
383
384const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
385 for (const Instruction &I : *this) {
386 if (isa<PHINode>(Val: I) || isa<DbgInfoIntrinsic>(Val: I))
387 continue;
388
389 if (SkipPseudoOp && isa<PseudoProbeInst>(Val: I))
390 continue;
391
392 return &I;
393 }
394 return nullptr;
395}
396
397const Instruction *
398BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
399 for (const Instruction &I : *this) {
400 if (isa<PHINode>(Val: I) || isa<DbgInfoIntrinsic>(Val: I))
401 continue;
402
403 if (I.isLifetimeStartOrEnd())
404 continue;
405
406 if (SkipPseudoOp && isa<PseudoProbeInst>(Val: I))
407 continue;
408
409 return &I;
410 }
411 return nullptr;
412}
413
414BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
415 const Instruction *FirstNonPHI = getFirstNonPHI();
416 if (!FirstNonPHI)
417 return end();
418
419 const_iterator InsertPt = FirstNonPHI->getIterator();
420 if (InsertPt->isEHPad()) ++InsertPt;
421 // Set the head-inclusive bit to indicate that this iterator includes
422 // any debug-info at the start of the block. This is a no-op unless the
423 // appropriate CMake flag is set.
424 InsertPt.setHeadBit(true);
425 return InsertPt;
426}
427
428BasicBlock::const_iterator BasicBlock::getFirstNonPHIOrDbgOrAlloca() const {
429 const Instruction *FirstNonPHI = getFirstNonPHI();
430 if (!FirstNonPHI)
431 return end();
432
433 const_iterator InsertPt = FirstNonPHI->getIterator();
434 if (InsertPt->isEHPad())
435 ++InsertPt;
436
437 if (isEntryBlock()) {
438 const_iterator End = end();
439 while (InsertPt != End &&
440 (isa<AllocaInst>(Val: *InsertPt) || isa<DbgInfoIntrinsic>(Val: *InsertPt) ||
441 isa<PseudoProbeInst>(Val: *InsertPt))) {
442 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Val: &*InsertPt)) {
443 if (!AI->isStaticAlloca())
444 break;
445 }
446 ++InsertPt;
447 }
448 }
449 return InsertPt;
450}
451
452void BasicBlock::dropAllReferences() {
453 for (Instruction &I : *this)
454 I.dropAllReferences();
455}
456
457const BasicBlock *BasicBlock::getSinglePredecessor() const {
458 const_pred_iterator PI = pred_begin(BB: this), E = pred_end(BB: this);
459 if (PI == E) return nullptr; // No preds.
460 const BasicBlock *ThePred = *PI;
461 ++PI;
462 return (PI == E) ? ThePred : nullptr /*multiple preds*/;
463}
464
465const BasicBlock *BasicBlock::getUniquePredecessor() const {
466 const_pred_iterator PI = pred_begin(BB: this), E = pred_end(BB: this);
467 if (PI == E) return nullptr; // No preds.
468 const BasicBlock *PredBB = *PI;
469 ++PI;
470 for (;PI != E; ++PI) {
471 if (*PI != PredBB)
472 return nullptr;
473 // The same predecessor appears multiple times in the predecessor list.
474 // This is OK.
475 }
476 return PredBB;
477}
478
479bool BasicBlock::hasNPredecessors(unsigned N) const {
480 return hasNItems(Begin: pred_begin(BB: this), End: pred_end(BB: this), N);
481}
482
483bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
484 return hasNItemsOrMore(Begin: pred_begin(BB: this), End: pred_end(BB: this), N);
485}
486
487const BasicBlock *BasicBlock::getSingleSuccessor() const {
488 const_succ_iterator SI = succ_begin(BB: this), E = succ_end(BB: this);
489 if (SI == E) return nullptr; // no successors
490 const BasicBlock *TheSucc = *SI;
491 ++SI;
492 return (SI == E) ? TheSucc : nullptr /* multiple successors */;
493}
494
495const BasicBlock *BasicBlock::getUniqueSuccessor() const {
496 const_succ_iterator SI = succ_begin(BB: this), E = succ_end(BB: this);
497 if (SI == E) return nullptr; // No successors
498 const BasicBlock *SuccBB = *SI;
499 ++SI;
500 for (;SI != E; ++SI) {
501 if (*SI != SuccBB)
502 return nullptr;
503 // The same successor appears multiple times in the successor list.
504 // This is OK.
505 }
506 return SuccBB;
507}
508
509iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
510 PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(Val: &*begin());
511 return make_range<phi_iterator>(x: P, y: nullptr);
512}
513
514void BasicBlock::removePredecessor(BasicBlock *Pred,
515 bool KeepOneInputPHIs) {
516 // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
517 assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
518 "Pred is not a predecessor!");
519
520 // Return early if there are no PHI nodes to update.
521 if (empty() || !isa<PHINode>(Val: begin()))
522 return;
523
524 unsigned NumPreds = cast<PHINode>(Val&: front()).getNumIncomingValues();
525 for (PHINode &Phi : make_early_inc_range(Range: phis())) {
526 Phi.removeIncomingValue(BB: Pred, DeletePHIIfEmpty: !KeepOneInputPHIs);
527 if (KeepOneInputPHIs)
528 continue;
529
530 // If we have a single predecessor, removeIncomingValue may have erased the
531 // PHI node itself.
532 if (NumPreds == 1)
533 continue;
534
535 // Try to replace the PHI node with a constant value.
536 if (Value *PhiConstant = Phi.hasConstantValue()) {
537 Phi.replaceAllUsesWith(V: PhiConstant);
538 Phi.eraseFromParent();
539 }
540 }
541}
542
543bool BasicBlock::canSplitPredecessors() const {
544 const Instruction *FirstNonPHI = getFirstNonPHI();
545 if (isa<LandingPadInst>(Val: FirstNonPHI))
546 return true;
547 // This is perhaps a little conservative because constructs like
548 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
549 // cannot handle such things just yet.
550 if (FirstNonPHI->isEHPad())
551 return false;
552 return true;
553}
554
555bool BasicBlock::isLegalToHoistInto() const {
556 auto *Term = getTerminator();
557 // No terminator means the block is under construction.
558 if (!Term)
559 return true;
560
561 // If the block has no successors, there can be no instructions to hoist.
562 assert(Term->getNumSuccessors() > 0);
563
564 // Instructions should not be hoisted across special terminators, which may
565 // have side effects or return values.
566 return !Term->isSpecialTerminator();
567}
568
569bool BasicBlock::isEntryBlock() const {
570 const Function *F = getParent();
571 assert(F && "Block must have a parent function to use this API");
572 return this == &F->getEntryBlock();
573}
574
575BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
576 bool Before) {
577 if (Before)
578 return splitBasicBlockBefore(I, BBName);
579
580 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
581 assert(I != InstList.end() &&
582 "Trying to get me to create degenerate basic block!");
583
584 BasicBlock *New = BasicBlock::Create(Context&: getContext(), Name: BBName, Parent: getParent(),
585 InsertBefore: this->getNextNode());
586
587 // Save DebugLoc of split point before invalidating iterator.
588 DebugLoc Loc = I->getStableDebugLoc();
589 // Move all of the specified instructions from the original basic block into
590 // the new basic block.
591 New->splice(ToIt: New->end(), FromBB: this, FromBeginIt: I, FromEndIt: end());
592
593 // Add a branch instruction to the newly formed basic block.
594 BranchInst *BI = BranchInst::Create(IfTrue: New, InsertBefore: this);
595 BI->setDebugLoc(Loc);
596
597 // Now we must loop through all of the successors of the New block (which
598 // _were_ the successors of the 'this' block), and update any PHI nodes in
599 // successors. If there were PHI nodes in the successors, then they need to
600 // know that incoming branches will be from New, not from Old (this).
601 //
602 New->replaceSuccessorsPhiUsesWith(Old: this, New);
603 return New;
604}
605
606BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
607 assert(getTerminator() &&
608 "Can't use splitBasicBlockBefore on degenerate BB!");
609 assert(I != InstList.end() &&
610 "Trying to get me to create degenerate basic block!");
611
612 assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
613 "cannot split on multi incoming phis");
614
615 BasicBlock *New = BasicBlock::Create(Context&: getContext(), Name: BBName, Parent: getParent(), InsertBefore: this);
616 // Save DebugLoc of split point before invalidating iterator.
617 DebugLoc Loc = I->getDebugLoc();
618 // Move all of the specified instructions from the original basic block into
619 // the new basic block.
620 New->splice(ToIt: New->end(), FromBB: this, FromBeginIt: begin(), FromEndIt: I);
621
622 // Loop through all of the predecessors of the 'this' block (which will be the
623 // predecessors of the New block), replace the specified successor 'this'
624 // block to point at the New block and update any PHI nodes in 'this' block.
625 // If there were PHI nodes in 'this' block, the PHI nodes are updated
626 // to reflect that the incoming branches will be from the New block and not
627 // from predecessors of the 'this' block.
628 // Save predecessors to separate vector before modifying them.
629 SmallVector<BasicBlock *, 4> Predecessors;
630 for (BasicBlock *Pred : predecessors(BB: this))
631 Predecessors.push_back(Elt: Pred);
632 for (BasicBlock *Pred : Predecessors) {
633 Instruction *TI = Pred->getTerminator();
634 TI->replaceSuccessorWith(OldBB: this, NewBB: New);
635 this->replacePhiUsesWith(Old: Pred, New);
636 }
637 // Add a branch instruction from "New" to "this" Block.
638 BranchInst *BI = BranchInst::Create(IfTrue: this, InsertBefore: New);
639 BI->setDebugLoc(Loc);
640
641 return New;
642}
643
644BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt,
645 BasicBlock::iterator ToIt) {
646 for (Instruction &I : make_early_inc_range(Range: make_range(x: FromIt, y: ToIt)))
647 I.eraseFromParent();
648 return ToIt;
649}
650
651void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
652 // N.B. This might not be a complete BasicBlock, so don't assume
653 // that it ends with a non-phi instruction.
654 for (Instruction &I : *this) {
655 PHINode *PN = dyn_cast<PHINode>(Val: &I);
656 if (!PN)
657 break;
658 PN->replaceIncomingBlockWith(Old, New);
659 }
660}
661
662void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
663 BasicBlock *New) {
664 Instruction *TI = getTerminator();
665 if (!TI)
666 // Cope with being called on a BasicBlock that doesn't have a terminator
667 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
668 return;
669 for (BasicBlock *Succ : successors(I: TI))
670 Succ->replacePhiUsesWith(Old, New);
671}
672
673void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
674 this->replaceSuccessorsPhiUsesWith(Old: this, New);
675}
676
677bool BasicBlock::isLandingPad() const {
678 return isa<LandingPadInst>(Val: getFirstNonPHI());
679}
680
681const LandingPadInst *BasicBlock::getLandingPadInst() const {
682 return dyn_cast<LandingPadInst>(Val: getFirstNonPHI());
683}
684
685std::optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
686 const Instruction *TI = getTerminator();
687 if (MDNode *MDIrrLoopHeader =
688 TI->getMetadata(KindID: LLVMContext::MD_irr_loop)) {
689 MDString *MDName = cast<MDString>(Val: MDIrrLoopHeader->getOperand(I: 0));
690 if (MDName->getString() == "loop_header_weight") {
691 auto *CI = mdconst::extract<ConstantInt>(MD: MDIrrLoopHeader->getOperand(I: 1));
692 return std::optional<uint64_t>(CI->getValue().getZExtValue());
693 }
694 }
695 return std::nullopt;
696}
697
698BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
699 while (isa<DbgInfoIntrinsic>(Val: It))
700 ++It;
701 return It;
702}
703
704void BasicBlock::renumberInstructions() {
705 unsigned Order = 0;
706 for (Instruction &I : *this)
707 I.Order = Order++;
708
709 // Set the bit to indicate that the instruction order valid and cached.
710 BasicBlockBits Bits = getBasicBlockBits();
711 Bits.InstrOrderValid = true;
712 setBasicBlockBits(Bits);
713
714 NumInstrRenumberings++;
715}
716
717void BasicBlock::flushTerminatorDbgRecords() {
718 // If we erase the terminator in a block, any DbgRecords will sink and "fall
719 // off the end", existing after any terminator that gets inserted. With
720 // dbg.value intrinsics we would just insert the terminator at end() and
721 // the dbg.values would come before the terminator. With DbgRecords, we must
722 // do this manually.
723 // To get out of this unfortunate form, whenever we insert a terminator,
724 // check whether there's anything trailing at the end and move those
725 // DbgRecords in front of the terminator.
726
727 // Do nothing if we're not in new debug-info format.
728 if (!IsNewDbgInfoFormat)
729 return;
730
731 // If there's no terminator, there's nothing to do.
732 Instruction *Term = getTerminator();
733 if (!Term)
734 return;
735
736 // Are there any dangling DbgRecords?
737 DbgMarker *TrailingDbgRecords = getTrailingDbgRecords();
738 if (!TrailingDbgRecords)
739 return;
740
741 // Transfer DbgRecords from the trailing position onto the terminator.
742 createMarker(I: Term);
743 Term->DebugMarker->absorbDebugValues(Src&: *TrailingDbgRecords, InsertAtHead: false);
744 TrailingDbgRecords->eraseFromParent();
745 deleteTrailingDbgRecords();
746}
747
748void BasicBlock::spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest,
749 BasicBlock *Src,
750 BasicBlock::iterator First,
751 BasicBlock::iterator Last) {
752 // Imagine the folowing:
753 //
754 // bb1:
755 // dbg.value(...
756 // ret i32 0
757 //
758 // If an optimisation pass attempts to splice the contents of the block from
759 // BB1->begin() to BB1->getTerminator(), then the dbg.value will be
760 // transferred to the destination.
761 // However, in the "new" DbgRecord format for debug-info, that range is empty:
762 // begin() returns an iterator to the terminator, as there will only be a
763 // single instruction in the block. We must piece together from the bits set
764 // in the iterators whether there was the intention to transfer any debug
765 // info.
766
767 // If we're not in "new" debug-info format, do nothing.
768 if (!IsNewDbgInfoFormat)
769 return;
770
771 assert(First == Last);
772 bool InsertAtHead = Dest.getHeadBit();
773 bool ReadFromHead = First.getHeadBit();
774
775 // If the source block is completely empty, including no terminator, then
776 // transfer any trailing DbgRecords that are still hanging around. This can
777 // occur when a block is optimised away and the terminator has been moved
778 // somewhere else.
779 if (Src->empty()) {
780 DbgMarker *SrcTrailingDbgRecords = Src->getTrailingDbgRecords();
781 if (!SrcTrailingDbgRecords)
782 return;
783
784 Dest->adoptDbgRecords(BB: Src, It: Src->end(), InsertAtHead);
785 // adoptDbgRecords should have released the trailing DbgRecords.
786 assert(!Src->getTrailingDbgRecords());
787 return;
788 }
789
790 // There are instructions in this block; if the First iterator was
791 // with begin() / getFirstInsertionPt() then the caller intended debug-info
792 // at the start of the block to be transferred. Return otherwise.
793 if (Src->empty() || First != Src->begin() || !ReadFromHead)
794 return;
795
796 // Is there actually anything to transfer?
797 if (!First->hasDbgRecords())
798 return;
799
800 createMarker(It: Dest)->absorbDebugValues(Src&: *First->DebugMarker, InsertAtHead);
801
802 return;
803}
804
805void BasicBlock::spliceDebugInfo(BasicBlock::iterator Dest, BasicBlock *Src,
806 BasicBlock::iterator First,
807 BasicBlock::iterator Last) {
808 /* Do a quick normalisation before calling the real splice implementation. We
809 might be operating on a degenerate basic block that has no instructions
810 in it, a legitimate transient state. In that case, Dest will be end() and
811 any DbgRecords temporarily stored in the TrailingDbgRecords map in
812 LLVMContext. We might illustrate it thus:
813
814 Dest
815 |
816 this-block: ~~~~~~~~
817 Src-block: ++++B---B---B---B:::C
818 | |
819 First Last
820
821 However: does the caller expect the "~" DbgRecords to end up before or
822 after the spliced segment? This is communciated in the "Head" bit of Dest,
823 which signals whether the caller called begin() or end() on this block.
824
825 If the head bit is set, then all is well, we leave DbgRecords trailing just
826 like how dbg.value instructions would trail after instructions spliced to
827 the beginning of this block.
828
829 If the head bit isn't set, then try to jam the "~" DbgRecords onto the
830 front of the First instruction, then splice like normal, which joins the
831 "~" DbgRecords with the "+" DbgRecords. However if the "+" DbgRecords are
832 supposed to be left behind in Src, then:
833 * detach the "+" DbgRecords,
834 * move the "~" DbgRecords onto First,
835 * splice like normal,
836 * replace the "+" DbgRecords onto the Last position.
837 Complicated, but gets the job done. */
838
839 // If we're inserting at end(), and not in front of dangling DbgRecords, then
840 // move the DbgRecords onto "First". They'll then be moved naturally in the
841 // splice process.
842 DbgMarker *MoreDanglingDbgRecords = nullptr;
843 DbgMarker *OurTrailingDbgRecords = getTrailingDbgRecords();
844 if (Dest == end() && !Dest.getHeadBit() && OurTrailingDbgRecords) {
845 // Are the "+" DbgRecords not supposed to move? If so, detach them
846 // temporarily.
847 if (!First.getHeadBit() && First->hasDbgRecords()) {
848 MoreDanglingDbgRecords = Src->getMarker(It: First);
849 MoreDanglingDbgRecords->removeFromParent();
850 }
851
852 if (First->hasDbgRecords()) {
853 // Place them at the front, it would look like this:
854 // Dest
855 // |
856 // this-block:
857 // Src-block: ~~~~~~~~++++B---B---B---B:::C
858 // | |
859 // First Last
860 First->adoptDbgRecords(BB: this, It: end(), InsertAtHead: true);
861 } else {
862 // No current marker, create one and absorb in. (FIXME: we can avoid an
863 // allocation in the future).
864 DbgMarker *CurMarker = Src->createMarker(I: &*First);
865 CurMarker->absorbDebugValues(Src&: *OurTrailingDbgRecords, InsertAtHead: false);
866 OurTrailingDbgRecords->eraseFromParent();
867 }
868 deleteTrailingDbgRecords();
869 First.setHeadBit(true);
870 }
871
872 // Call the main debug-info-splicing implementation.
873 spliceDebugInfoImpl(ToIt: Dest, FromBB: Src, FromBeginIt: First, FromEndIt: Last);
874
875 // Do we have some "+" DbgRecords hanging around that weren't supposed to
876 // move, and we detached to make things easier?
877 if (!MoreDanglingDbgRecords)
878 return;
879
880 // FIXME: we could avoid an allocation here sometimes. (adoptDbgRecords
881 // requires an iterator).
882 DbgMarker *LastMarker = Src->createMarker(It: Last);
883 LastMarker->absorbDebugValues(Src&: *MoreDanglingDbgRecords, InsertAtHead: true);
884 MoreDanglingDbgRecords->eraseFromParent();
885}
886
887void BasicBlock::spliceDebugInfoImpl(BasicBlock::iterator Dest, BasicBlock *Src,
888 BasicBlock::iterator First,
889 BasicBlock::iterator Last) {
890 // Find out where to _place_ these dbg.values; if InsertAtHead is specified,
891 // this will be at the start of Dest's debug value range, otherwise this is
892 // just Dest's marker.
893 bool InsertAtHead = Dest.getHeadBit();
894 bool ReadFromHead = First.getHeadBit();
895 // Use this flag to signal the abnormal case, where we don't want to copy the
896 // DbgRecords ahead of the "Last" position.
897 bool ReadFromTail = !Last.getTailBit();
898 bool LastIsEnd = (Last == Src->end());
899
900 /*
901 Here's an illustration of what we're about to do. We have two blocks, this
902 and Src, and two segments of list. Each instruction is marked by a capital
903 while potential DbgRecord debug-info is marked out by "-" characters and a
904 few other special characters (+:=) where I want to highlight what's going
905 on.
906
907 Dest
908 |
909 this-block: A----A----A ====A----A----A----A---A---A
910 Src-block ++++B---B---B---B:::C
911 | |
912 First Last
913
914 The splice method is going to take all the instructions from First up to
915 (but not including) Last and insert them in _front_ of Dest, forming one
916 long list. All the DbgRecords attached to instructions _between_ First and
917 Last need no maintenence. However, we have to do special things with the
918 DbgRecords marked with the +:= characters. We only have three positions:
919 should the "+" DbgRecords be transferred, and if so to where? Do we move the
920 ":" DbgRecords? Would they go in front of the "=" DbgRecords, or should the
921 "=" DbgRecords go before "+" DbgRecords?
922
923 We're told which way it should be by the bits carried in the iterators. The
924 "Head" bit indicates whether the specified position is supposed to be at the
925 front of the attached DbgRecords (true) or not (false). The Tail bit is true
926 on the other end of a range: is the range intended to include DbgRecords up
927 to the end (false) or not (true).
928
929 FIXME: the tail bit doesn't need to be distinct from the head bit, we could
930 combine them.
931
932 Here are some examples of different configurations:
933
934 Dest.Head = true, First.Head = true, Last.Tail = false
935
936 this-block: A----A----A++++B---B---B---B:::====A----A----A----A---A---A
937 | |
938 First Dest
939
940 Wheras if we didn't want to read from the Src list,
941
942 Dest.Head = true, First.Head = false, Last.Tail = false
943
944 this-block: A----A----AB---B---B---B:::====A----A----A----A---A---A
945 | |
946 First Dest
947
948 Or if we didn't want to insert at the head of Dest:
949
950 Dest.Head = false, First.Head = false, Last.Tail = false
951
952 this-block: A----A----A====B---B---B---B:::A----A----A----A---A---A
953 | |
954 First Dest
955
956 Tests for these various configurations can be found in the unit test file
957 BasicBlockDbgInfoTest.cpp.
958
959 */
960
961 // Detach the marker at Dest -- this lets us move the "====" DbgRecords
962 // around.
963 DbgMarker *DestMarker = nullptr;
964 if ((DestMarker = getMarker(It: Dest))) {
965 if (Dest == end()) {
966 assert(DestMarker == getTrailingDbgRecords());
967 deleteTrailingDbgRecords();
968 } else {
969 DestMarker->removeFromParent();
970 }
971 }
972
973 // If we're moving the tail range of DbgRecords (":::"), absorb them into the
974 // front of the DbgRecords at Dest.
975 if (ReadFromTail && Src->getMarker(It: Last)) {
976 DbgMarker *FromLast = Src->getMarker(It: Last);
977 if (LastIsEnd) {
978 if (Dest == end()) {
979 // Abosrb the trailing markers from Src.
980 assert(FromLast == Src->getTrailingDbgRecords());
981 createMarker(It: Dest)->absorbDebugValues(Src&: *FromLast, InsertAtHead: true);
982 FromLast->eraseFromParent();
983 Src->deleteTrailingDbgRecords();
984 } else {
985 // adoptDbgRecords will release any trailers.
986 Dest->adoptDbgRecords(BB: Src, It: Last, InsertAtHead: true);
987 }
988 assert(!Src->getTrailingDbgRecords());
989 } else {
990 // FIXME: can we use adoptDbgRecords here to reduce allocations?
991 DbgMarker *OntoDest = createMarker(It: Dest);
992 OntoDest->absorbDebugValues(Src&: *FromLast, InsertAtHead: true);
993 }
994 }
995
996 // If we're _not_ reading from the head of First, i.e. the "++++" DbgRecords,
997 // move their markers onto Last. They remain in the Src block. No action
998 // needed.
999 if (!ReadFromHead && First->hasDbgRecords()) {
1000 if (Last != Src->end()) {
1001 Last->adoptDbgRecords(BB: Src, It: First, InsertAtHead: true);
1002 } else {
1003 DbgMarker *OntoLast = Src->createMarker(It: Last);
1004 DbgMarker *FromFirst = Src->createMarker(It: First);
1005 // Always insert at front of Last.
1006 OntoLast->absorbDebugValues(Src&: *FromFirst, InsertAtHead: true);
1007 }
1008 }
1009
1010 // Finally, do something with the "====" DbgRecords we detached.
1011 if (DestMarker) {
1012 if (InsertAtHead) {
1013 // Insert them at the end of the DbgRecords at Dest. The "::::" DbgRecords
1014 // might be in front of them.
1015 DbgMarker *NewDestMarker = createMarker(It: Dest);
1016 NewDestMarker->absorbDebugValues(Src&: *DestMarker, InsertAtHead: false);
1017 } else {
1018 // Insert them right at the start of the range we moved, ahead of First
1019 // and the "++++" DbgRecords.
1020 // This also covers the rare circumstance where we insert at end(), and we
1021 // did not generate the iterator with begin() / getFirstInsertionPt(),
1022 // meaning any trailing debug-info at the end of the block would
1023 // "normally" have been pushed in front of "First". We move it there now.
1024 DbgMarker *FirstMarker = createMarker(It: First);
1025 FirstMarker->absorbDebugValues(Src&: *DestMarker, InsertAtHead: true);
1026 }
1027 DestMarker->eraseFromParent();
1028 }
1029}
1030
1031void BasicBlock::splice(iterator Dest, BasicBlock *Src, iterator First,
1032 iterator Last) {
1033 assert(Src->IsNewDbgInfoFormat == IsNewDbgInfoFormat);
1034
1035#ifdef EXPENSIVE_CHECKS
1036 // Check that First is before Last.
1037 auto FromBBEnd = Src->end();
1038 for (auto It = First; It != Last; ++It)
1039 assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
1040#endif // EXPENSIVE_CHECKS
1041
1042 // Lots of horrible special casing for empty transfers: the dbg.values between
1043 // two positions could be spliced in dbg.value mode.
1044 if (First == Last) {
1045 spliceDebugInfoEmptyBlock(Dest, Src, First, Last);
1046 return;
1047 }
1048
1049 // Handle non-instr debug-info specific juggling.
1050 if (IsNewDbgInfoFormat)
1051 spliceDebugInfo(Dest, Src, First, Last);
1052
1053 // And move the instructions.
1054 getInstList().splice(where: Dest, L2&: Src->getInstList(), first: First, last: Last);
1055
1056 flushTerminatorDbgRecords();
1057}
1058
1059void BasicBlock::insertDbgRecordAfter(DbgRecord *DR, Instruction *I) {
1060 assert(IsNewDbgInfoFormat);
1061 assert(I->getParent() == this);
1062
1063 iterator NextIt = std::next(x: I->getIterator());
1064 DbgMarker *NextMarker = createMarker(It: NextIt);
1065 NextMarker->insertDbgRecord(New: DR, InsertAtHead: true);
1066}
1067
1068void BasicBlock::insertDbgRecordBefore(DbgRecord *DR,
1069 InstListType::iterator Where) {
1070 assert(Where == end() || Where->getParent() == this);
1071 bool InsertAtHead = Where.getHeadBit();
1072 DbgMarker *M = createMarker(It: Where);
1073 M->insertDbgRecord(New: DR, InsertAtHead);
1074}
1075
1076DbgMarker *BasicBlock::getNextMarker(Instruction *I) {
1077 return getMarker(It: std::next(x: I->getIterator()));
1078}
1079
1080DbgMarker *BasicBlock::getMarker(InstListType::iterator It) {
1081 if (It == end()) {
1082 DbgMarker *DM = getTrailingDbgRecords();
1083 return DM;
1084 }
1085 return It->DebugMarker;
1086}
1087
1088void BasicBlock::reinsertInstInDbgRecords(
1089 Instruction *I, std::optional<DbgRecord::self_iterator> Pos) {
1090 // "I" was originally removed from a position where it was
1091 // immediately in front of Pos. Any DbgRecords on that position then "fell
1092 // down" onto Pos. "I" has been re-inserted at the front of that wedge of
1093 // DbgRecords, shuffle them around to represent the original positioning. To
1094 // illustrate:
1095 //
1096 // Instructions: I1---I---I0
1097 // DbgRecords: DDD DDD
1098 //
1099 // Instruction "I" removed,
1100 //
1101 // Instructions: I1------I0
1102 // DbgRecords: DDDDDD
1103 // ^Pos
1104 //
1105 // Instruction "I" re-inserted (now):
1106 //
1107 // Instructions: I1---I------I0
1108 // DbgRecords: DDDDDD
1109 // ^Pos
1110 //
1111 // After this method completes:
1112 //
1113 // Instructions: I1---I---I0
1114 // DbgRecords: DDD DDD
1115
1116 // This happens if there were no DbgRecords on I0. Are there now DbgRecords
1117 // there?
1118 if (!Pos) {
1119 DbgMarker *NextMarker = getNextMarker(I);
1120 if (!NextMarker)
1121 return;
1122 if (NextMarker->StoredDbgRecords.empty())
1123 return;
1124 // There are DbgMarkers there now -- they fell down from "I".
1125 DbgMarker *ThisMarker = createMarker(I);
1126 ThisMarker->absorbDebugValues(Src&: *NextMarker, InsertAtHead: false);
1127 return;
1128 }
1129
1130 // Is there even a range of DbgRecords to move?
1131 DbgMarker *DM = (*Pos)->getMarker();
1132 auto Range = make_range(x: DM->StoredDbgRecords.begin(), y: (*Pos));
1133 if (Range.begin() == Range.end())
1134 return;
1135
1136 // Otherwise: splice.
1137 DbgMarker *ThisMarker = createMarker(I);
1138 assert(ThisMarker->StoredDbgRecords.empty());
1139 ThisMarker->absorbDebugValues(Range, Src&: *DM, InsertAtHead: true);
1140}
1141
1142#ifndef NDEBUG
1143/// In asserts builds, this checks the numbering. In non-asserts builds, it
1144/// is defined as a no-op inline function in BasicBlock.h.
1145void BasicBlock::validateInstrOrdering() const {
1146 if (!isInstrOrderValid())
1147 return;
1148 const Instruction *Prev = nullptr;
1149 for (const Instruction &I : *this) {
1150 assert((!Prev || Prev->comesBefore(&I)) &&
1151 "cached instruction ordering is incorrect");
1152 Prev = &I;
1153 }
1154}
1155#endif
1156
1157void BasicBlock::setTrailingDbgRecords(DbgMarker *foo) {
1158 getContext().pImpl->setTrailingDbgRecords(B: this, M: foo);
1159}
1160
1161DbgMarker *BasicBlock::getTrailingDbgRecords() {
1162 return getContext().pImpl->getTrailingDbgRecords(B: this);
1163}
1164
1165void BasicBlock::deleteTrailingDbgRecords() {
1166 getContext().pImpl->deleteTrailingDbgRecords(B: this);
1167}
1168