Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -177,7 +177,7 @@ void initializeLoopDeletionPass(PassRegistry&); void initializeLoopDistributePass(PassRegistry&); void initializeLoopExtractorPass(PassRegistry&); -void initializeLoopIdiomRecognizePass(PassRegistry&); +void initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry&); void initializeLoopInfoWrapperPassPass(PassRegistry&); void initializeLoopInstSimplifyPass(PassRegistry&); void initializeLoopInterchangePass(PassRegistry &); Index: include/llvm/Transforms/Scalar/LoopIdiomRecognize.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/LoopIdiomRecognize.h @@ -0,0 +1,31 @@ +//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements an idiom recognizer that transforms simple loops into a +// non-loop form. In cases that this kicks in, it can be a significant +// performance win. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H +#define LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Idiom Recognize Pass. +class LoopIdiomRecognizePass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, AnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -88,6 +88,7 @@ #include "llvm/Transforms/Scalar/GuardWidening.h" #include "llvm/Transforms/Scalar/IndVarSimplify.h" #include "llvm/Transforms/Scalar/JumpThreading.h" +#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" #include "llvm/Transforms/Scalar/LoopRotation.h" #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h" #include "llvm/Transforms/Scalar/LowerAtomic.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -187,6 +187,7 @@ #define LOOP_PASS(NAME, CREATE_PASS) #endif LOOP_PASS("invalidate", InvalidateAllAnalysesPass()) +LOOP_PASS("loop-idiom", LoopIdiomRecognizePass()) LOOP_PASS("rotate", LoopRotatePass()) LOOP_PASS("no-op-loop", NoOpLoopPass()) LOOP_PASS("print", PrintLoopPass(dbgs())) Index: lib/Transforms/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -31,15 +31,16 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" -#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" @@ -53,6 +54,7 @@ #include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BuildLibCalls.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LoopUtils.h" @@ -65,7 +67,7 @@ namespace { -class LoopIdiomRecognize : public LoopPass { +class LoopIdiomRecognize { Loop *CurLoop; AliasAnalysis *AA; DominatorTree *DT; @@ -76,21 +78,15 @@ const DataLayout *DL; public: - static char ID; - explicit LoopIdiomRecognize() : LoopPass(ID) { - initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry()); - } - - bool runOnLoop(Loop *L, LPPassManager &LPM) override; + explicit LoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT, + LoopInfo *LI, ScalarEvolution *SE, + TargetLibraryInfo *TLI, + const TargetTransformInfo *TTI, + const DataLayout *DL) + : CurLoop(nullptr), AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), + DL(DL) {} - /// This transformation requires natural loop information & requires that - /// loop preheaders be inserted into the CFG. - /// - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - getLoopAnalysisUsage(AU); - } + bool runOnLoop(Loop *L); private: typedef SmallVector StoreList; @@ -137,18 +133,78 @@ /// @} }; +class LoopIdiomRecognizeLegacyPass : public LoopPass { +public: + static char ID; + explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) { + initializeLoopIdiomRecognizeLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + + AliasAnalysis *AA = &getAnalysis().getAAResults(); + DominatorTree *DT = &getAnalysis().getDomTree(); + LoopInfo *LI = &getAnalysis().getLoopInfo(); + ScalarEvolution *SE = &getAnalysis().getSE(); + TargetLibraryInfo *TLI = + &getAnalysis().getTLI(); + const TargetTransformInfo *TTI = + &getAnalysis().getTTI( + *L->getHeader()->getParent()); + const DataLayout *DL = &L->getHeader()->getModule()->getDataLayout(); + + LoopIdiomRecognize LIR(AA, DT, LI, SE, TLI, TTI, DL); + return LIR.runOnLoop(L); + } + + /// This transformation requires natural loop information & requires that + /// loop preheaders be inserted into the CFG. + /// + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + getLoopAnalysisUsage(AU); + } +}; } // End anonymous namespace. -char LoopIdiomRecognize::ID = 0; -INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", - false, false) +PreservedAnalyses LoopIdiomRecognizePass::run(Loop &L, + AnalysisManager &AM) { + const auto &FAM = + AM.getResult(L).getManager(); + Function *F = L.getHeader()->getParent(); + + // Use getCachedResult because Loop pass cannot trigger a function analysis. + auto *AA = FAM.getCachedResult(*F); + auto *DT = FAM.getCachedResult(*F); + auto *LI = FAM.getCachedResult(*F); + auto *SE = FAM.getCachedResult(*F); + auto *TLI = FAM.getCachedResult(*F); + const auto *TTI = FAM.getCachedResult(*F); + const auto *DL = &L.getHeader()->getModule()->getDataLayout(); + assert((AA && DT && LI && SE && TLI && TTI && DL) && + "Analyses for Loop Idiom Recognition not available"); + + LoopIdiomRecognize LIR(AA, DT, LI, SE, TLI, TTI, DL); + if (!LIR.runOnLoop(&L)) + return PreservedAnalyses::all(); + + return getLoopPassPreservedAnalyses(); +} + +char LoopIdiomRecognizeLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(LoopIdiomRecognizeLegacyPass, "loop-idiom", + "Recognize loop idioms", false, false) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) -INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", - false, false) +INITIALIZE_PASS_END(LoopIdiomRecognizeLegacyPass, "loop-idiom", + "Recognize loop idioms", false, false) -Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); } +Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognizeLegacyPass(); } static void deleteDeadInstruction(Instruction *I) { I->replaceAllUsesWith(UndefValue::get(I->getType())); @@ -161,10 +217,7 @@ // //===----------------------------------------------------------------------===// -bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) { - if (skipLoop(L)) - return false; - +bool LoopIdiomRecognize::runOnLoop(Loop *L) { CurLoop = L; // If the loop could not be converted to canonical form, it must have an // indirectbr in it, just give up. @@ -176,15 +229,6 @@ if (Name == "memset" || Name == "memcpy") return false; - AA = &getAnalysis().getAAResults(); - DT = &getAnalysis().getDomTree(); - LI = &getAnalysis().getLoopInfo(); - SE = &getAnalysis().getSE(); - TLI = &getAnalysis().getTLI(); - TTI = &getAnalysis().getTTI( - *CurLoop->getHeader()->getParent()); - DL = &CurLoop->getHeader()->getModule()->getDataLayout(); - HasMemset = TLI->has(LibFunc::memset); HasMemsetPattern = TLI->has(LibFunc::memset_pattern16); HasMemcpy = TLI->has(LibFunc::memcpy); Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -60,7 +60,7 @@ initializeLoopUnrollPass(Registry); initializeLoopUnswitchPass(Registry); initializeLoopVersioningLICMPass(Registry); - initializeLoopIdiomRecognizePass(Registry); + initializeLoopIdiomRecognizeLegacyPassPass(Registry); initializeLowerAtomicLegacyPassPass(Registry); initializeLowerExpectIntrinsicPass(Registry); initializeLowerGuardIntrinsicPass(Registry); Index: test/Transforms/LoopIdiom/nontemporal_store.ll =================================================================== --- test/Transforms/LoopIdiom/nontemporal_store.ll +++ test/Transforms/LoopIdiom/nontemporal_store.ll @@ -1,4 +1,5 @@ ; RUN: opt -loop-idiom < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,loop(loop-idiom)' < %s -S | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"