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