LLVM  15.0.0git
LoopSink.cpp
Go to the documentation of this file.
1 //===-- LoopSink.cpp - Loop Sink 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 pass does the inverse transformation of what LICM does.
10 // It traverses all of the instructions in the loop's preheader and sinks
11 // them to the loop body where frequency is lower than the loop's preheader.
12 // This pass is a reverse-transformation of LICM. It differs from the Sink
13 // pass in the following ways:
14 //
15 // * It only handles sinking of instructions from the loop's preheader to the
16 // loop's body
17 // * It uses alias set tracker to get more accurate alias info
18 // * It uses block frequency info to find the optimal sinking locations
19 //
20 // Overall algorithm:
21 //
22 // For I in Preheader:
23 // InsertBBs = BBs that uses I
24 // For BB in sorted(LoopBBs):
25 // DomBBs = BBs in InsertBBs that are dominated by BB
26 // if freq(DomBBs) > freq(BB)
27 // InsertBBs = UseBBs - DomBBs + BB
28 // For BB in InsertBBs:
29 // Insert I at BB's beginning
30 //
31 //===----------------------------------------------------------------------===//
32 
34 #include "llvm/ADT/SetOperations.h"
35 #include "llvm/ADT/Statistic.h"
38 #include "llvm/Analysis/LoopInfo.h"
39 #include "llvm/Analysis/LoopPass.h"
43 #include "llvm/IR/Dominators.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/InitializePasses.h"
48 #include "llvm/Transforms/Scalar.h"
51 using namespace llvm;
52 
53 #define DEBUG_TYPE "loopsink"
54 
55 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
56 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
57 
59  "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
60  cl::desc("Do not sink instructions that require cloning unless they "
61  "execute less than this percent of the time."));
62 
64  "max-uses-for-sinking", cl::Hidden, cl::init(30),
65  cl::desc("Do not sink instructions that have too many uses."));
66 
67 /// Return adjusted total frequency of \p BBs.
68 ///
69 /// * If there is only one BB, sinking instruction will not introduce code
70 /// size increase. Thus there is no need to adjust the frequency.
71 /// * If there are more than one BB, sinking would lead to code size increase.
72 /// In this case, we add some "tax" to the total frequency to make it harder
73 /// to sink. E.g.
74 /// Freq(Preheader) = 100
75 /// Freq(BBs) = sum(50, 49) = 99
76 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
77 /// BBs as the difference is too small to justify the code size increase.
78 /// To model this, The adjusted Freq(BBs) will be:
79 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
82  BlockFrequency T = 0;
83  for (BasicBlock *B : BBs)
84  T += BFI.getBlockFreq(B);
85  if (BBs.size() > 1)
87  return T;
88 }
89 
90 /// Return a set of basic blocks to insert sinked instructions.
91 ///
92 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
93 ///
94 /// * Inside the loop \p L
95 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
96 /// that domintates the UseBB
97 /// * Has minimum total frequency that is no greater than preheader frequency
98 ///
99 /// The purpose of the function is to find the optimal sinking points to
100 /// minimize execution cost, which is defined as "sum of frequency of
101 /// BBsToSinkInto".
102 /// As a result, the returned BBsToSinkInto needs to have minimum total
103 /// frequency.
104 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
105 /// frequency, the optimal solution is not sinking (return empty set).
106 ///
107 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
108 /// It stores a list of BBs that is:
109 ///
110 /// * Inside the loop \p L
111 /// * Has a frequency no larger than the loop's preheader
112 /// * Sorted by BB frequency
113 ///
114 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
115 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
116 /// caller.
119  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
121  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
122  if (UseBBs.size() == 0)
123  return BBsToSinkInto;
124 
125  BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
126  SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
127 
128  // For every iteration:
129  // * Pick the ColdestBB from ColdLoopBBs
130  // * Find the set BBsDominatedByColdestBB that satisfy:
131  // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
132  // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
133  // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
134  // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
135  // BBsToSinkInto
136  for (BasicBlock *ColdestBB : ColdLoopBBs) {
137  BBsDominatedByColdestBB.clear();
138  for (BasicBlock *SinkedBB : BBsToSinkInto)
139  if (DT.dominates(ColdestBB, SinkedBB))
140  BBsDominatedByColdestBB.insert(SinkedBB);
141  if (BBsDominatedByColdestBB.size() == 0)
142  continue;
143  if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
144  BFI.getBlockFreq(ColdestBB)) {
145  for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
146  BBsToSinkInto.erase(DominatedBB);
147  }
148  BBsToSinkInto.insert(ColdestBB);
149  }
150  }
151 
152  // Can't sink into blocks that have no valid insertion point.
153  for (BasicBlock *BB : BBsToSinkInto) {
154  if (BB->getFirstInsertionPt() == BB->end()) {
155  BBsToSinkInto.clear();
156  break;
157  }
158  }
159 
160  // If the total frequency of BBsToSinkInto is larger than preheader frequency,
161  // do not sink.
162  if (adjustedSumFreq(BBsToSinkInto, BFI) >
163  BFI.getBlockFreq(L.getLoopPreheader()))
164  BBsToSinkInto.clear();
165  return BBsToSinkInto;
166 }
167 
168 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
169 // sinking is successful.
170 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
171 // determinism.
172 static bool sinkInstruction(
173  Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
174  const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
176  // Compute the set of blocks in loop L which contain a use of I.
178  for (auto &U : I.uses()) {
179  Instruction *UI = cast<Instruction>(U.getUser());
180  // We cannot sink I to PHI-uses.
181  if (isa<PHINode>(UI))
182  return false;
183  // We cannot sink I if it has uses outside of the loop.
184  if (!L.contains(LI.getLoopFor(UI->getParent())))
185  return false;
186  BBs.insert(UI->getParent());
187  }
188 
189  // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
190  // BBs.size() to avoid expensive computation.
191  // FIXME: Handle code size growth for min_size and opt_size.
192  if (BBs.size() > MaxNumberOfUseBBsForSinking)
193  return false;
194 
195  // Find the set of BBs that we should insert a copy of I.
196  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
197  findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
198  if (BBsToSinkInto.empty())
199  return false;
200 
201  // Return if any of the candidate blocks to sink into is non-cold.
202  if (BBsToSinkInto.size() > 1 &&
203  !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
204  return false;
205 
206  // Copy the final BBs into a vector and sort them using the total ordering
207  // of the loop block numbers as iterating the set doesn't give a useful
208  // order. No need to stable sort as the block numbers are a total ordering.
209  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
210  llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
211  llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
212  return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
213  });
214 
215  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
216  // FIXME: Optimize the efficiency for cloned value replacement. The current
217  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
218  for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
219  assert(LoopBlockNumber.find(N)->second >
220  LoopBlockNumber.find(MoveBB)->second &&
221  "BBs not sorted!");
222  // Clone I and replace its uses.
223  Instruction *IC = I.clone();
224  IC->setName(I.getName());
225  IC->insertBefore(&*N->getFirstInsertionPt());
226 
227  if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
228  // Create a new MemoryAccess and let MemorySSA set its defining access.
229  MemoryAccess *NewMemAcc =
230  MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
231  if (NewMemAcc) {
232  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
233  MSSAU->insertDef(MemDef, /*RenameUses=*/true);
234  else {
235  auto *MemUse = cast<MemoryUse>(NewMemAcc);
236  MSSAU->insertUse(MemUse, /*RenameUses=*/true);
237  }
238  }
239  }
240 
241  // Replaces uses of I with IC in N
242  I.replaceUsesWithIf(IC, [N](Use &U) {
243  return cast<Instruction>(U.getUser())->getParent() == N;
244  });
245  // Replaces uses of I with IC in blocks dominated by N
246  replaceDominatedUsesWith(&I, IC, DT, N);
247  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
248  << '\n');
249  NumLoopSunkCloned++;
250  }
251  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
252  NumLoopSunk++;
253  I.moveBefore(&*MoveBB->getFirstInsertionPt());
254 
255  if (MSSAU)
256  if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
257  MSSAU->getMemorySSA()->getMemoryAccess(&I)))
258  MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
259 
260  return true;
261 }
262 
263 /// Sinks instructions from loop's preheader to the loop body if the
264 /// sum frequency of inserted copy is smaller than preheader's frequency.
266  DominatorTree &DT,
268  MemorySSA &MSSA,
269  ScalarEvolution *SE) {
270  BasicBlock *Preheader = L.getLoopPreheader();
271  assert(Preheader && "Expected loop to have preheader");
272 
273  assert(Preheader->getParent()->hasProfileData() &&
274  "Unexpected call when profile data unavailable.");
275 
276  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
277  // If there are no basic blocks with lower frequency than the preheader then
278  // we can avoid the detailed analysis as we will never find profitable sinking
279  // opportunities.
280  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
281  return BFI.getBlockFreq(BB) > PreheaderFreq;
282  }))
283  return false;
284 
285  MemorySSAUpdater MSSAU(&MSSA);
286  SinkAndHoistLICMFlags LICMFlags(/*IsSink=*/true, &L, &MSSA);
287 
288  bool Changed = false;
289 
290  // Sort loop's basic blocks by frequency
291  SmallVector<BasicBlock *, 10> ColdLoopBBs;
292  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
293  int i = 0;
294  for (BasicBlock *B : L.blocks())
295  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
296  ColdLoopBBs.push_back(B);
297  LoopBlockNumber[B] = ++i;
298  }
299  llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
300  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
301  });
302 
303  // Traverse preheader's instructions in reverse order becaue if A depends
304  // on B (A appears after B), A needs to be sinked first before B can be
305  // sinked.
306  for (Instruction &I : llvm::make_early_inc_range(llvm::reverse(*Preheader))) {
307  if (isa<PHINode>(&I))
308  continue;
309  // No need to check for instruction's operands are loop invariant.
311  "Insts in a loop's preheader should have loop invariant operands!");
312  if (!canSinkOrHoistInst(I, &AA, &DT, &L, MSSAU, false, LICMFlags))
313  continue;
314  if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
315  &MSSAU))
316  Changed = true;
317  }
318 
319  if (Changed && SE)
320  SE->forgetLoopDispositions(&L);
321  return Changed;
322 }
323 
326  // Nothing to do if there are no loops.
327  if (LI.empty())
328  return PreservedAnalyses::all();
329 
333  MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
334 
335  // We want to do a postorder walk over the loops. Since loops are a tree this
336  // is equivalent to a reversed preorder walk and preorder is easy to compute
337  // without recursion. Since we reverse the preorder, we will visit siblings
338  // in reverse program order. This isn't expected to matter at all but is more
339  // consistent with sinking algorithms which generally work bottom-up.
340  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
341 
342  bool Changed = false;
343  do {
344  Loop &L = *PreorderLoops.pop_back_val();
345 
346  BasicBlock *Preheader = L.getLoopPreheader();
347  if (!Preheader)
348  continue;
349 
350  // Enable LoopSink only when runtime profile is available.
351  // With static profile, the sinking decision may be sub-optimal.
352  if (!Preheader->getParent()->hasProfileData())
353  continue;
354 
355  // Note that we don't pass SCEV here because it is only used to invalidate
356  // loops in SCEV and we don't preserve (or request) SCEV at all making that
357  // unnecessary.
358  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, MSSA,
359  /*ScalarEvolution*/ nullptr);
360  } while (!PreorderLoops.empty());
361 
362  if (!Changed)
363  return PreservedAnalyses::all();
364 
366  PA.preserveSet<CFGAnalyses>();
368 
369  if (VerifyMemorySSA)
370  MSSA.verifyMemorySSA();
371 
372  return PA;
373 }
374 
375 namespace {
376 struct LegacyLoopSinkPass : public LoopPass {
377  static char ID;
378  LegacyLoopSinkPass() : LoopPass(ID) {
380  }
381 
382  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
383  if (skipLoop(L))
384  return false;
385 
386  BasicBlock *Preheader = L->getLoopPreheader();
387  if (!Preheader)
388  return false;
389 
390  // Enable LoopSink only when runtime profile is available.
391  // With static profile, the sinking decision may be sub-optimal.
392  if (!Preheader->getParent()->hasProfileData())
393  return false;
394 
395  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
396  MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
397  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
398  bool Changed = sinkLoopInvariantInstructions(
399  *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
400  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
401  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
402  MSSA, SE ? &SE->getSE() : nullptr);
403 
404  if (VerifyMemorySSA)
405  MSSA.verifyMemorySSA();
406 
407  return Changed;
408  }
409 
410  void getAnalysisUsage(AnalysisUsage &AU) const override {
411  AU.setPreservesCFG();
416  }
417 };
418 }
419 
420 char LegacyLoopSinkPass::ID = 0;
421 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
422  false)
426 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
427 
428 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
llvm::set_is_subset
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
Definition: SetOperations.h:72
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
Scalar.h
SetOperations.h
llvm::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:8118
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::BlockFrequencyInfoWrapperPass
Legacy analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:138
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
adjustedSumFreq
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:80
llvm::initializeLegacyLoopSinkPassPass
void initializeLegacyLoopSinkPassPass(PassRegistry &)
Statistic.h
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:83
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:144
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
ScalarEvolution.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::canSinkOrHoistInst
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:1137
llvm::MemorySSAUpdater::createMemoryAccessInBB
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
Definition: MemorySSAUpdater.cpp:1429
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
CommandLine.h
llvm::MemorySSAUpdater::insertUse
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:238
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::createLoopSinkPass
Pass * createLoopSinkPass()
findBBsToSinkInto
static SmallPtrSet< BasicBlock *, 2 > findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl< BasicBlock * > &UseBBs, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, DominatorTree &DT, BlockFrequencyInfo &BFI)
Return a set of basic blocks to insert sinked instructions.
Definition: LoopSink.cpp:118
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::MemorySSA::Beginning
@ Beginning
Definition: MemorySSA.h:802
llvm::SinkAndHoistLICMFlags
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:115
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:194
false
Definition: StackSlotColoring.cpp:141
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::LoopSinkPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:324
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:372
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:76
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
BranchProbability.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
Definition: LoopSink.cpp:421
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::LoopPass
Definition: LoopPass.h:28
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:731
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:618
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
sinkInstruction
static bool sinkInstruction(Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU)
Definition: LoopSink.cpp:172
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::replaceDominatedUsesWith
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2732
sinkLoopInvariantInstructions
static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSA &MSSA, ScalarEvolution *SE)
Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is sm...
Definition: LoopSink.cpp:265
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
sink
gvn sink
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: GVNSink.cpp:926
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::MemorySSAUpdater::insertDef
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
Definition: MemorySSAUpdater.cpp:307
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
LoopPass.h
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:167
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::BranchProbability
Definition: BranchProbability.h:30
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1823
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:429
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:66
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::LoopInfoBase::getLoopsInPreorder
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:575
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1761
MaxNumberOfUseBBsForSinking
static cl::opt< unsigned > MaxNumberOfUseBBsForSinking("max-uses-for-sinking", cl::Hidden, cl::init(30), cl::desc("Do not sink instructions that have too many uses."))
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::Function::hasProfileData
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:290
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
AA
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
LoopSink.h
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:965
llvm::SmallVectorImpl< BasicBlock * >
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
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:405
InitializePasses.h
SinkFrequencyPercentThreshold
static cl::opt< unsigned > SinkFrequencyPercentThreshold("sink-freq-percent-threshold", cl::Hidden, cl::init(90), cl::desc("Do not sink instructions that require cloning unless they " "execute less than this percent of the time."))
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38