Page MenuHomePhabricator

[SCEV][NFC] evaluateAtIteration may produce incorrect result if accuracy of evalutation point is not enough.
Needs RevisionPublic

Authored by ebrevnov on Aug 6 2019, 9:35 PM.

Details

Reviewers
reames
apilipenko
Summary

Originally these changes were part of https://reviews.llvm.org/D65276. Decided to have a separate review for changes aimed at improving evaluateAtIteration. The problem is that evaluateAtIteration can produce incorrect result under some circumstances. For example for evaluation 32-bit nested recurrence of level 2 we need to carry all calculations in 33-bits. This requirement applies to input iteration expression as well. Thus if the input iteration expression is 32-bit and we can't prove it doesn't overflow then evaluateAtIteration will give incorrect result.

Please note that we can't just discard all cases when number of bits in iteration expression is less than required. One common case which we need to support is constant. It's known that constant never overflows thus it's safe to extend it to required number of bits. There are over cases where we can prove that expression doesn't overflow.

Thanks
Evgeniy

Event Timeline

ebrevnov created this revision.Aug 6 2019, 9:35 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 6 2019, 9:35 PM
ebrevnov edited the summary of this revision. (Show Details)Aug 6 2019, 10:23 PM
ebrevnov added reviewers: reames, apilipenko.
ebrevnov updated this revision to Diff 222096.Sep 27 2019, 1:26 AM

Use alternative approach to ensure enough precision of 'It'

@apilipenko what do you think now?

ebrevnov retitled this revision from [SCEV] evaluateAtIteration may produce incorrect result if accuracy of evalutation point is not enough. to [SCEV][NFC] evaluateAtIteration may produce incorrect result if accuracy of evalutation point is not enough..Sep 27 2019, 1:28 AM
ebrevnov edited the summary of this revision. (Show Details)
reames requested changes to this revision.Oct 28 2019, 11:42 AM
reames added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
1209

Ok, I'm definitely not getting something here.

trunc(zext(y, N), M) is always equal to y when N > M and M is width of y. The zext adds zeros, then the truncate removes them.

Additionally, the comments above in the intro to this function seem to directly contradict the newly added code.

There's no test case provided to show a difference in output.

Given all of the above, I'm definitely unconvinced of this patch.

8332

This snippet is fine to land separately. This can already happen K > 1000.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
1630

This line too for same reason.

This revision now requires changes to proceed.Oct 28 2019, 11:42 AM