RFR: 8349479: C2: when a Type node becomes dead, make CFG path that uses it unreachable [v2]

[Roland Westrelin]

On Fri, 7 Feb 2025 13:27:00 GMT, Roland Westrelin <roland at openjdk.org> wrote:

>> This is primarily motivated by 8275202 (C2: optimize out more
>> redundant conditions). In the following code snippet:
>> 
>> 
>> int[] array = new int[arraySize];
>> if (j <= arraySize) {
>>   if (i >= 0) {
>>     if (i < j) {
>>       int v = array[i]; 
>> 
>> 
>> (`arraySize` is a constant)
>> 
>> at the range check, `j` is known to be in `[min, arraySize]` as a
>> consequence, `i` is known to be `[0, arraySize-1]`. The range check
>> can be eliminated.
>> 
>> Now, if later, `i` constant folds to some value that's positive but
>> out of range for the array:
>> 
>> - if that happens when the new pass runs, then it can prove that:
>> 
>>     if (i < j) {
>> 
>> is never taken.
>> 
>> - if that happens during IGVN or CCP however, that condition is not
>>   constant folded. And because the range check was removed, there's no
>>   guard protecting the range check `CastII`. It becomes `top` and, as
>>   a result, the graph can become broken.
>>   
>> What I propose here is that when the `CastII` becomes dead, any CFG
>> paths that use the `CastII` node is made unreachable. So in pseudo code:
>> 
>> 
>> int[] array = new int[arraySize];
>> if (j <= arraySize) {
>>   if (i >= 0) {
>>     if (i < j) {
>>       halt();
>> 
>> 
>> Finding the CFG paths is implemented in the patch by following the
>> uses of the node until a CFG node or a `Phi` is encountered.
>> 
>> The patch applies this to all `Type` nodes as with 8275202, I also ran
>> in some rare corner cases with other types of nodes. The exception is
>> `Phi` nodes which may not be as easy to handle (and for which I had no
>> issue with 8275202).
>> 
>> Finally, the patch includes a test case that's unrelated to the
>> discussion of 8275202 above. In that test case, a `CastII` becomes top
>> but the test that guards it doesn't constant fold. The root cause is a
>> transformation of:
>> 
>> 
>> (CastII (AddI
>> 
>> 
>> into 
>> 
>> 
>> (AddI (CastII ) (CastII)`
>> 
>> 
>> which causes the resulting node to have a wider type. The `CastII`
>> captures a type before the transformation above happens. Once it has
>> happened, the guard for the `CastII` can't be constant folded when an
>> out of bound value occurs.
>> 
>> This is likely fixable some other way (eventhough it doesn't seem
>> straightforward). Given the long history of similar issues (and the
>> test case that shows that they are more hiding), I think it would
>> make sense to try some other way of approaching them.
>
> Roland Westrelin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   review

Thanks for having a look.

> Looks like this patch now does it not only for `CastII` nodes but for all `Type` nodes. It's an interesting idea but I'm not quite clear on the impact and how expensive the new recursive output search with a `Halt` node insertion is given that most of the time `Type` nodes will be dying normally together with their control path. It seems like this patch is only to fix some edge cases? But maybe the story is different with JDK-8275202.

The goal of the patch is to free us from having to worry about `Type` nodes becoming dead on a cfg path that doesn't fold ever again. With this patch, there's no need for assert predicates AFAIU. I'm not suggesting we throw them away, this said. But how many hours have we spent working on them? This same problem is getting in the way of 8275202. Sure, it's for corner cases but they are corner cases that have no solution other than fragile workarounds or new complicated construct that will leak in a lot of parts of the compiler (the way code handling assert predicates are all over the place now).

Cost in terms of compilation time could be evaluated the usual way. I haven't done any of that but I could.

> If it was only about `CastII` (or other `ConstraintCast`), could we also just insert the `Halt` node below the control node the `CastII` is pinned to instead (we now enforce that almost all `ConstraintCast` nodes, including `CastII`, are pinned)?

That's actually the first thing I tried but that doesn't work. A `Cast` can sometimes be dependent on some condition that was hoisted. What makes the `Cast` top is both some condition the `Cast` is control dependent on and the type of its input which can itself be control dependent on some control flow that's dominated by the control of the `Cast`.

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

PR Comment: https://git.openjdk.org/jdk/pull/23468#issuecomment-2722012244