10b57cec5SDimitry Andric //===-- LoopSink.cpp - Loop Sink Pass -------------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This pass does the inverse transformation of what LICM does.
100b57cec5SDimitry Andric // It traverses all of the instructions in the loop's preheader and sinks
110b57cec5SDimitry Andric // them to the loop body where frequency is lower than the loop's preheader.
120b57cec5SDimitry Andric // This pass is a reverse-transformation of LICM. It differs from the Sink
130b57cec5SDimitry Andric // pass in the following ways:
140b57cec5SDimitry Andric //
150b57cec5SDimitry Andric // * It only handles sinking of instructions from the loop's preheader to the
160b57cec5SDimitry Andric // loop's body
170b57cec5SDimitry Andric // * It uses alias set tracker to get more accurate alias info
180b57cec5SDimitry Andric // * It uses block frequency info to find the optimal sinking locations
190b57cec5SDimitry Andric //
200b57cec5SDimitry Andric // Overall algorithm:
210b57cec5SDimitry Andric //
220b57cec5SDimitry Andric // For I in Preheader:
230b57cec5SDimitry Andric // InsertBBs = BBs that uses I
240b57cec5SDimitry Andric // For BB in sorted(LoopBBs):
250b57cec5SDimitry Andric // DomBBs = BBs in InsertBBs that are dominated by BB
260b57cec5SDimitry Andric // if freq(DomBBs) > freq(BB)
270b57cec5SDimitry Andric // InsertBBs = UseBBs - DomBBs + BB
280b57cec5SDimitry Andric // For BB in InsertBBs:
290b57cec5SDimitry Andric // Insert I at BB's beginning
300b57cec5SDimitry Andric //
310b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
320b57cec5SDimitry Andric
330b57cec5SDimitry Andric #include "llvm/Transforms/Scalar/LoopSink.h"
34fe6060f1SDimitry Andric #include "llvm/ADT/SetOperations.h"
350b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h"
360b57cec5SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h"
370b57cec5SDimitry Andric #include "llvm/Analysis/BlockFrequencyInfo.h"
380b57cec5SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
39e8d8bef9SDimitry Andric #include "llvm/Analysis/MemorySSA.h"
40e8d8bef9SDimitry Andric #include "llvm/Analysis/MemorySSAUpdater.h"
410b57cec5SDimitry Andric #include "llvm/Analysis/ScalarEvolution.h"
420b57cec5SDimitry Andric #include "llvm/IR/Dominators.h"
430b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
4481ad6265SDimitry Andric #include "llvm/Support/BranchProbability.h"
450b57cec5SDimitry Andric #include "llvm/Support/CommandLine.h"
460b57cec5SDimitry Andric #include "llvm/Transforms/Scalar.h"
47480093f4SDimitry Andric #include "llvm/Transforms/Utils/Local.h"
480b57cec5SDimitry Andric #include "llvm/Transforms/Utils/LoopUtils.h"
490b57cec5SDimitry Andric using namespace llvm;
500b57cec5SDimitry Andric
510b57cec5SDimitry Andric #define DEBUG_TYPE "loopsink"
520b57cec5SDimitry Andric
530b57cec5SDimitry Andric STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
540b57cec5SDimitry Andric STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
550b57cec5SDimitry Andric
560b57cec5SDimitry Andric static cl::opt<unsigned> SinkFrequencyPercentThreshold(
570b57cec5SDimitry Andric "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
580b57cec5SDimitry Andric cl::desc("Do not sink instructions that require cloning unless they "
590b57cec5SDimitry Andric "execute less than this percent of the time."));
600b57cec5SDimitry Andric
610b57cec5SDimitry Andric static cl::opt<unsigned> MaxNumberOfUseBBsForSinking(
620b57cec5SDimitry Andric "max-uses-for-sinking", cl::Hidden, cl::init(30),
630b57cec5SDimitry Andric cl::desc("Do not sink instructions that have too many uses."));
640b57cec5SDimitry Andric
650b57cec5SDimitry Andric /// Return adjusted total frequency of \p BBs.
660b57cec5SDimitry Andric ///
670b57cec5SDimitry Andric /// * If there is only one BB, sinking instruction will not introduce code
680b57cec5SDimitry Andric /// size increase. Thus there is no need to adjust the frequency.
690b57cec5SDimitry Andric /// * If there are more than one BB, sinking would lead to code size increase.
700b57cec5SDimitry Andric /// In this case, we add some "tax" to the total frequency to make it harder
710b57cec5SDimitry Andric /// to sink. E.g.
720b57cec5SDimitry Andric /// Freq(Preheader) = 100
730b57cec5SDimitry Andric /// Freq(BBs) = sum(50, 49) = 99
740b57cec5SDimitry Andric /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
750b57cec5SDimitry Andric /// BBs as the difference is too small to justify the code size increase.
760b57cec5SDimitry Andric /// To model this, The adjusted Freq(BBs) will be:
770b57cec5SDimitry Andric /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
adjustedSumFreq(SmallPtrSetImpl<BasicBlock * > & BBs,BlockFrequencyInfo & BFI)780b57cec5SDimitry Andric static BlockFrequency adjustedSumFreq(SmallPtrSetImpl<BasicBlock *> &BBs,
790b57cec5SDimitry Andric BlockFrequencyInfo &BFI) {
805f757f3fSDimitry Andric BlockFrequency T(0);
810b57cec5SDimitry Andric for (BasicBlock *B : BBs)
820b57cec5SDimitry Andric T += BFI.getBlockFreq(B);
830b57cec5SDimitry Andric if (BBs.size() > 1)
840b57cec5SDimitry Andric T /= BranchProbability(SinkFrequencyPercentThreshold, 100);
850b57cec5SDimitry Andric return T;
860b57cec5SDimitry Andric }
870b57cec5SDimitry Andric
880b57cec5SDimitry Andric /// Return a set of basic blocks to insert sinked instructions.
890b57cec5SDimitry Andric ///
900b57cec5SDimitry Andric /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
910b57cec5SDimitry Andric ///
920b57cec5SDimitry Andric /// * Inside the loop \p L
930b57cec5SDimitry Andric /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
940b57cec5SDimitry Andric /// that domintates the UseBB
950b57cec5SDimitry Andric /// * Has minimum total frequency that is no greater than preheader frequency
960b57cec5SDimitry Andric ///
970b57cec5SDimitry Andric /// The purpose of the function is to find the optimal sinking points to
980b57cec5SDimitry Andric /// minimize execution cost, which is defined as "sum of frequency of
990b57cec5SDimitry Andric /// BBsToSinkInto".
1000b57cec5SDimitry Andric /// As a result, the returned BBsToSinkInto needs to have minimum total
1010b57cec5SDimitry Andric /// frequency.
1020b57cec5SDimitry Andric /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
1030b57cec5SDimitry Andric /// frequency, the optimal solution is not sinking (return empty set).
1040b57cec5SDimitry Andric ///
1050b57cec5SDimitry Andric /// \p ColdLoopBBs is used to help find the optimal sinking locations.
1060b57cec5SDimitry Andric /// It stores a list of BBs that is:
1070b57cec5SDimitry Andric ///
1080b57cec5SDimitry Andric /// * Inside the loop \p L
1090b57cec5SDimitry Andric /// * Has a frequency no larger than the loop's preheader
1100b57cec5SDimitry Andric /// * Sorted by BB frequency
1110b57cec5SDimitry Andric ///
1120b57cec5SDimitry Andric /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
1130b57cec5SDimitry Andric /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
1140b57cec5SDimitry Andric /// caller.
1150b57cec5SDimitry Andric static SmallPtrSet<BasicBlock *, 2>
findBBsToSinkInto(const Loop & L,const SmallPtrSetImpl<BasicBlock * > & UseBBs,const SmallVectorImpl<BasicBlock * > & ColdLoopBBs,DominatorTree & DT,BlockFrequencyInfo & BFI)1160b57cec5SDimitry Andric findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs,
1170b57cec5SDimitry Andric const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
1180b57cec5SDimitry Andric DominatorTree &DT, BlockFrequencyInfo &BFI) {
1190b57cec5SDimitry Andric SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
1200b57cec5SDimitry Andric if (UseBBs.size() == 0)
1210b57cec5SDimitry Andric return BBsToSinkInto;
1220b57cec5SDimitry Andric
1230b57cec5SDimitry Andric BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
1240b57cec5SDimitry Andric SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
1250b57cec5SDimitry Andric
1260b57cec5SDimitry Andric // For every iteration:
1270b57cec5SDimitry Andric // * Pick the ColdestBB from ColdLoopBBs
1280b57cec5SDimitry Andric // * Find the set BBsDominatedByColdestBB that satisfy:
1290b57cec5SDimitry Andric // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
1300b57cec5SDimitry Andric // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
1310b57cec5SDimitry Andric // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
1320b57cec5SDimitry Andric // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
1330b57cec5SDimitry Andric // BBsToSinkInto
1340b57cec5SDimitry Andric for (BasicBlock *ColdestBB : ColdLoopBBs) {
1350b57cec5SDimitry Andric BBsDominatedByColdestBB.clear();
1360b57cec5SDimitry Andric for (BasicBlock *SinkedBB : BBsToSinkInto)
1370b57cec5SDimitry Andric if (DT.dominates(ColdestBB, SinkedBB))
1380b57cec5SDimitry Andric BBsDominatedByColdestBB.insert(SinkedBB);
1390b57cec5SDimitry Andric if (BBsDominatedByColdestBB.size() == 0)
1400b57cec5SDimitry Andric continue;
1410b57cec5SDimitry Andric if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
1420b57cec5SDimitry Andric BFI.getBlockFreq(ColdestBB)) {
1430b57cec5SDimitry Andric for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
1440b57cec5SDimitry Andric BBsToSinkInto.erase(DominatedBB);
1450b57cec5SDimitry Andric }
1460b57cec5SDimitry Andric BBsToSinkInto.insert(ColdestBB);
1470b57cec5SDimitry Andric }
1480b57cec5SDimitry Andric }
1490b57cec5SDimitry Andric
1500b57cec5SDimitry Andric // Can't sink into blocks that have no valid insertion point.
1510b57cec5SDimitry Andric for (BasicBlock *BB : BBsToSinkInto) {
1520b57cec5SDimitry Andric if (BB->getFirstInsertionPt() == BB->end()) {
1530b57cec5SDimitry Andric BBsToSinkInto.clear();
1540b57cec5SDimitry Andric break;
1550b57cec5SDimitry Andric }
1560b57cec5SDimitry Andric }
1570b57cec5SDimitry Andric
1580b57cec5SDimitry Andric // If the total frequency of BBsToSinkInto is larger than preheader frequency,
1590b57cec5SDimitry Andric // do not sink.
1600b57cec5SDimitry Andric if (adjustedSumFreq(BBsToSinkInto, BFI) >
1610b57cec5SDimitry Andric BFI.getBlockFreq(L.getLoopPreheader()))
1620b57cec5SDimitry Andric BBsToSinkInto.clear();
1630b57cec5SDimitry Andric return BBsToSinkInto;
1640b57cec5SDimitry Andric }
1650b57cec5SDimitry Andric
1660b57cec5SDimitry Andric // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
1670b57cec5SDimitry Andric // sinking is successful.
1680b57cec5SDimitry Andric // \p LoopBlockNumber is used to sort the insertion blocks to ensure
1690b57cec5SDimitry Andric // determinism.
sinkInstruction(Loop & L,Instruction & I,const SmallVectorImpl<BasicBlock * > & ColdLoopBBs,const SmallDenseMap<BasicBlock *,int,16> & LoopBlockNumber,LoopInfo & LI,DominatorTree & DT,BlockFrequencyInfo & BFI,MemorySSAUpdater * MSSAU)170e8d8bef9SDimitry Andric static bool sinkInstruction(
171e8d8bef9SDimitry Andric Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
172e8d8bef9SDimitry Andric const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
173e8d8bef9SDimitry Andric DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU) {
1740b57cec5SDimitry Andric // Compute the set of blocks in loop L which contain a use of I.
1750b57cec5SDimitry Andric SmallPtrSet<BasicBlock *, 2> BBs;
1760b57cec5SDimitry Andric for (auto &U : I.uses()) {
1770b57cec5SDimitry Andric Instruction *UI = cast<Instruction>(U.getUser());
17806c3fb27SDimitry Andric
1790b57cec5SDimitry Andric // We cannot sink I if it has uses outside of the loop.
1800b57cec5SDimitry Andric if (!L.contains(LI.getLoopFor(UI->getParent())))
1810b57cec5SDimitry Andric return false;
18206c3fb27SDimitry Andric
18306c3fb27SDimitry Andric if (!isa<PHINode>(UI)) {
1840b57cec5SDimitry Andric BBs.insert(UI->getParent());
18506c3fb27SDimitry Andric continue;
18606c3fb27SDimitry Andric }
18706c3fb27SDimitry Andric
18806c3fb27SDimitry Andric // We cannot sink I to PHI-uses, try to look through PHI to find the incoming
18906c3fb27SDimitry Andric // block of the value being used.
19006c3fb27SDimitry Andric PHINode *PN = dyn_cast<PHINode>(UI);
19106c3fb27SDimitry Andric BasicBlock *PhiBB = PN->getIncomingBlock(U);
19206c3fb27SDimitry Andric
19306c3fb27SDimitry Andric // If value's incoming block is from loop preheader directly, there's no
19406c3fb27SDimitry Andric // place to sink to, bailout.
19506c3fb27SDimitry Andric if (L.getLoopPreheader() == PhiBB)
19606c3fb27SDimitry Andric return false;
19706c3fb27SDimitry Andric
19806c3fb27SDimitry Andric BBs.insert(PhiBB);
1990b57cec5SDimitry Andric }
2000b57cec5SDimitry Andric
2010b57cec5SDimitry Andric // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
2020b57cec5SDimitry Andric // BBs.size() to avoid expensive computation.
2030b57cec5SDimitry Andric // FIXME: Handle code size growth for min_size and opt_size.
2040b57cec5SDimitry Andric if (BBs.size() > MaxNumberOfUseBBsForSinking)
2050b57cec5SDimitry Andric return false;
2060b57cec5SDimitry Andric
2070b57cec5SDimitry Andric // Find the set of BBs that we should insert a copy of I.
2080b57cec5SDimitry Andric SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
2090b57cec5SDimitry Andric findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
2100b57cec5SDimitry Andric if (BBsToSinkInto.empty())
2110b57cec5SDimitry Andric return false;
2120b57cec5SDimitry Andric
2130b57cec5SDimitry Andric // Return if any of the candidate blocks to sink into is non-cold.
214fe6060f1SDimitry Andric if (BBsToSinkInto.size() > 1 &&
215fe6060f1SDimitry Andric !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
2160b57cec5SDimitry Andric return false;
2170b57cec5SDimitry Andric
2180b57cec5SDimitry Andric // Copy the final BBs into a vector and sort them using the total ordering
2190b57cec5SDimitry Andric // of the loop block numbers as iterating the set doesn't give a useful
2200b57cec5SDimitry Andric // order. No need to stable sort as the block numbers are a total ordering.
2210b57cec5SDimitry Andric SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
222e8d8bef9SDimitry Andric llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
2235f757f3fSDimitry Andric if (SortedBBsToSinkInto.size() > 1) {
2240b57cec5SDimitry Andric llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
2250b57cec5SDimitry Andric return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
2260b57cec5SDimitry Andric });
2275f757f3fSDimitry Andric }
2280b57cec5SDimitry Andric
2290b57cec5SDimitry Andric BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
2300b57cec5SDimitry Andric // FIXME: Optimize the efficiency for cloned value replacement. The current
2310b57cec5SDimitry Andric // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
232bdd1243dSDimitry Andric for (BasicBlock *N : ArrayRef(SortedBBsToSinkInto).drop_front(1)) {
2330b57cec5SDimitry Andric assert(LoopBlockNumber.find(N)->second >
2340b57cec5SDimitry Andric LoopBlockNumber.find(MoveBB)->second &&
2350b57cec5SDimitry Andric "BBs not sorted!");
2360b57cec5SDimitry Andric // Clone I and replace its uses.
2370b57cec5SDimitry Andric Instruction *IC = I.clone();
2380b57cec5SDimitry Andric IC->setName(I.getName());
2390b57cec5SDimitry Andric IC->insertBefore(&*N->getFirstInsertionPt());
240e8d8bef9SDimitry Andric
241e8d8bef9SDimitry Andric if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
242e8d8bef9SDimitry Andric // Create a new MemoryAccess and let MemorySSA set its defining access.
243e8d8bef9SDimitry Andric MemoryAccess *NewMemAcc =
244e8d8bef9SDimitry Andric MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
245e8d8bef9SDimitry Andric if (NewMemAcc) {
246e8d8bef9SDimitry Andric if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
247e8d8bef9SDimitry Andric MSSAU->insertDef(MemDef, /*RenameUses=*/true);
248e8d8bef9SDimitry Andric else {
249e8d8bef9SDimitry Andric auto *MemUse = cast<MemoryUse>(NewMemAcc);
250e8d8bef9SDimitry Andric MSSAU->insertUse(MemUse, /*RenameUses=*/true);
251e8d8bef9SDimitry Andric }
252e8d8bef9SDimitry Andric }
253e8d8bef9SDimitry Andric }
254e8d8bef9SDimitry Andric
25506c3fb27SDimitry Andric // Replaces uses of I with IC in N, except PHI-use which is being taken
25606c3fb27SDimitry Andric // care of by defs in PHI's incoming blocks.
2578bcb0991SDimitry Andric I.replaceUsesWithIf(IC, [N](Use &U) {
25806c3fb27SDimitry Andric Instruction *UIToReplace = cast<Instruction>(U.getUser());
25906c3fb27SDimitry Andric return UIToReplace->getParent() == N && !isa<PHINode>(UIToReplace);
2608bcb0991SDimitry Andric });
2610b57cec5SDimitry Andric // Replaces uses of I with IC in blocks dominated by N
2620b57cec5SDimitry Andric replaceDominatedUsesWith(&I, IC, DT, N);
2630b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
2640b57cec5SDimitry Andric << '\n');
2650b57cec5SDimitry Andric NumLoopSunkCloned++;
2660b57cec5SDimitry Andric }
2670b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
2680b57cec5SDimitry Andric NumLoopSunk++;
2690b57cec5SDimitry Andric I.moveBefore(&*MoveBB->getFirstInsertionPt());
2700b57cec5SDimitry Andric
271e8d8bef9SDimitry Andric if (MSSAU)
272e8d8bef9SDimitry Andric if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
273e8d8bef9SDimitry Andric MSSAU->getMemorySSA()->getMemoryAccess(&I)))
274e8d8bef9SDimitry Andric MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
275e8d8bef9SDimitry Andric
2760b57cec5SDimitry Andric return true;
2770b57cec5SDimitry Andric }
2780b57cec5SDimitry Andric
2790b57cec5SDimitry Andric /// Sinks instructions from loop's preheader to the loop body if the
2800b57cec5SDimitry Andric /// sum frequency of inserted copy is smaller than preheader's frequency.
sinkLoopInvariantInstructions(Loop & L,AAResults & AA,LoopInfo & LI,DominatorTree & DT,BlockFrequencyInfo & BFI,MemorySSA & MSSA,ScalarEvolution * SE)2810b57cec5SDimitry Andric static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
2820b57cec5SDimitry Andric DominatorTree &DT,
2830b57cec5SDimitry Andric BlockFrequencyInfo &BFI,
28481ad6265SDimitry Andric MemorySSA &MSSA,
28581ad6265SDimitry Andric ScalarEvolution *SE) {
2860b57cec5SDimitry Andric BasicBlock *Preheader = L.getLoopPreheader();
287e8d8bef9SDimitry Andric assert(Preheader && "Expected loop to have preheader");
2880b57cec5SDimitry Andric
289e8d8bef9SDimitry Andric assert(Preheader->getParent()->hasProfileData() &&
290e8d8bef9SDimitry Andric "Unexpected call when profile data unavailable.");
2910b57cec5SDimitry Andric
2920b57cec5SDimitry Andric const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
2930b57cec5SDimitry Andric // If there are no basic blocks with lower frequency than the preheader then
2940b57cec5SDimitry Andric // we can avoid the detailed analysis as we will never find profitable sinking
2950b57cec5SDimitry Andric // opportunities.
2960b57cec5SDimitry Andric if (all_of(L.blocks(), [&](const BasicBlock *BB) {
2970b57cec5SDimitry Andric return BFI.getBlockFreq(BB) > PreheaderFreq;
2980b57cec5SDimitry Andric }))
2990b57cec5SDimitry Andric return false;
3000b57cec5SDimitry Andric
30181ad6265SDimitry Andric MemorySSAUpdater MSSAU(&MSSA);
30206c3fb27SDimitry Andric SinkAndHoistLICMFlags LICMFlags(/*IsSink=*/true, L, MSSA);
3030b57cec5SDimitry Andric
304e8d8bef9SDimitry Andric bool Changed = false;
3050b57cec5SDimitry Andric
3060b57cec5SDimitry Andric // Sort loop's basic blocks by frequency
3070b57cec5SDimitry Andric SmallVector<BasicBlock *, 10> ColdLoopBBs;
3080b57cec5SDimitry Andric SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
3090b57cec5SDimitry Andric int i = 0;
3100b57cec5SDimitry Andric for (BasicBlock *B : L.blocks())
3110b57cec5SDimitry Andric if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
3120b57cec5SDimitry Andric ColdLoopBBs.push_back(B);
3130b57cec5SDimitry Andric LoopBlockNumber[B] = ++i;
3140b57cec5SDimitry Andric }
3150b57cec5SDimitry Andric llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
3160b57cec5SDimitry Andric return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
3170b57cec5SDimitry Andric });
3180b57cec5SDimitry Andric
319bdd1243dSDimitry Andric // Traverse preheader's instructions in reverse order because if A depends
320bdd1243dSDimitry Andric // on B (A appears after B), A needs to be sunk first before B can be
3210b57cec5SDimitry Andric // sinked.
322349cc55cSDimitry Andric for (Instruction &I : llvm::make_early_inc_range(llvm::reverse(*Preheader))) {
32381ad6265SDimitry Andric if (isa<PHINode>(&I))
32481ad6265SDimitry Andric continue;
3250b57cec5SDimitry Andric // No need to check for instruction's operands are loop invariant.
326349cc55cSDimitry Andric assert(L.hasLoopInvariantOperands(&I) &&
3270b57cec5SDimitry Andric "Insts in a loop's preheader should have loop invariant operands!");
32881ad6265SDimitry Andric if (!canSinkOrHoistInst(I, &AA, &DT, &L, MSSAU, false, LICMFlags))
3290b57cec5SDimitry Andric continue;
330349cc55cSDimitry Andric if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
331bdd1243dSDimitry Andric &MSSAU)) {
3320b57cec5SDimitry Andric Changed = true;
333bdd1243dSDimitry Andric if (SE)
334bdd1243dSDimitry Andric SE->forgetBlockAndLoopDispositions(&I);
335bdd1243dSDimitry Andric }
3360b57cec5SDimitry Andric }
3370b57cec5SDimitry Andric
3380b57cec5SDimitry Andric return Changed;
3390b57cec5SDimitry Andric }
3400b57cec5SDimitry Andric
run(Function & F,FunctionAnalysisManager & FAM)3410b57cec5SDimitry Andric PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
34206c3fb27SDimitry Andric // Enable LoopSink only when runtime profile is available.
34306c3fb27SDimitry Andric // With static profile, the sinking decision may be sub-optimal.
34406c3fb27SDimitry Andric if (!F.hasProfileData())
34506c3fb27SDimitry Andric return PreservedAnalyses::all();
34606c3fb27SDimitry Andric
3470b57cec5SDimitry Andric LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
3480b57cec5SDimitry Andric // Nothing to do if there are no loops.
3490b57cec5SDimitry Andric if (LI.empty())
3500b57cec5SDimitry Andric return PreservedAnalyses::all();
3510b57cec5SDimitry Andric
3520b57cec5SDimitry Andric AAResults &AA = FAM.getResult<AAManager>(F);
3530b57cec5SDimitry Andric DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
3540b57cec5SDimitry Andric BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
35581ad6265SDimitry Andric MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
356e8d8bef9SDimitry Andric
3570b57cec5SDimitry Andric // We want to do a postorder walk over the loops. Since loops are a tree this
3580b57cec5SDimitry Andric // is equivalent to a reversed preorder walk and preorder is easy to compute
3590b57cec5SDimitry Andric // without recursion. Since we reverse the preorder, we will visit siblings
3600b57cec5SDimitry Andric // in reverse program order. This isn't expected to matter at all but is more
3610b57cec5SDimitry Andric // consistent with sinking algorithms which generally work bottom-up.
3620b57cec5SDimitry Andric SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
3630b57cec5SDimitry Andric
3640b57cec5SDimitry Andric bool Changed = false;
3650b57cec5SDimitry Andric do {
3660b57cec5SDimitry Andric Loop &L = *PreorderLoops.pop_back_val();
3670b57cec5SDimitry Andric
368e8d8bef9SDimitry Andric BasicBlock *Preheader = L.getLoopPreheader();
369e8d8bef9SDimitry Andric if (!Preheader)
370e8d8bef9SDimitry Andric continue;
371e8d8bef9SDimitry Andric
3720b57cec5SDimitry Andric // Note that we don't pass SCEV here because it is only used to invalidate
3730b57cec5SDimitry Andric // loops in SCEV and we don't preserve (or request) SCEV at all making that
3740b57cec5SDimitry Andric // unnecessary.
37581ad6265SDimitry Andric Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, MSSA,
37681ad6265SDimitry Andric /*ScalarEvolution*/ nullptr);
3770b57cec5SDimitry Andric } while (!PreorderLoops.empty());
3780b57cec5SDimitry Andric
3790b57cec5SDimitry Andric if (!Changed)
3800b57cec5SDimitry Andric return PreservedAnalyses::all();
3810b57cec5SDimitry Andric
3820b57cec5SDimitry Andric PreservedAnalyses PA;
3830b57cec5SDimitry Andric PA.preserveSet<CFGAnalyses>();
384e8d8bef9SDimitry Andric PA.preserve<MemorySSAAnalysis>();
385e8d8bef9SDimitry Andric
386e8d8bef9SDimitry Andric if (VerifyMemorySSA)
38781ad6265SDimitry Andric MSSA.verifyMemorySSA();
388e8d8bef9SDimitry Andric
3890b57cec5SDimitry Andric return PA;
3900b57cec5SDimitry Andric }
391