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 @@ -138,6 +138,8 @@ // Pass *createLICMPass(); +Pass *createLoopSinkPass(); + //===----------------------------------------------------------------------===// // // LoopInterchange - This pass interchanges loops to provide a more Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -21,12 +21,16 @@ #include "llvm/IR/IRBuilder.h" namespace llvm { +class AAResults; class AliasSet; class AliasSetTracker; class AssumptionCache; class BasicBlock; +class CallInst; class DataLayout; class DominatorTree; +class Instruction; +class LoadInst; class Loop; class LoopInfo; class Pass; @@ -467,6 +471,14 @@ /// All loop passes should call this as part of implementing their \c /// getAnalysisUsage. void getLoopAnalysisUsage(AnalysisUsage &AU); -} +/// Return true if the load instruction is hoistable. +bool isHoistableLoad(LoadInst *LI, AAResults *AA, AliasSetTracker *CurAST); + +/// Return true if the call instruction is hoistable. +bool isHoistableCall(CallInst *CI, AAResults *AA, AliasSetTracker *CurAST); + +/// Return true if the instruction is hoistable. +bool isHoistableInst(const Instruction *I); +} #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/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -100,7 +100,7 @@ CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo); -static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, +static bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo); @@ -436,84 +436,99 @@ SafetyInfo->BlockColors = colorEHFunclets(*Fn); } -/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this -/// instruction. +/// isHoistableLoad - Return true if the load instruction is hoistable. /// -bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT, - TargetLibraryInfo *TLI, Loop *CurLoop, - AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) { - // Loads have extra constraints we have to verify before we can hoist them. - if (LoadInst *LI = dyn_cast(&I)) { - if (!LI->isUnordered()) - return false; // Don't hoist volatile/atomic loads! +bool llvm::isHoistableLoad(LoadInst *LI, AAResults *AA, AliasSetTracker *CurAST) { + if (!LI->isUnordered()) + return false; // Don't hoist volatile/atomic loads! + + // Loads from constant memory are always safe to move, even if they end up + // in the same alias set as something that ends up being modified. + if (AA->pointsToConstantMemory(LI->getOperand(0))) + return true; + if (LI->getMetadata(LLVMContext::MD_invariant_load)) + return true; - // Loads from constant memory are always safe to move, even if they end up - // in the same alias set as something that ends up being modified. - if (AA->pointsToConstantMemory(LI->getOperand(0))) - return true; - if (LI->getMetadata(LLVMContext::MD_invariant_load)) - return true; + // Don't hoist loads which have may-aliased stores in loop. + uint64_t Size = 0; + if (LI->getType()->isSized()) + Size = LI->getModule()->getDataLayout().getTypeStoreSize(LI->getType()); - // 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()); + AAMDNodes AAInfo; + LI->getAAMetadata(AAInfo); - AAMDNodes AAInfo; - LI->getAAMetadata(AAInfo); + return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); +} - 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)) - return false; +/// isHoistableCall - Return true if the call instruction is hoistable. +/// +bool llvm::isHoistableCall(CallInst *CI, AAResults *AA, AliasSetTracker *CurAST) { + // Don't sink or hoist dbg info; it's legal, but not useful. + if (isa(*CI)) + return false; - // Don't sink calls which can throw. - if (CI->mayThrow()) - return false; + // Don't sink calls which can throw. + if (CI->mayThrow()) + return false; - // Handle simple cases by querying alias analysis. - FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI); - if (Behavior == FMRB_DoesNotAccessMemory) + // Handle simple cases by querying alias analysis. + FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI); + if (Behavior == FMRB_DoesNotAccessMemory) + return true; + if (AliasAnalysis::onlyReadsMemory(Behavior)) { + // A readonly argmemonly function only reads from memory pointed to by + // it's arguments with arbitrary offsets. If we can prove there are no + // writes to this memory in the loop, we can hoist or sink. + if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) { + for (Value *Op : CI->arg_operands()) + if (Op->getType()->isPointerTy() && + pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize, + AAMDNodes(), CurAST)) + return false; return true; - if (AliasAnalysis::onlyReadsMemory(Behavior)) { - // A readonly argmemonly function only reads from memory pointed to by - // it's arguments with arbitrary offsets. If we can prove there are no - // writes to this memory in the loop, we can hoist or sink. - if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) { - for (Value *Op : CI->arg_operands()) - if (Op->getType()->isPointerTy() && - pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize, - AAMDNodes(), CurAST)) - return false; - return true; - } - // If this call only reads from memory and there are no writes to memory - // in the loop, we can hoist or sink the call as appropriate. - bool FoundMod = false; - for (AliasSet &AS : *CurAST) { - if (!AS.isForwardingAliasSet() && AS.isMod()) { - FoundMod = true; - break; - } + } + // If this call only reads from memory and there are no writes to memory + // in the loop, we can hoist or sink the call as appropriate. + bool FoundMod = false; + for (AliasSet &AS : *CurAST) { + if (!AS.isForwardingAliasSet() && AS.isMod()) { + FoundMod = true; + break; } - if (!FoundMod) - return true; } + if (!FoundMod) + return true; + } - // FIXME: This should use mod/ref information to see if we can hoist or - // sink the call. + // FIXME: This should use mod/ref information to see if we can hoist or + // sink the call. + return false; +} - return false; - } +/// isHoistableInst - Return true if the instruction is hoistable. +/// +bool llvm::isHoistableInst(const Instruction *I) { + return isa(*I) || isa(*I) || isa(*I) || + isa(*I) || isa(*I) || + isa(*I) || isa(*I) || + isa(*I) || isa(*I) || + isa(*I); +} - // 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)) +/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this +/// instruction. +/// +bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, + TargetLibraryInfo *TLI, Loop *CurLoop, + AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) { + // Loads have extra constraints we have to verify before we can hoist them. + if (LoadInst *LI = dyn_cast(&I)) { + return isHoistableLoad(LI, AA, CurAST); + } else if (CallInst *CI = dyn_cast(&I)) { + return isHoistableCall(CI, AA, CurAST); + } else if (!isHoistableInst(&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 Index: lib/Transforms/Scalar/LoopSink.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/LoopSink.cpp @@ -0,0 +1,216 @@ +//===-- LICM.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. +// +//===----------------------------------------------------------------------===// + +#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/LoopUtils.h" +using namespace llvm; + +#define DEBUG_TYPE "sink" + +STATISTIC(NumLoopSunk, "Number of instructions sunk into loop"); + +static cl::opt SinkFrequencyPercentThreshold( + "sink-freq-percent-threshold", cl::Hidden, cl::init(90), + cl::desc("If sinking would incur duplication, the reduced " + "frequency must be lower than this threshold in " + "order to justify the code growth")); + +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(); } + +/// canSinkToLoopBody - Return true if the instruction can be sinked into loop +/// body. +static bool canSinkToLoopBody(Instruction &I, AliasAnalysis *AA, Loop *CurLoop, + AliasSetTracker *CurAST) { + // Loads have extra constraints we have to verify before we can hoist them. + if (LoadInst *LI = dyn_cast(&I)) { + return isHoistableLoad(LI, AA, CurAST); + } else if (CallInst *CI = dyn_cast(&I)) { + return isHoistableCall(CI, AA, CurAST); + } else { + return isHoistableInst(&I); + } +} + +/// 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 = false; + for (BasicBlock *BB : L->blocks()) + if (BFI->getBlockFreq(BB) <= PreheaderFreq) { + HasColdBB = true; + break; + } + + 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 + // get sinked out of preheader. + SmallVector INS; + for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) { + Instruction &I = *II++; + if (L->hasLoopInvariantOperands(&I) && canSinkToLoopBody(I, AA, L, &CurAST)) + 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; + BasicBlock *SinkBB = nullptr; + for (BasicBlock *N : BBs) { + if (SinkBB) { + BasicBlock *CDT = DT->findNearestCommonDominator(SinkBB, N); + if (BFI->getBlockFreq(CDT) >= PreheaderFreq || + BFI->getBlockFreq(CDT) * + BranchProbability(SinkFrequencyPercentThreshold, 100) > + BFI->getBlockFreq(SinkBB) + BFI->getBlockFreq(N)) { + SinkBBs.insert(SinkBB); + SinkBB = N; + } else { + SinkBB = CDT; + } + } else { + SinkBB = N; + } + } + if (SinkBB) + SinkBBs.insert(SinkBB); + + // If the total frequency of all inserted BBs exceeds preheader frequency, + // we should not sink I. + BlockFrequency T = 0; + bool ShouldSkip = false; + for (BasicBlock *N : SinkBBs) { + if (!L->contains(LI->getLoopFor(SinkBB))) { + ShouldSkip = true; + break; + } + T += BFI->getBlockFreq(N); + if (T > PreheaderFreq) + break; + } + if (ShouldSkip || T > PreheaderFreq || + (SinkBBs.size() > 1 && + T > PreheaderFreq * + BranchProbability(SinkFrequencyPercentThreshold, 100))) + continue; + + int i = 0; + for (BasicBlock *N : SinkBBs) { + DEBUG(dbgs() << "Sinking " << I << " To: " << N->getName() << '\n'); + NumLoopSunk++; + // Sinking I. If I is cloned, we need to replace its uses. + if (i++ == 0) { + I->moveBefore(&*N->getFirstInsertionPt()); + } else { + Instruction *IC = I->clone(); + IC->setName(I->getName()); + IC->insertBefore(&*N->getFirstInsertionPt()); + SmallVector UV; + for (Use &U : I->uses()) { + if (DT->dominates(IC, U)) + UV.push_back(&U); + } + for (Use *U : UV) { + U->set(IC); + } + } + } + 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/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,295 @@ +; 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 | +; \ / +; b6 +; preheader: 1000 +; b2: 15 +; b3: 7 +; b4: 7 +; Sink load to b2 +; CHECK: t1 +; CHECK: .b2: +; CHECK: load i32, i32* @g +; CHECK: .b3: +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 %.exit, label %.b1 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 B6 +; / \ | +; B3 b4 | +; \ / | +; b5 | +; \ / +; b6 +; preheader: 500 +; b1: 16016 +; b3: 8 +; b6: 8 +; Sink load to b3 and b6 +; CHECK: t2 +; 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 %.exit, label %.b1 + +.exit: + ret i32 10 +} + +; Function Attrs: norecurse nounwind readonly uwtable +; b1 +; / \ +; b2 b6 +; / \ | +; B3 b4 | +; \ / | +; B5 | +; \ / +; b6 +; preheader: 500 +; b3: 8 +; b5: 16008 +; Do not sink load from preheader. +; CHECK: t3 +; CHECK: .preheader: +; CHECK: load i32, i32* @g +; CHECK: .b1: +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 %.exit, label %.b1 + +.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: .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 | +; \ / +; b6 +; 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: +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 = add nsw i32 %iv, 100 + store i32 %t6, i32* %1, align 4 + 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 %.exit, label %.b1 + +.exit: + ret i32 10 +} + + +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} 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"}