source: trunk/optimizer.c @ 326

Last change on this file since 326 was 326, checked in by moo, 8 years ago

optimizer: handle try/catch and make all opnum(opline_num) to be bbid_t inside optimization

File size: 10.6 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
227#define bbs_get(bbs, n) ((bb_t *) xc_stack_get(bbs, n))
228#define bbs_count(bbs) xc_stack_count(bbs)
229static void bbs_destroy(bbs_t *bbs) /* {{{ */
230{
231    bb_t *bb;
232    while (bbs_count(bbs)) {
233        bb = (bb_t *) xc_stack_pop(bbs);
234        bb_destroy(bb);
235    }
236    xc_stack_destroy(bbs);
237}
238/* }}} */
239#ifdef DEBUG
240static void bbs_print(bbs_t *bbs, zend_op *opcodes) /* {{{ */
241{
242    int i;
243    fprintf(stderr,
244            " id cnt lno"
245            " UA"
246            " op1 op2 ext fal cat opcode\r\n"
247            );
248    for (i = 0; i < xc_stack_count(bbs); i ++) {
249        bb_print(bbs_get(bbs, i), opcodes);
250    }
251}
252/* }}} */
253#endif
254#define bbs_init(bbs) xc_stack_init_ex(bbs, 16)
255static bb_t *bbs_add_bb(bbs_t *bbs, bb_t *bb) /* {{{ */
256{
257    bb->id = (bbid_t) xc_stack_count(bbs);
258    xc_stack_push(bbs, (void *) bb);
259    return bb;
260}
261/* }}} */
262static bb_t *bbs_new_bb_ex(bbs_t *bbs, zend_op *opcodes, int count) /* {{{ */
263{
264    return bbs_add_bb(bbs, bb_new_ex(opcodes, count));
265}
266/* }}} */
267static int bbs_build_from(bbs_t *bbs, zend_op_array *op_array, int count) /* {{{ */
268{
269    int i, start;
270    bb_t *pbb;
271    bbid_t id;
272    op_flowinfo_t fi;
273    zend_op *opline;
274    bbid_t *bbids          = do_alloca(count * sizeof(bbid_t));
275    bbid_t *catchbbids     = do_alloca(count * sizeof(bbid_t));
276    zend_bool *markbbhead  = do_alloca(count * sizeof(zend_bool));
277
278    /* {{{ mark jmpin/jumpout */
279    memset(markbbhead,  0, count * sizeof(zend_bool));
280
281    markbbhead[0] = 1;
282    for (i = 0; i < count; i ++) {
283        if (op_get_flowinfo(&fi, &op_array->opcodes[i]) == SUCCESS) {
284            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
285                markbbhead[fi.jmpout_op1] = 1;
286            }
287            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
288                markbbhead[fi.jmpout_op2] = 1;
289            }
290            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
291                markbbhead[fi.jmpout_ext] = 1;
292            }
293            if (i + 1 < count) {
294                markbbhead[i + 1] = 1;
295            }
296        }
297    }
298    /* mark try start */
299    for (i = 0; i < op_array->last_try_catch; i ++) {
300        markbbhead[op_array->try_catch_array[i].try_op] = 1;
301    }
302    /* }}} */
303    /* {{{ fill op lines with newly allocated id */
304    for (i = 0; i < count; i ++) {
305        bbids[i] = BBID_INVALID;
306    }
307
308    /*
309    start = 0;
310    id = 0;
311    for (i = 1; i < count; i ++) {
312        if (markbbhead[i]) {
313            for (; start < i; start ++) {
314                bbids[start] = id;
315            }
316            id ++;
317            start = i;
318        }
319    }
320
321    for (; start < count; start ++) {
322        bbids[start] = id;
323    }
324    */
325    id = -1;
326    for (i = 0; i < count; i ++) {
327        if (markbbhead[i]) {
328            id ++;
329        }
330        bbids[i] = id;
331        TRACE("bbids[%d] = %d", i, id);
332    }
333    /* }}} */
334    /* {{{ fill op lines with catch id */
335    for (i = 0; i < count; i ++) {
336        catchbbids[i] = BBID_INVALID;
337    }
338
339    for (i = 0; i < op_array->last_try_catch; i ++) {
340        int j;
341        zend_try_catch_element *e = &op_array->try_catch_array[i];
342        for (j = e->try_op; j < e->catch_op; j ++) {
343            catchbbids[j] = bbids[e->catch_op];
344        }
345    }
346#ifdef DEBUG
347    for (i = 0; i < count; i ++) {
348        TRACE("catchbbids[%d] = %d", i, catchbbids[i]);
349    }
350#endif
351    /* }}} */
352    /* {{{ create basic blocks */
353    start = 0;
354    id = 0;
355    /* loop over to deal with the last block */
356    for (i = 1; i <= count; i ++) {
357        if (i < count && id == bbids[i]) {
358            continue;
359        }
360
361        opline = op_array->opcodes + start;
362        pbb = bbs_new_bb_ex(bbs, opline, i - start);
363        pbb->catch = catchbbids[start];
364
365        /* last */
366        opline = pbb->opcodes + pbb->count - 1;
367        if (op_get_flowinfo(&fi, opline) == SUCCESS) {
368            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
369                opline->op1.u.opline_num = bbids[fi.jmpout_op1];
370                assert(opline->op1.u.opline_num != BBID_INVALID);
371            }
372            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
373                opline->op2.u.opline_num = bbids[fi.jmpout_op2];
374                assert(opline->op2.u.opline_num != BBID_INVALID);
375            }
376            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
377                opline->extended_value = bbids[fi.jmpout_ext];
378                assert(opline->extended_value != BBID_INVALID);
379            }
380            if (fi.fall && i + 1 < count) {
381                pbb->fall = bbids[i + 1];
382                TRACE("fall %d", pbb->fall);
383                assert(pbb->fall != BBID_INVALID);
384            }
385        }
386        if (i >= count) {
387            break;
388        }
389        start = i + 1;
390        id = bbids[i];
391    }
392    /* }}} */
393
394    free_alloca(catchbbids);
395    free_alloca(bbids);
396    free_alloca(markbbhead);
397    return SUCCESS;
398}
399/* }}} */
400static void bbs_restore_opnum(bbs_t *bbs) /* {{{ */
401{
402    int i;
403    for (i = 0; i < bbs_count(bbs); i ++) {
404        op_flowinfo_t fi;
405        bb_t *bb = bbs_get(bbs, i);
406        zend_op *last = bb->opcodes + bb->count - 1;
407
408        if (op_get_flowinfo(&fi, last) == SUCCESS) {
409            if (fi.jmpout_op1 != XC_OPNUM_INVALID) {
410                last->op1.u.opline_num = bbs_get(bbs, fi.jmpout_op1)->opnum;
411                assert(last->op1.u.opline_num != BBID_INVALID);
412            }
413            if (fi.jmpout_op2 != XC_OPNUM_INVALID) {
414                last->op2.u.opline_num = bbs_get(bbs, fi.jmpout_op2)->opnum;
415                assert(last->op2.u.opline_num != BBID_INVALID);
416            }
417            if (fi.jmpout_ext != XC_OPNUM_INVALID) {
418                last->extended_value = bbs_get(bbs, fi.jmpout_ext)->opnum;
419                assert(last->extended_value != BBID_INVALID);
420            }
421        }
422    }
423
424    /* TODO: rebuild zend_try_catch_element here */
425}
426/* }}} */
427
428/*
429 * optimize
430 */
431static int xc_optimize_op_array(zend_op_array *op_array TSRMLS_DC) /* {{{ */
432{
433    bbs_t bbs;
434
435    if (op_array->type != ZEND_USER_FUNCTION) {
436        return 0;
437    }
438    xc_undo_pass_two(op_array TSRMLS_CC);
439#ifdef DEBUG
440#   if 0
441    TRACE("optimize file: %s", op_array->filename);
442    xc_dprint_zend_op_array(op_array, 0 TSRMLS_CC);
443#   endif
444#endif
445
446    if (op_array_convert_switch(op_array) == SUCCESS) {
447        bbs_init(&bbs);
448        if (bbs_build_from(&bbs, op_array, op_array->last) == SUCCESS) {
449            int i;
450#ifdef DEBUG
451            bbs_print(&bbs, op_array->opcodes);
452#endif
453            /* TODO: calc opnum after basic block move */
454            for (i = 0; i < bbs_count(&bbs); i ++) {
455                bb_t *bb = bbs_get(&bbs, i);
456                bb->opnum = bb->opcodes - op_array->opcodes;
457            }
458            bbs_restore_opnum(&bbs);
459        }
460        bbs_destroy(&bbs);
461    }
462
463#ifdef DEBUG
464#   if 0
465    TRACE("%s", "after compiles");
466    xc_dprint_zend_op_array(op_array, 0 TSRMLS_CC);
467#   endif
468#endif
469    xc_redo_pass_two(op_array TSRMLS_CC);
470    return 0;
471}
472/* }}} */
473void xc_optimize(zend_op_array *op_array TSRMLS_DC) /* {{{ */
474{
475    xc_compile_result_t cr;
476
477    if (!op_array) {
478        return;
479    }
480
481    xc_compile_result_init_cur(&cr, op_array TSRMLS_CC);
482
483    xc_apply_op_array(&cr, (apply_func_t) xc_undo_pass_two TSRMLS_CC);
484    xc_apply_op_array(&cr, (apply_func_t) xc_optimize_op_array TSRMLS_CC);
485    xc_apply_op_array(&cr, (apply_func_t) xc_redo_pass_two TSRMLS_CC);
486
487    xc_compile_result_free(&cr);
488}
489/* }}} */
Note: See TracBrowser for help on using the repository browser.