Add bswap, rotl, and rotr nodes

Add dag combiner code to recognize rotl, rotr
Add ppc code to match rotl

Targets should add rotl/rotr patterns if they have them


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@25222 91177308-0d34-0410-b5e6-96231b3b80d8

12 files changed, 95 insertions, 7 deletions

diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index eb48ce8..032f319 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -131,8 +131,10 @@ namespace ISD {
     // an unsigned/signed value of type i[2*n], then return the top part.
     MULHU, MULHS,
 
-    // Bitwise operators.
-    AND, OR, XOR, SHL, SRA, SRL,
+    // Bitwise operators - logical and, logical or, logical xor, shift left,
+    // shift right algebraic (shift in sign bits), shift right logical (shift in
+    // zeroes), rotate left, rotate right, and byteswap.
+    AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP,
 
     // Counting operators
     CTTZ, CTLZ, CTPOP,
diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 30a4c9f..1d35668 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -1133,8 +1133,6 @@ SDOperand DAGCombiner::visitOR(SDNode *N) {
                                                  N1),
                        DAG.getConstant(N1C->getValue() | C1->getValue(), VT));
   }
-  
-  
   // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
@@ -1180,6 +1178,42 @@ SDOperand DAGCombiner::visitOR(SDNode *N) {
     WorkList.push_back(ORNode.Val);
     return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode);
   }
+  // canonicalize shl to left side in a shl/srl pair, to match rotate
+  if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL)
+    std::swap(N0, N1);
+  // check for rotl, rotr
+  if (N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SRL &&
+      N0.getOperand(0) == N1.getOperand(0) &&
+      TLI.isOperationLegal(ISD::ROTL, VT)) {
+    // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
+    if (N0.getOperand(1).getOpcode() == ISD::Constant &&
+        N1.getOperand(1).getOpcode() == ISD::Constant) {
+      uint64_t c1val = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
+      uint64_t c2val = cast<ConstantSDNode>(N1.getOperand(1))->getValue();
+      if ((c1val + c2val) == OpSizeInBits)
+        return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1));
+    }
+    // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y)
+    if (N1.getOperand(1).getOpcode() == ISD::SUB &&
+        N0.getOperand(1) == N1.getOperand(1).getOperand(1))
+      if (ConstantSDNode *SUBC = 
+          dyn_cast<ConstantSDNode>(N1.getOperand(1).getOperand(0)))
+        if (SUBC->getValue() == OpSizeInBits)
+          return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1));
+    // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y)
+    if (N0.getOperand(1).getOpcode() == ISD::SUB &&
+        N1.getOperand(1) == N0.getOperand(1).getOperand(1))
+      if (ConstantSDNode *SUBC = 
+          dyn_cast<ConstantSDNode>(N0.getOperand(1).getOperand(0)))
+        if (SUBC->getValue() == OpSizeInBits) {
+          if (TLI.isOperationLegal(ISD::ROTR, VT))
+            return DAG.getNode(ISD::ROTR, VT, N0.getOperand(0), 
+                               N1.getOperand(1));
+          else
+            return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0),
+                               N0.getOperand(1));
+        }
+  }
   return SDOperand();
 }
 
diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index db5c8e2..fe6c476 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -2112,6 +2112,24 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     }
     break;
 
+  case ISD::ROTL:
+  case ISD::ROTR:
+    Tmp1 = LegalizeOp(Node->getOperand(0));   // LHS
+    Tmp2 = LegalizeOp(Node->getOperand(1));   // RHS
+    switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+    case TargetLowering::Custom:
+    case TargetLowering::Promote:
+    case TargetLowering::Expand:
+      assert(0 && "Cannot handle this yet!");
+    case TargetLowering::Legal:
+      if (Tmp1 != Node->getOperand(0) ||
+          Tmp2 != Node->getOperand(1))
+        Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,
+                             Tmp2);
+      break;
+    }
+    break;
+    
   case ISD::CTPOP:
   case ISD::CTTZ:
   case ISD::CTLZ:
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 5a0e2bf..4ecea2f 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -983,6 +983,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   case ISD::SHL:
   case ISD::SRA:
   case ISD::SRL:
+  case ISD::ROTL:
+  case ISD::ROTR:
     assert(VT == N1.getValueType() &&
            "Shift operators return type must be the same as their first arg");
     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
@@ -1039,6 +1041,12 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
       case ISD::SHL  : return getConstant(C1 << C2, VT);
       case ISD::SRL  : return getConstant(C1 >> C2, VT);
       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
