Index: include/llvm/Transforms/Scalar/LoopStrengthReduce.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/LoopStrengthReduce.h @@ -0,0 +1,37 @@ +//===- LoopStrengthReduce.h - Loop Strength Reduce Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This transformation analyzes and transforms the induction variables (and +// computations derived from them) into forms suitable for efficient execution +// on the target. +// +// This pass performs a strength reduction on array references inside loops that +// have as one or more of their components the loop induction variable, it +// rewrites expressions to take advantage of scaled-index addressing modes +// available on the target, and it performs a variety of other optimizations +// related to loop induction variables. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H +#define LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Strength Reduce Pass. +class LoopStrengthReducePass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, AnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -97,6 +97,7 @@ #include "llvm/Transforms/Scalar/LoopInstSimplify.h" #include "llvm/Transforms/Scalar/LoopRotation.h" #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h" +#include "llvm/Transforms/Scalar/LoopStrengthReduce.h" #include "llvm/Transforms/Scalar/LowerAtomic.h" #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" #include "llvm/Transforms/Scalar/MemCpyOptimizer.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -199,6 +199,7 @@ LOOP_PASS("print", PrintLoopPass(dbgs())) LOOP_PASS("loop-deletion", LoopDeletionPass()) LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass()) +LOOP_PASS("strength-reduce", LoopStrengthReducePass()) LOOP_PASS("indvars", IndVarSimplifyPass()) LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs())) LOOP_PASS("print", IVUsersPrinterPass(dbgs())) Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -53,7 +53,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/LoopStrengthReduce.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLExtras.h" @@ -61,6 +61,7 @@ #include "llvm/ADT/SmallBitVector.h" #include "llvm/Analysis/IVUsers.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Constants.h" @@ -73,6 +74,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include @@ -4940,12 +4942,11 @@ bool runOnLoop(Loop *L, LPPassManager &LPM) override; void getAnalysisUsage(AnalysisUsage &AU) const override; }; - } char LoopStrengthReduce::ID = 0; INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce", - "Loop Strength Reduction", false, false) + "Loop Strength Reduction", false, false) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) @@ -4953,12 +4954,9 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce", - "Loop Strength Reduction", false, false) - + "Loop Strength Reduction", false, false) -Pass *llvm::createLoopStrengthReducePass() { - return new LoopStrengthReduce(); -} +Pass *llvm::createLoopStrengthReducePass() { return new LoopStrengthReduce(); } LoopStrengthReduce::LoopStrengthReduce() : LoopPass(ID) { initializeLoopStrengthReducePass(*PassRegistry::getPassRegistry()); @@ -4984,16 +4982,9 @@ AU.addRequired(); } -bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { - if (skipLoop(L)) - return false; - - auto &IU = getAnalysis().getIU(); - auto &SE = getAnalysis().getSE(); - auto &DT = getAnalysis().getDomTree(); - auto &LI = getAnalysis().getLoopInfo(); - const auto &TTI = getAnalysis().getTTI( - *L->getHeader()->getParent()); +static bool ReduceLoopStrength(Loop *L, IVUsers &IU, ScalarEvolution &SE, + DominatorTree &DT, LoopInfo &LI, + const TargetTransformInfo &TTI) { bool Changed = false; // Run the main LSR transformation. @@ -5004,15 +4995,11 @@ if (EnablePhiElim && L->isLoopSimplifyForm()) { SmallVector DeadInsts; const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); - SCEVExpander Rewriter(getAnalysis().getSE(), DL, - "lsr"); + SCEVExpander Rewriter(SE, DL, "lsr"); #ifndef NDEBUG Rewriter.setDebugType(DEBUG_TYPE); #endif - unsigned numFolded = Rewriter.replaceCongruentIVs( - L, &getAnalysis().getDomTree(), DeadInsts, - &getAnalysis().getTTI( - *L->getHeader()->getParent())); + unsigned numFolded = Rewriter.replaceCongruentIVs(L, &DT, DeadInsts, &TTI); if (numFolded) { Changed = true; DeleteTriviallyDeadInstructions(DeadInsts); @@ -5021,3 +5008,36 @@ } return Changed; } + +bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { + if (skipLoop(L)) + return false; + + auto &IU = getAnalysis().getIU(); + auto &SE = getAnalysis().getSE(); + auto &DT = getAnalysis().getDomTree(); + auto &LI = getAnalysis().getLoopInfo(); + const auto &TTI = getAnalysis().getTTI( + *L->getHeader()->getParent()); + return ReduceLoopStrength(L, IU, SE, DT, LI, TTI); +} + +PreservedAnalyses LoopStrengthReducePass::run(Loop &L, + AnalysisManager &AM) { + const auto &FAM = + AM.getResult(L).getManager(); + Function *F = L.getHeader()->getParent(); + + auto &IU = AM.getResult(L); + auto *SE = FAM.getCachedResult(*F); + auto *DT = FAM.getCachedResult(*F); + auto *LI = FAM.getCachedResult(*F); + auto *TTI = FAM.getCachedResult(*F); + assert((SE && DT && LI && TTI) && + "Analyses for Loop Strength Reduce not available"); + + if (!ReduceLoopStrength(&L, IU, *SE, *DT, *LI, *TTI)) + return PreservedAnalyses::all(); + + return getLoopPassPreservedAnalyses(); +} Index: test/Transforms/LoopStrengthReduce/ivchain.ll =================================================================== --- test/Transforms/LoopStrengthReduce/ivchain.ll +++ test/Transforms/LoopStrengthReduce/ivchain.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -loop-reduce -S | FileCheck %s +; RUN: opt -passes='function(require,require),loop(require,strength-reduce)' < %s -S | FileCheck %s ; ; PR11782: bad cast to AddRecExpr. ; A sign extend feeds an IVUser and cannot be hoisted into the AddRec.