The title and summary of this patch describe a problem, but they don't describe how this patch fixes that problem (which makes it hard to figure out if this patch is correctly fixing the problem). It should be more like "[GlobalMerge] Do XYZ: We have problem ABC, doing XYZ in GlobalMerge fixes it because ...". Also this patch needs tests.

LGTM.

LGTM.

In D57820#1399586, @john.brawn wrote:

It's a bit hard to know whether to accept this or not, given that you says it's "probably better to avoid LDXR". Do you have any data to say if it is any better or not?

It's a bit hard to know whether to accept this or not, given that you says it's "probably better to avoid LDXR". Do you have any data to say if it is any better or not?

LGTM. Looking at it it does make me wonder if we should handle things that aren't ConstantInt, e.g.

bitcast <2 x i16> <i16 0, i16 0> to i32

is still zero, though I'm guessing things like this actually probably never happen and this commit is fine as it is anyway.

Adjust according to review comments, and also add some more tests.

OK, then this looks good to me.

The idea behind allowing Scalar PRE when the addressing mode isn't legal is for some thing like (adjusted from pre-gep-load.ll)

define void @foo(i32 %stat, i32 %i, double* %p, double* %q) {
entry:
  switch i32 %stat, label %sw.default [
    i32 0, label %sw.bb
    i32 1, label %sw.bb
    i32 2, label %sw.bb2
  ]

It may be worthwhile allowing scalar PRE on GEPs that we know won't be combined into the addressing mode of a load/store, i.e. those where TargetTransformInfo::isLegalAddressingMode returns false.

LGTM.

This looks good, but I think that some of the comments need to be adjusted as they're no longer accurate for what the code is doing.

Added an option to enable control flow hoisting, turned off by default.

Looks OK as a fix for the reported bug, with one minor nitpick. Taking a look at PR39625 it looks like there's an underlying problem where we insert a load of useless placeholders, e.g. for

declare void @otherfn()

In D52827#1306034, @mkazantsev wrote:

This rehoisting stuff has been wary for me before, and now I'm completely hesitant about what is going on there. Why do we end up hoisting to some block that does not dominate its users? Do we have a strong reason of doing so rather than finding the correct hoisting destination?

The thing causing the crash was incorrect handling of instructions that need to be rehoisted. When we have hoisted a phi, then hoisted a use of that phi, then if have to rehoist that use we need to make sure that we rehoist it to _after_ the hoisted phi. We can do this by rehoisting to the immediate dominator instead of just rehoisting everything to the original preheader.

Update according to review comments.

In D52827#1295052, @mkazantsev wrote:

The patch fails the following test:

...

Likely some corner case related to conditional branch to the same block for true and false is not handled. Please make sure that it passes before we can proceed with the patch.

Also, we should be disabling this transformation when optimising for size.

A few general comments:

Use SmallVector for HoistedInstructions, rename getHoistedBlock, add LI and DT verification, other small changes.

Use LoopBlocksRPO to generate the worklist.

In D52827#1283474, @mkazantsev wrote:

I generally like what this patch is doing, but the size of code and its complexity overwhelms me. Is it possible to separate the patch into smaller pieces so that it would be easier to review them in isolation? If yes, I'd appreciate that a lot.

Because the ABI says that the GE bits are undefined on entry / return from public interfaces (i.e. non-static functions) I think that it is possible to just look at the current translation unit and make a decision based on that. I'm not sure if just looking at whether the sel intrinsic is used will work though - the GE bits could be read by __arm_rsr("APSR"), or by inline assembly, and maybe there are other situations that I haven't thought of.

A few errors in comments, but otherwise LGTM so long as you fix those errors before committing.

In D52827#1280717, @probinson wrote:

Does this lose debug information? I do very little with optimization passes so I don't know, but it would be nice to keep it in mind.

Update according to review comments.

Having some way to generate a pipeline string which matches what opt does by default is definitely a good thing. I think that long-term splitting up simplifycfg is probably the best way, and I think I'm going to have to do some of that myself as part of D50723 (as the current implementation causes a lot of problems for bugpoint as the pass list it deduces doesn't do the same thing as -Owhatever), but doing it in this way for now seems fine.

Ping.

In D52827#1257963, @john.brawn wrote:

In D52827#1257485, @reames wrote:

Starting with only high level design comments....

I think this patch is going about things in slightly the wrong way. As far as I can tell, there are two key components to this: 1) hoisting PHIs w/loop invariant selectors and operands, and 2) hoisting instructions from below conditional branches into conditional blocks inserted in preheader. I think these two can and should be separate into distinct patches.

I'm concerned about (2). This really seems like a form of loop peeling, and a currently unrestricted one without a cost model. I'm not sure I'm convinced this belongs in LICM at all.

(1) could be formulated w/o (2). The easiest way would be to form a select chain using the LIV conditions and LIV operands. This also works for any instruction for which we have a predicated form.

I'd not considered going direct from phi to select when hoisting. It seems like it will restrict the kinds of phis that can be hoisted, but we're probably not hoisting them anyway due to the various TODOs here. I'll look into it.

Update based on review comments, and add some more tests.

In D52827#1257485, @reames wrote:

Starting with only high level design comments....

I think this patch is going about things in slightly the wrong way. As far as I can tell, there are two key components to this: 1) hoisting PHIs w/loop invariant selectors and operands, and 2) hoisting instructions from below conditional branches into conditional blocks inserted in preheader. I think these two can and should be separate into distinct patches.

I'm concerned about (2). This really seems like a form of loop peeling, and a currently unrestricted one without a cost model. I'm not sure I'm convinced this belongs in LICM at all.

(1) could be formulated w/o (2). The easiest way would be to form a select chain using the LIV conditions and LIV operands. This also works for any instruction for which we have a predicated form.

In D52827#1254146, @efriedma wrote:

This has no impact by itself that I've been able to see, as LICM typically doesn't see such phis as they will have been converted into selects by the time LICM is run

That's surprising... I would have expected this to show up in some cases. Some branches can't eliminated due to side-effects.

LGTM. I think it may be possible to remove the hasAllowReciprocal check, because the point of that (as I understand it) is to allow converting a divide into a multiply-by-reciprocal in ways that can change the end result and I don't think that the transformation that's being done here will give a different result to the untransformed version, but I'm not certain of that and it's fine to leave it as it is.

The reason for the default of not emitting a size (which ends up having the effect of the alias having the same size as the aliasee) is for compatibility with gcc where if you have

I've adjusted the comment in the test case. I'm pretty sure that the part that the test is testing (that PRE is happening) is correct even if the equality propagation didn't happen, as it's based on knowing that the value of two pointers differs by a nonzero value and not anything to do with the provenance of the pointers.

LGTM.

Note: not currently for review, posted in order to refer to it in an llvm-dev RFC.