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

[Chris Lattner via llvm-dev]

> On Sep 24, 2018, at 9:54 PM, Chris Lattner <clattner at nondot.org> wrote:
>> I think we have consensus that we should go forward with this. Would anyone mind formally stamping it in phab? So far everyone understandably has said "makes sense to me, but I don't consider myself to have authority to stamp this.”
> 
> Hi Reid,
> 
> I have significant concerns with this patch.  I’d really appreciate it if you could address the discussion feedback here before just plowing forward with such an invasive change to the core IR.
> 
> Have you done any memory use analysis or compile time impact analysis of this change?  Have you consider the algorithm I mentioned?  I am not motivated by your rationale above, and I think it will be a huge step forward and effectively define away the problem.

To be clear, I’m a superfan of your work and agree that “automatic invalidation and simplification” are good goals.  I’d just love to see more analysis of the situation before burning space on this extra field.

For example, it would be very interesting to see what the typical distribution of local dominance queries actually are.  You could take your patch here and have it instrument the “Instruction::comesBefore” method to log the distance between the instruction numbers to a file and generate a histogram of them.   My bet is that the vast vast vast majority of them will be small (and I’d guess a HUGE number of them have a distance of +1/-1, whose query can be resolved without computing a numbering in the first place).

Can you do that experiment and report back, e.g. on the SemaChecking.cpp testcase?

-Chris