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

Thu Feb 17 14:17:33 UTC 2022

This change improves the accuracy of IGV's schedule approximation algorithm w.r.t. C2 in two ways:

1. Scheduling 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 the special case S has multiple predecessors (i.e. (R, S) form a critical edge), N is scheduled into 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 obvious 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. Scheduling 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:

   <img src="https://user-images.githubusercontent.com/8792647/154481964-37d5c8a1-4243-49eb-a127-5a53f5ef0abb.png" width="95%">

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 does not trigger any assertion failure (by instrumenting IGV to schedule parsed graphs eagerly and running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4`) and does not warn with the message "inaccurate schedule: (...) are phi inputs but do not dominate the phi's input block.".

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

Commit messages:
 - 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
 - Schedule reachable pinned nodes before general scheduling
 - Move phi inputs above their source blocks and check schedule consistency

Changes: https://git.openjdk.java.net/jdk/pull/7493/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=7493&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8280568
  Stats: 402 lines in 3 files changed: 361 ins; 27 del; 14 mod
  Patch: https://git.openjdk.java.net/jdk/pull/7493.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/7493/head:pull/7493

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