RFR: 8275202: C2: optimize out more redundant conditions

[Dean Long]

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

OK, thanks for the explanation about the problem with casts.

Does your solution handle code like this?

    if (i >= 1) {
      if (i <= 2) {
        if (i != 2) {
          // do we know i == 1 here?

because the type system doesn't seem to handle != very well, unless it is != min or max.

BTW, the IR tests don't run with -XX:-UseLoopConditionalPropagation because it's not a recognized flag.

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

PR Comment: https://git.openjdk.org/jdk/pull/14586#issuecomment-1754051126
PR Comment: https://git.openjdk.org/jdk/pull/14586#issuecomment-1754051864
PR Comment: https://git.openjdk.org/jdk/pull/14586#issuecomment-1754051965