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

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