<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Tue, Sep 25, 2018 at 12:16 PM Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Let's not assume a dichotomy between storing a int64 in<br>
llvm::Instruction and bitwise tricks -- they're both ways of caching<br>
position within llvm::Instruction.  I think we first need to establish<br>
that we need such a cache in llvm::Instruction/llvm::BasicBlock at<br>
all.<br>
<br>
Do you have a sense of where these expensive domtree queries are<br>
coming from?  Are they from a couple of key places or are they<br>
scattered throughout the pass pipeline?<br></blockquote><div><br></div><div>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<font color="#000000">. 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.</font></div><div><br></div><div>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.</div><div><br></div><div>These key call sites aside, dominance seems like a pretty common query. We have several somewhat overlapping mechanisms for checking dominance:</div><div>- DominatorTree::dominates(Instruction*,Instruction*), the original interface, widely known as a bottleneck</div><div>- OrderedBasicBlock, as used by memdep, my motivating example<br></div><div>- OrderedInstructions, uses OrderedBasicBlock, used by GVN and others</div><div>- MemorySSA has a similar ordering of memory values that is also invalidated when inserting memory defs. I may have misunderstood how this works, though.</div></div></div>