1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
|
(**************************************************************************)
(* *)
(* OCaml *)
(* *)
(* Pierre Chambart, OCamlPro *)
(* Mark Shinwell and Leo White, Jane Street Europe *)
(* *)
(* Copyright 2013--2016 OCamlPro SAS *)
(* Copyright 2014--2016 Jane Street Group LLC *)
(* *)
(* All rights reserved. This file is distributed under the terms of *)
(* the GNU Lesser General Public License version 2.1, with the *)
(* special exception on linking described in the file LICENSE. *)
(* *)
(**************************************************************************)
[@@@ocaml.warning "+a-4-30-40-41-42"]
(* CR-someday vlaviron for mshinwell: I believe that the phantom lets introduced
in un_anf (when the new debug_full flag is enabled) bind mostly variables
that were created in the middle-end. Is it relevant to generate debugging
information for such variables ? I expect later pull requests to refine the
generation of these phantom constructions anyway, but maybe it would already
make sense to restrict the phantom let generation to variables with an actual
provenance.
*)
module V = Backend_var
module VP = Backend_var.With_provenance
(* We say that an [V.t] is "linear" iff:
(a) it is used exactly once;
(b) it is never assigned to (using [Uassign]).
*)
type var_info =
{ used_let_bound_vars : V.Set.t;
linear_let_bound_vars : V.Set.t;
assigned : V.Set.t;
closure_environment : V.Set.t;
}
let ignore_uconstant (_ : Clambda.uconstant) = ()
let ignore_ulambda (_ : Clambda.ulambda) = ()
let ignore_ulambda_list (_ : Clambda.ulambda list) = ()
let ignore_uphantom_defining_expr_option
(_ : Clambda.uphantom_defining_expr option) = ()
let ignore_function_label (_ : Clambda.function_label) = ()
let ignore_debuginfo (_ : Debuginfo.t) = ()
let ignore_int (_ : int) = ()
let ignore_var (_ : V.t) = ()
let ignore_var_option (_ : V.t option) = ()
let ignore_primitive (_ : Clambda_primitives.primitive) = ()
let ignore_string (_ : string) = ()
let ignore_int_array (_ : int array) = ()
let ignore_var_with_provenance (_ : VP.t) = ()
let ignore_params_with_value_kind (_ : (VP.t * Lambda.value_kind) list) = ()
let ignore_direction_flag (_ : Asttypes.direction_flag) = ()
let ignore_meth_kind (_ : Lambda.meth_kind) = ()
let ignore_value_kind (_ : Lambda.value_kind) = ()
(* CR-soon mshinwell: check we aren't traversing function bodies more than
once (need to analyse exactly what the calls are from Cmmgen into this
module). *)
let closure_environment_var (ufunction:Clambda.ufunction) =
(* The argument after the arity is the environment *)
if List.length ufunction.params = ufunction.arity + 1 then
let (env_var, _) = List.nth ufunction.params ufunction.arity in
assert (VP.name env_var = "env");
Some env_var
else
(* closed function, no environment *)
None
type var_uses =
| Zero
| One
| More_than_one
| Assigned
type var =
{ definition_depth : int;
uses : var_uses; }
let incr_uses { definition_depth; uses } depth =
assert (definition_depth <= depth);
let uses =
match uses with
| Zero ->
if definition_depth < depth then More_than_one
else One
| One -> More_than_one
| More_than_one -> More_than_one
| Assigned -> Assigned
in
{ definition_depth; uses }
let assign_uses r = { r with uses = Assigned }
let zero definition_depth = { definition_depth; uses = Zero }
let add_definition t var depth =
V.Tbl.add t var (zero depth)
let add_use t var depth =
match V.Tbl.find t var with
| info -> V.Tbl.replace t var (incr_uses info depth)
| exception Not_found -> () (* Variable is not let-bound *)
let add_assignment t var =
match V.Tbl.find t var with
| info -> V.Tbl.replace t var (assign_uses info)
| exception Not_found ->
Misc.fatal_errorf
"make_var_info: Assigned variable %a not let-bound"
V.print var
let make_var_info (clam : Clambda.ulambda) : var_info =
let t : var V.Tbl.t = V.Tbl.create 42 in
let environment_vars = ref V.Set.empty in
let rec loop ~depth : Clambda.ulambda -> unit = function
(* No underscores in the pattern match, to reduce the chance of failing
to traverse some subexpression. *)
| Uvar var -> add_use t var depth
| Uconst const ->
(* The only variables that might occur in [const] are those in constant
closures---and those are all bound by such closures. It follows that
[const] cannot contain any variables that are bound in the current
scope, so we do not need to count them here. (The function bodies
of the closures will be traversed when this function is called from
[Flambda_to_clambda.to_clambda_closed_set_of_closures].) *)
ignore_uconstant const
| Udirect_apply (label, args, dbg) ->
ignore_function_label label;
List.iter (loop ~depth) args;
ignore_debuginfo dbg
| Ugeneric_apply (func, args, dbg) ->
loop ~depth func;
List.iter (loop ~depth) args;
ignore_debuginfo dbg
| Uclosure (functions, captured_variables) ->
List.iter (loop ~depth) captured_variables;
List.iter (fun (
{ Clambda. label; arity; params; return; body; dbg; env; } as clos) ->
(match closure_environment_var clos with
| None -> ()
| Some env_var ->
environment_vars :=
V.Set.add (VP.var env_var) !environment_vars);
ignore_function_label label;
ignore_int arity;
ignore_params_with_value_kind params;
ignore_value_kind return;
loop ~depth:(depth + 1) body;
ignore_debuginfo dbg;
ignore_var_option env)
functions
| Uoffset (expr, offset) ->
loop ~depth expr;
ignore_int offset
| Ulet (_let_kind, _value_kind, var, def, body) ->
add_definition t (VP.var var) depth;
loop ~depth def;
loop ~depth body
| Uphantom_let (var, defining_expr_opt, body) ->
ignore_var_with_provenance var;
ignore_uphantom_defining_expr_option defining_expr_opt;
loop ~depth body
| Uletrec (defs, body) ->
List.iter (fun (var, def) ->
ignore_var_with_provenance var;
loop ~depth def)
defs;
loop ~depth body
| Uprim (prim, args, dbg) ->
ignore_primitive prim;
List.iter (loop ~depth) args;
ignore_debuginfo dbg
| Uswitch (cond, { us_index_consts; us_actions_consts;
us_index_blocks; us_actions_blocks }, dbg) ->
loop ~depth cond;
ignore_int_array us_index_consts;
Array.iter (loop ~depth) us_actions_consts;
ignore_int_array us_index_blocks;
Array.iter (loop ~depth) us_actions_blocks;
ignore_debuginfo dbg
| Ustringswitch (cond, branches, default) ->
loop ~depth cond;
List.iter (fun (str, branch) ->
ignore_string str;
loop ~depth branch)
branches;
Option.iter (loop ~depth) default
| Ustaticfail (static_exn, args) ->
ignore_int static_exn;
List.iter (loop ~depth) args
| Ucatch (static_exn, vars, body, handler) ->
ignore_int static_exn;
ignore_params_with_value_kind vars;
loop ~depth body;
loop ~depth handler
| Utrywith (body, var, handler) ->
loop ~depth body;
ignore_var_with_provenance var;
loop ~depth handler
| Uifthenelse (cond, ifso, ifnot) ->
loop ~depth cond;
loop ~depth ifso;
loop ~depth ifnot
| Usequence (e1, e2) ->
loop ~depth e1;
loop ~depth e2
| Uwhile (cond, body) ->
loop ~depth:(depth + 1) cond;
loop ~depth:(depth + 1) body
| Ufor (var, low, high, direction_flag, body) ->
ignore_var_with_provenance var;
loop ~depth low;
loop ~depth high;
ignore_direction_flag direction_flag;
loop ~depth:(depth + 1) body
| Uassign (var, expr) ->
add_assignment t var;
loop ~depth expr
| Usend (meth_kind, e1, e2, args, dbg) ->
ignore_meth_kind meth_kind;
loop ~depth e1;
loop ~depth e2;
List.iter (loop ~depth) args;
ignore_debuginfo dbg
| Uunreachable ->
()
in
loop ~depth:0 clam;
let linear_let_bound_vars, used_let_bound_vars, assigned =
V.Tbl.fold (fun var desc ((linear, used, assigned) as acc) ->
match desc.uses with
| Zero -> acc
| One -> (V.Set.add var linear, V.Set.add var used, assigned)
| More_than_one -> (linear, V.Set.add var used, assigned)
| Assigned -> (linear, V.Set.add var used, V.Set.add var assigned))
t (V.Set.empty, V.Set.empty, V.Set.empty)
in
{ used_let_bound_vars; linear_let_bound_vars; assigned;
closure_environment = !environment_vars;
}
(* When sequences of [let]-bindings match the evaluation order in a subsequent
primitive or function application whose arguments are linearly-used
non-assigned variables bound by such lets (possibly interspersed with other
variables that are known to be constant), and it is known that there were no
intervening side-effects during the evaluation of the [let]-bindings,
permit substitution of the variables for their defining expressions. *)
let let_bound_vars_that_can_be_moved var_info (clam : Clambda.ulambda) =
let obviously_constant = ref V.Set.empty in
let can_move = ref V.Set.empty in
let let_stack = ref [] in
let examine_argument_list args =
let rec loop let_bound_vars (args : Clambda.ulambda list) =
match let_bound_vars, args with
| _, [] ->
(* We've matched all arguments and will not substitute (in the
current application being considered) any of the remaining
[let_bound_vars]. As such they may stay on the stack. *)
let_bound_vars
| [], _ ->
(* There are no more [let]-bindings to consider, so the stack
is left empty. *)
[]
| let_bound_vars, (Uvar arg)::args
when V.Set.mem arg !obviously_constant ->
loop let_bound_vars args
| let_bound_var::let_bound_vars, (Uvar arg)::args
when V.same let_bound_var arg
&& not (V.Set.mem arg var_info.assigned) ->
assert (V.Set.mem arg var_info.used_let_bound_vars);
assert (V.Set.mem arg var_info.linear_let_bound_vars);
can_move := V.Set.add arg !can_move;
loop let_bound_vars args
| _::_, _::_ ->
(* The [let] sequence has ceased to match the evaluation order
or we have encountered some complicated argument. In this case
we empty the stack to ensure that we do not end up moving an
outer [let] across a side effect. *)
[]
in
(* Start at the most recent let binding and the leftmost argument
(the last argument to be evaluated). *)
let_stack := loop !let_stack args
in
let rec loop : Clambda.ulambda -> unit = function
| Uvar var ->
if V.Set.mem var var_info.assigned then begin
let_stack := []
end
| Uconst const ->
ignore_uconstant const
| Udirect_apply (label, args, dbg) ->
ignore_function_label label;
examine_argument_list args;
(* We don't currently traverse [args]; they should all be variables
anyway. If this is added in the future, take care to traverse [args]
following the evaluation order. *)
ignore_debuginfo dbg
| Ugeneric_apply (func, args, dbg) ->
examine_argument_list (args @ [func]);
ignore_debuginfo dbg
| Uclosure (functions, captured_variables) ->
ignore_ulambda_list captured_variables;
(* Start a new let stack for speed. *)
List.iter (fun {Clambda. label; arity; params; return; body; dbg; env} ->
ignore_function_label label;
ignore_int arity;
ignore_params_with_value_kind params;
ignore_value_kind return;
let_stack := [];
loop body;
let_stack := [];
ignore_debuginfo dbg;
ignore_var_option env)
functions
| Uoffset (expr, offset) ->
(* [expr] should usually be a variable. *)
examine_argument_list [expr];
ignore_int offset
| Ulet (_let_kind, _value_kind, var, def, body) ->
let var = VP.var var in
begin match def with
| Uconst _ ->
(* The defining expression is obviously constant, so we don't
have to put this [let] on the stack, and we don't have to
traverse the defining expression either. *)
obviously_constant := V.Set.add var !obviously_constant;
loop body
| _ ->
loop def;
if V.Set.mem var var_info.linear_let_bound_vars then begin
let_stack := var::!let_stack
end else begin
(* If we encounter a non-linear [let]-binding then we must clear
the let stack, since we cannot now move any previous binding
across the non-linear one. *)
let_stack := []
end;
loop body
end
| Uphantom_let (var, _defining_expr, body) ->
ignore_var_with_provenance var;
loop body
| Uletrec (defs, body) ->
(* Evaluation order for [defs] is not defined, and this case
probably isn't important for [Cmmgen] anyway. *)
let_stack := [];
List.iter (fun (var, def) ->
ignore_var_with_provenance var;
loop def;
let_stack := [])
defs;
loop body
| Uprim (prim, args, dbg) ->
ignore_primitive prim;
examine_argument_list args;
ignore_debuginfo dbg
| Uswitch (cond, { us_index_consts; us_actions_consts;
us_index_blocks; us_actions_blocks }, dbg) ->
examine_argument_list [cond];
ignore_int_array us_index_consts;
Array.iter (fun action ->
let_stack := [];
loop action)
us_actions_consts;
ignore_int_array us_index_blocks;
Array.iter (fun action ->
let_stack := [];
loop action)
us_actions_blocks;
ignore_debuginfo dbg;
let_stack := []
| Ustringswitch (cond, branches, default) ->
examine_argument_list [cond];
List.iter (fun (str, branch) ->
ignore_string str;
let_stack := [];
loop branch)
branches;
let_stack := [];
Option.iter loop default;
let_stack := []
| Ustaticfail (static_exn, args) ->
ignore_int static_exn;
examine_argument_list args
| Ucatch (static_exn, vars, body, handler) ->
ignore_int static_exn;
ignore_params_with_value_kind vars;
let_stack := [];
loop body;
let_stack := [];
loop handler;
let_stack := []
| Utrywith (body, var, handler) ->
let_stack := [];
loop body;
let_stack := [];
ignore_var_with_provenance var;
loop handler;
let_stack := []
| Uifthenelse (cond, ifso, ifnot) ->
examine_argument_list [cond];
let_stack := [];
loop ifso;
let_stack := [];
loop ifnot;
let_stack := []
| Usequence (e1, e2) ->
loop e1;
let_stack := [];
loop e2;
let_stack := []
| Uwhile (cond, body) ->
let_stack := [];
loop cond;
let_stack := [];
loop body;
let_stack := []
| Ufor (var, low, high, direction_flag, body) ->
ignore_var_with_provenance var;
(* Cmmgen generates code that evaluates low before high,
but we don't do anything here at the moment anyway. *)
ignore_ulambda low;
ignore_ulambda high;
ignore_direction_flag direction_flag;
let_stack := [];
loop body;
let_stack := []
| Uassign (var, expr) ->
ignore_var var;
ignore_ulambda expr;
let_stack := []
| Usend (meth_kind, e1, e2, args, dbg) ->
ignore_meth_kind meth_kind;
ignore_ulambda e1;
ignore_ulambda e2;
ignore_ulambda_list args;
let_stack := [];
ignore_debuginfo dbg
| Uunreachable ->
let_stack := []
in
loop clam;
!can_move
(* Substitution of an expression for a let-moveable variable can cause the
surrounding expression to become fixed. To avoid confusion, do the
let-moveable substitutions first. *)
let rec substitute_let_moveable is_let_moveable env (clam : Clambda.ulambda)
: Clambda.ulambda =
match clam with
| Uvar var ->
if not (V.Set.mem var is_let_moveable) then
clam
else
begin match V.Map.find var env with
| clam -> clam
| exception Not_found ->
Misc.fatal_errorf "substitute_let_moveable: Unbound variable %a"
V.print var
end
| Uconst _ -> clam
| Udirect_apply (label, args, dbg) ->
let args = substitute_let_moveable_list is_let_moveable env args in
Udirect_apply (label, args, dbg)
| Ugeneric_apply (func, args, dbg) ->
let func = substitute_let_moveable is_let_moveable env func in
let args = substitute_let_moveable_list is_let_moveable env args in
Ugeneric_apply (func, args, dbg)
| Uclosure (functions, variables_bound_by_the_closure) ->
let functions =
List.map (fun (ufunction : Clambda.ufunction) ->
{ ufunction with
body = substitute_let_moveable is_let_moveable env ufunction.body;
})
functions
in
let variables_bound_by_the_closure =
substitute_let_moveable_list is_let_moveable env
variables_bound_by_the_closure
in
Uclosure (functions, variables_bound_by_the_closure)
| Uoffset (clam, n) ->
let clam = substitute_let_moveable is_let_moveable env clam in
Uoffset (clam, n)
| Ulet (let_kind, value_kind, var, def, body) ->
let def = substitute_let_moveable is_let_moveable env def in
if V.Set.mem (VP.var var) is_let_moveable then
let env = V.Map.add (VP.var var) def env in
let body = substitute_let_moveable is_let_moveable env body in
(* If we are about to delete a [let] in debug mode, keep it for the
debugger. *)
(* CR-someday mshinwell: find out why some closure constructions were
not leaving phantom lets behind after substitution. *)
if not !Clflags.debug_full then
body
else
match def with
| Uconst const ->
Uphantom_let (var, Some (Clambda.Uphantom_const const), body)
| Uvar alias_of ->
Uphantom_let (var, Some (Clambda.Uphantom_var alias_of), body)
| _ ->
Uphantom_let (var, None, body)
else
Ulet (let_kind, value_kind,
var, def, substitute_let_moveable is_let_moveable env body)
| Uphantom_let (var, defining_expr, body) ->
let body = substitute_let_moveable is_let_moveable env body in
Uphantom_let (var, defining_expr, body)
| Uletrec (defs, body) ->
let defs =
List.map (fun (var, def) ->
var, substitute_let_moveable is_let_moveable env def)
defs
in
let body = substitute_let_moveable is_let_moveable env body in
Uletrec (defs, body)
| Uprim (prim, args, dbg) ->
let args = substitute_let_moveable_list is_let_moveable env args in
Uprim (prim, args, dbg)
| Uswitch (cond, sw, dbg) ->
let cond = substitute_let_moveable is_let_moveable env cond in
let sw =
{ sw with
us_actions_consts =
substitute_let_moveable_array is_let_moveable env
sw.us_actions_consts;
us_actions_blocks =
substitute_let_moveable_array is_let_moveable env
sw.us_actions_blocks;
}
in
Uswitch (cond, sw, dbg)
| Ustringswitch (cond, branches, default) ->
let cond = substitute_let_moveable is_let_moveable env cond in
let branches =
List.map (fun (s, branch) ->
s, substitute_let_moveable is_let_moveable env branch)
branches
in
let default =
Option.map (substitute_let_moveable is_let_moveable env) default
in
Ustringswitch (cond, branches, default)
| Ustaticfail (n, args) ->
let args = substitute_let_moveable_list is_let_moveable env args in
Ustaticfail (n, args)
| Ucatch (n, vars, body, handler) ->
let body = substitute_let_moveable is_let_moveable env body in
let handler = substitute_let_moveable is_let_moveable env handler in
Ucatch (n, vars, body, handler)
| Utrywith (body, var, handler) ->
let body = substitute_let_moveable is_let_moveable env body in
let handler = substitute_let_moveable is_let_moveable env handler in
Utrywith (body, var, handler)
| Uifthenelse (cond, ifso, ifnot) ->
let cond = substitute_let_moveable is_let_moveable env cond in
let ifso = substitute_let_moveable is_let_moveable env ifso in
let ifnot = substitute_let_moveable is_let_moveable env ifnot in
Uifthenelse (cond, ifso, ifnot)
| Usequence (e1, e2) ->
let e1 = substitute_let_moveable is_let_moveable env e1 in
let e2 = substitute_let_moveable is_let_moveable env e2 in
Usequence (e1, e2)
| Uwhile (cond, body) ->
let cond = substitute_let_moveable is_let_moveable env cond in
let body = substitute_let_moveable is_let_moveable env body in
Uwhile (cond, body)
| Ufor (var, low, high, direction, body) ->
let low = substitute_let_moveable is_let_moveable env low in
let high = substitute_let_moveable is_let_moveable env high in
let body = substitute_let_moveable is_let_moveable env body in
Ufor (var, low, high, direction, body)
| Uassign (var, expr) ->
let expr = substitute_let_moveable is_let_moveable env expr in
Uassign (var, expr)
| Usend (kind, e1, e2, args, dbg) ->
let e1 = substitute_let_moveable is_let_moveable env e1 in
let e2 = substitute_let_moveable is_let_moveable env e2 in
let args = substitute_let_moveable_list is_let_moveable env args in
Usend (kind, e1, e2, args, dbg)
| Uunreachable ->
Uunreachable
and substitute_let_moveable_list is_let_moveable env clams =
List.map (substitute_let_moveable is_let_moveable env) clams
and substitute_let_moveable_array is_let_moveable env clams =
Array.map (substitute_let_moveable is_let_moveable env) clams
(* We say that an expression is "moveable" iff it has neither effects nor
coeffects. (See semantics_of_primitives.mli.)
*)
type moveable = Fixed | Constant | Moveable
let both_moveable a b =
match a, b with
| Constant, Constant -> Constant
| Constant, Moveable
| Moveable, Constant
| Moveable, Moveable -> Moveable
| Constant, Fixed
| Moveable, Fixed
| Fixed, Constant
| Fixed, Moveable
| Fixed, Fixed -> Fixed
let primitive_moveable (prim : Clambda_primitives.primitive)
(args : Clambda.ulambda list)
(var_info : var_info) =
match prim, args with
| Pfield _, [Uconst (Uconst_ref (_, _))] ->
(* CR-someday mshinwell: Actually, maybe this shouldn't be needed; these
should have been simplified to [Read_symbol_field], which doesn't yield
a Clambda let. This might be fixed when Inline_and_simplify can
turn Pfield into Read_symbol_field. *)
(* Allow field access of symbols to be moveable. (The comment in
flambda.mli on [Read_symbol_field] may be helpful to the reader.) *)
Moveable
| Pfield _, [Uvar var] when V.Set.mem var var_info.closure_environment ->
(* accesses to the function environment is coeffect free: this block
is never mutated *)
Moveable
| _ ->
match Semantics_of_primitives.for_primitive prim with
| No_effects, No_coeffects -> Moveable
| No_effects, Has_coeffects
| Only_generative_effects, No_coeffects
| Only_generative_effects, Has_coeffects
| Arbitrary_effects, No_coeffects
| Arbitrary_effects, Has_coeffects -> Fixed
type moveable_for_env = Constant | Moveable
(** Eliminate, through substitution, [let]-bindings of linear variables with
moveable defining expressions. *)
let rec un_anf_and_moveable var_info env (clam : Clambda.ulambda)
: Clambda.ulambda * moveable =
match clam with
| Uvar var ->
begin match V.Map.find var env with
| Constant, def -> def, Constant
| Moveable, def -> def, Moveable
| exception Not_found ->
let moveable : moveable =
if V.Set.mem var var_info.assigned then
Fixed
else
Moveable
in
clam, moveable
end
| Uconst _ ->
(* Constant closures are rewritten separately. *)
clam, Constant
| Udirect_apply (label, args, dbg) ->
let args = un_anf_list var_info env args in
Udirect_apply (label, args, dbg), Fixed
| Ugeneric_apply (func, args, dbg) ->
let func = un_anf var_info env func in
let args = un_anf_list var_info env args in
Ugeneric_apply (func, args, dbg), Fixed
| Uclosure (functions, variables_bound_by_the_closure) ->
let functions =
List.map (fun (ufunction : Clambda.ufunction) ->
{ ufunction with
body = un_anf var_info env ufunction.body;
})
functions
in
let variables_bound_by_the_closure =
un_anf_list var_info env variables_bound_by_the_closure
in
Uclosure (functions, variables_bound_by_the_closure), Fixed
| Uoffset (clam, n) ->
let clam, moveable = un_anf_and_moveable var_info env clam in
Uoffset (clam, n), both_moveable Moveable moveable
| Ulet (_let_kind, _value_kind, var, def, Uvar var')
when V.same (VP.var var) var' ->
un_anf_and_moveable var_info env def
| Ulet (let_kind, value_kind, var, def, body) ->
let def, def_moveable = un_anf_and_moveable var_info env def in
let is_linear = V.Set.mem (VP.var var) var_info.linear_let_bound_vars in
let is_used = V.Set.mem (VP.var var) var_info.used_let_bound_vars in
let is_assigned =
V.Set.mem (VP.var var) var_info.assigned
in
let maybe_for_debugger (body, moveable) : Clambda.ulambda * moveable =
if not !Clflags.debug_full then
body, moveable
else
match def with
| Uconst const ->
Uphantom_let (var, Some (Clambda.Uphantom_const const),
body), moveable
| Uvar alias_of ->
Uphantom_let (var, Some (Clambda.Uphantom_var alias_of), body),
moveable
| _ ->
Uphantom_let (var, None, body), moveable
in
begin match def_moveable, is_linear, is_used, is_assigned with
| (Constant | Moveable), _, false, _ ->
(* A moveable expression that is never used may be eliminated.
However, if in debug mode and the defining expression is
appropriate, keep the let (as a phantom let) for the debugger. *)
maybe_for_debugger (un_anf_and_moveable var_info env body)
| Constant, _, true, false
(* A constant expression bound to an unassigned variable can replace any
occurrences of the variable. The same comment as above concerning
phantom lets applies. *)
| Moveable, true, true, false ->
(* A moveable expression bound to a linear unassigned [V.t]
may replace the single occurrence of the variable. The same comment
as above concerning phantom lets applies. *)
let def_moveable =
match def_moveable with
| Moveable -> Moveable
| Constant -> Constant
| Fixed -> assert false
in
let env = V.Map.add (VP.var var) (def_moveable, def) env in
maybe_for_debugger (un_anf_and_moveable var_info env body)
| (Constant | Moveable), _, _, true
(* Constant or Moveable but assigned. *)
| Moveable, false, _, _
(* Moveable but not used linearly. *)
| Fixed, _, _, _ ->
let body, body_moveable = un_anf_and_moveable var_info env body in
Ulet (let_kind, value_kind, var, def, body),
both_moveable def_moveable body_moveable
end
| Uphantom_let (var, defining_expr, body) ->
let body, body_moveable = un_anf_and_moveable var_info env body in
Uphantom_let (var, defining_expr, body), body_moveable
| Uletrec (defs, body) ->
let defs =
List.map (fun (var, def) -> var, un_anf var_info env def) defs
in
let body = un_anf var_info env body in
Uletrec (defs, body), Fixed
| Uprim (prim, args, dbg) ->
let args, args_moveable = un_anf_list_and_moveable var_info env args in
let moveable =
both_moveable args_moveable (primitive_moveable prim args var_info)
in
Uprim (prim, args, dbg), moveable
| Uswitch (cond, sw, dbg) ->
let cond = un_anf var_info env cond in
let sw =
{ sw with
us_actions_consts = un_anf_array var_info env sw.us_actions_consts;
us_actions_blocks = un_anf_array var_info env sw.us_actions_blocks;
}
in
Uswitch (cond, sw, dbg), Fixed
| Ustringswitch (cond, branches, default) ->
let cond = un_anf var_info env cond in
let branches =
List.map (fun (s, branch) -> s, un_anf var_info env branch)
branches
in
let default = Option.map (un_anf var_info env) default in
Ustringswitch (cond, branches, default), Fixed
| Ustaticfail (n, args) ->
let args = un_anf_list var_info env args in
Ustaticfail (n, args), Fixed
| Ucatch (n, vars, body, handler) ->
let body = un_anf var_info env body in
let handler = un_anf var_info env handler in
Ucatch (n, vars, body, handler), Fixed
| Utrywith (body, var, handler) ->
let body = un_anf var_info env body in
let handler = un_anf var_info env handler in
Utrywith (body, var, handler), Fixed
| Uifthenelse (cond, ifso, ifnot) ->
let cond, cond_moveable = un_anf_and_moveable var_info env cond in
let ifso, ifso_moveable = un_anf_and_moveable var_info env ifso in
let ifnot, ifnot_moveable = un_anf_and_moveable var_info env ifnot in
let moveable =
both_moveable cond_moveable
(both_moveable ifso_moveable ifnot_moveable)
in
Uifthenelse (cond, ifso, ifnot), moveable
| Usequence (e1, e2) ->
let e1 = un_anf var_info env e1 in
let e2 = un_anf var_info env e2 in
Usequence (e1, e2), Fixed
| Uwhile (cond, body) ->
let cond = un_anf var_info env cond in
let body = un_anf var_info env body in
Uwhile (cond, body), Fixed
| Ufor (var, low, high, direction, body) ->
let low = un_anf var_info env low in
let high = un_anf var_info env high in
let body = un_anf var_info env body in
Ufor (var, low, high, direction, body), Fixed
| Uassign (var, expr) ->
let expr = un_anf var_info env expr in
Uassign (var, expr), Fixed
| Usend (kind, e1, e2, args, dbg) ->
let e1 = un_anf var_info env e1 in
let e2 = un_anf var_info env e2 in
let args = un_anf_list var_info env args in
Usend (kind, e1, e2, args, dbg), Fixed
| Uunreachable ->
Uunreachable, Fixed
and un_anf var_info env clam : Clambda.ulambda =
let clam, _moveable = un_anf_and_moveable var_info env clam in
clam
and un_anf_list_and_moveable var_info env clams
: Clambda.ulambda list * moveable =
List.fold_right (fun clam (l, acc_moveable) ->
let clam, moveable = un_anf_and_moveable var_info env clam in
clam :: l, both_moveable moveable acc_moveable)
clams ([], (Moveable : moveable))
and un_anf_list var_info env clams : Clambda.ulambda list =
let clams, _moveable = un_anf_list_and_moveable var_info env clams in
clams
and un_anf_array var_info env clams : Clambda.ulambda array =
Array.map (un_anf var_info env) clams
let apply ~what ~ppf_dump clam =
let var_info = make_var_info clam in
let let_bound_vars_that_can_be_moved =
let_bound_vars_that_can_be_moved var_info clam
in
let clam =
substitute_let_moveable let_bound_vars_that_can_be_moved
V.Map.empty clam
in
let var_info = make_var_info clam in
let clam = un_anf var_info V.Map.empty clam in
if !Clflags.dump_clambda then begin
Format.fprintf ppf_dump
"@.un-anf (%a):@ %a@."
Symbol.print what
Printclambda.clambda clam
end;
clam
|