<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 06/13/2017 01:29 PM, Daniel Berlin
via llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTVeTqN8FG1v0UVtH=4o5j7mPs4eJCAnehPz5HAzMeF4DA@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Jun 12, 2017 at 11:24 PM,
Tobias Grosser via llvm-dev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Hi Jakub,<br>
<br>
thanks for the update. I was already eagerly waiting to
hear what your<br>
internship on dominance brings. I think the numbers are
already very<br>
encouraging and I believe moving incrementally over to the
new algorithm<br>
is exactly the right approach.<br>
<br>
I have a couple of questions:<br>
<br>
1) Daniel and Chandler have for a long time been talking
about computing<br>
dominance and post-dominance in one shot to reduce the
cost of<br>
post-dominance and make it (freely) available everywhere.
Is this<br>
covered by your current (or planned) work?<br>
</blockquote>
<div><br>
</div>
<div>I think chandler more than me. If me, assume I was
wrong :P</div>
<div><br>
</div>
<div>I believe you can prove it is not possible to do this
without doing all the work of the separate passes. The
main cost is the DFS walk, and you can't do an undirected
DFS that will work here.</div>
<div>I believe related things have even been proven to show
the brokenness of various algorithms.<br>
</div>
<div><br>
</div>
<div>See <a moz-do-not-send="true"
href="https://hal.inria.fr/hal-00761505">https://hal.inria.fr/hal-00761505</a>
section 4.1</div>
<div><br>
</div>
<div>Given the difficulties and subtleties here, I would
consider any such approach that tried to share work
between the passes as "fraught with peril"<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
Is there a difference here between sharing work and sharing updates?
The difficult part of using postdominance seems to be not the
one-time cost of computing it, but the fact that we don't preserve
it anywhere. Thus, using it would require re-computing it a lot.
Even if we can't share the work of constructing a dominance and
post-dominance tree, could we have an update API that could be used
to keep both trees consistent?<br>
<br>
Thanks again,<br>
Hal<br>
<br>
<blockquote
cite="mid:CAF4BwTVeTqN8FG1v0UVtH=4o5j7mPs4eJCAnehPz5HAzMeF4DA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<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>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>