RFR: 8282043: IGV: speed up schedule approximation

[Christian Hagedorn]

On Wed, 30 Mar 2022 11:42:45 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

> Schedule approximation for building the _clustered sea-of-nodes_ and _control-flow graph_ views is an expensive computation that can sometimes take as much time as computing the layout of the graph itself. This change removes the main bottleneck in schedule approximation by computing common dominators on-demand instead of pre-computing them.
> 
> Pre-computation of common dominators requires _(no. blocks)^2_ calls to `getCommonDominator()`. On-demand computation requires, in the worst case, _(no. Ideal nodes)^2_ calls, but in practice the number of calls is linear due to the sparseness of the Ideal graph, and the change speeds up scheduling by more than an order of magnitude (see details below).
> 
> #### Testing
> 
> ##### Functionality
> 
> - Tested manually the approximated schedule on a small selection of graphs.
> 
> - Tested automatically that scheduling and viewing thousands of graphs in the _clustered sea-of-nodes_ and _control-flow graph_ views does not trigger any assertion failure (by instrumenting IGV to schedule and view graphs as they are loaded and running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4`).
> 
> ##### Performance
> 
>  Measured the scheduling time for a selection of 100 large graphs (2511-7329 nodes). On average, this change speeds up scheduling by more than an order of magnitude (15x), where the largest improvements are seen on the largest graphs. The performance results are [attached](https://github.com/openjdk/jdk/files/8380091/performance-evaluation.ods) (note that each measurement in the sheet corresponds to the median of ten runs).

That's a great improvement! Looks good.

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

Marked as reviewed by chagedorn (Reviewer).

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