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

[Andrew Trick]

On Mar 25, 2014, at 5:22 PM, Duncan P. N. Exon Smith <dexonsmith at apple.com> wrote:

> On Mar 19, 2014, at 12:34 AM, Andrew Trick <atrick at apple.com> wrote:
> 
>> Originally, we did not want to make BlockFrequency depend on LoopInfo, but I no longer see a good reason to avoid it. On the other hand, LoopInfo is not a helpful representation for you. The only drawback to rolling your own is the little LoopStack utility. It's current position in the file is confusing to me because it appears to be part of the main algorithm. If you comment that it is a helper for initializeLoops, and place it adjacent in the code, then it's probably simpler than trying to reuse LoopInfo--unless you have an issue with irreducible CFG.
>> 
>> LoopInfo effectively ignores backedges that don't target a natural loop header. Whereas it looks like LoopStack will attempt to create a loop for every backedge. You will end up visiting blocks for different "loops" before finishing either loop. Have you reasoned through this and determined how it will play out? Does the comment "frequencies can be distorted past the end of the loop” still completely characterize the problem?
> 
> I did reason through this, and some slightly weird things happen.  I
> decided that the weird things are *less* weird than artifacts from
> ignoring such back edges entirely, but this was somewhat arbitrary.
> 
> There are some other problems with my loop detection.  I was running
> through some examples to confirm my answer to your question below, I
> noticed a significant regression that must have crept in while I was
> reorganizing code for review.
> 
> Rolling my own solution here was dangerous because it’s really hard to
> test (and, thus, to prevent regressions).  I think the right solution is
> to use LoopInfo; as unhelpful as it is, the complex part (loop detection)
> is already well-tested.
> 
> If the overhead is too high, that’s motivation to fix LoopInfo.
> 
> I.e., I plan to migrate to LoopInfo before turning this on.  Does that
> sound fine to you?

Yes. I agree with your and Chandler’s points on this. I just didn’t want to block progress on a LoopInfo rewrite. I was afraid that API changes would perturb other passes in nontrivial ways. If you can migrate to LoopInfo and have a plan for improving it incrementally that’s great.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140325/4ae8a14f/attachment.html>