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

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

Commit messages:
 - Do not precompute common dominators

Changes: https://git.openjdk.java.net/jdk/pull/8037/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=8037&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8282043
  Stats: 24 lines in 1 file changed: 0 ins; 22 del; 2 mod
  Patch: https://git.openjdk.java.net/jdk/pull/8037.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/8037/head:pull/8037

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

Reply via email to