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