llvm/IR/GenericConvergenceVerifierImpl.h

0001 //===- GenericConvergenceVerifierImpl.h -----------------------*- C++ -*---===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 ///
0011 /// A verifier for the static rules of convergence control tokens that works
0012 /// with both LLVM IR and MIR.
0013 ///
0014 /// This template implementation resides in a separate file so that it does not
0015 /// get injected into every .cpp file that includes the generic header.
0016 ///
0017 /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
0018 ///
0019 /// This file should only be included by files that implement a
0020 /// specialization of the relevant templates. Currently these are:
0021 /// - llvm/lib/IR/Verifier.cpp
0022 /// - llvm/lib/CodeGen/MachineVerifier.cpp
0023 ///
0024 //===----------------------------------------------------------------------===//
0025
0026 #ifndef LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
0027 #define LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
0028
0029 #include "llvm/ADT/GenericConvergenceVerifier.h"
0030 #include "llvm/ADT/PostOrderIterator.h"
0031 #include "llvm/ADT/Twine.h"
0032 #include "llvm/IR/IntrinsicInst.h"
0033
0034 #define Check(C, ...)                                                          \
0035   do {                                                                         \
0036     if (!(C)) {                                                                \
0037       reportFailure(__VA_ARGS__);                                              \
0038       return;                                                                  \
0039     }                                                                          \
0040   } while (false)
0041
0042 #define CheckOrNull(C, ...)                                                    \
0043   do {                                                                         \
0044     if (!(C)) {                                                                \
0045       reportFailure(__VA_ARGS__);                                              \
0046       return {};                                                               \
0047     }                                                                          \
0048   } while (false)
0049
0050 namespace llvm {
0051 template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
0052   Tokens.clear();
0053   CI.clear();
0054   ConvergenceKind = NoConvergence;
0055 }
0056
0057 template <class ContextT>
0058 void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) {
0059   SeenFirstConvOp = false;
0060 }
0061
0062 template <class ContextT>
0063 void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) {
0064   ConvOpKind ConvOp = getConvOp(I);
0065
0066   auto *TokenDef = findAndCheckConvergenceTokenUsed(I);
0067   switch (ConvOp) {
0068   case CONV_ENTRY:
0069     Check(isInsideConvergentFunction(I),
0070           "Entry intrinsic can occur only in a convergent function.",
0071           {Context.print(&I)});
0072     Check(I.getParent()->isEntryBlock(),
0073           "Entry intrinsic can occur only in the entry block.",
0074           {Context.print(&I)});
0075     Check(!SeenFirstConvOp,
0076           "Entry intrinsic cannot be preceded by a convergent operation in the "
0077           "same basic block.",
0078           {Context.print(&I)});
0079     [[fallthrough]];
0080   case CONV_ANCHOR:
0081     Check(!TokenDef,
0082           "Entry or anchor intrinsic cannot have a convergencectrl token "
0083           "operand.",
0084           {Context.print(&I)});
0085     break;
0086   case CONV_LOOP:
0087     Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand.",
0088           {Context.print(&I)});
0089     Check(!SeenFirstConvOp,
0090           "Loop intrinsic cannot be preceded by a convergent operation in the "
0091           "same basic block.",
0092           {Context.print(&I)});
0093     break;
0094   default:
0095     break;
0096   }
0097
0098   if (ConvOp != CONV_NONE)
0099     checkConvergenceTokenProduced(I);
0100
0101   if (isConvergent(I))
0102     SeenFirstConvOp = true;
0103
0104   if (TokenDef || ConvOp != CONV_NONE) {
0105     Check(isConvergent(I),
0106           "Convergence control token can only be used in a convergent call.",
0107           {Context.print(&I)});
0108     Check(ConvergenceKind != UncontrolledConvergence,
0109           "Cannot mix controlled and uncontrolled convergence in the same "
0110           "function.",
0111           {Context.print(&I)});
0112     ConvergenceKind = ControlledConvergence;
0113   } else if (isConvergent(I)) {
0114     Check(ConvergenceKind != ControlledConvergence,
0115           "Cannot mix controlled and uncontrolled convergence in the same "
0116           "function.",
0117           {Context.print(&I)});
0118     ConvergenceKind = UncontrolledConvergence;
0119   }
0120 }
0121
0122 template <class ContextT>
0123 void GenericConvergenceVerifier<ContextT>::reportFailure(
0124     const Twine &Message, ArrayRef<Printable> DumpedValues) {
0125   FailureCB(Message);
0126   if (OS) {
0127     for (auto V : DumpedValues)
0128       *OS << V << '\n';
0129   }
0130 }
0131
0132 template <class ContextT>
0133 void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) {
0134   assert(Context.getFunction());
0135   const auto &F = *Context.getFunction();
0136
0137   DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap;
0138   DenseMap<const CycleT *, const InstructionT *> CycleHearts;
0139
0140   // Just like the DominatorTree, compute the CycleInfo locally so that we
0141   // can run the verifier outside of a pass manager and we don't rely on
0142   // potentially out-dated analysis results.
0143   CI.compute(const_cast<FunctionT &>(F));
0144
0145   auto checkToken = [&](const InstructionT *Token, const InstructionT *User,
0146                         SmallVectorImpl<const InstructionT *> &LiveTokens) {
0147     Check(DT.dominates(Token->getParent(), User->getParent()),
0148           "Convergence control token must dominate all its uses.",
0149           {Context.print(Token), Context.print(User)});
0150
0151     Check(llvm::is_contained(LiveTokens, Token),
0152           "Convergence region is not well-nested.",
0153           {Context.print(Token), Context.print(User)});
0154     while (LiveTokens.back() != Token)
0155       LiveTokens.pop_back();
0156
0157     // Check static rules about cycles.
0158     auto *BB = User->getParent();
0159     auto *BBCycle = CI.getCycle(BB);
0160     if (!BBCycle)
0161       return;
0162
0163     auto *DefBB = Token->getParent();
0164     if (DefBB == BB || BBCycle->contains(DefBB)) {
0165       // degenerate occurrence of a loop intrinsic
0166       return;
0167     }
0168
0169     Check(getConvOp(*User) == CONV_LOOP,
0170           "Convergence token used by an instruction other than "
0171           "llvm.experimental.convergence.loop in a cycle that does "
0172           "not contain the token's definition.",
0173           {Context.print(User), CI.print(BBCycle)});
0174
0175     while (true) {
0176       auto *Parent = BBCycle->getParentCycle();
0177       if (!Parent || Parent->contains(DefBB))
0178         break;
0179       BBCycle = Parent;
0180     };
0181
0182     Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),
0183           "Cycle heart must dominate all blocks in the cycle.",
0184           {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)});
0185     Check(!CycleHearts.count(BBCycle),
0186           "Two static convergence token uses in a cycle that does "
0187           "not contain either token's definition.",
0188           {Context.print(User), Context.print(CycleHearts[BBCycle]),
0189            CI.print(BBCycle)});
0190     CycleHearts[BBCycle] = User;
0191   };
0192
0193   ReversePostOrderTraversal<const FunctionT *> RPOT(&F);
0194   SmallVector<const InstructionT *, 8> LiveTokens;
0195   for (auto *BB : RPOT) {
0196     LiveTokens.clear();
0197     auto LTIt = LiveTokenMap.find(BB);
0198     if (LTIt != LiveTokenMap.end()) {
0199       LiveTokens = std::move(LTIt->second);
0200       LiveTokenMap.erase(LTIt);
0201     }
0202
0203     for (auto &I : *BB) {
0204       if (auto *Token = Tokens.lookup(&I))
0205         checkToken(Token, &I, LiveTokens);
0206       if (getConvOp(I) != CONV_NONE)
0207         LiveTokens.push_back(&I);
0208     }
0209
0210     // Propagate token liveness
0211     for (auto *Succ : successors(BB)) {
0212       auto *SuccNode = DT.getNode(Succ);
0213       auto [LTIt, Inserted] = LiveTokenMap.try_emplace(Succ);
0214       if (Inserted) {
0215         // We're the first predecessor: all tokens which dominate the
0216         // successor are live for now.
0217         for (auto LiveToken : LiveTokens) {
0218           if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))
0219             break;
0220           LTIt->second.push_back(LiveToken);
0221         }
0222       } else {
0223         // Compute the intersection of live tokens.
0224         auto It = llvm::partition(
0225             LTIt->second, [&LiveTokens](const InstructionT *Token) {
0226               return llvm::is_contained(LiveTokens, Token);
0227             });
0228         LTIt->second.erase(It, LTIt->second.end());
0229       }
0230     }
0231   }
0232 }
0233
0234 } // end namespace llvm
0235
0236 #endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H