Infinite/exponential loop unswitch due to invariant condition injection

[nikic]

Running opt -passes='simple-loop-unswitch<nontrivial>' on https://gist.github.com/nikic/852fbcaa307231c3aa0a5cdc1f057ede does not finish after 5 minutes.

My attempt to reduce this resulted in https://gist.github.com/nikic/52d9fc05e986a4e9279620461fe54d26, which does finish after about 50 seconds, resulting in this output: https://gist.github.com/nikic/45fb4b1448caa7195618c5001874f8cc The first test case might not be infinite as well, just very slow.

This problem does not occur when -simple-loop-unswitch-inject-invariant-conditions=false is passed.

cc @serguei-katkov

[nikic]

I think what happens here is that we have a lot of branches where we can inject invariant conditions. Then we'll pick one of those and unswitch, creating two loops, where in one the relevant original condition is removed and in the other marked as llvm.invariant.condition.injection.disabled. However, we can then take the next-best injectable condition in each of those loops and repeat the process, increasing the number of loops by a factor of two in each iteration until we reach a cost threshold.

Possibly this should work more like partial unswitching, where we mark the entire old loop as llvm.loop.unswitch.partial.disable. In that case we should only end up with a linear number of loops (though even that seems potentially quite unprofitable?)

[nikic]

This cherry-pick also includes the fix for #63962 (a miscompile) in the same code.

/cherry-pick afd7db4 8362cae

[llvmbot]

/branch llvm/llvm-project-release-prs/issue66868