D42260 seems a better fix to this regression.

The idea to remove loop headers from destination list when selecting a threadable destination looks reasonable to me. This also fixes the regression we saw in spec2017/perlbench due to D36404.

Thanks for the reviews.

Hi everyone,

Thanks for the reviews.

Reduce unittest.

In D38960#899142, @kuhar wrote:

Thanks for adding the comment.

The testcase seems really long and it's not obvious why what it tries to exercise -- have you tried reducing it with bugpoint to something shorter and easier to reason about?

Add unittest and a comment.

In D38960#898713, @kuhar wrote:

I think that this deserves a comment with a (partial) example, otherwise the change looks suspicious.

In D38960#898701, @kuhar wrote:

For some irreducible CFG the domtree nodes might be dead, do not update domtree for dead nodes.

Can you show some example of such CFG and add a comment explaining this check?

DomTree::getNode return nullptr only for forward-unreachable CFG nodes.

Minor nit, use is_contained. NFCI.

I modified the test case per your suggestions before commiting. Thanks for taking a look.

fix the sequence of deleting an edge from DT.

Address review comments.

Added a comment in the test case to explain that the preheader is simplified during latesimplifycfg.

Kindly ping.

Thanks Daniel/Eli, I learnt something new today and am glad I asked the question. :)

Address review changes.

Fix make-check asserts.

Use batch updater to inform DT about CFG updates.

Rebased.

Precompute DT as suggested by Hal and Eli. Please take a look.

In D37866#882728, @craig.topper wrote:

What's going on with this patch? We also saw a performance regression on one of our benchmarks. And I was interested in whether this woudl help.

Added a testcase. Please take a look.

abandon this revision since it is a duplicate of D38263

Address Chad's testcase.

In D37343#880344, @efriedma wrote:

Remove quadratic complexity to calculate DT.

You're still computing DT once for every empty block?

Address review comments:

In D37343#875637, @efriedma wrote:

I think this needs more testcases to illustrate the different possibilities here.

Address Krzysztof's comment.

We need to figure out if LSR is doing something reasonable. It's possible that LSR is actually causing the regression, and old jumpthreading is just serving to obscure the loop structure (thus preventing LSR from doing whatever bad thing it's doing).

Address Eli's comment.

In D36404#870092, @hfinkel wrote:

In D36404#869695, @bmakam wrote:

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

I reverted this change and it recovered the regression. I was going to try to re-run the whole jumpthreading pass after latesimplifycfg to see if it would help, but I don't know if it is a good place because LSR that runs after, will not have the loop in canonical form and loopsimplify will again turn it into irreducible loop. Another place I was thinking was to try before CGP.

If it'll work right before CGP, that's probably best. That way targets can run IR-level passes that want to look at loops before that.

I tried right after latesimplifycfg and it almost recovers the regression. However, running it right before CGP made it even worse for performance of spec2017/perlbench. It seems to be due to some kind of bad interaction with LSR, I haven't digged deeper. Would running right before LSR be reasonable?

kindly ping.

In D36404#869657, @kparzysz wrote:

Have you tried it? Changing jump threading to have early/late versions is trivial, the question is when should the late one run, and if that would help in the first place.

In D36404#835401, @kparzysz wrote:

On our internal benchmarks it's mostly neutral, but the benchmark that motivated it improved by 5.3%. We have some extra code, though, that is supposed to deal with similar cases, so some of the impact may be reduced. By default it keeps the behavior unchanged, so for all other architectures it should have no effect.

Subsumed by D37343

• Added some more checks to allow merging empty cases when we can estimate extra moves are not added.
• Added test cases.
• spec2017/perlbench improves by 4.5%. No other improvements or regressions observed in Spec.

Is the actual value of the PHI operand relevant here? It looks like some of the testcases on r289988 involve constants, which are materialized during isel (and can be substantially more expensive).

I took a stab at this and created D37343. Please take a look.

Thanks for the review.

Move assert closer to AA->alias call.

rebase and fix x86 lit test.

ContainFolderableUsersInLoop -> ContainFoldableUsersInLoop?

Trim the patch and avoid handling stack references for non-value MMOs to prevent LNT test failures.

I have looked into the phi operands closely and I am not convinced if phi operands involving constants have any influence on the profitability of merging empty blocks. I identified empty exit blocks if when merged with their successors improved the performance a bit, yet if another similar empty exit block was merged with the destination block, it sinks the performance. The only difference between them is that the successor block is also empty when the performance regressed.

Thanks for taking a look. Rebased and committed in r310825.

In D35584#829791, @efriedma wrote:

To clarify, the original version of this patch recovered the full 3% regression, but the new version only recovers 0.7%?

Correct.

Is the actual value of the PHI operand relevant here? It looks like some of the testcases on r289988 involve constants, which are materialized during isel (and can be substantially more expensive).

Thanks Eli, this looks interesting. Another observation is that if we increase cgp-freq-ratio-to-skip-merge to 1000 it will recover the full 3% regression. I am trying to reduce the exact basic block which when skipped merging in CGP removes placing copies in hot path and improves performance due to reduced dynamic instruction count and the basic block(s) which when merged eliminate the unnecessary branches and improve the performance due to better branching/i-cache utilization. This might provide an answer to your question about the relevance of PHI operands.

In D36404#834053, @mcrosier wrote:

@bmakam: Isn't this very similar to some of your recent work?

Update to address Eli's comments.

A gentle ping.

Updated patch to address the underlying issue.

The underlying issue is that after loopsimplify creates empty exit blocks, CGP cannot clean up the empty blocks if it happens to be coming from a switch case. I am working on an alternative approach to address this issue.