1 //===- llvm/CodeGen/MachineBasicBlock.h -------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Collect the sequence of machine instructions for a basic block.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
14 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
16 #include "llvm/ADT/GraphTraits.h"
17 #include "llvm/ADT/ilist.h"
18 #include "llvm/ADT/iterator_range.h"
19 #include "llvm/ADT/SparseBitVector.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"
35 class MachineFunction;
37 class ModuleSlotTracker;
43 class TargetRegisterClass;
44 class TargetRegisterInfo;
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
55 Exception, // Special section type for exception handling blocks
56 Cold, // Special section type for cold blocks
60 MBBSectionID(unsigned N) : Type(Default), Number(N) {}
62 // Special unique sections for cold and exception blocks.
63 const static MBBSectionID ColdSectionID;
64 const static MBBSectionID ExceptionSectionID;
66 bool operator==(const MBBSectionID &Other) const {
67 return Type == Other.Type && Number == Other.Number;
70 bool operator!=(const MBBSectionID &Other) const { return !(*this == Other); }
73 // This is only used to construct the special cold and exception sections.
74 MBBSectionID(SectionType T) : Type(T), Number(0) {}
77 template <> struct ilist_traits<MachineInstr> {
79 friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
81 MachineBasicBlock *Parent;
83 using instr_iterator =
84 simple_ilist<MachineInstr, ilist_sentinel_tracking<true>>::iterator;
87 void addNodeToList(MachineInstr *N);
88 void removeNodeFromList(MachineInstr *N);
89 void transferNodesFromList(ilist_traits &FromList, instr_iterator First,
91 void deleteNode(MachineInstr *MI);
94 class MachineBasicBlock
95 : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> {
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.
100 struct RegisterMaskPair {
103 LaneBitmask LaneMask;
105 RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
106 : PhysReg(PhysReg), LaneMask(LaneMask) {}
110 using Instructions = ilist<MachineInstr, ilist_sentinel_tracking<true>>;
113 const BasicBlock *BB;
115 MachineFunction *xParent;
117 /// Keep track of the predecessor / successor basic blocks.
118 std::vector<MachineBasicBlock *> Predecessors;
119 std::vector<MachineBasicBlock *> Successors;
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
124 std::vector<BranchProbability> Probs;
125 using probability_iterator = std::vector<BranchProbability>::iterator;
126 using const_probability_iterator =
127 std::vector<BranchProbability>::const_iterator;
129 Optional<uint64_t> IrrLoopHeaderWeight;
131 /// Keep track of the physical registers that are livein of the basicblock.
132 using LiveInVector = std::vector<RegisterMaskPair>;
133 LiveInVector LiveIns;
135 /// Alignment of the basic block. One if the basic block does not need to be
139 /// Indicate that this basic block is entered via an exception handler.
140 bool IsEHPad = false;
142 /// Indicate that this basic block is potentially the target of an indirect
144 bool AddressTaken = false;
146 /// Indicate that this basic block needs its symbol be emitted regardless of
147 /// whether the flow just falls-through to it.
148 bool LabelMustBeEmitted = false;
150 /// Indicate that this basic block is the entry block of an EH scope, i.e.,
151 /// the block that used to have a catchpad or cleanuppad instruction in the
153 bool IsEHScopeEntry = false;
155 /// Indicate that this basic block is the entry block of an EH funclet.
156 bool IsEHFuncletEntry = false;
158 /// Indicate that this basic block is the entry block of a cleanup funclet.
159 bool IsCleanupFuncletEntry = false;
161 /// With basic block sections, this stores the Section ID of the basic block.
162 MBBSectionID SectionID{0};
164 // Indicate that this basic block begins a section.
165 bool IsBeginSection = false;
167 // Indicate that this basic block ends a section.
168 bool IsEndSection = false;
170 /// Indicate that this basic block is the indirect dest of an INLINEASM_BR.
171 bool IsInlineAsmBrIndirectTarget = false;
173 /// since getSymbol is a relatively heavy-weight operation, the symbol
174 /// is only computed once and is cached.
175 mutable MCSymbol *CachedMCSymbol = nullptr;
177 /// Used during basic block sections to mark the end of a basic block.
178 MCSymbol *EndMCSymbol = nullptr;
180 // Intrusive list support
181 MachineBasicBlock() = default;
183 explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB);
185 ~MachineBasicBlock();
187 // MachineBasicBlocks are allocated and owned by MachineFunction.
188 friend class MachineFunction;
191 /// Return the LLVM basic block that this instance corresponded to originally.
192 /// Note that this may be NULL if this instance does not correspond directly
193 /// to an LLVM basic block.
194 const BasicBlock *getBasicBlock() const { return BB; }
196 /// Return the name of the corresponding LLVM basic block, or an empty string.
197 StringRef getName() const;
199 /// Return a formatted string to identify this block and its parent function.
200 std::string getFullName() const;
202 /// Test whether this block is potentially the target of an indirect branch.
203 bool hasAddressTaken() const { return AddressTaken; }
205 /// Set this block to reflect that it potentially is the target of an indirect
207 void setHasAddressTaken() { AddressTaken = true; }
209 /// Test whether this block must have its label emitted.
210 bool hasLabelMustBeEmitted() const { return LabelMustBeEmitted; }
212 /// Set this block to reflect that, regardless how we flow to it, we need
213 /// its label be emitted.
214 void setLabelMustBeEmitted() { LabelMustBeEmitted = true; }
216 /// Return the MachineFunction containing this basic block.
217 const MachineFunction *getParent() const { return xParent; }
218 MachineFunction *getParent() { return xParent; }
220 using instr_iterator = Instructions::iterator;
221 using const_instr_iterator = Instructions::const_iterator;
222 using reverse_instr_iterator = Instructions::reverse_iterator;
223 using const_reverse_instr_iterator = Instructions::const_reverse_iterator;
225 using iterator = MachineInstrBundleIterator<MachineInstr>;
226 using const_iterator = MachineInstrBundleIterator<const MachineInstr>;
227 using reverse_iterator = MachineInstrBundleIterator<MachineInstr, true>;
228 using const_reverse_iterator =
229 MachineInstrBundleIterator<const MachineInstr, true>;
231 unsigned size() const { return (unsigned)Insts.size(); }
232 bool empty() const { return Insts.empty(); }
234 MachineInstr &instr_front() { return Insts.front(); }
235 MachineInstr &instr_back() { return Insts.back(); }
236 const MachineInstr &instr_front() const { return Insts.front(); }
237 const MachineInstr &instr_back() const { return Insts.back(); }
239 MachineInstr &front() { return Insts.front(); }
240 MachineInstr &back() { return *--end(); }
241 const MachineInstr &front() const { return Insts.front(); }
242 const MachineInstr &back() const { return *--end(); }
244 instr_iterator instr_begin() { return Insts.begin(); }
245 const_instr_iterator instr_begin() const { return Insts.begin(); }
246 instr_iterator instr_end() { return Insts.end(); }
247 const_instr_iterator instr_end() const { return Insts.end(); }
248 reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); }
249 const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
250 reverse_instr_iterator instr_rend () { return Insts.rend(); }
251 const_reverse_instr_iterator instr_rend () const { return Insts.rend(); }
253 using instr_range = iterator_range<instr_iterator>;
254 using const_instr_range = iterator_range<const_instr_iterator>;
255 instr_range instrs() { return instr_range(instr_begin(), instr_end()); }
256 const_instr_range instrs() const {
257 return const_instr_range(instr_begin(), instr_end());
260 iterator begin() { return instr_begin(); }
261 const_iterator begin() const { return instr_begin(); }
262 iterator end () { return instr_end(); }
263 const_iterator end () const { return instr_end(); }
264 reverse_iterator rbegin() {
265 return reverse_iterator::getAtBundleBegin(instr_rbegin());
267 const_reverse_iterator rbegin() const {
268 return const_reverse_iterator::getAtBundleBegin(instr_rbegin());
270 reverse_iterator rend() { return reverse_iterator(instr_rend()); }
271 const_reverse_iterator rend() const {
272 return const_reverse_iterator(instr_rend());
275 /// Support for MachineInstr::getNextNode().
276 static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) {
277 return &MachineBasicBlock::Insts;
280 inline iterator_range<iterator> terminators() {
281 return make_range(getFirstTerminator(), end());
283 inline iterator_range<const_iterator> terminators() const {
284 return make_range(getFirstTerminator(), end());
287 /// Returns a range that iterates over the phis in the basic block.
288 inline iterator_range<iterator> phis() {
289 return make_range(begin(), getFirstNonPHI());
291 inline iterator_range<const_iterator> phis() const {
292 return const_cast<MachineBasicBlock *>(this)->phis();
295 // Machine-CFG iterators
296 using pred_iterator = std::vector<MachineBasicBlock *>::iterator;
297 using const_pred_iterator = std::vector<MachineBasicBlock *>::const_iterator;
298 using succ_iterator = std::vector<MachineBasicBlock *>::iterator;
299 using const_succ_iterator = std::vector<MachineBasicBlock *>::const_iterator;
300 using pred_reverse_iterator =
301 std::vector<MachineBasicBlock *>::reverse_iterator;
302 using const_pred_reverse_iterator =
303 std::vector<MachineBasicBlock *>::const_reverse_iterator;
304 using succ_reverse_iterator =
305 std::vector<MachineBasicBlock *>::reverse_iterator;
306 using const_succ_reverse_iterator =
307 std::vector<MachineBasicBlock *>::const_reverse_iterator;
308 pred_iterator pred_begin() { return Predecessors.begin(); }
309 const_pred_iterator pred_begin() const { return Predecessors.begin(); }
310 pred_iterator pred_end() { return Predecessors.end(); }
311 const_pred_iterator pred_end() const { return Predecessors.end(); }
312 pred_reverse_iterator pred_rbegin()
313 { return Predecessors.rbegin();}
314 const_pred_reverse_iterator pred_rbegin() const
315 { return Predecessors.rbegin();}
316 pred_reverse_iterator pred_rend()
317 { return Predecessors.rend(); }
318 const_pred_reverse_iterator pred_rend() const
319 { return Predecessors.rend(); }
320 unsigned pred_size() const {
321 return (unsigned)Predecessors.size();
323 bool pred_empty() const { return Predecessors.empty(); }
324 succ_iterator succ_begin() { return Successors.begin(); }
325 const_succ_iterator succ_begin() const { return Successors.begin(); }
326 succ_iterator succ_end() { return Successors.end(); }
327 const_succ_iterator succ_end() const { return Successors.end(); }
328 succ_reverse_iterator succ_rbegin()
329 { return Successors.rbegin(); }
330 const_succ_reverse_iterator succ_rbegin() const
331 { return Successors.rbegin(); }
332 succ_reverse_iterator succ_rend()
333 { return Successors.rend(); }
334 const_succ_reverse_iterator succ_rend() const
335 { return Successors.rend(); }
336 unsigned succ_size() const {
337 return (unsigned)Successors.size();
339 bool succ_empty() const { return Successors.empty(); }
341 inline iterator_range<pred_iterator> predecessors() {
342 return make_range(pred_begin(), pred_end());
344 inline iterator_range<const_pred_iterator> predecessors() const {
345 return make_range(pred_begin(), pred_end());
347 inline iterator_range<succ_iterator> successors() {
348 return make_range(succ_begin(), succ_end());
350 inline iterator_range<const_succ_iterator> successors() const {
351 return make_range(succ_begin(), succ_end());
354 // LiveIn management methods.
356 /// Adds the specified register as a live in. Note that it is an error to add
357 /// the same register to the same set more than once unless the intention is
358 /// to call sortUniqueLiveIns after all registers are added.
359 void addLiveIn(MCRegister PhysReg,
360 LaneBitmask LaneMask = LaneBitmask::getAll()) {
361 LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
363 void addLiveIn(const RegisterMaskPair &RegMaskPair) {
364 LiveIns.push_back(RegMaskPair);
367 /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
368 /// this than repeatedly calling isLiveIn before calling addLiveIn for every
369 /// LiveIn insertion.
370 void sortUniqueLiveIns();
372 /// Clear live in list.
375 /// Add PhysReg as live in to this block, and ensure that there is a copy of
376 /// PhysReg to a virtual register of class RC. Return the virtual register
377 /// that is a copy of the live in PhysReg.
378 Register addLiveIn(MCRegister PhysReg, const TargetRegisterClass *RC);
380 /// Remove the specified register from the live in set.
381 void removeLiveIn(MCPhysReg Reg,
382 LaneBitmask LaneMask = LaneBitmask::getAll());
384 /// Return true if the specified register is in the live in set.
385 bool isLiveIn(MCPhysReg Reg,
386 LaneBitmask LaneMask = LaneBitmask::getAll()) const;
388 // Iteration support for live in sets. These sets are kept in sorted
389 // order by their register number.
390 using livein_iterator = LiveInVector::const_iterator;
392 /// Unlike livein_begin, this method does not check that the liveness
393 /// information is accurate. Still for debug purposes it may be useful
394 /// to have iterators that won't assert if the liveness information
396 livein_iterator livein_begin_dbg() const { return LiveIns.begin(); }
397 iterator_range<livein_iterator> liveins_dbg() const {
398 return make_range(livein_begin_dbg(), livein_end());
401 livein_iterator livein_begin() const;
402 livein_iterator livein_end() const { return LiveIns.end(); }
403 bool livein_empty() const { return LiveIns.empty(); }
404 iterator_range<livein_iterator> liveins() const {
405 return make_range(livein_begin(), livein_end());
408 /// Remove entry from the livein set and return iterator to the next.
409 livein_iterator removeLiveIn(livein_iterator I);
411 /// Get the clobber mask for the start of this basic block. Funclets use this
412 /// to prevent register allocation across funclet transitions.
413 const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
415 /// Get the clobber mask for the end of the basic block.
416 /// \see getBeginClobberMask()
417 const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
419 /// Return alignment of the basic block.
420 Align getAlignment() const { return Alignment; }
422 /// Set alignment of the basic block.
423 void setAlignment(Align A) { Alignment = A; }
425 /// Returns true if the block is a landing pad. That is this basic block is
426 /// entered via an exception handler.
427 bool isEHPad() const { return IsEHPad; }
429 /// Indicates the block is a landing pad. That is this basic block is entered
430 /// via an exception handler.
431 void setIsEHPad(bool V = true) { IsEHPad = V; }
433 bool hasEHPadSuccessor() const;
435 /// Returns true if this is the entry block of an EH scope, i.e., the block
436 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
437 bool isEHScopeEntry() const { return IsEHScopeEntry; }
439 /// Indicates if this is the entry block of an EH scope, i.e., the block that
440 /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
441 void setIsEHScopeEntry(bool V = true) { IsEHScopeEntry = V; }
443 /// Returns true if this is the entry block of an EH funclet.
444 bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
446 /// Indicates if this is the entry block of an EH funclet.
447 void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
449 /// Returns true if this is the entry block of a cleanup funclet.
450 bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
452 /// Indicates if this is the entry block of a cleanup funclet.
453 void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
455 /// Returns true if this block begins any section.
456 bool isBeginSection() const { return IsBeginSection; }
458 /// Returns true if this block ends any section.
459 bool isEndSection() const { return IsEndSection; }
461 void setIsBeginSection(bool V = true) { IsBeginSection = V; }
463 void setIsEndSection(bool V = true) { IsEndSection = V; }
465 /// Returns the section ID of this basic block.
466 MBBSectionID getSectionID() const { return SectionID; }
468 /// Returns the unique section ID number of this basic block.
469 unsigned getSectionIDNum() const {
470 return ((unsigned)MBBSectionID::SectionType::Cold) -
471 ((unsigned)SectionID.Type) + SectionID.Number;
474 /// Sets the section ID for this basic block.
475 void setSectionID(MBBSectionID V) { SectionID = V; }
477 /// Returns true if this block may have an INLINEASM_BR (overestimate, by
478 /// checking if any of the successors are indirect targets of any inlineasm_br
479 /// in the function).
480 bool mayHaveInlineAsmBr() const;
482 /// Returns true if this is the indirect dest of an INLINEASM_BR.
483 bool isInlineAsmBrIndirectTarget() const {
484 return IsInlineAsmBrIndirectTarget;
487 /// Indicates if this is the indirect dest of an INLINEASM_BR.
488 void setIsInlineAsmBrIndirectTarget(bool V = true) {
489 IsInlineAsmBrIndirectTarget = V;
492 /// Returns true if it is legal to hoist instructions into this block.
493 bool isLegalToHoistInto() const;
495 // Code Layout methods.
497 /// Move 'this' block before or after the specified block. This only moves
498 /// the block, it does not modify the CFG or adjust potential fall-throughs at
499 /// the end of the block.
500 void moveBefore(MachineBasicBlock *NewAfter);
501 void moveAfter(MachineBasicBlock *NewBefore);
503 /// Returns true if this and MBB belong to the same section.
504 bool sameSection(const MachineBasicBlock *MBB) const {
505 return getSectionID() == MBB->getSectionID();
508 /// Update the terminator instructions in block to account for changes to
509 /// block layout which may have been made. PreviousLayoutSuccessor should be
510 /// set to the block which may have been used as fallthrough before the block
511 /// layout was modified. If the block previously fell through to that block,
512 /// it may now need a branch. If it previously branched to another block, it
513 /// may now be able to fallthrough to the current layout successor.
514 void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor);
516 // Machine-CFG mutators
518 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
519 /// of Succ is automatically updated. PROB parameter is stored in
520 /// Probabilities list. The default probability is set as unknown. Mixing
521 /// known and unknown probabilities in successor list is not allowed. When all
522 /// successors have unknown probabilities, 1 / N is returned as the
523 /// probability for each successor, where N is the number of successors.
525 /// Note that duplicate Machine CFG edges are not allowed.
526 void addSuccessor(MachineBasicBlock *Succ,
527 BranchProbability Prob = BranchProbability::getUnknown());
529 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
530 /// of Succ is automatically updated. The probability is not provided because
531 /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
532 /// won't be used. Using this interface can save some space.
533 void addSuccessorWithoutProb(MachineBasicBlock *Succ);
535 /// Set successor probability of a given iterator.
536 void setSuccProbability(succ_iterator I, BranchProbability Prob);
538 /// Normalize probabilities of all successors so that the sum of them becomes
539 /// one. This is usually done when the current update on this MBB is done, and
540 /// the sum of its successors' probabilities is not guaranteed to be one. The
541 /// user is responsible for the correct use of this function.
542 /// MBB::removeSuccessor() has an option to do this automatically.
543 void normalizeSuccProbs() {
544 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
547 /// Validate successors' probabilities and check if the sum of them is
548 /// approximate one. This only works in DEBUG mode.
549 void validateSuccProbs() const;
551 /// Remove successor from the successors list of this MachineBasicBlock. The
552 /// Predecessors list of Succ is automatically updated.
553 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
554 /// after the successor is removed.
555 void removeSuccessor(MachineBasicBlock *Succ,
556 bool NormalizeSuccProbs = false);
558 /// Remove specified successor from the successors list of this
559 /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
560 /// If NormalizeSuccProbs is true, then normalize successors' probabilities
561 /// after the successor is removed.
562 /// Return the iterator to the element after the one removed.
563 succ_iterator removeSuccessor(succ_iterator I,
564 bool NormalizeSuccProbs = false);
566 /// Replace successor OLD with NEW and update probability info.
567 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
569 /// Copy a successor (and any probability info) from original block to this
570 /// block's. Uses an iterator into the original blocks successors.
572 /// This is useful when doing a partial clone of successors. Afterward, the
573 /// probabilities may need to be normalized.
574 void copySuccessor(MachineBasicBlock *Orig, succ_iterator I);
576 /// Split the old successor into old plus new and updates the probability
578 void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New,
579 bool NormalizeSuccProbs = false);
581 /// Transfers all the successors from MBB to this machine basic block (i.e.,
582 /// copies all the successors FromMBB and remove all the successors from
584 void transferSuccessors(MachineBasicBlock *FromMBB);
586 /// Transfers all the successors, as in transferSuccessors, and update PHI
587 /// operands in the successor blocks which refer to FromMBB to refer to this.
588 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
590 /// Return true if any of the successors have probabilities attached to them.
591 bool hasSuccessorProbabilities() const { return !Probs.empty(); }
593 /// Return true if the specified MBB is a predecessor of this block.
594 bool isPredecessor(const MachineBasicBlock *MBB) const;
596 /// Return true if the specified MBB is a successor of this block.
597 bool isSuccessor(const MachineBasicBlock *MBB) const;
599 /// Return true if the specified MBB will be emitted immediately after this
600 /// block, such that if this block exits by falling through, control will
601 /// transfer to the specified MBB. Note that MBB need not be a successor at
602 /// all, for example if this block ends with an unconditional branch to some
604 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
606 /// Return the fallthrough block if the block can implicitly
607 /// transfer control to the block after it by falling off the end of
608 /// it. This should return null if it can reach the block after
609 /// it, but it uses an explicit branch to do so (e.g., a table
610 /// jump). Non-null return is a conservative answer.
611 MachineBasicBlock *getFallThrough();
613 /// Return true if the block can implicitly transfer control to the
614 /// block after it by falling off the end of it. This should return
615 /// false if it can reach the block after it, but it uses an
616 /// explicit branch to do so (e.g., a table jump). True is a
617 /// conservative answer.
618 bool canFallThrough();
620 /// Returns a pointer to the first instruction in this block that is not a
621 /// PHINode instruction. When adding instructions to the beginning of the
622 /// basic block, they should be added before the returned value, not before
623 /// the first instruction, which might be PHI.
624 /// Returns end() is there's no non-PHI instruction.
625 iterator getFirstNonPHI();
627 /// Return the first instruction in MBB after I that is not a PHI or a label.
628 /// This is the correct point to insert lowered copies at the beginning of a
629 /// basic block that must be before any debugging information.
630 iterator SkipPHIsAndLabels(iterator I);
632 /// Return the first instruction in MBB after I that is not a PHI, label or
633 /// debug. This is the correct point to insert copies at the beginning of a
635 iterator SkipPHIsLabelsAndDebug(iterator I);
637 /// Returns an iterator to the first terminator instruction of this basic
638 /// block. If a terminator does not exist, it returns end().
639 iterator getFirstTerminator();
640 const_iterator getFirstTerminator() const {
641 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
644 /// Same getFirstTerminator but it ignores bundles and return an
645 /// instr_iterator instead.
646 instr_iterator getFirstInstrTerminator();
648 /// Returns an iterator to the first non-debug instruction in the basic block,
650 iterator getFirstNonDebugInstr();
651 const_iterator getFirstNonDebugInstr() const {
652 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr();
655 /// Returns an iterator to the last non-debug instruction in the basic block,
657 iterator getLastNonDebugInstr();
658 const_iterator getLastNonDebugInstr() const {
659 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr();
662 /// Convenience function that returns true if the block ends in a return
664 bool isReturnBlock() const {
665 return !empty() && back().isReturn();
668 /// Convenience function that returns true if the bock ends in a EH scope
669 /// return instruction.
670 bool isEHScopeReturnBlock() const {
671 return !empty() && back().isEHScopeReturn();
674 /// Split the critical edge from this block to the given successor block, and
675 /// return the newly created block, or null if splitting is not possible.
677 /// This function updates LiveVariables, MachineDominatorTree, and
678 /// MachineLoopInfo, as applicable.
680 SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P,
681 std::vector<SparseBitVector<>> *LiveInSets = nullptr);
683 /// Check if the edge between this block and the given successor \p
684 /// Succ, can be split. If this returns true a subsequent call to
685 /// SplitCriticalEdge is guaranteed to return a valid basic block if
686 /// no changes occurred in the meantime.
687 bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
689 void pop_front() { Insts.pop_front(); }
690 void pop_back() { Insts.pop_back(); }
691 void push_back(MachineInstr *MI) { Insts.push_back(MI); }
693 /// Insert MI into the instruction list before I, possibly inside a bundle.
695 /// If the insertion point is inside a bundle, MI will be added to the bundle,
696 /// otherwise MI will not be added to any bundle. That means this function
697 /// alone can't be used to prepend or append instructions to bundles. See
698 /// MIBundleBuilder::insert() for a more reliable way of doing that.
699 instr_iterator insert(instr_iterator I, MachineInstr *M);
701 /// Insert a range of instructions into the instruction list before I.
702 template<typename IT>
703 void insert(iterator I, IT S, IT E) {
704 assert((I == end() || I->getParent() == this) &&
705 "iterator points outside of basic block");
706 Insts.insert(I.getInstrIterator(), S, E);
709 /// Insert MI into the instruction list before I.
710 iterator insert(iterator I, MachineInstr *MI) {
711 assert((I == end() || I->getParent() == this) &&
712 "iterator points outside of basic block");
713 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
714 "Cannot insert instruction with bundle flags");
715 return Insts.insert(I.getInstrIterator(), MI);
718 /// Insert MI into the instruction list after I.
719 iterator insertAfter(iterator I, MachineInstr *MI) {
720 assert((I == end() || I->getParent() == this) &&
721 "iterator points outside of basic block");
722 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
723 "Cannot insert instruction with bundle flags");
724 return Insts.insertAfter(I.getInstrIterator(), MI);
727 /// If I is bundled then insert MI into the instruction list after the end of
728 /// the bundle, otherwise insert MI immediately after I.
729 instr_iterator insertAfterBundle(instr_iterator I, MachineInstr *MI) {
730 assert((I == instr_end() || I->getParent() == this) &&
731 "iterator points outside of basic block");
732 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
733 "Cannot insert instruction with bundle flags");
734 while (I->isBundledWithSucc())
736 return Insts.insertAfter(I, MI);
739 /// Remove an instruction from the instruction list and delete it.
741 /// If the instruction is part of a bundle, the other instructions in the
742 /// bundle will still be bundled after removing the single instruction.
743 instr_iterator erase(instr_iterator I);
745 /// Remove an instruction from the instruction list and delete it.
747 /// If the instruction is part of a bundle, the other instructions in the
748 /// bundle will still be bundled after removing the single instruction.
749 instr_iterator erase_instr(MachineInstr *I) {
750 return erase(instr_iterator(I));
753 /// Remove a range of instructions from the instruction list and delete them.
754 iterator erase(iterator I, iterator E) {
755 return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
758 /// Remove an instruction or bundle from the instruction list and delete it.
760 /// If I points to a bundle of instructions, they are all erased.
761 iterator erase(iterator I) {
762 return erase(I, std::next(I));
765 /// Remove an instruction from the instruction list and delete it.
767 /// If I is the head of a bundle of instructions, the whole bundle will be
769 iterator erase(MachineInstr *I) {
770 return erase(iterator(I));
773 /// Remove the unbundled instruction from the instruction list without
776 /// This function can not be used to remove bundled instructions, use
777 /// remove_instr to remove individual instructions from a bundle.
778 MachineInstr *remove(MachineInstr *I) {
779 assert(!I->isBundled() && "Cannot remove bundled instructions");
780 return Insts.remove(instr_iterator(I));
783 /// Remove the possibly bundled instruction from the instruction list
784 /// without deleting it.
786 /// If the instruction is part of a bundle, the other instructions in the
787 /// bundle will still be bundled after removing the single instruction.
788 MachineInstr *remove_instr(MachineInstr *I);
794 /// Take an instruction from MBB 'Other' at the position From, and insert it
795 /// into this MBB right before 'Where'.
797 /// If From points to a bundle of instructions, the whole bundle is moved.
798 void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
799 // The range splice() doesn't allow noop moves, but this one does.
801 splice(Where, Other, From, std::next(From));
804 /// Take a block of instructions from MBB 'Other' in the range [From, To),
805 /// and insert them into this MBB right before 'Where'.
807 /// The instruction at 'Where' must not be included in the range of
808 /// instructions to move.
809 void splice(iterator Where, MachineBasicBlock *Other,
810 iterator From, iterator To) {
811 Insts.splice(Where.getInstrIterator(), Other->Insts,
812 From.getInstrIterator(), To.getInstrIterator());
815 /// This method unlinks 'this' from the containing function, and returns it,
816 /// but does not delete it.
817 MachineBasicBlock *removeFromParent();
819 /// This method unlinks 'this' from the containing function and deletes it.
820 void eraseFromParent();
822 /// Given a machine basic block that branched to 'Old', change the code and
823 /// CFG so that it branches to 'New' instead.
824 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
826 /// Update all phi nodes in this basic block to refer to basic block \p New
827 /// instead of basic block \p Old.
828 void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New);
830 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
831 /// and DBG_LABEL instructions. Return UnknownLoc if there is none.
832 DebugLoc findDebugLoc(instr_iterator MBBI);
833 DebugLoc findDebugLoc(iterator MBBI) {
834 return findDebugLoc(MBBI.getInstrIterator());
837 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
838 /// instructions. Return UnknownLoc if there is none.
839 DebugLoc findPrevDebugLoc(instr_iterator MBBI);
840 DebugLoc findPrevDebugLoc(iterator MBBI) {
841 return findPrevDebugLoc(MBBI.getInstrIterator());
844 /// Find and return the merged DebugLoc of the branch instructions of the
845 /// block. Return UnknownLoc if there is none.
846 DebugLoc findBranchDebugLoc();
848 /// Possible outcome of a register liveness query to computeRegisterLiveness()
849 enum LivenessQueryResult {
850 LQR_Live, ///< Register is known to be (at least partially) live.
851 LQR_Dead, ///< Register is known to be fully dead.
852 LQR_Unknown ///< Register liveness not decidable from local neighborhood.
855 /// Return whether (physical) register \p Reg has been defined and not
856 /// killed as of just before \p Before.
858 /// Search is localised to a neighborhood of \p Neighborhood instructions
859 /// before (searching for defs or kills) and \p Neighborhood instructions
860 /// after (searching just for defs) \p Before.
862 /// \p Reg must be a physical register.
863 LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
865 const_iterator Before,
866 unsigned Neighborhood = 10) const;
868 // Debugging methods.
870 void print(raw_ostream &OS, const SlotIndexes * = nullptr,
871 bool IsStandalone = true) const;
872 void print(raw_ostream &OS, ModuleSlotTracker &MST,
873 const SlotIndexes * = nullptr, bool IsStandalone = true) const;
875 // Printing method used by LoopInfo.
876 void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
878 /// MachineBasicBlocks are uniquely numbered at the function level, unless
879 /// they're not in a MachineFunction yet, in which case this will return -1.
880 int getNumber() const { return Number; }
881 void setNumber(int N) { Number = N; }
883 /// Return the MCSymbol for this basic block.
884 MCSymbol *getSymbol() const;
886 Optional<uint64_t> getIrrLoopHeaderWeight() const {
887 return IrrLoopHeaderWeight;
890 void setIrrLoopHeaderWeight(uint64_t Weight) {
891 IrrLoopHeaderWeight = Weight;
895 /// Return probability iterator corresponding to the I successor iterator.
896 probability_iterator getProbabilityIterator(succ_iterator I);
897 const_probability_iterator
898 getProbabilityIterator(const_succ_iterator I) const;
900 friend class MachineBranchProbabilityInfo;
901 friend class MIPrinter;
903 /// Return probability of the edge from this block to MBB. This method should
904 /// NOT be called directly, but by using getEdgeProbability method from
905 /// MachineBranchProbabilityInfo class.
906 BranchProbability getSuccProbability(const_succ_iterator Succ) const;
908 // Methods used to maintain doubly linked list of blocks...
909 friend struct ilist_callback_traits<MachineBasicBlock>;
911 // Machine-CFG mutators
913 /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
914 /// unless you know what you're doing, because it doesn't update Pred's
915 /// successors list. Use Pred->addSuccessor instead.
916 void addPredecessor(MachineBasicBlock *Pred);
918 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
919 /// unless you know what you're doing, because it doesn't update Pred's
920 /// successors list. Use Pred->removeSuccessor instead.
921 void removePredecessor(MachineBasicBlock *Pred);
924 raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
926 /// Prints a machine basic block reference.
929 /// %bb.5 - a machine basic block with MBB.getNumber() == 5.
931 /// Usage: OS << printMBBReference(MBB) << '\n';
932 Printable printMBBReference(const MachineBasicBlock &MBB);
934 // This is useful when building IndexedMaps keyed on basic block pointers.
935 struct MBB2NumberFunctor {
936 using argument_type = const MachineBasicBlock *;
937 unsigned operator()(const MachineBasicBlock *MBB) const {
938 return MBB->getNumber();
942 //===--------------------------------------------------------------------===//
943 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
944 //===--------------------------------------------------------------------===//
946 // Provide specializations of GraphTraits to be able to treat a
947 // MachineFunction as a graph of MachineBasicBlocks.
950 template <> struct GraphTraits<MachineBasicBlock *> {
951 using NodeRef = MachineBasicBlock *;
952 using ChildIteratorType = MachineBasicBlock::succ_iterator;
954 static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
955 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
956 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
959 template <> struct GraphTraits<const MachineBasicBlock *> {
960 using NodeRef = const MachineBasicBlock *;
961 using ChildIteratorType = MachineBasicBlock::const_succ_iterator;
963 static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
964 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
965 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
968 // Provide specializations of GraphTraits to be able to treat a
969 // MachineFunction as a graph of MachineBasicBlocks and to walk it
970 // in inverse order. Inverse order for a function is considered
971 // to be when traversing the predecessor edges of a MBB
972 // instead of the successor edges.
974 template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
975 using NodeRef = MachineBasicBlock *;
976 using ChildIteratorType = MachineBasicBlock::pred_iterator;
978 static NodeRef getEntryNode(Inverse<MachineBasicBlock *> G) {
982 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
983 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
986 template <> struct GraphTraits<Inverse<const MachineBasicBlock*>> {
987 using NodeRef = const MachineBasicBlock *;
988 using ChildIteratorType = MachineBasicBlock::const_pred_iterator;
990 static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
994 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
995 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
998 /// MachineInstrSpan provides an interface to get an iteration range
999 /// containing the instruction it was initialized with, along with all
1000 /// those instructions inserted prior to or following that instruction
1001 /// at some point after the MachineInstrSpan is constructed.
1002 class MachineInstrSpan {
1003 MachineBasicBlock &MBB;
1004 MachineBasicBlock::iterator I, B, E;
1007 MachineInstrSpan(MachineBasicBlock::iterator I, MachineBasicBlock *BB)
1008 : MBB(*BB), I(I), B(I == MBB.begin() ? MBB.end() : std::prev(I)),
1010 assert(I == BB->end() || I->getParent() == BB);
1013 MachineBasicBlock::iterator begin() {
1014 return B == MBB.end() ? MBB.begin() : std::next(B);
1016 MachineBasicBlock::iterator end() { return E; }
1017 bool empty() { return begin() == end(); }
1019 MachineBasicBlock::iterator getInitial() { return I; }
1022 /// Increment \p It until it points to a non-debug instruction or to \p End
1023 /// and return the resulting iterator. This function should only be used
1024 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1025 /// const_instr_iterator} and the respective reverse iterators.
1026 template<typename IterT>
1027 inline IterT skipDebugInstructionsForward(IterT It, IterT End) {
1028 while (It != End && It->isDebugInstr())
1033 /// Decrement \p It until it points to a non-debug instruction or to \p Begin
1034 /// and return the resulting iterator. This function should only be used
1035 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
1036 /// const_instr_iterator} and the respective reverse iterators.
1037 template<class IterT>
1038 inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin) {
1039 while (It != Begin && It->isDebugInstr())
1044 /// Increment \p It, then continue incrementing it while it points to a debug
1045 /// instruction. A replacement for std::next.
1046 template <typename IterT> inline IterT next_nodbg(IterT It, IterT End) {
1047 return skipDebugInstructionsForward(std::next(It), End);
1050 /// Decrement \p It, then continue decrementing it while it points to a debug
1051 /// instruction. A replacement for std::prev.
1052 template <typename IterT> inline IterT prev_nodbg(IterT It, IterT Begin) {
1053 return skipDebugInstructionsBackward(std::prev(It), Begin);
1056 /// Construct a range iterator which begins at \p It and moves forwards until
1057 /// \p End is reached, skipping any debug instructions.
1058 template <typename IterT>
1059 inline auto instructionsWithoutDebug(IterT It, IterT End) {
1060 return make_filter_range(make_range(It, End), [](const MachineInstr &MI) {
1061 return !MI.isDebugInstr();
1065 } // end namespace llvm
1067 #endif // LLVM_CODEGEN_MACHINEBASICBLOCK_H