This is an archive of the discontinued LLVM Phabricator instance.

[ARM] Fix for PR39060
ClosedPublic

Authored by samparker on Sep 25 2018, 6:29 AM.

Details

Summary

When calculating whether a value can safely overflow for use by an icmp, we weren't checking that the value couldn't wrap around. To do this we need the icmp to be using a constant, as well as the incoming add or sub.

bugzilla report: https://bugs.llvm.org/show_bug.cgi?id=39060

Diff Detail

Event Timeline

samparker created this revision.Sep 25 2018, 6:29 AM
SjoerdMeijer added inline comments.Sep 25 2018, 8:29 AM
lib/Target/ARM/ARMCodeGenPrepare.cpp
249–302

Thanks for commenting on this, this is very useful! A few nits below.

253

can you specify what exactly the "overflowing value" in the pattern is?

254

and similarly, what the "underflowing instruction" is?

255

Thinking out loud.... I think we could be a bit more precise. Something along the lines of:

We are pattern matching a sequence of 2 instructions:

  • Instruction I is and add or sub, with a LHS, and a RHS that should be a constant C1, and
  • User of I is a compare instruction CI: the LHS is instruction I, the RHS a constant C2.

Instruction I needs to be decreasing, which is the case when instruction I as an add and C1 is negative or when I is a sub and C1 positive,
because <insert reason here>.

To determine whether wrapping occurs, we calculate a new constant C3:

C3 = abs(C1) + C2,       where C1 and C2 are zero-extend to 32 bits if necessary.

We define a new constant:

Max = ....

And overflow in C3 is okay if:

  • ...
  • ...

Thanks for suggestions Sjoerd. I've evidently had a difficult time of wrapping (pun intended) my head around this and really should have put some comments up before. Hopefully I've now also illustrated when and how we can use this.

SjoerdMeijer accepted this revision.Sep 26 2018, 2:47 AM

Thanks for clarifying! Looks good, with only a nit.

lib/Target/ARM/ARMCodeGenPrepare.cpp
274

This example plugs in numbers to show that evaluating this in different types gives different results. Perhaps a quick example too how we calculate that overflow might happen changing the result:

%a - 2 <= 254
%a <= 254 + 2
%a <= 256

we find that 256 does not fit in i8, and therefore we say this is not safe to promote.

And perhaps a note somewhere that this could all be generalised and we could be accepting the general case:

%a - %b <= %c

if we have (accurate) value range analysis available and a, b, or c are variables; I have never look at valuerange in LLVM though, and of course this definitely something for a follow up.

This revision is now accepted and ready to land.Sep 26 2018, 2:47 AM
This revision was automatically updated to reflect the committed changes.