RFR: 8275202: C2: optimize out more redundant conditions

[Roland Westrelin]

On Wed, 4 Oct 2023 13:53:48 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 927:
> 
>> 925: 
>> 926:  The second if is redundant but first if updates the type of i-1, not i alone, we can't tell i != 0.
>> 927:  Because i-1 becomes top in the second if branch, we can tell that branch is dead
> 
> Ok. So we have some value that becomes top in this branch.
> So if any value is TOP at a control, then we have to assume that the control is dead?
> 
> This is really cool. But what happens if we do things like `i + 1 > 0` and `i - 1 < 0`? I guess that would not give us more info about `i` or if anything was still valid or TOP?

`i + 1 > 0` and` i - 1 < 0` doesn't work indeed.

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

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