LLVM  10.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  I.replaceUsesWithIf(IC, [N](Use &U) {
234  return cast<Instruction>(U.getUser())->getParent() == N;
235  });
236  // Replaces uses of I with IC in blocks dominated by N
237  replaceDominatedUsesWith(&I, IC, DT, N);
238  LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
239  << '\n');
240  NumLoopSunkCloned++;
241  }
242  LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
243  NumLoopSunk++;
244  I.moveBefore(&*MoveBB->getFirstInsertionPt());
245 
246  return true;
247 }
248 
249 /// Sinks instructions from loop's preheader to the loop body if the
250 /// sum frequency of inserted copy is smaller than preheader's frequency.
252  DominatorTree &DT,
254  ScalarEvolution *SE) {
255  BasicBlock *Preheader = L.getLoopPreheader();
256  if (!Preheader)
257  return false;
258 
259  // Enable LoopSink only when runtime profile is available.
260  // With static profile, the sinking decision may be sub-optimal.
261  if (!Preheader->getParent()->hasProfileData())
262  return false;
263 
264  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
265  // If there are no basic blocks with lower frequency than the preheader then
266  // we can avoid the detailed analysis as we will never find profitable sinking
267  // opportunities.
268  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
269  return BFI.getBlockFreq(BB) > PreheaderFreq;
270  }))
271  return false;
272 
273  bool Changed = false;
274  AliasSetTracker CurAST(AA);
275 
276  // Compute alias set.
277  for (BasicBlock *BB : L.blocks())
278  CurAST.add(*BB);
279  CurAST.add(*Preheader);
280 
281  // Sort loop's basic blocks by frequency
282  SmallVector<BasicBlock *, 10> ColdLoopBBs;
283  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
284  int i = 0;
285  for (BasicBlock *B : L.blocks())
286  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
287  ColdLoopBBs.push_back(B);
288  LoopBlockNumber[B] = ++i;
289  }
290  llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
291  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
292  });
293 
294  // Traverse preheader's instructions in reverse order becaue if A depends
295  // on B (A appears after B), A needs to be sinked first before B can be
296  // sinked.
297  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
298  Instruction *I = &*II++;
299  // No need to check for instruction's operands are loop invariant.
301  "Insts in a loop's preheader should have loop invariant operands!");
302  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
303  continue;
304  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
305  Changed = true;
306  }
307 
308  if (Changed && SE)
309  SE->forgetLoopDispositions(&L);
310  return Changed;
311 }
312 
314  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
315  // Nothing to do if there are no loops.
316  if (LI.empty())
317  return PreservedAnalyses::all();
318 
319  AAResults &AA = FAM.getResult<AAManager>(F);
322 
323  // We want to do a postorder walk over the loops. Since loops are a tree this
324  // is equivalent to a reversed preorder walk and preorder is easy to compute
325  // without recursion. Since we reverse the preorder, we will visit siblings
326  // in reverse program order. This isn't expected to matter at all but is more
327  // consistent with sinking algorithms which generally work bottom-up.
328  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
329 
330  bool Changed = false;
331  do {
332  Loop &L = *PreorderLoops.pop_back_val();
333 
334  // Note that we don't pass SCEV here because it is only used to invalidate
335  // loops in SCEV and we don't preserve (or request) SCEV at all making that
336  // unnecessary.
337  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
338  /*ScalarEvolution*/ nullptr);
339  } while (!PreorderLoops.empty());
340 
341  if (!Changed)
342  return PreservedAnalyses::all();
343 
345  PA.preserveSet<CFGAnalyses>();
346  return PA;
347 }
348 
349 namespace {
350 struct LegacyLoopSinkPass : public LoopPass {
351  static char ID;
352  LegacyLoopSinkPass() : LoopPass(ID) {
354  }
355 
356  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
357  if (skipLoop(L))
358  return false;
359 
360  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
362  *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
363  getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
364  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
365  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
366  SE ? &SE->getSE() : nullptr);
367  }
368 
369  void getAnalysisUsage(AnalysisUsage &AU) const override {
370  AU.setPreservesCFG();
373  }
374 };
375 }
376 
377 char LegacyLoopSinkPass::ID = 0;
378 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
379  false)
382 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
383 
384 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
iterator_range< use_iterator > uses()
Definition: Value.h:374
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:926
bool empty() const
Definition: LoopInfo.h:907
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:160
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:1165
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:280
reverse_iterator rbegin()
Definition: BasicBlock.h:278
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:2496
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:67
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:928
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:1183
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
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
Definition: LoopSink.cpp:378
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
Definition: Value.h:300
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
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
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:251
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:1095
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:115
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:837
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:467
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:509
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:138
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:145
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:567
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:1289
static const Function * getParent(const Value *V)
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:1080
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:313
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
const BasicBlock * getParent() const
Definition: Instruction.h:66