Page MenuHomePhabricator

[ValueTracking] isKnownNonZero, computeKnownBits for freeze
ClosedPublic

Authored by aqjune on Mar 7 2020, 8:50 AM.

Details

Summary

This implements support for isKnownNonZero, computeKnownBits when freeze is involved.

  br (x != 0), BB1, BB2
BB1:
  y = freeze x

In the above program, we can say that y is non-zero. The reason is as follows:

(1) If x was poison, br (x != 0) raised UB
(2) If x was fully undef, the branch again raised UB
(3) If x was non-zero partially undef, say undef | 1, freeze x will return a nondeterministic value which is also non-zero.
(4) If x was just a concrete value, it is trivial

Diff Detail

Event Timeline

aqjune created this revision.Mar 7 2020, 8:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 7 2020, 8:50 AM
aqjune updated this revision to Diff 248936.Mar 7 2020, 8:57 AM

Consider alloca/undef too, minor update

jdoerfert added inline comments.Mar 8 2020, 1:47 PM
llvm/include/llvm/Analysis/ValueTracking.h
580 ↗(On Diff #248936)

We should consider having 3 API functions now. isUndef, isPoison, isUndefOrPoison, with a common impl that takes two booleans. It makes it clearer at the call sites (IMHO).

reames requested changes to this revision.Mar 10 2020, 6:32 PM
reames added inline comments.
llvm/include/llvm/Analysis/ValueTracking.h
580 ↗(On Diff #248936)

I agree, this is a very confusing API.

llvm/lib/Analysis/ValueTracking.cpp
1875

I don't think this is worth adding. Such a freeze is trivial, and I'd expect the optimizer to simply remove it instead.

4781–4805

Please test these additions through an existing user, separate and commit separately please.

4866

Same here.

4873

We've ended up with potentially very deep recursion here. In general, ValueTracking works with a small fixed depth window. I think we need to add the same here. (Should be done as a separate patch.)

Note: I don't think we can have a cycle in the graph since we only allow constant arguments to phis.

This revision now requires changes to proceed.Mar 10 2020, 6:32 PM
aqjune marked an inline comment as done.Mar 11 2020, 11:26 AM
aqjune added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4873

Made a separate patch here: https://reviews.llvm.org/D76010

aqjune updated this revision to Diff 279554.Jul 21 2020, 9:17 AM

Leave value analysis-related parts only

aqjune edited the summary of this revision. (Show Details)Jul 21 2020, 9:23 AM
fpichet added a subscriber: fpichet.Mon, Sep 7, 3:50 PM

What is the status of this patch?
I've seen cases in a out of tree target where an optimization dependent on ValueTracking was not performed because there was a freeze in the way.

aqjune added a comment.Mon, Sep 7, 6:45 PM

What is the status of this patch?
I've seen cases in a out of tree target where an optimization dependent on ValueTracking was not performed because there was a freeze in the way.

Hi, this patch has a dependency on D84242; I'll rebase the patch.

llvm/lib/Analysis/ValueTracking.cpp
1875

KnownBits analysis on freeze can be done when the operand is partially undef. (isGuaranteedNotToBePoison vs. isGuaranteedNotToBeUndefOrPoison)

nikic added a subscriber: nikic.Tue, Sep 8, 12:35 AM
nikic added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
1875

And we can do that because "computeKnownBits" provides a "KnownBits or poison" result and not a "KnownBits or undef/poison" result, right?

aqjune added inline comments.Tue, Sep 8, 1:00 AM
llvm/lib/Analysis/ValueTracking.cpp
1875

Yes, that's true. Take this example:

y = or i8 x, 1
y.fr = freeze y

The current implementation of computeKnownBits(y) will answer that the LSB of y is one, and this means that y is either poison or any value. y can be poison because or poison, 1 is poison. However, y cannot be full undef because or x, 1 cannot return full undef.

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

aqjune added a comment.Tue, Sep 8, 7:06 AM

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

It depends on whether SelDag has a poison value - does anyone know whether it has one?

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

It depends on whether SelDag has a poison value - does anyone know whether it has one?

We have nsw/nuw/exact flags on nodes, so that means poison exists?

nikic added a reviewer: nikic.Wed, Sep 9, 2:06 AM
aqjune updated this revision to Diff 290772.Wed, Sep 9, 10:55 AM
aqjune edited the summary of this revision. (Show Details)

Rebase

It depends on whether SelDag has a poison value - does anyone know whether it has one?

We have nsw/nuw/exact flags on nodes, so that means poison exists?

I think so. Whether calling computeKnownBits (Op.getOperand(0)) is valid in SelDag seems non trivial then.

nikic accepted this revision.Wed, Sep 9, 2:13 PM

LGTM. This does seem useful as at least assumes and dominating conditions always imply non-poison.

llvm/lib/Analysis/ValueTracking.cpp
1876

Should be Depth + 1 here?

2586

Please fix this tidy warning.

aqjune updated this revision to Diff 290840.Wed, Sep 9, 4:07 PM

Address comments

aqjune marked 2 inline comments as done.Wed, Sep 9, 4:07 PM
This revision was not accepted when it landed; it landed in state Needs Review.Wed, Sep 9, 4:08 PM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.