source: trunk/optimizer.c @ 657

Last change on this file since 657 was 657, checked in by moo, 4 years ago

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