1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, DFG - Data Flow Graph |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2018 The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Dmitry Stogov <dmitry@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #include "php.h"
20 #include "zend_compile.h"
21 #include "zend_dfg.h"
22
zend_build_dfg(const zend_op_array * op_array,const zend_cfg * cfg,zend_dfg * dfg,uint32_t build_flags)23 int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */
24 {
25 int set_size;
26 zend_basic_block *blocks = cfg->blocks;
27 int blocks_count = cfg->blocks_count;
28 zend_bitset tmp, def, use, in, out;
29 int k;
30 uint32_t var_num;
31 int j;
32
33 set_size = dfg->size;
34 tmp = dfg->tmp;
35 def = dfg->def;
36 use = dfg->use;
37 in = dfg->in;
38 out = dfg->out;
39
40 /* Collect "def" and "use" sets */
41 for (j = 0; j < blocks_count; j++) {
42 zend_op *opline, *end;
43 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
44 continue;
45 }
46
47 opline = op_array->opcodes + blocks[j].start;
48 end = opline + blocks[j].len;
49 for (; opline < end; opline++) {
50 if (opline->opcode != ZEND_OP_DATA) {
51 zend_op *next = opline + 1;
52 if (next < end && next->opcode == ZEND_OP_DATA) {
53 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
54 var_num = EX_VAR_TO_NUM(next->op1.var);
55 if (!DFG_ISSET(def, set_size, j, var_num)) {
56 DFG_SET(use, set_size, j, var_num);
57 }
58 }
59 if (next->op2_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
60 var_num = EX_VAR_TO_NUM(next->op2.var);
61 if (!DFG_ISSET(def, set_size, j, var_num)) {
62 DFG_SET(use, set_size, j, var_num);
63 }
64 }
65 }
66 if (opline->op1_type == IS_CV) {
67 var_num = EX_VAR_TO_NUM(opline->op1.var);
68 switch (opline->opcode) {
69 case ZEND_ADD_ARRAY_ELEMENT:
70 case ZEND_INIT_ARRAY:
71 if ((build_flags & ZEND_SSA_RC_INFERENCE)
72 || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF)) {
73 goto op1_def;
74 }
75 goto op1_use;
76 case ZEND_FE_RESET_R:
77 case ZEND_SEND_VAR:
78 case ZEND_CAST:
79 case ZEND_QM_ASSIGN:
80 case ZEND_JMP_SET:
81 case ZEND_COALESCE:
82 if (build_flags & ZEND_SSA_RC_INFERENCE) {
83 goto op1_def;
84 }
85 goto op1_use;
86 case ZEND_YIELD:
87 if ((build_flags & ZEND_SSA_RC_INFERENCE)
88 || (op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)) {
89 goto op1_def;
90 }
91 goto op1_use;
92 case ZEND_UNSET_CV:
93 case ZEND_ASSIGN:
94 case ZEND_ASSIGN_REF:
95 case ZEND_BIND_GLOBAL:
96 case ZEND_BIND_STATIC:
97 case ZEND_SEND_VAR_EX:
98 case ZEND_SEND_FUNC_ARG:
99 case ZEND_SEND_REF:
100 case ZEND_SEND_VAR_NO_REF:
101 case ZEND_SEND_VAR_NO_REF_EX:
102 case ZEND_FE_RESET_RW:
103 case ZEND_ASSIGN_ADD:
104 case ZEND_ASSIGN_SUB:
105 case ZEND_ASSIGN_MUL:
106 case ZEND_ASSIGN_DIV:
107 case ZEND_ASSIGN_MOD:
108 case ZEND_ASSIGN_SL:
109 case ZEND_ASSIGN_SR:
110 case ZEND_ASSIGN_CONCAT:
111 case ZEND_ASSIGN_BW_OR:
112 case ZEND_ASSIGN_BW_AND:
113 case ZEND_ASSIGN_BW_XOR:
114 case ZEND_ASSIGN_POW:
115 case ZEND_PRE_INC:
116 case ZEND_PRE_DEC:
117 case ZEND_POST_INC:
118 case ZEND_POST_DEC:
119 case ZEND_ASSIGN_DIM:
120 case ZEND_ASSIGN_OBJ:
121 case ZEND_UNSET_DIM:
122 case ZEND_UNSET_OBJ:
123 case ZEND_FETCH_DIM_W:
124 case ZEND_FETCH_DIM_RW:
125 case ZEND_FETCH_DIM_FUNC_ARG:
126 case ZEND_FETCH_DIM_UNSET:
127 case ZEND_FETCH_OBJ_W:
128 case ZEND_FETCH_OBJ_RW:
129 case ZEND_FETCH_OBJ_FUNC_ARG:
130 case ZEND_FETCH_OBJ_UNSET:
131 case ZEND_FETCH_LIST_W:
132 case ZEND_VERIFY_RETURN_TYPE:
133 case ZEND_PRE_INC_OBJ:
134 case ZEND_PRE_DEC_OBJ:
135 case ZEND_POST_INC_OBJ:
136 case ZEND_POST_DEC_OBJ:
137 op1_def:
138 /* `def` always come along with dtor or separation,
139 * thus the origin var info might be also `use`d in the feature(CG) */
140 DFG_SET(use, set_size, j, var_num);
141 DFG_SET(def, set_size, j, var_num);
142 break;
143 default:
144 op1_use:
145 if (!DFG_ISSET(def, set_size, j, var_num)) {
146 DFG_SET(use, set_size, j, var_num);
147 }
148 }
149 } else if (opline->op1_type & (IS_VAR|IS_TMP_VAR)) {
150 var_num = EX_VAR_TO_NUM(opline->op1.var);
151 if (!DFG_ISSET(def, set_size, j, var_num)) {
152 DFG_SET(use, set_size, j, var_num);
153 }
154 if (opline->opcode == ZEND_VERIFY_RETURN_TYPE) {
155 DFG_SET(def, set_size, j, var_num);
156 }
157 }
158 if (opline->op2_type == IS_CV) {
159 var_num = EX_VAR_TO_NUM(opline->op2.var);
160 switch (opline->opcode) {
161 case ZEND_ASSIGN:
162 if (build_flags & ZEND_SSA_RC_INFERENCE) {
163 goto op2_def;
164 }
165 goto op2_use;
166 case ZEND_BIND_LEXICAL:
167 if ((build_flags & ZEND_SSA_RC_INFERENCE) || (opline->extended_value & ZEND_BIND_REF)) {
168 goto op2_def;
169 }
170 goto op2_use;
171 case ZEND_ASSIGN_REF:
172 case ZEND_FE_FETCH_R:
173 case ZEND_FE_FETCH_RW:
174 op2_def:
175 // FIXME: include into "use" too ...?
176 DFG_SET(use, set_size, j, var_num);
177 DFG_SET(def, set_size, j, var_num);
178 break;
179 default:
180 op2_use:
181 if (!DFG_ISSET(def, set_size, j, var_num)) {
182 DFG_SET(use, set_size, j, var_num);
183 }
184 break;
185 }
186 } else if (opline->op2_type & (IS_VAR|IS_TMP_VAR)) {
187 var_num = EX_VAR_TO_NUM(opline->op2.var);
188 if (opline->opcode == ZEND_FE_FETCH_R || opline->opcode == ZEND_FE_FETCH_RW) {
189 DFG_SET(def, set_size, j, var_num);
190 } else {
191 if (!DFG_ISSET(def, set_size, j, var_num)) {
192 DFG_SET(use, set_size, j, var_num);
193 }
194 }
195 }
196 if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
197 var_num = EX_VAR_TO_NUM(opline->result.var);
198 if ((build_flags & ZEND_SSA_USE_CV_RESULTS)
199 && opline->result_type == IS_CV) {
200 DFG_SET(use, set_size, j, var_num);
201 }
202 DFG_SET(def, set_size, j, var_num);
203 }
204 }
205 }
206 }
207
208 /* Calculate "in" and "out" sets */
209 {
210 uint32_t worklist_len = zend_bitset_len(blocks_count);
211 zend_bitset worklist;
212 ALLOCA_FLAG(use_heap);
213 worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap);
214 memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE);
215 for (j = 0; j < blocks_count; j++) {
216 zend_bitset_incl(worklist, j);
217 }
218 while (!zend_bitset_empty(worklist, worklist_len)) {
219 /* We use the last block on the worklist, because predecessors tend to be located
220 * before the succeeding block, so this converges faster. */
221 j = zend_bitset_last(worklist, worklist_len);
222 zend_bitset_excl(worklist, j);
223
224 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
225 continue;
226 }
227 if (blocks[j].successors_count != 0) {
228 zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size);
229 for (k = 1; k < blocks[j].successors_count; k++) {
230 zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size);
231 }
232 } else {
233 zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size);
234 }
235 zend_bitset_union_with_difference(tmp, DFG_BITSET(use, set_size, j), DFG_BITSET(out, set_size, j), DFG_BITSET(def, set_size, j), set_size);
236 if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) {
237 zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size);
238
239 /* Add predecessors of changed block to worklist */
240 {
241 int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset];
242 for (k = 0; k < blocks[j].predecessors_count; k++) {
243 zend_bitset_incl(worklist, predecessors[k]);
244 }
245 }
246 }
247 }
248
249 free_alloca(worklist, use_heap);
250 }
251
252 return SUCCESS;
253 }
254 /* }}} */
255
256 /*
257 * Local variables:
258 * tab-width: 4
259 * c-basic-offset: 4
260 * indent-tabs-mode: t
261 * End:
262 */
263
