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

[Reid Kleckner via llvm-dev]

On Tue, Sep 25, 2018 at 12:16 PM Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> Let's not assume a dichotomy between storing a int64 in
> llvm::Instruction and bitwise tricks -- they're both ways of caching
> position within llvm::Instruction.  I think we first need to establish
> that we need such a cache in llvm::Instruction/llvm::BasicBlock at
> all.
>
> Do you have a sense of where these expensive domtree queries are
> coming from?  Are they from a couple of key places or are they
> scattered throughout the pass pipeline?
>

When I dug into the profile with WPA, most of the time was spent in DSE and
memcpyopt, which call AAResults::callCapturesBefore, which calls
llvm::PointerMayBeCapturedBefore. Neither pass in an OrderedBasicBlock, so
they rebuild the OrderedBasicBlock in linear time on every query. These
passes insert instructions, so it's not correct to simply create and reuse
an OrderedBasicBlock at this level.

As suggested in the bug, if we were to rewrite these passes to use
MemorySSA, this bottleneck would go away. I rebased a patch to do that for
DSE, but finishing it off and enabling it by default is probably out of
scope for me.

These key call sites aside, dominance seems like a pretty common query. We
have several somewhat overlapping mechanisms for checking dominance:
- DominatorTree::dominates(Instruction*,Instruction*), the original
interface, widely known as a bottleneck
- OrderedBasicBlock, as used by memdep, my motivating example
- OrderedInstructions, uses OrderedBasicBlock, used by GVN and others
- MemorySSA has a similar ordering of memory values that is also
invalidated when inserting memory defs. I may have misunderstood how this
works, though.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180925/952d0082/attachment.html>