Viewing file:  GenericConvergenceVerifierImpl.h (8.45 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
//===- 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/IntrinsicInst.h"
#define Check(C, ...) \
do { \
if (!(C)) { \
reportFailure(__VA_ARGS__); \
return; \
} \
} while (false)
#define CheckOrNull(C, ...) \
do { \
if (!(C)) { \
reportFailure(__VA_ARGS__); \
return {}; \
} \
} while (false)
namespace llvm {
template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
Tokens.clear();
CI.clear();
ConvergenceKind = NoConvergence;
}
template <class ContextT>
void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) {
SeenFirstConvOp = false;
}
template <class ContextT>
void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) {
ConvOpKind ConvOp = getConvOp(I);
auto *TokenDef = findAndCheckConvergenceTokenUsed(I);
switch (ConvOp) {
case CONV_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(!SeenFirstConvOp,
"Entry intrinsic cannot be preceded by a convergent operation in the "
"same basic block.",
{Context.print(&I)});
[[fallthrough]];
case CONV_ANCHOR:
Check(!TokenDef,
"Entry or anchor intrinsic cannot have a convergencectrl token "
"operand.",
{Context.print(&I)});
break;
case CONV_LOOP:
Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand.",
{Context.print(&I)});
Check(!SeenFirstConvOp,
"Loop intrinsic cannot be preceded by a convergent operation in the "
"same basic block.",
{Context.print(&I)});
break;
default:
break;
}
if (ConvOp != CONV_NONE)
checkConvergenceTokenProduced(I);
if (isConvergent(I))
SeenFirstConvOp = true;
if (TokenDef || ConvOp != CONV_NONE) {
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(DT.dominates(Token->getParent(), User->getParent()),
"Convergence control token must dominate all its uses.",
{Context.print(Token), Context.print(User)});
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(getConvOp(*User) == CONV_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 (getConvOp(I) != CONV_NONE)
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
|