?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
tagged release 0.7.1
[parrot.git] / compilers / imcc / optimizer.c
blobf5b21e8ca2d164b2737424c6beb54399c7d61cb0
1 /*
2 * $Id$
3 * Copyright (C) 2002-2008, The Perl Foundation.
4 */
5
6 /*
7
8 =head1 NAME
9
10 compilers/imcc/optimizer.c
11
12 =head1 DESCRIPTION
13
14 Optimization occurs in three stages:
15 1) pre_optimizer -- runs before control flow graph (CFG) is built
16 2) optimizer -- runs after CFG is built, but before register allocation
17 3) post_optimizer -- runs after register allocation
18
19 pre_optimizer
20 -------------
21
22 During pre-optimization we perform optimizations which don't require
23 full knowledge of the control flow graph and the life ranges of each
24 variable. This phase is handled by two functions: pre_optimize() and
25 cfg_optimize().
26
27 pre_optimize() runs before the construction of the CFG begins. It calls
28 strength_reduce() to perform simple strength reduction, and if_branch()
29 to rewrite certain if/branch/label constructs (for details, see
30 if_branch() below).
31
32 [pre_optimize() may also be called later, during the main optimization
33 phase, but this is not guaranteed.]
34
35 cfg_optimize() runs during the construction of the CFG. It calls
36 branch_branch() to perform jump optimization (i.e. branches to
37 branch statements or jumps to jumps are converted into single
38 branches/jumps to the final destination), unused_label() to remove
39 unused labels and dead_code_remove() to remove unreachable code
40 (e.g. basic blocks which are never entered or instructions after
41 and unconditional branch which are never branched to).
42
43 cfg_optimize may be called multiple times during the construction of the
44 CFG depending on whether or not it finds anything to optimize.
45
46 RT #46277: subst_constants ... rewrite e.g. add_i_ic_ic -- where does this happen?
47
48 optimizer
49 ---------
50
51 runs with CFG and life info
52
53 used_once ... deletes assignments, when LHS is unused
54 loop_optimization ... pulls invariants out of loops
55 RT #46279 e.g. constant_propagation
56
57 post_optimizer: currently pcc_optimize in pcc.c
58 ---------------
59
60 runs after register alloocation
61
62 e.g. eliminate new Px .PerlUndef because Px where different before
63
64 =head2 Functions
65
66 =over 4
67
68 =cut
69
70 */
71
72 #include <string.h>
73 #include "imc.h"
74 #include "pbc.h"
75 #include "optimizer.h"
76
77 /* HEADERIZER HFILE: compilers/imcc/optimizer.h */
78
79
80 /* buggy - turned off */
81 #define DO_LOOP_OPTIMIZATION 0
82
83 /* HEADERIZER BEGIN: static */
84 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
85
86 PARROT_WARN_UNUSED_RESULT
87 static int _is_ins_save(
88 ARGIN(const IMC_Unit *unit),
89 ARGIN(const Instruction *check_ins),
90 ARGIN(const SymReg *r),
91 int what)
92 __attribute__nonnull__(1)
93 __attribute__nonnull__(2)
94 __attribute__nonnull__(3);
95
96 static int branch_branch(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
97 __attribute__nonnull__(1)
98 __attribute__nonnull__(2)
99 FUNC_MODIFIES(*unit);
100
101 static int branch_cond_loop(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
102 __attribute__nonnull__(1)
103 __attribute__nonnull__(2)
104 FUNC_MODIFIES(*unit);
105
106 PARROT_WARN_UNUSED_RESULT
107 static int branch_cond_loop_swap(PARROT_INTERP,
108 ARGMOD(IMC_Unit *unit),
109 ARGMOD(Instruction *branch),
110 ARGMOD(Instruction *start),
111 ARGMOD(Instruction *cond))
112 __attribute__nonnull__(1)
113 __attribute__nonnull__(2)
114 __attribute__nonnull__(3)
115 __attribute__nonnull__(4)
116 __attribute__nonnull__(5)
117 FUNC_MODIFIES(*unit)
118 FUNC_MODIFIES(*branch)
119 FUNC_MODIFIES(*start)
120 FUNC_MODIFIES(*cond);
121
122 PARROT_WARN_UNUSED_RESULT
123 static int branch_reorg(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
124 __attribute__nonnull__(1)
125 __attribute__nonnull__(2)
126 FUNC_MODIFIES(*unit);
127
128 static int constant_propagation(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
129 __attribute__nonnull__(1)
130 __attribute__nonnull__(2)
131 FUNC_MODIFIES(*unit);
132
133 static int dead_code_remove(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
134 __attribute__nonnull__(1)
135 __attribute__nonnull__(2)
136 FUNC_MODIFIES(*unit);
137
138 PARROT_WARN_UNUSED_RESULT
139 static int eval_ins(PARROT_INTERP,
140 ARGIN(const char *op),
141 size_t ops,
142 ARGIN(SymReg **r))
143 __attribute__nonnull__(1)
144 __attribute__nonnull__(2)
145 __attribute__nonnull__(4);
146
147 static int if_branch(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
148 __attribute__nonnull__(1)
149 __attribute__nonnull__(2)
150 FUNC_MODIFIES(*unit);
151
152 PARROT_WARN_UNUSED_RESULT
153 static int is_ins_save(PARROT_INTERP,
154 ARGIN(const IMC_Unit *unit),
155 ARGIN(const Instruction *ins),
156 ARGIN(const SymReg *r),
157 int what)
158 __attribute__nonnull__(1)
159 __attribute__nonnull__(2)
160 __attribute__nonnull__(3)
161 __attribute__nonnull__(4);
162
163 static int strength_reduce(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
164 __attribute__nonnull__(1)
165 __attribute__nonnull__(2)
166 FUNC_MODIFIES(*unit);
167
168 PARROT_WARN_UNUSED_RESULT
169 static int unused_label(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
170 __attribute__nonnull__(1)
171 __attribute__nonnull__(2)
172 FUNC_MODIFIES(*unit);
173
174 static int used_once(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
175 __attribute__nonnull__(1)
176 __attribute__nonnull__(2)
177 FUNC_MODIFIES(*unit);
178
179 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
180 /* HEADERIZER END: static */
181
182 #if DO_LOOP_OPTIMIZATION
183 int loop_optimization(Interp *, IMC_Unit *);
184
185 PARROT_WARN_UNUSED_RESULT
186 int _is_ins_save(
187 ARGIN(const IMC_Unit *unit),
188 ARGIN(const Instruction *check_ins),
189 ARGIN(const SymReg *r),
190 int what)
191 __attribute__nonnull__(1)
192 __attribute__nonnull__(2)
193 __attribute__nonnull__(3);
194
195 PARROT_WARN_UNUSED_RESULT
196 int is_ins_save(PARROT_INTERP,
197 ARGIN(const IMC_Unit *unit),
198 ARGIN(const Instruction *ins),
199 ARGIN(const SymReg *r),
200 int what)
201 __attribute__nonnull__(1)
202 __attribute__nonnull__(2)
203 __attribute__nonnull__(3)
204 __attribute__nonnull__(4);
205
206 PARROT_WARN_UNUSED_RESULT
207 int max_loop_depth(ARGIN(const IMC_Unit *unit))
208 __attribute__nonnull__(1);
209
210 int is_invariant(PARROT_INTERP,
211 ARGIN(const IMC_Unit *unit),
212 ARGIN(const Instruction *ins))
213 __attribute__nonnull__(1)
214 __attribute__nonnull__(2)
215 __attribute__nonnull__(3);
216
217 PARROT_WARN_UNUSED_RESULT
218 PARROT_CAN_RETURN_NULL
219 Basic_block * find_outer(
220 ARGIN(const IMC_Unit *unit),
221 ARGIN(const Basic_block *blk))
222 __attribute__nonnull__(1)
223 __attribute__nonnull__(2);
224
225
226 #endif
227
228 /*
229
230 =item C<int pre_optimize>
231
232 Handles optimizations occuring before the construction of the CFG.
233
234 =cut
235
236 */
237
238 int
239 pre_optimize(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
240 {
241 int changed = 0;
242
243 if (IMCC_INFO(interp)->optimizer_level & OPT_PRE) {
244 IMCC_info(interp, 2, "pre_optimize\n");
245 /* RT #46281 integrate all in one pass */
246 changed += strength_reduce(interp, unit);
247 if (!IMCC_INFO(interp)->dont_optimize)
248 changed += if_branch(interp, unit);
249 }
250 return changed;
251 }
252
253 /*
254
255 =item C<int cfg_optimize>
256
257 Handles optimizations occuring during the construction of the CFG.
258 Returns TRUE if any optimization was performed. Otherwise, returns
259 FALSE.
260
261 =cut
262
263 */
264
265 PARROT_WARN_UNUSED_RESULT
266 int
267 cfg_optimize(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
268 {
269 if (IMCC_INFO(interp)->dont_optimize)
270 return 0;
271 if (IMCC_INFO(interp)->optimizer_level & OPT_PRE) {
272 IMCC_info(interp, 2, "cfg_optimize\n");
273 if (branch_branch(interp, unit))
274 return 1;
275 if (branch_cond_loop(interp, unit))
276 return 1;
277 if (branch_reorg(interp, unit))
278 return 1;
279 /* RT #46283 cfg / loop detection breaks e.g. in t/compiler/5_3 */
280 if (unused_label(interp, unit))
281 return 1;
282 if (dead_code_remove(interp, unit))
283 return 1;
284 }
285 return 0;
286 }
287
288 /*
289
290 =item C<int optimize>
291
292 RT #48260: Not yet documented!!!
293
294 =cut
295
296 */
297
298 int
299 optimize(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
300 {
301 int any = 0;
302 if (IMCC_INFO(interp)->optimizer_level & OPT_CFG) {
303 IMCC_info(interp, 2, "optimize\n");
304 any = constant_propagation(interp, unit);
305 if (used_once(interp, unit))
306 return 1;
307 #if DO_LOOP_OPTIMIZATION
308 if (loop_optimization(interp, unit))
309 return 1;
310 #endif
311 }
312 return any;
313 }
314
315 /*
316
317 =item C<const char * get_neg_op>
318
319 Get negated form of operator. If no negated form is known, return NULL.
320
321 =cut
322
323 */
324
325 PARROT_WARN_UNUSED_RESULT
326 PARROT_CAN_RETURN_NULL
327 const char *
328 get_neg_op(ARGIN(const char *op), ARGOUT(int *n))
329 {
330 static const struct br_pairs {
331 const char * const op;
332 const char * const nop;
333 int n;
334 } br_pairs[] = {
335 { "if", "unless", 2 },
336 { "eq", "ne", 3 },
337 { "gt", "le", 3 },
338 { "ge", "lt", 3 },
339 };
340 size_t i;
341 for (i = 0; i < N_ELEMENTS(br_pairs); i++) {
342 *n = br_pairs[i].n;
343 if (STREQ(op, br_pairs[i].op))
344 return br_pairs[i].nop;
345 if (STREQ(op, br_pairs[i].nop))
346 return br_pairs[i].op;
347 }
348 return NULL;
349 }
350
351 /*
352 *
353 */
354 /*
355
356 =item C<static int if_branch>
357
358 Convert if/branch/label constructs of the form:
359
360 if cond L1
361 branch L2
362 L1
363
364 to the simpler negated form:
365
366 unless cond L2
367
368 =cut
369
370 */
371
372 static int
373 if_branch(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
374 {
375 Instruction *ins, *last;
376 int reg, changed = 0;
377
378 last = unit->instructions;
379 if (!last->next)
380 return changed;
381 IMCC_info(interp, 2, "\tif_branch\n");
382 for (ins = last->next; ins;) {
383 if ((last->type & ITBRANCH) && /* if ...L1 */
384 (ins->type & IF_goto) && /* branch L2*/
385 STREQ(ins->opname, "branch") &&
386 (reg = get_branch_regno(last)) >= 0) {
387 SymReg * const br_dest = last->symregs[reg];
388 if (ins->next &&
389 (ins->next->type & ITLABEL) && /* L1 */
390 ins->next->symregs[0] == br_dest) {
391 const char * neg_op;
392 SymReg * const go = get_branch_reg(ins);
393 int args;
394
395 IMCC_debug(interp, DEBUG_OPT1, "if_branch %s ... %s\n",
396 last->opname, br_dest->name);
397 /* find the negated op (e.g if->unless, ne->eq ... */
398 if ((neg_op = get_neg_op(last->opname, &args)) != 0) {
399 Instruction * tmp;
400 last->symregs[reg] = go;
401 tmp = INS(interp, unit, (char*)neg_op, "",
402 last->symregs, args, 0, 0);
403 last->opnum = tmp->opnum;
404 last->opsize = tmp->opsize;
405 free(last->opname);
406 last->opname = str_dup(tmp->opname);
407 free_ins(tmp);
408
409 /* delete branch */
410 unit->ostat.deleted_ins++;
411 ins = delete_ins(unit, ins);
412 unit->ostat.if_branch++;
413 changed = 1;
414 }
415 } /* label found */
416 } /* branch detected */
417 last = ins;
418 ins = ins->next;
419 }
420 return changed;
421 }
422
423 /*
424
425 =item C<static int strength_reduce>
426
427 strength_reduce ... rewrites e.g add Ix, Ix, y => add Ix, y
428
429 These are run after constant simplification, so it is
430 guaranteed that one operand is non constant if opsize == 4
431
432 =cut
433
434 */
435
436 static int
437 strength_reduce(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
438 {
439 Instruction *ins, *tmp;
440 SymReg *r;
441 int changes = 0;
442 FLOATVAL f;
443
444 IMCC_info(interp, 2, "\tstrength_reduce\n");
445 for (ins = unit->instructions; ins; ins = ins->next) {
446 /*
447 * add Ix, Ix, Iy => add Ix, Iy
448 * add Ix, Iy, Ix => add Ix, Iy
449 * sub Ix, Ix, Iy => sub Ix, Iy
450 * mul Ix, Ix, Iy => sub Ix, Iy
451 * mul Ix, Iy, Ix => sub Ix, Iy
452 * div Ix, Ix, Iy => sub Ix, Iy
453 * fdiv Ix, Ix, Iy => sub Ix, Iy
454 * add Nx, Nx, Ny => add Nx, Ny
455 * add Nx, Ny, Nx => add Nx, Ny
456 * sub Nx, Nx, Ny => sub Nx, Ny
457 * mul Nx, Nx, Ny => sub Nx, Ny
458 * mul Nx, Ny, Nx => sub Nx, Ny
459 * div Nx, Nx, Ny => sub Nx, Ny
460 * fdiv Nx, Nx, Ny => sub Nx, Ny
461 */
462 if (((ins->opnum == PARROT_OP_sub_i_i_i ||
463 ins->opnum == PARROT_OP_sub_i_i_ic ||
464 ins->opnum == PARROT_OP_sub_i_ic_i ||
465 ins->opnum == PARROT_OP_div_i_i_i ||
466 ins->opnum == PARROT_OP_div_i_i_ic ||
467 ins->opnum == PARROT_OP_div_i_ic_i ||
468 ins->opnum == PARROT_OP_fdiv_i_i_i ||
469 ins->opnum == PARROT_OP_fdiv_i_i_ic ||
470 ins->opnum == PARROT_OP_fdiv_i_ic_i ||
471 ins->opnum == PARROT_OP_sub_n_n_n ||
472 ins->opnum == PARROT_OP_sub_n_n_nc ||
473 ins->opnum == PARROT_OP_sub_n_nc_n ||
474 ins->opnum == PARROT_OP_div_n_n_n ||
475 ins->opnum == PARROT_OP_div_n_n_nc ||
476 ins->opnum == PARROT_OP_div_n_nc_n ||
477 ins->opnum == PARROT_OP_fdiv_n_n_n ||
478 ins->opnum == PARROT_OP_fdiv_n_n_nc ||
479 ins->opnum == PARROT_OP_fdiv_n_nc_n) &&
480 ins->symregs[0] == ins->symregs[1])
481 || ((ins->opnum == PARROT_OP_add_i_i_i ||
482 ins->opnum == PARROT_OP_add_i_i_ic ||
483 ins->opnum == PARROT_OP_add_i_ic_i ||
484 ins->opnum == PARROT_OP_mul_i_i_i ||
485 ins->opnum == PARROT_OP_mul_i_i_ic ||
486 ins->opnum == PARROT_OP_mul_i_ic_i ||
487 ins->opnum == PARROT_OP_add_n_n_n ||
488 ins->opnum == PARROT_OP_add_n_n_nc ||
489 ins->opnum == PARROT_OP_add_n_nc_n ||
490 ins->opnum == PARROT_OP_mul_n_n_n ||
491 ins->opnum == PARROT_OP_mul_n_n_nc ||
492 ins->opnum == PARROT_OP_mul_n_nc_n) &&
493 (ins->symregs[0] == ins->symregs[1] ||
494 ins->symregs[0] == ins->symregs[2]))) {
495 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
496 if (ins->symregs[0] == ins->symregs[1]) {
497 ins->symregs[1] = ins->symregs[2];
498 }
499 tmp = INS(interp, unit, ins->opname, "", ins->symregs, 2, 0, 0);
500 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
501 subst_ins(unit, ins, tmp, 1);
502 ins = tmp;
503 changes = 1;
504 }
505 /*
506 * add Ix, 0 => delete
507 * sub Ix, 0 => delete
508 * mul Ix, 1 => delete
509 * div Ix, 1 => delete
510 * fdiv Ix, 1 => delete
511 * add Nx, 0 => delete
512 * sub Nx, 0 => delete
513 * mul Nx, 1 => delete
514 * div Nx, 1 => delete
515 * fdiv Nx, 1 => delete
516 */
517 if (((ins->opnum == PARROT_OP_add_i_ic ||
518 ins->opnum == PARROT_OP_sub_i_ic) &&
519 IMCC_int_from_reg(interp, ins->symregs[1]) == 0)
520 || ((ins->opnum == PARROT_OP_mul_i_ic ||
521 ins->opnum == PARROT_OP_div_i_ic ||
522 ins->opnum == PARROT_OP_fdiv_i_ic) &&
523 IMCC_int_from_reg(interp, ins->symregs[1]) == 1)
524 || ((ins->opnum == PARROT_OP_add_n_nc ||
525 ins->opnum == PARROT_OP_sub_n_nc) &&
526 (f = atof(ins->symregs[1]->name), FLOAT_IS_ZERO(f)))
527 || ((ins->opnum == PARROT_OP_mul_n_nc ||
528 ins->opnum == PARROT_OP_div_n_nc ||
529 ins->opnum == PARROT_OP_fdiv_n_nc) &&
530 atof(ins->symregs[1]->name) == 1.0)) {
531 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
532 ins = delete_ins(unit, ins);
533 if (ins)
534 ins = ins->prev ? ins->prev : unit->instructions;
535 else
536 break;
537 IMCC_debug(interp, DEBUG_OPT1, "deleted\n");
538 changes = 1;
539 continue;
540 }
541 /*
542 * add Ix, 1 => inc Ix
543 * add Nx, 1 => inc Nx
544 * sub Ix, 1 => dec Ix
545 * sub Nx, 1 => dec Nx
546 */
547 if (((ins->opnum == PARROT_OP_add_i_ic ||
548 ins->opnum == PARROT_OP_sub_i_ic) &&
549 IMCC_int_from_reg(interp, ins->symregs[1]) == 1)
550 || ((ins->opnum == PARROT_OP_add_n_nc ||
551 ins->opnum == PARROT_OP_sub_n_nc) &&
552 atof(ins->symregs[1]->name) == 1.0)) {
553 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
554 --ins->symregs[1]->use_count;
555 if (ins->opnum == PARROT_OP_add_i_ic ||
556 ins->opnum == PARROT_OP_add_n_nc)
557 tmp = INS(interp, unit, "inc", "", ins->symregs, 1, 0, 0);
558 else
559 tmp = INS(interp, unit, "dec", "", ins->symregs, 1, 0, 0);
560 subst_ins(unit, ins, tmp, 1);
561 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
562 ins = tmp;
563 changes = 1;
564 continue;
565 }
566 /*
567 * add Ix, Iy, 0 => set Ix, Iy
568 * add Ix, 0, Iy => set Ix, Iy
569 * sub Ix, Iy, 0 => set Ix, Iy
570 * mul Ix, Iy, 1 => set Ix, Iy
571 * mul Ix, 1, Iy => set Ix, Iy
572 * div Ix, Iy, 1 => set Ix, Iy
573 * fdiv Ix, Iy, 1 => set Ix, Iy
574 * add Nx, Ny, 0 => set Nx, Ny
575 * add Nx, 0, Ny => set Nx, Ny
576 * sub Nx, Ny, 0 => set Nx, Ny
577 * mul Nx, Ny, 1 => set Nx, Ny
578 * mul Nx, 1, Ny => set Nx, Ny
579 * div Nx, Ny, 1 => set Nx, Ny
580 * fdiv Nx, Ny, 1 => set Nx, Ny
581 */
582 if (((ins->opnum == PARROT_OP_add_i_i_ic ||
583 ins->opnum == PARROT_OP_sub_i_i_ic) &&
584 IMCC_int_from_reg(interp, ins->symregs[2]) == 0)
585 || (ins->opnum == PARROT_OP_add_i_ic_i &&
586 IMCC_int_from_reg(interp, ins->symregs[1]) == 0)
587 || ((ins->opnum == PARROT_OP_mul_i_i_ic ||
588 ins->opnum == PARROT_OP_div_i_i_ic ||
589 ins->opnum == PARROT_OP_fdiv_i_i_ic) &&
590 IMCC_int_from_reg(interp, ins->symregs[2]) == 1)
591 || (ins->opnum == PARROT_OP_mul_i_ic_i &&
592 IMCC_int_from_reg(interp, ins->symregs[1]) == 1)
593 || ((ins->opnum == PARROT_OP_add_n_n_nc ||
594 ins->opnum == PARROT_OP_sub_n_n_nc) &&
595 (f = atof(ins->symregs[2]->name), FLOAT_IS_ZERO(f)))
596 || (ins->opnum == PARROT_OP_add_n_nc_n &&
597 (f = atof(ins->symregs[1]->name), FLOAT_IS_ZERO(f)))
598 || ((ins->opnum == PARROT_OP_mul_n_n_nc ||
599 ins->opnum == PARROT_OP_div_n_n_nc ||
600 ins->opnum == PARROT_OP_fdiv_n_n_nc) &&
601 atof(ins->symregs[2]->name) == 1.0)
602 || (ins->opnum == PARROT_OP_mul_n_nc_n &&
603 atof(ins->symregs[1]->name) == 1.0)) {
604 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
605 if (ins->symregs[1]->type == VTCONST) {
606 --ins->symregs[1]->use_count;
607 ins->symregs[1] = ins->symregs[2];
608 }
609 else {
610 --ins->symregs[2]->use_count;
611 }
612 tmp = INS(interp, unit, "set", "", ins->symregs, 2, 0, 0);
613 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
614 subst_ins(unit, ins, tmp, 1);
615 ins = tmp;
616 changes = 1;
617 continue;
618 }
619 /*
620 * mul Ix, Iy, 0 => set Ix, 0
621 * mul Ix, 0, Iy => set Ix, 0
622 * mul Ix, 0 => set Ix, 0
623 */
624 if ((ins->opnum == PARROT_OP_mul_i_i_ic &&
625 IMCC_int_from_reg(interp, ins->symregs[2]) == 0)
626 || ((ins->opnum == PARROT_OP_mul_i_ic_i ||
627 ins->opnum == PARROT_OP_mul_i_ic) &&
628 IMCC_int_from_reg(interp, ins->symregs[1]) == 0)
629 || (ins->opnum == PARROT_OP_mul_n_n_nc &&
630 (f = atof(ins->symregs[2]->name), FLOAT_IS_ZERO(f)))
631 || ((ins->opnum == PARROT_OP_mul_n_nc_n ||
632 ins->opnum == PARROT_OP_mul_n_nc) &&
633 (f = atof(ins->symregs[1]->name), FLOAT_IS_ZERO(f)))) {
634 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
635 r = mk_const(interp, "0", ins->symregs[0]->set);
636 --ins->symregs[1]->use_count;
637 if (ins->opsize == 4)
638 --ins->symregs[2]->use_count;
639 ins->symregs[1] = r;
640 tmp = INS(interp, unit, "set", "", ins->symregs, 2, 0, 0);
641 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
642 subst_ins(unit, ins, tmp, 1);
643 ins = tmp;
644 changes = 1;
645 }
646 /*
647 * set Ix, 0 => null Ix
648 * set Nx, 0 => null Nx
649 */
650 if ((ins->opnum == PARROT_OP_set_i_ic &&
651 IMCC_int_from_reg(interp, ins->symregs[1]) == 0)
652 || (ins->opnum == PARROT_OP_set_n_nc &&
653 (f = atof(ins->symregs[1]->name), FLOAT_IS_ZERO(f)) &&
654 ins->symregs[1]->name[0] != '-')) {
655 IMCC_debug(interp, DEBUG_OPT1, "opt1 %I => ", ins);
656 --ins->symregs[1]->use_count;
657 tmp = INS(interp, unit, "null", "", ins->symregs, 1, 0, 0);
658 subst_ins(unit, ins, tmp, 1);
659 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
660 ins = tmp;
661 changes = 1;
662 continue;
663 }
664 }
665 return changes;
666 }
667
668 /*
669
670 =item C<static int constant_propagation>
671
672 Does conservative constant propagation.
673 This code will not propagate constants past labels or saves,
674 even though sometimes it may be safe.
675
676 =cut
677
678 */
679
680 static int
681 constant_propagation(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
682 {
683 Instruction *ins, *ins2, *tmp, *prev;
684 int i;
685 SymReg *c, *o;
686 int any = 0;
687
688 o = c = NULL; /* silence compiler uninit warning */
689
690 IMCC_info(interp, 2, "\tconstant_propagation\n");
691 for (ins = unit->instructions; ins; ins = ins->next) {
692 int found = 0;
693 if (STREQ(ins->opname, "set") &&
694 ins->opsize == 3 && /* no keyed set */
695 ins->symregs[1]->type == VTCONST &&
696 ins->symregs[0]->set != 'P') { /* no PMC consts */
697 found = 1;
698 c = ins->symregs[1];
699 o = ins->symregs[0];
700 } else if (STREQ(ins->opname, "null") && ins->symregs[0]->set == 'I') {
701 found = 1;
702 c = mk_const(interp, "0", 'I');
703 o = ins->symregs[0];
704 } /* this would be good because 'set I0, 0' is reduced to 'null I0'
705 before it gets to us */
706
707 if (found) {
708 IMCC_debug(interp, DEBUG_OPT2,
709 "propagating constant %I => \n", ins);
710 for (ins2 = ins->next; ins2; ins2 = ins2->next) {
711 if (ins2->bbindex != ins->bbindex)
712 /* restrict to within a basic block */
713 goto next_constant;
714 /* was opsize - 2, changed to n_r - 1
715 */
716 for (i = ins2->symreg_count - 1; i >= 0; i--) {
717 if (STREQ(o->name, ins2->symregs[i]->name)) {
718 if (instruction_writes(ins2, ins2->symregs[i]))
719 goto next_constant;
720 else if (instruction_reads(ins2, ins2->symregs[i])) {
721 SymReg *old;
722 IMCC_debug(interp, DEBUG_OPT2,
723 "\tpropagating into %I register %i",
724 ins2, i);
725 old = ins2->symregs[i];
726 ins2->symregs[i] = c;
727 /* first we try subst_constants for e.g. if 10 < 5 goto next*/
728 tmp = IMCC_subst_constants(interp,
729 unit, ins2->opname, ins2->symregs, ins2->opsize,
730 &found);
731 if (found) {
732 prev = ins2->prev;
733 if (prev) {
734 subst_ins(unit, ins2, tmp, 1);
735 any = 1;
736 IMCC_debug(interp, DEBUG_OPT2,
737 " reduced to %I\n", tmp);
738 ins2 = prev->next;
739 }
740 }
741 else {
742 char fullname[128];
743 const int op = check_op(interp, fullname, ins2->opname,
744 ins2->symregs, ins2->symreg_count, ins2->keys);
745 if (op < 0) {
746 ins2->symregs[i] = old;
747 IMCC_debug(interp, DEBUG_OPT2,
748 " - no %s\n", fullname);
749 }
750 else {
751 --old->use_count;
752 ins2->opnum = op;
753 any = 1;
754 IMCC_debug(interp, DEBUG_OPT2,
755 " -> %I\n", ins2);
756 }
757 }
758 }
759 }
760
761 }/* for (i ... )*/
762 }/* for (ins2 ... )*/
763 } /* if */
764 next_constant:;
765
766 }/*for (ins ... )*/
767 return any;
768 }
769
770 /*
771
772 =item C<Instruction * IMCC_subst_constants_umix>
773
774 rewrite e.g. add_n_ic => add_n_nc
775
776 =cut
777
778 */
779
780 PARROT_WARN_UNUSED_RESULT
781 PARROT_CAN_RETURN_NULL
782 Instruction *
783 IMCC_subst_constants_umix(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGIN(const char *name),
784 ARGMOD(SymReg **r), int n)
785 {
786 Instruction *tmp;
787 const char * const ops[] = {
788 "abs", "add", "div", "mul", "sub", "fdiv"
789 };
790 size_t i;
791 char b[128];
792
793 tmp = NULL;
794 for (i = 0; i < N_ELEMENTS(ops); i++) {
795 if (n == 3 &&
796 r[0]->set == 'N' &&
797 r[1]->type == VTCONST &&
798 r[1]->set == 'I' &&
799 STREQ(name, ops[i])) {
800 IMCC_debug(interp, DEBUG_OPT1, "opt1 %s_nc_ic => ", name);
801 strcpy(b, r[1]->name);
802 r[1] = mk_const(interp, b, 'N');
803 tmp = INS(interp, unit, name, "", r, 2, 0, 0);
804 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
805 }
806 }
807 return tmp;
808 }
809
810 /*
811
812 =item C<static int eval_ins>
813
814 Run one parrot instruction, registers are filled with the
815 according constants. If an exception occurs, return -1, aborting
816 this optimization: this lets the runtime handle any exceptions.
817
818 =cut
819
820 */
821
822 PARROT_WARN_UNUSED_RESULT
823 static int
824 eval_ins(PARROT_INTERP, ARGIN(const char *op), size_t ops, ARGIN(SymReg **r))
825 {
826 opcode_t eval[4], *pc;
827 int opnum;
828 int i;
829 op_info_t *op_info;
830
831 opnum = interp->op_lib->op_code(op, 1);
832 if (opnum < 0)
833 IMCC_fatal(interp, 1, "eval_ins: op '%s' not found\n", op);
834 op_info = interp->op_info_table + opnum;
835 /* now fill registers */
836 eval[0] = opnum;
837 for (i = 0; i < op_info->op_count - 1; i++) {
838 switch (op_info->types[i]) {
839 case PARROT_ARG_IC:
840 PARROT_ASSERT(i && ops == (unsigned int)i);
841 /* set branch offset to zero */
842 eval[i + 1] = 0;
843 break;
844 case PARROT_ARG_I:
845 case PARROT_ARG_N:
846 case PARROT_ARG_S:
847 eval[i + 1] = i; /* regs used are I0, I1, I2 */
848 if (ops <= 2 || i) { /* fill source regs */
849 switch (r[i]->set) {
850 case 'I':
851 REG_INT(interp, i) = IMCC_int_from_reg(interp, r[i]);
852 break;
853 case 'N':
854 {
855 STRING * const s = string_from_cstring(interp, r[i]->name, 0);
856 REG_NUM(interp, i) = string_to_num(interp, s);
857 }
858 break;
859 case 'S':
860 REG_STR(interp, i) = IMCC_string_from_reg(interp, r[i]);
861 break;
862 default:
863 break;
864 }
865 }
866 break;
867 default:
868 IMCC_fatal(interp, 1, "eval_ins"
869 "invalid arg #%d for op '%s' not found\n",
870 i, op);
871 }
872 }
873
874 /* eval the opcode */
875 new_runloop_jump_point(interp);
876 if (setjmp(interp->current_runloop->resume))
877 return -1;
878
879 pc = (interp->op_func_table[opnum]) (eval, interp);
880 free_runloop_jump_point(interp);
881 /* the returned pc is either incremented by op_count or is eval,
882 * as the branch offset is 0 - return true if it branched
883 */
884 PARROT_ASSERT(pc == eval + op_info->op_count || pc == eval);
885 return pc == eval;
886 }
887
888 /*
889
890 =item C<Instruction * IMCC_subst_constants>
891
892 rewrite e.g. add_n_nc_nc => set_n_nc
893 abs_i_ic => set_i_ic
894 eq_ic_ic_ic => branch_ic / delete
895 if_ic_ic => branch_ic / delete
896
897 =cut
898
899 */
900
901 PARROT_WARN_UNUSED_RESULT
902 PARROT_CAN_RETURN_NULL
903 Instruction *
904 IMCC_subst_constants(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGIN(const char *name),
905 ARGMOD(SymReg **r), int n, ARGOUT(int *ok))
906 {
907 Instruction *tmp;
908 const char * const ops[] = {
909 "add", "sub", "mul", "div", "fdiv", "pow",
910 "cmod", "mod", "atan",
911 "shr", "shl", "lsr",
912 "gcd", "lcm",
913 "band", "bor", "bxor",
914 "bands", "bors", "bxors",
915 "and", "or", "xor",
916 "iseq", "isne", "islt", "isle", "isgt", "isge", "cmp", "concat"
917 };
918 const char * const ops2[] = {
919 "abs", "neg", "not", "fact", "sqrt", "ceil", "floor"
920 "acos", "asec", "asin",
921 "atan", "cos", "cosh", "exp", "ln", "log10", "log2", "sec",
922 "sech", "sin", "sinh", "tan", "tanh", "fact"
923 };
924 const char * const ops3[] = {
925 "eq", "ne", "gt", "ge", "lt", "le"
926 };
927 const char * const ops4[] = {
928 "if", "unless"
929 };
930
931 size_t i;
932 char fmt[64], op[20];
933 const char *debug_fmt = NULL; /* gcc -O uninit warn */
934 int found, branched;
935
936 /* construct a FLOATVAL_FMT with needed precision */
937 switch (NUMVAL_SIZE) {
938 case 8:
939 strcpy(fmt, "%0.16g");
940 break;
941 case 12:
942 strcpy(fmt, "%0.18Lg");
943 break;
944 default:
945 IMCC_warning(interp, "subs_constants",
946 "used default FLOATVAL_FMT\n");
947 strcpy(fmt, FLOATVAL_FMT);
948 break;
949 }
950
951 tmp = NULL;
952 found = 0;
953 for (i = 0; i < N_ELEMENTS(ops); i++) {
954 if (n == 4 &&
955 r[1]->type & (VTCONST|VT_CONSTP) &&
956 r[2]->type & (VTCONST|VT_CONSTP) &&
957 STREQ(name, ops[i])) {
958 found = 4;
959 /*
960 * create instruction e.g. add_i_ic_ic => add_i_i_i
961 */
962 snprintf(op, sizeof (op), "%s_%c_%c_%c", name, tolower((unsigned char)r[0]->set),
963 tolower((unsigned char)r[1]->set), tolower((unsigned char)r[2]->set));
964 debug_fmt = "opt %s_x_xc_xc => ";
965 break;
966 }
967 }
968 for (i = 0; !found && i < N_ELEMENTS(ops2); i++) {
969 /*
970 * abs_i_ic ...
971 */
972 if (n == 3) {
973 PARROT_ASSERT(r[1]);
974 if (r[1]->type & (VTCONST|VT_CONSTP) &&
975 STREQ(name, ops2[i])) {
976 found = 3;
977 snprintf(op, sizeof (op), "%s_%c_%c", name, tolower((unsigned char)r[0]->set),
978 tolower((unsigned char)r[1]->set));
979 debug_fmt = "opt %s_x_xc => ";
980 break;
981 }
982 }
983 }
984 for (i = 0; !found && i < N_ELEMENTS(ops3); i++) {
985 /*
986 * eq_xc_xc_labelc ...
987 */
988 if (n == 4 &&
989 r[0]->type & (VTCONST|VT_CONSTP) &&
990 r[1]->type & (VTCONST|VT_CONSTP) &&
991 STREQ(name, ops3[i])) {
992 found = 2;
993 snprintf(op, sizeof (op), "%s_%c_%c_ic", name, tolower((unsigned char)r[0]->set),
994 tolower((unsigned char)r[1]->set));
995 debug_fmt = "opt %s_xc_xc_ic => ";
996 break;
997 }
998 }
999 for (i = 0; !found && i < N_ELEMENTS(ops4); i++) {
1000 /*
1001 * if_xc_labelc, unless
1002 */
1003 if (n == 3 &&
1004 r[0]->type & (VTCONST|VT_CONSTP) &&
1005 STREQ(name, ops4[i])) {
1006 found = 1;
1007 snprintf(op, sizeof (op), "%s_%c_ic", name, tolower((unsigned char)r[0]->set));
1008 debug_fmt = "opt %s_xc_ic => ";
1009 break;
1010 }
1011 }
1012
1013 if (!found) {
1014 *ok = 0;
1015 return NULL;
1016 }
1017
1018 IMCC_debug(interp, DEBUG_OPT1, debug_fmt, name);
1019 /* we construct a parrot instruction
1020 * here and let parrot do the calculation in a
1021 * separate context and make a constant
1022 * from the result
1023 */
1024 branched = eval_ins(interp, op, found, r);
1025 if (branched == -1) {
1026 /* Don't set ok (See RT #43048 for info) */
1027 return NULL;
1028 }
1029 /*
1030 * for math ops result is in I0/N0
1031 * if it was a branch with constant args, the result is
1032 * the return value
1033 */
1034 if (found <= 2) {
1035 /*
1036 * create a branch or delete instruction
1037 */
1038 if (branched) {
1039 r[0] = r[found];
1040 tmp = INS(interp, unit, "branch", "", r, 1, 0, 0);
1041 }
1042 else {
1043 IMCC_debug(interp, DEBUG_OPT1, "deleted\n");
1044 }
1045 }
1046 else {
1047 /*
1048 * create set x, constant
1049 */
1050 char b[128];
1051 switch (r[0]->set) {
1052 case 'I':
1053 snprintf(b, sizeof (b), INTVAL_FMT, REG_INT(interp, 0));
1054 r[1] = mk_const(interp, b, r[0]->set);
1055 break;
1056 case 'N':
1057 snprintf(b, sizeof (b), fmt, REG_NUM(interp, 0));
1058 r[1] = mk_const(interp, b, r[0]->set);
1059 break;
1060 case 'S':
1061 r[1] = mk_const(interp, string_to_cstring(interp,
1062 REG_STR(interp, 0)), r[0]->set);
1063 snprintf(b, sizeof (b), "%p", REG_STR(interp, 0));
1064 break;
1065 default:
1066 break;
1067 }
1068 tmp = INS(interp, unit, "set", "", r, 2, 0, 0);
1069 }
1070 if (tmp) {
1071 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
1072 }
1073 *ok = 1;
1074 return tmp;
1075 }
1076
1077
1078 /* optimizations with CFG built */
1079
1080 /*
1081
1082 =item C<static int branch_branch>
1083
1084 if I0 goto L1 => if IO goto L2
1085 ...
1086 L1:
1087 branch L2
1088
1089 Returns TRUE if any optimizations were performed. Otherwise, returns
1090 FALSE.
1091
1092 =cut
1093
1094 */
1095
1096 static int
1097 branch_branch(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1098 {
1099 Instruction *ins;
1100 int changed = 0;
1101
1102 IMCC_info(interp, 2, "\tbranch_branch\n");
1103 /* reset statistic globals */
1104 for (ins = unit->instructions; ins; ins = ins->next) {
1105 if (get_branch_regno(ins) >= 0) {
1106 SymReg * const r = get_sym(interp, get_branch_reg(ins)->name);
1107
1108 if (r && (r->type & VTADDRESS) && r->first_ins) {
1109 Instruction * const next = r->first_ins->next;
1110 /* if (!next ||
1111 STREQ(next->symregs[0]->name, get_branch_reg(ins)->name))
1112 break;*/
1113 if (next &&
1114 (next->type & IF_goto) &&
1115 STREQ(next->opname, "branch") &&
1116 !STREQ(next->symregs[0]->name, get_branch_reg(ins)->name)) {
1117 const int regno = get_branch_regno(ins);
1118 IMCC_debug(interp, DEBUG_OPT1,
1119 "found branch to branch '%s' %I\n",
1120 r->first_ins->symregs[0]->name, next);
1121 unit->ostat.branch_branch++;
1122 if (regno < 0)
1123 Parrot_ex_throw_from_c_args(interp, NULL, 1,
1124 "Register number determination failed in branch_branch()");
1125
1126 ins->symregs[regno] = next->symregs[0];
1127 changed = 1;
1128 }
1129 }
1130 }
1131 }
1132 return changed;
1133 }
1134
1135 /*
1136
1137 =item C<static int branch_reorg>
1138
1139 branch L2 => ...
1140 L1: branch L4
1141 ... L1:
1142 branch L3 ...
1143 L2: branch L3
1144 ... L5:
1145 branch L4
1146 L5:
1147
1148 Returns TRUE if any optimizations were performed. Otherwise, returns
1149 FALSE.
1150
1151 =cut
1152
1153 */
1154
1155 PARROT_WARN_UNUSED_RESULT
1156 static int
1157 branch_reorg(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1158 {
1159 unsigned int i;
1160 int changed = 0;
1161
1162 IMCC_info(interp, 2, "\tbranch_reorg\n");
1163 for (i = 0; i < unit->n_basic_blocks; i++) {
1164 Instruction *ins = unit->bb_list[i]->end;
1165
1166 /* if basic block ends with unconditional jump */
1167 if ((ins->type & IF_goto) && STREQ(ins->opname, "branch")) {
1168 SymReg * const r = get_sym(interp, ins->symregs[0]->name);
1169 if (r && (r->type & VTADDRESS) && r->first_ins) {
1170 Edge *edge;
1171 Instruction * const start = r->first_ins;
1172 int found = 0;
1173 for (edge = unit->bb_list[start->bbindex]->pred_list;
1174 edge; edge = edge->pred_next) {
1175 if (edge->from->index == start->bbindex - 1) {
1176 found = 1;
1177 break;
1178 }
1179 }
1180
1181 /* if target block is not reached by falling into it
1182 * from another block */
1183 if (!found) {
1184 Instruction *end;
1185 /* move target block and its positional successors
1186 * to follow block with unconditional jump
1187 * (this could actually be in another block) */
1188 for (end = start; end->next; end = end->next) {
1189 if ((end->type & IF_goto) &&
1190 STREQ(end->opname, "branch")) {
1191 break;
1192 }
1193 }
1194
1195 /* this was screwing up multi-block loops... */
1196 if (end != ins && ins->next != NULL) {
1197 ins->next->prev = end;
1198 start->prev->next = end->next;
1199 if (end->next)
1200 end->next->prev = start->prev;
1201
1202 end->next = ins->next;
1203 ins->next = start;
1204 start->prev = ins;
1205
1206 IMCC_debug(interp, DEBUG_OPT1,
1207 "found branch to reorganize '%s' %I\n",
1208 r->first_ins->symregs[0]->name, ins);
1209
1210 /* unconditional jump can be eliminated */
1211 unit->ostat.deleted_ins++;
1212 ins = delete_ins(unit, ins);
1213 return 1;
1214 }
1215 }
1216 }
1217 }
1218 }
1219
1220 return changed;
1221 }
1222
1223 /*
1224
1225 =item C<static int branch_cond_loop_swap>
1226
1227 RT #48260: Not yet documented!!!
1228
1229 =cut
1230
1231 */
1232
1233 PARROT_WARN_UNUSED_RESULT
1234 static int
1235 branch_cond_loop_swap(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGMOD(Instruction *branch),
1236 ARGMOD(Instruction *start), ARGMOD(Instruction *cond))
1237 {
1238 int changed = 0;
1239 int args;
1240 const char * const neg_op = get_neg_op(cond->opname, &args);
1241 if (neg_op) {
1242 const size_t size = strlen(branch->symregs[0]->name) + 10; /* + '_post999' */
1243 char * const label = (char *)mem_sys_allocate(size);
1244 int count;
1245 int found = 0;
1246
1247 for (count = 1; count != 999; ++count) {
1248 snprintf(label, size, "%s_post%d", branch->symregs[0]->name, count);
1249 if (get_sym(interp, label) == 0) {
1250 found = 1;
1251 break;
1252 }
1253 }
1254
1255 if (found) {
1256 Instruction *tmp;
1257 SymReg *regs[3], *r;
1258 int reg_index;
1259
1260 /* cond_op has 2 or 3 args */
1261 PARROT_ASSERT(args <= 3);
1262
1263 r = mk_local_label(interp, label);
1264 tmp = INS_LABEL(interp, unit, r, 0);
1265 insert_ins(unit, cond, tmp);
1266
1267 for (start = start->next; start != cond; start = start->next) {
1268 if (!(start->type & ITLABEL)) {
1269 tmp = INS(interp, unit, start->opname, "",
1270 start->symregs, start->symreg_count, start->keys, 0);
1271 prepend_ins(unit, branch, tmp);
1272 }
1273 }
1274
1275 for (count = 0; count != args; ++count) {
1276 regs[count] = cond->symregs[count];
1277 }
1278
1279 reg_index = get_branch_regno(cond);
1280 if (reg_index < 0)
1281 Parrot_ex_throw_from_c_args(interp, NULL, 1,
1282 "Negative branch register address detected");
1283
1284 regs[reg_index] = mk_label_address(interp, label);
1285 tmp = INS(interp, unit, (const char*)neg_op, "", regs, args, 0, 0);
1286
1287 IMCC_debug(interp, DEBUG_OPT1,
1288 "loop %s -> %s converted to post-test, added label %s\n",
1289 branch->symregs[0]->name, get_branch_reg(cond)->name, label);
1290
1291 subst_ins(unit, branch, tmp, 1);
1292 unit->ostat.branch_cond_loop++;
1293 changed = 1;
1294 }
1295
1296 free(label);
1297 }
1298
1299 return changed;
1300 }
1301
1302 /*
1303
1304 =item C<static int branch_cond_loop>
1305
1306 start: => start:
1307 if cond goto end if cond goto end
1308 ...
1309 branch start start_post1:
1310 end: ...
1311 unless cond goto start_post562
1312 end:
1313
1314 The basic premise is "branch (A) to conditional (B), where B goes to
1315 just after A."
1316
1317 Returns TRUE if any optimizations were performed. Otherwise, returns
1318 FALSE.
1319
1320 =cut
1321
1322 */
1323
1324 static int
1325 branch_cond_loop(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1326 {
1327 Instruction *ins, *cond, *start, *prev;
1328 int changed = 0, found;
1329
1330 IMCC_info(interp, 2, "\tbranch_cond_loop\n");
1331 /* reset statistic globals */
1332
1333 for (ins = unit->instructions; ins; ins = ins->next) {
1334 if ((ins->type & IF_goto) && STREQ(ins->opname, "branch")) {
1335 /* get `end` label */
1336 Instruction * const end = ins->next;
1337 /* get `start` label */
1338 SymReg * const r = get_sym(interp, ins->symregs[0]->name);
1339
1340 if (end && (end->type & ITLABEL) &&
1341 r && (r->type & VTADDRESS) && r->first_ins) {
1342
1343 start = r->first_ins;
1344 found = 0;
1345
1346 for (cond = start->next; cond; cond = cond->next) {
1347 /* no good if it's an unconditional branch*/
1348 if (cond->type & IF_goto && STREQ(cond->opname, "branch")) {
1349 break;
1350 } else if (cond->type & ITPCCRET || cond->type & ITPCCSUB
1351 || cond->type & ITCALL) {
1352 break;
1353 /* just until we can copy set_args et al */
1354 } else if (cond->type & ITBRANCH &&
1355 get_branch_regno(cond) >= 0) {
1356 found = 1;
1357 break;
1358 }
1359 }
1360
1361 if (found) {
1362 const char * const lbl = get_branch_reg(cond)->name;
1363 const SymReg * const r = get_sym(interp, lbl);
1364 if (r && (r->type & VTADDRESS) && r->first_ins == end) {
1365 /* the current ins is replaced - remember prev
1366 * and set ins again after the changes
1367 */
1368 prev = ins->prev;
1369 if (!prev)
1370 continue;
1371 changed |= branch_cond_loop_swap(interp,
1372 unit, ins, start, cond);
1373 ins = prev->next;
1374 }
1375 }
1376 }
1377 }
1378 }
1379 return changed;
1380 }
1381
1382 /*
1383
1384 =item C<static int unused_label>
1385
1386 Removes unused labels. A label is unused if ... [RT #46287: finish this].
1387
1388 Returns TRUE if any optimizations were performed. Otherwise, returns
1389 FALSE.
1390
1391 =cut
1392
1393 */
1394
1395 PARROT_WARN_UNUSED_RESULT
1396 static int
1397 unused_label(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1398 {
1399 unsigned int i;
1400 int used;
1401 int changed = 0;
1402
1403 IMCC_info(interp, 2, "\tunused_label\n");
1404 for (i = 1; i < unit->n_basic_blocks; i++) {
1405 Instruction *ins = unit->bb_list[i]->start;
1406 if ((ins->type & ITLABEL) && *ins->symregs[0]->name != '_') {
1407 const SymReg * const lab = ins->symregs[0];
1408 used = IMCC_INFO(interp)->has_compile ? 1 : 0;
1409
1410 if (!lab->first_ins)
1411 continue;
1412 #if 1
1413 else if (lab->last_ins)
1414 used = 1;
1415 #else
1416 else {
1417 Instruction *ins2;
1418 SymReg *addr;
1419 int j;
1420
1421 for (j=0; unit->bb_list[j]; j++) {
1422 /* a branch can be the first ins in a block
1423 * (if prev ins was a label)
1424 * or the last ins in a block */
1425 ins2 = unit->bb_list[j]->start;
1426 if ((ins2->type & ITBRANCH) &&
1427 (addr = get_branch_reg(ins2)) != 0) {
1428 if (addr == lab && addr->type == VTADDRESS) {
1429 used = 1;
1430 break;
1431 }
1432 }
1433 ins2 = unit->bb_list[j]->end;
1434 if ((ins2->type & ITBRANCH) &&
1435 (addr = get_branch_reg(ins2)) != 0) {
1436 if (addr == lab && addr->type == VTADDRESS) {
1437 used = 1;
1438 break;
1439 }
1440 }
1441 }
1442 }
1443 #endif
1444 if (!used) {
1445 unit->ostat.deleted_labels++;
1446 IMCC_debug(interp, DEBUG_OPT1,
1447 "block %d label %s deleted\n", i, lab->name);
1448 unit->ostat.deleted_ins++;
1449 ins = delete_ins(unit, ins);
1450 changed = 1;
1451 }
1452
1453 }
1454 }
1455 return changed;
1456 }
1457
1458 /*
1459
1460 =item C<static int dead_code_remove>
1461
1462 RT #48260: Not yet documented!!!
1463
1464 =cut
1465
1466 */
1467
1468 static int
1469 dead_code_remove(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1470 {
1471 unsigned int i;
1472 int changed = 0;
1473 Instruction *ins, *last;
1474
1475 /* this could be a separate level, now it's done with -O1 */
1476 if (!(IMCC_INFO(interp)->optimizer_level & OPT_PRE))
1477 return 0;
1478 IMCC_info(interp, 2, "\tdead_code_remove\n");
1479
1480 /* Unreachable blocks */
1481
1482 for (i = 1; i < unit->n_basic_blocks; i++) {
1483 Basic_block * const bb = unit->bb_list[i];
1484
1485 if ((bb->start->type & ITLABEL) && *bb->start->symregs[0]->name == '_')
1486 continue;
1487 /* this block isn't entered from anywhere */
1488 if (!bb->pred_list) {
1489 const int bbi = bb->index;
1490 IMCC_debug(interp, DEBUG_OPT1,
1491 "found dead block %d\n", bb->index);
1492 for (ins = bb->start; ins && ins->bbindex == bbi;) {
1493 IMCC_debug(interp, DEBUG_OPT1,
1494 "\tins deleted (dead block) %I\n", ins);
1495 ins = delete_ins(unit, ins);
1496 unit->ostat.deleted_ins++;
1497 changed++;
1498 }
1499 }
1500 }
1501
1502 /* Unreachable instructions */
1503
1504 for (last = unit->instructions, ins=last->next;
1505 last && ins;
1506 ins = ins->next) {
1507 if ((last->type & IF_goto) && !(ins->type & ITLABEL) &&
1508 STREQ(last->opname, "branch")) {
1509 IMCC_debug(interp, DEBUG_OPT1,
1510 "unreachable ins deleted (after branch) %I\n", ins);
1511 ins = delete_ins(unit, ins);
1512 unit->ostat.deleted_ins++;
1513 changed++;
1514 }
1515 /*
1516 * branch L1 => --
1517 * L1: ... L1:
1518 */
1519 if (ins && last && (last->type & IF_goto) && (ins->type & ITLABEL) &&
1520 STREQ(last->opname, "branch") &&
1521 STREQ(last->symregs[0]->name, ins->symregs[0]->name)) {
1522 IMCC_debug(interp, DEBUG_OPT1, "dead branch deleted %I\n", ins);
1523 ins = delete_ins(unit, last);
1524 unit->ostat.deleted_ins++;
1525 changed++;
1526 }
1527 last = ins;
1528 if (!ins)
1529 break;
1530 }
1531 return changed;
1532 }
1533
1534 /* optimizations with CFG & life info built */
1535 /*
1536
1537 =item C<static int used_once>
1538
1539 RT #48260: Not yet documented!!!
1540
1541 =cut
1542
1543 */
1544
1545 static int
1546 used_once(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1547 {
1548 Instruction *ins;
1549 int opt = 0;
1550
1551 for (ins = unit->instructions; ins; ins = ins->next) {
1552 if (ins->symregs) {
1553 SymReg * const r = ins->symregs[0];
1554 if (r && (r->use_count == 1 && r->lhs_use_count == 1)) {
1555 IMCC_debug(interp, DEBUG_OPT2, "used once '%I' deleted\n", ins);
1556 ins = delete_ins(unit, ins);
1557 ins = ins->prev ? ins->prev : unit->instructions;
1558 unit->ostat.deleted_ins++;
1559 unit->ostat.used_once++;
1560 opt++;
1561 }
1562 }
1563 }
1564 return opt;
1565 }
1566
1567 #if DO_LOOP_OPTIMIZATION
1568
1569 static int reason;
1570 enum check_t { CHK_INV_NEW, CHK_INV_SET, CHK_CLONE };
1571
1572 /*
1573
1574 =item C<static int _is_ins_save>
1575
1576 RT #48260: Not yet documented!!!
1577
1578 =cut
1579
1580 */
1581
1582 PARROT_WARN_UNUSED_RESULT
1583 static int
1584 _is_ins_save(ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *check_ins),
1585 ARGIN(const SymReg *r), int what)
1586 {
1587 Instruction *ins;
1588 int bb;
1589 int use_count, lhs_use_count;
1590 int i, in_use;
1591 int new_bl=-1, set_bl=-1;
1592
1593 /* now check all instructions where r is used */
1594
1595 /* we give up fast ;-) */
1596 switch (what) {
1597 case CHK_INV_NEW:
1598 case CHK_INV_SET:
1599 if (r->set == 'P' && r->lhs_use_count != 2)
1600 return reason=1, 0;
1601 if (r->set != 'P' && r->lhs_use_count != 1)
1602 return reason=2, 0;
1603 break;
1604 case CHK_CLONE:
1605 if (r->set == 'P' && r->lhs_use_count != 2)
1606 return reason=1, 0;
1607 break;
1608 default:
1609 break;
1610 }
1611
1612 use_count = r->use_count;
1613 lhs_use_count = r->lhs_use_count;
1614 for (bb = 0; bb < unit->n_basic_blocks; bb++) {
1615 const Life_range * const lr = r->life_info[bb];
1616
1617 for (ins = lr->first_ins; ins; ins = ins->next) {
1618 int nregs;
1619 /* finished with this range */
1620 if (!lr->last_ins->next || ins == lr->last_ins->next)
1621 break;
1622 for (i = in_use = 0; ins->symregs[i]; i++)
1623 if (ins->symregs[i] == r) {
1624 in_use++;
1625 }
1626 nregs = i;
1627 if (!in_use)
1628 continue;
1629
1630 /* var is in use in this ins */
1631 use_count--;
1632 if (instruction_writes(ins, r)) {
1633 lhs_use_count--;
1634 if (STREQ(ins->opname, "new"))
1635 new_bl=bb;
1636 if (STREQ(ins->opname, ""))
1637 set_bl=bb;
1638 }
1639 /* this is the instruction, to check, it's safe */
1640 if (check_ins == ins)
1641 continue;
1642
1643 /* now look for dangerous ops */
1644 if (STREQ(ins->opname, "find_global"))
1645 return reason=4, 0;
1646 if (STREQ(ins->opname, "store_global"))
1647 return reason=4, 0;
1648 if (STREQ(ins->opname, "push"))
1649 return reason=4, 0;
1650 if (STREQ(ins->opname, "pop"))
1651 return reason=4, 0;
1652 if (STREQ(ins->opname, "clone"))
1653 return reason=4, 0;
1654 /* indexed set/get ??? RT #46289, as index is ok */
1655 if (0 && STREQ(ins->opname, "set") && nregs != 2)
1656 return reason=5, 0;
1657 /*
1658 * set P, P - dangerous?
1659 */
1660 if (ins->type & ITALIAS)
1661 return reason=6, 0;
1662 /* we saw all occurencies of reg, so fine */
1663 if (lhs_use_count == 0 && use_count == 0) {
1664 if (what == CHK_INV_SET && new_bl != set_bl)
1665 return 0;
1666 return 1;
1667 }
1668 }
1669 /* we have finished this life range */
1670 } /* for bb */
1671 return what == CHK_CLONE ? 1 : (reason=10, 0);
1672 }
1673
1674 /*
1675
1676 =item C<static int is_ins_save>
1677
1678 RT #48260: Not yet documented!!!
1679
1680 =cut
1681
1682 */
1683
1684 PARROT_WARN_UNUSED_RESULT
1685 static int
1686 is_ins_save(PARROT_INTERP, ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *ins),
1687 ARGIN(const SymReg *r), int what)
1688 {
1689 int save;
1690
1691 reason = 0;
1692 save = _is_ins_save(unit, ins, r, what);
1693 if (!save && reason)
1694 IMCC_debug(interp, DEBUG_OPT2,
1695 "ins not save var %s reason %d %I\n",
1696 r->name, reason, ins);
1697 return save;
1698 }
1699
1700 /*
1701
1702 =item C<int max_loop_depth>
1703
1704 RT #48260: Not yet documented!!!
1705
1706 =cut
1707
1708 */
1709
1710 PARROT_WARN_UNUSED_RESULT
1711 int
1712 max_loop_depth(ARGIN(const IMC_Unit *unit))
1713 {
1714 int i;
1715 int d = 0;
1716
1717 for (i = 0; i < unit->n_basic_blocks; i++)
1718 if (unit->bb_list[i]->loop_depth > d)
1719 d = unit->bb_list[i]->loop_depth;
1720 return d;
1721 }
1722
1723 /*
1724
1725 =item C<int is_invariant>
1726
1727 RT #48260: Not yet documented!!!
1728
1729 =cut
1730
1731 */
1732
1733 int
1734 is_invariant(PARROT_INTERP, ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *ins))
1735 {
1736 int ok = 0;
1737 int what = 0;
1738
1739 if (STREQ(ins->opname, "new")) {
1740 ok = 1;
1741 what = CHK_INV_NEW;
1742 }
1743 /* only, if once assigned and not changed */
1744 else if (STREQ(ins->opname, "set") &&
1745 !(ins->symregs[0]->usage & U_KEYED) &&
1746 ins->symregs[1]->type & VTCONST) {
1747 ok = 1;
1748 what = CHK_INV_SET;
1749 }
1750 if (ok)
1751 return is_ins_save(interp, unit, ins, ins->symregs[0], what);
1752 return 0;
1753 }
1754
1755 # define MOVE_INS_1_BL
1756 # ifdef MOVE_INS_1_BL
1757 /*
1758
1759 =item C<Basic_block * find_outer>
1760
1761 RT #48260: Not yet documented!!!
1762
1763 =cut
1764
1765 */
1766
1767 PARROT_WARN_UNUSED_RESULT
1768 PARROT_CAN_RETURN_NULL
1769 Basic_block *
1770 find_outer(ARGIN(const IMC_Unit *unit), ARGIN(const Basic_block *blk))
1771 {
1772 int i;
1773 Loop_info ** const loop_info = unit->loop_info;
1774 const int bb = blk->index;
1775 int i = unit->n_loops - 1;
1776
1777 /* loops are sorted depth last */
1778 for (; i >= 0; i--) {
1779 Loop_info * const info = loop_info[i];
1780 if (set_contains(info->loop, bb)) {
1781 const int preheader = info->preheader;
1782 if (preheader >= 0)
1783 return unit->bb_list[preheader];
1784 }
1785 }
1786 return NULL;
1787 }
1788 # endif
1789
1790 /*
1791
1792 =item C<int move_ins_out>
1793
1794 move the instruction ins before loop in bb
1795
1796 =cut
1797
1798 */
1799
1800 int
1801 move_ins_out(PARROT_INTERP, ARGMOD(IMC_Unit *unit),
1802 ARGMOD(Instruction **ins), ARGIN(const Basic_block *bb))
1803 {
1804 Basic_block *pred;
1805 Instruction * next, *out;
1806
1807 /* check loop_info, where this loop started
1808 * actually, this moves instruction to block 0 */
1809 # ifdef MOVE_INS_1_BL
1810 pred = find_outer(unit, bb);
1811 # else
1812 UNUSED(bb);
1813 pred = unit->bb_list[0];
1814 # endif
1815 if (!pred) {
1816 IMCC_debug(interp, DEBUG_OPT2, "outer loop not found (CFG?)\n");
1817 return 0;
1818 }
1819 out = pred->end;
1820 next = (*ins)->next;
1821 (*ins)->bbindex = pred->index;
1822 IMCC_debug(interp, DEBUG_OPT2, "inserting it in blk %d after %I\n",
1823 pred->index, out);
1824 *ins = move_ins(unit, *ins, out);
1825 if (0 && (DEBUG_OPT2 & IMCC_INFO(interp)->debug)) {
1826 char buf[256];
1827 SymReg * regs[IMCC_MAX_REGS];
1828 Instruction * tmp;
1829
1830 regs[0] = 0;
1831 snprintf(buf, sizeof (buf), "# Invar moved: %s", out->next->op);
1832 tmp = INS(interp, unit, "", buf, regs, 0, 0, 0);
1833 insert_ins(unit, (*ins)->prev, tmp);
1834 }
1835 ostat.invariants_moved++;
1836 /* RT #46291 CFG is changed here, which also means
1837 * that the life_info is wrong now
1838 * so, currently we calc CFG and life again */
1839 return 1;
1840 }
1841
1842 /*
1843
1844 =item C<int loop_one>
1845
1846 RT #48260: Not yet documented!!!
1847
1848 =cut
1849
1850 */
1851
1852 int
1853 loop_one(PARROT_INTERP, ARGMOD(IMC_Unit *unit), int bnr)
1854 {
1855 Basic_block * const bb = unit->bb_list[bnr];
1856 Instruction *ins;
1857 int changed = 0;
1858
1859 if (bnr == 0) {
1860 IMCC_warning(interp, "loop_one", "wrong loop depth in block 0\n");
1861 return 0;
1862 }
1863 IMCC_debug(interp, DEBUG_OPT2, "loop_one blk %d\n", bnr);
1864 for (ins = bb->start ; ins ; ins = ins->next) {
1865 reason = 0;
1866 if (is_invariant(interp, unit, ins)) {
1867 IMCC_debug(interp, DEBUG_OPT2, "found invariant %I\n", ins);
1868 if (move_ins_out(interp, unit, &ins, bb)) {
1869 changed++;
1870 ins = ins->prev;
1871 }
1872 }
1873 if (ins == bb->end)
1874 break;
1875 }
1876 return changed;
1877
1878 }
1879
1880 /*
1881
1882 =item C<int loop_optimization>
1883
1884 RT #48260: Not yet documented!!!
1885
1886 =cut
1887
1888 */
1889
1890 int
1891 loop_optimization(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1892 {
1893 int l;
1894 int changed = 0;
1895 static int prev_depth;
1896
1897 const int loop_depth = prev_depth ? prev_depth : max_loop_depth(unit);
1898
1899 /* work from inside out */
1900 IMCC_debug(interp, DEBUG_OPT2, "loop_optimization\n");
1901 for (l = loop_depth; l > 0; l--) {
1902 int bb;
1903
1904 IMCC_debug(interp, DEBUG_OPT2, "loop_depth %d\n", l);
1905 for (bb = 0; bb < unit->n_basic_blocks; bb++)
1906 if (unit->bb_list[bb]->loop_depth == l) {
1907 changed |= loop_one(interp, unit, bb);
1908 }
1909 /* currently e.g. mandel.p6 breaks, if not only the most
1910 * inner loop is changed, but outer loops too */
1911 if (changed) {
1912 prev_depth = l-1;
1913 IMCC_debug(interp, DEBUG_OPT2, "after loop_opt\n");
1914 if (IMCC_INFO(interp)->debug>1)
1915 dump_instructions(interp, unit);
1916 return changed;
1917 }
1918 }
1919 prev_depth = 0;
1920 return 0;
1921 }
1922 #endif
1923
1924 /*
1925
1926 =back
1927
1928 =cut
1929
1930 */
1931
1932 /*
1933 * Local variables:
1934 * c-file-style: "parrot"
1935 * End:
1936 * vim: expandtab shiftwidth=4:
1937 */
parrot vm git mirror