Home | History | Annotate | Line # | Download | only in Scalar 
      1 //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 // This file implements Loop Rotation Pass.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #include "llvm/Transforms/Scalar/LoopRotation.h"
     14 #include "llvm/ADT/Statistic.h"
     15 #include "llvm/Analysis/AssumptionCache.h"
     16 #include "llvm/Analysis/InstructionSimplify.h"
     17 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
     18 #include "llvm/Analysis/LoopPass.h"
     19 #include "llvm/Analysis/MemorySSA.h"
     20 #include "llvm/Analysis/MemorySSAUpdater.h"
     21 #include "llvm/Analysis/ScalarEvolution.h"
     22 #include "llvm/Analysis/TargetTransformInfo.h"
     23 #include "llvm/InitializePasses.h"
     24 #include "llvm/Support/CommandLine.h"
     25 #include "llvm/Support/Debug.h"
     26 #include "llvm/Transforms/Scalar.h"
     27 #include "llvm/Transforms/Scalar/LoopPassManager.h"
     28 #include "llvm/Transforms/Utils/LoopRotationUtils.h"
     29 #include "llvm/Transforms/Utils/LoopUtils.h"
     30 using namespace llvm;
     31 
     32 #define DEBUG_TYPE "loop-rotate"
     33 
     34 static cl::opt<unsigned> DefaultRotationThreshold(
     35     "rotation-max-header-size", cl::init(16), cl::Hidden,
     36     cl::desc("The default maximum header size for automatic loop rotation"));
     37 
     38 static cl::opt<bool> PrepareForLTOOption(
     39     "rotation-prepare-for-lto", cl::init(false), cl::Hidden,
     40     cl::desc("Run loop-rotation in the prepare-for-lto stage. This option "
     41              "should be used for testing only."));
     42 
     43 LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication, bool PrepareForLTO)
     44     : EnableHeaderDuplication(EnableHeaderDuplication),
     45       PrepareForLTO(PrepareForLTO) {}
     46 
     47 PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
     48                                       LoopStandardAnalysisResults &AR,
     49                                       LPMUpdater &) {
     50   // Vectorization requires loop-rotation. Use default threshold for loops the
     51   // user explicitly marked for vectorization, even when header duplication is
     52   // disabled.
     53   int Threshold = EnableHeaderDuplication ||
     54                           hasVectorizeTransformation(&L) == TM_ForcedByUser
     55                       ? DefaultRotationThreshold
     56                       : 0;
     57   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
     58   const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL);
     59 
     60   Optional<MemorySSAUpdater> MSSAU;
     61   if (AR.MSSA)
     62     MSSAU = MemorySSAUpdater(AR.MSSA);
     63   bool Changed =
     64       LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
     65                    MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ, false,
     66                    Threshold, false, PrepareForLTO || PrepareForLTOOption);
     67 
     68   if (!Changed)
     69     return PreservedAnalyses::all();
     70 
     71   if (AR.MSSA && VerifyMemorySSA)
     72     AR.MSSA->verifyMemorySSA();
     73 
     74   auto PA = getLoopPassPreservedAnalyses();
     75   if (AR.MSSA)
     76     PA.preserve<MemorySSAAnalysis>();
     77   return PA;
     78 }
     79 
     80 namespace {
     81 
     82 class LoopRotateLegacyPass : public LoopPass {
     83   unsigned MaxHeaderSize;
     84   bool PrepareForLTO;
     85 
     86 public:
     87   static char ID; // Pass ID, replacement for typeid
     88   LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1,
     89                        bool PrepareForLTO = false)
     90       : LoopPass(ID), PrepareForLTO(PrepareForLTO) {
     91     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
     92     if (SpecifiedMaxHeaderSize == -1)
     93       MaxHeaderSize = DefaultRotationThreshold;
     94     else
     95       MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
     96   }
     97 
     98   // LCSSA form makes instruction renaming easier.
     99   void getAnalysisUsage(AnalysisUsage &AU) const override {
    100     AU.addRequired<AssumptionCacheTracker>();
    101     AU.addRequired<TargetTransformInfoWrapperPass>();
    102     if (EnableMSSALoopDependency)
    103       AU.addPreserved<MemorySSAWrapperPass>();
    104     getLoopAnalysisUsage(AU);
    105 
    106     // Lazy BFI and BPI are marked as preserved here so LoopRotate
    107     // can remain part of the same loop pass manager as LICM.
    108     AU.addPreserved<LazyBlockFrequencyInfoPass>();
    109     AU.addPreserved<LazyBranchProbabilityInfoPass>();
    110   }
    111 
    112   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
    113     if (skipLoop(L))
    114       return false;
    115     Function &F = *L->getHeader()->getParent();
    116 
    117     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
    118     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
    119     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
    120     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    121     auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
    122     const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
    123     Optional<MemorySSAUpdater> MSSAU;
    124     if (EnableMSSALoopDependency) {
    125       // Not requiring MemorySSA and getting it only if available will split
    126       // the loop pass pipeline when LoopRotate is being run first.
    127       auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
    128       if (MSSAA)
    129         MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
    130     }
    131     // Vectorization requires loop-rotation. Use default threshold for loops the
    132     // user explicitly marked for vectorization, even when header duplication is
    133     // disabled.
    134     int Threshold = hasVectorizeTransformation(L) == TM_ForcedByUser
    135                         ? DefaultRotationThreshold
    136                         : MaxHeaderSize;
    137 
    138     return LoopRotation(L, LI, TTI, AC, &DT, &SE,
    139                         MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ,
    140                         false, Threshold, false,
    141                         PrepareForLTO || PrepareForLTOOption);
    142   }
    143 };
    144 } // end namespace
    145 
    146 char LoopRotateLegacyPass::ID = 0;
    147 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
    148                       false, false)
    149 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
    150 INITIALIZE_PASS_DEPENDENCY(LoopPass)
    151 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
    152 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
    153 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
    154                     false)
    155 
    156 Pass *llvm::createLoopRotatePass(int MaxHeaderSize, bool PrepareForLTO) {
    157   return new LoopRotateLegacyPass(MaxHeaderSize, PrepareForLTO);
    158 }
    159