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

4 files changed, 119 insertions, 30 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
index b840db86cc..6f3ffba52e 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.h
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
@@ -159,23 +159,26 @@ private:
     
   // Result Promotion.
   void PromoteResult(SDNode *N, unsigned ResNo);
-  SDOperand PromoteResult_UNDEF(SDNode *N);
   SDOperand PromoteResult_Constant(SDNode *N);
-  SDOperand PromoteResult_TRUNCATE(SDNode *N);
-  SDOperand PromoteResult_INT_EXTEND(SDNode *N);
+  SDOperand PromoteResult_CTLZ(SDNode *N);
+  SDOperand PromoteResult_CTPOP(SDNode *N);
+  SDOperand PromoteResult_CTTZ(SDNode *N);
   SDOperand PromoteResult_FP_ROUND(SDNode *N);
   SDOperand PromoteResult_FP_TO_XINT(SDNode *N);
-  SDOperand PromoteResult_SETCC(SDNode *N);
+  SDOperand PromoteResult_INT_EXTEND(SDNode *N);
   SDOperand PromoteResult_LOAD(LoadSDNode *N);
-  SDOperand PromoteResult_SimpleIntBinOp(SDNode *N);
   SDOperand PromoteResult_SDIV(SDNode *N);
-  SDOperand PromoteResult_UDIV(SDNode *N);
+  SDOperand PromoteResult_SELECT   (SDNode *N);
+  SDOperand PromoteResult_SELECT_CC(SDNode *N);
+  SDOperand PromoteResult_SETCC(SDNode *N);
   SDOperand PromoteResult_SHL(SDNode *N);
+  SDOperand PromoteResult_SimpleIntBinOp(SDNode *N);
   SDOperand PromoteResult_SRA(SDNode *N);
   SDOperand PromoteResult_SRL(SDNode *N);
-  SDOperand PromoteResult_SELECT   (SDNode *N);
-  SDOperand PromoteResult_SELECT_CC(SDNode *N);
-  
+  SDOperand PromoteResult_TRUNCATE(SDNode *N);
+  SDOperand PromoteResult_UDIV(SDNode *N);
+  SDOperand PromoteResult_UNDEF(SDNode *N);
+
   // Operand Promotion.
   bool PromoteOperand(SDNode *N, unsigned OperandNo);
   SDOperand PromoteOperand_ANY_EXTEND(SDNode *N);
@@ -202,18 +205,21 @@ private:
     
   // Result Expansion.
   void ExpandResult(SDNode *N, unsigned ResNo);
-  void ExpandResult_UNDEF      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_Constant   (SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi);
   void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
   void ExpandResult_AssertZext (SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_TRUNCATE   (SDNode *N, SDOperand &Lo, SDOperand &Hi);
   void ExpandResult_BIT_CONVERT(SDNode *N, SDOperand &Lo, SDOperand &Hi);
-  void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_Constant   (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_CTLZ       (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_CTPOP      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_CTTZ       (SDNode *N, SDOperand &Lo, SDOperand &Hi);
   void ExpandResult_LOAD       (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_MERGE_VALUES(SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_SIGN_EXTEND_INREG(SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_TRUNCATE   (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_UNDEF      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
+  void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi);
 
   void ExpandResult_Logical    (SDNode *N, SDOperand &Lo, SDOperand &Hi);
   void ExpandResult_BSWAP      (SDNode *N, SDOperand &Lo, SDOperand &Hi);
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.
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
diff --git a/test/CodeGen/Generic/2008-02-04-Ctlz.ll b/test/CodeGen/Generic/2008-02-04-Ctlz.ll
index 5a560aa953..4639b6f977 100644
--- a/test/CodeGen/Generic/2008-02-04-Ctlz.ll
+++ b/test/CodeGen/Generic/2008-02-04-Ctlz.ll
@@ -1,22 +1,21 @@
 ; RUN: llvm-as < %s | llc
 
-@.str3 = external constant [56 x i8]		; <[56 x i8]*> [#uses=1]
+@.str = internal constant [14 x i8] c"%lld %d %d %d\00"
 
-define i32 @main() nounwind  {
+define i32 @main(i64 %arg) nounwind  {
 entry:
-	br label %bb30
-
-bb30:		; preds = %bb30, %entry
-	%l.024 = phi i64 [ -10000, %entry ], [ 0, %bb30 ]		; <i64> [#uses=2]
-	%tmp37 = tail call i64 @llvm.ctlz.i64( i64 %l.024 )		; <i64> [#uses=1]
-	trunc i64 %tmp37 to i32		; <i32>:0 [#uses=1]
-	%tmp40 = tail call i32 (i8*, ...)* @printf( i8* noalias  getelementptr ([56 x i8]* @.str3, i32 0, i32 0), i64 %l.024, i32 %0, i32 0, i32 0 ) nounwind 		; <i32> [#uses=0]
-	br i1 false, label %bb30, label %bb9.i
-
-bb9.i:		; preds = %bb30
+	%tmp37 = tail call i64 @llvm.ctlz.i64( i64 %arg )		; <i64> [#uses=1]
+	%tmp47 = tail call i64 @llvm.cttz.i64( i64 %arg )		; <i64> [#uses=1]
+	%tmp57 = tail call i64 @llvm.ctpop.i64( i64 %arg )		; <i64> [#uses=1]
+	%tmp38 = trunc i64 %tmp37 to i32		; <i32>:0 [#uses=1]
+	%tmp48 = trunc i64 %tmp47 to i32		; <i32>:0 [#uses=1]
+	%tmp58 = trunc i64 %tmp57 to i32		; <i32>:0 [#uses=1]
+	%tmp40 = tail call i32 (i8*, ...)* @printf( i8* noalias  getelementptr ([14 x i8]* @.str, i32 0, i32 0), i64 %arg, i32 %tmp38, i32 %tmp48, i32 %tmp58 ) nounwind 		; <i32> [#uses=0]
 	ret i32 0
 }
 
 declare i32 @printf(i8* noalias , ...) nounwind 
 
 declare i64 @llvm.ctlz.i64(i64) nounwind readnone 
+declare i64 @llvm.cttz.i64(i64) nounwind readnone 
+declare i64 @llvm.ctpop.i64(i64) nounwind readnone