SPIRVConvergenceRegionAnalysis.cpp Source File (original) (raw)

21#include

22#include

24#define DEBUG_TYPE "spirv-convergence-region-analysis"

26using namespace llvm;

28namespace llvm {

30}

33 "convergence-region",

34 "SPIRV convergence regions analysis", true, true)

42namespace llvm {

44namespace {

46template <typename BasicBlockType, typename IntrinsicInstType>

47std::optional<IntrinsicInstType *>

48getConvergenceTokenInternal(BasicBlockType *BB) {

49 static_assert(std::is_const_v ==

50 std::is_const_v,

51 "Constness must match between input and output.");

52 static_assert(std::is_same_v<BasicBlock, std::remove_const_t>,

53 "Input must be a basic block.");

54 static_assert(

55 std::is_same_v<IntrinsicInst, std::remove_const_t>,

56 "Output type must be an intrinsic instruction.");

58 for (auto &I : *BB) {

59 if (auto *CI = dyn_cast(&I)) {

62 assert(CI->isLoop() ||

64 return CI;

65 }

67 if (auto *CI = dyn_cast(&I)) {

69 if (!OB.has_value())

70 continue;

71 return dyn_cast(OB.value().Inputs[0]);

72 }

73 }

75 return std::nullopt;

76}

86 while (Candidate != NextCandidate && NextCandidate != nullptr) {

87 Candidate = NextCandidate;

88 NextCandidate = nullptr;

91 if (Candidate->Children.size() == 0)

92 return Candidate;

94 for (auto *Child : Candidate->Children) {

95 if (Child->Blocks.count(Entry) != 0) {

96 NextCandidate = Child;

97 break;

98 }

99 }

100 }

101

102 return Candidate;

103}

104

105}

106

108 return getConvergenceTokenInternal<BasicBlock, IntrinsicInst>(BB);

109}

110

112 return getConvergenceTokenInternal<const BasicBlock, const IntrinsicInst>(BB);

113}

114

117 : DT(DT), LI(LI), Parent(nullptr) {

118 Entry = &F.getEntryBlock();

120 for (auto &B : F) {

122 if (isa(B.getTerminator()))

124 }

125}

126

129 std::optional<IntrinsicInst *> ConvergenceToken, BasicBlock *Entry,

131 : DT(DT), LI(LI), ConvergenceToken(ConvergenceToken), Entry(Entry),

133 for ([[maybe_unused]] auto *BB : this->Exits)

135 assert(this->Blocks.count(this->Entry) != 0);

136}

137

139

141 for (auto *Child : Children) {

143 delete Child;

144 }

146}

147

149 const std::string Indent(IndentSize, '\t');

150 dbgs() << Indent << this << ": {\n";

151 dbgs() << Indent << " Parent: " << Parent << "\n";

152

154 dbgs() << Indent

155 << " ConvergenceToken: " << ConvergenceToken.value()->getName()

156 << "\n";

157 }

158

161 else

162 dbgs() << Indent << " Entry: " << Entry << "\n";

163

164 dbgs() << Indent << " Exits: { ";

165 for (const auto &Exit : Exits) {

166 if (Exit->getName() != "")

167 dbgs() << Exit->getName() << ", ";

168 else

169 dbgs() << Exit << ", ";

170 }

171 dbgs() << " }\n";

172

173 dbgs() << Indent << " Blocks: { ";

175 if (Block->getName() != "")

176 dbgs() << Block->getName() << ", ";

177 else

179 }

180 dbgs() << " }\n";

181

182 dbgs() << Indent << " Children: {\n";

183 for (const auto Child : Children)

184 Child->dump(IndentSize + 2);

185 dbgs() << Indent << " }\n";

186

187 dbgs() << Indent << "}\n";

188}

189

191

192public:

194 : DT(DT), LI(LI), F(F) {}

195

196private:

198 if (From == To)

199 return true;

200

201

202

203

204

206 return false;

207

209 if (L->contains(From) && L->isLoopLatch(From))

210 return true;

211

212 return false;

213 }

214

215 std::unordered_set<BasicBlock *>

