<div dir="ltr">Hello again. :)<div><br></div><div>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><a href="https://reviews.llvm.org/D51664">https://reviews.llvm.org/D51664</a> </div><div><br></div><div>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></div><div><br></div><div>MLIR already uses this technique:</div><div><a href="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</a><br></div><div><br></div><div>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><a href="http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html">http://lists.llvm.org/pipermail/llvm-dev/2018-September/126249.html</a> <br></div><div><br></div><div>Thanks,</div><div>Reid</div></div>