> On Jun 11, 2015, at 12:48 AM, Sanjoy Das <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> 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/20150611/948f846a/attachment.html>
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 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> wrote: On Thu, Jun 11, 2015 at 12:02 AM, Adam Nemet <anemet at apple.com> wrote: On Jun 10, 2015, at 11:44 PM, Sanjoy Das <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/e30dc5bd/attachment.html>
> 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 standardNo, 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>