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 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
557 assert(I != InstList.end() &&
558 "Trying to get me to create degenerate basic block!");
559
560 BasicBlock *New = BasicBlock::Create(Context&: getContext(), Name: BBName, Parent: getParent(),
561 InsertBefore: this->getNextNode());
562
563 // Save DebugLoc of split point before invalidating iterator.
564 DebugLoc Loc = I->getStableDebugLoc();
565 if (Loc)
566 Loc = Loc->getWithoutAtom();
567
568 // Move all of the specified instructions from the original basic block into
569 // the new basic block.
570 New->splice(ToIt: New->end(), FromBB: this, FromBeginIt: I, FromEndIt: end());
571
572 // Add a branch instruction to the newly formed basic block.
573 BranchInst *BI = BranchInst::Create(IfTrue: New, InsertBefore: this);
574 BI->setDebugLoc(Loc);
575
576 // Now we must loop through all of the successors of the New block (which
577 // _were_ the successors of the 'this' block), and update any PHI nodes in
578 // successors. If there were PHI nodes in the successors, then they need to
579 // know that incoming branches will be from New, not from Old (this).
580 //
581 New->replaceSuccessorsPhiUsesWith(Old: this, New);
582 return New;
583}
584
585BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
586 assert(getTerminator() &&
587 "Can't use splitBasicBlockBefore on degenerate BB!");
588 assert(I != InstList.end() &&
589 "Trying to get me to create degenerate basic block!");
590
591 assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
592 "cannot split on multi incoming phis");
593
594 BasicBlock *New = BasicBlock::Create(Context&: getContext(), Name: BBName, Parent: getParent(), InsertBefore: this);
595 // Save DebugLoc of split point before invalidating iterator.
596 DebugLoc Loc = I->getDebugLoc();
597 if (Loc)
598 Loc = Loc->getWithoutAtom();
599
600 // Move all of the specified instructions from the original basic block into
601 // the new basic block.
602 New->splice(ToIt: New->end(), FromBB: this, FromBeginIt: begin(), FromEndIt: I);
603
604 // Loop through all of the predecessors of the 'this' block (which will be the
605 // predecessors of the New block), replace the specified successor 'this'
606 // block to point at the New block and update any PHI nodes in 'this' block.
607 // If there were PHI nodes in 'this' block, the PHI nodes are updated
608 // to reflect that the incoming branches will be from the New block and not
609 // from predecessors of the 'this' block.
610 // Save predecessors to separate vector before modifying them.
611 SmallVector<BasicBlock *, 4> Predecessors(predecessors(BB: this));
612 for (BasicBlock *Pred : Predecessors) {
613 Instruction *TI = Pred->getTerminator();
614 TI->replaceSuccessorWith(OldBB: this, NewBB: New);
615 this->replacePhiUsesWith(Old: Pred, New);
616 }
617 // Add a branch instruction from "New" to "this" Block.
618 BranchInst *BI = BranchInst::Create(IfTrue: this, InsertBefore: New);
619 BI->setDebugLoc(Loc);
620
621 return New;
622}
623
624BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt,
625 BasicBlock::iterator ToIt) {
626 for (Instruction &I : make_early_inc_range(Range: make_range(x: FromIt, y: ToIt)))
627 I.eraseFromParent();
628 return ToIt;
629}
630
631void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
632 // N.B. This might not be a complete BasicBlock, so don't assume
633 // that it ends with a non-phi instruction.
634 for (Instruction &I : *this) {
635 PHINode *PN = dyn_cast<PHINode>(Val: &I);
636 if (!PN)
637 break;
638 PN->replaceIncomingBlockWith(Old, New);
639 }
640}
641
642void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
643 BasicBlock *New) {
644 Instruction *TI = getTerminator();
645 if (!TI)
646 // Cope with being called on a BasicBlock that doesn't have a terminator
647 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
648 return;
649 for (BasicBlock *Succ : successors(I: TI))
650 Succ->replacePhiUsesWith(Old, New);
651}
652
653void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
654 this->replaceSuccessorsPhiUsesWith(Old: this, New);
655}
656
657bool BasicBlock::isLandingPad() const {
658 return isa<LandingPadInst>(Val: getFirstNonPHIIt());
659}
660
661const LandingPadInst *BasicBlock::getLandingPadInst() const {
662 return dyn_cast<LandingPadInst>(Val: getFirstNonPHIIt());
663}
664
665std::optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
666 const Instruction *TI = getTerminator();
667 if (MDNode *MDIrrLoopHeader =
668 TI->getMetadata(KindID: LLVMContext::MD_irr_loop)) {
669 MDString *MDName = cast<MDString>(Val: MDIrrLoopHeader->getOperand(I: 0));
670 if (MDName->getString() == "loop_header_weight") {
671 auto *CI = mdconst::extract<ConstantInt>(MD: MDIrrLoopHeader->getOperand(I: 1));
672 return std::optional<uint64_t>(CI->getValue().getZExtValue());
673 }
674 }
675 return std::nullopt;
676}
677
678BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
679 while (isa<DbgInfoIntrinsic>(Val: It))
680 ++It;
681 return It;
682}
683
684void BasicBlock::renumberInstructions() {
685 unsigned Order = 0;
686 for (Instruction &I : *this)
687 I.Order = Order++;
688
689 // Set the bit to indicate that the instruction order valid and cached.
690 SubclassOptionalData |= InstrOrderValid;
691
692 NumInstrRenumberings++;
693}
694
695void BasicBlock::flushTerminatorDbgRecords() {
696 // If we erase the terminator in a block, any DbgRecords will sink and "fall
697 // off the end", existing after any terminator that gets inserted. With
698 // dbg.value intrinsics we would just insert the terminator at end() and
699 // the dbg.values would come before the terminator. With DbgRecords, we must
700 // do this manually.
701 // To get out of this unfortunate form, whenever we insert a terminator,
702 // check whether there's anything trailing at the end and move those
703 // DbgRecords in front of the terminator.
704
705 // If there's no terminator, there's nothing to do.
706 Instruction *Term = getTerminator();
707 if (!Term)
708 return;
709
710 // Are there any dangling DbgRecords?
711 DbgMarker *TrailingDbgRecords = getTrailingDbgRecords();
712 if (!TrailingDbgRecords)
713 return;
714
715 // Transfer DbgRecords from the trailing position onto the terminator.
716 createMarker(I: Term);
717 Term->DebugMarker->absorbDebugValues(Src&: *TrailingDbgRecords, InsertAtHead: false);
718 TrailingDbgRecords->eraseFromParent();
719 deleteTrailingDbgRecords();
720}
721
722void BasicBlock::spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest,
723 BasicBlock *Src,
724 BasicBlock::iterator First,
725 BasicBlock::iterator Last) {
726 // Imagine the folowing:
727 //
728 // bb1:
729 // dbg.value(...
730 // ret i32 0
731 //
732 // If an optimisation pass attempts to splice the contents of the block from
733 // BB1->begin() to BB1->getTerminator(), then the dbg.value will be
734 // transferred to the destination.
735 // However, in the "new" DbgRecord format for debug-info, that range is empty:
736 // begin() returns an iterator to the terminator, as there will only be a
737 // single instruction in the block. We must piece together from the bits set
738 // in the iterators whether there was the intention to transfer any debug
739 // info.
740
741 assert(First == Last);
742 bool InsertAtHead = Dest.getHeadBit();
743 bool ReadFromHead = First.getHeadBit();
744
745 // If the source block is completely empty, including no terminator, then
746 // transfer any trailing DbgRecords that are still hanging around. This can
747 // occur when a block is optimised away and the terminator has been moved
748 // somewhere else.
749 if (Src->empty()) {
750 DbgMarker *SrcTrailingDbgRecords = Src->getTrailingDbgRecords();
751 if (!SrcTrailingDbgRecords)
752 return;
753
754 Dest->adoptDbgRecords(BB: Src, It: Src->end(), InsertAtHead);
755 // adoptDbgRecords should have released the trailing DbgRecords.
756 assert(!Src->getTrailingDbgRecords());
757 return;
758 }
759
760 // There are instructions in this block; if the First iterator was
761 // with begin() / getFirstInsertionPt() then the caller intended debug-info
762 // at the start of the block to be transferred. Return otherwise.
763 if (Src->empty() || First != Src->begin() || !ReadFromHead)
764 return;
765
766 // Is there actually anything to transfer?
767 if (!First->hasDbgRecords())
768 return;
769
770 createMarker(It: Dest)->absorbDebugValues(Src&: *First->DebugMarker, InsertAtHead);
771}
772
773void BasicBlock::spliceDebugInfo(BasicBlock::iterator Dest, BasicBlock *Src,
774 BasicBlock::iterator First,
775 BasicBlock::iterator Last) {
776 /* Do a quick normalisation before calling the real splice implementation. We
777 might be operating on a degenerate basic block that has no instructions
778 in it, a legitimate transient state. In that case, Dest will be end() and
779 any DbgRecords temporarily stored in the TrailingDbgRecords map in
780 LLVMContext. We might illustrate it thus:
781
782 Dest
783 |
784 this-block: ~~~~~~~~
785 Src-block: ++++B---B---B---B:::C
786 | |
787 First Last
788
789 However: does the caller expect the "~" DbgRecords to end up before or
790 after the spliced segment? This is communciated in the "Head" bit of Dest,
791 which signals whether the caller called begin() or end() on this block.
792
793 If the head bit is set, then all is well, we leave DbgRecords trailing just
794 like how dbg.value instructions would trail after instructions spliced to
795 the beginning of this block.
796
797 If the head bit isn't set, then try to jam the "~" DbgRecords onto the
798 front of the First instruction, then splice like normal, which joins the
799 "~" DbgRecords with the "+" DbgRecords. However if the "+" DbgRecords are
800 supposed to be left behind in Src, then:
801 * detach the "+" DbgRecords,
802 * move the "~" DbgRecords onto First,
803 * splice like normal,
804 * replace the "+" DbgRecords onto the Last position.
805 Complicated, but gets the job done. */
806
807 // If we're inserting at end(), and not in front of dangling DbgRecords, then
808 // move the DbgRecords onto "First". They'll then be moved naturally in the
809 // splice process.
810 DbgMarker *MoreDanglingDbgRecords = nullptr;
811 DbgMarker *OurTrailingDbgRecords = getTrailingDbgRecords();
812 if (Dest == end() && !Dest.getHeadBit() && OurTrailingDbgRecords) {
813 // Are the "+" DbgRecords not supposed to move? If so, detach them
814 // temporarily.
815 if (!First.getHeadBit() && First->hasDbgRecords()) {
816 MoreDanglingDbgRecords = Src->getMarker(It: First);
817 MoreDanglingDbgRecords->removeFromParent();
818 }
819
820 if (First->hasDbgRecords()) {
821 // Place them at the front, it would look like this:
822 // Dest
823 // |
824 // this-block:
825 // Src-block: ~~~~~~~~++++B---B---B---B:::C
826 // | |
827 // First Last
828 First->adoptDbgRecords(BB: this, It: end(), InsertAtHead: true);
829 } else {
830 // No current marker, create one and absorb in. (FIXME: we can avoid an
831 // allocation in the future).
832 DbgMarker *CurMarker = Src->createMarker(I: &*First);
833 CurMarker->absorbDebugValues(Src&: *OurTrailingDbgRecords, InsertAtHead: false);
834 OurTrailingDbgRecords->eraseFromParent();
835 }
836 deleteTrailingDbgRecords();
837 First.setHeadBit(true);
838 }
839
840 // Call the main debug-info-splicing implementation.
841 spliceDebugInfoImpl(ToIt: Dest, FromBB: Src, FromBeginIt: First, FromEndIt: Last);
842
843 // Do we have some "+" DbgRecords hanging around that weren't supposed to
844 // move, and we detached to make things easier?
845 if (!MoreDanglingDbgRecords)
846 return;
847
848 // FIXME: we could avoid an allocation here sometimes. (adoptDbgRecords
849 // requires an iterator).
850 DbgMarker *LastMarker = Src->createMarker(It: Last);
851 LastMarker->absorbDebugValues(Src&: *MoreDanglingDbgRecords, InsertAtHead: true);
852 MoreDanglingDbgRecords->eraseFromParent();
853}
854
855void BasicBlock::spliceDebugInfoImpl(BasicBlock::iterator Dest, BasicBlock *Src,
856 BasicBlock::iterator First,
857 BasicBlock::iterator Last) {
858 // Find out where to _place_ these dbg.values; if InsertAtHead is specified,
859 // this will be at the start of Dest's debug value range, otherwise this is
860 // just Dest's marker.
861 bool InsertAtHead = Dest.getHeadBit();
862 bool ReadFromHead = First.getHeadBit();
863 // Use this flag to signal the abnormal case, where we don't want to copy the
864 // DbgRecords ahead of the "Last" position.
865 bool ReadFromTail = !Last.getTailBit();
866 bool LastIsEnd = (Last == Src->end());
867
868 /*
869 Here's an illustration of what we're about to do. We have two blocks, this
870 and Src, and two segments of list. Each instruction is marked by a capital
871 while potential DbgRecord debug-info is marked out by "-" characters and a
872 few other special characters (+:=) where I want to highlight what's going
873 on.
874
875 Dest
876 |
877 this-block: A----A----A ====A----A----A----A---A---A
878 Src-block ++++B---B---B---B:::C
879 | |
880 First Last
881
882 The splice method is going to take all the instructions from First up to
883 (but not including) Last and insert them in _front_ of Dest, forming one
884 long list. All the DbgRecords attached to instructions _between_ First and
885 Last need no maintenence. However, we have to do special things with the
886 DbgRecords marked with the +:= characters. We only have three positions:
887 should the "+" DbgRecords be transferred, and if so to where? Do we move the
888 ":" DbgRecords? Would they go in front of the "=" DbgRecords, or should the
889 "=" DbgRecords go before "+" DbgRecords?
890
891 We're told which way it should be by the bits carried in the iterators. The
892 "Head" bit indicates whether the specified position is supposed to be at the
893 front of the attached DbgRecords (true) or not (false). The Tail bit is true
894 on the other end of a range: is the range intended to include DbgRecords up
895 to the end (false) or not (true).
896
897 FIXME: the tail bit doesn't need to be distinct from the head bit, we could
898 combine them.
899
900 Here are some examples of different configurations:
901
902 Dest.Head = true, First.Head = true, Last.Tail = false
903
904 this-block: A----A----A++++B---B---B---B:::====A----A----A----A---A---A
905 | |
906 First Dest
907
908 Wheras if we didn't want to read from the Src list,
909
910 Dest.Head = true, First.Head = false, Last.Tail = false
911
912 this-block: A----A----AB---B---B---B:::====A----A----A----A---A---A
913 | |
914 First Dest
915
916 Or if we didn't want to insert at the head of Dest:
917
918 Dest.Head = false, First.Head = false, Last.Tail = false
919
920 this-block: A----A----A====B---B---B---B:::A----A----A----A---A---A
921 | |
922 First Dest
923
924 Tests for these various configurations can be found in the unit test file
925 BasicBlockDbgInfoTest.cpp.
926
927 */
928
929 // Detach the marker at Dest -- this lets us move the "====" DbgRecords
930 // around.
931 DbgMarker *DestMarker = nullptr;
932 if ((DestMarker = getMarker(It: Dest))) {
933 if (Dest == end()) {
934 assert(DestMarker == getTrailingDbgRecords());
935 deleteTrailingDbgRecords();
936 } else {
937 DestMarker->removeFromParent();
938 }
939 }
940
941 // If we're moving the tail range of DbgRecords (":::"), absorb them into the
942 // front of the DbgRecords at Dest.
943 if (ReadFromTail && Src->getMarker(It: Last)) {
944 DbgMarker *FromLast = Src->getMarker(It: Last);
945 if (LastIsEnd) {
946 if (Dest == end()) {
947 // Abosrb the trailing markers from Src.
948 assert(FromLast == Src->getTrailingDbgRecords());
949 createMarker(It: Dest)->absorbDebugValues(Src&: *FromLast, InsertAtHead: true);
950 FromLast->eraseFromParent();
951 Src->deleteTrailingDbgRecords();
952 } else {
953 // adoptDbgRecords will release any trailers.
954 Dest->adoptDbgRecords(BB: Src, It: Last, InsertAtHead: true);
955 }
956 assert(!Src->getTrailingDbgRecords());
957 } else {
958 // FIXME: can we use adoptDbgRecords here to reduce allocations?
959 DbgMarker *OntoDest = createMarker(It: Dest);
960 OntoDest->absorbDebugValues(Src&: *FromLast, InsertAtHead: true);
961 }
962 }
963
964 // If we're _not_ reading from the head of First, i.e. the "++++" DbgRecords,
965 // move their markers onto Last. They remain in the Src block. No action
966 // needed.
967 if (!ReadFromHead && First->hasDbgRecords()) {
968 if (Last != Src->end()) {
969 Last->adoptDbgRecords(BB: Src, It: First, InsertAtHead: true);
970 } else {
971 DbgMarker *OntoLast = Src->createMarker(It: Last);
972 DbgMarker *FromFirst = Src->createMarker(It: First);
973 // Always insert at front of Last.
974 OntoLast->absorbDebugValues(Src&: *FromFirst, InsertAtHead: true);
975 }
976 }
977
978 // Finally, do something with the "====" DbgRecords we detached.
979 if (DestMarker) {
980 if (InsertAtHead) {
981 // Insert them at the end of the DbgRecords at Dest. The "::::" DbgRecords
982 // might be in front of them.
983 DbgMarker *NewDestMarker = createMarker(It: Dest);
984 NewDestMarker->absorbDebugValues(Src&: *DestMarker, InsertAtHead: false);
985 } else {
986 // Insert them right at the start of the range we moved, ahead of First
987 // and the "++++" DbgRecords.
988 // This also covers the rare circumstance where we insert at end(), and we
989 // did not generate the iterator with begin() / getFirstInsertionPt(),
990 // meaning any trailing debug-info at the end of the block would
991 // "normally" have been pushed in front of "First". We move it there now.
992 DbgMarker *FirstMarker = createMarker(It: First);
993 FirstMarker->absorbDebugValues(Src&: *DestMarker, InsertAtHead: true);
994 }
995 DestMarker->eraseFromParent();
996 }
997}
998
999void BasicBlock::splice(iterator Dest, BasicBlock *Src, iterator First,
1000 iterator Last) {
1001#ifdef EXPENSIVE_CHECKS
1002 // Check that First is before Last.
1003 auto FromBBEnd = Src->end();
1004 for (auto It = First; It != Last; ++It)
1005 assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
1006#endif // EXPENSIVE_CHECKS
1007
1008 // Lots of horrible special casing for empty transfers: the dbg.values between
1009 // two positions could be spliced in dbg.value mode.
1010 if (First == Last) {
1011 spliceDebugInfoEmptyBlock(Dest, Src, First, Last);
1012 return;
1013 }
1014
1015 spliceDebugInfo(Dest, Src, First, Last);
1016
1017 // And move the instructions.
1018 getInstList().splice(where: Dest, L2&: Src->getInstList(), first: First, last: Last);
1019
1020 flushTerminatorDbgRecords();
1021}
1022
1023void BasicBlock::insertDbgRecordAfter(DbgRecord *DR, Instruction *I) {
1024 assert(I->getParent() == this);
1025
1026 iterator NextIt = std::next(x: I->getIterator());
1027 DbgMarker *NextMarker = createMarker(It: NextIt);
1028 NextMarker->insertDbgRecord(New: DR, InsertAtHead: true);
1029}
1030
1031void BasicBlock::insertDbgRecordBefore(DbgRecord *DR,
1032 InstListType::iterator Where) {
1033 assert(Where == end() || Where->getParent() == this);
1034 bool InsertAtHead = Where.getHeadBit();
1035 DbgMarker *M = createMarker(It: Where);
1036 M->insertDbgRecord(New: DR, InsertAtHead);
1037}
1038
1039DbgMarker *BasicBlock::getNextMarker(Instruction *I) {
1040 return getMarker(It: std::next(x: I->getIterator()));
1041}
1042
1043DbgMarker *BasicBlock::getMarker(InstListType::iterator It) {
1044 if (It == end()) {
1045 DbgMarker *DM = getTrailingDbgRecords();
1046 return DM;
1047 }
1048 return It->DebugMarker;
1049}
1050
1051void BasicBlock::reinsertInstInDbgRecords(
1052 Instruction *I, std::optional<DbgRecord::self_iterator> Pos) {
1053 // "I" was originally removed from a position where it was
1054 // immediately in front of Pos. Any DbgRecords on that position then "fell
1055 // down" onto Pos. "I" has been re-inserted at the front of that wedge of
1056 // DbgRecords, shuffle them around to represent the original positioning. To
1057 // illustrate:
1058 //
1059 // Instructions: I1---I---I0
1060 // DbgRecords: DDD DDD
1061 //
1062 // Instruction "I" removed,
1063 //
1064 // Instructions: I1------I0
1065 // DbgRecords: DDDDDD
1066 // ^Pos
1067 //
1068 // Instruction "I" re-inserted (now):
1069 //
1070 // Instructions: I1---I------I0
1071 // DbgRecords: DDDDDD
1072 // ^Pos
1073 //
1074 // After this method completes:
1075 //
1076 // Instructions: I1---I---I0
1077 // DbgRecords: DDD DDD
1078
1079 // This happens if there were no DbgRecords on I0. Are there now DbgRecords
1080 // there?
1081 if (!Pos) {
1082 DbgMarker *NextMarker = getNextMarker(I);
1083 if (!NextMarker)
1084 return;
1085 if (NextMarker->StoredDbgRecords.empty())
1086 return;
1087 // There are DbgMarkers there now -- they fell down from "I".
1088 DbgMarker *ThisMarker = createMarker(I);
1089 ThisMarker->absorbDebugValues(Src&: *NextMarker, InsertAtHead: false);
1090 return;
1091 }
1092
1093 // Is there even a range of DbgRecords to move?
1094 DbgMarker *DM = (*Pos)->getMarker();
1095 auto Range = make_range(x: DM->StoredDbgRecords.begin(), y: (*Pos));
1096 if (Range.begin() == Range.end())
1097 return;
1098
1099 // Otherwise: splice.
1100 DbgMarker *ThisMarker = createMarker(I);
1101 assert(ThisMarker->StoredDbgRecords.empty());
1102 ThisMarker->absorbDebugValues(Range, Src&: *DM, InsertAtHead: true);
1103}
1104
1105#ifndef NDEBUG
1106/// In asserts builds, this checks the numbering. In non-asserts builds, it
1107/// is defined as a no-op inline function in BasicBlock.h.
1108void BasicBlock::validateInstrOrdering() const {
1109 if (!isInstrOrderValid())
1110 return;
1111 const Instruction *Prev = nullptr;
1112 for (const Instruction &I : *this) {
1113 assert((!Prev || Prev->comesBefore(&I)) &&
1114 "cached instruction ordering is incorrect");
1115 Prev = &I;
1116 }
1117}
1118#endif
1119
1120void BasicBlock::setTrailingDbgRecords(DbgMarker *foo) {
1121 getContext().pImpl->setTrailingDbgRecords(B: this, M: foo);
1122}
1123
1124DbgMarker *BasicBlock::getTrailingDbgRecords() {
1125 return getContext().pImpl->getTrailingDbgRecords(B: this);
1126}
1127
1128void BasicBlock::deleteTrailingDbgRecords() {
1129 getContext().pImpl->deleteTrailingDbgRecords(B: this);
1130}
1131