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

[Philip Reames via llvm-dev]

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