1 //===- llvm/CodeGen/MachineInstrBundleIterator.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 // Defines an iterator class that bundles MachineInstr.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
15 #define LLVM_CODEGEN_MACHINEINSTRBUNDLEITERATOR_H
16 
17 #include "llvm/ADT/ilist.h"
18 #include <iterator>
19 
20 namespace llvm {
21 
22 template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits;
23 template <class T> struct MachineInstrBundleIteratorTraits<T, false> {
24   typedef simple_ilist<T, ilist_sentinel_tracking<true>> list_type;
25   typedef typename list_type::iterator instr_iterator;
26   typedef typename list_type::iterator nonconst_instr_iterator;
27   typedef typename list_type::const_iterator const_instr_iterator;
28 };
29 template <class T> struct MachineInstrBundleIteratorTraits<T, true> {
30   typedef simple_ilist<T, ilist_sentinel_tracking<true>> list_type;
31   typedef typename list_type::reverse_iterator instr_iterator;
32   typedef typename list_type::reverse_iterator nonconst_instr_iterator;
33   typedef typename list_type::const_reverse_iterator const_instr_iterator;
34 };
35 template <class T> struct MachineInstrBundleIteratorTraits<const T, false> {
36   typedef simple_ilist<T, ilist_sentinel_tracking<true>> list_type;
37   typedef typename list_type::const_iterator instr_iterator;
38   typedef typename list_type::iterator nonconst_instr_iterator;
39   typedef typename list_type::const_iterator const_instr_iterator;
40 };
41 template <class T> struct MachineInstrBundleIteratorTraits<const T, true> {
42   typedef simple_ilist<T, ilist_sentinel_tracking<true>> list_type;
43   typedef typename list_type::const_reverse_iterator instr_iterator;
44   typedef typename list_type::reverse_iterator nonconst_instr_iterator;
45   typedef typename list_type::const_reverse_iterator const_instr_iterator;
46 };
47 
48 template <bool IsReverse> struct MachineInstrBundleIteratorHelper;
49 template <> struct MachineInstrBundleIteratorHelper<false> {
50   /// Get the beginning of the current bundle.
51   template <class Iterator> static Iterator getBundleBegin(Iterator I) {
52     if (!I.isEnd())
53       while (I->isBundledWithPred())
54         --I;
55     return I;
56   }
57 
58   /// Get the final node of the current bundle.
59   template <class Iterator> static Iterator getBundleFinal(Iterator I) {
60     if (!I.isEnd())
61       while (I->isBundledWithSucc())
62         ++I;
63     return I;
64   }
65 
66   /// Increment forward ilist iterator.
67   template <class Iterator> static void increment(Iterator &I) {
68     I = std::next(getBundleFinal(I));
69   }
70 
71   /// Decrement forward ilist iterator.
72   template <class Iterator> static void decrement(Iterator &I) {
73     I = getBundleBegin(std::prev(I));
74   }
75 };
76 
77 template <> struct MachineInstrBundleIteratorHelper<true> {
78   /// Get the beginning of the current bundle.
79   template <class Iterator> static Iterator getBundleBegin(Iterator I) {
80     return MachineInstrBundleIteratorHelper<false>::getBundleBegin(
81                I.getReverse())
82         .getReverse();
83   }
84 
85   /// Get the final node of the current bundle.
86   template <class Iterator> static Iterator getBundleFinal(Iterator I) {
87     return MachineInstrBundleIteratorHelper<false>::getBundleFinal(
88                I.getReverse())
89         .getReverse();
90   }
91 
92   /// Increment reverse ilist iterator.
93   template <class Iterator> static void increment(Iterator &I) {
94     I = getBundleBegin(std::next(I));
95   }
96 
97   /// Decrement reverse ilist iterator.
98   template <class Iterator> static void decrement(Iterator &I) {
99     I = std::prev(getBundleFinal(I));
100   }
101 };
102 
103 /// MachineBasicBlock iterator that automatically skips over MIs that are
104 /// inside bundles (i.e. walk top level MIs only).
105 template <typename Ty, bool IsReverse = false>
106 class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> {
107   typedef MachineInstrBundleIteratorTraits<Ty, IsReverse> Traits;
108   typedef typename Traits::instr_iterator instr_iterator;
109   instr_iterator MII;
110 
111 public:
112   typedef typename instr_iterator::value_type value_type;
113   typedef typename instr_iterator::difference_type difference_type;
114   typedef typename instr_iterator::pointer pointer;
115   typedef typename instr_iterator::reference reference;
116   typedef std::bidirectional_iterator_tag iterator_category;
117 
118   typedef typename instr_iterator::const_pointer const_pointer;
119   typedef typename instr_iterator::const_reference const_reference;
120 
121 private:
122   typedef typename Traits::nonconst_instr_iterator nonconst_instr_iterator;
123   typedef typename Traits::const_instr_iterator const_instr_iterator;
124   typedef MachineInstrBundleIterator<
125       typename nonconst_instr_iterator::value_type, IsReverse>
126       nonconst_iterator;
127   typedef MachineInstrBundleIterator<Ty, !IsReverse> reverse_iterator;
128 
129 public:
130   MachineInstrBundleIterator(instr_iterator MI) : MII(MI) {
131     assert((!MI.getNodePtr() || MI.isEnd() || !MI->isBundledWithPred()) &&
132            "It's not legal to initialize MachineInstrBundleIterator with a "
133            "bundled MI");
134   }
135 
136   MachineInstrBundleIterator(reference MI) : MII(MI) {
137     assert(!MI.isBundledWithPred() && "It's not legal to initialize "
138                                       "MachineInstrBundleIterator with a "
139                                       "bundled MI");
140   }
141   MachineInstrBundleIterator(pointer MI) : MII(MI) {
142     // FIXME: This conversion should be explicit.
143     assert((!MI || !MI->isBundledWithPred()) && "It's not legal to initialize "
144                                                 "MachineInstrBundleIterator "
145                                                 "with a bundled MI");
146   }
147   // Template allows conversion from const to nonconst.
148   template <class OtherTy>
149   MachineInstrBundleIterator(
150       const MachineInstrBundleIterator<OtherTy, IsReverse> &I,
151       typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value,
152                               void *>::type = nullptr)
153       : MII(I.getInstrIterator()) {}
154   MachineInstrBundleIterator() : MII(nullptr) {}
155 
156   /// Explicit conversion between forward/reverse iterators.
157   ///
158   /// Translate between forward and reverse iterators without changing range
159   /// boundaries.  The resulting iterator will dereference (and have a handle)
160   /// to the previous node, which is somewhat unexpected; but converting the
161   /// two endpoints in a range will give the same range in reverse.
162   ///
163   /// This matches std::reverse_iterator conversions.
164   explicit MachineInstrBundleIterator(
165       const MachineInstrBundleIterator<Ty, !IsReverse> &I)
166       : MachineInstrBundleIterator(++I.getReverse()) {}
167 
168   /// Get the bundle iterator for the given instruction's bundle.
169   static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) {
170     return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI);
171   }
172 
173   reference operator*() const { return *MII; }
174   pointer operator->() const { return &operator*(); }
175 
176   /// Check for null.
177   bool isValid() const { return MII.getNodePtr(); }
178 
179   friend bool operator==(const MachineInstrBundleIterator &L,
180                          const MachineInstrBundleIterator &R) {
181     return L.MII == R.MII;
182   }
183   friend bool operator==(const MachineInstrBundleIterator &L,
184                          const const_instr_iterator &R) {
185     return L.MII == R; // Avoid assertion about validity of R.
186   }
187   friend bool operator==(const const_instr_iterator &L,
188                          const MachineInstrBundleIterator &R) {
189     return L == R.MII; // Avoid assertion about validity of L.
190   }
191   friend bool operator==(const MachineInstrBundleIterator &L,
192                          const nonconst_instr_iterator &R) {
193     return L.MII == R; // Avoid assertion about validity of R.
194   }
195   friend bool operator==(const nonconst_instr_iterator &L,
196                          const MachineInstrBundleIterator &R) {
197     return L == R.MII; // Avoid assertion about validity of L.
198   }
199   friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) {
200     return L == const_instr_iterator(R); // Avoid assertion about validity of R.
201   }
202   friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) {
203     return const_instr_iterator(L) == R; // Avoid assertion about validity of L.
204   }
205   friend bool operator==(const MachineInstrBundleIterator &L,
206                          const_reference R) {
207     return L == &R; // Avoid assertion about validity of R.
208   }
209   friend bool operator==(const_reference L,
210                          const MachineInstrBundleIterator &R) {
211     return &L == R; // Avoid assertion about validity of L.
212   }
213 
214   friend bool operator!=(const MachineInstrBundleIterator &L,
215                          const MachineInstrBundleIterator &R) {
216     return !(L == R);
217   }
218   friend bool operator!=(const MachineInstrBundleIterator &L,
219                          const const_instr_iterator &R) {
220     return !(L == R);
221   }
222   friend bool operator!=(const const_instr_iterator &L,
223                          const MachineInstrBundleIterator &R) {
224     return !(L == R);
225   }
226   friend bool operator!=(const MachineInstrBundleIterator &L,
227                          const nonconst_instr_iterator &R) {
228     return !(L == R);
229   }
230   friend bool operator!=(const nonconst_instr_iterator &L,
231                          const MachineInstrBundleIterator &R) {
232     return !(L == R);
233   }
234   friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) {
235     return !(L == R);
236   }
237   friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) {
238     return !(L == R);
239   }
240   friend bool operator!=(const MachineInstrBundleIterator &L,
241                          const_reference R) {
242     return !(L == R);
243   }
244   friend bool operator!=(const_reference L,
245                          const MachineInstrBundleIterator &R) {
246     return !(L == R);
247   }
248 
249   // Increment and decrement operators...
250   MachineInstrBundleIterator &operator--() {
251     this->decrement(MII);
252     return *this;
253   }
254   MachineInstrBundleIterator &operator++() {
255     this->increment(MII);
256     return *this;
257   }
258   MachineInstrBundleIterator operator--(int) {
259     MachineInstrBundleIterator Temp = *this;
260     --*this;
261     return Temp;
262   }
263   MachineInstrBundleIterator operator++(int) {
264     MachineInstrBundleIterator Temp = *this;
265     ++*this;
266     return Temp;
267   }
268 
269   instr_iterator getInstrIterator() const { return MII; }
270 
271   nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); }
272 
273   /// Get a reverse iterator to the same node.
274   ///
275   /// Gives a reverse iterator that will dereference (and have a handle) to the
276   /// same node.  Converting the endpoint iterators in a range will give a
277   /// different range; for range operations, use the explicit conversions.
278   reverse_iterator getReverse() const { return MII.getReverse(); }
279 };
280 
281 } // end namespace llvm
282 
283 #endif
284