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  // Return if any of the candidate blocks to sink into is non-cold.
206  if (BBsToSinkInto.size() > 1) {
207  for (auto *BB : BBsToSinkInto)
208  if (!LoopBlockNumber.count(BB))
209  return false;
210  }
211 
212  // Copy the final BBs into a vector and sort them using the total ordering
213  // of the loop block numbers as iterating the set doesn't give a useful
214  // order. No need to stable sort as the block numbers are a total ordering.
215  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
216  SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
217  BBsToSinkInto.end());
218  llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
219  return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
220  });
221 
222  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
223  // FIXME: Optimize the efficiency for cloned value replacement. The current
224  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
225  for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
226  assert(LoopBlockNumber.find(N)->second >
227  LoopBlockNumber.find(MoveBB)->second &&
228  "BBs not sorted!");
229  // Clone I and replace its uses.
230  Instruction *IC = I.clone();
231  IC->setName(I.getName());
232  IC->insertBefore(&*N->getFirstInsertionPt());
233  // Replaces uses of I with IC in N
234  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
235  Use &U = *UI++;
236  auto *I = cast<Instruction>(U.getUser());
237  if (I->getParent() == N)
238  U.set(IC);
239  }
240  // Replaces uses of I with IC in blocks dominated by N
241  replaceDominatedUsesWith(&I, IC, DT, N);
242  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
243  << '\n');
244  NumLoopSunkCloned++;
245  }
246  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
247  NumLoopSunk++;
248  I.moveBefore(&*MoveBB->getFirstInsertionPt());
249 
250  return true;
251 }
252 
253 /// Sinks instructions from loop's preheader to the loop body if the
254 /// sum frequency of inserted copy is smaller than preheader's frequency.
256  DominatorTree &DT,
258  ScalarEvolution *SE) {
259  BasicBlock *Preheader = L.getLoopPreheader();
260  if (!Preheader)
261  return false;
262 
263  // Enable LoopSink only when runtime profile is available.
264  // With static profile, the sinking decision may be sub-optimal.
265  if (!Preheader->getParent()->hasProfileData())
266  return false;
267 
268  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
269  // If there are no basic blocks with lower frequency than the preheader then
270  // we can avoid the detailed analysis as we will never find profitable sinking
271  // opportunities.
272  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
273  return BFI.getBlockFreq(BB) > PreheaderFreq;
274  }))
275  return false;
276 
277  bool Changed = false;
278  AliasSetTracker CurAST(AA);
279 
280  // Compute alias set.
281  for (BasicBlock *BB : L.blocks())
282  CurAST.add(*BB);
283  CurAST.add(*Preheader);
284 
285  // Sort loop's basic blocks by frequency
286  SmallVector<BasicBlock *, 10> ColdLoopBBs;
287  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
288  int i = 0;
289  for (BasicBlock *B : L.blocks())
290  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
291  ColdLoopBBs.push_back(B);
292  LoopBlockNumber[B] = ++i;
293  }
294  std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
295  [&](BasicBlock *A, BasicBlock *B) {
296  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
297  });
298 
299  // Traverse preheader's instructions in reverse order becaue if A depends
300  // on B (A appears after B), A needs to be sinked first before B can be
301  // sinked.
302  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
303  Instruction *I = &*II++;
304  // No need to check for instruction's operands are loop invariant.
306  "Insts in a loop's preheader should have loop invariant operands!");
307  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, false))
308  continue;
309  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
310  Changed = true;
311  }
312 
313  if (Changed && SE)
314  SE->forgetLoopDispositions(&L);
315  return Changed;
316 }
317 
319  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
320  // Nothing to do if there are no loops.
321  if (LI.empty())
322  return PreservedAnalyses::all();
323 
324  AAResults &AA = FAM.getResult<AAManager>(F);
327 
328  // We want to do a postorder walk over the loops. Since loops are a tree this
329  // is equivalent to a reversed preorder walk and preorder is easy to compute
330  // without recursion. Since we reverse the preorder, we will visit siblings
331  // in reverse program order. This isn't expected to matter at all but is more
332  // consistent with sinking algorithms which generally work bottom-up.
333  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
334 
335  bool Changed = false;
336  do {
337  Loop &L = *PreorderLoops.pop_back_val();
338 
339  // Note that we don't pass SCEV here because it is only used to invalidate
340  // loops in SCEV and we don't preserve (or request) SCEV at all making that
341  // unnecessary.
342  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
343  /*ScalarEvolution*/ nullptr);
344  } while (!PreorderLoops.empty());
345 
346  if (!Changed)
347  return PreservedAnalyses::all();
348 
350  PA.preserveSet<CFGAnalyses>();
351  return PA;
352 }
353 
354 namespace {
355 struct LegacyLoopSinkPass : public LoopPass {
356  static char ID;
357  LegacyLoopSinkPass() : LoopPass(ID) {
359  }
360 
361  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
362  if (skipLoop(L))
363  return false;
364 
365  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
367  *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
368  getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
369  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
370  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
371  SE ? &SE->getSE() : nullptr);
372  }
373 
374  void getAnalysisUsage(AnalysisUsage &AU) const override {
375  AU.setPreservesCFG();
378  }
379 };
380 }
381 
382 char LegacyLoopSinkPass::ID = 0;
383 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
384  false)
387 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
388 
389 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
This class represents lattice values for constants.
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:918
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:1180
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:276
reverse_iterator rbegin()
Definition: BasicBlock.h:274
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:2454
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:64
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:286
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:383
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:419
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:58
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:255
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:1110
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:215
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#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
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: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:318
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