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 [[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