lgtm.

Abandon the review.

Philip, I'm not sure that I completely follow your comment about spirit of the tests but I've added a coverage for size/alignment.
I hope it will be enough.

Ping, any progress on this?

I've verified that this patch fixes the original problem.

I was able to create a pure LLVM reproducer for this issue and filed a bug https://bugs.llvm.org/show_bug.cgi?id=40061.
Could you please take a look into it?

Hello @wmi, in our local fuzzing testing we've got the following assert:
src/include/llvm/ADT/IntervalMap.h:630: unsigned int llvm::IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits>::insertFrom(unsigned int&, unsigned int, KeyT, KeyT, ValT) [with KeyT = llvm::SlotIndex; ValT = unsigned int; unsigned int N = 9u; Traits = llvm::IntervalMapInfo<llvm::SlotIndex>]: Assertion `!Traits::stopLess(b, a) && "Invalid interval"' failed.

abandon in favor of D54932.

In D54713#1312442, @wristow wrote:

@skatkov: About the loop unswitching suggestion, that sounds like a fine idea to me. But definitely outside the scope of this fix.

Absolutely agreed. It was just a sid comment.

(As an aside, other than a compiler-crash during vectorization (due to a deref of a null pointer), this is my first experience in the llvm vectorizer.  So I'm not familiar with how to go about adding the improvement you suggested.

I'm not sure whether you use a custom pipeline or not. But my point was that code came to vectorization pass seems strange because trivial loop unswitch optimization (provided by LoopUnswitch pass) could hoist the invariant check. By some reason it did not happen.

It's experience I'd like to gain, so I'll consider it as possible future work. But to make sure I'm not misleading you, I don't have time to work on this in the immediate future.)

Not a problem at all.

This is invalid patch.

LGTM. If Max or Sanjoy does not object in a, say, one day, feel free to land.

Comments updated.

Agreed, I missed comments in hurry. Will update a patch...

Hi @john.brawn, could you please take a look at https://reviews.llvm.org/D54932. It makes a compile time improvement and I guess we will not need this patch for a while.

In D54517#1308063, @john.brawn wrote:

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()

define i32 @fn(i32* %arg1, i32* %arg2) {
entry:
  %gep1 = getelementptr i32, i32* %arg1, i32 4
  %gep2 = getelementptr i32, i32* %arg1, i32 8
  br i1 undef, label %a1, label %b1

a1:
  call void @otherfn()
  br label %middle

b1:
  call void @otherfn()
  br label %middle

middle:
  br i1 undef, label %a2, label %b2

a2:
  call void @otherfn()
  br label %end

b2:
  call void @otherfn()
  br label %end

end:
  %phi = phi i32* [ %gep1, %a2 ], [ %gep2, %b2 ]
  %val = load i32, i32* %phi, align 4
  ret i32 %val
}

we insert a total of 9 placeholders, but actually we need only one and the rest get deleted later. So I think there's something that could be done to improve that, but that's no reason not to do this fix.

FYI: in parallel there is an idea how to simplify algorithm significantly. I'll try to implement it...

Feel free to mention @dmgreen in description who found this bug.

Thank you, Bjorn.

In D54517#1304803, @bjope wrote:

Basically I think the code looks ok. However, I'm not so familiar with this algorithm so it is hard to comment about the actual solution.

My understanding is that you introduce a threshold, and if the size of the TraverseOrder vector grows past the threshold we bail out from findCommon. So what is the impact of this?
I assume it means that we limit the amount of "Complex Addressing mode" optimizations somehow. Is this limit only hit for "large" programs? When compiling a program that hits the threshold, do we lose some optimizations or will the amount of Complex Addressing mode optimizations in such a program be reduced significantly?

How did you choose the current threshold? (that is probably something people want to know when trying to finetune this 4 years from now, so it could be nice to say something about it in the commit msg even if it just is an estimate)

Hi Bjorn, thank you for looking into this patch.

Basing on https://bugs.llvm.org/show_bug.cgi?id=23603 I think this patch is incorrect.

ping.

In D54289#1292458, @skatkov wrote:

In D54289#1292418, @skatkov wrote:

In D54289#1292417, @arsenm wrote:

There's also a sinking pass, why isn't this done there?

Sink pass is written in the way it sink instructions only to nearest successors while for invariant load I want to move it anywhere in CFG...

Ok, I was wrong Sink pass iterates. If I add a support for invariant.load it can sink it but it definitely cannot sink it through diamond or loop. In parallel I'm going to take a look deeper whether I can handle my case in Sink pass...

LGTM as well

In D54289#1292418, @skatkov wrote:

In D54289#1292417, @arsenm wrote:

There's also a sinking pass, why isn't this done there?

Sink pass is written in the way it sink instructions only to nearest successors while for invariant load I want to move it anywhere in CFG...

Ok, I was wrong Sink pass iterates. If I add a support for invariant.load it can sink it but it definitely cannot sink it through diamond or loop. In parallel I'm going to take a look deeper whether I can handle my case in Sink pass...

Handled comments. Fow a while I'll double check Sink.cpp...

In D54289#1292417, @arsenm wrote:

There's also a sinking pass, why isn't this done there?

Hi @arsenm, could you please take a look into this patch? If I turn the option on I see some AMDGPU test failures. I'm not an expert in AMDGPU asm/arch but it seems that 4 invariant loads are added in the beginning of pipeline in entry block and I hoist one of them to colder block. As a result as I understand instead of loading of two load at once this "double-load" is split into two loads. I'm not sure that it is a beneficial for this platform. So I wonder whether there is a easy way to prohibit optimization for such cases for this platform?
Even if there is no easy way to do that I'd like to land it with option off by default.

In general I think it is what we can go/start with.
This formula seems to be a bit pessimistic. Specifically not every candidate creates sibling loops. Only if all successors is in loop or there are sub-loops before unswitch candidate. So applying the power multiplier for this candidates seems unreasonable.
Also it is possible that several unswitch candidates can be done at one shot (the same condition), in this case the number of siblings will not grow so fast.
But these improvements can be done as a follow-up if needed.

In D54007#1289874, @bjope wrote:

In D54007#1289855, @skatkov wrote:

Just a note, there is a specific usage of this data structure.
Phi nodes are inserted in the initial step without any removals and then only removals are used.

So we should not see something like delete-insert.
So while data structure really suffers from what Bjorn wrote but in this specific application of this data structure I do not expect any problems...

Ok. Just worried that someone might find this set implementation nifty, trying to reuse it in some other part of the code or moving it to ADT, without considering this limitation regarding delete-insert.

Completely agreed!

Just a note, there is a specific usage of this data structure.
Phi nodes are inserted in the initial step without any removals and then only removals are used.

LGTM, please wait a bit and if Bjorn does not object, feel free to land.

Also Max, please consider split this patch into two ones. One just NFC patch with analysis and update tests to check the output of dump and then patches which does modifications.

The same comment as in D51777, The semantics of the patch itself lgtm.

I see that IndVarsSimplify uses class field Changed. You propose to use Changed as return value. I just want to see the same approach through the whole IndVars...

LGTM with follow-up handling of Changed. If you do not have cycles for handling Changed, please file a bug at least.

is it better?

Could you please add a test producing something with #2 and #3... I guess any loop pass for function with 2-3 loops should work.

Verifier fix landed, can we proceed with this change?

Test is updated to be valid.

ping. Can I do anything to proceed with this change?

Thank you! I've added two unit tests.

Thank you for your comment. Unfortunately till now I failed to create a test showing the benefit from this change in a pass (I tried). I can make one more try.
The problem I'm trying to solve is the following: in downstream pass I have a BitCast instruction which is actually originated from allocation but has a vector type gotten using gep + bitcast from allocation.
I'd like to know the fact that it is an underlying allocation but now utility function just ignore instructions with vector of pointers.

Test, actually can be simplified bit if you do not mind.

LGTM. If no one objects in 1-2 days, feel free to land.

Please take a look.