| blob | 8eea02765769c55a87d56989aab0fc60638c452d |
1 {*
2 * Copyright (C) 2024, 2025 Mikulas Patocka
3 *
4 * This file is part of Ajla.
5 *
6 * Ajla is free software: you can redistribute it and/or modify it under the
7 * terms of the GNU General Public License as published by the Free Software
8 * Foundation, either version 3 of the License, or (at your option) any later
9 * version.
10 *
11 * Ajla is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
13 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along with
16 * Ajla. If not, see <https://www.gnu.org/licenses/>.
17 *}
19 private unit compiler.optimize.ssa;
21 uses compiler.optimize.defs;
23 fn process_pcode(pc : list(pcode_t), get_inline : fn(function, bool) : list(pcode_t), verify : bool) : list(pcode_t);
26 implementation
28 uses exception;
29 uses compiler.common.blob;
30 uses compiler.common.gvn;
31 uses compiler.common.evaluate;
32 uses compiler.optimize.utils;
33 uses compiler.optimize.inline;
34 uses compiler.optimize.verify;
36 fn mtos(x : var_set) : bytes
37 [
38 var str := "(";
39 while x <> 0 do [
40 var v : int := bsf x;
41 x btr= v;
42 if len(str) > 1 then
43 str += ",";
44 str += ntos(v);
45 ]
46 str += ")";
47 return str;
48 ]
50 fn insert_instr(ctx : context, ins : instruction, pos : int) : context
51 [
52 var id := len(ctx.instrs);
53 ctx.instrs +<= ins;
54 var block := ctx.blocks[ins.bb];
55 var new_list := block.instrs[.. pos] +< id + block.instrs[pos ..];
56 ctx.blocks[ins.bb].instrs := new_list;
57 return ctx;
58 ]
60 fn deactivate_arrow(ctx : context, bgi : int, pidx : int) : context
61 [
62 var p := ctx.blocks[bgi].post_list[pidx];
63 //eval debug("deleting arrow " + ntos(bgi) + "(" + ntos(pidx) + ") -> " + ntos(p));
64 if not ctx.blocks[bgi].active then
65 abort internal("deactivating an arrow from an invalid block");
66 if not ctx.blocks[p].active then
67 abort internal("deactivating an arrow to an invalid block");
68 again:
69 for j := 0 to len(ctx.blocks[p].pred_list) do [
70 if ctx.blocks[p].pred_list[j] = bgi and ctx.blocks[p].pred_position[j] = pidx then [
71 ctx.blocks[p].pred_list := ctx.blocks[p].pred_list[ .. j] + ctx.blocks[p].pred_list[j + 1 ..];
72 ctx.blocks[p].pred_position := ctx.blocks[p].pred_position[ .. j] + ctx.blocks[p].pred_position[j + 1 ..];
73 for lidx := 0 to len(ctx.blocks[p].instrs) do [
74 var ins := ctx.instrs[ctx.blocks[p].instrs[lidx]];
75 if ins.opcode <> P_Phi then
76 break;
77 ins.params := ins.params[.. j + 1] + ins.params[j + 2 ..];
78 ins.read_set := ins.read_set shr 1 btc 0;
79 ctx.instrs[ctx.blocks[p].instrs[lidx]] := ins;
80 ]
81 goto again;
82 ]
83 ]
84 ctx.blocks[bgi].post_list := ctx.blocks[bgi].post_list[ .. pidx] + ctx.blocks[bgi].post_list[pidx + 1 .. ];
85 for i := pidx to len(ctx.blocks[bgi].post_list) do [
86 var bgi_post := ctx.blocks[bgi].post_list[i];
87 var block_post := ctx.blocks[bgi_post];
88 for j := 0 to len(block_post.pred_list) do [
89 if block_post.pred_list[j] = bgi and block_post.pred_position[j] > pidx then [
90 ctx.blocks[bgi_post].pred_position[j] -= 1;
91 ]
92 ]
93 ]
94 return ctx;
95 ]
97 fn deactivate_node(ctx : context, bgi : int) : context
98 [
99 while len(ctx.blocks[bgi].pred_list) <> 0 do [
100 var pred_bgi := ctx.blocks[bgi].pred_list[0];
101 var pred_idx := ctx.blocks[bgi].pred_position[0];
102 ctx := deactivate_arrow(ctx, pred_bgi, pred_idx);
103 ]
104 while len(ctx.blocks[bgi].post_list) <> 0 do [
105 ctx := deactivate_arrow(ctx, bgi, 0);
106 ]
107 ctx.blocks[bgi] := basic_block.[
108 active : false,
109 instrs : empty(int),
110 pred_list : empty(int),
111 pred_position : empty(int),
112 post_list : empty(int),
113 dom : -1,
114 dominates : -1,
115 idom : -1,
116 is_idom_of : -1,
117 df : -1,
118 uninitialized : -1,
119 live_top : -1,
120 live_bottom : -1,
121 ];
122 return ctx;
123 ]
125 fn find_dominators_1(ctx : context) : context
126 [
127 again:
128 var did_something := false;
129 for bgi := 1 to len(ctx.blocks) do [
130 if not ctx.blocks[bgi].active then
131 continue;
132 var un_set : node_set := -1;
133 for p_idx := 0 to len(ctx.blocks[bgi].pred_list) do [
134 var pred := ctx.blocks[bgi].pred_list[p_idx];
135 un_set and= ctx.blocks[pred].dom;
136 ]
137 un_set bts= bgi;
138 if un_set <> ctx.blocks[bgi].dom then [
139 ctx.blocks[bgi].dom := un_set;
140 did_something := true;
141 ]
142 ]
143 {
144 var bgi := len(ctx.blocks);
145 while bgi > 1 do [
146 bgi -= 1;
147 if not ctx.blocks[bgi].active then
148 continue;
149 var un_set : node_set := -1;
150 for p_idx := 0 to len(ctx.blocks[bgi].pred_list) do [
151 var pred := ctx.blocks[bgi].pred_list[p_idx];
152 un_set and= ctx.blocks[pred].dom;
153 ]
154 un_set bts= bgi;
155 if un_set <> ctx.blocks[bgi].dom then [
156 ctx.blocks[bgi].dom := un_set;
157 did_something := true;
158 ]
159 ]
160 }
161 if did_something then
162 goto again;
163 return ctx;
164 ]
166 fn find_dominators_2(ctx : context) : context
167 [
168 for bgi := 0 to len(ctx.blocks) do [
169 if not ctx.blocks[bgi].active then
170 continue;
171 var dom_set := ctx.blocks[bgi].dom;
172 while dom_set <> 0 do [
173 var dom : int := bsr dom_set;
174 dom_set btr= dom;
175 ctx.blocks[dom].dominates bts= bgi;
176 ]
177 ctx.blocks[bgi].is_idom_of := 0;
178 ]
179 return ctx;
180 ]
182 fn find_dominators_3(ctx : context) : context
183 [
184 for bgi := 1 to len(ctx.blocks) do [
185 if not ctx.blocks[bgi].active then
186 continue;
187 ctx.blocks[bgi].idom := -1;
188 var dom_set := ctx.blocks[bgi].dom btc bgi;
189 while dom_set <> 0 do [
190 var dom : int := bsr dom_set;
191 dom_set btr= dom;
192 var dominates := ctx.blocks[dom].dominates btc dom;
193 if (dominates and ctx.blocks[bgi].dom btc bgi) = 0 then [
194 //eval debug("idom (" + ntos(bgi) + ") = " + ntos(dom));
195 if ctx.blocks[bgi].idom = -1 then
196 ctx.blocks[bgi].idom := dom;
197 else
198 abort internal("a block has multiple immediate dominators");
199 ]
200 ]
201 if ctx.blocks[bgi].idom = -1 then [
202 abort internal("a block doesn't have immediate dominator");
203 ]
204 ctx.blocks[ctx.blocks[bgi].idom].is_idom_of bts= bgi;
205 ]
206 return ctx;
207 ]
209 fn find_dominators(ctx : context) : context
210 [
211 var n_blocks := len(ctx.blocks);
212 ctx.blocks[0].dom := 0 bts 0;
213 ctx.blocks[0].dominates := 0;
214 for i := 1 to n_blocks do [
215 var zero : node_set := 0;
216 ctx.blocks[i].dom := (zero bts n_blocks) - 1;
217 ctx.blocks[i].dominates := 0;
218 ]
220 ctx := find_dominators_1(ctx);
221 ctx := find_dominators_2(ctx);
222 ctx := find_dominators_3(ctx);
224 {for bgi := 0 to n_blocks do [
225 eval debug("dom(" + ntos(bgi) + ") = " + ntos_base(ctx.blocks[bgi].dom, 2) + ", idom = " + ntos(ctx.blocks[bgi].idom));
226 ]}
228 return ctx;
229 ]
231 fn prune_unreachable(ctx : context) : context
232 [
233 var worklist : node_set := 0 bts 0;
234 var active : node_set := 0;
236 while worklist <> 0 do [
237 var w : int := bsr worklist;
238 worklist btr= w;
240 active bts= w;
242 for post_idx := 0 to len(ctx.blocks[w].post_list) do [
243 var p := ctx.blocks[w].post_list[post_idx];
244 if not active bt p then
245 worklist bts= p;
246 ]
247 ]
249 for bgi := 0 to len(ctx.blocks) do [
250 if not active bt bgi and ctx.blocks[bgi].active then [
251 //eval debug("deactivating node " + ntos(bgi));
252 ctx := deactivate_node(ctx, bgi);
253 ]
254 ]
256 return ctx;
257 ]
259 fn join_adjacent(ctx : context) : context
260 [
261 var n_blocks := len(ctx.blocks);
262 var did_something : bool;
264 again:
265 did_something := false;
266 for bgi := 0 to n_blocks do [
267 if not ctx.blocks[bgi].active then
268 continue;
269 {rpt:
270 var instrs := ctx.blocks[bgi].instrs;
271 if len_greater_than(instrs, 0) then [
272 var instr := ctx.instrs[instrs[0]];
273 if instr.opcode = P_Copy, instr.params[0] = instr.params[2] then [
274 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[1 .. ];
275 goto rpt;
276 ]
277 ]}
278 {if len(ctx.blocks[bgi].post_list) = 3 then [
279 var false_block := ctx.blocks[bgi].post_list[1];
280 if len(ctx.blocks[false_block].instrs) = 1 and ctx.instrs[ctx.blocks[false_block].instrs[0]].opcode = P_Label then [
281 if ctx.name = "fact" then eval debug("label node " + ntos(bgi) + " -> " + ntos(false_block));
282 ]
283 if len(ctx.blocks[false_block].instrs) = 0 and len(ctx.blocks[false_block].post_list) = 1 then [
284 var next_block := ctx.blocks[false_block].post_list[0];
285 if ctx.name = "fact" then eval debug("empty node " + ntos(bgi) + " -> " + ntos(false_block) + " -> " + ntos(next_block));
286 for pl := 0 to len(ctx.blocks[next_block].pred_list) do [
287 if ctx.blocks[next_block].pred_list[pl] = false_block then [
288 ctx.blocks[next_block].pred_list[pl] := bgi;
289 ctx.blocks[next_block].pred_position[pl] := 1;
290 ]
291 ]
292 ctx.blocks[bgi].post_list[1] := next_block;
293 ctx.blocks[false_block].pred_list := empty(int);
294 ctx.blocks[false_block].post_list := empty(int);
295 ctx := deactivate_node(ctx, false_block);
296 did_something := true;
297 continue;
298 ]
299 ]
300 }
301 if len(ctx.blocks[bgi].post_list) = 1 then [
302 var post := ctx.blocks[bgi].post_list[0];
303 if len(ctx.blocks[post].pred_list) = 1 then [
304 //eval debug("joining nodes " + ntos(bgi) + " -> " + ntos(post));
305 var lbl := -1;
306 var instrs1 := ctx.blocks[bgi].instrs;
307 var instrs2 := ctx.blocks[post].instrs;
308 for n := 0 to len(instrs2) do [
309 var in_idx := instrs2[n];
310 if ctx.instrs[in_idx].bb <> post then
311 abort internal("bb doesn't match: " + ntos(ctx.instrs[in_idx].bb) + " <> " + ntos(post) + " (opcode " + ntos(ctx.instrs[in_idx].opcode) + ")");
312 ctx.instrs[in_idx].bb := bgi;
313 ]
314 if len_greater_than(instrs1, 0) then [
315 var last1 := ctx.instrs[instrs1[len(instrs1) - 1]].opcode;
316 if last1 = P_Jmp or last1 = P_Jmp_False then [
317 instrs1 := instrs1[ .. len(instrs1) - 1];
318 ]
319 ]
320 if len_greater_than(instrs2, 0) then [
321 var first2 := ctx.instrs[instrs2[0]].opcode;
322 if first2 = P_Label then [
323 lbl := ctx.instrs[instrs2[0]].params[0];
324 instrs2 := instrs2[1 .. ];
325 ]
326 ]
327 ctx.blocks[bgi].instrs := instrs1 + instrs2;
328 ctx.blocks[bgi].post_list := ctx.blocks[post].post_list;
329 for pl := 0 to len(ctx.blocks[bgi].post_list) do [
330 var p := ctx.blocks[bgi].post_list[pl];
331 for q := 0 to len(ctx.blocks[p].pred_list) do
332 if ctx.blocks[p].pred_list[q] = post then
333 ctx.blocks[p].pred_list[q] := bgi;
334 ]
335 ctx.blocks[post].pred_list := empty(int);
336 ctx := deactivate_node(ctx, post);
337 if lbl >= 0 then [
338 if ctx.label_to_block[lbl] <> post then
339 abort internal("label doesn't match");
340 ctx.label_to_block[lbl] := -1;
341 ]
342 did_something := true;
343 ]
344 ]
345 ]
347 if did_something then
348 goto again;
350 return ctx;
351 ]
353 fn propagate_types(ctx : context) : context
354 [
355 var did_something : bool;
356 again:
357 did_something := false;
358 var n_blocks := len(ctx.blocks);
359 for bgi := 0 to n_blocks do [
360 if not ctx.blocks[bgi].active then
361 continue;
362 var n_instrs := len(ctx.blocks[bgi].instrs);
363 for ili := 0 to n_instrs do [
364 var ins := ctx.instrs[ ctx.blocks[bgi].instrs[ili] ];
365 if ins.opcode = P_Copy then [
366 var dest : int := ins.params[0];
367 var src : int := ins.params[2];
368 var dest_rt := ctx.variables[dest].runtime_type;
369 var src_rt := T_Type;
370 if src >= 0 then
371 src_rt := ctx.variables[src].runtime_type;
372 else if src = T_Type then
373 src_rt := T_TypeOfType;
374 if src_rt = dest_rt then
375 continue;
376 if src_rt = T_Undetermined then
377 ctx.variables[src].runtime_type := dest_rt;
378 else if dest_rt = T_Undetermined then
379 ctx.variables[dest].runtime_type := src_rt;
380 else [
381 if src_rt >= 0, dest_rt >= 0 then
382 continue;
383 abort internal("copying between variables '" + ctx.variables[src].name + "', '" + ctx.variables[dest].name + "' with types " + ntos(src_rt) + " and " + ntos(dest_rt));
384 ]
385 did_something := true;
386 ]
387 ]
388 ]
389 if did_something then
390 goto again;
391 return ctx;
392 ]
394 fn set_to_mask(ins : instruction, s : param_set) : var_set
395 [
396 var r : var_set := 0;
397 while s <> 0 do [
398 var q : int := bsr s;
399 s btr= q;
400 if ins.params[q] >= 0 then
401 r bts= ins.params[q];
402 ]
403 return r;
404 ]
406 fn test_uninitialized(ctx : context) : context
407 [
408 var n_blocks := len(ctx.blocks);
410 var zero : var_set := 0;
411 ctx.blocks[0].uninitialized := (zero bts len(ctx.variables)) - 1;
412 for bgi := 1 to n_blocks do [
413 if not ctx.blocks[bgi].active then
414 continue;
415 ctx.blocks[bgi].uninitialized := 0;
416 ]
418 var worklist : node_set := 0 bts 0;
420 while worklist <> 0 do [
421 var w : int := bsr worklist;
422 worklist btr= w;
424 var uninit := ctx.blocks[w].uninitialized;
426 for ili := 0 to len(ctx.blocks[w].instrs) do [
427 var ins := ctx.instrs[ ctx.blocks[w].instrs[ili] ];
428 //eval debug("opcode " + ntos(ins.opcode) + " rd " + ntos_base(ins.read_set, 2) + " wr " + ntos_base(ins.write_set, 2) + " fr " + ntos_base(ins.free_set, 2));
429 var read_mask := set_to_mask(ins, ins.read_set);
430 var write_mask := set_to_mask(ins, ins.write_set);
431 //var free_mask := set_to_mask(ins, ins.free_set);
432 var uninit_mask := read_mask and uninit;
433 if uninit_mask <> 0 then [
434 {
435 eval dump_basic_blocks(ctx, true);
436 eval debug("read mask: " + ntos_base(read_mask, 2));
437 eval debug("write mask: " + ntos_base(write_mask, 2));
438 //eval debug("free mask: " + ntos_base(free_mask, 2));
439 for j := 0 to len(ins.params) do
440 eval debug("param: " + ntos(ins.params[j]));
441 abort internal("uninitialized variable " + ntos_base(uninit_mask, 2) + " at bb " + ntos(w) + " in " + ntos(ili) + " opc " + ntos(ins.opcode));
442 }
443 var str := "Uninitialized variable in " + ctx.name;
444 var v : int := bsf uninit_mask;
445 if len(ctx.variables[v].name) > 0 then
446 str += ": " + ctx.variables[v].name;
447 ctx := exception_make_str(context, ec_async, error_compiler_error, 0, false, str);
448 return ctx;
449 ]
450 //uninit or= free_mask;
451 uninit and= not write_mask;
452 ]
454 for post := 0 to len(ctx.blocks[w].post_list) do [
455 var p := ctx.blocks[w].post_list[post];
456 if (uninit and not ctx.blocks[p].uninitialized) <> 0 then [
457 ctx.blocks[p].uninitialized or= uninit;
458 worklist bts= p;
459 ]
460 ]
461 ]
463 return ctx;
464 ]
466 fn get_pred_set(b : basic_block) : node_set
467 [
468 var pred_set : node_set := 0;
469 for j := 0 to len(b.pred_list) do
470 pred_set bts= b.pred_list[j];
471 return pred_set;
472 ]
474 fn find_dominance_frontiers(ctx : context) : context
475 [
476 var n_blocks := len(ctx.blocks);
478 for bgi := 0 to n_blocks do
479 ctx.blocks[bgi].df := 0;
481 for bgi := 0 to n_blocks do [
482 if not ctx.blocks[bgi].active then
483 continue;
484 var pred_set := get_pred_set(ctx.blocks[bgi]);
485 if popcnt pred_set >= 2 then [
486 while pred_set <> 0 do [
487 var runner : int := bsr pred_set;
488 pred_set btr= runner;
489 while runner <> ctx.blocks[bgi].idom do [
490 ctx.blocks[runner].df bts= bgi;
491 runner := ctx.blocks[runner].idom;
492 ]
493 ]
494 ]
495 ]
497 {for bgi := 0 to n_blocks do [
498 eval debug("df(" + ntos(bgi) + ") = " + ntos_base(ctx.blocks[bgi].df, 2));
499 ]}
501 return ctx;
502 ]
504 fn process_variables(ctx : context) : context
505 [
506 for vgi := 0 to len(ctx.variables) do [
507 ctx.variables[vgi].writing_instrs := 0;
508 ctx.variables[vgi].reaching_def := -1;
509 ]
510 for bgi := 0 to len(ctx.blocks) do [
511 if not ctx.blocks[bgi].active then
512 continue;
513 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
514 var igi := ctx.blocks[bgi].instrs[ili];
515 var ins := ctx.instrs[igi];
516 {
517 var rset := ins.read_set;
518 while rset <> 0 do [
519 var rd : int := bsr rset;
520 rset btr= rd;
521 var v := ins.params[rd];
522 if v >= 0 then [
523 //ctx.variables[v].reading_instrs bts= igi;
524 //ctx.variables[v].var_active := true;
525 ]
526 ]
527 }
528 var wset := ins.write_set;
529 while wset <> 0 do [
530 var wr : int := bsr wset;
531 wset btr= wr;
532 var v := ins.params[wr];
533 if v >= 0 then [
534 ctx.variables[v].writing_instrs bts= igi;
535 ]
536 ]
537 ]
538 ]
539 return ctx;
540 ]
542 fn is_noclone_variable(ctx : context, vgi : int) : bool
543 [
544 return popcnt(ctx.variables[vgi].writing_instrs) = 1;
545 ]
547 fn insert_phi(ctx : context, vgi : int, bgi : int) : context
548 [
549 var n : int := len(ctx.blocks[bgi].pred_list);
550 var instr := create_instr(P_Phi, fill(pcode_t, vgi, n + 1), bgi);
551 ctx := insert_instr(ctx, instr, 0);
552 return ctx;
553 ]
555 fn find_phi_blocks(ctx : context) : context
556 [
557 for vgi := 0 to len(ctx.variables) do [
558 if is_noclone_variable(ctx, vgi) then
559 continue;
561 var f : node_set := 0;
562 var w : node_set := 0;
564 var wset := ctx.variables[vgi].writing_instrs;
565 while wset <> 0 do [
566 var wr : int := bsr wset;
567 wset btr= wr;
568 if ctx.blocks[ ctx.instrs[wr].bb ].active then
569 w bts= ctx.instrs[wr].bb;
570 ]
571 var defs_v := w;
572 while w <> 0 do [
573 var x : int := bsr w;
574 w btr= x;
575 var dfw := ctx.blocks[x].df;
576 //eval debug("dfs( " + ntos(x) + ") = " + ntos_base(dfw, 2));
577 while dfw <> 0 do [
578 var y : int := bsr dfw;
579 dfw btr= y;
580 if not f bt y then [
581 if not ctx.blocks[y].uninitialized bt vgi then [
582 //eval debug("insert phi for " + ntos(vgi) + " at " + ntos(y));
583 ctx := insert_phi(ctx, vgi, y);
584 f bts= y;
585 if not defs_v bt y then
586 w bts= y;
587 ] else [
588 //eval debug("don't insert phi for " + ntos(vgi) + " at " + ntos(y));
589 ]
590 ]
591 ]
592 ]
593 ]
594 return ctx;
595 ]
598 fn clone_variable(ctx : context, vgi : int) : (variable, int)
599 [
600 var v1_idx := len(ctx.variables);
601 var v1 := new_variable;
603 v1.type_index := ctx.variables[vgi].type_index;
604 v1.runtime_type := ctx.variables[vgi].runtime_type;
605 v1.local_type := ctx.variables[vgi].local_type;
606 v1.color := ctx.variables[vgi].color;
607 v1.name := ctx.variables[vgi].name;
608 v1.is_option_type := ctx.variables[vgi].is_option_type;
610 return v1, v1_idx;
611 ]
613 fn update_reaching_def(ctx : context, vgi : int, bgi : int) : context
614 [
615 var r := ctx.variables[vgi].reaching_def;
616 //var s := r;
617 while r <> -1, not ctx.blocks[ctx.variables[r].defining_block].dominates bt bgi do [
618 //eval debug("go up " + ntos(r) + " -> " + ntos(ctx.variables[r].reaching_def) + " dblock " + ntos(ctx.variables[r].defining_block));
619 r := ctx.variables[r].reaching_def;
620 ]
621 ctx.variables[vgi].reaching_def := r;
622 //eval debug("update_reaching_def: bgi : " + ntos(bgi) + " vgi: " + ntos(vgi) + " : " + ntos(s) + " -> " + ntos(r));
623 return ctx;
624 ]
626 fn rename_variables_recursive(ctx : context, bgi : int) : context
627 [
628 //eval debug("walking block " + ntos(bgi) + " (" + ntos(len(ctx.blocks[bgi].instrs)) + ")");
630 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
631 var igi := ctx.blocks[bgi].instrs[ili];
632 var instr := ctx.instrs[igi];
633 if instr.opcode <> P_Phi then [
634 var read_set := instr.read_set;
635 while read_set <> 0 do [
636 var rd_idx : int := bsr read_set;
637 read_set btr= rd_idx;
638 var v := instr.params[rd_idx];
639 if v < 0 then
640 continue;
642 if is_noclone_variable(ctx, v) then
643 continue;
645 //eval debug("prev reaching def " + ntos(ctx.variables[v].reaching_def));
646 ctx := update_reaching_def(ctx, v, bgi);
647 if ctx.variables[v].reaching_def = -1 then
648 abort internal("bad reaching def, bgi " + ntos(bgi) + " instr " + ntos(ili) + " v " + ntos(v) + " opcode " + ntos(instr.opcode));
649 ctx.instrs[ ctx.blocks[bgi].instrs[ili] ].params[rd_idx] := ctx.variables[v].reaching_def;
650 //eval debug("processing renamed, bgi " + ntos(bgi) + " " + ntos(v) + " -> " + ntos(ctx.variables[v].reaching_def));
651 ]
652 ]
653 var write_set := instr.write_set;
654 while write_set <> 0 do [
655 var wr_idx : int := bsr write_set;
656 write_set btr= wr_idx;
657 var v := instr.params[wr_idx];
658 if v = -1 then
659 abort internal("negative v: " + ntos(v));
661 if is_noclone_variable(ctx, v) then [
662 ctx.variables[v].defining_block := bgi;
663 ctx.variables[v].defining_instr := igi;
664 continue;
665 ]
667 ctx := update_reaching_def(ctx, v, bgi);
669 var v1, v1_idx := clone_variable(ctx, v);
670 v1.defining_block := bgi;
671 v1.defining_instr := igi;
673 ctx.instrs[ ctx.blocks[bgi].instrs[ili] ].params[wr_idx] := v1_idx;
674 v1.reaching_def := ctx.variables[v].reaching_def;
675 ctx.variables[v].reaching_def := v1_idx;
677 ctx.variables +<= v1;
679 //eval debug("renaming bgi " + ntos(bgi) + ", idx " + ntos(ili) + ", var " + ntos(v) + " -> " + ntos(v1_idx) + " opcode " + ntos(instr.opcode));
680 ]
681 ]
683 for p := 0 to len(ctx.blocks[bgi].post_list) do [
684 var bbb := ctx.blocks[bgi].post_list[p];
685 var post_block := ctx.blocks[bbb];
686 for idx := 0 to len(post_block.pred_list) do [
687 if post_block.pred_list[idx] = bgi then [
688 //eval debug("bgi: " + ntos(bgi) + " p:" + ntos(idx) + " bbb:" + ntos(bbb));
689 for ili := 0 to len(ctx.blocks[bbb].instrs) do [
690 var igi := ctx.blocks[bbb].instrs[ili];
691 var instr := ctx.instrs[igi];
692 if instr.opcode <> P_Phi then
693 break;
695 var v := instr.params[idx + 1];
696 ctx := update_reaching_def(ctx, v, bgi);
697 //eval debug("adjusting phi, bgi " + ntos(bgi) + " bbb " + ntos(bbb) + " " + ntos(ctx.instrs[ igi ].params[idx + 1]) + " -> " + ntos(ctx.variables[v].reaching_def));
698 ctx.instrs[ igi ].params[idx + 1] := ctx.variables[v].reaching_def;
699 if ctx.variables[v].reaching_def = -1 then
700 abort internal("phi with uninitialized argument " + ntos(ctx.instrs[ ctx.blocks[bbb].instrs[ili]].params[0]) + ", bbb " + ntos(bbb) + ", instr " + ntos(ili) + " opcode " + ntos(instr.opcode) + " v " + ntos(v));
701 ]
702 ]
703 ]
704 ]
706 var is_idom_of := ctx.blocks[bgi].is_idom_of;
707 while is_idom_of <> 0 do [
708 var next : int := bsr is_idom_of;
709 is_idom_of btr= next;
710 ctx := rename_variables_recursive(ctx, next);
711 ]
712 return ctx;
713 ]
715 fn rename_variables(ctx : context) : context
716 [
717 return rename_variables_recursive(ctx, 0);
718 ]
720 fn verify_ssa(ctx : context) : context
721 [
722 if not check then
723 return ctx;
724 var assign_mask : var_set := 0;
725 var n_blocks := len(ctx.blocks);
726 for bgi := 0 to n_blocks do [
727 var block := ctx.blocks[bgi];
728 if not block.active then
729 continue;
730 for ili := 0 to len(block.instrs) do [
731 var igi := block.instrs[ili];
732 var ins := ctx.instrs[igi];
733 var write_mask := set_to_mask(ins, ins.write_set);
734 if (assign_mask and write_mask) <> 0 then [
735 abort internal("verify_ssa: variables are assigned multiple times: " + mtos(assign_mask and write_mask));
736 ]
737 assign_mask or= write_mask;
738 ]
739 ]
740 return ctx;
741 ]
744 fn remap_instruction(ins : instruction, var_map : list(int), test_write : bool) : instruction
745 [
746 var rs := ins.read_set;
747 while rs <> 0 do [
748 var idx : int := bsr rs;
749 rs btr= idx;
750 var param := ins.params[idx];
751 if param >= 0 then
752 ins.params[idx] := var_map[param];
753 ]
754 if test_write then [
755 var ws := ins.write_set;
756 while ws <> 0 do [
757 var idx : int := bsr ws;
758 ws btr= idx;
759 var param := ins.params[idx];
760 if var_map[param] <> param then
761 abort internal("output variable was remapped");
762 ]
763 ]
764 return ins;
765 ]
767 fn remap_variable(ctx : context, vgi : int) : context
768 [
769 var v := ctx.variables[vgi].type_index;
770 if v >= 0 then [
771 var vm := ctx.var_map[v];
772 ctx.variables[vgi].type_index := vm;
773 if vm > T_Undetermined and vm < 0 then [
774 ctx.variables[vgi].runtime_type := vm;
775 ] else if vm >= 0, ctx.variables[vm].is_option_type then [
776 if ctx.variables[vm].always_flat_option then
777 ctx.variables[vgi].runtime_type := T_AlwaysFlatOption;
778 else
779 ctx.variables[vgi].runtime_type := T_FlatOption;
780 ]
781 ]
782 return ctx;
783 ]
785 fn gvn_recursive(ctx : context, bgi : int, vals : list(int)) : context
786 [
787 for i := 0 to len(ctx.blocks[bgi].instrs) do [
788 var igi := ctx.blocks[bgi].instrs[i];
789 var ins := ctx.instrs[igi];
790 ins := remap_instruction(ins, ctx.var_map, true);
791 ctx.instrs[igi] := ins;
792 if ins.opcode = P_Copy then [
793 var dest : int := ins.params[0];
794 var src : int := ins.params[2];
795 ctx.var_map[dest] := src;
796 continue;
797 ]
798 if ins.opcode = P_Free or
799 ins.opcode = P_Load_Local_Type or
800 ins.opcode = P_Eval or
801 ins.opcode = P_Keep or
802 ins.opcode = P_Jmp or
803 ins.opcode = P_Jmp_False or
804 ins.opcode = P_Label or
805 ins.opcode = P_IO or
806 ins.opcode = P_Args or
807 ins.opcode = P_Return_Vars or
808 ins.opcode = P_Return or
809 ins.opcode = P_Line_Info
810 then continue;
812 var value_list := list(pcode_t).[ ins.opcode, len(ins.params) ];
813 for i := 0 to len(ins.params) do [
814 if ins.write_set bt i then
815 continue;
816 var v := ins.params[i];
817 if ins.free_set bt i + 1 then
818 v and= not Flag_Free_Argument;
819 value_list +<= v;
820 ]
822 if ins.opcode = P_UnaryOp, ins.params[0] = Un_ConvertFromInt then [
823 value_list +<= ctx.variables[ins.params[1]].runtime_type;
824 ]
825 if ins.opcode = P_Copy_Type_Cast then [
826 if ctx.variables[ins.params[0]].runtime_type = T_Undetermined then
827 continue;
828 if ctx.variables[ins.params[1]].runtime_type = T_Undetermined then
829 continue;
830 value_list +<= ctx.variables[ins.params[0]].runtime_type;
831 ]
832 if ins.opcode = P_Load_Const then [
833 value_list +<= ctx.variables[ins.params[0]].runtime_type;
834 ]
836 var value_number := gvn_encode(value_list);
837 if vals[value_number] = -1 then [
838 vals[value_number] := igi;
839 continue;
840 ]
841 //eval debug("gvn found a case, opcode " + ntos(ins.opcode) + " vn " + ntos_base(value_number, 16));
842 var prev_ins := ctx.instrs[vals[value_number]];
843 if ins.write_set <> prev_ins.write_set then
844 abort internal("write set of the old and new instruction doesn't match");
845 var ws := ins.write_set;
846 while ws <> 0 do [
847 var idx : int := bsr ws;
848 ws btr= idx;
849 var prev_result := prev_ins.params[idx];
850 var new_result := ins.params[idx];
851 if ctx.var_map[new_result] <> new_result then
852 abort internal("variable was already remapped");
853 ctx.var_map[new_result] := prev_result;
854 ]
855 ]
857 var is_idom_of := ctx.blocks[bgi].is_idom_of;
858 while is_idom_of <> 0 do [
859 var next : int := bsr is_idom_of;
860 is_idom_of btr= next;
861 ctx := gvn_recursive(ctx, next, vals);
862 ]
864 return ctx;
865 ]
867 fn gvn(ctx : context) : context
868 [
869 var vals := infinite(-1);
871 ctx.var_map := fill(-1, len(ctx.variables));
872 for vgi := 0 to len(ctx.variables) do
873 ctx.var_map[vgi] := vgi;
875 ctx := gvn_recursive(ctx, 0, vals);
877 for vgi := 0 to len(ctx.variables) do
878 ctx := remap_variable(ctx, vgi);
880 return ctx;
881 ]
883 fn verify_positive(ctx : context, vgii : int) : bool
884 [
885 var done : var_set := 0;
886 var todo : var_set := 0;
887 todo bts= vgii;
888 while todo <> 0 do [
889 var vgi : int := bsr todo;
890 todo btr= vgi;
891 done bts= vgi;
892 var v := ctx.variables[vgi];
893 var ins := ctx.instrs[v.defining_instr];
894 if ins.opcode = P_Phi then [
895 for i := 1 to len(ins.params) do [
896 var p := ins.params[i];
897 if not done bt p then
898 todo bts= p;
899 ]
900 ] else if ins.opcode = P_BinaryOp,
901 ins.params[0] = Bin_Add or
902 ins.params[0] = Bin_Multiply or
903 ins.params[0] = Bin_Power or
904 ins.params[0] = Bin_And or
905 ins.params[0] = Bin_Or or
906 ins.params[0] = Bin_Xor or
907 ins.params[0] = Bin_Shl or
908 ins.params[0] = Bin_Shr or
909 ins.params[0] = Bin_Bts or
910 ins.params[0] = Bin_Btr or
911 ins.params[0] = Bin_Btc then [
912 var p := ins.params[3];
913 if not done bt p then
914 todo bts= p;
915 p := ins.params[5];
916 if not done bt p then
917 todo bts= p;
918 continue;
919 ] else if ins.opcode = P_BinaryConstOp,
920 ins.params[4] >= 0,
921 ins.params[0] = Bin_Add or
922 ins.params[0] = Bin_Multiply or
923 ins.params[0] = Bin_Power or
924 ins.params[0] = Bin_And or
925 ins.params[0] = Bin_Or or
926 ins.params[0] = Bin_Xor or
927 ins.params[0] = Bin_Shl or
928 ins.params[0] = Bin_Shr or
929 ins.params[0] = Bin_Bts or
930 ins.params[0] = Bin_Btr or
931 ins.params[0] = Bin_Btc then [
932 var p := ins.params[3];
933 if not done bt p then
934 todo bts= p;
935 continue;
936 ] else if ins.opcode = P_Load_Const then [
937 var l := blob_to_int(ins.params[1 ..]);
938 if l < 0 then
939 return false;
940 ] else [
941 return false;
942 ]
943 ]
944 return true;
945 ]
947 fn operator_not~inline(op : pcode_t) : pcode_t
948 [
949 if op = Bin_Equal then return Bin_NotEqual;
950 if op = Bin_NotEqual then return Bin_Equal;
951 if op = Bin_Less then return Bin_GreaterEqual;
952 if op = Bin_GreaterEqual then return Bin_Less;
953 if op = Bin_LessEqual then return Bin_Greater;
954 if op = Bin_Greater then return Bin_LessEqual;
955 return -1;
956 ]
958 fn operator_swap~inline(op : pcode_t) : pcode_t
959 [
960 if op = Bin_Add then return op;
961 if op = Bin_Multiply then return op;
962 if op = Bin_And then return op;
963 if op = Bin_Or then return op;
964 if op = Bin_Xor then return op;
965 if op = Bin_Equal then return op;
966 if op = Bin_NotEqual then return op;
967 if op = Bin_Less then return Bin_Greater;
968 if op = Bin_LessEqual then return Bin_GreaterEqual;
969 if op = Bin_Greater then return Bin_Less;
970 if op = Bin_GreaterEqual then return Bin_LessEqual;
971 return -1;
972 ]
974 fn simplify_instr(ctx : context, ins : instruction) : (instruction, bool)
975 [
976 if ins.opcode = P_Load_Local_Type then [
977 var params := list(pcode_t).[ IO_Exception_Make, 1, 0, 4, ins.params[0], ec_sync, error_optimizer_error, 0, 1 ];
978 return create_instr(P_IO, params, ins.bb), true;
979 ]
980 if ins.opcode = P_Curry then [
981 var vgi := ins.params[3];
982 var v := ctx.variables[vgi];
983 var fn_ins := ctx.instrs[v.defining_instr];
984 if fn_ins.opcode = P_Load_Fn then [
985 fn_ins.params[0] := ins.params[0];
986 fn_ins.params[1] += ins.params[1];
987 fn_ins.params += ins.params[4 .. ];
988 return create_instr(P_Load_Fn, fn_ins.params, ins.bb), true;
989 ]
990 if fn_ins.opcode = P_Curry then [
991 fn_ins.params[0] := ins.params[0];
992 fn_ins.params[1] += ins.params[1];
993 fn_ins.params += ins.params[4 .. ];
994 return create_instr(P_Curry, fn_ins.params, ins.bb), true;
995 ]
996 goto end;
997 ]
998 if ins.opcode = P_Call_Indirect then [
999 var vgi := ins.params[4];
1000 var v := ctx.variables[vgi];
1001 var fn_ins := ctx.instrs[v.defining_instr];
1002 if fn_ins.opcode = P_Load_Fn then [
1003 var fn_spec_len := function_specifier_length(fn_ins.params[3 .. ]);
1004 var fn_args := fn_ins.params[3 + fn_spec_len .. ];
1005 var call_params := list(pcode_t).[ ins.params[0], ins.params[1], ins.params[2] + fn_ins.params[1]] + fn_ins.params[3 .. 3 + fn_spec_len] + fn_args + ins.params[5 .. ];
1006 if fn_ins.params[2] = Call_Mode_Flat then
1007 call_params[0] := fn_ins.params[2];
1008 else if call_params[0] = Call_Mode_Unspecified then
1009 call_params[0] := fn_ins.params[2];
1010 return create_instr(P_Call, call_params, ins.bb), true;
1011 ]
1012 if fn_ins.opcode = P_Curry then [
1013 ins.params[2] += fn_ins.params[1];
1014 ins.params[4] := fn_ins.params[3];
1015 var call_indirect_params := ins.params[0 .. 5] + fn_ins.params[4 .. ] + ins.params[5 .. ];
1016 return create_instr(P_Call_Indirect, call_indirect_params, ins.bb), true;
1017 ]
1018 goto end;
1019 ]
1020 if ins.opcode = P_BinaryOp then [
1021 var vgi1 := ins.params[3];
1022 var v1 := ctx.variables[vgi1];
1023 var v1_ins := ctx.instrs[v1.defining_instr];
1024 var vgi2 := ins.params[5];
1025 var v2 := ctx.variables[vgi2];
1026 var v2_ins := ctx.instrs[v2.defining_instr];
1027 var vgir := ins.params[1];
1028 var vr := ctx.variables[vgir];
1029 //eval debug("test const vgi " + ntos(vgi1) + " " + ntos(vgi2));
1030 //eval debug("test const " + ntos(v1_ins.opcode) + " " + ntos(v2_ins.opcode));
1031 if v1_ins.opcode = P_Load_Const and v2_ins.opcode = P_Load_Const then [
1032 //var str : bytes;
1033 //str := "v1: (" + ntos(vgi1) + ")"; for i := 0 to len(v1_ins.params) do [ str += " " + ntos(v1_ins.params[i]); ]; eval debug(str);
1034 //str := "v2: (" + ntos(vgi2) + ")"; for i := 0 to len(v2_ins.params) do [ str += " " + ntos(v2_ins.params[i]); ]; eval debug(str);
1035 var c := evaluate_binary(v1.runtime_type, vr.runtime_type, ins.params[0], v1_ins.params[1 ..], v2_ins.params[1 ..]);
1036 if is_exception c then
1037 return ins, false;
1038 var params := list(pcode_t).[ ins.params[1] ] + c;
1039 //str := "vr:"; for i := 0 to len(params) do [ str += " " + ntos(params[i]); ]; eval debug(str);
1040 return create_instr(P_Load_Const, params, ins.bb), true;
1041 ]
1042 if v1.runtime_type = T_AlwaysFlatOption then [
1043 var c res : int;
1044 var op := ins.params[0];
1045 if v1_ins.opcode = P_Load_Const then [
1046 c := blob_to_int(v1_ins.params[1 .. ]);
1047 ] else if v2_ins.opcode = P_Load_Const then [
1048 c := blob_to_int(v2_ins.params[1 .. ]);
1049 op := operator_swap(op);
1050 ] else [
1051 goto skip_bool;
1052 ]
1053 if op = Bin_And, c = 0 then [
1054 res := 0;
1055 ] else if op = Bin_Or, c = 1 then [
1056 res := 1;
1057 ] else if op = Bin_Less, c = 1 then [
1058 res := 0;
1059 ] else if op = Bin_LessEqual, c = 0 then [
1060 res := 1;
1061 ] else if op = Bin_Greater, c = 0 then [
1062 res := 0;
1063 ] else if op = Bin_GreaterEqual, c = 1 then [
1064 res := 1;
1065 ] else [
1066 goto skip_bool;
1067 ]
1068 var params := list(pcode_t).[ ins.params[1] ] + int_to_blob(res);
1069 return create_instr(P_Load_Const, params, ins.bb), true;
1070 skip_bool:
1071 ]
1072 if v1.runtime_type <= T_SInt8, v1.runtime_type >= T_Integer128, v2_ins.opcode = P_Load_Const then [
1073 var i := blob_to_int(v2_ins.params[1 .. ]);
1074 //if v1.runtime_type <= T_SInt8, v1.runtime_type >= T_UInt128 then eval debug("evaluating constant " + ntos(i));
1075 // this logic is copied in frame_t_from_const
1076 var lower_limit, upper_limit := -#40000000, #3fffffff;
1077 if v1.runtime_type = T_Integer8 or v1.runtime_type = T_SInt8 then
1078 lower_limit, upper_limit := -#80, #80;
1079 if v1.runtime_type = T_UInt8 then
1080 lower_limit, upper_limit := #0, #100;
1081 if v1.runtime_type = T_Integer16 or v1.runtime_type = T_SInt16 then
1082 lower_limit, upper_limit := -#8000, #8000;
1083 if v1.runtime_type = T_UInt16 then
1084 lower_limit, upper_limit := #0, #10000;
1085 if v1.runtime_type = T_UInt32 or v1.runtime_type = T_UInt64 or v1.runtime_type = T_UInt128 then
1086 lower_limit := #0;
1087 if i >= lower_limit, i < upper_limit then
1088 return create_instr(P_BinaryConstOp, ins.params[ .. 4] +< i, ins.bb), true;
1089 ]
1090 if v1.runtime_type <= T_SInt8, v1.runtime_type >= T_Integer128, v1_ins.opcode = P_Load_Const then [
1091 var new_op := operator_swap(ins.params[0]);
1092 if new_op >= 0 then [
1093 var params := ins.params;
1094 params[0] := new_op;
1095 params[2] := ins.params[4];
1096 params[3] := ins.params[5];
1097 params[4] := ins.params[2];
1098 params[5] := ins.params[3];
1099 return create_instr(P_BinaryOp, params, ins.bb), true;
1100 ]
1101 ]
1102 if v1_ins.opcode = P_IO, v1_ins.params[0] = IO_Exception_Make,
1103 v1.runtime_type <> T_AlwaysFlatOption or (v2_ins.opcode = P_IO and v2_ins.params[0] = IO_Exception_Make) then [
1104 var params := v1_ins.params;
1105 params[4] := ins.params[1];
1106 return create_instr(P_IO, params, ins.bb), true;
1107 ]
1108 if v2_ins.opcode = P_IO, v2_ins.params[0] = IO_Exception_Make,
1109 v1.runtime_type <> T_AlwaysFlatOption then [
1110 var params := v2_ins.params;
1111 params[4] := ins.params[1];
1112 return create_instr(P_IO, params, ins.bb), true;
1113 ]
1114 if ins.params[0] = Bin_Less, v2_ins.opcode = P_Array_Len then [
1115 //eval debug(ctx.name + ": P_Array_Len_Greater_Than optimized");
1116 var params := list(pcode_t).[ vgir, v2_ins.params[1], vgi1, 0 ];
1117 return create_instr(P_Array_Len_Greater_Than, params, ins.bb), true;
1118 ]
1119 goto end;
1120 ]
1121 if ins.opcode = P_BinaryConstOp then [
1122 var vgi1 := ins.params[3];
1123 var v1 := ctx.variables[vgi1];
1124 var v1_ins := ctx.instrs[v1.defining_instr];
1125 var vgir := ins.params[1];
1126 var vr := ctx.variables[vgir];
1127 if v1_ins.opcode = P_Load_Const then [
1128 var cnst := ins.params[4];
1129 var c := evaluate_binary(v1.runtime_type, vr.runtime_type, ins.params[0], v1_ins.params[1 ..], int_to_blob(cnst));
1130 if is_exception c then
1131 return ins, false;
1132 var params := list(pcode_t).[ ins.params[1] ] + c;
1133 return create_instr(P_Load_Const, params, ins.bb), true;
1134 ]
1135 if vr.runtime_type <= T_SInt8, vr.runtime_type >= T_Integer128 then [
1136 if ins.params[0] = Bin_Multiply, ins.params[4] = 2 then [
1137 return create_instr(P_BinaryOp, list(pcode_t).[ Bin_Add, ins.params[1], ins.params[2], ins.params[3], ins.params[2], ins.params[3] ], ins.bb), true;
1138 ]
1139 if ins.params[0] = Bin_Shl, ins.params[4] = 1 then [
1140 return create_instr(P_BinaryOp, list(pcode_t).[ Bin_Add, ins.params[1], ins.params[2], ins.params[3], ins.params[2], ins.params[3] ], ins.bb), true;
1141 ]
1142 ]
1143 goto end;
1144 ]
1145 if ins.opcode = P_UnaryOp then [
1146 var vgi1 := ins.params[3];
1147 var v1 := ctx.variables[vgi1];
1148 var v1_ins := ctx.instrs[v1.defining_instr];
1149 var vgir := ins.params[1];
1150 var vr := ctx.variables[vgir];
1151 if v1_ins.opcode = P_Load_Const then [
1152 //var str : bytes;
1153 //str := "v1: (" + ntos(vgi1) + ")"; for i := 0 to len(v1_ins.params) do [ str += " " + ntos(v1_ins.params[i]); ]; eval debug(str);
1154 var c := evaluate_unary(v1.runtime_type, vr.runtime_type, ins.params[0], v1_ins.params[1 ..]);
1155 if is_exception c then
1156 return ins, false;
1157 var params := list(pcode_t).[ ins.params[1] ] + c;
1158 //str := "vr:"; for i := 0 to len(params) do [ str += " " + ntos(params[i]); ]; eval debug(str);
1159 return create_instr(P_Load_Const, params, ins.bb), true;
1160 ]
1161 if v1_ins.opcode = P_IO, v1_ins.params[0] = IO_Exception_Make,
1162 ins.params[0] <> Un_IsException, ins.params[0] <> Un_ExceptionClass, ins.params[0] <> Un_ExceptionType, ins.params[0] <> Un_ExceptionAux then [
1163 var params := v1_ins.params;
1164 params[4] := ins.params[1];
1165 return create_instr(P_IO, params, ins.bb), true;
1166 ]
1167 if ins.params[0] = Un_Not, v1_ins.opcode = P_BinaryOp or v1_ins.opcode = P_BinaryConstOp then [
1168 var new_op := operator_not(v1_ins.params[0]);
1169 if new_op >= 0 then [
1170 var params := v1_ins.params;
1171 params[0] := new_op;
1172 params[1] := ins.params[1];
1173 return create_instr(v1_ins.opcode, params, ins.bb), true;
1174 ]
1175 ]
1176 goto end;
1177 ]
1178 if ins.opcode = P_Option_Test then [
1179 var idx := ins.params[2];
1180 var vgis := ins.params[1];
1181 var vs := ctx.variables[vgis];
1182 var vs_ins := ctx.instrs[vs.defining_instr];
1183 var is_idx := -1;
1184 if vs_ins.opcode = P_Option_Create then [
1185 is_idx := vs_ins.params[1];
1186 ] else if vs_ins.opcode = P_Load_Const then [
1187 is_idx := blob_to_int(vs_ins.params[1 ..]);
1188 ]
1189 if is_idx >= 0 then [
1190 var res : int;
1191 if idx = is_idx then
1192 res := 1;
1193 else
1194 res := 0;
1195 return create_instr(P_Load_Const, list(pcode_t).[ ins.params[0] ] + int_to_blob(res), ins.bb), true;
1196 ]
1197 goto end;
1198 ]
1199 if ins.opcode = P_Array_Load then [
1200 if (ins.params[1] and Flag_Index_In_Range) <> 0 then
1201 goto end;
1202 var vgis := ins.params[2];
1203 var vgii := ins.params[3];
1204 var bgi := ins.bb;
1205 var dom_set := ctx.blocks[bgi].dom;
1206 while dom_set <> 0 do [
1207 var dom : int := bsr dom_set;
1208 dom_set btr= dom;
1209 var bb := ctx.blocks[dom];
1210 if not bb.active then
1211 abort internal("dominator is not active");
1212 if len(bb.pred_list) = 0 then
1213 goto next_dom;
1214 for i := 0 to len(bb.pred_list) do [
1215 if bb.pred_position[i] <> 0 then
1216 goto next_dom;
1217 var bb_pred := ctx.blocks[bb.pred_list[i]];
1218 if len(bb_pred.instrs) = 0 then
1219 goto next_dom;
1220 var lins := ctx.instrs[bb_pred.instrs[len(bb_pred.instrs) - 1]];
1221 if lins.opcode <> P_Jmp_False then
1222 goto next_dom;
1223 var vgic := lins.params[0];
1224 var dins := ctx.instrs[ctx.variables[vgic].defining_instr];
1225 if dins.opcode <> P_Array_Len_Greater_Than then
1226 goto next_dom;
1227 if dins.params[1] <> vgis or dins.params[2] <> vgii then
1228 goto next_dom;
1229 ]
1230 if not verify_positive(ctx, vgii) then
1231 goto next_dom;
1232 //eval debug(ctx.name + ": array index optimized");
1233 ins.params[1] or= Flag_Index_In_Range;
1234 return ins, true;
1235 next_dom:
1236 ]
1237 goto end;
1238 ]
1239 if ins.opcode = P_Array_Len then [
1240 var vgis := ins.params[1];
1241 var vs := ctx.variables[vgis];
1242 var vs_ins := ctx.instrs[vs.defining_instr];
1243 if vs_ins.opcode = P_Array_Create then [
1244 return create_instr(P_Load_Const, list(pcode_t).[ ins.params[0] ] + int_to_blob(vs_ins.params[2]), ins.bb), true;
1245 ]
1246 goto end;
1247 ]
1248 if ins.opcode = P_Array_Len_Greater_Than then [
1249 var vgis := ins.params[1];
1250 var vs := ctx.variables[vgis];
1251 var vs_ins := ctx.instrs[vs.defining_instr];
1252 var vgii := ins.params[2];
1253 var vi := ctx.variables[vgii];
1254 var vi_ins := ctx.instrs[vi.defining_instr];
1255 if vs_ins.opcode = P_Array_Create and vi_ins.opcode = P_Load_Const then [
1256 var l := blob_to_int(vi_ins.params[1 ..]);
1257 if l >= 0 then [
1258 var v : int;
1259 if vs_ins.params[2] > l then
1260 v := 1;
1261 else
1262 v := 0;
1263 return create_instr(P_Load_Const, list(pcode_t).[ ins.params[0] ] + int_to_blob(v), ins.bb), true;
1264 ]
1265 ]
1266 goto end;
1267 ]
1268 if ins.opcode = P_Array_Append then [
1269 var vgi2 := ins.params[4];
1270 var vs2 := ctx.variables[vgi2];
1271 var vs2_ins := ctx.instrs[vs2.defining_instr];
1272 if vs2_ins.opcode = P_Array_Create, vs2_ins.params[2] = 1 then [
1273 return create_instr(P_Array_Append_One, ins.params[ .. 4] +< vs2_ins.params[5], ins.bb), true;
1274 ]
1275 goto end;
1276 ]
1277 end:
1278 if ins.borrow <> -1, (ins.params[ins.borrow - 1] and Flag_Borrow) = 0 then [
1279 ins.params[ins.borrow - 1] or= Flag_Borrow;
1280 return ins, true;
1281 ]
1282 return ins, false;
1283 ]
1285 fn substitute_variable(ctx : context, ins : instruction) : (int, int)
1286 [
1287 if ins.opcode = P_Phi then [
1288 var p := ins.params[1];
1289 for i := 2 to len(ins.params) do
1290 if ins.params[i] <> p then
1291 goto nothing;
1292 return ins.params[0], ins.params[1];
1293 ]
1295 if ins.opcode = P_Record_Load then [
1296 var idx := ins.params[3];
1297 var vgis := ins.params[2];
1298 var vs := ctx.variables[vgis];
1299 var vs_ins := ctx.instrs[vs.defining_instr];
1300 if vs_ins.opcode = P_Record_Create then [
1301 return ins.params[0], vs_ins.params[3 + idx * 2];
1302 ]
1303 ]
1304 if ins.opcode = P_Option_Load then [
1305 var idx := ins.params[3];
1306 var vgis := ins.params[2];
1307 var vs := ctx.variables[vgis];
1308 var vs_ins := ctx.instrs[vs.defining_instr];
1309 if vs_ins.opcode = P_Option_Create then [
1310 if vs_ins.params[1] = idx then [
1311 return ins.params[0], vs_ins.params[3];
1312 ]
1313 ]
1314 ]
1315 if ins.opcode = P_Array_Load then [
1316 var vgii := ins.params[3];
1317 var vi := ctx.variables[vgii];
1318 var vi_ins := ctx.instrs[vi.defining_instr];
1319 var vgis := ins.params[2];
1320 var vs := ctx.variables[vgis];
1321 var vs_ins := ctx.instrs[vs.defining_instr];
1322 if vi_ins.opcode = P_Load_Const and vs_ins.opcode = P_Array_Create then [
1323 var idx := blob_to_int(vi_ins.params[1 ..]);
1324 if idx >= 0 and idx < vs_ins.params[2] then [
1325 return ins.params[0], vs_ins.params[5 + idx * 2];
1326 ]
1327 ]
1328 if vi_ins.opcode = P_Load_Const and vs_ins.opcode = P_Array_Fill then [
1329 var vgll := vs_ins.params[4];
1330 var vl := ctx.variables[vgll];
1331 var vl_ins := ctx.instrs[vl.defining_instr];
1332 if vl_ins.opcode = P_Load_Const then [
1333 var idx := blob_to_int(vi_ins.params[1 ..]);
1334 var length := blob_to_int(vl_ins.params[1 ..]);
1335 if idx >= 0 and idx < length then [
1336 return ins.params[0], vs_ins.params[3];
1337 ]
1338 ]
1339 ]
1340 ]
1342 nothing:
1343 return -1, -1;
1344 ]
1346 fn misc_opt(ctx : context) : context
1347 [
1348 var n_blocks := len(ctx.blocks);
1350 again:
1351 var again := false;
1352 for bgi := 0 to n_blocks do [
1353 var block := ctx.blocks[bgi];
1354 if not block.active then
1355 continue;
1356 var l := len(block.instrs);
1357 for ili := 0 to l do [
1358 var igi := ctx.blocks[bgi].instrs[ili];
1359 var ins := ctx.instrs[igi];
1360 ins := remap_instruction(ins, ctx.var_map, false);
1361 var did_something : bool;
1362 //eval debug("simplify_instr: bb " + ntos(bgi) + ", idx " + ntos(ili));
1363 ins, did_something := simplify_instr(ctx, ins);
1364 if did_something then
1365 again := true;
1366 ctx.instrs[igi] := ins;
1368 var src, dst := substitute_variable(ctx, ins);
1369 if src >= 0, ctx.var_map[src] <> dst then [
1370 ctx.var_map[src] := dst;
1371 again := true;
1372 ]
1374 if ins.opcode = P_Jmp_False then [
1375 var vgi1 := ins.params[0];
1376 var v1 := ctx.variables[vgi1];
1377 var v1_ins := ctx.instrs[v1.defining_instr];
1378 var vgir := ins.params[1];
1379 var vr := ctx.variables[vgir];
1380 if v1_ins.opcode = P_Load_Const then [
1381 var const_int := blob_to_int(v1_ins.params[1 ..]);
1382 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[ .. l - 1];
1383 if const_int = 0 then [
1384 ctx := deactivate_arrow(ctx, bgi, 2);
1385 ctx := deactivate_arrow(ctx, bgi, 0);
1386 ] else if const_int = 1 then [
1387 ctx := deactivate_arrow(ctx, bgi, 2);
1388 ctx := deactivate_arrow(ctx, bgi, 1);
1389 ] else
1390 abort internal("invalid constant in bool context: " + ntos(const_int));
1391 ctx.should_retry := true;
1392 ] else if v1_ins.opcode = P_IO and v1_ins.params[0] = IO_Exception_Make then [
1393 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[ .. l - 1];
1394 ctx := deactivate_arrow(ctx, bgi, 0);
1395 ctx := deactivate_arrow(ctx, bgi, 1);
1396 ctx.should_retry := true;
1397 ]
1398 ]
1399 ]
1400 ]
1401 if again then
1402 goto again;
1404 return ctx;
1405 ]
1407 fn dce(ctx : context) : context
1408 [
1409 for vgi := 0 to len(ctx.variables) do [
1410 ctx.variables[vgi].color := -1;
1411 ]
1412 var worklist : var_set := 0;
1413 var n_blocks := len(ctx.blocks);
1414 for bgi := 0 to n_blocks do [
1415 var block := ctx.blocks[bgi];
1416 if not block.active then
1417 continue;
1418 var l := len(block.instrs);
1419 //eval debug("block: " + ntos(bgi));
1420 if l > 0 then [
1421 var igi_last := block.instrs[l - 1];
1422 var ins := ctx.instrs[igi_last];
1423 //eval debug("l: " + ntos(l) + " opcode: " + ntos(ins.opcode));
1424 if ins.opcode = P_Return or ins.opcode = P_Jmp_False then [
1425 var read_mask := set_to_mask(ins, ins.read_set);
1426 worklist or= read_mask;
1427 //eval debug("read_mask: " + ntos_base(read_mask, 2));
1428 ]
1430 // function arguments must not be elided, even if they are unused
1431 var igi_first := block.instrs[0];
1432 ins := ctx.instrs[igi_first];
1433 if ins.opcode = P_Args then [
1434 var write_mask := set_to_mask(ins, ins.write_set);
1435 while write_mask <> 0 do [
1436 var vgi : int := bsr write_mask;
1437 write_mask btr= vgi;
1438 if ctx.variables[vgi].type_index <> T_Type then [
1439 ctx.variables[vgi].color := vgi;
1440 ]
1441 ]
1442 ]
1443 ]
1444 for ili := 0 to l do [
1445 var igi := block.instrs[ili];
1446 var ins := ctx.instrs[igi];
1447 if ins.opcode = P_Eval or ins.opcode = P_Keep or ins.opcode = P_Assume or ins.opcode = P_Claim then [
1448 if ins.params[0] >= 0 then
1449 worklist bts= ins.params[0];
1450 ]
1451 ]
1452 ]
1454 var done : var_set := 0;
1455 while worklist <> 0 do [
1456 //eval debug("worklist: " + ntos_base(worklist, 2));
1457 var vgi : int := bsr worklist;
1458 worklist btr= vgi;
1459 if ctx.variables[vgi].type_index <> T_Type then
1460 ctx.variables[vgi].color := vgi;
1461 done bts= vgi;
1462 var igi := ctx.variables[vgi].defining_instr;
1463 var ins := ctx.instrs[igi];
1464 var var_mask := set_to_mask(ins, ins.read_set) or set_to_mask(ins, ins.write_set);
1465 //eval debug("variable " + ntos(vgi) + " defined at " + ntos(igi) + " opcode " + ntos(ins.opcode) + " read_mask " + mtos(set_to_mask(ins, ins.read_set)) + " write_mask " + mtos(set_to_mask(ins, ins.write_set)));
1466 worklist or= var_mask and not done;
1467 ]
1469 return ctx;
1470 ]
1472 fn dce2(ctx : context) : context
1473 [
1474 for vgi := 0 to len(ctx.variables) do [
1475 ctx.variables[vgi].needed := false;
1476 ]
1477 var worklist : var_set := 0;
1478 for vgi := 0 to len(ctx.variables) do [
1479 ctx := remap_variable(ctx, vgi);
1480 var v := ctx.variables[vgi].type_index;
1481 if v >= 0 then
1482 worklist bts= v;
1483 if ctx.variables[vgi].color >= 0 then
1484 worklist bts= vgi;
1485 ]
1487 for bgi := 0 to len(ctx.blocks) do [
1488 if not ctx.blocks[bgi].active then
1489 continue;
1490 if len(ctx.blocks[bgi].instrs) > 0 then [
1491 var ili := len(ctx.blocks[bgi].instrs) - 1;
1492 var igi := ctx.blocks[bgi].instrs[ili];
1493 var ins := ctx.instrs[igi];
1494 if ins.write_set = 0 then [
1495 var read_mask := set_to_mask(ins, ins.read_set);
1496 worklist or= read_mask;
1497 ]
1498 ]
1499 ]
1501 var done : var_set := 0;
1502 while worklist <> 0 do [
1503 //eval debug("worklist: " + ntos_base(worklist, 2));
1504 var vgi : int := bsr worklist;
1505 worklist btr= vgi;
1506 ctx.variables[vgi].needed := true;
1507 done bts= vgi;
1508 var igi := ctx.variables[vgi].defining_instr;
1509 if igi = -1 then
1510 continue;
1511 var ins := ctx.instrs[igi];
1512 var var_mask := set_to_mask(ins, ins.read_set) or set_to_mask(ins, ins.write_set);
1513 //eval debug("variable " + ntos(vgi) + " defined at " + ntos(igi) + " opcode " + ntos(ins.opcode) + " read_mask " + mtos(set_to_mask(ins, ins.read_set)) + " write_mask " + mtos(set_to_mask(ins, ins.write_set)));
1514 worklist or= var_mask and not done;
1515 ]
1517 for bgi := 0 to len(ctx.blocks) do [
1518 if not ctx.blocks[bgi].active then
1519 continue;
1520 var ili := 0;
1521 while len_greater_than(int, ctx.blocks[bgi].instrs, ili) do [
1522 var igi := ctx.blocks[bgi].instrs[ili];
1523 var ins := ctx.instrs[igi];
1524 if ins.opcode = P_Args then
1525 goto cont;
1526 var write_set := ins.write_set;
1527 if write_set = 0 then
1528 goto cont;
1529 while write_set <> 0 do [
1530 var p : int := bsr write_set;
1531 write_set btr= p;
1532 var v := ins.params[p];
1533 if ctx.variables[v].needed then
1534 goto cont;
1535 if ctx.variables[v].color >= 0 then
1536 goto cont;
1537 ]
1538 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[ .. ili ] + ctx.blocks[bgi].instrs[ ili + 1 .. ];
1539 if false then [
1540 cont:
1541 ili += 1;
1542 ]
1543 ]
1544 ]
1546 return ctx;
1547 ]
1549 fn create_lt(ctx : context) : context
1550 [
1551 var did_something need_retry : bool;
1552 retry:
1553 did_something := false;
1554 need_retry := false;
1556 for vgi := 0 to len(ctx.variables) do [
1557 var v := ctx.variables[vgi];
1558 if v.local_type >= 0 then
1559 continue;
1560 if v.defining_instr < 0 then
1561 continue;
1562 var ins := ctx.instrs[v.defining_instr];
1563 if ins.opcode = P_Record_Type then [
1564 var ltfr := local_type_flat_record.[
1565 non_flat_record : -1,
1566 flat_types : empty(int),
1567 ];
1568 for i := 0 to ins.params[1] do [
1569 var l := ins.params[2 + i];
1570 if l = T_Undetermined then [
1571 goto skip;
1572 ]
1573 if l < 0 then [
1574 ltfr.flat_types +<= l;
1575 ] else if ctx.variables[l].local_type >= 0 then [
1576 ltfr.flat_types +<= ctx.variables[l].local_type;
1577 ] else [
1578 need_retry := true;
1579 goto skip;
1580 ]
1581 ]
1583 var n, f := function_load(ins.params[2 + ins.params[1] .. ]);
1584 ltfr.non_flat_record := len(ctx.local_types);
1585 ctx.local_types +<= local_type.rec.(f);
1587 ctx.variables[vgi].local_type := len(ctx.local_types);
1588 ctx.local_types +<= local_type.flat_rec.(ltfr);
1589 did_something := true;
1590 ] else if ins.opcode = P_Array_Fixed then [
1591 var ltfa := local_type_flat_array.[
1592 flat_type : T_InvalidType,
1593 number_of_elements : 1,
1594 ];
1595 var shape := ins.params[2];
1596 var vt2 := ctx.variables[shape];
1597 if vt2.defining_instr < 0 then [
1598 goto skip;
1599 ]
1600 var in2 := ctx.instrs[vt2.defining_instr];
1601 if in2.opcode <> P_Array_Create then [
1602 goto skip;
1603 ]
1604 for i := 0 to in2.params[2] do [
1605 var d := in2.params[5 + 2 * i];
1606 var vt3 := ctx.variables[d];
1607 if vt3.defining_instr < 0 then [
1608 goto skip;
1609 ]
1610 var in3 := ctx.instrs[vt3.defining_instr];
1611 if in3.opcode <> P_Load_Const then [
1612 goto skip;
1613 ]
1614 var n := blob_to_int(in3.params[1 .. ]);
1615 if n <= 0 or n > #100 then [
1616 goto skip;
1617 ]
1618 ltfa.number_of_elements *= n;
1619 if ltfa.number_of_elements > #100 then [
1620 goto skip;
1621 ]
1622 ]
1623 var l := ins.params[1];
1624 if l = T_Undetermined then [
1625 goto skip;
1626 ]
1627 if l < 0 then [
1628 ltfa.flat_type := l;
1629 ] else if ctx.variables[l].local_type >= 0 then [
1630 ltfa.flat_type := ctx.variables[l].local_type;
1631 ] else [
1632 need_retry := true;
1633 goto skip;
1634 ]
1636 ctx.variables[vgi].local_type := len(ctx.local_types);
1637 ctx.local_types +<= local_type.flat_array.(ltfa);
1638 did_something := true;
1639 ]
1640 skip:
1641 ]
1642 if need_retry, did_something then
1643 goto retry;
1645 for vgi := 0 to len(ctx.variables) do [
1646 var v := ctx.variables[vgi];
1647 var typ := v.type_index;
1648 if typ < 0 then
1649 continue;
1650 var vt := ctx.variables[typ];
1651 if vt.local_type >= 0 then
1652 ctx.variables[vgi].runtime_type := vt.local_type;
1653 ]
1655 return ctx;
1656 ]
1659 fn append_copy(ctx : context, dest : int, src : int, bgi : int) : context
1660 [
1661 var instr := create_instr(P_Copy, list(pcode_t).[dest, 0, src], bgi);
1662 var append_idx := len(ctx.blocks[bgi].instrs);
1663 if append_idx <> 0, ctx.instrs[ctx.blocks[bgi].instrs[append_idx - 1]].opcode = P_Jmp_False then
1664 append_idx -= 1;
1665 ctx := insert_instr(ctx, instr, len(ctx.blocks[bgi].instrs));
1666 return ctx;
1667 ]
1669 fn remove_phis(ctx : context) : context
1670 [
1671 for bgi := 0 to len(ctx.blocks) do [
1672 var block := ctx.blocks[bgi];
1673 if not block.active then
1674 continue;
1675 for ili := 0 to len(block.instrs) do [
1676 var phi_instr := ctx.instrs[block.instrs[ili]];
1677 if phi_instr.opcode <> P_Phi then
1678 break;
1680 var v := phi_instr.params[0];
1681 var v1, v1_idx := clone_variable(ctx, v);
1682 ctx.variables +<= v1;
1684 var copy_instr := create_instr(P_Copy, list(pcode_t).[ v, 0, v1_idx ], bgi);
1685 //eval debug("change phi to copy: " + ntos(v) + " <- " + ntos(v1_idx));
1686 ctx.instrs[block.instrs[ili]] := copy_instr;
1688 for prev_block_bli := 0 to len(ctx.blocks[bgi].pred_list) do [
1689 var block := ctx.blocks[bgi];
1690 var prev_bgi := block.pred_list[prev_block_bli];
1691 var pred_pos := block.pred_position[prev_block_bli];
1692 var src := phi_instr.params[prev_block_bli + 1];
1694 var prev_block := ctx.blocks[prev_bgi];
1696 if {false and} len(prev_block.post_list) = 1 then [
1697 ctx := append_copy(ctx, v1_idx, src, prev_bgi);
1698 //eval debug("append copy " + ntos(prev_bgi) + " " + ntos(src) + " -> " + ntos(v1_idx));
1699 ] else [
1700 var nb := new_basic_block;
1701 var nb_bgi := len(ctx.blocks);
1702 //eval debug("injecting block " + ntos(nb_bgi) + " between " + ntos(prev_bgi) + " and " + ntos(bgi));
1703 nb.pred_list := list(int).[ prev_bgi ];
1704 nb.pred_position := list(int).[ pred_pos ];
1705 nb.post_list := list(int).[ bgi ];
1706 ctx.blocks[bgi].pred_list[prev_block_bli] := nb_bgi;
1707 ctx.blocks[bgi].pred_position[prev_block_bli] := 0;
1709 if prev_block.post_list[pred_pos] <> bgi then
1710 abort internal("an arrow from previous block not found");
1712 //prev_block.post_list[pred_pos] := nb_bgi;
1713 ctx.blocks[prev_bgi].post_list[pred_pos] := nb_bgi;
1715 ctx.blocks +<= nb;
1716 ctx := append_copy(ctx, v1_idx, src, nb_bgi);
1717 ]
1718 ]
1719 ]
1720 ]
1722 return ctx;
1723 ]
1725 fn var_set_2_list(vs : var_set) : list(pcode_t)
1726 [
1727 var p := empty(pcode_t);
1728 while vs <> 0 do [
1729 var v : int := bsr vs;
1730 vs btr= v;
1731 p +<= v;
1732 ]
1733 return p;
1734 ]
1736 fn remap_variables(ctx : context, old_new : list(int)) : context
1737 [
1738 for bgi := 0 to len(ctx.blocks) do [
1739 if not ctx.blocks[bgi].active then
1740 continue;
1741 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
1742 var igi := ctx.blocks[bgi].instrs[ili];
1743 var ins := ctx.instrs[igi];
1744 if ins.opcode = P_Checkpoint then [
1745 var new_set : var_set := 0;
1746 for s := 0 to len(ins.params) do [
1747 var n := old_new[ins.params[s]];
1748 if n >= 0 then
1749 new_set bts= old_new[ins.params[s]];
1750 ]
1751 ctx.instrs[igi].params := var_set_2_list(new_set);
1752 continue;
1753 ]
1754 var s := ins.read_set or ins.write_set;
1755 while s <> 0 do [
1756 var p : int := bsr s;
1757 s btr= p;
1758 var parm := ctx.instrs[igi].params[p];
1759 if parm >= 0 then
1760 ctx.instrs[igi].params[p] := old_new[parm];
1761 ]
1762 ]
1763 ]
1764 return ctx;
1765 ]
1767 fn dve(ctx : context) : context
1768 [
1769 var old_new := fill(-1, len(ctx.variables));
1770 var new_old := empty(int);
1771 for vgi := 0 to len(ctx.variables) do [
1772 ctx.variables[vgi].needed := false;
1773 ]
1774 for bgi := 0 to len(ctx.blocks) do [
1775 if not ctx.blocks[bgi].active then
1776 continue;
1777 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
1778 var igi := ctx.blocks[bgi].instrs[ili];
1779 var ins := ctx.instrs[igi];
1780 var s := ins.read_set or ins.write_set;
1781 while s <> 0 do [
1782 var p : int := bsr s;
1783 s btr= p;
1784 var typ := ins.params[p];
1785 while typ >= 0, not ctx.variables[typ].needed do [
1786 ctx.variables[typ].needed := true;
1787 old_new[typ] := len(new_old);
1788 new_old +<= typ;
1789 typ := ctx.variables[typ].type_index;
1790 ]
1791 ]
1792 ]
1793 ]
1795 //if ctx.name = "tokenize_recursive" then eval debug("n_variables: " + ntos(len(ctx.variables)) + " -> " + ntos(len(new_old)));
1797 var new_variables := empty(variable);
1798 for i := 0 to len(new_old) do [
1799 var va := ctx.variables[new_old[i]];
1800 if va.type_index >= 0 then
1801 va.type_index := old_new[va.type_index];
1802 new_variables +<= va;
1803 ]
1804 ctx.variables := new_variables;
1806 ctx := remap_variables(ctx, old_new);
1808 return ctx;
1809 ]
1811 fn encode_local_type(lt : local_type) : int
1812 [
1813 var pc : list(pcode_t);
1814 if lt is rec then [
1815 pc := list(pcode_t).[ Local_Type_Record ] + function_store(lt.rec);
1816 ] else if lt is flat_rec then [
1817 pc := list(pcode_t).[ Local_Type_Flat_Record, lt.flat_rec.non_flat_record, len(lt.flat_rec.flat_types) ];
1818 for i := 0 to len(lt.flat_rec.flat_types) do [
1819 pc +<= lt.flat_rec.flat_types[i];
1820 ]
1821 ] else if lt is flat_array then [
1822 pc := list(pcode_t).[ Local_Type_Flat_Array, lt.flat_array.flat_type, lt.flat_array.number_of_elements ];
1823 ] else [
1824 abort internal("invalid local type");
1825 ]
1826 return gvn_encode(pc);
1827 ]
1829 fn dlte(ctx : context) : context
1830 [
1831 var needed := fill(false, len(ctx.local_types));
1832 for vgi := 0 to len(ctx.variables) do [
1833 if ctx.variables[vgi].runtime_type >= 0 then
1834 needed[ctx.variables[vgi].runtime_type] := true;
1835 ]
1836 for bgi := 0 to len(ctx.blocks) do [
1837 if not ctx.blocks[bgi].active then
1838 continue;
1839 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
1840 var igi := ctx.blocks[bgi].instrs[ili];
1841 var ins := ctx.instrs[igi];
1842 var s := ins.lt_set;
1843 while s <> 0 do [
1844 var p : int := bsr s;
1845 s btr= p;
1846 needed[ins.params[p]] := true;
1847 ]
1848 ]
1849 ]
1851 while true do [
1852 var did_something := false;
1853 for lti := 0 to len(ctx.local_types) do [
1854 if needed[lti] then [
1855 var lt := ctx.local_types[lti];
1856 if lt is flat_rec then [
1857 if not needed[lt.flat_rec.non_flat_record] then [
1858 needed[lt.flat_rec.non_flat_record] := true;
1859 did_something := true;
1860 ]
1861 for i := 0 to len(lt.flat_rec.flat_types) do [
1862 if lt.flat_rec.flat_types[i] >= 0 then [
1863 if not needed[lt.flat_rec.flat_types[i]] then [
1864 needed[lt.flat_rec.flat_types[i]] := true;
1865 did_something := true;
1866 ]
1867 ]
1868 ]
1869 ] else if lt is flat_array then [
1870 if lt.flat_array.flat_type >= 0 then [
1871 if not needed[lt.flat_array.flat_type] then [
1872 needed[lt.flat_array.flat_type] := true;
1873 did_something := true;
1874 ]
1875 ]
1876 ]
1877 ]
1878 ]
1879 if not did_something then
1880 break;
1881 ]
1883 while true do [
1884 var use_map := infinite(-1);
1885 var new_local_types := empty(local_type);
1886 var old_new := fill(T_InvalidType, len(ctx.local_types));
1887 for lti := 0 to len(ctx.local_types) do [
1888 if not needed[lti] then
1889 continue;
1890 var m := encode_local_type(ctx.local_types[lti]);
1891 if use_map[m] = -1 then [
1892 use_map[m] := len(new_local_types);
1893 old_new[lti] := len(new_local_types);
1894 new_local_types +<= ctx.local_types[lti];
1895 ] else [
1896 old_new[lti] := use_map[m];
1897 ]
1898 ]
1900 if len(new_local_types) = len(ctx.local_types) then
1901 break;
1903 for ili := 0 to len(new_local_types) do [
1904 if new_local_types[ili] is flat_rec then [
1905 new_local_types[ili].flat_rec.non_flat_record := old_new[new_local_types[ili].flat_rec.non_flat_record];
1906 for i := 0 to len(new_local_types[ili].flat_rec.flat_types) do
1907 if new_local_types[ili].flat_rec.flat_types[i] >= 0 then
1908 new_local_types[ili].flat_rec.flat_types[i] := old_new[new_local_types[ili].flat_rec.flat_types[i]];
1909 ] else if new_local_types[ili] is flat_array then [
1910 if new_local_types[ili].flat_array.flat_type >= 0 then
1911 new_local_types[ili].flat_array.flat_type := old_new[new_local_types[ili].flat_array.flat_type];
1912 ]
1913 ]
1914 for vgi := 0 to len(ctx.variables) do [
1915 if ctx.variables[vgi].runtime_type >= 0 then
1916 ctx.variables[vgi].runtime_type := old_new[ctx.variables[vgi].runtime_type];
1917 ]
1918 for bgi := 0 to len(ctx.blocks) do [
1919 if not ctx.blocks[bgi].active then
1920 continue;
1921 for ili := 0 to len(ctx.blocks[bgi].instrs) do [
1922 var igi := ctx.blocks[bgi].instrs[ili];
1923 var ins := ctx.instrs[igi];
1924 var s := ins.lt_set;
1925 while s <> 0 do [
1926 var p : int := bsr s;
1927 s btr= p;
1928 needed[ins.params[p]] := true;
1929 ctx.instrs[igi].params[p] := old_new[ins.params[p]];
1930 ]
1931 ]
1932 ]
1934 ctx.local_types := new_local_types;
1935 needed := fill(true, len(ctx.local_types));
1936 ]
1938 return ctx;
1939 ]
1941 fn identify_loops(ctx : context) : context
1942 [
1943 var loops : node_set := 0;
1944 for bgi := 0 to len(ctx.blocks) do [
1945 if not ctx.blocks[bgi].active then
1946 continue;
1947 var block := ctx.blocks[bgi];
1948 for ili := 0 to len(block.instrs) do [
1949 var instr := ctx.instrs[block.instrs[ili]];
1950 if instr.opcode = P_Call or instr.opcode = P_Call_Indirect then [
1951 var output := set_to_mask(instr, instr.write_set);
1952 while output <> 0 do [
1953 var o : int := bsr output;
1954 output btr= o;
1955 if ctx.variables[o].color <> -1 then
1956 goto skip;
1957 ]
1958 ]
1959 ]
1960 loops bts= bgi;
1961 skip:
1962 ]
1964 while true do [
1965 var did_something := false;
1967 var loops2 := loops;
1968 while loops2 <> 0 do [
1969 var bgi : int := bsr loops2;
1970 loops2 btr= bgi;
1971 var block := ctx.blocks[bgi];
1972 for i := 0 to len(block.pred_list) do [
1973 if loops bt block.pred_list[i] then
1974 goto in_loop;
1975 ]
1976 loops btr= bgi;
1977 did_something := true;
1978 continue;
1979 in_loop:
1980 for i := 0 to len(block.post_list) do [
1981 if loops bt block.post_list[i] then
1982 goto in_loop2;
1983 ]
1984 loops btr= bgi;
1985 did_something := true;
1986 continue;
1987 in_loop2:
1988 ]
1989 if not did_something then
1990 break;
1991 ]
1993 while loops <> 0 do [
1994 var bgi : int := bsr loops;
1995 loops btr= bgi;
1996 var block := ctx.blocks[bgi];
1997 for ili := 0 to len(block.instrs) do [
1998 var instr := ctx.instrs[block.instrs[ili]];
1999 var read_mask := set_to_mask(instr, instr.read_set);
2000 while read_mask <> 0 do [
2001 var vgi : int := bsr read_mask;
2002 read_mask btr= vgi;
2003 var rt := ctx.variables[vgi].runtime_type;
2004 if rt = T_AlwaysFlatOption then [
2005 ctx.variables[vgi].must_be_flat := true;
2006 ctx.variables[vgi].ra_priority += 1;
2007 ]
2008 if rt < 0, rt > T_FlatOption then [
2009 ctx.variables[vgi].must_be_flat := true;
2010 ctx.variables[vgi].ra_priority += 1;
2011 ]
2012 if rt = T_Undetermined then [
2013 ctx.variables[vgi].must_be_data := true;
2014 ctx.variables[vgi].ra_priority += 1;
2015 ]
2016 if rt >= 0, ctx.local_types[rt] is rec then [
2017 ctx.variables[vgi].must_be_data := true;
2018 ctx.variables[vgi].ra_priority += 1;
2019 ]
2020 ]
2021 ]
2022 ]
2023 {for vgi := 0 to len(ctx.variables) do [
2024 var rt := ctx.variables[vgi].runtime_type;
2025 if rt = T_AlwaysFlatOption then
2026 ctx.variables[vgi].must_be_flat := true;
2027 if rt < 0, rt > T_FlatOption then
2028 ctx.variables[vgi].must_be_flat := true;
2029 if rt = T_Undetermined then
2030 ctx.variables[vgi].must_be_data := true;
2031 if rt >= 0, ctx.local_types[rt] is rec then
2032 ctx.variables[vgi].must_be_data := true;
2033 ]}
2035 return ctx;
2036 ]
2038 fn liveness(ctx : context) : context
2039 [
2040 var worklist : node_set := 0;
2041 for bgi := 0 to len(ctx.blocks) do [
2042 if not ctx.blocks[bgi].active then
2043 continue;
2044 ctx.blocks[bgi].live_top := 0;
2045 ctx.blocks[bgi].live_bottom := 0;
2046 worklist bts= bgi;
2047 ]
2049 while worklist <> 0 do [
2050 var bgi : int := bsr worklist;
2051 worklist btr= bgi;
2053 var live : var_set := ctx.blocks[bgi].live_bottom;
2055 var block := ctx.blocks[bgi];
2056 var ili := len(block.instrs) - 1;
2057 while ili >= 0 do [
2058 var instr := ctx.instrs[block.instrs[ili]];
2060 if instr.opcode = P_Jmp_False, not live bt instr.params[0] then [
2061 live bts= instr.params[0];
2062 ctx.blocks[bgi].live_bottom := live;
2063 ]
2065 var read_mask := set_to_mask(instr, instr.read_set);
2066 var write_mask := set_to_mask(instr, instr.write_set);
2068 live and= not write_mask;
2069 live or= read_mask;
2071 ili -= 1;
2072 ]
2073 ctx.blocks[bgi].live_top := live;
2074 block := ctx.blocks[bgi];
2076 for i := 0 to len(block.pred_list) do [
2077 var prev_bgi := block.pred_list[i];
2078 var prev_block := ctx.blocks[prev_bgi];
2079 if (live and not prev_block.live_bottom) <> 0 then [
2080 ctx.blocks[prev_bgi].live_bottom or= live;
2081 worklist bts= prev_bgi;
2082 ]
2083 ]
2084 ]
2086 return ctx;
2087 ]
2089 fn update_conflict_map(cm : conflict_map, live : var_set) : conflict_map
2090 [
2091 var f := live;
2092 while f <> 0 do [
2093 var vgi : int := bsr f;
2094 f btr= vgi;
2095 cm[vgi] or= live;
2096 ]
2097 return cm;
2098 ]
2100 fn update_rw_conflict_map(cm : conflict_map, conflict_1 conflict_2 : var_set) : conflict_map
2101 [
2102 var conflict_1_c := conflict_1;
2103 while conflict_1_c <> 0 do [
2104 var c1 : int := bsr conflict_1_c;
2105 conflict_1_c btr= c1;
2106 cm[c1] or= conflict_2;
2107 ]
2109 var conflict_2_c := conflict_2;
2110 while conflict_2_c <> 0 do [
2111 var c2 : int := bsr conflict_2_c;
2112 conflict_2_c btr= c2;
2113 cm[c2] or= conflict_1;
2115 ]
2117 return cm;
2118 ]
2120 fn undo_borrow(ctx : context, to_free : int, prev_live : var_set) : context
2121 [
2122 var v := ctx.variables[to_free];
2123 if v.defining_instr < 0 then
2124 return ctx;
2125 var ins := ctx.instrs[v.defining_instr];
2126 if ins.borrow >= 0, (ins.params[ins.borrow - 1] and Flag_Borrow) <> 0 then [
2127 var v_borrow := ins.params[ins.borrow];
2128 again:
2129 var v_v := ctx.variables[v_borrow];
2130 var v_def := v_v.defining_instr;
2131 if v_def >= 0 then [
2132 var v_ins := ctx.instrs[v_def];
2133 if v_ins.borrow >= 0 then [
2134 v_borrow := v_ins.params[v_ins.borrow];
2135 goto again;
2136 ]
2137 ]
2139 if not prev_live bt v_borrow then [
2140 ins.params[ins.borrow - 1] and= not Flag_Borrow;
2141 ctx.instrs[v.defining_instr] := ins;
2142 ]
2143 ]
2144 return ctx;
2145 ]
2148 fn insert_free(ctx : context) : context
2149 [
2150 var cm : conflict_map := fill(var_set, 0, len(ctx.variables));
2151 //eval debug("1: insert_free: " + ctx.name + ", " + ntos(len(ctx.variables)));
2152 for i := 0 to len(ctx.variables) do
2153 cm[i] bts= i;
2155 for bgi := 0 to len(ctx.blocks) do [
2156 if not ctx.blocks[bgi].active then
2157 continue;
2159 var live : var_set := ctx.blocks[bgi].live_bottom;
2160 cm := update_conflict_map(cm, live);
2162 var block := ctx.blocks[bgi];
2164 var needs_checkpoint := false;
2165 var fused_variable := -1;
2166 for post_idx := 0 to len(block.post_list) do [
2167 var post := block.post_list[post_idx];
2168 if post < bgi then [
2169 needs_checkpoint := true;
2170 break;
2171 ]
2172 ]
2174 var ili := len(block.instrs) - 1;
2176 if ili >= 1 then [
2177 var instr1 := ctx.instrs[block.instrs[ili - 1]];
2178 var instr2 := ctx.instrs[block.instrs[ili]];
2179 if instr2.opcode = P_Jmp_False then [
2180 var bvar := instr2.params[0];
2181 var post0 := block.post_list[0];
2182 var post1 := block.post_list[1];
2183 if not ctx.blocks[post0].live_top bt bvar,
2184 not ctx.blocks[post1].live_top bt bvar then [
2185 if instr1.opcode = P_BinaryOp, instr1.params[1] = bvar then [
2186 ctx.instrs[block.instrs[ili - 1]].params[2] or= Flag_Fused_Bin_Jmp;
2187 fused_variable := bvar;
2188 ]
2189 if instr1.opcode = P_BinaryConstOp, instr1.params[1] = bvar then [
2190 ctx.instrs[block.instrs[ili - 1]].params[2] or= Flag_Fused_Bin_Jmp;
2191 fused_variable := bvar;
2192 ]
2193 if instr1.opcode = P_Array_Len_Greater_Than, instr1.params[0] = bvar then [
2194 ctx.instrs[block.instrs[ili - 1]].params[3] or= Flag_Fused_Bin_Jmp;
2195 fused_variable := bvar;
2196 ]
2197 ]
2198 ]
2199 ]
2201 while ili >= 0 do [
2202 var instr := ctx.instrs[block.instrs[ili]];
2204 var read_mask := set_to_mask(instr, instr.read_set);
2205 var write_mask := set_to_mask(instr, instr.write_set);
2207 var prev_live := live;
2209 live and= not write_mask;
2210 live or= read_mask;
2212 cm := update_conflict_map(cm, live);
2214 var conflict_1 := set_to_mask(instr, instr.conflict_1);
2215 var conflict_2 := set_to_mask(instr, instr.conflict_2);
2216 cm := update_rw_conflict_map(cm, conflict_1, conflict_2);
2218 var set_to_free := (read_mask or write_mask) and not prev_live;
2220 while set_to_free <> 0 do [
2221 var to_free : int := bsr set_to_free;
2222 set_to_free btr= to_free;
2223 ctx := undo_borrow(ctx, to_free, prev_live);
2224 ]
2226 set_to_free := write_mask and not prev_live;
2227 var freed := set_to_free;
2228 while set_to_free <> 0 do [
2229 var to_free : int := bsr set_to_free;
2230 set_to_free btr= to_free;
2232 var free_instr := create_instr(P_Free, list(pcode_t).[ to_free ], bgi);
2233 ctx := insert_instr(ctx, free_instr, ili + 1);
2234 //eval debug("2: inserting free at " + ntos(bgi) + ":" + ntos(ili + 1) + " -> " + ntos(to_free));
2235 ]
2237 set_to_free := read_mask and not prev_live;
2238 while set_to_free <> 0 do [
2239 var to_free : int := bsr set_to_free;
2240 set_to_free btr= to_free;
2242 var free_set : param_set := instr.free_set;
2243 while free_set <> 0 do [
2244 var param : int := bsr free_set;
2245 free_set btr= param;
2246 var v := instr.params[param];
2247 if v = to_free then [
2248 //eval debug("3: setting Flag_Free_Argument at " + ntos(bgi) + ": " + pcode_name(instr.opcode) + " param " + ntos(param) + " n " + ntos(instr.params[param-1]));
2249 if (ctx.instrs[block.instrs[ili]].params[param - 1] and Flag_Free_Argument) <> 0 then
2250 abort internal("Flag_Free_Argument is already set");
2251 ctx.instrs[block.instrs[ili]].params[param - 1] or= Flag_Free_Argument;
2252 goto skip_free_instr;
2253 ]
2254 ]
2256 if not ((write_mask and not prev_live) bt to_free) then [
2257 var free_instr := create_instr(P_Free, list(pcode_t).[ to_free ], bgi);
2258 ctx := insert_instr(ctx, free_instr, ili + 1);
2259 freed bts= to_free;
2260 ]
2261 //eval debug("inserting free at " + ntos(bgi) + ":" + ntos(ili + 1) + " -> " + ntos(to_free));
2262 skip_free_instr:
2263 ]
2264 if freed <> 0 then
2265 cm := update_conflict_map(cm, prev_live or freed);
2267 if instr.opcode = P_Call or instr.opcode = P_Call_Indirect then [
2268 var output := write_mask;
2269 while output <> 0 do [
2270 var o : int := bsr output;
2271 output btr= o;
2272 if ctx.variables[o].color <> -1 then
2273 goto not_elided;
2274 ]
2275 goto skip_call;
2276 not_elided:
2277 var p_live := prev_live or write_mask;
2278 var new_live : var_set := 0;
2279 while p_live <> 0 do [
2280 var l : int := bsr p_live;
2281 p_live btr= l;
2282 if ctx.variables[l].must_be_flat or ctx.variables[l].must_be_data then
2283 new_live bts= l;
2284 ]
2285 var cp_instr := create_instr(P_Checkpoint, var_set_2_list(new_live), bgi);
2286 ctx := insert_instr(ctx, cp_instr, ili + 1);
2287 needs_checkpoint := false;
2288 skip_call:
2289 ]
2291 ili -= 1;
2292 ]
2294 for post_bli := 0 to len(block.post_list) do [
2295 var post_bgi := block.post_list[post_bli];
2296 //eval debug("testing cleanup: " + ntos(bgi) + " -> " + ntos(post_bli) + " -> " + ntos(post_bgi));
2297 var post_block := ctx.blocks[post_bgi];
2298 if post_block.live_top <> block.live_bottom then [
2299 if (not block.live_bottom and post_block.live_top) <> 0 then
2300 abort internal("the successor has more live variables than the predecessor");
2302 var must_free_set : var_set := block.live_bottom and not post_block.live_top;
2303 //cm := update_conflict_map(cm, post_block.live_top or must_free_set);
2304 while must_free_set <> 0 do [
2305 var to_free : int := bsr must_free_set;
2306 must_free_set btr= to_free;
2308 ctx := undo_borrow(ctx, to_free, post_block.live_top);
2310 if post_bli <= 1, to_free = fused_variable then
2311 continue;
2313 //eval debug("4: inserting free at " + ntos(bgi) + ":" + ntos(post_bgi) + " -> " + ntos(to_free));
2314 var free_instr := create_instr(P_Free, list(pcode_t).[ to_free ], post_bgi);
2315 ctx := insert_instr(ctx, free_instr, 0);
2316 ]
2317 ]
2318 ]
2320 if needs_checkpoint, len(ctx.blocks[bgi].instrs) > 0 then [
2321 var live_bottom := ctx.blocks[bgi].live_bottom;
2323 var ili := len(ctx.blocks[bgi].instrs);
2324 if ili > 0 then [
2325 var instr := ctx.instrs[ctx.blocks[bgi].instrs[ili - 1]];
2326 if instr.opcode = P_Jmp_False or instr.opcode = P_Return then
2327 ili -= 1;
2328 if fused_variable >= 0 then [
2329 skip_derefs:
2330 ili -= 1;
2331 var instr := ctx.instrs[ctx.blocks[bgi].instrs[ili]];
2332 if instr.opcode = P_Free then [
2333 goto skip_derefs;
2334 ]
2335 if instr.opcode = P_BinaryOp, (instr.params[2] and Flag_Fused_Bin_Jmp) <> 0 then [
2336 live_bottom bts= instr.params[3];
2337 live_bottom bts= instr.params[5];
2338 goto have_ili;
2339 ]
2340 if instr.opcode = P_BinaryConstOp, (instr.params[2] and Flag_Fused_Bin_Jmp) <> 0 then [
2341 live_bottom bts= instr.params[3];
2342 goto have_ili;
2343 ]
2344 if instr.opcode = P_Array_Len_Greater_Than, (instr.params[3] and Flag_Fused_Bin_Jmp) <> 0 then [
2345 live_bottom bts= instr.params[1];
2346 live_bottom bts= instr.params[2];
2347 goto have_ili;
2348 ]
2349 abort internal("insert_free: invalid opcode " + ntos(instr.opcode));
2350 have_ili:
2351 ]
2352 ]
2354 var new_live_bottom : var_set := 0;
2355 while live_bottom <> 0 do [
2356 var l : int := bsr live_bottom;
2357 live_bottom btr= l;
2358 if ctx.variables[l].must_be_flat or ctx.variables[l].must_be_data then
2359 new_live_bottom bts= l;
2360 ]
2361 var cp_instr := create_instr(P_Checkpoint, var_set_2_list(new_live_bottom), bgi);
2362 ctx := insert_instr(ctx, cp_instr, ili);
2363 ]
2364 ]
2366 ctx.cm := cm;
2368 return ctx;
2369 ]
2371 fn compare_type_index~inline(ctx : context, v1 v2 : int) : int := ctx.variables[v1].type_index - ctx.variables[v2].type_index;
2372 fn type_index_equal(ctx : context, v1 v2 : int) : bool := compare_type_index(ctx, v1, v2) = 0;
2373 fn type_index_less(ctx : context, v1 v2 : int) : bool := compare_type_index(ctx, v1, v2) < 0;
2374 fn instance_ord_type_index(ctx : context) : class_ord(int) :=
2375 class_ord(int).[
2376 equal : type_index_equal(ctx,,),
2377 less : type_index_less(ctx,,),
2378 ];
2380 fn allocate_variables(ctx : context) : context
2381 [
2382 var type_to_var_set : list(var_set) := fill(var_set, 0, (len(ctx.local_types) - T_Undetermined) * 4);
2383 for vgi := 0 to len(ctx.variables) do [
2384 var v := ctx.variables[vgi];
2385 if v.color = -1 then
2386 continue;
2387 if v.runtime_type < T_Undetermined then
2388 abort internal("allocate_variables: invalid runtime_type: " + ctx.name + ", " + ntos(vgi) + "(" + v.name + "): " + ntos(v.runtime_type));
2389 type_to_var_set[(v.runtime_type - T_Undetermined) * 4 + select(v.must_be_flat, 0, 1) + select(v.must_be_data, 0, 2)] bts= vgi;
2390 if not ctx.cm[vgi] bt vgi then
2391 abort internal("self-bit not set for variable " + ntos(vgi));
2392 ctx.variables[vgi].color := -1;
2393 ]
2394 var color := 0;
2395 var ra_color := empty(tuple2(int, int));
2396 for t := 0 to len(type_to_var_set) do [
2397 var vs := type_to_var_set[t];
2398 var vsl := vs;
2399 while vsl <> 0 do [
2400 var vgi : int := bsf vsl;
2401 vsl btr= vgi;
2402 ctx.variables[vgi].color := color;
2403 ra_color +<= mktuple2(-ctx.variables[vgi].ra_priority, color);
2404 var remaining := not ctx.cm[vgi] and vs;
2405 while remaining <> 0 do [
2406 var vgi2 := bsf remaining;
2407 vsl btr= vgi2;
2408 remaining btr= vgi2;
2409 var old_color := ctx.variables[vgi2].color;
2410 if old_color <> -1 then
2411 continue;
2412 remaining and= not ctx.cm[vgi2];
2413 ctx.variables[vgi2].color := color;
2414 ra_color[color].v1 -= ctx.variables[vgi2].ra_priority;
2415 ]
2416 color += 1;
2417 ]
2418 ]
2419 ra_color := list_sort(ra_color);
2420 var cmap := fill(-1, color);
2421 for i := 0 to len(ra_color) do [
2422 cmap[ra_color[i].v2] := i;
2423 //eval debug("ra_color: " + ntos(i) + ", " + ntos(ra_color[i].v1) + ", " + ntos(ra_color[i].v2));
2424 ]
2426 var vars_for_color := fill(empty(int), color);
2427 for vgi := 0 to len(ctx.variables) do [
2428 var v := ctx.variables[vgi];
2429 if v.color = -1 then
2430 continue;
2431 //eval debug(ctx.name + ": " + ntos(v.color) + " -> " + ntos(cmap[v.color]));
2432 v.color := cmap[v.color];
2433 vars_for_color[v.color] +<= vgi;
2434 ]
2435 var new_idx := -1;
2436 var old_new := fill(-1, len(ctx.variables));
2437 for c := 0 to color do [
2438 var l := vars_for_color[c];
2439 l := list_sort(instance_ord_type_index(ctx), l);
2440 //if ctx.name = "tokenize_recursive" then for i := 0 to len(l) do eval debug("color " + ntos(c) + ": " + ntos(ctx.variables[l[i]].type_index));
2441 var last := T_InvalidType;
2442 for i := 0 to len(l) do [
2443 var v := ctx.variables[l[i]];
2444 if v.type_index <> last then [
2445 last := v.type_index;
2446 new_idx += 1;
2447 ]
2448 old_new[l[i]] := new_idx;
2449 ]
2450 ]
2451 for vgi := 0 to len(ctx.variables) do [
2452 if old_new[vgi] = -1 then [
2453 new_idx += 1;
2454 old_new[vgi] := new_idx;
2455 ]
2456 ]
2457 new_idx += 1;
2459 //if ctx.name = "tokenize_recursive" then eval debug("alloc: " + ntos(len(ctx.variables)) + " -> " + ntos(non_elided) + " -> " + ntos(new_idx) + " -> " + ntos(color) + " (" + ctx.name + ")");
2461 var new_variables := fill(uninitialized(variable), new_idx);
2462 for vgi := 0 to len(ctx.variables) do [
2463 var new := old_new[vgi];
2464 if is_uninitialized(new_variables[new]) then [
2465 new_variables[new] := ctx.variables[vgi];
2466 if new_variables[new].type_index >= 0 then
2467 new_variables[new].type_index := old_new[new_variables[new].type_index];
2468 new_variables[new].name := "";
2469 ]
2470 ]
2471 ctx.variables := new_variables;
2473 ctx := remap_variables(ctx, old_new);
2475 return ctx;
2476 ]
2478 fn remove_redundant_frees(ctx : context) : context
2479 [
2480 for bgi := 0 to len(ctx.blocks) do [
2481 if not ctx.blocks[bgi].active then
2482 continue;
2483 var freed_vars : var_set := 0;
2484 var i := 0;
2485 while i < len(ctx.blocks[bgi].instrs), ctx.instrs[ctx.blocks[bgi].instrs[i]].opcode = P_Free do [
2486 var v := ctx.instrs[ctx.blocks[bgi].instrs[i]].params[0];
2487 if freed_vars bt v then [
2488 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[ .. i] + ctx.blocks[bgi].instrs[i + 1 .. ];
2489 continue;
2490 ]
2491 freed_vars bts= v;
2492 i += 1;
2493 ]
2494 while i < len(ctx.blocks[bgi].instrs), ctx.instrs[ctx.blocks[bgi].instrs[i]].opcode = P_Copy do [
2495 var v1 := ctx.instrs[ctx.blocks[bgi].instrs[i]].params[0];
2496 var v2 := ctx.instrs[ctx.blocks[bgi].instrs[i]].params[2];
2497 if v1 = v2 then [
2498 ctx.blocks[bgi].instrs := ctx.blocks[bgi].instrs[ .. i] + ctx.blocks[bgi].instrs[i + 1 .. ];
2499 continue;
2500 ]
2501 i += 1;
2502 ]
2503 ]
2504 for bgi := 0 to len(ctx.blocks) do [
2505 if not ctx.blocks[bgi].active then
2506 continue;
2507 var i := len(ctx.blocks[bgi].instrs);
2508 if i > 0 then [
2509 var instr := ctx.instrs[ctx.blocks[bgi].instrs[i - 1]];
2510 if instr.opcode = P_Jmp_False then [
2511 var false_bgi := ctx.blocks[bgi].post_list[1];
2512 var false_block := ctx.blocks[false_bgi];
2513 if len(false_block.instrs) = 0, len(false_block.post_list) = 1, len(false_block.pred_list) = 1 then [
2514 var next_bgi := false_block.post_list[0];
2515 //eval debug("folding nodes " + ntos(bgi) + ", " + ntos(false_bgi) + ", " + ntos(next_bgi));
2516 ctx.blocks[bgi].post_list[1] := next_bgi;
2517 for j := 0 to len(ctx.blocks[next_bgi].pred_list) do [
2518 if ctx.blocks[next_bgi].pred_list[j] = false_bgi then [
2519 ctx.blocks[next_bgi].pred_list[j] := bgi;
2520 ctx.blocks[next_bgi].pred_position[j] := 1;
2521 ]
2522 ]
2523 ctx.blocks[false_bgi].pred_list := empty(int);
2524 ctx.blocks[false_bgi].pred_position := empty(int);
2525 ctx.blocks[false_bgi].post_list := empty(int);
2526 ctx := deactivate_node(ctx, false_bgi);
2527 ]
2528 ]
2529 ]
2530 ]
2532 return ctx;
2533 ]
2535 fn check_consistency(ctx : context, msg : bytes, test_no_pred : bool) : context
2536 [
2537 if not check then
2538 return ctx;
2539 //eval debug("check_consistency: " + msg);
2540 for i := 0 to len(ctx.blocks) do [
2541 var block := ctx.blocks[i];
2542 if not block.active then
2543 continue;
2544 var len_pred := len(block.pred_list);
2545 if len_pred <> len(block.pred_position) then
2546 abort internal(msg + ": the length of pred_list and pred_position differ");
2547 if test_no_pred and (len_pred = 0) <> (i = 0) then
2548 abort internal(msg + ": unexpected block with no predecessors");
2549 for j := 0 to len_pred do [
2550 var pred_bgi := block.pred_list[j];
2551 var pred_pos := block.pred_position[j];
2552 var pred_block := ctx.blocks[pred_bgi];
2553 if pred_block.post_list[pred_pos] <> i then
2554 abort internal(msg + ": pred_set - post_set mismatch (" + ntos(pred_bgi) + ", " + ntos(i) + ")");
2555 ]
2556 for j := 0 to len(block.post_list) do [
2557 var post_bgi := block.post_list[j];
2558 var post_block := ctx.blocks[post_bgi];
2559 var match := 0;
2560 for k := 0 to len(post_block.pred_list) do [
2561 if post_block.pred_list[k] = i and post_block.pred_position[k] = j then
2562 match += 1;
2563 ]
2564 if match <> 1 then
2565 abort internal(msg + ": post_set - pred_set mismatch (" + ntos(post_bgi) + ", " + ntos(i) + ", " + ntos(match) + ")");
2566 ]
2567 if len(block.pred_list) <> len(block.pred_position) then
2568 abort internal(msg + ": pred_list and pred_position mismatch: " + ntos(len(block.pred_list)) + " <> " + ntos(len(block.pred_position)));
2569 for pred_i := 0 to len(block.pred_list) do [
2570 var p := block.pred_list[pred_i];
2571 var q := block.pred_position[pred_i];
2572 var p_block := ctx.blocks[p];
2573 if q >= len(p_block.post_list) then
2574 abort internal(msg + ": block(" + ntos(i) + ").pred_position is too high: " + ntos(q) + " >= " + ntos(len(p_block.post_list)));
2575 if p_block.post_list[q] <> i then
2576 abort internal(msg + ": pred_position doesn't match (" + ntos(pred_i) + ", " + ntos(p) + ", " + ntos(q) + "): " + ntos(p_block.post_list[q]) + " <> " + ntos(i));
2577 ]
2578 for j := 0 to len(block.instrs) do [
2579 var ins := ctx.instrs[block.instrs[j]];
2580 if ins.bb <> i then
2581 abort internal(msg + ": basic block doesn't match");
2582 ]
2583 ]
2585 return ctx;
2586 ]
2588 fn process_pcode(pc : list(pcode_t), get_inline : fn(function, bool) : list(pcode_t), verify : bool) : list(pcode_t)
2589 [
2590 {[
2591 var src_type : pcode_t := T_FlatOption;
2592 var dst_type : pcode_t := T_FlatOption;
2593 var op : pcode_t := Bin_And;
2594 var src := list(pcode_t).[ 1, 0 ];
2595 var dst := list(pcode_t).[ 1, 1 ];
2596 eval debug("start evaluate");
2597 var res := evaluate(src_type, dst_type, op, src, dst);
2598 eval debug("end evaluate");
2599 var str := "result:";
2600 for i := 0 to len(res) do [
2601 str += " " + ntos_base(res[i], 16);
2602 ]
2603 eval debug(str);
2604 ]}
2606 //eval debug("process_pcode");
2608 var ft := pc[0] and Fn_Mask;
2609 if ft <> Fn_Function then [
2610 if ft <> Fn_Record and ft <> Fn_Option then
2611 abort internal("unsupported function type " + ntos(pc[0]));
2612 { no need to optimize it, it won't be executed }
2613 return pc;
2614 ]
2616 var ctx := load_function_context(pc);
2617 //eval debug("optimizing: " + ctx.name);
2619 var print_passes := false;
2621 {
2622 if ctx.name[0] = 'Q' then [
2623 eval debug("start waiting on " + ctx.name);
2624 for i := 0 to 1000000000 do [
2625 ]
2626 eval debug("end waiting on " + ctx.name);
2627 ]
2628 }
2630 ctx := check_consistency(ctx, "start", false);
2632 var num_retries := 0;
2633 var do_verify := false;
2634 retry_optimize:
2635 ctx.should_retry := false;
2636 ctx := check_consistency(ctx, "retry_optimize", false);
2638 if print_passes then [ eval ctx; eval debug("prune_unreachable"); if is_exception ctx then eval debug("ctx exception"); ]
2639 ctx := prune_unreachable(ctx);
2640 ctx := check_consistency(ctx, "prune_unreachable", true);
2642 if print_passes then [ eval ctx; eval debug("join_adjacent"); if is_exception ctx then eval debug("ctx exception"); ]
2643 ctx := join_adjacent(ctx);
2644 ctx := check_consistency(ctx, "join_adjacent", true);
2646 if print_passes then [ eval ctx; eval debug("propagate_types"); if is_exception ctx then eval debug("ctx exception"); ]
2647 ctx := propagate_types(ctx);
2648 ctx := check_consistency(ctx, "propagate_types", true);
2650 if print_passes then [ eval ctx; eval debug("test_uninitialized"); if is_exception ctx then eval debug("ctx exception"); ]
2651 ctx := test_uninitialized(ctx);
2652 ctx := check_consistency(ctx, "test_uninitialized", true);
2654 if print_passes then [ eval ctx; eval debug("find_dominators"); if is_exception ctx then eval debug("ctx exception"); ]
2655 ctx := find_dominators(ctx);
2656 ctx := check_consistency(ctx, "find_dominators", true);
2658 if print_passes then [ eval ctx; eval debug("find_dominance_frontiers"); if is_exception ctx then eval debug("ctx exception"); ]
2659 ctx := find_dominance_frontiers(ctx);
2660 ctx := check_consistency(ctx, "find_dominance_frontiers", true);
2662 if print_passes then [ eval ctx; eval debug("process_variables"); if is_exception ctx then eval debug("ctx exception"); ]
2663 ctx := process_variables(ctx);
2664 ctx := check_consistency(ctx, "process_variables", true);
2666 if print_passes then [ eval ctx; eval debug("find_phi_blocks"); if is_exception ctx then eval debug("ctx exception"); ]
2667 ctx := find_phi_blocks(ctx);
2668 ctx := check_consistency(ctx, "find_phi_blocks", true);
2670 if print_passes then [ eval ctx; eval debug("rename_variables"); if is_exception ctx then eval debug("ctx exception"); ]
2671 ctx := rename_variables(ctx);
2672 ctx := check_consistency(ctx, "rename_variables", true);
2674 if print_passes then [ eval ctx; eval debug("verify_ssa"); if is_exception ctx then eval debug("ctx exception"); ]
2675 ctx := verify_ssa(ctx);
2676 ctx := check_consistency(ctx, "verify_ssa", true);
2678 if print_passes then [ eval ctx; eval debug("gvn"); if is_exception ctx then eval debug("ctx exception"); ]
2679 ctx := gvn(ctx);
2680 ctx := check_consistency(ctx, "gvn", true);
2682 if print_passes then [ eval ctx; eval debug("misc_opt"); if is_exception ctx then eval debug("ctx exception"); ]
2683 ctx := misc_opt(ctx);
2684 ctx := check_consistency(ctx, "misc_opt", false);
2686 if print_passes then [ eval ctx; eval debug("prune_unreachable"); if is_exception ctx then eval debug("ctx exception"); ]
2687 ctx := prune_unreachable(ctx);
2688 ctx := check_consistency(ctx, "prune_unreachable", true);
2690 if print_passes then [ eval ctx; eval debug("dce"); if is_exception ctx then eval debug("ctx exception"); ]
2691 ctx := dce(ctx);
2692 ctx := check_consistency(ctx, "dce", true);
2694 if print_passes then [ eval ctx; eval debug("dce2"); if is_exception ctx then eval debug("ctx exception"); ]
2695 ctx := dce2(ctx);
2696 ctx := check_consistency(ctx, "dce2", true);
2698 if print_passes then [ eval ctx; eval debug("create_lt"); if is_exception ctx then eval debug("ctx exception"); ]
2699 ctx := create_lt(ctx);
2700 ctx := check_consistency(ctx, "create_lt", true);
2702 if do_verify then [
2703 if print_passes then [ eval ctx; eval debug("verify_function"); if is_exception ctx then eval debug("ctx exception"); ]
2704 xeval verify_function(ctx);
2705 ]
2707 if print_passes then [ eval ctx; eval debug("remove_phis"); if is_exception ctx then eval debug("ctx exception"); ]
2708 ctx := remove_phis(ctx);
2709 ctx := check_consistency(ctx, "remove_phis", true);
2711 if print_passes then [ eval ctx; eval debug("inline_functions"); if is_exception ctx then eval debug("ctx exception"); ]
2712 ctx := inline_functions(ctx, get_inline);
2713 ctx := check_consistency(ctx, "inline_functions", false);
2715 if print_passes then [ eval ctx; eval debug("dve"); if is_exception ctx then eval debug("ctx exception"); ]
2716 ctx := dve(ctx);
2717 ctx := check_consistency(ctx, "dve", true);
2719 if ctx.should_retry then [
2720 //eval debug("retrying optimize");
2721 num_retries += 1;
2722 goto retry_optimize;
2723 ]
2725 if verify and not do_verify then [
2726 do_verify := true;
2727 num_retries += 1;
2728 goto retry_optimize;
2729 ]
2731 //eval debug("retries: " + ntos(num_retries));
2733 if print_passes then [ eval ctx; eval debug("join_adjacent"); if is_exception ctx then eval debug("ctx exception"); ]
2734 ctx := join_adjacent(ctx);
2735 ctx := check_consistency(ctx, "join_adjacent", true);
2737 if print_passes then [ eval ctx; eval debug("dlte"); if is_exception ctx then eval debug("ctx exception"); ]
2738 ctx := dlte(ctx);
2739 ctx := check_consistency(ctx, "dlte", true);
2741 if print_passes then [ eval ctx; eval debug("identify_loops"); if is_exception ctx then eval debug("ctx exception"); ]
2742 ctx := identify_loops(ctx);
2743 ctx := check_consistency(ctx, "liveness", true);
2745 if print_passes then [ eval ctx; eval debug("liveness"); if is_exception ctx then eval debug("ctx exception"); ]
2746 ctx := liveness(ctx);
2747 ctx := check_consistency(ctx, "liveness", true);
2749 if print_passes then [ eval ctx; eval debug("insert_free"); if is_exception ctx then eval debug("ctx exception"); ]
2750 ctx := insert_free(ctx);
2751 ctx := check_consistency(ctx, "inset_free", true);
2753 if print_passes then [ eval ctx; eval debug("allocate_variables"); if is_exception ctx then eval debug("ctx exception"); ]
2754 ctx := allocate_variables(ctx);
2755 ctx := check_consistency(ctx, "allocate_variables", true);
2757 if print_passes then [ eval ctx; eval debug("remove_redundant_frees"); if is_exception ctx then eval debug("ctx exception"); ]
2758 ctx := remove_redundant_frees(ctx);
2759 ctx := check_consistency(ctx, "remove_redundant_frees", true);
2761 if print_passes then [ eval ctx; eval debug("check_consistency"); if is_exception ctx then eval debug("ctx exception"); ]
2762 ctx := check_consistency(ctx, "end", true);
2764 var n_blocks := len(ctx.blocks);
2766 while not ctx.blocks[n_blocks - 1].active do
2767 n_blocks -= 1;
2769 var rpc := list(pcode_t).[
2770 Fn_Function or select(n_blocks > 1, Fn_AutoInline, 0),
2771 pc[1],
2772 0,
2773 len(ctx.local_types),
2774 len(ctx.variables),
2775 pc[5],
2776 pc[6],
2777 pc[7],
2778 n_blocks - 1
2779 ];
2780 rpc += blob_store(ctx.name);
2781 for i := 0 to len(ctx.local_types) do [
2782 if ctx.local_types[i] is rec then [
2783 rpc +<= Local_Type_Record;
2784 rpc += function_store(ctx.local_types[i].rec);
2785 ] else if ctx.local_types[i] is flat_rec then [
2786 rpc +<= Local_Type_Flat_Record;
2787 rpc +<= ctx.local_types[i].flat_rec.non_flat_record;
2788 rpc +<= len(ctx.local_types[i].flat_rec.flat_types);
2789 for t := 0 to len(ctx.local_types[i].flat_rec.flat_types) do [
2790 rpc +<= ctx.local_types[i].flat_rec.flat_types[t];
2791 ]
2792 ] else if ctx.local_types[i] is flat_array then [
2793 rpc +<= Local_Type_Flat_Array;
2794 rpc +<= ctx.local_types[i].flat_array.flat_type;
2795 rpc +<= ctx.local_types[i].flat_array.number_of_elements;
2796 ] else [
2797 abort internal("unknown local type");
2798 ]
2799 ]
2800 for i := 0 to len(ctx.variables) do [
2801 var v := ctx.variables[i];
2802 rpc +<= v.type_index;
2803 rpc +<= v.runtime_type;
2804 rpc +<= v.color;
2805 rpc +<= select(v.must_be_flat, 0, VarFlag_Must_Be_Flat) or select(v.must_be_data, 0, VarFlag_Must_Be_Data);
2806 rpc += blob_store(v.name);
2807 ]
2809 //eval stop("ssa");
2811 rpc += dump_basic_blocks(ctx, false);
2813 if is_exception ctx then [
2814 pc := exception_copy(list(pcode_t), ctx);
2815 ] else if is_exception ctx.instrs then [
2816 pc := exception_copy(list(pcode_t), ctx.instrs);
2817 ] else if is_exception ctx.blocks then [
2818 pc := exception_copy(list(pcode_t), ctx.blocks);
2819 ] else if is_exception ctx.variables then [
2820 pc := exception_copy(list(pcode_t), ctx.variables);
2821 ] else if is_exception rpc then [
2822 pc := exception_copy(list(pcode_t), rpc);
2823 ]
2825 //eval debug("optimized: " + ctx.name);
2827 return rpc;
2828 return pc;
2829 ]