The original patch introduces a function minIterationWidthForEvaluateAtIteration. This way it exposes the limitation of evaluateAtIteration through the API and makes it possible for the user to choose the proper It width (e.g. like I did in the first revision https://reviews.llvm.org/D62563?vs=on&id=201795). What was the reason to remove it?

Even though it's motivated by downstream code, looks harmless to change upstream.

Fall back to non-canonical mode for non-affine addrecs.

LGTM

In D62563#1521477, @reames wrote:

Artur, nice find. In terms of staging complexity, have you considered how impactful it would be to simply refuse to generate the value at the given iteration in this case? evaluateAtIteration is allowed to return SCEVCouldNotCompute. I'm tempted to first introduce a bailout for a quick correctness fix - maybe along side your assert to see if we're missing any other cases - and then spend more time considering your full fix.

Have you considered reusing calculateByteProvider mechanism from load combining instead of matching an exact pattern?

LGTM. I agree that we can leave the stronger variant for the future.

Looks good overall, a couple of comments inline.

1. Since we need to fiddle with the insertion point I think we should stop using single IRBuilder which we pass around. It looks like creating a local IRBuilder is a cheap operation, so we can have local IRBuilders when we need to generate instructions. This way the insertion point will be clear from the local context.

Add diff with context.

One of the alternatives naming schemes which was discussed is to call this intrinsic should_deoptimize. In this case the meaning of the returned value is inverted, so we need to or it with the condition which we want to widen.

With this change you seem to be invalidating AST for instructions which have not been previously invalidated. I would hesitate to call this NFC.

Current patch seems to have comments like "this block doesn't need invalidation". Maybe sink this decision down to the SafetyInfo implementation? It should reduce the complexity of the user: just call invalidate every time you delete/insert instructions and you would be fine.

@rcorcs this has been accepted for quite a while, is there anything preventing integration? I'm looking forward to using colored graphs out of the box.

Can you describe what is the difference you observe in the verifier behavior with and without simplifications before? There will always be cases when some simplifications before the verifier change the CFG. You won't be able to handle everything in this analysis.

The suggestion to apply calcInvokeHeuristics before calcUnreachableHeuristics and calcColdCallHeuristics makes sense.

This is very similar to what we had as an initial implementation of loop predication. Later we found that this approach is problematic. See https://reviews.llvm.org/D37569 description for the details. This patch likely suffers from a similar problem.

Thanks for adding the test case!

We also observed regressions caused by this change. In our case the change increases the perceived cost of a loop which in turn reduced the unrolling factor. Let me know if you need further details about the regressions.

In D39097#905174, @anna wrote:

Artur, before this patch, we were checking whether RangeCheckIV's postIncExpr is latchCheckIV.

Now, the header comments and proof seems to point to the fact that the guard and latch are using the same offset (lines 103 - 110), but the code does not have any check that we are using the same offset. Or, is it that the offset is the same, but the difference in the latchCheckIV versus rangeCheckIV is caught in their respective start values, and the offset for both latch and guard remains the same?

I changed the loop in the description so it doesn't use Start. Instead the offsets are sunk into predicates G and B.

Clarified the description, added the requested test case.

Upload diff with context. Minor fix in the header comment.

Did you measure the compile time impact somehow?

In D38547#888359, @RKSimon wrote:

Is this PR10114 ?

@andrew.w.kaylor - ping, do you have any comments about the latest revision?

Add the comment about overly conservative legality check, add the test demonstrating it.

Update, I didn't see that there was a request to add a comment. Will do and update the patch,

Address review comments.

In D31182#706365, @spatel wrote:

Before getting to any details about the patch, we need to address the question raised in PR27036: why are we doing this transform in InstCombine at all? The assumption is that an integer add is more canonical and/or cheaper than an FP add. Is that universally true?

It's difficult to tell. Even if FP addition is cheaper the second combine also saves us one sitofp conversion. It should be also taken into account.