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

[Tobias Hartmann]

On Fri, 29 Apr 2022 13:37:12 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

>> This changeset improves the accuracy of IGV's schedule approximation algorithm by
>> 
>> 1) scheduling pinned nodes in the same block as their corresponding control nodes (or in the immediate successor block for nodes pinned to block projections); and
>> 2) scheduling phi input nodes above the phi block, in their corresponding control path.
>> 
>> The combined effect of these scheduling improvements can be seen in the example below. In the current version of IGV **(before)**, `135 ClearArray` is wrongly scheduled in the same block as its output phi node (`91 Phi`). After this changeset **(after)**, `135 ClearArray` is correctly scheduled above the phi node, in its corresponding control path. Since `135 ClearArray` is pinned to the block projection `151 True`, a new block is created between `151 True` and `91 Phi` to accommodate it.
>> 
>> ![fix](https://user-images.githubusercontent.com/8792647/165956029-8e8bae8c-d836-444c-8861-2c13f52c22c6.png)
>> 
>> Additionally, the changeset 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 if these invariants are broken. Warning 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. The warnings are reported both textually in the IGV log and visually for each node, if the corresponding filter ("Show node warnings") is active:
>> 
>> ![warning](https://user-images.githubusercontent.com/8792647/165957171-50c2bcb9-0247-45cc-b806-c4e811996ce4.png)
>> 
>> Node warnings are implemented as a general filter and can be used in custom filters for other purposes, for example highlighting nodes that match a certain property of interest.
>> 
>> #### Testing
>> 
>> ##### Functionality
>> 
>> - Tested manually that 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 "Phi input that does not dominate the phi's input block".
>> 
>> ##### Performance
>> 
>> Measured that the scheduling time is not slowed down for a selection of 89 large graphs (2511-7329 nodes). The performance results are attached (note that each measurement in the sheet corresponds to the median of ten runs).
>
> Roberto Castañeda Lozano has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 12 commits:
> 
>  - Build dummy blocks in a single pass, refactor scheduleLatest, add warnings
>  - Merge branch 'master' into JDK-8280568
>  - Update copyright years
>  - Structure error reporting
>  - Recompute dominator info for final checks, as this is invalidated by block renaming
>  - Rename all blocks as a last step, to accomodate new blocks
>  - Schedule nodes pinned to critical-edge projections in edge-splitting blocks
>  - Make scheduling warning messages more readable
>  - Sink nodes pinned to block projections when possible
>  - Fix warning message
>  - ... and 2 more: https://git.openjdk.java.net/jdk/compare/e333cd33...35bb56fb

Awesome, looks good to me.

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

Marked as reviewed by thartmann (Reviewer).

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