Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -161,6 +161,7 @@ void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAWrapperPassPass(PassRegistry &); void initializeLegacyLICMPassPass(PassRegistry&); +void initializeLegacyLoopSinkPassPass(PassRegistry&); void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&); void initializeLazyValueInfoWrapperPassPass(PassRegistry&); void initializeLintPass(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: 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/LoopSink.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/LoopSink.cpp @@ -0,0 +1,218 @@ +//===-- 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" + +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(); } + +/// Returns true if Child is in subloop of Parent. +static bool IsInSubLoop(const Loop *Parent, const Loop *Child) { + for (; Child; Child = Child->getParentLoop()) { + if (Child == Parent) + return true; + } + return false; +} + +/// 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 sink them. + if (LoadInst *LI = dyn_cast(&I)) { + if (!LI->isUnordered()) + return false; // Don't sink 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; + + // Don't sink 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); + + return !CurAST.getAliasSetForPointer(LI->getOperand(0), Size, AAInfo) + .isMod(); + } + + // Only these instructions are sinkable. + if (!isa(I) && !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I)) + return false; + + return true; +} + +bool SinkLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, + BlockFrequencyInfo *BFI, ScalarEvolution *SE) { + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) + return false; + + bool Changed = false; + AliasSetTracker CurAST(*AA); + const BlockFrequency PreheaderFreq = BFI->getBlockFreq(Preheader); + SmallVector INS; + + // Compute alias set. + for (BasicBlock *BB : L->blocks()) + CurAST.add(*BB); + + // Putting all preheader instructions in a working list in reverse order. + 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 if phi node, we can not sink I to this BB. + if (dyn_cast(UI) || + !IsInSubLoop(L, 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) { + 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; + for (BasicBlock *N : SinkBBs) { + if (!IsInSubLoop(L, LI->getLoopFor(SinkBB))) { + T = PreheaderFreq; + break; + } + T += BFI->getBlockFreq(N); + if (T >= PreheaderFreq) + break; + } + if (T < PreheaderFreq) { + int i = 0; + for (BasicBlock *N : SinkBBs) { + // 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/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"}