[InstCombine] Remove computeKnownBits() fold for returns

[nikic]

Summary

We try to fold constant computeKnownBits() with context for return instructions only. Otherwise, we rely on SimplifyDemandedBits() to fold instructions with constant known bits.

The presence of this special fold for returns is dangerous, because it makes our tests lie about what works and what doesn't. Tests are usually written by returning the result we're interested in, but will go through this separate code path that is not used for anything else. This patch removes the special fold.

This primarily regresses patterns of the style "assume(x); return x". The responsibility of handling such patterns lies with passes like EarlyCSE/GVN anyway, which will do this reliably, and not just for returns.

[goldstein.w.n]

This seems a bit counter-intuitive to the aim InstCombine, which unless I'm mistaken
is to simplify/cannonicalize IR to help other passes.
I would certainly think a constant is easier to work with than whatever expression
it came from.

[nikic]

In D151099#4361082, @goldstein.w.n wrote:

This seems a bit counter-intuitive to the aim InstCombine, which unless I'm mistaken
is to simplify/cannonicalize IR to help other passes.
I would certainly think a constant is easier to work with than whatever expression
it came from.

My point here is that this fold does not actually work, but its existence hides that fact because all our tests are return based. Take a look at: https://llvm.godbolt.org/z/zezhbvqhh Only the return case gets folded, but the store and br cases don't. All three cases are handled by -passes=gvn.

And yes, the aim of InstCombine is to simplify/canonicalize IR, but that does not mean that it is responsible for all possible simplifications, only a certain class of them. For example, it is not responsible for any CSE simplifications, which are under the purview of EarlyCSE and GVN.

If we do want to propagate "assume equals constant" facts in InstCombine, the way to do that would be as a combine on the assume itself, replacing the value of all dominated uses. The approach used by this code is not extensible to other cases, as it would basically require doing a separate computeKnownBits() call on every single use of every single value (to take into account different contexts). If you think handling this in InstCombine rather than GVN is important, I could look into implementing that...

For the case where the assumption is not a plain equality assumption (but e.g. that certain bits are known, and then only those bits are masked by and), we *should* be handling this via SimplifyDemandedBits -- but currently don't. This is actually how I got here in the first place. I'm trying to make sure that SimplifyDemandedBits produces the same results as computeKnownBits(). Such discrepancies are currently hidden by this return-only fold.

[goldstein.w.n]

In D151099#4361225, @nikic wrote:

In D151099#4361082, @goldstein.w.n wrote:

This seems a bit counter-intuitive to the aim InstCombine, which unless I'm mistaken
is to simplify/cannonicalize IR to help other passes.
I would certainly think a constant is easier to work with than whatever expression
it came from.

My point here is that this fold does not actually work, but its existence hides that fact because all our tests are return based. Take a look at: https://llvm.godbolt.org/z/zezhbvqhh Only the return case gets folded, but the store and br cases don't. All three cases are handled by -passes=gvn.

And yes, the aim of InstCombine is to simplify/canonicalize IR, but that does not mean that it is responsible for all possible simplifications, only a certain class of them. For example, it is not responsible for any CSE simplifications, which are under the purview of EarlyCSE and GVN.

I see what you mean about the tests and agree. Is there any situation where due to this change, we end up
propagating less simplified IR to other passes or will CSE/GVN always be in the pipeline to handle it?
If the former, I think we probably need some data from llvm-test-suite to make sure this doesn't end up
messing up other passes and maybe this change should be put in a series with the fixed for
SimplifyDemandedBits. If the latter then I have no objection to this change.

If we do want to propagate "assume equals constant" facts in InstCombine, the way to do that would be as a combine on the assume itself, replacing the value of all dominated uses. The approach used by this code is not extensible to other cases, as it would basically require doing a separate computeKnownBits() call on every single use of every single value (to take into account different contexts). If you think handling this in InstCombine rather than GVN is important, I could look into implementing that...

For the case where the assumption is not a plain equality assumption (but e.g. that certain bits are known, and then only those bits are masked by and), we *should* be handling this via SimplifyDemandedBits -- but currently don't. This is actually how I got here in the first place. I'm trying to make sure that SimplifyDemandedBits produces the same results as computeKnownBits(). Such discrepancies are currently hidden by this return-only fold.

[nikic]

In D151099#4361250, @goldstein.w.n wrote:

In D151099#4361225, @nikic wrote:

In D151099#4361082, @goldstein.w.n wrote:

This seems a bit counter-intuitive to the aim InstCombine, which unless I'm mistaken
is to simplify/cannonicalize IR to help other passes.
I would certainly think a constant is easier to work with than whatever expression
it came from.

My point here is that this fold does not actually work, but its existence hides that fact because all our tests are return based. Take a look at: https://llvm.godbolt.org/z/zezhbvqhh Only the return case gets folded, but the store and br cases don't. All three cases are handled by -passes=gvn.

And yes, the aim of InstCombine is to simplify/canonicalize IR, but that does not mean that it is responsible for all possible simplifications, only a certain class of them. For example, it is not responsible for any CSE simplifications, which are under the purview of EarlyCSE and GVN.

