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