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 {
clear()51 template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
52 Tokens.clear();
53 CI.clear();
54 ConvergenceKind = NoConvergence;
55 }
56
57 template <class ContextT>
visit(const BlockT & BB)58 void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) {
59 SeenFirstConvOp = false;
60 }
61
62 template <class ContextT>
visit(const InstructionT & I)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 [[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(ConvergenceKind != UncontrolledConvergence,
106 "Cannot mix controlled and uncontrolled convergence in the same "
107 "function.",
108 {Context.print(&I)});
109 ConvergenceKind = ControlledConvergence;
110 } else if (isConvergent(I)) {
111 Check(ConvergenceKind != ControlledConvergence,
112 "Cannot mix controlled and uncontrolled convergence in the same "
113 "function.",
114 {Context.print(&I)});
115 ConvergenceKind = UncontrolledConvergence;
116 }
117 }
118
119 template <class ContextT>
reportFailure(const Twine & Message,ArrayRef<Printable> DumpedValues)120 void GenericConvergenceVerifier<ContextT>::reportFailure(
121 const Twine &Message, ArrayRef<Printable> DumpedValues) {
122 FailureCB(Message);
123 if (OS) {
124 for (auto V : DumpedValues)
125 *OS << V << '\n';
126 }
127 }
128
129 template <class ContextT>
verify(const DominatorTreeT & DT)130 void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) {
131 assert(Context.getFunction());
132 const auto &F = *Context.getFunction();
133
134 DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap;
135 DenseMap<const CycleT *, const InstructionT *> CycleHearts;
136
137 // Just like the DominatorTree, compute the CycleInfo locally so that we
138 // can run the verifier outside of a pass manager and we don't rely on
139 // potentially out-dated analysis results.
140 CI.compute(const_cast<FunctionT &>(F));
141
142 auto checkToken = [&](const InstructionT *Token, const InstructionT *User,
143 SmallVectorImpl<const InstructionT *> &LiveTokens) {
144 Check(DT.dominates(Token->getParent(), User->getParent()),
145 "Convergence control token must dominate all its uses.",
146 {Context.print(Token), Context.print(User)});
147
148 Check(llvm::is_contained(LiveTokens, Token),
149 "Convergence region is not well-nested.",
150 {Context.print(Token), Context.print(User)});
151 while (LiveTokens.back() != Token)
152 LiveTokens.pop_back();
153
154 // Check static rules about cycles.
155 auto *BB = User->getParent();
156 auto *BBCycle = CI.getCycle(BB);
157 if (!BBCycle)
158 return;
159
160 auto *DefBB = Token->getParent();
161 if (DefBB == BB || BBCycle->contains(DefBB)) {
162 // degenerate occurrence of a loop intrinsic
163 return;
164 }
165
166 Check(getConvOp(*User) == CONV_LOOP,
167 "Convergence token used by an instruction other than "
168 "llvm.experimental.convergence.loop in a cycle that does "
169 "not contain the token's definition.",
170 {Context.print(User), CI.print(BBCycle)});
171
172 while (true) {
173 auto *Parent = BBCycle->getParentCycle();
174 if (!Parent || Parent->contains(DefBB))
175 break;
176 BBCycle = Parent;
177 };
178
179 Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),
180 "Cycle heart must dominate all blocks in the cycle.",
181 {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)});
182 Check(!CycleHearts.count(BBCycle),
183 "Two static convergence token uses in a cycle that does "
184 "not contain either token's definition.",
185 {Context.print(User), Context.print(CycleHearts[BBCycle]),
186 CI.print(BBCycle)});
187 CycleHearts[BBCycle] = User;
188 };
189
190 ReversePostOrderTraversal<const FunctionT *> RPOT(&F);
191 SmallVector<const InstructionT *, 8> LiveTokens;
192 for (auto *BB : RPOT) {
193 LiveTokens.clear();
194 auto LTIt = LiveTokenMap.find(BB);
195 if (LTIt != LiveTokenMap.end()) {
196 LiveTokens = std::move(LTIt->second);
197 LiveTokenMap.erase(LTIt);
198 }
199
200 for (auto &I : *BB) {
201 if (auto *Token = Tokens.lookup(&I))
202 checkToken(Token, &I, LiveTokens);
203 if (getConvOp(I) != CONV_NONE)
204 LiveTokens.push_back(&I);
205 }
206
207 // Propagate token liveness
208 for (auto *Succ : successors(BB)) {
209 auto *SuccNode = DT.getNode(Succ);
210 auto [LTIt, Inserted] = LiveTokenMap.try_emplace(Succ);
211 if (Inserted) {
212 // We're the first predecessor: all tokens which dominate the
213 // successor are live for now.
214 for (auto LiveToken : LiveTokens) {
215 if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))
216 break;
217 LTIt->second.push_back(LiveToken);
218 }
219 } else {
220 // Compute the intersection of live tokens.
221 auto It = llvm::partition(
222 LTIt->second, [&LiveTokens](const InstructionT *Token) {
223 return llvm::is_contained(LiveTokens, Token);
224 });
225 LTIt->second.erase(It, LTIt->second.end());
226 }
227 }
228 }
229 }
230
231 } // end namespace llvm
232
233 #endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
234