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

[Reid Kleckner via llvm-dev]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200214/5428af8e/attachment.html>