source: trunk/optimizer.c @ 365

Last change on this file since 365 was 365, checked in by moo, 8 years ago

remove warning

File size: 13.0 KB
Line 
1#if 0
2#   define DEBUG
3#endif
4
5#include "utils.h"
6#include "optimizer.h"
7/* the "vector" stack */
8#include "stack.h"
9
10#ifdef DEBUG
11#   include "processor.h"
12#   include "const_string.h"
13#   include "ext/standard/php_var.h"
14#endif
15
16#ifdef IS_CV
17#   define XCACHE_IS_CV IS_CV
18#else
19#   define XCACHE_IS_CV 16
20#endif
21#define optimized_flag done_pass_two
22
23typedef int bbid_t;
24enum {
25    BBID_INVALID = -1,
26};
27/* {{{ basic block */
28typedef struct _bb_t {
29    bbid_t     id;
30    zend_bool  used;
31
32    zend_bool  alloc;
33    zend_op   *opcodes;
34    int        count;
35    int        size;
36
37    bbid_t     fall;
38    bbid_t     catch;
39
40    int        opnum; /* opnum after joining basic block */
41} bb_t;
42/* }}} */
43
44/* basic blocks */
45typedef xc_stack_t bbs_t;
46
47/* op array helper functions */
48static int op_array_convert_switch(zend_op_array *op_array) /* {{{ */
49{
50    int i;
51
52    if (op_array->brk_cont_array == NULL) {
53        return SUCCESS;
54    }
55
56    for (i = 0; i < op_array->last; i ++) {
57        zend_op *opline = &op_array->opcodes[i];
58        zend_brk_cont_element *jmp_to;
59        int array_offset, nest_levels, original_nest_levels;
60
61        if (opline->opcode != ZEND_BRK && opline->opcode != ZEND_CONT) {
62            continue;
63        }
64        if (opline->op2.op_type != IS_CONST
65         || opline->op2.u.constant.type != IS_LONG) {
66            return FAILURE;
67        }
68
69        nest_levels = opline->op2.u.constant.value.lval;
70        original_nest_levels = nest_levels;
71
72        array_offset = opline->op1.u.opline_num;
73        do {
74            if (array_offset == -1) {
75                /* this is a runtime error in ZE
76                zend_error(E_ERROR, "Cannot break/continue %d level%s", original_nest_levels, (original_nest_levels == 1) ? "" : "s");
77                */
78                return FAILURE;
79            }
80            jmp_to = &op_array->brk_cont_array[array_offset];
81            if (nest_levels > 1) {
82                zend_op *brk_opline = &op_array->opcodes[jmp_to->brk];
83
84                switch (brk_opline->opcode) {
85                case ZEND_SWITCH_FREE:
86                    break;
87                case ZEND_FREE:
88                    break;
89                }
90            }
91            array_offset = jmp_to->parent;
92        } while (--nest_levels > 0);
93
94        /* rewrite to jmp */
95        if (opline->opcode == ZEND_BRK) {
96            opline->op1.u.opline_num = jmp_to->brk;
97        }
98        else {
99            opline->op1.u.opline_num = jmp_to->cont;
100        }
101        opline->op2.op_type = IS_UNUSED;
102        opline->opcode = ZEND_JMP;
103    }
104
105    if (op_array->brk_cont_array != NULL) {
106        efree(op_array->brk_cont_array);
107        op_array->brk_cont_array = NULL;
108    }
109    op_array->last_brk_cont = 0;
110    return SUCCESS;
111}
112/* }}} */
113/* {{{ op_flowinfo helper func */
114enum {
115    XC_OPNUM_INVALID = -1,
116};
117typedef struct {
118    int       jmpout_op1;
119    int       jmpout_op2;
120    int       jmpout_ext;
121    zend_bool fall;
122} op_flowinfo_t;
123static void op_flowinfo_init(op_flowinfo_t *fi)
124{
125    fi->jmpout_op1 = fi->jmpout_op2 = fi->jmpout_ext = XC_OPNUM_INVALID;
126    fi->fall = 0;
127}
128/* }}} */
129static int op_get_flowinfo(op_flowinfo_t *fi, zend_op *opline) /* {{{ */
130{
131    op_flowinfo_init(fi);
132
133    /* break=will fall */
134    switch (opline->opcode) {
135    case ZEND_HANDLE_EXCEPTION:
136    case ZEND_RETURN:
137    case ZEND_EXIT:
138        return SUCCESS; /* no fall */
139
140    case ZEND_JMP:
141        fi->jmpout_op1 = opline->op1.u.opline_num;
142        return SUCCESS; /* no fall */
143
144    case ZEND_JMPZNZ:
145        fi->jmpout_op2 = opline->op2.u.opline_num;
146        fi->jmpout_ext = (int) opline->extended_value;
147        return SUCCESS; /* no fall */
148
149    case ZEND_JMPZ:
150    case ZEND_JMPNZ:
151    case ZEND_JMPZ_EX:
152    case ZEND_JMPNZ_EX:
153#ifdef ZEND_JMP_NO_CTOR
154    case ZEND_JMP_NO_CTOR:
155#endif
156#ifdef ZEND_NEW
157    case ZEND_NEW:
158#endif
159#ifdef ZEND_FE_RESET
160    case ZEND_FE_RESET:
161#endif     
162    case ZEND_FE_FETCH:
163        fi->jmpout_op2 = opline->op2.u.opline_num;
164        break;
165
166#ifdef ZEND_CATCH
167    case ZEND_CATCH:
168        fi->jmpout_ext = (int) opline->extended_value;
169        break;
170#endif
171
172    default:
173        return FAILURE;
174    }
175
176    fi->fall = 1;
177    return SUCCESS;
178}
179/* }}} */
180#ifdef DEBUG
181static void op_snprint(char *buf, int size, znode *op) /* {{{ */
182{
183    switch (op->op_type) {
184    case IS_CONST:
185        {
186            zval result;
187            zval *zv = &op->u.constant;
188            TSRMLS_FETCH();
189
190            php_start_ob_buffer(NULL, 0, 1 TSRMLS_CC);
191            php_var_export(&zv, 1 TSRMLS_CC);
192
193            php_ob_get_buffer(&result TSRMLS_CC); 
194            php_end_ob_buffer(0, 0 TSRMLS_CC);
195            snprintf(buf, size, Z_STRVAL(result));
196            zval_dtor(&result);
197        }
198        break;
199
200    case IS_TMP_VAR:
201        snprintf(buf, size, "t@%d", op->u.var);
202        break;
203
204    case XCACHE_IS_CV:
205    case IS_VAR:
206        snprintf(buf, size, "v@%d", op->u.var);
207        break;
208
209    case IS_UNUSED:
210        if (op->u.opline_num) {
211            snprintf(buf, size, "u#%d", op->u.opline_num);
212        }
213        else {
214            snprintf(buf, size, "-");
215        }
216        break;
217
218    default:
219        snprintf(buf, size, "%d %d", op->op_type, op->u.var);
220    }
221}
222/* }}} */
223static void op_print(int line, zend_op *first, zend_op *end) /* {{{ */
224{
225    zend_op *opline;
226    for (opline = first; opline < end; opline ++) {
227        char buf_r[20];
228        char buf_1[20];
229        char buf_2[20];
230        op_snprint(buf_r, sizeof(buf_r), &opline->result);
231        op_snprint(buf_1, sizeof(buf_1), &opline->op1);
232        op_snprint(buf_2, sizeof(buf_2), &opline->op2);
233        fprintf(stderr,
234                "%3d %3d"
235                " %-25s%-5s%-20s%-20s%5lu\r\n"
236                , opline->lineno, opline - first + line
237                , xc_get_opcode(opline->opcode), buf_r, buf_1, buf_2, opline->extended_value);
238    }
239}
240/* }}} */
241#endif
242
243/*
244 * basic block functions
245 */
246
247static bb_t *bb_new_ex(zend_op *opcodes, int count) /* {{{ */
248{
249    bb_t *bb = (bb_t *) ecalloc(sizeof(bb_t), 1);
250
251    bb->fall       = BBID_INVALID;
252    bb->catch      = BBID_INVALID;
253
254    if (opcodes) {
255        bb->alloc   = 0;
256        bb->size    = bb->count = count;
257        bb->opcodes = opcodes;
258    }
259    else {
260        bb->alloc   = 1;
261        bb->size    = bb->count = 8;
262        bb->opcodes = ecalloc(sizeof(zend_op), bb->size);
263    }
264
265    return bb;
266}
267/* }}} */
268#define bb_new() bb_new_ex(NULL, 0)
269static void bb_destroy(bb_t *bb) /* {{{ */
270{
271    if (bb->alloc) {
272        efree(bb->opcodes);
273    }
274    efree(bb);
275}
276/* }}} */
277#ifdef DEBUG
278static void bb_print(bb_t *bb, zend_op *opcodes) /* {{{ */
279{
280    int line = bb->opcodes - opcodes;
281    op_flowinfo_t fi;
282    zend_op *last = bb->opcodes + bb->count - 1;
283
284    op_get_flowinfo(&fi, last);
285
286    fprintf(stderr,
287            "\r\n==== #%-3d cnt:%-3d lno:%-3d"
288            " %c%c"
289            " op1:%-3d op2:%-3d ext:%-3d fal:%-3d cat:%-3d %s ====\r\n"
290            , bb->id, bb->count, bb->alloc ? -1 : line
291            , bb->used ? 'U' : ' ', bb->alloc ? 'A' : ' '
292            , fi.jmpout_op1, fi.jmpout_op2, fi.jmpout_ext, bb->fall, bb->catch, xc_get_opcode(last->opcode)
293            );
294    op_print(line, bb->opcodes, last + 1);
295}
296/* }}} */
297#endif
298
299static bb_t *bbs_get(bbs_t *bbs, int n) /* {{{ */
300{
301    return (bb_t *) xc_stack_get(bbs, n);
302}
303/* }}} */
304static int bbs_count(bbs_t *bbs) /* {{{ */
305{
306    return xc_stack_count(bbs);
307}
308/* }}} */
309static void bbs_destroy(bbs_t *bbs) /* {{{ */
310{
311    bb_t *bb;
312    while (bbs_count(bbs)) {
313        bb = (bb_t *) xc_stack_pop(bbs);
314        bb_destroy(bb);
315    }
316    xc_stack_destroy(bbs);
317}
318/* }}} */
319#ifdef DEBUG
320static void bbs_print(bbs_t *bbs, zend_op *opcodes) /* {{{ */
321{
322    int i;
323    for (i = 0; i < xc_stack_count(bbs); i ++) {
324        bb_print(bbs_get(bbs, i), opcodes);
325    }
326}
327/* }}} */
328#endif
329#define bbs_init(bbs) xc_stack_init_ex(bbs, 16)
330static bb_t *bbs_add_bb(bbs_t *bbs, bb_t *bb) /* {{{ */
331{
332    bb->id = (bbid_t) xc_stack_count(bbs);
333    xc_stack_push(bbs, (void *) bb);
334    return bb;
335}
336/* }}} */
337static bb_t *bbs_new_bb_ex(bbs_t *bbs, zend_op *opcodes, int count) /* {{{ */
338{
339    return bbs_add_bb(bbs, bb_new_ex(opcodes, count));
340}
341/* }}} */
342static int bbs_build_from(bbs_t *bbs, zend_op_array *op_array, int count) /* {{{ */
343{
344    int i, start;
345    bb_t *pbb;
346    bbid_t id;
347    op_flowinfo_t fi;
348    zend_op *opline;
349    bbid_t *bbids          = do_alloca(count * sizeof(bbid_t));
350    bbid_t *catchbbids     = do_alloca(count * sizeof(bbid_t));
351    zend_bool *markbbhead  = do_alloca(count * sizeof(zend_bool));
352
353    /* {{{ mark jmpin/jumpout */
354    memset(markbbhead,  0, count * sizeof(zend_bool));
355
356    markbbhead[0] = 1;
357    for (i = 0; i < count; i ++) {
358        if (op_get_flowinfo(&fi, &op_array->opcodes[i]) == SUCCESS) {
359            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
360                markbbhead[fi.jmpout_op1] = 1;
361            }
362            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
363                markbbhead[fi.jmpout_op2] = 1;
364            }
365            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
366                markbbhead[fi.jmpout_ext] = 1;
367            }
368            if (i + 1 < count) {
369                markbbhead[i + 1] = 1;
370            }
371        }
372    }
373    /* mark try start */
374    for (i = 0; i < op_array->last_try_catch; i ++) {
375        markbbhead[op_array->try_catch_array[i].try_op] = 1;
376    }
377    /* }}} */
378    /* {{{ fill op lines with newly allocated id */
379    for (i = 0; i < count; i ++) {
380        bbids[i] = BBID_INVALID;
381    }
382
383    id = -1;
384    for (i = 0; i < count; i ++) {
385        if (markbbhead[i]) {
386            id ++;
387        }
388        bbids[i] = id;
389        TRACE("bbids[%d] = %d", i, id);
390    }
391    /* }}} */
392    /* {{{ fill op lines with catch id */
393    for (i = 0; i < count; i ++) {
394        catchbbids[i] = BBID_INVALID;
395    }
396
397    for (i = 0; i < op_array->last_try_catch; i ++) {
398        int j;
399        zend_try_catch_element *e = &op_array->try_catch_array[i];
400        for (j = e->try_op; j < e->catch_op; j ++) {
401            catchbbids[j] = bbids[e->catch_op];
402        }
403    }
404#ifdef DEBUG
405    for (i = 0; i < count; i ++) {
406        TRACE("catchbbids[%d] = %d", i, catchbbids[i]);
407    }
408#endif
409    /* }}} */
410    /* {{{ create basic blocks */
411    start = 0;
412    id = 0;
413    /* loop over to deal with the last block */
414    for (i = 1; i <= count; i ++) {
415        if (i < count && id == bbids[i]) {
416            continue;
417        }
418
419        opline = op_array->opcodes + start;
420        pbb = bbs_new_bb_ex(bbs, opline, i - start);
421        pbb->catch = catchbbids[start];
422
423        /* last */
424        opline = pbb->opcodes + pbb->count - 1;
425        if (op_get_flowinfo(&fi, opline) == SUCCESS) {
426            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
427                opline->op1.u.opline_num = bbids[fi.jmpout_op1];
428                assert(opline->op1.u.opline_num != BBID_INVALID);
429            }
430            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
431                opline->op2.u.opline_num = bbids[fi.jmpout_op2];
432                assert(opline->op2.u.opline_num != BBID_INVALID);
433            }
434            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
435                opline->extended_value = bbids[fi.jmpout_ext];
436                assert(opline->extended_value != BBID_INVALID);
437            }
438            if (fi.fall && i + 1 < count) {
439                pbb->fall = bbids[i + 1];
440                TRACE("fall %d", pbb->fall);
441                assert(pbb->fall != BBID_INVALID);
442            }
443        }
444        if (i >= count) {
445            break;
446        }
447        start = i;
448        id = bbids[i];
449    }
450    /* }}} */
451
452    free_alloca(catchbbids);
453    free_alloca(bbids);
454    free_alloca(markbbhead);
455    return SUCCESS;
456}
457/* }}} */
458static void bbs_restore_opnum(bbs_t *bbs, zend_op_array *op_array) /* {{{ */
459{
460    int i;
461    bbid_t lasttrybbid;
462
463    for (i = 0; i < bbs_count(bbs); i ++) {
464        op_flowinfo_t fi;
465        bb_t *bb = bbs_get(bbs, i);
466        zend_op *last = bb->opcodes + bb->count - 1;
467
468        if (op_get_flowinfo(&fi, last) == SUCCESS) {
469            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
470                last->op1.u.opline_num = bbs_get(bbs, fi.jmpout_op1)->opnum;
471                assert(last->op1.u.opline_num != BBID_INVALID);
472            }
473            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
474                last->op2.u.opline_num = bbs_get(bbs, fi.jmpout_op2)->opnum;
475                assert(last->op2.u.opline_num != BBID_INVALID);
476            }
477            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
478                last->extended_value = bbs_get(bbs, fi.jmpout_ext)->opnum;
479                assert(last->extended_value != BBID_INVALID);
480            }
481        }
482    }
483
484    lasttrybbid = BBID_INVALID;
485    op_array->last_try_catch = 0;
486    for (i = 0; i < bbs_count(bbs); i ++) {
487        bb_t *bb = bbs_get(bbs, i);
488
489        if (lasttrybbid != bb->catch) {
490            if (lasttrybbid != BBID_INVALID) {
491                int try_catch_offset = op_array->last_try_catch ++;
492
493                op_array->try_catch_array = erealloc(op_array->try_catch_array, sizeof(zend_try_catch_element) * op_array->last_try_catch);
494                op_array->try_catch_array[try_catch_offset].try_op = bbs_get(bbs, lasttrybbid)->opnum;
495                op_array->try_catch_array[try_catch_offset].catch_op = bbs_get(bbs, bb->id)->opnum;
496            }
497            lasttrybbid = bb->catch;
498        }
499    }
500    /* it is impossible to have last bb catched */
501}
502/* }}} */
503
504/*
505 * optimize
506 */
507static int xc_optimize_op_array(zend_op_array *op_array TSRMLS_DC) /* {{{ */
508{
509    bbs_t bbs;
510
511    if (op_array->type != ZEND_USER_FUNCTION) {
512        return 0;
513    }
514
515    /* don't optimize twice */
516    if (op_array->optimized_flag) {
517        return 0;
518    }
519    op_array->optimized_flag = 1;
520
521#ifdef DEBUG
522#   if 0
523    TRACE("optimize file: %s", op_array->filename);
524    xc_dprint_zend_op_array(op_array, 0 TSRMLS_CC);
525#   endif
526    op_print(0, op_array->opcodes, op_array->opcodes + op_array->last);
527#endif
528
529    if (op_array_convert_switch(op_array) == SUCCESS) {
530        bbs_init(&bbs);
531        if (bbs_build_from(&bbs, op_array, op_array->last) == SUCCESS) {
532            int i;
533#ifdef DEBUG
534            bbs_print(&bbs, op_array->opcodes);
535#endif
536            /* TODO: calc opnum after basic block move */
537            for (i = 0; i < bbs_count(&bbs); i ++) {
538                bb_t *bb = bbs_get(&bbs, i);
539                bb->opnum = bb->opcodes - op_array->opcodes;
540            }
541            bbs_restore_opnum(&bbs, op_array);
542        }
543        bbs_destroy(&bbs);
544    }
545
546#ifdef DEBUG
547#   if 0
548    TRACE("%s", "after compiles");
549    xc_dprint_zend_op_array(op_array, 0 TSRMLS_CC);
550#   endif
551#endif
552    return 0;
553}
554/* }}} */
555int xc_clear_flag_optimized(zend_op_array *op_array TSRMLS_DC) /* {{{ */
556{
557    op_array->done_pass_two = 0;
558    return 0;
559}
560/* }}} */
561void xc_optimize(zend_op_array *op_array TSRMLS_DC) /* {{{ */
562{
563    xc_compile_result_t cr;
564
565    if (!op_array) {
566        return;
567    }
568
569    xc_compile_result_init_cur(&cr, op_array TSRMLS_CC);
570
571    xc_apply_op_array(&cr, (apply_func_t) xc_undo_pass_two TSRMLS_CC);
572    /* op_array->done_pass_two is now used as if it's op_array->flag_optimized */
573    xc_apply_op_array(&cr, (apply_func_t) xc_optimize_op_array TSRMLS_CC);
574    xc_apply_op_array(&cr, (apply_func_t) xc_clear_flag_optimized TSRMLS_CC);
575    xc_apply_op_array(&cr, (apply_func_t) xc_redo_pass_two TSRMLS_CC);
576
577    xc_compile_result_free(&cr);
578}
579/* }}} */
Note: See TracBrowser for help on using the repository browser.