[LLVMdev] sign extensions, SCEVs, and wrap flags

[Preston Briggs]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120919/af4ca8d7/attachment.html>