Page MenuHomePhabricator

[ValueTracking] usub(a, b) cannot overflow if a >= b.
ClosedPublic

Authored by fhahn on Feb 5 2020, 9:02 AM.

Details

Summary

If we know that a >= b (unsigned), usub.with.overflow(a, b) cannot
overflow. Similarly, if b > a, the same expression overflows.

Diff Detail

Event Timeline

fhahn created this revision.Feb 5 2020, 9:02 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 5 2020, 9:02 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

nikic added a comment.Feb 5 2020, 9:47 AM

My only concern here is compile-time impact. Keep in mind that this function is not just being called for usub.with.overflow, but for every sub in the IR, trying to infer the nuw flag. As isImpliedByDomCondition() only inspects the direct predecessor, that's probably fine though.

Generally we're missing a pass that can propagate conditions and assumes with non-constant operands (CVP mostly covers the constant operand case)...

fhahn updated this revision to Diff 242840.Feb 6 2020, 2:26 AM

Updated to limit isImpliedByDomCond to usub.with.overflow calls for now.

My only concern here is compile-time impact. Keep in mind that this function is not just being called for usub.with.overflow, but for every sub in the IR, trying to infer the nuw flag. As isImpliedByDomCondition() only inspects the direct predecessor, that's probably fine though.

Ah right! isImpliedByDomCondition should not be too expensive, but I've limited using it to usub.with.overflow for now.

Generally we're missing a pass that can propagate conditions and assumes with non-constant operands (CVP mostly covers the constant operand case)...

Agreed!

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

fhahn updated this revision to Diff 242841.Feb 6 2020, 2:30 AM

clang-format.

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Gerolf added a subscriber: Gerolf.Feb 6 2020, 12:22 PM

Nice. LGTM.

-Gerolf

nikic accepted this revision.Feb 6 2020, 12:36 PM

LG as well.

For what it's worth, I think doing this generally is also fine, but we should probably wait until it actually shows up in practice before enabling that.

This revision is now accepted and ready to land.Feb 6 2020, 12:36 PM
fhahn added a comment.Feb 7 2020, 2:36 AM

Thanks for taking a look!

This revision was automatically updated to reflect the committed changes.