source: trunk/optimizer.c @ 877

Last change on this file since 877 was 877, checked in by moo, 15 months ago

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