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:

Simon Pilgrim via llvm-dev

2017-Sep-16 13:46 UTC

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

This conversation has (partially) moved on to D37896 now, but if possible I was
hoping that we could perform this in DAGCombiner and remove the various target
specific combines that we still have.

At least ARM/AARCH64 and X86 have cases that can hopefully be generalised and
removed, but there will probably be a few legality/perf issues that will occur.

Simon.
 > On 14 Sep 2017, at 06:23, Craig Topper <craig.topper at gmail.com>
wrote:
> 
> Probably in visitMUL in DAGCombiner.cpp to be target independent. Or in
LowerMUL in X86ISelLowering.cpp to be X86 specific.
> 
> Adding Simon. Simon, which were you thinking?
> 
> ~Craig
> 
> On Wed, Sep 13, 2017 at 10:06 PM, Haidl, Michael <michael.haidl at
uni-muenster.de <mailto:michael.haidl at uni-muenster.de>> wrote:
> 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>
> > <mailto: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> <mailto: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> <mailto: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170916/791e22a1/attachment.html>

Haidl, Michael via llvm-dev

2017-Sep-19 11:23 UTC

head link

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

I am currently improving the D37896 to include the suggestions from 
Chad. However, running the lit checks for the x86 backend I observe some 
changes in the generated MC, e.g.:

llvm/test/CodeGen/X86/lea-3.ll:13:10: error: expected string not found 
in input
; CHECK: leal ([[A0]],[[A0]],2), %eax
          ^
<stdin>:10:2: note: scanning from here
  orq %rdi, %rax
  ^
<stdin>:10:2: note: with variable "A0" equal to "%rdi"
  orq %rdi, %rax
  ^
<stdin>:10:2: note: with variable "A0" equal to "%rdi"
  orq %rdi, %rax
  ^
<stdin>:23:2: note: possible intended match here
  leal (,%rdi,4), %eax
  ^
or:

llvm/test/CodeGen/X86/mul-constant-i16.ll:40:13: error: expected string 
not found in input
; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax
             ^
<stdin>:35:2: note: scanning from here
  movzwl 4(%esp), %ecx
  ^
llvm/test/CodeGen/X86/mul-constant-i16.ll:272:13: error: expected string 
not found in input
; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax
             ^
<stdin>:212:2: note: scanning from here
  movzwl 4(%esp), %ecx
  ^

What is the right way to fix this? Is it ok to modify the tests to match 
the new generated pattern?

Cheers,
Michael


Am 16.09.2017 um 15:46 schrieb Simon Pilgrim:> This conversation has (partially) moved on to D37896 now, but if 
> possible I was hoping that we could perform this in DAGCombiner and 
> remove the various target specific combines that we still have.
> 
> At least ARM/AARCH64 and X86 have cases that can hopefully be 
> generalised and removed, but there will probably be a few legality/perf 
> issues that will occur.
> 
> Simon.
> 
>> On 14 Sep 2017, at 06:23, Craig Topper <craig.topper at gmail.com 
>> <mailto:craig.topper at gmail.com>> wrote:
>>
>> Probably in visitMUL in DAGCombiner.cpp to be target independent. Or 
>> in LowerMUL in X86ISelLowering.cpp to be X86 specific.
>>
>> Adding Simon. Simon, which were you thinking?
>>
>> ~Craig
>>
>> On Wed, Sep 13, 2017 at 10:06 PM, Haidl, Michael 
>> <michael.haidl at uni-muenster.de <mailto:michael.haidl at
uni-muenster.de>>
>> wrote:
>>
>>     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>
>>     > <mailto: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>
>>     <mailto: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> <mailto: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
>>
>

Sanjay Patel via llvm-dev

2017-Sep-19 13:58 UTC

head link

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

For the tests that are changing, you should see if those changes are
improvements, regressions, or neutral. This is unfortunately not always
obvious for x86 asm, so feel free to just post those diffs in an updated
version of the patch at D37896.

If the test files have auto-generated assertions (look for this string on
the first line of the test file: "NOTE: Assertions have been autogenerated
by utils/update_llc_test_checks.py"...
and both of these do as of: https://reviews.llvm.org/rL313631 ), then it's
easy to observe the diffs by re-running that script after your code patch
is applied:
$ /path/to/update_llc_test_checks.py --llc=/path/to/local/and/new/llc
lea-3.ll
$ svn diff lea-3.ll

On Tue, Sep 19, 2017 at 5:23 AM, Haidl, Michael via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I am currently improving the D37896 to include the suggestions from
> Chad. However, running the lit checks for the x86 backend I observe some
> changes in the generated MC, e.g.:
>
> llvm/test/CodeGen/X86/lea-3.ll:13:10: error: expected string not found
> in input
> ; CHECK: leal ([[A0]],[[A0]],2), %eax
>           ^
> <stdin>:10:2: note: scanning from here
>   orq %rdi, %rax
>   ^
> <stdin>:10:2: note: with variable "A0" equal to
"%rdi"
>   orq %rdi, %rax
>   ^
> <stdin>:10:2: note: with variable "A0" equal to
"%rdi"
>   orq %rdi, %rax
>   ^
> <stdin>:23:2: note: possible intended match here
>   leal (,%rdi,4), %eax
>   ^
> or:
>
> llvm/test/CodeGen/X86/mul-constant-i16.ll:40:13: error: expected string
> not found in input
> ; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax
>              ^
> <stdin>:35:2: note: scanning from here
>   movzwl 4(%esp), %ecx
>   ^
> llvm/test/CodeGen/X86/mul-constant-i16.ll:272:13: error: expected string
> not found in input
> ; X86-NEXT: movzwl {{[0-9]+}}(%esp), %eax
>              ^
> <stdin>:212:2: note: scanning from here
>   movzwl 4(%esp), %ecx
>   ^
>
> What is the right way to fix this? Is it ok to modify the tests to match
> the new generated pattern?
>
> Cheers,
> Michael
>
>
> Am 16.09.2017 um 15:46 schrieb Simon Pilgrim:
> > This conversation has (partially) moved on to D37896 now, but if
> > possible I was hoping that we could perform this in DAGCombiner and
> > remove the various target specific combines that we still have.
> >
> > At least ARM/AARCH64 and X86 have cases that can hopefully be
> > generalised and removed, but there will probably be a few
legality/perf
> > issues that will occur.
> >
> > Simon.
> >
> >> On 14 Sep 2017, at 06:23, Craig Topper <craig.topper at
gmail.com
> >> <mailto:craig.topper at gmail.com>> wrote:
> >>
> >> Probably in visitMUL in DAGCombiner.cpp to be target independent.
Or
> >> in LowerMUL in X86ISelLowering.cpp to be X86 specific.
> >>
> >> Adding Simon. Simon, which were you thinking?
> >>
> >> ~Craig
> >>
> >> On Wed, Sep 13, 2017 at 10:06 PM, Haidl, Michael
> >> <michael.haidl at uni-muenster.de <mailto:michael.haidl at
uni-muenster.de>>
> >> wrote:
> >>
> >>     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>
> >>     > <mailto: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>
> >>     <mailto: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> <mailto: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
> 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/20170919/61c43cf6/attachment-0001.html>

Reasonably Related Threads

Search for more reasonably related 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?

Reasonably Related Threads