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
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 @@
// 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 @@
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 @@
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 @@
}
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 @@
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 @@
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 @@
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 @@
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 @@
//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 @@
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 @@
// 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 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 @@
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 @@
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 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 @@
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);