Page MenuHomePhabricator

Compute known bits using invariants

Authored by hfinkel on Jul 13 2014, 4:41 PM.



This is a large patch, but only because I had to add some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc.

The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for invariant expressions that make use of the value we're trying to learn something about, attempts to pattern match that expression, and uses the result if successful.

Part of the structure being passed around inside ValueTracking is a set of already-considered invariants. This is to prevent a query using, for example, the invariant(a == b), to recurse on itself. The context and DT params are used to find applicable invariants. An invariant needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the invariant and the context instruction are in the same block, and we need to exclude invariants from being used to simplify their own ephemeral values (those which contribute only to the invariant) because otherwise the invariant would prove its feeding comparison trivial and would be removed.

Diff Detail

Event Timeline

hfinkel updated this revision to Diff 11359.Jul 13 2014, 4:41 PM
hfinkel retitled this revision from to Compute known bits using invariants.
hfinkel updated this object.
hfinkel edited the test plan for this revision. (Show Details)
hfinkel added a reviewer: chandlerc.
hfinkel added a subscriber: Unknown Object (MLST).
hfinkel updated this revision to Diff 11360.Jul 13 2014, 9:41 PM

Same as before, but also expose the isValidInvariantForContext method for use by other passes.

hfinkel updated this revision to Diff 11396.Jul 14 2014, 10:41 AM

Added a few lines of code (and a couple of test cases) for the most trivial case: for invariant(c) we know that c == 1.

hfinkel updated this revision to Diff 11400.Jul 14 2014, 12:29 PM

Removed outdated comment.

hfinkel updated this revision to Diff 11461.Jul 15 2014, 1:05 PM

No functional change from the previous version, but I cleaned up the matching of commutative instructions ('and' and 'icmp/eq') by introducing commutative matchers (and naming a generic pattern to cover the (v, ptrtoint(v), bitcast(v)) possibilities) instead of enumerating all possible permutations.

hfinkel updated this revision to Diff 11462.Jul 15 2014, 1:19 PM

(remove the FIXME comment associated with the last update).

chandlerc added inline comments.Jul 17 2014, 11:54 AM

This kind of logic is the only part of the current invariant approach that really made me want to structure it more as an analysis pass. I feel like this is too likely to end up being a set of magical sequences that are the only ways we recognize invariants.

What do you think about separating out the logic for computing relevant invariant sets and using them completely? I'm wondering if we should essentially have an invariant "analysis" which constitutes the interface that transformations can query. This might include:

  • Binding the context and dominance queries away from the user code behind a single API.
  • Supporting use cases where we do an expensive search of invariants first, and then query those invariants repeatedly. I'm specifically thinking we might reverse the pattern and build from the roots up.
hfinkel updated this revision to Diff 11628.Jul 17 2014, 8:34 PM

Rebased and use SmallPtrSet instead of DenseSet.

hfinkel updated this revision to Diff 11695.Jul 20 2014, 11:57 AM

Renamed to llvm.assume.

hfinkel updated this revision to Diff 11930.Jul 27 2014, 11:21 PM

Updated for AssumptionTracker (so we no longer search for @llvm.assume users).

hfinkel accepted this revision.Sep 7 2014, 1:33 PM
hfinkel added a reviewer: hfinkel.

(will close)

This revision is now accepted and ready to land.Sep 7 2014, 1:33 PM
hfinkel closed this revision.Sep 7 2014, 1:33 PM