[DAE] Don't DAE if we musttail call a "live" (non-DAE-able) function

[mtrofin]

Summary

There are 2 such base cases: indirect calls and calls to functions external to the module; and then any musttail calls to live functions (because of the first 2 reasons or otherwise).

The IR validator reports, in these cases, that it "cannot guarantee tail call due to mismatched parameter counts".

The fix is two-fold: first, we mark as "live" (i.e. non-DAE-able) functions that make an indirect musttail call. Then, we propagate live-ness to musttail callers of live functions.

Declared functions are already marked "live".

[mtrofin]

newline at end of test file

[efriedma]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Please explain why this matters. Intuitively, whether a function is virtual shouldn't affect liveness... do we handle the non-virtual case somewhere else?

[mtrofin]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Not sure I understand. It's about virtual musttail calls, not just virtual. "Liveness" in this pass means "it can't change".

Without the patch, the test fails in the validator, because the module is transformed to:

define internal void @test(ptr %fptr, i32 %a, i32 %b) {
  %r = musttail call i32 %fptr(ptr %fptr, i32 %a, i32 0)
  ret void
}

The error is what the test checks isn't present: cannot guarantee tail call due to mismatched parameter counts

The patch is actually incomplete - about to update it. This marking needs to be also propagated to users of the function.

[mtrofin]

propagate

[nikic]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

I believe Eli's point is that this is also true for non-virtual functions. For example, this example without virtual calls fails in the same way:

define internal i32 @test() {
  %r = musttail call i32 @foo()
  ret i32 %r
}

declare i32 @foo()

[mtrofin]

non-virt

[mtrofin]

remove spurious member

[mtrofin]

<eyeroll>

[mtrofin]

handle cycles

[mtrofin]

I *think* @rnk is out for a few weeks, @nikic, does the patch look reasonable to you?

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Oh, I see. Let me update then.

[efriedma]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Please add a comment explaining why direct calls and indirect calls are handled differently. (Is it related to the usage of getCalledFunction() in surveyUse?)

[mtrofin]

clarify it's not about indirect calls only

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Ah, it's not "direct" vs "indirect", rather, it's "can the callee be statically known and is it defined in this module". If it is, then we know that whatever transformations we plan on making at the callsite will also be reflected in the body of that callee. But if it's not, we don't know if that could happen.

Declarations ended up being marked as "live" just below. So we'd pick up that in propagateVirtMustcallLiveness.

All that being said, I think handling both callee cases here is more clear (+clarifying comment)

WDYT?

[efriedma]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

The concept makes sense to me... I'd prefer some more obvious way to quantify "calls to functions we can't analyze" to make it more obvious this is the inverse of the calls we do analyze.

[mtrofin]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

Would a isCalleeAnalyzable member that does the !TC->getCalledFunction() || TC->getCalledFunction()->isDeclaration() address that?

[efriedma]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

That's reasonable.

[mtrofin]

more clarity

[mtrofin]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

531

done, ptal (ended up just a function, no need for a member)

[mtrofin]

@efriedma , is this patch good to go? Thanks!

[efriedma]

I'm not really an expert on this pass, but sure, seems fine, assuming @nikic doesn't have any further comments.

[nikic]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

89

Is isDeclaration() the right criterion here? Shouldn't we be checking for hasLocalLinkage()?

1115

It's not really clear to me why we need a separate loop to do this, and this can't be included as part of the existing liveness propagation. E.g. surveyFunction() already looks at all the users, and even checks for musttail callers there. Currently, that's only used to mark all the arguments as live, but not the return values. Would it be sufficient to force live return values at that point?

llvm/test/Transforms/DeadArgElim/musttail-indirect.ll

2

verify is unnecessary, as is 2>&1, as is the CHECK-NOT. Verification failure causes a crash and will fail the test regardless of output.

Please also update update_test_checks.py.

[mtrofin]

feedback

[mtrofin]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

89

Line 544 has the hasLocalLinkage bit. The case here is about callees of musttail calls.

Maybe I can rename this to isMusttailCalleeAnalyzable and hoist up the rest of the test, for clarity.

1115

IIUC, if both argument and return values are marked, it'd be equivalent to the function being marked as live.

But that aside, we can have A->B->C->x (all are musttail calls), and C has the unanalyzable callsite. That needs to "taint" all in the call chain. We could do that propagation in surveyFunction, but that would be equivalent to this patch, unless I'm missing something?

llvm/test/Transforms/DeadArgElim/musttail-indirect.ll

2

