llvm dev - Jan 2017 - Folding zext from i1 into PHI nodes with only zwo incoming values.

Hi Sanjay,

unfortunately that patch does not help in my case. Here's the IR that fails
to get fully optimized:

    target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
    target triple = "x86_64-unknown-linux-gnu"

    define fastcc zeroext i1 @testfunc(i8** noalias nocapture readonly
dereferenceable(8)) unnamed_addr {
    entry-block:
      %1 = load i8*, i8** %0, align 8
      %2 = icmp ne i8* %1, null
      %.mux = zext i1 %2 to i8
      br i1 %2, label %bb10, label %bb15

    bb10:                                             ; preds = %entry-block
      %3 = load i8, i8* %1, align 1
      %4 = icmp eq i8 %3, 42
      %.1 = zext i1 %4 to i8
      br label %bb15

    bb15:                                             ; preds %entry-block,
%bb10
      %_0.1 = phi i8 [ %.mux, %entry-block ], [ %.1, %bb10 ]
      %5 = icmp ne i8 %_0.1, 0
      ret i1 %5
    }

The zext instructions should be folded into the phi, and then the new zext
gets removed along with the icmp instruction at the end.

Björn

2017-01-30 20:20 GMT+01:00 Sanjay Patel <spatel at rotateright.com>:
> I'm looking at a similar problem in:
> https://reviews.llvm.org/D28625
>
> Does that patch make any difference on the cases that you are looking at?
>
> Instead of avoiding ShouldChangeType with zext as a special-case opcode,
> it might be better to treat i1 as a special-case type. There's no way
to
> avoid i1 in IR, so we might as well allow transforming to that type?
>
> I'm not sure yet, but there's a chance that change might induce
problems
> (infinite loops) with this:
> https://github.com/llvm-mirror/llvm/blob/master/lib/Transfor
> ms/InstCombine/InstCombineSimplifyDemanded.cpp#L374
>
>
> On Sun, Jan 29, 2017 at 3:09 PM, Björn Steinbrink via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi,
>>
>> AFAICT there are two places where zext instructions may get folded into
>> PHI nodes. One is FoldPHIArgZextsIntoPHI and the other is the more
generic
>> FoldPHIArgOpIntoPHI. Now, the former only handles PHIs with more than 2
>> incoming values, while the latter only handles casts where the source
type
>> is legal.
>>
>> This means that for an PHI node with two incoming i8 values, both
>> resulting from `zext i1 * to i8` instructions, both of these functions
will
>> refuse to actually fold the zext into the PHI, while the same operation
>> would be performed if there were three or more arms. We noticed this
>> because we saw a optimization regression when a function got
specialized
>> and the PHI node only had two incoming values left.
>>
>> Since I'm not fully aware of any implications this might have, I
wonder
>> what is the right way to fix this? Looking at FoldPHIArgZextsIntoPHI,
it
>> seems that making the check for `ShouldChangeType` in
FoldPHIArgOpIntoPHI
>> conditional on the cast instruction not being a zext instruction. Does
that
>> sound right, or am I missing something here?
>>
>> Thanks
>> Björn
>>
>> _______________________________________________
>> 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/20170130/e46eb1c8/attachment.html>

Hi Björn and Daniel,

FoldPHIArgOpIntoPHI() is for unary ops (casts), but it calls
FoldPHIArgBinOpIntoPHI() for binops which takes care of almost everything
else?

My minimal patch idea is to ease the restriction in ShouldChangeType
because i1 is special. I tried the patch below, and it works on the
example...and nothing in 'make check' failed. :)

Index: lib/Transforms/InstCombine/InstructionCombining.cpp
==================================================================---
lib/Transforms/InstCombine/InstructionCombining.cpp    (revision 293485)
+++ lib/Transforms/InstCombine/InstructionCombining.cpp    (working copy)
@@ -88,12 +88,12 @@

 /// Return true if it is desirable to convert an integer computation from a
 /// given bit width to a new bit width.
