Can we split restructuring and generalization (possibly adding a test for the generalization part)? It's hard to assess correctness when you combine the two in one change.

Accepting this change to unblock the progress.

Address review comments.

Still digging through the main logic. In the meantime see some minor comments inline.

Added a note into the doc that a GC parseable copy operation is not required to take a safepoint.

Currently, if we have a loop with a safepoint poll it is not converted into a memcpy/memmove. This is because the safepoint has read semantic and prevents LoopIdiomRecognize from performing the transform. In theory we can have a transform which recognizes loops with safepoints and converts them to non-leaf memcpy/memmove. It will be up to this new transform to figure out the legality and interactions with the runtime requirements.

This was a draft. Abandoned in favor of D88861.

@mtrofin, I think it makes sense to have these tests available in all configurations. We have a bunch of printer passes which are not conditioned by NDEBUG.

Look good.

In D81026#2069624, @mtrofin wrote:

That sounds fine, my point is that having some run on benchmarks to quantify the benefit would help understand the value of this particular omission from the cost analysis (or at minimum show there's no regression, or understand where the regressions may be). It could shed important insights into what matters for the cost analysis, basically.

Can you please elaborate what is the issue you are solving? May be give an example?

Demonstrating an improvement accuracy due to PHI translation turned out to be a bit tricky.

Finished by @ebrevnov as D65276.

I reworked the patch using PHITransAddr. Now instead of tracking the backedge flag I keep track of the address to check and translate the address when needed.

Couple of nit comments inlined, LGTM once addressed.

In D74346#1873034, @davidxl wrote:

what is the use case of these options? Do hidden nodes create too much noise?

LGTM with the renaming addressed.

Ping?

• Comment cleanup was landed separately
• Fixed the issue mentioned in https://reviews.llvm.org/D68006#inline-616849
• Added more tests

Yeah, this limitation seems arbitrary and overly conservative.

Can we handle the case with inbounds offsets only first and extend with non-inbounds support in a follow up change? This way in the first change you'll not need to change IR interfaces at all.

LGTM. Maybe add a test when the WC has one use but the branch condition is used in multiple branches.

Ping?

This change was resubmitted as D68006.

In D67870#1680256, @efriedma wrote:

This is specifically a hole in the calloc() handling, right? This case can't come up in regular load->store no-op stores: the address of the load dominates the load, so the address dominates all the operations between the load and the store, so alias() does the right thing.

That's right. I don't think that load->store case is affected.

It looks like you successfully avoid the pitfall the original original loop predication fell into by filtering implicit exits and using trip counts. It makes me think that we can revisit loop predication again and go back to SCEV based implementation.

+1 to a test.

In D67870#1680256, @efriedma wrote:

It looks like you forgot to CC llvm-commits? Please post a new differential so the patch is sent to the list.

Resubmitted as D68006.

We should just skip debug instructions while looking for the guard in the window. Just use getNextNonDebugInstruction instead of current getNextNode.

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?