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