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

[Nicolai Hähnle via llvm-dev]

+1, this is a really good idea.

Cheers,
Nicolai

On Fri, Feb 14, 2020 at 10:50 PM Reid Kleckner via llvm-dev
<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
>
> 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
>
> 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
>
> Thanks,
> Reid
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.