[llvm-dev] Are SCEV normal form?

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

[llvm-dev] Are SCEV normal form?

George Karpenkov via llvm-dev
Hello,

I assumed SCEV purpose was to be a normal form, but then I wondered which one of those is the normal form:

(zext i16 (trunc i32 %a to i16) to i32)

vs

(-((%a /u 65536) *u 65536) + %a)


The first one is nice for interval analysis, and known bit analysis.
The second one is nice when plugged into gep of 2d arrays.

--
Alexandre Isoard

_______________________________________________
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] Are SCEV normal form?

George Karpenkov via llvm-dev
Hello again,

On that subject, I have the following SCEV:

(zext i16 (trunc i32 %a to i16) to i32) + ((%a /u 65536) *u 65536)

That I would like to normalize into:

%a

I am not sure where is the most natural spot in which to do that?
Also, this pattern is much more general. The idea is that I want to coalesce bit ranges that have been extracted and put back together.

Should I detect patterns, or look for a more generic strategy? Do you have input on that?

On Tue, Jul 25, 2017 at 9:21 PM, Alexandre Isoard <[hidden email]> wrote:
Hello,

I assumed SCEV purpose was to be a normal form, but then I wondered which one of those is the normal form:

(zext i16 (trunc i32 %a to i16) to i32)

vs

(-((%a /u 65536) *u 65536) + %a)


The first one is nice for interval analysis, and known bit analysis.
The second one is nice when plugged into gep of 2d arrays.

--
Alexandre Isoard



--
Alexandre Isoard

_______________________________________________
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] Are SCEV normal form?

George Karpenkov via llvm-dev
Note that there is a slight difficulty due to the fact that we "sink" the trunc:

