This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Fix isKnownPredicate
ClosedPublic

Authored by skatkov on Feb 20 2018, 3:37 AM.

Details

Summary

IsKnownPredicate is updated to implement the following algorithm
proposed by @sanjoy and @mkazantsev :
isKnownPredicate(Pred, LHS, RHS) {

  1. Collect set S all loops on which either LHS or RHS depend.
  2. If S is non-empty a. Let PD be the element of S which is dominated by all other elements of S b. Let E(LHS) be value of LHS on entry of PD. To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values. Define E(RHS) in the same way. c. Let B(LHS) be value of L on backedge of PD. To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values. Define B(RHS) in the same way. d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that. e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
  3. Return true if Pred, L, R is known from ranges, splitting etc.

}
This is follow-up for https://reviews.llvm.org/D42417.

Diff Detail

Event Timeline

sanjoy requested changes to this revision.Feb 25 2018, 1:14 PM

This change definitely needs some tests.

lib/Analysis/ScalarEvolution.cpp
8779

Can we assert that this is not the case (i.e. that we never have two loops in the expression unrelated by dominance)? If yes, perhaps we can do:

#ifdef NDEBUG
for (x, y) all pairs of loops in LoopsUsed:
  assert x dom y or y dom x
#endif
MDL = std::max(LoopsUsed, <compare function using dom tree>);
8786

This lambda is lifting a lot of weight -- I think it should be a separate function and documented explicitly.

How about extracting a separate function SplitIntoInitAndPostInc that returns a tuple of an init expression, post-inc expression and loop that you call from isKnownPredicate? Please also give a simple concrete example of what's going on in the comment.

8798

Should be "other loops than L"

Same applies above.

This revision now requires changes to proceed.Feb 25 2018, 1:14 PM
skatkov updated this revision to Diff 136962.Mar 5 2018, 2:46 AM
skatkov removed subscribers: sanjoy, mkazantsev.

Updated patch to handle comments. I still have a trouble to create a unit tests for this change...
I'm trying to figure out some case when the old version did not work but new one does...

Sanjoy, if you have any suggestions I'm appreciate them.

skatkov updated this revision to Diff 136966.Mar 5 2018, 4:02 AM

By the end of the working day I was able to create one test which shows the advantage of new approach...

mkazantsev accepted this revision.Mar 11 2018, 11:04 PM

LGTM with comments inlined.

include/llvm/Analysis/ScalarEvolution.h
843

Please fix ) --> }

lib/Analysis/ScalarEvolution.cpp
8735

Better make it optional and return None here.

sanjoy accepted this revision.Mar 12 2018, 10:49 AM

lgtm (didn't review the logic based on @mkazantsev 's LGTM).

include/llvm/Analysis/ScalarEvolution.h
848

Let's drop

/// The primary goal of this function is an utility function for
/// isKnownPredicate.

for now. Statements like that don't clarify things very much, and has a tendency to get stale.

lib/Analysis/ScalarEvolution.cpp
8771

This comment should be indented.

This revision is now accepted and ready to land.Mar 12 2018, 10:49 AM
skatkov added inline comments.Mar 12 2018, 8:43 PM
lib/Analysis/ScalarEvolution.cpp
8771

Interesting that Clang format uses this indent.

skatkov updated this revision to Diff 138127.Mar 12 2018, 9:48 PM

Handled comments.

mkazantsev accepted this revision.Mar 12 2018, 9:52 PM

Looks fine.

This revision was automatically updated to reflect the committed changes.