?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
tagged release 0.6.4
[parrot.git] / compilers / imcc / optimizer.c
blob721e8e0381deeae2a54924a5110edd01746db810
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_internal_exception(interp);
876 if (setjmp(interp->exceptions->destination))
877 return -1;
878
879 pc = (interp->op_func_table[opnum]) (eval, interp);
880 free_internal_exception(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 r[1]->type & (VTCONST|VT_CONSTP) &&
974 STREQ(name, ops2[i])) {
975 found = 3;
976 snprintf(op, sizeof (op), "%s_%c_%c", name, tolower((unsigned char)r[0]->set),
977 tolower((unsigned char)r[1]->set));
978 debug_fmt = "opt %s_x_xc => ";
979 break;
980 }
981 }
982 for (i = 0; !found && i < N_ELEMENTS(ops3); i++) {
983 /*
984 * eq_xc_xc_labelc ...
985 */
986 if (n == 4 &&
987 r[0]->type & (VTCONST|VT_CONSTP) &&
988 r[1]->type & (VTCONST|VT_CONSTP) &&
989 STREQ(name, ops3[i])) {
990 found = 2;
991 snprintf(op, sizeof (op), "%s_%c_%c_ic", name, tolower((unsigned char)r[0]->set),
992 tolower((unsigned char)r[1]->set));
993 debug_fmt = "opt %s_xc_xc_ic => ";
994 break;
995 }
996 }
997 for (i = 0; !found && i < N_ELEMENTS(ops4); i++) {
998 /*
999 * if_xc_labelc, unless
1000 */
1001 if (n == 3 &&
1002 r[0]->type & (VTCONST|VT_CONSTP) &&
1003 STREQ(name, ops4[i])) {
1004 found = 1;
1005 snprintf(op, sizeof (op), "%s_%c_ic", name, tolower((unsigned char)r[0]->set));
1006 debug_fmt = "opt %s_xc_ic => ";
1007 break;
1008 }
1009 }
1010
1011 if (!found) {
1012 *ok = 0;
1013 return NULL;
1014 }
1015
1016 IMCC_debug(interp, DEBUG_OPT1, debug_fmt, name);
1017 /* we construct a parrot instruction
1018 * here and let parrot do the calculation in a
1019 * separate context and make a constant
1020 * from the result
1021 */
1022 branched = eval_ins(interp, op, found, r);
1023 if (branched == -1) {
1024 /* Don't set ok (See RT #43048 for info) */
1025 return NULL;
1026 }
1027 /*
1028 * for math ops result is in I0/N0
1029 * if it was a branch with constant args, the result is
1030 * the return value
1031 */
1032 if (found <= 2) {
1033 /*
1034 * create a branch or delete instruction
1035 */
1036 if (branched) {
1037 r[0] = r[found];
1038 tmp = INS(interp, unit, "branch", "", r, 1, 0, 0);
1039 }
1040 else {
1041 IMCC_debug(interp, DEBUG_OPT1, "deleted\n");
1042 }
1043 }
1044 else {
1045 /*
1046 * create set x, constant
1047 */
1048 char b[128];
1049 switch (r[0]->set) {
1050 case 'I':
1051 snprintf(b, sizeof (b), INTVAL_FMT, REG_INT(interp, 0));
1052 r[1] = mk_const(interp, b, r[0]->set);
1053 break;
1054 case 'N':
1055 snprintf(b, sizeof (b), fmt, REG_NUM(interp, 0));
1056 r[1] = mk_const(interp, b, r[0]->set);
1057 break;
1058 case 'S':
1059 r[1] = mk_const(interp, string_to_cstring(interp,
1060 REG_STR(interp, 0)), r[0]->set);
1061 snprintf(b, sizeof (b), "%p", REG_STR(interp, 0));
1062 break;
1063 default:
1064 break;
1065 }
1066 tmp = INS(interp, unit, "set", "", r, 2, 0, 0);
1067 }
1068 if (tmp) {
1069 IMCC_debug(interp, DEBUG_OPT1, "%I\n", tmp);
1070 }
1071 *ok = 1;
1072 return tmp;
1073 }
1074
1075
1076 /* optimizations with CFG built */
1077
1078 /*
1079
1080 =item C<static int branch_branch>
1081
1082 if I0 goto L1 => if IO goto L2
1083 ...
1084 L1:
1085 branch L2
1086
1087 Returns TRUE if any optimizations were performed. Otherwise, returns
1088 FALSE.
1089
1090 =cut
1091
1092 */
1093
1094 static int
1095 branch_branch(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1096 {
1097 Instruction *ins;
1098 int changed = 0;
1099
1100 IMCC_info(interp, 2, "\tbranch_branch\n");
1101 /* reset statistic globals */
1102 for (ins = unit->instructions; ins; ins = ins->next) {
1103 if (get_branch_regno(ins) >= 0) {
1104 SymReg * const r = get_sym(interp, get_branch_reg(ins)->name);
1105
1106 if (r && (r->type & VTADDRESS) && r->first_ins) {
1107 Instruction * const next = r->first_ins->next;
1108 /* if (!next ||
1109 STREQ(next->symregs[0]->name, get_branch_reg(ins)->name))
1110 break;*/
1111 if (next &&
1112 (next->type & IF_goto) &&
1113 STREQ(next->opname, "branch") &&
1114 !STREQ(next->symregs[0]->name, get_branch_reg(ins)->name)) {
1115 const int regno = get_branch_regno(ins);
1116 IMCC_debug(interp, DEBUG_OPT1,
1117 "found branch to branch '%s' %I\n",
1118 r->first_ins->symregs[0]->name, next);
1119 unit->ostat.branch_branch++;
1120 if (regno < 0) {
1121 real_exception(interp, NULL, 1,
1122 "Register number determination failed in branch_branch()");
1123 }
1124 ins->symregs[regno] = next->symregs[0];
1125 changed = 1;
1126 }
1127 }
1128 }
1129 }
1130 return changed;
1131 }
1132
1133 /*
1134
1135 =item C<static int branch_reorg>
1136
1137 branch L2 => ...
1138 L1: branch L4
1139 ... L1:
1140 branch L3 ...
1141 L2: branch L3
1142 ... L5:
1143 branch L4
1144 L5:
1145
1146 Returns TRUE if any optimizations were performed. Otherwise, returns
1147 FALSE.
1148
1149 =cut
1150
1151 */
1152
1153 PARROT_WARN_UNUSED_RESULT
1154 static int
1155 branch_reorg(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1156 {
1157 unsigned int i;
1158 int changed = 0;
1159
1160 IMCC_info(interp, 2, "\tbranch_reorg\n");
1161 for (i = 0; i < unit->n_basic_blocks; i++) {
1162 Instruction *ins = unit->bb_list[i]->end;
1163
1164 /* if basic block ends with unconditional jump */
1165 if ((ins->type & IF_goto) && STREQ(ins->opname, "branch")) {
1166 SymReg * const r = get_sym(interp, ins->symregs[0]->name);
1167 if (r && (r->type & VTADDRESS) && r->first_ins) {
1168 Edge *edge;
1169 Instruction * const start = r->first_ins;
1170 int found = 0;
1171 for (edge = unit->bb_list[start->bbindex]->pred_list;
1172 edge; edge = edge->pred_next)
1173 {
1174 if (edge->from->index == start->bbindex - 1) {
1175 found = 1;
1176 break;
1177 }
1178 }
1179 /* if target block is not reached by falling into it
1180 * from another block */
1181 if (!found) {
1182 Instruction *end;
1183 /* move target block and its positional successors
1184 * to follow block with unconditional jump
1185 * (this could actually be in another block) */
1186 for (end = start; end->next; end = end->next) {
1187 if ((end->type & IF_goto) &&
1188 STREQ(end->opname, "branch")) {
1189 break;
1190 }
1191 }
1192
1193 /* this was screwing up multi-block loops... */
1194 if (end != ins && ins->next != NULL) {
1195 ins->next->prev = end;
1196 start->prev->next = end->next;
1197 if (end->next)
1198 end->next->prev = start->prev;
1199 end->next = ins->next;
1200 ins->next = start;
1201 start->prev = ins;
1202 IMCC_debug(interp, DEBUG_OPT1,
1203 "found branch to reorganize '%s' %I\n",
1204 r->first_ins->symregs[0]->name, ins);
1205 /* unconditional jump can be eliminated */
1206 unit->ostat.deleted_ins++;
1207 ins = delete_ins(unit, ins);
1208 return 1;
1209 }
1210 }
1211 }
1212 }
1213 }
1214 return changed;
1215 }
1216
1217 /*
1218
1219 =item C<static int branch_cond_loop_swap>
1220
1221 RT#48260: Not yet documented!!!
1222
1223 =cut
1224
1225 */
1226
1227 PARROT_WARN_UNUSED_RESULT
1228 static int
1229 branch_cond_loop_swap(PARROT_INTERP, ARGMOD(IMC_Unit *unit), ARGMOD(Instruction *branch),
1230 ARGMOD(Instruction *start), ARGMOD(Instruction *cond))
1231 {
1232 int changed = 0;
1233 int args;
1234 const char * const neg_op = get_neg_op(cond->opname, &args);
1235 if (neg_op) {
1236 const size_t size = strlen(branch->symregs[0]->name) + 10; /* + '_post999' */
1237 char * const label = (char *)mem_sys_allocate(size);
1238 int count;
1239 int found = 0;
1240
1241 for (count = 1; count != 999; ++count) {
1242 snprintf(label, size, "%s_post%d", branch->symregs[0]->name, count);
1243 if (get_sym(interp, label) == 0) {
1244 found = 1;
1245 break;
1246 }
1247 }
1248
1249 if (found) {
1250 Instruction *tmp;
1251 SymReg *regs[3], *r;
1252 int reg_index;
1253
1254 /* cond_op has 2 or 3 args */
1255 PARROT_ASSERT(args <= 3);
1256
1257 r = mk_local_label(interp, label);
1258 tmp = INS_LABEL(interp, unit, r, 0);
1259 insert_ins(unit, cond, tmp);
1260
1261 for (start = start->next; start != cond; start = start->next) {
1262 if (!(start->type & ITLABEL)) {
1263 tmp = INS(interp, unit, start->opname, "",
1264 start->symregs, start->symreg_count, start->keys, 0);
1265 prepend_ins(unit, branch, tmp);
1266 }
1267 }
1268
1269 for (count = 0; count != args; ++count) {
1270 regs[count] = cond->symregs[count];
1271 }
1272
1273 reg_index = get_branch_regno(cond);
1274 if (reg_index < 0) {
1275 real_exception(interp, NULL, 1,
1276 "Negative branch register address detected");
1277 }
1278 regs[reg_index] = mk_label_address(interp, label);
1279 tmp = INS(interp, unit, (const char*)neg_op, "", regs, args, 0, 0);
1280
1281 IMCC_debug(interp, DEBUG_OPT1,
1282 "loop %s -> %s converted to post-test, added label %s\n",
1283 branch->symregs[0]->name, get_branch_reg(cond)->name, label);
1284
1285 subst_ins(unit, branch, tmp, 1);
1286 unit->ostat.branch_cond_loop++;
1287 changed = 1;
1288 }
1289
1290 free(label);
1291 }
1292
1293 return changed;
1294 }
1295
1296 /*
1297
1298 =item C<static int branch_cond_loop>
1299
1300 start: => start:
1301 if cond goto end if cond goto end
1302 ...
1303 branch start start_post1:
1304 end: ...
1305 unless cond goto start_post562
1306 end:
1307
1308 The basic premise is "branch (A) to conditional (B), where B goes to
1309 just after A."
1310
1311 Returns TRUE if any optimizations were performed. Otherwise, returns
1312 FALSE.
1313
1314 =cut
1315
1316 */
1317
1318 static int
1319 branch_cond_loop(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1320 {
1321 Instruction *ins, *cond, *start, *prev;
1322 int changed = 0, found;
1323
1324 IMCC_info(interp, 2, "\tbranch_cond_loop\n");
1325 /* reset statistic globals */
1326
1327 for (ins = unit->instructions; ins; ins = ins->next) {
1328 if ((ins->type & IF_goto) && STREQ(ins->opname, "branch")) {
1329 /* get `end` label */
1330 Instruction * const end = ins->next;
1331 /* get `start` label */
1332 SymReg * const r = get_sym(interp, ins->symregs[0]->name);
1333
1334 if (end && (end->type & ITLABEL) &&
1335 r && (r->type & VTADDRESS) && r->first_ins) {
1336
1337 start = r->first_ins;
1338 found = 0;
1339
1340 for (cond = start->next; cond; cond = cond->next) {
1341 /* no good if it's an unconditional branch*/
1342 if (cond->type & IF_goto && STREQ(cond->opname, "branch")) {
1343 break;
1344 } else if (cond->type & ITPCCRET || cond->type & ITPCCSUB
1345 || cond->type & ITCALL) {
1346 break;
1347 /* just until we can copy set_args et al */
1348 } else if (cond->type & ITBRANCH &&
1349 get_branch_regno(cond) >= 0) {
1350 found = 1;
1351 break;
1352 }
1353 }
1354
1355 if (found) {
1356 const char * const lbl = get_branch_reg(cond)->name;
1357 const SymReg * const r = get_sym(interp, lbl);
1358 if (r && (r->type & VTADDRESS) && r->first_ins == end) {
1359 /* the current ins is replaced - remember prev
1360 * and set ins again after the changes
1361 */
1362 prev = ins->prev;
1363 if (!prev)
1364 continue;
1365 changed |= branch_cond_loop_swap(interp,
1366 unit, ins, start, cond);
1367 ins = prev->next;
1368 }
1369 }
1370 }
1371 }
1372 }
1373 return changed;
1374 }
1375
1376 /*
1377
1378 =item C<static int unused_label>
1379
1380 Removes unused labels. A label is unused if ... [RT#46287: finish this].
1381
1382 Returns TRUE if any optimizations were performed. Otherwise, returns
1383 FALSE.
1384
1385 =cut
1386
1387 */
1388
1389 PARROT_WARN_UNUSED_RESULT
1390 static int
1391 unused_label(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1392 {
1393 int used;
1394 unsigned int i;
1395 int changed = 0;
1396
1397 IMCC_info(interp, 2, "\tunused_label\n");
1398 for (i = 1; i < unit->n_basic_blocks; i++) {
1399 Instruction *ins = unit->bb_list[i]->start;
1400 if ((ins->type & ITLABEL) && *ins->symregs[0]->name != '_') {
1401 const SymReg * const lab = ins->symregs[0];
1402 used = 0;
1403 if (IMCC_INFO(interp)->has_compile)
1404 used = 1;
1405 if (!lab->first_ins)
1406 continue;
1407 #if 1
1408 else if (lab->last_ins)
1409 used = 1;
1410 #else
1411 else {
1412 Instruction *ins2;
1413 int j;
1414 SymReg * addr;
1415 for (j=0; unit->bb_list[j]; j++) {
1416 /* a branch can be the first ins in a block
1417 * (if prev ins was a label)
1418 * or the last ins in a block
1419 */
1420 ins2 = unit->bb_list[j]->start;
1421 if ((ins2->type & ITBRANCH) &&
1422 (addr = get_branch_reg(ins2)) != 0) {
1423 if (addr == lab && addr->type == VTADDRESS) {
1424 used = 1;
1425 break;
1426 }
1427 }
1428 ins2 = unit->bb_list[j]->end;
1429 if ((ins2->type & ITBRANCH) &&
1430 (addr = get_branch_reg(ins2)) != 0) {
1431 if (addr == lab && addr->type == VTADDRESS) {
1432 used = 1;
1433 break;
1434 }
1435 }
1436 }
1437 }
1438 #endif
1439 if (!used) {
1440 unit->ostat.deleted_labels++;
1441 IMCC_debug(interp, DEBUG_OPT1,
1442 "block %d label %s deleted\n", i, lab->name);
1443 unit->ostat.deleted_ins++;
1444 ins = delete_ins(unit, ins);
1445 changed = 1;
1446 }
1447
1448 }
1449 }
1450 return changed;
1451 }
1452
1453 /*
1454
1455 =item C<static int dead_code_remove>
1456
1457 RT#48260: Not yet documented!!!
1458
1459 =cut
1460
1461 */
1462
1463 static int
1464 dead_code_remove(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1465 {
1466 unsigned int i;
1467 int changed = 0;
1468 Instruction *ins, *last;
1469
1470 /* this could be a separate level, now it's done with -O1 */
1471 if (!(IMCC_INFO(interp)->optimizer_level & OPT_PRE))
1472 return 0;
1473 IMCC_info(interp, 2, "\tdead_code_remove\n");
1474
1475 /* Unreachable blocks */
1476
1477 for (i = 1; i < unit->n_basic_blocks; i++) {
1478 Basic_block * const bb = unit->bb_list[i];
1479
1480 if ((bb->start->type & ITLABEL) && *bb->start->symregs[0]->name == '_')
1481 continue;
1482 /* this block isn't entered from anywhere */
1483 if (!bb->pred_list) {
1484 const int bbi = bb->index;
1485 IMCC_debug(interp, DEBUG_OPT1,
1486 "found dead block %d\n", bb->index);
1487 for (ins = bb->start; ins && ins->bbindex == bbi;) {
1488 IMCC_debug(interp, DEBUG_OPT1,
1489 "\tins deleted (dead block) %I\n", ins);
1490 ins = delete_ins(unit, ins);
1491 unit->ostat.deleted_ins++;
1492 changed++;
1493 }
1494 }
1495 }
1496
1497 /* Unreachable instructions */
1498
1499 for (last = unit->instructions, ins=last->next;
1500 last && ins;
1501 ins = ins->next) {
1502 if ((last->type & IF_goto) && !(ins->type & ITLABEL) &&
1503 STREQ(last->opname, "branch")) {
1504 IMCC_debug(interp, DEBUG_OPT1,
1505 "unreachable ins deleted (after branch) %I\n", ins);
1506 ins = delete_ins(unit, ins);
1507 unit->ostat.deleted_ins++;
1508 changed++;
1509 }
1510 /*
1511 * branch L1 => --
1512 * L1: ... L1:
1513 */
1514 if (ins && last && (last->type & IF_goto) && (ins->type & ITLABEL) &&
1515 STREQ(last->opname, "branch") &&
1516 STREQ(last->symregs[0]->name, ins->symregs[0]->name)) {
1517 IMCC_debug(interp, DEBUG_OPT1, "dead branch deleted %I\n", ins);
1518 ins = delete_ins(unit, last);
1519 unit->ostat.deleted_ins++;
1520 changed++;
1521 }
1522 last = ins;
1523 if (!ins)
1524 break;
1525 }
1526 return changed;
1527 }
1528
1529 /* optimizations with CFG & life info built */
1530 /*
1531
1532 =item C<static int used_once>
1533
1534 RT#48260: Not yet documented!!!
1535
1536 =cut
1537
1538 */
1539
1540 static int
1541 used_once(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1542 {
1543 Instruction *ins;
1544 int opt = 0;
1545
1546 for (ins = unit->instructions; ins; ins = ins->next) {
1547 if (ins->symregs) {
1548 SymReg * const r = ins->symregs[0];
1549 if (r && (r->use_count == 1 && r->lhs_use_count == 1)) {
1550 IMCC_debug(interp, DEBUG_OPT2, "used once '%I' deleted\n", ins);
1551 ins = delete_ins(unit, ins);
1552 ins = ins->prev ? ins->prev : unit->instructions;
1553 unit->ostat.deleted_ins++;
1554 unit->ostat.used_once++;
1555 opt++;
1556 }
1557 }
1558 }
1559 return opt;
1560 }
1561
1562 #if DO_LOOP_OPTIMIZATION
1563
1564 static int reason;
1565 enum check_t { CHK_INV_NEW, CHK_INV_SET, CHK_CLONE };
1566
1567 /*
1568
1569 =item C<static int _is_ins_save>
1570
1571 RT#48260: Not yet documented!!!
1572
1573 =cut
1574
1575 */
1576
1577 PARROT_WARN_UNUSED_RESULT
1578 static int
1579 _is_ins_save(ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *check_ins),
1580 ARGIN(const SymReg *r), int what)
1581 {
1582 Instruction *ins;
1583 int bb;
1584 int use_count, lhs_use_count;
1585 int i, in_use;
1586 int new_bl=-1, set_bl=-1;
1587
1588 /* now check all instructions where r is used */
1589
1590 /* we give up fast ;-) */
1591 switch (what) {
1592 case CHK_INV_NEW:
1593 case CHK_INV_SET:
1594 if (r->set == 'P' && r->lhs_use_count != 2)
1595 return reason=1, 0;
1596 if (r->set != 'P' && r->lhs_use_count != 1)
1597 return reason=2, 0;
1598 break;
1599 case CHK_CLONE:
1600 if (r->set == 'P' && r->lhs_use_count != 2)
1601 return reason=1, 0;
1602 break;
1603 default:
1604 break;
1605 }
1606
1607 use_count = r->use_count;
1608 lhs_use_count = r->lhs_use_count;
1609 for (bb = 0; bb < unit->n_basic_blocks; bb++) {
1610 const Life_range * const lr = r->life_info[bb];
1611
1612 for (ins = lr->first_ins; ins; ins = ins->next) {
1613 int nregs;
1614 /* finished with this range */
1615 if (!lr->last_ins->next || ins == lr->last_ins->next)
1616 break;
1617 for (i = in_use = 0; ins->symregs[i]; i++)
1618 if (ins->symregs[i] == r) {
1619 in_use++;
1620 }
1621 nregs = i;
1622 if (!in_use)
1623 continue;
1624
1625 /* var is in use in this ins */
1626 use_count--;
1627 if (instruction_writes(ins, r)) {
1628 lhs_use_count--;
1629 if (STREQ(ins->opname, "new"))
1630 new_bl=bb;
1631 if (STREQ(ins->opname, ""))
1632 set_bl=bb;
1633 }
1634 /* this is the instruction, to check, it's safe */
1635 if (check_ins == ins)
1636 continue;
1637
1638 /* now look for dangerous ops */
1639 if (STREQ(ins->opname, "find_global"))
1640 return reason=4, 0;
1641 if (STREQ(ins->opname, "store_global"))
1642 return reason=4, 0;
1643 if (STREQ(ins->opname, "push"))
1644 return reason=4, 0;
1645 if (STREQ(ins->opname, "pop"))
1646 return reason=4, 0;
1647 if (STREQ(ins->opname, "clone"))
1648 return reason=4, 0;
1649 /* indexed set/get ??? RT#46289, as index is ok */
1650 if (0 && STREQ(ins->opname, "set") && nregs != 2)
1651 return reason=5, 0;
1652 /*
1653 * set P, P - dangerous?
1654 */
1655 if (ins->type & ITALIAS)
1656 return reason=6, 0;
1657 /* we saw all occurencies of reg, so fine */
1658 if (lhs_use_count == 0 && use_count == 0) {
1659 if (what == CHK_INV_SET && new_bl != set_bl)
1660 return 0;
1661 return 1;
1662 }
1663 }
1664 /* we have finished this life range */
1665 } /* for bb */
1666 return what == CHK_CLONE ? 1 : (reason=10, 0);
1667 }
1668
1669 /*
1670
1671 =item C<static int is_ins_save>
1672
1673 RT#48260: Not yet documented!!!
1674
1675 =cut
1676
1677 */
1678
1679 PARROT_WARN_UNUSED_RESULT
1680 static int
1681 is_ins_save(PARROT_INTERP, ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *ins),
1682 ARGIN(const SymReg *r), int what)
1683 {
1684 int save;
1685
1686 reason = 0;
1687 save = _is_ins_save(unit, ins, r, what);
1688 if (!save && reason)
1689 IMCC_debug(interp, DEBUG_OPT2,
1690 "ins not save var %s reason %d %I\n",
1691 r->name, reason, ins);
1692 return save;
1693 }
1694
1695 /*
1696
1697 =item C<int max_loop_depth>
1698
1699 RT#48260: Not yet documented!!!
1700
1701 =cut
1702
1703 */
1704
1705 PARROT_WARN_UNUSED_RESULT
1706 int
1707 max_loop_depth(ARGIN(const IMC_Unit *unit))
1708 {
1709 int i;
1710 int d = 0;
1711
1712 for (i = 0; i < unit->n_basic_blocks; i++)
1713 if (unit->bb_list[i]->loop_depth > d)
1714 d = unit->bb_list[i]->loop_depth;
1715 return d;
1716 }
1717
1718 /*
1719
1720 =item C<int is_invariant>
1721
1722 RT#48260: Not yet documented!!!
1723
1724 =cut
1725
1726 */
1727
1728 int
1729 is_invariant(PARROT_INTERP, ARGIN(const IMC_Unit *unit), ARGIN(const Instruction *ins))
1730 {
1731 int ok = 0;
1732 int what = 0;
1733
1734 if (STREQ(ins->opname, "new")) {
1735 ok = 1;
1736 what = CHK_INV_NEW;
1737 }
1738 /* only, if once assigned and not changed */
1739 else if (STREQ(ins->opname, "set") &&
1740 !(ins->symregs[0]->usage & U_KEYED) &&
1741 ins->symregs[1]->type & VTCONST) {
1742 ok = 1;
1743 what = CHK_INV_SET;
1744 }
1745 if (ok)
1746 return is_ins_save(interp, unit, ins, ins->symregs[0], what);
1747 return 0;
1748 }
1749
1750 # define MOVE_INS_1_BL
1751 # ifdef MOVE_INS_1_BL
1752 /*
1753
1754 =item C<Basic_block * find_outer>
1755
1756 RT #48260: Not yet documented!!!
1757
1758 =cut
1759
1760 */
1761
1762 PARROT_WARN_UNUSED_RESULT
1763 PARROT_CAN_RETURN_NULL
1764 Basic_block *
1765 find_outer(ARGIN(const IMC_Unit *unit), ARGIN(const Basic_block *blk))
1766 {
1767 int i;
1768 Loop_info ** const loop_info = unit->loop_info;
1769 const int bb = blk->index;
1770 int i = unit->n_loops - 1;
1771
1772 /* loops are sorted depth last */
1773 for (; i >= 0; i--) {
1774 Loop_info * const info = loop_info[i];
1775 if (set_contains(info->loop, bb)) {
1776 const int preheader = info->preheader;
1777 if (preheader >= 0)
1778 return unit->bb_list[preheader];
1779 }
1780 }
1781 return NULL;
1782 }
1783 # endif
1784
1785 /*
1786
1787 =item C<int move_ins_out>
1788
1789 move the instruction ins before loop in bb
1790
1791 =cut
1792
1793 */
1794
1795 int
1796 move_ins_out(PARROT_INTERP, ARGMOD(IMC_Unit *unit),
1797 ARGMOD(Instruction **ins), ARGIN(const Basic_block *bb))
1798 {
1799 Basic_block *pred;
1800 Instruction * next, *out;
1801
1802 /* check loop_info, where this loop started
1803 * actually, this moves instruction to block 0 */
1804 # ifdef MOVE_INS_1_BL
1805 pred = find_outer(unit, bb);
1806 # else
1807 UNUSED(bb);
1808 pred = unit->bb_list[0];
1809 # endif
1810 if (!pred) {
1811 IMCC_debug(interp, DEBUG_OPT2, "outer loop not found (CFG?)\n");
1812 return 0;
1813 }
1814 out = pred->end;
1815 next = (*ins)->next;
1816 (*ins)->bbindex = pred->index;
1817 IMCC_debug(interp, DEBUG_OPT2, "inserting it in blk %d after %I\n",
1818 pred->index, out);
1819 *ins = move_ins(unit, *ins, out);
1820 if (0 && (DEBUG_OPT2 & IMCC_INFO(interp)->debug)) {
1821 char buf[256];
1822 SymReg * regs[IMCC_MAX_REGS];
1823 Instruction * tmp;
1824
1825 regs[0] = 0;
1826 snprintf(buf, sizeof (buf), "# Invar moved: %s", out->next->op);
1827 tmp = INS(interp, unit, "", buf, regs, 0, 0, 0);
1828 insert_ins(unit, (*ins)->prev, tmp);
1829 }
1830 ostat.invariants_moved++;
1831 /* RT#46291 CFG is changed here, which also means
1832 * that the life_info is wrong now
1833 * so, currently we calc CFG and life again */
1834 return 1;
1835 }
1836
1837 /*
1838
1839 =item C<int loop_one>
1840
1841 RT#48260: Not yet documented!!!
1842
1843 =cut
1844
1845 */
1846
1847 int
1848 loop_one(PARROT_INTERP, ARGMOD(IMC_Unit *unit), int bnr)
1849 {
1850 Basic_block * const bb = unit->bb_list[bnr];
1851 Instruction *ins;
1852 int changed = 0;
1853
1854 if (bnr == 0) {
1855 IMCC_warning(interp, "loop_one", "wrong loop depth in block 0\n");
1856 return 0;
1857 }
1858 IMCC_debug(interp, DEBUG_OPT2, "loop_one blk %d\n", bnr);
1859 for (ins = bb->start ; ins ; ins = ins->next) {
1860 reason = 0;
1861 if (is_invariant(interp, unit, ins)) {
1862 IMCC_debug(interp, DEBUG_OPT2, "found invariant %I\n", ins);
1863 if (move_ins_out(interp, unit, &ins, bb)) {
1864 changed++;
1865 ins = ins->prev;
1866 }
1867 }
1868 if (ins == bb->end)
1869 break;
1870 }
1871 return changed;
1872
1873 }
1874
1875 /*
1876
1877 =item C<int loop_optimization>
1878
1879 RT#48260: Not yet documented!!!
1880
1881 =cut
1882
1883 */
1884
1885 int
1886 loop_optimization(PARROT_INTERP, ARGMOD(IMC_Unit *unit))
1887 {
1888 int l;
1889 int changed = 0;
1890 static int prev_depth;
1891
1892 const int loop_depth = prev_depth ? prev_depth : max_loop_depth(unit);
1893
1894 /* work from inside out */
1895 IMCC_debug(interp, DEBUG_OPT2, "loop_optimization\n");
1896 for (l = loop_depth; l > 0; l--) {
1897 int bb;
1898
1899 IMCC_debug(interp, DEBUG_OPT2, "loop_depth %d\n", l);
1900 for (bb = 0; bb < unit->n_basic_blocks; bb++)
1901 if (unit->bb_list[bb]->loop_depth == l) {
1902 changed |= loop_one(interp, unit, bb);
1903 }
1904 /* currently e.g. mandel.p6 breaks, if not only the most
1905 * inner loop is changed, but outer loops too */
1906 if (changed) {
1907 prev_depth = l-1;
1908 IMCC_debug(interp, DEBUG_OPT2, "after loop_opt\n");
1909 if (IMCC_INFO(interp)->debug>1)
1910 dump_instructions(interp, unit);
1911 return changed;
1912 }
1913 }
1914 prev_depth = 0;
1915 return 0;
1916 }
1917 #endif
1918
1919 /*
1920
1921 =back
1922
1923 =cut
1924
1925 */
1926
1927 /*
1928 * Local variables:
1929 * c-file-style: "parrot"
1930 * End:
1931 * vim: expandtab shiftwidth=4:
1932 */
parrot vm git mirror