All libcalls should be considered to be GC-leaf functions.

[dneilson]

Summary

It is possible for some passes to materialize a call to a libcall (ex: ldexp, exp2, etc),
but these passes will not mark the call as a gc-leaf-function. All libcalls are
actually gc-leaf-functions, so we change llvm::callsGCLeafFunction() to tell us that
available libcalls are equivalent to gc-leaf-function calls.

[dneilson]

clang-format patch

[anna]

This change looks good to me. However, I would suggest separating out the PlaceSafepoints (and it's testcase) change from the RewriteStatepointsForGC change. We don't use placeSafepoint anymore, so we should perhaps just deprecate it upstream, instead of fixing it.
@reames: What do you suggest?

lib/Transforms/Utils/Local.cpp

1850 ↗

(On Diff #108083)

Please state that libcalls can be materialized by RS4GC, there's no other passes right? (frankly, the placeSafepoints.cpp is deprecated).

[dneilson]

In D35840#822809, @anna wrote:

This change looks good to me. However, I would suggest separating out the PlaceSafepoints (and it's testcase) change from the RewriteStatepointsForGC change. We don't use placeSafepoint anymore, so we should perhaps just deprecate it upstream, instead of fixing it.
@reames: What do you suggest?

With the codebase in its current state, the PlaceSafepoints & RewriteStatepointsForGC changes cannot be separated. Fundamentally, the change is to behaviour of callsGCLeafFunction() -- making it flag lib calls as gc-leaf. That change required changing the prototype for the function, which in turn required the change in PlaceSafepoints.

The change could be contained to add the libcall check to just RewriteStatepointsForGC in the NeedsRewrite lambda, but that's less of a proper fix in my view -- it fixes a location of the bug's manifestation, but not the source of the bug.

lib/Transforms/Utils/Local.cpp

1850 ↗

(On Diff #108083)

That's not true. Libcalls can be created by other passes than just RS4GC. For example, where we noticed this problem was in a series of simplifications:
pow(x, 2) -> exp2(x) -> ldexp(x, 2)
pow & exp2 are both intrinsics, so we'd have been fine with that simplification, but ldexp does not have an intrinsic form, so the standard lib version is used (i.e. a libcall).

[anna]

In D35840#822820, @dneilson wrote:

In D35840#822809, @anna wrote:

This change looks good to me. However, I would suggest separating out the PlaceSafepoints (and it's testcase) change from the RewriteStatepointsForGC change. We don't use placeSafepoint anymore, so we should perhaps just deprecate it upstream, instead of fixing it.
@reames: What do you suggest?

With the codebase in its current state, the PlaceSafepoints & RewriteStatepointsForGC changes cannot be separated. Fundamentally, the change is to behaviour of callsGCLeafFunction() -- making it flag lib calls as gc-leaf. That change required changing the prototype for the function, which in turn required the change in PlaceSafepoints.

The change could be contained to add the libcall check to just RewriteStatepointsForGC in the NeedsRewrite lambda, but that's less of a proper fix in my view -- it fixes a location of the bug's manifestation, but not the source of the bug.

SGTM!

lib/Transforms/Utils/Local.cpp

1850 ↗

(On Diff #108083)

ah thanks for the clarification.

[reames]

In D35840#822809, @anna wrote:

This change looks good to me. However, I would suggest separating out the PlaceSafepoints (and it's testcase) change from the RewriteStatepointsForGC change. We don't use placeSafepoint anymore, so we should perhaps just deprecate it upstream, instead of fixing it.
@reames: What do you suggest?

Fixing both is definitely the right answer for the moment. PlaceSafepoints is questionable. It's a nice proof of concept, but given we aren't using it and thus testing it, it's probably starting to bit rot. I'd lean toward removing it, but let's check on llvm-dev to see if anyone else is using it before we just delete the code.

llvm/trunk/include/llvm/Transforms/Utils/Local.h

 /// Return true if the CallSite CS calls a gc leaf function.
 ///
 /// A leaf function is a function that does not safepoint the thread during its
 /// execution.  During a call or invoke to such a function, the callers stack
 /// does not have to be made parseable.
 ///
 /// Most passes can and should ignore this information, and it is only used
 /// during lowering by the GC infrastructure.
-bool callsGCLeafFunction(ImmutableCallSite CS);
+bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI);
 
 /// Copy a nonnull metadata node to a new load instruction.
 ///
 /// This handles mapping it to range metadata if the new load is an integer
 /// load instead of a pointer load.
 void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI);
 
 /// Copy a range metadata node to a new load instruction.

llvm/trunk/lib/Transforms/Scalar/PlaceSafepoints.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Pass.h"
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Statepoint.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
struct PlaceBackedgeSafepointsImpl : public FunctionPass {
 
   /// True unless we're running spp-no-calls in which case we need to disable
   /// the call-dependent placement opts.
   bool CallSafepointsEnabled;
 
   ScalarEvolution *SE = nullptr;
   DominatorTree *DT = nullptr;
   LoopInfo *LI = nullptr;
+  TargetLibraryInfo *TLI = nullptr;
 
   PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
       : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {
     initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *);
   void runOnLoopAndSubLoops(Loop *L) {
     // Visit all the subloops
     for (Loop *I : *L)
       runOnLoopAndSubLoops(I);
     runOnLoop(L);
   }
 
   bool runOnFunction(Function &F) override {
     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     for (Loop *I : *LI) {
       runOnLoopAndSubLoops(I);
     }
     return false;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
     // We no longer modify the IR at all in this pass.  Thus all
     // analysis are preserved.
     AU.setPreservesAll();
   }
 };
 }
 
 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));
 
 namespace {
 struct PlaceSafepoints : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
 
   PlaceSafepoints() : FunctionPass(ID) {
     initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     // We modify the graph wholesale (inlining, block insertion, etc).  We
     // preserve nothing at the moment.  We could potentially preserve dom tree
     // if that was worth doing
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 };
 }
 
 // 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(Instruction *InsertBefore,
-                    std::vector<CallSite> &ParsePointsNeeded /*rval*/);
+                    std::vector<CallSite> &ParsePointsNeeded /*rval*/,
+                    const TargetLibraryInfo &TLI);
 
