<div dir="ltr"><div>About the impact of disabling GVN for pointers - for SPEC CPU and llvm-test-suite the slowdown wasn't significant (avg. <0.1%),</div><div>but I'm concerned that they are only a small number of programs written in C/C++ on and my experiment was done on only one architecture.</div><div>Certainly for programs using many pointers disabling GVN is likely to be problematic.</div><div dir="ltr"><br></div><div dir="ltr">If we have an operation that is similar to launder, then the optimization can be almost salvaged.</div><div>Let's call it 'q = wildcard_provenance(p)'; it means that q can be used to access an object that is at (intptr_t)p but not necessarily p's object.</div><div dir="ltr"><div><div>(In our memory model, wildcard_provenance(p) is equivalent to 'inttoptr(ptrtoint p)').</div><div></div></div><div><div></div></div><div><br></div><div>Replacing p with 'wildcard_provenance(p)' is correct because it makes the program more defined.</div><div></div><div><div><div></div></div></div><div>For example, load p raises UB if p is freed, but load wildcard_provenance(p) is still well-defined if a new live malloc is exactly placed at (intptr_t)p.<br></div><div><div><div>When lowered to MachineIR, wildcard_provenance(p) is simply a register copy.</div><div></div></div><div></div><div></div></div><div><div><br></div><div>Here is the list of valid optimizations:</div><div><div><br></div><div><div><div><div></div></div></div></div></div><div>1. GVN</div><div>if (p == q) {</div><div> use(p);</div><div> use(q);</div><div>}</div><div>=></div><div>if (p == q) {</div><div> use(p);<br> use(wildcard_provenance(p));</div><div>}</div></div><div><br></div><div>2.</div><div><div><div><div><div>dereference(p);</div><div></div></div><div></div><div>dereference(wildcard_provenance(p));</div><div>=></div><div>dereference(p);</div><div>dereference(p);</div><div></div><div><br></div></div></div></div><div>3.</div><div><div><div><div>store v, wildcard_provenance(p);</div><div></div></div><div></div><div>w = load p;</div><div>=></div><div><div>store v, wildcard_provenance(p);</div><div></div></div><div></div><div></div><div>w = v;</div><div><br></div></div></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">4.</div><div class="gmail_attr">must-alias(p, wildcard_provenance(p))? // answer: true<br></div><div class="gmail_attr"><br></div><div class="gmail_attr"><br></div><div class="gmail_attr">I don't have a performance number for this yet because the operation did not exist when designing the memory model.</div><div class="gmail_attr"><br></div><div class="gmail_attr">Juneyoung</div><div dir="ltr" class="gmail_attr"><br></div><div dir="ltr" class="gmail_attr">On Wed, Jun 23, 2021 at 1:07 AM Hal Finkel <<a href="mailto:hal.finkel.llvm@gmail.com" target="_blank">hal.finkel.llvm@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 6/22/21 05:58, Ralf Jung via llvm-dev wrote:<br>
> Hi John,<br>
><br>
>> Unfortunately, though, I this non-determinism still doesn’t allow LLVM<br>
>> to be anywhere near as naive about pointer-to-int casts as it is today.<br>
><br>
> Definitely. There are limits to how naive one can be; beyond those <br>
> limits, miscompilations lurk. <br>
> <<a href="https://www.ralfj.de/blog/2020/12/14/provenance.html" rel="noreferrer" target="_blank">https://www.ralfj.de/blog/2020/12/14/provenance.html</a>> explains this <br>
> by showing such a miscompilation arising from three naive <br>
> optimizations being chained together.<br>
><br>
>> The rule is intended to allow the compiler to start doing use-analysis<br>
>> of exposures; let’s assume that this analysis doesn’t see any<br>
>> un-analyzable uses, since of course it would need to conservatively<br>
>> treat them as escapes. But if we can optimize uses of integers as if<br>
>> they didn’t carry pointer data — say, in a function that takes integer<br>
>> parameters — and then we can apply those optimized uses to integers<br>
>> that concretely result from pointer-to-int casts — say, by inlining<br>
>> that function into one of its callers — can’t we end up with a use<br>
>> pattern for one or more of those pointer-to-int casts that no longer<br>
>> reflects the fact that it’s been exposed? It seems to me that either<br>
>> (1) we cannot do those optimizations on opaque integers or (2) we<br>
>> need to record that we did them in a way that, if it turns out that<br>
>> they were created by a pointer-to-int casts, forces other code to<br>
>> treat that pointer as opaquely exposed.<br>
><br>
> There is a third option: don't optimize away ptr-int-ptr roundtrips. <br>
> Then you can still do all the same optimizations on integers that LLVM <br>
> does today, completely naively -- the integer world remains "sane". <br>
> Only the pointer world has to be "strange".<br>
> (You can also not do things like GVN replacement of *pointer-typed* <br>
> values, but for values of integer types this remains unproblematic.)<br>
<br>
<br>
Do we have any idea how large of an effect this might be? If we disable <br>
GVN for all pointer-typed values? And is it really all GVN, or just <br>
cases where you unify the equivalence classes based on some dominating <br>
comparison operation? We should be careful here, perhaps, because LLVM's <br>
GVN does a lot of plain-old CSE, store-to-load forwarding, etc. and we <br>
should say specifically what would need to be disabled and in what contexts.<br>
<br>
-Hal<br>
<br>
<br>
><br>
> I don't think it makes sense for LLVM to adopt an explicit "exposed" <br>
> flag in its semantics. Reasoning based on non-determinism works fine, <br>
> and has the advantage of keeping ptr-to-int casts a pure, <br>
> side-effect-free operation. This is the model we explored in <br>
> <<a href="https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf" rel="noreferrer" target="_blank">https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf</a>>, and we were <br>
> able to show quite a few of LLVM's standard optimizations correct <br>
> formally. Some changes are still needed as you noted, but those <br>
> changes will be required anyway even if LLVM were to adopt PNVI-ae:<br>
> - No removal of ptr-int-ptr roundtrips. <br>
> (<a href="https://bugs.llvm.org/show_bug.cgi?id=34548" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=34548</a>)<br>
> - No GVN replacement of pointer-typed values. <br>
> (<a href="https://bugs.llvm.org/show_bug.cgi?id=35229" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=35229</a>)<br>
><br>
>> (I'm not sure whether this is a good place to introduce this, <br>
>> but) we<br>
>> actually have semantics for pointer castings tailored to LLVM (link<br>
>> <<a href="https://sf.snu.ac.kr/publications/llvmtwin.pdf" rel="noreferrer" target="_blank">https://sf.snu.ac.kr/publications/llvmtwin.pdf</a><br>
>> <<a href="https://sf.snu.ac.kr/publications/llvmtwin.pdf" rel="noreferrer" target="_blank">https://sf.snu.ac.kr/publications/llvmtwin.pdf</a>>>).<br>
>> In this proposal, ptrtoint does not have an escaping side effect; <br>
>> ptrtoint<br>
>> and inttoptr are scalar operations.<br>
>> inttoptr simply returns a pointer which can access any object.<br>
>><br>
>> Skimming your paper, I can see how this works /except/ that I don’t<br>
>> see any way not to treat |ptrtoint| as an escape. And really I think<br>
>> you’re already partially acknowledging that, because that’s the only<br>
>> real sense of saying that |inttoptr(ptrtoint p)| can’t be reduced to<br>
>> |p|. If those are really just scalar operations that don’t expose<br>
>> |p| in ways that might be disconnected from the uses of the |inttoptr|<br>
>> then that reduction ought to be safe.<br>
><br>
> They are indeed just scalar operations, but the reduction is not safe.<br>
> The reason is that pointer-typed variables have values of the form <br>
> "(addr, provenance)". There is essentially an 'invisible' component in <br>
> each pointer value that tracks some additional information -- the <br>
> "provenance" of the pointer. Casting a ptr to an int removes that <br>
> provenance. Casting an int to a ptr picks a "default" provenance. So <br>
> the overall effect of inttoptr(ptrtoint p) is to turn "(addr, <br>
> provenance)" into "(addr, DEFAULT_PROVENANCE)".<br>
> Clearly that is *not* a NOP, and hence performing the reduction <br>
> actually changes the result of this operation. Before the reduction, <br>
> the resulting pointer had DEFAULT_PROVENANCE; after the reduction, it <br>
> maintains the original provenance of "p". This can introduce UB into <br>
> previously UB-free programs.<br>
><br>
> Kind regards,<br>
> Ralf<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div>
</div>