[DAGCombiner] mulhi + 1 never overflow.

[deadalnix]

Summary

This can be used to optimize large multiplications after legalization.

Depends on D29565

[efriedma]

Is it possible to write a testcase which isn't quite so big?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2779 ↗

(On Diff #87241)

Missing a check for which result you're using from the UMUL_LOHI. (I think this transform is only valid for the high result.)

2780 ↗

(On Diff #87241)

Could you just write this as "~N1Zero == 1"?

[deadalnix]

There is a nice small test case in adde-carry.ll , but it needs D29528 in addition to that one to trigger.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2779 ↗

(On Diff #87241)

You are absolutely right.

2780 ↗

(On Diff #87241)

I was wondering if I should match 0 or not. I went for the safe road and matched 0.

[deadalnix]

Only match mulhi

[efriedma]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2781 ↗

(On Diff #87305)

Another question: is there some reason to expect that N0 is the multiply, rather than N1?

[deadalnix]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2781 ↗

(On Diff #87305)

The specific case I'm looking at is fma like construct on big ints. After legalization you end up with combination of adde and mulhi no the left hand side. But indeed, that's an option to do it the other way around.

[deadalnix]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2781 ↗

(On Diff #87305)

So i tried to do it both ways. I see no difference in any of my tests cases, but, on the other hand, I see no reason not to do it. What do you think ?

[deadalnix]

Match the pattern both ways.

[efriedma]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2781 ↗

(On Diff #87305)

I don't really like duplicating the code like that... but I guess we need to do it that way to avoid calling computeKnownBits when we don't use the result?

You can probably construct a smaller testcase to trigger this; maybe something like (uint64_t)(c == 0) + (((uint64_t)a * (uint64_t)b) >> 32), where a, b, and c are 32-bit integers.

[deadalnix]

Update so it doesn't depend on D29565 anymore and has its own test.

[efriedma]

LGTM.

test/CodeGen/X86/overflow.ll

38 ↗

(On Diff #90233)

Maybe change this test to return %7 rather than just one bit of the high half of %7, so the code isn't completely dead? Not really important.

[deadalnix]

test/CodeGen/X86/overflow.ll

38 ↗

(On Diff #90233)

The code is dead either way, we shift right to get the carry.

[efriedma]

test/CodeGen/X86/overflow.ll

38 ↗

(On Diff #90233)

I mean make the function return i128, and make the last instruction "ret i128 %7", so we return the 64-bit sum in RAX, and zero in RDX.

[deadalnix]

test/CodeGen/X86/overflow.ll

38 ↗

(On Diff #90233)

Patch incoming.

[deadalnix]

Improve test case

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (N1Zero.getBoolValue()) {
     computeKnownBits(N0, N0Zero, N0One);
 
     bool overflow;
     (~N0Zero).uadd_ov(~N1Zero, overflow);
     if (!overflow)
       return OFK_Never;
   }
 
+  // mulhi + 1 never overflow
+  if (N0.getOpcode() == ISD::UMUL_LOHI && N0.getResNo() == 1 &&
+      (~N1Zero & 0x01) == ~N1Zero)
+    return OFK_Never;
+
+  if (N1.getOpcode() == ISD::UMUL_LOHI && N1.getResNo() == 1) {
+    APInt N0Zero, N0One;
+    computeKnownBits(N0, N0Zero, N0One);
+
+    if ((~N0Zero & 0x01) == ~N0Zero)
+      return OFK_Never;
+  }
+
   return OFK_Sometime;
 }
 
 bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val) const {
   EVT OpVT = Val.getValueType();
   unsigned BitWidth = OpVT.getScalarSizeInBits();
 
   // Is the constant a known power of 2?

llvm/trunk/test/CodeGen/X86/overflow.ll

 ; X32-NEXT:    retl $4
 ;
 ; X64-LABEL: mulhioverflow:
 ; X64:       # BB#0:
 ; X64-NEXT:    movq %rdx, %rcx
 ; X64-NEXT:    movq %rdi, %rax
 ; X64-NEXT:    mulq %rsi
 ; X64-NEXT:    andl $1, %ecx
-; X64-NEXT:    addq %rdx, %rcx
-; X64-NEXT:    sbbq %rdx, %rdx
-; X64-NEXT:    andl $1, %edx
-; X64-NEXT:    movq %rcx, %rax
+; X64-NEXT:    leaq (%rcx,%rdx), %rax
+; X64-NEXT:    xorl %edx, %edx
 ; X64-NEXT:    retq
   %1 = zext i64 %a to i128
   %2 = zext i64 %b to i128
   %3 = mul i128 %1, %2
   %4 = lshr i128 %3, 64
   %5 = and i64 %c, 1
   %6 = zext i64 %5 to i128
   %7 = add i128 %4, %6
   ret i128 %7
 }