DAG: avoid truncating a sign extended operand when test equality against zero

[weimingz]

Summary

When an operand is tested for EQ/NE against zero and the operand is sign extended, the truncate instruction is not needed.

E.g. given

if (short_val == 0)
...

It currently generates code for ARM like

movw r1, #65535
tst r0, r1
it eq
...

instead of
cbz r0

[t.p.northover]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

961–962

The comment should probably be in the block it belongs to.

963

I think there are a couple of issues here.

First, I think you need to check that the AssertSext is from the same type (or smaller) as the original values (like above). Otherwise there could still be unknown rubbish in between the two cut-offs.

Second, don't all of these cases apply equally to AssertZext?

test/CodeGen/ARM/interrupt-attr.ll

52–54 ↗

(On Diff #65976)

This looks unrelated?

[weimingz]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

963

AssertZExt is handled in later DAG combining because it can computes the known bits.

test/CodeGen/ARM/interrupt-attr.ll

52–54 ↗

(On Diff #65976)

sorry. I added the wrong file. I suppose to add the test case for it.

[eli.friedman]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

949–958

Could you just use OpL->ComputeNumSignBits() > ExtensionBits && OpR->ComputeNumSignBits() > ExtensionBits or something like that here?

[weimingz]

@Eli please review the new patch.

[eli.friedman]

I think you missed the point of my suggestion... as long as you can prove both sides have enough sign bits, it doesn't matter what kind of node you're dealing with.

[weimingz]

@Eli, is patch set 5 what you mean? I'm more confident with patch set 4 though. :)

[eli.friedman]

It would be nice to have a couple testcases involving numbers which aren't zero.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

949–958

This check is now unnecessary.

966

Maybe reorganize this a bit to make it more readable? A couple variables might be helpful.

[eli.friedman]

Oh, and yes, this version is what I was thinking of.

[weimingz]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

949–958

Yes. I was thinking the same. But my concern is computeNumSignBits only gives its best knowledge by looking into no more than 6 steps. Will it miss some cases?

[eli.friedman]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

949–958

It definitely won't miss this case, which doesn't require any recursion at all. When computeNumSignBits hits the recursion limit, it doesn't completely abandon the computation; it just treats the SDValue at the recursion limit as an opaque value.

[weimingz]

Address Eli's comments

[eli.friedman]

test/CodeGen/ARM/no_redundant_trunc_for_cmp.ll

11

Some of these tests look a little fragile; maybe generate checks with update_llc_test_checks.py?

Otherwise LGTM.

[weimingz]

Thanks Eli for reviewing.
Is the tool for x86 only?

Anyway, I added some reg exp to let the CHECK rule be more generic

[eli.friedman]

Oh, I wasn't really paying attention to that... I guess it is? If it doesn't work, that's fine. :) The tests look better now.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

void DAGTypeLegalizer::PromoteSetCCOperands(SDValue &NewLHS,SDValue &NewRHS,
   // many machines (an AND instead of two shifts), so prefer it.
   switch (CCCode) {
   default: llvm_unreachable("Unknown integer comparison!");
   case ISD::SETEQ:
   case ISD::SETNE: {
     SDValue OpL = GetPromotedInteger(NewLHS);
     SDValue OpR = GetPromotedInteger(NewRHS);
 
-    // We would prefer to promote the comparison operand with sign extension,
-    // if we find the operand is actually to truncate an AssertSext. With this
-    // optimization, we can avoid inserting real truncate instruction, which
-    // is redudant eventually.
-    if (OpL->getOpcode() == ISD::AssertSext &&
-        cast<VTSDNode>(OpL->getOperand(1))->getVT() == NewLHS.getValueType() &&
-        OpR->getOpcode() == ISD::AssertSext &&
-        cast<VTSDNode>(OpR->getOperand(1))->getVT() == NewRHS.getValueType()) {
+    // We would prefer to promote the comparison operand with sign extension.
+    // If the width of OpL/OpR excluding the duplicated sign bits is no greater
+    // than the width of NewLHS/NewRH, we can avoid inserting real truncate
+    // instruction, which is redudant eventually.
+    unsigned OpLEffectiveBits =
+        OpL.getValueType().getSizeInBits() - DAG.ComputeNumSignBits(OpL) + 1;
+    unsigned OpREffectiveBits =
+        OpR.getValueType().getSizeInBits() - DAG.ComputeNumSignBits(OpR) + 1;
+    if (OpLEffectiveBits <= NewLHS.getValueType().getSizeInBits() &&
+        OpREffectiveBits <= NewRHS.getValueType().getSizeInBits()) {
       NewLHS = OpL;
       NewRHS = OpR;
     } else {
       NewLHS = ZExtPromotedInteger(NewLHS);
       NewRHS = ZExtPromotedInteger(NewRHS);
     }
     break;
   }
   case ISD::SETUGE:
   case ISD::SETUGT:
   case ISD::SETULE:
   case ISD::SETULT:
     // ALL of these operations will work if we either sign or zero extend
     // the operands (including the unsigned comparisons!).  Zero extend is
     // usually a simpler/cheaper operation, so prefer it.
     NewLHS = ZExtPromotedInteger(NewLHS);

test/CodeGen/AArch64/arm64-shrink-wrapping.ll

 
 ; Make sure we do not insert unreachable code after noreturn function.
 ; Although this is not incorrect to insert such code, it is useless
 ; and it hurts the binary size.
 ;
 ; CHECK-LABEL: noreturn:
 ; DISABLE: stp
 ;
-; CHECK: and [[TEST:w[0-9]+]], w0, #0xff
-; CHECK-NEXT: cbnz [[TEST]], [[ABORT:LBB[0-9_]+]]
+; CHECK: cbnz w0, [[ABORT:LBB[0-9_]+]]
 ;
 ; CHECK: mov w0, #42
 ;
 ; DISABLE-NEXT: ldp
 ;
 ; CHECK-NEXT: ret
 ;
 ; CHECK: [[ABORT]]: ; %if.abort

test/CodeGen/ARM/arm-shrink-wrapping.ll

 declare i32 @someVariadicFunc(i32, ...)
 
 ; Make sure we do not insert unreachable code after noreturn function.
 ; Although this is not incorrect to insert such code, it is useless
 ; and it hurts the binary size.
 ;
 ; CHECK-LABEL: noreturn:
 ; DISABLE: push
-;
-; CHECK: tst{{(\.w)?}}  r0, #255
-; CHECK-NEXT: bne      [[ABORT:LBB[0-9_]+]]
+; ARM-ENABLE: cmp r0, #0
+; ARM-DISABLE: cmp r0, #0
+; ARM-ENABLE: bne [[ABORT:LBB[0-9_]+]]
+; ARM-DISABLE: bne [[ABORT:LBB[0-9_]+]]
+; THUMB-ENABLE: cbnz r0,  [[ABORT:LBB[0-9_]+]]
+; THUMB-DISABLE: cbnz r0,  [[ABORT:LBB[0-9_]+]]
+
 ;
 ; CHECK: mov{{s?}} r0, #42
 ;
 ; ENABLE-NEXT: bx lr
 ;
 ; DISABLE-NEXT: pop
 ;;
 ; CHECK: [[ABORT]]: @ %if.abort

test/CodeGen/ARM/no_redundant_trunc_for_cmp.ll

+; This test check if redundant truncate for eq/ne cmp is skipped during code gen.
+;RUN: llc -mtriple=thumbv7-eabi < %s | FileCheck %s
+
+define void @test_zero(i16 signext %x) optsize {
+;CHECK-LABEL: test_zero
+entry:
+  %tobool = icmp eq i16 %x, 0
+  br i1 %tobool, label %if.else, label %if.then
+;CHECK-NOT: movw {{.*}}, #65535
+;CHECK: cbz r0,
+if.then:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo1 to void ()*)()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo2 to void ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define void @test_i8_nonzero(i18 signext %x) optsize {
+;CHECK-LABEL: test_i8_nonzero
+entry:
+  %tobool = icmp eq i18 %x, 150
+  br i1 %tobool, label %if.else, label %if.then
+;CHECK-NOT: bfc
+;CHECK: cmp r{{[0-9]+}}, #150
+if.then:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo1 to void ()*)()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo2 to void ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define void @test_i8_i16(i8 signext %x) optsize {
+;CHECK-LABEL: test_i8_i16
+entry:
+  %x16 = sext i8 %x to i16
+  %tobool = icmp eq i16 %x16, 300
+  br i1 %tobool, label %if.else, label %if.then
+;CHECK-NOT: uxth r0, r0
+;CHECK: cmp.w r0, #300
+if.then:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo1 to void ()*)()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo2 to void ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define void @test_i16_i8(i16 signext %x) optsize {
+;CHECK-LABEL: test_i16_i8
+entry:
+;CHECK: uxtb [[REG:r[0-9+]]], r0
+;CHECK: cmp [[REG]], #128
+  %x8 = trunc i16 %x to i8
+  %tobool = icmp eq i8 %x8, 128
+  br i1 %tobool, label %if.else, label %if.then
+if.then:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo1 to void ()*)()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo2 to void ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define void @test_zext_zero(i16 zeroext %x) optsize {
+;CHECK-LABEL: test_zext_zero
+entry:
+  %tobool = icmp eq i16 %x, 0
+  br i1 %tobool, label %if.else, label %if.then
+;CHECK-NOT: movw {{.*}}, #65535
+;CHECK: cbz r0,
+if.then:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo1 to void ()*)()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void bitcast (void (...)* @foo2 to void ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+
+declare void @foo1(...)
+declare void @foo2(...)
+
+

test/CodeGen/PowerPC/ppc-shrink-wrapping.ll

 
 ; Make sure we do not insert unreachable code after noreturn function.
 ; Although this is not incorrect to insert such code, it is useless
 ; and it hurts the binary size.
 ;
 ; CHECK-LABEL: noreturn:
 ; DISABLE: mflr {{[0-9]+}}
 ;
-; CHECK: cmplwi 3, 0
+; CHECK: cmplwi 0, 3, 0
 ; CHECK-NEXT: bne{{[-]?}} 0, .[[ABORT:LBB[0-9_]+]]
 ;
 ; CHECK: li 3, 42
 ;
 ; DISABLE: mtlr {{[0-9]+}}
 ;
 ; CHECK-NEXT: blr
 ;

test/CodeGen/Thumb/thumb-shrink-wrapping.ll

 
 ; Make sure we do not insert unreachable code after noreturn function.
 ; Although this is not incorrect to insert such code, it is useless
 ; and it hurts the binary size.
 ;
 ; CHECK-LABEL: noreturn:
 ; DISABLE: push
 ;
-; CHECK: movs [[TMP:r[0-9]+]], #255
-; CHECK-NEXT: tst  r0, [[TMP]]
+; CHECK: cmp r0, #0
 ; CHECK-NEXT: bne      [[ABORT:LBB[0-9_]+]]
 ;
 ; CHECK: movs r0, #42
 ;
 ; ENABLE-NEXT: bx lr
 ;
 ; DISABLE-NEXT: pop
 ;;