| //===- GenericConvergenceVerifierImpl.h -----------------------*- C++ -*---===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// |
| /// A verifier for the static rules of convergence control tokens that works |
| /// with both LLVM IR and MIR. |
| /// |
| /// This template implementation resides in a separate file so that it does not |
| /// get injected into every .cpp file that includes the generic header. |
| /// |
| /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO. |
| /// |
| /// This file should only be included by files that implement a |
| /// specialization of the relevant templates. Currently these are: |
| /// - llvm/lib/IR/Verifier.cpp |
| /// - llvm/lib/CodeGen/MachineVerifier.cpp |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |
| #define LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |
| |
| #include "llvm/ADT/GenericConvergenceVerifier.h" |
| #include "llvm/ADT/PostOrderIterator.h" |
| #include "llvm/ADT/Twine.h" |
| #include "llvm/IR/Intrinsics.h" |
| |
| using namespace llvm; |
| |
| #define Check(C, ...) \ |
| do { \ |
| if (!(C)) { \ |
| reportFailure(__VA_ARGS__); \ |
| return; \ |
| } \ |
| } while (false) |
| |
| #define CheckOrNull(C, ...) \ |
| do { \ |
| if (!(C)) { \ |
| reportFailure(__VA_ARGS__); \ |
| return {}; \ |
| } \ |
| } while (false) |
| |
| static bool isConvergenceControlIntrinsic(unsigned IntrinsicID) { |
| switch (IntrinsicID) { |
| default: |
| return false; |
| case Intrinsic::experimental_convergence_anchor: |
| case Intrinsic::experimental_convergence_entry: |
| case Intrinsic::experimental_convergence_loop: |
| return true; |
| } |
| } |
| |
| namespace llvm { |
| template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() { |
| Tokens.clear(); |
| CI.clear(); |
| ConvergenceKind = NoConvergence; |
| } |
| |
| template <class ContextT> |
| void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) { |
| auto ID = ContextT::getIntrinsicID(I); |
| auto *TokenDef = findAndCheckConvergenceTokenUsed(I); |
| |
| bool IsCtrlIntrinsic = true; |
| |
| switch (ID) { |
| case Intrinsic::experimental_convergence_entry: |
| Check(isInsideConvergentFunction(I), |
| "Entry intrinsic can occur only in a convergent function.", |
| {Context.print(&I)}); |
| Check(I.getParent()->isEntryBlock(), |
| "Entry intrinsic can occur only in the entry block.", |
| {Context.print(&I)}); |
| Check(I.getParent()->getFirstNonPHI() == &I, |
| "Entry intrinsic can occur only at the start of the basic block.", |
| {Context.print(&I)}); |
| LLVM_FALLTHROUGH; |
| case Intrinsic::experimental_convergence_anchor: |
| Check(!TokenDef, |
| "Entry or anchor intrinsic cannot have a convergencectrl token " |
| "operand.", |
| {Context.print(&I)}); |
| break; |
| case Intrinsic::experimental_convergence_loop: |
| Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand.", |
| {Context.print(&I)}); |
| Check(I.getParent()->getFirstNonPHI() == &I, |
| "Loop intrinsic can occur only at the start of the basic block.", |
| {Context.print(&I)}); |
| break; |
| default: |
| IsCtrlIntrinsic = false; |
| break; |
| } |
| |
| if (TokenDef || IsCtrlIntrinsic) { |
| Check(isConvergent(I), |
| "Convergence control token can only be used in a convergent call.", |
| {Context.print(&I)}); |
| Check(ConvergenceKind != UncontrolledConvergence, |
| "Cannot mix controlled and uncontrolled convergence in the same " |
| "function.", |
| {Context.print(&I)}); |
| ConvergenceKind = ControlledConvergence; |
| } else if (isConvergent(I)) { |
| Check(ConvergenceKind != ControlledConvergence, |
| "Cannot mix controlled and uncontrolled convergence in the same " |
| "function.", |
| {Context.print(&I)}); |
| ConvergenceKind = UncontrolledConvergence; |
| } |
| } |
| |
| template <class ContextT> |
| void GenericConvergenceVerifier<ContextT>::reportFailure( |
| const Twine &Message, ArrayRef<Printable> DumpedValues) { |
| FailureCB(Message); |
| if (OS) { |
| for (auto V : DumpedValues) |
| *OS << V << '\n'; |
| } |
| } |
| |
| template <class ContextT> |
| void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) { |
| assert(Context.getFunction()); |
| const auto &F = *Context.getFunction(); |
| |
| DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap; |
| DenseMap<const CycleT *, const InstructionT *> CycleHearts; |
| |
| // Just like the DominatorTree, compute the CycleInfo locally so that we |
| // can run the verifier outside of a pass manager and we don't rely on |
| // potentially out-dated analysis results. |
| CI.compute(const_cast<FunctionT &>(F)); |
| |
| auto checkToken = [&](const InstructionT *Token, const InstructionT *User, |
| SmallVectorImpl<const InstructionT *> &LiveTokens) { |
| Check(llvm::is_contained(LiveTokens, Token), |
| "Convergence region is not well-nested.", |
| {Context.print(Token), Context.print(User)}); |
| while (LiveTokens.back() != Token) |
| LiveTokens.pop_back(); |
| |
| // Check static rules about cycles. |
| auto *BB = User->getParent(); |
| auto *BBCycle = CI.getCycle(BB); |
| if (!BBCycle) |
| return; |
| |
| auto *DefBB = Token->getParent(); |
| if (DefBB == BB || BBCycle->contains(DefBB)) { |
| // degenerate occurrence of a loop intrinsic |
| return; |
| } |
| |
| Check(ContextT::getIntrinsicID(*User) == |
| Intrinsic::experimental_convergence_loop, |
| "Convergence token used by an instruction other than " |
| "llvm.experimental.convergence.loop in a cycle that does " |
| "not contain the token's definition.", |
| {Context.print(User), CI.print(BBCycle)}); |
| |
| while (true) { |
| auto *Parent = BBCycle->getParentCycle(); |
| if (!Parent || Parent->contains(DefBB)) |
| break; |
| BBCycle = Parent; |
| }; |
| |
| Check(BBCycle->isReducible() && BB == BBCycle->getHeader(), |
| "Cycle heart must dominate all blocks in the cycle.", |
| {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)}); |
| Check(!CycleHearts.count(BBCycle), |
| "Two static convergence token uses in a cycle that does " |
| "not contain either token's definition.", |
| {Context.print(User), Context.print(CycleHearts[BBCycle]), |
| CI.print(BBCycle)}); |
| CycleHearts[BBCycle] = User; |
| }; |
| |
| ReversePostOrderTraversal<const FunctionT *> RPOT(&F); |
| SmallVector<const InstructionT *, 8> LiveTokens; |
| for (auto *BB : RPOT) { |
| LiveTokens.clear(); |
| auto LTIt = LiveTokenMap.find(BB); |
| if (LTIt != LiveTokenMap.end()) { |
| LiveTokens = std::move(LTIt->second); |
| LiveTokenMap.erase(LTIt); |
| } |
| |
| for (auto &I : *BB) { |
| if (auto *Token = Tokens.lookup(&I)) |
| checkToken(Token, &I, LiveTokens); |
| if (isConvergenceControlIntrinsic(ContextT::getIntrinsicID(I))) |
| LiveTokens.push_back(&I); |
| } |
| |
| // Propagate token liveness |
| for (auto *Succ : successors(BB)) { |
| auto *SuccNode = DT.getNode(Succ); |
| auto LTIt = LiveTokenMap.find(Succ); |
| if (LTIt == LiveTokenMap.end()) { |
| // We're the first predecessor: all tokens which dominate the |
| // successor are live for now. |
| LTIt = LiveTokenMap.try_emplace(Succ).first; |
| for (auto LiveToken : LiveTokens) { |
| if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode)) |
| break; |
| LTIt->second.push_back(LiveToken); |
| } |
| } else { |
| // Compute the intersection of live tokens. |
| auto It = llvm::partition( |
| LTIt->second, [&LiveTokens](const InstructionT *Token) { |
| return llvm::is_contained(LiveTokens, Token); |
| }); |
| LTIt->second.erase(It, LTIt->second.end()); |
| } |
| } |
| } |
| } |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H |