LLVM  6.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"
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"
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  // If the total frequency of BBsToSinkInto is larger than preheader frequency,
156  // do not sink.
157  if (adjustedSumFreq(BBsToSinkInto, BFI) >
159  BBsToSinkInto.clear();
160  return BBsToSinkInto;
161 }
162 
163 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
164 // sinking is successful.
165 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
166 // determinism.
168  const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
169  const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber,
170  LoopInfo &LI, DominatorTree &DT,
172  // Compute the set of blocks in loop L which contain a use of I.
174  for (auto &U : I.uses()) {
175  Instruction *UI = cast<Instruction>(U.getUser());
176  // We cannot sink I to PHI-uses.
177  if (dyn_cast<PHINode>(UI))
178  return false;
179  // We cannot sink I if it has uses outside of the loop.
180  if (!L.contains(LI.getLoopFor(UI->getParent())))
181  return false;
182  BBs.insert(UI->getParent());
183  }
184 
185  // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
186  // BBs.size() to avoid expensive computation.
187  // FIXME: Handle code size growth for min_size and opt_size.
188  if (BBs.size() > MaxNumberOfUseBBsForSinking)
189  return false;
190 
191  // Find the set of BBs that we should insert a copy of I.
192  SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
193  findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
194  if (BBsToSinkInto.empty())
195  return false;
196 
197  // Copy the final BBs into a vector and sort them using the total ordering
198  // of the loop block numbers as iterating the set doesn't give a useful
199  // order. No need to stable sort as the block numbers are a total ordering.
200  SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
201  SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
202  BBsToSinkInto.end());
203  std::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(),
204  [&](BasicBlock *A, BasicBlock *B) {
205  return *LoopBlockNumber.find(A) < *LoopBlockNumber.find(B);
206  });
207 
208  BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
209  // FIXME: Optimize the efficiency for cloned value replacement. The current
210  // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
211  for (BasicBlock *N : SortedBBsToSinkInto) {
212  if (N == MoveBB)
213  continue;
214  // Clone I and replace its uses.
215  Instruction *IC = I.clone();
216  IC->setName(I.getName());
217  IC->insertBefore(&*N->getFirstInsertionPt());
218  // Replaces uses of I with IC in N
219  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
220  Use &U = *UI++;
221  auto *I = cast<Instruction>(U.getUser());
222  if (I->getParent() == N)
223  U.set(IC);
224  }
225  // Replaces uses of I with IC in blocks dominated by N
226  replaceDominatedUsesWith(&I, IC, DT, N);
227  DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
228  << '\n');
229  NumLoopSunkCloned++;
230  }
231  DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
232  NumLoopSunk++;
233  I.moveBefore(&*MoveBB->getFirstInsertionPt());
234 
235  return true;
236 }
237 
238 /// Sinks instructions from loop's preheader to the loop body if the
239 /// sum frequency of inserted copy is smaller than preheader's frequency.
241  DominatorTree &DT,
243  ScalarEvolution *SE) {
244  BasicBlock *Preheader = L.getLoopPreheader();
245  if (!Preheader)
246  return false;
247 
248  // Enable LoopSink only when runtime profile is available.
249  // With static profile, the sinking decision may be sub-optimal.
250  if (!Preheader->getParent()->getEntryCount())
251  return false;
252 
253  const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
254  // If there are no basic blocks with lower frequency than the preheader then
255  // we can avoid the detailed analysis as we will never find profitable sinking
256  // opportunities.
257  if (all_of(L.blocks(), [&](const BasicBlock *BB) {
258  return BFI.getBlockFreq(BB) > PreheaderFreq;
259  }))
260  return false;
261 
262  bool Changed = false;
263  AliasSetTracker CurAST(AA);
264 
265  // Compute alias set.
266  for (BasicBlock *BB : L.blocks())
267  CurAST.add(*BB);
268 
269  // Sort loop's basic blocks by frequency
270  SmallVector<BasicBlock *, 10> ColdLoopBBs;
271  SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
272  int i = 0;
273  for (BasicBlock *B : L.blocks())
274  if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
275  ColdLoopBBs.push_back(B);
276  LoopBlockNumber[B] = ++i;
277  }
278  std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
279  [&](BasicBlock *A, BasicBlock *B) {
280  return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
281  });
282 
283  // Traverse preheader's instructions in reverse order becaue if A depends
284  // on B (A appears after B), A needs to be sinked first before B can be
285  // sinked.
286  for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
287  Instruction *I = &*II++;
288  // No need to check for instruction's operands are loop invariant.
290  "Insts in a loop's preheader should have loop invariant operands!");
291  if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
292  continue;
293  if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
294  Changed = true;
295  }
296 
297  if (Changed && SE)
298  SE->forgetLoopDispositions(&L);
299  return Changed;
300 }
301 
303  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
304  // Nothing to do if there are no loops.
305  if (LI.empty())
306  return PreservedAnalyses::all();
307 
308  AAResults &AA = FAM.getResult<AAManager>(F);
311 
312  // We want to do a postorder walk over the loops. Since loops are a tree this
313  // is equivalent to a reversed preorder walk and preorder is easy to compute
314  // without recursion. Since we reverse the preorder, we will visit siblings
315  // in reverse program order. This isn't expected to matter at all but is more
316  // consistent with sinking algorithms which generally work bottom-up.
317  SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
318 
319  bool Changed = false;
320  do {
321  Loop &L = *PreorderLoops.pop_back_val();
322 
323  // Note that we don't pass SCEV here because it is only used to invalidate
324  // loops in SCEV and we don't preserve (or request) SCEV at all making that
325  // unnecessary.
326  Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
327  /*ScalarEvolution*/ nullptr);
328  } while (!PreorderLoops.empty());
329 
330  if (!Changed)
331  return PreservedAnalyses::all();
332 
334  PA.preserveSet<CFGAnalyses>();
335  return PA;
336 }
337 
338 namespace {
339 struct LegacyLoopSinkPass : public LoopPass {
340  static char ID;
341  LegacyLoopSinkPass() : LoopPass(ID) {
343  }
344 
345  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
346  if (skipLoop(L))
347  return false;
348 
349  auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
351  *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
352  getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
353  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
354  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
355  SE ? &SE->getSE() : nullptr);
356  }
357 
358  void getAnalysisUsage(AnalysisUsage &AU) const override {
359  AU.setPreservesCFG();
362  }
363 };
364 }
365 
366 char LegacyLoopSinkPass::ID = 0;
367 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
368  false)
371 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
372 
373 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:348
iterator_range< use_iterator > uses()
Definition: Value.h:356
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:923
bool empty() const
Definition: LoopInfo.h:657
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
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...
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:106
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:813
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:259
reverse_iterator rbegin()
Definition: BasicBlock.h:257
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:1877
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:62
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:678
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:933
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:367
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:333
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:677
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:75
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:116
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:240
Pass * createLoopSinkPass()
Optional< uint64_t > getEntryCount() const
Get the entry count for this function.
Definition: Function.cpp:1330
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
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:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
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:482
use_iterator use_begin()
Definition: Value.h:340
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
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:439
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:220
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:1023
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:512
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:88
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:167
#define DEBUG(X)
Definition: Debug.h:118
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.
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if the hoister and sinker can handle this instruction.
Definition: LICM.cpp:580
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:302
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
const BasicBlock * getParent() const
Definition: Instruction.h:66