Teach LegalizeTypes how to expand and promote CTLZ,

CTTZ and CTPOP.  The expansion code differs from
that in LegalizeDAG in that it chooses to take the
CTLZ/CTTZ count from the Hi/Lo part depending on
whether the Hi/Lo value is zero, not on whether
CTLZ/CTTZ of Hi/Lo returned 32 (or whatever the
width of the type is) for it.  I made this change
because the optimizers may well know that Hi/Lo
is zero and exploit it.  The promotion code for
CTTZ also differs from that in LegalizeDAG: it
uses an "or" to get the right result when the
original value is zero, rather than using a compare
and select.  This also means the value doesn't
need to be zero extended.


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

1 files changed, 35 insertions, 0 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
index 19d9d5bb62..3dab01a981 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
@@ -70,6 +70,9 @@ void DAGTypeLegalizer::PromoteResult(SDNode *N, unsigned ResNo) {
   case ISD::SELECT:    Result = PromoteResult_SELECT(N); break;
   case ISD::SELECT_CC: Result = PromoteResult_SELECT_CC(N); break;
 
+  case ISD::CTLZ:     Result = PromoteResult_CTLZ(N); break;
+  case ISD::CTPOP:    Result = PromoteResult_CTPOP(N); break;
+  case ISD::CTTZ:     Result = PromoteResult_CTTZ(N); break;
   }      
   
   // If Result is null, the sub-method took care of registering the result.
@@ -265,6 +268,38 @@ SDOperand DAGTypeLegalizer::PromoteResult_SELECT_CC(SDNode *N) {
                      N->getOperand(1), LHS, RHS, N->getOperand(4));
 }
 
+SDOperand DAGTypeLegalizer::PromoteResult_CTLZ(SDNode *N) {
+  SDOperand Op = GetPromotedOp(N->getOperand(0));
+  MVT::ValueType OVT = N->getValueType(0);
+  MVT::ValueType NVT = Op.getValueType();
+  // Zero extend to the promoted type and do the count there.
+  Op = DAG.getNode(ISD::CTLZ, NVT, DAG.getZeroExtendInReg(Op, OVT));
+  // Subtract off the extra leading bits in the bigger type.
+  return DAG.getNode(ISD::SUB, NVT, Op,
+                     DAG.getConstant(MVT::getSizeInBits(NVT) -
+                                     MVT::getSizeInBits(OVT), NVT));
+}
+
+SDOperand DAGTypeLegalizer::PromoteResult_CTPOP(SDNode *N) {
+  SDOperand Op = GetPromotedOp(N->getOperand(0));
+  MVT::ValueType OVT = N->getValueType(0);
+  MVT::ValueType NVT = Op.getValueType();
+  // Zero extend to the promoted type and do the count there.
+  return DAG.getNode(ISD::CTPOP, NVT, DAG.getZeroExtendInReg(Op, OVT));
+}
+
+SDOperand DAGTypeLegalizer::PromoteResult_CTTZ(SDNode *N) {
+  SDOperand Op = GetPromotedOp(N->getOperand(0));
+  MVT::ValueType OVT = N->getValueType(0);
+  MVT::ValueType NVT = Op.getValueType();
+  // The count is the same in the promoted type except if the original
+  // value was zero.  This can be handled by setting the bit just off
+  // the top of the original type.
+  Op = DAG.getNode(ISD::OR, NVT, Op,
+                   // FIXME: Do this using an APINT constant.
+                   DAG.getConstant(1UL << MVT::getSizeInBits(OVT), NVT));
+  return DAG.getNode(ISD::CTTZ, NVT, Op);
+}
 
 //===----------------------------------------------------------------------===//
 //  Operand Promotion