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

[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".

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

Depends on: https://git.openjdk.org/jdk/pull/11666

Commit messages:
 - fix

Changes: https://git.openjdk.org/jdk/pull/11673/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=11673&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8297582
  Stats: 211 lines in 5 files changed: 188 ins; 13 del; 10 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