1 //===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Collect the sequence of machine instructions for a basic block.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
15 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/Support/Streams.h"
24 class MachineFunction;
27 class ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
28 mutable MachineInstr Sentinel;
30 // this is only set by the MachineBasicBlock owning the LiveList
31 friend class MachineBasicBlock;
32 MachineBasicBlock* Parent;
35 MachineInstr *createSentinel() const { return &Sentinel; }
36 void destroySentinel(MachineInstr *) const {}
38 void addNodeToList(MachineInstr* N);
39 void removeNodeFromList(MachineInstr* N);
40 void transferNodesFromList(ilist_traits &SrcTraits,
41 ilist_iterator<MachineInstr> first,
42 ilist_iterator<MachineInstr> last);
43 void deleteNode(MachineInstr *N);
45 void createNode(const MachineInstr &);
48 class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
49 typedef ilist<MachineInstr> Instructions;
53 MachineFunction *xParent;
55 /// Predecessors/Successors - Keep track of the predecessor / successor
57 std::vector<MachineBasicBlock *> Predecessors;
58 std::vector<MachineBasicBlock *> Successors;
60 /// LiveIns - Keep track of the physical registers that are livein of
62 std::vector<unsigned> LiveIns;
64 /// Alignment - Alignment of the basic block. Zero if the basic block does
65 /// not need to be aligned.
68 /// IsLandingPad - Indicate that this basic block is entered via an
69 /// exception handler.
72 // Intrusive list support
73 friend class ilist_sentinel_traits<MachineBasicBlock>;
74 MachineBasicBlock() {}
76 explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb);
80 // MachineBasicBlocks are allocated and owned by MachineFunction.
81 friend class MachineFunction;
84 /// getBasicBlock - Return the LLVM basic block that this instance
85 /// corresponded to originally.
87 const BasicBlock *getBasicBlock() const { return BB; }
89 /// getParent - Return the MachineFunction containing this basic block.
91 const MachineFunction *getParent() const { return xParent; }
92 MachineFunction *getParent() { return xParent; }
94 typedef Instructions::iterator iterator;
95 typedef Instructions::const_iterator const_iterator;
96 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
97 typedef std::reverse_iterator<iterator> reverse_iterator;
99 unsigned size() const { return (unsigned)Insts.size(); }
100 bool empty() const { return Insts.empty(); }
102 MachineInstr& front() { return Insts.front(); }
103 MachineInstr& back() { return Insts.back(); }
105 iterator begin() { return Insts.begin(); }
106 const_iterator begin() const { return Insts.begin(); }
107 iterator end() { return Insts.end(); }
108 const_iterator end() const { return Insts.end(); }
109 reverse_iterator rbegin() { return Insts.rbegin(); }
110 const_reverse_iterator rbegin() const { return Insts.rbegin(); }
111 reverse_iterator rend () { return Insts.rend(); }
112 const_reverse_iterator rend () const { return Insts.rend(); }
114 // Machine-CFG iterators
115 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator;
116 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
117 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator;
118 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
119 typedef std::vector<MachineBasicBlock *>::reverse_iterator
120 pred_reverse_iterator;
121 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
122 const_pred_reverse_iterator;
123 typedef std::vector<MachineBasicBlock *>::reverse_iterator
124 succ_reverse_iterator;
125 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
126 const_succ_reverse_iterator;
128 pred_iterator pred_begin() { return Predecessors.begin(); }
129 const_pred_iterator pred_begin() const { return Predecessors.begin(); }
130 pred_iterator pred_end() { return Predecessors.end(); }
131 const_pred_iterator pred_end() const { return Predecessors.end(); }
132 pred_reverse_iterator pred_rbegin()
133 { return Predecessors.rbegin();}
134 const_pred_reverse_iterator pred_rbegin() const
135 { return Predecessors.rbegin();}
136 pred_reverse_iterator pred_rend()
137 { return Predecessors.rend(); }
138 const_pred_reverse_iterator pred_rend() const
139 { return Predecessors.rend(); }
140 unsigned pred_size() const {
141 return (unsigned)Predecessors.size();
143 bool pred_empty() const { return Predecessors.empty(); }
144 succ_iterator succ_begin() { return Successors.begin(); }
145 const_succ_iterator succ_begin() const { return Successors.begin(); }
146 succ_iterator succ_end() { return Successors.end(); }
147 const_succ_iterator succ_end() const { return Successors.end(); }
148 succ_reverse_iterator succ_rbegin()
149 { return Successors.rbegin(); }
150 const_succ_reverse_iterator succ_rbegin() const
151 { return Successors.rbegin(); }
152 succ_reverse_iterator succ_rend()
153 { return Successors.rend(); }
154 const_succ_reverse_iterator succ_rend() const
155 { return Successors.rend(); }
156 unsigned succ_size() const {
157 return (unsigned)Successors.size();
159 bool succ_empty() const { return Successors.empty(); }
161 // LiveIn management methods.
163 /// addLiveIn - Add the specified register as a live in. Note that it
164 /// is an error to add the same register to the same set more than once.
165 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); }
167 /// removeLiveIn - Remove the specified register from the live in set.
169 void removeLiveIn(unsigned Reg);
171 /// isLiveIn - Return true if the specified register is in the live in set.
173 bool isLiveIn(unsigned Reg) const;
175 // Iteration support for live in sets. These sets are kept in sorted
176 // order by their register number.
177 typedef std::vector<unsigned>::iterator livein_iterator;
178 typedef std::vector<unsigned>::const_iterator const_livein_iterator;
179 livein_iterator livein_begin() { return LiveIns.begin(); }
180 const_livein_iterator livein_begin() const { return LiveIns.begin(); }
181 livein_iterator livein_end() { return LiveIns.end(); }
182 const_livein_iterator livein_end() const { return LiveIns.end(); }
183 bool livein_empty() const { return LiveIns.empty(); }
185 /// getAlignment - Return alignment of the basic block.
187 unsigned getAlignment() const { return Alignment; }
189 /// setAlignment - Set alignment of the basic block.
191 void setAlignment(unsigned Align) { Alignment = Align; }
193 /// isLandingPad - Returns true if the block is a landing pad. That is
194 /// this basic block is entered via an exception handler.
195 bool isLandingPad() const { return IsLandingPad; }
197 /// setIsLandingPad - Indicates the block is a landing pad. That is
198 /// this basic block is entered via an exception handler.
199 void setIsLandingPad() { IsLandingPad = true; }
201 // Code Layout methods.
203 /// moveBefore/moveAfter - move 'this' block before or after the specified
204 /// block. This only moves the block, it does not modify the CFG or adjust
205 /// potential fall-throughs at the end of the block.
206 void moveBefore(MachineBasicBlock *NewAfter);
207 void moveAfter(MachineBasicBlock *NewBefore);
209 // Machine-CFG mutators
211 /// addSuccessor - Add succ as a successor of this MachineBasicBlock.
212 /// The Predecessors list of succ is automatically updated.
214 void addSuccessor(MachineBasicBlock *succ);
216 /// removeSuccessor - Remove successor from the successors list of this
217 /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
219 void removeSuccessor(MachineBasicBlock *succ);
221 /// removeSuccessor - Remove specified successor from the successors list of
222 /// this MachineBasicBlock. The Predecessors list of succ is automatically
223 /// updated. Return the iterator to the element after the one removed.
225 succ_iterator removeSuccessor(succ_iterator I);
227 /// transferSuccessors - Transfers all the successors from MBB to this
228 /// machine basic block (i.e., copies all the successors fromMBB and
229 /// remove all the successors fromBB).
230 void transferSuccessors(MachineBasicBlock *fromMBB);
232 /// isSuccessor - Return true if the specified MBB is a successor of this
234 bool isSuccessor(MachineBasicBlock *MBB) const;
236 /// getFirstTerminator - returns an iterator to the first terminator
237 /// instruction of this basic block. If a terminator does not exist,
239 iterator getFirstTerminator();
241 void pop_front() { Insts.pop_front(); }
242 void pop_back() { Insts.pop_back(); }
243 void push_back(MachineInstr *MI) { Insts.push_back(MI); }
244 template<typename IT>
245 void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); }
246 iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); }
248 // erase - Remove the specified element or range from the instruction list.
249 // These functions delete any instructions removed.
251 iterator erase(iterator I) { return Insts.erase(I); }
252 iterator erase(iterator I, iterator E) { return Insts.erase(I, E); }
253 MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); }
254 void clear() { Insts.clear(); }
256 /// splice - Take a block of instructions from MBB 'Other' in the range [From,
257 /// To), and insert them into this MBB right before 'where'.
258 void splice(iterator where, MachineBasicBlock *Other, iterator From,
260 Insts.splice(where, Other->Insts, From, To);
263 /// removeFromParent - This method unlinks 'this' from the containing
264 /// function, and returns it, but does not delete it.
265 MachineBasicBlock *removeFromParent();
267 /// eraseFromParent - This method unlinks 'this' from the containing
268 /// function and deletes it.
269 void eraseFromParent();
271 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
272 /// 'Old', change the code and CFG so that it branches to 'New' instead.
273 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
275 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in
276 /// the CFG to be inserted. If we have proven that MBB can only branch to
277 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and
278 /// DestB can be null. Besides DestA and DestB, retain other edges leading
279 /// to LandingPads (currently there can be only one; we don't check or require
280 /// that here). Note it is possible that DestA and/or DestB are LandingPads.
281 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
282 MachineBasicBlock *DestB,
285 // Debugging methods.
287 void print(std::ostream &OS) const;
288 void print(std::ostream *OS) const { if (OS) print(*OS); }
290 /// getNumber - MachineBasicBlocks are uniquely numbered at the function
291 /// level, unless they're not in a MachineFunction yet, in which case this
294 int getNumber() const { return Number; }
295 void setNumber(int N) { Number = N; }
297 private: // Methods used to maintain doubly linked list of blocks...
298 friend struct ilist_traits<MachineBasicBlock>;
300 // Machine-CFG mutators
302 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock.
303 /// Don't do this unless you know what you're doing, because it doesn't
304 /// update pred's successors list. Use pred->addSuccessor instead.
306 void addPredecessor(MachineBasicBlock *pred);
308 /// removePredecessor - Remove pred as a predecessor of this
309 /// MachineBasicBlock. Don't do this unless you know what you're
310 /// doing, because it doesn't update pred's successors list. Use
311 /// pred->removeSuccessor instead.
313 void removePredecessor(MachineBasicBlock *pred);
316 std::ostream& operator<<(std::ostream &OS, const MachineBasicBlock &MBB);
318 //===--------------------------------------------------------------------===//
319 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
320 //===--------------------------------------------------------------------===//
322 // Provide specializations of GraphTraits to be able to treat a
323 // MachineFunction as a graph of MachineBasicBlocks...
326 template <> struct GraphTraits<MachineBasicBlock *> {
327 typedef MachineBasicBlock NodeType;
328 typedef MachineBasicBlock::succ_iterator ChildIteratorType;
330 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
331 static inline ChildIteratorType child_begin(NodeType *N) {
332 return N->succ_begin();
334 static inline ChildIteratorType child_end(NodeType *N) {
335 return N->succ_end();
339 template <> struct GraphTraits<const MachineBasicBlock *> {
340 typedef const MachineBasicBlock NodeType;
341 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
343 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
344 static inline ChildIteratorType child_begin(NodeType *N) {
345 return N->succ_begin();
347 static inline ChildIteratorType child_end(NodeType *N) {
348 return N->succ_end();
352 // Provide specializations of GraphTraits to be able to treat a
353 // MachineFunction as a graph of MachineBasicBlocks... and to walk it
354 // in inverse order. Inverse order for a function is considered
355 // to be when traversing the predecessor edges of a MBB
356 // instead of the successor edges.
358 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
359 typedef MachineBasicBlock NodeType;
360 typedef MachineBasicBlock::pred_iterator ChildIteratorType;
361 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
364 static inline ChildIteratorType child_begin(NodeType *N) {
365 return N->pred_begin();
367 static inline ChildIteratorType child_end(NodeType *N) {
368 return N->pred_end();
372 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
373 typedef const MachineBasicBlock NodeType;
374 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
375 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
378 static inline ChildIteratorType child_begin(NodeType *N) {
379 return N->pred_begin();
381 static inline ChildIteratorType child_end(NodeType *N) {
382 return N->pred_end();
386 } // End llvm namespace