[CodeGenPrepare] Delete intrinsic call to llvm.assume to enable more tailcall

[Carrot]

Summary

The attached test case is simplified from tcmalloc. Both function calls should be optimized as tailcall. But llvm can only optimize the first call. The second call can't be optimized because function dupRetToEnableTailCallOpts failed to duplicate ret into block case2.

There 2 problems blocked the duplication:

1 Intrinsic call llvm.assume is not handled by dupRetToEnableTailCallOpts
2 The control flow is more complex than expected, dupRetToEnableTailCallOpts can only duplicate ret into its predecessor, but here we have an intermediate block between call and ret.

The solutions:

1 Since CodeGenPrepare is already at the end of LLVM IR phase, we can simply delete the intrinsic call to llvm.assume.
2 A general solution to the complex control flow is hard, but for this case, after exit2 is duplicated into case1, exit2 is the only successor of exit1 and exit1 is the only predecessor of exit2, so they can be combined through eliminateFallThrough. But this function is called too late, there is no more dupRetToEnableTailCallOpts after it. We can add an earlier call to eliminateFallThrough to solve it.

[arsenm]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

I would expect like object size/is_constant this would have been lowered already? I do disagree with using unreachable to error on this case though

[Carrot]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

This is not in my patch.
Do you want me to delete these 2 cases in the same patch?

[arsenm]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

I know, but I would expect this case to be handle the same way. These should also not be deleted, just upgraded to an error that won't be deleted in a release build

[Carrot]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

objectsize and is_constant are lowered at LowerConstantIntrinsics, Intrinsic::assume does not generate instructions, so was simply ignored at SelectionDAG. Do you mean delete it at LowerConstantIntrinsics?

Also does "just upgraded to an error that won't be deleted in a release build" mean Ctx.emitError()?

thanks!

[arsenm]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

That or report_fatal_error

[arsenm]

llvm/test/CodeGen/X86/tailcall-assume-xbb.ll

1 ↗