I see what you mean about the tests and agree. Is there any situation where due to this change, we end up
propagating less simplified IR to other passes or will CSE/GVN always be in the pipeline to handle it?
If the former, I think we probably need some data from llvm-test-suite to make sure this doesn't end up
messing up other passes and maybe this change should be put in a series with the fixed for
SimplifyDemandedBits. If the latter then I have no objection to this change.

At least on llvm-test-suite, this patch does not result in any codegen changes (binaries are identical).

[goldstein.w.n]

In D151099#4368306, @nikic wrote:

In D151099#4361250, @goldstein.w.n wrote:

In D151099#4361225, @nikic wrote:

In D151099#4361082, @goldstein.w.n wrote:

This seems a bit counter-intuitive to the aim InstCombine, which unless I'm mistaken
is to simplify/cannonicalize IR to help other passes.
I would certainly think a constant is easier to work with than whatever expression
it came from.

My point here is that this fold does not actually work, but its existence hides that fact because all our tests are return based. Take a look at: https://llvm.godbolt.org/z/zezhbvqhh Only the return case gets folded, but the store and br cases don't. All three cases are handled by -passes=gvn.

And yes, the aim of InstCombine is to simplify/canonicalize IR, but that does not mean that it is responsible for all possible simplifications, only a certain class of them. For example, it is not responsible for any CSE simplifications, which are under the purview of EarlyCSE and GVN.

I see what you mean about the tests and agree. Is there any situation where due to this change, we end up
propagating less simplified IR to other passes or will CSE/GVN always be in the pipeline to handle it?
If the former, I think we probably need some data from llvm-test-suite to make sure this doesn't end up
messing up other passes and maybe this change should be put in a series with the fixed for
SimplifyDemandedBits. If the latter then I have no objection to this change.

At least on llvm-test-suite, this patch does not result in any codegen changes (binaries are identical).

Okay LGTM.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 
 static bool isMustTailCall(Value *V) {
   if (auto *CI = dyn_cast<CallInst>(V))
     return CI->isMustTailCall();
   return false;
 }
 
 Instruction *InstCombinerImpl::visitReturnInst(ReturnInst &RI) {
-  if (RI.getNumOperands() == 0) // ret void
-    return nullptr;
-
-  Value *ResultOp = RI.getOperand(0);
-  Type *VTy = ResultOp->getType();
-  if (!VTy->isIntegerTy() || isa<Constant>(ResultOp))
-    return nullptr;
-
-  // Don't replace result of musttail calls.
-  if (isMustTailCall(ResultOp))
-    return nullptr;
-
-  // There might be assume intrinsics dominating this return that completely
-  // determine the value. If so, constant fold it.
-  KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
-  if (Known.isConstant())
-    return replaceOperand(RI, 0,
-        Constant::getIntegerValue(VTy, Known.getConstant()));
-
+  // Nothing for now.
   return nullptr;
 }
 
 // WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()!
 Instruction *InstCombinerImpl::visitUnreachableInst(UnreachableInst &I) {
   // Try to remove the previous instruction if it must lead to unreachable.
   // This includes instructions like stores and "llvm.assume" that may not get
   // removed by simple dead code elimination.

llvm/test/Transforms/InstCombine/assume.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=instcombine -S  -instcombine-infinite-loop-threshold=2  | FileCheck --check-prefixes=CHECK,DEFAULT %s
-; RUN: opt < %s -passes=instcombine --enable-knowledge-retention -S  -instcombine-infinite-loop-threshold=2  | FileCheck --check-prefixes=CHECK,BUNDLES %s
+; RUN: opt < %s -passes=instcombine -S  -instcombine-infinite-loop-threshold=3  | FileCheck --check-prefixes=CHECK,DEFAULT %s
+; RUN: opt < %s -passes=instcombine --enable-knowledge-retention -S  -instcombine-infinite-loop-threshold=3  | FileCheck --check-prefixes=CHECK,BUNDLES %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @llvm.assume(i1) #1
 
 ; Check that the alignment has been upgraded and that the assume has not
 ; been removed:
;
   %t0 = load i32, ptr %a, align 4
   ret i32 %t0
 }
 
 define i32 @simple(i32 %a) #1 {
 ; CHECK-LABEL: @simple(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A:%.*]], 4
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    ret i32 4
+; CHECK-NEXT:    ret i32 [[A]]
 ;
   %cmp = icmp eq i32 %a, 4
   tail call void @llvm.assume(i1 %cmp)
   ret i32 %a
 }
 
 define i32 @can1(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @can1(
entry:
   tail call void @llvm.assume(i1 %cmp2)
   ret i32 %and1
 }
 
 define i32 @icmp1(i32 %a) #0 {
 ; CHECK-LABEL: @icmp1(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A:%.*]], 5
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 }
 
 define i32 @icmp2(i32 %a) #0 {

 }
 
 ; If the 'not' of a condition is known true, then the condition must be false.
 
 define i1 @assume_not(i1 %cond) {
 ; CHECK-LABEL: @assume_not(
 ; CHECK-NEXT:    [[NOTCOND:%.*]] = xor i1 [[COND:%.*]], true
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NOTCOND]])
-; CHECK-NEXT:    ret i1 false
+; CHECK-NEXT:    ret i1 [[COND]]
 ;
   %notcond = xor i1 %cond, true
   call void @llvm.assume(i1 %notcond)
   ret i1 %cond
 }
 
 declare void @escape(ptr %a)
 
