RFR: 8275202: C2: optimize out more redundant conditions [v2]

[Roland Westrelin]

On Fri, 6 Jun 2025 13:51:57 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 ...
>
> Roland Westrelin has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains three commits:
> 
>  - updated conditional propagation
>  - Merge branch 'master' into JDK-8275202
>  - conditional propagation

I finally updated this PR. The main push back from the previous version of this change was excessive compile time. The updated change addresses this issue. In the previous version of the change, the new optimization pass was run on every pass of loop optimizations. The reason for that was issues similar to the one explained in https://github.com/openjdk/jdk/pull/23468 . Running the new pass often was a way to mitigate the issue. Since the first version of this PR, I actually found code patterns where running the pass often was not even sufficient to prevent a crash. The change from 8349479 solves all those issues and running the pass only once or a few times doesn't cause any problem. This helps compilation time quite a bit. According to my rough measurement (running `CompileTheWorld` on java.base and looking at times reported by `CITime`), the overhead of the new pass is now around 20% for `IdealLoop` (from 4.7s to 5.7s) and around 2.5% on total compilation time (1 extra second on a
 round 40s of total compilation time).

I also refactored the code quite a bit, worked on integrating changes that are non specific to the new pass and is in other parts of the compiler so there are a lot fewer unrelated changes now, added more tests and comments.

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

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