[RISCV] Reorder (and/or/xor (shl X, C1), C2) if we can form ANDI/ORI/XORI.

[craig.topper]

Summary

InstCombine and DAGCombine prefer to keep shl before binops.

This patch teaches isel to convert to (shl (and/or/xor X, C1 >> C2), C2)
if (C1 >> C2) is a simm12. The idea was taken from X86's isel code.

There's a special case implemented for a sext_inreg between the
shift and the binop.

[luismarques]

LGTM. Nice!

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.h

public:
 
   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
                                     std::vector<SDValue> &OutOps) override;
 
   bool SelectAddrFrameIndex(SDValue Addr, SDValue &Base, SDValue &Offset);
   bool SelectFrameAddrRegImm(SDValue Addr, SDValue &Base, SDValue &Offset);
   bool SelectAddrRegImm(SDValue Addr, SDValue &Base, SDValue &Offset);
 
+  bool tryShrinkShlLogicImm(SDNode *Node);
+
   bool selectShiftMask(SDValue N, unsigned ShiftWidth, SDValue &ShAmt);
   bool selectShiftMaskXLen(SDValue N, SDValue &ShAmt) {
     return selectShiftMask(N, Subtarget->getXLen(), ShAmt);
   }
   bool selectShiftMask32(SDValue N, SDValue &ShAmt) {
     return selectShiftMask(N, 32, ShAmt);
   }
 

llvm/lib/Target/RISCV/RISCVISelDAGToDAG.cpp

void RISCVDAGToDAGISel::selectVSETVLI(SDNode *Node) {
 
   SmallVector<SDValue, 3> Ops = {VLOperand, VTypeIOp};
   if (HasChain)
     Ops.push_back(Node->getOperand(0));
 
   ReplaceNode(Node, CurDAG->getMachineNode(Opcode, DL, VTs, Ops));
 }
 
+bool RISCVDAGToDAGISel::tryShrinkShlLogicImm(SDNode *Node) {
+  MVT VT = Node->getSimpleValueType(0);
+  unsigned Opcode = Node->getOpcode();
+  assert((Opcode == ISD::AND || Opcode == ISD::OR || Opcode == ISD::XOR) &&
+         "Unexpected opcode");
+  SDLoc DL(Node);
+
+  // For operations of the form (x << C1) op C2, check if we can use
+  // ANDI/ORI/XORI by transforming it into (x op (C2>>C1)) << C1.
+  SDValue N0 = Node->getOperand(0);
+  SDValue N1 = Node->getOperand(1);
+
+  ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N1);
+  if (!Cst)
+    return false;
+
+  int64_t Val = Cst->getSExtValue();
+
+  // Check if immediate can already use ANDI/ORI/XORI.
+  if (isInt<12>(Val))
+    return false;
+
+  SDValue Shift = N0;
+
+  // If Val is simm32 and we have a sext_inreg from i32, then the binop
+  // produces at least 33 sign bits. We can peek through the sext_inreg and use
+  // a SLLIW at the end.
+  bool SignExt = false;
+  if (isInt<32>(Val) && N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
+      N0.hasOneUse() && cast<VTSDNode>(N0.getOperand(1))->getVT() == MVT::i32) {
+    SignExt = true;
+    Shift = N0.getOperand(0);
+  }
+
+  if (Shift.getOpcode() != ISD::SHL || !Shift.hasOneUse())
+    return false;
+
+  ConstantSDNode *ShlCst = dyn_cast<ConstantSDNode>(Shift.getOperand(1));
+  if (!ShlCst)
+    return false;
+
+  uint64_t ShAmt = ShlCst->getZExtValue();
+
+  // Make sure that we don't change the operation by removing bits.
+  // This only matters for OR and XOR, AND is unaffected.
+  uint64_t RemovedBitsMask = maskTrailingOnes<uint64_t>(ShAmt);
+  if (Opcode != ISD::AND && (Val & RemovedBitsMask) != 0)
+    return false;
+
+  int64_t ShiftedVal = Val >> ShAmt;
+  if (!isInt<12>(ShiftedVal))
+    return false;
+
+  // If we peeked through a sext_inreg, make sure the shift is valid for SLLIW.
+  if (SignExt && ShAmt >= 32)
+    return false;
+
+  // Ok, we can reorder to get a smaller immediate.
+  unsigned BinOpc;
+  switch (Opcode) {
+  default: llvm_unreachable("Unexpected opcode");
+  case ISD::AND: BinOpc = RISCV::ANDI; break;
+  case ISD::OR:  BinOpc = RISCV::ORI;  break;
+  case ISD::XOR: BinOpc = RISCV::XORI; break;
+  }
+
+  unsigned ShOpc = SignExt ? RISCV::SLLIW : RISCV::SLLI;
+
+  SDNode *BinOp =
+      CurDAG->getMachineNode(BinOpc, DL, VT, Shift.getOperand(0),
+                             CurDAG->getTargetConstant(ShiftedVal, DL, VT));
+  SDNode *SLLI =
+      CurDAG->getMachineNode(ShOpc, DL, VT, SDValue(BinOp, 0),
+                             CurDAG->getTargetConstant(ShAmt, DL, VT));
+  ReplaceNode(Node, SLLI);
+  return true;
+}
+
 void RISCVDAGToDAGISel::Select(SDNode *Node) {
   // If we have a custom node, we have already selected.
   if (Node->isMachineOpcode()) {
     LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << "\n");
     Node->setNodeId(-1);
     return;
   }
 
