Mostly minor comments. I considered giving a conditional LGTM, but decided it warranted one last round. I think this is very close to landing.

Just noting a couple of known gaps (to save reviewers time):

• No verifier support (will add before submission)
• Need to add references from each support instruction type in the docs (done to avoid rebase headache)

Another round of bugs found.

I'm approving this in the current form, despite a bit of hesitation doing so. I'd like to see the conversation around the restriction of widening based on target block to continue. I think there's a good change we'll want to tweak the semantics there, but I see that as a minor tweak, not a major redesign.

Looked at the history in more detail, and decided I'm comfortable with this fix. So, LGTM.

This looks correct to me, but this is so glaringly bad I'd like a second set of eyes to make sure I'm not missing something. Can someone else confirm?

Overall, looks pretty good. One rounds of comments, but I'm expecting this to converge quickly.

LGTM w/ changes made before submit.

reverse last rebase, the small addition was buggy (iterator invalidation)

(slightly modified patch to reduce overhead for multiple predecessor case too)

rebase for minor issue I commented on, also ping?

No longer needed, and extremely stale.

All component pieces have been split and landed individually.

In D50925#1211383, @anna wrote:

Added example:

(snipped example for length)

In D50925#1211015, @anna wrote:

There are 3 kinds of tests worth adding:

1. predicated invariant stores, i.e. the block containing the store itself is predicated and not guaranteed to execute (cannot be handled by LICM)

Covered by existing early exit test.

2. invariant store value is a phi containing invariant incoming values and the phi result depends on an invariant condition (can be handled by LICM. This patch handles?)

Unclear what you mean here.

3. invariant store value is a phi containing invariant incoming values and the phi result depends on a variant condition (cannot be handled by LICM safely)

Again, I don't know what you mean by this. If the value is a phi in the loop, it's by definition not invariant.

with the right patch this time

rebase and incorporate suggestions.

Adding requested tests, ready for review.

Address first couple comments, another update to come before re-review justified.

Strip out the call hoisting bits until a future patch.

Rebase on top of tests, with test updates.

Committed as:
Author: reames
Date: Tue Aug 21 10:59:11 2018
New Revision: 340312

Max, I landed the changes for the test separately. I applied your check-label request, but not one about single iteration loops since the test file is filed with such. Anyone who wants to specialize single iteration loops has some work to do later anyways, so I didn't see any value.

Hold this one please. I have some concerns about the naming, but have lost track of the dependent patches and can't fully review. Once dependent changes have landed, let's revisit.

LGTM. Don't see where you're going with this, but the patch is obvious correct and doesn't make anything particularly messy.

I still feel the framing comment could use some improvement, but I don't have anything specific I can suggest.

Detailed comments inline.

Thinking about it, I think it may be worth introducing a separate isGuaranteedToExecuteBeforeLoopExit with the old logic. While LICM's hoisting logic needs the "must execute if loop entered" property, load store promotion actually only needs "store executes before any taken exits" property. (We do need one "must execute" dereferencing instruction, but it doesn't have to be the store.)

In D50480#1200014, @hsaito wrote:

In D50480#1199900, @reames wrote:

I have a general question about direction, not specific to this patch.

It seems like we're adding a specific form of predication to the vectorizer in this patch and I know we already have support for various predicated load and store idioms. What are our plans in terms of supporting more general predication? For instance, I don't believe we handle loops like the following at the moment:
for (int i = 0; i < N; i++) {

if (unlikely(i > M)) 
   break;
sum += a[i];

}

Can the infrastructure in this patch be generalized to handle such cases? And if so, are their any specific plans to do so?

Short answer is No.

From vectorizer perspective, mechanics is quite different.

Ok, I think we're talking past each other a bit. I see these both as forms of predication. It sounds like you have a slightly different view; I'll try to ask clarifying questions in the right spots. I think we have different mental models here and I'm trying to understand where that difference is.

In D50786#1200886, @hiraditya wrote:

There was discussion sometime back, might be worth looking at: https://groups.google.com/forum/#!topic/llvm-dev/uLvitfqEd_g

I'm missing why this is relevant? It happens to involve a volatile access as an AliasSet, but seems otherwise unrelated. From what I can tell, the "volatile implies mod" thing hasn't been true for years.

Max convinced me that there's no algorithmic complexity change implied here. Given the getLoopExits code walks all edges leaving blocks in the loop, both the old and new code is O(outbound edges of blocks in loop).

LGTM

In D48602#1198563, @vext01 wrote:

Do you know if anyone is actually using the stackmap functionality? As far as I know JavaScriptCore used to use it, but have since moved on.

Not that I know of. We (Azul) are using the statepoint infrastructure which shares many of the same ideas, but we are not using either STACKMAP or PATCHPOINT. I suspect we could generalize if needed, patches and discussion welcome!