[LoopIdiomRecognize] Generalize loop-carried shift-count recurrence recognition

## Summary

LLVM recognizes some shift-until-zero loop idioms, but it still misses common
loop-carried shift-count recurrences where the shifted value itself is carried
through the loop:

```llvm
%count = phi i32 [ 0, %entry ], [ %count.next, %loop ]
%value = phi i32 [ %x, %entry ], [ %value.next, %loop ]
%count.next = add i32 %count, 1
%value.next = lshr i32 %value, C
%done = icmp eq i32 %value.next, 0
br i1 %done, label %exit, label %loop
```

For constant `C > 1`, this loop computes a small digit/count-style expression
from the active bit width of `%x`. It is common in integer digit counting,
octal/hex formatting, varint sizing, and related size-estimation code.

## Missed Family

Two frequently occurring forms are:

### Do-while count

The loop always executes at least once:

```llvm
define i32 @do_while_shift4_count(i32 %x) {
entry:
br label %loop

loop:
%count = phi i32 [ 0, %entry ], [ %count.next, %loop ]
%value = phi i32 [ %x, %entry ], [ %value.next, %loop ]
%count.next = add nuw nsw i32 %count, 1
%value.next = lshr i32 %value, 4
%done = icmp eq i32 %value.next, 0
br i1 %done, label %exit, label %loop

exit:
ret i32 %count.next
}
```

This computes:

```text
max(ceil(active_bits(x) / 4), 1)
```

where `active_bits(x) = bitwidth(x) - ctlz(x, false)`.

### Prechecked count

The zero input is handled before the loop:

```llvm
define i32 @prechecked_shift7_count(i32 %x) {
entry:
%iszero = icmp eq i32 %x, 0
br i1 %iszero, label %zero, label %loop

loop:
%count = phi i32 [ 0, %entry ], [ %count.next, %loop ]
%value = phi i32 [ %x, %entry ], [ %value.next, %loop ]
%count.next = add nuw nsw i32 %count, 1
%value.next = lshr i32 %value, 7
%done = icmp eq i32 %value.next, 0
br i1 %done, label %exit, label %loop

exit:
ret i32 %count.next

zero:
ret i32 0
}
```

This computes:

```text
ceil(active_bits(x) / 7)
```

## Expected Direction

When profitable for the target, LoopIdiomRecognize could compute the trip count
from `ctlz` and replace the loop-carried count recurrence:

```text
active_bits = bitwidth - ctlz(x, false)
count = ceil(active_bits / C)
```

For do-while forms, clamp the count to at least one. For prechecked forms, the
zero path already supplies zero.

For powers of two, the division becomes an add plus shift. For non-powers of
two such as 3 or 7, the implementation can use the existing target-cost checks
and constant-division lowering strategy.

## Current Coverage Gap

There is existing nearby support for shift-until-zero idioms, including:

- shift-by-3 do-while forms on targets where the `ctlz`-based replacement is
profitable;
- some prechecked shift-count forms;
- invariant-value shifted-by-IV forms.

The observed family is broader:

- loop-carried value recurrence: `%value.next = lshr %value, C`;
- constant shifts greater than one, especially `3`, `4`, and `7`;
- both `i32` and `i64` values;
- both do-while and prechecked zero-input conventions;
- some loops where the count recurrence can be replaced even if the whole loop
cannot be deleted.

## Corpus Evidence

In a refreshed optimized benchmark corpus, the scanner found:

- 5,833 loop-carried shift-count recurrence hits;
- 4,688 hits with shift amount greater than one;
- 625 files with at least one hit.

Exact shift distribution for the `C > 1` pool:

- shift 2: 5
- shift 3: 892
- shift 4: 2,785
- shift 7: 929
- shift 8: 55
- shift 11: 1
- shift 14: 1
- shift 15: 2
- shift 16: 14
- shift 30: 2
- shift 32: 2

Top projects by hit count:

- `open3d`: 2,114
- `lief`: 1,375
- `yalantinglibs`: 778
- `oiio`: 393
- `wasmedge`: 356
- `ffmpeg`: 123
- `arrow`: 81
- `fmt`: 80
- `duckdb`: 72

Representative source patterns include `fmt`/`duckdb_fmt` digit-counting loops,
Brotli population-cost loops, varint-size loops, and protobuf-style serialized
size computations.

## Backend And Profitability Guidance

This transform is target-sensitive. It should not be implemented as an
unconditional canonicalization that always replaces the loop with `ctlz`.

The replacement changes a data-dependent loop into a fixed-cost expression:

```text
count = ceil((bitwidth - ctlz(x)) / C)
```

That is usually a win when:

- `ctlz` lowers to a real instruction;
- the loop often runs more than one or two iterations;
- the division by `C` is cheap, or `C` is a power of two;
- the replacement avoids a large zero-handling sequence.

It can be a loss when:

