llvm dev - Aug 2017 - PHI nodes and connected ICMp

Hi!
By only two cases I mean , that in exiting block when computing the
condition related to PHI node I can expect only icmp on one of incoming
values or on phi node itself... I tried to come up with some more complex
examples but I always receive only these two cases, that is why I am asking.

This problem still relates to the problem of all induction, cumulative and
so on variables in loop. SCEV didn't help me, as it doesn't provide me
with
the value against which I am comparing when exiting, and when it cannot
detect loop trip count directly I need this "exiting value". That is
why I
am searching for all compare instructions in exiting blocks that are using
either "phi" itself or "incoming value".

2017-08-10 9:47 GMT+02:00 Sanjoy Das <sanjoy at google.com>:
> It may be helpful to see the incoming value as the incoming value of
> the "next" PHI (i.e. the instance of the PHI node on the next
> iteration).  With that interpretation in mind, you can see that
> comparing the PHI node itself is equivalent to:
>
> do {
>   ...
>   // I is the value that becomes the PHI node
> } while (I++ < N);
>
> and comparing with the incoming value of the PHI is equivalent to:
>
> do {
>   ...
> } while (++I < N);
>
>
> I can't think of any fundamental reason why one would be preferred for
> increasing induction variables and the other would be preferred for
> decreasing induction variables.  I suspect what you're seeing is just
> an artifact of how clang lowers these loops.
>
> I'm also not sure what you mean by "I can have only two
cases".   Loop
> backedge conditions can be arbitrarily complex, if that's what
you're
> asking.
>
> -- Sanjoy
>
>
> On Thu, Aug 10, 2017 at 12:34 AM, Anastasiya Ruzhanskaya via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > Hello,
> > I have one more question about how phi nodes and their corresponding
ICmp
> > instructions are associated. maybe it is simple, but at first I
thought
> that
> > we always compare against one of incoming value. Is it true that  I
can
> have
> > only  two cases:
> > %indvars.iv = phi i64 [ %indvars.iv.next, %1 ], [ 0, %0 ]
> > ...
> > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
> > %exitcond = icmp eq i64 %indvars.iv.next, 32
> >
> >
> > and
> >
> > %i.11 = phi i32 [ %i.11.be, %.backedge ], [ 32, %1 ]
> > ...
> > %13 = icmp sgt i32 %i.11, 3
> > ?
> > In the first one we always have icmp on the incoming value after
> addition,
> > multiplication and so on.
> > In the second - we compare at first against our phi variable and then
> > perform operations. I have noticed, that the first case correspond to
> "up"
> > operations - +=, *= ans do on, the second - to "down" : -=,
/= and so on.
> > But maybe it depends on logic of the cycle too... So, are their two
> cases :
> > comparing in exiting block against PHI variable or against one of
its'
> > incoming value?
> >
> > _______________________________________________
> > 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/20170810/34eae336/attachment-0001.html>

Maybe you, as a person connected with this theme, have some
recommendations? Analyzing SCEV didn't help me, as I am not able to extract
information, that is crucial for me.

