This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] Match (add X, X) as (shl X, 1) when detecting rotate.
ClosedPublic

Authored by deadalnix on Aug 28 2019, 7:00 AM.

Diff Detail

Event Timeline

deadalnix created this revision.Aug 28 2019, 7:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 28 2019, 7:00 AM

Pattern look good to me, but i recall having disscussion in https://reviews.llvm.org/D64275#inline-576684
Granted, that is InstCombine, but what happens here if we create instruction but then fail to fold?

RKSimon added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6019

Is there any easy way that we can avoid creating nodes like this? Its purpose seems purely to be matched again later.

Pattern look good to me, but i recall having disscussion in https://reviews.llvm.org/D64275#inline-576684
Granted, that is InstCombine, but what happens here if we create instruction but then fail to fold?

The node created this way end up added to PruningList by WorklistInserter are are removed when poping the next element from the worklist in clearAddedDanglingWorklistEntries.

@RKSimon Let me try that. This will require to refactor MatchRotate quite a bit, but it may be possible.

I looked at the problem that @spatel ran into. It is not applicable to DAGCombiner, because the DAG is processed only once rather than in a loop as long as it is modified. I wouldn't be possible to change it to work like InstCombine does as there are a ton of A -> B -> A type of tranforms. That being said, it's not a good reason to add more, so it's worth looking into improving this if possible.

deadalnix updated this revision to Diff 217843.Aug 29 2019, 5:18 AM
  • Avoid creating the shift node when not stricly required.
  • Add negative tests.
deadalnix updated this revision to Diff 217916.Aug 29 2019, 9:42 AM

Tighten the checks before creating the node.

Precommit tests pls.
Please add commutative test - or is commutative.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6033

I suppose add v v implies that c can only be bitwidth-1

deadalnix updated this revision to Diff 218088.Aug 30 2019, 6:55 AM
deadalnix marked an inline comment as done.

Add tests for the commutative case.
Precommit tests.

lebedev.ri added inline comments.Aug 30 2019, 7:32 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6111

Hm, this function already handles non-shifts.
Can it simply be extended with a similar block?

deadalnix marked 3 inline comments as done.Aug 30 2019, 10:10 AM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6111

The whole function is about reconstructing shifts from something else.

RKSimon accepted this revision.Aug 30 2019, 10:48 AM

LGTM - cheers!

This revision is now accepted and ready to land.Aug 30 2019, 10:48 AM
lebedev.ri added inline comments.Aug 30 2019, 10:58 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6111

duh?
That is not what i was talking about.
This code already matches non-shifts - multiplications, divisions,
I'm wondering if it can be extended to also handle add's, without adding that explicit return DAG.getNode(ISD::SHL,

deadalnix marked 2 inline comments as done.Aug 30 2019, 2:01 PM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6111

But this code DOES build a shift node.

6136

This is where the shift node is built.

lebedev.ri added inline comments.Aug 30 2019, 2:12 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6136

Err, this is actually exactly what i'm saying :)
I'm simply wondering if the current implementation, i.e.

// Value and Type of the shift.
SDValue OppShiftLHS = OppShift.getOperand(0);
EVT ShiftedVT = OppShiftLHS.getValueType();

// Amount of the existing shift.
ConstantSDNode *OppShiftCst = isConstOrConstSplat(OppShift.getOperand(1));

// (add v v) -> (shl v 1)
if (OppShift.getOpcode() == ISD::SRL && OppShiftCst &&
    ExtractFrom.getOpcode() == ISD::ADD &&
    ExtractFrom.getOperand(0) == ExtractFrom.getOperand(1) &&
    ExtractFrom.getOperand(0) == OppShiftLHS &&
    OppShiftCst->getAPIntValue() == ShiftedVT.getScalarSizeInBits() - 1)
  return DAG.getNode(ISD::SHL, DL, ShiftedVT, OppShiftLHS,
                     DAG.getShiftAmountConstant(1, ShiftedVT, DL));

is the simplest solution here, or the code that is located later in the function
can be refactored to handle this new add %x, %x case too, just like it already
handles div/rem nodes?

deadalnix marked an inline comment as done.Aug 31 2019, 4:08 AM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6136

The code is written in a style where it bail when something is wrong. As a result it either need to be rewritten, or new patterns need to be added early on.

Sorry for not understanding what you were hinting at before.

lebedev.ri accepted this revision.Aug 31 2019, 4:15 AM

No further comments, thanks.

This revision was automatically updated to reflect the committed changes.