<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<div class="moz-cite-prefix">On 09/19/2018 03:30 PM, Reid Kleckner via llvm-dev wrote:<br>
</div>
<blockquote type="cite" cite="mid:CACs=ty+wzBKMYz==V1tK=Ys7d1EyiGiGzU05SWDuaGdbPwggsA@mail.gmail.com">
<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>
</div>
</blockquote>
<br>
Sounds great!<br>
<br>
-Hal<br>
<br>
<blockquote type="cite" cite="mid:CACs=ty+wzBKMYz==V1tK=Ys7d1EyiGiGzU05SWDuaGdbPwggsA@mail.gmail.com">
<div dir="ltr">
<div dir="ltr">
<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>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>