Index: llvm/trunk/include/llvm/Transforms/Scalar/LoopSink.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/LoopSink.h +++ llvm/trunk/include/llvm/Transforms/Scalar/LoopSink.h @@ -0,0 +1,40 @@ +//===- LoopSink.h - Loop Sink Pass ------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Loop Sink pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSINK_H +#define LLVM_TRANSFORMS_SCALAR_LOOPSINK_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +/// A pass that does profile-guided sinking of instructions into loops. +/// +/// This is a function pass as it shouldn't be composed into any kind of +/// unified loop pass pipeline. The goal of it is to sink code into loops that +/// is loop invariant but only required within the loop body when doing so +/// reduces the global expected dynamic frequency with which it executes. +/// A classic example is an extremely cold branch within a loop body. +/// +/// We do this as a separate pass so that during normal optimization all +/// invariant operations can be held outside the loop body to simplify +/// fundamental analyses and transforms of the loop. +class LoopSinkPass : public PassInfoMixin { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPSINK_H Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -107,6 +107,7 @@ #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Scalar/LoopRotation.h" #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h" +#include "llvm/Transforms/Scalar/LoopSink.h" #include "llvm/Transforms/Scalar/LoopStrengthReduce.h" #include "llvm/Transforms/Scalar/LoopUnrollPass.h" #include "llvm/Transforms/Scalar/LowerAtomic.h" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -159,6 +159,7 @@ FUNCTION_PASS("guard-widening", GuardWideningPass()) FUNCTION_PASS("gvn", GVN()) FUNCTION_PASS("loop-simplify", LoopSimplifyPass()) +FUNCTION_PASS("loop-sink", LoopSinkPass()) FUNCTION_PASS("lowerinvoke", LowerInvokePass()) FUNCTION_PASS("mem2reg", PromotePass()) FUNCTION_PASS("memcpyopt", MemCpyOptPass()) Index: llvm/trunk/lib/Transforms/Scalar/LoopSink.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopSink.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopSink.cpp @@ -31,6 +31,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/LoopSink.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" @@ -298,6 +299,42 @@ return Changed; } +PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) { + LoopInfo &LI = FAM.getResult(F); + // Nothing to do if there are no loops. + if (LI.empty()) + return PreservedAnalyses::all(); + + AAResults &AA = FAM.getResult(F); + DominatorTree &DT = FAM.getResult(F); + BlockFrequencyInfo &BFI = FAM.getResult(F); + + // We want to do a postorder walk over the loops. Since loops are a tree this + // is equivalent to a reversed preorder walk and preorder is easy to compute + // without recursion. Since we reverse the preorder, we will visit siblings + // in reverse program order. This isn't expected to matter at all but is more + // consistent with sinking algorithms which generally work bottom-up. + SmallVector PreorderLoops = LI.getLoopsInPreorder(); + + bool Changed = false; + do { + Loop &L = *PreorderLoops.pop_back_val(); + + // Note that we don't pass SCEV here because it is only used to invalidate + // loops in SCEV and we don't preserve (or request) SCEV at all making that + // unnecessary. + Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, + /*ScalarEvolution*/ nullptr); + } while (!PreorderLoops.empty()); + + if (!Changed) + return PreservedAnalyses::all(); + + PreservedAnalyses PA; + PA.preserveSet(); + return PA; +} + namespace { struct LegacyLoopSinkPass : public LoopPass { static char ID; Index: llvm/trunk/test/Transforms/LICM/loopsink.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/loopsink.ll +++ llvm/trunk/test/Transforms/LICM/loopsink.ll @@ -1,4 +1,5 @@ ; RUN: opt -S -loop-sink < %s | FileCheck %s +; RUN: opt -S -passes=loop-sink < %s | FileCheck %s @g = global i32 0, align 4 Index: llvm/trunk/test/Transforms/LICM/sink.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/sink.ll +++ llvm/trunk/test/Transforms/LICM/sink.ll @@ -1,5 +1,7 @@ ; 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 +; RUN: opt -S < %s -passes='require,loop(licm),loop-sink' \ +; RUN: | FileCheck %s --check-prefix=CHECK-SINK ; Original source code: ; int g;