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