This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Add support to deduce a PHI node being a power of 2 if each incoming value is a power of 2.
ClosedPublic

Authored by huangjd on May 3 2022, 3:50 PM.

Diff Detail

Event Timeline

huangjd created this revision.May 3 2022, 3:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 3 2022, 3:50 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
huangjd requested review of this revision.May 3 2022, 3:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 3 2022, 3:50 PM
huangjd retitled this revision from Summary: Add support to deduce a PHI node being a power of 2 if each incoming value is a power of 2. to [ValueTracking] Add support to deduce a PHI node being a power of 2 if each incoming value is a power of 2..
spatel added inline comments.May 4 2022, 3:35 AM
llvm/lib/Analysis/ValueTracking.cpp
2196

As mentioned in the earlier patch (D123748), the Depth should be limited here to prevent a compile-time explosion. If the phi has a large number of operands, this could consume a lot of time - O(Operands^Depth).

The code that this patch is copying from was added with D88276, and there is more discussion about it there.
Note that the limit was derived from this code, but it dropped the explanatory code comment:
https://github.com/llvm/llvm-project/blob/d2166076b882e38becf3657ea830ffd2b6a5695e/llvm/lib/Analysis/ValueTracking.cpp#L1574-L1606

I'm not sure why it is using std::max instead of just passing MaxAnalysisRecursionDepth - 1. If I'm seeing the tests in this patch correctly, we will not see a functional difference on either of those tests by limiting the recursion.

The other non-obvious part of this patch is the setting of the context instruction; that is copied/derived from:
D71181

All of this copying and mutation suggests that we really need to create a helper function, so the logic is consistent for phi analysis across these functions. If that isn't feasible, at least copy the code comments, so we don't have to dig all over the place to figure out why this code does what it does. :)

huangjd added inline comments.May 9 2022, 9:18 AM
llvm/lib/Analysis/ValueTracking.cpp
2196

Passing MaxAnalysisRecursionDepth - 1 leads to incorrect behavior, as it defeats the purpose of limiting the depth of recursion. Every time the code execution calls the function on this line the same depth Passing MaxAnalysisRecursionDepth - 1 is passed in, so line 2065 will never be true, and the function never terminates due to depth exceeding limit.

huangjd updated this revision to Diff 428131.EditedMay 9 2022, 10:40 AM

Added back recursion limit
Added comment on instruction context

Why was D124890 pulled back into this patch? I still think it would be better to have 2 patches to reduce risk.

huangjd updated this revision to Diff 428489.EditedMay 10 2022, 1:47 PM

Added back D124890 (now D125332)

This one looks fine to me. Wait to see if other reviewers have further comment.

huangjd updated this revision to Diff 430551.May 18 2022, 6:18 PM

Updated parent D125332

huangjd abandoned this revision.May 19 2022, 2:28 PM
huangjd reclaimed this revision.May 26 2022, 2:48 PM
huangjd updated this revision to Diff 432399.May 26 2022, 3:12 PM

Restore D124889 for review

davidxl accepted this revision.May 30 2022, 1:41 PM

looks like all comments have been addressed. Wait a few days to commit. (also abandon the duplicate https://reviews.llvm.org/D126020)

This revision is now accepted and ready to land.May 30 2022, 1:41 PM
nikic added inline comments.May 30 2022, 3:00 PM
llvm/lib/Analysis/ValueTracking.cpp
2193

Rather than requiring Q.IIQ.UseInstrInfo here, it would be better to use Q.IIQ.hasNoUnsignedWrap() etc in the function. Presence of nowrap flags is not required for all cases.

huangjd updated this revision to Diff 433209.May 31 2022, 3:31 PM
This comment was removed by huangjd.
huangjd marked an inline comment as done.May 31 2022, 3:31 PM
huangjd updated this revision to Diff 433212.May 31 2022, 3:41 PM

[ValueTracking] Relaxed requirement of UseInstrInfo in power of 2
recurrece check

nikic added inline comments.Jun 1 2022, 1:41 AM
llvm/lib/Analysis/ValueTracking.cpp
2057

Hm, I think that for recurrences, this context instruction adjustment is not necessary. I believe the reason why we need it in general for phis is that we might follow a backedge, in which case we will be working with values from a previous loop iterations. This can't happen when we're looking at Start, because it must dominate the whole loop.

2089

Similar to the nowrap cases above, can't this (and div) use OrZero || Q.IIQ.isExact(BO)?

huangjd added inline comments.Jun 2 2022, 2:30 PM
llvm/lib/Analysis/ValueTracking.cpp
2057

I saw similar usage in computeKnownBitsFromOperator. at line 1464. The comment said

... TODO: It may be correct to use the original context.  IF warranted, explore and
 add sufficient tests to cover.

I am worry about some unusual cases such as the "Start" value is actually coming from a BB dominated by PHI's BB, and matchSimpleRecurrence is not strict on checking value domination, so I would be cautious here

huangjd updated this revision to Diff 433896.Jun 2 2022, 2:51 PM

Add isExact check for power of 2 in recursion

huangjd marked an inline comment as done.Jun 2 2022, 2:52 PM
huangjd updated this revision to Diff 434903.Jun 7 2022, 11:50 AM

Updated by merging main
Just to confirm it still passes all tests

This revision was landed with ongoing or failed builds.Jun 7 2022, 11:54 AM
This revision was automatically updated to reflect the committed changes.