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

Reid Kleckner via llvm-dev llvm-dev at lists.llvm.org
Tue Sep 25 14:35:58 PDT 2018

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:

More information about the llvm-dev mailing list