RFR: 8281539: IGV: schedule approximation computes immediate dominators wrongly

[Roberto Castañeda Lozano]

On Wed, 9 Feb 2022 15:16:42 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

> The `ServerCompiler` module in IGV computes an approximation of C2's schedule for unscheduled graphs, for clustering and showing control flow information in the "Control Flow" window. This approximation uses domination information to guide the scheduling of nodes into basic blocks. Currently, this information is computed with a custom algorithm implementation that gives wrong results for some graphs, as shown in [the issue report](https://bugs.openjdk.java.net/browse/JDK-8281539).
> 
> This change simply replaces the custom implementation with one from the [T. J. Watson Libraries for Analysis (WALA)](https://github.com/wala/WALA), a popular set of static analysis libraries licensed under the [OSI](http://www.opensource.org/)-approved [Eclipse Public License](http://www.eclipse.org/legal/epl-v10.html). The replacement gives correct domination information for the reported graphs and reduces significantly the complexity of the `ServerCompiler` module.
> 
> #### Testing
> 
> - Tested manually that the dominator tree computed for a few selected graphs (included the reported one) is correct.
> - Tested manually, for large graphs, that the dominator tree computation takes a negligible fraction (around 1%) of the entire graph scheduling time.
> - 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`).

Thanks Christian and Nils for reviewing!

@neliasso: yes, there are multiple sources of inaccuracy in IGV's schedule approximation, and this change addresses just one of them. [JDK-8280568](https://bugs.openjdk.java.net/browse/JDK-8280568) addresses another one (work in progress), and I am still collecting and documenting others.

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

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