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