+      case ISD::ROTL : 
+        return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)),
+                           VT);
+      case ISD::ROTR : 
+        return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 
+                           VT);
       default: break;
       }
     } else {      // Cannonicalize constant to RHS if commutative
@@ -1915,6 +1923,9 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::SHL:    return "shl";
   case ISD::SRA:    return "sra";
   case ISD::SRL:    return "srl";
+  case ISD::ROTL:   return "rotl";
+  case ISD::ROTR:   return "rotr";
+  case ISD::BSWAP:  return "bswap";
   case ISD::FADD:   return "fadd";
   case ISD::FSUB:   return "fsub";
   case ISD::FMUL:   return "fmul";
diff --git a/lib/Target/Alpha/AlphaISelLowering.cpp b/lib/Target/Alpha/AlphaISelLowering.cpp
index 63a04e4..734e7b9 100644
--- a/lib/Target/Alpha/AlphaISelLowering.cpp
+++ b/lib/Target/Alpha/AlphaISelLowering.cpp
@@ -81,6 +81,8 @@ AlphaTargetLowering::AlphaTargetLowering(TargetMachine &TM) : TargetLowering(TM)
     setOperationAction(ISD::CTTZ     , MVT::i64  , Expand);
     setOperationAction(ISD::CTLZ     , MVT::i64  , Expand);
   }
+  setOperationAction(ISD::ROTL     , MVT::i64, Expand);
+  setOperationAction(ISD::ROTR     , MVT::i64, Expand);
   
   setOperationAction(ISD::SREM     , MVT::i64, Custom);
   setOperationAction(ISD::UREM     , MVT::i64, Custom);
diff --git a/lib/Target/IA64/IA64ISelLowering.cpp b/lib/Target/IA64/IA64ISelLowering.cpp
index e97bb12..256d3ef 100644
--- a/lib/Target/IA64/IA64ISelLowering.cpp
+++ b/lib/Target/IA64/IA64ISelLowering.cpp
@@ -80,6 +80,8 @@ IA64TargetLowering::IA64TargetLowering(TargetMachine &TM)
       //IA64 has these, but they are not implemented
       setOperationAction(ISD::CTTZ , MVT::i64  , Expand);
       setOperationAction(ISD::CTLZ , MVT::i64  , Expand);
+      setOperationAction(ISD::ROTL , MVT::i64  , Expand);
+      setOperationAction(ISD::ROTR , MVT::i64  , Expand);
 
       computeRegisterProperties();
 
diff --git a/lib/Target/PowerPC/PPCISelLowering.cpp b/lib/Target/PowerPC/PPCISelLowering.cpp
index 9674432..a5ba28d 100644
--- a/lib/Target/PowerPC/PPCISelLowering.cpp
+++ b/lib/Target/PowerPC/PPCISelLowering.cpp
@@ -68,6 +68,9 @@ PPCTargetLowering::PPCTargetLowering(TargetMachine &TM)
   setOperationAction(ISD::CTPOP, MVT::i32  , Expand);
   setOperationAction(ISD::CTTZ , MVT::i32  , Expand);
   
+  // PowerPC does not have ROTR
+  setOperationAction(ISD::ROTR, MVT::i32   , Expand);
+  
   // PowerPC does not have Select
   setOperationAction(ISD::SELECT, MVT::i32, Expand);
   setOperationAction(ISD::SELECT, MVT::f32, Expand);
diff --git a/lib/Target/PowerPC/PPCInstrInfo.td b/lib/Target/PowerPC/PPCInstrInfo.td
index 2af0dd1..e8f3593 100644
--- a/lib/Target/PowerPC/PPCInstrInfo.td
+++ b/lib/Target/PowerPC/PPCInstrInfo.td
@@ -982,9 +982,6 @@ def : Pat<(or GPRC:$in, imm:$imm),
 // XOR an arbitrary immediate.
 def : Pat<(xor GPRC:$in, imm:$imm),
           (XORIS (XORI GPRC:$in, (LO16 imm:$imm)), (HI16 imm:$imm))>;
-def : Pat<(or (shl GPRC:$rS, GPRC:$rB),
-              (srl GPRC:$rS, (sub 32, GPRC:$rB))),
-          (RLWNM GPRC:$rS, GPRC:$rB, 0, 31)>;
 
 // Return void support.
 def : Pat<(ret), (BLR)>;
@@ -1008,6 +1005,12 @@ def : Pat<(srl GPRC:$in, (i32 imm:$imm)),
 def : Pat<(srl G8RC:$in, (i64 imm:$imm)),
           (RLDICL G8RC:$in, (SRL64 imm:$imm), imm:$imm)>;
 
