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 @@ -241,7 +241,7 @@ void initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry&); void initializeLoopInfoWrapperPassPass(PassRegistry&); void initializeLoopInstSimplifyLegacyPassPass(PassRegistry&); -void initializeLoopInterchangePass(PassRegistry&); +void initializeLoopInterchangeLegacyPassPass(PassRegistry &); void initializeLoopFlattenLegacyPassPass(PassRegistry&); void initializeLoopLoadEliminationPass(PassRegistry&); void initializeLoopPassPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/Scalar/LoopInterchange.h b/llvm/include/llvm/Transforms/Scalar/LoopInterchange.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/LoopInterchange.h @@ -0,0 +1,27 @@ +//===- LoopInterchange.h - Loop rerolling pass ----------------------------===// +// +// 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_LOOPINTERCHANGE_H +#define LLVM_TRANSFORMS_SCALAR_LOOPINTERCHANGE_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +class Function; + +class LoopInterchangePass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPINTERCHANGE_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 @@ -154,6 +154,7 @@ #include "llvm/Transforms/Scalar/LoopFuse.h" #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" #include "llvm/Transforms/Scalar/LoopInstSimplify.h" +#include "llvm/Transforms/Scalar/LoopInterchange.h" #include "llvm/Transforms/Scalar/LoopLoadElimination.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Scalar/LoopPredication.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 @@ -358,6 +358,7 @@ LOOP_PASS("licm", LICMPass()) LOOP_PASS("loop-idiom", LoopIdiomRecognizePass()) LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass()) +LOOP_PASS("loop-interchange", LoopInterchangePass()) LOOP_PASS("loop-rotate", LoopRotatePass()) LOOP_PASS("no-op-loop", NoOpLoopPass()) LOOP_PASS("print", PrintLoopPass(dbgs())) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/LoopInterchange.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -428,9 +429,7 @@ const LoopInterchangeLegality &LIL; }; -// Main LoopInterchange Pass. -struct LoopInterchange : public LoopPass { - static char ID; +struct LoopInterchange { ScalarEvolution *SE = nullptr; LoopInfo *LI = nullptr; DependenceInfo *DI = nullptr; @@ -439,27 +438,14 @@ /// Interface to emit optimization remarks. OptimizationRemarkEmitter *ORE; - LoopInterchange() : LoopPass(ID) { - initializeLoopInterchangePass(*PassRegistry::getPassRegistry()); - } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - - getLoopAnalysisUsage(AU); - } + LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI, + DominatorTree *DT, OptimizationRemarkEmitter *ORE) + : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {} - bool runOnLoop(Loop *L, LPPassManager &LPM) override { - if (skipLoop(L) || L->getParentLoop()) + bool run(Loop *L) { + if (L->getParentLoop()) return false; - SE = &getAnalysis().getSE(); - LI = &getAnalysis().getLoopInfo(); - DI = &getAnalysis().getDI(); - DT = &getAnalysis().getDomTree(); - ORE = &getAnalysis().getORE(); - return processLoopList(populateWorklist(*L)); } @@ -1645,15 +1631,58 @@ return Changed; } -char LoopInterchange::ID = 0; +// Main LoopInterchange Pass. +struct LoopInterchangeLegacyPass : public LoopPass { + static char ID; -INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", + LoopInterchangeLegacyPass() : LoopPass(ID) { + initializeLoopInterchangeLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + + getLoopAnalysisUsage(AU); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + + auto *SE = &getAnalysis().getSE(); + auto *LI = &getAnalysis().getLoopInfo(); + auto *DI = &getAnalysis().getDI(); + auto *DT = &getAnalysis().getDomTree(); + auto *ORE = &getAnalysis().getORE(); + + return LoopInterchange(SE, LI, DI, DT, ORE).run(L); + } +}; + +char LoopInterchangeLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass) INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) -INITIALIZE_PASS_END(LoopInterchange, "loop-interchange", +INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange", "Interchanges loops for cache reuse", false, false) -Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); } +Pass *llvm::createLoopInterchangePass() { + return new LoopInterchangeLegacyPass(); +} + +PreservedAnalyses LoopInterchangePass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + Function &F = *L.getHeader()->getParent(); + + DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI); + OptimizationRemarkEmitter ORE(&F); + if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(&L)) + return PreservedAnalyses::all(); + return getLoopPassPreservedAnalyses(); +} 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 @@ -66,7 +66,7 @@ initializeLoopDeletionLegacyPassPass(Registry); initializeLoopAccessLegacyAnalysisPass(Registry); initializeLoopInstSimplifyLegacyPassPass(Registry); - initializeLoopInterchangePass(Registry); + initializeLoopInterchangeLegacyPassPass(Registry); initializeLoopFlattenLegacyPassPass(Registry); initializeLoopPredicationLegacyPassPass(Registry); initializeLoopRotateLegacyPassPass(Registry); diff --git a/llvm/test/Transforms/LoopInterchange/interchangeable.ll b/llvm/test/Transforms/LoopInterchange/interchangeable.ll --- a/llvm/test/Transforms/LoopInterchange/interchangeable.ll +++ b/llvm/test/Transforms/LoopInterchange/interchangeable.ll @@ -1,5 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes=loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"