Page MenuHomePhabricator

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

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. Current solution is to relay on getTruncateOrZeroExtend which tries to prove that overflow won't happen and optimizes out zero extension. I understand that this solution relies in implementation internals of getTruncateOrZeroExtend which is not good. I'm open for your suggestions.

Thanks
Evgeniy

Diff Detail

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.