diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -418,7 +418,7 @@ void initializeStripNonDebugSymbolsPass(PassRegistry&); void initializeStripNonLineTableDebugLegacyPassPass(PassRegistry &); void initializeStripSymbolsPass(PassRegistry&); -void initializeStructurizeCFGPass(PassRegistry&); +void initializeStructurizeCFGLegacyPassPass(PassRegistry &); void initializeTailCallElimPass(PassRegistry&); void initializeTailDuplicatePass(PassRegistry&); void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/Scalar/StructurizeCFG.h b/llvm/include/llvm/Transforms/Scalar/StructurizeCFG.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/StructurizeCFG.h @@ -0,0 +1,20 @@ +//===- StructurizeCFG.h ---------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_STRUCTURIZECFG_H +#define LLVM_TRANSFORMS_SCALAR_STRUCTURIZECFG_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { +struct StructurizeCFGPass : PassInfoMixin { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_STRUCTURIZECFG_H diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -191,6 +191,7 @@ #include "llvm/Transforms/Scalar/Sink.h" #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h" #include "llvm/Transforms/Scalar/SpeculativeExecution.h" +#include "llvm/Transforms/Scalar/StructurizeCFG.h" #include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Scalar/WarnMissedTransforms.h" #include "llvm/Transforms/Utils/AddDiscriminators.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -287,6 +287,7 @@ FUNCTION_PASS("spec-phis", SpeculateAroundPHIsPass()) FUNCTION_PASS("sroa", SROA()) FUNCTION_PASS("strip-gc-relocates", StripGCRelocates()) +FUNCTION_PASS("structurizecfg", StructurizeCFGPass()) FUNCTION_PASS("tailcallelim", TailCallElimPass()) FUNCTION_PASS("unify-loop-exits", UnifyLoopExitsPass()) FUNCTION_PASS("vector-combine", VectorCombinePass()) diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -97,7 +97,7 @@ initializeSCCPLegacyPassPass(Registry); initializeSROALegacyPassPass(Registry); initializeCFGSimplifyPassPass(Registry); - initializeStructurizeCFGPass(Registry); + initializeStructurizeCFGLegacyPassPass(Registry); initializeSimpleLoopUnswitchLegacyPassPass(Registry); initializeSinkingLegacyPassPass(Registry); initializeTailCallElimPass(Registry); diff --git a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp --- a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp +++ b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/StructurizeCFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SCCIterator.h" @@ -28,6 +29,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" @@ -233,9 +235,8 @@ /// while the true side continues the general flow. So the loop condition /// consist of a network of PHI nodes where the true incoming values expresses /// breaks and the false values expresses continue states. -class StructurizeCFG : public RegionPass { - bool SkipUniformRegions; +class StructurizeCFG { Type *Boolean; ConstantInt *BoolTrue; ConstantInt *BoolFalse; @@ -244,7 +245,7 @@ Function *Func; Region *ParentRegion; - LegacyDivergenceAnalysis *DA; + LegacyDivergenceAnalysis *DA = nullptr; DominatorTree *DT; SmallVector Order; @@ -308,20 +309,36 @@ void rebuildSSA(); +public: + void init(Region *R); + bool run(Region *R, DominatorTree *DT); + bool makeUniformRegion(Region *R, LegacyDivergenceAnalysis *DA); +}; + +class StructurizeCFGLegacyPass : public RegionPass { + bool SkipUniformRegions; + public: static char ID; - explicit StructurizeCFG(bool SkipUniformRegions_ = false) - : RegionPass(ID), - SkipUniformRegions(SkipUniformRegions_) { + explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false) + : RegionPass(ID), SkipUniformRegions(SkipUniformRegions_) { if (ForceSkipUniformRegions.getNumOccurrences()) SkipUniformRegions = ForceSkipUniformRegions.getValue(); - initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); + initializeStructurizeCFGLegacyPassPass(*PassRegistry::getPassRegistry()); } - bool doInitialization(Region *R, RGPassManager &RGM) override; - - bool runOnRegion(Region *R, RGPassManager &RGM) override; + bool runOnRegion(Region *R, RGPassManager &RGM) override { + StructurizeCFG SCFG; + SCFG.init(R); + if (SkipUniformRegions) { + LegacyDivergenceAnalysis *DA = &getAnalysis(); + if (SCFG.makeUniformRegion(R, DA)) + return false; + } + DominatorTree *DT = &getAnalysis().getDomTree(); + return SCFG.run(R, DT); + } StringRef getPassName() const override { return "Structurize control flow"; } @@ -338,28 +355,16 @@ } // end anonymous namespace -char StructurizeCFG::ID = 0; +char StructurizeCFGLegacyPass::ID = 0; -INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", - false, false) +INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg", + "Structurize the CFG", false, false) INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) -INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", - false, false) - -/// Initialize the types and constants used in the pass -bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { - LLVMContext &Context = R->getEntry()->getContext(); - - Boolean = Type::getInt1Ty(Context); - BoolTrue = ConstantInt::getTrue(Context); - BoolFalse = ConstantInt::getFalse(Context); - BoolUndef = UndefValue::get(Boolean); - - return false; -} +INITIALIZE_PASS_END(StructurizeCFGLegacyPass, "structurizecfg", + "Structurize the CFG", false, false) /// Build up the general order of nodes, by performing a topological sort of the /// parent region's nodes, while ensuring that there is no outer cycle node @@ -1003,48 +1008,62 @@ return SubRegionsAreUniform || (ConditionalDirectChildren <= 1); } -/// Run the transformation for each region found -bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { +void StructurizeCFG::init(Region *R) { + LLVMContext &Context = R->getEntry()->getContext(); + + Boolean = Type::getInt1Ty(Context); + BoolTrue = ConstantInt::getTrue(Context); + BoolFalse = ConstantInt::getFalse(Context); + BoolUndef = UndefValue::get(Boolean); + + this->DA = nullptr; +} + +bool StructurizeCFG::makeUniformRegion(Region *R, + LegacyDivergenceAnalysis *DA) { if (R->isTopLevelRegion()) return false; - DA = nullptr; - - if (SkipUniformRegions) { - // TODO: We could probably be smarter here with how we handle sub-regions. - // We currently rely on the fact that metadata is set by earlier invocations - // of the pass on sub-regions, and that this metadata doesn't get lost -- - // but we shouldn't rely on metadata for correctness! - unsigned UniformMDKindID = - R->getEntry()->getContext().getMDKindID("structurizecfg.uniform"); - DA = &getAnalysis(); - - if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) { - LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R - << '\n'); - - // Mark all direct child block terminators as having been treated as - // uniform. To account for a possible future in which non-uniform - // sub-regions are treated more cleverly, indirect children are not - // marked as uniform. - MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {}); - for (RegionNode *E : R->elements()) { - if (E->isSubRegion()) - continue; - - if (Instruction *Term = E->getEntry()->getTerminator()) - Term->setMetadata(UniformMDKindID, MD); - } + this->DA = DA; + // TODO: We could probably be smarter here with how we handle sub-regions. + // We currently rely on the fact that metadata is set by earlier invocations + // of the pass on sub-regions, and that this metadata doesn't get lost -- + // but we shouldn't rely on metadata for correctness! + unsigned UniformMDKindID = + R->getEntry()->getContext().getMDKindID("structurizecfg.uniform"); + + if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) { + LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R + << '\n'); + + // Mark all direct child block terminators as having been treated as + // uniform. To account for a possible future in which non-uniform + // sub-regions are treated more cleverly, indirect children are not + // marked as uniform. + MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {}); + for (RegionNode *E : R->elements()) { + if (E->isSubRegion()) + continue; - return false; + if (Instruction *Term = E->getEntry()->getTerminator()) + Term->setMetadata(UniformMDKindID, MD); } + + return true; } + return false; +} + +/// Run the transformation for each region found +bool StructurizeCFG::run(Region *R, DominatorTree *DT) { + if (R->isTopLevelRegion()) + return false; + + this->DT = DT; Func = R->getEntry()->getParent(); ParentRegion = R; - DT = &getAnalysis().getDomTree(); - orderNodes(); collectInfos(); createFlow(); @@ -1069,5 +1088,33 @@ } Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) { - return new StructurizeCFG(SkipUniformRegions); + return new StructurizeCFGLegacyPass(SkipUniformRegions); +} + +static void addRegionIntoQueue(Region &R, std::vector &Regions) { + Regions.push_back(&R); + for (const auto &E : R) + addRegionIntoQueue(*E, Regions); +} + +PreservedAnalyses StructurizeCFGPass::run(Function &F, + FunctionAnalysisManager &AM) { + + bool Changed = false; + DominatorTree *DT = &AM.getResult(F); + auto &RI = AM.getResult(F); + std::vector Regions; + addRegionIntoQueue(*RI.getTopLevelRegion(), Regions); + while (!Regions.empty()) { + Region *R = Regions.back(); + StructurizeCFG SCFG; + SCFG.init(R); + Changed |= SCFG.run(R, DT); + Regions.pop_back(); + } + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve(); + return PA; } diff --git a/llvm/test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll b/llvm/test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll --- a/llvm/test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll +++ b/llvm/test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -mtriple=amdgcn-- -S -o - -structurizecfg -structurizecfg-skip-uniform-regions -structurizecfg-relaxed-uniform-regions < %s | FileCheck %s +; RUN: opt -mtriple=amdgcn-- -S -o - -structurizecfg -structurizecfg-skip-uniform-regions -structurizecfg-relaxed-uniform-regions -enable-new-pm=0 < %s | FileCheck %s define amdgpu_cs void @uniform(i32 inreg %v) { ; CHECK-LABEL: @uniform( diff --git a/llvm/test/Transforms/StructurizeCFG/interleaved-loop-order.ll b/llvm/test/Transforms/StructurizeCFG/interleaved-loop-order.ll --- a/llvm/test/Transforms/StructurizeCFG/interleaved-loop-order.ll +++ b/llvm/test/Transforms/StructurizeCFG/interleaved-loop-order.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S -structurizecfg %s -o - | FileCheck %s +; RUN: opt -S -lowerswitch -structurizecfg %s -o - | FileCheck %s ; This test have an outer loop containing an inner loop, ; for which there is an interleaved post-order traversal. diff --git a/llvm/test/Transforms/StructurizeCFG/nested-loop-order.ll b/llvm/test/Transforms/StructurizeCFG/nested-loop-order.ll --- a/llvm/test/Transforms/StructurizeCFG/nested-loop-order.ll +++ b/llvm/test/Transforms/StructurizeCFG/nested-loop-order.ll @@ -1,4 +1,5 @@ ; RUN: opt -S -structurizecfg %s -o - | FileCheck %s +; RUN: opt -S -passes=structurizecfg %s -o - | FileCheck %s define void @main(float addrspace(1)* %out) { diff --git a/llvm/test/Transforms/StructurizeCFG/switch.ll b/llvm/test/Transforms/StructurizeCFG/switch.ll --- a/llvm/test/Transforms/StructurizeCFG/switch.ll +++ b/llvm/test/Transforms/StructurizeCFG/switch.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -structurizecfg %s -o - | FileCheck %s +; RUN: opt -S -structurizecfg %s -o - -enable-new-pm=0 | FileCheck %s ; The structurizecfg pass cannot handle switch instructions, so we need to ; make sure the lower switch pass is always run before structurizecfg.