1//===- llvm/CodeGen/MachineBasicBlock.h -------------------------*- C++ -*-===//
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// Collect the sequence of machine instructions for a basic block.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
14#define LLVM_CODEGEN_MACHINEBASICBLOCK_H
15
16#include "llvm/ADT/DenseMapInfo.h"
17#include "llvm/ADT/GraphTraits.h"
18#include "llvm/ADT/SparseBitVector.h"
19#include "llvm/ADT/ilist.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineInstrBundleIterator.h"
24#include "llvm/IR/DebugLoc.h"
25#include "llvm/MC/LaneBitmask.h"
26#include "llvm/Support/BranchProbability.h"
27#include "llvm/Support/Compiler.h"
28#include <cassert>
29#include <cstdint>
30#include <iterator>
31#include <string>
32#include <vector>
33
34namespace llvm {
35
36class BasicBlock;
37class MachineDomTreeUpdater;
38class MachineFunction;
39class MachineLoopInfo;
40class MCSymbol;
41class ModuleSlotTracker;
42class Pass;
43class Printable;
44class SlotIndexes;
45class StringRef;
46class raw_ostream;
47class LiveIntervals;
48class LiveVariables;
49class TargetRegisterClass;
50class TargetRegisterInfo;
51
52// This structure uniquely identifies a basic block section.
53// Possible values are
54// {Type: Default, Number: (unsigned)} (These are regular section IDs)
55// {Type: Exception, Number: 0} (ExceptionSectionID)
56// {Type: Cold, Number: 0} (ColdSectionID)
57struct MBBSectionID {
58 enum SectionType {
59 Default = 0, // Regular section (these sections are distinguished by the
60 // Number field).
61 Exception, // Special section type for exception handling blocks
62 Cold, // Special section type for cold blocks
63 } Type;
64 unsigned Number;
65
66 MBBSectionID(unsigned N) : Type(Default), Number(N) {}
67
68 // Special unique sections for cold and exception blocks.
69 LLVM_ABI const static MBBSectionID ColdSectionID;
70 LLVM_ABI const static MBBSectionID ExceptionSectionID;
71
72 bool operator==(const MBBSectionID &Other) const {
73 return Type == Other.Type && Number == Other.Number;
74 }
75
76 bool operator!=(const MBBSectionID &Other) const { return !(*this == Other); }
77
78private:
79 // This is only used to construct the special cold and exception sections.
80 MBBSectionID(SectionType T) : Type(T), Number(0) {}
81};
82
83template <> struct DenseMapInfo<MBBSectionID> {
84 using TypeInfo = DenseMapInfo<MBBSectionID::SectionType>;
85 using NumberInfo = DenseMapInfo<unsigned>;
86
87 static inline MBBSectionID getEmptyKey() {
88 return MBBSectionID(NumberInfo::getEmptyKey());
89 }
90 static inline MBBSectionID getTombstoneKey() {
91 return MBBSectionID(NumberInfo::getTombstoneKey());
92 }
93 static unsigned getHashValue(const MBBSectionID &SecID) {
94 return detail::combineHashValue(a: TypeInfo::getHashValue(Val: SecID.Type),
95 b: NumberInfo::getHashValue(Val: SecID.Number));
96 }
97 static bool isEqual(const MBBSectionID &LHS, const MBBSectionID &RHS) {
98 return LHS == RHS;
99 }
100};
101
102// This structure represents the information for a basic block pertaining to
103// the basic block sections profile.
104struct UniqueBBID {
105 unsigned BaseID;
106 unsigned CloneID;
107};
108
109template <> struct ilist_traits<MachineInstr> {
110private:
111 friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
112
113 MachineBasicBlock *Parent;
114
115 using instr_iterator =
116 simple_ilist<MachineInstr, ilist_sentinel_tracking<true>>::iterator;
117
118public:
119 LLVM_ABI void addNodeToList(MachineInstr *N);
120 LLVM_ABI void removeNodeFromList(MachineInstr *N);
121 LLVM_ABI void transferNodesFromList(ilist_traits &FromList,
122 instr_iterator First,
123 instr_iterator Last);
124 LLVM_ABI void deleteNode(MachineInstr *MI);
125};
126
127class MachineBasicBlock
128 : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> {
129public:
130 /// Pair of physical register and lane mask.
131 /// This is not simply a std::pair typedef because the members should be named
132 /// clearly as they both have an integer type.
133 struct RegisterMaskPair {
134 public:
135 MCRegister PhysReg;
136 LaneBitmask LaneMask;
137
138 RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
139 : PhysReg(PhysReg), LaneMask(LaneMask) {}
140
141 bool operator==(const RegisterMaskPair &other) const {
142 return PhysReg == other.PhysReg && LaneMask == other.LaneMask;
143 }
144 };
145
146private:
147 using Instructions = ilist<MachineInstr, ilist_sentinel_tracking<true>>;
148
149 const BasicBlock *BB;
150 int Number;
151
152 /// The call frame size on entry to this basic block due to call frame setup
153 /// instructions in a predecessor. This is usually zero, unless basic blocks
154 /// are split in the middle of a call sequence.
155 ///
156 /// This information is only maintained until PrologEpilogInserter eliminates
157 /// call frame pseudos.
158 unsigned CallFrameSize = 0;
159
160 MachineFunction *xParent;
161 Instructions Insts;
162
163 /// Keep track of the predecessor / successor basic blocks.
164 SmallVector<MachineBasicBlock *, 4> Predecessors;
165 SmallVector<MachineBasicBlock *, 2> Successors;
166
167 /// Keep track of the probabilities to the successors. This vector has the
168 /// same order as Successors, or it is empty if we don't use it (disable
169 /// optimization).
170 std::vector<BranchProbability> Probs;
171 using probability_iterator = std::vector<BranchProbability>::iterator;
172 using const_probability_iterator =
173 std::vector<BranchProbability>::const_iterator;
174
175 std::optional<uint64_t> IrrLoopHeaderWeight;
176
177 /// Keep track of the physical registers that are livein of the basicblock.
178 using LiveInVector = std::vector<RegisterMaskPair>;
179 LiveInVector LiveIns;
180
181 /// Alignment of the basic block. One if the basic block does not need to be
182 /// aligned.
183 Align Alignment;
184 /// Maximum amount of bytes that can be added to align the basic block. If the
185 /// alignment cannot be reached in this many bytes, no bytes are emitted.
186 /// Zero to represent no maximum.
187 unsigned MaxBytesForAlignment = 0;
188
189 /// Indicate that this basic block is entered via an exception handler.
190 bool IsEHPad = false;
191
192 /// Indicate that this MachineBasicBlock is referenced somewhere other than
193 /// as predecessor/successor, a terminator MachineInstr, or a jump table.
194 bool MachineBlockAddressTaken = false;
195
196 /// If this MachineBasicBlock corresponds to an IR-level "blockaddress"
197 /// constant, this contains a pointer to that block.
198 BasicBlock *AddressTakenIRBlock = nullptr;
199
200 /// Indicate that this basic block needs its symbol be emitted regardless of
201 /// whether the flow just falls-through to it.
202 bool LabelMustBeEmitted = false;
203
204 /// Indicate that this basic block is the entry block of an EH scope, i.e.,
205 /// the block that used to have a catchpad or cleanuppad instruction in the
206 /// LLVM IR.
207 bool IsEHScopeEntry = false;
208
209 /// Indicates if this is a target of Windows EH Continuation Guard.
210 bool IsEHContTarget = false;
211
212 /// Indicate that this basic block is the entry block of an EH funclet.
213 bool IsEHFuncletEntry = false;
214
215 /// Indicate that this basic block is the entry block of a cleanup funclet.
216 bool IsCleanupFuncletEntry = false;
217
218 /// Fixed unique ID assigned to this basic block upon creation. Used with
219 /// basic block sections and basic block labels.
220 std::optional<UniqueBBID> BBID;
221
222 /// With basic block sections, this stores the Section ID of the basic block.
223 MBBSectionID SectionID{0};
224
225 // Indicate that this basic block begins a section.
226 bool IsBeginSection = false;
227
228 // Indicate that this basic block ends a section.
229 bool IsEndSection = false;
230
231 /// Indicate that this basic block is the indirect dest of an INLINEASM_BR.
232 bool IsInlineAsmBrIndirectTarget = false;
233
234 /// since getSymbol is a relatively heavy-weight operation, the symbol
235 /// is only computed once and is cached.
236 mutable MCSymbol *CachedMCSymbol = nullptr;
237
238 /// Cached MCSymbol for this block (used if IsEHContTarget).
239 mutable MCSymbol *CachedEHContMCSymbol = nullptr;
240
241 /// Marks the end of the basic block. Used during basic block sections to
242 /// calculate the size of the basic block, or the BB section ending with it.
243 mutable MCSymbol *CachedEndMCSymbol = nullptr;
244
245 // Intrusive list support
246 MachineBasicBlock() = default;
247
248 explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB);
249
250 ~MachineBasicBlock();
251
252 // MachineBasicBlocks are allocated and owned by MachineFunction.
253 friend class MachineFunction;
254
255public:
256 /// Return the LLVM basic block that this instance corresponded to originally.
257 /// Note that this may be NULL if this instance does not correspond directly
258 /// to an LLVM basic block.
259 const BasicBlock *getBasicBlock() const { return BB; }
260
261 /// Remove the reference to the underlying IR BasicBlock. This is for
262 /// reduction tools and should generally not be used.
263 void clearBasicBlock() {
264 BB = nullptr;
265 }
266
267 /// Check if there is a name of corresponding LLVM basic block.
268 LLVM_ABI bool hasName() const;
269
270 /// Return the name of the corresponding LLVM basic block, or an empty string.
271 LLVM_ABI StringRef getName() const;
272
273 /// Return a formatted string to identify this block and its parent function.
274 LLVM_ABI std::string getFullName() const;
275
276 /// Test whether this block is used as something other than the target
277 /// of a terminator, exception-handling target, or jump table. This is
278 /// either the result of an IR-level "blockaddress", or some form
279 /// of target-specific branch lowering.
280 ///
281 /// The name of this function `hasAddressTaken` implies that the address of
282 /// the block is known and used in a general sense, but not necessarily that
283 /// the address is used by an indirect branch instruction. So branch target
284 /// enforcement need not put a BTI instruction (or equivalent) at the start
285 /// of a block just because this function returns true. The decision about
286 /// whether to add a BTI can be more subtle than that, and depends on the
287 /// more detailed checks that this function aggregates together.
288 bool hasAddressTaken() const {
289 return MachineBlockAddressTaken || AddressTakenIRBlock ||
290 IsInlineAsmBrIndirectTarget;
291 }
292
293 /// Test whether this block is used as something other than the target of a
294 /// terminator, exception-handling target, jump table, or IR blockaddress.
295 /// For example, its address might be loaded into a register, or
296 /// stored in some branch table that isn't part of MachineJumpTableInfo.
297 ///
298 /// If this function returns true, it _does_ mean that branch target
299 /// enforcement needs to put a BTI or equivalent at the start of the block.
300 bool isMachineBlockAddressTaken() const { return MachineBlockAddressTaken; }
301
302 /// Test whether this block is the target of an IR BlockAddress. (There can
303 /// more than one MBB associated with an IR BB where the address is taken.)
304 ///
305 /// If this function returns true, it _does_ mean that branch target
306 /// enforcement needs to put a BTI or equivalent at the start of the block.
307 bool isIRBlockAddressTaken() const { return AddressTakenIRBlock; }
308
309 /// Retrieves the BasicBlock which corresponds to this MachineBasicBlock.
310 BasicBlock *getAddressTakenIRBlock() const { return AddressTakenIRBlock; }
311
312 /// Set this block to indicate that its address is used as something other
313 /// than the target of a terminator, exception-handling target, jump table,
314 /// or IR-level "blockaddress".
315 void setMachineBlockAddressTaken() { MachineBlockAddressTaken = true; }
316
317 /// Set this block to reflect that it corresponds to an IR-level basic block
318 /// with a BlockAddress.
319 void setAddressTakenIRBlock(BasicBlock *BB) { AddressTakenIRBlock = BB; }
320
321 /// Test whether this block must have its label emitted.
322 bool hasLabelMustBeEmitted() const { return LabelMustBeEmitted; }
323
324 /// Set this block to reflect that, regardless how we flow to it, we need
325 /// its label be emitted.
326 void setLabelMustBeEmitted() { LabelMustBeEmitted = true; }
327
328 /// Return the MachineFunction containing this basic block.
329 const MachineFunction *getParent() const { return xParent; }
330 MachineFunction *getParent() { return xParent; }
331
332 /// Returns true if the original IR terminator is an `indirectbr`. This
333 /// typically corresponds to a `goto` in C, rather than jump tables.
334 bool terminatorIsComputedGoto() const {
335 return back().isIndirectBranch() &&
336 llvm::all_of(Range: successors(), P: [](const MachineBasicBlock *Succ) {
337 return Succ->isIRBlockAddressTaken();
338 });
339 }
340
341 using instr_iterator = Instructions::iterator;
342 using const_instr_iterator = Instructions::const_iterator;
343 using reverse_instr_iterator = Instructions::reverse_iterator;
344 using const_reverse_instr_iterator = Instructions::const_reverse_iterator;
345
346 using iterator = MachineInstrBundleIterator<MachineInstr>;
347 using const_iterator = MachineInstrBundleIterator<const MachineInstr>;
348 using reverse_iterator = MachineInstrBundleIterator<MachineInstr, true>;
349 using const_reverse_iterator =
350 MachineInstrBundleIterator<const MachineInstr, true>;
351
352 unsigned size() const { return (unsigned)Insts.size(); }
353 LLVM_ABI bool sizeWithoutDebugLargerThan(unsigned Limit) const;
354 bool empty() const { return Insts.empty(); }
355
356 MachineInstr &instr_front() { return Insts.front(); }
357 MachineInstr &instr_back() { return Insts.back(); }
358 const MachineInstr &instr_front() const { return Insts.front(); }
359 const MachineInstr &instr_back() const { return Insts.back(); }
360
361 MachineInstr &front() { return Insts.front(); }
362 MachineInstr &back() { return *--end(); }
363 const MachineInstr &front() const { return Insts.front(); }
364 const MachineInstr &back() const { return *--end(); }
365
366 instr_iterator instr_begin() { return Insts.begin(); }
367 const_instr_iterator instr_begin() const { return Insts.begin(); }
368 instr_iterator instr_end() { return Insts.end(); }
369 const_instr_iterator instr_end() const { return Insts.end(); }
370 reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); }
371 const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
372 reverse_instr_iterator instr_rend () { return Insts.rend(); }
373 const_reverse_instr_iterator instr_rend () const { return Insts.rend(); }
374
375 using instr_range = iterator_range<instr_iterator>;
376 using const_instr_range = iterator_range<const_instr_iterator>;
377 instr_range instrs() { return instr_range(instr_begin(), instr_end()); }
378 const_instr_range instrs() const {
379 return const_instr_range(instr_begin(), instr_end());
380 }
381
382 iterator begin() { return instr_begin(); }
383 const_iterator begin() const { return instr_begin(); }
384 iterator end () { return instr_end(); }
385 const_iterator end () const { return instr_end(); }
386 reverse_iterator rbegin() {
387 return reverse_iterator::getAtBundleBegin(MI: instr_rbegin());
388 }
389 const_reverse_iterator rbegin() const {
390 return const_reverse_iterator::getAtBundleBegin(MI: instr_rbegin());
391 }
392 reverse_iterator rend() { return reverse_iterator(instr_rend()); }
393 const_reverse_iterator rend() const {
394 return const_reverse_iterator(instr_rend());
395 }
396
397 /// Support for MachineInstr::getNextNode().
398 static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) {
399 return &MachineBasicBlock::Insts;
400 }
401
402 inline iterator_range<iterator> terminators() {
403 return make_range(x: getFirstTerminator(), y: end());
404 }
405 inline iterator_range<const_iterator> terminators() const {
406 return make_range(x: getFirstTerminator(), y: end());
407 }
408
409 /// Returns a range that iterates over the phis in the basic block.
410 inline iterator_range<iterator> phis() {
411 return make_range(x: begin(), y: getFirstNonPHI());
412 }
413 inline iterator_range<const_iterator> phis() const {
414 return const_cast<MachineBasicBlock *>(this)->phis();
415 }
416
417 // Machine-CFG iterators
418 using pred_iterator = SmallVectorImpl<MachineBasicBlock *>::iterator;
419 using const_pred_iterator =
420 SmallVectorImpl<MachineBasicBlock *>::const_iterator;
421 using succ_iterator = SmallVectorImpl<MachineBasicBlock *>::iterator;
422 using const_succ_iterator =
423 SmallVectorImpl<MachineBasicBlock *>::const_iterator;
424 using pred_reverse_iterator =
425 SmallVectorImpl<MachineBasicBlock *>::reverse_iterator;
426 using const_pred_reverse_iterator =
427 SmallVectorImpl<MachineBasicBlock *>::const_reverse_iterator;
428 using succ_reverse_iterator =
429 SmallVectorImpl<MachineBasicBlock *>::reverse_iterator;
430 using const_succ_reverse_iterator =
431 SmallVectorImpl<MachineBasicBlock *>::const_reverse_iterator;
432 pred_iterator pred_begin() { return Predecessors.begin(); }
433 const_pred_iterator pred_begin() const { return Predecessors.begin(); }
434 pred_iterator pred_end() { return Predecessors.end(); }
435 const_pred_iterator pred_end() const { return Predecessors.end(); }
436 pred_reverse_iterator pred_rbegin()
437 { return Predecessors.rbegin();}
438 const_pred_reverse_iterator pred_rbegin() const
439 { return Predecessors.rbegin();}
440 pred_reverse_iterator pred_rend()
441 { return Predecessors.rend(); }
442 const_pred_reverse_iterator pred_rend() const
443 { return Predecessors.rend(); }
444 unsigned pred_size() const {
445 return (unsigned)Predecessors.size();
446 }
447 bool pred_empty() const { return Predecessors.empty(); }
448 succ_iterator succ_begin() { return Successors.begin(); }
449 const_succ_iterator succ_begin() const { return Successors.begin(); }
450 succ_iterator succ_end() { return Successors.end(); }
451 const_succ_iterator succ_end() const { return Successors.end(); }
452 succ_reverse_iterator succ_rbegin()
453 { return Successors.rbegin(); }
454 const_succ_reverse_iterator succ_rbegin() const
455 { return Successors.rbegin(); }
456 succ_reverse_iterator succ_rend()
457 { return Successors.rend(); }
458 const_succ_reverse_iterator succ_rend() const
459 { return Successors.rend(); }
460 unsigned succ_size() const {
461 return (unsigned)Successors.size();
462 }
463 bool succ_empty() const { return Successors.empty(); }
464
465 inline iterator_range<pred_iterator> predecessors() {
466 return make_range(x: pred_begin(), y: pred_end());
467 }
468 inline iterator_range<const_pred_iterator> predecessors() const {
469 return make_range(x: pred_begin(), y: pred_end());
470 }
471 inline iterator_range<succ_iterator> successors() {
472 return make_range(x: succ_begin(), y: succ_end());
473 }
474 inline iterator_range<const_succ_iterator> successors() const {
475 return make_range(x: succ_begin(), y: succ_end());
476 }
477
478 // LiveIn management methods.
479
480 /// Adds the specified register as a live in. Note that it is an error to add
481 /// the same register to the same set more than once unless the intention is
482 /// to call sortUniqueLiveIns after all registers are added.
483 void addLiveIn(MCRegister PhysReg,
484 LaneBitmask LaneMask = LaneBitmask::getAll()) {
485 LiveIns.push_back(x: RegisterMaskPair(PhysReg, LaneMask));
486 }
487 void addLiveIn(const RegisterMaskPair &RegMaskPair) {
488 LiveIns.push_back(x: RegMaskPair);
489 }
490
491 /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
492 /// this than repeatedly calling isLiveIn before calling addLiveIn for every
493 /// LiveIn insertion.
494 LLVM_ABI void sortUniqueLiveIns();
495
496 /// Clear live in list.
497 LLVM_ABI void clearLiveIns();
498
499 /// Clear the live in list, and return the removed live in's in \p OldLiveIns.
500 /// Requires that the vector \p OldLiveIns is empty.
501 LLVM_ABI void clearLiveIns(std::vector<RegisterMaskPair> &OldLiveIns);
502
503 /// Add PhysReg as live in to this block, and ensure that there is a copy of
504 /// PhysReg to a virtual register of class RC. Return the virtual register
505 /// that is a copy of the live in PhysReg.
506 LLVM_ABI Register addLiveIn(MCRegister PhysReg,
507 const TargetRegisterClass *RC);
508
509 /// Remove the specified register from the live in set.
510 LLVM_ABI void removeLiveIn(MCRegister Reg,
511 LaneBitmask LaneMask = LaneBitmask::getAll());
512
513 /// Return true if the specified register is in the live in set.
514 LLVM_ABI bool isLiveIn(MCRegister Reg,
515 LaneBitmask LaneMask = LaneBitmask::getAll()) const;
516
517 // Iteration support for live in sets. These sets are kept in sorted
518 // order by their register number.
519 using livein_iterator = LiveInVector::const_iterator;
520
521 /// Unlike livein_begin, this method does not check that the liveness
522 /// information is accurate. Still for debug purposes it may be useful
523 /// to have iterators that won't assert if the liveness information
524 /// is not current.
525 livein_iterator livein_begin_dbg() const { return LiveIns.begin(); }
526 iterator_range<livein_iterator> liveins_dbg() const {
527 return make_range(x: livein_begin_dbg(), y: livein_end());
528 }
529
530 LLVM_ABI livein_iterator livein_begin() const;
531 livein_iterator livein_end() const { return LiveIns.end(); }
532 bool livein_empty() const { return LiveIns.empty(); }
533 iterator_range<livein_iterator> liveins() const {
534 return make_range(x: livein_begin(), y: livein_end());
535 }
536
537 /// Remove entry from the livein set and return iterator to the next.
538 LLVM_ABI livein_iterator removeLiveIn(livein_iterator I);
539
540 const std::vector<RegisterMaskPair> &getLiveIns() const { return LiveIns; }
541
542 class liveout_iterator {
543 public:
544 using iterator_category = std::input_iterator_tag;
545 using difference_type = std::ptrdiff_t;
546 using value_type = RegisterMaskPair;
547 using pointer = const RegisterMaskPair *;
548 using reference = const RegisterMaskPair &;
549
550 liveout_iterator(const MachineBasicBlock &MBB, MCPhysReg ExceptionPointer,
551 MCPhysReg ExceptionSelector, bool End)
552 : ExceptionPointer(ExceptionPointer),
553 ExceptionSelector(ExceptionSelector), BlockI(MBB.succ_begin()),
554 BlockEnd(MBB.succ_end()) {
555 if (End)
556 BlockI = BlockEnd;
557 else if (BlockI != BlockEnd) {
558 LiveRegI = (*BlockI)->livein_begin();
559 if (!advanceToValidPosition())
560 return;
561 if (LiveRegI->PhysReg == ExceptionPointer ||
562 LiveRegI->PhysReg == ExceptionSelector)
563 ++(*this);
564 }
565 }
566
567 liveout_iterator &operator++() {
568 do {
569 ++LiveRegI;
570 if (!advanceToValidPosition())
571 return *this;
572 } while ((*BlockI)->isEHPad() &&
573 (LiveRegI->PhysReg == ExceptionPointer ||
574 LiveRegI->PhysReg == ExceptionSelector));
575 return *this;
576 }
577
578 liveout_iterator operator++(int) {
579 liveout_iterator Tmp = *this;
580 ++(*this);
581 return Tmp;
582 }
583
584 reference operator*() const {
585 return *LiveRegI;
586 }
587
588 pointer operator->() const {
589 return &*LiveRegI;
590 }
591
592 bool operator==(const liveout_iterator &RHS) const {
593 if (BlockI != BlockEnd)
594 return BlockI == RHS.BlockI && LiveRegI == RHS.LiveRegI;
595 return RHS.BlockI == BlockEnd;
596 }
597
598 bool operator!=(const liveout_iterator &RHS) const {
599 return !(*this == RHS);
600 }
601 private:
602 bool advanceToValidPosition() {
603 if (LiveRegI != (*BlockI)->livein_end())
604 return true;
605
606 do {
607 ++BlockI;
608 } while (BlockI != BlockEnd && (*BlockI)->livein_empty());
609 if (BlockI == BlockEnd)
610 return false;
611
612 LiveRegI = (*BlockI)->livein_begin();
613 return true;
614 }
615
616 MCPhysReg ExceptionPointer, ExceptionSelector;
617 const_succ_iterator BlockI;
618 const_succ_iterator BlockEnd;
619 livein_iterator LiveRegI;
620 };
621
622 /// Iterator scanning successor basic blocks' liveins to determine the
623 /// registers potentially live at the end of this block. There may be
624 /// duplicates or overlapping registers in the list returned.
625 LLVM_ABI liveout_iterator liveout_begin() const;
626 liveout_iterator liveout_end() const {
627 return liveout_iterator(*this, 0, 0, true);
628 }
629 iterator_range<liveout_iterator> liveouts() const {
630 return make_range(x: liveout_begin(), y: liveout_end());
631 }
632
633 /// Get the clobber mask for the start of this basic block. Funclets use this
634 /// to prevent register allocation across funclet transitions.
635 LLVM_ABI const uint32_t *
636 getBeginClobberMask(const TargetRegisterInfo *TRI) const;
637
638 /// Get the clobber mask for the end of the basic block.
639 /// \see getBeginClobberMask()
640 LLVM_ABI const uint32_t *
641 getEndClobberMask(const TargetRegisterInfo *TRI) const;
642
643 /// Return alignment of the basic block.
644 Align getAlignment() const { return Alignment; }
645
646 /// Set alignment of the basic block.
647 void setAlignment(Align A) { Alignment = A; }
648
649 void setAlignment(Align A, unsigned MaxBytes) {
650 setAlignment(A);
651 setMaxBytesForAlignment(MaxBytes);
652 }
653
654 /// Return the maximum amount of padding allowed for aligning the basic block.
655 unsigned getMaxBytesForAlignment() const { return MaxBytesForAlignment; }
656
657 /// Set the maximum amount of padding allowed for aligning the basic block
658 void setMaxBytesForAlignment(unsigned MaxBytes) {
659 MaxBytesForAlignment = MaxBytes;
660 }
661
662 /// Returns true if the block is a landing pad. That is this basic block is
663 /// entered via an exception handler.
664 bool isEHPad() const { return IsEHPad; }
665
666 /// Indicates the block is a landing pad. That is this basic block is entered
667 /// via an exception handler.
668 void setIsEHPad(bool V = true) { IsEHPad = V; }
669
670 LLVM_ABI bool hasEHPadSuccessor() const;
671
672 /// Returns true if this is the entry block of the function.
673 LLVM_ABI bool isEntryBlock() const;
674
675 /// Returns true if this is the entry block of an EH scope, i.e., the block
676 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
677 bool isEHScopeEntry() const { return IsEHScopeEntry; }
678
679 /// Indicates if this is the entry block of an EH scope, i.e., the block that
680 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
681 void setIsEHScopeEntry(bool V = true) { IsEHScopeEntry = V; }
682
683 /// Returns true if this is a target of Windows EH Continuation Guard.
684 bool isEHContTarget() const { return IsEHContTarget; }
685
686 /// Indicates if this is a target of Windows EH Continuation Guard.
687 void setIsEHContTarget(bool V = true) { IsEHContTarget = V; }
688
689 /// Returns true if this is the entry block of an EH funclet.
690 bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
691
692 /// Indicates if this is the entry block of an EH funclet.
693 void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
694
695 /// Returns true if this is the entry block of a cleanup funclet.
696 bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
697
698 /// Indicates if this is the entry block of a cleanup funclet.
699 void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
700
701 /// Returns true if this block begins any section.
702 bool isBeginSection() const { return IsBeginSection; }
703
704 /// Returns true if this block ends any section.
705 bool isEndSection() const { return IsEndSection; }
706
707 void setIsBeginSection(bool V = true) { IsBeginSection = V; }
708
709 void setIsEndSection(bool V = true) { IsEndSection = V; }
710
711 std::optional<UniqueBBID> getBBID() const { return BBID; }
712
713 /// Returns the section ID of this basic block.
714 MBBSectionID getSectionID() const { return SectionID; }
715
716 /// Sets the fixed BBID of this basic block.
717 void setBBID(const UniqueBBID &V) {
718 assert(!BBID.has_value() && "Cannot change BBID.");
719 BBID = V;
720 }
721
722 /// Sets the section ID for this basic block.
723 void setSectionID(MBBSectionID V) { SectionID = V; }
724
725 /// Returns the MCSymbol marking the end of this basic block.
726 LLVM_ABI MCSymbol *getEndSymbol() const;
727
728 /// Returns true if this block may have an INLINEASM_BR (overestimate, by
729 /// checking if any of the successors are indirect targets of any inlineasm_br
730 /// in the function).
731 LLVM_ABI bool mayHaveInlineAsmBr() const;
732
733 /// Returns true if this is the indirect dest of an INLINEASM_BR.
734 bool isInlineAsmBrIndirectTarget() const {
735 return IsInlineAsmBrIndirectTarget;
736 }
737
738 /// Indicates if this is the indirect dest of an INLINEASM_BR.
739 void setIsInlineAsmBrIndirectTarget(bool V = true) {
740 IsInlineAsmBrIndirectTarget = V;
741 }
742
743 /// Returns true if it is legal to hoist instructions into this block.
744 LLVM_ABI bool isLegalToHoistInto() const;
745
746 // Code Layout methods.
747
748 /// Move 'this' block before or after the specified block. This only moves
749 /// the block, it does not modify the CFG or adjust potential fall-throughs at
750 /// the end of the block.
751 LLVM_ABI void moveBefore(MachineBasicBlock *NewAfter);
752 LLVM_ABI void moveAfter(MachineBasicBlock *NewBefore);
753
754 /// Returns true if this and MBB belong to the same section.
755 bool sameSection(const MachineBasicBlock *MBB) const {
756 return getSectionID() == MBB->getSectionID();
757 }
758
759 /// Update the terminator instructions in block to account for changes to
760 /// block layout which may have been made. PreviousLayoutSuccessor should be
761 /// set to the block which may have been used as fallthrough before the block
762 /// layout was modified. If the block previously fell through to that block,
763 /// it may now need a branch. If it previously branched to another block, it
764 /// may now be able to fallthrough to the current layout successor.
765 LLVM_ABI void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor);
766
767 // Machine-CFG mutators
768
769 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
770 /// of Succ is automatically updated. PROB parameter is stored in
771 /// Probabilities list. The default probability is set as unknown. Mixing
772 /// known and unknown probabilities in successor list is not allowed. When all
773 /// successors have unknown probabilities, 1 / N is returned as the
774 /// probability for each successor, where N is the number of successors.
775 ///
776 /// Note that duplicate Machine CFG edges are not allowed.
777 LLVM_ABI void
778 addSuccessor(MachineBasicBlock *Succ,
779 BranchProbability Prob = BranchProbability::getUnknown());
780
781 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
782 /// of Succ is automatically updated. The probability is not provided because
783 /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
784 /// won't be used. Using this interface can save some space.
785 LLVM_ABI void addSuccessorWithoutProb(MachineBasicBlock *Succ);
786
787 /// Set successor probability of a given iterator.
788 LLVM_ABI void setSuccProbability(succ_iterator I, BranchProbability Prob);
789
790 /// Normalize probabilities of all successors so that the sum of them becomes
791 /// one. This is usually done when the current update on this MBB is done, and
792 /// the sum of its successors' probabilities is not guaranteed to be one. The
793 /// user is responsible for the correct use of this function.
794 /// MBB::removeSuccessor() has an option to do this automatically.
795 void normalizeSuccProbs() {
796 BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end());
797 }
798
799 /// Validate successors' probabilities and check if the sum of them is
800 /// approximate one. This only works in DEBUG mode.
801 LLVM_ABI void validateSuccProbs() const;
802
803 /// Remove successor from the successors list of this MachineBasicBlock. The
804 /// Predecessors list of Succ is automatically updated.
805 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
806 /// after the successor is removed.
807 LLVM_ABI void removeSuccessor(MachineBasicBlock *Succ,
808 bool NormalizeSuccProbs = false);
809
810 /// Remove specified successor from the successors list of this
811 /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
812 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
813 /// after the successor is removed.
814 /// Return the iterator to the element after the one removed.
815 LLVM_ABI succ_iterator removeSuccessor(succ_iterator I,
816 bool NormalizeSuccProbs = false);
817
818 /// Replace successor OLD with NEW and update probability info.
819 LLVM_ABI void replaceSuccessor(MachineBasicBlock *Old,
820 MachineBasicBlock *New);
821
822 /// Copy a successor (and any probability info) from original block to this
823 /// block's. Uses an iterator into the original blocks successors.
824 ///
825 /// This is useful when doing a partial clone of successors. Afterward, the
826 /// probabilities may need to be normalized.
827 LLVM_ABI void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I);
828
829 /// Split the old successor into old plus new and updates the probability
830 /// info.
831 LLVM_ABI void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New,
832 bool NormalizeSuccProbs = false);
833
834 /// Transfers all the successors from MBB to this machine basic block (i.e.,
835 /// copies all the successors FromMBB and remove all the successors from
836 /// FromMBB).
837 LLVM_ABI void transferSuccessors(MachineBasicBlock *FromMBB);
838
839 /// Transfers all the successors, as in transferSuccessors, and update PHI
840 /// operands in the successor blocks which refer to FromMBB to refer to this.
841 LLVM_ABI void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
842
843 /// Return true if any of the successors have probabilities attached to them.
844 bool hasSuccessorProbabilities() const { return !Probs.empty(); }
845
846 /// Return true if the specified MBB is a predecessor of this block.
847 LLVM_ABI bool isPredecessor(const MachineBasicBlock *MBB) const;
848
849 /// Return true if the specified MBB is a successor of this block.
850 LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const;
851
852 /// Return true if the specified MBB will be emitted immediately after this
853 /// block, such that if this block exits by falling through, control will
854 /// transfer to the specified MBB. Note that MBB need not be a successor at
855 /// all, for example if this block ends with an unconditional branch to some
856 /// other block.
857 LLVM_ABI bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
858
859 /// Return the successor of this block if it has a single successor.
860 /// Otherwise return a null pointer.
861 ///
862 LLVM_ABI const MachineBasicBlock *getSingleSuccessor() const;
863 MachineBasicBlock *getSingleSuccessor() {
864 return const_cast<MachineBasicBlock *>(
865 static_cast<const MachineBasicBlock *>(this)->getSingleSuccessor());
866 }
867
868 /// Return the predecessor of this block if it has a single predecessor.
869 /// Otherwise return a null pointer.
870 ///
871 LLVM_ABI const MachineBasicBlock *getSinglePredecessor() const;
872 MachineBasicBlock *getSinglePredecessor() {
873 return const_cast<MachineBasicBlock *>(
874 static_cast<const MachineBasicBlock *>(this)->getSinglePredecessor());
875 }
876
877 /// Return the fallthrough block if the block can implicitly
878 /// transfer control to the block after it by falling off the end of
879 /// it. If an explicit branch to the fallthrough block is not allowed,
880 /// set JumpToFallThrough to be false. Non-null return is a conservative
881 /// answer.
882 LLVM_ABI MachineBasicBlock *getFallThrough(bool JumpToFallThrough = true);
883
884 /// Return the fallthrough block if the block can implicitly
885 /// transfer control to it's successor, whether by a branch or
886 /// a fallthrough. Non-null return is a conservative answer.
887 MachineBasicBlock *getLogicalFallThrough() { return getFallThrough(JumpToFallThrough: false); }
888
889 /// Return true if the block can implicitly transfer control to the
890 /// block after it by falling off the end of it. This should return
891 /// false if it can reach the block after it, but it uses an
892 /// explicit branch to do so (e.g., a table jump). True is a
893 /// conservative answer.
894 LLVM_ABI bool canFallThrough();
895
896 /// Returns a pointer to the first instruction in this block that is not a
897 /// PHINode instruction. When adding instructions to the beginning of the
898 /// basic block, they should be added before the returned value, not before
899 /// the first instruction, which might be PHI.
900 /// Returns end() is there's no non-PHI instruction.
901 LLVM_ABI iterator getFirstNonPHI();
902 const_iterator getFirstNonPHI() const {
903 return const_cast<MachineBasicBlock *>(this)->getFirstNonPHI();
904 }
905
906 /// Return the first instruction in MBB after I that is not a PHI or a label.
907 /// This is the correct point to insert lowered copies at the beginning of a
908 /// basic block that must be before any debugging information.
909 LLVM_ABI iterator SkipPHIsAndLabels(iterator I);
910
911 /// Return the first instruction in MBB after I that is not a PHI, label or
912 /// debug. This is the correct point to insert copies at the beginning of a
913 /// basic block. \p Reg is the register being used by a spill or defined for a
914 /// restore/split during register allocation.
915 LLVM_ABI iterator SkipPHIsLabelsAndDebug(iterator I,
916 Register Reg = Register(),
917 bool SkipPseudoOp = true);
918
919 /// Returns an iterator to the first terminator instruction of this basic
920 /// block. If a terminator does not exist, it returns end().
921 LLVM_ABI iterator getFirstTerminator();
922 const_iterator getFirstTerminator() const {
923 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
924 }
925
926 /// Same getFirstTerminator but it ignores bundles and return an
927 /// instr_iterator instead.
928 LLVM_ABI instr_iterator getFirstInstrTerminator();
929
930 /// Finds the first terminator in a block by scanning forward. This can handle
931 /// cases in GlobalISel where there may be non-terminator instructions between
932 /// terminators, for which getFirstTerminator() will not work correctly.
933 LLVM_ABI iterator getFirstTerminatorForward();
934
935 /// Returns an iterator to the first non-debug instruction in the basic block,
936 /// or end(). Skip any pseudo probe operation if \c SkipPseudoOp is true.
937 /// Pseudo probes are like debug instructions which do not turn into real
938 /// machine code. We try to use the function to skip both debug instructions
939 /// and pseudo probe operations to avoid API proliferation. This should work
940 /// most of the time when considering optimizing the rest of code in the
941 /// block, except for certain cases where pseudo probes are designed to block
942 /// the optimizations. For example, code merge like optimizations are supposed
943 /// to be blocked by pseudo probes for better AutoFDO profile quality.
944 /// Therefore, they should be considered as a valid instruction when this
945 /// function is called in a context of such optimizations. On the other hand,
946 /// \c SkipPseudoOp should be true when it's used in optimizations that
947 /// unlikely hurt profile quality, e.g., without block merging. The default
948 /// value of \c SkipPseudoOp is set to true to maximize code quality in
949 /// general, with an explict false value passed in in a few places like branch
950 /// folding and if-conversion to favor profile quality.
951 LLVM_ABI iterator getFirstNonDebugInstr(bool SkipPseudoOp = true);
952 const_iterator getFirstNonDebugInstr(bool SkipPseudoOp = true) const {
953 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr(
954 SkipPseudoOp);
955 }
956
957 /// Returns an iterator to the last non-debug instruction in the basic block,
958 /// or end(). Skip any pseudo operation if \c SkipPseudoOp is true.
959 /// Pseudo probes are like debug instructions which do not turn into real
960 /// machine code. We try to use the function to skip both debug instructions
961 /// and pseudo probe operations to avoid API proliferation. This should work
962 /// most of the time when considering optimizing the rest of code in the
963 /// block, except for certain cases where pseudo probes are designed to block
964 /// the optimizations. For example, code merge like optimizations are supposed
965 /// to be blocked by pseudo probes for better AutoFDO profile quality.
966 /// Therefore, they should be considered as a valid instruction when this
967 /// function is called in a context of such optimizations. On the other hand,
968 /// \c SkipPseudoOp should be true when it's used in optimizations that
969 /// unlikely hurt profile quality, e.g., without block merging. The default
970 /// value of \c SkipPseudoOp is set to true to maximize code quality in
971 /// general, with an explict false value passed in in a few places like branch
972 /// folding and if-conversion to favor profile quality.
973 LLVM_ABI iterator getLastNonDebugInstr(bool SkipPseudoOp = true);
974 const_iterator getLastNonDebugInstr(bool SkipPseudoOp = true) const {
975 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr(
976 SkipPseudoOp);
977 }
978
979 /// Convenience function that returns true if the block ends in a return
980 /// instruction.
981 bool isReturnBlock() const {
982 return !empty() && back().isReturn();
983 }
984
985 /// Convenience function that returns true if the bock ends in a EH scope
986 /// return instruction.
987 bool isEHScopeReturnBlock() const {
988 return !empty() && back().isEHScopeReturn();
989 }
990
991 /// Split a basic block into 2 pieces at \p SplitPoint. A new block will be
992 /// inserted after this block, and all instructions after \p SplitInst moved
993 /// to it (\p SplitInst will be in the original block). If \p LIS is provided,
994 /// LiveIntervals will be appropriately updated. \return the newly inserted
995 /// block.
996 ///
997 /// If \p UpdateLiveIns is true, this will ensure the live ins list is
998 /// accurate, including for physreg uses/defs in the original block.
999 LLVM_ABI MachineBasicBlock *splitAt(MachineInstr &SplitInst,
1000 bool UpdateLiveIns = true,
1001 LiveIntervals *LIS = nullptr);
1002
1003 /// Split the critical edge from this block to the given successor block, and
1004 /// return the newly created block, or null if splitting is not possible.
1005 ///
1006 /// This function updates LiveVariables, MachineDominatorTree, and
1007 /// MachineLoopInfo, as applicable.
1008 struct SplitCriticalEdgeAnalyses {
1009 LiveIntervals *LIS;
1010 SlotIndexes *SI;
1011 LiveVariables *LV;
1012 MachineLoopInfo *MLI;
1013 };
1014
1015 MachineBasicBlock *
1016 SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P,
1017 std::vector<SparseBitVector<>> *LiveInSets = nullptr,
1018 MachineDomTreeUpdater *MDTU = nullptr) {
1019 return SplitCriticalEdge(Succ, P: &P, MFAM: nullptr, LiveInSets, MDTU);
1020 }
1021
1022 MachineBasicBlock *
1023 SplitCriticalEdge(MachineBasicBlock *Succ,
1024 MachineFunctionAnalysisManager &MFAM,
1025 std::vector<SparseBitVector<>> *LiveInSets = nullptr,
1026 MachineDomTreeUpdater *MDTU = nullptr) {
1027 return SplitCriticalEdge(Succ, P: nullptr, MFAM: &MFAM, LiveInSets, MDTU);
1028 }
1029
1030 // Helper method for new pass manager migration.
1031 LLVM_ABI MachineBasicBlock *SplitCriticalEdge(
1032 MachineBasicBlock *Succ, const SplitCriticalEdgeAnalyses &Analyses,
1033 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater *MDTU);
1034
1035 LLVM_ABI MachineBasicBlock *SplitCriticalEdge(
1036 MachineBasicBlock *Succ, Pass *P, MachineFunctionAnalysisManager *MFAM,
1037 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater *MDTU);
1038
1039 /// Check if the edge between this block and the given successor \p
1040 /// Succ, can be split. If this returns true a subsequent call to
1041 /// SplitCriticalEdge is guaranteed to return a valid basic block if
1042 /// no changes occurred in the meantime.
1043 LLVM_ABI bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
1044
1045 void pop_front() { Insts.pop_front(); }
1046 void pop_back() { Insts.pop_back(); }
1047 void push_back(MachineInstr *MI) { Insts.push_back(val: MI); }
1048
1049 /// Insert MI into the instruction list before I, possibly inside a bundle.
1050 ///
1051 /// If the insertion point is inside a bundle, MI will be added to the bundle,
1052 /// otherwise MI will not be added to any bundle. That means this function
1053 /// alone can't be used to prepend or append instructions to bundles. See
1054 /// MIBundleBuilder::insert() for a more reliable way of doing that.
1055 LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M);
1056
1057 /// Insert a range of instructions into the instruction list before I.
1058 template<typename IT>
1059 void insert(iterator I, IT S, IT E) {
1060 assert((I == end() || I->getParent() == this) &&
1061 "iterator points outside of basic block");
1062 Insts.insert(I.getInstrIterator(), S, E);
1063 }
1064
1065 /// Insert MI into the instruction list before I.
1066 iterator insert(iterator I, MachineInstr *MI) {
1067 assert((I == end() || I->getParent() == this) &&
1068 "iterator points outside of basic block");
1069 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1070 "Cannot insert instruction with bundle flags");
1071 return Insts.insert(where: I.getInstrIterator(), New: MI);
1072 }
1073
1074 /// Insert MI into the instruction list after I.
1075 iterator insertAfter(iterator I, MachineInstr *MI) {
1076 assert((I == end() || I->getParent() == this) &&
1077 "iterator points outside of basic block");
1078 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1079 "Cannot insert instruction with bundle flags");
1080 return Insts.insertAfter(where: I.getInstrIterator(), New: MI);
1081 }
1082
1083 /// If I is bundled then insert MI into the instruction list after the end of
1084 /// the bundle, otherwise insert MI immediately after I.
1085 instr_iterator insertAfterBundle(instr_iterator I, MachineInstr *MI) {
1086 assert((I == instr_end() || I->getParent() == this) &&
1087 "iterator points outside of basic block");
1088 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1089 "Cannot insert instruction with bundle flags");
1090 while (I->isBundledWithSucc())
1091 ++I;
1092 return Insts.insertAfter(where: I, New: MI);
1093 }
1094
1095 /// Remove an instruction from the instruction list and delete it.
1096 ///
1097 /// If the instruction is part of a bundle, the other instructions in the
1098 /// bundle will still be bundled after removing the single instruction.
1099 LLVM_ABI instr_iterator erase(instr_iterator I);
1100
1101 /// Remove an instruction from the instruction list and delete it.
1102 ///
1103 /// If the instruction is part of a bundle, the other instructions in the
1104 /// bundle will still be bundled after removing the single instruction.
1105 instr_iterator erase_instr(MachineInstr *I) {
1106 return erase(I: instr_iterator(I));
1107 }
1108
1109 /// Remove a range of instructions from the instruction list and delete them.
1110 iterator erase(iterator I, iterator E) {
1111 return Insts.erase(first: I.getInstrIterator(), last: E.getInstrIterator());
1112 }
1113
1114 /// Remove an instruction or bundle from the instruction list and delete it.
1115 ///
1116 /// If I points to a bundle of instructions, they are all erased.
1117 iterator erase(iterator I) {
1118 return erase(I, E: std::next(x: I));
1119 }
1120
1121 /// Remove an instruction from the instruction list and delete it.
1122 ///
1123 /// If I is the head of a bundle of instructions, the whole bundle will be
1124 /// erased.
1125 iterator erase(MachineInstr *I) {
1126 return erase(I: iterator(I));
1127 }
1128
1129 /// Remove the unbundled instruction from the instruction list without
1130 /// deleting it.
1131 ///
1132 /// This function can not be used to remove bundled instructions, use
1133 /// remove_instr to remove individual instructions from a bundle.
1134 MachineInstr *remove(MachineInstr *I) {
1135 assert(!I->isBundled() && "Cannot remove bundled instructions");
1136 return Insts.remove(IT: instr_iterator(I));
1137 }
1138
1139 /// Remove the possibly bundled instruction from the instruction list
1140 /// without deleting it.
1141 ///
1142 /// If the instruction is part of a bundle, the other instructions in the
1143 /// bundle will still be bundled after removing the single instruction.
1144 LLVM_ABI MachineInstr *remove_instr(MachineInstr *I);
1145
1146 void clear() {
1147 Insts.clear();
1148 }
1149
1150 /// Take an instruction from MBB 'Other' at the position From, and insert it
1151 /// into this MBB right before 'Where'.
1152 ///
1153 /// If From points to a bundle of instructions, the whole bundle is moved.
1154 void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
1155 // The range splice() doesn't allow noop moves, but this one does.
1156 if (Where != From)
1157 splice(Where, Other, From, To: std::next(x: From));
1158 }
1159
1160 /// Take a block of instructions from MBB 'Other' in the range [From, To),
1161 /// and insert them into this MBB right before 'Where'.
1162 ///
1163 /// The instruction at 'Where' must not be included in the range of
1164 /// instructions to move.
1165 void splice(iterator Where, MachineBasicBlock *Other,
1166 iterator From, iterator To) {
1167 Insts.splice(where: Where.getInstrIterator(), L2&: Other->Insts,
1168 first: From.getInstrIterator(), last: To.getInstrIterator());
1169 }
1170
1171 /// This method unlinks 'this' from the containing function, and returns it,
1172 /// but does not delete it.
1173 LLVM_ABI MachineBasicBlock *removeFromParent();
1174
1175 /// This method unlinks 'this' from the containing function and deletes it.
1176 LLVM_ABI void eraseFromParent();
1177
1178 /// Given a machine basic block that branched to 'Old', change the code and
1179 /// CFG so that it branches to 'New' instead.
1180 LLVM_ABI void ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1181 MachineBasicBlock *New);
1182
1183 /// Update all phi nodes in this basic block to refer to basic block \p New
1184 /// instead of basic block \p Old.
1185 LLVM_ABI void replacePhiUsesWith(MachineBasicBlock *Old,
1186 MachineBasicBlock *New);
1187
1188 /// Find the next valid DebugLoc starting at MBBI, skipping any debug
1189 /// instructions. Return UnknownLoc if there is none.
1190 LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI);
1191 DebugLoc findDebugLoc(iterator MBBI) {
1192 return findDebugLoc(MBBI: MBBI.getInstrIterator());
1193 }
1194
1195 /// Has exact same behavior as @ref findDebugLoc (it also searches towards the
1196 /// end of this MBB) except that this function takes a reverse iterator to
1197 /// identify the starting MI.
1198 LLVM_ABI DebugLoc rfindDebugLoc(reverse_instr_iterator MBBI);
1199 DebugLoc rfindDebugLoc(reverse_iterator MBBI) {
1200 return rfindDebugLoc(MBBI: MBBI.getInstrIterator());
1201 }
1202
1203 /// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1204 /// instructions. It is possible to find the last DebugLoc in the MBB using
1205 /// findPrevDebugLoc(instr_end()). Return UnknownLoc if there is none.
1206 LLVM_ABI DebugLoc findPrevDebugLoc(instr_iterator MBBI);
1207 DebugLoc findPrevDebugLoc(iterator MBBI) {
1208 return findPrevDebugLoc(MBBI: MBBI.getInstrIterator());
1209 }
1210
1211 /// Has exact same behavior as @ref findPrevDebugLoc (it also searches towards
1212 /// the beginning of this MBB) except that this function takes reverse
1213 /// iterator to identify the starting MI. A minor difference compared to
1214 /// findPrevDebugLoc is that we can't start scanning at "instr_end".
1215 LLVM_ABI DebugLoc rfindPrevDebugLoc(reverse_instr_iterator MBBI);
1216 DebugLoc rfindPrevDebugLoc(reverse_iterator MBBI) {
1217 return rfindPrevDebugLoc(MBBI: MBBI.getInstrIterator());
1218 }
1219
1220 /// Find and return the merged DebugLoc of the branch instructions of the
1221 /// block. Return UnknownLoc if there is none.
1222 LLVM_ABI DebugLoc findBranchDebugLoc();
1223
1224 /// Possible outcome of a register liveness query to computeRegisterLiveness()
1225 enum LivenessQueryResult {
1226 LQR_Live, ///< Register is known to be (at least partially) live.
1227 LQR_Dead, ///< Register is known to be fully dead.
1228 LQR_Unknown ///< Register liveness not decidable from local neighborhood.
1229 };
1230
1231 /// Return whether (physical) register \p Reg has been defined and not
1232 /// killed as of just before \p Before.
1233 ///
1234 /// Search is localised to a neighborhood of \p Neighborhood instructions
1235 /// before (searching for defs or kills) and \p Neighborhood instructions
1236 /// after (searching just for defs) \p Before.
1237 ///
1238 /// \p Reg must be a physical register.
1239 LLVM_ABI LivenessQueryResult computeRegisterLiveness(
1240 const TargetRegisterInfo *TRI, MCRegister Reg, const_iterator Before,
1241 unsigned Neighborhood = 10) const;
1242
1243 // Debugging methods.
1244 LLVM_ABI void dump() const;
1245 LLVM_ABI void print(raw_ostream &OS, const SlotIndexes * = nullptr,
1246 bool IsStandalone = true) const;
1247 LLVM_ABI void print(raw_ostream &OS, ModuleSlotTracker &MST,
1248 const SlotIndexes * = nullptr,
1249 bool IsStandalone = true) const;
1250
1251 enum PrintNameFlag {
1252 PrintNameIr = (1 << 0), ///< Add IR name where available
1253 PrintNameAttributes = (1 << 1), ///< Print attributes
1254 };
1255
1256 LLVM_ABI void printName(raw_ostream &os,
1257 unsigned printNameFlags = PrintNameIr,
1258 ModuleSlotTracker *moduleSlotTracker = nullptr) const;
1259
1260 // Printing method used by LoopInfo.
1261 LLVM_ABI void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
1262
1263 /// MachineBasicBlocks are uniquely numbered at the function level, unless
1264 /// they're not in a MachineFunction yet, in which case this will return -1.
1265 int getNumber() const { return Number; }
1266 void setNumber(int N) { Number = N; }
1267
1268 /// Return the call frame size on entry to this basic block.
1269 unsigned getCallFrameSize() const { return CallFrameSize; }
1270 /// Set the call frame size on entry to this basic block.
1271 void setCallFrameSize(unsigned N) { CallFrameSize = N; }
1272
1273 /// Return the MCSymbol for this basic block.
1274 LLVM_ABI MCSymbol *getSymbol() const;
1275
1276 /// Return the Windows EH Continuation Symbol for this basic block.
1277 LLVM_ABI MCSymbol *getEHContSymbol() const;
1278
1279 std::optional<uint64_t> getIrrLoopHeaderWeight() const {
1280 return IrrLoopHeaderWeight;
1281 }
1282
1283 void setIrrLoopHeaderWeight(uint64_t Weight) {
1284 IrrLoopHeaderWeight = Weight;
1285 }
1286
1287 /// Return probability of the edge from this block to MBB. This method should
1288 /// NOT be called directly, but by using getEdgeProbability method from
1289 /// MachineBranchProbabilityInfo class.
1290 LLVM_ABI BranchProbability getSuccProbability(const_succ_iterator Succ) const;
1291
1292 // Helper function for MIRPrinter.
1293 LLVM_ABI bool canPredictBranchProbabilities() const;
1294
1295private:
1296 /// Return probability iterator corresponding to the I successor iterator.
1297 probability_iterator getProbabilityIterator(succ_iterator I);
1298 const_probability_iterator
1299 getProbabilityIterator(const_succ_iterator I) const;
1300
1301 friend class MachineBranchProbabilityInfo;
1302
1303 // Methods used to maintain doubly linked list of blocks...
1304 friend struct ilist_callback_traits<MachineBasicBlock>;
1305
1306 // Machine-CFG mutators
1307
1308 /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
1309 /// unless you know what you're doing, because it doesn't update Pred's
1310 /// successors list. Use Pred->addSuccessor instead.
1311 void addPredecessor(MachineBasicBlock *Pred);
1312
1313 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
1314 /// unless you know what you're doing, because it doesn't update Pred's
1315 /// successors list. Use Pred->removeSuccessor instead.
1316 void removePredecessor(MachineBasicBlock *Pred);
1317};
1318
1319LLVM_ABI raw_ostream &operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
1320
1321/// Prints a machine basic block reference.
1322///
1323/// The format is:
1324/// %bb.5 - a machine basic block with MBB.getNumber() == 5.
1325///
1326/// Usage: OS << printMBBReference(MBB) << '\n';
1327LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB);
1328
1329// This is useful when building IndexedMaps keyed on basic block pointers.
1330struct MBB2NumberFunctor {
1331 using argument_type = const MachineBasicBlock *;
1332 unsigned operator()(const MachineBasicBlock *MBB) const {
1333 return MBB->getNumber();
1334 }
1335};
1336
1337//===--------------------------------------------------------------------===//
1338// GraphTraits specializations for machine basic block graphs (machine-CFGs)
1339//===--------------------------------------------------------------------===//
1340
1341// Provide specializations of GraphTraits to be able to treat a
1342// MachineFunction as a graph of MachineBasicBlocks.
1343//
1344
1345template <> struct GraphTraits<MachineBasicBlock *> {
1346 using NodeRef = MachineBasicBlock *;
1347 using ChildIteratorType = MachineBasicBlock::succ_iterator;
1348
1349 static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
1350 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1351 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1352
1353 static unsigned getNumber(MachineBasicBlock *BB) {
1354 assert(BB->getNumber() >= 0 && "negative block number");
1355 return BB->getNumber();
1356 }
1357};
1358
1359static_assert(GraphHasNodeNumbers<MachineBasicBlock *>,
1360 "GraphTraits getNumber() not detected");
1361
1362template <> struct GraphTraits<const MachineBasicBlock *> {
1363 using NodeRef = const MachineBasicBlock *;
1364 using ChildIteratorType = MachineBasicBlock::const_succ_iterator;
1365
1366 static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
1367 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1368 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1369
1370 static unsigned getNumber(const MachineBasicBlock *BB) {
1371 assert(BB->getNumber() >= 0 && "negative block number");
1372 return BB->getNumber();
1373 }
1374};
1375
1376static_assert(GraphHasNodeNumbers<const MachineBasicBlock *>,
1377 "GraphTraits getNumber() not detected");
1378
1379// Provide specializations of GraphTraits to be able to treat a
1380// MachineFunction as a graph of MachineBasicBlocks and to walk it
1381// in inverse order. Inverse order for a function is considered
1382// to be when traversing the predecessor edges of a MBB
1383// instead of the successor edges.
1384//
1385template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
1386 using NodeRef = MachineBasicBlock *;
1387 using ChildIteratorType = MachineBasicBlock::pred_iterator;
1388
1389 static NodeRef getEntryNode(Inverse<MachineBasicBlock *> G) {
1390 return G.Graph;
1391 }
1392
1393 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1394 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1395
1396 static unsigned getNumber(MachineBasicBlock *BB) {
1397 assert(BB->getNumber() >= 0 && "negative block number");
1398 return BB->getNumber();
1399 }
1400};
1401
1402static_assert(GraphHasNodeNumbers<Inverse<MachineBasicBlock *>>,
1403 "GraphTraits getNumber() not detected");
1404
1405template <> struct GraphTraits<Inverse<const MachineBasicBlock*>> {
1406 using NodeRef = const MachineBasicBlock *;
1407 using ChildIteratorType = MachineBasicBlock::const_pred_iterator;
1408
1409 static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
1410 return G.Graph;
1411 }
1412
1413 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1414 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1415
1416 static unsigned getNumber(const MachineBasicBlock *BB) {
1417 assert(BB->getNumber() >= 0 && "negative block number");
1418 return BB->getNumber();
1419 }
1420};
1421
1422static_assert(GraphHasNodeNumbers<Inverse<const MachineBasicBlock *>>,
1423 "GraphTraits getNumber() not detected");
1424
1425// These accessors are handy for sharing templated code between IR and MIR.
1426inline auto successors(const MachineBasicBlock *BB) { return BB->successors(); }
1427inline auto predecessors(const MachineBasicBlock *BB) {
1428 return BB->predecessors();
1429}
1430inline auto succ_size(const MachineBasicBlock *BB) { return BB->succ_size(); }
1431inline auto pred_size(const MachineBasicBlock *BB) { return BB->pred_size(); }
1432inline auto succ_begin(const MachineBasicBlock *BB) { return BB->succ_begin(); }
1433inline auto pred_begin(const MachineBasicBlock *BB) { return BB->pred_begin(); }
1434inline auto succ_end(const MachineBasicBlock *BB) { return BB->succ_end(); }
1435inline auto pred_end(const MachineBasicBlock *BB) { return BB->pred_end(); }
1436
1437/// MachineInstrSpan provides an interface to get an iteration range
1438/// containing the instruction it was initialized with, along with all
1439/// those instructions inserted prior to or following that instruction
1440/// at some point after the MachineInstrSpan is constructed.
1441class MachineInstrSpan {
1442 MachineBasicBlock &MBB;
1443 MachineBasicBlock::iterator I, B, E;
1444
1445public:
1446 MachineInstrSpan(MachineBasicBlock::iterator I, MachineBasicBlock *BB)
1447 : MBB(*BB), I(I), B(I == MBB.begin() ? MBB.end() : std::prev(x: I)),
1448 E(std::next(x: I)) {
1449 assert(I == BB->end() || I->getParent() == BB);
1450 }
1451
1452 MachineBasicBlock::iterator begin() {
1453 return B == MBB.end() ? MBB.begin() : std::next(x: B);
1454 }
1455 MachineBasicBlock::iterator end() { return E; }
1456 bool empty() { return begin() == end(); }
1457
1458 MachineBasicBlock::iterator getInitial() { return I; }
1459};
1460
1461/// Increment \p It until it points to a non-debug instruction or to \p End
1462/// and return the resulting iterator. This function should only be used
1463/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1464/// const_instr_iterator} and the respective reverse iterators.
1465template <typename IterT>
1466inline IterT skipDebugInstructionsForward(IterT It, IterT End,
1467 bool SkipPseudoOp = true) {
1468 while (It != End &&
1469 (It->isDebugInstr() || (SkipPseudoOp && It->isPseudoProbe())))
1470 ++It;
1471 return It;
1472}
1473
1474/// Decrement \p It until it points to a non-debug instruction or to \p Begin
1475/// and return the resulting iterator. This function should only be used
1476/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1477/// const_instr_iterator} and the respective reverse iterators.
1478template <class IterT>
1479inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin,
1480 bool SkipPseudoOp = true) {
1481 while (It != Begin &&
1482 (It->isDebugInstr() || (SkipPseudoOp && It->isPseudoProbe())))
1483 --It;
1484 return It;
1485}
1486
1487/// Increment \p It, then continue incrementing it while it points to a debug
1488/// instruction. A replacement for std::next.
1489template <typename IterT>
1490inline IterT next_nodbg(IterT It, IterT End, bool SkipPseudoOp = true) {
1491 return skipDebugInstructionsForward(std::next(It), End, SkipPseudoOp);
1492}
1493
1494/// Decrement \p It, then continue decrementing it while it points to a debug
1495/// instruction. A replacement for std::prev.
1496template <typename IterT>
1497inline IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp = true) {
1498 return skipDebugInstructionsBackward(std::prev(It), Begin, SkipPseudoOp);
1499}
1500
1501/// Construct a range iterator which begins at \p It and moves forwards until
1502/// \p End is reached, skipping any debug instructions.
1503template <typename IterT>
1504inline auto instructionsWithoutDebug(IterT It, IterT End,
1505 bool SkipPseudoOp = true) {
1506 return make_filter_range(make_range(It, End), [=](const MachineInstr &MI) {
1507 return !MI.isDebugInstr() && !(SkipPseudoOp && MI.isPseudoProbe());
1508 });
1509}
1510
1511} // end namespace llvm
1512
1513#endif // LLVM_CODEGEN_MACHINEBASICBLOCK_H
1514

source code of llvm/include/llvm/CodeGen/MachineBasicBlock.h