[LLVMdev] Question about NoWrap flag for SCEVAddRecExpr

[Adam Nemet]

> On Jun 12, 2015, at 6:47 AM, Tong Chen <chentong at us.ibm.com> wrote:
> 
> Thanks for all the discussions. Can I draw following conclusions from them: 
> 1.  We cannot set NoWrap flag for x+2k only based on the loop induction 
> 2. If we know x+2k is an inbound array GEP, the NoWrap flag can be set true according to the C standard 

No, but we can further analyze the SCEVs to conclude something more meaningful than Dependence::Unknown in certain special cases.  I am actually looking at this based on the examples I included in my reply to Arnold.  Should have something soon.

Adam

> Therefore, should I make the following change in LoopAccessAnalysis.cpp:543: 
> 
> 
> original code: 
> 
>    bool IsInBoundsGEP = isInBoundsGep(Ptr); 
>   bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask); 
> 
> to 
> 
>    bool IsInBoundsGEP = isInBoundsGep(Ptr); 
>   bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask) || IsInBoundsGEP; 
> 
> Tong 
> 
> 
> 
> From:        Adam Nemet <anemet at apple.com> 
> To:        Sanjoy Das <sanjoy at playingwithpointers.com> 
> Cc:        Tong Chen/Watson/IBM at IBMUS, Andrew Trick <atrick at apple.com>, LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>, Arnold <aschwaighofer at apple.com> 
> Date:        06/11/2015 04:40 PM 
> Subject:        Re: [LLVMdev] Question about NoWrap flag for SCEVAddRecExpr 
> 
> 
> 
> 
> On Jun 11, 2015, at 12:48 AM, Sanjoy Das <sanjoy at playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>> wrote: 
> 
> On Thu, Jun 11, 2015 at 12:02 AM, Adam Nemet <anemet at apple.com <mailto:anemet at apple.com>> wrote: 
> 
> On Jun 10, 2015, at 11:44 PM, Sanjoy Das <sanjoy at playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>> wrote:
> 
> Base is treated as unsigned so 0xff…ff + 1 would be 0x100…00 
> 
> This is the part I was missing, thanks for pointing out the FAQ.  So
> the infinitely precise address computed by a GEP is
> 
> zext(Base) + sext(Idx0) + sext(Idx1) … ? 
> 
> Yes, that is the way I read it.
> 
> 0x100…00 which would be out of bounds (sort of). 
> 
> Does this mean, for C++ programs of the form,
> 
> for (int *I = array, *E = array + size; I != E; ++I)
> ...
> 
> the memory allocator has to guarantee that array cannot span
> [0xff..fffff-31,0xff..fffff] (both inclusive) with size == 32? 
> 
> I think so.  Address 0 cannot be dereferenced, so you can’t have a valid object spanning across address 0. 
> 
> I the example I meant to give, [0xff..fffff-31,0xff..fffff] == [-32,
> -1] does not span address 0 -- address 0 is the address one byte
> outside the range assigned to `array`. 
> 
> Digging more reveals that the formulation of inbounds matches the C standard — not too surprisingly. 
> 
> C99 6.5.8/5 Relational operators 
> 
> If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined. 
> 
> So this works as expected without a potential overflow: 
> 
> for (char *p = array; p < array + sizeof(array); ++p) … 
> 
> Adam 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150612/69ec3953/attachment.html>