1 //===- LockstepReverseIterator.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 #ifndef LLVM_TRANSFORMS_UTILS_LOCKSTEPREVERSEITERATOR_H 10 #define LLVM_TRANSFORMS_UTILS_LOCKSTEPREVERSEITERATOR_H 11 12 #include "llvm/ADT/ArrayRef.h" 13 #include "llvm/ADT/SetVector.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/IR/BasicBlock.h" 16 #include "llvm/IR/Instruction.h" 17 18 namespace llvm { 19 20 struct NoActiveBlocksOption {}; 21 22 struct ActiveBlocksOption { 23 SmallSetVector<BasicBlock *, 4> ActiveBlocks; getActiveBlocksActiveBlocksOption24 SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; } 25 ActiveBlocksOption() = default; 26 }; 27 28 /// Iterates through instructions in a set of blocks in reverse order from the 29 /// first non-terminator. For example (assume all blocks have size n): 30 /// LockstepReverseIterator I([B1, B2, B3]); 31 /// *I-- = [B1[n], B2[n], B3[n]]; 32 /// *I-- = [B1[n-1], B2[n-1], B3[n-1]]; 33 /// *I-- = [B1[n-2], B2[n-2], B3[n-2]]; 34 /// ... 35 /// 36 /// The iterator continues processing until all blocks have been exhausted if \p 37 /// EarlyFailure is explicitly set to \c false. Use \c getActiveBlocks() to 38 /// determine which blocks are still going and the order they appear in the list 39 /// returned by operator*. 40 template <bool EarlyFailure = true> 41 class LockstepReverseIterator 42 : private std::conditional_t<EarlyFailure, NoActiveBlocksOption, 43 ActiveBlocksOption> { 44 private: 45 using Base = std::conditional_t<EarlyFailure, NoActiveBlocksOption, 46 ActiveBlocksOption>; 47 ArrayRef<BasicBlock *> Blocks; 48 SmallVector<Instruction *, 4> Insts; 49 bool Fail; 50 51 public: LockstepReverseIterator(ArrayRef<BasicBlock * > Blocks)52 LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) { 53 reset(); 54 } 55 reset()56 void reset() { 57 Fail = false; 58 if constexpr (!EarlyFailure) { 59 this->ActiveBlocks.clear(); 60 this->ActiveBlocks.insert_range(Blocks); 61 } 62 Insts.clear(); 63 for (BasicBlock *BB : Blocks) { 64 Instruction *Prev = BB->getTerminator()->getPrevNonDebugInstruction(); 65 if (!Prev) { 66 // Block wasn't big enough - only contained a terminator. 67 if constexpr (EarlyFailure) { 68 Fail = true; 69 return; 70 } else { 71 this->ActiveBlocks.remove(BB); 72 continue; 73 } 74 } 75 Insts.push_back(Prev); 76 } 77 if (Insts.empty()) 78 Fail = true; 79 } 80 isValid()81 bool isValid() const { return !Fail; } 82 ArrayRef<Instruction *> operator*() const { return Insts; } 83 84 // Note: This needs to return a SmallSetVector as the elements of 85 // ActiveBlocks will be later copied to Blocks using std::copy. The 86 // resultant order of elements in Blocks needs to be deterministic. 87 // Using SmallPtrSet instead causes non-deterministic order while 88 // copying. And we cannot simply sort Blocks as they need to match the 89 // corresponding Values. getActiveBlocks()90 SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { 91 return Base::getActiveBlocks(); 92 } 93 restrictToBlocks(SmallSetVector<BasicBlock *,4> & Blocks)94 void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) { 95 static_assert(!EarlyFailure, "Unknown method"); 96 for (auto It = Insts.begin(); It != Insts.end();) { 97 if (!Blocks.contains((*It)->getParent())) { 98 this->ActiveBlocks.remove((*It)->getParent()); 99 It = Insts.erase(It); 100 } else { 101 ++It; 102 } 103 } 104 } 105 106 LockstepReverseIterator &operator--() { 107 if (Fail) 108 return *this; 109 SmallVector<Instruction *, 4> NewInsts; 110 for (Instruction *Inst : Insts) { 111 Instruction *Prev = Inst->getPrevNonDebugInstruction(); 112 if (!Prev) { 113 if constexpr (!EarlyFailure) { 114 this->ActiveBlocks.remove(Inst->getParent()); 115 } else { 116 Fail = true; 117 return *this; 118 } 119 } else { 120 NewInsts.push_back(Prev); 121 } 122 } 123 if (NewInsts.empty()) 124 Fail = true; 125 else 126 Insts = NewInsts; 127 return *this; 128 } 129 130 LockstepReverseIterator &operator++() { 131 static_assert(EarlyFailure, "Unknown method"); 132 if (Fail) 133 return *this; 134 SmallVector<Instruction *, 4> NewInsts; 135 for (Instruction *Inst : Insts) { 136 Instruction *Next = Inst->getNextNonDebugInstruction(); 137 // Already at end of block. 138 if (!Next) { 139 Fail = true; 140 return *this; 141 } 142 NewInsts.push_back(Next); 143 } 144 if (NewInsts.empty()) 145 Fail = true; 146 else 147 Insts = NewInsts; 148 return *this; 149 } 150 }; 151 152 } // end namespace llvm 153 154 #endif // LLVM_TRANSFORMS_UTILS_LOCKSTEPREVERSEITERATOR_H 155