[LLVMdev] Question about NoWrap flag for SCEVAddRecExpr

[Tong Chen]

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>