Page MenuHomePhabricator

[SCEV] Make computeExitLimit more simple and more powerful
ClosedPublic

Authored by mkazantsev on Mar 20 2018, 3:51 AM.

Details

Summary

Current implementation of computeExitLimit has a big piece of code
the only purpose of which is to prove that after the execution of this
block the latch will be executed. What it currently checks is actually a
subset of situations where the exiting block dominates latch.

This patch replaces all these checks for simple particular cases with
domination check over loop's latch which is the only necessary condition
of taking the exiting block into consideration. This change allows to
calculate exact loop taken count for simple loops like

for (int i = 0; i < 100; i++) {
  if (cond) {...} else {...}
  if (i > 50) break;
  . . .
}

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev planned changes to this revision.Mar 20 2018, 11:42 PM

One internal fuzzer test failed, investigating.

mkazantsev requested review of this revision.Mar 21 2018, 2:40 AM

It seems that this patch is OK, it just revealed some existing bug in IndVar simplifier: it fails to forget loops at some point.

Fix for the bug triggered by this patch is https://reviews.llvm.org/D44818

mkazantsev accepted this revision.Apr 1 2018, 10:42 PM

I think it's safe to go with. Sanjoy is on vacation for few weeks and we have an agreement that he will review it after he returns. If no one has objections, I will have in merged in 24 hours.

This revision is now accepted and ready to land.Apr 1 2018, 10:42 PM
efriedma accepted this revision.Apr 2 2018, 11:55 AM
efriedma added a subscriber: efriedma.

LGTM with one minor comment.

lib/Analysis/ScalarEvolution.cpp
6921 ↗(On Diff #139098)

assert(Exit && "Exiting block must have at least one exit");

mkazantsev added inline comments.Apr 2 2018, 9:46 PM
lib/Analysis/ScalarEvolution.cpp
6921 ↗(On Diff #139098)

Fair enough, will add before commiting.

This revision was automatically updated to reflect the committed changes.

Given how many places we've had to add SE->forgetTopmostLoop after this pass, I'm wondering if this change violated some poorly specified SCEV invariant. In particular, previously had we called computeExitLimit on an exiting block in an loop inner to L we'd always conclude said exiting block was not "always executed the same number of times as the loop" because we'd bail out of the backwards climb at the header of the inner loop (which cannot have a getUniquePredecessor). What do you think?

lib/Analysis/ScalarEvolution.cpp
6895 ↗(On Diff #139098)

"far from trivial" is too vague -- can you please rewrite this bit to be more specific?

computeExitLimit's logic shouldn't care if the exiting block is inside a nested loop, as long as the condition is invariant relative to the inner loop. (This should work correctly, as far as I can tell; if it doesn't, it would be easy to fix.) So the question is if there's some invariant related to the caching?

The comment for forgetLoop says "This method should be called by the client when it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count". We could try to restrict this, bit I'm not sure what restriction would actually be useful. I can't imagine any formulation which doesn't require calling forgetLoop when a branch that exits that loop is added/removed/modified.

computeExitLimit's logic shouldn't care if the exiting block is inside a nested loop, as long as the condition is invariant relative to the inner loop. (This should work correctly, as far as I can tell; if it doesn't, it would be easy to fix.) So the question is if there's some invariant related to the caching?

Agreed -- I too was thinking of a caching invariant. For instance, maybe there is some invariant which lets us avoid caching blocks from child loops in parent's BackedgeTakenInfo instances and effectively treats child loops as black boxes.

The comment for forgetLoop says "This method should be called by the client when it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count". We could try to restrict this, bit I'm not sure what restriction would actually be useful. I can't imagine any formulation which doesn't require calling forgetLoop when a branch that exits that loop is added/removed/modified.

The kind of invariant I had in mind was as long as you don't change the *trip count* of a loop, its parents do not need to be invalidated. So unrolling or rotating a loop needs to invalidate its parent (but not its grandparent).

computeExitLimit's logic shouldn't care if the exiting block is inside a nested loop, as long as the condition is invariant relative to the inner loop. (This should work correctly, as far as I can tell; if it doesn't, it would be easy to fix.) So the question is if there's some invariant related to the caching?

Agreed -- I too was thinking of a caching invariant. For instance, maybe there is some invariant which lets us avoid caching blocks from child loops in parent's BackedgeTakenInfo instances and effectively treats child loops as black boxes.

The comment for forgetLoop says "This method should be called by the client when it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count". We could try to restrict this, bit I'm not sure what restriction would actually be useful. I can't imagine any formulation which doesn't require calling forgetLoop when a branch that exits that loop is added/removed/modified.

The kind of invariant I had in mind was as long as you don't change the *trip count* of a loop, its parents do not need to be invalidated. So unrolling or rotating a loop needs to invalidate its parent (but not its grandparent).

I think the invariant here has to be that, so long as you don't change the trip count, you don't need to invalidate it in SE. "When it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count" is an impossible contract to keep, except in the most conservative sense. How could the client know exactly how powerful SE's analysis capabilities are such that it would know whether it has done something that would affect SE's ability to compute the trip count? How should the client know which IR values SE is relying on to compute the trip count?

I am not sure that we actually break the invariant which was preserved before. Note that all recent failures we have seen were on assert from the patch D44676. We might as well just break this invariant previously, but without this assert we did not know about it.

As for the invariant itself, SCEV assumes that CFG did not change because it keeps mapping of blocks to exit counts for these blocks. Whenever we change the CFG and, for example, change some domination relationship between blocks, we must invalidate the cache.