-/// We don't want to convert from a legal to an illegal type for example
or from
-/// a smaller to a larger illegal type.
+/// We don't want to convert from a legal to an illegal type or from a
smaller
+/// to a larger illegal type. Width of '1' is always treated as a legal
type.
 bool InstCombiner::ShouldChangeType(unsigned FromWidth,
                                     unsigned ToWidth) const {
-  bool FromLegal = DL.isLegalInteger(FromWidth);
-  bool ToLegal = DL.isLegalInteger(ToWidth);
+  bool FromLegal = FromWidth == 1 ? true : DL.isLegalInteger(FromWidth);
+  bool ToLegal = ToWidth == 1 ? true : DL.isLegalInteger(ToWidth);

   // If this is a legal integer from type, and the result would be an
illegal
   // type, don't do the transformation.
@@ -110,7 +110,7 @@

 /// Return true if it is desirable to convert a computation from 'From'
to
'To'.
 /// We don't want to convert from a legal to an illegal type for example
or from
-/// a smaller to a larger illegal type.
+/// a smaller to a larger illegal type. i1 is always treated as a legal
type.
 bool InstCombiner::ShouldChangeType(Type *From, Type *To) const {
   assert(From->isIntegerTy() && To->isIntegerTy());


On Mon, Jan 30, 2017 at 1:22 PM, Björn Steinbrink <bsteinbr at gmail.com>
wrote:
> Hi Sanjay,
>
> unfortunately that patch does not help in my case. Here's the IR that
> fails to get fully optimized:
>
>     target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
>     target triple = "x86_64-unknown-linux-gnu"
>
>     define fastcc zeroext i1 @testfunc(i8** noalias nocapture readonly
> dereferenceable(8)) unnamed_addr {
>     entry-block:
>       %1 = load i8*, i8** %0, align 8
>       %2 = icmp ne i8* %1, null
>       %.mux = zext i1 %2 to i8
>       br i1 %2, label %bb10, label %bb15
>
>     bb10:                                             ; preds >
%entry-block
>       %3 = load i8, i8* %1, align 1
>       %4 = icmp eq i8 %3, 42
>       %.1 = zext i1 %4 to i8
>       br label %bb15
>
>     bb15:                                             ; preds >
%entry-block, %bb10
>       %_0.1 = phi i8 [ %.mux, %entry-block ], [ %.1, %bb10 ]
>       %5 = icmp ne i8 %_0.1, 0
>       ret i1 %5
>     }
>
> The zext instructions should be folded into the phi, and then the new zext
> gets removed along with the icmp instruction at the end.
>
> Björn
>
> 2017-01-30 20:20 GMT+01:00 Sanjay Patel <spatel at rotateright.com>:
>
>> I'm looking at a similar problem in:
>> https://reviews.llvm.org/D28625
>>
>> Does that patch make any difference on the cases that you are looking
at?
>>
>> Instead of avoiding ShouldChangeType with zext as a special-case
opcode,
>> it might be better to treat i1 as a special-case type. There's no
way to
>> avoid i1 in IR, so we might as well allow transforming to that type?
>>
>> I'm not sure yet, but there's a chance that change might induce
problems
>> (infinite loops) with this:
>> https://github.com/llvm-mirror/llvm/blob/master/lib/Transfor
>> ms/InstCombine/InstCombineSimplifyDemanded.cpp#L374
>>
>>
>> On Sun, Jan 29, 2017 at 3:09 PM, Björn Steinbrink via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Hi,
>>>
>>> AFAICT there are two places where zext instructions may get folded
into
>>> PHI nodes. One is FoldPHIArgZextsIntoPHI and the other is the more
generic
>>> FoldPHIArgOpIntoPHI. Now, the former only handles PHIs with more
than 2
>>> incoming values, while the latter only handles casts where the
source type
>>> is legal.
>>>
>>> This means that for an PHI node with two incoming i8 values, both
>>> resulting from `zext i1 * to i8` instructions, both of these
functions will
>>> refuse to actually fold the zext into the PHI, while the same
operation
>>> would be performed if there were three or more arms. We noticed
this
>>> because we saw a optimization regression when a function got
specialized
>>> and the PHI node only had two incoming values left.
>>>
>>> Since I'm not fully aware of any implications this might have,
I wonder
>>> what is the right way to fix this? Looking at
FoldPHIArgZextsIntoPHI, it
>>> seems that making the check for `ShouldChangeType` in
FoldPHIArgOpIntoPHI
>>> conditional on the cast instruction not being a zext instruction.
Does that
>>> sound right, or am I missing something here?
>>>
>>> Thanks
>>> Björn
>>>
>>> _______________________________________________
>>> 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/20170130/1dd36a91/attachment.html>

Hi Sanjay,

2017-01-30 22:22 GMT+01:00 Sanjay Patel <spatel at rotateright.com>:
> My minimal patch idea is to ease the restriction in ShouldChangeType
> because i1 is special. I tried the patch below, and it works on the
> example...and nothing in 'make check' failed. :)
>
Yeah, that would work for me as well, I just wasn't sure about the
implications that has. Simply making FoldPHIArgOpIntoPHI act like
FoldPHIArgZextsIntoPHI seemed like the safer option to me, but I wanted
feedback on it before creating a PR. Do you want to go ahead with that
minimal approach and create a PR yourself?

Björn

> Index: lib/Transforms/InstCombine/InstructionCombining.cpp
> ==================================================================> ---
lib/Transforms/InstCombine/InstructionCombining.cpp    (revision
> 293485)
> +++ lib/Transforms/InstCombine/InstructionCombining.cpp    (working copy)
> @@ -88,12 +88,12 @@
>
>  /// Return true if it is desirable to convert an integer computation from
> a
>  /// given bit width to a new bit width.
> -/// We don't want to convert from a legal to an illegal type for
example
> or from
> -/// a smaller to a larger illegal type.
> +/// We don't want to convert from a legal to an illegal type or from a
> smaller
> +/// to a larger illegal type. Width of '1' is always treated as a
legal
> type.
>  bool InstCombiner::ShouldChangeType(unsigned FromWidth,
>                                      unsigned ToWidth) const {
> -  bool FromLegal = DL.isLegalInteger(FromWidth);
> -  bool ToLegal = DL.isLegalInteger(ToWidth);
> +  bool FromLegal = FromWidth == 1 ? true : DL.isLegalInteger(FromWidth);
> +  bool ToLegal = ToWidth == 1 ? true : DL.isLegalInteger(ToWidth);
>
>    // If this is a legal integer from type, and the result would be an
> illegal
>    // type, don't do the transformation.
> @@ -110,7 +110,7 @@
>
>  /// Return true if it is desirable to convert a computation from
'From'
> to 'To'.
>  /// We don't want to convert from a legal to an illegal type for
example
> or from
> -/// a smaller to a larger illegal type.
> +/// a smaller to a larger illegal type. i1 is always treated as a legal
> type.
>  bool InstCombiner::ShouldChangeType(Type *From, Type *To) const {
>    assert(From->isIntegerTy() && To->isIntegerTy());
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170131/38a0e09a/attachment.html>

On Mon, Jan 30, 2017 at 1:22 PM, Sanjay Patel <spatel at rotateright.com>
wrote:
> Hi Björn and Daniel,
>
> FoldPHIArgOpIntoPHI() is for unary ops (casts), but it calls
> FoldPHIArgBinOpIntoPHI() for binops which takes care of almost everything
> else?
>
FWIW: It seems like it tries to restrict itself to certain cases (single
use) but i can still pretty easily produce a testcase where it would
require an exponential number of applications.

That said, hasn't triggered so far for folks, so \_(ツ)_/¯
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170131/eaf558b2/attachment.html>