[#2143] Strip references pass and collect them in checking
Motivation and Context
Problem
References pass takes too many cycles for the checker contract
(around 618.54M cycles). We can collect them during the type checking since
the typer looks for original binders with original locations.
Solution
Strip the references pass, introduce a references hashtable in the typer, fill it on each value/type/label/module resolution request.
Flame Graph Comparison
Before Stripping References Pass
Call graph 'ligo info get-scope --format dev --with-types --defs-only src/main.mligo':
--------------------------------------------------------------------------------------
[ 11.23G cycles in 1 calls ] - 72.42% : Scopes.run
[ 8.45G cycles in 1 calls ] | - 75.21% : Types_pass.Typing_env.type_program
[ 618.54M cycles in 1 calls ] | - 5.51% : References.declarations (src/main/scopes/references)
[ 618.54M cycles in 1 calls ] | | - 100.00% : References.declarations (src/main/scopes/references)
[ 310.68M cycles in 8752 calls ] | | | - 50.23% : References.resolve_module_alias_and_update_mvar_references
[ 211.58M cycles in 8752 calls ] | | | | - 68.10% : References.resolve_mpath
[ 42.88M cycles in 8752 calls ] | | | | - 13.80% : References.References.add_module_usages
[ 39.07M cycles in 8756 calls ] | | | | | - 91.12% : References.References.map_ref
[ 452.92K cycles in 8756 calls ] | | | | | - 1.06% : References.References.add_def_usage
[ 41.99M cycles in 8404 calls ] | | | | - 13.52% : References.References.add_def_opt_usage
[ 38.53M cycles in 8404 calls ] | | | | | - 91.76% : References.References.map_ref
[ 8.69M cycles in 8404 calls ] | | | | - 2.80% : References.References.add_maccess
[ 2.49M cycles in 6214 calls ] | | | | | - 28.68% : References.References.add_tvar
[ 2.00M cycles in 2190 calls ] | | | | | - 23.08% : References.References.add_vvar
[ 173.44M cycles in 38957 calls ] | | | - 28.04% : References.References.add_def_opt_usage
[ 160.36M cycles in 38350 calls ] | | | | - 92.46% : References.References.map_ref
[ 2.52M cycles in 38350 calls ] | | | | - 1.45% : References.References.add_def_usage
[ 46.92M cycles in 7904 calls ] | | | - 7.59% : References.References.add_ctor
[ 21.25M cycles in 5581 calls ] | | | | - 45.29% : References.References.map_ref
[ 14.31M cycles in 24212 calls ] | | | - 2.31% : References.References.add_tvar
[ 11.06M cycles in 14745 calls ] | | | - 1.79% : References.References.add_vvar
Note: Nodes accounting for less than 1.00% of their parent have been ignored.
Aggregated table:
----------------
Name; Filename; Calls; Time
ROOT; src/landmark.ml; 0; 15.51G
Scopes.run; src/main/scopes/scopes.ml:70; 1; 11.23G
Types_pass.Typing_env.type_program; src/main/scopes/types_pass.ml:774; 1; 8.45G
References.declarations; src/main/scopes/references.ml:732; 1; 618.54M
References.declarations; src/main/scopes/references.ml:721; 1; 618.54M
References.resolve_module_alias_and_update_mvar_references; src/main/scopes/references.ml:308; 8752; 310.68M
References.References.map_ref; src/main/scopes/references.ml:64; 61091; 259.21M
References.References.add_def_opt_usage; src/main/scopes/references.ml:115; 47361; 215.43M
References.resolve_mpath; src/main/scopes/references.ml:286; 8752; 211.58M
References.patch; src/main/scopes/references.ml:786; 1; 66.25M
Types_pass.patch; src/main/scopes/types_pass.ml:899; 2; 64.39M
References.References.add_ctor; src/main/scopes/references.ml:141; 7904; 46.92M
References.References.add_module_usages; src/main/scopes/references.ml:179; 8752; 42.88M
References.References.add_tvar; src/main/scopes/references.ml:132; 30426; 16.80M
References.References.add_vvar; src/main/scopes/references.ml:124; 16935; 13.07M
References.References.add_maccess; src/main/scopes/references.ml:216; 8404; 8.69M
References.References.add_def_usage; src/main/scopes/references.ml:80; 61091; 3.68M
References.patch_references; src/main/scopes/references.ml:747; 1; 853.82KAfter Stripping References Pass
Call graph 'ligo info get-scope --format dev --with-types --defs-only src/main.mligo':
--------------------------------------------------------------------------------------
[ 10.44G cycles in 1 calls ] - 71.12% : Scopes.run
[ 8.36G cycles in 1 calls ] | - 80.10% : Types_pass.Typing_env.type_program_with_refs
Note: Nodes accounting for less than 1.00% of their parent have been ignored.
Aggregated table:
----------------
Name; Filename; Calls; Time
ROOT; src/landmark.ml; 0; 14.67G
Scopes.run; src/main/scopes/scopes.ml:70; 1; 10.44G
Types_pass.Typing_env.type_program_with_refs; src/main/scopes/types_pass.ml:781; 1; 8.36G
Types_pass.patch; src/main/scopes/types_pass.ml:910; 2; 79.34M
Related issues
Resolves a part of #2143 .
✅ Checklist for the LIGO Language Server
- I checked whether I need to update the
README.mdfile for the plugin and did so if necessary:-
If I implemented a new LSP request, I added it to the list of supported features that may be disabled -
If I implemented a new LSP method, I added it to the list of supported functionality
-
-
I checked that my changes work in Emacs, Vim, and Visual Studio Code -
(Before merging) The commit history is squashed and prettified, and follows the Serokell commit policy, or the MR is set to squash the commits
Description
Component
-
compiler -
website -
webide -
vscode-plugin -
debugger
Types of changes
-
Bug fix (non-breaking change which fixes an issue) -
New feature (non-breaking change which adds functionality) -
Breaking change (fix or feature that would cause existing functionality to not work as expected) -
Performance improvement (non-breaking change that improves performance) -
None (change with no changelog)
Changelog
Improved performance for LSP.
The LSP should now take less time between keystrokes.
This is done by stripping the references pass and moving their collection to the type checker.
Checklist:
-
Changes follow the existing coding style (use dune @fmtto check). -
Tests for the changes have been added (for bug fixes / feature). -
Documentation has been updated. -
Changelog description has been added (if appropriate). -
Start titles under ## Changelogsection with #### (if appropriate). -
There is no image or uploaded file in changelog -
Examples in changed behaviour have been added to the changelog (for breaking change / feature).