- `ctlz` expands into a long software sequence;
- `C` is not a power of two and constant division is expensive;
- the source loop usually exits after one iteration;
- the value type is `i64` on a 32-bit target.

### Power-Of-Two Shifts

For shifts such as `4` and `8`, the closed form is cheap after `ctlz`:

```text
ceil(active_bits / C) = (active_bits + C - 1) >> log2(C)
```

Representative backend results for an `i32` shift-by-4 digit-count loop:

| target family | lowering | result |
| --- | --- | --- |
| x86-64 with `lzcnt` | `lzcnt` plus simple arithmetic | favorable |
| x86-64 generic | `bsr`-style lowering | favorable in static lowering, but still needs TTI gating |
| AArch64 | `clz` plus simple arithmetic | favorable |
| ARMv7 | `clz` for `i32` | favorable |
| RISC-V without Zbb | software/SWAR `ctlz` expansion | unfavorable |
| RISC-V with Zbb | `clz`/`clzw` | favorable to mixed |

The same shift-by-4 transform on `i64` is less uniformly profitable:

| target family | concern |
| --- | --- |
| x86-64 with `lzcnt` | branchless but may introduce `cmov`/zero handling; mixed for small inputs |
| AArch64 | branchless `clz`/`csel`; mixed statically, better for larger inputs |
| ARMv7 | 64-bit `clz` requires a two-half sequence; mixed to unfavorable |
| RISC-V without Zbb | hard negative because of large software `ctlz` |
| RISC-V with Zbb | viable, but still check zero/base-add overhead |

This suggests a conservative first implementation should prefer `i32`
power-of-two shifts where `ctlz` is cheap/legal.

### Shift-By-3

Shift-by-3 is not just a shift after `ctlz`; it needs division by 3 or an
equivalent multiply/shift sequence. Existing support can recognize some
do-while shift-by-3 forms when the target says the `ctlz` replacement is cheap.
For example, on an x86 target with `lzcnt`, a representative `duckdb_fmt`
octal digit-count loop is rewritten into:

```llvm
%lz = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
%biased = sub nuw nsw i32 34, %lz
%scaled = mul nuw nsw i32 %biased, 43
%wide = lshr i32 %scaled, 7
%count = call i32 @llvm.umax.i32(i32 %wide, i32 1)
```

The same loop may remain unchanged for a generic target if the target-cost
model does not consider `ctlz` cheap enough. This is desirable: the transform
should be controlled by TTI rather than applied blindly.

Shift-by-3 loops with additional carried state are a separate tier. A Brotli
population-cost representative has the shift-count recurrence, but the loop
also updates a floating accumulator:

```llvm
%acc.next = fadd double %acc, 3.0
%value.next = lshr i32 %value, 3
```

That is not a simple loop-deletion candidate. A later extension might still
use the computed trip count to simplify the count result or make the loop more
countable, but the initial recognizer should probably require that the loop body
contains only the shift recurrence, the count recurrence, the compare, and the
terminator.

### Shift-By-7

Shift-by-7 occurs in varint/protobuf-style size computations. It often has a
different exit convention:

```text
observed_extra = ceil(active_bits(x) / 7) - 1
= (active_bits(x) - 1) / 7
```

This is a real coverage gap, but it is a weaker first target:

- it needs division by 7 or target-specific strength reduction;
- some representatives add the result into a larger size expression;
- the static IR instruction count may not improve even when the formula is
correct;
- profitability depends on both `ctlz` cost and constant-division lowering.

Treat shift-by-7 as a follow-up once the implementation has robust off-by-one
handling and target cost checks.

### Implementation Implications

Useful profitability checks for the implementation:

- Query TTI for `ctlz`/`cttz` cost on the value type. Reject targets where it
expands into a large sequence, especially RISC-V without Zbb.
- Query or approximate the arithmetic cost of the division by `C`.
Power-of-two `C` is the safest class.
- Prefer `i32` over `i64` on 32-bit targets.
- Prefer loops where the count result is directly used outside the loop through
`%count.next`, `%count`, or simple LCSSA phis.
- Be cautious with base-add and zero-select forms, because they can introduce
`cmov`/`csel`/masking overhead.
- Keep shift-by-1 excluded unless profile/range data shows the source loop
usually runs many iterations.
- For generic targets, it is acceptable for the matcher to leave the loop in
place if the target model reports the fixed-cost sequence as too expensive.

## Notes

- This should remain profitability-gated. The request is not to force `ctlz`
expansion on targets where it is too expensive.
- The transform must preserve the off-by-one convention of each loop: some
exits use `%count.next`, while others use `%count` or LCSSA phis.
- Shift-by-1 has different profitability and existing coverage considerations;
this issue focuses on constant shifts greater than one.
- Some hits contain additional carried state. Those may not be full
loop-deletion candidates, but the shift-count recurrence can still expose a
known trip count or replace the count result.