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 22 namespace llvm { 23 24 template <class T, bool IsReverse> struct MachineInstrBundleIteratorTraits; 25 template <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 }; 31 template <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 }; 37 template <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 }; 43 template <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 50 template <bool IsReverse> struct MachineInstrBundleIteratorHelper; 51 template <> 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 79 template <> 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). 107 template <typename Ty, bool IsReverse = false> 108 class MachineInstrBundleIterator : MachineInstrBundleIteratorHelper<IsReverse> { 109 using Traits = MachineInstrBundleIteratorTraits<Ty, IsReverse>; 110 using instr_iterator = typename Traits::instr_iterator; 111 112 instr_iterator MII; 113 114 public: 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 123 private: 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 131 public: 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 std::enable_if_t<std::is_convertible<OtherTy *, Ty *>::value, void *> = 156 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