Page MenuHomePhabricator

[DAGCombine] Simplify funnel shifts with undef/zero args to bitshifts
ClosedPublic

Authored by RKSimon on Feb 9 2019, 2:39 PM.

Details

Summary

Now that we have SimplifyDemandedBits support for funnel shifts (rL353539), we need to simplify funnel shifts back to bitshifts in cases where either argument has been folded to undef/zero.

Diff Detail

Repository
rL LLVM

Event Timeline

RKSimon created this revision.Feb 9 2019, 2:39 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 9 2019, 2:39 PM

Some thoughts.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7119 ↗(On Diff #186135)

What should be done if N2 is undef?
Pretend that it is 0, or replace the entire op with undef?

7148 ↗(On Diff #186135)

Since we can replace undef with something, e.g. 0, we should do the same if it's 0 too.

7152 ↗(On Diff #186135)

Same

7158–7159 ↗(On Diff #186135)

Do ISD::SRL / ISD::SHL implicitly take the modulo of the shift amount?

7161 ↗(On Diff #186135)

Same remark re 0.

7163 ↗(On Diff #186135)

Same remark re 0.

nikic added a subscriber: nikic.Feb 10 2019, 1:13 AM
nikic added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7119 ↗(On Diff #186135)

Pretending it is zero would be consistent with InstSimplify: https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/InstructionSimplify.cpp#L5129

Replacing with undef is not legal (consider for example N0=0, N1=0, which has zero as the only possible result, regardless of N2).

7148 ↗(On Diff #186135)
RKSimon marked 2 inline comments as done.Feb 10 2019, 3:34 AM
RKSimon added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7148 ↗(On Diff #186135)

Sure, I can add support for zero as well.

7158–7159 ↗(On Diff #186135)

Ah good point! Will limit this to PowerOf2 cases that have passed the maskediszero above

lebedev.ri added inline comments.Feb 10 2019, 4:40 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7158–7159 ↗(On Diff #186135)

By modulo meant that funnel shift implicitly urem's the shift amount by the bitwidth.
So

%r = fshl %a, 0, %c
  =>
%r = shl %a, %c

is a miscompile.

I.e. this should be folded to

%r = fshl i32 %a, 0, %c
  =>
%cmodwidth = and i32 %c, 31 ; <- !!!
%r = shl i32 %a, %cmodwidth
RKSimon updated this revision to Diff 186153.Feb 10 2019, 8:07 AM
RKSimon retitled this revision from [DAGCombine] Simplify funnel shifts with undef args to bitshifts to [DAGCombine] Simplify funnel shifts with undef/zero args to bitshifts.
RKSimon edited the summary of this revision. (Show Details)

Add support for folding cases with zero arguments.

Limited the variable cases to where we know the shift is in range

I'd prefer to deal with the undef shift amounts in a separate patch as that's mostly separate from this fold logic.

lebedev.ri accepted this revision.Feb 10 2019, 8:19 AM

Looks ok to me.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7169 ↗(On Diff #186153)

Hmm, if FeatureSlowSHLD is set, or we have BMI2 (and thus sh[lr]x, not depending on %cl reg)?
Also, to be noted sub 32, n should get folded to neg n, IIRC.

This revision is now accepted and ready to land.Feb 10 2019, 8:19 AM
nikic added inline comments.Feb 10 2019, 8:26 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7133 ↗(On Diff #186153)

Maybe pass AllowUndefs=true, as we want to deal with both undef/zero anyway?

7155 ↗(On Diff #186153)

Should be s/lshr/shl in the two latter comments.

7171 ↗(On Diff #186153)

Shouldn't this be either setting the BitWidth - Log2_32(BitWidth) high bits, or maybe use getBitsSetFrom() instead? I think right now this is checking too few bits.

RKSimon marked an inline comment as done.Feb 10 2019, 8:54 AM
RKSimon added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
7171 ↗(On Diff #186153)

Nice catch!

This revision was automatically updated to reflect the committed changes.