LLVM  7.0.0svn
MachineBasicBlock.h
Go to the documentation of this file.
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"
21 #include "llvm/ADT/simple_ilist.h"
24 #include "llvm/IR/DebugLoc.h"
25 #include "llvm/MC/LaneBitmask.h"
26 #include "llvm/MC/MCRegisterInfo.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 =
57 
58 public:
62  instr_iterator Last);
63  void deleteNode(MachineInstr *MI);
64 };
65 
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.
73  public:
76 
78  : PhysReg(PhysReg), LaneMask(LaneMask) {}
79  };
80 
81 private:
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 funclet.
119  bool IsEHFuncletEntry = false;
120 
121  /// Indicate that this basic block is the entry block of a cleanup funclet.
122  bool IsCleanupFuncletEntry = false;
123 
124  /// \brief since getSymbol is a relatively heavy-weight operation, the symbol
125  /// is only computed once and is cached.
126  mutable MCSymbol *CachedMCSymbol = nullptr;
127 
128  // Intrusive list support
129  MachineBasicBlock() = default;
130 
131  explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB);
132 
134 
135  // MachineBasicBlocks are allocated and owned by MachineFunction.
136  friend class MachineFunction;
137 
138 public:
139  /// Return the LLVM basic block that this instance corresponded to originally.
140  /// Note that this may be NULL if this instance does not correspond directly
141  /// to an LLVM basic block.
142  const BasicBlock *getBasicBlock() const { return BB; }
143 
144  /// Return the name of the corresponding LLVM basic block, or an empty string.
145  StringRef getName() const;
146 
147  /// Return a formatted string to identify this block and its parent function.
148  std::string getFullName() const;
149 
150  /// Test whether this block is potentially the target of an indirect branch.
151  bool hasAddressTaken() const { return AddressTaken; }
152 
153  /// Set this block to reflect that it potentially is the target of an indirect
154  /// branch.
155  void setHasAddressTaken() { AddressTaken = true; }
156 
157  /// Return the MachineFunction containing this basic block.
158  const MachineFunction *getParent() const { return xParent; }
159  MachineFunction *getParent() { return xParent; }
160 
161  using instr_iterator = Instructions::iterator;
162  using const_instr_iterator = Instructions::const_iterator;
165 
169  using const_reverse_iterator =
171 
172  unsigned size() const { return (unsigned)Insts.size(); }
173  bool empty() const { return Insts.empty(); }
174 
175  MachineInstr &instr_front() { return Insts.front(); }
176  MachineInstr &instr_back() { return Insts.back(); }
177  const MachineInstr &instr_front() const { return Insts.front(); }
178  const MachineInstr &instr_back() const { return Insts.back(); }
179 
180  MachineInstr &front() { return Insts.front(); }
181  MachineInstr &back() { return *--end(); }
182  const MachineInstr &front() const { return Insts.front(); }
183  const MachineInstr &back() const { return *--end(); }
184 
185  instr_iterator instr_begin() { return Insts.begin(); }
186  const_instr_iterator instr_begin() const { return Insts.begin(); }
187  instr_iterator instr_end() { return Insts.end(); }
188  const_instr_iterator instr_end() const { return Insts.end(); }
189  reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); }
190  const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
191  reverse_instr_iterator instr_rend () { return Insts.rend(); }
192  const_reverse_instr_iterator instr_rend () const { return Insts.rend(); }
193 
196  instr_range instrs() { return instr_range(instr_begin(), instr_end()); }
198  return const_instr_range(instr_begin(), instr_end());
199  }
200 
201  iterator begin() { return instr_begin(); }
202  const_iterator begin() const { return instr_begin(); }
203  iterator end () { return instr_end(); }
204  const_iterator end () const { return instr_end(); }
206  return reverse_iterator::getAtBundleBegin(instr_rbegin());
207  }
209  return const_reverse_iterator::getAtBundleBegin(instr_rbegin());
210  }
211  reverse_iterator rend() { return reverse_iterator(instr_rend()); }
213  return const_reverse_iterator(instr_rend());
214  }
215 
216  /// Support for MachineInstr::getNextNode().
218  return &MachineBasicBlock::Insts;
219  }
220 
222  return make_range(getFirstTerminator(), end());
223  }
225  return make_range(getFirstTerminator(), end());
226  }
227 
228  /// Returns a range that iterates over the phis in the basic block.
230  return make_range(begin(), getFirstNonPHI());
231  }
233  return const_cast<MachineBasicBlock *>(this)->phis();
234  }
235 
236  // Machine-CFG iterators
237  using pred_iterator = std::vector<MachineBasicBlock *>::iterator;
238  using const_pred_iterator = std::vector<MachineBasicBlock *>::const_iterator;
239  using succ_iterator = std::vector<MachineBasicBlock *>::iterator;
240  using const_succ_iterator = std::vector<MachineBasicBlock *>::const_iterator;
241  using pred_reverse_iterator =
242  std::vector<MachineBasicBlock *>::reverse_iterator;
244  std::vector<MachineBasicBlock *>::const_reverse_iterator;
245  using succ_reverse_iterator =
246  std::vector<MachineBasicBlock *>::reverse_iterator;
248  std::vector<MachineBasicBlock *>::const_reverse_iterator;
249  pred_iterator pred_begin() { return Predecessors.begin(); }
250  const_pred_iterator pred_begin() const { return Predecessors.begin(); }
251  pred_iterator pred_end() { return Predecessors.end(); }
252  const_pred_iterator pred_end() const { return Predecessors.end(); }
254  { return Predecessors.rbegin();}
256  { return Predecessors.rbegin();}
258  { return Predecessors.rend(); }
260  { return Predecessors.rend(); }
261  unsigned pred_size() const {
262  return (unsigned)Predecessors.size();
263  }
264  bool pred_empty() const { return Predecessors.empty(); }
265  succ_iterator succ_begin() { return Successors.begin(); }
266  const_succ_iterator succ_begin() const { return Successors.begin(); }
267  succ_iterator succ_end() { return Successors.end(); }
268  const_succ_iterator succ_end() const { return Successors.end(); }
270  { return Successors.rbegin(); }
272  { return Successors.rbegin(); }
274  { return Successors.rend(); }
276  { return Successors.rend(); }
277  unsigned succ_size() const {
278  return (unsigned)Successors.size();
279  }
280  bool succ_empty() const { return Successors.empty(); }
281 
283  return make_range(pred_begin(), pred_end());
284  }
286  return make_range(pred_begin(), pred_end());
287  }
289  return make_range(succ_begin(), succ_end());
290  }
292  return make_range(succ_begin(), succ_end());
293  }
294 
295  // LiveIn management methods.
296 
297  /// Adds the specified register as a live in. Note that it is an error to add
298  /// the same register to the same set more than once unless the intention is
299  /// to call sortUniqueLiveIns after all registers are added.
300  void addLiveIn(MCPhysReg PhysReg,
301  LaneBitmask LaneMask = LaneBitmask::getAll()) {
302  LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
303  }
304  void addLiveIn(const RegisterMaskPair &RegMaskPair) {
305  LiveIns.push_back(RegMaskPair);
306  }
307 
308  /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
309  /// this than repeatedly calling isLiveIn before calling addLiveIn for every
310  /// LiveIn insertion.
311  void sortUniqueLiveIns();
312 
313  /// Clear live in list.
314  void clearLiveIns();
315 
316  /// Add PhysReg as live in to this block, and ensure that there is a copy of
317  /// PhysReg to a virtual register of class RC. Return the virtual register
318  /// that is a copy of the live in PhysReg.
319  unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC);
320 
321  /// Remove the specified register from the live in set.
322  void removeLiveIn(MCPhysReg Reg,
323  LaneBitmask LaneMask = LaneBitmask::getAll());
324 
325  /// Return true if the specified register is in the live in set.
326  bool isLiveIn(MCPhysReg Reg,
327  LaneBitmask LaneMask = LaneBitmask::getAll()) const;
328 
329  // Iteration support for live in sets. These sets are kept in sorted
330  // order by their register number.
331  using livein_iterator = LiveInVector::const_iterator;
332 #ifndef NDEBUG
333  /// Unlike livein_begin, this method does not check that the liveness
334  /// information is accurate. Still for debug purposes it may be useful
335  /// to have iterators that won't assert if the liveness information
336  /// is not current.
337  livein_iterator livein_begin_dbg() const { return LiveIns.begin(); }
339  return make_range(livein_begin_dbg(), livein_end());
340  }
341 #endif
342  livein_iterator livein_begin() const;
343  livein_iterator livein_end() const { return LiveIns.end(); }
344  bool livein_empty() const { return LiveIns.empty(); }
346  return make_range(livein_begin(), livein_end());
347  }
348 
349  /// Remove entry from the livein set and return iterator to the next.
350  livein_iterator removeLiveIn(livein_iterator I);
351 
352  /// Get the clobber mask for the start of this basic block. Funclets use this
353  /// to prevent register allocation across funclet transitions.
354  const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
355 
356  /// Get the clobber mask for the end of the basic block.
357  /// \see getBeginClobberMask()
358  const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
359 
360  /// Return alignment of the basic block. The alignment is specified as
361  /// log2(bytes).
362  unsigned getAlignment() const { return Alignment; }
363 
364  /// Set alignment of the basic block. The alignment is specified as
365  /// log2(bytes).
366  void setAlignment(unsigned Align) { Alignment = Align; }
367 
368  /// Returns true if the block is a landing pad. That is this basic block is
369  /// entered via an exception handler.
370  bool isEHPad() const { return IsEHPad; }
371 
372  /// Indicates the block is a landing pad. That is this basic block is entered
373  /// via an exception handler.
374  void setIsEHPad(bool V = true) { IsEHPad = V; }
375 
376  bool hasEHPadSuccessor() const;
377 
378  /// Returns true if this is the entry block of an EH funclet.
379  bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
380 
381  /// Indicates if this is the entry block of an EH funclet.
382  void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
383 
384  /// Returns true if this is the entry block of a cleanup funclet.
385  bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
386 
387  /// Indicates if this is the entry block of a cleanup funclet.
388  void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
389 
390  /// Returns true if it is legal to hoist instructions into this block.
391  bool isLegalToHoistInto() const;
392 
393  // Code Layout methods.
394 
395  /// Move 'this' block before or after the specified block. This only moves
396  /// the block, it does not modify the CFG or adjust potential fall-throughs at
397  /// the end of the block.
398  void moveBefore(MachineBasicBlock *NewAfter);
399  void moveAfter(MachineBasicBlock *NewBefore);
400 
401  /// Update the terminator instructions in block to account for changes to the
402  /// layout. If the block previously used a fallthrough, it may now need a
403  /// branch, and if it previously used branching it may now be able to use a
404  /// fallthrough.
405  void updateTerminator();
406 
407  // Machine-CFG mutators
408 
409  /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
410  /// of Succ is automatically updated. PROB parameter is stored in
411  /// Probabilities list. The default probability is set as unknown. Mixing
412  /// known and unknown probabilities in successor list is not allowed. When all
413  /// successors have unknown probabilities, 1 / N is returned as the
414  /// probability for each successor, where N is the number of successors.
415  ///
416  /// Note that duplicate Machine CFG edges are not allowed.
417  void addSuccessor(MachineBasicBlock *Succ,
419 
420  /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list
421  /// of Succ is automatically updated. The probability is not provided because
422  /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
423  /// won't be used. Using this interface can save some space.
424  void addSuccessorWithoutProb(MachineBasicBlock *Succ);
425 
426  /// Set successor probability of a given iterator.
427  void setSuccProbability(succ_iterator I, BranchProbability Prob);
428 
429  /// Normalize probabilities of all successors so that the sum of them becomes
430  /// one. This is usually done when the current update on this MBB is done, and
431  /// the sum of its successors' probabilities is not guaranteed to be one. The
432  /// user is responsible for the correct use of this function.
433  /// MBB::removeSuccessor() has an option to do this automatically.
435  BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
436  }
437 
438  /// Validate successors' probabilities and check if the sum of them is
439  /// approximate one. This only works in DEBUG mode.
440  void validateSuccProbs() const;
441 
442  /// Remove successor from the successors list of this MachineBasicBlock. The
443  /// Predecessors list of Succ is automatically updated.
444  /// If NormalizeSuccProbs is true, then normalize successors' probabilities
445  /// after the successor is removed.
446  void removeSuccessor(MachineBasicBlock *Succ,
447  bool NormalizeSuccProbs = false);
448 
449  /// Remove specified successor from the successors list of this
450  /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
451  /// If NormalizeSuccProbs is true, then normalize successors' probabilities
452  /// after the successor is removed.
453  /// Return the iterator to the element after the one removed.
454  succ_iterator removeSuccessor(succ_iterator I,
455  bool NormalizeSuccProbs = false);
456 
457  /// Replace successor OLD with NEW and update probability info.
458  void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
459 
460  /// Copy a successor (and any probability info) from original block to this
461  /// block's. Uses an iterator into the original blocks successors.
462  ///
463  /// This is useful when doing a partial clone of successors. Afterward, the
464  /// probabilities may need to be normalized.
465  void copySuccessor(MachineBasicBlock *Orig, succ_iterator I);
466 
467  /// Transfers all the successors from MBB to this machine basic block (i.e.,
468  /// copies all the successors FromMBB and remove all the successors from
469  /// FromMBB).
470  void transferSuccessors(MachineBasicBlock *FromMBB);
471 
472  /// Transfers all the successors, as in transferSuccessors, and update PHI
473  /// operands in the successor blocks which refer to FromMBB to refer to this.
474  void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
475 
476  /// Return true if any of the successors have probabilities attached to them.
477  bool hasSuccessorProbabilities() const { return !Probs.empty(); }
478 
479  /// Return true if the specified MBB is a predecessor of this block.
480  bool isPredecessor(const MachineBasicBlock *MBB) const;
481 
482  /// Return true if the specified MBB is a successor of this block.
483  bool isSuccessor(const MachineBasicBlock *MBB) const;
484 
485  /// Return true if the specified MBB will be emitted immediately after this
486  /// block, such that if this block exits by falling through, control will
487  /// transfer to the specified MBB. Note that MBB need not be a successor at
488  /// all, for example if this block ends with an unconditional branch to some
489  /// other block.
490  bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
491 
492  /// Return the fallthrough block if the block can implicitly
493  /// transfer control to the block after it by falling off the end of
494  /// it. This should return null if it can reach the block after
495  /// it, but it uses an explicit branch to do so (e.g., a table
496  /// jump). Non-null return is a conservative answer.
497  MachineBasicBlock *getFallThrough();
498 
499  /// Return true if the block can implicitly transfer control to the
500  /// block after it by falling off the end of it. This should return
501  /// false if it can reach the block after it, but it uses an
502  /// explicit branch to do so (e.g., a table jump). True is a
503  /// conservative answer.
504  bool canFallThrough();
505 
506  /// Returns a pointer to the first instruction in this block that is not a
507  /// PHINode instruction. When adding instructions to the beginning of the
508  /// basic block, they should be added before the returned value, not before
509  /// the first instruction, which might be PHI.
510  /// Returns end() is there's no non-PHI instruction.
511  iterator getFirstNonPHI();
512 
513  /// Return the first instruction in MBB after I that is not a PHI or a label.
514  /// This is the correct point to insert lowered copies at the beginning of a
515  /// basic block that must be before any debugging information.
516  iterator SkipPHIsAndLabels(iterator I);
517 
518  /// Return the first instruction in MBB after I that is not a PHI, label or
519  /// debug. This is the correct point to insert copies at the beginning of a
520  /// basic block.
521  iterator SkipPHIsLabelsAndDebug(iterator I);
522 
523  /// Returns an iterator to the first terminator instruction of this basic
524  /// block. If a terminator does not exist, it returns end().
525  iterator getFirstTerminator();
527  return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
528  }
529 
530  /// Same getFirstTerminator but it ignores bundles and return an
531  /// instr_iterator instead.
532  instr_iterator getFirstInstrTerminator();
533 
534  /// Returns an iterator to the first non-debug instruction in the basic block,
535  /// or end().
536  iterator getFirstNonDebugInstr();
538  return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr();
539  }
540 
541  /// Returns an iterator to the last non-debug instruction in the basic block,
542  /// or end().
543  iterator getLastNonDebugInstr();
545  return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr();
546  }
547 
548  /// Convenience function that returns true if the block ends in a return
549  /// instruction.
550  bool isReturnBlock() const {
551  return !empty() && back().isReturn();
552  }
553 
554  /// Split the critical edge from this block to the given successor block, and
555  /// return the newly created block, or null if splitting is not possible.
556  ///
557  /// This function updates LiveVariables, MachineDominatorTree, and
558  /// MachineLoopInfo, as applicable.
560 
561  /// Check if the edge between this block and the given successor \p
562  /// Succ, can be split. If this returns true a subsequent call to
563  /// SplitCriticalEdge is guaranteed to return a valid basic block if
564  /// no changes occurred in the meantime.
565  bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
566 
567  void pop_front() { Insts.pop_front(); }
568  void pop_back() { Insts.pop_back(); }
569  void push_back(MachineInstr *MI) { Insts.push_back(MI); }
570 
571  /// Insert MI into the instruction list before I, possibly inside a bundle.
572  ///
573  /// If the insertion point is inside a bundle, MI will be added to the bundle,
574  /// otherwise MI will not be added to any bundle. That means this function
575  /// alone can't be used to prepend or append instructions to bundles. See
576  /// MIBundleBuilder::insert() for a more reliable way of doing that.
578 
579  /// Insert a range of instructions into the instruction list before I.
580  template<typename IT>
581  void insert(iterator I, IT S, IT E) {
582  assert((I == end() || I->getParent() == this) &&
583  "iterator points outside of basic block");
584  Insts.insert(I.getInstrIterator(), S, E);
585  }
586 
587  /// Insert MI into the instruction list before I.
589  assert((I == end() || I->getParent() == this) &&
590  "iterator points outside of basic block");
591  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
592  "Cannot insert instruction with bundle flags");
593  return Insts.insert(I.getInstrIterator(), MI);
594  }
595 
596  /// Insert MI into the instruction list after I.
598  assert((I == end() || I->getParent() == this) &&
599  "iterator points outside of basic block");
600  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
601  "Cannot insert instruction with bundle flags");
602  return Insts.insertAfter(I.getInstrIterator(), MI);
603  }
604 
605  /// Remove an instruction from the instruction list and delete it.
606  ///
607  /// If the instruction is part of a bundle, the other instructions in the
608  /// bundle will still be bundled after removing the single instruction.
610 
611  /// Remove an instruction from the instruction list and delete it.
612  ///
613  /// If the instruction is part of a bundle, the other instructions in the
614  /// bundle will still be bundled after removing the single instruction.
616  return erase(instr_iterator(I));
617  }
618 
619  /// Remove a range of instructions from the instruction list and delete them.
621  return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
622  }
623 
624  /// Remove an instruction or bundle from the instruction list and delete it.
625  ///
626  /// If I points to a bundle of instructions, they are all erased.
628  return erase(I, std::next(I));
629  }
630 
631  /// Remove an instruction from the instruction list and delete it.
632  ///
633  /// If I is the head of a bundle of instructions, the whole bundle will be
634  /// erased.
636  return erase(iterator(I));
637  }
638 
639  /// Remove the unbundled instruction from the instruction list without
640  /// deleting it.
641  ///
642  /// This function can not be used to remove bundled instructions, use
643  /// remove_instr to remove individual instructions from a bundle.
645  assert(!I->isBundled() && "Cannot remove bundled instructions");
646  return Insts.remove(instr_iterator(I));
647  }
648 
649  /// Remove the possibly bundled instruction from the instruction list
650  /// without deleting it.
651  ///
652  /// If the instruction is part of a bundle, the other instructions in the
653  /// bundle will still be bundled after removing the single instruction.
654  MachineInstr *remove_instr(MachineInstr *I);
655 
656  void clear() {
657  Insts.clear();
658  }
659 
660  /// Take an instruction from MBB 'Other' at the position From, and insert it
661  /// into this MBB right before 'Where'.
662  ///
663  /// If From points to a bundle of instructions, the whole bundle is moved.
665  // The range splice() doesn't allow noop moves, but this one does.
666  if (Where != From)
667  splice(Where, Other, From, std::next(From));
668  }
669 
670  /// Take a block of instructions from MBB 'Other' in the range [From, To),
671  /// and insert them into this MBB right before 'Where'.
672  ///
673  /// The instruction at 'Where' must not be included in the range of
674  /// instructions to move.
676  iterator From, iterator To) {
677  Insts.splice(Where.getInstrIterator(), Other->Insts,
678  From.getInstrIterator(), To.getInstrIterator());
679  }
680 
681  /// This method unlinks 'this' from the containing function, and returns it,
682  /// but does not delete it.
683  MachineBasicBlock *removeFromParent();
684 
685  /// This method unlinks 'this' from the containing function and deletes it.
686  void eraseFromParent();
687 
688  /// Given a machine basic block that branched to 'Old', change the code and
689  /// CFG so that it branches to 'New' instead.
690  void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
691 
692  /// Various pieces of code can cause excess edges in the CFG to be inserted.
693  /// If we have proven that MBB can only branch to DestA and DestB, remove any
694  /// other MBB successors from the CFG. DestA and DestB can be null. Besides
695  /// DestA and DestB, retain other edges leading to LandingPads (currently
696  /// there can be only one; we don't check or require that here). Note it is
697  /// possible that DestA and/or DestB are LandingPads.
698  bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
699  MachineBasicBlock *DestB,
700  bool IsCond);
701 
702  /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
703  /// instructions. Return UnknownLoc if there is none.
704  DebugLoc findDebugLoc(instr_iterator MBBI);
706  return findDebugLoc(MBBI.getInstrIterator());
707  }
708 
709  /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
710  /// instructions. Return UnknownLoc if there is none.
711  DebugLoc findPrevDebugLoc(instr_iterator MBBI);
713  return findPrevDebugLoc(MBBI.getInstrIterator());
714  }
715 
716  /// Find and return the merged DebugLoc of the branch instructions of the
717  /// block. Return UnknownLoc if there is none.
718  DebugLoc findBranchDebugLoc();
719 
720  /// Possible outcome of a register liveness query to computeRegisterLiveness()
722  LQR_Live, ///< Register is known to be (at least partially) live.
723  LQR_Dead, ///< Register is known to be fully dead.
724  LQR_Unknown ///< Register liveness not decidable from local neighborhood.
725  };
726 
727  /// Return whether (physical) register \p Reg has been defined and not
728  /// killed as of just before \p Before.
729  ///
730  /// Search is localised to a neighborhood of \p Neighborhood instructions
731  /// before (searching for defs or kills) and \p Neighborhood instructions
732  /// after (searching just for defs) \p Before.
733  ///
734  /// \p Reg must be a physical register.
735  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
736  unsigned Reg,
737  const_iterator Before,
738  unsigned Neighborhood = 10) const;
739 
740  // Debugging methods.
741  void dump() const;
742  void print(raw_ostream &OS, const SlotIndexes * = nullptr,
743  bool IsStandalone = true) const;
744  void print(raw_ostream &OS, ModuleSlotTracker &MST,
745  const SlotIndexes * = nullptr, bool IsStandalone = true) const;
746 
747  // Printing method used by LoopInfo.
748  void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
749 
750  /// MachineBasicBlocks are uniquely numbered at the function level, unless
751  /// they're not in a MachineFunction yet, in which case this will return -1.
752  int getNumber() const { return Number; }
753  void setNumber(int N) { Number = N; }
754 
755  /// Return the MCSymbol for this basic block.
756  MCSymbol *getSymbol() const;
757 
759  return IrrLoopHeaderWeight;
760  }
761 
762  void setIrrLoopHeaderWeight(uint64_t Weight) {
763  IrrLoopHeaderWeight = Weight;
764  }
765 
766 private:
767  /// Return probability iterator corresponding to the I successor iterator.
768  probability_iterator getProbabilityIterator(succ_iterator I);
769  const_probability_iterator
770  getProbabilityIterator(const_succ_iterator I) const;
771 
773  friend class MIPrinter;
774 
775  /// Return probability of the edge from this block to MBB. This method should
776  /// NOT be called directly, but by using getEdgeProbability method from
777  /// MachineBranchProbabilityInfo class.
778  BranchProbability getSuccProbability(const_succ_iterator Succ) const;
779 
780  // Methods used to maintain doubly linked list of blocks...
782 
783  // Machine-CFG mutators
784 
785  /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
786  /// unless you know what you're doing, because it doesn't update Pred's
787  /// successors list. Use Pred->addSuccessor instead.
788  void addPredecessor(MachineBasicBlock *Pred);
789 
790  /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
791  /// unless you know what you're doing, because it doesn't update Pred's
792  /// successors list. Use Pred->removeSuccessor instead.
793  void removePredecessor(MachineBasicBlock *Pred);
794 };
795 
797 
798 /// Prints a machine basic block reference.
799 ///
800 /// The format is:
801 /// %bb.5 - a machine basic block with MBB.getNumber() == 5.
802 ///
803 /// Usage: OS << printMBBReference(MBB) << '\n';
805 
806 // This is useful when building IndexedMaps keyed on basic block pointers.
809  unsigned operator()(const MachineBasicBlock *MBB) const {
810  return MBB->getNumber();
811  }
812 };
813 
814 //===--------------------------------------------------------------------===//
815 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
816 //===--------------------------------------------------------------------===//
817 
818 // Provide specializations of GraphTraits to be able to treat a
819 // MachineFunction as a graph of MachineBasicBlocks.
820 //
821 
822 template <> struct GraphTraits<MachineBasicBlock *> {
825 
826  static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
828  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
829 };
830 
831 template <> struct GraphTraits<const MachineBasicBlock *> {
832  using NodeRef = const MachineBasicBlock *;
834 
835  static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
837  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
838 };
839 
840 // Provide specializations of GraphTraits to be able to treat a
841 // MachineFunction as a graph of MachineBasicBlocks and to walk it
842 // in inverse order. Inverse order for a function is considered
843 // to be when traversing the predecessor edges of a MBB
844 // instead of the successor edges.
845 //
846 template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
849 
851  return G.Graph;
852  }
853 
855  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
856 };
857 
859  using NodeRef = const MachineBasicBlock *;
861 
863  return G.Graph;
864  }
865 
867  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
868 };
869 
870 /// MachineInstrSpan provides an interface to get an iteration range
871 /// containing the instruction it was initialized with, along with all
872 /// those instructions inserted prior to or following that instruction
873 /// at some point after the MachineInstrSpan is constructed.
875  MachineBasicBlock &MBB;
877 
878 public:
880  : MBB(*I->getParent()),
881  I(I),
882  B(I == MBB.begin() ? MBB.end() : std::prev(I)),
883  E(std::next(I)) {}
884 
886  return B == MBB.end() ? MBB.begin() : std::next(B);
887  }
889  bool empty() { return begin() == end(); }
890 
892 };
893 
894 /// Increment \p It until it points to a non-debug instruction or to \p End
895 /// and return the resulting iterator. This function should only be used
896 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
897 /// const_instr_iterator} and the respective reverse iterators.
898 template<typename IterT>
899 inline IterT skipDebugInstructionsForward(IterT It, IterT End) {
900  while (It != End && It->isDebugValue())
901  It++;
902  return It;
903 }
904 
905 /// Decrement \p It until it points to a non-debug instruction or to \p Begin
906 /// and return the resulting iterator. This function should only be used
907 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
908 /// const_instr_iterator} and the respective reverse iterators.
909 template<class IterT>
910 inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin) {
911  while (It != Begin && It->isDebugValue())
912  It--;
913  return It;
914 }
915 
916 } // end namespace llvm
917 
918 #endif // LLVM_CODEGEN_MACHINEBASICBLOCK_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
pred_reverse_iterator pred_rbegin()
const_iterator getLastNonDebugInstr() const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
bool hasSuccessorProbabilities() const
Return true if any of the successors have probabilities attached to them.
A common definition of LaneBitmask for use in TableGen and CodeGen.
pred_reverse_iterator pred_rend()
instr_iterator instr_begin()
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:236
instr_iterator instr_end()
iterator erase(iterator where)
Definition: ilist.h:267
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
void addNodeToList(NodeTy *)
When an MBB is added to an MF, we need to update the parent pointer of the MBB, the MBB numbering...
Definition: ilist.h:66
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
const_pred_reverse_iterator pred_rbegin() const
RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
void setIsEHPad(bool V=true)
Indicates the block is a landing pad.
MachineInstr & instr_front()
const_succ_iterator succ_begin() const
bool isBundledWithPred() const
Return true if this instruction is part of a bundle, and it is not the first instruction in the bundl...
Definition: MachineInstr.h:250
static ChildIteratorType child_begin(NodeRef N)
const_succ_reverse_iterator succ_rbegin() const
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
bool isCleanupFuncletEntry() const
Returns true if this is the entry block of a cleanup funclet.
void setIrrLoopHeaderWeight(uint64_t Weight)
MachineBasicBlock::succ_iterator ChildIteratorType
const_reverse_instr_iterator instr_rbegin() const
MachineInstr & instr_back()
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
iterator insertAfter(iterator I, MachineInstr *MI)
Insert MI into the instruction list after I.
Template traits for intrusive list.
Definition: ilist.h:91
const_pred_iterator pred_end() const
DebugLoc findDebugLoc(iterator MBBI)
A debug info location.
Definition: DebugLoc.h:34
Manage lifetime of a slot tracker for printing IR.
std::vector< MachineBasicBlock * >::const_iterator const_pred_iterator
MachineInstrSpan(MachineBasicBlock::iterator I)
iterator insert(iterator I, MachineInstr *MI)
Insert MI into the instruction list before I.
void setAlignment(unsigned Align)
Set alignment of the basic block.
static ChildIteratorType child_begin(NodeRef N)
iterator_range< succ_iterator > successors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From, iterator To)
Take a block of instructions from MBB &#39;Other&#39; in the range [From, To), and insert them into this MBB ...
const MachineInstr & back() const
MachineInstrSpan provides an interface to get an iteration range containing the instruction it was in...
Definition: BitVector.h:921
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
MachineBasicBlock::pred_iterator ChildIteratorType
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
static unsigned addLiveIn(MachineFunction &MF, unsigned PReg, const TargetRegisterClass *RC)
bool isBundledWithSucc() const
Return true if this instruction is part of a bundle, and it is not the last instruction in the bundle...
Definition: MachineInstr.h:254
iterator erase(MachineInstr *I)
Remove an instruction from the instruction list and delete it.
void insert(iterator I, IT S, IT E)
Insert a range of instructions into the instruction list before I.
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
Reg
All possible values of the reg field in the ModR/M byte.
static StringRef getName(Value *V)
iterator_range< iterator > terminators()
LiveInVector::const_iterator livein_iterator
void setIsCleanupFuncletEntry(bool V=true)
Indicates if this is the entry block of a cleanup funclet.
MachineBasicBlock::iterator end()
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:767
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
A simple intrusive list implementation.
Definition: simple_ilist.h:79
static ChildIteratorType child_end(NodeRef N)
SlotIndexes pass.
Definition: SlotIndexes.h:331
const_pred_reverse_iterator pred_rend() const
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
const_succ_reverse_iterator succ_rend() const
static Instructions MachineBasicBlock::* getSublistAccess(MachineInstr *)
Support for MachineInstr::getNextNode().
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
succ_reverse_iterator succ_rend()
reverse_iterator rend()
Expected< const typename ELFT::Sym * > getSymbol(typename ELFT::SymRange Symbols, uint32_t Index)
Definition: ELF.h:319
reverse_iterator rbegin()
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
unsigned operator()(const MachineBasicBlock *MBB) const
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
#define P(N)
std::vector< MachineBasicBlock * >::const_reverse_iterator const_succ_reverse_iterator
An ilist node that can access its parent list.
Definition: ilist_node.h:257
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
instr_iterator erase_instr(MachineInstr *I)
Remove an instruction from the instruction list and delete it.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
const_reverse_iterator rbegin() const
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static ChildIteratorType child_end(NodeRef N)
succ_reverse_iterator succ_rbegin()
static ChildIteratorType child_begin(NodeRef N)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
livein_iterator livein_end() const
unsigned getAlignment() const
Return alignment of the basic block.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Register is known to be fully dead.
void pop_front()
Definition: ilist.h:314
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:329
static const unsigned End
This class prints out the machine instructions using the MIR serialization format.
Definition: MIRPrinter.cpp:138
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
MachineBasicBlock::const_succ_iterator ChildIteratorType
iterator_range< pred_iterator > predecessors()
std::vector< MachineBasicBlock * >::iterator pred_iterator
LivenessQueryResult
Possible outcome of a register liveness query to computeRegisterLiveness()
Register is known to be (at least partially) live.
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
iterator erase(iterator I)
Remove an instruction or bundle from the instruction list and delete it.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
iterator erase(iterator I, iterator E)
Remove a range of instructions from the instruction list and delete them.
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
const_iterator begin() const
static BranchProbability getUnknown()
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
print lazy value Lazy Value Info Printer Pass
const MachineInstr & instr_back() const
Iterator for intrusive lists based on ilist_node.
const GraphType & Graph
Definition: GraphTraits.h:90
reverse_instr_iterator instr_rbegin()
iterator_range< const_iterator > phis() const
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
livein_iterator livein_begin_dbg() const
Unlike livein_begin, this method does not check that the liveness information is accurate.
const_instr_iterator instr_end() const
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
iterator_range< livein_iterator > liveins_dbg() const
MachineBasicBlock::iterator getInitial()
void addLiveIn(const RegisterMaskPair &RegMaskPair)
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
unsigned pred_size() const
IterT skipDebugInstructionsBackward(IterT It, IterT Begin)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
reverse_instr_iterator instr_rend()
const_iterator getFirstTerminator() const
MachineBasicBlock::const_pred_iterator ChildIteratorType
A range adaptor for a pair of iterators.
static NodeRef getEntryNode(Inverse< MachineBasicBlock *> G)
void push_back(pointer val)
Definition: ilist.h:313
DebugLoc findPrevDebugLoc(iterator MBBI)
const MachineInstr & front() const
void setHasAddressTaken()
Set this block to reflect that it potentially is the target of an indirect branch.
std::vector< MachineBasicBlock * >::const_reverse_iterator const_pred_reverse_iterator
MachineFunction * getParent()
unsigned succ_size() const
IterT skipDebugInstructionsForward(IterT It, IterT End)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator...
iterator_range< const_succ_iterator > successors() const
void setIsEHFuncletEntry(bool V=true)
Indicates if this is the entry block of an EH funclet.
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
iterator_range< const_pred_iterator > predecessors() const
Representation of each machine instruction.
Definition: MachineInstr.h:60
pointer remove(iterator &IT)
Definition: ilist.h:251
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
void clear()
Definition: ilist.h:309
std::vector< MachineBasicBlock * >::reverse_iterator pred_reverse_iterator
bool isEHPad() const
Returns true if the block is a landing pad.
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
static NodeRef getEntryNode(const MachineBasicBlock *BB)
static NodeRef getEntryNode(Inverse< const MachineBasicBlock *> G)
void push_back(MachineInstr *MI)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Pair of physical register and lane mask.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
const_instr_iterator instr_begin() const
const_iterator end() const
const_succ_iterator succ_end() const
std::vector< MachineBasicBlock * >::reverse_iterator succ_reverse_iterator
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
iterator_range< livein_iterator > liveins() const
Instructions::iterator instr_iterator
const_iterator getFirstNonDebugInstr() const
iterator_range< const_iterator > terminators() const
Optional< uint64_t > getIrrLoopHeaderWeight() const
const_reverse_instr_iterator instr_rend() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static ChildIteratorType child_end(NodeRef N)
aarch64 promote const
const_instr_range instrs() const
static const Function * getParent(const Value *V)
const_pred_iterator pred_begin() const
Callbacks do nothing by default in iplist and ilist.
Definition: ilist.h:65
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
void pop_back()
Definition: ilist.h:318
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:237
Instructions::const_iterator const_instr_iterator
const_reverse_iterator rend() const
std::vector< MachineBasicBlock * >::iterator succ_iterator
const MachineInstr & instr_front() const
static NodeRef getEntryNode(MachineBasicBlock *BB)
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:73
MachineBasicBlock::iterator begin()