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