This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Maintain and use a loop->loop invalidation dependency
ClosedPublic

Authored by sanjoy on Sep 29 2017, 3:20 PM.

Details

Summary

This change uses the loop use list added in the previous change to remember the
loops that appear in the trip count expressions of other loops; and uses it in
forgetLoop. This lets us not scan every loop in the function on a forgetLoop
call.

With this change we no longer invalidate clear out backedge taken counts on
forgetValue. I think this is fine -- the contract is that SCEV users must call
forgetLoop(L) if their change to the IR could have changed the trip count of L;
solely calling forgetValue on a value feeding into the backedge condition of L
is not enough. Moreover, I don't think we can strengthen forgetValue to be
sufficient for invalidating trip counts without significantly re-architecting
SCEV. For instance, if we have the loop:

I = *Ptr;
E = I + 10;
do {
  // ...
} while (++I != E);

then the backedge taken count of the loop is 9, and it has no reference to
either I or E, i.e. there is no way in SCEV today to re-discover the dependency
of the loop's trip count on E or I. So a SCEV client cannot change E to (say)
"I + 20", call forgetValue(E) and expect the loop's trip count to be updated.

Event Timeline

sanjoy created this revision.Sep 29 2017, 3:20 PM
mkazantsev added inline comments.Oct 8 2017, 9:32 PM
lib/Analysis/ScalarEvolution.cpp
6566

Make this SmallPtrSetImpl to get rid of dependency on size here?

unittests/Analysis/ScalarEvolutionTest.cpp
36

Duplicating check or misprint?

sanjoy updated this revision to Diff 118887.Oct 12 2017, 11:14 PM
sanjoy marked 2 inline comments as done.
  • address review
mkazantsev edited edge metadata.Oct 13 2017, 1:32 AM

I have one real question left, why we don't use forgetLoop.

include/llvm/Analysis/ScalarEvolution.h
1269

SmallPtrSetImpl?

lib/Analysis/ScalarEvolution.cpp
6414

Why we are not using forgetLoop here?

6563

SmallPtrSetImpl?

11071

Why do we need { } here?

mkazantsev accepted this revision.Oct 13 2017, 2:20 AM

LGTM with nits inlined.

lib/Analysis/ScalarEvolution.cpp
6414

Scratch this, I've re-written the commit message and understood the point. :)

This revision is now accepted and ready to land.Oct 13 2017, 2:20 AM
This revision was automatically updated to reflect the committed changes.
sanjoy marked 3 inline comments as done.