konsoletyper / teavm

Compiles Java bytecode to JavaScript, WebAssembly and C
https://teavm.org
Apache License 2.0
2.55k stars 262 forks source link

Improve performance of dependency analysis phase #794

Open konsoletyper opened 8 months ago

konsoletyper commented 8 months ago

Currently, it's the most memory and time consuming phase of compilation, especially for large code bases. There are some thoughts how this could be improved:

  1. Instead of storing full set of reached typed for each node, a new "overflow" mechanism can be used: when the number of types of a node reaches some limit, "merge" this node with special "all reachable types" node. This also makes unnecessary special kind of "fast dependency analysis": the same effect can be achieved by controlling type number threshold (e.g. by setting it to 1).
  2. Sometimes type propagation should be stopped and graph optimization could be performed: all loops merged into one node, nodes sorted topologically, etc.
  3. Sort nodes topologically so that propagation could be done from the first node to the last one instead of current queue-based approach
  4. Sometimes all nodes of graph should be fully re-created in topological order to achieve better space locality and to reduce CPU cache misses.