Perf: Implement a new algorithm for pattern matching compilation to reduce code size

Motivation and Context

Closes #1924 (closed)

This MR implements the algorithm from the paper "Compiling Pattern Matching to Good Decision Trees" for pattern matching compiler.

This algorithm performs better than the previous one in the cases when there are nested pattens in a match expression coupled with wildcards in between.

In some cases we can see more than 80% reduction in code size (compared to the old algorthim).

This algorithm simpler to implement and this also removes the pattern simplification pass (pattern_simpl.ml) which was needed by the old algorithm for compressing the matches. The new algorithm generates smaller automaton/match so there is not need for simplification/compression.

Description

examples	0.67.1 (bytes)	new algo (bytes)	diff (%)
edge_case_T.mligo	3920	468	-88.06
bug_report.mligo	2801	468	-83.29
permit-cameligo	4967	4955	-0.24
dao-cameligo	6481	6479	-0.03
permit-jsligo	5010	5010	0
randomness-cameligo	12542	12542	0
randomness-jsligo	23695	23695	0
fa2 (single-asset)	1550	1550	0
fa2 (multi-asset)	2054	2054	0
fa2 (nft)	2447	2447	0
dao-jsligo	6323	6323	0
predictive-market-jsligo	7769	7769	0
predictive-market-cameligo	7804	7804	0
advisor-jsligo	308	308	0
advisor-cameligo	308	308	0
multisig-jsligo	1302	1302	0
multisig-cameligo	1274	1274	0
shifumi-jsligo	9090	9090	0
shifumi-cameligo	5353	5353	0
NFT-factory-jsligo	3491	3491	0
NFT-factory-cameligo	3497	3497	0
checker-ligo	18467	18467	0
tzsafe	6854	6854	0
batcher	23135	23149	+0.06

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

We implement a new algorithm for the pattern-matching compiler which reduces the size of generated code in some cases.

In some cases we observed upto 80% reduction in generated code.

Example

type t = A | B

type p = (t * t * t * t)

let main (p : p) (_ : int) : operation list * int = 
  [], (match p with
    A,A,A,A -> 1
  | B,B,B,B -> 1
  | _,A,A,A -> 2
  | _,B,B,B -> 2
  | _,_,A,A -> 3
  | _,_,B,B -> 3
  | _,_,_,A -> 4
  | _,_,_,B -> 4)

Before

$ ligo.67 info measure-contract x.mligo 
3920 bytes

After

$ ligo info measure-contract x.mligo 
468 bytes

Checklist:

• Changes follow the existing coding style (use dune @fmt to 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 ## Changelog section 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).

src/passes/13.1-expansion/decision_tree.ml

@@ -16,8 +16,10 @@ let label_to_var (Label.Label name) = Value_var.of_input_var ~loc:Location.gener
 
 module LabelSet = Set.Make (Label)
 module LabelMap = Label.Map
+module Usages = Set.Make (Value_var)
 
 type signature = LabelSet.t
+type usages = Usages.t
 
 (* NOTE: Maybe add type expression later if needed *)
 type simple_pattern =
@@ -390,34 +392,39 @@ let swap_column_in_matrix : int -> matrix -> matrix =
 
 
 let rec generate_match_record
-    : Value_var.t -> O.type_expression -> decision_tree -> decision_tree
+    :  Value_var.t -> O.type_expression -> bool -> usages -> decision_tree
+    -> bool * decision_tree
   =
- fun constructor_var t dt ->
+ fun constructor_var t used usages dt ->
   match C.get_t_record t with
   | Some row ->
     let fields = I.Row.to_alist row in
-    let case =
-      List.fold fields ~init:dt ~f:(fun dt (l, ty) ->
+    let used, case =
+      List.fold fields ~init:(used, dt) ~f:(fun (used, dt) (l, ty) ->
           match C.get_t_record ty with
           | Some _ ->
-            generate_match_record (join_vars [ constructor_var; var_of_label l ]) ty dt
-          | None -> dt)
+            let v = join_vars [ constructor_var; var_of_label l ] in
+            let used', dt = generate_match_record v ty used usages dt in
+            used || used', dt
+          | None -> used, dt)
     in
-    let field_binders =
-      Record.of_list
-      @@ List.map fields ~f:(fun (field_label, t) ->
-             let var = join_vars [ constructor_var; var_of_label field_label ] in
-             let binder = Binder.make var t in
-             field_label, binder)
+    let used, field_binders =
+      List.fold_map fields ~init:used ~f:(fun used (field_label, t) ->
+          let var = join_vars [ constructor_var; var_of_label field_label ] in
+          let binder = Binder.make var t in
+          used || Usages.mem usages var, (field_label, binder))
     in
+    let field_binders = Record.of_list field_binders in
     (* TODO: check if the type expression is correct here *)
     let matchee = Binder.make constructor_var t in
-    SwitchRecord { matchee; field_binders; case; record_type = t }
-  | None -> dt
+    used, SwitchRecord { matchee; field_binders; case; record_type = t }
+  | None -> used, dt
 
 
-let rec compile : (Value_var.t * O.type_expression) list -> matrix -> decision_tree =
- fun occurances matrix ->
+let rec compile
+    : usages -> (Value_var.t * O.type_expression) list -> matrix -> decision_tree
+  =
+ fun usages occurances matrix ->
   (* Format.printf "++++++++++++++++++++++\n";
   List.iter occurances ~f:(fun (o, t) ->
       Format.printf "(%a, %a) " Label.pp o O.PP.type_expression t);
@@ -446,17 +453,23 @@ let rec compile : (Value_var.t * O.type_expression) list -> matrix -> decision_t
              ~init:[]
              ~f:(fun ~key:c ~data:(a, ty, parent_ty) l ->
                let t =
-                 compile (specialize_occurances c occurances ty) (specialize c a matrix)
+                 compile
+                   usages
+                   (specialize_occurances c occurances ty)
+                   (specialize c a matrix)
                in
                let constructor_var = join_vars [ o; var_of_label c ] in
-               let t = generate_match_record constructor_var ty t in
+               let used, rt = generate_match_record constructor_var ty false usages t in
+               let t = if used then rt else t in
                ({ constructor = c; binder = constructor_var; subtree = t }, parent_ty)
                :: l)
       in
       let default =
         List.map (LabelSet.to_list missing_constructors) ~f:(fun c ->
             let binder = join_vars [ o; var_of_label c ] in
-            let subtree = compile (default_occurances occurances) (default matrix) in
+            let subtree =
+              compile usages (default_occurances occurances) (default matrix)
+            in
             { constructor = c; binder; subtree })
       in
       let variant_type = List.hd_exn parent_tys in
@@ -486,7 +499,7 @@ let rec compile : (Value_var.t * O.type_expression) list -> matrix -> decision_t
           Format.printf "\n$$$$$$$$$$$$$$$$$\n"; *)
           raise e
       in
-      compile swapped_occurances swapped_matrix)
+      compile usages swapped_occurances swapped_matrix)
 
 
 let fail ~loc ty () =
@@ -568,38 +581,18 @@ let test
         "%a\n"
         (Simple_utils.PP_helpers.list_sep_d Sexp.pp_hum)
         (List.map sp ~f:sexp_of_simple_pattern)) *)
-  let matrix =
-    List.map cases ~f:(fun { pattern; body } ->
+  let usages, matrix =
+    List.fold_map cases ~init:Usages.empty ~f:(fun usages { pattern; body } ->
         let vars_projs = get_vars_and_projections matchee pattern in
-        let body =
+        let body, usages =
           List.fold
             vars_projs
-            ~init:body
-            ~f:(fun body { bound_var = to_subst; new_var } ->
-              (* Format.printf
-                "pattern = %a | to_subst = %a | new_var = %a | body = %a\n"
-                (I.Pattern.pp I.PP.type_expression)
-                pattern
-                Value_var.pp
-                to_subst
-                Value_var.pp
-                new_var
-                O.PP.expression
-                body; *)
-              Substitution.substitute_var_in_body ~to_subst ~new_var body)
+            ~init:(body, usages)
+            ~f:(fun (body, usages) { bound_var = to_subst; new_var } ->
+              ( Substitution.substitute_var_in_body ~to_subst ~new_var body
+              , Usages.add usages new_var ))
         in
-        (* Format.printf
-          "\n\
-           ******************\n\
-           old body = %a\n\
-           ******************\n\
-          \ new_body = %a\n\
-           ******************\n"
-          O.PP.expression
-          body
-          O.PP.expression
-          body'; *)
-        to_simple_pattern matchee_type pattern, body)
+        usages, (to_simple_pattern matchee_type pattern, body))
   in
   (* print_matrix matrix; *)
   let top_occurances =
@@ -609,8 +602,9 @@ let test
     "top_occurances = %a\n"
     (Simple_utils.PP_helpers.list_sep_d Label.pp)
     top_occurances; *)
-  let dt = compile top_occurances matrix in
-  let dt = generate_match_record matchee matchee_type dt in
+  let dt = compile usages top_occurances matrix in
+  let used, rdt = generate_match_record matchee matchee_type false usages dt in
+  let dt = if used then rdt else dt in
   let match_expr = to_match_expression ~fail ~body_type dt in
   (* Format.printf "\n@@@@@@@@@@@@\n%a\n@@@@@@@@@@@@\n" O.PP.expression match_expr; *)
   (* print_decision_tree dt; *)