done, sending a separate patch w the change in 2010-04-30-DbgInfo.ll, seems unrelated.

[nikic]

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

1115

DAE already propagates liveness across call chains, so it is best to reuse existing propagation is possible. However, after looking a bit closer I don't think we can actually use it, because for return values the propagation will go in the wrong direction. In that case, doing this separate propagation is reasonable.

llvm/test/Transforms/DeadArgElim/2010-04-30-DbgInfo.ll

111 ↗

(On Diff #503773)

Why the changes to this file? I don't see any musttail usage.

llvm/test/Transforms/DeadArgElim/musttail-indirect.ll

2

This still has an unnecessary verify and doesn't use update_test_checks.

[mtrofin]

gen test with update_test_checks

[mtrofin]

llvm/test/Transforms/DeadArgElim/2010-04-30-DbgInfo.ll

111 ↗

(On Diff #503773)

Misunderstanding on my part.

llvm/test/Transforms/DeadArgElim/musttail-indirect.ll

2

Ah, I misunderstood - I thought you meant "run update_test_checks on the other tests" - to see if they need a refresh due to this change (I assumed).

[mtrofin]

Tried out the change on compile-time tracker, seems very neutral: http://llvm-compile-time-tracker.com/compare.php?from=2e8ef93439a4a430fe5f96b9d999ce96405345f4&to=c4b2e5550264027608d40db0da53b1b9019d45a2&stat=instructions:u

@nikic, is this patch good to go now? Thanks!

[nikic]

LG

llvm/include/llvm/Transforms/IPO/DeadArgumentElimination.h

private:
   void markValue(const RetOrArg &RA, Liveness L,
                  const UseVector &MaybeLiveUses);
   void markLive(const RetOrArg &RA);
   void markLive(const Function &F);
   void propagateLiveness(const RetOrArg &RA);
   bool removeDeadStuffFromFunction(Function *F);
   bool deleteDeadVarargs(Function &F);
   bool removeDeadArgumentsFromCallers(Function &F);
+  void propagateVirtMustcallLiveness(const Module &M);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H

llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

bool runOnModule(Module &M) override {
     ModuleAnalysisManager DummyMAM;
     PreservedAnalyses PA = DAEP.run(M, DummyMAM);
     return !PA.areAllPreserved();
   }
 
   virtual bool shouldHackArguments() const { return false; }
 };
 
+bool isMustTailCalleeAnalyzable(const CallBase &CB) {
+  assert(CB.isMustTailCall());
+  return CB.getCalledFunction() && !CB.getCalledFunction()->isDeclaration();
+}
+
 } // end anonymous namespace
 
 char DAE::ID = 0;
 
 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)
 
 namespace {
 
void DeadArgumentEliminationPass::surveyFunction(const Function &F) {
   // we can add those to the Uses map if the return value really turns out to be
   // MaybeLive. Initialized to a list of RetCount empty lists.
   RetUses MaybeLiveRetUses(RetCount);
 
   bool HasMustTailCalls = false;
   for (const BasicBlock &BB : F) {
     // If we have any returns of `musttail` results - the signature can't
     // change
-    if (BB.getTerminatingMustTailCall() != nullptr)
+    if (const auto *TC = BB.getTerminatingMustTailCall()) {
       HasMustTailCalls = true;
+      // In addition, if the called function is not locally defined (or unknown,
+      // if this is an indirect call), we can't change the callsite and thus
+      // can't change this function's signature either.
+      if (!isMustTailCalleeAnalyzable(*TC)) {
+        markLive(F);
+        return;
+      }
+    }
   }
 
   if (HasMustTailCalls) {
     LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()
                       << " has musttail calls\n");
   }
 
   if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {
bool DeadArgumentEliminationPass::removeDeadStuffFromFunction(Function *F) {
   }
 
   // Now that the old function is dead, delete it.
   F->eraseFromParent();
 
   return true;
 }
 
+void DeadArgumentEliminationPass::propagateVirtMustcallLiveness(
+    const Module &M) {
+  // If a function was marked "live", and it has musttail callers, they in turn
+  // can't change either.
+  LiveFuncSet NewLiveFuncs(LiveFunctions);
+  while (!NewLiveFuncs.empty()) {
+    LiveFuncSet Temp;
+    for (const auto *F : NewLiveFuncs)
+      for (const auto *U : F->users())
+        if (const auto *CB = dyn_cast<CallBase>(U))
+          if (CB->isMustTailCall())
+            if (!LiveFunctions.count(CB->getParent()->getParent()))
+              Temp.insert(CB->getParent()->getParent());
+    NewLiveFuncs.clear();
+    NewLiveFuncs.insert(Temp.begin(), Temp.end());
+    for (const auto *F : Temp)
+      markLive(*F);
+  }
+}
+
 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M,
                                                    ModuleAnalysisManager &) {
   bool Changed = false;
 
   // First pass: Do a simple check to see if any functions can have their "..."
   // removed.  We can do this if they never call va_start.  This loop cannot be
   // fused with the next loop, because deleting a function invalidates
   // information computed while surveying other functions.
   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n");
   for (Function &F : llvm::make_early_inc_range(M))
     if (F.getFunctionType()->isVarArg())
       Changed |= deleteDeadVarargs(F);
 
   // Second phase: Loop through the module, determining which arguments are
   // live. We assume all arguments are dead unless proven otherwise (allowing us
   // to determine that dead arguments passed into recursive functions are dead).
   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");
   for (auto &F : M)
     surveyFunction(F);
 
+  propagateVirtMustcallLiveness(M);
+
   // Now, remove all dead arguments and return values from each function in
   // turn.  We use make_early_inc_range here because functions will probably get
   // removed (i.e. replaced by new ones).
   for (Function &F : llvm::make_early_inc_range(M))
     Changed |= removeDeadStuffFromFunction(&F);
 
   // Finally, look for any unused parameters in functions with non-local
   // linkage and replace the passed in parameters with poison.
   for (auto &F : M)
     Changed |= removeDeadArgumentsFromCallers(F);
 
   if (!Changed)
     return PreservedAnalyses::all();
   return PreservedAnalyses::none();
 }

