RFR: 8275202: C2: optimize out more redundant conditions

[Roland Westrelin]

On Wed, 4 Oct 2023 13:27:52 GMT, Emanuel Peter <epeter 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 ...
>
> src/hotspot/share/opto/loopConditionalPropagation.cpp line 137:
> 
>> 135: }
>> 136: 
>> 137: void PhaseConditionalPropagation::enqueue_uses(const Node* n, Node* c) {
> 
> This sounds like `PhaseCCP::push_child_nodes_to_worklist` and `PhaseIterGVN::add_users_to_worklist`.
> Looks like it will be quite easy to forget some "notification-pattern". Do you have some kind of verification that everything was processed to the full extent, just like `PhaseIterGVN::verify_node_value`, which is used for both IGVN and CCP?
> 
> [JDK-8298094](https://bugs.openjdk.org/browse/JDK-8298094) Refactor PhaseCCP and IGVN notification

You're right. Having shared code to push uses that's shared across CCP, IGVN and this would be nice. There are 2 kind of issues, right: 1) missed opportunities that are otherwise harmless 2) inconsistencies that cause something to break. I would be happy if this was guaranteed to avoid 2) initially. There's verification code that checks that no further progress can be made once we reached a fixed point.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/14586#discussion_r1347348567