[DAGCombiner] Create rotates more aggressively

[kparzysz]

Summary

The DAG combiner can recognize a pattern of ORed shifts that evaluate to a bit rotation. When the rotation is ORed with another value, the OR operations can get reassociated in such a way that the rotation will no longer be identified. This patch implements a more aggressive analysis of OR operations to detect rotation patterns.

[kparzysz]

Rebased on top of D47725.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4893

Please use while (!WorkQ.empty()) instead of this for loop.

4928–4929

This check is redundant.

4933

Could you sort the nodes so that shifts with the same LHS end up together, and use that to change this loop into something that isn't O(N^2)?

4942

Use of "break" here is weird; it breaks out of the inner loop, but not the outer loop.

I'd like to see a testcase with multiple rotates or'ed together.

[kparzysz]

Changed pair-matching to work on smaller segments (only on shifts of the same value).

Added a testcase of rotates ORed with other rotates, or with unrelated operations.

[kparzysz]

Ping.

[lebedev.ri]

Is this related to D47681 ?
This only has tests for Hexagon, can you please also add test[s] for X86, maybe AArch64?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4892

You can do

std::queue<SDValue, SmallVector<SDValue, 8>> WorkQ;

to get the usual small-size-optimization benefits.

4908

I would think you'd want DenseMap here.

[kparzysz]

This patch and the one you mentioned coincidentally both apply to rotates, but there wasn't any coordination between them.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4892

SmallVector doesn't have pop_front, so that won't work.

[kparzysz]

Responded to comments, added x86-64 testcase.

[lebedev.ri]

In D47735#1135475, @kparzysz wrote:

This patch and the one you mentioned coincidentally both apply to rotates, but there wasn't any coordination between them.

What i guess i was asking, there is no overlap, they are working on a slightly different problems, although related to rotates.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4892

Right, i was thinking of std::stack, not queue, sorry.

test/CodeGen/X86/rotate-multi.ll

1 ↗

