RFR: 8275202: C2: optimize out more redundant conditions

[Joshua Cao]

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

Would it make sense to handle this case in `IfNode::ideal()`? `IfNode::fold_compares` already handles more complicated cases of integer comparisons. We can match `cmp(i, constant)`, build integer range data, and eliminate IfNode's based on the data.

It won't be as powerful as the fixed point optimization that is proposed in this PR, but it is sufficient to cover the case mentioned in the JBS issue and would have less compile time overhead.

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

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