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  /// Transfers all the successors from MBB to this machine basic block (i.e.,
461  /// copies all the successors FromMBB and remove all the successors from
462  /// FromMBB).
463  void transferSuccessors(MachineBasicBlock *FromMBB);
464 
465  /// Transfers all the successors, as in transferSuccessors, and update PHI
466  /// operands in the successor blocks which refer to FromMBB to refer to this.
467  void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
468 
469  /// Return true if any of the successors have probabilities attached to them.
470  bool hasSuccessorProbabilities() const { return !Probs.empty(); }
471 
472  /// Return true if the specified MBB is a predecessor of this block.
473  bool isPredecessor(const MachineBasicBlock *MBB) const;
474 
475  /// Return true if the specified MBB is a successor of this block.
476  bool isSuccessor(const MachineBasicBlock *MBB) const;
477 
478  /// Return true if the specified MBB will be emitted immediately after this
479  /// block, such that if this block exits by falling through, control will
480  /// transfer to the specified MBB. Note that MBB need not be a successor at
481  /// all, for example if this block ends with an unconditional branch to some
482  /// other block.
483  bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
484 
485  /// Return the fallthrough block if the block can implicitly
486  /// transfer control to the block after it by falling off the end of
487  /// it. This should return null if it can reach the block after
488  /// it, but it uses an explicit branch to do so (e.g., a table
489  /// jump). Non-null return is a conservative answer.
490  MachineBasicBlock *getFallThrough();
491 
492  /// Return true if the block can implicitly transfer control to the
493  /// block after it by falling off the end of it. This should return
494  /// false if it can reach the block after it, but it uses an
495  /// explicit branch to do so (e.g., a table jump). True is a
496  /// conservative answer.
497  bool canFallThrough();
498 
499  /// Returns a pointer to the first instruction in this block that is not a
500  /// PHINode instruction. When adding instructions to the beginning of the
501  /// basic block, they should be added before the returned value, not before
502  /// the first instruction, which might be PHI.
503  /// Returns end() is there's no non-PHI instruction.
504  iterator getFirstNonPHI();
505 
506  /// Return the first instruction in MBB after I that is not a PHI or a label.
507  /// This is the correct point to insert lowered copies at the beginning of a
508  /// basic block that must be before any debugging information.
509  iterator SkipPHIsAndLabels(iterator I);
510 
511  /// Return the first instruction in MBB after I that is not a PHI, label or
512  /// debug. This is the correct point to insert copies at the beginning of a
513  /// basic block.
514  iterator SkipPHIsLabelsAndDebug(iterator I);
515 
516  /// Returns an iterator to the first terminator instruction of this basic
517  /// block. If a terminator does not exist, it returns end().
518  iterator getFirstTerminator();
520  return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
521  }
522 
523  /// Same getFirstTerminator but it ignores bundles and return an
524  /// instr_iterator instead.
525  instr_iterator getFirstInstrTerminator();
526 
527  /// Returns an iterator to the first non-debug instruction in the basic block,
528  /// or end().
529  iterator getFirstNonDebugInstr();
531  return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr();
532  }
533 
534  /// Returns an iterator to the last non-debug instruction in the basic block,
535  /// or end().
536  iterator getLastNonDebugInstr();
538  return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr();
539  }
540 
541  /// Convenience function that returns true if the block ends in a return
542  /// instruction.
543  bool isReturnBlock() const {
544  return !empty() && back().isReturn();
545  }
546 
547  /// Split the critical edge from this block to the given successor block, and
548  /// return the newly created block, or null if splitting is not possible.
549  ///
550  /// This function updates LiveVariables, MachineDominatorTree, and
551  /// MachineLoopInfo, as applicable.
553 
554  /// Check if the edge between this block and the given successor \p
555  /// Succ, can be split. If this returns true a subsequent call to
556  /// SplitCriticalEdge is guaranteed to return a valid basic block if
557  /// no changes occurred in the meantime.
558  bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
559 
560  void pop_front() { Insts.pop_front(); }
561  void pop_back() { Insts.pop_back(); }
562  void push_back(MachineInstr *MI) { Insts.push_back(MI); }
563 
564  /// Insert MI into the instruction list before I, possibly inside a bundle.
565  ///
566  /// If the insertion point is inside a bundle, MI will be added to the bundle,
567  /// otherwise MI will not be added to any bundle. That means this function
568  /// alone can't be used to prepend or append instructions to bundles. See
569  /// MIBundleBuilder::insert() for a more reliable way of doing that.
571 
572  /// Insert a range of instructions into the instruction list before I.
573  template<typename IT>
574  void insert(iterator I, IT S, IT E) {
575  assert((I == end() || I->getParent() == this) &&
576  "iterator points outside of basic block");
577  Insts.insert(I.getInstrIterator(), S, E);
578  }
579 
580  /// Insert MI into the instruction list before I.
582  assert((I == end() || I->getParent() == this) &&
583  "iterator points outside of basic block");
584  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
585  "Cannot insert instruction with bundle flags");
586  return Insts.insert(I.getInstrIterator(), MI);
587  }
588 
589  /// Insert MI into the instruction list after I.
591  assert((I == end() || I->getParent() == this) &&
592  "iterator points outside of basic block");
593  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
594  "Cannot insert instruction with bundle flags");
595  return Insts.insertAfter(I.getInstrIterator(), MI);
596  }
597 
598  /// Remove an instruction from the instruction list and delete it.
599  ///
600  /// If the instruction is part of a bundle, the other instructions in the
601  /// bundle will still be bundled after removing the single instruction.
603 
604  /// Remove an instruction from the instruction list and delete it.
605  ///
606  /// If the instruction is part of a bundle, the other instructions in the
607  /// bundle will still be bundled after removing the single instruction.
609  return erase(instr_iterator(I));
610  }
611 
612  /// Remove a range of instructions from the instruction list and delete them.
614  return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
615  }
616 
617  /// Remove an instruction or bundle from the instruction list and delete it.
618  ///
619  /// If I points to a bundle of instructions, they are all erased.
621  return erase(I, std::next(I));
622  }
623 
624  /// Remove an instruction from the instruction list and delete it.
625  ///
626  /// If I is the head of a bundle of instructions, the whole bundle will be
627  /// erased.
629  return erase(iterator(I));
630  }
631 
632  /// Remove the unbundled instruction from the instruction list without
633  /// deleting it.
634  ///
635  /// This function can not be used to remove bundled instructions, use
636  /// remove_instr to remove individual instructions from a bundle.
638  assert(!I->isBundled() && "Cannot remove bundled instructions");
639  return Insts.remove(instr_iterator(I));
640  }
641 
642  /// Remove the possibly bundled instruction from the instruction list
643  /// without deleting it.
644  ///
645  /// If the instruction is part of a bundle, the other instructions in the
646  /// bundle will still be bundled after removing the single instruction.
647  MachineInstr *remove_instr(MachineInstr *I);
648 
649  void clear() {
650  Insts.clear();
651  }
652 
653  /// Take an instruction from MBB 'Other' at the position From, and insert it
654  /// into this MBB right before 'Where'.
655  ///
656  /// If From points to a bundle of instructions, the whole bundle is moved.
658  // The range splice() doesn't allow noop moves, but this one does.
659  if (Where != From)
660  splice(Where, Other, From, std::next(From));
661  }
662 
663  /// Take a block of instructions from MBB 'Other' in the range [From, To),
664  /// and insert them into this MBB right before 'Where'.
665  ///
666  /// The instruction at 'Where' must not be included in the range of
667  /// instructions to move.
669  iterator From, iterator To) {
670  Insts.splice(Where.getInstrIterator(), Other->Insts,
671  From.getInstrIterator(), To.getInstrIterator());
672  }
673 
674  /// This method unlinks 'this' from the containing function, and returns it,
675  /// but does not delete it.
676  MachineBasicBlock *removeFromParent();
677 
678  /// This method unlinks 'this' from the containing function and deletes it.
679  void eraseFromParent();
680 
681  /// Given a machine basic block that branched to 'Old', change the code and
682  /// CFG so that it branches to 'New' instead.
683  void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
684 
685  /// Various pieces of code can cause excess edges in the CFG to be inserted.
686  /// If we have proven that MBB can only branch to DestA and DestB, remove any
687  /// other MBB successors from the CFG. DestA and DestB can be null. Besides
688  /// DestA and DestB, retain other edges leading to LandingPads (currently
689  /// there can be only one; we don't check or require that here). Note it is
690  /// possible that DestA and/or DestB are LandingPads.
691  bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
692  MachineBasicBlock *DestB,
693  bool IsCond);
694 
695  /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
696  /// instructions. Return UnknownLoc if there is none.
697  DebugLoc findDebugLoc(instr_iterator MBBI);
699  return findDebugLoc(MBBI.getInstrIterator());
700  }
701 
702  /// Find and return the merged DebugLoc of the branch instructions of the
703  /// block. Return UnknownLoc if there is none.
704  DebugLoc findBranchDebugLoc();
705 
706  /// Possible outcome of a register liveness query to computeRegisterLiveness()
708  LQR_Live, ///< Register is known to be (at least partially) live.
709  LQR_Dead, ///< Register is known to be fully dead.
710  LQR_Unknown ///< Register liveness not decidable from local neighborhood.
711  };
712 
713  /// Return whether (physical) register \p Reg has been defined and not
714  /// killed as of just before \p Before.
715  ///
716  /// Search is localised to a neighborhood of \p Neighborhood instructions
717  /// before (searching for defs or kills) and \p Neighborhood instructions
718  /// after (searching just for defs) \p Before.
719  ///
720  /// \p Reg must be a physical register.
721  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
722  unsigned Reg,
723  const_iterator Before,
724  unsigned Neighborhood = 10) const;
725 
726  // Debugging methods.
727  void dump() const;
728  void print(raw_ostream &OS, const SlotIndexes * = nullptr,
729  bool IsStandalone = true) const;
730  void print(raw_ostream &OS, ModuleSlotTracker &MST,
731  const SlotIndexes * = nullptr, bool IsStandalone = true) const;
732 
733  // Printing method used by LoopInfo.
734  void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
735 
736  /// MachineBasicBlocks are uniquely numbered at the function level, unless
737  /// they're not in a MachineFunction yet, in which case this will return -1.
738  int getNumber() const { return Number; }
739  void setNumber(int N) { Number = N; }
740 
741  /// Return the MCSymbol for this basic block.
742  MCSymbol *getSymbol() const;
743 
745  return IrrLoopHeaderWeight;
746  }
747 
748  void setIrrLoopHeaderWeight(uint64_t Weight) {
749  IrrLoopHeaderWeight = Weight;
750  }
751 
752 private:
753  /// Return probability iterator corresponding to the I successor iterator.
754  probability_iterator getProbabilityIterator(succ_iterator I);
755  const_probability_iterator
756  getProbabilityIterator(const_succ_iterator I) const;
757 
759  friend class MIPrinter;
760 
761  /// Return probability of the edge from this block to MBB. This method should
762  /// NOT be called directly, but by using getEdgeProbability method from
763  /// MachineBranchProbabilityInfo class.
764  BranchProbability getSuccProbability(const_succ_iterator Succ) const;
765 
766  // Methods used to maintain doubly linked list of blocks...
768 
769  // Machine-CFG mutators
770 
771  /// Add Pred as a predecessor of this MachineBasicBlock. Don't do this
772  /// unless you know what you're doing, because it doesn't update Pred's
773  /// successors list. Use Pred->addSuccessor instead.
774  void addPredecessor(MachineBasicBlock *Pred);
775 
776  /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
777  /// unless you know what you're doing, because it doesn't update Pred's
778  /// successors list. Use Pred->removeSuccessor instead.
779  void removePredecessor(MachineBasicBlock *Pred);
780 };
781 
783 
784 /// Prints a machine basic block reference.
785 ///
786 /// The format is:
787 /// %bb.5 - a machine basic block with MBB.getNumber() == 5.
788 ///
789 /// Usage: OS << printMBBReference(MBB) << '\n';
791 
792 // This is useful when building IndexedMaps keyed on basic block pointers.
795  unsigned operator()(const MachineBasicBlock *MBB) const {
796  return MBB->getNumber();
797  }
798 };
799 
800 //===--------------------------------------------------------------------===//
801 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
802 //===--------------------------------------------------------------------===//
803 
804 // Provide specializations of GraphTraits to be able to treat a
805 // MachineFunction as a graph of MachineBasicBlocks.
806 //
807 
808 template <> struct GraphTraits<MachineBasicBlock *> {
811 
812  static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
814  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
815 };
816 
817 template <> struct GraphTraits<const MachineBasicBlock *> {
818  using NodeRef = const MachineBasicBlock *;
820 
821  static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
823  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
824 };
825 
826 // Provide specializations of GraphTraits to be able to treat a
827 // MachineFunction as a graph of MachineBasicBlocks and to walk it
828 // in inverse order. Inverse order for a function is considered
829 // to be when traversing the predecessor edges of a MBB
830 // instead of the successor edges.
831 //
832 template <> struct GraphTraits<Inverse<MachineBasicBlock*>> {
835 
837  return G.Graph;
838  }
839 
841  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
842 };
843 
845  using NodeRef = const MachineBasicBlock *;
847 
849  return G.Graph;
850  }
851 
853  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
854 };
855 
856 /// MachineInstrSpan provides an interface to get an iteration range
857 /// containing the instruction it was initialized with, along with all
858 /// those instructions inserted prior to or following that instruction
859 /// at some point after the MachineInstrSpan is constructed.
861  MachineBasicBlock &MBB;
863 
864 public:
866  : MBB(*I->getParent()),
867  I(I),
868  B(I == MBB.begin() ? MBB.end() : std::prev(I)),
869  E(std::next(I)) {}
870 
872  return B == MBB.end() ? MBB.begin() : std::next(B);
873  }
875  bool empty() { return begin() == end(); }
876 
878 };
879 
880 /// Increment \p It until it points to a non-debug instruction or to \p End
881 /// and return the resulting iterator. This function should only be used
882 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
883 /// const_instr_iterator} and the respective reverse iterators.
884 template<typename IterT>
885 inline IterT skipDebugInstructionsForward(IterT It, IterT End) {
886  while (It != End && It->isDebugValue())
887  It++;
888  return It;
889 }
890 
891 /// Decrement \p It until it points to a non-debug instruction or to \p Begin
892 /// and return the resulting iterator. This function should only be used
893 /// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
894 /// const_instr_iterator} and the respective reverse iterators.
895 template<class IterT>
896 inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin) {
897  while (It != Begin && It->isDebugValue())
898  It--;
899  return It;
900 }
901 
902 } // end namespace llvm
903 
904 #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:280
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:101
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:766
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:249
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:327
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:342
static const unsigned End
This class prints out the machine instructions using the MIR serialization format.
Definition: MIRPrinter.cpp:139
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:403
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:326
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:264
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
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:322
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:2018
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:331
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:250
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()