This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Do not cache comparison result upon reached max depth as "equivalence". PR48725
ClosedPublic

Authored by mkazantsev on Jan 13 2021, 11:38 PM.

Details

Summary

We use EquivalenceClasses to cache the notion that two SCEVs are equivalent,
so save time in situation when A is equivalent to B and B is equivalent to C,
making check "if A is equivalent to C?" cheaper.

We also return 0 in the comparator when we reach max analysis depth to save
compile time. After doing this, we also cache them as being equivalent.

Now, imagine the following situation:

  • A is proved equivalent to B;
  • C is proved equivalent to D;
  • Comparison of A against D is proved non-zero;
  • Comparison of B against C reaches max depth (and gets cached as equivalence).

Now, before the invocation of compare(B, C), A and D belonged
to different equivalence classes, and their comparison returned non-zero.
After the the invocation of compare(B, C), equivalence classes get merged
and A, B, C and D all fall into the same equivalence class. So the comparator
will change its behavior for couple A and D, with weird consequences following it.
This comparator is finally used in std::stable_sort, and this behavior change
makes it crash (looks like it's causing a memory corruption).

Solution: this patch changes CompareSCEVComplexity to return None
when the max depth is reached. So in this case, we do not cache these SCEVs
(and their parents in the tree) as being equivalent.

Diff Detail

Event Timeline

mkazantsev created this revision.Jan 13 2021, 11:38 PM
mkazantsev requested review of this revision.Jan 13 2021, 11:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 13 2021, 11:38 PM
aqjune added inline comments.Jan 25 2021, 2:40 AM
llvm/lib/Analysis/ScalarEvolution.cpp
858

I see that the definition of Optional::operator< is as follows:

template <typename T>
constexpr bool operator<(const Optional<T> &X, const T &Y) {
  return !X || *X < Y;
}

So, this will hold if CompareSCEVComplexity returns None as well. Is this okay?

mkazantsev planned changes to this revision.Jan 27 2021, 4:30 AM
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
858

Good point! Actually it's not. Thanks for catching this.

Factored out a lambda that ensures that None comparison result does not lead to sort elements swap.

Seems fine to me.

This revision was not accepted when it landed; it landed in state Needs Review.Jan 28 2021, 9:36 PM
This revision was automatically updated to reflect the committed changes.