LLVM  17.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 : ArrayRef(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 because if A depends
304  // on B (A appears after B), A needs to be sunk 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  if (SE)
319  }
320  }
321 
322  return Changed;
323 }
324 
327  // Nothing to do if there are no loops.
328  if (LI.empty())
329  return PreservedAnalyses::all();
330 
334  MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
335 
336  // We want to do a postorder walk over the loops. Since loops are a tree this
337  // is equivalent to a reversed preorder walk and preorder is easy to compute
338  // without recursion. Since we reverse the preorder, we will visit siblings
339  // in reverse program order. This isn't expected to matter at all but is more
340  // consistent with sinking algorithms which generally work bottom-up.
341  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
342 
343  bool Changed = false;
344  do {
345  Loop &L = *PreorderLoops.pop_back_val();
346 
347  BasicBlock *Preheader = L.getLoopPreheader();
348  if (!Preheader)
349  continue;
350 
351  // Enable LoopSink only when runtime profile is available.
352  // With static profile, the sinking decision may be sub-optimal.
353  if (!Preheader->getParent()->hasProfileData())
354  continue;
355 
356  // Note that we don't pass SCEV here because it is only used to invalidate
357  // loops in SCEV and we don't preserve (or request) SCEV at all making that
358  // unnecessary.
359  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, MSSA,
360  /*ScalarEvolution*/ nullptr);
361  } while (!PreorderLoops.empty());
362 
363  if (!Changed)
364  return PreservedAnalyses::all();
365 
367  PA.preserveSet<CFGAnalyses>();
369 
370  if (VerifyMemorySSA)
371  MSSA.verifyMemorySSA();
372 
373  return PA;
374 }
375 
376 namespace {
377 struct LegacyLoopSinkPass : public LoopPass {
378  static char ID;
379  LegacyLoopSinkPass() : LoopPass(ID) {
381  }
382 
383  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
384  if (skipLoop(L))
385  return false;
386 
387  BasicBlock *Preheader = L->getLoopPreheader();
388  if (!Preheader)
389  return false;
390 
391  // Enable LoopSink only when runtime profile is available.
392  // With static profile, the sinking decision may be sub-optimal.
393  if (!Preheader->getParent()->hasProfileData())
394  return false;
395 
396  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
397  MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
398  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
399  bool Changed = sinkLoopInvariantInstructions(
400  *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
401  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
402  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
403  MSSA, SE ? &SE->getSE() : nullptr);
404 
405  if (VerifyMemorySSA)
406  MSSA.verifyMemorySSA();
407 
408  return Changed;
409  }
410 
411  void getAnalysisUsage(AnalysisUsage &AU) const override {
412  AU.setPreservesCFG();
417  }
418 };
419 }
420 
421 char LegacyLoopSinkPass::ID = 0;
422 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
423  false)
427 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
428 
429 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:885
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1863
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::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
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:774
Scalar.h
SetOperations.h
T
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:59
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
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:1199
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:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:452
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:88
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:141
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:138
ScalarEvolution.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:1150
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:1735
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:986
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:294
llvm::MemorySSA::Beginning
@ Beginning
Definition: MemorySSA.h:788
llvm::SinkAndHoistLICMFlags
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:114
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:195
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:41
llvm::LoopSinkPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:325
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:375
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:59
LoopInfo.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1683
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
Definition: LoopSink.cpp:422
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::cl::opt
Definition: CommandLine.h:1410
llvm::ScalarEvolution::forgetBlockAndLoopDispositions
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
Definition: ScalarEvolution.cpp:8552
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:700
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
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:717
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:721
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
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:150
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:936
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:2844
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:927
llvm::LoopInfo
Definition: LoopInfo.h:1108
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:265
LoopPass.h
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:166
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:2014
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:433
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:587
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1948
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::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:289
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
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
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:90
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:971
llvm::SmallVectorImpl< BasicBlock * >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
llvm::ArrayRef
ArrayRef(const T &OneElt) -> ArrayRef< T >
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:89
llvm::cl::desc
Definition: CommandLine.h:411
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:1268
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