Page MenuHomePhabricator

In SCEV's printer pass, print an estimate of the exit count for each exit from profiling information
Needs ReviewPublic

Authored by reames on Jan 24 2020, 6:06 PM.

Details

Summary

This is geared at being a debugging aid. When analysing IR, it's common to have large complicated loops with multiple exits and profiling data which indicates which exit is actually taken. When looking to see if there's a problem in SCEV's exit count logic, it really helps to be able to quickly see which exits are probably dead in practice. These are frequently - though not always - good places to examine further.

For the moment, the implementation of the estimated exit count stuff is SCEV specific. There's a version of something analogous in getEstimatedTripCount but a) trip count != exit count, and b) this needs to handle multiple exit loops, and c) I want to be able switch consumes over one by one to minimize breakage. My plan is to land this, move the impl into a common analysis header, then visit each one by one.

Diff Detail

Event Timeline

reames created this revision.Jan 24 2020, 6:06 PM
nikic added inline comments.Jan 25 2020, 1:30 AM
llvm/test/Analysis/ScalarEvolution/trip-count.ll
143

Why are the branch weights here 20/1 and not 19/1 (and relatedly, why do we need to subtract -1 in the exit count calculation)?

reames marked an inline comment as done.Jan 27 2020, 10:24 AM
reames added inline comments.
llvm/test/Analysis/ScalarEvolution/trip-count.ll
143

Because I made a mental off by one error, and then made everything else consistent with that mistake. Oops. :)

I was thinking in iterations not backedges taken. Despite the comments which say the opposite.

Thanks for catching that!

reames updated this revision to Diff 240636.Jan 27 2020, 10:31 AM

Fix off by one bug pointed out in review.

nikic added a comment.Jan 27 2020, 1:45 PM

What you're doing here is right for a single exit, but I don't think it holds up for multiple exits. Talking in terms of probabilities, you are given P(E_i | not E_{i-1}), where E_i is the event that exit i is taken. The non-conditional exit probability is P(E_i) = P(E_i | not E_{i-1}) / P(not E_{i-1}). The predicted exit count is (1 / P(E_i)) - 1.

To get accurate exit counts, you'd have to walk down the chain of (dominating) exits and adjust probabilities/weights as you go along.

Am I overthinking things?