[llvm-dev] PHI nodes and connected ICMp

[Anastasiya Ruzhanskaya via llvm-dev]

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>