Page MenuHomePhabricator

[ValueTracking] look through bitcast of vector in computeKnownBits
ClosedPublic

Authored by spatel on Jun 17 2021, 10:03 AM.

Details

Summary

This borrows as much as possible from the SDAG version of the code (originally added with D27129 and since updated with big endian support).

In IR, we can test more easily for correctness than we did in the original patch. I'm using the simplest cases that I could find for InstSimplify - we computeKnownBits on variable shift amounts to see if they are zero or in range, so I used a shuffle to push constant elements into a vector.

The motivating x86 example from https://llvm.org/PR50123 is also here. We computeKnownBits in the caller code, but we only check if the shift amount is in range. That could be enhanced to catch the 2nd x86 test - if the shift amount is known too big, the result is 0.

Alive2 understands the datalayout and agrees that the tests here are correct - example:
https://alive2.llvm.org/ce/z/KZJFMZ

Diff Detail

Event Timeline

spatel created this revision.Jun 17 2021, 10:03 AM
spatel requested review of this revision.Jun 17 2021, 10:03 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 17 2021, 10:03 AM

Would it please be possible to either enhance comments, or port more comments from the SelectionDAG::computeKnownBits()?
It appears to match that original implementation, and seems correct, but it is hard to read/get through.

Would it please be possible to either enhance comments, or port more comments from the SelectionDAG::computeKnownBits()?
It appears to match that original implementation, and seems correct, but it is hard to read/get through.

I thought I had improved the original code comments, but it might have made it worse.

The tricky part is the calling of computeKnownBits with the shifting demanded elements vector.
The original says this:

// Collect known bits for the (larger) output by collecting the known
// bits from each set of sub elements and shift these into place.
// We need to separately call computeKnownBits for each set of
// sub elements as the knownbits for each is likely to be different.

Is this better or worse?

// Known bits are automatically intersected across demanded
// elements of a vector. So for example, if a bit is computed as 
// known zero, it must be zero across all demanded elements 
// of the vector. 
//
// For this bitcast, each demanded element of the output is 
// sub-divided across a set of smaller vector elements in the 
// source vector. To get the known bits for an entire element 
// of the output, compute the known bits for each sub-element 
// sequentially. This is done by shifting the one-set-bit demanded 
// elements parameter across the sub-elements for consecutive
// calls to computeKnownBits.
//
// The known bits of each sub-element are then extended
// and shifted into place (dependent on endian) to form the
// full result of known bits.

Thanks again for looking at this!

llvm/lib/Analysis/ValueTracking.cpp
1217

Can you use APInt::insertBits here ?

spatel added inline comments.Jun 18 2021, 4:39 AM
llvm/lib/Analysis/ValueTracking.cpp
1217

Yes - at least that's how I drafted it originally. But I made it match the existing DAG code, so we'd get more testing for both versions once this is in (there seems to be much more fuzz/bot coverage for IR than codegen).

How about a TODO that we could update both versions simultaneously?

spatel edited the summary of this revision. (Show Details)Jun 18 2021, 6:08 AM
RKSimon added inline comments.Jun 18 2021, 7:39 AM
llvm/lib/Analysis/ValueTracking.cpp
1217

Updated in rG7353beda4aa1 - there's several additional cases where we could use insertBits/extractBits that I'll deal with at another time.

spatel updated this revision to Diff 353020.Jun 18 2021, 9:02 AM

Patch updated - no logic changes from earlier rev, but:

  1. Make code comment more extensive (I'm speculating that this version is better than what I had before. If so, I can update the SDAG comment too; if not, I can paste in the existing comment from SDAG.)
  2. Use KnownBits.insertBits() to reduce code.

No objections from me - anyone else?

lebedev.ri accepted this revision.Jun 23 2021, 6:55 AM

LG, thank you.

This revision is now accepted and ready to land.Jun 23 2021, 6:55 AM
This revision was landed with ongoing or failed builds.Jun 23 2021, 8:47 AM
This revision was automatically updated to reflect the committed changes.