Index: include/llvm/Transforms/Scalar/LoopSink.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/LoopSink.h @@ -0,0 +1,41 @@ +//===- 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: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -122,6 +122,7 @@ #include "llvm/Transforms/Scalar/SROA.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include "llvm/Transforms/Scalar/Sink.h" +#include "llvm/Transforms/Scalar/LoopSink.h" #include "llvm/Transforms/Scalar/SpeculativeExecution.h" #include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Utils/AddDiscriminators.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ 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: lib/Transforms/Scalar/LoopSink.cpp =================================================================== --- lib/Transforms/Scalar/LoopSink.cpp +++ 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,51 @@ 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. + // FIXME: We do this in several places, we should factor it into a helper. + SmallVector PreOrderLoops, PreOrderWorklist; + for (Loop *RootL : reverse(LI)) { + assert(PreOrderWorklist.empty() && + "Must start with an empty preorder walk worklist."); + PreOrderWorklist.push_back(RootL); + do { + Loop *L = PreOrderWorklist.pop_back_val(); + PreOrderWorklist.append(L->begin(), L->end()); + PreOrderLoops.push_back(L); + } while (!PreOrderWorklist.empty()); + } + + 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: test/Transforms/LICM/loopsink.ll =================================================================== --- test/Transforms/LICM/loopsink.ll +++ 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: test/Transforms/LICM/sink.ll =================================================================== --- test/Transforms/LICM/sink.ll +++ 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;