llvm dev - Aug 2017 - PHI nodes and connected ICMp

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

Yes,
basically my problem is that I want to reduce a bit size of induction
variables as i and maybe some reduction one in a loop.
1) I wanted to use SCEV at first, but then realized that this is a real
waste of time of finding the exact phi node that led to this trip count.
   1.1) Even if I can determine phi, and loop was like for (i = 1000; 5*i >
100; i--) - my trip count is not the range of i.
2) I wanted to track only exiting blocks and values with which phi nodes
are compared there - again there too tiny cases, where i can change
unpredictable inside a cycle and I will not detect it or even the
    example above : I have to track these arithmetic expressions.

By now, I decided to restrict myself with only cycles of type for (i = 0; i
<N ; i++/i--/i+=2/i*=2 ) and so on + the condition that there no more users
of these phi except addition, multiplication and so on and they should be
definitely compared with some value in exiting block.

The indvars2 pass, that was eliminated some years ago, seems to be perfect
solution, but seems, that this is a not good decision as inserting it and
updating llvm and this pass every time accordingly.
So, task is simple: for integers track the range of phi ( llvm's vrp
can't
do this). Also.

for (i = 0; i < N;i++)
 - when I know some bits in N, I can also try to find out the range of i,
what llvm can't do.

That is the problem:)

2017-08-14 5:00 GMT+02:00 Sanjoy Das <sanjoy at playingwithpointers.com>:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170814/1418582c/attachment.html>

Do you think, that the best way - is to totally restrict myself with loop
tipe and give up the idea of trying to get the info from SCEV?

2017-08-14 8:48 GMT+02:00 Anastasiya Ruzhanskaya <
anastasiya.ruzhanskaya at frtk.ru>:
> Yes,
> basically my problem is that I want to reduce a bit size of induction
> variables as i and maybe some reduction one in a loop.
> 1) I wanted to use SCEV at first, but then realized that this is a real
> waste of time of finding the exact phi node that led to this trip count.
>    1.1) Even if I can determine phi, and loop was like for (i = 1000; 5*i
> > 100; i--) - my trip count is not the range of i.
> 2) I wanted to track only exiting blocks and values with which phi nodes
> are compared there - again there too tiny cases, where i can change
> unpredictable inside a cycle and I will not detect it or even the
>     example above : I have to track these arithmetic expressions.
>
> By now, I decided to restrict myself with only cycles of type for (i = 0;
> i <N ; i++/i--/i+=2/i*=2 ) and so on + the condition that there no more
> users of these phi except addition, multiplication and so on and they
> should be definitely compared with some value in exiting block.
>
> The indvars2 pass, that was eliminated some years ago, seems to be perfect
> solution, but seems, that this is a not good decision as inserting it and
> updating llvm and this pass every time accordingly.
> So, task is simple: for integers track the range of phi ( llvm's vrp
can't
> do this). Also.
>
> for (i = 0; i < N;i++)
>  - when I know some bits in N, I can also try to find out the range of i,
> what llvm can't do.
>
> That is the problem:)
>
> 2017-08-14 5:00 GMT+02:00 Sanjoy Das <sanjoy at
playingwithpointers.com>:
>
>> 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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170814/35a04f3a/attachment.html>