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