This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Drop cached info after late nsw/nuw flags setting
AbandonedPublic

Authored by mkazantsev on Jun 5 2018, 4:33 AM.

Details

Summary

SCEV sometimes set nuw/nsw flags to AddRecs lately. As a result, the cached data
about this AddRec may be too pessimistic. For example, we keep seeing the following
pattern over and over again:

  1. An AddRec {0,+,1} is created without any flags, and its range is set to full-set;
  2. Later, from loop iteration count, we derive nsw for this SCEV and set it;
  3. Despite that, we are unable to prove non-negativity of such SCEV basing on cached range.

The complete and comprehensive fix for this problem will be to get rid of setNoWrapsFlag at all.
We should be able to derive them in the moment of SCEV creation. However, from what I see in
the comments, this may lead to infinite recursion: we need loop iteration count to create SCEVAddRec
and we need SCEVAddRec to compute this count. We need to study thoroughly if it is possible to move
to this new model without introducing this infinite logic.

So now we propose an alternative solution which is not comprehensive, but should be good enough
in most real cases. After late setting of nsw/nuw flags, we drop all cached data related to this SCEV,
in particular ranges data, and give SCEV a chance to derive more optimistic estimations basing on the flags.

The practical outcome of that solution is that we can handle a typical case in IV widening, when
SCEV fails to prove non-negativity of the IV (even after it derived respective no-wrap flags) and cannot
widen latch condition. As result, we have trunc in loop and latch condition of narrow type, while we
could have it widened as well.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 5 2018, 4:33 AM

Can you please also add a SCEV-only test case?

lib/Analysis/ScalarEvolution.cpp
1624

Let's pull out a setNoWrapFlagsOnAddRec helper that does the right thing and has a comment explaining what's going on and what the alternatives are.

mkazantsev updated this revision to Diff 154198.Jul 5 2018, 4:11 AM

I failed to construct pure SCEV test easily, will try unit test if needed.

mkazantsev abandoned this revision.Sep 5 2018, 3:13 AM

I've just checked that this test now works fine. Apparently it was fixed somehow else, and I cannot construct another test where it matters. So let's just abandon it, not clear if it's needed anymore or not.

Test commited as NFC at rL341456.