<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 09/10/2014 02:42 PM, Kevin Modzelewski wrote:<br>
<blockquote
cite="mid:CAO=oM6uBbAeScZe_zUvswc_088Thee1ODdMo6iwbSHtZ_B5oWg@mail.gmail.com"
type="cite">
<div dir="ltr">We have some similar cases and wanted the same
thing; what we were doing for a while is using the third "is
constant" field of the TBAA metadata and setting that to 1. I'm
not 100% sure what the semantics of that are -- LangRef says it
means that pointsToConstantMemory() returns true which means
that the memory is "impossible ... to be modified", which seems
like not quite a fit for this set-exactly-once use case. In
practice, looking at the IR after our optimization pipeline, we
were getting the results we wanted: if a store and subsequent
loads were seen together, the store would remain and the value
would be forwarded to all the loads. (I don't think I looked at
the "multiple loads with no visible store which should get
collapsed to a single load" case.) ymmv</div>
</blockquote>
I hadn't looked at this approach much, but based on the
documentation, you're basically just asking for miscompiles here.
The semantics seem to be the same as "invariant.load". While the
optimizer happens to not be removing the stores, it seems like it
would be perfectly legal for it to do so. <br>
<blockquote
cite="mid:CAO=oM6uBbAeScZe_zUvswc_088Thee1ODdMo6iwbSHtZ_B5oWg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>We've disabled the optimization for now, since without an
easy way of putting the annotation in the C++ source code and
getting it passed through clang, it became a burden to keep
the application logic in sync with the tbaa-fixup code that
lived in a different place. We'll fix it eventually...</div>
</div>
</blockquote>
I can't comment on this part. I'm assuming the C++ code being
compiled is your runtime or something?<br>
<blockquote
cite="mid:CAO=oM6uBbAeScZe_zUvswc_088Thee1ODdMo6iwbSHtZ_B5oWg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>kmod</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Tue, Sep 9, 2014 at 10:11 PM, Philip
Reames <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">I'm
looking at how to optimize IR which contains reads from a
field which is known to be initialized exactly once. I've
got an idea on how to approach this, but wanted to see if
others have alternate ideas or similar problems which might
spark discussion. It feels like there's a potentially
generally useful optimization hint here if we can generalize
it sufficiently without loosing optimization potential.<br>
<br>
The problem:<br>
struct array {<br>
private:<br>
// once initialized 'len' never changes<br>
int len;<br>
// data can be modified at will<br>
char data[0];<br>
public:<br>
static array* make(int len) {<br>
array* a = ... allocate uninitialized space<br>
a->len = len;<br>
return a;<br>
}<br>
};<br>
void access(array* a, int idx) {<br>
if( idx >= 0 && idx <- a->len ) {<br>
a->data[idx] = 5;<br>
}<br>
}<br>
void foo(array* a) {<br>
for(int i = 0; i < a->len; i++) {<br>
access(a, i);<br>
}<br>
}<br>
// assume 'access' is inlined into 'foo' and the loop is
unrolled a time or two<br>
<br>
To phrase that again in english, I've got a field which is
initialized once, with naive code which reads from it many
times. I know at IR generation time that a load from
array::len is special, but I loose this information as soon
as I generate IR. In particular, I run into aliasing
problems where the location a->len is considered
'mayalias' with unrelated stores thus preventing value
forwarding, LICM, and other desirable optimizations.<br>
<br>
Existing Approaches:<br>
1) Use TBAA - By tagging loads and stores to the two fields
of the array struct as disjoint branches in the TBAA tree, I
can inform LLVM that a load of 'len' never aliases with a
store through 'data'. This mostly works, and enables many
loads to be forwarded by GVN, but (due to the intervening
stores) is a complete loss in EarlyCSE and (due to
intervening calls) LICM.<br>
a) Things like <a moz-do-not-send="true"
href="http://llvm.org/bugs/show_bug.cgi?id=20805"
target="_blank">http://llvm.org/bugs/show_bug.cgi?id=20805</a>
could improve the situation in EarlyCSE.<br>
2) Use "invariant.load" metadata - This metadata indicates
that the field loaded from is initialized before the
execution of the code being compiled. In particular,
"invariant.load" implies that the load is not control
dependent on any branch, is safe to speculate, and that no
write aliases the location read from. This mostly works,
but only if 'array::make' is never visible in the IR. As
soon as 'array::make' gets inlined, all bets are off and
mis-compiles may result.<br>
a) Also, in practice, only LICM really knows about
"invariant.load". It would be pretty straight forward to
teach both EarlyCSE and GVN about them though. <a
moz-do-not-send="true"
href="http://llvm.org/bugs/show_bug.cgi?id=20806"
target="_blank">http://llvm.org/bugs/show_bug.cgi?id=20806</a><br>
<br>
New Approaches:<br>
(This isn't so much "being proposed" as "being put forward
for discussion".)<br>
<br>
1) Introduce a new metadata type "initialized-before-load"
which implies that the value of any two loads tagged with
the metadata along any execution path must yield the same
result.<br>
<br>
This doesn't give much freedom to the 'first' load; it's
still control dependent, can't be reordered with preceding
stores, can't be lifted out of loops, etc... It can however
be reordered with following stores or sunk out of a loop
provided the loop body is known to execute at least once.<br>
<br>
The second load has a lot more freedom. Provided that there
is always another load to the same location (with the
metadata) provable preceding it on all paths, it can be
reordered freely, lifted over control branches, lifted out
of loops, etc... Importantly, it is also legal to forward
the value of a preceding load to a later load provided that
a) both have the metadata and b) that one load executes
strictly before the other.<br>
<br>
A store marked "initialized-before-load" is undefined if
there is a load with the same metadata on the same location
preceding it. There may be *multiple* stores to the location
along a path, provided that the first load is strictly after
*all* of them.<br>
<br>
This seems staight forward to implement in EarlyCSE and
LICM. I haven't looked closely at GVN, but expect it's
probably not hard either.<br>
<br>
2) Introduce a slightly different metadata
"initialized-once". Semantics are very similar to the
preceding except that there can only be a single store to
the location along any path.<br>
<br>
Value forwarding from the store to a following load (with
metadata) is allowed regardless of potentially aliasing
intervening stores.<br>
<br>
This was actually my original idea, but it has a couple of
problems. First, it breaks on surprisingly common
initialization patterns such as default initialization
followed by real initialization. Secondly, I'm not sure the
optimizer would always preserve the "write once" property.
In particular, the optimizer is free to divide a large write
into several smaller ones (assuming the write is not
atomic.)<br>
<br>
<br>
<br>
Thoughts? Suggestions? Similar sounding problems this
might be able to solve?<br>
<br>
Philip<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu"
target="_blank">LLVMdev@cs.uiuc.edu</a> <a
moz-do-not-send="true" href="http://llvm.cs.uiuc.edu"
target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>