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