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