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?

Looks good to me.

@arsenm @hiraditya
Are you fine with committing the patch as-is and exploring using the incremental updater later?

Fix a typo

I'd like to commit this simple fix as-is, make sure no buildbots complain, and then introduce a proper incremental updating in a later revision.

In D68154#1687316, @kuhar wrote:

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

Thanks for the comments, @arsenm and @hiraditya.

The changes to verifier caught a MDT bug on AArch64:

test/CodeGen/AArch64/tailmerging_in_mbp.ll -mtriple=aarch64-eabi -verify-machine-dom-info 
DominatorTree is different than a freshly computed one!
	Current:
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 25 slow queries.
  [1] %bb.0 {4294967295,4294967295} [0]
    [2] %bb.1 {4294967295,4294967295} [1]
      [3] %bb.2 {4294967295,4294967295} [2]
        [4] %bb.3 {4294967295,4294967295} [3]
          [5] %bb.7 {4294967295,4294967295} [4]
          [5] %bb.4 {4294967295,4294967295} [4]
            [6] %bb.5 {4294967295,4294967295} [5]
              [7] %bb.6 {4294967295,4294967295} [6]
    [2] %bb.8 {4294967295,4294967295} [1]
Roots: %bb.0

Seems fine to me. Thanks for the fixes.
Please wait some time and see if others are OK with this change too.