llvm/test/Transforms/DeadArgElim/musttail-indirect.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: -p --function-signature
+; RUN: opt -passes=deadargelim -S < %s | FileCheck %s
+
+define internal i32 @test_caller(ptr %fptr, i32 %a, i32 %b) {
+; CHECK-LABEL: define {{[^@]+}}@test_caller(ptr %fptr, i32 %a, i32 %b) {
+; CHECK-NEXT:    %r = musttail call i32 @test(ptr %fptr, i32 %a, i32 poison)
+; CHECK-NEXT:    ret i32 %r
+;
+  %r = musttail call i32 @test(ptr %fptr, i32 %a, i32 %b)
+  ret i32 %r
+}
+
+define internal i32 @test(ptr %fptr, i32 %a, i32 %b) {
+; CHECK-LABEL: define {{[^@]+}}@test(ptr %fptr, i32 %a, i32 %b) {
+; CHECK-NEXT:    %r = musttail call i32 %fptr(ptr %fptr, i32 %a, i32 0)
+; CHECK-NEXT:    ret i32 %r
+;
+  %r = musttail call i32 %fptr(ptr %fptr, i32 %a, i32 0)
+  ret i32 %r
+}
+
+define internal i32 @direct_test() {
+; CHECK-LABEL: define {{[^@]+}}@direct_test() {
+; CHECK-NEXT:    %r = musttail call i32 @foo()
+; CHECK-NEXT:    ret i32 %r
+;
+  %r = musttail call i32 @foo()
+  ret i32 %r
+}
+
+declare i32 @foo()
+
+define internal i32 @ping(i32 %x) {
+; CHECK-LABEL: define {{[^@]+}}@ping(i32 %x) {
+; CHECK-NEXT:    %r = musttail call i32 @pong(i32 %x)
+; CHECK-NEXT:    ret i32 %r
+;
+  %r = musttail call i32 @pong(i32 %x)
+  ret i32 %r
+}
+
+define internal i32 @pong(i32 %x) {
+; CHECK-LABEL: define {{[^@]+}}@pong(i32 %x) {
+; CHECK-NEXT:    %cond = icmp eq i32 %x, 2
+; CHECK-NEXT:    br i1 %cond, label %yes, label %no
+; CHECK:       yes:
+; CHECK-NEXT:    %r1 = musttail call i32 @ping(i32 %x)
+; CHECK-NEXT:    ret i32 %r1
+; CHECK:       no:
+; CHECK-NEXT:    %r2 = musttail call i32 @bar(i32 %x)
+; CHECK-NEXT:    ret i32 %r2
+;
+  %cond = icmp eq i32 %x, 2
+  br i1 %cond, label %yes, label %no
+
+yes:
+  %r1 = musttail call i32 @ping(i32 %x)
+  ret i32 %r1
+no:
+  %r2 = musttail call i32 @bar(i32 %x)
+  ret i32 %r2
+}
+
+declare i32 @bar(i32 %x)
+