Avoid tail recursion elimination across calls with operand bundles

[sanjoy]

Summary

In some specific scenarios with well understood operand bundle types
(like "deopt") it may be possible to go ahead and convert recursion to
iteration, but TailRecursionElimination does not have that logic today
so avoid doing the right thing for now.

I need some input on whether "funclet" operand bundles should also
block tail recursion elimination. If not, I'll allow TRE across calls
with "funclet" operand bundles and add a test case.

[majnemer]

I don't think funclets need to worry about this.

[sanjoy]

Address review: don't block TRE on funclet operand bundles.

[JosephTremoulet]

In D26270#586489, @majnemer wrote:

I don't think funclets need to worry about this.

I would have thought they did. If an exception is caught (so we enter the funclet) and then there's a recursive call to the main method (which has the funclet bundle), I think we want a new frame for the main method; if we rewrite that recursive call as a jump, but then an exception is raised in the recursive invocation, is the unwinder going to do the right thing? The IP will be telling it that we're in the main function, not the funclet. If that catch handler enters a try region before it makes the recursive call, then the main function and funclet would have different handlers, so we should be able to see empirically whether the right thing happens.

[majnemer]

In D26270#586668, @JosephTremoulet wrote:

In D26270#586489, @majnemer wrote:

I don't think funclets need to worry about this.

I would have thought they did. If an exception is caught (so we enter the funclet) and then there's a recursive call to the main method (which has the funclet bundle), I think we want a new frame for the main method; if we rewrite that recursive call as a jump, but then an exception is raised in the recursive invocation, is the unwinder going to do the right thing? The IP will be telling it that we're in the main function, not the funclet. If that catch handler enters a try region before it makes the recursive call, then the main function and funclet would have different handlers, so we should be able to see empirically whether the right thing happens.

This makes sense. OK, so we should treat funclet bundles like deopt bundles here.

[rnk]

test/Transforms/TailCallElim/operand-bundles.ll

53–54 ↗

(On Diff #76815)

It's kind of meaningless to attempt to return from a funclet without first returning to the parent function. Bad things would happen. I think we should go with the previous patch without the special casing for funclet.

[efriedma]

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

259

If CI->hasOperandBundles() is true, IsNoTail Is true, so this code is never reached. Therefore, this is equivalent to "SafeToTail = false;".

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

do {
     for (auto &I : *BB) {
       if (Tracker.EscapePoints.count(&I))
         Escaped = ESCAPED;
 
       CallInst *CI = dyn_cast<CallInst>(&I);
       if (!CI || CI->isTailCall())
         continue;
 
-      bool IsNoTail = CI->isNoTailCall();
+      bool IsNoTail = CI->isNoTailCall() || CI->hasOperandBundles();
 
       if (!IsNoTail && CI->doesNotAccessMemory()) {
         // A call to a readnone function whose arguments are all things computed
         // outside this function can be marked tail. Even if you stored the
         // alloca address into a global, a readnone function can't load the
         // global anyhow.
         //
         // Note that this runs whether we know an alloca has escaped or not. If
         // it has, then we can't trust Tracker.AllocaUsers to be accurate.
         bool SafeToTail = true;
         for (auto &Arg : CI->arg_operands()) {
           if (isa<Constant>(Arg.getUser()))
             continue;
           if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
             if (!A->hasByValAttr())
               continue;
           SafeToTail = false;
           break;
         }
+        SafeToTail &= CI->hasOperandBundles();
         if (SafeToTail) {
           emitOptimizationRemark(
               F.getContext(), "tailcallelim", F, CI->getDebugLoc(),
               "marked this readnone call a tail call candidate");
           CI->setTailCall();
           Modified = true;
           continue;
         }

llvm/trunk/test/Transforms/TailCallElim/deopt-bundle.ll

+; RUN: opt < %s -tailcallelim -S | FileCheck %s
+
+define i32 @f_1(i32 %x) {
+; CHECK-LABEL: @f_1(
+wentry:
+  %cond = icmp ugt i32 %x, 0
+  br i1 %cond, label %return, label %body
+
+body:
+; CHECK: body:
+; CHECK: call i32 @f_1(i32 %y) [ "deopt"() ]
+  %y = add i32 %x, 1
+  %tmp = call i32 @f_1(i32 %y) [ "deopt"() ]
+  ret i32 0
+
+return:
+  ret i32 1
+}
+
+define i32 @f_2(i32 %x) {
+; CHECK-LABEL: @f_2
+
+entry:
+  %cond = icmp ugt i32 %x, 0
+  br i1 %cond, label %return, label %body
+
+body:
+; CHECK: body:
+; CHECK: call i32 @f_2(i32 %y) [ "unknown"() ]
+  %y = add i32 %x, 1
+  %tmp = call i32 @f_2(i32 %y) [ "unknown"() ]
+  ret i32 0
+
+return:
+  ret i32 1
+}
+
+declare void @func()
+
+define void @f_3(i1 %B) personality i8 42 {
+; CHECK-LABEL: @f_3(
+entry:
+  invoke void @func()
+          to label %exit unwind label %merge
+merge:
+  %cs1 = catchswitch within none [label %catch] unwind to caller
+
+catch:
+; CHECK: catch:
+; CHECK: call void @f_3(i1 %B) [ "funclet"(token %cp) ]
+  %cp = catchpad within %cs1 []
+  call void @f_3(i1 %B) [ "funclet"(token %cp) ]
+  ret void
+
+exit:
+  ret void
+}