RFR: 8275202: C2: optimize out more redundant conditions

[Vladimir Kozlov]

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...

1. Yes, it is worth pursuing. This is obvious missing optimization opportunity.
2. Yes, not directly related changes could be pushed separately.

Do you know why CCP phase can't help for simple cases (not in loop)? Can we fix CCP to handle simple cases?

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

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