[llvm-dev] PHI nodes and connected ICMp

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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 <[hidden email]>:
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
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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 <[hidden email]>:
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 <[hidden email]>:
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
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
In reply to this post by George Karpenkov via llvm-dev
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
<[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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
<[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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 <[hidden email]>:
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
<[hidden email]> 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



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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 <[hidden email]>:
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 <[hidden email]>:
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
<[hidden email]> 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




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
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 <[hidden email]>:
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 <[hidden email]>:
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 <[hidden email]>:
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 <[hidden email]>:
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
<[hidden email]> 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





_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov via llvm-dev
Hi,

On Sun, Aug 13, 2017 at 5:58 AM, Anastasiya Ruzhanskaya via llvm-dev
<[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov 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 <[hidden email]>:
Hi,

On Sun, Aug 13, 2017 at 5:58 AM, Anastasiya Ruzhanskaya via llvm-dev
<[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] PHI nodes and connected ICMp

George Karpenkov 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 <[hidden email]>:
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 <[hidden email]>:
Hi,

On Sun, Aug 13, 2017 at 5:58 AM, Anastasiya Ruzhanskaya via llvm-dev
<[hidden email]> 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



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Loading...