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