LLVM 19.0.0git
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
35#include "llvm/ADT/Statistic.h"
42#include "llvm/IR/Dominators.h"
49using namespace llvm;
50
51#define DEBUG_TYPE "loopsink"
52
53STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
54STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
55
57 "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
58 cl::desc("Do not sink instructions that require cloning unless they "
59 "execute less than this percent of the time."));
60
62 "max-uses-for-sinking", cl::Hidden, cl::init(30),
63 cl::desc("Do not sink instructions that have too many uses."));
64
65/// Return adjusted total frequency of \p BBs.
66///
67/// * If there is only one BB, sinking instruction will not introduce code
68/// size increase. Thus there is no need to adjust the frequency.
69/// * If there are more than one BB, sinking would lead to code size increase.
70/// In this case, we add some "tax" to the total frequency to make it harder
71/// to sink. E.g.
72/// Freq(Preheader) = 100
73/// Freq(BBs) = sum(50, 49) = 99
74/// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
75/// BBs as the difference is too small to justify the code size increase.
76/// To model this, The adjusted Freq(BBs) will be:
77/// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
79 BlockFrequencyInfo &BFI) {
81 for (BasicBlock *B : BBs)
82 T += BFI.getBlockFreq(B);
83 if (BBs.size() > 1)
85 return T;
86}
87
88/// Return a set of basic blocks to insert sinked instructions.
89///
90/// The returned set of basic blocks (BBsToSinkInto) should satisfy:
91///
92/// * Inside the loop \p L
93/// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
94/// that domintates the UseBB
95/// * Has minimum total frequency that is no greater than preheader frequency
96///
97/// The purpose of the function is to find the optimal sinking points to
98/// minimize execution cost, which is defined as "sum of frequency of
99/// BBsToSinkInto".
100/// As a result, the returned BBsToSinkInto needs to have minimum total
101/// frequency.
102/// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
103/// frequency, the optimal solution is not sinking (return empty set).
104///
105/// \p ColdLoopBBs is used to help find the optimal sinking locations.
106/// It stores a list of BBs that is:
107///
108/// * Inside the loop \p L
109/// * Has a frequency no larger than the loop's preheader
110/// * Sorted by BB frequency
111///
112/// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
113/// To avoid expensive computation, we cap the maximum UseBBs.size() in its
114/// caller.
117 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
119 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
120 if (UseBBs.size() == 0)
121 return BBsToSinkInto;
122
123 BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
124 SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
125
126 // For every iteration:
127 // * Pick the ColdestBB from ColdLoopBBs
128 // * Find the set BBsDominatedByColdestBB that satisfy:
129 // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
130 // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
131 // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
132 // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
133 // BBsToSinkInto
134 for (BasicBlock *ColdestBB : ColdLoopBBs) {
135 BBsDominatedByColdestBB.clear();
136 for (BasicBlock *SinkedBB : BBsToSinkInto)
137 if (DT.dominates(ColdestBB, SinkedBB))
138 BBsDominatedByColdestBB.insert(SinkedBB);
139 if (BBsDominatedByColdestBB.size() == 0)
140 continue;
141 if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
142 BFI.getBlockFreq(ColdestBB)) {
143 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
144 BBsToSinkInto.erase(DominatedBB);
145 }
146 BBsToSinkInto.insert(ColdestBB);
147 }
148 }
149
150 // Can't sink into blocks that have no valid insertion point.
151 for (BasicBlock *BB : BBsToSinkInto) {
152 if (BB->getFirstInsertionPt() == BB->end()) {
153 BBsToSinkInto.clear();
154 break;
155 }
156 }
157
158 // If the total frequency of BBsToSinkInto is larger than preheader frequency,
159 // do not sink.
160 if (adjustedSumFreq(BBsToSinkInto, BFI) >
161 BFI.getBlockFreq(L.getLoopPreheader()))
162 BBsToSinkInto.clear();
163 return BBsToSinkInto;
164}
165
166// Sinks \p I from the loop \p L's preheader to its uses. Returns true if
167// sinking is successful.
168// \p LoopBlockNumber is used to sort the insertion blocks to ensure
169// determinism.
170static bool sinkInstruction(
171 Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
172 const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
174 // Compute the set of blocks in loop L which contain a use of I.
176 for (auto &U : I.uses()) {
177 Instruction *UI = cast<Instruction>(U.getUser());
178
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
183 if (!isa<PHINode>(UI)) {
184 BBs.insert(UI->getParent());
185 continue;
186 }
187
188 // We cannot sink I to PHI-uses, try to look through PHI to find the incoming
189 // block of the value being used.
190 PHINode *PN = dyn_cast<PHINode>(UI);
191 BasicBlock *PhiBB = PN->getIncomingBlock(U);
192
193 // If value's incoming block is from loop preheader directly, there's no
194 // place to sink to, bailout.
195 if (L.getLoopPreheader() == PhiBB)
196 return false;
197
198 BBs.insert(PhiBB);
199 }
200
201 // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
202 // BBs.size() to avoid expensive computation.
203 // FIXME: Handle code size growth for min_size and opt_size.
205 return false;
206
207 // Find the set of BBs that we should insert a copy of I.
208 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
209 findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
210 if (BBsToSinkInto.empty())
211 return false;
212
213 // Return if any of the candidate blocks to sink into is non-cold.
214 if (BBsToSinkInto.size() > 1 &&
215 !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
216 return false;
217
218 // Copy the final BBs into a vector and sort them using the total ordering
219 // of the loop block numbers as iterating the set doesn't give a useful
220 // order. No need to stable sort as the block numbers are a total ordering.
221 SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
222 llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
223 if (SortedBBsToSinkInto.size() > 1) {
224 llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
225 return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
226 });
227 }
228
229 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
230 // FIXME: Optimize the efficiency for cloned value replacement. The current
231 // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
232 for (BasicBlock *N : ArrayRef(SortedBBsToSinkInto).drop_front(1)) {
233 assert(LoopBlockNumber.find(N)->second >
234 LoopBlockNumber.find(MoveBB)->second &&
235 "BBs not sorted!");
236 // Clone I and replace its uses.
237 Instruction *IC = I.clone();
238 IC->setName(I.getName());
239 IC->insertBefore(&*N->getFirstInsertionPt());
240
241 if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
242 // Create a new MemoryAccess and let MemorySSA set its defining access.
243 MemoryAccess *NewMemAcc =
244 MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
245 if (NewMemAcc) {
246 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
247 MSSAU->insertDef(MemDef, /*RenameUses=*/true);
248 else {
249 auto *MemUse = cast<MemoryUse>(NewMemAcc);
250 MSSAU->insertUse(MemUse, /*RenameUses=*/true);
251 }
252 }
253 }
254
255 // Replaces uses of I with IC in N, except PHI-use which is being taken
256 // care of by defs in PHI's incoming blocks.
257 I.replaceUsesWithIf(IC, [N](Use &U) {
258 Instruction *UIToReplace = cast<Instruction>(U.getUser());
259 return UIToReplace->getParent() == N && !isa<PHINode>(UIToReplace);
260 });
261 // Replaces uses of I with IC in blocks dominated by N
262 replaceDominatedUsesWith(&I, IC, DT, N);
263 LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
264 << '\n');
265 NumLoopSunkCloned++;
266 }
267 LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
268 NumLoopSunk++;
269 I.moveBefore(&*MoveBB->getFirstInsertionPt());
270
271 if (MSSAU)
272 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
273 MSSAU->getMemorySSA()->getMemoryAccess(&I)))
274 MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
275
276 return true;
277}
278
279/// Sinks instructions from loop's preheader to the loop body if the
280/// sum frequency of inserted copy is smaller than preheader's frequency.
282 DominatorTree &DT,
284 MemorySSA &MSSA,
285 ScalarEvolution *SE) {
286 BasicBlock *Preheader = L.getLoopPreheader();
287 assert(Preheader && "Expected loop to have preheader");
288
289 assert(Preheader->getParent()->hasProfileData() &&
290 "Unexpected call when profile data unavailable.");
291
292 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
293 // If there are no basic blocks with lower frequency than the preheader then
294 // we can avoid the detailed analysis as we will never find profitable sinking
295 // opportunities.
296 if (all_of(L.blocks(), [&](const BasicBlock *BB) {
297 return BFI.getBlockFreq(BB) > PreheaderFreq;
298 }))
299 return false;
300
301 MemorySSAUpdater MSSAU(&MSSA);
302 SinkAndHoistLICMFlags LICMFlags(/*IsSink=*/true, L, MSSA);
303
304 bool Changed = false;
305
306 // Sort loop's basic blocks by frequency
309 int i = 0;
310 for (BasicBlock *B : L.blocks())
311 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
312 ColdLoopBBs.push_back(B);
313 LoopBlockNumber[B] = ++i;
314 }
315 llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
316 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
317 });
318
319 // Traverse preheader's instructions in reverse order because if A depends
320 // on B (A appears after B), A needs to be sunk first before B can be
321 // sinked.
323 if (isa<PHINode>(&I))
324 continue;
325 // No need to check for instruction's operands are loop invariant.
326 assert(L.hasLoopInvariantOperands(&I) &&
327 "Insts in a loop's preheader should have loop invariant operands!");
328 if (!canSinkOrHoistInst(I, &AA, &DT, &L, MSSAU, false, LICMFlags))
329 continue;
330 if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
331 &MSSAU)) {
332 Changed = true;
333 if (SE)
335 }
336 }
337
338 return Changed;
339}
340
342 // Enable LoopSink only when runtime profile is available.
343 // With static profile, the sinking decision may be sub-optimal.
344 if (!F.hasProfileData())
345 return PreservedAnalyses::all();
346
348 // Nothing to do if there are no loops.
349 if (LI.empty())
350 return PreservedAnalyses::all();
351
355 MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
356
357 // We want to do a postorder walk over the loops. Since loops are a tree this
358 // is equivalent to a reversed preorder walk and preorder is easy to compute
359 // without recursion. Since we reverse the preorder, we will visit siblings
360 // in reverse program order. This isn't expected to matter at all but is more
361 // consistent with sinking algorithms which generally work bottom-up.
362 SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
363
364 bool Changed = false;
365 do {
366 Loop &L = *PreorderLoops.pop_back_val();
367
368 BasicBlock *Preheader = L.getLoopPreheader();
369 if (!Preheader)
370 continue;
371
372 // Note that we don't pass SCEV here because it is only used to invalidate
373 // loops in SCEV and we don't preserve (or request) SCEV at all making that
374 // unnecessary.
375 Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, MSSA,
376 /*ScalarEvolution*/ nullptr);
377 } while (!PreorderLoops.empty());
378
379 if (!Changed)
380 return PreservedAnalyses::all();
381
385
386 if (VerifyMemorySSA)
387 MSSA.verifyMemorySSA();
388
389 return PA;
390}
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 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:170
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:116
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:281
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
Definition: LoopSink.cpp:78
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
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...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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:60
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:396
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
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: Analysis.h:70
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:162
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:314
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const BasicBlock * getParent() const
Definition: Instruction.h:151
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
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:341
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
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)
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
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.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
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:94
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
iterator end() const
Definition: SmallPtrSet.h:385
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:342
iterator begin() const
Definition: SmallPtrSet.h:380
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:377
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:2004
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:1731
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:1158
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 range R to container C.
Definition: STLExtras.h:2082
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:665
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
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:3449
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
#define N