MachineBasicBlock.h revision 251662
1193323Sed//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===//
2193323Sed//
3193323Sed//                     The LLVM Compiler Infrastructure
4193323Sed//
5193323Sed// This file is distributed under the University of Illinois Open Source
6193323Sed// License. See LICENSE.TXT for details.
7193323Sed//
8193323Sed//===----------------------------------------------------------------------===//
9193323Sed//
10193323Sed// Collect the sequence of machine instructions for a basic block.
11193323Sed//
12193323Sed//===----------------------------------------------------------------------===//
13193323Sed
14193323Sed#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
15193323Sed#define LLVM_CODEGEN_MACHINEBASICBLOCK_H
16193323Sed
17249423Sdim#include "llvm/ADT/GraphTraits.h"
18193323Sed#include "llvm/CodeGen/MachineInstr.h"
19224145Sdim#include "llvm/Support/DataTypes.h"
20221345Sdim#include <functional>
21193323Sed
22193323Sednamespace llvm {
23193323Sed
24210299Sedclass Pass;
25193323Sedclass BasicBlock;
26193323Sedclass MachineFunction;
27203954Srdivackyclass MCSymbol;
28218893Sdimclass SlotIndexes;
29203954Srdivackyclass StringRef;
30198090Srdivackyclass raw_ostream;
31224145Sdimclass MachineBranchProbabilityInfo;
32193323Sed
33193323Sedtemplate <>
34193323Sedstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
35193323Sedprivate:
36198090Srdivacky  mutable ilist_half_node<MachineInstr> Sentinel;
37193323Sed
38193323Sed  // this is only set by the MachineBasicBlock owning the LiveList
39193323Sed  friend class MachineBasicBlock;
40193323Sed  MachineBasicBlock* Parent;
41193323Sed
42193323Sedpublic:
43193323Sed  MachineInstr *createSentinel() const {
44193323Sed    return static_cast<MachineInstr*>(&Sentinel);
45193323Sed  }
46193323Sed  void destroySentinel(MachineInstr *) const {}
47193323Sed
48193323Sed  MachineInstr *provideInitialHead() const { return createSentinel(); }
49193323Sed  MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); }
50193323Sed  static void noteHead(MachineInstr*, MachineInstr*) {}
51193323Sed
52193323Sed  void addNodeToList(MachineInstr* N);
53193323Sed  void removeNodeFromList(MachineInstr* N);
54193323Sed  void transferNodesFromList(ilist_traits &SrcTraits,
55193323Sed                             ilist_iterator<MachineInstr> first,
56193323Sed                             ilist_iterator<MachineInstr> last);
57193323Sed  void deleteNode(MachineInstr *N);
58193323Sedprivate:
59193323Sed  void createNode(const MachineInstr &);
60193323Sed};
61193323Sed
62193323Sedclass MachineBasicBlock : public ilist_node<MachineBasicBlock> {
63193323Sed  typedef ilist<MachineInstr> Instructions;
64193323Sed  Instructions Insts;
65193323Sed  const BasicBlock *BB;
66193323Sed  int Number;
67193323Sed  MachineFunction *xParent;
68224145Sdim
69193323Sed  /// Predecessors/Successors - Keep track of the predecessor / successor
70193323Sed  /// basicblocks.
71193323Sed  std::vector<MachineBasicBlock *> Predecessors;
72193323Sed  std::vector<MachineBasicBlock *> Successors;
73193323Sed
74224145Sdim  /// Weights - Keep track of the weights to the successors. This vector
75224145Sdim  /// has the same order as Successors, or it is empty if we don't use it
76224145Sdim  /// (disable optimization).
77224145Sdim  std::vector<uint32_t> Weights;
78224145Sdim  typedef std::vector<uint32_t>::iterator weight_iterator;
79234353Sdim  typedef std::vector<uint32_t>::const_iterator const_weight_iterator;
80224145Sdim
81193323Sed  /// LiveIns - Keep track of the physical registers that are livein of
82193323Sed  /// the basicblock.
83193323Sed  std::vector<unsigned> LiveIns;
84193323Sed
85193323Sed  /// Alignment - Alignment of the basic block. Zero if the basic block does
86193323Sed  /// not need to be aligned.
87234353Sdim  /// The alignment is specified as log2(bytes).
88193323Sed  unsigned Alignment;
89234353Sdim
90193323Sed  /// IsLandingPad - Indicate that this basic block is entered via an
91193323Sed  /// exception handler.
92193323Sed  bool IsLandingPad;
93193323Sed
94198892Srdivacky  /// AddressTaken - Indicate that this basic block is potentially the
95198892Srdivacky  /// target of an indirect branch.
96198892Srdivacky  bool AddressTaken;
97198892Srdivacky
98251662Sdim  /// \brief since getSymbol is a relatively heavy-weight operation, the symbol
99251662Sdim  /// is only computed once and is cached.
100251662Sdim  mutable MCSymbol *CachedMCSymbol;
101251662Sdim
102193323Sed  // Intrusive list support
103193323Sed  MachineBasicBlock() {}
104193323Sed
105193323Sed  explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb);
106193323Sed
107193323Sed  ~MachineBasicBlock();
108193323Sed
109193323Sed  // MachineBasicBlocks are allocated and owned by MachineFunction.
110193323Sed  friend class MachineFunction;
111193323Sed
112193323Sedpublic:
113193323Sed  /// getBasicBlock - Return the LLVM basic block that this instance
114199989Srdivacky  /// corresponded to originally. Note that this may be NULL if this instance
115199989Srdivacky  /// does not correspond directly to an LLVM basic block.
116193323Sed  ///
117193323Sed  const BasicBlock *getBasicBlock() const { return BB; }
118193323Sed
119199989Srdivacky  /// getName - Return the name of the corresponding LLVM basic block, or
120199989Srdivacky  /// "(null)".
121199989Srdivacky  StringRef getName() const;
122199989Srdivacky
123234353Sdim  /// getFullName - Return a formatted string to identify this block and its
124234353Sdim  /// parent function.
125234353Sdim  std::string getFullName() const;
126234353Sdim
127198892Srdivacky  /// hasAddressTaken - Test whether this block is potentially the target
128198892Srdivacky  /// of an indirect branch.
129198892Srdivacky  bool hasAddressTaken() const { return AddressTaken; }
130198892Srdivacky
131198892Srdivacky  /// setHasAddressTaken - Set this block to reflect that it potentially
132198892Srdivacky  /// is the target of an indirect branch.
133198892Srdivacky  void setHasAddressTaken() { AddressTaken = true; }
134198892Srdivacky
135193323Sed  /// getParent - Return the MachineFunction containing this basic block.
136193323Sed  ///
137193323Sed  const MachineFunction *getParent() const { return xParent; }
138193323Sed  MachineFunction *getParent() { return xParent; }
139193323Sed
140193323Sed
141234353Sdim  /// bundle_iterator - MachineBasicBlock iterator that automatically skips over
142234353Sdim  /// MIs that are inside bundles (i.e. walk top level MIs only).
143234353Sdim  template<typename Ty, typename IterTy>
144234353Sdim  class bundle_iterator
145234353Sdim    : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> {
146234353Sdim    IterTy MII;
147234353Sdim
148234353Sdim  public:
149239462Sdim    bundle_iterator(IterTy mii) : MII(mii) {}
150234353Sdim
151234353Sdim    bundle_iterator(Ty &mi) : MII(mi) {
152249423Sdim      assert(!mi.isBundledWithPred() &&
153234353Sdim             "It's not legal to initialize bundle_iterator with a bundled MI");
154234353Sdim    }
155234353Sdim    bundle_iterator(Ty *mi) : MII(mi) {
156249423Sdim      assert((!mi || !mi->isBundledWithPred()) &&
157234353Sdim             "It's not legal to initialize bundle_iterator with a bundled MI");
158234353Sdim    }
159239462Sdim    // Template allows conversion from const to nonconst.
160239462Sdim    template<class OtherTy, class OtherIterTy>
161239462Sdim    bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I)
162239462Sdim      : MII(I.getInstrIterator()) {}
163234353Sdim    bundle_iterator() : MII(0) {}
164234353Sdim
165234353Sdim    Ty &operator*() const { return *MII; }
166234353Sdim    Ty *operator->() const { return &operator*(); }
167234353Sdim
168234353Sdim    operator Ty*() const { return MII; }
169234353Sdim
170234353Sdim    bool operator==(const bundle_iterator &x) const {
171234353Sdim      return MII == x.MII;
172234353Sdim    }
173234353Sdim    bool operator!=(const bundle_iterator &x) const {
174234353Sdim      return !operator==(x);
175234353Sdim    }
176234353Sdim
177234353Sdim    // Increment and decrement operators...
178234353Sdim    bundle_iterator &operator--() {      // predecrement - Back up
179239462Sdim      do --MII;
180249423Sdim      while (MII->isBundledWithPred());
181234353Sdim      return *this;
182234353Sdim    }
183234353Sdim    bundle_iterator &operator++() {      // preincrement - Advance
184249423Sdim      while (MII->isBundledWithSucc())
185249423Sdim        ++MII;
186249423Sdim      ++MII;
187234353Sdim      return *this;
188234353Sdim    }
189234353Sdim    bundle_iterator operator--(int) {    // postdecrement operators...
190234353Sdim      bundle_iterator tmp = *this;
191239462Sdim      --*this;
192234353Sdim      return tmp;
193234353Sdim    }
194234353Sdim    bundle_iterator operator++(int) {    // postincrement operators...
195234353Sdim      bundle_iterator tmp = *this;
196239462Sdim      ++*this;
197234353Sdim      return tmp;
198234353Sdim    }
199234353Sdim
200234353Sdim    IterTy getInstrIterator() const {
201234353Sdim      return MII;
202234353Sdim    }
203234353Sdim  };
204234353Sdim
205234353Sdim  typedef Instructions::iterator                                 instr_iterator;
206234353Sdim  typedef Instructions::const_iterator                     const_instr_iterator;
207234353Sdim  typedef std::reverse_iterator<instr_iterator>          reverse_instr_iterator;
208234353Sdim  typedef
209234353Sdim  std::reverse_iterator<const_instr_iterator>      const_reverse_instr_iterator;
210234353Sdim
211234353Sdim  typedef
212234353Sdim  bundle_iterator<MachineInstr,instr_iterator>                         iterator;
213234353Sdim  typedef
214234353Sdim  bundle_iterator<const MachineInstr,const_instr_iterator>       const_iterator;
215234353Sdim  typedef std::reverse_iterator<const_iterator>          const_reverse_iterator;
216234353Sdim  typedef std::reverse_iterator<iterator>                      reverse_iterator;
217234353Sdim
218234353Sdim
219193323Sed  unsigned size() const { return (unsigned)Insts.size(); }
220193323Sed  bool empty() const { return Insts.empty(); }
221193323Sed
222193323Sed  MachineInstr& front() { return Insts.front(); }
223193323Sed  MachineInstr& back()  { return Insts.back(); }
224193323Sed  const MachineInstr& front() const { return Insts.front(); }
225193323Sed  const MachineInstr& back()  const { return Insts.back(); }
226193323Sed
227234353Sdim  instr_iterator                instr_begin()       { return Insts.begin();  }
228234353Sdim  const_instr_iterator          instr_begin() const { return Insts.begin();  }
229234353Sdim  instr_iterator                  instr_end()       { return Insts.end();    }
230234353Sdim  const_instr_iterator            instr_end() const { return Insts.end();    }
231234353Sdim  reverse_instr_iterator       instr_rbegin()       { return Insts.rbegin(); }
232234353Sdim  const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
233234353Sdim  reverse_instr_iterator       instr_rend  ()       { return Insts.rend();   }
234234353Sdim  const_reverse_instr_iterator instr_rend  () const { return Insts.rend();   }
235234353Sdim
236239462Sdim  iterator                begin()       { return instr_begin();  }
237239462Sdim  const_iterator          begin() const { return instr_begin();  }
238239462Sdim  iterator                end  ()       { return instr_end();    }
239239462Sdim  const_iterator          end  () const { return instr_end();    }
240239462Sdim  reverse_iterator       rbegin()       { return instr_rbegin(); }
241239462Sdim  const_reverse_iterator rbegin() const { return instr_rbegin(); }
242239462Sdim  reverse_iterator       rend  ()       { return instr_rend();   }
243239462Sdim  const_reverse_iterator rend  () const { return instr_rend();   }
244193323Sed
245234353Sdim
246193323Sed  // Machine-CFG iterators
247193323Sed  typedef std::vector<MachineBasicBlock *>::iterator       pred_iterator;
248193323Sed  typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
249193323Sed  typedef std::vector<MachineBasicBlock *>::iterator       succ_iterator;
250193323Sed  typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
251193323Sed  typedef std::vector<MachineBasicBlock *>::reverse_iterator
252193323Sed                                                         pred_reverse_iterator;
253193323Sed  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
254193323Sed                                                   const_pred_reverse_iterator;
255193323Sed  typedef std::vector<MachineBasicBlock *>::reverse_iterator
256193323Sed                                                         succ_reverse_iterator;
257193323Sed  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
258193323Sed                                                   const_succ_reverse_iterator;
259193323Sed
260193323Sed  pred_iterator        pred_begin()       { return Predecessors.begin(); }
261193323Sed  const_pred_iterator  pred_begin() const { return Predecessors.begin(); }
262193323Sed  pred_iterator        pred_end()         { return Predecessors.end();   }
263193323Sed  const_pred_iterator  pred_end()   const { return Predecessors.end();   }
264193323Sed  pred_reverse_iterator        pred_rbegin()
265193323Sed                                          { return Predecessors.rbegin();}
266193323Sed  const_pred_reverse_iterator  pred_rbegin() const
267193323Sed                                          { return Predecessors.rbegin();}
268193323Sed  pred_reverse_iterator        pred_rend()
269193323Sed                                          { return Predecessors.rend();  }
270193323Sed  const_pred_reverse_iterator  pred_rend()   const
271193323Sed                                          { return Predecessors.rend();  }
272193323Sed  unsigned             pred_size()  const {
273193323Sed    return (unsigned)Predecessors.size();
274193323Sed  }
275193323Sed  bool                 pred_empty() const { return Predecessors.empty(); }
276193323Sed  succ_iterator        succ_begin()       { return Successors.begin();   }
277193323Sed  const_succ_iterator  succ_begin() const { return Successors.begin();   }
278193323Sed  succ_iterator        succ_end()         { return Successors.end();     }
279193323Sed  const_succ_iterator  succ_end()   const { return Successors.end();     }
280193323Sed  succ_reverse_iterator        succ_rbegin()
281193323Sed                                          { return Successors.rbegin();  }
282193323Sed  const_succ_reverse_iterator  succ_rbegin() const
283193323Sed                                          { return Successors.rbegin();  }
284193323Sed  succ_reverse_iterator        succ_rend()
285193323Sed                                          { return Successors.rend();    }
286193323Sed  const_succ_reverse_iterator  succ_rend()   const
287193323Sed                                          { return Successors.rend();    }
288193323Sed  unsigned             succ_size()  const {
289193323Sed    return (unsigned)Successors.size();
290193323Sed  }
291193323Sed  bool                 succ_empty() const { return Successors.empty();   }
292193323Sed
293193323Sed  // LiveIn management methods.
294193323Sed
295193323Sed  /// addLiveIn - Add the specified register as a live in.  Note that it
296193323Sed  /// is an error to add the same register to the same set more than once.
297193323Sed  void addLiveIn(unsigned Reg)  { LiveIns.push_back(Reg); }
298193323Sed
299193323Sed  /// removeLiveIn - Remove the specified register from the live in set.
300193323Sed  ///
301193323Sed  void removeLiveIn(unsigned Reg);
302193323Sed
303193323Sed  /// isLiveIn - Return true if the specified register is in the live in set.
304193323Sed  ///
305193323Sed  bool isLiveIn(unsigned Reg) const;
306193323Sed
307193323Sed  // Iteration support for live in sets.  These sets are kept in sorted
308193323Sed  // order by their register number.
309207618Srdivacky  typedef std::vector<unsigned>::const_iterator livein_iterator;
310207618Srdivacky  livein_iterator livein_begin() const { return LiveIns.begin(); }
311207618Srdivacky  livein_iterator livein_end()   const { return LiveIns.end(); }
312193323Sed  bool            livein_empty() const { return LiveIns.empty(); }
313193323Sed
314193323Sed  /// getAlignment - Return alignment of the basic block.
315234353Sdim  /// The alignment is specified as log2(bytes).
316193323Sed  ///
317193323Sed  unsigned getAlignment() const { return Alignment; }
318193323Sed
319193323Sed  /// setAlignment - Set alignment of the basic block.
320234353Sdim  /// The alignment is specified as log2(bytes).
321193323Sed  ///
322193323Sed  void setAlignment(unsigned Align) { Alignment = Align; }
323193323Sed
324193323Sed  /// isLandingPad - Returns true if the block is a landing pad. That is
325193323Sed  /// this basic block is entered via an exception handler.
326193323Sed  bool isLandingPad() const { return IsLandingPad; }
327193323Sed
328193323Sed  /// setIsLandingPad - Indicates the block is a landing pad.  That is
329193323Sed  /// this basic block is entered via an exception handler.
330226633Sdim  void setIsLandingPad(bool V = true) { IsLandingPad = V; }
331193323Sed
332218893Sdim  /// getLandingPadSuccessor - If this block has a successor that is a landing
333218893Sdim  /// pad, return it. Otherwise return NULL.
334218893Sdim  const MachineBasicBlock *getLandingPadSuccessor() const;
335218893Sdim
336193323Sed  // Code Layout methods.
337234353Sdim
338193323Sed  /// moveBefore/moveAfter - move 'this' block before or after the specified
339193323Sed  /// block.  This only moves the block, it does not modify the CFG or adjust
340193323Sed  /// potential fall-throughs at the end of the block.
341193323Sed  void moveBefore(MachineBasicBlock *NewAfter);
342193323Sed  void moveAfter(MachineBasicBlock *NewBefore);
343199481Srdivacky
344199481Srdivacky  /// updateTerminator - Update the terminator instructions in block to account
345199481Srdivacky  /// for changes to the layout. If the block previously used a fallthrough,
346199481Srdivacky  /// it may now need a branch, and if it previously used branching it may now
347199481Srdivacky  /// be able to use a fallthrough.
348199481Srdivacky  void updateTerminator();
349199481Srdivacky
350193323Sed  // Machine-CFG mutators
351224145Sdim
352193323Sed  /// addSuccessor - Add succ as a successor of this MachineBasicBlock.
353224145Sdim  /// The Predecessors list of succ is automatically updated. WEIGHT
354224145Sdim  /// parameter is stored in Weights list and it may be used by
355224145Sdim  /// MachineBranchProbabilityInfo analysis to calculate branch probability.
356193323Sed  ///
357243830Sdim  /// Note that duplicate Machine CFG edges are not allowed.
358243830Sdim  ///
359224145Sdim  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0);
360193323Sed
361193323Sed  /// removeSuccessor - Remove successor from the successors list of this
362193323Sed  /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
363193323Sed  ///
364193323Sed  void removeSuccessor(MachineBasicBlock *succ);
365193323Sed
366193323Sed  /// removeSuccessor - Remove specified successor from the successors list of
367193323Sed  /// this MachineBasicBlock. The Predecessors list of succ is automatically
368193323Sed  /// updated.  Return the iterator to the element after the one removed.
369193323Sed  ///
370193323Sed  succ_iterator removeSuccessor(succ_iterator I);
371224145Sdim
372224145Sdim  /// replaceSuccessor - Replace successor OLD with NEW and update weight info.
373224145Sdim  ///
374224145Sdim  void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
375224145Sdim
376224145Sdim
377193323Sed  /// transferSuccessors - Transfers all the successors from MBB to this
378193323Sed  /// machine basic block (i.e., copies all the successors fromMBB and
379199481Srdivacky  /// remove all the successors from fromMBB).
380193323Sed  void transferSuccessors(MachineBasicBlock *fromMBB);
381210299Sed
382210299Sed  /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as
383210299Sed  /// in transferSuccessors, and update PHI operands in the successor blocks
384210299Sed  /// which refer to fromMBB to refer to this.
385210299Sed  void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB);
386234353Sdim
387239462Sdim  /// isPredecessor - Return true if the specified MBB is a predecessor of this
388239462Sdim  /// block.
389239462Sdim  bool isPredecessor(const MachineBasicBlock *MBB) const;
390239462Sdim
391193323Sed  /// isSuccessor - Return true if the specified MBB is a successor of this
392193323Sed  /// block.
393193323Sed  bool isSuccessor(const MachineBasicBlock *MBB) const;
394193323Sed
395193323Sed  /// isLayoutSuccessor - Return true if the specified MBB will be emitted
396193323Sed  /// immediately after this block, such that if this block exits by
397193323Sed  /// falling through, control will transfer to the specified MBB. Note
398193323Sed  /// that MBB need not be a successor at all, for example if this block
399193323Sed  /// ends with an unconditional branch to some other block.
400193323Sed  bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
401193323Sed
402199989Srdivacky  /// canFallThrough - Return true if the block can implicitly transfer
403199989Srdivacky  /// control to the block after it by falling off the end of it.  This should
404199989Srdivacky  /// return false if it can reach the block after it, but it uses an explicit
405199989Srdivacky  /// branch to do so (e.g., a table jump).  True is a conservative answer.
406199989Srdivacky  bool canFallThrough();
407199989Srdivacky
408234353Sdim  /// Returns a pointer to the first instructon in this block that is not a
409210299Sed  /// PHINode instruction. When adding instruction to the beginning of the
410210299Sed  /// basic block, they should be added before the returned value, not before
411210299Sed  /// the first instruction, which might be PHI.
412210299Sed  /// Returns end() is there's no non-PHI instruction.
413210299Sed  iterator getFirstNonPHI();
414210299Sed
415218893Sdim  /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is
416218893Sdim  /// not a PHI or a label. This is the correct point to insert copies at the
417218893Sdim  /// beginning of a basic block.
418218893Sdim  iterator SkipPHIsAndLabels(iterator I);
419218893Sdim
420193323Sed  /// getFirstTerminator - returns an iterator to the first terminator
421193323Sed  /// instruction of this basic block. If a terminator does not exist,
422193323Sed  /// it returns end()
423193323Sed  iterator getFirstTerminator();
424234353Sdim  const_iterator getFirstTerminator() const;
425193323Sed
426234353Sdim  /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles
427234353Sdim  /// and return an instr_iterator instead.
428234353Sdim  instr_iterator getFirstInstrTerminator();
429221345Sdim
430218893Sdim  /// getLastNonDebugInstr - returns an iterator to the last non-debug
431218893Sdim  /// instruction in the basic block, or end()
432218893Sdim  iterator getLastNonDebugInstr();
433234353Sdim  const_iterator getLastNonDebugInstr() const;
434218893Sdim
435210299Sed  /// SplitCriticalEdge - Split the critical edge from this block to the
436210299Sed  /// given successor block, and return the newly created block, or null
437210299Sed  /// if splitting is not possible.
438210299Sed  ///
439210299Sed  /// This function updates LiveVariables, MachineDominatorTree, and
440210299Sed  /// MachineLoopInfo, as applicable.
441210299Sed  MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);
442210299Sed
443193323Sed  void pop_front() { Insts.pop_front(); }
444193323Sed  void pop_back() { Insts.pop_back(); }
445193323Sed  void push_back(MachineInstr *MI) { Insts.push_back(MI); }
446234353Sdim
447249423Sdim  /// Insert MI into the instruction list before I, possibly inside a bundle.
448249423Sdim  ///
449249423Sdim  /// If the insertion point is inside a bundle, MI will be added to the bundle,
450249423Sdim  /// otherwise MI will not be added to any bundle. That means this function
451249423Sdim  /// alone can't be used to prepend or append instructions to bundles. See
452249423Sdim  /// MIBundleBuilder::insert() for a more reliable way of doing that.
453249423Sdim  instr_iterator insert(instr_iterator I, MachineInstr *M);
454193323Sed
455249423Sdim  /// Insert a range of instructions into the instruction list before I.
456234353Sdim  template<typename IT>
457234353Sdim  void insert(iterator I, IT S, IT E) {
458234353Sdim    Insts.insert(I.getInstrIterator(), S, E);
459234353Sdim  }
460249423Sdim
461249423Sdim  /// Insert MI into the instruction list before I.
462249423Sdim  iterator insert(iterator I, MachineInstr *MI) {
463249423Sdim    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
464249423Sdim           "Cannot insert instruction with bundle flags");
465249423Sdim    return Insts.insert(I.getInstrIterator(), MI);
466234353Sdim  }
467249423Sdim
468249423Sdim  /// Insert MI into the instruction list after I.
469249423Sdim  iterator insertAfter(iterator I, MachineInstr *MI) {
470249423Sdim    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
471249423Sdim           "Cannot insert instruction with bundle flags");
472249423Sdim    return Insts.insertAfter(I.getInstrIterator(), MI);
473234353Sdim  }
474193323Sed
475249423Sdim  /// Remove an instruction from the instruction list and delete it.
476234353Sdim  ///
477249423Sdim  /// If the instruction is part of a bundle, the other instructions in the
478249423Sdim  /// bundle will still be bundled after removing the single instruction.
479249423Sdim  instr_iterator erase(instr_iterator I);
480249423Sdim
481249423Sdim  /// Remove an instruction from the instruction list and delete it.
482249423Sdim  ///
483249423Sdim  /// If the instruction is part of a bundle, the other instructions in the
484249423Sdim  /// bundle will still be bundled after removing the single instruction.
485234353Sdim  instr_iterator erase_instr(MachineInstr *I) {
486249423Sdim    return erase(instr_iterator(I));
487234353Sdim  }
488234353Sdim
489249423Sdim  /// Remove a range of instructions from the instruction list and delete them.
490234353Sdim  iterator erase(iterator I, iterator E) {
491234353Sdim    return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
492234353Sdim  }
493249423Sdim
494249423Sdim  /// Remove an instruction or bundle from the instruction list and delete it.
495249423Sdim  ///
496249423Sdim  /// If I points to a bundle of instructions, they are all erased.
497249423Sdim  iterator erase(iterator I) {
498249423Sdim    return erase(I, llvm::next(I));
499249423Sdim  }
500249423Sdim
501249423Sdim  /// Remove an instruction from the instruction list and delete it.
502249423Sdim  ///
503249423Sdim  /// If I is the head of a bundle of instructions, the whole bundle will be
504249423Sdim  /// erased.
505234353Sdim  iterator erase(MachineInstr *I) {
506249423Sdim    return erase(iterator(I));
507234353Sdim  }
508234353Sdim
509249423Sdim  /// Remove the unbundled instruction from the instruction list without
510249423Sdim  /// deleting it.
511249423Sdim  ///
512249423Sdim  /// This function can not be used to remove bundled instructions, use
513249423Sdim  /// remove_instr to remove individual instructions from a bundle.
514249423Sdim  MachineInstr *remove(MachineInstr *I) {
515249423Sdim    assert(!I->isBundled() && "Cannot remove bundled instructions");
516249423Sdim    return Insts.remove(I);
517249423Sdim  }
518249423Sdim
519249423Sdim  /// Remove the possibly bundled instruction from the instruction list
520249423Sdim  /// without deleting it.
521249423Sdim  ///
522249423Sdim  /// If the instruction is part of a bundle, the other instructions in the
523249423Sdim  /// bundle will still be bundled after removing the single instruction.
524249423Sdim  MachineInstr *remove_instr(MachineInstr *I);
525249423Sdim
526234353Sdim  void clear() {
527234353Sdim    Insts.clear();
528234353Sdim  }
529234353Sdim
530249423Sdim  /// Take an instruction from MBB 'Other' at the position From, and insert it
531249423Sdim  /// into this MBB right before 'Where'.
532249423Sdim  ///
533249423Sdim  /// If From points to a bundle of instructions, the whole bundle is moved.
534249423Sdim  void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
535249423Sdim    // The range splice() doesn't allow noop moves, but this one does.
536249423Sdim    if (Where != From)
537249423Sdim      splice(Where, Other, From, llvm::next(From));
538193323Sed  }
539193323Sed
540249423Sdim  /// Take a block of instructions from MBB 'Other' in the range [From, To),
541249423Sdim  /// and insert them into this MBB right before 'Where'.
542249423Sdim  ///
543249423Sdim  /// The instruction at 'Where' must not be included in the range of
544249423Sdim  /// instructions to move.
545249423Sdim  void splice(iterator Where, MachineBasicBlock *Other,
546249423Sdim              iterator From, iterator To) {
547249423Sdim    Insts.splice(Where.getInstrIterator(), Other->Insts,
548234353Sdim                 From.getInstrIterator(), To.getInstrIterator());
549193323Sed  }
550193323Sed
551193323Sed  /// removeFromParent - This method unlinks 'this' from the containing
552193323Sed  /// function, and returns it, but does not delete it.
553193323Sed  MachineBasicBlock *removeFromParent();
554234353Sdim
555193323Sed  /// eraseFromParent - This method unlinks 'this' from the containing
556193323Sed  /// function and deletes it.
557193323Sed  void eraseFromParent();
558193323Sed
559193323Sed  /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
560193323Sed  /// 'Old', change the code and CFG so that it branches to 'New' instead.
561193323Sed  void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
562193323Sed
563193323Sed  /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in
564193323Sed  /// the CFG to be inserted.  If we have proven that MBB can only branch to
565193323Sed  /// DestA and DestB, remove any other MBB successors from the CFG. DestA and
566193323Sed  /// DestB can be null. Besides DestA and DestB, retain other edges leading
567193323Sed  /// to LandingPads (currently there can be only one; we don't check or require
568193323Sed  /// that here). Note it is possible that DestA and/or DestB are LandingPads.
569193323Sed  bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
570193323Sed                            MachineBasicBlock *DestB,
571193323Sed                            bool isCond);
572193323Sed
573202878Srdivacky  /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping
574203954Srdivacky  /// any DBG_VALUE instructions.  Return UnknownLoc if there is none.
575234353Sdim  DebugLoc findDebugLoc(instr_iterator MBBI);
576234353Sdim  DebugLoc findDebugLoc(iterator MBBI) {
577234353Sdim    return findDebugLoc(MBBI.getInstrIterator());
578234353Sdim  }
579202878Srdivacky
580243830Sdim  /// Possible outcome of a register liveness query to computeRegisterLiveness()
581243830Sdim  enum LivenessQueryResult {
582243830Sdim    LQR_Live,            ///< Register is known to be live.
583243830Sdim    LQR_OverlappingLive, ///< Register itself is not live, but some overlapping
584243830Sdim                         ///< register is.
585243830Sdim    LQR_Dead,            ///< Register is known to be dead.
586243830Sdim    LQR_Unknown          ///< Register liveness not decidable from local
587243830Sdim                         ///< neighborhood.
588243830Sdim  };
589243830Sdim
590243830Sdim  /// computeRegisterLiveness - Return whether (physical) register \c Reg
591243830Sdim  /// has been <def>ined and not <kill>ed as of just before \c MI.
592243830Sdim  ///
593243830Sdim  /// Search is localised to a neighborhood of
594243830Sdim  /// \c Neighborhood instructions before (searching for defs or kills) and
595243830Sdim  /// Neighborhood instructions after (searching just for defs) MI.
596243830Sdim  ///
597243830Sdim  /// \c Reg must be a physical register.
598243830Sdim  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
599243830Sdim                                              unsigned Reg, MachineInstr *MI,
600243830Sdim                                              unsigned Neighborhood=10);
601243830Sdim
602193323Sed  // Debugging methods.
603193323Sed  void dump() const;
604218893Sdim  void print(raw_ostream &OS, SlotIndexes* = 0) const;
605193323Sed
606193323Sed  /// getNumber - MachineBasicBlocks are uniquely numbered at the function
607193323Sed  /// level, unless they're not in a MachineFunction yet, in which case this
608193323Sed  /// will return -1.
609193323Sed  ///
610193323Sed  int getNumber() const { return Number; }
611193323Sed  void setNumber(int N) { Number = N; }
612193323Sed
613203954Srdivacky  /// getSymbol - Return the MCSymbol for this basic block.
614203954Srdivacky  ///
615205218Srdivacky  MCSymbol *getSymbol() const;
616224145Sdim
617224145Sdim
618224145Sdimprivate:
619224145Sdim  /// getWeightIterator - Return weight iterator corresponding to the I
620224145Sdim  /// successor iterator.
621224145Sdim  weight_iterator getWeightIterator(succ_iterator I);
622234353Sdim  const_weight_iterator getWeightIterator(const_succ_iterator I) const;
623224145Sdim
624224145Sdim  friend class MachineBranchProbabilityInfo;
625224145Sdim
626224145Sdim  /// getSuccWeight - Return weight of the edge from this block to MBB. This
627224145Sdim  /// method should NOT be called directly, but by using getEdgeWeight method
628224145Sdim  /// from MachineBranchProbabilityInfo class.
629243830Sdim  uint32_t getSuccWeight(const_succ_iterator Succ) const;
630224145Sdim
631224145Sdim
632224145Sdim  // Methods used to maintain doubly linked list of blocks...
633193323Sed  friend struct ilist_traits<MachineBasicBlock>;
634193323Sed
635193323Sed  // Machine-CFG mutators
636193323Sed
637193323Sed  /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock.
638193323Sed  /// Don't do this unless you know what you're doing, because it doesn't
639193323Sed  /// update pred's successors list. Use pred->addSuccessor instead.
640193323Sed  ///
641193323Sed  void addPredecessor(MachineBasicBlock *pred);
642193323Sed
643193323Sed  /// removePredecessor - Remove pred as a predecessor of this
644193323Sed  /// MachineBasicBlock. Don't do this unless you know what you're
645193323Sed  /// doing, because it doesn't update pred's successors list. Use
646193323Sed  /// pred->removeSuccessor instead.
647193323Sed  ///
648193323Sed  void removePredecessor(MachineBasicBlock *pred);
649193323Sed};
650193323Sed
651198090Srdivackyraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
652193323Sed
653199481Srdivackyvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t);
654199481Srdivacky
655221345Sdim// This is useful when building IndexedMaps keyed on basic block pointers.
656221345Sdimstruct MBB2NumberFunctor :
657221345Sdim  public std::unary_function<const MachineBasicBlock*, unsigned> {
658221345Sdim  unsigned operator()(const MachineBasicBlock *MBB) const {
659221345Sdim    return MBB->getNumber();
660221345Sdim  }
661221345Sdim};
662221345Sdim
663193323Sed//===--------------------------------------------------------------------===//
664193323Sed// GraphTraits specializations for machine basic block graphs (machine-CFGs)
665193323Sed//===--------------------------------------------------------------------===//
666193323Sed
667193323Sed// Provide specializations of GraphTraits to be able to treat a
668193323Sed// MachineFunction as a graph of MachineBasicBlocks...
669193323Sed//
670193323Sed
671193323Sedtemplate <> struct GraphTraits<MachineBasicBlock *> {
672193323Sed  typedef MachineBasicBlock NodeType;
673193323Sed  typedef MachineBasicBlock::succ_iterator ChildIteratorType;
674193323Sed
675193323Sed  static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
676193323Sed  static inline ChildIteratorType child_begin(NodeType *N) {
677193323Sed    return N->succ_begin();
678193323Sed  }
679193323Sed  static inline ChildIteratorType child_end(NodeType *N) {
680193323Sed    return N->succ_end();
681193323Sed  }
682193323Sed};
683193323Sed
684193323Sedtemplate <> struct GraphTraits<const MachineBasicBlock *> {
685193323Sed  typedef const MachineBasicBlock NodeType;
686193323Sed  typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
687193323Sed
688193323Sed  static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
689193323Sed  static inline ChildIteratorType child_begin(NodeType *N) {
690193323Sed    return N->succ_begin();
691193323Sed  }
692193323Sed  static inline ChildIteratorType child_end(NodeType *N) {
693193323Sed    return N->succ_end();
694193323Sed  }
695193323Sed};
696193323Sed
697193323Sed// Provide specializations of GraphTraits to be able to treat a
698193323Sed// MachineFunction as a graph of MachineBasicBlocks... and to walk it
699193323Sed// in inverse order.  Inverse order for a function is considered
700193323Sed// to be when traversing the predecessor edges of a MBB
701193323Sed// instead of the successor edges.
702193323Sed//
703193323Sedtemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
704193323Sed  typedef MachineBasicBlock NodeType;
705193323Sed  typedef MachineBasicBlock::pred_iterator ChildIteratorType;
706193323Sed  static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
707193323Sed    return G.Graph;
708193323Sed  }
709193323Sed  static inline ChildIteratorType child_begin(NodeType *N) {
710193323Sed    return N->pred_begin();
711193323Sed  }
712193323Sed  static inline ChildIteratorType child_end(NodeType *N) {
713193323Sed    return N->pred_end();
714193323Sed  }
715193323Sed};
716193323Sed
717193323Sedtemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
718193323Sed  typedef const MachineBasicBlock NodeType;
719193323Sed  typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
720193323Sed  static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
721193323Sed    return G.Graph;
722193323Sed  }
723193323Sed  static inline ChildIteratorType child_begin(NodeType *N) {
724193323Sed    return N->pred_begin();
725193323Sed  }
726193323Sed  static inline ChildIteratorType child_end(NodeType *N) {
727193323Sed    return N->pred_end();
728193323Sed  }
729193323Sed};
730193323Sed
731193323Sed} // End llvm namespace
732193323Sed
733193323Sed#endif
734