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