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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170129/0251168f/attachment.html>

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/Transforms/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/a37b2069/attachment.html>

The foldPhiOpArgIntoPhi looks like a few special cases of the general
transform (that is applicable as a rewrite rule):

phi(F(1,2,...), F(A,B,...),...) == F(phi(1,A,...), phi(1,B,...), ...)

This follows directly from phis being conditional selects.

in code:


a = b + c
b = d + e
result = phi(a, b)

is equivalent to

tmp1 = phi(b, d)
tmp2 = phi(c, e)
result = tmp1 + tmp2

this is true for any number of operators and operations.


The downside is fixpointing this rule (and even probably the one being used
in foldPhiOpArgIntoPhi) is that it may require exponential applications of
the rule.



On Mon, Jan 30, 2017 at 11:20 AM, Sanjay Patel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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
>>
>>
>
> _______________________________________________
> 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/d4495c6a/attachment.html>

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>