Page MenuHomePhabricator

[CVP] simplify phi with constant incoming values that match common variable edge values
ClosedPublic

Authored by spatel on Apr 9 2018, 11:26 AM.

Details

Summary

This is based on an example that was recently posted on llvm-dev:

void *propagate_null(void* b, int* g) {
        if (!b) {
                return 0;
        }
        (*g)++;
        return b;
}

https://godbolt.org/g/xYk3qG

The original code or constant propagation in other passes has obscured the fact that the phi can be removed completely.

There's an instcombine proposal to fix part of this at D45378, but I don't think we want instcombine doing things like that (and I'm not sure that patch is correct as-is).

Diff Detail

Repository
rL LLVM

Event Timeline

spatel created this revision.Apr 9 2018, 11:26 AM

Any idea how often this triggers in practice?

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
155 ↗(On Diff #141690)

This could potentially be improved to handle the !CommonValue case, I think, but I guess it might be tricky to find the appropriate value.

165 ↗(On Diff #141690)

I don't think you have to check this separately for each incoming block; it should be enough that CommonInst dominates the block which contains the PHI node.

fhahn added a subscriber: fhahn.Apr 9 2018, 1:44 PM
fhahn added inline comments.
test/Transforms/CorrelatedValuePropagation/phi-common-val.ll
4 ↗(On Diff #141690)

It looks like the reason we miss those cases is that we are missing the links between the null constants in the comparison and the PHI node.

Now, if we would have something like the code below, GVN could handle it.

define i8* @simplify_phi_common_value_op0(i8* %ptr, i32* %b, i8* %cmp) {
entry:
  %null.v = call i8* @llvm.ssa.copy.p0i8(i8* null)
  %isnull = icmp eq i8* %ptr, %cmp
  br i1 %isnull, label %return, label %else

else:                                             ; preds = %entry
  %lb = load i32, i32* %b
  %add = add nsw i32 %lb, 1
  store i32 %add, i32* %b
  br label %return

return:                                           ; preds = %else, %entry
  ret i8* %ptr
}

Unfortunately I don't think we have an easy way to get to that. In theory, I think should be able to annotate constants with the possible variables they are equal to, similar to what PredicateInfo does. Then we could use that to check if a constant is equal to a helpful variable. But that is a long shot and also (much) more work than this solution.

spatel added a comment.Apr 9 2018, 5:26 PM

Any idea how often this triggers in practice?

I didn't, but I added a debug stat and built test-suite -O3. This fired 94 times across 48 files.

For some context, the existing CVP phi optimization counter shows that it fired 6758 times across 680 files. That one counts both the existing threading over select transform here in CVP and any folds done by instsimplify when called from here.

Not sure how to judge this data in the larger context...rare, but not impossible, so worth the effort of looking for the pattern?

spatel updated this revision to Diff 141845.Apr 10 2018, 7:44 AM
spatel marked an inline comment as done.

Patch updated:

  1. Move the dominance check, so it only happens once. This matches the logic in InstSimplify that handles the simpler case of a phi where all incoming values are identical except for undefs.
  2. Added a debug statistic to count how often this fires.

To expand on the previous test-suite experiment, I moved the existing counter above the call to InstSimplify (that's not in this patch though). This tells us how often the phi-select transform fires vs. the common value simplification in InstSimplify. The split of the 6758 cases is: 1830 are here in CVP for the select transform and 4928 is the easy elimination of a phi with all common incoming values in InstSimplify. So we use the more complicated common value analysis of this patch about 2% (94/4928) of the time to eliminate a phi.

Seems like it triggers frequently enough to be worth doing.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
161 ↗(On Diff #141845)

if (!SQ.DT->dominates(CommonInst, P->getParent())) is probably closer to what you want; the two-instruction form actually scans the block if the two instructions are in the same BB. (We should probably get rid of the two-instruction form at some point...)

spatel updated this revision to Diff 141883.Apr 10 2018, 11:22 AM
spatel marked an inline comment as done.

Patch updated:
Fixed the call to dominates() to use the phi's block, not the phi itself.

This revision is now accepted and ready to land.Apr 10 2018, 12:02 PM
This revision was automatically updated to reflect the committed changes.

(and i have patches to start down this path if anyone is ever interested)

fhahn added a comment.Apr 11 2018, 3:34 PM

(and i have patches to start down this path if anyone is ever interested)

Looks like I am missing something here. Down which path? :)

oh phabricator email and it's inability to be consistent about putting emails in comments.
Read the thread on llvm-commits and it'll make more sense :)

fhahn added a comment.Apr 12 2018, 3:51 PM

oh phabricator email and it's inability to be consistent about putting emails in comments.
Read the thread on llvm-commits and it'll make more sense :)

Oh yes! Weirdly I still could not find it on the list.