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 /// Add PhysReg as live in to this block, and ensure that there is a copy of
445 /// PhysReg to a virtual register of class RC. Return the virtual register
446 /// that is a copy of the live in PhysReg.
447 Register addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC);
448
449 /// Remove the specified register from the live in set.
450 void removeLiveIn(MCPhysReg Reg,
451 LaneBitmask LaneMask = LaneBitmask::getAll());
452
453 /// Return true if the specified register is in the live in set.
454 bool isLiveIn(MCPhysReg Reg,
455 LaneBitmask LaneMask = LaneBitmask::getAll()) const;
456
457 // Iteration support for live in sets. These sets are kept in sorted
458 // order by their register number.
459 using livein_iterator = LiveInVector::const_iterator;
460
461 /// Unlike livein_begin, this method does not check that the liveness
462 /// information is accurate. Still for debug purposes it may be useful
463 /// to have iterators that won't assert if the liveness information
464 /// is not current.
465 livein_iterator livein_begin_dbg() const { return LiveIns.begin(); }
466 iterator_range<livein_iterator> liveins_dbg() const {
467 return make_range(x: livein_begin_dbg(), y: livein_end());
468 }
469
470 livein_iterator livein_begin() const;
471 livein_iterator livein_end() const { return LiveIns.end(); }
472 bool livein_empty() const { return LiveIns.empty(); }
473 iterator_range<livein_iterator> liveins() const {
474 return make_range(x: livein_begin(), y: livein_end());
475 }
476
477 /// Remove entry from the livein set and return iterator to the next.
478 livein_iterator removeLiveIn(livein_iterator I);
479
480 std::vector<RegisterMaskPair> getLiveIns() const { return LiveIns; }
481
482 class liveout_iterator {
483 public:
484 using iterator_category = std::input_iterator_tag;
485 using difference_type = std::ptrdiff_t;
486 using value_type = RegisterMaskPair;
487 using pointer = const RegisterMaskPair *;
488 using reference = const RegisterMaskPair &;
489
490 liveout_iterator(const MachineBasicBlock &MBB, MCPhysReg ExceptionPointer,
491 MCPhysReg ExceptionSelector, bool End)
492 : ExceptionPointer(ExceptionPointer),
493 ExceptionSelector(ExceptionSelector), BlockI(MBB.succ_begin()),
494 BlockEnd(MBB.succ_end()) {
495 if (End)
496 BlockI = BlockEnd;
497 else if (BlockI != BlockEnd) {
498 LiveRegI = (*BlockI)->livein_begin();
499 if (!advanceToValidPosition())
500 return;
501 if (LiveRegI->PhysReg == ExceptionPointer ||
502 LiveRegI->PhysReg == ExceptionSelector)
503 ++(*this);
504 }
505 }
506
507 liveout_iterator &operator++() {
508 do {
509 ++LiveRegI;
510 if (!advanceToValidPosition())
511 return *this;
512 } while ((*BlockI)->isEHPad() &&
513 (LiveRegI->PhysReg == ExceptionPointer ||
514 LiveRegI->PhysReg == ExceptionSelector));
515 return *this;
516 }
517
518 liveout_iterator operator++(int) {
519 liveout_iterator Tmp = *this;
520 ++(*this);
521 return Tmp;
522 }
523
524 reference operator*() const {
525 return *LiveRegI;
526 }
527
528 pointer operator->() const {
529 return &*LiveRegI;
530 }
531
532 bool operator==(const liveout_iterator &RHS) const {
533 if (BlockI != BlockEnd)
534 return BlockI == RHS.BlockI && LiveRegI == RHS.LiveRegI;
535 return RHS.BlockI == BlockEnd;
536 }
537
538 bool operator!=(const liveout_iterator &RHS) const {
539 return !(*this == RHS);
540 }
541 private:
542 bool advanceToValidPosition() {
543 if (LiveRegI != (*BlockI)->livein_end())
544 return true;
545
546 do {
547 ++BlockI;
548 } while (BlockI != BlockEnd && (*BlockI)->livein_empty());
549 if (BlockI == BlockEnd)
550 return false;
551
552 LiveRegI = (*BlockI)->livein_begin();
553 return true;
554 }
555
556 MCPhysReg ExceptionPointer, ExceptionSelector;
557 const_succ_iterator BlockI;
558 const_succ_iterator BlockEnd;
559 livein_iterator LiveRegI;
560 };
561
562 /// Iterator scanning successor basic blocks' liveins to determine the
563 /// registers potentially live at the end of this block. There may be
564 /// duplicates or overlapping registers in the list returned.
565 liveout_iterator liveout_begin() const;
566 liveout_iterator liveout_end() const {
567 return liveout_iterator(*this, 0, 0, true);
568 }
569 iterator_range<liveout_iterator> liveouts() const {
570 return make_range(x: liveout_begin(), y: liveout_end());
571 }
572
573 /// Get the clobber mask for the start of this basic block. Funclets use this
574 /// to prevent register allocation across funclet transitions.
575 const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
576
577 /// Get the clobber mask for the end of the basic block.
578 /// \see getBeginClobberMask()
579 const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
580
581 /// Return alignment of the basic block.
582 Align getAlignment() const { return Alignment; }
583
584 /// Set alignment of the basic block.
585 void setAlignment(Align A) { Alignment = A; }
586
587 void setAlignment(Align A, unsigned MaxBytes) {
588 setAlignment(A);
589 setMaxBytesForAlignment(MaxBytes);
590 }
591
592 /// Return the maximum amount of padding allowed for aligning the basic block.
593 unsigned getMaxBytesForAlignment() const { return MaxBytesForAlignment; }
594
595 /// Set the maximum amount of padding allowed for aligning the basic block
596 void setMaxBytesForAlignment(unsigned MaxBytes) {
597 MaxBytesForAlignment = MaxBytes;
598 }
599
600 /// Returns true if the block is a landing pad. That is this basic block is
601 /// entered via an exception handler.
602 bool isEHPad() const { return IsEHPad; }
603
604 /// Indicates the block is a landing pad. That is this basic block is entered
605 /// via an exception handler.
606 void setIsEHPad(bool V = true) { IsEHPad = V; }
607
608 bool hasEHPadSuccessor() const;
609
610 /// Returns true if this is the entry block of the function.
611 bool isEntryBlock() const;
612
613 /// Returns true if this is the entry block of an EH scope, i.e., the block
614 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
615 bool isEHScopeEntry() const { return IsEHScopeEntry; }
616
617 /// Indicates if this is the entry block of an EH scope, i.e., the block that
618 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
619 void setIsEHScopeEntry(bool V = true) { IsEHScopeEntry = V; }
620
621 /// Returns true if this is a target block of a catchret.
622 bool isEHCatchretTarget() const { return IsEHCatchretTarget; }
623
624 /// Indicates if this is a target block of a catchret.
625 void setIsEHCatchretTarget(bool V = true) { IsEHCatchretTarget = V; }
626
627 /// Returns true if this is the entry block of an EH funclet.
628 bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
629
630 /// Indicates if this is the entry block of an EH funclet.
631 void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
632
633 /// Returns true if this is the entry block of a cleanup funclet.
634 bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
635
636 /// Indicates if this is the entry block of a cleanup funclet.
637 void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
638
639 /// Returns true if this block begins any section.
640 bool isBeginSection() const { return IsBeginSection; }
641
642 /// Returns true if this block ends any section.
643 bool isEndSection() const { return IsEndSection; }
644
645 void setIsBeginSection(bool V = true) { IsBeginSection = V; }
646
647 void setIsEndSection(bool V = true) { IsEndSection = V; }
648
649 std::optional<UniqueBBID> getBBID() const { return BBID; }
650
651 /// Returns the section ID of this basic block.
652 MBBSectionID getSectionID() const { return SectionID; }
653
654 /// Returns the unique section ID number of this basic block.
655 unsigned getSectionIDNum() const {
656 return ((unsigned)MBBSectionID::SectionType::Cold) -
657 ((unsigned)SectionID.Type) + SectionID.Number;
658 }
659
660 /// Sets the fixed BBID of this basic block.
661 void setBBID(const UniqueBBID &V) {
662 assert(!BBID.has_value() && "Cannot change BBID.");
663 BBID = V;
664 }
665
666 /// Sets the section ID for this basic block.
667 void setSectionID(MBBSectionID V) { SectionID = V; }
668
669 /// Returns the MCSymbol marking the end of this basic block.
670 MCSymbol *getEndSymbol() const;
671
672 /// Returns true if this block may have an INLINEASM_BR (overestimate, by
673 /// checking if any of the successors are indirect targets of any inlineasm_br
674 /// in the function).
675 bool mayHaveInlineAsmBr() const;
676
677 /// Returns true if this is the indirect dest of an INLINEASM_BR.
678 bool isInlineAsmBrIndirectTarget() const {
679 return IsInlineAsmBrIndirectTarget;
680 }
681
682 /// Indicates if this is the indirect dest of an INLINEASM_BR.
683 void setIsInlineAsmBrIndirectTarget(bool V = true) {
684 IsInlineAsmBrIndirectTarget = V;
685 }
686
687 /// Returns true if it is legal to hoist instructions into this block.
688 bool isLegalToHoistInto() const;
689
690 // Code Layout methods.
691
692 /// Move 'this' block before or after the specified block. This only moves
693 /// the block, it does not modify the CFG or adjust potential fall-throughs at
694 /// the end of the block.
695 void moveBefore(MachineBasicBlock *NewAfter);
696 void moveAfter(MachineBasicBlock *NewBefore);
697
698 /// Returns true if this and MBB belong to the same section.
699 bool sameSection(const MachineBasicBlock *MBB) const {
700 return getSectionID() == MBB->getSectionID();
701 }
702
703 /// Update the terminator instructions in block to account for changes to
704 /// block layout which may have been made. PreviousLayoutSuccessor should be
705 /// set to the block which may have been used as fallthrough before the block
706 /// layout was modified. If the block previously fell through to that block,
707 /// it may now need a branch. If it previously branched to another block, it
708 /// may now be able to fallthrough to the current layout successor.
709 void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor);
710
711 // Machine-CFG mutators
712
713 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
714 /// of Succ is automatically updated. PROB parameter is stored in
715 /// Probabilities list. The default probability is set as unknown. Mixing
716 /// known and unknown probabilities in successor list is not allowed. When all
717 /// successors have unknown probabilities, 1 / N is returned as the
718 /// probability for each successor, where N is the number of successors.
719 ///
720 /// Note that duplicate Machine CFG edges are not allowed.
721 void addSuccessor(MachineBasicBlock *Succ,
722 BranchProbability Prob = BranchProbability::getUnknown());
723
724 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
725 /// of Succ is automatically updated. The probability is not provided because
726 /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
727 /// won't be used. Using this interface can save some space.
728 void addSuccessorWithoutProb(MachineBasicBlock *Succ);
729
730 /// Set successor probability of a given iterator.
731 void setSuccProbability(succ_iterator I, BranchProbability Prob);
732
733 /// Normalize probabilities of all successors so that the sum of them becomes
734 /// one. This is usually done when the current update on this MBB is done, and
735 /// the sum of its successors' probabilities is not guaranteed to be one. The
736 /// user is responsible for the correct use of this function.
737 /// MBB::removeSuccessor() has an option to do this automatically.
738 void normalizeSuccProbs() {
739 BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end());
740 }
741
742 /// Validate successors' probabilities and check if the sum of them is
743 /// approximate one. This only works in DEBUG mode.
744 void validateSuccProbs() const;
745
746 /// Remove successor from the successors list of this MachineBasicBlock. The
747 /// Predecessors list of Succ is automatically updated.
748 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
749 /// after the successor is removed.
750 void removeSuccessor(MachineBasicBlock *Succ,
751 bool NormalizeSuccProbs = false);
752
753 /// Remove specified successor from the successors list of this
754 /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
755 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
756 /// after the successor is removed.
757 /// Return the iterator to the element after the one removed.
758 succ_iterator removeSuccessor(succ_iterator I,
759 bool NormalizeSuccProbs = false);
760
761 /// Replace successor OLD with NEW and update probability info.
762 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
763
764 /// Copy a successor (and any probability info) from original block to this
765 /// block's. Uses an iterator into the original blocks successors.
766 ///
767 /// This is useful when doing a partial clone of successors. Afterward, the
768 /// probabilities may need to be normalized.
769 void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I);
770
771 /// Split the old successor into old plus new and updates the probability
772 /// info.
773 void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New,
774 bool NormalizeSuccProbs = false);
775
776 /// Transfers all the successors from MBB to this machine basic block (i.e.,
777 /// copies all the successors FromMBB and remove all the successors from
778 /// FromMBB).
779 void transferSuccessors(MachineBasicBlock *FromMBB);
780
781 /// Transfers all the successors, as in transferSuccessors, and update PHI
782 /// operands in the successor blocks which refer to FromMBB to refer to this.
783 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
784
785 /// Return true if any of the successors have probabilities attached to them.
786 bool hasSuccessorProbabilities() const { return !Probs.empty(); }
787
788 /// Return true if the specified MBB is a predecessor of this block.
789 bool isPredecessor(const MachineBasicBlock *MBB) const;
790
791 /// Return true if the specified MBB is a successor of this block.
792 bool isSuccessor(const MachineBasicBlock *MBB) const;
793
794 /// Return true if the specified MBB will be emitted immediately after this
795 /// block, such that if this block exits by falling through, control will
796 /// transfer to the specified MBB. Note that MBB need not be a successor at
797 /// all, for example if this block ends with an unconditional branch to some
798 /// other block.
799 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
800
801 /// Return the successor of this block if it has a single successor.
802 /// Otherwise return a null pointer.
803 ///
804 const MachineBasicBlock *getSingleSuccessor() const;
805 MachineBasicBlock *getSingleSuccessor() {
806 return const_cast<MachineBasicBlock *>(
807 static_cast<const MachineBasicBlock *>(this)->getSingleSuccessor());
808 }
809
810 /// Return the predecessor of this block if it has a single predecessor.
811 /// Otherwise return a null pointer.
812 ///
813 const MachineBasicBlock *getSinglePredecessor() const;
814 MachineBasicBlock *getSinglePredecessor() {
815 return const_cast<MachineBasicBlock *>(
816 static_cast<const MachineBasicBlock *>(this)->getSinglePredecessor());
817 }
818
819 /// Return the fallthrough block if the block can implicitly
820 /// transfer control to the block after it by falling off the end of
821 /// it. If an explicit branch to the fallthrough block is not allowed,
822 /// set JumpToFallThrough to be false. Non-null return is a conservative
823 /// answer.
824 MachineBasicBlock *getFallThrough(bool JumpToFallThrough = true);
825
826 /// Return the fallthrough block if the block can implicitly
827 /// transfer control to it's successor, whether by a branch or
828 /// a fallthrough. Non-null return is a conservative answer.
829 MachineBasicBlock *getLogicalFallThrough() { return getFallThrough(JumpToFallThrough: false); }
830
831 /// Return true if the block can implicitly transfer control to the
832 /// block after it by falling off the end of it. This should return
833 /// false if it can reach the block after it, but it uses an
834 /// explicit branch to do so (e.g., a table jump). True is a
835 /// conservative answer.
836 bool canFallThrough();
837
838 /// Returns a pointer to the first instruction in this block that is not a
839 /// PHINode instruction. When adding instructions to the beginning of the
840 /// basic block, they should be added before the returned value, not before
841 /// the first instruction, which might be PHI.
842 /// Returns end() is there's no non-PHI instruction.
843 iterator getFirstNonPHI();
844 const_iterator getFirstNonPHI() const {
845 return const_cast<MachineBasicBlock *>(this)->getFirstNonPHI();
846 }
847
848 /// Return the first instruction in MBB after I that is not a PHI or a label.
849 /// This is the correct point to insert lowered copies at the beginning of a
850 /// basic block that must be before any debugging information.
851 iterator SkipPHIsAndLabels(iterator I);
852
853 /// Return the first instruction in MBB after I that is not a PHI, label or
854 /// debug. This is the correct point to insert copies at the beginning of a
855 /// basic block. \p Reg is the register being used by a spill or defined for a
856 /// restore/split during register allocation.
857 iterator SkipPHIsLabelsAndDebug(iterator I, Register Reg = Register(),
858 bool SkipPseudoOp = true);
859
860 /// Returns an iterator to the first terminator instruction of this basic
861 /// block. If a terminator does not exist, it returns end().
862 iterator getFirstTerminator();
863 const_iterator getFirstTerminator() const {
864 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
865 }
866
867 /// Same getFirstTerminator but it ignores bundles and return an
868 /// instr_iterator instead.
869 instr_iterator getFirstInstrTerminator();
870
871 /// Finds the first terminator in a block by scanning forward. This can handle
872 /// cases in GlobalISel where there may be non-terminator instructions between
873 /// terminators, for which getFirstTerminator() will not work correctly.
874 iterator getFirstTerminatorForward();
875
876 /// Returns an iterator to the first non-debug instruction in the basic block,
877 /// or end(). Skip any pseudo probe operation if \c SkipPseudoOp is true.
878 /// Pseudo probes are like debug instructions which do not turn into real
879 /// machine code. We try to use the function to skip both debug instructions
880 /// and pseudo probe operations to avoid API proliferation. This should work
881 /// most of the time when considering optimizing the rest of code in the
882 /// block, except for certain cases where pseudo probes are designed to block
883 /// the optimizations. For example, code merge like optimizations are supposed
884 /// to be blocked by pseudo probes for better AutoFDO profile quality.
885 /// Therefore, they should be considered as a valid instruction when this
886 /// function is called in a context of such optimizations. On the other hand,
887 /// \c SkipPseudoOp should be true when it's used in optimizations that
888 /// unlikely hurt profile quality, e.g., without block merging. The default
889 /// value of \c SkipPseudoOp is set to true to maximize code quality in
890 /// general, with an explict false value passed in in a few places like branch
891 /// folding and if-conversion to favor profile quality.
892 iterator getFirstNonDebugInstr(bool SkipPseudoOp = true);
893 const_iterator getFirstNonDebugInstr(bool SkipPseudoOp = true) const {
894 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr(
895 SkipPseudoOp);
896 }
897
898 /// Returns an iterator to the last non-debug instruction in the basic block,
899 /// or end(). Skip any pseudo operation if \c SkipPseudoOp is true.
900 /// Pseudo probes are like debug instructions which do not turn into real
901 /// machine code. We try to use the function to skip both debug instructions
902 /// and pseudo probe operations to avoid API proliferation. This should work
903 /// most of the time when considering optimizing the rest of code in the
904 /// block, except for certain cases where pseudo probes are designed to block
905 /// the optimizations. For example, code merge like optimizations are supposed
906 /// to be blocked by pseudo probes for better AutoFDO profile quality.
907 /// Therefore, they should be considered as a valid instruction when this
908 /// function is called in a context of such optimizations. On the other hand,
909 /// \c SkipPseudoOp should be true when it's used in optimizations that
910 /// unlikely hurt profile quality, e.g., without block merging. The default
911 /// value of \c SkipPseudoOp is set to true to maximize code quality in
912 /// general, with an explict false value passed in in a few places like branch
913 /// folding and if-conversion to favor profile quality.
914 iterator getLastNonDebugInstr(bool SkipPseudoOp = true);
915 const_iterator getLastNonDebugInstr(bool SkipPseudoOp = true) const {
916 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr(
917 SkipPseudoOp);
918 }
919
920 /// Convenience function that returns true if the block ends in a return
921 /// instruction.
922 bool isReturnBlock() const {
923 return !empty() && back().isReturn();
924 }
925
926 /// Convenience function that returns true if the bock ends in a EH scope
927 /// return instruction.
928 bool isEHScopeReturnBlock() const {
929 return !empty() && back().isEHScopeReturn();
930 }
931
932 /// Split a basic block into 2 pieces at \p SplitPoint. A new block will be
933 /// inserted after this block, and all instructions after \p SplitInst moved
934 /// to it (\p SplitInst will be in the original block). If \p LIS is provided,
935 /// LiveIntervals will be appropriately updated. \return the newly inserted
936 /// block.
937 ///
938 /// If \p UpdateLiveIns is true, this will ensure the live ins list is
939 /// accurate, including for physreg uses/defs in the original block.
940 MachineBasicBlock *splitAt(MachineInstr &SplitInst, bool UpdateLiveIns = true,
941 LiveIntervals *LIS = nullptr);
942
943 /// Split the critical edge from this block to the given successor block, and
944 /// return the newly created block, or null if splitting is not possible.
945 ///
946 /// This function updates LiveVariables, MachineDominatorTree, and
947 /// MachineLoopInfo, as applicable.
948 MachineBasicBlock *
949 SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P,
950 std::vector<SparseBitVector<>> *LiveInSets = nullptr);
951
952 /// Check if the edge between this block and the given successor \p
953 /// Succ, can be split. If this returns true a subsequent call to
954 /// SplitCriticalEdge is guaranteed to return a valid basic block if
955 /// no changes occurred in the meantime.
956 bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
957
958 void pop_front() { Insts.pop_front(); }
959 void pop_back() { Insts.pop_back(); }
960 void push_back(MachineInstr *MI) { Insts.push_back(val: MI); }
961
962 /// Insert MI into the instruction list before I, possibly inside a bundle.
963 ///
964 /// If the insertion point is inside a bundle, MI will be added to the bundle,
965 /// otherwise MI will not be added to any bundle. That means this function
966 /// alone can't be used to prepend or append instructions to bundles. See
967 /// MIBundleBuilder::insert() for a more reliable way of doing that.
968 instr_iterator insert(instr_iterator I, MachineInstr *M);
969
970 /// Insert a range of instructions into the instruction list before I.
971 template<typename IT>
972 void insert(iterator I, IT S, IT E) {
973 assert((I == end() || I->getParent() == this) &&
974 "iterator points outside of basic block");
975 Insts.insert(I.getInstrIterator(), S, E);
976 }
977
978 /// Insert MI into the instruction list before I.
979 iterator insert(iterator I, MachineInstr *MI) {
980 assert((I == end() || I->getParent() == this) &&
981 "iterator points outside of basic block");
982 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
983 "Cannot insert instruction with bundle flags");
984 return Insts.insert(where: I.getInstrIterator(), New: MI);
985 }
986
987 /// Insert MI into the instruction list after I.
988 iterator insertAfter(iterator I, MachineInstr *MI) {
989 assert((I == end() || I->getParent() == this) &&
990 "iterator points outside of basic block");
991 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
992 "Cannot insert instruction with bundle flags");
993 return Insts.insertAfter(where: I.getInstrIterator(), New: MI);
994 }
995
996 /// If I is bundled then insert MI into the instruction list after the end of
997 /// the bundle, otherwise insert MI immediately after I.
998 instr_iterator insertAfterBundle(instr_iterator I, MachineInstr *MI) {
999 assert((I == instr_end() || I->getParent() == this) &&
1000 "iterator points outside of basic block");
1001 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1002 "Cannot insert instruction with bundle flags");
1003 while (I->isBundledWithSucc())
1004 ++I;
1005 return Insts.insertAfter(where: I, New: MI);
1006 }
1007
1008 /// Remove an instruction from the instruction list and delete it.
1009 ///
1010 /// If the instruction is part of a bundle, the other instructions in the
1011 /// bundle will still be bundled after removing the single instruction.
1012 instr_iterator erase(instr_iterator I);
1013
1014 /// Remove an instruction from the instruction list and delete it.
1015 ///
1016 /// If the instruction is part of a bundle, the other instructions in the
1017 /// bundle will still be bundled after removing the single instruction.
1018 instr_iterator erase_instr(MachineInstr *I) {
1019 return erase(I: instr_iterator(I));
1020 }
1021
1022 /// Remove a range of instructions from the instruction list and delete them.
1023 iterator erase(iterator I, iterator E) {
1024 return Insts.erase(first: I.getInstrIterator(), last: E.getInstrIterator());
1025 }
1026
1027 /// Remove an instruction or bundle from the instruction list and delete it.
1028 ///
1029 /// If I points to a bundle of instructions, they are all erased.
1030 iterator erase(iterator I) {
1031 return erase(I, E: std::next(x: I));
1032 }
1033
1034 /// Remove an instruction from the instruction list and delete it.
1035 ///
1036 /// If I is the head of a bundle of instructions, the whole bundle will be
1037 /// erased.
1038 iterator erase(MachineInstr *I) {
1039 return erase(I: iterator(I));
1040 }
1041
1042 /// Remove the unbundled instruction from the instruction list without
1043 /// deleting it.
1044 ///
1045 /// This function can not be used to remove bundled instructions, use
1046 /// remove_instr to remove individual instructions from a bundle.
1047 MachineInstr *remove(MachineInstr *I) {
1048 assert(!I->isBundled() && "Cannot remove bundled instructions");
1049 return Insts.remove(IT: instr_iterator(I));
1050 }
1051
1052 /// Remove the possibly bundled instruction from the instruction list
1053 /// without deleting it.
1054 ///
1055 /// If the instruction is part of a bundle, the other instructions in the
1056 /// bundle will still be bundled after removing the single instruction.
1057 MachineInstr *remove_instr(MachineInstr *I);
1058
1059 void clear() {
1060 Insts.clear();
1061 }
1062
1063 /// Take an instruction from MBB 'Other' at the position From, and insert it
1064 /// into this MBB right before 'Where'.
1065 ///
1066 /// If From points to a bundle of instructions, the whole bundle is moved.
1067 void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
1068 // The range splice() doesn't allow noop moves, but this one does.
1069 if (Where != From)
1070 splice(Where, Other, From, To: std::next(x: From));
1071 }
1072
1073 /// Take a block of instructions from MBB 'Other' in the range [From, To),
1074 /// and insert them into this MBB right before 'Where'.
1075 ///
1076 /// The instruction at 'Where' must not be included in the range of
1077 /// instructions to move.
1078 void splice(iterator Where, MachineBasicBlock *Other,
1079 iterator From, iterator To) {
1080 Insts.splice(where: Where.getInstrIterator(), L2&: Other->Insts,
1081 first: From.getInstrIterator(), last: To.getInstrIterator());
1082 }
1083
1084 /// This method unlinks 'this' from the containing function, and returns it,
1085 /// but does not delete it.
1086 MachineBasicBlock *removeFromParent();
1087
1088 /// This method unlinks 'this' from the containing function and deletes it.
1089 void eraseFromParent();
1090
1091 /// Given a machine basic block that branched to 'Old', change the code and
1092 /// CFG so that it branches to 'New' instead.
1093 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
1094
1095 /// Update all phi nodes in this basic block to refer to basic block \p New
1096 /// instead of basic block \p Old.
1097 void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New);
1098
1099 /// Find the next valid DebugLoc starting at MBBI, skipping any debug
1100 /// instructions. Return UnknownLoc if there is none.
1101 DebugLoc findDebugLoc(instr_iterator MBBI);
1102 DebugLoc findDebugLoc(iterator MBBI) {
1103 return findDebugLoc(MBBI: MBBI.getInstrIterator());
1104 }
1105
1106 /// Has exact same behavior as @ref findDebugLoc (it also searches towards the
1107 /// end of this MBB) except that this function takes a reverse iterator to
1108 /// identify the starting MI.
1109 DebugLoc rfindDebugLoc(reverse_instr_iterator MBBI);
1110 DebugLoc rfindDebugLoc(reverse_iterator MBBI) {
1111 return rfindDebugLoc(MBBI: MBBI.getInstrIterator());
1112 }
1113
1114 /// Find the previous valid DebugLoc preceding MBBI, skipping any debug
1115 /// instructions. It is possible to find the last DebugLoc in the MBB using
1116 /// findPrevDebugLoc(instr_end()). Return UnknownLoc if there is none.
1117 DebugLoc findPrevDebugLoc(instr_iterator MBBI);
1118 DebugLoc findPrevDebugLoc(iterator MBBI) {
1119 return findPrevDebugLoc(MBBI: MBBI.getInstrIterator());
1120 }
1121
1122 /// Has exact same behavior as @ref findPrevDebugLoc (it also searches towards
1123 /// the beginning of this MBB) except that this function takes reverse
1124 /// iterator to identify the starting MI. A minor difference compared to
1125 /// findPrevDebugLoc is that we can't start scanning at "instr_end".
1126 DebugLoc rfindPrevDebugLoc(reverse_instr_iterator MBBI);
1127 DebugLoc rfindPrevDebugLoc(reverse_iterator MBBI) {
1128 return rfindPrevDebugLoc(MBBI: MBBI.getInstrIterator());
1129 }
1130
1131 /// Find and return the merged DebugLoc of the branch instructions of the
1132 /// block. Return UnknownLoc if there is none.
1133 DebugLoc findBranchDebugLoc();
1134
1135 /// Possible outcome of a register liveness query to computeRegisterLiveness()
1136 enum LivenessQueryResult {
1137 LQR_Live, ///< Register is known to be (at least partially) live.
1138 LQR_Dead, ///< Register is known to be fully dead.
1139 LQR_Unknown ///< Register liveness not decidable from local neighborhood.
1140 };
1141
1142 /// Return whether (physical) register \p Reg has been defined and not
1143 /// killed as of just before \p Before.
1144 ///
1145 /// Search is localised to a neighborhood of \p Neighborhood instructions
1146 /// before (searching for defs or kills) and \p Neighborhood instructions
1147 /// after (searching just for defs) \p Before.
1148 ///
1149 /// \p Reg must be a physical register.
1150 LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
1151 MCRegister Reg,
1152 const_iterator Before,
1153 unsigned Neighborhood = 10) const;
1154
1155 // Debugging methods.
1156 void dump() const;
1157 void print(raw_ostream &OS, const SlotIndexes * = nullptr,
1158 bool IsStandalone = true) const;
1159 void print(raw_ostream &OS, ModuleSlotTracker &MST,
1160 const SlotIndexes * = nullptr, bool IsStandalone = true) const;
1161
1162 enum PrintNameFlag {
1163 PrintNameIr = (1 << 0), ///< Add IR name where available
1164 PrintNameAttributes = (1 << 1), ///< Print attributes
1165 };
1166
1167 void printName(raw_ostream &os, unsigned printNameFlags = PrintNameIr,
1168 ModuleSlotTracker *moduleSlotTracker = nullptr) const;
1169
1170 // Printing method used by LoopInfo.
1171 void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
1172
1173 /// MachineBasicBlocks are uniquely numbered at the function level, unless
1174 /// they're not in a MachineFunction yet, in which case this will return -1.
1175 int getNumber() const { return Number; }
1176 void setNumber(int N) { Number = N; }
1177
1178 /// Return the call frame size on entry to this basic block.
1179 unsigned getCallFrameSize() const { return CallFrameSize; }
1180 /// Set the call frame size on entry to this basic block.
1181 void setCallFrameSize(unsigned N) { CallFrameSize = N; }
1182
1183 /// Return the MCSymbol for this basic block.
1184 MCSymbol *getSymbol() const;
1185
1186 /// Return the EHCatchret Symbol for this basic block.
1187 MCSymbol *getEHCatchretSymbol() const;
1188
1189 std::optional<uint64_t> getIrrLoopHeaderWeight() const {
1190 return IrrLoopHeaderWeight;
1191 }
1192
1193 void setIrrLoopHeaderWeight(uint64_t Weight) {
1194 IrrLoopHeaderWeight = Weight;
1195 }
1196
1197 /// Return probability of the edge from this block to MBB. This method should
1198 /// NOT be called directly, but by using getEdgeProbability method from
1199 /// MachineBranchProbabilityInfo class.
1200 BranchProbability getSuccProbability(const_succ_iterator Succ) const;
1201
1202private:
1203 /// Return probability iterator corresponding to the I successor iterator.
1204 probability_iterator getProbabilityIterator(succ_iterator I);
1205 const_probability_iterator
1206 getProbabilityIterator(const_succ_iterator I) const;
1207
1208 friend class MachineBranchProbabilityInfo;
1209 friend class MIPrinter;
1210
1211 // Methods used to maintain doubly linked list of blocks...
1212 friend struct ilist_callback_traits<MachineBasicBlock>;
1213
1214 // Machine-CFG mutators
1215
1216 /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
1217 /// unless you know what you're doing, because it doesn't update Pred's
1218 /// successors list. Use Pred->addSuccessor instead.
1219 void addPredecessor(MachineBasicBlock *Pred);
1220
1221 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
1222 /// unless you know what you're doing, because it doesn't update Pred's
1223 /// successors list. Use Pred->removeSuccessor instead.
1224 void removePredecessor(MachineBasicBlock *Pred);
1225};
1226
1227raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
1228
1229/// Prints a machine basic block reference.
1230///
1231/// The format is:
1232/// %bb.5 - a machine basic block with MBB.getNumber() == 5.
1233///
1234/// Usage: OS << printMBBReference(MBB) << '\n';
1235Printable printMBBReference(const MachineBasicBlock &MBB);
1236
1237// This is useful when building IndexedMaps keyed on basic block pointers.
1238struct MBB2NumberFunctor {
1239 using argument_type = const MachineBasicBlock *;
1240 unsigned operator()(const MachineBasicBlock *MBB) const {
1241 return MBB->getNumber();
1242 }
1243};
1244
1245//===--------------------------------------------------------------------===//
1246// GraphTraits specializations for machine basic block graphs (machine-CFGs)
1247//===--------------------------------------------------------------------===//
1248
1249// Provide specializations of GraphTraits to be able to treat a
1250// MachineFunction as a graph of MachineBasicBlocks.
1251//
1252
1253template <> struct GraphTraits<MachineBasicBlock *> {
1254 using NodeRef = MachineBasicBlock *;
1255 using ChildIteratorType = MachineBasicBlock::succ_iterator;
1256
1257 static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
1258 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1259 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1260};
1261
1262template <> struct GraphTraits<const MachineBasicBlock *> {
1263 using NodeRef = const MachineBasicBlock *;
1264 using ChildIteratorType = MachineBasicBlock::const_succ_iterator;
1265
1266 static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
1267 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1268 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1269};
1270
1271// Provide specializations of GraphTraits to be able to treat a
1272// MachineFunction as a graph of MachineBasicBlocks and to walk it
1273// in inverse order. Inverse order for a function is considered
1274// to be when traversing the predecessor edges of a MBB
1275// instead of the successor edges.
1276//
1277template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
1278 using NodeRef = MachineBasicBlock *;
1279 using ChildIteratorType = MachineBasicBlock::pred_iterator;
1280
1281 static NodeRef getEntryNode(Inverse<MachineBasicBlock *> G) {
1282 return G.Graph;
1283 }
1284
1285 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1286 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1287};
1288
1289template <> struct GraphTraits<Inverse<const MachineBasicBlock*>> {
1290 using NodeRef = const MachineBasicBlock *;
1291 using ChildIteratorType = MachineBasicBlock::const_pred_iterator;
1292
1293 static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
1294 return G.Graph;
1295 }
1296
1297 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1298 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1299};
1300
1301// These accessors are handy for sharing templated code between IR and MIR.
1302inline auto successors(const MachineBasicBlock *BB) { return BB->successors(); }
1303inline auto predecessors(const MachineBasicBlock *BB) {
1304 return BB->predecessors();
1305}
1306
1307/// MachineInstrSpan provides an interface to get an iteration range
1308/// containing the instruction it was initialized with, along with all
1309/// those instructions inserted prior to or following that instruction
1310/// at some point after the MachineInstrSpan is constructed.
1311class MachineInstrSpan {
1312 MachineBasicBlock &MBB;
1313 MachineBasicBlock::iterator I, B, E;
1314
1315public:
1316 MachineInstrSpan(MachineBasicBlock::iterator I, MachineBasicBlock *BB)
1317 : MBB(*BB), I(I), B(I == MBB.begin() ? MBB.end() : std::prev(x: I)),
1318 E(std::next(x: I)) {
1319 assert(I == BB->end() || I->getParent() == BB);
1320 }
1321
1322 MachineBasicBlock::iterator begin() {
1323 return B == MBB.end() ? MBB.begin() : std::next(x: B);
1324 }
1325 MachineBasicBlock::iterator end() { return E; }
1326 bool empty() { return begin() == end(); }
1327
1328 MachineBasicBlock::iterator getInitial() { return I; }
1329};
1330
1331/// Increment \p It until it points to a non-debug instruction or to \p End
1332/// and return the resulting iterator. This function should only be used
1333/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1334/// const_instr_iterator} and the respective reverse iterators.
1335template <typename IterT>
1336inline IterT skipDebugInstructionsForward(IterT It, IterT End,
1337 bool SkipPseudoOp = true) {
1338 while (It != End &&
1339 (It->isDebugInstr() || (SkipPseudoOp && It->isPseudoProbe())))
1340 ++It;
1341 return It;
1342}
1343
1344/// Decrement \p It until it points to a non-debug instruction or to \p Begin
1345/// and return the resulting iterator. This function should only be used
1346/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1347/// const_instr_iterator} and the respective reverse iterators.
1348template <class IterT>
1349inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin,
1350 bool SkipPseudoOp = true) {
1351 while (It != Begin &&
1352 (It->isDebugInstr() || (SkipPseudoOp && It->isPseudoProbe())))
1353 --It;
1354 return It;
1355}
1356
1357/// Increment \p It, then continue incrementing it while it points to a debug
1358/// instruction. A replacement for std::next.
1359template <typename IterT>
1360inline IterT next_nodbg(IterT It, IterT End, bool SkipPseudoOp = true) {
1361 return skipDebugInstructionsForward(std::next(It), End, SkipPseudoOp);
1362}
1363
1364/// Decrement \p It, then continue decrementing it while it points to a debug
1365/// instruction. A replacement for std::prev.
1366template <typename IterT>
1367inline IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp = true) {
1368 return skipDebugInstructionsBackward(std::prev(It), Begin, SkipPseudoOp);
1369}
1370
1371/// Construct a range iterator which begins at \p It and moves forwards until
1372/// \p End is reached, skipping any debug instructions.
1373template <typename IterT>
1374inline auto instructionsWithoutDebug(IterT It, IterT End,
1375 bool SkipPseudoOp = true) {
1376 return make_filter_range(make_range(It, End), [=](const MachineInstr &MI) {
1377 return !MI.isDebugInstr() && !(SkipPseudoOp && MI.isPseudoProbe());
1378 });
1379}
1380
1381} // end namespace llvm
1382
1383#endif // LLVM_CODEGEN_MACHINEBASICBLOCK_H
1384

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