thr3ads.net - llvm dev - [llvm-dev] How to add optimizations to InstCombine correctly? [Sep 2017]

If this information is useful, please help other people find it:
Share via:

Craig Topper via llvm-dev

2017-Sep-13 17:18 UTC

[llvm-dev] How to add optimizations to InstCombine correctly?

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>

Craig Topper via llvm-dev

2017-Sep-13 17:21 UTC

head link

[llvm-dev] How to add optimizations to InstCombine correctly?

And that is less instructions. So from InstCombine's perspective the
multiply is the correct answer. I think this transformation is better left
to codegen where we know whether multiply or shift is truly better.

~Craig

On Wed, Sep 13, 2017 at 10:18 AM, Craig Topper <craig.topper at gmail.com>
wrote:
> 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/70f3bc07/attachment.html>

Haidl, Michael via llvm-dev

2017-Sep-14 05:06 UTC

head link

[llvm-dev] How to add optimizations to InstCombine correctly?

Hi Craig,

thanks for digging into this. So InstCombine is the wrong place for 
fixing PR34474. Can you give me a hint where such an optimization should 
go into CodeGen? I am not really familiar with stuff that happens after 
the MidLevel.

Cheers,
Michael

Am 13.09.2017 um 19:21 schrieb Craig Topper:> And that is less instructions. So from InstCombine's perspective the 
> multiply is the correct answer. I think this transformation is better 
> left to codegen where we know whether multiply or shift is truly better.
> 
> ~Craig
> 
> On Wed, Sep 13, 2017 at 10:18 AM, Craig Topper <craig.topper at
gmail.com
> <mailto:craig.topper at gmail.com>> wrote:
> 
>     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 <mailto: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 <mailto: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 <mailto:llvm-dev at
lists.llvm.org>
>             http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>             <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> 
>

David Menendez via llvm-dev

2017-Sep-15 04:22 UTC

head link

[llvm-dev] How to add optimizations to InstCombine correctly?

The relevant transformation appears to be in SimplifyUsingDistributiveLaws. When
trying to optimize an add, it treats left shifts as multiplies, so (X <<
C) + X becomes (X * (1<<C)) + (X * 1) which factorizes to X * ((1 <<
C) + 1).

In Alive, this would be:

Name: Factor
%y = shl %X, C
%r = add %y, %X
=>
%r = mul %X, (1<<C)+1

The two variations of the proposed optimization are,

Name: Plus
Pre: isPowerOf2(C+1)
%r = mul %X, C
=>
%y = shl %X, log2(C+1)
%r = sub %y, %X

Name: Minus
Pre: isPowerOf2(C-1)
%r = mul %X, C
=>
%y = shl %X, log2(C-1)
%r = add %y, %X

The Alive-Loops tool confirms that these can cause InstCombine to loop.

Specifically, it finds this transformation, which applies Factor and then Plus:

Name: (Factor;Plus)
Pre: isPowerOf2((((1 << C) + 1) - 1))
  %y = shl %X, C
  %r = add %y, %X
=>
  %y1 = shl %X, log2((((1 << C) + 1) - 1))
  %r = add %y1, %X

Note that its precondition is trivial and its source and target code are
identical (aside from renaming). Barring interference from other
transformations, this will cause InstCombine to apply this transformation
endlessly.

There’s a more complete discussion of InstCombine non-termination in the paper
“Termination checking for LLVM peephole optimizations” (ICSE 2016), by Santosh
Nagarakatte and me.

    https://www.cs.rutgers.edu/~sn349/papers/icse2016-alive-loops.pdf

The prototype can be downloaded from

    https://github.com/rutgers-apl/alive-loops

On Sep 13, 2017, at 1:18 PM, Craig Topper via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

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<mailto: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<mailto: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<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7Cdavemm%40cs.rutgers.edu%7C594c390a062c47fb24ca08d4facb7f42%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636409199301439466&sdata=liiyqDyCdRjljCAcZ0NhC3zi%2BvbdzN0E5%2BZ2iY4QYPM%3D&reserved=0>


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7Cdavemm%40cs.rutgers.edu%7C594c390a062c47fb24ca08d4facb7f42%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636409199301439466&sdata=liiyqDyCdRjljCAcZ0NhC3zi%2BvbdzN0E5%2BZ2iY4QYPM%3D&reserved=0

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

Apparently Analagous Threads

Search for more possibly parallel threads

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

[llvm-dev] How to add optimizations to InstCombine correctly?

[llvm-dev] How to add optimizations to InstCombine correctly?

[llvm-dev] How to add optimizations to InstCombine correctly?

[llvm-dev] How to add optimizations to InstCombine correctly?

Apparently Analagous Threads