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

[Roland Westrelin]

On Mon, 9 Jan 2023 09:41:27 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".
>
> 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"

FTR, merged now that interface changes are in.

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

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