(On Diff #251827)

Move to test/CodeGenPrepare/X86?

2 ↗

(On Diff #251827)

Add a comment explaining what this tests?

[Carrot]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

Also delete Intrinsic::assume in LowerConstantIntrinsics?

llvm/test/CodeGen/X86/tailcall-assume-xbb.ll

1 ↗

(On Diff #251827)

I assume you mean test/Transforms/CodeGenPrepare/X86.

[arsenm]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

It's not handled there as you said, so I'm not sure what you're asking?

[Carrot]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1989–1990

Sorry for my bad English :(

Is this version OK now?

[xbolva00]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1971

Do we need to run RecursivelyDeleteTriviallyDeadInstructions on arg?

1992

Split these changes to new patch?

[Carrot]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1971

This function is called in a "while (MadeChange)" loop in function runOnFunction, so the instruction generates the assume condition will be deleted in next iteration. Either or not call RecursivelyDeleteTriviallyDeadInstructions are both OK.

[xbolva00]

Ok, thanks.

[thakis]

This likely broke many tests on Windows: http://45.33.8.238/win/11741/step_7.txt / http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/15029

Can you take a look, and revert while you investigate if it takes a while?

[Carrot]

This patch doesn't do any register level changes, so it looks unlike the root cause of the failure, maybe some unrelated bug was uncovered by this patch.

Do you have a linux reproduction? This test passed on my linux desktop.

[Carrot]

I took a look at the first failed test case amdgpu-hip-implicit-kernarg.cu, it contains an empty kernel function, it should not trigger any optimization code.

Does https://reviews.llvm.org/rG7e4e9f4a2fcb096778fb81fc96da6bb8aa966661 fixed this failure?

llvm/lib/CodeGen/CodeGenPrepare.cpp

for (Function::iterator I = F.begin(); I != F.end(); ) {
       if (ModifiedDTOnIteration)
         break;
     }
     if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
       MadeChange |= mergeSExts(F);
     if (!LargeOffsetGEPMap.empty())
       MadeChange |= splitLargeGEPOffsets();
 
+    if (MadeChange)
+      eliminateFallThrough(F);
+
     // Really free removed instructions during promotion.
     for (Instruction *I : RemovedInsts)
       I->deleteValue();
 
     EverMadeChange |= MadeChange;
     SeenChainsForSExt.clear();
     ValToSExtendedUses.clear();
     RemovedInsts.clear();
for (auto &Arg : CI->arg_operands()) {
       unsigned AS = Arg->getType()->getPointerAddressSpace();
       return optimizeMemoryInst(CI, Arg, Arg->getType(), AS);
     }
 
   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
   if (II) {
     switch (II->getIntrinsicID()) {
     default: break;
+    case Intrinsic::assume: {
+      II->eraseFromParent();
+      return true;
+    }
+
     case Intrinsic::experimental_widenable_condition: {
       // Give up on future widening oppurtunties so that we can fold away dead
       // paths and merge blocks before going into block-local instruction
       // selection.
       if (II->use_empty()) {
         II->eraseFromParent();
         return true;
       }
       Constant *RetVal = ConstantInt::getTrue(II->getContext());
       resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
         replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr);
       });
       return true;
     }
     case Intrinsic::objectsize:
       llvm_unreachable("llvm.objectsize.* should have been lowered already");
     case Intrinsic::is_constant:
       llvm_unreachable("llvm.is.constant.* should have been lowered already");
     case Intrinsic::aarch64_stlxr:
     case Intrinsic::aarch64_stxr: {
       ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
       if (!ExtVal || !ExtVal->hasOneUse() ||
           ExtVal->getParent() == CI->getParent())
         return false;
       // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
       ExtVal->moveBefore(CI);

llvm/test/Transforms/CodeGenPrepare/X86/extend-sink-hoist.ll

 ; RUN: opt -codegenprepare -disable-cgp-branch-opts -S < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; The first cast should be sunk into block2, in order that the
 ; instruction selector can form an efficient
 ; i64 * i64 -> i128 multiplication.
 define i128 @sink(i64* %mem1, i64* %mem2) {
 ; CHECK-LABEL: block1:
 ; CHECK-NEXT: load
 block1:
   %l1 = load i64, i64* %mem1
   %s1 = sext i64 %l1 to i128
   br label %block2
 
-; CHECK-LABEL: block2:
 ; CHECK-NEXT: sext
 ; CHECK-NEXT: load
 ; CHECK-NEXT: sext
 block2:
   %l2 = load i64, i64* %mem2
   %s2 = sext i64 %l2 to i128
   %res = mul i128 %s1, %s2
   ret i128 %res
 }
 
 ; The first cast should be hoisted into block1, in order that the
 ; instruction selector can form an extend-load.
 define i64 @hoist(i32* %mem1, i32* %mem2) {
 ; CHECK-LABEL: block1:
 ; CHECK-NEXT: load
 ; CHECK-NEXT: sext
 block1:
   %l1 = load i32, i32* %mem1
   br label %block2
 
-; CHECK-LABEL: block2:
 ; CHECK-NEXT: load
 ; CHECK-NEXT: sext
 block2:
   %s1 = sext i32 %l1 to i64
   %l2 = load i32, i32* %mem2
   %s2 = sext i32 %l2 to i64
   %res = mul i64 %s1, %s2
   ret i64 %res

llvm/test/Transforms/CodeGenPrepare/X86/optimizeSelect-DT.ll

 ; CHECK-NEXT:    [[MUL_FR:%.*]] = freeze i32 [[Y:%.*]]
 ; CHECK-NEXT:    [[T0:%.*]] = icmp eq i32 [[MUL_FR]], 1
 ; CHECK-NEXT:    br i1 [[T0]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]]
 ; CHECK:       select.true.sink:
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X:%.*]], 2
 ; CHECK-NEXT:    br label [[SELECT_END]]
 ; CHECK:       select.end:
 ; CHECK-NEXT:    [[MUL:%.*]] = phi i32 [ [[REM]], [[SELECT_TRUE_SINK]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[NEG:%.*]] = add i32 [[T1:%.*]], -1
+; CHECK-NEXT:    [[USUB:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[T1:%.*]], i32 1)
+; CHECK-NEXT:    [[NEG:%.*]] = extractvalue { i32, i1 } [[USUB]], 0
+; CHECK-NEXT:    [[TOBOOL:%.*]] = extractvalue { i32, i1 } [[USUB]], 1
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[NEG]], [[MUL]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    ret i1 [[TOBOOL]]
 ;
 entry:
   %rem = srem i32 %x, 2
   %t0 = icmp eq i32 %y, 1
   %mul = select i1 %t0, i32 %rem, i32 0
   %neg = add i32 %t1, -1
   %add = add i32 %neg, %mul
   br label %if
 
 if:
   %tobool = icmp eq i32 %t1, 0
   ret i1 %tobool
 }

llvm/test/Transforms/CodeGenPrepare/X86/tailcall-assume-xbb.ll

+; RUN: opt -codegenprepare -S -mtriple=x86_64-linux < %s | FileCheck %s
+
+; The ret instruction can be duplicated into BB case2 even though there is an
+; intermediate BB exit1 and call to llvm.assume.
+
+@ptr = external global i8*, align 8
+
+; CHECK:       %ret1 = tail call i8* @qux()
+; CHECK-NEXT:  ret i8* %ret1
+
+; CHECK:       %ret2 = tail call i8* @bar()
+; CHECK-NEXT:  ret i8* %ret2
+
+define i8* @foo(i64 %size, i64 %v1, i64 %v2) {
+entry:
+  %cmp1 = icmp ult i64 %size, 1025
+  br i1 %cmp1, label %if.end, label %case1
+
+case1:
+  %ret1 = tail call i8* @qux()
+  br label %exit2
+
+if.end:
+  %cmp2 = icmp ult i64 %v1, %v2
+  br i1 %cmp2, label %case3, label %case2
+
+case2:
+  %ret2 = tail call i8* @bar()
+  br label %exit1
+
+case3:
+  %ret3 = load i8*, i8** @ptr, align 8
+  br label %exit1
+
+exit1:
+  %retval1 = phi i8* [ %ret2, %case2 ], [ %ret3, %case3 ]
+  %cmp3 = icmp ne i8* %retval1, null
+  tail call void @llvm.assume(i1 %cmp3)
+  br label %exit2
+
+exit2:
+  %retval2 = phi i8* [ %ret1, %case1 ], [ %retval1, %exit1 ]
+  ret i8* %retval2
+}
+
+declare void @llvm.assume(i1)
+declare i8* @qux()
+declare i8* @bar()