RFR: 8297582: C2: very slow compilation due to type system verification code [v5]

[Roland Westrelin]

> The problem here is that for arrays, verification code computes a
> number of meet operations that grows exponentially with the number of
> dimensions while the number of unique meet operations that need to be
> computed is a linear function of the number of dimensions:
> 
> 
> // With verification code, the meet of A and B causes the computation of:
> // 1- meet(A, B)
> // 2- meet(B, A)
> // 3- meet(dual(meet(A, B)), dual(A))
> // 4- meet(dual(meet(A, B)), dual(B))
> // 5- meet(dual(A), dual(B))
> // 6- meet(dual(B), dual(A))
> // 7- meet(dual(meet(dual(A), dual(B))), A)
> // 8- meet(dual(meet(dual(A), dual(B))), B)
> //
> // In addition the meet of A[] and B[] requires the computation of the meet of A and B.
> //
> // The meet of A[] and B[] triggers the computation of:
> // 1- meet(A[], B[][)
> //   1.1- meet(A, B)
> //   1.2- meet(B, A)
> //   1.3- meet(dual(meet(A, B)), dual(A))
> //   1.4- meet(dual(meet(A, B)), dual(B))
> //   1.5- meet(dual(A), dual(B))
> //   1.6- meet(dual(B), dual(A))
> //   1.7- meet(dual(meet(dual(A), dual(B))), A)
> //   1.8- meet(dual(meet(dual(A), dual(B))), B)
> // 2- meet(B[], A[])
> //   2.1- meet(B, A) = 1.2
> //   2.2- meet(A, B) = 1.1
> //   2.3- meet(dual(meet(B, A)), dual(B)) = 1.4
> //   2.4- meet(dual(meet(B, A)), dual(A)) = 1.3
> //   2.5- meet(dual(B), dual(A)) = 1.6
> //   2.6- meet(dual(A), dual(B)) = 1.5
> //   2.7- meet(dual(meet(dual(B), dual(A))), B) = 1.8
> //   2.8- meet(dual(meet(dual(B), dual(A))), B) = 1.7
> // etc.
> 
> 
> 
> There are a lot of redundant computations being performed. The fix I
> propose is simply to cache the result of meet computations. So whene
> the type system code is called to compute, for instance, the meet of
> A[][] and B[][], the cache starts empty. Then as the meet computations
> proceed, the cache is filled with meet result for meet of A[] and B[],
> meet of A and B etc. Once the type system code returns with the result
> for A[][] and B[][], the cache is cleared.
> 
> With this, the test case I added goes from "never seem to ever finish"
> to "complete in no time".

Roland Westrelin has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains eight commits:

 - remove new line
 - Merge branch 'master' of https://git.openjdk.org/jdk into JDK-8297582
 - review
 - Vladimir's review
 - build fix
 - fix
 - more fixes
 - Revert "8297934: [BACKOUT] Compiler should only use verified interface types for optimization"

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

Changes: https://git.openjdk.org/jdk/pull/11673/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=11673&range=04
  Stats: 247 lines in 5 files changed: 220 ins; 15 del; 12 mod
  Patch: https://git.openjdk.org/jdk/pull/11673.diff
  Fetch: git fetch https://git.openjdk.org/jdk pull/11673/head:pull/11673

PR: https://git.openjdk.org/jdk/pull/11673