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