[LLVMdev] sign extensions, SCEVs, and wrap flags

[Preston Briggs]

On Wed, Sep 19, 2012 at 9:29 PM, Preston Briggs <preston.briggs at gmail.com>wrote:

> On Wed, Sep 19, 2012 at 6:30 PM, Andrew Trick <atrick at apple.com> wrote:
>
>>
>> On Sep 19, 2012, at 2:18 PM, Preston Briggs <preston.briggs at gmail.com>
>> wrote:
>>
>> On Tue, Sep 18, 2012 at 10:59 PM, Andrew Trick <atrick at apple.com> wrote:
>>
>>>
>>> On Sep 18, 2012, at 8:21 PM, Preston Briggs <preston.briggs at gmail.com>
>>> wrote:
>>>
>>> Given the following SCEV,
>>>
>>> *(sext i32 {2,+,1}<nw><%for.body> to i64)*
>>>
>>>
>>> from the following C source,
>>>
>>> *void strong3(int *A, int *B, int n) {*
>>> *  for (int i = 0; i < n; i++) {*
>>> *    A[i + 2] = i;*
>>> *    ...*
>>> *  }*
>>> *}*
>>>
>>>
>>> Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as
>>>
>>> *{2,+,1}<nw><%for.body>*
>>>
>>>
>>> If I can, why isn't the SCEV package simplifying things for me?
>>>
>>>
>>> The short answer is that SCEV is terrible at preserving NSW flags. I
>>> personally don't believe they belong in SCEV but the merits of making any
>>> design change here are dubious.
>>>
>>> To understand one example of SCEV dropping NSW, see createSCEV for
>>> Instruction::Add. Synopsis: your add is not a "basic induction variable" so
>>> its NSW flag does not bound the number of loop iterations. We only know
>>> that the add's original IR users expect NSW. There could be other IR adds
>>> with the same expression, but without the NSW flag. SCEV doesn't know
>>> anything about acyclic control flow or IR users, so it must drop the flags.
>>>
>>> I would try hard not to rely on NSW flags on arbitrary SCEVs. I would
>>> first find the phi or basic induction variable before checking the
>>> recurrence's NSW flag. Or, better yet, only rely on SCEVAddRec's NW (no
>>> self-wrap flag) rather than NSW. Notice that the NW is preserved in your
>>> add's recurrence!
>>>
>>> -Andy
>>>
>>>
>> OK.  I think...
>> Basically, I'm trying to understand how two subscripts relate to one
>> another. When I find sign and zero extensions, life gets confusing. In an
>> effort to keep life simple, I begin by walking though the expressions,
>> trying to eliminate extensions where it won't change the answer. For
>> example, I think
>>
>> *(sext i32 {2,+,1}<nw><%for.body> to i64)
>> *
>>
>> is the same as
>>
>> *{2,+,1}<nw><%for.body>*
>>
>> right?
>>
>> Mechanically, when I see an sext over an addrec and the addrec has the NW
>> flag, then I can rewrite is as an addrec<nw> with the base and step
>> extended. In this case, the base and step are constants, which are
>> particularly easy.
>>
>> On the other hand, if the addrec is missing the NW flag, I'd be making a
>> mistake.
>>
>> In a similar vein, it seems plausible that I can rewrite a sign-extend
>> over an add (or multiply), as long as the add (multiply) has the NSW flag,
>> right? Same for zero-extend, over add with NUW flag.
>>
>>
>> Sorry, I probably led you astray. No-self-wrap is useful for determining
>> trip count, but does not mean that sign/zero extension can be hoisted.
>>
>> But if you run your analysis after -indvars, the sign-extension should be
>> removed if possible. The algorithm walks the derived induction variables
>> specifically looking for add nsw/nuw and replacing only those IR users with
>> a wide induction variable. See GetExtendedOperandRecurrence.
>>
>> If you have a situation where the sign extends cannot removed, then you
>> may need your own IR-level analysis to determine whether you can ignore
>> them. Otherwise, you may run into trouble operating on SCEVs that contain
>> sext/zext/truncs. Are all your array indices uniformly sign-extended? I
>> don't know if this is a good idea, but why can't you consider the sext
>> operand the array index rather than the gep operand? If you prove that the
>> narrow indices are disjoint, then the extended indices must be disjoint.
>> SCEV operations should work fine on the narrow indices which shouldn't have
>> any impure type casting operations.
>>
>> This can all be avoided by limiting your optimization to code that uses
>> pointer-size loop counters!
>>
>> -Andy
>>
>
> The array indices are out of my control; depends on the code people
> write. If they'd use long ints for everything, life would be good; but ints
> happen.
>
> I'll play with -indvars.
>
> Thanks,
> Preston
>

Ah, -indvars works a treat.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120919/7be6108c/attachment.html>