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
18namespace llvm {
19
20struct NoActiveBlocksOption {};
21
22struct ActiveBlocksOption {
23 SmallSetVector<BasicBlock *, 4> ActiveBlocks;
24 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*.
40template <bool EarlyFailure = true>
41class LockstepReverseIterator
42 : private std::conditional_t<EarlyFailure, NoActiveBlocksOption,
43 ActiveBlocksOption> {
44private:
45 using Base = std::conditional_t<EarlyFailure, NoActiveBlocksOption,
46 ActiveBlocksOption>;
47 ArrayRef<BasicBlock *> Blocks;
48 SmallVector<Instruction *, 4> Insts;
49 bool Fail;
50
51public:
52 LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
53 reset();
54 }
55
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()->getPrevNode();
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(Elt: Prev);
76 }
77 if (Insts.empty())
78 Fail = true;
79 }
80
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.
90 SmallSetVector<BasicBlock *, 4> &getActiveBlocks() {
91 return Base::getActiveBlocks();
92 }
93
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(key: (*It)->getParent())) {
98 this->ActiveBlocks.remove((*It)->getParent());
99 It = Insts.erase(CI: 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->getPrevNode();
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(Elt: 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->getNextNode();
137 // Already at end of block.
138 if (!Next) {
139 Fail = true;
140 return *this;
141 }
142 NewInsts.push_back(Elt: 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