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