[TargetLowering][RISCV] Make expandCTLZ work for non-power of 2 types.

[craig.topper]

Summary

To convert CTLZ to popcount we do

x = x | (x >> 1);
x = x | (x >> 2);
...
x = x | (x >>16);
x = x | (x >>32); // for 64-bit input
return popcount(~x);

This smears the most significant set bit across all of the bits
below it then inverts the remaining 0s and does a population count.

To support non-power of 2 types, the last shift amount must be
more than half of the size of the type. For i15, the last shift
was previously a shift by 4, with this patch we add another shift
of 8.

Fixes PR56457.

[reames]

LGTM

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::expandCTLZ(SDNode *Node, SelectionDAG &DAG) const {
   // x = x | (x >> 1);
   // x = x | (x >> 2);
   // ...
   // x = x | (x >>16);
   // x = x | (x >>32); // for 64-bit input
   // return popcount(~x);
   //
   // Ref: "Hacker's Delight" by Henry Warren
-  for (unsigned i = 0; (1U << i) <= (NumBitsPerElt / 2); ++i) {
+  for (unsigned i = 0; (1U << i) < NumBitsPerElt; ++i) {
     SDValue Tmp = DAG.getConstant(1ULL << i, dl, ShVT);
     Op = DAG.getNode(ISD::OR, dl, VT, Op,
                      DAG.getNode(ISD::SRL, dl, VT, Op, Tmp));
   }
   Op = DAG.getNOT(dl, Op, VT);
   return DAG.getNode(ISD::CTPOP, dl, VT, Op);
 }
 

llvm/test/CodeGen/RISCV/pr56457.ll

 ; CHECK-NEXT:    srli a1, a1, 50
 ; CHECK-NEXT:    or a0, a0, a1
 ; CHECK-NEXT:    slli a1, a0, 49
 ; CHECK-NEXT:    srli a1, a1, 51
 ; CHECK-NEXT:    or a0, a0, a1
 ; CHECK-NEXT:    slli a1, a0, 49
 ; CHECK-NEXT:    srli a1, a1, 53
 ; CHECK-NEXT:    or a0, a0, a1
+; CHECK-NEXT:    slli a1, a0, 49
+; CHECK-NEXT:    srli a1, a1, 57
+; CHECK-NEXT:    or a0, a0, a1
 ; CHECK-NEXT:    not a0, a0
 ; CHECK-NEXT:    slli a0, a0, 49
 ; CHECK-NEXT:    srli a0, a0, 49
 ; CHECK-NEXT:    lui a1, %hi(.LCPI0_0)
 ; CHECK-NEXT:    ld a1, %lo(.LCPI0_0)(a1)
 ; CHECK-NEXT:    lui a2, %hi(.LCPI0_1)
 ; CHECK-NEXT:    ld a2, %lo(.LCPI0_1)(a2)
 ; CHECK-NEXT:    srli a3, a0, 1