LLVM  9.0.0svn
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/Statistic.h"
39 #include "llvm/Analysis/Loads.h"
40 #include "llvm/Analysis/LoopInfo.h"
41 #include "llvm/Analysis/LoopPass.h"
45 #include "llvm/IR/Dominators.h"
46 #include "llvm/IR/Instructions.h"
47 #include "llvm/IR/LLVMContext.h"
48 #include "llvm/IR/Metadata.h"
50 #include "llvm/Transforms/Scalar.h"
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "loopsink"
56 
57 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
58 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
59 
61  "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
62  cl::desc("Do not sink instructions that require cloning unless they "
63  "execute less than this percent of the time."));
64 
66  "max-uses-for-sinking", cl::Hidden, cl::init(30),
67  cl::desc("Do not sink instructions that have too many uses."));
68 
69 /// Return adjusted total frequency of \p BBs.
70 ///
71 /// * If there is only one BB, sinking instruction will not introduce code
72 /// size increase. Thus there is no need to adjust the frequency.
73 /// * If there are more than one BB, sinking would lead to code size increase.
74 /// In this case, we add some "tax" to the total frequency to make it harder
75 /// to sink. E.g.
76 /// Freq(Preheader) = 100
77 /// Freq(BBs) = sum(50, 49) = 99
78 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
79 /// BBs as the difference is too small to justify the code size increase.
80 /// To model this, The adjusted Freq(BBs) will be:
81 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
84  BlockFrequency T = 0;
85  for (BasicBlock *B : BBs)
86  T += BFI.getBlockFreq(B);
87  if (BBs.size() > 1)
89  return T;
90 }
91 
92 /// Return a set of basic blocks to insert sinked instructions.
93 ///
94 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
95 ///
96 /// * Inside the loop \p L
97 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
98 /// that domintates the UseBB
99 /// * Has minimum total frequency that is no greater than preheader frequency
100 ///
101 /// The purpose of the function is to find the optimal sinking points to
102 /// minimize execution cost, which is defined as "sum of frequency of
103 /// BBsToSinkInto".
104 /// As a result, the returned BBsToSinkInto needs to have minimum total
105 /// frequency.
106 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
107 /// frequency, the optimal solution is not sinking (return empty set).
108 ///
109 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
110 /// It stores a list of BBs that is:
111 ///
112 /// * Inside the loop \p L
113 /// * Has a frequency no larger than the loop's preheader
114 /// * Sorted by BB frequency
115 ///
116 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
117 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
118 /// caller.
121  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
123  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
124  if (UseBBs.size() == 0)
125  return BBsToSinkInto;
126 
127  BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
128  SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
129 
130  // For every iteration:
131  // * Pick the ColdestBB from ColdLoopBBs
132  // * Find the set BBsDominatedByColdestBB that satisfy:
133  // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
134  // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
135  // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
136  // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
137  // BBsToSinkInto
138  for (BasicBlock *ColdestBB : ColdLoopBBs) {
139  BBsDominatedByColdestBB.clear();
140  for (BasicBlock *SinkedBB : BBsToSinkInto)
141  if (DT.dominates(ColdestBB, SinkedBB))
142  BBsDominatedByColdestBB.insert(SinkedBB);
143  if (BBsDominatedByColdestBB.size() == 0)
144  continue;
145  if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
146  BFI.getBlockFreq(ColdestBB)) {
147  for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
148  BBsToSinkInto.erase(DominatedBB);
149  }
150  BBsToSinkInto.insert(ColdestBB);
151  }
152  }
153 
154  // Can't sink into blocks that have no valid insertion point.
155  for (BasicBlock *BB : BBsToSinkInto) {
156  if (BB->getFirstInsertionPt() == BB->end()) {
157  BBsToSinkInto.clear();
158  break;
159  }
160  }
161 
162  // If the total frequency of BBsToSinkInto is larger than preheader frequency,
163  // do not sink.
164  if (adjustedSumFreq(BBsToSinkInto, BFI) >
166  BBsToSinkInto.clear();
167  return BBsToSinkInto;
168 }
169 
170 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
171 // sinking is successful.
172 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
173 // determinism.
175  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
176  const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber,
177  LoopInfo &LI, DominatorTree &DT,
179  // Compute the set of blocks in loop L which contain a use of I.
181  for (auto &U : I.uses()) {
182  Instruction *UI = cast<Instruction>(U.getUser());
183  // We cannot sink I to PHI-uses.
184  if (dyn_cast<PHINode>(UI))
185  return false;
186  // We cannot sink I if it has uses outside of the loop.
187  if (!L.contains(LI.getLoopFor(UI->getParent())))
188  return false;
189  BBs.insert(UI->getParent());
190  }
191 
192  // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
193  // BBs.size() to avoid expensive computation.
194  // FIXME: Handle code size growth for min_size and opt_size.
195  if (BBs.size() > MaxNumberOfUseBBsForSinking)
196  return false;
197 
198  // Find the set of BBs that we should insert a copy of I.
199  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
200  findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
201  if (BBsToSinkInto.empty())
202  return false;
203 
204  // Return if any of the candidate blocks to sink into is non-cold.
205  if (BBsToSinkInto.size() > 1) {
206  for (auto *BB : BBsToSinkInto)
207  if (!LoopBlockNumber.count(BB))
208  return false;
209  }
210 
211  // Copy the final BBs into a vector and sort them using the total ordering
212  // of the loop block numbers as iterating the set doesn't give a useful
213  // order. No need to stable sort as the block numbers are a total ordering.
214  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
215  SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
216  BBsToSinkInto.end());
217  llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
218  return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
219  });
220 
221  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
222  // FIXME: Optimize the efficiency for cloned value replacement. The current
223  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
224  for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
225  assert(LoopBlockNumber.find(N)->second >
226  LoopBlockNumber.find(MoveBB)->second &&
227  "BBs not sorted!");
228  // Clone I and replace its uses.
229  Instruction *IC = I.clone();
230  IC->setName(I.getName());
231  IC->insertBefore(&*N->getFirstInsertionPt());
232  // Replaces uses of I with IC in N
233  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
234  Use &U = *UI++;
235  auto *I = cast<Instruction>(U.getUser());
236  if (I->getParent() == N)
237  U.set(IC);
238  }
239  // Replaces uses of I with IC in blocks dominated by N
240  replaceDominatedUsesWith(&I, IC, DT, N);
241  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
242  << '\n');
243  NumLoopSunkCloned++;
244  }
245  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
246  NumLoopSunk++;
247  I.moveBefore(&*MoveBB->getFirstInsertionPt());
248 
249  return true;
250 }
251 
252 /// Sinks instructions from loop's preheader to the loop body if the
253 /// sum frequency of inserted copy is smaller than preheader's frequency.
255  DominatorTree &DT,
257  ScalarEvolution *SE) {
258  BasicBlock *Preheader = L.getLoopPreheader();
259  if (!Preheader)
260  return false;
261 
262  // Enable LoopSink only when runtime profile is available.
263  // With static profile, the sinking decision may be sub-optimal.
264  if (!Preheader->getParent()->hasProfileData())
265  return false;
266 
267  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
268  // If there are no basic blocks with lower frequency than the preheader then
269  // we can avoid the detailed analysis as we will never find profitable sinking
270  // opportunities.
271  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
272  return BFI.getBlockFreq(BB) > PreheaderFreq;
273  }))
274  return false;
275 
276  bool Changed = false;
277  AliasSetTracker CurAST(AA);
278 
279  // Compute alias set.
280  for (BasicBlock *BB : L.blocks())
281  CurAST.add(*BB);
282  CurAST.add(*Preheader);
283 
284  // Sort loop's basic blocks by frequency
285  SmallVector<BasicBlock *, 10> ColdLoopBBs;
286  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
287  int i = 0;
288  for (BasicBlock *B : L.blocks())
289  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
290  ColdLoopBBs.push_back(B);
291  LoopBlockNumber[B] = ++i;
292  }
293  llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
294  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
295  });
296 
297  // Traverse preheader's instructions in reverse order becaue if A depends
298  // on B (A appears after B), A needs to be sinked first before B can be
299  // sinked.
300  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
301  Instruction *I = &*II++;
302  // No need to check for instruction's operands are loop invariant.
304  "Insts in a loop's preheader should have loop invariant operands!");
305  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
306  continue;
307  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
308  Changed = true;
309  }
310 
311  if (Changed && SE)
312  SE->forgetLoopDispositions(&L);
313  return Changed;
314 }
315 
317  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
318  // Nothing to do if there are no loops.
319  if (LI.empty())
320  return PreservedAnalyses::all();
321 
322  AAResults &AA = FAM.getResult<AAManager>(F);
325 
326  // We want to do a postorder walk over the loops. Since loops are a tree this
327  // is equivalent to a reversed preorder walk and preorder is easy to compute
328  // without recursion. Since we reverse the preorder, we will visit siblings
329  // in reverse program order. This isn't expected to matter at all but is more
330  // consistent with sinking algorithms which generally work bottom-up.
331  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
332 
333  bool Changed = false;
334  do {
335  Loop &L = *PreorderLoops.pop_back_val();
336 
337  // Note that we don't pass SCEV here because it is only used to invalidate
338  // loops in SCEV and we don't preserve (or request) SCEV at all making that
339  // unnecessary.
340  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
341  /*ScalarEvolution*/ nullptr);
342  } while (!PreorderLoops.empty());
343 
344  if (!Changed)
345  return PreservedAnalyses::all();
346 
348  PA.preserveSet<CFGAnalyses>();
349  return PA;
350 }
351 
352 namespace {
353 struct LegacyLoopSinkPass : public LoopPass {
354  static char ID;
355  LegacyLoopSinkPass() : LoopPass(ID) {
357  }
358 
359  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
360  if (skipLoop(L))
361  return false;
362 
363  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
365  *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
366  getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
367  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
368  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
369  SE ? &SE->getSE() : nullptr);
370  }
371 
372  void getAnalysisUsage(AnalysisUsage &AU) const override {
373  AU.setPreservesCFG();
376  }
377 };
378 }
379 
380 char LegacyLoopSinkPass::ID = 0;
381 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
382  false)
385 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
386 
387 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
use_iterator use_end()
Definition: Value.h:346
iterator_range< use_iterator > uses()
Definition: Value.h:354
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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:916
bool empty() const
Definition: LoopInfo.h:676
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
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:1185
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:275
reverse_iterator rbegin()
Definition: BasicBlock.h:273
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of &#39;From&#39; with &#39;To&#39; if that use is dominated by the given edge.
Definition: Local.cpp:2461
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:65
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
This is the interface for a SCEV-based alias analysis.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:697
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
Legacy analysis pass which computes BlockFrequencyInfo.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:952
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
#define T
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
Definition: LoopSink.cpp:381
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
use_iterator_impl< Use > use_iterator
Definition: Value.h:331
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void set(Value *Val)
Definition: Value.h:670
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
A manager for alias analyses.
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:370
Represent the analysis usage information of a pass.
static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, ScalarEvolution *SE)
Sinks instructions from loop&#39;s preheader to the loop body if the sum frequency of inserted copy is sm...
Definition: LoopSink.cpp:254
Pass * createLoopSinkPass()
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:308
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
size_type size() const
Definition: SmallPtrSet.h:92
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Analysis pass which computes BlockFrequencyInfo.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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."))
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:471
use_iterator use_begin()
Definition: Value.h:338
iterator begin() const
Definition: SmallPtrSet.h:396
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock *> &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:82
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:136
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:120
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
iterator end() const
Definition: SmallPtrSet.h:401
SmallVector< LoopT *, 4 > getLoopsInPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:582
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."))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeLegacyLoopSinkPassPass(PassRegistry &)
void stable_sort(R &&Range)
Definition: STLExtras.h:1309
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
static bool sinkInstruction(Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock *> &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI)
Definition: LoopSink.cpp:174
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:1069
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:316
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
const BasicBlock * getParent() const
Definition: Instruction.h:66