DAGCombiner: fold (xor (shl 1, x), -1) -> (rotl -2, x)

[majnemer]

Summary

Targets which provide a rotate make it possible to replace a sequence of
(XOR (SHL 1, x), -1) with (ROTL -2, x). This saves an instruction on
architectures like X86 and POWER(64).

[nadav]

David, the code and test case look great. The transformation is not trivial. Do you mind adding a line of comment that explains why -2 is used? Maybe an example input like 00000001 -> 11111101. Also a comment about how rotate can only pull in 1s and how large x values are undefined.

[majnemer]

• Add comments to explain the reasoning behind the transform.

[silvas]

Maybe a z3 proof in the commit message would make people feel a bit more at home with this also?

[majnemer]

In D8350#141699, @silvas wrote:

Maybe a z3 proof in the commit message would make people feel a bit more at home with this also?

I sent this out for review mainly for the SelectionDAG specific bits. I think the arithmetic behind it is pretty clear.

[meadori]

FWIW, the logic seems straight forward to me too. LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N01C)
       return DAG.getNode(ISD::XOR, SDLoc(N), VT, N0.getOperand(0),
                          DAG.getConstant(N1C->getAPIntValue() ^
                                          N01C->getAPIntValue(), VT));
   }
   // fold (xor x, x) -> 0
   if (N0 == N1)
     return tryFoldToZero(SDLoc(N), TLI, VT, DAG, LegalOperations, LegalTypes);
 
+  // fold (xor (shl 1, x), -1) -> (rotl ~1, x)
+  // Here is a concrete example of this equivalence:
+  // i16   x ==  14
+  // i16 shl ==   1 << 14  == 16384 == 0b0100000000000000
+  // i16 xor == ~(1 << 14) == 49151 == 0b1011111111111111
+  //
+  // =>
+  //
+  // i16     ~1      == 0b1111111111111110
+  // i16 rol(~1, 14) == 0b1011111111111111
+  //
+  // Some additional tips to help conceptualize this transform:
+  // - Try to see the operation as placing a single zero in a value of all ones.
+  // - There exists no value for x which would allow the result to contain zero.
+  // - Values of x larger than the bitwidth are undefined and do not require a
+  //   consistent result.
+  // - Pushing the zero left requires shifting one bits in from the right.
+  // A rotate left of ~1 is a nice way of achieving the desired result.
+  if (TLI.isOperationLegalOrCustom(ISD::ROTL, VT))
+    if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode()))
+      if (N0.getOpcode() == ISD::SHL)
+        if (auto *ShlLHS = dyn_cast<ConstantSDNode>(N0.getOperand(0)))
+          if (N1C->isAllOnesValue() && ShlLHS->isOne())
+            return DAG.getNode(ISD::ROTL, SDLoc(N), VT, DAG.getConstant(~1, VT),
+                               N0.getOperand(1));
+
   // Simplify: xor (op x...), (op y...)  -> (op (xor x, y))
   if (N0.getOpcode() == N1.getOpcode()) {
     SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N);
     if (Tmp.getNode()) return Tmp;
   }
 
   // Simplify the expression using non-local knowledge.
   if (!VT.isVector() &&

test/CodeGen/X86/xor.ll

define i32 @PR17487(i1 %tobool) {
   %conv7 = zext i1 %cmp6 to i32
   ret i32 %conv7
 
 ; X64-LABEL: PR17487:
 ; X64: andn
 ; X32-LABEL: PR17487:
 ; X32: andn
 }
+
+define i32 @test11(i32 %b) {
+  %shl = shl i32 1, %b
+  %neg = xor i32 %shl, -1
+  ret i32 %neg
+; X64-LABEL: test11:
+; X64: movl    $-2, %[[REG:.*]]
+; X64: roll    %{{.*}}, %[[REG]]
+; X32-LABEL: test11:
+; X32: movl    $-2, %[[REG:.*]]
+; X32: roll    %{{.*}}, %[[REG]]
+}