RFR: 8275202: C2: optimize out more redundant conditions

[Roland Westrelin]

On Wed, 18 Dec 2024 13:35:48 GMT, Quan Anh Mai <qamai 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 519:
> 
>> 517:           Node* cmp2 = cmp->in(2);
>> 518:           sync(iff);
>> 519:           // narrowing the type of a LoadRange could cause a range check to optimize out and a Load to be hoisted above
> 
> Not sure if you are still working on this one. Here you can remove the range check if you pin all the nodes that depend on this check. Similar logic can be found in range check smearing.

Yes, I'm still working on this. I'll update this PR soon, hopefully. I reworked it quite a bit.

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

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