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
50namespace llvm {
51template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
52  Tokens.clear();
53  CI.clear();
54  ConvergenceKind = NoConvergence;
55}
56
57template <class ContextT>
58void GenericConvergenceVerifier<ContextT>::visit(const BlockT &BB) {
59  SeenFirstConvOp = false;
60}
61
62template <class ContextT>
63void 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
121template <class ContextT>
122void 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
131template <class ContextT>
132void 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