llvm dev - Apr 2015 - [LLVMdev] Instruction combiner multiplication canonicalization

Hi,

I observed below behavior with Instruction combiner (visitMul  Canonicalization)
It tries to convert "(X+C1)*C2" to "X*C2+C1*C2"
While transforming if operation is guaranteed to not overflow it does not
reflect same property to transformed instructions.

Consider following scenarios:
1) If input is ((X+C1)*C2)<nsw>
Then post canonicalization output should be (X*C2+C1*C2) <nsw>

2) If input is (((X+C1)<nsw>)*C2)<nsw>
Then post canonicalization output should be ((X*C2) <nsw>+(C1*C2)
<nsw>) <nsw>

** C1 & C2 are constants.

Current canonicalization transforms to (X*C2+C1*C2) in both scenarios (1 &
2).

To me this looks like a limitation with canonicalization where its missing
guarantee to not overflow property.
Please confirm my understanding.

<File: InstCombineMulDivRem.cpp >
 168 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 268     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
 269     {
 270       Value *X;
 271       Constant *C1;
 272       if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
 273         Value *Mul = Builder->CreateMul(C1, Op1);
 274         // Only go forward with the transform if C1*CI simplifies to a
tidier
 275         // constant.
 276         if (!match(Mul, m_Mul(m_Value(), m_Value())))
 277           return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1),
Mul);
 278       }
 279     }

If my understanding is correct then I like propose below change here:
If input operation to canonicalization is guaranteed to not overflow then
transformed operation should have the same property.
Specifically I like to handle above explained 2 scenarios for 'nsw'
& 'nuw'.

Regards,
Ashutosh

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150415/03bae597/attachment.html>

> Consider following scenarios:
> 1) If input is ((X+C1)*C2)<nsw>
> Then post canonicalization output should be (X*C2+C1*C2) <nsw>
Say X = INT_SMAX, C1 = C2 = 1.

Then (X + C1) = INT_SMIN and INT_SMIN * 1 does not overflow.

But X*C2 = INT_SMAX and C1*C2 = 1 and INT_SMAX + 1 does sign overflow.
> 2) If input is (((X+C1)<nsw>)*C2)<nsw>
> Then post canonicalization output should be ((X*C2) <nsw>+(C1*C2)
<nsw>)
> <nsw>
This is more interesting, let X = INT_SMIN, C1 = 1, C2 -1.

Then the first set of operations don't sign overflow.  But X * C2 INT_SMIN *
-1 will sign overflow

-- Sanjoy

Thanks Sanjoy for detailed explanation. 
I got your point, there is a possibility of overflow. 
Hence we can't do explained transformation.

Regards,
Ashutosh

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Wednesday, April 15, 2015 10:43 PM
To: Nema, Ashutosh
Cc: llvmdev at cs.uiuc.edu; Nick Lewycky
Subject: Re: Instruction combiner multiplication canonicalization
> Consider following scenarios:
> 1) If input is ((X+C1)*C2)<nsw>
> Then post canonicalization output should be (X*C2+C1*C2) <nsw>
Say X = INT_SMAX, C1 = C2 = 1.

Then (X + C1) = INT_SMIN and INT_SMIN * 1 does not overflow.

But X*C2 = INT_SMAX and C1*C2 = 1 and INT_SMAX + 1 does sign overflow.
> 2) If input is (((X+C1)<nsw>)*C2)<nsw>
> Then post canonicalization output should be ((X*C2) <nsw>+(C1*C2)
<nsw>)
> <nsw>
This is more interesting, let X = INT_SMIN, C1 = 1, C2 -1.

Then the first set of operations don't sign overflow.  But X * C2 INT_SMIN *
-1 will sign overflow

-- Sanjoy