Line data Source code
1 : //===- llvm/CodeGen/MachineBasicBlock.h -------------------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // Collect the sequence of machine instructions for a basic block.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
15 : #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
16 :
17 : #include "llvm/ADT/GraphTraits.h"
18 : #include "llvm/ADT/ilist.h"
19 : #include "llvm/ADT/ilist_node.h"
20 : #include "llvm/ADT/iterator_range.h"
21 : #include "llvm/ADT/simple_ilist.h"
22 : #include "llvm/CodeGen/MachineInstr.h"
23 : #include "llvm/CodeGen/MachineInstrBundleIterator.h"
24 : #include "llvm/IR/DebugLoc.h"
25 : #include "llvm/MC/LaneBitmask.h"
26 : #include "llvm/MC/MCRegisterInfo.h"
27 : #include "llvm/Support/BranchProbability.h"
28 : #include "llvm/Support/Printable.h"
29 : #include <cassert>
30 : #include <cstdint>
31 : #include <functional>
32 : #include <iterator>
33 : #include <string>
34 : #include <vector>
35 :
36 : namespace llvm {
37 :
38 : class BasicBlock;
39 : class MachineFunction;
40 : class MCSymbol;
41 : class ModuleSlotTracker;
42 : class Pass;
43 : class SlotIndexes;
44 : class StringRef;
45 : class raw_ostream;
46 : class TargetRegisterClass;
47 : class TargetRegisterInfo;
48 :
49 : template <> struct ilist_traits<MachineInstr> {
50 : private:
51 : friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
52 :
53 : MachineBasicBlock *Parent;
54 :
55 : using instr_iterator =
56 : simple_ilist<MachineInstr, ilist_sentinel_tracking<true>>::iterator;
57 :
58 : public:
59 : void addNodeToList(MachineInstr *N);
60 : void removeNodeFromList(MachineInstr *N);
61 : void transferNodesFromList(ilist_traits &FromList, instr_iterator First,
62 : instr_iterator Last);
63 : void deleteNode(MachineInstr *MI);
64 : };
65 :
66 : class MachineBasicBlock
67 : : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> {
68 : public:
69 : /// Pair of physical register and lane mask.
70 : /// This is not simply a std::pair typedef because the members should be named
71 : /// clearly as they both have an integer type.
72 : struct RegisterMaskPair {
73 : public:
74 : MCPhysReg PhysReg;
75 : LaneBitmask LaneMask;
76 :
77 : RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
78 2101923 : : PhysReg(PhysReg), LaneMask(LaneMask) {}
79 : };
80 :
81 : private:
82 : using Instructions = ilist<MachineInstr, ilist_sentinel_tracking<true>>;
83 :
84 : Instructions Insts;
85 : const BasicBlock *BB;
86 : int Number;
87 : MachineFunction *xParent;
88 :
89 : /// Keep track of the predecessor / successor basic blocks.
90 : std::vector<MachineBasicBlock *> Predecessors;
91 : std::vector<MachineBasicBlock *> Successors;
92 :
93 : /// Keep track of the probabilities to the successors. This vector has the
94 : /// same order as Successors, or it is empty if we don't use it (disable
95 : /// optimization).
96 : std::vector<BranchProbability> Probs;
97 : using probability_iterator = std::vector<BranchProbability>::iterator;
98 : using const_probability_iterator =
99 : std::vector<BranchProbability>::const_iterator;
100 :
101 : Optional<uint64_t> IrrLoopHeaderWeight;
102 :
103 : /// Keep track of the physical registers that are livein of the basicblock.
104 : using LiveInVector = std::vector<RegisterMaskPair>;
105 : LiveInVector LiveIns;
106 :
107 : /// Alignment of the basic block. Zero if the basic block does not need to be
108 : /// aligned. The alignment is specified as log2(bytes).
109 : unsigned Alignment = 0;
110 :
111 : /// Indicate that this basic block is entered via an exception handler.
112 : bool IsEHPad = false;
113 :
114 : /// Indicate that this basic block is potentially the target of an indirect
115 : /// branch.
116 : bool AddressTaken = false;
117 :
118 : /// Indicate that this basic block is the entry block of an EH scope, i.e.,
119 : /// the block that used to have a catchpad or cleanuppad instruction in the
120 : /// LLVM IR.
121 : bool IsEHScopeEntry = false;
122 :
123 : /// Indicate that this basic block is the entry block of an EH funclet.
124 : bool IsEHFuncletEntry = false;
125 :
126 : /// Indicate that this basic block is the entry block of a cleanup funclet.
127 : bool IsCleanupFuncletEntry = false;
128 :
129 : /// since getSymbol is a relatively heavy-weight operation, the symbol
130 : /// is only computed once and is cached.
131 : mutable MCSymbol *CachedMCSymbol = nullptr;
132 :
133 : // Intrusive list support
134 : MachineBasicBlock() = default;
135 :
136 : explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB);
137 :
138 : ~MachineBasicBlock();
139 :
140 : // MachineBasicBlocks are allocated and owned by MachineFunction.
141 : friend class MachineFunction;
142 :
143 : public:
144 : /// Return the LLVM basic block that this instance corresponded to originally.
145 : /// Note that this may be NULL if this instance does not correspond directly
146 : /// to an LLVM basic block.
147 0 : const BasicBlock *getBasicBlock() const { return BB; }
148 :
149 : /// Return the name of the corresponding LLVM basic block, or an empty string.
150 : StringRef getName() const;
151 :
152 : /// Return a formatted string to identify this block and its parent function.
153 : std::string getFullName() const;
154 :
155 : /// Test whether this block is potentially the target of an indirect branch.
156 0 : bool hasAddressTaken() const { return AddressTaken; }
157 :
158 : /// Set this block to reflect that it potentially is the target of an indirect
159 : /// branch.
160 748 : void setHasAddressTaken() { AddressTaken = true; }
161 :
162 : /// Return the MachineFunction containing this basic block.
163 0 : const MachineFunction *getParent() const { return xParent; }
164 0 : MachineFunction *getParent() { return xParent; }
165 :
166 : using instr_iterator = Instructions::iterator;
167 : using const_instr_iterator = Instructions::const_iterator;
168 : using reverse_instr_iterator = Instructions::reverse_iterator;
169 : using const_reverse_instr_iterator = Instructions::const_reverse_iterator;
170 :
171 : using iterator = MachineInstrBundleIterator<MachineInstr>;
172 : using const_iterator = MachineInstrBundleIterator<const MachineInstr>;
173 : using reverse_iterator = MachineInstrBundleIterator<MachineInstr, true>;
174 : using const_reverse_iterator =
175 : MachineInstrBundleIterator<const MachineInstr, true>;
176 :
177 372035 : unsigned size() const { return (unsigned)Insts.size(); }
178 : bool empty() const { return Insts.empty(); }
179 :
180 : MachineInstr &instr_front() { return Insts.front(); }
181 : MachineInstr &instr_back() { return Insts.back(); }
182 : const MachineInstr &instr_front() const { return Insts.front(); }
183 : const MachineInstr &instr_back() const { return Insts.back(); }
184 :
185 : MachineInstr &front() { return Insts.front(); }
186 1109830 : MachineInstr &back() { return *--end(); }
187 : const MachineInstr &front() const { return Insts.front(); }
188 7454689 : const MachineInstr &back() const { return *--end(); }
189 :
190 : instr_iterator instr_begin() { return Insts.begin(); }
191 : const_instr_iterator instr_begin() const { return Insts.begin(); }
192 : instr_iterator instr_end() { return Insts.end(); }
193 : const_instr_iterator instr_end() const { return Insts.end(); }
194 : reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); }
195 : const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
196 : reverse_instr_iterator instr_rend () { return Insts.rend(); }
197 : const_reverse_instr_iterator instr_rend () const { return Insts.rend(); }
198 :
199 : using instr_range = iterator_range<instr_iterator>;
200 : using const_instr_range = iterator_range<const_instr_iterator>;
201 : instr_range instrs() { return instr_range(instr_begin(), instr_end()); }
202 : const_instr_range instrs() const {
203 : return const_instr_range(instr_begin(), instr_end());
204 : }
205 :
206 : iterator begin() { return instr_begin(); }
207 : const_iterator begin() const { return instr_begin(); }
208 : iterator end () { return instr_end(); }
209 : const_iterator end () const { return instr_end(); }
210 : reverse_iterator rbegin() {
211 1388743 : return reverse_iterator::getAtBundleBegin(instr_rbegin());
212 : }
213 : const_reverse_iterator rbegin() const {
214 22441 : return const_reverse_iterator::getAtBundleBegin(instr_rbegin());
215 : }
216 : reverse_iterator rend() { return reverse_iterator(instr_rend()); }
217 : const_reverse_iterator rend() const {
218 : return const_reverse_iterator(instr_rend());
219 : }
220 :
221 : /// Support for MachineInstr::getNextNode().
222 0 : static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) {
223 0 : return &MachineBasicBlock::Insts;
224 : }
225 :
226 : inline iterator_range<iterator> terminators() {
227 4066032 : return make_range(getFirstTerminator(), end());
228 : }
229 : inline iterator_range<const_iterator> terminators() const {
230 : return make_range(getFirstTerminator(), end());
231 : }
232 :
233 : /// Returns a range that iterates over the phis in the basic block.
234 : inline iterator_range<iterator> phis() {
235 213 : return make_range(begin(), getFirstNonPHI());
236 : }
237 : inline iterator_range<const_iterator> phis() const {
238 : return const_cast<MachineBasicBlock *>(this)->phis();
239 : }
240 :
241 : // Machine-CFG iterators
242 : using pred_iterator = std::vector<MachineBasicBlock *>::iterator;
243 : using const_pred_iterator = std::vector<MachineBasicBlock *>::const_iterator;
244 : using succ_iterator = std::vector<MachineBasicBlock *>::iterator;
245 : using const_succ_iterator = std::vector<MachineBasicBlock *>::const_iterator;
246 : using pred_reverse_iterator =
247 : std::vector<MachineBasicBlock *>::reverse_iterator;
248 : using const_pred_reverse_iterator =
249 : std::vector<MachineBasicBlock *>::const_reverse_iterator;
250 : using succ_reverse_iterator =
251 : std::vector<MachineBasicBlock *>::reverse_iterator;
252 : using const_succ_reverse_iterator =
253 : std::vector<MachineBasicBlock *>::const_reverse_iterator;
254 : pred_iterator pred_begin() { return Predecessors.begin(); }
255 16356103 : const_pred_iterator pred_begin() const { return Predecessors.begin(); }
256 : pred_iterator pred_end() { return Predecessors.end(); }
257 16340787 : const_pred_iterator pred_end() const { return Predecessors.end(); }
258 : pred_reverse_iterator pred_rbegin()
259 : { return Predecessors.rbegin();}
260 : const_pred_reverse_iterator pred_rbegin() const
261 : { return Predecessors.rbegin();}
262 : pred_reverse_iterator pred_rend()
263 : { return Predecessors.rend(); }
264 : const_pred_reverse_iterator pred_rend() const
265 : { return Predecessors.rend(); }
266 : unsigned pred_size() const {
267 39005053 : return (unsigned)Predecessors.size();
268 : }
269 : bool pred_empty() const { return Predecessors.empty(); }
270 : succ_iterator succ_begin() { return Successors.begin(); }
271 11055952 : const_succ_iterator succ_begin() const { return Successors.begin(); }
272 : succ_iterator succ_end() { return Successors.end(); }
273 31987894 : const_succ_iterator succ_end() const { return Successors.end(); }
274 : succ_reverse_iterator succ_rbegin()
275 : { return Successors.rbegin(); }
276 : const_succ_reverse_iterator succ_rbegin() const
277 : { return Successors.rbegin(); }
278 : succ_reverse_iterator succ_rend()
279 : { return Successors.rend(); }
280 : const_succ_reverse_iterator succ_rend() const
281 : { return Successors.rend(); }
282 : unsigned succ_size() const {
283 16852728 : return (unsigned)Successors.size();
284 : }
285 : bool succ_empty() const { return Successors.empty(); }
286 :
287 : inline iterator_range<pred_iterator> predecessors() {
288 : return make_range(pred_begin(), pred_end());
289 : }
290 : inline iterator_range<const_pred_iterator> predecessors() const {
291 : return make_range(pred_begin(), pred_end());
292 : }
293 : inline iterator_range<succ_iterator> successors() {
294 : return make_range(succ_begin(), succ_end());
295 : }
296 : inline iterator_range<const_succ_iterator> successors() const {
297 : return make_range(succ_begin(), succ_end());
298 : }
299 :
300 : // LiveIn management methods.
301 :
302 : /// Adds the specified register as a live in. Note that it is an error to add
303 : /// the same register to the same set more than once unless the intention is
304 : /// to call sortUniqueLiveIns after all registers are added.
305 : void addLiveIn(MCPhysReg PhysReg,
306 : LaneBitmask LaneMask = LaneBitmask::getAll()) {
307 2129805 : LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
308 : }
309 : void addLiveIn(const RegisterMaskPair &RegMaskPair) {
310 19665 : LiveIns.push_back(RegMaskPair);
311 : }
312 :
313 : /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
314 : /// this than repeatedly calling isLiveIn before calling addLiveIn for every
315 : /// LiveIn insertion.
316 : void sortUniqueLiveIns();
317 :
318 : /// Clear live in list.
319 : void clearLiveIns();
320 :
321 : /// Add PhysReg as live in to this block, and ensure that there is a copy of
322 : /// PhysReg to a virtual register of class RC. Return the virtual register
323 : /// that is a copy of the live in PhysReg.
324 : unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC);
325 :
326 : /// Remove the specified register from the live in set.
327 : void removeLiveIn(MCPhysReg Reg,
328 : LaneBitmask LaneMask = LaneBitmask::getAll());
329 :
330 : /// Return true if the specified register is in the live in set.
331 : bool isLiveIn(MCPhysReg Reg,
332 : LaneBitmask LaneMask = LaneBitmask::getAll()) const;
333 :
334 : // Iteration support for live in sets. These sets are kept in sorted
335 : // order by their register number.
336 : using livein_iterator = LiveInVector::const_iterator;
337 : #ifndef NDEBUG
338 : /// Unlike livein_begin, this method does not check that the liveness
339 : /// information is accurate. Still for debug purposes it may be useful
340 : /// to have iterators that won't assert if the liveness information
341 : /// is not current.
342 : livein_iterator livein_begin_dbg() const { return LiveIns.begin(); }
343 : iterator_range<livein_iterator> liveins_dbg() const {
344 : return make_range(livein_begin_dbg(), livein_end());
345 : }
346 : #endif
347 : livein_iterator livein_begin() const;
348 9859664 : livein_iterator livein_end() const { return LiveIns.end(); }
349 : bool livein_empty() const { return LiveIns.empty(); }
350 : iterator_range<livein_iterator> liveins() const {
351 8964540 : return make_range(livein_begin(), livein_end());
352 : }
353 :
354 : /// Remove entry from the livein set and return iterator to the next.
355 : livein_iterator removeLiveIn(livein_iterator I);
356 :
357 : /// Get the clobber mask for the start of this basic block. Funclets use this
358 : /// to prevent register allocation across funclet transitions.
359 : const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
360 :
361 : /// Get the clobber mask for the end of the basic block.
362 : /// \see getBeginClobberMask()
363 : const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
364 :
365 : /// Return alignment of the basic block. The alignment is specified as
366 : /// log2(bytes).
367 0 : unsigned getAlignment() const { return Alignment; }
368 :
369 : /// Set alignment of the basic block. The alignment is specified as
370 : /// log2(bytes).
371 10778 : void setAlignment(unsigned Align) { Alignment = Align; }
372 :
373 : /// Returns true if the block is a landing pad. That is this basic block is
374 : /// entered via an exception handler.
375 0 : bool isEHPad() const { return IsEHPad; }
376 :
377 : /// Indicates the block is a landing pad. That is this basic block is entered
378 : /// via an exception handler.
379 842052 : void setIsEHPad(bool V = true) { IsEHPad = V; }
380 :
381 : bool hasEHPadSuccessor() const;
382 :
383 : /// Returns true if this is the entry block of an EH scope, i.e., the block
384 : /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
385 0 : bool isEHScopeEntry() const { return IsEHScopeEntry; }
386 :
387 : /// Indicates if this is the entry block of an EH scope, i.e., the block that
388 : /// that used to have a catchpad or cleanuppad instruction in the LLVM IR.
389 315 : void setIsEHScopeEntry(bool V = true) { IsEHScopeEntry = V; }
390 :
391 : /// Returns true if this is the entry block of an EH funclet.
392 0 : bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
393 :
394 : /// Indicates if this is the entry block of an EH funclet.
395 274 : void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
396 :
397 : /// Returns true if this is the entry block of a cleanup funclet.
398 0 : bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
399 :
400 : /// Indicates if this is the entry block of a cleanup funclet.
401 40 : void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
402 :
403 : /// Returns true if it is legal to hoist instructions into this block.
404 : bool isLegalToHoistInto() const;
405 :
406 : // Code Layout methods.
407 :
408 : /// Move 'this' block before or after the specified block. This only moves
409 : /// the block, it does not modify the CFG or adjust potential fall-throughs at
410 : /// the end of the block.
411 : void moveBefore(MachineBasicBlock *NewAfter);
412 : void moveAfter(MachineBasicBlock *NewBefore);
413 :
414 : /// Update the terminator instructions in block to account for changes to the
415 : /// layout. If the block previously used a fallthrough, it may now need a
416 : /// branch, and if it previously used branching it may now be able to use a
417 : /// fallthrough.
418 : void updateTerminator();
419 :
420 : // Machine-CFG mutators
421 :
422 : /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
423 : /// of Succ is automatically updated. PROB parameter is stored in
424 : /// Probabilities list. The default probability is set as unknown. Mixing
425 : /// known and unknown probabilities in successor list is not allowed. When all
426 : /// successors have unknown probabilities, 1 / N is returned as the
427 : /// probability for each successor, where N is the number of successors.
428 : ///
429 : /// Note that duplicate Machine CFG edges are not allowed.
430 : void addSuccessor(MachineBasicBlock *Succ,
431 : BranchProbability Prob = BranchProbability::getUnknown());
432 :
433 : /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
434 : /// of Succ is automatically updated. The probability is not provided because
435 : /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
436 : /// won't be used. Using this interface can save some space.
437 : void addSuccessorWithoutProb(MachineBasicBlock *Succ);
438 :
439 : /// Set successor probability of a given iterator.
440 : void setSuccProbability(succ_iterator I, BranchProbability Prob);
441 :
442 : /// Normalize probabilities of all successors so that the sum of them becomes
443 : /// one. This is usually done when the current update on this MBB is done, and
444 : /// the sum of its successors' probabilities is not guaranteed to be one. The
445 : /// user is responsible for the correct use of this function.
446 : /// MBB::removeSuccessor() has an option to do this automatically.
447 : void normalizeSuccProbs() {
448 608220 : BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
449 : }
450 :
451 : /// Validate successors' probabilities and check if the sum of them is
452 : /// approximate one. This only works in DEBUG mode.
453 : void validateSuccProbs() const;
454 :
455 : /// Remove successor from the successors list of this MachineBasicBlock. The
456 : /// Predecessors list of Succ is automatically updated.
457 : /// If NormalizeSuccProbs is true, then normalize successors' probabilities
458 : /// after the successor is removed.
459 : void removeSuccessor(MachineBasicBlock *Succ,
460 : bool NormalizeSuccProbs = false);
461 :
462 : /// Remove specified successor from the successors list of this
463 : /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
464 : /// If NormalizeSuccProbs is true, then normalize successors' probabilities
465 : /// after the successor is removed.
466 : /// Return the iterator to the element after the one removed.
467 : succ_iterator removeSuccessor(succ_iterator I,
468 : bool NormalizeSuccProbs = false);
469 :
470 : /// Replace successor OLD with NEW and update probability info.
471 : void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
472 :
473 : /// Copy a successor (and any probability info) from original block to this
474 : /// block's. Uses an iterator into the original blocks successors.
475 : ///
476 : /// This is useful when doing a partial clone of successors. Afterward, the
477 : /// probabilities may need to be normalized.
478 : void copySuccessor(MachineBasicBlock *Orig, succ_iterator I);
479 :
480 : /// Split the old successor into old plus new and updates the probability
481 : /// info.
482 : void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New,
483 : bool NormalizeSuccProbs = false);
484 :
485 : /// Transfers all the successors from MBB to this machine basic block (i.e.,
486 : /// copies all the successors FromMBB and remove all the successors from
487 : /// FromMBB).
488 : void transferSuccessors(MachineBasicBlock *FromMBB);
489 :
490 : /// Transfers all the successors, as in transferSuccessors, and update PHI
491 : /// operands in the successor blocks which refer to FromMBB to refer to this.
492 : void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
493 :
494 : /// Return true if any of the successors have probabilities attached to them.
495 : bool hasSuccessorProbabilities() const { return !Probs.empty(); }
496 :
497 : /// Return true if the specified MBB is a predecessor of this block.
498 : bool isPredecessor(const MachineBasicBlock *MBB) const;
499 :
500 : /// Return true if the specified MBB is a successor of this block.
501 : bool isSuccessor(const MachineBasicBlock *MBB) const;
502 :
503 : /// Return true if the specified MBB will be emitted immediately after this
504 : /// block, such that if this block exits by falling through, control will
505 : /// transfer to the specified MBB. Note that MBB need not be a successor at
506 : /// all, for example if this block ends with an unconditional branch to some
507 : /// other block.
508 : bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
509 :
510 : /// Return the fallthrough block if the block can implicitly
511 : /// transfer control to the block after it by falling off the end of
512 : /// it. This should return null if it can reach the block after
513 : /// it, but it uses an explicit branch to do so (e.g., a table
514 : /// jump). Non-null return is a conservative answer.
515 : MachineBasicBlock *getFallThrough();
516 :
517 : /// Return true if the block can implicitly transfer control to the
518 : /// block after it by falling off the end of it. This should return
519 : /// false if it can reach the block after it, but it uses an
520 : /// explicit branch to do so (e.g., a table jump). True is a
521 : /// conservative answer.
522 : bool canFallThrough();
523 :
524 : /// Returns a pointer to the first instruction in this block that is not a
525 : /// PHINode instruction. When adding instructions to the beginning of the
526 : /// basic block, they should be added before the returned value, not before
527 : /// the first instruction, which might be PHI.
528 : /// Returns end() is there's no non-PHI instruction.
529 : iterator getFirstNonPHI();
530 :
531 : /// Return the first instruction in MBB after I that is not a PHI or a label.
532 : /// This is the correct point to insert lowered copies at the beginning of a
533 : /// basic block that must be before any debugging information.
534 : iterator SkipPHIsAndLabels(iterator I);
535 :
536 : /// Return the first instruction in MBB after I that is not a PHI, label or
537 : /// debug. This is the correct point to insert copies at the beginning of a
538 : /// basic block.
539 : iterator SkipPHIsLabelsAndDebug(iterator I);
540 :
541 : /// Returns an iterator to the first terminator instruction of this basic
542 : /// block. If a terminator does not exist, it returns end().
543 : iterator getFirstTerminator();
544 : const_iterator getFirstTerminator() const {
545 229783 : return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
546 : }
547 :
548 : /// Same getFirstTerminator but it ignores bundles and return an
549 : /// instr_iterator instead.
550 : instr_iterator getFirstInstrTerminator();
551 :
552 : /// Returns an iterator to the first non-debug instruction in the basic block,
553 : /// or end().
554 : iterator getFirstNonDebugInstr();
555 : const_iterator getFirstNonDebugInstr() const {
556 : return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr();
557 : }
558 :
559 : /// Returns an iterator to the last non-debug instruction in the basic block,
560 : /// or end().
561 : iterator getLastNonDebugInstr();
562 : const_iterator getLastNonDebugInstr() const {
563 1103431 : return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr();
564 : }
565 :
566 : /// Convenience function that returns true if the block ends in a return
567 : /// instruction.
568 4584171 : bool isReturnBlock() const {
569 9142577 : return !empty() && back().isReturn();
570 : }
571 :
572 : /// Convenience function that returns true if the bock ends in a EH scope
573 : /// return instruction.
574 1979 : bool isEHScopeReturnBlock() const {
575 3936 : return !empty() && back().isEHScopeReturn();
576 : }
577 :
578 : /// Split the critical edge from this block to the given successor block, and
579 : /// return the newly created block, or null if splitting is not possible.
580 : ///
581 : /// This function updates LiveVariables, MachineDominatorTree, and
582 : /// MachineLoopInfo, as applicable.
583 : MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P);
584 :
585 : /// Check if the edge between this block and the given successor \p
586 : /// Succ, can be split. If this returns true a subsequent call to
587 : /// SplitCriticalEdge is guaranteed to return a valid basic block if
588 : /// no changes occurred in the meantime.
589 : bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
590 :
591 : void pop_front() { Insts.pop_front(); }
592 : void pop_back() { Insts.pop_back(); }
593 2786 : void push_back(MachineInstr *MI) { Insts.push_back(MI); }
594 :
595 : /// Insert MI into the instruction list before I, possibly inside a bundle.
596 : ///
597 : /// If the insertion point is inside a bundle, MI will be added to the bundle,
598 : /// otherwise MI will not be added to any bundle. That means this function
599 : /// alone can't be used to prepend or append instructions to bundles. See
600 : /// MIBundleBuilder::insert() for a more reliable way of doing that.
601 : instr_iterator insert(instr_iterator I, MachineInstr *M);
602 :
603 : /// Insert a range of instructions into the instruction list before I.
604 : template<typename IT>
605 : void insert(iterator I, IT S, IT E) {
606 : assert((I == end() || I->getParent() == this) &&
607 : "iterator points outside of basic block");
608 38448 : Insts.insert(I.getInstrIterator(), S, E);
609 : }
610 :
611 : /// Insert MI into the instruction list before I.
612 : iterator insert(iterator I, MachineInstr *MI) {
613 : assert((I == end() || I->getParent() == this) &&
614 : "iterator points outside of basic block");
615 : assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
616 : "Cannot insert instruction with bundle flags");
617 52493073 : return Insts.insert(I.getInstrIterator(), MI);
618 : }
619 :
620 : /// Insert MI into the instruction list after I.
621 : iterator insertAfter(iterator I, MachineInstr *MI) {
622 : assert((I == end() || I->getParent() == this) &&
623 : "iterator points outside of basic block");
624 : assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
625 : "Cannot insert instruction with bundle flags");
626 2113 : return Insts.insertAfter(I.getInstrIterator(), MI);
627 : }
628 :
629 : /// Remove an instruction from the instruction list and delete it.
630 : ///
631 : /// If the instruction is part of a bundle, the other instructions in the
632 : /// bundle will still be bundled after removing the single instruction.
633 : instr_iterator erase(instr_iterator I);
634 :
635 : /// Remove an instruction from the instruction list and delete it.
636 : ///
637 : /// If the instruction is part of a bundle, the other instructions in the
638 : /// bundle will still be bundled after removing the single instruction.
639 : instr_iterator erase_instr(MachineInstr *I) {
640 621412 : return erase(instr_iterator(I));
641 : }
642 :
643 : /// Remove a range of instructions from the instruction list and delete them.
644 : iterator erase(iterator I, iterator E) {
645 17182745 : return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
646 : }
647 :
648 : /// Remove an instruction or bundle from the instruction list and delete it.
649 : ///
650 : /// If I points to a bundle of instructions, they are all erased.
651 17149104 : iterator erase(iterator I) {
652 17149104 : return erase(I, std::next(I));
653 : }
654 :
655 : /// Remove an instruction from the instruction list and delete it.
656 : ///
657 : /// If I is the head of a bundle of instructions, the whole bundle will be
658 : /// erased.
659 : iterator erase(MachineInstr *I) {
660 12329345 : return erase(iterator(I));
661 : }
662 :
663 : /// Remove the unbundled instruction from the instruction list without
664 : /// deleting it.
665 : ///
666 : /// This function can not be used to remove bundled instructions, use
667 : /// remove_instr to remove individual instructions from a bundle.
668 : MachineInstr *remove(MachineInstr *I) {
669 : assert(!I->isBundled() && "Cannot remove bundled instructions");
670 1736839 : return Insts.remove(instr_iterator(I));
671 : }
672 :
673 : /// Remove the possibly bundled instruction from the instruction list
674 : /// without deleting it.
675 : ///
676 : /// If the instruction is part of a bundle, the other instructions in the
677 : /// bundle will still be bundled after removing the single instruction.
678 : MachineInstr *remove_instr(MachineInstr *I);
679 :
680 : void clear() {
681 146 : Insts.clear();
682 : }
683 :
684 : /// Take an instruction from MBB 'Other' at the position From, and insert it
685 : /// into this MBB right before 'Where'.
686 : ///
687 : /// If From points to a bundle of instructions, the whole bundle is moved.
688 1331269 : void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
689 : // The range splice() doesn't allow noop moves, but this one does.
690 1331269 : if (Where != From)
691 1206685 : splice(Where, Other, From, std::next(From));
692 1331269 : }
693 :
694 : /// Take a block of instructions from MBB 'Other' in the range [From, To),
695 : /// and insert them into this MBB right before 'Where'.
696 : ///
697 : /// The instruction at 'Where' must not be included in the range of
698 : /// instructions to move.
699 : void splice(iterator Where, MachineBasicBlock *Other,
700 : iterator From, iterator To) {
701 2606805 : Insts.splice(Where.getInstrIterator(), Other->Insts,
702 : From.getInstrIterator(), To.getInstrIterator());
703 : }
704 :
705 : /// This method unlinks 'this' from the containing function, and returns it,
706 : /// but does not delete it.
707 : MachineBasicBlock *removeFromParent();
708 :
709 : /// This method unlinks 'this' from the containing function and deletes it.
710 : void eraseFromParent();
711 :
712 : /// Given a machine basic block that branched to 'Old', change the code and
713 : /// CFG so that it branches to 'New' instead.
714 : void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
715 :
716 : /// Various pieces of code can cause excess edges in the CFG to be inserted.
717 : /// If we have proven that MBB can only branch to DestA and DestB, remove any
718 : /// other MBB successors from the CFG. DestA and DestB can be null. Besides
719 : /// DestA and DestB, retain other edges leading to LandingPads (currently
720 : /// there can be only one; we don't check or require that here). Note it is
721 : /// possible that DestA and/or DestB are LandingPads.
722 : bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
723 : MachineBasicBlock *DestB,
724 : bool IsCond);
725 :
726 : /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
727 : /// and DBG_LABEL instructions. Return UnknownLoc if there is none.
728 : DebugLoc findDebugLoc(instr_iterator MBBI);
729 : DebugLoc findDebugLoc(iterator MBBI) {
730 3234482 : return findDebugLoc(MBBI.getInstrIterator());
731 : }
732 :
733 : /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
734 : /// instructions. Return UnknownLoc if there is none.
735 : DebugLoc findPrevDebugLoc(instr_iterator MBBI);
736 : DebugLoc findPrevDebugLoc(iterator MBBI) {
737 3227 : return findPrevDebugLoc(MBBI.getInstrIterator());
738 : }
739 :
740 : /// Find and return the merged DebugLoc of the branch instructions of the
741 : /// block. Return UnknownLoc if there is none.
742 : DebugLoc findBranchDebugLoc();
743 :
744 : /// Possible outcome of a register liveness query to computeRegisterLiveness()
745 : enum LivenessQueryResult {
746 : LQR_Live, ///< Register is known to be (at least partially) live.
747 : LQR_Dead, ///< Register is known to be fully dead.
748 : LQR_Unknown ///< Register liveness not decidable from local neighborhood.
749 : };
750 :
751 : /// Return whether (physical) register \p Reg has been defined and not
752 : /// killed as of just before \p Before.
753 : ///
754 : /// Search is localised to a neighborhood of \p Neighborhood instructions
755 : /// before (searching for defs or kills) and \p Neighborhood instructions
756 : /// after (searching just for defs) \p Before.
757 : ///
758 : /// \p Reg must be a physical register.
759 : LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
760 : unsigned Reg,
761 : const_iterator Before,
762 : unsigned Neighborhood = 10) const;
763 :
764 : // Debugging methods.
765 : void dump() const;
766 : void print(raw_ostream &OS, const SlotIndexes * = nullptr,
767 : bool IsStandalone = true) const;
768 : void print(raw_ostream &OS, ModuleSlotTracker &MST,
769 : const SlotIndexes * = nullptr, bool IsStandalone = true) const;
770 :
771 : // Printing method used by LoopInfo.
772 : void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
773 :
774 : /// MachineBasicBlocks are uniquely numbered at the function level, unless
775 : /// they're not in a MachineFunction yet, in which case this will return -1.
776 0 : int getNumber() const { return Number; }
777 774656 : void setNumber(int N) { Number = N; }
778 :
779 : /// Return the MCSymbol for this basic block.
780 : MCSymbol *getSymbol() const;
781 :
782 : Optional<uint64_t> getIrrLoopHeaderWeight() const {
783 : return IrrLoopHeaderWeight;
784 : }
785 :
786 : void setIrrLoopHeaderWeight(uint64_t Weight) {
787 : IrrLoopHeaderWeight = Weight;
788 : }
789 :
790 : private:
791 : /// Return probability iterator corresponding to the I successor iterator.
792 : probability_iterator getProbabilityIterator(succ_iterator I);
793 : const_probability_iterator
794 : getProbabilityIterator(const_succ_iterator I) const;
795 :
796 : friend class MachineBranchProbabilityInfo;
797 : friend class MIPrinter;
798 :
799 : /// Return probability of the edge from this block to MBB. This method should
800 : /// NOT be called directly, but by using getEdgeProbability method from
801 : /// MachineBranchProbabilityInfo class.
802 : BranchProbability getSuccProbability(const_succ_iterator Succ) const;
803 :
804 : // Methods used to maintain doubly linked list of blocks...
805 : friend struct ilist_callback_traits<MachineBasicBlock>;
806 :
807 : // Machine-CFG mutators
808 :
809 : /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
810 : /// unless you know what you're doing, because it doesn't update Pred's
811 : /// successors list. Use Pred->addSuccessor instead.
812 : void addPredecessor(MachineBasicBlock *Pred);
813 :
814 : /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
815 : /// unless you know what you're doing, because it doesn't update Pred's
816 : /// successors list. Use Pred->removeSuccessor instead.
817 : void removePredecessor(MachineBasicBlock *Pred);
818 : };
819 :
820 : raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
821 :
822 : /// Prints a machine basic block reference.
823 : ///
824 : /// The format is:
825 : /// %bb.5 - a machine basic block with MBB.getNumber() == 5.
826 : ///
827 : /// Usage: OS << printMBBReference(MBB) << '\n';
828 : Printable printMBBReference(const MachineBasicBlock &MBB);
829 :
830 : // This is useful when building IndexedMaps keyed on basic block pointers.
831 : struct MBB2NumberFunctor {
832 : using argument_type = const MachineBasicBlock *;
833 0 : unsigned operator()(const MachineBasicBlock *MBB) const {
834 3992315 : return MBB->getNumber();
835 : }
836 : };
837 :
838 : //===--------------------------------------------------------------------===//
839 : // GraphTraits specializations for machine basic block graphs (machine-CFGs)
840 : //===--------------------------------------------------------------------===//
841 :
842 : // Provide specializations of GraphTraits to be able to treat a
843 : // MachineFunction as a graph of MachineBasicBlocks.
844 : //
845 :
846 : template <> struct GraphTraits<MachineBasicBlock *> {
847 : using NodeRef = MachineBasicBlock *;
848 : using ChildIteratorType = MachineBasicBlock::succ_iterator;
849 :
850 : static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
851 : static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
852 : static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
853 : };
854 :
855 : template <> struct GraphTraits<const MachineBasicBlock *> {
856 : using NodeRef = const MachineBasicBlock *;
857 : using ChildIteratorType = MachineBasicBlock::const_succ_iterator;
858 :
859 : static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
860 : static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
861 : static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
862 : };
863 :
864 : // Provide specializations of GraphTraits to be able to treat a
865 : // MachineFunction as a graph of MachineBasicBlocks and to walk it
866 : // in inverse order. Inverse order for a function is considered
867 : // to be when traversing the predecessor edges of a MBB
868 : // instead of the successor edges.
869 : //
870 : template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
871 : using NodeRef = MachineBasicBlock *;
872 : using ChildIteratorType = MachineBasicBlock::pred_iterator;
873 :
874 : static NodeRef getEntryNode(Inverse<MachineBasicBlock *> G) {
875 : return G.Graph;
876 : }
877 :
878 : static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
879 : static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
880 : };
881 :
882 : template <> struct GraphTraits<Inverse<const MachineBasicBlock*>> {
883 : using NodeRef = const MachineBasicBlock *;
884 : using ChildIteratorType = MachineBasicBlock::const_pred_iterator;
885 :
886 : static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
887 0 : return G.Graph;
888 : }
889 :
890 : static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
891 : static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
892 : };
893 :
894 : /// MachineInstrSpan provides an interface to get an iteration range
895 : /// containing the instruction it was initialized with, along with all
896 : /// those instructions inserted prior to or following that instruction
897 : /// at some point after the MachineInstrSpan is constructed.
898 : class MachineInstrSpan {
899 : MachineBasicBlock &MBB;
900 : MachineBasicBlock::iterator I, B, E;
901 :
902 : public:
903 57831 : MachineInstrSpan(MachineBasicBlock::iterator I)
904 57831 : : MBB(*I->getParent()),
905 : I(I),
906 57831 : B(I == MBB.begin() ? MBB.end() : std::prev(I)),
907 115662 : E(std::next(I)) {}
908 :
909 35730 : MachineBasicBlock::iterator begin() {
910 102668 : return B == MBB.end() ? MBB.begin() : std::next(B);
911 : }
912 0 : MachineBasicBlock::iterator end() { return E; }
913 : bool empty() { return begin() == end(); }
914 :
915 : MachineBasicBlock::iterator getInitial() { return I; }
916 : };
917 :
918 : /// Increment \p It until it points to a non-debug instruction or to \p End
919 : /// and return the resulting iterator. This function should only be used
920 : /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
921 : /// const_instr_iterator} and the respective reverse iterators.
922 : template<typename IterT>
923 8514786 : inline IterT skipDebugInstructionsForward(IterT It, IterT End) {
924 12120526 : while (It != End && It->isDebugInstr())
925 : It++;
926 8514786 : return It;
927 : }
928 :
929 : /// Decrement \p It until it points to a non-debug instruction or to \p Begin
930 : /// and return the resulting iterator. This function should only be used
931 : /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
932 : /// const_instr_iterator} and the respective reverse iterators.
933 : template<class IterT>
934 3509931 : inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin) {
935 3562586 : while (It != Begin && It->isDebugInstr())
936 : It--;
937 3509931 : return It;
938 : }
939 :
940 : } // end namespace llvm
941 :
942 : #endif // LLVM_CODEGEN_MACHINEBASICBLOCK_H
|
