Go to the documentation of this file.
53 #define DEBUG_TYPE "loopsink"
55 STATISTIC(NumLoopSunk,
"Number of instructions sunk into loop");
56 STATISTIC(NumLoopSunkCloned,
"Number of cloned instructions sunk into loop");
60 cl::desc(
"Do not sink instructions that require cloning unless they "
61 "execute less than this percent of the time."));
65 cl::desc(
"Do not sink instructions that have too many uses."));
84 T +=
BFI.getBlockFreq(
B);
122 if (UseBBs.
size() == 0)
123 return BBsToSinkInto;
137 BBsDominatedByColdestBB.
clear();
140 BBsDominatedByColdestBB.
insert(SinkedBB);
141 if (BBsDominatedByColdestBB.
size() == 0)
144 BFI.getBlockFreq(ColdestBB)) {
145 for (
BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
146 BBsToSinkInto.erase(DominatedBB);
148 BBsToSinkInto.insert(ColdestBB);
154 if (
BB->getFirstInsertionPt() ==
BB->end()) {
155 BBsToSinkInto.clear();
164 BBsToSinkInto.clear();
165 return BBsToSinkInto;
178 for (
auto &U :
I.uses()) {
181 if (isa<PHINode>(UI))
198 if (BBsToSinkInto.
empty())
202 if (BBsToSinkInto.
size() > 1 &&
212 return LoopBlockNumber.
find(A)->second < LoopBlockNumber.
find(
B)->second;
215 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
220 LoopBlockNumber.
find(MoveBB)->second &&
232 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
235 auto *MemUse = cast<MemoryUse>(NewMemAcc);
242 I.replaceUsesWithIf(IC, [
N](
Use &U) {
251 LLVM_DEBUG(
dbgs() <<
"Sinking " <<
I <<
" To: " << MoveBB->getName() <<
'\n');
253 I.moveBefore(&*MoveBB->getFirstInsertionPt());
271 assert(Preheader &&
"Expected loop to have preheader");
274 "Unexpected call when profile data unavailable.");
281 return BFI.getBlockFreq(BB) > PreheaderFreq;
288 bool Changed =
false;
296 ColdLoopBBs.push_back(
B);
297 LoopBlockNumber[
B] = ++
i;
300 return BFI.getBlockFreq(A) <
BFI.getBlockFreq(
B);
307 if (isa<PHINode>(&
I))
311 "Insts in a loop's preheader should have loop invariant operands!");
343 bool Changed =
false;
361 }
while (!PreorderLoops.empty());
371 MSSA.verifyMemorySSA();
377 struct LegacyLoopSinkPass :
public LoopPass {
396 AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
397 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
398 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
400 *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
401 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
402 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
403 MSSA, SE ? &SE->getSE() :
nullptr);
A set of analyses that are preserved following a run of a transformation pass.
A manager for alias analyses.
This is an optimization pass for GlobalISel generic memory operations.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Legacy analysis pass which computes BlockFrequencyInfo.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
Return adjusted total frequency of BBs.
void initializeLegacyLoopSinkPassPass(PassRegistry &)
The main scalar evolution driver.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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 ...
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void insertUse(MemoryUse *Use, bool RenameUses=false)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass * createLoopSinkPass()
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.
Flags controlling how much is checked when sinking or hoisting instructions.
Represent the analysis usage information of a pass.
iterator_range< block_iterator > blocks() const
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
STATISTIC(NumFunctions, "Total number of functions")
void setName(const Twine &Name)
Change the name of the value.
User * getUser() const
Returns the User that contains this Use.
Analysis pass which computes BlockFrequencyInfo.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void sort(IteratorTy Start, IteratorTy End)
INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
Encapsulates MemorySSA, including all data associated with memory accesses.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
initializer< Ty > init(const Ty &Val)
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...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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)
An analysis that produces MemorySSA for a function.
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.
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...
gvn sink
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Represents analyses that only rely on functions' control flow.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
void stable_sort(R &&Range)
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."))
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Class that has the common methods + fields of memory uses/defs.
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Analysis pass which computes a DominatorTree.
Pass interface - Implemented by all 'passes'.
void preserveSet()
Mark an analysis set as preserved.
const BasicBlock * getParent() const
auto reverse(ContainerTy &&C)
ArrayRef(const T &OneElt) -> ArrayRef< T >
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A container for analyses that lazily runs them and caches their results.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
bool VerifyMemorySSA
Enables verification of MemorySSA.
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."))
Analysis pass that exposes the LoopInfo for a function.
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.