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/Intrinsics.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 static bool isConvergenceControlIntrinsic(unsigned IntrinsicID) {
52   switch (IntrinsicID) {
53   default:
54     return false;
55   case Intrinsic::experimental_convergence_anchor:
56   case Intrinsic::experimental_convergence_entry:
57   case Intrinsic::experimental_convergence_loop:
58     return true;
59   }
60 }
61 
62 template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
63   Tokens.clear();
64   CI.clear();
65   ConvergenceKind = NoConvergence;
66 }
67 
68 template <class ContextT>
69 void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) {
70   SeenFirstConvOp = false;
71 }
72 
73 template <class ContextT>
74 void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) {
75   auto ID = ContextT::getIntrinsicID(I);
76   auto *TokenDef = findAndCheckConvergenceTokenUsed(I);
77   bool IsCtrlIntrinsic = true;
78 
79   switch (ID) {
80   case Intrinsic::experimental_convergence_entry:
81     Check(isInsideConvergentFunction(I),
82           "Entry intrinsic can occur only in a convergent function.",
83           {Context.print(&I)});
84     Check(I.getParent()->isEntryBlock(),
85           "Entry intrinsic can occur only in the entry block.",
86           {Context.print(&I)});
87     Check(!SeenFirstConvOp,
88           "Entry intrinsic cannot be preceded by a convergent operation in the "
89           "same basic block.",
90           {Context.print(&I)});
91     LLVM_FALLTHROUGH;
92   case Intrinsic::experimental_convergence_anchor:
93     Check(!TokenDef,
94           "Entry or anchor intrinsic cannot have a convergencectrl token "
95           "operand.",
96           {Context.print(&I)});
97     break;
98   case Intrinsic::experimental_convergence_loop:
99     Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand.",
100           {Context.print(&I)});
101     Check(!SeenFirstConvOp,
102           "Loop intrinsic cannot be preceded by a convergent operation in the "
103           "same basic block.",
104           {Context.print(&I)});
105     break;
106   default:
107     IsCtrlIntrinsic = false;
108     break;
109   }
110 
111   if (isConvergent(I))
112     SeenFirstConvOp = true;
113 
114   if (TokenDef || IsCtrlIntrinsic) {
115     Check(isConvergent(I),
116           "Convergence control token can only be used in a convergent call.",
117           {Context.print(&I)});
118     Check(ConvergenceKind != UncontrolledConvergence,
119           "Cannot mix controlled and uncontrolled convergence in the same "
120           "function.",
121           {Context.print(&I)});
122     ConvergenceKind = ControlledConvergence;
123   } else if (isConvergent(I)) {
124     Check(ConvergenceKind != ControlledConvergence,
125           "Cannot mix controlled and uncontrolled convergence in the same "
126           "function.",
127           {Context.print(&I)});
128     ConvergenceKind = UncontrolledConvergence;
129   }
130 }
131 
132 template <class ContextT>
133 void GenericConvergenceVerifier<ContextT>::reportFailure(
134     const Twine &Message, ArrayRef<Printable> DumpedValues) {
135   FailureCB(Message);
136   if (OS) {
137     for (auto V : DumpedValues)
138       *OS << V << '\n';
139   }
140 }
141 
142 template <class ContextT>
143 void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) {
144   assert(Context.getFunction());
145   const auto &F = *Context.getFunction();
146 
147   DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap;
148   DenseMap<const CycleT *, const InstructionT *> CycleHearts;
149 
150   // Just like the DominatorTree, compute the CycleInfo locally so that we
151   // can run the verifier outside of a pass manager and we don't rely on
152   // potentially out-dated analysis results.
153   CI.compute(const_cast<FunctionT &>(F));
154 
155   auto checkToken = [&](const InstructionT *Token, const InstructionT *User,
156                         SmallVectorImpl<const InstructionT *> &LiveTokens) {
157     Check(llvm::is_contained(LiveTokens, Token),
158           "Convergence region is not well-nested.",
159           {Context.print(Token), Context.print(User)});
160     while (LiveTokens.back() != Token)
161       LiveTokens.pop_back();
162 
163     // Check static rules about cycles.
164     auto *BB = User->getParent();
165     auto *BBCycle = CI.getCycle(BB);
166     if (!BBCycle)
167       return;
168 
169     auto *DefBB = Token->getParent();
170     if (DefBB == BB || BBCycle->contains(DefBB)) {
171       // degenerate occurrence of a loop intrinsic
172       return;
173     }
174 
175     Check(ContextT::getIntrinsicID(*User) ==
176               Intrinsic::experimental_convergence_loop,
177           "Convergence token used by an instruction other than "
178           "llvm.experimental.convergence.loop in a cycle that does "
179           "not contain the token's definition.",
180           {Context.print(User), CI.print(BBCycle)});
181 
182     while (true) {
183       auto *Parent = BBCycle->getParentCycle();
184       if (!Parent || Parent->contains(DefBB))
185         break;
186       BBCycle = Parent;
187     };
188 
189     Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),
190           "Cycle heart must dominate all blocks in the cycle.",
191           {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)});
192     Check(!CycleHearts.count(BBCycle),
193           "Two static convergence token uses in a cycle that does "
194           "not contain either token's definition.",
195           {Context.print(User), Context.print(CycleHearts[BBCycle]),
196            CI.print(BBCycle)});
197     CycleHearts[BBCycle] = User;
198   };
199 
200   ReversePostOrderTraversal<const FunctionT *> RPOT(&F);
201   SmallVector<const InstructionT *, 8> LiveTokens;
202   for (auto *BB : RPOT) {
203     LiveTokens.clear();
204     auto LTIt = LiveTokenMap.find(BB);
205     if (LTIt != LiveTokenMap.end()) {
206       LiveTokens = std::move(LTIt->second);
207       LiveTokenMap.erase(LTIt);
208     }
209 
210     for (auto &I : *BB) {
211       if (auto *Token = Tokens.lookup(&I))
212         checkToken(Token, &I, LiveTokens);
213       if (isConvergenceControlIntrinsic(ContextT::getIntrinsicID(I)))
214         LiveTokens.push_back(&I);
215     }
216 
217     // Propagate token liveness
218     for (auto *Succ : successors(BB)) {
219       auto *SuccNode = DT.getNode(Succ);
220       auto LTIt = LiveTokenMap.find(Succ);
221       if (LTIt == LiveTokenMap.end()) {
222         // We're the first predecessor: all tokens which dominate the
223         // successor are live for now.
224         LTIt = LiveTokenMap.try_emplace(Succ).first;
225         for (auto LiveToken : LiveTokens) {
226           if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))
227             break;
228           LTIt->second.push_back(LiveToken);
229         }
230       } else {
231         // Compute the intersection of live tokens.
232         auto It = llvm::partition(
233             LTIt->second, [&LiveTokens](const InstructionT *Token) {
234               return llvm::is_contained(LiveTokens, Token);
235             });
236         LTIt->second.erase(It, LTIt->second.end());
237       }
238     }
239   }
240 }
241 
242 } // end namespace llvm
243 
244 #endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
245