Page MenuHomePhabricator

[GVN] Make propagateEquality look into the operand of freeze
Needs ReviewPublic

Authored by aqjune on Sep 24 2020, 4:32 AM.

Details

Summary

Given a program

 x.fr = freeze x
 c = icmp eq x.fr, y
 br c, A, B
A:
 use(x) // here

We can replace x with y.

This can be proved by case analysis.
If y is undef or poison, c is also undef or poison, so br c raises UB.
If y is a well-defined value, x.fr and y are equal, so x (which is more undefined than x) can be replaced with y.

Demonstration: https://alive2.llvm.org/ce/z/UWX2fL , https://alive2.llvm.org/ce/z/vxcMLS , https://alive2.llvm.org/ce/z/_mcXgJ

If the branch condition itself was frozen (br freeze (icmp eq x, y)), this optimization isn't valid (https://alive2.llvm.org/ce/z/X5eetc ).
If either x or y is constant, converting it into br (icmp eq (freeze x), y) will make the optimization above fire again.
InstCombine might be a good candidate for doing this preprocessing.

Diff Detail

Event Timeline

aqjune created this revision.Sep 24 2020, 4:32 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 24 2020, 4:32 AM
aqjune requested review of this revision.Sep 24 2020, 4:32 AM
aqjune edited the summary of this revision. (Show Details)Sep 24 2020, 4:32 AM

On a related note, did we ever make any progress on the issue of propagating equalities on pointers?

llvm/lib/Transforms/Scalar/GVN.cpp
2000–2001

I guess favoring "prefer the non-freeze" over "prefer the oldest" is a heuristic?

aqjune added inline comments.Sep 24 2020, 12:08 PM
llvm/lib/Transforms/Scalar/GVN.cpp
2000–2001

Yes. I chose the heuristic because replacing non-freeze with freeze may cause later optimizations that are unaware of freeze.

About pointer equality propagation - @fhahn added canReplacePointersIfEqual at https://reviews.llvm.org/D85524. Would it be good if I update GVN to use this function?

fhahn added a comment.Sep 24 2020, 1:30 PM

About pointer equality propagation - @fhahn added canReplacePointersIfEqual at https://reviews.llvm.org/D85524. Would it be good if I update GVN to use this function?

I have some patches for GVN & CVP, just need to find some time to get them ready. Should hopefully happen soon.

nikic added inline comments.Sep 25 2020, 1:18 PM
llvm/lib/Transforms/Scalar/GVN.cpp
2006

Won't something fishy happen here if LHS and RHS are swapped, but LHSFr still refers to the old LHS?

aqjune updated this revision to Diff 294490.Sep 26 2020, 5:17 AM

Do not replace freeze's operand with rhs if rhs is also freeze

aqjune added inline comments.Sep 26 2020, 5:21 AM
llvm/lib/Transforms/Scalar/GVN.cpp
2006

Yes, it might have caused a problem; LHSFr should have been updated.
But, allowing this transformation when LHS and RHS were both freeze seemed problematic as well - its benefit wasn't clear. So I fixed this patch to simply be disabled in that case.
Added a few negative tests for such case.