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