PlaceSafepoints.cpp | Explore in Territory

//===- PlaceSafepoints.cpp - Place GC Safepoints --------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Place garbage collection safepoints at appropriate locations in the IR. This
// does not make relocation semantics or variable liveness explicit.  That's
// done by RewriteStatepointsForGC.
//
// Terminology:
// - A call is said to be "parseable" if there is a stack map generated for the
// return PC of the call.  A runtime can determine where values listed in the
// deopt arguments and (after RewriteStatepointsForGC) gc arguments are located
// on the stack when the code is suspended inside such a call.  Every parse
// point is represented by a call wrapped in an gc.statepoint intrinsic.
// - A "poll" is an explicit check in the generated code to determine if the
// runtime needs the generated code to cooperate by calling a helper routine
// and thus suspending its execution at a known state. The call to the helper
// routine will be parseable.  The (gc & runtime specific) logic of a poll is
// assumed to be provided in a function of the name "gc.safepoint_poll".
//
// We aim to insert polls such that running code can quickly be brought to a
// well defined state for inspection by the collector.  In the current
// implementation, this is done via the insertion of poll sites at method entry
// and the backedge of most loops.  We try to avoid inserting more polls than
// are necessary to ensure a finite period between poll sites.  This is not
// because the poll itself is expensive in the generated code; it's not.  Polls
// do tend to impact the optimizer itself in negative ways; we'd like to avoid
// perturbing the optimization of the method as much as we can.
//
// We also need to make most call sites parseable.  The callee might execute a
// poll (or otherwise be inspected by the GC).  If so, the entire stack
// (including the suspended frame of the current method) must be parseable.
//
// This pass will insert:
// - Call parse points ("call safepoints") for any call which may need to
// reach a safepoint during the execution of the callee function.
// - Backedge safepoint polls and entry safepoint polls to ensure that
// executing code reaches a safepoint poll in a finite amount of time.
//
// We do not currently support return statepoints, but adding them would not
// be hard.  They are not required for correctness - entry safepoints are an
// alternative - but some GCs may prefer them.  Patches welcome.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/PlaceSafepoints.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"

#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");

STATISTIC(CallInLoop,
          "Number of loops without safepoints due to calls in loop");
STATISTIC(FiniteExecution,
          "Number of loops without safepoints finite execution");

// Ignore opportunities to avoid placing safepoints on backedges, useful for
// validation
static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden,
                                  cl::init(false));

/// How narrow does the trip count of a loop have to be to have to be considered
/// "counted"?  Counted loops do not get safepoints at backedges.
static cl::opt<int> CountedLoopTripWidth("spp-counted-loop-trip-width",
                                         cl::Hidden, cl::init(32));

// If true, split the backedge of a loop when placing the safepoint, otherwise
// split the latch block itself.  Both are useful to support for
// experimentation, but in practice, it looks like splitting the backedge
// optimizes better.
static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
                                   cl::init(false));

namespace {
/// An analysis pass whose purpose is to identify each of the backedges in
/// the function which require a safepoint poll to be inserted.
class PlaceBackedgeSafepointsLegacyPass : public FunctionPass { … };
} // namespace

static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));

char PlaceBackedgeSafepointsLegacyPass::ID = …;

INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsLegacyPass,
                      "place-backedge-safepoints-impl",
                      "Place Backedge Safepoints", false, false)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(PlaceBackedgeSafepointsLegacyPass,
                    "place-backedge-safepoints-impl",
                    "Place Backedge Safepoints", false, false)

static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
                                               BasicBlock *Pred,
                                               DominatorTree &DT,
                                               const TargetLibraryInfo &TLI);

static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
                                    BasicBlock *Pred);

static Instruction *findLocationForEntrySafepoint(Function &F,
                                                  DominatorTree &DT);

static bool isGCSafepointPoll(Function &F);
static bool shouldRewriteFunction(Function &F);
static bool enableEntrySafepoints(Function &F);
static bool enableBackedgeSafepoints(Function &F);
static bool enableCallSafepoints(Function &F);

static void
InsertSafepointPoll(BasicBlock::iterator InsertBefore,
                    std::vector<CallBase *> &ParsePointsNeeded /*rval*/,
                    const TargetLibraryInfo &TLI);

bool PlaceBackedgeSafepointsLegacyPass::runOnLoop(Loop *L) { … }

bool PlaceSafepointsPass::runImpl(Function &F, const TargetLibraryInfo &TLI) { … }

PreservedAnalyses PlaceSafepointsPass::run(Function &F,
                                           FunctionAnalysisManager &AM) { … }

static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI) { … }

/// Returns true if this loop is known to contain a call safepoint which
/// must unconditionally execute on any iteration of the loop which returns
/// to the loop header via an edge from Pred.  Returns a conservative correct
/// answer; i.e. false is always valid.
static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
                                               BasicBlock *Pred,
                                               DominatorTree &DT,
                                               const TargetLibraryInfo &TLI) { … }

/// Returns true if this loop is known to terminate in a finite number of
/// iterations.  Note that this function may return false for a loop which
/// does actual terminate in a finite constant number of iterations due to
/// conservatism in the analysis.
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
                                    BasicBlock *Pred) { … }

static void scanOneBB(Instruction *Start, Instruction *End,
                      std::vector<CallInst *> &Calls,
                      DenseSet<BasicBlock *> &Seen,
                      std::vector<BasicBlock *> &Worklist) { … }

static void scanInlinedCode(Instruction *Start, Instruction *End,
                            std::vector<CallInst *> &Calls,
                            DenseSet<BasicBlock *> &Seen) { … }

/// Returns true if an entry safepoint is not required before this callsite in
/// the caller function.
static bool doesNotRequireEntrySafepointBefore(CallBase *Call) { … }

static Instruction *findLocationForEntrySafepoint(Function &F,
                                                  DominatorTree &DT) { … }

const char GCSafepointPollName[] = …;

static bool isGCSafepointPoll(Function &F) { … }

/// Returns true if this function should be rewritten to include safepoint
/// polls and parseable call sites.  The main point of this function is to be
/// an extension point for custom logic.
static bool shouldRewriteFunction(Function &F) { … }

// TODO: These should become properties of the GCStrategy, possibly with
// command line overrides.
static bool enableEntrySafepoints(Function &F) { … }
static bool enableBackedgeSafepoints(Function &F) { … }
static bool enableCallSafepoints(Function &F) { … }

// Insert a safepoint poll immediately before the given instruction.  Does
// not handle the parsability of state at the runtime call, that's the
// callers job.
static void
InsertSafepointPoll(BasicBlock::iterator InsertBefore,
                    std::vector<CallBase *> &ParsePointsNeeded /*rval*/,
                    const TargetLibraryInfo &TLI) { … }
llvm/llvm/lib/Transforms/Scalar/PlaceSafepoints.cpp
