llvm dev - Aug 2017 - PHI nodes and connected ICMp

To continue this topic:
sometimes SCEV's behavior is rather controversial : for loops with i
changing as i \=2 for example, he can't figure what the type of expressions
is, but surprisingly can determine max trip count. Shouldn't it be able to
detect or not detect  these parameters at the same time?

2017-08-11 15:56 GMT+02:00 Anastasiya Ruzhanskaya <
anastasiya.ruzhanskaya at frtk.ru>:
> Sorry,  I just saw this enumeration with SCEV types - all operations
> should be possible then...
>
> 2017-08-11 15:55 GMT+02:00 Anastasiya Ruzhanskaya <
> anastasiya.ruzhanskaya at frtk.ru>:
>
>> 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/Transfor
>>> ms/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/20170813/8323a859/attachment.html>

And still, aren't there any possibilities to find that phi node, that led
SCEV to compute max trip count?

2017-08-13 14:55 GMT+02:00 Anastasiya Ruzhanskaya <
anastasiya.ruzhanskaya at frtk.ru>:
> To continue this topic:
> sometimes SCEV's behavior is rather controversial : for loops with i
> changing as i \=2 for example, he can't figure what the type of
expressions
> is, but surprisingly can determine max trip count. Shouldn't it be able
to
> detect or not detect  these parameters at the same time?
>
> 2017-08-11 15:56 GMT+02:00 Anastasiya Ruzhanskaya <
> anastasiya.ruzhanskaya at frtk.ru>:
>
>> Sorry,  I just saw this enumeration with SCEV types - all operations
>> should be possible then...
>>
>> 2017-08-11 15:55 GMT+02:00 Anastasiya Ruzhanskaya <
>> anastasiya.ruzhanskaya at frtk.ru>:
>>
>>> 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/Transfor
>>>> ms/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/20170813/a6740b1f/attachment.html>

Hi,

On Sun, Aug 13, 2017 at 5:58 AM, Anastasiya Ruzhanskaya via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> And still, aren't there any possibilities to find that phi node, that
led
> SCEV to compute max trip count?
So there is no good  answer to your question since in most cases SCEV
does not directly look at PHI nodes (or expressions based off of the
PHI node).  It converts PHI nodes and related expressions into SCEV
expressions and computes trip counts off of these SCEV expressions;
and there is no reliable way to map a SCEV expression back into a PHI
node (though it may be possible in some cases).

However this is sounding like an XY problem (http://xyproblem.info/)
:)  Do you mind taking a step back and giving us some information
about the broader picture?
> 2017-08-13 14:55 GMT+02:00 Anastasiya Ruzhanskaya
>> To continue this topic:
>> sometimes SCEV's behavior is rather controversial : for loops with
i
>> changing as i \=2 for example, he can't figure what the type of
expressions
>> is, but surprisingly can determine max trip count. Shouldn't it be
able to
>> detect or not detect  these parameters at the same time?
SCEV expressions cannot represent recurrences that are are divided by
some amount every iteration.  And while not being able to represent
induction variables as SCEV expressions does make it more difficult to
compute trip counts, SCEV has some other patterns it tries to
recognize even in cases where the relevant expressions could not be
mapped to neat SCEV add recurrences.  Another example: SCEV can
compute the trip counts for strlen-like loops:
https://godbolt.org/g/hWtEWm

-- Sanjoy