Thanks for the numbers. LGTM.

Thanks for the table, this looks good to me now, modulo the two remaining nits. I'd be more comfortable if somebody familiar with the new pass manager reviewed this too.

This looks very useful. Does it currently report any errors when enabled?

Hi Nicoali,

This makes sense to me. I think the only missing piece is some documentation which also explains how to interpret when PostView is missing (PostView == nullptr ===> Current CFG is the implicit PostView?)

I think this deserves some extra documentation that explains what it means to preserve CFG in plain English. For example, should we also care about preserving the number of return blocks?

The code looks fine to me. Have you checked if compilation times are affected by this patch?

The patch looks fine to me, but I'm not familiar enough with the backend and GlobalIsel to review it.

One more thing: should this be backported for the upcoming 11.0 release?

In D84763#2181020, @yrouban wrote:

In D84763#2179638, @kuhar wrote:

Taking a few steps back, I'd love to see a cfg preservation check like D81558 ...

I'm about to update the patches.

In D84763#2179475, @kuhar wrote:

While this makes root finding insensitive to successors' order, I think it still may be possible to run into tree instability by changing the order of tree children (also plain domtree),...

I feel I do not understand. Any example?

and in turn changing DFS numbers used by other analyses. ...

I agree that DFS numbers are changed by successors swap, but can we make an exclusion for DFS numbers? If not, then this patch is useless because successors swap change CFG by definition (DFS numbers will be changes if we recalculate them).

AFAIK tree updates would still be based on some Cfg/Graph traits, which may give you unstable order.

As I see successors swap cannot be encoded for DomTreeUpdater. So this kind of change are not tracked.

I think this is a good direction.

In D84763#2179546, @lebedev.ri wrote:

In D84763#2179475, @kuhar wrote:

Given that you want to fix InstCombine not to swap successors and move this to SimplifyCFG, does this patch improve anything in the current pass pipeline?

I don't believe that is the correct fix, because it literally says "nope, there is no way to update PDT after swapping successors other than full domtree recomputation", that is why i'm pushing for fixing PDT.

In D84493#2171946, @yrouban wrote:

In D84493#2171849, @lebedev.ri wrote:

In D81089#2088014, @kuhar wrote:

<..> you have to chose some arbitrary way of selecting a fake-entry node from nodes in an scc. Right now this order is whatever children or inverse_children return, but could be based on the order of blocks in a function instead.

Ok. Let us try now. But why did not they do it a few years ago then?

Would it make sense to enable the canonicalization in SimplifyCFG and disable the one in InstCombine as a single patch?

Thanks for pushing on this.

One tiny nit: the function name ChildrenGet sounds kind of backwards to me, but it seems like the other direction is already taken.

Thanks for checking this. I dug up some old whole-program bitcode and uploaded it here in case it helps with future code reviews: https://drive.google.com/drive/folders/1VJpym19cW-8BVgdtl2MsD3zB4CoEQ93O?usp=sharing

In D83087#2139211, @nhaehnle wrote:

In D83087#2134881, @kuhar wrote:

modulo accidental formatting changes.

I'm not aware of any. Some line breaks changed because "const_iterator" is longer than "iterator".

LGTM modulo accidental formatting changes.

LGTM

Overall, this seems like a good idea to me. The amount of templated code started growing out of hand some time ago, to the point where it's really hard to make logically changes, especially in the generic updater code.

Overall, I think this is a good direction, but I'd like to understand better why InstCombine needs more than a few iterations and how 'fix' these cases without bailing out after a fixed number of iterations.
I'd be interested to find out if we can make an IR pattern generator that forces InstCombine to run N iterations. Are there any algorithmic guarantees of the current implementation which we could use to show that InstCombine doesn't go into an infinite loop?

In D81089#2086985, @nikic wrote:

If we define that changing successor order constitutes a CFG change, then these optimizations need to be dropped from InstCombine, and moved into SimplifyCFG.

