[llvm-dev] RFC Storing BB order in llvm::Instruction for faster local dominance (original) (raw)

Duncan Exon Smith via llvm-dev llvm-dev at lists.llvm.org
Fri Feb 14 17:00:50 PST 2020

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.

Duncan

On 2020 Feb 14, at 14:47, Vedant Kumar via llvm-dev <llvm-dev at lists.llvm.org> wrote:

+ 1 from me. 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 https://reviews.llvm.org/D74642 <https://reviews.llvm.org/D74642> would be needed. Thanks a lot for working on this! vedant

On Feb 14, 2020, at 1:49 PM, Reid Kleckner via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:

Hello again. :) 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: https://reviews.llvm.org/D51664 <https://reviews.llvm.org/D51664> 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. MLIR already uses this technique: https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615 <https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/IR/Operation.h#L615> 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". http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html <http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html> Thanks, Reid

LLVM Developers mailing list llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

LLVM Developers mailing list llvm-dev at lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200214/644cbac5/attachment-0001.html>

More information about the llvm-dev mailing list