<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
<br class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">On 4 Jan 2019, at 16:39, Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div text="#000000" bgcolor="#FFFFFF" class="">
<p class=""><br class="">
</p>
<div class="moz-cite-prefix">On 1/4/19 5:24 PM, Artur Pilipenko via llvm-dev wrote:<br class="">
</div>
<blockquote type="cite" cite="mid:F06F7B97-C6B5-43AD-A6EE-BB13FC4AA978@azul.com" class="">
<div class="">Working on a downstream optimization which uses CaptureTracking (CT) I came </div>
<div class="">across a coupling problem. It looks like optimizations and analyses which use CT</div>
<div class="">often need to be in sync with CT implementation.</div>
<div class=""><br class="">
</div>
<div class="">Analyzing the uses of the given pointer CT handles three kinds of uses:</div>
<div class=""> * Simple non-capturing use. When one is encountered, CT just moves on.</div>
<div class=""> * Non-capturing, but produces another value, which needs to be tracked. </div>
<div class=""> Examples: bitcasts, geps, phis, selects, etc. I’ll call this kind of uses </div>
<div class=""> "aliases", for the lack of better word.</div>
<div class=""> * Capturing.</div>
<div class=""><br class="">
</div>
<div class="">The "aliases" are tricky. CT users often need to know about these. For example,</div>
<div class=""><a href="https://reviews.llvm.org/rL331587" class="" moz-do-not-send="true">rL331587</a> taught CT the "alias" semantic of launder.invariant.group calls. </div>
<div class="">Because BasicAA was not aware of this change, it lead to incorrect AA results.</div>
<div class="">"BasicAA still considered every call instruction as a possible escape source and </div>
<div class="">hence concluded that the result of a launder_invariant_group call cannot alias </div>
<div class="">any local non-escaping value."</div>
<div class="">The first attempt to fix it fixed BasicAA (<a href="https://reviews.llvm.org/rL332466" class="" moz-do-not-send="true">rL332466</a>), but apparently there were </div>
<div class="">similar issues in other parts. These were fixed by <a href="https://reviews.llvm.org/rL333070" class="" moz-do-not-send="true">
rL333070</a>.</div>
<div class=""><br class="">
</div>
<div class="">Another example is our downstream optimization which does some sort of scalar </div>
<div class="">replacement of non-escaping allocations. It rewrites uses of the allocation and </div>
<div class="">needs to know about "aliases" as their uses also need to be rewritten. Currently </div>
<div class="">it knows about all the "aliases" supported by CT, but it's not resilient to </div>
<div class="">further changes in CT.</div>
<div class=""><br class="">
</div>
<div class="">Proposal</div>
<div class=""><br class="">
</div>
<div class="">Currently CaptureTracker is notified about capturing uses through </div>
<div class="">CaptureTracker::captured. I propose to notify the tracker about all the uses </div>
<div class="">explicitly specifying the kind (NoCapture, Alias, Capture). This way the tracker</div>
<div class="">can only accept Alias uses it knows how to handle. If something unexpected comes</div>
<div class="">up the tracker can give up the analysis.</div>
<div class=""><br class="">
</div>
<div class="">The default tracker can ignore Alias uses under the assumption that upstream</div>
<div class="">users of CT maintain tight coupling with the analysis, like it is today. </div>
<div class="">Refactoring of upstream users of CT is out of scope for this proposal. But in </div>
<div class="">future they can be decoupled from CT implementation by explicitly checking the</div>
<div class="">Alias uses. <br class="">
</div>
</blockquote>
<p class="">Can you elaborate on how this makes the handling of special intrinsics, etc. easier to maintain? I certainly agree that the launder_invariant_group coupling seems unfortunate, but seemed to me to be a special case (and it is an intrinsic designed
to have special aliasing properties).<br class="">
</p>
</div>
</div>
</blockquote>
<div>Currently there is an implicit dependency: CT clients should know to look though</div>
<div>all "alias" uses known to CT. If the dependency is not satisfied, the result is </div>
<div>a subtle miscompile. The proposal is to notify CT clients about "alias" uses,</div>
<div>which gives them a chance to give up the analysis if an unexpected use comes up.</div>
<div><br class="">
</div>
<div>It doesn't eliminate the need to teach the optimizations about new "aliases"</div>
<div>added to CT. What it does, it turns a miscompile into a missed optimization.</div>
<div><br class="">
</div>
<div>To give an example, let's say we had had this mechanism implemented before we</div>
<div>taught launder_invariant_group semantic to CT. CT clients which need to look</div>
<div>though CT "aliases" would have used a custom tracker which checks the aliases</div>
<div>explicitly:</div>
<div><br class="">
</div>
<div> bool CaptureTracker::notifyUse(Use *U, UseKind Kind) {</div>
<div> if (Kind == Alias)</div>
<div> if (U->getUser() is not supported type)</div>
<div> return false; // Terminate the analysis</div>
<div> }</div>
<div><br class="">
</div>
<div>Introduction of a new launder_invariant_group "alias" wouldn't have resulted in</div>
<div>miscompiles because the clients which didn't expect it as an alias would have </div>
<div>conservatively treated it as a capture.</div>
<div><br class="">
</div>
<div>Artur</div>
<blockquote type="cite" class="">
<div class="">
<div text="#000000" bgcolor="#FFFFFF" class="">
<p class=""></p>
<p class=""> -Hal<br class="">
</p>
<blockquote type="cite" cite="mid:F06F7B97-C6B5-43AD-A6EE-BB13FC4AA978@azul.com" class="">
<div class=""><br class="">
</div>
<div class="">Thoughts?</div>
<div class=""><br class="">
</div>
<div class="">Artur</div>
<br class="">
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div>
</div>
</blockquote>
</div>
<br class="">
</body>
</html>