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

[Vladimir Kozlov]

On Wed, 14 Dec 2022 13:56:49 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 incrementally with one additional commit since the last revision:
> 
>   build fix

src/hotspot/share/opto/compile.cpp line 654:

> 652: #endif
> 653: #ifdef ASSERT
> 654:                   , _type_verif_cache(comp_arena(), 2, 0, VerifyMeetResult())

I assume it is typo: `_verif_`. Please use `_verify_`.

src/hotspot/share/opto/compile.cpp line 1084:

> 1082:   _phase_optimize_finished = false;
> 1083:   _exception_backedge = false;
> 1084:   _type_depth = 0;

Please use `_type_verify_depth` to show that it is related to the cache.

src/hotspot/share/opto/type.cpp line 845:

> 843: }
> 844: 
> 845: class TypeVerif {

Please change to `VerifyMeetMark`.

src/hotspot/share/opto/type.cpp line 918:

> 916:   TypeVerif verif(C);
> 917: #endif
> 918: 

Can `VerifyMeetResult` class be local to `Type` class instead of `Compile` since it is used only locally here and you reset cache each time anyway? (`Compile` is become very big with verification code from all parts of compiler).

I thought you build the cache for duration of compilation then it may make sense to keep it in `Compile`. But you are resetting it after each `meet` so you don't need to have it in `Compile`.

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

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