Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -165,6 +165,7 @@ void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAWrapperPassPass(PassRegistry &); void initializeLegacyLICMPassPass(PassRegistry&); +void initializeLegacyLoopSinkPassPass(PassRegistry&); void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&); void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&); void initializeLazyValueInfoWrapperPassPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -110,6 +110,7 @@ (void) llvm::createInternalizePass(); (void) llvm::createLCSSAPass(); (void) llvm::createLICMPass(); + (void) llvm::createLoopSinkPass(); (void) llvm::createLazyValueInfoPass(); (void) llvm::createLoopExtractorPass(); (void) llvm::createLoopInterchangePass(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -140,6 +140,13 @@ //===----------------------------------------------------------------------===// // +// LoopSink - This pass sinks invariants from preheader to loop body where +// frequency is lower than loop preheader. +// +Pass *createLoopSinkPass(); + +//===----------------------------------------------------------------------===// +// // LoopInterchange - This pass interchanges loops to provide a more // cache-friendly memory access patterns. // Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -320,10 +320,12 @@ /// the given edge. Returns the number of replacements made. 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 end of the given BasicBlock. Returns the number of replacements made. +/// the end of 'BB'. Returns the number of replacements made. +/// Replace use of 'From' with 'To' in 'BB' if 'IncludeSelf' is true. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, - const BasicBlock *BB); + const BasicBlock *BB, bool IncludeSelf); /// Return true if the CallSite CS calls a gc leaf function. Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -21,12 +21,14 @@ #include "llvm/IR/IRBuilder.h" namespace llvm { +class AAResults; class AliasSet; class AliasSetTracker; class AssumptionCache; class BasicBlock; class DataLayout; class DominatorTree; +class Instruction; class Loop; class LoopInfo; class Pass; @@ -467,6 +469,12 @@ /// All loop passes should call this as part of implementing their \c /// getAnalysisUsage. void getLoopAnalysisUsage(AnalysisUsage &AU); -} +/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this +/// instruction. If SafetyInfo is not nullptr, check if the instruction can +/// execute speculatively. +bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, + Loop *CurLoop, AliasSetTracker *CurAST, + LoopSafetyInfo *SafetyInfo); +} #endif Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -17,6 +17,7 @@ IndVarSimplify.cpp JumpThreading.cpp LICM.cpp + LoopSink.cpp LoadCombine.cpp LoopDeletion.cpp LoopDataPrefetch.cpp Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -1962,7 +1962,7 @@ unsigned NumReplacements = DominatesByEdge ? replaceDominatedUsesWith(LHS, RHS, *DT, Root) - : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart()); + : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart(), false); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; @@ -2038,7 +2038,7 @@ DominatesByEdge ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root) : replaceDominatedUsesWith(NotCmp, NotVal, *DT, - Root.getStart()); + Root.getStart(), false); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -100,10 +100,6 @@ CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo); -static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, - DominatorTree *DT, TargetLibraryInfo *TLI, - Loop *CurLoop, AliasSetTracker *CurAST, - LoopSafetyInfo *SafetyInfo); namespace { struct LoopInvariantCodeMotion { @@ -337,7 +333,7 @@ // operands of the instruction are loop invariant. // if (isNotUsedInLoop(I, CurLoop, SafetyInfo) && - canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) { + canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) { ++II; Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo); } @@ -390,7 +386,7 @@ // is safe to hoist the instruction. // if (CurLoop->hasLoopInvariantOperands(&I) && - canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) && + canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) && isSafeToExecuteUnconditionally( I, DT, CurLoop, SafetyInfo, CurLoop->getLoopPreheader()->getTerminator())) @@ -439,9 +435,17 @@ /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this /// instruction. /// -bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT, - TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) { +bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, + Loop *CurLoop, AliasSetTracker *CurAST, + LoopSafetyInfo *SafetyInfo) { + if (!isa(I) && !isa(I) && + !isa(I) && !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I)) + return false; + // Loads have extra constraints we have to verify before we can hoist them. if (LoadInst *LI = dyn_cast(&I)) { if (!LI->isUnordered()) @@ -457,7 +461,7 @@ // Don't hoist loads which have may-aliased stores in loop. uint64_t Size = 0; if (LI->getType()->isSized()) - Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType()); + Size = LI->getModule()->getDataLayout().getTypeStoreSize(LI->getType()); AAMDNodes AAInfo; LI->getAAMetadata(AAInfo); @@ -465,7 +469,7 @@ return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); } else if (CallInst *CI = dyn_cast(&I)) { // Don't sink or hoist dbg info; it's legal, but not useful. - if (isa(I)) + if (isa(*CI)) return false; // Don't sink calls which can throw. @@ -503,22 +507,16 @@ // FIXME: This should use mod/ref information to see if we can hoist or // sink the call. - return false; } - // Only these instructions are hoistable/sinkable. - if (!isa(I) && !isa(I) && !isa(I) && - !isa(I) && !isa(I) && - !isa(I) && !isa(I) && - !isa(I) && !isa(I) && - !isa(I)) - return false; - - // TODO: Plumb the context instruction through to make hoisting and sinking - // more powerful. Hoisting of loads already works due to the special casing - // above. - return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr); + if (SafetyInfo) + // TODO: Plumb the context instruction through to make hoisting and sinking + // more powerful. Hoisting of loads already works due to the special casing + // above. + return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr); + else + return true; } /// Returns true if a PHINode is a trivially replaceable with an Index: lib/Transforms/Scalar/LoopSink.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/LoopSink.cpp @@ -0,0 +1,221 @@ +//===-- LoopSink.cpp - Loop Sink Pass ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass traverses all instructions in loop preheader and sink it to the +// loop body where frequency is lower than the loop's preheader. +// This pass is a reverse-transformation of LICM. It differs from the Sink +// pass that it only processes instructions in loop's preheader, and has more +// accurate alias/profile info to guide sinking decisions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AliasSetTracker.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopPassManager.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +using namespace llvm; + +#define DEBUG_TYPE "loopsink" + +STATISTIC(NumLoopSunk, "Number of instructions sunk into loop"); + +static cl::opt 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 SinkLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, BlockFrequencyInfo *BFI, + ScalarEvolution *SE); + +namespace { +struct LegacyLoopSinkPass : public LoopPass { + static char ID; + LegacyLoopSinkPass() : LoopPass(ID) { + initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + + auto *SE = getAnalysisIfAvailable(); + return SinkLoop(L, &getAnalysis().getAAResults(), + &getAnalysis().getLoopInfo(), + &getAnalysis().getDomTree(), + &getAnalysis().getBFI(), + SE ? &SE->getSE() : nullptr); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + getLoopAnalysisUsage(AU); + } +}; +} + +char LegacyLoopSinkPass::ID = 0; +INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, + false) +INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) +INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) + +Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); } + +/// Return adjusted total frequency of BBs. +/// If the size of BBs is > 1, sinking would lead to code size increase, +/// which is tax by adding extra frequency to the total frequency. +static BlockFrequency AdjustedSumFreq(DenseSet &BBs, + BlockFrequencyInfo *BFI) { + BlockFrequency T = 0; + for (BasicBlock *B : BBs) + T += BFI->getBlockFreq(B); + if (BBs.size() > 1) + T /= BranchProbability(SinkFrequencyPercentThreshold, 100); + return T; +} + +/// FindSinkBBs - Return a set of basic blocks that are: +/// * Inside the loop +/// * Dominate BBs +/// * Has minimum total frequency that is no greater than preheader frequency +/// If no such set can be found, return an empty set. +static DenseSet FindSinkBBs(const Loop *L, + const DenseSet &BBs, + DominatorTree *DT, + BlockFrequencyInfo *BFI) { + DenseSet SinkBBs; + if (BBs.size() == 0) + return SinkBBs; + + // Sort loop's basic blocks by frequency + SmallVector SortedLoopBBs; + for (BasicBlock *B : L->blocks()) + if (BFI->getBlockFreq(B) <= BFI->getBlockFreq(L->getLoopPreheader())) + SortedLoopBBs.push_back(B); + std::stable_sort(SortedLoopBBs.begin(), SortedLoopBBs.end(), + [&](BasicBlock *A, BasicBlock *B) { + return BFI->getBlockFreq(A) < BFI->getBlockFreq(B); + }); + + SinkBBs.insert(BBs.begin(), BBs.end()); + // Start from the coldest BB, if its frequency is no greater than all SinkBBs + // that are dominated it, replace them with the coldest BB. + for (BasicBlock *BB : SortedLoopBBs) { + DenseSet AddedBBs; + for (BasicBlock *B : SinkBBs) + if (DT->dominates(BB, B)) + AddedBBs.insert(B); + if (AddedBBs.size() == 0) + continue; + if (AdjustedSumFreq(AddedBBs, BFI) > BFI->getBlockFreq(BB)) { + for (BasicBlock *B : AddedBBs) { + SinkBBs.erase(B); + } + SinkBBs.insert(BB); + } + } + + // If SinkBBs' frequency sum to be larger than preheader frequency, do not + // sink. + if (AdjustedSumFreq(SinkBBs, BFI) > BFI->getBlockFreq(L->getLoopPreheader())) + SinkBBs.clear(); + return SinkBBs; +} + +/// SinkLoop - Sink instructions from loop's preheader to the loop body if the +/// sum frequency of inserted copy is smaller than preheader's frequency. +bool SinkLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, + BlockFrequencyInfo *BFI, ScalarEvolution *SE) { + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) + return false; + + const BlockFrequency PreheaderFreq = BFI->getBlockFreq(Preheader); + bool HasColdBB = llvm::any_of(L->blocks(), [&](const BasicBlock *BB) { + return BFI->getBlockFreq(BB) <= PreheaderFreq; + }); + if (!HasColdBB) + return false; + + bool Changed = false; + AliasSetTracker CurAST(*AA); + + // Compute alias set. + for (BasicBlock *BB : L->blocks()) + CurAST.add(*BB); + + // Putting all preheader instructions in a working list in reverse order. + // This maintains the integrety of the working set while some instructions + // sunk into loop body. + SmallVector INS; + for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) { + Instruction &I = *II++; + if (L->hasLoopInvariantOperands(&I) && + canSinkOrHoistInst(I, AA, DT, L, &CurAST, nullptr)) + INS.push_back(&I); + } + for (auto I : INS) { + // All blocks that have uses of I and are in the sub loop of L. + DenseSet BBs; + for (auto &U : I->uses()) { + Instruction *UI = cast(U.getUser()); + // If the use is phi node, we can not sink I to this BB. + if (dyn_cast(UI) || + !L->contains(LI->getLoopFor(UI->getParent()))) { + BBs.clear(); + break; + } + BBs.insert(UI->getParent()); + } + + // Find the set of BBs that we should insert a copy of I. + DenseSet SinkBBs = FindSinkBBs(L, BBs, DT, BFI); + if (SinkBBs.size() == 0) + continue; + + auto BI = SinkBBs.begin(); + DEBUG(dbgs() << "Sinking " << I << " To: " << BI->getName() << '\n'); + NumLoopSunk++; + I->moveBefore(&*(*BI)->getFirstInsertionPt()); + + for (++BI; BI != SinkBBs.end(); ++BI) { + BasicBlock *N = *BI; + // Clone I and replace its uses. + Instruction *IC = I->clone(); + IC->setName(I->getName()); + IC->insertBefore(&*N->getFirstInsertionPt()); + replaceDominatedUsesWith(I, IC, *DT, IC->getParent(), true); + DEBUG(dbgs() << "Sinking " << I << " To: " << N->getName() << '\n'); + NumLoopSunk++; + } + Changed = true; + } + + if (Changed && SE) + SE->forgetLoopDispositions(L); + return Changed; +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -50,6 +50,7 @@ initializeIndVarSimplifyLegacyPassPass(Registry); initializeJumpThreadingPass(Registry); initializeLegacyLICMPassPass(Registry); + initializeLegacyLoopSinkPassPass(Registry); initializeLoopDataPrefetchPass(Registry); initializeLoopDeletionLegacyPassPass(Registry); initializeLoopAccessLegacyAnalysisPass(Registry); @@ -140,6 +141,10 @@ unwrap(PM)->add(createJumpThreadingPass()); } +void LLVMAddLoopSinkPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createLoopSinkPass()); +} + void LLVMAddLICMPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createLICMPass()); } Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -1668,7 +1668,8 @@ unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, - const BasicBlock *BB) { + const BasicBlock *BB, + bool IncludeSelf) { assert(From->getType() == To->getType()); unsigned Count = 0; @@ -1676,7 +1677,8 @@ UI != UE;) { Use &U = *UI++; auto *I = cast(U.getUser()); - if (DT.properlyDominates(BB, I->getParent())) { + if ((IncludeSelf && BB == I->getParent()) || + DT.properlyDominates(BB, I->getParent())) { U.set(To); DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " << *To << " in " << *U << "\n"); Index: lib/Transforms/Utils/SimplifyInstructions.cpp =================================================================== --- lib/Transforms/Utils/SimplifyInstructions.cpp +++ lib/Transforms/Utils/SimplifyInstructions.cpp @@ -90,6 +90,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); } @@ -100,7 +101,7 @@ return false; const DominatorTreeWrapperPass *DTWP = - getAnalysisIfAvailable(); + &getAnalysis(); const DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; const TargetLibraryInfo *TLI = &getAnalysis().getTLI(); Index: test/Transforms/LICM/loopsink.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/loopsink.ll @@ -0,0 +1,303 @@ +; RUN: opt -S -loop-sink < %s | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@g = global i32 0, align 4 + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 b6 +; / \ | +; b3 b4 | +; \ / | +; b5 | +; \ / +; b7 +; preheader: 1000 +; b2: 15 +; b3: 7 +; b4: 7 +; Sink load to b2 +; CHECK: t1 +; CHECK: .b2: +; CHECK: load i32, i32* @g +; CHECK: .b3: +; CHECK-NOT: load i32, i32* @g +define i32 @t1(i32, i32) #0 { + %3 = icmp eq i32 %1, 0 + br i1 %3, label %.exit, label %.preheader + +.preheader: + %invariant = load i32, i32* @g + br label %.b1 + +.b1: + %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ] + %c1 = icmp sgt i32 %iv, %0 + br i1 %c1, label %.b2, label %.b6, !prof !1 + +.b2: + %c2 = icmp sgt i32 %iv, 1 + br i1 %c2, label %.b3, label %.b4 + +.b3: + %t3 = sub nsw i32 %invariant, %iv + br label %.b5 + +.b4: + %t4 = add nsw i32 %invariant, %iv + br label %.b5 + +.b5: + %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ] + %t5 = mul nsw i32 %p5, 5 + br label %.b7 + +.b6: + %t6 = add nsw i32 %iv, 100 + br label %.b7 + +.b7: + %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ] + %t7 = add nuw nsw i32 %iv, 1 + %c7 = icmp eq i32 %t7, %p7 + br i1 %c7, label %.b1, label %.exit, !prof !7 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 b6 +; / \ | +; b3 b4 | +; \ / | +; b5 | +; \ / +; b7 +; preheader: 500 +; b1: 16016 +; b3: 8 +; b6: 8 +; Sink load to b3 and b6 +; CHECK: t2 +; CHECK: .preheader: +; CHECK-NOT: load i32, i32* @g +; CHECK: .b3: +; CHECK: load i32, i32* @g +; CHECK: .b4: +; CHECK: .b6: +; CHECK: load i32, i32* @g +; CHECK: .b7: +define i32 @t2(i32, i32) #0 { + %3 = icmp eq i32 %1, 0 + br i1 %3, label %.exit, label %.preheader + +.preheader: + %invariant = load i32, i32* @g + br label %.b1 + +.b1: + %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ] + %c1 = icmp sgt i32 %iv, %0 + br i1 %c1, label %.b2, label %.b6, !prof !6 + +.b2: + %c2 = icmp sgt i32 %iv, 1 + br i1 %c2, label %.b3, label %.b4, !prof !1 + +.b3: + %t3 = sub nsw i32 %invariant, %iv + br label %.b5 + +.b4: + %t4 = add nsw i32 5, %iv + br label %.b5 + +.b5: + %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ] + %t5 = mul nsw i32 %p5, 5 + br label %.b7 + +.b6: + %t6 = add nsw i32 %iv, %invariant + br label %.b7 + +.b7: + %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ] + %t7 = add nuw nsw i32 %iv, 1 + %c7 = icmp eq i32 %t7, %p7 + br i1 %c7, label %.b1, label %.exit, !prof !7 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 b6 +; / \ | +; b3 b4 | +; \ / | +; b5 | +; \ / +; b7 +; preheader: 500 +; b3: 8 +; b5: 16008 +; Do not sink load from preheader. +; CHECK: t3 +; CHECK: .preheader: +; CHECK: load i32, i32* @g +; CHECK: .b1: +; CHECK-NOT: load i32, i32* @g +define i32 @t3(i32, i32) #0 { + %3 = icmp eq i32 %1, 0 + br i1 %3, label %.exit, label %.preheader + +.preheader: + %invariant = load i32, i32* @g + br label %.b1 + +.b1: + %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ] + %c1 = icmp sgt i32 %iv, %0 + br i1 %c1, label %.b2, label %.b6, !prof !6 + +.b2: + %c2 = icmp sgt i32 %iv, 1 + br i1 %c2, label %.b3, label %.b4, !prof !1 + +.b3: + %t3 = sub nsw i32 %invariant, %iv + br label %.b5 + +.b4: + %t4 = add nsw i32 5, %iv + br label %.b5 + +.b5: + %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ] + %t5 = mul nsw i32 %p5, %invariant + br label %.b7 + +.b6: + %t6 = add nsw i32 %iv, 5 + br label %.b7 + +.b7: + %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ] + %t7 = add nuw nsw i32 %iv, 1 + %c7 = icmp eq i32 %t7, %p7 + br i1 %c7, label %.b1, label %.exit, !prof !7 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; For single-BB loop with <=1 avg trip count, sink load to b1 +; CHECK: t4 +; CHECK: .preheader: +; CHECK-not: load i32, i32* @g +; CHECK: .b1: +; CHECK: load i32, i32* @g +; CHECK: .exit: +define i32 @t4(i32, i32) #0 { +.preheader: + %invariant = load i32, i32* @g + br label %.b1 + +.b1: + %iv = phi i32 [ %t1, %.b1 ], [ 0, %.preheader ] + %t1 = add nsw i32 %invariant, %iv + %c1 = icmp sgt i32 %iv, %0 + br i1 %c1, label %.b1, label %.exit, !prof !1 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 b6 +; / \ | +; b3 b4 | +; \ / | +; b5 | +; \ / +; b7 +; preheader: 1000 +; b2: 15 +; b3: 7 +; b4: 7 +; There is alias store in loop, do not sink load +; CHECK: t5 +; CHECK: .preheader: +; CHECK: load i32, i32* @g +; CHECK: .b1: +; CHECK-NOT: load i32, i32* @g +define i32 @t5(i32, i32*) #0 { + %3 = icmp eq i32 %0, 0 + br i1 %3, label %.exit, label %.preheader + +.preheader: + %invariant = load i32, i32* @g + br label %.b1 + +.b1: + %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ] + %c1 = icmp sgt i32 %iv, %0 + br i1 %c1, label %.b2, label %.b6, !prof !1 + +.b2: + %c2 = icmp sgt i32 %iv, 1 + br i1 %c2, label %.b3, label %.b4 + +.b3: + %t3 = sub nsw i32 %invariant, %iv + br label %.b5 + +.b4: + %t4 = add nsw i32 %invariant, %iv + br label %.b5 + +.b5: + %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ] + %t5 = mul nsw i32 %p5, 5 + br label %.b7 + +.b6: + %t6 = call i32 @foo() + br label %.b7 + +.b7: + %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ] + %t7 = add nuw nsw i32 %iv, 1 + %c7 = icmp eq i32 %t7, %p7 + br i1 %c7, label %.b1, label %.exit, !prof !7 + +.exit: + ret i32 10 +} + +declare i32 @foo() + +attributes #0 = { norecurse nounwind readonly uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 3.9.0 (trunk 268689)"} +!1 = !{!"branch_weights", i32 1, i32 2000} +!2 = !{!3, !3, i64 0} +!3 = !{!"int", !4, i64 0} +!4 = !{!"omnipotent char", !5, i64 0} +!5 = !{!"Simple C++ TBAA"} +!6 = !{!"branch_weights", i32 2000, i32 1} +!7 = !{!"branch_weights", i32 100, i32 1} Index: test/Transforms/LICM/sink.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/sink.ll @@ -0,0 +1,73 @@ +; RUN: opt -S -licm < %s | FileCheck %s --check-prefix=CHECK-LICM +; RUN: opt -S -licm < %s | opt -S -loop-sink | FileCheck %s --check-prefix=CHECK-SINK + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Original source code: +; int g; +; int foo(int p, int x) { +; for (int i = 0; i != x; i++) +; if (__builtin_expect(i == p, 0)) { +; x += g; x *= g; +; } +; return x; +; } +; +; Load of global value g should not be hoisted to preheader. + +@g = global i32 0, align 4 + +; Function Attrs: norecurse nounwind readonly uwtable +define i32 @_Z3fooii(i32, i32) #0 { + %3 = icmp eq i32 %1, 0 + br i1 %3, label %._crit_edge, label %.lr.ph.preheader + +.lr.ph.preheader: ; preds = %2 + br label %.lr.ph + +; CHECK-LICM: .lr.ph.preheader: +; CHECK-LICM: load i32, i32* @g +; CHECK-LICM: br label %.lr.ph + +.lr.ph: ; preds = %.lr.ph.preheader, %9 + %.03 = phi i32 [ %8, %.combine ], [ 0, %.lr.ph.preheader ] + %.012 = phi i32 [ %.1, %.combine ], [ %1, %.lr.ph.preheader ] + %4 = icmp eq i32 %.03, %0 + br i1 %4, label %.then, label %.combine, !prof !1 + +.then: ; preds = %.lr.ph + %5 = load i32, i32* @g, align 4, !tbaa !2 + %6 = add nsw i32 %5, %.012 + %7 = mul nsw i32 %6, %5 + br label %.combine + +; CHECK-SINK: .then: +; CHECK-SINK: load i32, i32* @g +; CHECK-SINK: br label %.combine + +.combine: ; preds = %.lr.ph, %.then + %.1 = phi i32 [ %7, %.then ], [ %.012, %.lr.ph ] + %8 = add nuw nsw i32 %.03, 1 + %9 = icmp eq i32 %8, %.1 + br i1 %9, label %._crit_edge.loopexit, label %.lr.ph + +._crit_edge.loopexit: ; preds = %.combine + %.1.lcssa = phi i32 [ %.1, %.combine ] + br label %._crit_edge + +._crit_edge: ; preds = %._crit_edge.loopexit, %2 + %.01.lcssa = phi i32 [ 0, %2 ], [ %.1.lcssa, %._crit_edge.loopexit ] + ret i32 %.01.lcssa +} + +attributes #0 = { norecurse nounwind readonly uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 3.9.0 (trunk 268689)"} +!1 = !{!"branch_weights", i32 1, i32 2000} +!2 = !{!3, !3, i64 0} +!3 = !{!"int", !4, i64 0} +!4 = !{!"omnipotent char", !5, i64 0} +!5 = !{!"Simple C++ TBAA"}