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

Philip Reames via llvm-dev llvm-dev at lists.llvm.org
Wed Sep 19 16:44:22 PDT 2018

+1 to the general direction

My concern is the invalidation/recompute cost, but I think we can manage that.

Philip

On 09/19/2018 01:30 PM, Reid Kleckner via llvm-dev wrote:

Hi folks,

I looked into some slow compiles and filed https://bugs.llvm.org/showbug.cgi?id=38829. The gist of it is that we spend a lot of time iterating basic blocks to compute local dominance, i.e. given two instructions in the same BB, which comes first. LLVM already has a tool, OrderedBasicBlock, which attempts to address this problem by building a lazy mapping from Instruction* to position. The problem is that cache invalidation is hard. If we don't cache orderings at a high enough level, our transformations become O(n^2). If we cache them too much and insert instructions without renumbering the BB, we get miscompiles. My solution is to hook into the actual BB ilist modification methods, so that we can have greater confidence that our cache invalidation is correct. I created a patch for this at https://reviews.llvm.org/D51664, which adds a lazily calculated position integer to every llvm::Instruction. I stole a bit from BasicBlock's Value subclass data to indicate whether the orders are valid. Hopefully everyone agrees that this a reasonable direction. I just figured I should announce this IR data structure change to the -dev list. :) Reid

LLVM Developers mailing list llvm-dev at lists.llvm.org http://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/20180919/9e280943/attachment.html>

More information about the llvm-dev mailing list