LLVM 19.0.0git
GenericConvergenceVerifierImpl.h
Go to the documentation of this file.
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
31#include "llvm/ADT/Twine.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
50namespace llvm {
51template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
52 Tokens.clear();
53 CI.clear();
54 ConvergenceKind = NoConvergence;
55}
56
57template <class ContextT>
59 SeenFirstConvOp = false;
60}
61
62template <class ContextT>
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)});
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
122template <class ContextT>
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
132template <class ContextT>
134 assert(Context.getFunction());
135 const auto &F = *Context.getFunction();
136
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,
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
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
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:301
#define Check(C,...)
A verifier for the static rules of convergence control tokens that works with both LLVM IR and MIR.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
typename ContextT::InstructionT InstructionT
typename ContextT::DominatorTreeT DominatorTreeT
typename ContextT::FunctionT FunctionT
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1935
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879