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 @@ -264,7 +264,7 @@ void initializeLowerWidenableConditionLegacyPassPass(PassRegistry&); void initializeLowerIntrinsicsPass(PassRegistry&); void initializeLowerInvokeLegacyPassPass(PassRegistry&); -void initializeLowerSwitchPass(PassRegistry&); +void initializeLowerSwitchLegacyPassPass(PassRegistry &); void initializeLowerTypeTestsPass(PassRegistry&); void initializeLowerMatrixIntrinsicsLegacyPassPass(PassRegistry &); void initializeLowerMatrixIntrinsicsMinimalLegacyPassPass(PassRegistry &); diff --git a/llvm/include/llvm/Transforms/Utils/LowerSwitch.h b/llvm/include/llvm/Transforms/Utils/LowerSwitch.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Utils/LowerSwitch.h @@ -0,0 +1,26 @@ +//===- LowerSwitch.h - Eliminate Switch instructions ----------------------===// +// +// 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 LowerSwitch transformation rewrites switch instructions with a sequence +// of branches, which allows targets to get away with not implementing the +// switch instruction until it is convenient. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LOWERSWITCH_H +#define LLVM_TRANSFORMS_UTILS_LOWERSWITCH_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { +struct LowerSwitchPass : public PassInfoMixin { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} // namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOWERSWITCH_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 @@ -193,6 +193,7 @@ #include "llvm/Transforms/Utils/LoopSimplify.h" #include "llvm/Transforms/Utils/LoopVersioning.h" #include "llvm/Transforms/Utils/LowerInvoke.h" +#include "llvm/Transforms/Utils/LowerSwitch.h" #include "llvm/Transforms/Utils/Mem2Reg.h" #include "llvm/Transforms/Utils/NameAnonGlobals.h" #include "llvm/Transforms/Utils/SymbolRewriter.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 @@ -220,6 +220,7 @@ FUNCTION_PASS("loop-sink", LoopSinkPass()) FUNCTION_PASS("loop-unroll-and-jam", LoopUnrollAndJamPass()) FUNCTION_PASS("lowerinvoke", LowerInvokePass()) +FUNCTION_PASS("lowerswitch", LowerSwitchPass()) FUNCTION_PASS("mem2reg", PromotePass()) FUNCTION_PASS("memcpyopt", MemCpyOptPass()) FUNCTION_PASS("mergeicmps", MergeICmpsPass()) 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 @@ -343,7 +343,7 @@ INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) -INITIALIZE_PASS_DEPENDENCY(LowerSwitch) +INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", diff --git a/llvm/lib/Transforms/Utils/FixIrreducible.cpp b/llvm/lib/Transforms/Utils/FixIrreducible.cpp --- a/llvm/lib/Transforms/Utils/FixIrreducible.cpp +++ b/llvm/lib/Transforms/Utils/FixIrreducible.cpp @@ -104,7 +104,7 @@ INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", "Convert irreducible control-flow into natural loops", false /* Only looks at CFG */, false /* Analysis Pass */) -INITIALIZE_PASS_DEPENDENCY(LowerSwitch) +INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible", diff --git a/llvm/lib/Transforms/Utils/LowerSwitch.cpp b/llvm/lib/Transforms/Utils/LowerSwitch.cpp --- a/llvm/lib/Transforms/Utils/LowerSwitch.cpp +++ b/llvm/lib/Transforms/Utils/LowerSwitch.cpp @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Utils/LowerSwitch.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" @@ -26,6 +27,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" @@ -71,49 +73,54 @@ namespace { /// Replace all SwitchInst instructions with chained branch instructions. - class LowerSwitch : public FunctionPass { - public: - // Pass identification, replacement for typeid - static char ID; +class LowerSwitchLegacyPass : public FunctionPass { +public: + // Pass identification, replacement for typeid + static char ID; - LowerSwitch() : FunctionPass(ID) { - initializeLowerSwitchPass(*PassRegistry::getPassRegistry()); - } + LowerSwitchLegacyPass() : FunctionPass(ID) { + initializeLowerSwitchLegacyPassPass(*PassRegistry::getPassRegistry()); + } - bool runOnFunction(Function &F) override; + bool runOnFunction(Function &F) override; - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - } + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + } +}; + +class LowerSwitch { +public: + bool runImpl(Function &F, LazyValueInfo *LVI, AssumptionCache *AC); - struct CaseRange { - ConstantInt* Low; - ConstantInt* High; - BasicBlock* BB; - - CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) - : Low(low), High(high), BB(bb) {} - }; - - using CaseVector = std::vector; - using CaseItr = std::vector::iterator; - - private: - void processSwitchInst(SwitchInst *SI, - SmallPtrSetImpl &DeleteList, - AssumptionCache *AC, LazyValueInfo *LVI); - - BasicBlock *switchConvert(CaseItr Begin, CaseItr End, - ConstantInt *LowerBound, ConstantInt *UpperBound, - Value *Val, BasicBlock *Predecessor, - BasicBlock *OrigBlock, BasicBlock *Default, - const std::vector &UnreachableRanges); - BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, - ConstantInt *LowerBound, ConstantInt *UpperBound, - BasicBlock *OrigBlock, BasicBlock *Default); - unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); + struct CaseRange { + ConstantInt *Low; + ConstantInt *High; + BasicBlock *BB; + + CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb) + : Low(low), High(high), BB(bb) {} }; + using CaseVector = std::vector; + using CaseItr = std::vector::iterator; + +private: + void processSwitchInst(SwitchInst *SI, + SmallPtrSetImpl &DeleteList, + AssumptionCache *AC, LazyValueInfo *LVI); + + BasicBlock *switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound, + ConstantInt *UpperBound, Value *Val, + BasicBlock *Predecessor, BasicBlock *OrigBlock, + BasicBlock *Default, + const std::vector &UnreachableRanges); + BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, ConstantInt *LowerBound, + ConstantInt *UpperBound, BasicBlock *OrigBlock, + BasicBlock *Default); + unsigned Clusterify(CaseVector &Cases, SwitchInst *SI); +}; + /// The comparison function for sorting the switch case values in the vector. /// WARNING: Case ranges should be disjoint! struct CaseCmp { @@ -127,28 +134,25 @@ } // end anonymous namespace -char LowerSwitch::ID = 0; +char LowerSwitchLegacyPass::ID = 0; // Publicly exposed interface to pass... -char &llvm::LowerSwitchID = LowerSwitch::ID; +char &llvm::LowerSwitchID = LowerSwitchLegacyPass::ID; -INITIALIZE_PASS_BEGIN(LowerSwitch, "lowerswitch", +INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) -INITIALIZE_PASS_END(LowerSwitch, "lowerswitch", +INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) // createLowerSwitchPass - Interface to this file... FunctionPass *llvm::createLowerSwitchPass() { - return new LowerSwitch(); + return new LowerSwitchLegacyPass(); } -bool LowerSwitch::runOnFunction(Function &F) { - LazyValueInfo *LVI = &getAnalysis().getLVI(); - auto *ACT = getAnalysisIfAvailable(); - AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr; - +bool LowerSwitch::runImpl(Function &F, LazyValueInfo *LVI, + AssumptionCache *AC) { bool Changed = false; SmallPtrSet DeleteList; @@ -174,6 +178,14 @@ return Changed; } +bool LowerSwitchLegacyPass::runOnFunction(Function &F) { + LazyValueInfo *LVI = &getAnalysis().getLVI(); + auto *ACT = getAnalysisIfAvailable(); + AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr; + LowerSwitch LS; + return LS.runImpl(F, LVI, AC); +} + /// Used for debugging purposes. LLVM_ATTRIBUTE_USED static raw_ostream &operator<<(raw_ostream &O, @@ -610,3 +622,12 @@ if (pred_begin(OldDefault) == pred_end(OldDefault)) DeleteList.insert(OldDefault); } + +PreservedAnalyses LowerSwitchPass::run(Function &F, + FunctionAnalysisManager &AM) { + LazyValueInfo *LVI = &AM.getResult(F); + AssumptionCache *AC = AM.getCachedResult(F); + LowerSwitch LS; + return LS.runImpl(F, LVI, AC) ? PreservedAnalyses::none() + : PreservedAnalyses::all(); +} diff --git a/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp b/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp --- a/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp +++ b/llvm/lib/Transforms/Utils/UnifyLoopExits.cpp @@ -54,7 +54,7 @@ INITIALIZE_PASS_BEGIN(UnifyLoopExits, "unify-loop-exits", "Fixup each natural loop to have a single exit block", false /* Only looks at CFG */, false /* Analysis Pass */) -INITIALIZE_PASS_DEPENDENCY(LowerSwitch) +INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(UnifyLoopExits, "unify-loop-exits", diff --git a/llvm/lib/Transforms/Utils/Utils.cpp b/llvm/lib/Transforms/Utils/Utils.cpp --- a/llvm/lib/Transforms/Utils/Utils.cpp +++ b/llvm/lib/Transforms/Utils/Utils.cpp @@ -34,7 +34,7 @@ initializeLibCallsShrinkWrapLegacyPassPass(Registry); initializeLoopSimplifyPass(Registry); initializeLowerInvokeLegacyPassPass(Registry); - initializeLowerSwitchPass(Registry); + initializeLowerSwitchLegacyPassPass(Registry); initializeNameAnonGlobalLegacyPassPass(Registry); initializePromoteLegacyPassPass(Registry); initializeStripNonLineTableDebugInfoPass(Registry); diff --git a/llvm/test/Transforms/LowerSwitch/feature.ll b/llvm/test/Transforms/LowerSwitch/feature.ll --- a/llvm/test/Transforms/LowerSwitch/feature.ll +++ b/llvm/test/Transforms/LowerSwitch/feature.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -lowerswitch -S | FileCheck %s +; RUN: opt < %s -passes=lowerswitch -S | FileCheck %s ; We have switch on input. ; On output we should got binary comparison tree. Check that all is fine.