;
   %rval = icmp eq ptr %load, null
   ret i1 %rval
 }
 
 ; PR35846 - https://bugs.llvm.org/show_bug.cgi?id=35846
 
 define i32 @assumption_conflicts_with_known_bits(i32 %a, i32 %b) {
 ; CHECK-LABEL: @assumption_conflicts_with_known_bits(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], 3
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 false)
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[AND1]], 0
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
 ; CHECK-NEXT:    ret i32 0
 ;
   %and1 = and i32 %b, 3
   %B1 = lshr i32 %and1, %and1
   %B3 = shl nuw nsw i32 %and1, %B1
   %cmp = icmp eq i32 %B3, 1
   tail call void @llvm.assume(i1 %cmp)
   %cmp2 = icmp eq i32 %B1, %B3

 define i1 @nonnull3A(ptr %a, i1 %control) {
 ; DEFAULT-LABEL: @nonnull3A(
 ; DEFAULT-NEXT:  entry:
 ; DEFAULT-NEXT:    [[LOAD:%.*]] = load ptr, ptr [[A:%.*]], align 8
 ; DEFAULT-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
 ; DEFAULT:       taken:
 ; DEFAULT-NEXT:    [[CMP:%.*]] = icmp ne ptr [[LOAD]], null
 ; DEFAULT-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; DEFAULT-NEXT:    ret i1 true
+; DEFAULT-NEXT:    ret i1 [[CMP]]
 ; DEFAULT:       not_taken:
 ; DEFAULT-NEXT:    [[RVAL_2:%.*]] = icmp sgt ptr [[LOAD]], null
 ; DEFAULT-NEXT:    ret i1 [[RVAL_2]]
 ;
 ; BUNDLES-LABEL: @nonnull3A(
 ; BUNDLES-NEXT:  entry:
 ; BUNDLES-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
 ; BUNDLES:       taken:

 define i1 @nonnull3B(ptr %a, i1 %control) {
 ; CHECK-LABEL: @nonnull3B(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    [[LOAD:%.*]] = load ptr, ptr [[A:%.*]], align 8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne ptr [[LOAD]], null
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]]) [ "nonnull"(ptr [[LOAD]]) ]
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 [[CMP]]
 ; CHECK:       not_taken:
 ; CHECK-NEXT:    ret i1 [[CONTROL]]
 ;
 entry:
   %load = load ptr, ptr %a
   %cmp = icmp ne ptr %load, null
   br i1 %control, label %taken, label %not_taken
 taken:

llvm/test/Transforms/InstCombine/known-phi-br.ll

 define i64 @limit_i64_eq_7(i64 %x) {
 ; CHECK-LABEL: @limit_i64_eq_7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[X:%.*]], 7
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[BODY:%.*]]
 ; CHECK:       body:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret i64 7
+; CHECK-NEXT:    [[RES:%.*]] = phi i64 [ [[X]], [[ENTRY:%.*]] ], [ 7, [[BODY]] ]
+; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   %cmp = icmp eq i64 %x, 7
   br i1 %cmp, label %end, label %body
 body:
   br label %end
 end:
   %res = phi i64 [ %x, %entry ], [ 7, %body ]
   ret i64 %res
 }
 
 ; %x either eq 255 or is set to 255
 define i64 @limit_i64_ne_255(i64 %x) {
 ; CHECK-LABEL: @limit_i64_ne_255(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[X:%.*]], 255
 ; CHECK-NEXT:    call void @use(i1 [[CMP]])
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]]
 ; CHECK:       body:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret i64 255
+; CHECK-NEXT:    [[RES:%.*]] = phi i64 [ [[X]], [[ENTRY:%.*]] ], [ 255, [[BODY]] ]
+; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   %cmp = icmp ne i64 %x, 255
   call void @use(i1 %cmp)
   br i1 %cmp, label %body, label %end
 body:
   br label %end
 end:

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

 ; CHECK-NEXT:    [[T3:%.*]] = load i32, ptr [[F:%.*]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[T3]], [[CONV17]]
 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[F]], align 4
 ; CHECK-NEXT:    [[REM18:%.*]] = srem i32 [[LOR_EXT]], [[ADD]]
 ; CHECK-NEXT:    [[CONV19:%.*]] = zext i32 [[REM18]] to i64
 ; CHECK-NEXT:    store i32 [[SROA38]], ptr [[D]], align 8
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i64 [[INSERT_INSERT41]], [[CONV19]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[R]])
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 [[R]]
 ;
 entry:
   br label %for.cond
 
 for.cond:
   %i.sroa.8.0 = phi i32 [ poison, %entry ], [ %i.sroa.8.0.extract.trunc, %cond.true ]
   br i1 %c1, label %cond.true, label %for.end11