[ValueTracking] Missed optimization of modulo power-of-two

[YanWQ-monad]

Recently I found a missed optimization related to modulo power-of-two. It's

https://github.com/dtcxzyw/llvm-opt-benchmark/blob/b79d63cb8adea5949cc449d4186e342d3dbdd871/bench/wasmtime-rs/optimized/1ham0fg2czw77e66.ll#L235

and it's compiled from something like

let modulo = if size.is_power_of_two() {  // i.e. ctpop(size) == 1
    size * 2
} else {
    size.next_power_of_two()
};

let result = xxx % modulo;

where urem xxx, modulo could be optimized to and xxx, (modulo - 1).

To solve it, I have created a PR #91171 that enables the recognization of .next_power_of_two(), and I also have a draft patch that could recognize power-of-two from dom conditions.

However, the key problem in this case is that LLVM currently only search 2 levels beyond phi nodes, so the resursion of isKnownToBeAPowerOfTwo stops at size * 2, and fails to know size is a power-of-two from the condition.

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Lines 2197 to 2199 in 37ffbbb

	// Recursively check all incoming values. Limit recursion to 2 levels, so
	// that search complexity is limited to number of operands^2.
	unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);

Though changing - 1 to - 3 could make it work in this case, it's obviously not a proper way to solve the problem.

I am not sure if there is a way to handle this complex context across multiple basic blocks, or should we instead patch wasmtime to use let modulo = (size + 1).next_power_of_two()?

cc @nikic @dtcxzyw