SDNode *SLLI =
         CurDAG->getMachineNode(RISCV::SLLI, DL, VT, N0->getOperand(0),
                                CurDAG->getTargetConstant(LShAmt, DL, VT));
     SDNode *SRAI = CurDAG->getMachineNode(
         RISCV::SRAI, DL, VT, SDValue(SLLI, 0),
         CurDAG->getTargetConstant(LShAmt + ShAmt, DL, VT));
     ReplaceNode(Node, SRAI);
     return;
   }
+  case ISD::OR:
+  case ISD::XOR:
+    if (tryShrinkShlLogicImm(Node))
+      return;
+
+    break;
   case ISD::AND: {
     auto *N1C = dyn_cast<ConstantSDNode>(Node->getOperand(1));
     if (!N1C)
       break;
 
     SDValue N0 = Node->getOperand(0);
 
     bool LeftShift = N0.getOpcode() == ISD::SHL;
if (LeftShift && isShiftedMask_64(C1)) {
         SDNode *SLLI =
             CurDAG->getMachineNode(RISCV::SLLI, DL, VT, SDValue(SRLIW, 0),
                                    CurDAG->getTargetConstant(Trailing, DL, VT));
         ReplaceNode(Node, SLLI);
         return;
       }
     }
 
+    if (tryShrinkShlLogicImm(Node))
+      return;
+
     break;
   }
   case ISD::MUL: {
     // Special case for calculating (mul (and X, C2), C1) where the full product
     // fits in XLen bits. We can shift X left by the number of leading zeros in
     // C2 and shift C1 left by XLen-lzcnt(C2). This will ensure the final
     // product has XLen trailing zeros, putting it in the output of MULHU. This
     // can avoid materializing a constant in a register for C2.

llvm/test/CodeGen/RISCV/narrow-shl-cst.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=riscv32 | FileCheck %s --check-prefixes=RV32
 ; RUN: llc < %s -mtriple=riscv64 | FileCheck %s --check-prefixes=RV64
 
 define signext i32 @test1(i32 signext %x) nounwind {
 ; RV32-LABEL: test1:
 ; RV32:       # %bb.0:
+; RV32-NEXT:    ori a0, a0, 31
 ; RV32-NEXT:    slli a0, a0, 10
-; RV32-NEXT:    lui a1, 8
-; RV32-NEXT:    addi a1, a1, -1024
-; RV32-NEXT:    or a0, a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test1:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    ori a0, a0, 31
 ; RV64-NEXT:    slliw a0, a0, 10
-; RV64-NEXT:    lui a1, 8
-; RV64-NEXT:    addiw a1, a1, -1024
-; RV64-NEXT:    or a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i32 %x, 10
   %shl = or i32 %or, 31744
   ret i32 %shl
 }
 
 define signext i32 @test2(i32 signext %x) nounwind {
 ; RV32-LABEL: test2:
 ; RV32:       # %bb.0:
+; RV32-NEXT:    xori a0, a0, 31
 ; RV32-NEXT:    slli a0, a0, 10
-; RV32-NEXT:    lui a1, 8
-; RV32-NEXT:    addi a1, a1, -1024
-; RV32-NEXT:    xor a0, a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test2:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    xori a0, a0, 31
 ; RV64-NEXT:    slliw a0, a0, 10
-; RV64-NEXT:    lui a1, 8
-; RV64-NEXT:    addiw a1, a1, -1024
-; RV64-NEXT:    xor a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i32 %x, 10
   %shl = xor i32 %xor, 31744
   ret i32 %shl
 }
 
 define i64 @test3(i64 %x) nounwind {
 ; RV32-LABEL: test3:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    slli a0, a0, 8
-; RV32-NEXT:    lui a1, 15
-; RV32-NEXT:    addi a1, a1, 256
-; RV32-NEXT:    and a1, a0, a1
+; RV32-NEXT:    andi a0, a0, 241
+; RV32-NEXT:    slli a1, a0, 8
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test3:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    andi a0, a0, 241
 ; RV64-NEXT:    slli a0, a0, 40
-; RV64-NEXT:    li a1, 241
-; RV64-NEXT:    slli a1, a1, 40
-; RV64-NEXT:    and a0, a0, a1
 ; RV64-NEXT:    ret
   %and = shl i64 %x, 40
   %shl = and i64 %and, 264982302294016
   ret i64 %shl
 }
 
 define i64 @test4(i64 %x) nounwind {
 ; RV32-LABEL: test4:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    slli a0, a0, 8
-; RV32-NEXT:    lui a1, 15
-; RV32-NEXT:    addi a1, a1, 256
-; RV32-NEXT:    or a1, a0, a1
+; RV32-NEXT:    ori a0, a0, 241
+; RV32-NEXT:    slli a1, a0, 8
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test4:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    ori a0, a0, 241
 ; RV64-NEXT:    slli a0, a0, 40
-; RV64-NEXT:    li a1, 241
-; RV64-NEXT:    slli a1, a1, 40
-; RV64-NEXT:    or a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i64 %x, 40
   %shl = or i64 %or, 264982302294016
   ret i64 %shl
 }
 
 define i64 @test5(i64 %x) nounwind {
 ; RV32-LABEL: test5:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    slli a0, a0, 8
-; RV32-NEXT:    lui a1, 2
-; RV32-NEXT:    addi a1, a1, -256
-; RV32-NEXT:    or a1, a0, a1
+; RV32-NEXT:    ori a0, a0, 31
+; RV32-NEXT:    slli a1, a0, 8
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test5:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    ori a0, a0, 31
 ; RV64-NEXT:    slli a0, a0, 40
-; RV64-NEXT:    li a1, 31
-; RV64-NEXT:    slli a1, a1, 40
-; RV64-NEXT:    or a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i64 %x, 40
   %shl = or i64 %or, 34084860461056
   ret i64 %shl
 }
 
 define i64 @test6(i64 %x) nounwind {
 ; RV32-LABEL: test6:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    slli a0, a0, 8
-; RV32-NEXT:    lui a1, 15
-; RV32-NEXT:    addi a1, a1, 256
-; RV32-NEXT:    xor a1, a0, a1
+; RV32-NEXT:    xori a0, a0, 241
+; RV32-NEXT:    slli a1, a0, 8
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test6:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    xori a0, a0, 241
 ; RV64-NEXT:    slli a0, a0, 40
-; RV64-NEXT:    li a1, 241
-; RV64-NEXT:    slli a1, a1, 40
-; RV64-NEXT:    xor a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i64 %x, 40
   %shl = xor i64 %xor, 264982302294016
   ret i64 %shl
 }
 
 define i64 @test7(i64 %x) nounwind {
 ; RV32-LABEL: test7:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    slli a0, a0, 8
-; RV32-NEXT:    lui a1, 2
-; RV32-NEXT:    addi a1, a1, -256
-; RV32-NEXT:    xor a1, a0, a1
+; RV32-NEXT:    xori a0, a0, 31
+; RV32-NEXT:    slli a1, a0, 8
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test7:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    xori a0, a0, 31
 ; RV64-NEXT:    slli a0, a0, 40
-; RV64-NEXT:    li a1, 31
-; RV64-NEXT:    slli a1, a1, 40
-; RV64-NEXT:    xor a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i64 %x, 40
   %shl = xor i64 %xor, 34084860461056
   ret i64 %shl
 }
 
 define i64 @test8(i64 %x) nounwind {
 ; RV32-LABEL: test8:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    slli a0, a0, 1
 ; RV32-NEXT:    andi a1, a0, -482
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test8:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    andi a0, a0, -241
 ; RV64-NEXT:    slli a0, a0, 33
-; RV64-NEXT:    li a1, -241
-; RV64-NEXT:    slli a1, a1, 33
-; RV64-NEXT:    and a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i64 %x, 33
   %shl = and i64 %xor, -2070174236672
   ret i64 %shl
 }
 
 define i64 @test9(i64 %x) nounwind {
 ; RV32-LABEL: test9:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    slli a0, a0, 1
 ; RV32-NEXT:    ori a1, a0, -482
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test9:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    ori a0, a0, -241
 ; RV64-NEXT:    slli a0, a0, 33
-; RV64-NEXT:    li a1, -241
-; RV64-NEXT:    slli a1, a1, 33
-; RV64-NEXT:    or a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i64 %x, 33
   %shl = or i64 %xor, -2070174236672
   ret i64 %shl
 }
 
 define i64 @test10(i64 %x) nounwind {
 ; RV32-LABEL: test10:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    slli a0, a0, 1
 ; RV32-NEXT:    xori a1, a0, -482
 ; RV32-NEXT:    li a0, 0
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test10:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    xori a0, a0, -241
 ; RV64-NEXT:    slli a0, a0, 33
-; RV64-NEXT:    li a1, -241
-; RV64-NEXT:    slli a1, a1, 33
-; RV64-NEXT:    xor a0, a0, a1
 ; RV64-NEXT:    ret
   %xor = shl i64 %x, 33
   %shl = xor i64 %xor, -2070174236672
   ret i64 %shl
 }
 
 define signext i32 @test11(i32 signext %x) nounwind {
 ; RV32-LABEL: test11:
 ; RV32:       # %bb.0:
+; RV32-NEXT:    andi a0, a0, -241
 ; RV32-NEXT:    slli a0, a0, 17
-; RV32-NEXT:    lui a1, 1040864
-; RV32-NEXT:    and a0, a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test11:
 ; RV64:       # %bb.0:
 ; RV64-NEXT:    slliw a0, a0, 17
 ; RV64-NEXT:    lui a1, 1040864
 ; RV64-NEXT:    and a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i32 %x, 17
   %shl = and i32 %or, -31588352
   ret i32 %shl
 }
 
 define signext i32 @test12(i32 signext %x) nounwind {
 ; RV32-LABEL: test12:
 ; RV32:       # %bb.0:
+; RV32-NEXT:    ori a0, a0, -241
 ; RV32-NEXT:    slli a0, a0, 17
-; RV32-NEXT:    lui a1, 1040864
-; RV32-NEXT:    or a0, a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test12:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    ori a0, a0, -241
 ; RV64-NEXT:    slli a0, a0, 17
-; RV64-NEXT:    lui a1, 1040864
-; RV64-NEXT:    or a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i32 %x, 17
   %shl = or i32 %or, -31588352
   ret i32 %shl
 }
 
 define signext i32 @test13(i32 signext %x) nounwind {
 ; RV32-LABEL: test13:
 ; RV32:       # %bb.0:
+; RV32-NEXT:    xori a0, a0, -241
 ; RV32-NEXT:    slli a0, a0, 17
-; RV32-NEXT:    lui a1, 1040864
-; RV32-NEXT:    xor a0, a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: test13:
 ; RV64:       # %bb.0:
+; RV64-NEXT:    xori a0, a0, -241
 ; RV64-NEXT:    slliw a0, a0, 17
-; RV64-NEXT:    lui a1, 1040864
-; RV64-NEXT:    xor a0, a0, a1
 ; RV64-NEXT:    ret
   %or = shl i32 %x, 17
   %shl = xor i32 %or, -31588352
   ret i32 %shl
 }
 
 ; Negative test. Can't transform because the constant has a 1 in the bits
 ; cleared by the shl.