RFR: 8280568: IGV: Phi inputs and pinned nodes are not scheduled correctly [v2]

[Roberto Castañeda Lozano]

On Fri, 18 Feb 2022 08:36:20 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

>> This change improves the accuracy of IGV's schedule approximation algorithm w.r.t. C2 in two ways:
>> 
>> 1. Schedule each node N pinned to a control node R in:
>> 
>>    1a. the same block as R, if R is a "regular" control node such as `Region` or `Proj`. For example (N = `168 LoadP`, R = `75 Proj`):
>> 
>>    <p align="center">
>>    <img src="https://user-images.githubusercontent.com/8792647/154474596-ad326ad0-e127-4529-9837-6427c0a17314.png" width="50%">
>>    </p>
>> 
>>    or
>> 
>>    1b. R's successor block S, if R is a block projection node (such as `IfTrue` or `CatchProj`). For example (N = `92 LoadN`, R = `29 IfTrue`, S = `B4`):
>> 
>>    <p align="center">
>>    <img src="https://user-images.githubusercontent.com/8792647/154476147-4d53e2d9-db19-4449-bd79-053e6380cf4d.png" width="45%">
>>    </p>
>> 
>>    In case S has multiple predecessors (i.e. (R, S) form a critical edge), N is scheduled in a critical-edge-splitting block between R and S. For example (N = `135 ClearArray`, R = `151 IfTrue`, S=`B5` in _(before)_ and `B8` in _(after)_, and `B5` is the new critical-edge-splitting block in _(after)_):
>> 
>>    <p align="center">
>>    <img src="https://user-images.githubusercontent.com/8792647/154487037-24d3f147-b592-484a-bdf2-e93c3bec053c.png" width="90%">
>>    </p>
>> 
>>    Note that in _(after)_, B5 is a predecessor of B8. This can be seen in the CFG view, but is not visible in the sea-of-nodes graph view, due to the lack of control nodes in the blocks such as B5 created by critical-edge splitting.
>> 
>> 2. Schedule each node N that is input to a `Phi` node P in a block that dominates P's corresponding predecessor block B. For example (N = `36 ConvI2L`, P = `33 Phi`, B = `B2`):
>> 
>>    <p align="center">
>>    <img src="https://user-images.githubusercontent.com/8792647/154479876-1e2ae61a-a9a9-453f-b031-55d5dce17ce7.png" width="55%">
>>    </p>
>> 
>> The combined effect of these scheduling improvements can be seen in the subgraph below, that illustrates cases 1b (where a critical edge must be split) and 2. In _(before)_, `135 ClearArray` is both input to a phi node `91 Phi` and pinned to a block projection `151 IfTrue` on a critical edge (B7, B5), hence (_after_) a new critical-edge-splitting block B5 is created in which `135 ClearArray` and the rest of nodes pinned to `151 IfTrue` are scheduled:
>> <p align="center"> 
>> <img src="https://user-images.githubusercontent.com/8792647/154481964-37d5c8a1-4243-49eb-a127-5a53f5ef0abb.png" width="95%">
>> </p>
>> 
>> Additionally, the change introduces checks on graph invariants that are assumed by scheduling approximation (e.g. each block projection has a single control successor), warning the IGV user about possible issues in the schedule if these invariants are broken. Emitting warnings and gracefully degrading the approximated schedule is preferred to just failing since one of IGV's main use cases is debugging graphs which might be ill-formed.
>> 
>> These changes increase the overhead of scheduling large graphs by about 10-20%, however there are opportunities for speeding up scheduling by about an order of magnitude (see [JDK-8282043](https://bugs.openjdk.java.net/browse/JDK-8282043)) that would more than compensate for this overhead.
>> 
>> #### Testing
>> 
>> - Tested manually that the phi inputs and pinned nodes are scheduled correctly for a few selected graphs (included the reported one).
>> - Tested automatically that scheduling tens of thousands of graphs (by instrumenting IGV to schedule parsed graphs eagerly and running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4`) does not trigger any assertion failure and does not warn with the message "inaccurate schedule: (...) are phi inputs but do not dominate the phi's input block.".
>
> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Update copyright years

Switching back to draft mode to incorporate some offline feedback about reporting of scheduling warnings, and possibly generalize the scheduling algorithm to cover additional, related cases.

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

PR: https://git.openjdk.java.net/jdk/pull/7493