<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>+1 to the general direction</p>
<p>My concern is the invalidation/recompute cost, but I think we can
manage that. <br>
</p>
<p>Philip<br>
</p>
<br>
<div class="moz-cite-prefix">On 09/19/2018 01:30 PM, Reid Kleckner
via llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CACs=ty+wzBKMYz==V1tK=Ys7d1EyiGiGzU05SWDuaGdbPwggsA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<div dir="ltr">
<div dir="ltr">
<div>Hi folks,</div>
<div><br>
</div>
<div>I looked into some slow compiles and filed <a
href="https://bugs.llvm.org/show_bug.cgi?id=38829"
moz-do-not-send="true">https://bugs.llvm.org/show_bug.cgi?id=38829</a>.
The gist of it is that we spend a lot of time iterating
basic blocks to compute local dominance, i.e. given two
instructions in the same BB, which comes first.<br>
</div>
<div dir="ltr"><br>
</div>
<div>LLVM already has a tool, OrderedBasicBlock, which
attempts to address this problem by building a lazy mapping
from Instruction* to position. The problem is that cache
invalidation is hard. If we don't cache orderings at a high
enough level, our transformations become O(n^2). If we cache
them too much and insert instructions without renumbering
the BB, we get miscompiles. My solution is to hook into the
actual BB ilist modification methods, so that we can have
greater confidence that our cache invalidation is correct.</div>
<div dir="ltr"><br>
</div>
<div dir="ltr">I created a patch for this at <a
href="https://reviews.llvm.org/D51664"
moz-do-not-send="true">https://reviews.llvm.org/D51664</a>,
which adds a lazily calculated position integer to every
llvm::Instruction. I stole a bit from BasicBlock's Value
subclass data to indicate whether the orders are valid.</div>
<div dir="ltr"><br>
</div>
<div>Hopefully everyone agrees that this a reasonable
direction. I just figured I should announce this IR data
structure change to the -dev list. :)</div>
<div><br>
</div>
<div>Reid</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>
</body>
</html>