LLVM 18.0.0git
Go to the documentation of this file.
1//===-- LoopSink.cpp - Loop Sink Pass -------------------------------------===//
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
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:
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
20// Overall algorithm:
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
35#include "llvm/ADT/Statistic.h"
43#include "llvm/IR/Dominators.h"
51using namespace llvm;
53#define DEBUG_TYPE "loopsink"
55STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
56STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
59 "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
60 cl::desc("Do not sink instructions that require cloning unless they "
61 "execute less than this percent of the time."));
64 "max-uses-for-sinking", cl::Hidden, cl::init(30),
65 cl::desc("Do not sink instructions that have too many uses."));
67/// Return adjusted total frequency of \p BBs.
69/// * If there is only one BB, sinking instruction will not introduce code
70/// size increase. Thus there is no need to adjust the frequency.
71/// * If there are more than one BB, sinking would lead to code size increase.
72/// In this case, we add some "tax" to the total frequency to make it harder
73/// to sink. E.g.
74/// Freq(Preheader) = 100
75/// Freq(BBs) = sum(50, 49) = 99
76/// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
77/// BBs as the difference is too small to justify the code size increase.
78/// To model this, The adjusted Freq(BBs) will be:
79/// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
81 BlockFrequencyInfo &BFI) {
82 BlockFrequency T = 0;
83 for (BasicBlock *B : BBs)
84 T += BFI.getBlockFreq(B);
85 if (BBs.size() > 1)
87 return T;
90/// Return a set of basic blocks to insert sinked instructions.
92/// The returned set of basic blocks (BBsToSinkInto) should satisfy:
94/// * Inside the loop \p L
95/// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
96/// that domintates the UseBB
97/// * Has minimum total frequency that is no greater than preheader frequency
99/// The purpose of the function is to find the optimal sinking points to
100/// minimize execution cost, which is defined as "sum of frequency of
101/// BBsToSinkInto".
102/// As a result, the returned BBsToSinkInto needs to have minimum total
103/// frequency.
104/// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
105/// frequency, the optimal solution is not sinking (return empty set).
107/// \p ColdLoopBBs is used to help find the optimal sinking locations.
108/// It stores a list of BBs that is:
110/// * Inside the loop \p L
111/// * Has a frequency no larger than the loop's preheader
112/// * Sorted by BB frequency
114/// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
115/// To avoid expensive computation, we cap the maximum UseBBs.size() in its
116/// caller.
119 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
121 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
122 if (UseBBs.size() == 0)
123 return BBsToSinkInto;
125 BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
126 SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
128 // For every iteration:
129 // * Pick the ColdestBB from ColdLoopBBs
130 // * Find the set BBsDominatedByColdestBB that satisfy:
131 // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
132 // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
133 // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
134 // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
135 // BBsToSinkInto
136 for (BasicBlock *ColdestBB : ColdLoopBBs) {
137 BBsDominatedByColdestBB.clear();
138 for (BasicBlock *SinkedBB : BBsToSinkInto)
139 if (DT.dominates(ColdestBB, SinkedBB))
140 BBsDominatedByColdestBB.insert(SinkedBB);
141 if (BBsDominatedByColdestBB.size() == 0)
142 continue;
143 if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
144 BFI.getBlockFreq(ColdestBB)) {
145 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
146 BBsToSinkInto.erase(DominatedBB);
147 }
148 BBsToSinkInto.insert(ColdestBB);
149 }
150 }
152 // Can't sink into blocks that have no valid insertion point.
153 for (BasicBlock *BB : BBsToSinkInto) {
154 if (BB->getFirstInsertionPt() == BB->end()) {
155 BBsToSinkInto.clear();
156 break;
157 }
158 }
160 // If the total frequency of BBsToSinkInto is larger than preheader frequency,
161 // do not sink.
162 if (adjustedSumFreq(BBsToSinkInto, BFI) >
163 BFI.getBlockFreq(L.getLoopPreheader()))
164 BBsToSinkInto.clear();
165 return BBsToSinkInto;
168// Sinks \p I from the loop \p L's preheader to its uses. Returns true if
169// sinking is successful.
170// \p LoopBlockNumber is used to sort the insertion blocks to ensure
171// determinism.
172static bool sinkInstruction(
173 Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
174 const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
176 // Compute the set of blocks in loop L which contain a use of I.
178 for (auto &U : I.uses()) {
179 Instruction *UI = cast<Instruction>(U.getUser());
181 // We cannot sink I if it has uses outside of the loop.
182 if (!L.contains(LI.getLoopFor(UI->getParent())))
183 return false;
185 if (!isa<PHINode>(UI)) {
186 BBs.insert(UI->getParent());
187 continue;
188 }
190 // We cannot sink I to PHI-uses, try to look through PHI to find the incoming
191 // block of the value being used.
192 PHINode *PN = dyn_cast<PHINode>(UI);
193 BasicBlock *PhiBB = PN->getIncomingBlock(U);
195 // If value's incoming block is from loop preheader directly, there's no
196 // place to sink to, bailout.
197 if (L.getLoopPreheader() == PhiBB)
198 return false;
200 BBs.insert(PhiBB);
201 }
203 // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
204 // BBs.size() to avoid expensive computation.
205 // FIXME: Handle code size growth for min_size and opt_size.
207 return false;
209 // Find the set of BBs that we should insert a copy of I.
210 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
211 findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
212 if (BBsToSinkInto.empty())
213 return false;
215 // Return if any of the candidate blocks to sink into is non-cold.
216 if (BBsToSinkInto.size() > 1 &&
217 !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
218 return false;
220 // Copy the final BBs into a vector and sort them using the total ordering
221 // of the loop block numbers as iterating the set doesn't give a useful
222 // order. No need to stable sort as the block numbers are a total ordering.
223 SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
224 llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
225 if (SortedBBsToSinkInto.size() > 1) {
226 llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
227 return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
228 });
229 }
231 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
232 // FIXME: Optimize the efficiency for cloned value replacement. The current
233 // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
234 for (BasicBlock *N : ArrayRef(SortedBBsToSinkInto).drop_front(1)) {
235 assert(LoopBlockNumber.find(N)->second >
236 LoopBlockNumber.find(MoveBB)->second &&
237 "BBs not sorted!");
238 // Clone I and replace its uses.
239 Instruction *IC = I.clone();
240 IC->setName(I.getName());
241 IC->insertBefore(&*N->getFirstInsertionPt());
243 if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
244 // Create a new MemoryAccess and let MemorySSA set its defining access.
245 MemoryAccess *NewMemAcc =
246 MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
247 if (NewMemAcc) {
248 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
249 MSSAU->insertDef(MemDef, /*RenameUses=*/true);
250 else {
251 auto *MemUse = cast<MemoryUse>(NewMemAcc);
252 MSSAU->insertUse(MemUse, /*RenameUses=*/true);
253 }
254 }
255 }
257 // Replaces uses of I with IC in N, except PHI-use which is being taken
258 // care of by defs in PHI's incoming blocks.
259 I.replaceUsesWithIf(IC, [N](Use &U) {
260 Instruction *UIToReplace = cast<Instruction>(U.getUser());
261 return UIToReplace->getParent() == N && !isa<PHINode>(UIToReplace);
262 });
263 // Replaces uses of I with IC in blocks dominated by N
264 replaceDominatedUsesWith(&I, IC, DT, N);
265 LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
266 << '\n');
267 NumLoopSunkCloned++;
268 }
269 LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
270 NumLoopSunk++;
271 I.moveBefore(&*MoveBB->getFirstInsertionPt());
273 if (MSSAU)
274 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
275 MSSAU->getMemorySSA()->getMemoryAccess(&I)))
276 MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
278 return true;
281/// Sinks instructions from loop's preheader to the loop body if the
282/// sum frequency of inserted copy is smaller than preheader's frequency.
284 DominatorTree &DT,
286 MemorySSA &MSSA,
287 ScalarEvolution *SE) {
288 BasicBlock *Preheader = L.getLoopPreheader();
289 assert(Preheader && "Expected loop to have preheader");
291 assert(Preheader->getParent()->hasProfileData() &&
292 "Unexpected call when profile data unavailable.");
294 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
295 // If there are no basic blocks with lower frequency than the preheader then
296 // we can avoid the detailed analysis as we will never find profitable sinking
297 // opportunities.
298 if (all_of(L.blocks(), [&](const BasicBlock *BB) {
299 return BFI.getBlockFreq(BB) > PreheaderFreq;
300 }))
301 return false;
303 MemorySSAUpdater MSSAU(&MSSA);
304 SinkAndHoistLICMFlags LICMFlags(/*IsSink=*/true, L, MSSA);
306 bool Changed = false;
308 // Sort loop's basic blocks by frequency
311 int i = 0;
312 for (BasicBlock *B : L.blocks())
313 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
314 ColdLoopBBs.push_back(B);
315 LoopBlockNumber[B] = ++i;
316 }
317 llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
318 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
319 });
321 // Traverse preheader's instructions in reverse order because if A depends
322 // on B (A appears after B), A needs to be sunk first before B can be
323 // sinked.
325 if (isa<PHINode>(&I))
326 continue;
327 // No need to check for instruction's operands are loop invariant.
328 assert(L.hasLoopInvariantOperands(&I) &&
329 "Insts in a loop's preheader should have loop invariant operands!");
330 if (!canSinkOrHoistInst(I, &AA, &DT, &L, MSSAU, false, LICMFlags))
331 continue;
332 if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
333 &MSSAU)) {
334 Changed = true;
335 if (SE)
337 }
338 }
340 return Changed;
344 // Enable LoopSink only when runtime profile is available.
345 // With static profile, the sinking decision may be sub-optimal.
346 if (!F.hasProfileData())
347 return PreservedAnalyses::all();
350 // Nothing to do if there are no loops.
351 if (LI.empty())
352 return PreservedAnalyses::all();
357 MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
359 // We want to do a postorder walk over the loops. Since loops are a tree this
360 // is equivalent to a reversed preorder walk and preorder is easy to compute
361 // without recursion. Since we reverse the preorder, we will visit siblings
362 // in reverse program order. This isn't expected to matter at all but is more
363 // consistent with sinking algorithms which generally work bottom-up.
364 SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
366 bool Changed = false;
367 do {
368 Loop &L = *PreorderLoops.pop_back_val();
370 BasicBlock *Preheader = L.getLoopPreheader();
371 if (!Preheader)
372 continue;
374 // Note that we don't pass SCEV here because it is only used to invalidate
375 // loops in SCEV and we don't preserve (or request) SCEV at all making that
376 // unnecessary.
377 Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, MSSA,
378 /*ScalarEvolution*/ nullptr);
379 } while (!PreorderLoops.empty());
381 if (!Changed)
382 return PreservedAnalyses::all();
388 if (VerifyMemorySSA)
389 MSSA.verifyMemorySSA();
391 return PA;
394namespace {
395struct LegacyLoopSinkPass : public LoopPass {
396 static char ID;
397 LegacyLoopSinkPass() : LoopPass(ID) {
399 }
401 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
402 if (skipLoop(L))
403 return false;
405 BasicBlock *Preheader = L->getLoopPreheader();
406 if (!Preheader)
407 return false;
409 // Enable LoopSink only when runtime profile is available.
410 // With static profile, the sinking decision may be sub-optimal.
411 if (!Preheader->getParent()->hasProfileData())
412 return false;
414 AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
415 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
416 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
417 bool Changed = sinkLoopInvariantInstructions(
418 *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
419 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
420 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
421 MSSA, SE ? &SE->getSE() : nullptr);
423 if (VerifyMemorySSA)
424 MSSA.verifyMemorySSA();
426 return Changed;
427 }
429 void getAnalysisUsage(AnalysisUsage &AU) const override {
430 AU.setPreservesCFG();
435 }
439char LegacyLoopSinkPass::ID = 0;
440INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
441 false)
445INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
447Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: LICM.cpp:1615
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."))
static bool sinkInstruction(Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU)
Definition: LoopSink.cpp:172
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:118
static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSA &MSSA, ScalarEvolution *SE)
Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is sm...
Definition: LoopSink.cpp:283
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:80
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."))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
FunctionAnalysisManager FAM
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
Definition: Statistic.h:167
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:257
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
Analysis pass which computes BlockFrequencyInfo.
Legacy analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:291
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:89
const BasicBlock * getParent() const
Definition: Instruction.h:90
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:569
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopSink.cpp:343
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block.
void insertUse(MemoryUse *Use, bool RenameUses=false)
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:975
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1857
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
The main scalar evolution driver.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:118
size_type size() const
Definition: SmallPtrSet.h:93
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
iterator end() const
Definition: SmallPtrSet.h:409
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:366
iterator begin() const
Definition: SmallPtrSet.h:404
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:378
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:1971
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:1727
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
Definition: LICM.cpp:1148
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:666
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1652
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2933
void initializeLegacyLoopSinkPassPass(PassRegistry &)
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:141
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
Pass * createLoopSinkPass()
#define N