-static bool needsStatepoint(const CallSite &CS) {
-  if (callsGCLeafFunction(CS))
+static bool needsStatepoint(const CallSite &CS, const TargetLibraryInfo &TLI) {
+  if (callsGCLeafFunction(CS, TLI))
     return false;
   if (CS.isCall()) {
     CallInst *call = cast<CallInst>(CS.getInstruction());
     if (call->isInlineAsm())
       return false;
   }
 
   return !(isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS));
 }
 
 /// 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) {
+                                               DominatorTree &DT,
+                                               const TargetLibraryInfo &TLI) {
   // In general, we're looking for any cut of the graph which ensures
   // there's a call safepoint along every edge between Header and Pred.
   // For the moment, we look only for the 'cuts' that consist of a single call
   // instruction in a block which is dominated by the Header and dominates the
   // loop latch (Pred) block.  Somewhat surprisingly, walking the entire chain
   // of such dominating blocks gets substantially more occurrences than just
   // checking the Pred and Header blocks themselves.  This may be due to the
   // density of loop exit conditions caused by range and null checks.
   // TODO: structure this as an analysis pass, cache the result for subloops,
   // avoid dom tree recalculations
   assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
 
   BasicBlock *Current = Pred;
   while (true) {
     for (Instruction &I : *Current) {
       if (auto CS = CallSite(&I))
         // Note: Technically, needing a safepoint isn't quite the right
         // condition here.  We should instead be checking if the target method
         // has an
         // unconditional poll. In practice, this is only a theoretical concern
         // since we don't have any methods with conditional-only safepoint
         // polls.
-        if (needsStatepoint(CS))
+        if (needsStatepoint(CS, TLI))
           return true;
     }
 
     if (Current == Header)
       break;
     Current = DT.getNode(Current)->getIDom()->getBlock();
   }
 
for (BasicBlock *Pred : LoopLatches) {
     // avoiding the runtime cost of the actual safepoint.
     if (!AllBackedges) {
       if (mustBeFiniteCountedLoop(L, SE, Pred)) {
         DEBUG(dbgs() << "skipping safepoint placement in finite loop\n");
         FiniteExecution++;
         continue;
       }
       if (CallSafepointsEnabled &&
-          containsUnconditionalCallSafepoint(L, Header, Pred, *DT)) {
+          containsUnconditionalCallSafepoint(L, Header, Pred, *DT, *TLI)) {
         // Note: This is only semantically legal since we won't do any further
         // IPO or inlining before the actual call insertion..  If we hadn't, we
         // might latter loose this call safepoint.
         DEBUG(dbgs() << "skipping safepoint placement due to unconditional call\n");
         CallInLoop++;
         continue;
       }
     }
if (isGCSafepointPoll(F)) {
     // doesn't make any sense.  Note that we do make any contained calls
     // parseable after we inline a poll.
     return false;
   }
 
   if (!shouldRewriteFunction(F))
     return false;
 
+  const TargetLibraryInfo &TLI =
+      getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+
   bool Modified = false;
 
   // In various bits below, we rely on the fact that uses are reachable from
   // defs.  When there are basic blocks unreachable from the entry, dominance
   // and reachablity queries return non-sensical results.  Thus, we preprocess
   // the function to ensure these properties hold.
   Modified |= removeUnreachableBlocks(F);
 
if (enableEntrySafepoints(F)) {
     // TODO: else we should assert that there was, in fact, a policy choice to
     // not insert a entry safepoint poll.
   }
 
   // Now that we've identified all the needed safepoint poll locations, insert
   // safepoint polls themselves.
   for (Instruction *PollLocation : PollsNeeded) {
     std::vector<CallSite> RuntimeCalls;
-    InsertSafepointPoll(PollLocation, RuntimeCalls);
+    InsertSafepointPoll(PollLocation, RuntimeCalls, TLI);
     ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
                             RuntimeCalls.end());
   }
 
   return Modified;
 }
 
 char PlaceBackedgeSafepointsImpl::ID = 0;

 
 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
                       false, false)
 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
                     false, false)
 
 static void
 InsertSafepointPoll(Instruction *InsertBefore,
-                    std::vector<CallSite> &ParsePointsNeeded /*rval*/) {
+                    std::vector<CallSite> &ParsePointsNeeded /*rval*/,
+                    const TargetLibraryInfo &TLI) {
   BasicBlock *OrigBB = InsertBefore->getParent();
   Module *M = InsertBefore->getModule();
   assert(M && "must be part of a module");
 
   // Inline the safepoint poll implementation - this will get all the branch,
   // control flow, etc..  Most importantly, it will introduce the actual slow
   // path call - where we need to insert a safepoint (parsepoint).
 
InsertSafepointPoll(Instruction *InsertBefore,
 
   // Record the fact we need a parsable state at the runtime call contained in
   // the poll function.  This is required so that the runtime knows how to
   // parse the last frame when we actually take  the safepoint (i.e. execute
   // the slow path)
   assert(ParsePointsNeeded.empty());
   for (auto *CI : Calls) {
     // No safepoint needed or wanted
-    if (!needsStatepoint(CI))
+    if (!needsStatepoint(CI, TLI))
       continue;
 
     // These are likely runtime calls.  Should we assert that via calling
     // convention or something?
     ParsePointsNeeded.push_back(CallSite(CI));
   }
   assert(ParsePointsNeeded.size() <= Calls.size());
 }

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
bool runOnModule(Module &M) override {
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     // We add and rewrite a bunch of instructions, but don't really do much
     // else.  We could in theory preserve a lot more analyses here.
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 
   /// The IR fed into RewriteStatepointsForGC may have had attributes and
   /// metadata implying dereferenceability that are no longer valid/correct after
   /// RewriteStatepointsForGC has run. This is because semantically, after
   /// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire
   /// heap. stripNonValidAttributesAndMetadata (conservatively) restores
   /// correctness by erasing all attributes in the module that externally imply
bool RewriteStatepointsForGC::runOnFunction(Function &F) {
   // Policy choice says not to rewrite - the most common reason is that we're
   // compiling code without a GCStrategy.
   if (!shouldRewriteStatepointsIn(F))
     return false;
 
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
   TargetTransformInfo &TTI =
       getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+  const TargetLibraryInfo &TLI =
+      getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
-  auto NeedsRewrite = [](Instruction &I) {
+  auto NeedsRewrite = [&TLI](Instruction &I) {
     if (ImmutableCallSite CS = ImmutableCallSite(&I))
-      return !callsGCLeafFunction(CS) && !isStatepoint(CS);
+      return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
     return false;
   };
 
   // Gather all the statepoints which need rewritten.  Be careful to only
   // consider those in reachable code since we need to ask dominance queries
   // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallSite, 64> ParsePointNeeded;
   bool HasUnreachableStatepoint = false;

llvm/trunk/lib/Transforms/Utils/Local.cpp

unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         const BasicBlock *BB) {
   auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
     auto *I = cast<Instruction>(U.getUser())->getParent();
     return DT.properlyDominates(BB, I);
   };
   return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
 }
 
-bool llvm::callsGCLeafFunction(ImmutableCallSite CS) {
+bool llvm::callsGCLeafFunction(ImmutableCallSite CS,
+                               const TargetLibraryInfo &TLI) {
   // Check if the function is specifically marked as a gc leaf function.
   if (CS.hasFnAttr("gc-leaf-function"))
     return true;
   if (const Function *F = CS.getCalledFunction()) {
     if (F->hasFnAttribute("gc-leaf-function"))
       return true;
 
     if (auto IID = F->getIntrinsicID())
       // Most LLVM intrinsics do not take safepoints.
       return IID != Intrinsic::experimental_gc_statepoint &&
              IID != Intrinsic::experimental_deoptimize;
   }
 
+  // Lib calls can be materialized by some passes, and won't be
+  // marked as 'gc-leaf-function.' All available Libcalls are
+  // GC-leaf.
+  LibFunc LF;
+  if (TLI.getLibFunc(CS, LF)) {
+    return TLI.has(LF);
+  }
+
   return false;
 }
 
 void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
                                LoadInst &NewLI) {
   auto *NewTy = NewLI.getType();
 
   // This only directly applies if the new type is also a pointer.

llvm/trunk/test/Transforms/PlaceSafepoints/libcall.ll

+; RUN: opt -S -place-safepoints < %s | FileCheck %s
+
+; Libcalls will not contain a safepoint poll, so check that we insert
+; a safepoint in a loop containing a libcall.
+declare double @ldexp(double %x, i32 %n) nounwind readnone
+define double @test_libcall(double %x) gc "statepoint-example" {
+; CHECK-LABEL: test_libcall
+
+entry:
+; CHECK: entry
+; CHECK-NEXT: call void @do_safepoint
+; CHECK-NEXT: br label %loop
+  br label %loop
+
+loop:
+; CHECK: loop
+; CHECK-NEXT: %x_loop = phi double [ %x, %entry ], [ %x_exp, %loop ]
+; CHECK-NEXT: %x_exp = call double @ldexp(double %x_loop, i32 5)
+; CHECK-NEXT: %done = fcmp ogt double %x_exp, 1.5
+; CHECK-NEXT: call void @do_safepoint
+  %x_loop = phi double [ %x, %entry ], [ %x_exp, %loop ]
+  %x_exp = call double @ldexp(double %x_loop, i32 5) nounwind readnone
+  %done = fcmp ogt double %x_exp, 1.5
+  br i1 %done, label %end, label %loop
+end:
+  %x_end = phi double [%x_exp, %loop]
+  ret double %x_end
+}
+
+; This function is inlined when inserting a poll.
+declare void @do_safepoint()
+define void @gc.safepoint_poll() {
+; CHECK-LABEL: gc.safepoint_poll
+entry:
+  call void @do_safepoint()
+  ret void
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/libcall.ll

+; A call to a libcall function is not a statepoint.
+; This test verifies that calls to libcalls functions do not get converted to
+; statepoint calls.
+; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
+
+declare double @ldexp(double %x, i32 %n) nounwind readnone
+
+define double @test_libcall(double %x) gc "statepoint-example" {
+; CHECK-LABEL: test_libcall
+; CHECK-NEXT: %res = call double @ldexp(double %x, i32 5)
+; CHECK-NEXT: ret double %res
+  %res = call double @ldexp(double %x, i32 5) nounwind readnone
+  ret double %res
+}