217 std::function<bool(const BasicBlock *)> isMatch) const {

218 std::unordered_set<BasicBlock *> Output;

219

220 if (isMatch(From))

221 Output.insert(From);

222

223 auto *Terminator = From->getTerminator();

224 for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) {

225 auto *To = Terminator->getSuccessor(i);

226

227 if (isBackEdge(From, To))

228 continue;

229

230 auto ChildSet = findPathsToMatch(LI, To, isMatch);

231 if (ChildSet.size() == 0)

232 continue;

233

234 Output.insert(ChildSet.begin(), ChildSet.end());

235 Output.insert(From);

238 for (auto *BB : L->getBlocks()) {

239 Output.insert(BB);

240 }

241 }

242 }

243

244 return Output;

245 }

246

250

251 for (auto *B : RegionBlocks) {

253 for (unsigned i = 0; i < Terminator->getNumSuccessors(); ++i) {

254 auto *Child = Terminator->getSuccessor(i);

255 if (RegionBlocks.count(Child) == 0)

257 }

258 }

259

260 return Exits;

261 }

262

263public:

266 std::queue<Loop *> ToProcess;

268 ToProcess.push(L);

269

270 while (ToProcess.size() != 0) {

271 auto *L = ToProcess.front();

272 ToProcess.pop();

273

276 L->block_end());

278 L->getExitingBlocks(LoopExits);

279 if (CT.has_value()) {

280 for (auto *Exit : LoopExits) {

281 auto N = findPathsToMatch(LI, Exit, [&CT](const BasicBlock *block) {

283 if (Token == std::nullopt)

284 return false;

285 return Token.value() == CT.value();

286 });

287 RegionBlocks.insert(N.begin(), N.end());

288 }

289 }

290

291 auto RegionExits = findExitNodes(RegionBlocks);

293 DT, LI, CT, L->getHeader(), std::move(RegionBlocks),

294 std::move(RegionExits));

295 Region->Parent = findParentRegion(TopLevelRegion, Region->Entry);

296 assert(Region->Parent != nullptr && "This is impossible.");

298 }

299

301 }

302

303private:

307};

308

312 return Analyzer.analyze();

313}

314

315}

316

318

322

324 DominatorTree &DT = getAnalysis().getDomTree();

325 LoopInfo &LI = getAnalysis().getLoopInfo();

326

328

329 return false;

330}

331

338 return CRI;

339}

340

341AnalysisKey SPIRVConvergenceRegionAnalysis::Key;

342

343}

BlockVerifier::State From

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

DenseMap< Block *, BlockRelaxAux > Blocks

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

convergence SPIRV convergence regions true

convergence SPIRV convergence regions analysis

unify loop Fixup each natural loop to have a single exit block

A container for analyses that lazily runs them and caches their results.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM Basic Block Representation.

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

FunctionPass class - This class is used to implement most global optimizations.

Analysis pass that exposes the LoopInfo for a function.

bool isLoopHeader(const BlockT *BB) const

SmallVector< LoopT *, 4 > getLoopsInPreorder() const

Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

SPIRVConvergenceRegionAnalysisWrapperPass()

Result run(Function &F, FunctionAnalysisManager &AM)

ConvergenceRegionAnalyzer(Function &F, DominatorTree &DT, LoopInfo &LI)

ConvergenceRegionInfo analyze()

SmallVector< ConvergenceRegion * > Children

SmallPtrSet< BasicBlock *, 2 > Exits

std::optional< IntrinsicInst * > ConvergenceToken

ConvergenceRegion * Parent

void dump(const unsigned IndentSize=0) const

ConvergenceRegion(DominatorTree &DT, LoopInfo &LI, Function &F)

SmallPtrSet< BasicBlock *, 8 > Blocks

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef getName() const

Return a constant reference to the value's name.

ConvergenceRegionInfo getConvergenceRegions(Function &F, DominatorTree &DT, LoopInfo &LI)

std::optional< IntrinsicInst * > getConvergenceToken(BasicBlock *BB)

This is an optimization pass for GlobalISel generic memory operations.

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

void initializeSPIRVConvergenceRegionAnalysisWrapperPassPass(PassRegistry &)

Implement std::hash so that hash_code can be used in STL containers.

A special type used by analysis passes to provide an address that identifies that particular analysis...