This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Known bits support for unsigned saturating add/sub
ClosedPublic

Authored by nikic on Feb 17 2019, 10:37 AM.

Details

Summary

This adds known bits support for the unsigned saturating add/sub intrinsics. The procedure is basically:

  1. Compute known bits for a normal add/sub with one extra bit to capture the carry-out.
  2. If known overflow, use the saturation value (all ones or zero).
  3. If known no overflow, use the add/sub result.
  4. If unknown overflow: For additions we can preserve leading ones, because either there is no carry into the ones and they stay, or there is one, the result overflows and all ones is used (which also has leading ones). Additionally we preserve ones in the add result, as we're selecting between the add result and all ones. For subtractions the situation is the same but with zeros instead of ones.

I'm only handling the unsigned case here as it is simpler. It's likely not worthwhile having known bits for the signed cases at all, as we just can't get a lot of information there.

Diff Detail

Event Timeline

nikic created this revision.Feb 17 2019, 10:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 17 2019, 10:37 AM
spatel added inline comments.Feb 19 2019, 6:59 AM
lib/Analysis/ValueTracking.cpp
1540–1546

This is more accurate than what we currently do in computeOverflowForUnsignedAdd(), right? Can we adjust that existing API to use this method and then call it?

nikic updated this revision to Diff 188766.Feb 28 2019, 11:34 AM

Simplify implementation: Remove checks for overflow, relying on InstCombine to handle the always/never overflow cases. Focus on only the maybe overflow case here.

spatel accepted this revision.Feb 28 2019, 3:35 PM

LGTM

This revision is now accepted and ready to land.Feb 28 2019, 3:35 PM
This revision was automatically updated to reflect the committed changes.