================ @@ -0,0 +1,1410 @@ +//===-- SPIRVStructurizer.cpp ----------------------*- 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 +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#include "Analysis/SPIRVConvergenceRegionAnalysis.h" +#include "SPIRV.h" +#include "SPIRVSubtarget.h" +#include "SPIRVTargetMachine.h" +#include "SPIRVUtils.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/CodeGen/IntrinsicLowering.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/IntrinsicsSPIRV.h" +#include "llvm/InitializePasses.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" +#include "llvm/Transforms/Utils/LowerMemIntrinsics.h" +#include <queue> +#include <stack> + +using namespace llvm; +using namespace SPIRV; + +namespace llvm { + +void initializeSPIRVStructurizerPass(PassRegistry &); + +namespace { + +using BlockSet = std::unordered_set<BasicBlock *>; +using Edge = std::pair<BasicBlock *, BasicBlock *>; + +// This class implements a partial ordering visitor, which visits a cyclic graph +// in natural topological-like ordering. Topological ordering is not defined for +// directed graphs with cycles, so this assumes cycles are a single node, and +// ignores back-edges. The cycle is visited from the entry in the same +// topological-like ordering. +// +// This means once we visit a node, we know all the possible ancestors have been +// visited. +// +// clang-format off +// +// Given this graph: +// +// ,-> B -\ +// A -+ +---> D ----> E -> F -> G -> H +// `-> C -/ ^ | +// +-----------------+ +// +// Visit order is: +// A, [B, C in any order], D, E, F, G, H +// +// clang-format on +// +// Changing the function CFG between the construction of the visitor and +// visiting is undefined. The visitor can be reused, but if the CFG is updated, +// the visitor must be rebuilt. +class PartialOrderingVisitor { + DomTreeBuilder::BBDomTree DT; + LoopInfo LI; + BlockSet Visited; + std::unordered_map<BasicBlock *, size_t> B2R; + std::vector<std::pair<BasicBlock *, size_t>> Order; + + // Get all basic-blocks reachable from Start. + BlockSet getReachableFrom(BasicBlock *Start) { + std::queue<BasicBlock *> ToVisit; + ToVisit.push(Start); + + BlockSet Output; + while (ToVisit.size() != 0) { + BasicBlock *BB = ToVisit.front(); + ToVisit.pop(); + + if (Output.count(BB) != 0) + continue; + Output.insert(BB); + + for (BasicBlock *Successor : successors(BB)) { + if (DT.dominates(Successor, BB)) + continue; + ToVisit.push(Successor); + } + } + + return Output; + } + + size_t visit(BasicBlock *BB, size_t Rank) { + if (Visited.count(BB) != 0) + return Rank; + + Loop *L = LI.getLoopFor(BB); + const bool isLoopHeader = LI.isLoopHeader(BB); + + if (B2R.count(BB) == 0) { + B2R.emplace(BB, Rank); + } else { + B2R[BB] = std::max(B2R[BB], Rank); + } + + for (BasicBlock *Predecessor : predecessors(BB)) { + if (isLoopHeader && L->contains(Predecessor)) { + continue; + } + + if (B2R.count(Predecessor) == 0) { + return Rank; + } + } + + Visited.insert(BB); + + SmallVector<BasicBlock *, 2> OtherSuccessors; + BasicBlock *LoopSuccessor = nullptr; + + for (BasicBlock *Successor : successors(BB)) { + // Ignoring back-edges. + if (DT.dominates(Successor, BB)) + continue; + + if (isLoopHeader && L->contains(Successor)) { + assert(LoopSuccessor == nullptr); + LoopSuccessor = Successor; + } else + OtherSuccessors.push_back(Successor); + } + + if (LoopSuccessor) + Rank = visit(LoopSuccessor, Rank + 1); + + size_t OutputRank = Rank; + for (BasicBlock *Item : OtherSuccessors) + OutputRank = std::max(OutputRank, visit(Item, Rank + 1)); + return OutputRank; + }; + +public: + // Build the visitor to operate on the function F. + PartialOrderingVisitor(Function &F) { + DT.recalculate(F); + LI = LoopInfo(DT); + + visit(&*F.begin(), 0); + + for (auto &[BB, Rank] : B2R) + Order.emplace_back(BB, Rank); + + std::sort(Order.begin(), Order.end(), [](const auto &LHS, const auto &RHS) { + return LHS.second < RHS.second; + }); + + for (size_t i = 0; i < Order.size(); i++) + B2R[Order[i].first] = i; + } + + // Visit the function starting from the basic block |Start|, and calling |Op| + // on each visited BB. This traversal ignores back-edges, meaning this won't + // visit a node to which |Start| is not an ancestor. + void partialOrderVisit(BasicBlock &Start, + std::function<bool(BasicBlock *)> Op) { + BlockSet Reachable = getReachableFrom(&Start); + assert(B2R.count(&Start) != 0); + size_t Rank = Order[B2R[&Start]].second; + + auto It = Order.begin(); + while (It != Order.end() && It->second < Rank) + ++It; + + if (It == Order.end()) + return; + + size_t EndRank = Order.rbegin()->second + 1; + for (; It != Order.end() && It->second <= EndRank; ++It) { + if (Reachable.count(It->first) == 0) { + continue; + } + + if (!Op(It->first)) { + EndRank = It->second; + } + } + } +}; + +// Helper function to do a partial order visit from the block |Start|, calling +// |Op| on each visited node. +void partialOrderVisit(BasicBlock &Start, + std::function<bool(BasicBlock *)> Op) { + PartialOrderingVisitor V(*Start.getParent()); + V.partialOrderVisit(Start, Op); +} + +// Returns the exact convergence region in the tree defined by `Node` for which +// `BB` is the header, nullptr otherwise. +const ConvergenceRegion *getRegionForHeader(const ConvergenceRegion *Node, + BasicBlock *BB) { + if (Node->Entry == BB) + return Node; + + for (auto *Child : Node->Children) { + const auto *CR = getRegionForHeader(Child, BB); + if (CR != nullptr) + return CR; + } + return nullptr; +} + +// Returns the single BasicBlock exiting the convergence region `CR`, +// nullptr if no such exit exists. F must be the function CR belongs to. ---------------- Keenuts wrote:
An old parameter, cleaned up thanks! https://github.com/llvm/llvm-project/pull/107408 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
