source: trunk/optimizer.c @ 331

Last change on this file since 331 was 331, checked in by moo, 7 years ago

optimzer: implement dop for debugging

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