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