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 <
alexandre.isoard at gmail.com> 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 <
> alexandre.isoard at gmail.com> 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*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170811/f55f9f2b/attachment.html>
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 <llvm-dev at lists.llvm.org> 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 > <alexandre.isoard at gmail.com> 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 >> <alexandre.isoard at gmail.com> 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 > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >
Hi Sanjoy, On Fri, Aug 11, 2017 at 7:37 PM, Sanjoy Das <sanjoy at google.com> 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! > -- SanjoyBest regard. -- *Alexandre Isoard* -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170815/5b97a83b/attachment.html>