2017-08-10 9:55 GMT+02:00 Anastasiya Ruzhanskaya <
anastasiya.ruzhanskaya at frtk.ru>:
> Hi!
> By only two cases I mean , that in exiting block when computing the
> condition related to PHI node I can expect only icmp on one of incoming
> values or on phi node itself... I tried to come up with some more complex
> examples but I always receive only these two cases, that is why I am
asking.
>
> This problem still relates to the problem of all induction, cumulative and
> so on variables in loop. SCEV didn't help me, as it doesn't provide
me with
> the value against which I am comparing when exiting, and when it cannot
> detect loop trip count directly I need this "exiting value". That
is why I
> am searching for all compare instructions in exiting blocks that are using
> either "phi" itself or "incoming value".
>
> 2017-08-10 9:47 GMT+02:00 Sanjoy Das <sanjoy at google.com>:
>
>> It may be helpful to see the incoming value as the incoming value of
>> the "next" PHI (i.e. the instance of the PHI node on the next
>> iteration).  With that interpretation in mind, you can see that
>> comparing the PHI node itself is equivalent to:
>>
>> do {
>>   ...
>>   // I is the value that becomes the PHI node
>> } while (I++ < N);
>>
>> and comparing with the incoming value of the PHI is equivalent to:
>>
>> do {
>>   ...
>> } while (++I < N);
>>
>>
>> I can't think of any fundamental reason why one would be preferred
for
>> increasing induction variables and the other would be preferred for
>> decreasing induction variables.  I suspect what you're seeing is
just
>> an artifact of how clang lowers these loops.
>>
>> I'm also not sure what you mean by "I can have only two
cases".   Loop
>> backedge conditions can be arbitrarily complex, if that's what
you're
>> asking.
>>
>> -- Sanjoy
>>
>>
>> On Thu, Aug 10, 2017 at 12:34 AM, Anastasiya Ruzhanskaya via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> > Hello,
>> > I have one more question about how phi nodes and their
corresponding
>> ICmp
>> > instructions are associated. maybe it is simple, but at first I
thought
>> that
>> > we always compare against one of incoming value. Is it true that 
I can
>> have
>> > only  two cases:
>> > %indvars.iv = phi i64 [ %indvars.iv.next, %1 ], [ 0, %0 ]
>> > ...
>> > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
>> > %exitcond = icmp eq i64 %indvars.iv.next, 32
>> >
>> >
>> > and
>> >
>> > %i.11 = phi i32 [ %i.11.be, %.backedge ], [ 32, %1 ]
>> > ...
>> > %13 = icmp sgt i32 %i.11, 3
>> > ?
>> > In the first one we always have icmp on the incoming value after
>> addition,
>> > multiplication and so on.
>> > In the second - we compare at first against our phi variable and
then
>> > perform operations. I have noticed, that the first case correspond
to
>> "up"
>> > operations - +=, *= ans do on, the second - to "down" :
-=, /= and so
>> on.
>> > But maybe it depends on logic of the cycle too... So, are their
two
>> cases :
>> > comparing in exiting block against PHI variable or against one of
its'
>> > incoming value?
>> >
>> > _______________________________________________
>> > 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/20170810/87946d0c/attachment.html>

Also, even when not using canonical induction variables, and extracting max
backedge taken count, then I can't determine to which phi instruction ( if
I have many of them in cycle) this backedge taken count relates to (as Loop
can only provide me with canonical variable and SCEV gives a description of
PHI). Or maybe again I didn't find an appropriate method to extract this
phi node, which gives this count.

