llvm dev - Feb 2020 - RFC Storing BB order in llvm::Instruction for faster local dominance

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>

+ 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> 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
> 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/6df6b201/attachment.html>

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>

+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.