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