2017-08-10 10:00 GMT+02:00 Anastasiya Ruzhanskaya <
anastasiya.ruzhanskaya at frtk.ru>:
> Maybe you, as a person connected with this theme, have some
> recommendations? Analyzing SCEV didn't help me, as I am not able to
extract
> information, that is crucial for me.
>
> 2017-08-10 9:55 GMT+02:00 Anastasiya Ruzhanskaya <
> anastasiya.ruzhanskaya at frtk.ru>:
>
>> Hi!
>> By only two cases I mean , that in exiting block when computing the
>> condition related to PHI node I can expect only icmp on one of incoming
>> values or on phi node itself... I tried to come up with some more
complex
>> examples but I always receive only these two cases, that is why I am
asking.
>>
>> This problem still relates to the problem of all induction, cumulative
>> and so on variables in loop. SCEV didn't help me, as it doesn't
provide me
>> with the value against which I am comparing when exiting, and when it
>> cannot detect loop trip count directly I need this "exiting
value". That is
>> why I am searching for all compare instructions in exiting blocks that
are
>> using either "phi" itself or "incoming value".
>>
>> 2017-08-10 9:47 GMT+02:00 Sanjoy Das <sanjoy at google.com>:
>>
>>> It may be helpful to see the incoming value as the incoming value
of
>>> the "next" PHI (i.e. the instance of the PHI node on the
next
>>> iteration).  With that interpretation in mind, you can see that
>>> comparing the PHI node itself is equivalent to:
>>>
>>> do {
>>>   ...
>>>   // I is the value that becomes the PHI node
>>> } while (I++ < N);
>>>
>>> and comparing with the incoming value of the PHI is equivalent to:
>>>
>>> do {
>>>   ...
>>> } while (++I < N);
>>>
>>>
>>> I can't think of any fundamental reason why one would be
preferred for
>>> increasing induction variables and the other would be preferred for
>>> decreasing induction variables.  I suspect what you're seeing
is just
>>> an artifact of how clang lowers these loops.
>>>
>>> I'm also not sure what you mean by "I can have only two
cases".   Loop
>>> backedge conditions can be arbitrarily complex, if that's what
you're
>>> asking.
>>>
>>> -- Sanjoy
>>>
>>>
>>> On Thu, Aug 10, 2017 at 12:34 AM, Anastasiya Ruzhanskaya via
llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>> > Hello,
>>> > I have one more question about how phi nodes and their
corresponding
>>> ICmp
>>> > instructions are associated. maybe it is simple, but at first
I
>>> thought that
>>> > we always compare against one of incoming value. Is it true
that  I
>>> can have
>>> > only  two cases:
>>> > %indvars.iv = phi i64 [ %indvars.iv.next, %1 ], [ 0, %0 ]
>>> > ...
>>> > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
>>> > %exitcond = icmp eq i64 %indvars.iv.next, 32
>>> >
>>> >
>>> > and
>>> >
>>> > %i.11 = phi i32 [ %i.11.be, %.backedge ], [ 32, %1 ]
>>> > ...
>>> > %13 = icmp sgt i32 %i.11, 3
>>> > ?
>>> > In the first one we always have icmp on the incoming value
after
>>> addition,
>>> > multiplication and so on.
>>> > In the second - we compare at first against our phi variable
and then
>>> > perform operations. I have noticed, that the first case
correspond to
>>> "up"
>>> > operations - +=, *= ans do on, the second - to
"down" : -=, /= and so
>>> on.
>>> > But maybe it depends on logic of the cycle too... So, are
their two
>>> cases :
>>> > comparing in exiting block against PHI variable or against one
of its'
>>> > incoming value?
>>> >
>>> > _______________________________________________
>>> > 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/20170810/a6ae6f34/attachment.html>

Hi Anastasiya,

If you're looking for the exit value of a PHI node, please take a look
at what IndVarSimplify does here:
https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/IndVarSimplify.cpp#L516

On Thu, Aug 10, 2017 at 12:55 AM, Anastasiya Ruzhanskaya
<anastasiya.ruzhanskaya at frtk.ru> wrote:
> By only two cases I mean , that in exiting block when computing the
> condition related to PHI node I can expect only icmp on one of incoming
> values or on phi node itself... I tried to come up with some more complex
> examples but I always receive only these two cases, that is why I am
asking.
So you could have cases like this: https://godbolt.org/g/j4zcWy

-- Sanjoy

Thank you for your answer! I tested your example, yes, perhaps I should
preserve some kind of tree to parse this start and end expressions for
induction variable... I was surprised, that SCEV cannot compute the
tripcount here. I thought, that all linear and maybe expressions with
multiplication are suitable for analysis.

2017-08-10 19:30 GMT+02:00 Sanjoy Das <sanjoy at google.com>:
> Hi Anastasiya,
>
> If you're looking for the exit value of a PHI node, please take a look
> at what IndVarSimplify does here:
> https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/
> IndVarSimplify.cpp#L516
>
> On Thu, Aug 10, 2017 at 12:55 AM, Anastasiya Ruzhanskaya
> <anastasiya.ruzhanskaya at frtk.ru> wrote:
> > By only two cases I mean , that in exiting block when computing the
> > condition related to PHI node I can expect only icmp on one of
incoming
> > values or on phi node itself... I tried to come up with some more
complex
> > examples but I always receive only these two cases, that is why I am
> asking.
>
> So you could have cases like this: https://godbolt.org/g/j4zcWy
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170811/f11177de/attachment.html>