RFR: 8275202: C2: optimize out more redundant conditions

[Roland Westrelin]

On Wed, 21 Jun 2023 12:47:26 GMT, Roland Westrelin <roland at openjdk.org> wrote:

> This change adds a new loop opts pass to optimize redundant conditions
> such as the second one in:
> 
> 
> if (i < 10) {
>   if (i < 42) {
> 
> 
> In the branch of the first if, the type of i can be narrowed down to
> [min_jint, 9] which can then be used to constant fold the second
> condition.
>   
> The compiler already keeps track of type[n] for every node in the
> current compilation unit. That's not sufficient to optimize the
> snippet above though because the type of i can only be narrowed in
> some sections of the control flow (that is a subset of all
> controls). The solution is to build a new table that tracks the type
> of n at every control c
> 
> 
> type'[n, root] = type[n] // initialized from igvn's type table
> type'[n, c] = type[n, idom(c)]
> 
> 
> This pass iterates over the CFG looking for conditions such as:
> 
> 
> if (i < 10) {
> 
> 
> that allows narrowing the type of i and updates the type' table
> accordingly.
> 
> At a region r:
> 
> 
> type'[n, r] = meet(type'[n, r->in(1)], type'[n, r->in(2)]...)
> 
> 
> For a Phi phi at a region r:
> 
> 
> type'[phi, r] = meet(type'[phi->in(1), r->in(1)], type'[phi->in(2), r->in(2)]...)
> 
> 
> Once a type is narrowed, uses are enqueued and their types are
> computed by calling the Value() methods. If a use's type is narrowed,
> it's recorded at c in the type' table. Value() methods retrieve types
> from the type table, not the type' table. To address that issue while
> leaving Value() methods unchanged, before calling Value() at c, the
> type table is updated so:
> 
> 
> type[n] = type'[n, c]
> 
> 
> An exception is for Phi::Value which needs to retrieve the type of
> nodes are various controls: there, a new type(Node* n, Node* c)
> method is used.
> 
> For most n and c, type'[n, c] is likely the same as type[n], the type
> recorded in the global igvn table (that is there shouldn't be many
> nodes at only a few control for which we can narrow the type down). As
> a consequence, the types'[n, c] table is implemented with:
> 
> - At c, narrowed down types are stored in a GrowableArray. Each entry
>   records the previous type at idom(c) and the narrowed down type at
>   c.
> 
> - The GrowableArray of type updates is recorded in a hash table
>   indexed by c. If there's no update at c, there's no entry in the
>   hash table.
> 
> This pass operates in 2 steps:
> 
> - it first iterates over the graph looking for conditions that narrow
>   the types of some nodes and propagate type updates to uses until a
>   fix point.
> 
> - it transforms the graph so newly found constant nodes are folded.
> 
> 
> The new pass is run on every loop opts. There are a couple rea...

Hi Roberto,

Thanks for the beedback.

> Do you know of other benchmarks / applications where the proposed optimization gives measurable overall improvements?

I'm not. Out of curiosity, have you tried anything from Renaissance?

> I also compared the overall C2 speed (as reported by `-XX:+CITime` in bytes/s) with and without `UseLoopConditionalPropagation` on DaCapo and SPECjvm2008 (x64 only), additionally using `-Xbatch -XX:-TieredCompilation` to reduce variability. Overall, in this context the proposed pass slows down C2 by more than 10%, see results here: [C2-median-speed-baseline-vs-JDK-8275202.pdf](https://github.com/openjdk/jdk/files/13476248/C2-median-speed-baseline-vs-JDK-8275202.pdf) and normalized version here: [C2-median-speed-baseline-vs-JDK-8275202-normalized-to-baseline.pdf](https://github.com/openjdk/jdk/files/13476257/C2-median-speed-baseline-vs-JDK-8275202-normalized-to-baseline.pdf).

Thanks for the details. I'm aware of the impact on compilation time and I will propose a new change where the slow down is not as big (the new pass is run less often).

-------------

PR Comment: https://git.openjdk.org/jdk/pull/14586#issuecomment-1829830903