1 | //===- GenericConvergenceVerifierImpl.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 | /// \file |
10 | /// |
11 | /// A verifier for the static rules of convergence control tokens that works |
12 | /// with both LLVM IR and MIR. |
13 | /// |
14 | /// This template implementation resides in a separate file so that it does not |
15 | /// get injected into every .cpp file that includes the generic header. |
16 | /// |
17 | /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO. |
18 | /// |
19 | /// This file should only be included by files that implement a |
20 | /// specialization of the relevant templates. Currently these are: |
21 | /// - llvm/lib/IR/Verifier.cpp |
22 | /// - llvm/lib/CodeGen/MachineVerifier.cpp |
23 | /// |
24 | //===----------------------------------------------------------------------===// |
25 | |
26 | #ifndef LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |
27 | #define LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |
28 | |
29 | #include "llvm/ADT/GenericConvergenceVerifier.h" |
30 | #include "llvm/ADT/PostOrderIterator.h" |
31 | #include "llvm/ADT/Twine.h" |
32 | #include "llvm/IR/IntrinsicInst.h" |
33 | |
34 | #define Check(C, ...) \ |
35 | do { \ |
36 | if (!(C)) { \ |
37 | reportFailure(__VA_ARGS__); \ |
38 | return; \ |
39 | } \ |
40 | } while (false) |
41 | |
42 | #define CheckOrNull(C, ...) \ |
43 | do { \ |
44 | if (!(C)) { \ |
45 | reportFailure(__VA_ARGS__); \ |
46 | return {}; \ |
47 | } \ |
48 | } while (false) |
49 | |
50 | namespace llvm { |
51 | template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() { |
52 | Tokens.clear(); |
53 | CI.clear(); |
54 | ConvergenceKind = NoConvergence; |
55 | } |
56 | |
57 | template <class ContextT> |
58 | void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) { |
59 | SeenFirstConvOp = false; |
60 | } |
61 | |
62 | template <class ContextT> |
63 | void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) { |
64 | ConvOpKind ConvOp = getConvOp(I); |
65 | |
66 | auto *TokenDef = findAndCheckConvergenceTokenUsed(I); |
67 | switch (ConvOp) { |
68 | case CONV_ENTRY: |
69 | Check(isInsideConvergentFunction(I), |
70 | "Entry intrinsic can occur only in a convergent function." , |
71 | {Context.print(&I)}); |
72 | Check(I.getParent()->isEntryBlock(), |
73 | "Entry intrinsic can occur only in the entry block." , |
74 | {Context.print(&I)}); |
75 | Check(!SeenFirstConvOp, |
76 | "Entry intrinsic cannot be preceded by a convergent operation in the " |
77 | "same basic block." , |
78 | {Context.print(&I)}); |
79 | LLVM_FALLTHROUGH; |
80 | case CONV_ANCHOR: |
81 | Check(!TokenDef, |
82 | "Entry or anchor intrinsic cannot have a convergencectrl token " |
83 | "operand." , |
84 | {Context.print(&I)}); |
85 | break; |
86 | case CONV_LOOP: |
87 | Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand." , |
88 | {Context.print(&I)}); |
89 | Check(!SeenFirstConvOp, |
90 | "Loop intrinsic cannot be preceded by a convergent operation in the " |
91 | "same basic block." , |
92 | {Context.print(&I)}); |
93 | break; |
94 | default: |
95 | break; |
96 | } |
97 | |
98 | if (ConvOp != CONV_NONE) |
99 | checkConvergenceTokenProduced(I); |
100 | |
101 | if (isConvergent(I)) |
102 | SeenFirstConvOp = true; |
103 | |
104 | if (TokenDef || ConvOp != CONV_NONE) { |
105 | Check(isConvergent(I), |
106 | "Convergence control token can only be used in a convergent call." , |
107 | {Context.print(&I)}); |
108 | Check(ConvergenceKind != UncontrolledConvergence, |
109 | "Cannot mix controlled and uncontrolled convergence in the same " |
110 | "function." , |
111 | {Context.print(&I)}); |
112 | ConvergenceKind = ControlledConvergence; |
113 | } else if (isConvergent(I)) { |
114 | Check(ConvergenceKind != ControlledConvergence, |
115 | "Cannot mix controlled and uncontrolled convergence in the same " |
116 | "function." , |
117 | {Context.print(&I)}); |
118 | ConvergenceKind = UncontrolledConvergence; |
119 | } |
120 | } |
121 | |
122 | template <class ContextT> |
123 | void GenericConvergenceVerifier<ContextT>::reportFailure( |
124 | const Twine &Message, ArrayRef<Printable> DumpedValues) { |
125 | FailureCB(Message); |
126 | if (OS) { |
127 | for (auto V : DumpedValues) |
128 | *OS << V << '\n'; |
129 | } |
130 | } |
131 | |
132 | template <class ContextT> |
133 | void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) { |
134 | assert(Context.getFunction()); |
135 | const auto &F = *Context.getFunction(); |
136 | |
137 | DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap; |
138 | DenseMap<const CycleT *, const InstructionT *> CycleHearts; |
139 | |
140 | // Just like the DominatorTree, compute the CycleInfo locally so that we |
141 | // can run the verifier outside of a pass manager and we don't rely on |
142 | // potentially out-dated analysis results. |
143 | CI.compute(const_cast<FunctionT &>(F)); |
144 | |
145 | auto checkToken = [&](const InstructionT *Token, const InstructionT *User, |
146 | SmallVectorImpl<const InstructionT *> &LiveTokens) { |
147 | Check(DT.dominates(Token->getParent(), User->getParent()), |
148 | "Convergence control token must dominate all its uses." , |
149 | {Context.print(Token), Context.print(User)}); |
150 | |
151 | Check(llvm::is_contained(LiveTokens, Token), |
152 | "Convergence region is not well-nested." , |
153 | {Context.print(Token), Context.print(User)}); |
154 | while (LiveTokens.back() != Token) |
155 | LiveTokens.pop_back(); |
156 | |
157 | // Check static rules about cycles. |
158 | auto *BB = User->getParent(); |
159 | auto *BBCycle = CI.getCycle(BB); |
160 | if (!BBCycle) |
161 | return; |
162 | |
163 | auto *DefBB = Token->getParent(); |
164 | if (DefBB == BB || BBCycle->contains(DefBB)) { |
165 | // degenerate occurrence of a loop intrinsic |
166 | return; |
167 | } |
168 | |
169 | Check(getConvOp(*User) == CONV_LOOP, |
170 | "Convergence token used by an instruction other than " |
171 | "llvm.experimental.convergence.loop in a cycle that does " |
172 | "not contain the token's definition." , |
173 | {Context.print(User), CI.print(BBCycle)}); |
174 | |
175 | while (true) { |
176 | auto *Parent = BBCycle->getParentCycle(); |
177 | if (!Parent || Parent->contains(DefBB)) |
178 | break; |
179 | BBCycle = Parent; |
180 | }; |
181 | |
182 | Check(BBCycle->isReducible() && BB == BBCycle->getHeader(), |
183 | "Cycle heart must dominate all blocks in the cycle." , |
184 | {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)}); |
185 | Check(!CycleHearts.count(BBCycle), |
186 | "Two static convergence token uses in a cycle that does " |
187 | "not contain either token's definition." , |
188 | {Context.print(User), Context.print(CycleHearts[BBCycle]), |
189 | CI.print(BBCycle)}); |
190 | CycleHearts[BBCycle] = User; |
191 | }; |
192 | |
193 | ReversePostOrderTraversal<const FunctionT *> RPOT(&F); |
194 | SmallVector<const InstructionT *, 8> LiveTokens; |
195 | for (auto *BB : RPOT) { |
196 | LiveTokens.clear(); |
197 | auto LTIt = LiveTokenMap.find(BB); |
198 | if (LTIt != LiveTokenMap.end()) { |
199 | LiveTokens = std::move(LTIt->second); |
200 | LiveTokenMap.erase(LTIt); |
201 | } |
202 | |
203 | for (auto &I : *BB) { |
204 | if (auto *Token = Tokens.lookup(&I)) |
205 | checkToken(Token, &I, LiveTokens); |
206 | if (getConvOp(I) != CONV_NONE) |
207 | LiveTokens.push_back(&I); |
208 | } |
209 | |
210 | // Propagate token liveness |
211 | for (auto *Succ : successors(BB)) { |
212 | auto *SuccNode = DT.getNode(Succ); |
213 | auto LTIt = LiveTokenMap.find(Succ); |
214 | if (LTIt == LiveTokenMap.end()) { |
215 | // We're the first predecessor: all tokens which dominate the |
216 | // successor are live for now. |
217 | LTIt = LiveTokenMap.try_emplace(Succ).first; |
218 | for (auto LiveToken : LiveTokens) { |
219 | if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode)) |
220 | break; |
221 | LTIt->second.push_back(LiveToken); |
222 | } |
223 | } else { |
224 | // Compute the intersection of live tokens. |
225 | auto It = llvm::partition( |
226 | LTIt->second, [&LiveTokens](const InstructionT *Token) { |
227 | return llvm::is_contained(LiveTokens, Token); |
228 | }); |
229 | LTIt->second.erase(It, LTIt->second.end()); |
230 | } |
231 | } |
232 | } |
233 | } |
234 | |
235 | } // end namespace llvm |
236 | |
237 | #endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |
238 | |