[InstCombine] Added support for: trunc(ashr(mul(sext(...), sext(...))) -> ashr(mul(...))

[aaboud]

Summary

Added support for the following case:

define i16 @test6_ashr_mul(i8 %X, i8 %Y) {
; CHECK-LABEL: @test6_ashr_mul(
; CHECK-NEXT: [[A:%.*]] = sext i8 %X to i16
; CHECK-NEXT: [[B:%.*]] = sext i8 %Y to i16
; CHECK-NEXT: [[C:%.*]] = mul nsw i16 [[A]], [[B]]
; CHECK-NEXT: [[D:%.*]] = ashr i16 %C, 15
; CHECK-NEXT: ret i16 %D

%A = sext i8 %X to i32
%B = sext i8 %Y to i32
%C = mul i32 %A, %B
%D = ashr i32 %C, 15
%E = trunc i32 %D to i16
ret i16 %E

}

So far, InstCombine handled only LShr instruction and tried to replace AShr instruction with the LShr when applicable.
However, there are cases where LShr has no advantage over AShr, especially when the higher bits are not known to be zero, but are known to be equal to the sign bit.

Note: There is more to do to catch all the cases where AShr can be optimized, but we end up having LShr instead, e.g., we could replace LShr with AShr when applicable. However, the current implementation of InstCombine will probably lead into infinite loop if we try implement both transform direction (i.e., LShr->AShr and AShr->LShr).

[spatel]

lib/Transforms/InstCombine/InstCombineShifts.cpp

562–565 ↗

(On Diff #110960)

Use 'm_Shr' to reduce the code. This change is independent of anything else, so I think it should go in first.
http://rise4fun.com/Alive/lBi
Here's a test you can use for that patch:

define i8 @shishi(i8 %x) {
  %a = ashr i8 %x, 6
  %b = shl i8 %a, 6
  %extra_use_of_a = mul i8 %a, 5
  %r = sdiv i8 %extra_use_of_a, %b
  ret i8 %r
}

[aaboud]

Split the patch by moving: (X >>s C) << C --> X & (-1 << C) to D36743.

[spatel]

I think all of the non-multiply tests are simplified after rL310942. Can you double-check that? If so, you can remove those tests from this patch. Feel free to add them as an independent NFC commit if they cover some case that isn't covered already.

It may also be possible to simplify the code in this patch now, but I didn't check that.

[aaboud]

Updated patch to top of trunk and removed NFC tests (will commit them separately).

[spatel]

Can we have the ashr fix as a separate patch before the mul patch? If yes, make tests for just that diff and split this up?

lib/Transforms/InstCombine/InstCombineCasts.cpp

378 ↗

(On Diff #111247)

Over in D36763, we're going to (or maybe already have) made the other shift cases splat-vector-friendly. Can you do the same here and add a vector test?

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

468 ↗

(On Diff #111247)

Why change this in this patch? Seem like that might be better as just 'unsigned', but either way, I think it's an independent diff.

[aaboud]

In D36679#842794, @spatel wrote:

Can we have the ashr fix as a separate patch before the mul patch? If yes, make tests for just that diff and split this up?

I uploaded a separate patch that handles ashr including vector type handling (D36784).

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

468 ↗

(On Diff #111247)

I change it to uint32_t to be consistent with line 507 (the case for AShr).
Sure, we can commit this separately.
Do we need a review for this?
Do you want to take care of it? or I should just commit it now?

[spatel]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

468 ↗

(On Diff #111247)

Ah, I see the LangRef says we're allowed to go up to 24 bits of width:
http://llvm.org/docs/LangRef.html#integer-type

So I guess it's ok to specify 32-bit here...or just change them all to 'unsigned'? Either way seems fine to me. Feel free to commit separately.

[aaboud]

After committing the other parts, this patch was reduced to handle only the multiply in ComputeNumSignBitsImpl.

[spatel]

Thanks for breaking this up - LGTM.
See inline for a couple of nits.

lib/Analysis/ValueTracking.cpp

2200 ↗

(On Diff #111512)

can at -> can be at

2201–2203 ↗

(On Diff #111512)

It's poor to have variables named 'Tmp'. These can be locals now, so let's give these meaningful names - SignBitsOp0/SignBitsOp1 or something like that.

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
       }
 
     // Sub can have at most one carry bit.  Thus we know that the output
     // is, at worst, one more bit than the inputs.
     Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
     if (Tmp == 1) return 1;  // Early out.
     return std::min(Tmp, Tmp2)-1;
 
+  case Instruction::Mul: {
+    // The output of the Mul can be at most twice the valid bits in the inputs.
+    unsigned SignBitsOp0 = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
+    if (SignBitsOp0 == 1) return 1;  // Early out.
+    unsigned SignBitsOp1 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
+    if (SignBitsOp1 == 1) return 1;
+    unsigned OutValidBits =
+        (TyBits - SignBitsOp0 + 1) + (TyBits - SignBitsOp1 + 1);
+    return OutValidBits > TyBits ? 1 : TyBits - OutValidBits + 1;
+  }
+
   case Instruction::PHI: {
     const PHINode *PN = cast<PHINode>(U);
     unsigned NumIncomingValues = PN->getNumIncomingValues();
     // Don't analyze large in-degree PHIs.
     if (NumIncomingValues > 4) break;
     // Unreachable blocks may have zero-operand PHI nodes.
     if (NumIncomingValues == 0) break;
 

llvm/trunk/test/Transforms/InstCombine/trunc.ll

 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %B = zext i64 %A to i128
   %C = lshr i128 %B, 32
   %D = trunc i128 %C to i32
   ret i32 %D
 }
 
+define i16 @ashr_mul(i8 %X, i8 %Y) {
+; CHECK-LABEL: @ashr_mul(
+; CHECK-NEXT:    [[A:%.*]] = sext i8 %X to i16
+; CHECK-NEXT:    [[B:%.*]] = sext i8 %Y to i16
+; CHECK-NEXT:    [[C:%.*]] = mul nsw i16 [[A]], [[B]]
+; CHECK-NEXT:    [[D:%.*]] = ashr i16 [[C]], 8
+; CHECK-NEXT:    ret i16 [[D]]
+  %A = sext i8 %X to i20
+  %B = sext i8 %Y to i20
+  %C = mul i20 %A, %B
+  %D = ashr i20 %C, 8
+  %E = trunc i20 %D to i16
+  ret i16 %E
+}
+
 define i32 @trunc_ashr(i32 %X) {
 ; CHECK-LABEL: @trunc_ashr(
 ; CHECK-NEXT:    [[B:%.*]] = or i32 [[X:%.*]], -2147483648
 ; CHECK-NEXT:    [[C:%.*]] = ashr i32 [[B]], 8
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = zext i32 %X to i36
   %B = or i36 %A, -2147483648 ; 0xF80000000