source: trunk/optimizer.c @ 330

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

rebuild zend_try_catch_element

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