File: SPIRVConvergenceRegionAnalysis.h

package info (click to toggle)
llvm-toolchain-19 1%3A19.1.7-3
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 1,998,520 kB
  • sloc: cpp: 6,951,680; ansic: 1,486,157; asm: 913,598; python: 232,024; f90: 80,126; objc: 75,281; lisp: 37,276; pascal: 16,990; sh: 10,009; ml: 5,058; perl: 4,724; awk: 3,523; makefile: 3,167; javascript: 2,504; xml: 892; fortran: 664; cs: 573
file content (176 lines) | stat: -rw-r--r-- 6,087 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//===- SPIRVConvergenceRegionAnalysis.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
//
//===----------------------------------------------------------------------===//
//
// The analysis determines the convergence region for each basic block of
// the module, and provides a tree-like structure describing the region
// hierarchy.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H
#define LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H

#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include <iostream>
#include <optional>
#include <unordered_set>

namespace llvm {
class SPIRVSubtarget;
class MachineFunction;
class MachineModuleInfo;

namespace SPIRV {

// Returns the first convergence intrinsic found in |BB|, |nullopt| otherwise.
std::optional<IntrinsicInst *> getConvergenceToken(BasicBlock *BB);
std::optional<const IntrinsicInst *> getConvergenceToken(const BasicBlock *BB);

// Describes a hierarchy of convergence regions.
// A convergence region defines a CFG for which the execution flow can diverge
// starting from the entry block, but should reconverge back before the end of
// the exit blocks.
class ConvergenceRegion {
  DominatorTree &DT;
  LoopInfo &LI;

public:
  // The parent region of this region, if any.
  ConvergenceRegion *Parent = nullptr;
  // The sub-regions contained in this region, if any.
  SmallVector<ConvergenceRegion *> Children = {};
  // The convergence instruction linked to this region, if any.
  std::optional<IntrinsicInst *> ConvergenceToken = std::nullopt;
  // The only block with a predecessor outside of this region.
  BasicBlock *Entry = nullptr;
  // All the blocks with an edge leaving this convergence region.
  SmallPtrSet<BasicBlock *, 2> Exits = {};
  // All the blocks that belongs to this region, including its subregions'.
  SmallPtrSet<BasicBlock *, 8> Blocks = {};

  // Creates a single convergence region encapsulating the whole function |F|.
  ConvergenceRegion(DominatorTree &DT, LoopInfo &LI, Function &F);

  // Creates a single convergence region defined by entry and exits nodes, a
  // list of blocks, and possibly a convergence token.
  ConvergenceRegion(DominatorTree &DT, LoopInfo &LI,
                    std::optional<IntrinsicInst *> ConvergenceToken,
                    BasicBlock *Entry, SmallPtrSet<BasicBlock *, 8> &&Blocks,
                    SmallPtrSet<BasicBlock *, 2> &&Exits);

  ConvergenceRegion(ConvergenceRegion &&CR)
      : DT(CR.DT), LI(CR.LI), Parent(std::move(CR.Parent)),
        Children(std::move(CR.Children)),
        ConvergenceToken(std::move(CR.ConvergenceToken)),
        Entry(std::move(CR.Entry)), Exits(std::move(CR.Exits)),
        Blocks(std::move(CR.Blocks)) {}

  ConvergenceRegion(const ConvergenceRegion &other) = delete;

  // Returns true if the given basic block belongs to this region, or to one of
  // its subregion.
  bool contains(const BasicBlock *BB) const { return Blocks.count(BB) != 0; }

  void releaseMemory();

  // Write to the debug output this region's hierarchy.
  // |IndentSize| defines the number of tabs to print before any new line.
  void dump(const unsigned IndentSize = 0) const;
};

// Holds a ConvergenceRegion hierarchy.
class ConvergenceRegionInfo {
  // The convergence region this structure holds.
  ConvergenceRegion *TopLevelRegion;

public:
  ConvergenceRegionInfo() : TopLevelRegion(nullptr) {}

  // Creates a new ConvergenceRegionInfo. Ownership of the TopLevelRegion is
  // passed to this object.
  ConvergenceRegionInfo(ConvergenceRegion *TopLevelRegion)
      : TopLevelRegion(TopLevelRegion) {}

  ~ConvergenceRegionInfo() { releaseMemory(); }

  ConvergenceRegionInfo(ConvergenceRegionInfo &&LHS)
      : TopLevelRegion(LHS.TopLevelRegion) {
    if (TopLevelRegion != LHS.TopLevelRegion) {
      releaseMemory();
      TopLevelRegion = LHS.TopLevelRegion;
    }
    LHS.TopLevelRegion = nullptr;
  }

  ConvergenceRegionInfo &operator=(ConvergenceRegionInfo &&LHS) {
    if (TopLevelRegion != LHS.TopLevelRegion) {
      releaseMemory();
      TopLevelRegion = LHS.TopLevelRegion;
    }
    LHS.TopLevelRegion = nullptr;
    return *this;
  }

  void releaseMemory() {
    if (TopLevelRegion == nullptr)
      return;

    TopLevelRegion->releaseMemory();
    delete TopLevelRegion;
    TopLevelRegion = nullptr;
  }

  const ConvergenceRegion *getTopLevelRegion() const { return TopLevelRegion; }
};

} // namespace SPIRV

// Wrapper around the function above to use it with the legacy pass manager.
class SPIRVConvergenceRegionAnalysisWrapperPass : public FunctionPass {
  SPIRV::ConvergenceRegionInfo CRI;

public:
  static char ID;

  SPIRVConvergenceRegionAnalysisWrapperPass();

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesAll();
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addRequired<DominatorTreeWrapperPass>();
  };

  bool runOnFunction(Function &F) override;

  SPIRV::ConvergenceRegionInfo &getRegionInfo() { return CRI; }
  const SPIRV::ConvergenceRegionInfo &getRegionInfo() const { return CRI; }
};

// Wrapper around the function above to use it with the new pass manager.
class SPIRVConvergenceRegionAnalysis
    : public AnalysisInfoMixin<SPIRVConvergenceRegionAnalysis> {
  friend AnalysisInfoMixin<SPIRVConvergenceRegionAnalysis>;
  static AnalysisKey Key;

public:
  using Result = SPIRV::ConvergenceRegionInfo;

  Result run(Function &F, FunctionAnalysisManager &AM);
};

namespace SPIRV {
ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT,
                                            LoopInfo &LI);
} // namespace SPIRV

} // namespace llvm
#endif // LLVM_LIB_TARGET_SPIRV_SPIRVCONVERGENCEREGIONANALYSIS_H