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, 50 insertions, 1 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
index 0461ea7ce6..136ae68686 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
@@ -82,8 +82,12 @@ void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) {
   case ISD::SHL:
   case ISD::SRA:
   case ISD::SRL:         ExpandResult_Shift(N, Lo, Hi); break;
+
+  case ISD::CTLZ:        ExpandResult_CTLZ(N, Lo, Hi); break;
+  case ISD::CTPOP:       ExpandResult_CTPOP(N, Lo, Hi); break;
+  case ISD::CTTZ:        ExpandResult_CTTZ(N, Lo, Hi); break;
   }
-  
+
   // If Lo/Hi is null, the sub-method took care of registering results etc.
   if (Lo.Val)
     SetExpandedOp(SDOperand(N, ResNo), Lo, Hi);
@@ -615,6 +619,51 @@ void DAGTypeLegalizer::ExpandResult_Shift(SDNode *N,
 #endif
 }  
 
+void DAGTypeLegalizer::ExpandResult_CTLZ(SDNode *N,
+                                         SDOperand &Lo, SDOperand &Hi) {
+  // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
+  GetExpandedOp(N->getOperand(0), Lo, Hi);
+  MVT::ValueType NVT = Lo.getValueType();
+
+  SDOperand HiNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), Hi,
+                                     DAG.getConstant(0, NVT), ISD::SETNE);
+
+  SDOperand LoLZ = DAG.getNode(ISD::CTLZ, NVT, Lo);
+  SDOperand HiLZ = DAG.getNode(ISD::CTLZ, NVT, Hi);
+
+  Lo = DAG.getNode(ISD::SELECT, NVT, HiNotZero, HiLZ,
+                   DAG.getNode(ISD::ADD, NVT, LoLZ,
+                               DAG.getConstant(MVT::getSizeInBits(NVT), NVT)));
+  Hi = DAG.getConstant(0, NVT);
+}
+
+void DAGTypeLegalizer::ExpandResult_CTPOP(SDNode *N,
+                                          SDOperand &Lo, SDOperand &Hi) {
+  // ctpop(HiLo) -> ctpop(Hi)+ctpop(Lo)
+  GetExpandedOp(N->getOperand(0), Lo, Hi);
+  MVT::ValueType NVT = Lo.getValueType();
+  Lo = DAG.getNode(ISD::ADD, NVT, DAG.getNode(ISD::CTPOP, NVT, Lo),
+                   DAG.getNode(ISD::CTPOP, NVT, Hi));
+  Hi = DAG.getConstant(0, NVT);
+}
+
+void DAGTypeLegalizer::ExpandResult_CTTZ(SDNode *N,
+                                         SDOperand &Lo, SDOperand &Hi) {
+  // cttz (HiLo) -> Lo != 0 ? cttz(Lo) : (cttz(Hi)+32)
+  GetExpandedOp(N->getOperand(0), Lo, Hi);
+  MVT::ValueType NVT = Lo.getValueType();
+
+  SDOperand LoNotZero = DAG.getSetCC(TLI.getSetCCResultTy(), Lo,
+                                     DAG.getConstant(0, NVT), ISD::SETNE);
+
+  SDOperand LoLZ = DAG.getNode(ISD::CTTZ, NVT, Lo);
+  SDOperand HiLZ = DAG.getNode(ISD::CTTZ, NVT, Hi);
+
+  Lo = DAG.getNode(ISD::SELECT, NVT, LoNotZero, LoLZ,
+                   DAG.getNode(ISD::ADD, NVT, HiLZ,
+                               DAG.getConstant(MVT::getSizeInBits(NVT), NVT)));
+  Hi = DAG.getConstant(0, NVT);
+}
 
 /// ExpandShiftByConstant - N is a shift by a value that needs to be expanded,
 /// and the shift amount is a constant 'Amt'.  Expand the operation.