(On Diff #151750)

X86(and most others) tests mostly use utils/update_llc_test_checks.py

[kparzysz]

test/CodeGen/X86/rotate-multi.ll

1 ↗

(On Diff #151750)

The output looks worse: it checks almost every instruction and has specific register names (outside of argument registers).

[RKSimon]

test/CodeGen/X86/rotate-multi.ll

1 ↗

(On Diff #151750)

But its much less likely to allow mistakes to get through. Plus on x86 its often very useful to check all the surrounding code as that often hides issues.

Once the test file is finalised best practice is to use update_llc_test_checks on it against trunk, commit that and then update the patch to show the codegen diff.

Also, your RUN line should use a triple, not an arch.

[kparzysz]

Updated x86 testcase.

[kparzysz]

Ping.

[kparzysz]

Ping.

[kparzysz]

Ping.

[RKSimon]

Please can you add the tests to trunk with the current codegen and rebase this patch to show the codegen diff.

[kparzysz]

Rebased on top of trunk.

[spatel]

Assuming we're not too far off from adding IR intrinsics to represent rotate ops (D49242), would transforming to those intrinsics in IR take care of the motivating problem?

[kparzysz]

At the moment D49242 expands these intrinsics into individual DAG operations. If the intrinsics were transformed into ROTL, and if instcombine could reassociate "or" operations to expose more fshl opportunities, then I guess it would be sufficient.

A benefit of having it in the DAG combiner is that it could handle IR generators that have not generated funnel shifts.

[spatel]

In D47735#1163728, @kparzysz wrote:

At the moment D49242 expands these intrinsics into individual DAG operations. If the intrinsics were transformed into ROTL, and if instcombine could reassociate "or" operations to expose more fshl opportunities, then I guess it would be sufficient.

A benefit of having it in the DAG combiner is that it could handle IR generators that have not generated funnel shifts.

The next steps as I see it after D49242:

1. Convert the intrinsics directly to ROTL/ROTR nodes (this should be a ~2 line patch in SelectionDAGBuilder).
2. Expose the intrinsic as clang or other front-end builtins (the first of these will be builtin_rotate* rather than the more general builtin_funnel_shift).
3. Add simplifications/folds/analysis for the intrinsics to IR passes.
4. Canonicalize to the intrinsics in instcombine.

So if these rotate ops can be created/matched sooner (and likely more easily) in IR, then I think it's a better investment to get those intrinsics into the IR rather than trying to put the patterns back together again here in the DAG.

[RKSimon]

@kparzysz Do we still need this? Does the IR funnel shift work that @spatel did last year make this redundant?

[kparzysz]

One goal was to be able to generate rol-and-accumulate instruction (on Hexagon), specifically for the accumulate operation being | (see f11 in rotate.ll). For the C code we still don't generate it:

unsigned blah(unsigned s, unsigned x) {
  return s | (x << 27) | (x >> 5);
}

Using clang -S -target hexagon -O2 fs.c -o - gives

{
        r0 |= asl(r1,#25)
}
{
        r0 |= lsr(r1,#7)
        jumpr r31
}

What we'd want is r0 |= rol(r1,#7).

[spatel]

In D47735#1404861, @kparzysz wrote:

One goal was to be able to generate rol-and-accumulate instruction (on Hexagon), specifically for the accumulate operation being | (see f11 in rotate.ll). For the C code we still don't generate it:

unsigned blah(unsigned s, unsigned x) {
  return s | (x << 27) | (x >> 5);
}

We need reassociation to happen in the IR optimizer if we want to recognize this as rotate (there could be any number of intermediate ops separating the 2 halves of the rotate):

define i32 @blah(i32 %x, i32 %s) {
  %shl = shl i32 %x, 27
  %or = or i32 %shl, %s
  %shr = lshr i32 %x, 5
  %or1 = or i32 %or, %shr <--- the 1st 'or' is between the rotated halves
  ret i32 %or1
}

D45842 was hoping to do something like that too. Note also that we don't currently canonicalize shl/shr/or with a constant shift amount to a rotate because that wasn't noted as a problem case, but this example suggests that we should do that.

[kparzysz]

Are you opposed to having this done in the DAG combiner?

[spatel]

In D47735#1406249, @kparzysz wrote:

Are you opposed to having this done in the DAG combiner?

Looking back at the comments from July 2018 - we have completed most of those tasks (in particular, we don't just expand the intrinsics now). So I think it would be nicer to get this part done with 'opt -reassociate', but I can't commit to doing that work myself immediately, so I can't be too opposed. :)

@efriedma - you started reviewing this, so I assume you're ok with a DAG patch. Does the introduction of the funnel shift intrinsics change your opinion of the implementation strategy?

[efriedma]

I think the general approach is still fine. Given we have funnel shifts, we might want to reassociate to form funnel shifts, rather than just rotates, on targets which have native funnel shift instructions. (We'd still want to prefer rotates where possible, I think.)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4913

getNodeId()?

[kparzysz]

Changed getIROrder to getNodeId.

This patch uses MatchRotate to do the actual matching, so it's only going to look for opportunities to create a rotate. Maybe that function should be replaced with MatchRotateOrFunnelShift in a future patch.

[kparzysz]

Ping.

[RKSimon]

Please can you commit the rotate-multi.ll test files with trunk's current codegen, and rebase this patch to show the codegen delta?

[RKSimon]

In D47735#1428262, @RKSimon wrote:

Please can you commit the rotate-multi.ll test files with trunk's current codegen, and rebase this patch to show the codegen delta?

And the additional rotate.ll tests as well - cheers!

[kparzysz]

Oof, I somehow missed the comments... :o

Committed the test cases (with checks against current trunk) in r356683.

[lebedev.ri]

In D47735#1438183, @kparzysz wrote:

Oof, I somehow missed the comments... :o

Committed the test cases (with checks against current trunk) in r356683.

.. and rebase this diff to show the changes?

[lebedev.ri]

I have a question: why do we want to do this here, in the backend?
Does back-end itself create these patterns?
Now that we have funnel-shift, we really really should be doing this in the middle-end.
In particular, yes, the reassoc pass may need some work. That did come up previously.

[kparzysz]

Rebased on top of the pre-committed testcases.

[kparzysz]

There can be many changes to the compiled code between the IR combiner and the DAG combiner, so these patterns can certainly appear before DAG combining takes place. Also, we already combine for rotates in the DAG, this patch only makes it more comprehensive.

[kparzysz]

Ping.

[kparzysz]

Ping.

[lebedev.ri]

After thinking about it, i think it may make sense to have this after all.
I left some comments.

Also, it would be good to have some compile-time stats comparison here.
I really think you want do add some safety limits from the getgo.
E.g. would it make sense to have more than 8 levels of these ors?
More than 256 nodes? Etc.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4980–4981

Do you want to assert that you start with ISD::OR?

4985

This comment should be next to the loop itself.
It would be best to explain the data structures here instead.

4997–5008

Can you not do this

if (Opc == ISD::SHL || Opc == ISD::SRL)
  OpMap[V.getOperand(0)->getNodeId()].push_back(I);

inside

} else
  OredOps.push_back(V);

?

One less loop.

5002

// for each shifted value, create a list of shifts.

5003

This data structure really needs a better name/description.

5019–5020

I'm not sure whether or not auto is good here..

5022

Do we care about the order within those two groups? Is this still good in reverse-iteration mode?

5023–5026

llvm::partition_point()?

5028–5030

I'm not sure what is going on here, would be good to have a high-level description comment.

5033

Early continue?

5050

Likewise, this really needs to have a high-level description comment.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
     SDValue buildSqrtNROneConst(SDValue Op, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue buildSqrtNRTwoConst(SDValue Op, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                bool DemandHighBits = true);
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
+    SDNode *ReassociateOrForRotate(SDValue Op0, SDValue Op1, const SDLoc &dl);
     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDNode *MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
     SDValue MatchLoadCombine(SDNode *N);
     SDValue ReduceLoadWidth(SDNode *N);
     SDValue ReduceLoadOpStoreWidth(SDNode *N);
SDValue DAGCombiner::visitOR(SDNode *N) {
   // Simplify: (or (op x...), (op y...))  -> (op (or x, y))
   if (N0.getOpcode() == N1.getOpcode())
     if (SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N))
       return Tmp;
 
   // See if this is some rotate idiom.
   if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N)))
     return SDValue(Rot, 0);
+  // If N0 or N1 are themselves ORs, there is still a potential for a rotate
+  // whose parts got reassociated with some other stuff.
+  if (N0.getOpcode() == ISD::OR || N1.getOpcode() == ISD::OR)
+    if (SDNode *Or = ReassociateOrForRotate(N0, N1, SDLoc(N)))
+      return SDValue(Or, 0);
 
   if (SDValue Load = MatchLoadCombine(N))
     return Load;
 
   // Simplify the operands using demanded-bits information.
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   return SDValue();
 }
 
+SDNode *DAGCombiner::ReassociateOrForRotate(SDValue Op0, SDValue Op1,
+                                            const SDLoc &dl) {
+  EVT VT = Op0.getValueType();
+  if (!hasOperation(ISD::ROTL, VT) && !hasOperation(ISD::ROTR, VT))
+    return nullptr;
+
+  // Expand all single-use ORs into a list (OredOps).
+  SmallVector<SDValue,8> WorkQ = { Op0, Op1 };
+  SmallVector<SDValue,8> OredOps;
+  for (unsigned i = 0; i != WorkQ.size(); ++i) {
+    SDValue V = WorkQ[i];
+    if (V.getOpcode() == ISD::OR && V.hasOneUse()) {
+      WorkQ.push_back(V.getOperand(0));
+      WorkQ.push_back(V.getOperand(1));
+    } else
+      OredOps.push_back(V);
+  }
+
+  // Sort the ORed values with respect to the opcodes. This is to isolate
+  // the SHL operations into one contiguous block and same for SRL.
+  auto OpcOrder = [](SDValue A, SDValue B) {
+    // SHL < SRL < ...
+    unsigned OA = A.getOpcode(), OB = B.getOpcode();
+    if (OA == ISD::SHL)
+      return true;
+    if (OB == ISD::SHL)
+      return false;
+    if (OA == ISD::SRL)
+      return true;
+    if (OB == ISD::SRL)
+      return false;
+    return OA < OB;
+  };
+  std::stable_sort(OredOps.begin(), OredOps.end(), OpcOrder);
+
+  // Find the number of SHLs and SRLs.
+  auto TmpL = find_if(OredOps,
+                      [](SDValue V) { return V.getOpcode() != ISD::SHL; });
+  unsigned LeftCount = std::distance(OredOps.begin(), TmpL);
+  auto TmpR = find_if(make_range(OredOps.begin()+LeftCount, OredOps.end()),
+                      [](SDValue V) { return V.getOpcode() != ISD::SRL; });
+  unsigned TotalCount = std::distance(OredOps.begin(), TmpR);
+
+  // If there is at least one left and right shift, do pairwise matching.
+  if (LeftCount == 0 || LeftCount == TotalCount)
+    return nullptr;
+
+  bool CreatedRotate = false;
+  for (unsigned L = 0; L != LeftCount; ++L) {
+    for (unsigned R = LeftCount; R != TotalCount; ++R) {
+      if (!OredOps[R])
+        continue;
+      // If a rotate was generated, nullify original pieces and append
+      // the rotate to the list.
+      if (SDNode *T = MatchRotate(OredOps[L], OredOps[R], dl)) {
+        OredOps.push_back(SDValue(T, 0));
+        OredOps[L] = OredOps[R] = SDValue();
+        CreatedRotate = true;
+        break;
+      }
+    }
+  }
+
+  // All pairs of left-right shifts have been examined. Now, re-package
+  // the values back into an OR tree.
+  if (!CreatedRotate)
+    return nullptr;
+
+  auto OredEnd = remove_if(OredOps, [](SDValue V) { return !bool(V); });
+  unsigned Size = OredEnd - OredOps.begin();
+  while (Size != 1) {
+    for (unsigned i = 0; i != Size/2; ++i)
+      OredOps[i] = DAG.getNode(ISD::OR, dl, VT, OredOps[2*i], OredOps[2*i+1]);
+    if (Size % 2 != 0) {
+      OredOps[Size/2+1] = OredOps[Size-1];
+      Size = Size/2 + 1;
+    } else
+      Size /= 2;
+  }
+
+  // The last remaining op is the root.
+  return OredOps[0].getNode();
+}
+
 /// Match "(X shl/srl V1) & V2" where V2 may not be present.
 bool DAGCombiner::MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask) {
   if (Op.getOpcode() == ISD::AND) {
     if (DAG.isConstantIntBuildVectorOrConstantInt(Op.getOperand(1))) {
       Mask = Op.getOperand(1);
       Op = Op.getOperand(0);
     } else {
       return false;
     }
   }
 
   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
     Shift = Op;
     return true;
   }
 
   return false;
 }
 
 // Return true if we can prove that, whenever Neg and Pos are both in the
 // range [0, EltSize), Neg == (Pos == 0 ? 0 : EltSize - Pos).  This means that
 // for two opposing shifts shift1 and shift2 and a value X with OpBits bits:
 //
 //     (or (shift1 X, Neg), (shift2 X, Pos))
 //
 // reduces to a rotate in direction shift2 by Pos or (equivalently) a rotate
 // in direction shift1 by Neg.  The range [0, EltSize) means that we only need
 // to consider shift amounts with defined behavior.
 static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize,
                            SelectionDAG &DAG) {
   // If EltSize is a power of 2 then:
   //
   //  (a) (Pos == 0 ? 0 : EltSize - Pos) == (EltSize - Pos) & (EltSize - 1)
   //  (b) Neg == Neg & (EltSize - 1) whenever Neg is in [0, EltSize).
   //
   // So if EltSize is a power of 2 and Neg is (and Neg', EltSize-1), we check
   // for the stronger condition:
   //
   //     Neg & (EltSize - 1) == (EltSize - Pos) & (EltSize - 1)    [A]
   //
   // for all Neg and Pos.  Since Neg & (EltSize - 1) == Neg' & (EltSize - 1)
   // we can just replace Neg with Neg' for the rest of the function.
   //
   // In other cases we check for the even stronger condition:
   //
   //     Neg == EltSize - Pos                                    [B]
   //
   // for all Neg and Pos.  Note that the (or ...) then invokes undefined
   // behavior if Pos == 0 (and consequently Neg == EltSize).
   //
   // We could actually use [A] whenever EltSize is a power of 2, but the
   // only extra cases that it would match are those uninteresting ones
   // where Neg and Pos are never in range at the same time.  E.g. for
   // EltSize == 32, using [A] would allow a Neg of the form (sub 64, Pos)
   // as well as (sub 32, Pos), but:
   //
   //     (or (shift1 X, (sub 64, Pos)), (shift2 X, Pos))
   //
   // always invokes undefined behavior for 32-bit X.
   //
   // Below, Mask == EltSize - 1 when using [A] and is all-ones otherwise.
   unsigned MaskLoBits = 0;
   if (Neg.getOpcode() == ISD::AND && isPowerOf2_64(EltSize)) {
     if (ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(1))) {
       KnownBits Known;
       DAG.computeKnownBits(Neg.getOperand(0), Known);
       unsigned Bits = Log2_64(EltSize);
       if (NegC->getAPIntValue().getActiveBits() <= Bits &&
           ((NegC->getAPIntValue() | Known.Zero).countTrailingOnes() >= Bits)) {
         Neg = Neg.getOperand(0);
         MaskLoBits = Bits;
       }
     }
   }
 
   // Check whether Neg has the form (sub NegC, NegOp1) for some NegC and NegOp1.
   if (Neg.getOpcode() != ISD::SUB)
     return false;
   ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(0));
   if (!NegC)
     return false;
   SDValue NegOp1 = Neg.getOperand(1);
 
   // On the RHS of [A], if Pos is Pos' & (EltSize - 1), just replace Pos with
   // Pos'.  The truncation is redundant for the purpose of the equality.
   if (MaskLoBits && Pos.getOpcode() == ISD::AND) {
     if (ConstantSDNode *PosC = isConstOrConstSplat(Pos.getOperand(1))) {
       KnownBits Known;
       DAG.computeKnownBits(Pos.getOperand(0), Known);
       if (PosC->getAPIntValue().getActiveBits() <= MaskLoBits &&
           ((PosC->getAPIntValue() | Known.Zero).countTrailingOnes() >=

test/CodeGen/Hexagon/rotate.ll

 b0:
   %v0 = shl i32 %a1, 7
   %v1 = lshr i32 %a1, 25
   %v2 = or i32 %v0, %v1
   %v3 = and i32 %v2, %a0
   ret i32 %v3
 }
 
+; CHECK-LABEL: f11
+; CHECK: r0 |= rol(r1,#7)
+define dso_local i32 @f11(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v1, %a0
+  %v3 = or i32 %v2, %v0
+  ret i32 %v3
+}
+
 ; CHECK-LABEL: f12
 ; CHECK: r0 ^= rol(r1,#7)
 define dso_local i32 @f12(i32 %a0, i32 %a1) local_unnamed_addr #0 {
 b0:
   %v0 = shl i32 %a1, 7
   %v1 = lshr i32 %a1, 25
   %v2 = or i32 %v0, %v1
   %v3 = xor i32 %v2, %a0

 b0:
   %v0 = shl i64 %a1, 7
   %v1 = lshr i64 %a1, 57
   %v2 = or i64 %v0, %v1
   %v3 = and i64 %v2, %a0
   ret i64 %v3
 }
 
+; CHECK-LABEL: f16
+; CHECK: r1:0 |= rol(r3:2,#7)
+define dso_local i64 @f16(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v1, %a0
+  %v3 = or i64 %v2, %v0
+  ret i64 %v3
+}
+
 ; CHECK-LABEL: f17
 ; CHECK: r1:0 ^= rol(r3:2,#7)
 define dso_local i64 @f17(i64 %a0, i64 %a1) local_unnamed_addr #0 {
 b0:
   %v0 = shl i64 %a1, 7
   %v1 = lshr i64 %a1, 57
   %v2 = or i64 %v0, %v1
   %v3 = xor i64 %v2, %a0
   ret i64 %v3
 }
 
 attributes #0 = { norecurse nounwind readnone "target-cpu"="hexagonv60" }