Integrated: 8282043: IGV: speed up schedule approximation

[Roberto Castañeda Lozano]

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).

This pull request has now been integrated.

Changeset: 003aa2ee
Author:    Roberto Castañeda Lozano <rcastanedalo at openjdk.org>
URL:       https://git.openjdk.java.net/jdk/commit/003aa2ee76df8e14cf8e363abfa2123a67f168e7
Stats:     24 lines in 1 file changed: 0 ins; 22 del; 2 mod

8282043: IGV: speed up schedule approximation

Reviewed-by: chagedorn, kvn

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

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