Wow, this is fantastic. When I first started working on the domtree updater back in 2017, SimplifyGFG seemed like one of the most difficult passes to handle, and I wasn't sure if we ever get there. Very impressive work, @lebedev.ri!

LGTM

In D91767#2410579, @mkazantsev wrote:

I see the deep API problem here now. Current dominates(Value *, Instruction *) should not be called like that (at least because it returns false for dominates(X, X)). It has a different semantics, and should be called something like "canBeUserOf".

The clear definition of dominance between two instructions is also something fishy. Specifically, it is fishy for Phi nodes from the same block (there is no precedence between them). Maybe the best name to express what we need in this patch would be comesBefore.

It looks like a vast rework of whole DomTree API. I'm OK doing that, but do not want to have my patches waiting for this API rework (they honestly don't need). Let's unblock this branch first and then think how to name it better.

In D91767#2410450, @mkazantsev wrote:

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

I need the common dom to find the latest context where we can prove predicate so that it's also true for all given instructions.

In D91767#2410439, @mkazantsev wrote:

I was considering that, but don't really see how it's useful. The existing code makes N iterations, for which of them it either calls comesBefore or findNCD (findNCD will be called as many times as many different blocks there is - 1).

In the proposed solution, I'll need to:

• FIll the set of blocks (because API of findNCD needs blocks)
• Call multi-arg findNCD (which will call two-arg NCD same amount of times)
• make comesBefore queries for all instructions in topmost block.

Effectively it's always the same number of findNCD queries, overhead on set creation and potentially less number of comesBefore queries (in my solution we do it in all blocks). So overhead on set filling doesn't seem worth saving some number of cheap comesBefore queries in general case. So I just don't see why this alternative solution is better.

Looks fine to me, but I'm not confident enough to give an approval.

As an alternative implementation, have you considered teaching DomTree::findNCD to work with multiple basic blocks first, and then using this to implement the multi-instruction findNCD?
The algorithm would be like this: create a vector VBB of BB of all instructions, find its NCD, case split on the NCD and VBB being the same block or not.

Found some cosmetics, but I'm not familiar enough with the NPM to do a full review.

LGTM

Thanks for updating the comments.

OK, thanks for the clarification. Can you update the function-level comment with an explanation like this?

Interesting idea.

OK, thanks for looking into this.

One remaining thing: the function documentation needs to be updated:

Does this break any existing code?

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?