LLVM  13.0.0git
LoopRotation.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/InitializePasses.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Transforms/Scalar.h"
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "loop-rotate"
33 
35  "rotation-max-header-size", cl::init(16), cl::Hidden,
36  cl::desc("The default maximum header size for automatic loop rotation"));
37 
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 
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 ||
56  : 0;
57  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
58  const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL);
59 
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) {
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 {
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.
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);
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.
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)
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 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
Definition: AllocatorList.h:23
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:54
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
Scalar.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
LazyBlockFrequencyInfo.h
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:150
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
Loops
loop Rotate Loops
Definition: LoopRotation.cpp:153
ScalarEvolution.h
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::Optional
Definition: APInt.h:33
llvm::EnableMSSALoopDependency
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::LazyBlockFrequencyInfoPass
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
Definition: LazyBlockFrequencyInfo.h:100
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:278
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:286
CommandLine.h
LoopRotation.h
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:961
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LoopRotatePass::LoopRotatePass
LoopRotatePass(bool EnableHeaderDuplication=true, bool PrepareForLTO=false)
Definition: LoopRotation.cpp:43
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::LoopRotatePass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopRotation.cpp:47
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:75
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:144
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::cl::opt
Definition: CommandLine.h:1422
DefaultRotationThreshold
static cl::opt< unsigned > DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden, cl::desc("The default maximum header size for automatic loop rotation"))
llvm::LoopPass
Definition: LoopPass.h:27
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2375
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:243
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1867
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:922
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::TM_ForcedByUser
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:288
LoopPass.h
LoopRotationUtils.h
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
llvm::getBestSimplifyQuery
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
Definition: InstructionSimplify.cpp:6032
llvm::LoopStandardAnalysisResults::TTI
TargetTransformInfo & TTI
Definition: LoopAnalysisManager.h:59
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::LoopRotation
bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode, bool PrepareForLTO=false)
Convert a loop into a loop with bottom test.
Definition: LoopRotationUtils.cpp:829
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::createLoopRotatePass
Pass * createLoopRotatePass(int MaxHeaderSize=-1, bool PrepareForLTO=false)
Definition: LoopRotation.cpp:156
PrepareForLTOOption
static cl::opt< bool > PrepareForLTOOption("rotation-prepare-for-lto", cl::init(false), cl::Hidden, cl::desc("Run loop-rotation in the prepare-for-lto stage. This option " "should be used for testing only."))
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false, false) INITIALIZE_PASS_END(LoopRotateLegacyPass
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
llvm::hasVectorizeTransformation
TransformationMode hasVectorizeTransformation(const Loop *L)
Definition: LoopUtils.cpp:460
InstructionSimplify.h
TargetTransformInfo.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::initializeLoopRotateLegacyPassPass
void initializeLoopRotateLegacyPassPass(PassRegistry &)
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
llvm::cl::desc
Definition: CommandLine.h:414
llvm::LazyBranchProbabilityInfoPass
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
Definition: LazyBranchProbabilityInfo.h:50
InitializePasses.h
Debug.h
rotate
loop rotate
Definition: LoopRotation.cpp:153
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38