[DAGCombiner] Fix (shl (ctlz x) n) for non-power-of-two Data

[lenary]

Summary

This DAGCombine is not valid for some combinations of the known bits
of x and non-power-of-two widths of x. As shown in the bug:

• The bitwidth of x is 35 (n=5)
• The unknown bits of x is only the least significant bit
• This gives the result of the ctlz two possible values: 34 or 35, both of which will give 1 when left-shifted 5 bits.
• So the eor x, 1 that this optimisation would give is not correct.

A similar instcombine optimisation is only applied when the width of x is
a power-of-two. GlobalISel does not have this bug, as shown by the testcase.

Fixes #61549

[RKSimon]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSRL(SDNode *N) {
 
   // fold (srl (sra X, Y), 31) -> (srl X, 31).  This srl only looks at the sign
   // bit, which is unmodified by sra.
   if (N1C && N1C->getAPIntValue() == (OpSizeInBits - 1)) {
     if (N0.getOpcode() == ISD::SRA)
       return DAG.getNode(ISD::SRL, SDLoc(N), VT, N0.getOperand(0), N1);
   }
 
-  // fold (srl (ctlz x), "5") -> x  iff x has one bit set (the low bit).
+  // fold (srl (ctlz x), "5") -> x  iff x has one bit set (the low bit), and x has a power
+  // of two bitwidth. The "5" represents (log2 (bitwidth x)).
   if (N1C && N0.getOpcode() == ISD::CTLZ &&
+      isPowerOf2_32(OpSizeInBits) &&
       N1C->getAPIntValue() == Log2_32(OpSizeInBits)) {
     KnownBits Known = DAG.computeKnownBits(N0.getOperand(0));
 
     // If any of the input bits are KnownOne, then the input couldn't be all
     // zeros, thus the result of the srl will always be zero.
     if (Known.One.getBoolValue()) return DAG.getConstant(0, SDLoc(N0), VT);
 
     // If all of the bits input the to ctlz node are known to be zero, then

llvm/test/CodeGen/AArch64/pr61549.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=aarch64 | FileCheck %s
 ; RUN: llc < %s -mtriple=aarch64 --global-isel | FileCheck %s --check-prefix=GISEL
 
 define i35 @f(i35 %0) {
 ; CHECK-LABEL: f:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #1 // =0x1
 ; CHECK-NEXT:    sbfx x9, x0, #0, #35
 ; CHECK-NEXT:    sdiv x10, x8, x9
 ; CHECK-NEXT:    msub x8, x10, x9, x8
-; CHECK-NEXT:    eor x0, x8, #0x1
+; CHECK-NEXT:    clz x8, x8
+; CHECK-NEXT:    sub x8, x8, #29
+; CHECK-NEXT:    ubfx x0, x8, #5, #30
 ; CHECK-NEXT:    ret
 ;
 ; GISEL-LABEL: f:
 ; GISEL:       // %bb.0:
 ; GISEL-NEXT:    mov w8, #1 // =0x1
 ; GISEL-NEXT:    sbfx x9, x0, #0, #35
 ; GISEL-NEXT:    sdiv x10, x8, x9
 ; GISEL-NEXT:    msub x8, x10, x9, x8