Improve Native Image points-to analysis performance

[cstancu]

In 92d44c1 we merged a feature that improves the Native Image analysis performance: it significantly reduces both memory footprint and analysis time at the cost of a slight accuracy loss (see next paragraph for a detailed explanation). This feature will be part of the 20.1.0 release but it is disabled by default; it can be enabled using -H:+RemoveSaturatedTypeFlows. The reduced analysis accuracy means that the number of methods/types included in the image can increase. You can print these numbers with -H:+PrintAnalysisStatistics. The impact on analysis time can be observed by looking at the (typeflow) step of the analysis phase in the native-image output. The biggest impact will be observed on larger applications. Please try it and report any bugs. The plan is to turn the feature on by default as soon as we make sure it doesn't negatively impact downstream projects.

This change addresses a pathological performance issue for points-to analysis. For bigger applications, with many megamorphic call sites, the points-to analysis can exhibit a superlinear behavior, i.e., the analysis can explode when the program complexity increases. To address this issue we limit the types that are tracked for each individual type state, i.e., if the number of types in a type state increases above a predefined limit then we conservatively assume that it has the maximal type state, limited only by the statically inferred type bounds from Graal graphs and by the subset of types discovered as instantiated, and stop tracking individual updates to that type flow. Therefore, that type flow is considered to be saturated and completely removed from the type flow graph. For saturated invoke type flows this means that we stop tracking callees at each invocation site and instead we globally track all the reachable callees for each invocation target method. This approach reduces analysis time and memory consumption at the cost of a reduced analysis accuracy, i.e., it can increase the size of the reachable universe (types/methods/fields). In the experiments run so far, the reduced accuracy is minimal, while the analysis performance improvements are significant.

[samyc1201]

Probably it is not related, but I have been seeing -H:xxx arguments for the native-image command, but I couldn't find it here. Where are those -H:xxx arguments documented actually?

[jaikiran]

Hello @samyc1201,

The following command should show you all those available options for that particular version of native-image tool:

native-image --expert-options-all