<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/21/2017 08:49 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTWrCMh9D46M+kt+QT4kATu3Hy_5er27XJnVvvT8qtfdCg@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 Wed, Jun 21, 2017 at 6:00 PM, Hal
Finkel <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div class="h5">
<p><br>
</p>
<div class="m_-4487549714715789291moz-cite-prefix">On
06/13/2017 01:29 PM, Daniel Berlin via llvm-dev
wrote:<br>
</div>
<blockquote type="cite">
<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"
target="_blank">https://hal.inria.fr/hal-<wbr>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>
</div>
</div>
Is there a difference here between sharing work and
sharing updates?
</div>
</blockquote>
<div><br>
</div>
<div>Yes.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> 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>
</div>
</blockquote>
<div><br>
</div>
<div>This is precisely what Jakub's set of patches solves.</div>
<div>The API for updating either dominance or post-dominance
will be identical.</div>
<div>It just needs to be informed of new edges and removed
edges in the CFG.</div>
<div><br>
</div>
<div>It's possible,at least in the new PM, to easily have a
DominatorTreeUpdater utility that uses
getAnalysisIfAvailable on both dominator and postdominator
analysis, and calls through to the update API for each
one.</div>
</div>
</div>
</div>
</blockquote>
<br>
Great!<br>
<br>
-Hal<br>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>