llvm dev - Sep 2017 - How to add optimizations to InstCombine correctly?

Hi,

I am working on PR34474 and try to add a new optimization to 
InstCombine. Like in other parts of the visitMul function I add a Shl 
through the IR builder and create a new BinaryOp which I return from 
visitMul. If I understand correctly the new BinaryOp returned from 
visitMul should replace the original Instruction in the Worklist. 
However, I end up in an infinite loop and the Instruction I try to 
replace gets scheduled again and again. What is wrong in my code?

// Replace X * (2^C+/-1) with (X << C) -/+ X
APInt Plus1 = *IVal + 1;
APInt Minus1 = *IVal - 1;
int isPow2 = Plus1.isPowerOf2() ? 1 : Minus1.isPowerOf2() ? -1 : 0;

if (isPow2) {
   APInt &Pow2 = isPow2 > 0 ? Plus1 : Minus1;
   Value *Shl = Builder.CreateShl(Op0, Pow2.logBase2());
   return BinaryOperator::Create(isPow2 > 0 ? BinaryOperator::Sub : 
BinaryOperator::Add, Shl, Op0);
}

Thanks,
Michael

Your code seems fine. InstCombine can infinite loop if some other transform
is reversing your transform. Can you send the whole patch and a test case?

~Craig

On Wed, Sep 13, 2017 at 10:01 AM, Haidl, Michael via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I am working on PR34474 and try to add a new optimization to
> InstCombine. Like in other parts of the visitMul function I add a Shl
> through the IR builder and create a new BinaryOp which I return from
> visitMul. If I understand correctly the new BinaryOp returned from
> visitMul should replace the original Instruction in the Worklist.
> However, I end up in an infinite loop and the Instruction I try to
> replace gets scheduled again and again. What is wrong in my code?
>
> // Replace X * (2^C+/-1) with (X << C) -/+ X
> APInt Plus1 = *IVal + 1;
> APInt Minus1 = *IVal - 1;
> int isPow2 = Plus1.isPowerOf2() ? 1 : Minus1.isPowerOf2() ? -1 : 0;
>
> if (isPow2) {
>    APInt &Pow2 = isPow2 > 0 ? Plus1 : Minus1;
>    Value *Shl = Builder.CreateShl(Op0, Pow2.logBase2());
>    return BinaryOperator::Create(isPow2 > 0 ? BinaryOperator::Sub :
> BinaryOperator::Add, Shl, Op0);
> }
>
> Thanks,
> Michael
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170913/47dfe404/attachment.html>

There is in fact a transform out there somewhere that reverses yours.

define i64 @foo(i64 %a) {
  %b = shl i64 %a, 5
  %c = add i64 %b, %a
  ret i64 %c
}

becomes

define i64 @foo(i64 %a) {

  %c = mul i64 %a, 33

  ret i64 %c

}

~Craig

On Wed, Sep 13, 2017 at 10:11 AM, Craig Topper <craig.topper at gmail.com>
wrote:
> Your code seems fine. InstCombine can infinite loop if some other
> transform is reversing your transform. Can you send the whole patch and a
> test case?
>
> ~Craig
>
> On Wed, Sep 13, 2017 at 10:01 AM, Haidl, Michael via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi,
>>
>> I am working on PR34474 and try to add a new optimization to
>> InstCombine. Like in other parts of the visitMul function I add a Shl
>> through the IR builder and create a new BinaryOp which I return from
>> visitMul. If I understand correctly the new BinaryOp returned from
>> visitMul should replace the original Instruction in the Worklist.
>> However, I end up in an infinite loop and the Instruction I try to
>> replace gets scheduled again and again. What is wrong in my code?
>>
>> // Replace X * (2^C+/-1) with (X << C) -/+ X
>> APInt Plus1 = *IVal + 1;
>> APInt Minus1 = *IVal - 1;
>> int isPow2 = Plus1.isPowerOf2() ? 1 : Minus1.isPowerOf2() ? -1 : 0;
>>
>> if (isPow2) {
>>    APInt &Pow2 = isPow2 > 0 ? Plus1 : Minus1;
>>    Value *Shl = Builder.CreateShl(Op0, Pow2.logBase2());
>>    return BinaryOperator::Create(isPow2 > 0 ? BinaryOperator::Sub :
>> BinaryOperator::Add, Shl, Op0);
>> }
>>
>> Thanks,
>> Michael
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170913/6df7f0de/attachment.html>