Does it make sense to extend this for arbitrary shuffles in the future? The mask construction logic in https://github.com/llvm/llvm-project/blob/4aa8cdfeebec115b928e0ccb452551b520d00f0b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp#L1612-L1660 can probably mostly be reused for the icmp case.

I don't fully understand how this API is going to be used. The current API makes sense to me (are all elements in the vector the same?) but the new one is unclear, especially for the case where no shufflevector is involved. If I have a splat constant, which index does the value come from?

Ping

Fix typo

What you're doing here is right for a single exit, but I don't think it holds up for multiple exits. Talking in terms of probabilities, you are given P(E_i | not E_{i-1}), where E_i is the event that exit i is taken. The non-conditional exit probability is P(E_i) = P(E_i | not E_{i-1}) / P(not E_{i-1}). The predicted exit count is (1 / P(E_i)) - 1.

Rebase

Use switch instead of match chain.

In D72837#1840886, @aymanmus wrote:

IMHO, there is no added value to splitting to 2 patches, the select changed are too obvious, and the compare is strongly related to the select changes.

Is it possible to split this into a patch that adds just the select handling, and another that extends the icmp support? It seems like the select part should be testable independently, as long as you don't derive the select condition from the select operands.

Also move the ashr/lshr and trunc patterns into freelyNegateValue() and keep existing handling regarding one-use checks.

In D73342#1838974, @jeroen.dobbelaere wrote:

Hal Finkel provided following example on the mailing list:

int * restrict r = a;
...
int x = noaliasing ? *r : *a;

This shows that the intersection of '*r' and '*a' must be taken.

Can you explain in more detail why the current behavior is incorrect? Why is using the aliasing information in program order wrong? If the first load is noalias, then we should be able to deduplicate to that noalias load. If the second load is noalias, then generally we can't assume the first load is also noalias. Unless there is a must-exec relation between them, as @nlopes mentioned.

Ping

In D72944#1829322, @spatel wrote:

To fix the infinite loop bug without this change, we could add a clause in canonicalizeMinMaxWithConstant() to avoid creating this:
%cmp = icmp sgt i16 0, %sub

Ie, if the LHS returned by matchSelectPattern() is a constant, swap LHS and RHS because we know we can't create a canonical compare that way. An alternative would be to do that swap within matchSelectPattern() itself. We already have a different LHS/RHS constraint for ABS/NABS on that analysis.

I'm not sure how we can expose that bug with this fix in place though, so might want to make that fix first to be safer?

LGTM

@spatel I've reported https://bugs.llvm.org/show_bug.cgi?id=44573 and https://bugs.llvm.org/show_bug.cgi?id=44574 to keep track of this.

LGTM

Remove unnecessary iterator increment. Reduce test case to use 100 instead of 1000 iterations.

I've added the complete original test case with -instcombine-infinite-loop-threshold=2. It would also be possible to reduce it (it just wouldn't need the full 1000 iterations that trigger the default threshold), but as the test now runs quickly even on a debug build, I figured keeping the original is fine.

https://github.com/llvm/llvm-project/blob/ab72db7fc85266f094cc6b9452dd01f175c04cab/llvm/lib/Analysis/ScalarEvolutionExpander.cpp#L1300-L1325 => This piece of code in SCEVExpander breaks in practice (creating separate values for the same predecessor block).

I've now verified that this passes test-suite when applied together with D72657.

I was able to create a reproducer with uselistorder:

Okay, I think I got it. I don't have a standalone reproducer for this, but what seems to be happening is that we're iterating over OldPN->users() in https://github.com/llvm/llvm-project/blob/a506f7f9105eec4baac296d21c922457d6f4b52a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp#L2347, but https://github.com/llvm/llvm-project/blob/a506f7f9105eec4baac296d21c922457d6f4b52a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp#L2353 is going to modify the users. That makes us skip over a user (specifically, the original bitcast), which then refers to the old phi node.

I'm a bit stumped here. From the trace I see that previously instcombine produced

In D71164#1816462, @lebedev.ri wrote:

Did you verify that test-suite now passes?

Add comment, split out NFC change.

In D72423#1816715, @rrika wrote:

In D72423#1815871, @nikic wrote:

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

Are you suggesting factoring out the logic for addition/subtraction only or all opcodes? Where should this new function live?

Ping

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

I'm open to being convinced that the change in canonical form to allow multiple identical backedges is reasonable, but I'd expect to see an argument to that form, not simple a code change.

I've updated the patch to directly perform the load combine now. I believe the store case shouldn't exhibit the same issue, as the bitcast is cannot be a phi operand there. I've also added the new looping testcase and -instcombine-infinite-loop-threshold=2 to make sure that the combine runs through in one iteration.

Explicitly perform load combine.

As far as I can see this is basically the same issue as what this patch tries to solve. Just this time it's not the extra use in the old phi causing the loop, but a change in worklist order caused by this change.

Mostly reduced testcase triggering an infinite loop with this patch:

LGTM