Re: [patch][rfc] PR tree-optimization/21883

[Daniel Berlin <dberlin at dberlin dot org>]

> BTW, to not iterate, XLC, as an example, identifies all the
> opportunities top down by tracking live conditions, classifying the
> redundancy opportunities, and then does a transitive closure to find the
> rest of the "really" redundant ones (IE originally thought to be
> mergeable/redundant conditions where the live condition for the first
> candidate dominates the condition we believed to be the condition for
> the second block, making the second condition really redundant instead
> of just mergable or adjacent).
> 
> We currently do this all on the fly, so we have to iterate to discover
> that we could have made something else really redundant, etc.

As someone pointed out to me, there is still one corner case you may
need to iterate in if your goal is to merge every pair of adjacent
conditions, but it still will iterate much less than when we currently
iterate.

The case you may need to iterate in is when two conditions you were
considering merging because they were adjacent end up in blocks that are
modified due to merging other adjacent conditions.

However, this only needs to iterate when you *actually modify the blocks
involving those conditions*, whereas right now we iterate whenever the
CFG changes at all, regardless of whether it will actually affect any
conditions.  You also know the execution counts, etc, of the jumps that
have been potentially blocked so you can decide whether it is worth
iterating.

I sent Steven some detailed pseudocode of the algorithm.