(zext i16 {0,+,1}<%bb> to i32) + (65536 * ({0,+,1}<nuw><%bb> /u 65536)

Here the recurrence lost it's <nuw> and got reduced to a i16 (on the left), but not on the right.

But we can prove:
- that (zext i16 {0,+,1}<%bb> to i32) has the same 16 LSB than (i32 {0,+,1}<nuw><%bb>)
- that (65536 * ({0,+,1}<nuw><%bb> /u 65536) has the same 16 MSB than (i32 {0,+,1}<nuw><%bb>)
And therefore conclude that we can simplify it to (i32 {0,+,1}<nuw><%bb>).

The difficulty is to come up with the (i32 {0,+,1}<nuw><%bb>) in the first place.

On Fri, Aug 11, 2017 at 5:57 PM, Alexandre Isoard <[hidden email]> wrote:
Hello again,

On that subject, I have the following SCEV:

(zext i16 (trunc i32 %a to i16) to i32) + ((%a /u 65536) *u 65536)

That I would like to normalize into:

%a

I am not sure where is the most natural spot in which to do that?
Also, this pattern is much more general. The idea is that I want to coalesce bit ranges that have been extracted and put back together.

Should I detect patterns, or look for a more generic strategy? Do you have input on that?

On Tue, Jul 25, 2017 at 9:21 PM, Alexandre Isoard <[hidden email]> wrote:
Hello,

I assumed SCEV purpose was to be a normal form, but then I wondered which one of those is the normal form:

(zext i16 (trunc i32 %a to i16) to i32)

vs

(-((%a /u 65536) *u 65536) + %a)


The first one is nice for interval analysis, and known bit analysis.
The second one is nice when plugged into gep of 2d arrays.

--
Alexandre Isoard



--
Alexandre Isoard



--
Alexandre Isoard

_______________________________________________
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] Are SCEV normal form?

George Karpenkov via llvm-dev
Hi Alexandre,

Right now there is no phase where we simplify or canonicalize SCEV
expressions after their creation -- the shape of a SCEV expression is
expected to be canonical when you create it.  For this reason the
right place to do the simplification you suggest is during the
creation of the SCEV expression itself (createSCEV).

If there is a general strategy here that isn't too complex, I'd
suggest going with that; otherwise detecting some simple patterns that
you care about is fine too.

As far as your initial question is concerned (which I am sorry for not
replying too -- it looks like it slipped through the cracks somehow):
if there isn't a universal good reason to pick one over the other, I
think we should just pick one as the normal form as per our
convenience and teach downstream users to how to effectively use it.
For instance, if we choose the zext-trunc version as the canonical
form then we should teach the 2D array GEP generation logic (not sure
if there is such a thing in LLVM today?) that is equivalent to the
udiv-mul form, perhaps by helpers on ScalarEvolution itself.

Thanks!
-- Sanjoy


On Fri, Aug 11, 2017 at 10:17 AM, Alexandre Isoard via llvm-dev
<[hidden email]> wrote:

> Note that there is a slight difficulty due to the fact that we "sink" the
> trunc:
>
> (zext i16 {0,+,1}<%bb> to i32) + (65536 * ({0,+,1}<nuw><%bb> /u 65536)
>
> Here the recurrence lost it's <nuw> and got reduced to a i16 (on the left),
> but not on the right.
>
> But we can prove:
> - that (zext i16 {0,+,1}<%bb> to i32) has the same 16 LSB than (i32
> {0,+,1}<nuw><%bb>)
> - that (65536 * ({0,+,1}<nuw><%bb> /u 65536) has the same 16 MSB than (i32
> {0,+,1}<nuw><%bb>)
> And therefore conclude that we can simplify it to (i32 {0,+,1}<nuw><%bb>).
>
> The difficulty is to come up with the (i32 {0,+,1}<nuw><%bb>) in the first
> place.
>
> On Fri, Aug 11, 2017 at 5:57 PM, Alexandre Isoard
> <[hidden email]> wrote:
>>
>> Hello again,
>>
>> On that subject, I have the following SCEV:
>>
>> (zext i16 (trunc i32 %a to i16) to i32) + ((%a /u 65536) *u 65536)
>>
>> That I would like to normalize into:
>>
>> %a
>>
>> I am not sure where is the most natural spot in which to do that?
>> Also, this pattern is much more general. The idea is that I want to
>> coalesce bit ranges that have been extracted and put back together.
>>
>> Should I detect patterns, or look for a more generic strategy? Do you have
>> input on that?
>>
>> On Tue, Jul 25, 2017 at 9:21 PM, Alexandre Isoard
>> <[hidden email]> wrote:
>>>
>>> Hello,
>>>
>>> I assumed SCEV purpose was to be a normal form, but then I wondered which
>>> one of those is the normal form:
>>>
>>> (zext i16 (trunc i32 %a to i16) to i32)
>>>
>>> vs
>>>
>>> (-((%a /u 65536) *u 65536) + %a)
>>>
>>>
>>> The first one is nice for interval analysis, and known bit analysis.
>>> The second one is nice when plugged into gep of 2d arrays.
>>>
>>> --
>>> Alexandre Isoard
>>
>>
>>
>>
>> --
>> Alexandre Isoard
>
>
>
>
> --
> Alexandre Isoard
>
> _______________________________________________
> 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] Are SCEV normal form?

George Karpenkov via llvm-dev
Hi Sanjoy,

On Fri, Aug 11, 2017 at 7:37 PM, Sanjoy Das <[hidden email]> wrote:
Hi Alexandre,

Right now there is no phase where we simplify or canonicalize SCEV
expressions after their creation -- the shape of a SCEV expression is
expected to be canonical when you create it.  For this reason the
right place to do the simplification you suggest is during the
creation of the SCEV expression itself (createSCEV).

I guess I will have to add a new case in getAddExpr. (which is already huge!)
 
If there is a general strategy here that isn't too complex, I'd
suggest going with that; otherwise detecting some simple patterns that
you care about is fine too.

The idea is to simplify:

    zext(trunc(%a))+shl(lshr(%a))

Into `%a`.

The problem is that sometime trunc has been sunk into %a, and shl/lshr are encoded as UDiv/Mul.
This is a little bit difficult to match the general case. Also, this can be generalized in splitting %a into three, or more parts.
 
As far as your initial question is concerned (which I am sorry for not
replying too -- it looks like it slipped through the cracks somehow):
if there isn't a universal good reason to pick one over the other, I
think we should just pick one as the normal form as per our
convenience and teach downstream users to how to effectively use it.

Here there is a good reason to pick the zext-trunc version as the range/known-bits analysis are exact.
While the subtraction make those over-estimated.
I am wondering if I should not generate a zext-trunc-sub-mul-div when it is not a power-of-two to bound the result of the subtraction...
 
For instance, if we choose the zext-trunc version as the canonical
form then we should teach the 2D array GEP generation logic (not sure
if there is such a thing in LLVM today?) that is equivalent to the
udiv-mul form, perhaps by helpers on ScalarEvolution itself.

If I fold the add expression the GEP should end up all right by itself.
 
Thanks!
-- Sanjoy

Best regard. 

--
Alexandre Isoard

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