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