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   /// Get the bundle iterator for the given instruction's bundle.
157   static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) {
158     return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI);
159   }
160 
161   reference operator*() const { return *MII; }
162   pointer operator->() const { return &operator*(); }
163 
164   /// Check for null.
165   bool isValid() const { return MII.getNodePtr(); }
166 
167   friend bool operator==(const MachineInstrBundleIterator &L,
168                          const MachineInstrBundleIterator &R) {
169     return L.MII == R.MII;
170   }
171   friend bool operator==(const MachineInstrBundleIterator &L,
172                          const const_instr_iterator &R) {
173     return L.MII == R; // Avoid assertion about validity of R.
174   }
175   friend bool operator==(const const_instr_iterator &L,
176                          const MachineInstrBundleIterator &R) {
177     return L == R.MII; // Avoid assertion about validity of L.
178   }
179   friend bool operator==(const MachineInstrBundleIterator &L,
180                          const nonconst_instr_iterator &R) {
181     return L.MII == R; // Avoid assertion about validity of R.
182   }
183   friend bool operator==(const nonconst_instr_iterator &L,
184                          const MachineInstrBundleIterator &R) {
185     return L == R.MII; // Avoid assertion about validity of L.
186   }
187   friend bool operator==(const MachineInstrBundleIterator &L, const_pointer R) {
188     return L == const_instr_iterator(R); // Avoid assertion about validity of R.
189   }
190   friend bool operator==(const_pointer L, const MachineInstrBundleIterator &R) {
191     return const_instr_iterator(L) == R; // Avoid assertion about validity of L.
192   }
193   friend bool operator==(const MachineInstrBundleIterator &L,
194                          const_reference R) {
195     return L == &R; // Avoid assertion about validity of R.
196   }
197   friend bool operator==(const_reference L,
198                          const MachineInstrBundleIterator &R) {
199     return &L == R; // Avoid assertion about validity of L.
200   }
201 
202   friend bool operator!=(const MachineInstrBundleIterator &L,
203                          const MachineInstrBundleIterator &R) {
204     return !(L == R);
205   }
206   friend bool operator!=(const MachineInstrBundleIterator &L,
207                          const const_instr_iterator &R) {
208     return !(L == R);
209   }
210   friend bool operator!=(const const_instr_iterator &L,
211                          const MachineInstrBundleIterator &R) {
212     return !(L == R);
213   }
214   friend bool operator!=(const MachineInstrBundleIterator &L,
215                          const nonconst_instr_iterator &R) {
216     return !(L == R);
217   }
218   friend bool operator!=(const nonconst_instr_iterator &L,
219                          const MachineInstrBundleIterator &R) {
220     return !(L == R);
221   }
222   friend bool operator!=(const MachineInstrBundleIterator &L, const_pointer R) {
223     return !(L == R);
224   }
225   friend bool operator!=(const_pointer L, const MachineInstrBundleIterator &R) {
226     return !(L == R);
227   }
228   friend bool operator!=(const MachineInstrBundleIterator &L,
229                          const_reference R) {
230     return !(L == R);
231   }
232   friend bool operator!=(const_reference L,
233                          const MachineInstrBundleIterator &R) {
234     return !(L == R);
235   }
236 
237   // Increment and decrement operators...
238   MachineInstrBundleIterator &operator--() {
239     this->decrement(MII);
240     return *this;
241   }
242   MachineInstrBundleIterator &operator++() {
243     this->increment(MII);
244     return *this;
245   }
246   MachineInstrBundleIterator operator--(int) {
247     MachineInstrBundleIterator Temp = *this;
248     --*this;
249     return Temp;
250   }
251   MachineInstrBundleIterator operator++(int) {
252     MachineInstrBundleIterator Temp = *this;
253     ++*this;
254     return Temp;
255   }
256 
257   instr_iterator getInstrIterator() const { return MII; }
258 
259   nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); }
260 
261   reverse_iterator getReverse() const { return MII.getReverse(); }
262 };
263 
264 } // end namespace llvm
265 
266 #endif
267