RFC Storing BB order in llvm::Instruction for faster local dominance

Hello again. :slight_smile:

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

  • 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 would be needed.

Thanks a lot for working on this!

vedant

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

+1, this is a really good idea.

Cheers,
Nicolai