LLVM  8.0.0svn
LoopSink.cpp
Go to the documentation of this file.
1 //===-- LoopSink.cpp - Loop Sink Pass -------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass does the inverse transformation of what LICM does.
11 // It traverses all of the instructions in the loop's preheader and sinks
12 // them to the loop body where frequency is lower than the loop's preheader.
13 // This pass is a reverse-transformation of LICM. It differs from the Sink
14 // pass in the following ways:
15 //
16 // * It only handles sinking of instructions from the loop's preheader to the
17 // loop's body
18 // * It uses alias set tracker to get more accurate alias info
19 // * It uses block frequency info to find the optimal sinking locations
20 //
21 // Overall algorithm:
22 //
23 // For I in Preheader:
24 // InsertBBs = BBs that uses I
25 // For BB in sorted(LoopBBs):
26 // DomBBs = BBs in InsertBBs that are dominated by BB
27 // if freq(DomBBs) > freq(BB)
28 // InsertBBs = UseBBs - DomBBs + BB
29 // For BB in InsertBBs:
30 // Insert I at BB's beginning
31 //
32 //===----------------------------------------------------------------------===//
33 
35 #include "llvm/ADT/Statistic.h"
40 #include "llvm/Analysis/Loads.h"
41 #include "llvm/Analysis/LoopInfo.h"
42 #include "llvm/Analysis/LoopPass.h"
46 #include "llvm/IR/Dominators.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/LLVMContext.h"
49 #include "llvm/IR/Metadata.h"
51 #include "llvm/Transforms/Scalar.h"
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "loopsink"
57 
58 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
59 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
60 
62  "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
63  cl::desc("Do not sink instructions that require cloning unless they "
64  "execute less than this percent of the time."));
65 
67  "max-uses-for-sinking", cl::Hidden, cl::init(30),
68  cl::desc("Do not sink instructions that have too many uses."));
69 
70 /// Return adjusted total frequency of \p BBs.
71 ///
72 /// * If there is only one BB, sinking instruction will not introduce code
73 /// size increase. Thus there is no need to adjust the frequency.
74 /// * If there are more than one BB, sinking would lead to code size increase.
75 /// In this case, we add some "tax" to the total frequency to make it harder
76 /// to sink. E.g.
77 /// Freq(Preheader) = 100
78 /// Freq(BBs) = sum(50, 49) = 99
79 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
80 /// BBs as the difference is too small to justify the code size increase.
81 /// To model this, The adjusted Freq(BBs) will be:
82 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
85  BlockFrequency T = 0;
86  for (BasicBlock *B : BBs)
87  T += BFI.getBlockFreq(B);
88  if (BBs.size() > 1)
90  return T;
91 }
92 
93 /// Return a set of basic blocks to insert sinked instructions.
94 ///
95 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
96 ///
97 /// * Inside the loop \p L
98 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
99 /// that domintates the UseBB
100 /// * Has minimum total frequency that is no greater than preheader frequency
101 ///
102 /// The purpose of the function is to find the optimal sinking points to
103 /// minimize execution cost, which is defined as "sum of frequency of
104 /// BBsToSinkInto".
105 /// As a result, the returned BBsToSinkInto needs to have minimum total
106 /// frequency.
107 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
108 /// frequency, the optimal solution is not sinking (return empty set).
109 ///
110 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
111 /// It stores a list of BBs that is:
112 ///
113 /// * Inside the loop \p L
114 /// * Has a frequency no larger than the loop's preheader
115 /// * Sorted by BB frequency
116 ///
117 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
118 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
119 /// caller.
122  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
124  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
125  if (UseBBs.size() == 0)
126  return BBsToSinkInto;
127 
128  BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
129  SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
130 
131  // For every iteration:
132  // * Pick the ColdestBB from ColdLoopBBs
133  // * Find the set BBsDominatedByColdestBB that satisfy:
134  // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
135  // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
136  // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
137  // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
138  // BBsToSinkInto
139  for (BasicBlock *ColdestBB : ColdLoopBBs) {
140  BBsDominatedByColdestBB.clear();
141  for (BasicBlock *SinkedBB : BBsToSinkInto)
142  if (DT.dominates(ColdestBB, SinkedBB))
143  BBsDominatedByColdestBB.insert(SinkedBB);
144  if (BBsDominatedByColdestBB.size() == 0)
145  continue;
146  if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
147  BFI.getBlockFreq(ColdestBB)) {
148  for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
149  BBsToSinkInto.erase(DominatedBB);
150  }
151  BBsToSinkInto.insert(ColdestBB);
152  }
153  }
154 
155  // Can't sink into blocks that have no valid insertion point.
156  for (BasicBlock *BB : BBsToSinkInto) {
157  if (BB->getFirstInsertionPt() == BB->end()) {
158  BBsToSinkInto.clear();
159  break;
160  }
161  }
162 
163  // If the total frequency of BBsToSinkInto is larger than preheader frequency,
164  // do not sink.
165  if (adjustedSumFreq(BBsToSinkInto, BFI) >
167  BBsToSinkInto.clear();
168  return BBsToSinkInto;
169 }
170 
171 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
172 // sinking is successful.
173 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
174 // determinism.
176  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
177  const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber,
178  LoopInfo &LI, DominatorTree &DT,
180  // Compute the set of blocks in loop L which contain a use of I.
182  for (auto &U : I.uses()) {
183  Instruction *UI = cast<Instruction>(U.getUser());
184  // We cannot sink I to PHI-uses.
185  if (dyn_cast<PHINode>(UI))
186  return false;
187  // We cannot sink I if it has uses outside of the loop.
188  if (!L.contains(LI.getLoopFor(UI->getParent())))
189  return false;
190  BBs.insert(UI->getParent());
191  }
192 
193  // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
194  // BBs.size() to avoid expensive computation.
195  // FIXME: Handle code size growth for min_size and opt_size.
196  if (BBs.size() > MaxNumberOfUseBBsForSinking)
197  return false;
198 
199  // Find the set of BBs that we should insert a copy of I.
200  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
201  findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
202  if (BBsToSinkInto.empty())
203  return false;
204 
205  // Copy the final BBs into a vector and sort them using the total ordering
206  // of the loop block numbers as iterating the set doesn't give a useful
207  // order. No need to stable sort as the block numbers are a total ordering.
208  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
209  SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
210  BBsToSinkInto.end());
211  llvm::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(),
212  [&](BasicBlock *A, BasicBlock *B) {
213  return LoopBlockNumber.find(A)->second <
214  LoopBlockNumber.find(B)->second;
215  });
216 
217  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
218  // FIXME: Optimize the efficiency for cloned value replacement. The current
219  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
220  for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
221  assert(LoopBlockNumber.find(N)->second >
222  LoopBlockNumber.find(MoveBB)->second &&
223  "BBs not sorted!");
224  // Clone I and replace its uses.
225  Instruction *IC = I.clone();
226  IC->setName(I.getName());
227  IC->insertBefore(&*N->getFirstInsertionPt());
228  // Replaces uses of I with IC in N
229  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
230  Use &U = *UI++;
231  auto *I = cast<Instruction>(U.getUser());
232  if (I->getParent() == N)
233  U.set(IC);
234  }
235  // Replaces uses of I with IC in blocks dominated by N
236  replaceDominatedUsesWith(&I, IC, DT, N);
237  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
238  << '\n');
239  NumLoopSunkCloned++;
240  }
241  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
242  NumLoopSunk++;
243  I.moveBefore(&*MoveBB->getFirstInsertionPt());
244 
245  return true;
246 }
247 
248 /// Sinks instructions from loop's preheader to the loop body if the
249 /// sum frequency of inserted copy is smaller than preheader's frequency.
251  DominatorTree &DT,
253  ScalarEvolution *SE) {
254  BasicBlock *Preheader = L.getLoopPreheader();
255  if (!Preheader)
256  return false;
257 
258  // Enable LoopSink only when runtime profile is available.
259  // With static profile, the sinking decision may be sub-optimal.
260  if (!Preheader->getParent()->hasProfileData())
261  return false;
262 
263  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
264  // If there are no basic blocks with lower frequency than the preheader then
265  // we can avoid the detailed analysis as we will never find profitable sinking
266  // opportunities.
267  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
268  return BFI.getBlockFreq(BB) > PreheaderFreq;
269  }))
270  return false;
271 
272  bool Changed = false;
273  AliasSetTracker CurAST(AA);
274 
275  // Compute alias set.
276  for (BasicBlock *BB : L.blocks())
277  CurAST.add(*BB);
278 
279  // Sort loop's basic blocks by frequency
280  SmallVector<BasicBlock *, 10> ColdLoopBBs;
281  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
282  int i = 0;
283  for (BasicBlock *B : L.blocks())
284  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
285  ColdLoopBBs.push_back(B);
286  LoopBlockNumber[B] = ++i;
287  }
288  std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
289  [&](BasicBlock *A, BasicBlock *B) {
290  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
291  });
292 
293  // Traverse preheader's instructions in reverse order becaue if A depends
294  // on B (A appears after B), A needs to be sinked first before B can be
295  // sinked.
296  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
297  Instruction *I = &*II++;
298  // No need to check for instruction's operands are loop invariant.
300  "Insts in a loop's preheader should have loop invariant operands!");
301  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, false))
302  continue;
303  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
304  Changed = true;
305  }
306 
307  if (Changed && SE)
308  SE->forgetLoopDispositions(&L);
309  return Changed;
310 }
311 
313  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
314  // Nothing to do if there are no loops.
315  if (LI.empty())
316  return PreservedAnalyses::all();
317 
318  AAResults &AA = FAM.getResult<AAManager>(F);
321 
322  // We want to do a postorder walk over the loops. Since loops are a tree this
323  // is equivalent to a reversed preorder walk and preorder is easy to compute
324  // without recursion. Since we reverse the preorder, we will visit siblings
325  // in reverse program order. This isn't expected to matter at all but is more
326  // consistent with sinking algorithms which generally work bottom-up.
327  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
328 
329  bool Changed = false;
330  do {
331  Loop &L = *PreorderLoops.pop_back_val();
332 
333  // Note that we don't pass SCEV here because it is only used to invalidate
334  // loops in SCEV and we don't preserve (or request) SCEV at all making that
335  // unnecessary.
336  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
337  /*ScalarEvolution*/ nullptr);
338  } while (!PreorderLoops.empty());
339 
340  if (!Changed)
341  return PreservedAnalyses::all();
342 
344  PA.preserveSet<CFGAnalyses>();
345  return PA;
346 }
347 
348 namespace {
349 struct LegacyLoopSinkPass : public LoopPass {
350  static char ID;
351  LegacyLoopSinkPass() : LoopPass(ID) {
353  }
354 
355  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
356  if (skipLoop(L))
357  return false;
358 
359  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
361  *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
362  getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
363  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
364  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
365  SE ? &SE->getSE() : nullptr);
366  }
367 
368  void getAnalysisUsage(AnalysisUsage &AU) const override {
369  AU.setPreservesCFG();
372  }
373 };
374 }
375 
376 char LegacyLoopSinkPass::ID = 0;
377 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
378  false)
381 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
382 
383 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
use_iterator use_end()
Definition: Value.h:347
iterator_range< use_iterator > uses()
Definition: Value.h:355
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:920
bool empty() const
Definition: LoopInfo.h:663
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:174
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, bool TargetExecutesOncePerLoop, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:629
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:1042
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:271
reverse_iterator rbegin()
Definition: BasicBlock.h:269
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:2437
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:63
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
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:684
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Legacy analysis pass which computes BlockFrequencyInfo.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:939
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:41
#define T
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
Definition: LoopSink.cpp:377
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
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:332
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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:154
void set(Value *Val)
Definition: Value.h:671
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:371
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:250
Pass * createLoopSinkPass()
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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:972
size_type size() const
Definition: SmallPtrSet.h:93
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:418
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
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:133
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:115
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:478
use_iterator use_begin()
Definition: Value.h:339
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
iterator begin() const
Definition: SmallPtrSet.h:397
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock *> &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:83
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#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:128
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:121
iterator end() const
Definition: SmallPtrSet.h:402
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:580
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 moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:87
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:175
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:123
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:312
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
bool hasProfileData() const
Return true if the function is annotated with profile data.
Definition: Function.h:308
const BasicBlock * getParent() const
Definition: Instruction.h:67