<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></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 Dec 1, 2014, at 3:22 PM, Philip Reames <<a href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<br class="">
<div class="moz-cite-prefix">On 12/01/2014 02:42 PM, Andrew Trick
wrote:<br class="">
</div>
<blockquote cite="mid:A1A1CB5D-299D-4D03-BA15-DD1FA70A6B74@apple.com" type="cite" class="">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252" class="">
<br class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On Dec 1, 2014, at 2:21 PM, Philip Reames <<a moz-do-not-send="true" href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class=""> <br class="">
<div class="moz-cite-prefix">On 12/01/2014 11:14 AM,
Andrew Trick wrote:<br class="">
</div>
<blockquote cite="mid:3C814DCF-2BCF-413A-906F-560B84918529@apple.com" type="cite" class="">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252" class="">
<br class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On Oct 21, 2014, at 4:03 PM, Philip
Reames <<a moz-do-not-send="true" href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class=""><span style="font-family: Helvetica;
font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal;
letter-spacing: normal; line-height: normal;
orphans: auto; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
widows: auto; word-spacing: 0px;
-webkit-text-stroke-width: 0px; float: none;
display: inline !important;" class="">Sanjoy
made a good point. We don't actually need a new
variant of "invariant.start". Simply using an
invariant.start with no uses gives us a notion
of an invariant region with no end. (Since the
result doesn't escape, there can be no end
hidden inside a function call.) This seems
like a simple notion to exploit and is strict
step forward from where we are, without a new
intrinsic.</span></div>
</blockquote>
</div>
<br class="">
<div class="">
<div class="">I'm coming back to this because it is a
sticking point for me in all of the proposals that
were floated informally on the commits list. I would
really like this to work, but can't prove that it's
safe.</div>
</div>
</blockquote>
As I said in the other thread, !invariant.load and
llvm.invariant.* are not the same. This thread is
discussing the later, not the former. The other thread is
discussing the former, but not the later. <br class="">
<blockquote cite="mid:3C814DCF-2BCF-413A-906F-560B84918529@apple.com" type="cite" class="">
<div class="">
<div class=""><br class="">
</div>
<div class="">Given:</div>
<div class=""><br class="">
</div>
<div class="">%a = newArray()</div>
<div class="">%pLen = gep(%a, <length offset>)</div>
<div class="">invariant.start(<size>, %pLen)</div>
<div class="">%len = load %pLen</div>
<div class=""><br class="">
</div>
<div class="">%o = foo() // may deallocate %a</div>
<div class="">store %something</div>
<div class="">load %o</div>
<div class=""><br class="">
</div>
<div class="">I want to claim that the LLVM optimizer
cannot do the following (but don't have a complete
line of reasoning yet):</div>
<div class=""><br class="">
</div>
<div class="">%a = newArray()</div>
<div class="">%pLen = gep(%a, <length offset>)</div>
<div class="">invariant.start(<size>, %pLen)</div>
<div class="">%len = load %pLen</div>
<div class=""><br class="">
</div>
<div class="">%o = foo() // may deallocate %a</div>
<div class="">if ptrtoint(%o) == ptrtoint(%pLen)</div>
<div class=""> load %pLen</div>
<div class=""> store %something // Oops... this might
alias</div>
<div class="">else</div>
<div class=""> store %something</div>
<div class=""> load %o</div>
</div>
</blockquote>
Just to make sure we're on the same page, it *would* be
legal for the optimizer to construct:<br class="">
<div class="">%a = newArray()</div>
<div class="">%pLen = gep(%a, <length offset>)</div>
<div class="">invariant.start(<size>, %pLen)</div>
<div class="">%len = load %pLen</div>
<div class=""><br class="">
</div>
<div class="">%o = foo() // may deallocate %a</div>
<div class="">if ptrtoint(%o) == ptrtoint(%pLen)</div>
<div class=""> store %something // Oops... this might
alias<br class="">
load %pLen <--- This is now after the store<br class="">
</div>
<div class="">else</div>
<div class=""> store %something</div>
<div class=""> load %o<br class="">
<br class="">
Are we in agreement here? <br class="">
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
It’s fine in the sense that memory access has not been
reordered… yet.</div>
</blockquote>
I think I've actually convinced myself my example is not okay, but
for a completely different reason. :) See my last comment below.<br class="">
<blockquote cite="mid:A1A1CB5D-299D-4D03-BA15-DD1FA70A6B74@apple.com" type="cite" class="">
<div class=""><br class="">
</div>
<div class="">But is there an implicit invariant.end(%pLen) at the call to
foo(), at which point the array can be freed and another object
allocated in its place? I don’t think so. </div>
</blockquote>
Given the current semantics, if the result of the invariant.start is
not passed to foo, we can assume foo does not contain an
invariant.end. However, for foo to allocate a new object in the
same memory, it must write to that memory. Doing so without ending
the previous invariant region is ill defined. As such, your example
isn't a valid test. <br class="">
<br class="">
We have two cases:<br class="">
a) The invariant region hasn't ended. As a result, the input IR is
ill defined and the problematic reordering can happen. <br class="">
b) The invariant region ended (and we either encountered a
llvm.invariant.end, or saw the result of invariant.start passed to
foo). In this case, the location is no longer invariant and the
reordering isn't legal and wouldn't happen.<br class="">
<br class="">
As I think came up before, this would imply that an invariant.end
can't be dropped without dropping it's corresponding
invariant.start. That's problematic. <br class="">
<br class="">
<blockquote cite="mid:A1A1CB5D-299D-4D03-BA15-DD1FA70A6B74@apple.com" type="cite" class="">
<div class="">The way I interpreted the conclusion of this email thread is
that invariant.start can be used without invariant.end. </div>
</blockquote>
We had a proposal for this, but I don't believe it's actually been
implemented yet. I believe this proposal is still consistent with
everything I said above though. <br class="">
<blockquote cite="mid:A1A1CB5D-299D-4D03-BA15-DD1FA70A6B74@apple.com" type="cite" class="">
<div class="">Since the token returned by the intrinsic never escapes, you
can just assume the memory is invariant at all uses. The problem
here is that the optimizer could (in theory) introduce new uses
of the pointer after the object lifetime. This is the same
problem that you yourself have raised. I hoped we could sidestep
the problem because it crops up with any representation that
attaches invariance to a pointer value. If we have an answer for
this, then we can easily debate other representations like
broadening !invariant.load metadata semantics and introducing
new intrinsics.</div>
</blockquote>
I agree there is a general issue here. However, I don't actually
think it's an issue of invariance. Instead, I see this as being a
problem of *derefenceability*. Regardless of the 'invariant-ness'
of the memory in question, it's problematic for the optimizer to
insert uses after a deallocation because the memory transitions from
dereferenceable to non-dereferenceable. (i.e. Consider a malloc
routine allocates one page per object, and a free which protects the
page freed.) Any transformation which inserts such a load is
dangerous. <br class="">
<br class="">
What your example really shows is that we can have two names for the
same *memory address*. One of those names can be dereferenceable
while the other is not. <br class="">
<br class="">
The dynamic check of the pointer values essentially allows the
optimizer to chose which of the two names for the same physical
address it wants to use. I think that is valid, but it's odd to say
the least. The particular example you've shown isn't legal since
the optimizer is choosing to insert a load to a non-dereferenceable
location and thus could introduce a fault.</div></div></blockquote><div><br class=""></div>Sorry, I didn’t follow your response. I was showing that the optimizer can theoretically substitute the use of one pointer value (%o) with another pointer value (%pLen) after checking value equivalence. Doing that creates multiple uses of the same pointer value where not all uses dereference the same memory object. To me, that means we cannot associate a pointer value/address with an object-specific attribute, like invariance, without tying it to a closed lifetime. I wish we could prevent the optimizer from doing this.</div><div><br class=""></div><div>-Andy</div><div><br class=""><blockquote type="cite" class=""><div class=""><div bgcolor="#FFFFFF" text="#000000" class=""> <br class="">
<blockquote cite="mid:A1A1CB5D-299D-4D03-BA15-DD1FA70A6B74@apple.com" type="cite" class="">
<div class=""><br class="">
</div>
<div class="">-Andy</div>
<div class=""><br class="">
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<div class=""> <br class="">
What is the argument that you see leading from the
second to your problematic example? I'm missing the
reasoning by which you got there. I agree that the
example is problematic, I'm just not sure how it would
arise. <br class="">
</div>
<br class="">
<br class="">
<blockquote cite="mid:3C814DCF-2BCF-413A-906F-560B84918529@apple.com" type="cite" class="">
<div class="">
<div class=""><br class="">
</div>
<div class="">Either we need to make a convincing
argument, or bail on most of the tentative proposals
for expressing invariance, and resort to generating
IR like this:</div>
<div class=""><br class="">
</div>
<div class="">%a = newArray()</div>
<div class="">%pLen = gep(%a, <length offset>)</div>
<div class="">%t = invariant.start(<size>,
%pLen)</div>
<div class="">%len = load %pLen</div>
<div class=""><br class="">
</div>
<div class="">%o = foo() // may deallocate %a</div>
<div class="">invariant.end(%t, <size>, %pLen)</div>
<div class="">store %something</div>
<div class="">load %o</div>
<div class=""><br class="">
</div>
<div class="">...which is pretty painful to implement
and may be very difficult to optimize.</div>
</div>
<div class=""><br class="">
</div>
<div class="">-Andy</div>
</blockquote>
<br class="">
</div>
</div>
</blockquote>
</div>
<br class="">
</blockquote>
<br class="">
</div>
</div></blockquote></div><br class=""></body></html>