This is an archive of the discontinued LLVM Phabricator instance.

[knownbits] Preserve known bits for small shift recurrences
ClosedPublic

Authored by reames on Feb 10 2021, 10:58 AM.

Details

Summary

The motivation for this is that I'm looking at an example that uses shifts as induction variables. There's lots of other omissions, but one of the first I noticed is that we can't compute tight known bits. (This indirectly causes SCEV's range analysis to produce very poor results as well.)

One specific question to reviewers. This patch essentially treats all shifts as if they were not exact/nsw/nuw. This is a valid interpretation, but I'm concerned it might differ from that taken elsewhere in the optimizer in a problematic way. What is the best practice for this in known bits computation?

Compile time wise, this should be reasonable. We locally match the recurrence using simple IR pattern matching, and only recurse on the operand once we found a recurrence.

Diff Detail

Event Timeline

reames created this revision.Feb 10 2021, 10:58 AM
reames requested review of this revision.Feb 10 2021, 10:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 10 2021, 10:58 AM
nikic added inline comments.Feb 10 2021, 11:25 AM
llvm/lib/Analysis/ValueTracking.cpp
1258

Why do we need to do this both starting from the shifts and starting from the phi? The existing code for add recurrences only starts from phis.

reames added inline comments.Feb 10 2021, 11:44 AM
llvm/lib/Analysis/ValueTracking.cpp
1258

Great question! Turns out I don't, I just never thought to check after adding the phi logic. Will remove these three call sites.

reames updated this revision to Diff 322780.Feb 10 2021, 12:02 PM

Remove unneeded lines as pointed out by Nikita.

nikic added inline comments.Feb 10 2021, 2:51 PM
llvm/lib/Analysis/ValueTracking.cpp
1031

The context instruction here needs to be adjusted to the terminator of the block for the incoming value StartV. Context can't be preserved when looking through phis.

1387

The surrounding code here is already handling other types of recurrences of the same form -- combining it with RefineRecurrence is rather odd, because it does it's own recurrence matching that is partially redundant with the code here. I think these should be integrated, or at least factored differently. The scaffolding here should work for the shift case as well (restricted to LL == I, as for Sub below), just with different KnownBits logic being applied.

One specific question to reviewers. This patch essentially treats all shifts as if they were not exact/nsw/nuw. This is a valid interpretation, but I'm concerned it might differ from that taken elsewhere in the optimizer in a problematic way. What is the best practice for this in known bits computation?

I think this is okay because IIUC analyses in ValueTracking (computeKnownXX/isKnownXX) can answer anything if the value was poison.
For example, isGEPKnownNonNull(I) is returning true if I = gep inbounds X, ofs where ofs > 0.
Users of the analyses should assume that the value can be poison; this is consistent with the recent change in the definition of nonnull/align attribute.

reames added inline comments.Feb 11 2021, 10:23 AM
llvm/lib/Analysis/ValueTracking.cpp
1031

In this particular case, I believe the current usage is actually correct. The general problem with phis is that you can end up traversing a value which is not control dependent on the conditions controlling the original context. In this particular case, we know that the phi dominates the binop which dominates the original context (or at least it had better), and thus we should be okay to preserve the initial context.

Having said all that, I hadn't intended to be fancy here and don't care about the potential quality gain from preserving the context. I'm going to switch to using the phi one as a defensive programming measure anyways. It's much more obviously correct.

1387

I acknowledge this ends up being slightly odd for this caller. I want to preserve the matching logic structure anyways. Specifically, immediately after this lands, I have several other use cases for recognizing shift recurrences.

If you really want, I can invert and generalize the existing code here and defer the addition of the new matcher to a following patch. I wouldn't bother myself, but don't care strongly enough to really argue against it either.

reames updated this revision to Diff 323075.Feb 11 2021, 10:44 AM

Adjust context instruction.

Another diff updated expected shortly. Going to land tests, and rebase. Also want to try out the code structure suggested by Nikita to see how much cleaner that is. Depending on that, may update that as well.

reames updated this revision to Diff 323082.Feb 11 2021, 11:08 AM

Rebase over landed tests and integrate into single remaining caller as suggested by Nikita.

nikic accepted this revision.Feb 11 2021, 12:16 PM

LGTM

llvm/lib/Analysis/ValueTracking.cpp
1031

Yeah, I think you're right that keeping the context instruction would be correct in this case.

1411

nit: switch (

llvm/test/Analysis/ValueTracking/shift-recurrence-knownbits.ll
64

I'd suggest another negative case where the wrong operand of the shift is used (lshr i64 C, %phi style).

And another positive test where the order of the phi operands is swapped.

This revision is now accepted and ready to land.Feb 11 2021, 12:16 PM