[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

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

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

You are absolutely right.

2780

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

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

[deadalnix]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2781

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

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

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

52–54

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

52–54

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

[efriedma]

test/CodeGen/X86/overflow.ll

52–54

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

52–54

Patch incoming.

[deadalnix]

Improve test case

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?

test/CodeGen/X86/overflow.ll

 ; X32-NEXT:    popl %ebp
 ; 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
 }