<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Indeed, we see some variation of this at least every six months causing compile time explosions *somewhere* in the optimization pipeline. We would benefit tremendously from this being merged.<div class=""><br class=""></div><div class="">Duncan<br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On 2020 Feb 14, at 14:47, Vedant Kumar via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html; charset=us-ascii" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="">+ 1 from me.</div><div class=""><br class=""></div><div class="">We just got a report about clang spending 10 minutes doing block-local dominance queries in CodeGenPrepare. I believe that with D51664 in place, the issue would never have occurred, and no workaround like <a href="https://reviews.llvm.org/D74642" class="">https://reviews.llvm.org/D74642</a> would be needed.</div><div class=""><br class=""></div><div class="">Thanks a lot for working on this!</div><div class=""><br class=""></div><div class="">vedant</div><div class=""><br class=""><blockquote type="cite" class=""><div class="">On Feb 14, 2020, at 1:49 PM, Reid Kleckner via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hello again. :)<div class=""><br class=""></div><div class="">There has been renewed interest in having instructions track their own order in basic blocks to help make dominance queries fast. I have a very simple naive implementation of this here:</div><div class=""><a href="https://reviews.llvm.org/D51664" class="">https://reviews.llvm.org/D51664</a> </div><div class=""><br class=""></div><div class="">Essentially, every instruction will carry an integer order number, and inserting new instructions invalidates the ordering. I know there are better algorithms for maintaining the ordering in the face of random insertions, but I wanted to focus on the simple case of making dominance queries amortized O(1) when no insertion is occuring. My personal belief is that most transforms are 80% analysis, 20% transformation, so most of the benefits can be delivered with simple heuristics.<br class=""></div><div class=""><br class=""></div><div class="">MLIR already uses this technique:</div><div class=""><a href="https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615" class="">https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615</a><br class=""></div><div class=""><br class=""></div><div class="">With the renewed interest in the patch, I believe there is broad consensus that we should do this, but I wanted to re-open this RFC that I started back in 2018 to give anyone a chance to say "no".</div><div class=""><a href="http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html" class="">http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html</a> <br class=""></div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Reid</div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div><br class=""></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></body></html>