[llvm-dev] PHI nodes and connected ICMp

[Anastasiya Ruzhanskaya via llvm-dev]

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>