[LLVMdev] [RFC] BlockFrequency is the wrong metric; we need a new one

[Bob Wilson]

On Feb 2, 2014, at 6:55 PM, Chandler Carruth <chandlerc at gmail.com> wrote:
> 
> If you want to take a more complex approach, we could definitely add a confidence dimension to the branch probability. This would allow us to express a high-confidence un-predictable branch and optimize based on that. However, we would *still* want block weights to be computed more like I have proposed. Instead of only branch probabilities that were far outside of 50/50 influencing it, we would want branch probabilities that were highly confident to influence it. The practical result would be exactly the same as what I have proposed, it is just that I'm making the simplifying assumption that at the moment, there are no evenly distributed branch probabilities which we have high confidence in.

Adding a confidence dimension seems like overkill to me. It seems like we should be able to distinguish branches with known 50/50 probability, e.g., from real profile data, from those where we have no idea, simply by omitting the branch probability information in the latter case. I suppose that is essentially adding a confidence dimension, but only in a very simple way.

That’s a separate question from what to do when you don’t know anything about the probability of a branch. Andy has thought a lot more about this than I have, so for now, I will defer to his opinion. I will just point out that Duncan Exon Smith is currently looking at rewriting the BlockFrequency pass in a way that Jakob had suggested to help fix some serious problems with the loss of precision. Your proposed change to BlockFrequency would almost certainly have an impact on his work, so hopefully we can figure out soon what we want to do.

Incidentally, while looking at this, I noticed that our current static heuristics are assigning naive 50/50 probabilities due to a bug. I filed PR18705 to describe it, but basically we’re often doing the wrong thing for anything inside a loop.