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

[Roland Westrelin]

On Wed, 14 Dec 2022 13:26:43 GMT, Roland Westrelin <roland at openjdk.org> wrote:

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

This pull request has now been integrated.

Changeset: af474ce3
Author:    Roland Westrelin <roland at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/af474ce35997315774e408f2e8a1beecf8349c75
Stats:     247 lines in 5 files changed: 220 ins; 15 del; 12 mod

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

Reviewed-by: kvn, vlivanov

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

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