+// ROTL
+def : Pat<(rotl GPRC:$in, GPRC:$sh),
+          (RLWNM GPRC:$in, GPRC:$sh, 0, 31)>;
+def : Pat<(rotl GPRC:$in, (i32 imm:$imm)),
+          (RLWINM GPRC:$in, imm:$imm, 0, 31)>;
+          
 // Hi and Lo for Darwin Global Addresses.
 def : Pat<(PPChi tglobaladdr:$in, 0), (LIS tglobaladdr:$in)>;
 def : Pat<(PPClo tglobaladdr:$in, 0), (LI tglobaladdr:$in)>;
diff --git a/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index 978229f..b418f57 100644
--- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -146,6 +146,8 @@ SparcV8TargetLowering::SparcV8TargetLowering(TargetMachine &TM)
   setOperationAction(ISD::CTPOP, MVT::i32, Expand);
   setOperationAction(ISD::CTTZ , MVT::i32, Expand);
   setOperationAction(ISD::CTLZ , MVT::i32, Expand);
+  setOperationAction(ISD::ROTL , MVT::i32, Expand);
+  setOperationAction(ISD::ROTR , MVT::i32, Expand);
 
   setOperationAction(ISD::SHL_PARTS, MVT::i32, Expand);
   setOperationAction(ISD::SRA_PARTS, MVT::i32, Expand);
diff --git a/lib/Target/SparcV8/SparcV8ISelDAGToDAG.cpp b/lib/Target/SparcV8/SparcV8ISelDAGToDAG.cpp
index 978229f..b418f57 100644
--- a/lib/Target/SparcV8/SparcV8ISelDAGToDAG.cpp
+++ b/lib/Target/SparcV8/SparcV8ISelDAGToDAG.cpp
@@ -146,6 +146,8 @@ SparcV8TargetLowering::SparcV8TargetLowering(TargetMachine &TM)
   setOperationAction(ISD::CTPOP, MVT::i32, Expand);
   setOperationAction(ISD::CTTZ , MVT::i32, Expand);
   setOperationAction(ISD::CTLZ , MVT::i32, Expand);
+  setOperationAction(ISD::ROTL , MVT::i32, Expand);
+  setOperationAction(ISD::ROTR , MVT::i32, Expand);
 
   setOperationAction(ISD::SHL_PARTS, MVT::i32, Expand);
   setOperationAction(ISD::SRA_PARTS, MVT::i32, Expand);
diff --git a/lib/Target/TargetSelectionDAG.td b/lib/Target/TargetSelectionDAG.td
index 1e019d3..23abb10 100644
--- a/lib/Target/TargetSelectionDAG.td
+++ b/lib/Target/TargetSelectionDAG.td
@@ -230,6 +230,8 @@ def urem       : SDNode<"ISD::UREM"      , SDTIntBinOp>;
 def srl        : SDNode<"ISD::SRL"       , SDTIntShiftOp>;
 def sra        : SDNode<"ISD::SRA"       , SDTIntShiftOp>;
 def shl        : SDNode<"ISD::SHL"       , SDTIntShiftOp>;
+def rotl       : SDNode<"ISD::ROTL"      , SDTIntShiftOp>;
+def rotr       : SDNode<"ISD::ROTR"      , SDTIntShiftOp>;
 def and        : SDNode<"ISD::AND"       , SDTIntBinOp,
                         [SDNPCommutative, SDNPAssociative]>;
 def or         : SDNode<"ISD::OR"        , SDTIntBinOp,
diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp
index fee12ef..65622af 100644
--- a/lib/Target/X86/X86ISelLowering.cpp
+++ b/lib/Target/X86/X86ISelLowering.cpp
@@ -107,6 +107,13 @@ X86TargetLowering::X86TargetLowering(TargetMachine &TM)
   setOperationAction(ISD::CTLZ             , MVT::i32  , Expand);
   setOperationAction(ISD::READCYCLECOUNTER , MVT::i64  , Custom);
 
+  setOperationAction(ISD::ROTL             , MVT::i8   , Expand);
+  setOperationAction(ISD::ROTR             , MVT::i8   , Expand);
+  setOperationAction(ISD::ROTL             , MVT::i16  , Expand);
+  setOperationAction(ISD::ROTR             , MVT::i16  , Expand);
+  setOperationAction(ISD::ROTL             , MVT::i32  , Expand);
+  setOperationAction(ISD::ROTR             , MVT::i32  , Expand);
+
   setOperationAction(ISD::READIO           , MVT::i1   , Expand);
   setOperationAction(ISD::READIO           , MVT::i8   , Expand);
   setOperationAction(ISD::READIO           , MVT::i16  , Expand);