source: trunk/optimizer.c @ 834

Last change on this file since 834 was 834, checked in by moo, 2 years ago

optimizer: handle goto in convert_switch optimization

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