LLVM  14.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"
40 #include "llvm/Analysis/Loads.h"
41 #include "llvm/Analysis/LoopInfo.h"
42 #include "llvm/Analysis/LoopPass.h"
47 #include "llvm/IR/Dominators.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/LLVMContext.h"
50 #include "llvm/IR/Metadata.h"
51 #include "llvm/InitializePasses.h"
53 #include "llvm/Transforms/Scalar.h"
57 using namespace llvm;
58 
59 #define DEBUG_TYPE "loopsink"
60 
61 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
62 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
63 
65  "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
66  cl::desc("Do not sink instructions that require cloning unless they "
67  "execute less than this percent of the time."));
68 
70  "max-uses-for-sinking", cl::Hidden, cl::init(30),
71  cl::desc("Do not sink instructions that have too many uses."));
72 
74  "enable-mssa-in-loop-sink", cl::Hidden, cl::init(true),
75  cl::desc("Enable MemorySSA for LoopSink in new pass manager"));
76 
78  "enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false),
79  cl::desc("Enable MemorySSA for LoopSink in legacy pass manager"));
80 
81 /// Return adjusted total frequency of \p BBs.
82 ///
83 /// * If there is only one BB, sinking instruction will not introduce code
84 /// size increase. Thus there is no need to adjust the frequency.
85 /// * If there are more than one BB, sinking would lead to code size increase.
86 /// In this case, we add some "tax" to the total frequency to make it harder
87 /// to sink. E.g.
88 /// Freq(Preheader) = 100
89 /// Freq(BBs) = sum(50, 49) = 99
90 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
91 /// BBs as the difference is too small to justify the code size increase.
92 /// To model this, The adjusted Freq(BBs) will be:
93 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
96  BlockFrequency T = 0;
97  for (BasicBlock *B : BBs)
98  T += BFI.getBlockFreq(B);
99  if (BBs.size() > 1)
101  return T;
102 }
103 
104 /// Return a set of basic blocks to insert sinked instructions.
105 ///
106 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
107 ///
108 /// * Inside the loop \p L
109 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
110 /// that domintates the UseBB
111 /// * Has minimum total frequency that is no greater than preheader frequency
112 ///
113 /// The purpose of the function is to find the optimal sinking points to
114 /// minimize execution cost, which is defined as "sum of frequency of
115 /// BBsToSinkInto".
116 /// As a result, the returned BBsToSinkInto needs to have minimum total
117 /// frequency.
118 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
119 /// frequency, the optimal solution is not sinking (return empty set).
120 ///
121 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
122 /// It stores a list of BBs that is:
123 ///
124 /// * Inside the loop \p L
125 /// * Has a frequency no larger than the loop's preheader
126 /// * Sorted by BB frequency
127 ///
128 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
129 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
130 /// caller.
133  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
135  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
136  if (UseBBs.size() == 0)
137  return BBsToSinkInto;
138 
139  BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
140  SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
141 
142  // For every iteration:
143  // * Pick the ColdestBB from ColdLoopBBs
144  // * Find the set BBsDominatedByColdestBB that satisfy:
145  // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
146  // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
147  // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
148  // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
149  // BBsToSinkInto
150  for (BasicBlock *ColdestBB : ColdLoopBBs) {
151  BBsDominatedByColdestBB.clear();
152  for (BasicBlock *SinkedBB : BBsToSinkInto)
153  if (DT.dominates(ColdestBB, SinkedBB))
154  BBsDominatedByColdestBB.insert(SinkedBB);
155  if (BBsDominatedByColdestBB.size() == 0)
156  continue;
157  if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
158  BFI.getBlockFreq(ColdestBB)) {
159  for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
160  BBsToSinkInto.erase(DominatedBB);
161  }
162  BBsToSinkInto.insert(ColdestBB);
163  }
164  }
165 
166  // Can't sink into blocks that have no valid insertion point.
167  for (BasicBlock *BB : BBsToSinkInto) {
168  if (BB->getFirstInsertionPt() == BB->end()) {
169  BBsToSinkInto.clear();
170  break;
171  }
172  }
173 
174  // If the total frequency of BBsToSinkInto is larger than preheader frequency,
175  // do not sink.
176  if (adjustedSumFreq(BBsToSinkInto, BFI) >
177  BFI.getBlockFreq(L.getLoopPreheader()))
178  BBsToSinkInto.clear();
179  return BBsToSinkInto;
180 }
181 
182 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
183 // sinking is successful.
184 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
185 // determinism.
186 static bool sinkInstruction(
187  Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
188  const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
190  // Compute the set of blocks in loop L which contain a use of I.
192  for (auto &U : I.uses()) {
193  Instruction *UI = cast<Instruction>(U.getUser());
194  // We cannot sink I to PHI-uses.
195  if (isa<PHINode>(UI))
196  return false;
197  // We cannot sink I if it has uses outside of the loop.
198  if (!L.contains(LI.getLoopFor(UI->getParent())))
199  return false;
200  BBs.insert(UI->getParent());
201  }
202 
203  // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
204  // BBs.size() to avoid expensive computation.
205  // FIXME: Handle code size growth for min_size and opt_size.
206  if (BBs.size() > MaxNumberOfUseBBsForSinking)
207  return false;
208 
209  // Find the set of BBs that we should insert a copy of I.
210  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
211  findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
212  if (BBsToSinkInto.empty())
213  return false;
214 
215  // Return if any of the candidate blocks to sink into is non-cold.
216  if (BBsToSinkInto.size() > 1 &&
217  !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
218  return false;
219 
220  // Copy the final BBs into a vector and sort them using the total ordering
221  // of the loop block numbers as iterating the set doesn't give a useful
222  // order. No need to stable sort as the block numbers are a total ordering.
223  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
224  llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
225  llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
226  return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
227  });
228 
229  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
230  // FIXME: Optimize the efficiency for cloned value replacement. The current
231  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
232  for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
233  assert(LoopBlockNumber.find(N)->second >
234  LoopBlockNumber.find(MoveBB)->second &&
235  "BBs not sorted!");
236  // Clone I and replace its uses.
237  Instruction *IC = I.clone();
238  IC->setName(I.getName());
239  IC->insertBefore(&*N->getFirstInsertionPt());
240 
241  if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
242  // Create a new MemoryAccess and let MemorySSA set its defining access.
243  MemoryAccess *NewMemAcc =
244  MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
245  if (NewMemAcc) {
246  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
247  MSSAU->insertDef(MemDef, /*RenameUses=*/true);
248  else {
249  auto *MemUse = cast<MemoryUse>(NewMemAcc);
250  MSSAU->insertUse(MemUse, /*RenameUses=*/true);
251  }
252  }
253  }
254 
255  // Replaces uses of I with IC in N
256  I.replaceUsesWithIf(IC, [N](Use &U) {
257  return cast<Instruction>(U.getUser())->getParent() == N;
258  });
259  // Replaces uses of I with IC in blocks dominated by N
260  replaceDominatedUsesWith(&I, IC, DT, N);
261  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
262  << '\n');
263  NumLoopSunkCloned++;
264  }
265  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
266  NumLoopSunk++;
267  I.moveBefore(&*MoveBB->getFirstInsertionPt());
268 
269  if (MSSAU)
270  if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
271  MSSAU->getMemorySSA()->getMemoryAccess(&I)))
272  MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
273 
274  return true;
275 }
276 
277 /// Sinks instructions from loop's preheader to the loop body if the
278 /// sum frequency of inserted copy is smaller than preheader's frequency.
280  DominatorTree &DT,
282  ScalarEvolution *SE,
283  AliasSetTracker *CurAST,
284  MemorySSA *MSSA) {
285  BasicBlock *Preheader = L.getLoopPreheader();
286  assert(Preheader && "Expected loop to have preheader");
287 
288  assert(Preheader->getParent()->hasProfileData() &&
289  "Unexpected call when profile data unavailable.");
290 
291  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
292  // If there are no basic blocks with lower frequency than the preheader then
293  // we can avoid the detailed analysis as we will never find profitable sinking
294  // opportunities.
295  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
296  return BFI.getBlockFreq(BB) > PreheaderFreq;
297  }))
298  return false;
299 
300  std::unique_ptr<MemorySSAUpdater> MSSAU;
301  std::unique_ptr<SinkAndHoistLICMFlags> LICMFlags;
302  if (MSSA) {
303  MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
304  LICMFlags =
305  std::make_unique<SinkAndHoistLICMFlags>(/*IsSink=*/true, &L, MSSA);
306  }
307 
308  bool Changed = false;
309 
310  // Sort loop's basic blocks by frequency
311  SmallVector<BasicBlock *, 10> ColdLoopBBs;
312  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
313  int i = 0;
314  for (BasicBlock *B : L.blocks())
315  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
316  ColdLoopBBs.push_back(B);
317  LoopBlockNumber[B] = ++i;
318  }
319  llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
320  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
321  });
322 
323  // Traverse preheader's instructions in reverse order becaue if A depends
324  // on B (A appears after B), A needs to be sinked first before B can be
325  // sinked.
326  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
327  Instruction *I = &*II++;
328  // No need to check for instruction's operands are loop invariant.
330  "Insts in a loop's preheader should have loop invariant operands!");
331  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, CurAST, MSSAU.get(), false,
332  LICMFlags.get()))
333  continue;
334  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
335  MSSAU.get()))
336  Changed = true;
337  }
338 
339  if (Changed && SE)
340  SE->forgetLoopDispositions(&L);
341  return Changed;
342 }
343 
344 static void computeAliasSet(Loop &L, BasicBlock &Preheader,
345  AliasSetTracker &CurAST) {
346  for (BasicBlock *BB : L.blocks())
347  CurAST.add(*BB);
348  CurAST.add(Preheader);
349 }
350 
353  // Nothing to do if there are no loops.
354  if (LI.empty())
355  return PreservedAnalyses::all();
356 
360 
362  ? &FAM.getResult<MemorySSAAnalysis>(F).getMSSA()
363  : nullptr;
364 
365  // We want to do a postorder walk over the loops. Since loops are a tree this
366  // is equivalent to a reversed preorder walk and preorder is easy to compute
367  // without recursion. Since we reverse the preorder, we will visit siblings
368  // in reverse program order. This isn't expected to matter at all but is more
369  // consistent with sinking algorithms which generally work bottom-up.
370  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
371 
372  bool Changed = false;
373  do {
374  Loop &L = *PreorderLoops.pop_back_val();
375 
376  BasicBlock *Preheader = L.getLoopPreheader();
377  if (!Preheader)
378  continue;
379 
380  // Enable LoopSink only when runtime profile is available.
381  // With static profile, the sinking decision may be sub-optimal.
382  if (!Preheader->getParent()->hasProfileData())
383  continue;
384 
385  std::unique_ptr<AliasSetTracker> CurAST;
386  if (!EnableMSSAInLoopSink) {
387  CurAST = std::make_unique<AliasSetTracker>(AA);
388  computeAliasSet(L, *Preheader, *CurAST.get());
389  }
390 
391  // Note that we don't pass SCEV here because it is only used to invalidate
392  // loops in SCEV and we don't preserve (or request) SCEV at all making that
393  // unnecessary.
394  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
395  /*ScalarEvolution*/ nullptr,
396  CurAST.get(), MSSA);
397  } while (!PreorderLoops.empty());
398 
399  if (!Changed)
400  return PreservedAnalyses::all();
401 
403  PA.preserveSet<CFGAnalyses>();
404 
405  if (MSSA) {
407 
408  if (VerifyMemorySSA)
409  MSSA->verifyMemorySSA();
410  }
411 
412  return PA;
413 }
414 
415 namespace {
416 struct LegacyLoopSinkPass : public LoopPass {
417  static char ID;
418  LegacyLoopSinkPass() : LoopPass(ID) {
420  }
421 
422  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
423  if (skipLoop(L))
424  return false;
425 
426  BasicBlock *Preheader = L->getLoopPreheader();
427  if (!Preheader)
428  return false;
429 
430  // Enable LoopSink only when runtime profile is available.
431  // With static profile, the sinking decision may be sub-optimal.
432  if (!Preheader->getParent()->hasProfileData())
433  return false;
434 
435  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
436  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
437  std::unique_ptr<AliasSetTracker> CurAST;
438  MemorySSA *MSSA = nullptr;
440  MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
441  else {
442  CurAST = std::make_unique<AliasSetTracker>(AA);
443  computeAliasSet(*L, *Preheader, *CurAST.get());
444  }
445 
446  bool Changed = sinkLoopInvariantInstructions(
447  *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
448  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
449  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
450  SE ? &SE->getSE() : nullptr, CurAST.get(), MSSA);
451 
452  if (MSSA && VerifyMemorySSA)
453  MSSA->verifyMemorySSA();
454 
455  return Changed;
456  }
457 
458  void getAnalysisUsage(AnalysisUsage &AU) const override {
459  AU.setPreservesCFG();
465  }
466  }
467 };
468 }
469 
470 char LegacyLoopSinkPass::ID = 0;
471 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
472  false)
476 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
477 
478 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:155
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1288
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:1899
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:71
Metadata.h
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:779
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:7542
Loads.h
T
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
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:1168
adjustedSumFreq
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:94
llvm::initializeLegacyLoopSinkPassPass
void initializeLegacyLoopSinkPassPass(PassRegistry &)
Statistic.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
Local.h
sinkLoopInvariantInstructions
static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, ScalarEvolution *SE, AliasSetTracker *CurAST, MemorySSA *MSSA)
Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is sm...
Definition: LoopSink.cpp:279
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:149
llvm::AliasSetTracker
Definition: AliasSetTracker.h:329
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
ScalarEvolution.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
BasicAliasAnalysis.h
llvm::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:303
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:1433
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
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:58
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:115
CommandLine.h
llvm::MemorySSAUpdater::insertUse
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:245
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:1551
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:981
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:132
llvm::AAResults
Definition: AliasAnalysis.h:508
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MemorySSA::Beginning
@ Beginning
Definition: MemorySSA.h:793
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:178
false
Definition: StackSlotColoring.cpp:142
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1204
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
computeAliasSet
static void computeAliasSet(Loop &L, BasicBlock &Preheader, AliasSetTracker &CurAST)
Definition: LoopSink.cpp:344
EnableMSSAInLoopSink
static cl::opt< bool > EnableMSSAInLoopSink("enable-mssa-in-loop-sink", cl::Hidden, cl::init(true), cl::desc("Enable MemorySSA for LoopSink in new pass manager"))
llvm::LoopSinkPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:351
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:376
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
LoopUtils.h
llvm::BasicBlock::rbegin
reverse_iterator rbegin()
Definition: BasicBlock.h:301
llvm::LPPassManager
Definition: LoopPass.h:75
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
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:471
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::BlockFrequency
Definition: BlockFrequency.h:24
llvm::AliasSetTracker::add
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
Definition: AliasSetTracker.cpp:397
llvm::LoopPass
Definition: LoopPass.h:27
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:244
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:705
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:722
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
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:150
llvm::canSinkOrHoistInst
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags *LICMFlags=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:1154
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:186
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:931
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:2706
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
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:924
EnableMSSAInLegacyLoopSink
static cl::opt< bool > EnableMSSAInLegacyLoopSink("enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false), cl::desc("Enable MemorySSA for LoopSink in legacy pass manager"))
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::MemorySSAUpdater::insertDef
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
Definition: MemorySSAUpdater.cpp:314
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
LoopPass.h
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:171
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:1748
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
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:70
llvm::MemoryAccess
Definition: MemorySSA.h:137
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
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:578
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1686
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:161
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:247
llvm::Function::hasProfileData
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:302
ScalarEvolutionAliasAnalysis.h
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
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:191
LoopSink.h
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:946
llvm::SmallVectorImpl< BasicBlock * >
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
AliasSetTracker.h
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
LLVMContext.h
llvm::cl::desc
Definition: CommandLine.h:414
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:1243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37