Haidl, Michael via llvm-dev
2017-Sep-14 05:06 UTC
[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> > > > >
Craig Topper via llvm-dev
2017-Sep-14 05:23 UTC
[llvm-dev] How to add optimizations to InstCombine correctly?
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> 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>> 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> > > > > > > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170913/28afd8b2/attachment.html>
Haidl, Michael via llvm-dev
2017-Sep-14 07:12 UTC
[llvm-dev] How to add optimizations to InstCombine correctly?
Hi Craig, until Simon answers, I have implemented the opt in DAGCombiner. How do I test this change to avoid regressions? Cheers, Michael Am 14.09.2017 um 07:23 schrieb Craig Topper:> 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 <mailto:llvm-dev at lists.llvm.org> > <mailto: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> > > > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>> > > > > > > > > > >
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>