<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 12, 2015, at 6:47 AM, Tong Chen <<a href="mailto:chentong@us.ibm.com" class="">chentong@us.ibm.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><font size="2" face="sans-serif" class="">Thanks for all the discussions. Can I draw
following conclusions from them:</font>
<br class=""><font size="2" face="sans-serif" class="">1. We cannot set NoWrap flag for
x+2k only based on the loop induction </font>
<br class=""><font size="2" face="sans-serif" class="">2. If we know x+2k is an inbound array
GEP, the NoWrap flag can be set true according to the C standard</font>
<br class=""></div></blockquote><div><br class=""></div><div>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.</div><div><br class=""></div><div>Adam</div><br class=""><blockquote type="cite" class=""><div class="">
<font size="2" face="sans-serif" class="">Therefore, should I make the following
change in LoopAccessAnalysis.cpp:543:</font>
<br class="">
<br class="">
<br class=""><font size="2" face="sans-serif" class="">original code:</font>
<br class="">
<br class=""><font size="2" face="sans-serif" class=""> bool IsInBoundsGEP = isInBoundsGep(Ptr);</font>
<br class=""><font size="2" face="sans-serif" class=""> bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask);</font>
<br class="">
<br class=""><font size="2" face="sans-serif" class="">to </font>
<br class="">
<br class=""><font size="2" face="sans-serif" class=""> bool IsInBoundsGEP = isInBoundsGep(Ptr);</font>
<br class=""><font size="2" face="sans-serif" class=""> bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask)
|| IsInBoundsGEP;</font>
<br class="">
<br class=""><font size="2" face="sans-serif" class="">Tong</font>
<br class="">
<br class="">
<br class="">
<br class=""><font size="1" color="#5f5f5f" face="sans-serif" class="">From:
</font><font size="1" face="sans-serif" class="">Adam Nemet <<a href="mailto:anemet@apple.com" class="">anemet@apple.com</a>></font>
<br class=""><font size="1" color="#5f5f5f" face="sans-serif" class="">To:
</font><font size="1" face="sans-serif" class="">Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="">sanjoy@playingwithpointers.com</a>></font>
<br class=""><font size="1" color="#5f5f5f" face="sans-serif" class="">Cc:
</font><font size="1" face="sans-serif" class="">Tong Chen/Watson/IBM@IBMUS,
Andrew Trick <<a href="mailto:atrick@apple.com" class="">atrick@apple.com</a>>, LLVM Developers Mailing List <<a href="mailto:llvmdev@cs.uiuc.edu" class="">llvmdev@cs.uiuc.edu</a>>,
Arnold <<a href="mailto:aschwaighofer@apple.com" class="">aschwaighofer@apple.com</a>></font>
<br class=""><font size="1" color="#5f5f5f" face="sans-serif" class="">Date:
</font><font size="1" face="sans-serif" class="">06/11/2015 04:40 PM</font>
<br class=""><font size="1" color="#5f5f5f" face="sans-serif" class="">Subject:
</font><font size="1" face="sans-serif" class="">Re: [LLVMdev]
Question about NoWrap flag for SCEVAddRecExpr</font>
<br class="">
<hr noshade="" class="">
<br class="">
<br class="">
<br class="">
<br class=""><font size="3" class="">On Jun 11, 2015, at 12:48 AM, Sanjoy Das <</font><a href="mailto:sanjoy@playingwithpointers.com" class=""><font size="3" color="blue" class=""><u class="">sanjoy@playingwithpointers.com</u></font></a><font size="3" class="">>
wrote:</font>
<br class="">
<br class=""><font size="1" face="Helvetica" class="">On Thu, Jun 11, 2015 at 12:02 AM, Adam
Nemet <</font><a href="mailto:anemet@apple.com" class=""><font size="1" color="blue" face="Helvetica" class=""><u class="">anemet@apple.com</u></font></a><font size="1" face="Helvetica" class="">>
wrote:</font>
<br class="">
<br class=""><font size="1" face="Helvetica" class="">On Jun 10, 2015, at 11:44 PM, Sanjoy
Das <</font><a href="mailto:sanjoy@playingwithpointers.com" class=""><font size="1" color="blue" face="Helvetica" class=""><u class="">sanjoy@playingwithpointers.com</u></font></a><font size="1" face="Helvetica" class="">>
wrote:<br class="">
</font>
<br class=""><font size="1" face="Helvetica" class="">Base is treated as unsigned so 0xff…ff
+ 1 would be 0x100…00</font>
<br class=""><font size="1" face="Helvetica" class=""><br class="">
This is the part I was missing, thanks for pointing out the FAQ. So<br class="">
the infinitely precise address computed by a GEP is<br class="">
<br class="">
zext(Base) + sext(Idx0) + sext(Idx1) … ?</font>
<br class=""><font size="1" face="Helvetica" class=""><br class="">
Yes, that is the way I read it.<br class="">
</font>
<br class=""><font size="1" face="Helvetica" class="">0x100…00 which would be out of bounds
(sort of).</font>
<br class=""><font size="1" face="Helvetica" class=""><br class="">
Does this mean, for C++ programs of the form,<br class="">
<br class="">
for (int *I = array, *E = array + size; I != E; ++I)<br class="">
...<br class="">
<br class="">
the memory allocator has to guarantee that array cannot span<br class="">
[0xff..fffff-31,0xff..fffff] (both inclusive) with size == 32?</font>
<br class=""><font size="1" face="Helvetica" class=""><br class="">
I think so. Address 0 cannot be dereferenced, so you can’t have
a valid object spanning across address 0.</font>
<br class=""><font size="1" face="Helvetica" class=""><br class="">
I the example I meant to give, [0xff..fffff-31,0xff..fffff] == [-32,<br class="">
-1] does not span address 0 -- address 0 is the address one byte<br class="">
outside the range assigned to `array`.</font>
<br class="">
<br class=""><font size="3" class="">Digging more reveals that the formulation of inbounds
matches the C standard — not too surprisingly.</font>
<br class="">
<br class=""><font size="3" class="">C99 6.5.8/5 Relational operators</font>
<br class="">
<br class=""><font size="3" class="">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.</font>
<br class="">
<br class=""><font size="3" class="">So this works as expected without a potential overflow:</font>
<br class="">
<br class=""><font size="3" class="">for (char *p = array; p < array + sizeof(array); ++p)
…</font>
<br class="">
<br class=""><font size="3" class="">Adam</font>
<br class="">
</div></blockquote></div><br class=""></body></html>