As said before, InstCombine is supposed to be CFG-preserving -- if it isn't because the definition of what "CFG-preserving" means was unclear, then we need to fix InstCombine to be in line with we new definition.

As the pipeline diffs show, not preserving CFG has a very real cost (five new domtree calculations at least). We should try to avoid that :)

In D81089#2086290, @efriedma wrote:

Even if we agree the way the PostDominatorTree computes roots in cases involving infinite loops shouldn't depend on the ordering of successors, I'm not sure it's correct to say that instcombine "preserves the CFG". Even for the regular DominatorTree, I think reordering the successors invalidates DFS numbering (in the sense that it changes the result of getDFSNumIn()).

You can always preserve domtrees by marking dfsnumbers as invalid.

As a quick fix, maybe we could try to detect changes in reverse-unreachable code and update postdominators when that's detected? Not sure how much overhead that would be; InstCombine is already very expensive w.r.t. compilation times.

In D78881#2031146, @ekatz wrote:

Rename Invert2 variable to InvertCond2.
Hope it makes more sense.

I followed the new tests and the patch seems fine to me, but I'd rather someone else took a look too.

While this is fine, I'm I don't understand how splitting critical edges will interact with domtree updates when you call getBase in MachineDominators.h. But we can discuss that in another patch.

Could you add some basic unit tests and a separate set of unit tests where critical edges get split?

Looks good to me overall. I don't want to block it over the cosmetic issues like allocating the empty GD object.

In D77341#1960854, @asbirlea wrote:

Address comments.

LGTM

LGTM

Replace UINT_MAX with InstCombineDefaultMaxIterations

Fix instruction insertion in InstCombineCasts for zext-or-icmp.

In D71145#1788369, @nikic wrote:

I think it may be worthwhile to separate the limits for "stop after N iterations" and "assert after N iterations". In particular what I have in mind is that we can use -instcombine-max-iterations=2 in tests to ensure that correct worklist management allows everything to be folded in a single iteration (with the second establishing the fixed point). However, for this purpose -instcombine-max-iterations would actually need to assert. Possibly there's room for two separate options?

@lebedev.ri @spatel @craig.topper
Do you have any other feedback or questions/concerns about the patch?

In D71093#1783809, @lebedev.ri wrote:

I'm sorry, i'm not following the patch's logic anymore.
First it was about relying on Add() printing ADD: line, and now
all the printing stuff seems to be gone and the patch is adding some
invariants on when the instruction should be inserted into worklist?

Since the beginning, the patch was about ensuring that the instructions added to the worklist are properly inserted. One manifestation of instructions not being correctly inserted that was easy to observe was debug ADD lines with <badrefs> being printed.
One confusing thing that happened was that I followed a suggestion of reducing the amount of debug output printed and removing the line containing NEW that directly preceded ADD. But this change is no more and the amount of the debug output is the same.

In D71093#1783729, @spatel wrote:

Do you have a small IR example with before/after output that we can put here in the review? That way there's at least a record of what the improvement looks like.

Do you have any other feedback? @spatel @lebedev.ri

In D71145#1779870, @craig.topper wrote:

In my experience extra iterations are often caused by bad worklist management when updating nodes sometimes. For example https://reviews.llvm.org/D50990 was supposed to fix one case of that, but I never got around to finding the original test where I observed the issue. If that patch still applies does it have any effect on any of the extra iterations in the table?

Change the default iteration limit to UINT_MAX - 1.

I ran some experiments to see how many iterations of InstCombine are necessary on real-world C++ applications. I paste the results below.
The numbers were collected by running InstCombine in a Full-LTO-like scenario: first I compiled all the code with -O3 with *optimizations disabled*, then I linked it together (using gllvm), and gave it to opt with -O3.

Thanks for the suggestions.

I added an assertion checking if the instructions added have a parent (block).
Also restored the previous debug message.

This looks fine, I wonder whether it's worth testing [how easy it's to test, that is]

Would it be possible to add a verifyAnalysis function to MLI and check if a freshly calculated one matches the 'preserved' one?