1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, SSA - Static Single Assignment Form |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 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 | https://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 | Nikita Popov <nikic@php.net> |
17 +----------------------------------------------------------------------+
18 */
19
20 #include "zend_compile.h"
21 #include "zend_dfg.h"
22 #include "zend_ssa.h"
23 #include "zend_dump.h"
24 #include "zend_inference.h"
25 #include "Optimizer/zend_optimizer_internal.h"
26
dominates(const zend_basic_block * blocks,int a,int b)27 static bool dominates(const zend_basic_block *blocks, int a, int b) {
28 while (blocks[b].level > blocks[a].level) {
29 b = blocks[b].idom;
30 }
31 return a == b;
32 }
33
will_rejoin(const zend_cfg * cfg,const zend_dfg * dfg,const zend_basic_block * block,int other_successor,int exclude,int var)34 static bool will_rejoin(
35 const zend_cfg *cfg, const zend_dfg *dfg, const zend_basic_block *block,
36 int other_successor, int exclude, int var) {
37 int i;
38 for (i = 0; i < block->predecessors_count; i++) {
39 int predecessor = cfg->predecessors[block->predecessor_offset + i];
40 if (predecessor == exclude) {
41 continue;
42 }
43
44 /* The variable is changed in this predecessor,
45 * so we will not rejoin with the original value. */
46 // TODO: This should not be limited to the direct predecessor block.
47 if (DFG_ISSET(dfg->def, dfg->size, predecessor, var)) {
48 continue;
49 }
50
51 /* The other successor dominates this predecessor,
52 * so we will get the original value from it. */
53 if (dominates(cfg->blocks, other_successor, predecessor)) {
54 return 1;
55 }
56 }
57 return 0;
58 }
59
needs_pi(const zend_op_array * op_array,const zend_dfg * dfg,const zend_ssa * ssa,int from,int to,int var)60 static bool needs_pi(const zend_op_array *op_array, const zend_dfg *dfg, const zend_ssa *ssa, int from, int to, int var) /* {{{ */
61 {
62 const zend_basic_block *from_block, *to_block;
63 int other_successor;
64
65 if (!DFG_ISSET(dfg->in, dfg->size, to, var)) {
66 /* Variable is not live, certainly won't benefit from pi */
67 return 0;
68 }
69
70 /* Make sure that both successors of the from block aren't the same. Pi nodes are associated
71 * with predecessor blocks, so we can't distinguish which edge the pi belongs to. */
72 from_block = &ssa->cfg.blocks[from];
73 ZEND_ASSERT(from_block->successors_count == 2);
74 if (from_block->successors[0] == from_block->successors[1]) {
75 return 0;
76 }
77
78 to_block = &ssa->cfg.blocks[to];
79 if (to_block->predecessors_count == 1) {
80 /* Always place pi if one predecessor (an if branch) */
81 return 1;
82 }
83
84 /* Check whether we will rejoin with the original value coming from the other successor,
85 * in which case the pi node will not have an effect. */
86 other_successor = from_block->successors[0] == to
87 ? from_block->successors[1] : from_block->successors[0];
88 return !will_rejoin(&ssa->cfg, dfg, to_block, other_successor, from, var);
89 }
90 /* }}} */
91
add_pi(zend_arena ** arena,const zend_op_array * op_array,zend_dfg * dfg,zend_ssa * ssa,int from,int to,int var)92 static zend_ssa_phi *add_pi(
93 zend_arena **arena, const zend_op_array *op_array, zend_dfg *dfg, zend_ssa *ssa,
94 int from, int to, int var) /* {{{ */
95 {
96 zend_ssa_phi *phi;
97 if (!needs_pi(op_array, dfg, ssa, from, to, var)) {
98 return NULL;
99 }
100
101 phi = zend_arena_calloc(arena, 1,
102 ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)) +
103 ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[to].predecessors_count) +
104 sizeof(void*) * ssa->cfg.blocks[to].predecessors_count);
105 phi->sources = (int*)(((char*)phi) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)));
106 memset(phi->sources, 0xff, sizeof(int) * ssa->cfg.blocks[to].predecessors_count);
107 phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[to].predecessors_count));
108
109 phi->pi = from;
110 phi->var = var;
111 phi->ssa_var = -1;
112 phi->next = ssa->blocks[to].phis;
113 ssa->blocks[to].phis = phi;
114
115 /* Block "to" now defines "var" via the pi statement, so add it to the "def" set. Note that
116 * this is not entirely accurate, because the pi is actually placed along the edge from->to.
117 * If there is a back-edge to "to" this may result in non-minimal SSA form. */
118 DFG_SET(dfg->def, dfg->size, to, var);
119
120 /* If there are multiple predecessors in the target block, we need to place a phi there.
121 * However this can (generally) not be expressed in terms of dominance frontiers, so place it
122 * explicitly. dfg->use here really is dfg->phi, we're reusing the set. */
123 if (ssa->cfg.blocks[to].predecessors_count > 1) {
124 DFG_SET(dfg->use, dfg->size, to, var);
125 }
126
127 return phi;
128 }
129 /* }}} */
130
pi_range(zend_ssa_phi * phi,int min_var,int max_var,zend_long min,zend_long max,char underflow,char overflow,char negative)131 static void pi_range(
132 zend_ssa_phi *phi, int min_var, int max_var, zend_long min, zend_long max,
133 char underflow, char overflow, char negative) /* {{{ */
134 {
135 zend_ssa_range_constraint *constraint = &phi->constraint.range;
136 constraint->min_var = min_var;
137 constraint->max_var = max_var;
138 constraint->min_ssa_var = -1;
139 constraint->max_ssa_var = -1;
140 constraint->range.min = min;
141 constraint->range.max = max;
142 constraint->range.underflow = underflow;
143 constraint->range.overflow = overflow;
144 constraint->negative = negative ? NEG_INIT : NEG_NONE;
145 phi->has_range_constraint = true;
146 }
147 /* }}} */
148
pi_range_equals(zend_ssa_phi * phi,int var,zend_long val)149 static inline void pi_range_equals(zend_ssa_phi *phi, int var, zend_long val) {
150 pi_range(phi, var, var, val, val, 0, 0, 0);
151 }
pi_range_not_equals(zend_ssa_phi * phi,int var,zend_long val)152 static inline void pi_range_not_equals(zend_ssa_phi *phi, int var, zend_long val) {
153 pi_range(phi, var, var, val, val, 0, 0, 1);
154 }
pi_range_min(zend_ssa_phi * phi,int var,zend_long val)155 static inline void pi_range_min(zend_ssa_phi *phi, int var, zend_long val) {
156 pi_range(phi, var, -1, val, ZEND_LONG_MAX, 0, 1, 0);
157 }
pi_range_max(zend_ssa_phi * phi,int var,zend_long val)158 static inline void pi_range_max(zend_ssa_phi *phi, int var, zend_long val) {
159 pi_range(phi, -1, var, ZEND_LONG_MIN, val, 1, 0, 0);
160 }
161
pi_type_mask(zend_ssa_phi * phi,uint32_t type_mask)162 static void pi_type_mask(zend_ssa_phi *phi, uint32_t type_mask) {
163 phi->has_range_constraint = false;
164 phi->constraint.type.ce = NULL;
165 phi->constraint.type.type_mask = MAY_BE_REF|MAY_BE_RC1|MAY_BE_RCN;
166 phi->constraint.type.type_mask |= type_mask;
167 if (type_mask & MAY_BE_NULL) {
168 phi->constraint.type.type_mask |= MAY_BE_UNDEF;
169 }
170 }
pi_not_type_mask(zend_ssa_phi * phi,uint32_t type_mask)171 static inline void pi_not_type_mask(zend_ssa_phi *phi, uint32_t type_mask) {
172 uint32_t relevant = MAY_BE_ANY|MAY_BE_ARRAY_KEY_ANY|MAY_BE_ARRAY_OF_ANY|MAY_BE_ARRAY_OF_REF;
173 pi_type_mask(phi, ~type_mask & relevant);
174 }
mask_for_type_check(uint32_t type)175 static inline uint32_t mask_for_type_check(uint32_t type) {
176 if (type & MAY_BE_ARRAY) {
177 return type | (MAY_BE_ARRAY_KEY_ANY|MAY_BE_ARRAY_OF_ANY|MAY_BE_ARRAY_OF_REF);
178 } else {
179 return type;
180 }
181 }
182
183 /* We can interpret $a + 5 == 0 as $a = 0 - 5, i.e. shift the adjustment to the other operand.
184 * This negated adjustment is what is written into the "adjustment" parameter. */
find_adjusted_tmp_var(const zend_op_array * op_array,uint32_t build_flags,zend_op * opline,uint32_t var_num,zend_long * adjustment)185 static int find_adjusted_tmp_var(const zend_op_array *op_array, uint32_t build_flags, zend_op *opline, uint32_t var_num, zend_long *adjustment) /* {{{ */
186 {
187 zend_op *op = opline;
188 zval *zv;
189
190 while (op != op_array->opcodes) {
191 op--;
192 if (op->result_type != IS_TMP_VAR || op->result.var != var_num) {
193 continue;
194 }
195
196 if (op->opcode == ZEND_POST_DEC) {
197 if (op->op1_type == IS_CV) {
198 *adjustment = -1;
199 return EX_VAR_TO_NUM(op->op1.var);
200 }
201 } else if (op->opcode == ZEND_POST_INC) {
202 if (op->op1_type == IS_CV) {
203 *adjustment = 1;
204 return EX_VAR_TO_NUM(op->op1.var);
205 }
206 } else if (op->opcode == ZEND_ADD) {
207 if (op->op1_type == IS_CV && op->op2_type == IS_CONST) {
208 zv = CRT_CONSTANT_EX(op_array, op, op->op2);
209 if (Z_TYPE_P(zv) == IS_LONG
210 && Z_LVAL_P(zv) != ZEND_LONG_MIN) {
211 *adjustment = -Z_LVAL_P(zv);
212 return EX_VAR_TO_NUM(op->op1.var);
213 }
214 } else if (op->op2_type == IS_CV && op->op1_type == IS_CONST) {
215 zv = CRT_CONSTANT_EX(op_array, op, op->op1);
216 if (Z_TYPE_P(zv) == IS_LONG
217 && Z_LVAL_P(zv) != ZEND_LONG_MIN) {
218 *adjustment = -Z_LVAL_P(zv);
219 return EX_VAR_TO_NUM(op->op2.var);
220 }
221 }
222 } else if (op->opcode == ZEND_SUB) {
223 if (op->op1_type == IS_CV && op->op2_type == IS_CONST) {
224 zv = CRT_CONSTANT_EX(op_array, op, op->op2);
225 if (Z_TYPE_P(zv) == IS_LONG) {
226 *adjustment = Z_LVAL_P(zv);
227 return EX_VAR_TO_NUM(op->op1.var);
228 }
229 }
230 }
231 break;
232 }
233 return -1;
234 }
235 /* }}} */
236
237 /* e-SSA construction: Pi placement (Pi is actually a Phi with single
238 * source and constraint).
239 * Order of Phis is important, Pis must be placed before Phis
240 */
place_essa_pis(zend_arena ** arena,const zend_script * script,const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa,zend_dfg * dfg)241 static void place_essa_pis(
242 zend_arena **arena, const zend_script *script, const zend_op_array *op_array,
243 uint32_t build_flags, zend_ssa *ssa, zend_dfg *dfg) /* {{{ */ {
244 zend_basic_block *blocks = ssa->cfg.blocks;
245 int j, blocks_count = ssa->cfg.blocks_count;
246 for (j = 0; j < blocks_count; j++) {
247 zend_ssa_phi *pi;
248 zend_op *opline = op_array->opcodes + blocks[j].start + blocks[j].len - 1;
249 int bt; /* successor block number if a condition is true */
250 int bf; /* successor block number if a condition is false */
251
252 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0 || blocks[j].len == 0) {
253 continue;
254 }
255 /* the last instruction of basic block is conditional branch,
256 * based on comparison of CV(s)
257 */
258 switch (opline->opcode) {
259 case ZEND_JMPZ:
260 bf = blocks[j].successors[0];
261 bt = blocks[j].successors[1];
262 break;
263 case ZEND_JMPNZ:
264 bt = blocks[j].successors[0];
265 bf = blocks[j].successors[1];
266 break;
267 case ZEND_COALESCE:
268 if (opline->op1_type == IS_CV) {
269 int var = EX_VAR_TO_NUM(opline->op1.var);
270 if ((pi = add_pi(arena, op_array, dfg, ssa, j, blocks[j].successors[0], var))) {
271 pi_not_type_mask(pi, MAY_BE_NULL);
272 }
273 }
274 continue;
275 case ZEND_JMP_NULL:
276 if (opline->op1_type == IS_CV) {
277 int var = EX_VAR_TO_NUM(opline->op1.var);
278 if ((pi = add_pi(arena, op_array, dfg, ssa, j, blocks[j].successors[1], var))) {
279 pi_not_type_mask(pi, MAY_BE_NULL);
280 }
281 }
282 continue;
283 default:
284 continue;
285 }
286
287 /* The following patterns all inspect the opline directly before the JMPZ opcode.
288 * Make sure that it is part of the same block, otherwise it might not be a dominating
289 * assignment. */
290 if (blocks[j].len == 1) {
291 continue;
292 }
293
294 if (opline->op1_type == IS_TMP_VAR &&
295 ((opline-1)->opcode == ZEND_IS_EQUAL ||
296 (opline-1)->opcode == ZEND_IS_NOT_EQUAL ||
297 (opline-1)->opcode == ZEND_IS_SMALLER ||
298 (opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) &&
299 opline->op1.var == (opline-1)->result.var) {
300 int var1 = -1;
301 int var2 = -1;
302 zend_long val1 = 0;
303 zend_long val2 = 0;
304 // long val = 0;
305
306 if ((opline-1)->op1_type == IS_CV) {
307 var1 = EX_VAR_TO_NUM((opline-1)->op1.var);
308 } else if ((opline-1)->op1_type == IS_TMP_VAR) {
309 var1 = find_adjusted_tmp_var(
310 op_array, build_flags, opline, (opline-1)->op1.var, &val2);
311 }
312
313 if ((opline-1)->op2_type == IS_CV) {
314 var2 = EX_VAR_TO_NUM((opline-1)->op2.var);
315 } else if ((opline-1)->op2_type == IS_TMP_VAR) {
316 var2 = find_adjusted_tmp_var(
317 op_array, build_flags, opline, (opline-1)->op2.var, &val1);
318 }
319
320 if (var1 >= 0 && var2 >= 0) {
321 if (!zend_sub_will_overflow(val1, val2) && !zend_sub_will_overflow(val2, val1)) {
322 zend_long tmp = val1;
323 val1 -= val2;
324 val2 -= tmp;
325 } else {
326 var1 = -1;
327 var2 = -1;
328 }
329 } else if (var1 >= 0 && var2 < 0) {
330 zend_long add_val2 = 0;
331 if ((opline-1)->op2_type == IS_CONST) {
332 zval *zv = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2);
333
334 if (Z_TYPE_P(zv) == IS_LONG) {
335 add_val2 = Z_LVAL_P(zv);
336 } else {
337 var1 = -1;
338 }
339 } else {
340 var1 = -1;
341 }
342 if (!zend_add_will_overflow(val2, add_val2)) {
343 val2 += add_val2;
344 } else {
345 var1 = -1;
346 }
347 } else if (var1 < 0 && var2 >= 0) {
348 zend_long add_val1 = 0;
349 if ((opline-1)->op1_type == IS_CONST) {
350 zval *zv = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1);
351 if (Z_TYPE_P(zv) == IS_LONG) {
352 add_val1 = Z_LVAL_P(CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1));
353 } else {
354 var2 = -1;
355 }
356 } else {
357 var2 = -1;
358 }
359 if (!zend_add_will_overflow(val1, add_val1)) {
360 val1 += add_val1;
361 } else {
362 var2 = -1;
363 }
364 }
365
366 if (var1 >= 0) {
367 if ((opline-1)->opcode == ZEND_IS_EQUAL) {
368 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
369 pi_range_equals(pi, var2, val2);
370 }
371 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
372 pi_range_not_equals(pi, var2, val2);
373 }
374 } else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) {
375 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
376 pi_range_equals(pi, var2, val2);
377 }
378 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
379 pi_range_not_equals(pi, var2, val2);
380 }
381 } else if ((opline-1)->opcode == ZEND_IS_SMALLER) {
382 if (val2 > ZEND_LONG_MIN) {
383 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
384 pi_range_max(pi, var2, val2-1);
385 }
386 }
387 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
388 pi_range_min(pi, var2, val2);
389 }
390 } else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) {
391 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
392 pi_range_max(pi, var2, val2);
393 }
394 if (val2 < ZEND_LONG_MAX) {
395 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
396 pi_range_min(pi, var2, val2+1);
397 }
398 }
399 }
400 }
401 if (var2 >= 0) {
402 if((opline-1)->opcode == ZEND_IS_EQUAL) {
403 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
404 pi_range_equals(pi, var1, val1);
405 }
406 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
407 pi_range_not_equals(pi, var1, val1);
408 }
409 } else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) {
410 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
411 pi_range_equals(pi, var1, val1);
412 }
413 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
414 pi_range_not_equals(pi, var1, val1);
415 }
416 } else if ((opline-1)->opcode == ZEND_IS_SMALLER) {
417 if (val1 < ZEND_LONG_MAX) {
418 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
419 pi_range_min(pi, var1, val1+1);
420 }
421 }
422 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
423 pi_range_max(pi, var1, val1);
424 }
425 } else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) {
426 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
427 pi_range_min(pi, var1, val1);
428 }
429 if (val1 > ZEND_LONG_MIN) {
430 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
431 pi_range_max(pi, var1, val1-1);
432 }
433 }
434 }
435 }
436 } else if (opline->op1_type == IS_TMP_VAR &&
437 ((opline-1)->opcode == ZEND_POST_INC ||
438 (opline-1)->opcode == ZEND_POST_DEC) &&
439 opline->op1.var == (opline-1)->result.var &&
440 (opline-1)->op1_type == IS_CV) {
441 int var = EX_VAR_TO_NUM((opline-1)->op1.var);
442
443 if ((opline-1)->opcode == ZEND_POST_DEC) {
444 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
445 pi_range_equals(pi, -1, -1);
446 }
447 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
448 pi_range_not_equals(pi, -1, -1);
449 }
450 } else if ((opline-1)->opcode == ZEND_POST_INC) {
451 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
452 pi_range_equals(pi, -1, 1);
453 }
454 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
455 pi_range_not_equals(pi, -1, 1);
456 }
457 }
458 } else if (opline->op1_type == IS_TMP_VAR &&
459 ((opline-1)->opcode == ZEND_PRE_INC ||
460 (opline-1)->opcode == ZEND_PRE_DEC) &&
461 opline->op1.var == (opline-1)->result.var &&
462 (opline-1)->op1_type == IS_CV) {
463 int var = EX_VAR_TO_NUM((opline-1)->op1.var);
464
465 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
466 pi_range_equals(pi, -1, 0);
467 }
468 /* speculative */
469 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
470 pi_range_not_equals(pi, -1, 0);
471 }
472 } else if (opline->op1_type == IS_TMP_VAR && (opline-1)->opcode == ZEND_TYPE_CHECK &&
473 opline->op1.var == (opline-1)->result.var && (opline-1)->op1_type == IS_CV) {
474 int var = EX_VAR_TO_NUM((opline-1)->op1.var);
475 uint32_t type = (opline-1)->extended_value;
476 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
477 pi_type_mask(pi, mask_for_type_check(type));
478 }
479 if (type != MAY_BE_RESOURCE) {
480 /* is_resource() may return false for closed resources */
481 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
482 pi_not_type_mask(pi, mask_for_type_check(type));
483 }
484 }
485 } else if (opline->op1_type == IS_TMP_VAR &&
486 ((opline-1)->opcode == ZEND_IS_IDENTICAL
487 || (opline-1)->opcode == ZEND_IS_NOT_IDENTICAL) &&
488 opline->op1.var == (opline-1)->result.var) {
489 int var;
490 zval *val;
491 uint32_t type_mask;
492 if ((opline-1)->op1_type == IS_CV && (opline-1)->op2_type == IS_CONST) {
493 var = EX_VAR_TO_NUM((opline-1)->op1.var);
494 val = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2);
495 } else if ((opline-1)->op1_type == IS_CONST && (opline-1)->op2_type == IS_CV) {
496 var = EX_VAR_TO_NUM((opline-1)->op2.var);
497 val = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1);
498 } else {
499 continue;
500 }
501
502 /* We're interested in === null/true/false comparisons here, because they eliminate
503 * a type in the false-branch. Other === VAL comparisons are unlikely to be useful. */
504 if (Z_TYPE_P(val) != IS_NULL && Z_TYPE_P(val) != IS_TRUE && Z_TYPE_P(val) != IS_FALSE) {
505 continue;
506 }
507
508 type_mask = _const_op_type(val);
509 if ((opline-1)->opcode == ZEND_IS_IDENTICAL) {
510 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
511 pi_type_mask(pi, type_mask);
512 }
513 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
514 pi_not_type_mask(pi, type_mask);
515 }
516 } else {
517 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
518 pi_type_mask(pi, type_mask);
519 }
520 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
521 pi_not_type_mask(pi, type_mask);
522 }
523 }
524 } else if (opline->op1_type == IS_TMP_VAR && (opline-1)->opcode == ZEND_INSTANCEOF &&
525 opline->op1.var == (opline-1)->result.var && (opline-1)->op1_type == IS_CV &&
526 (opline-1)->op2_type == IS_CONST) {
527 int var = EX_VAR_TO_NUM((opline-1)->op1.var);
528 zend_string *lcname = Z_STR_P(CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2) + 1);
529 zend_class_entry *ce = zend_optimizer_get_class_entry(script, op_array, lcname);
530 if (!ce) {
531 continue;
532 }
533
534 if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
535 pi_type_mask(pi, MAY_BE_OBJECT);
536 pi->constraint.type.ce = ce;
537 }
538 }
539 }
540 }
541 /* }}} */
542
_zend_ssa_rename_op(const zend_op_array * op_array,const zend_op * opline,uint32_t k,uint32_t build_flags,int ssa_vars_count,zend_ssa_op * ssa_ops,int * var)543 static zend_always_inline int _zend_ssa_rename_op(const zend_op_array *op_array, const zend_op *opline, uint32_t k, uint32_t build_flags, int ssa_vars_count, zend_ssa_op *ssa_ops, int *var) /* {{{ */
544 {
545 const zend_op *next;
546
547 if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
548 ssa_ops[k].op1_use = var[EX_VAR_TO_NUM(opline->op1.var)];
549 //USE_SSA_VAR(op_array->last_var + opline->op1.var)
550 }
551 if (opline->op2_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
552 ssa_ops[k].op2_use = var[EX_VAR_TO_NUM(opline->op2.var)];
553 //USE_SSA_VAR(op_array->last_var + opline->op2.var)
554 }
555 if ((build_flags & ZEND_SSA_USE_CV_RESULTS)
556 && opline->result_type == IS_CV
557 && opline->opcode != ZEND_RECV) {
558 ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
559 //USE_SSA_VAR(op_array->last_var + opline->result.var)
560 }
561
562 switch (opline->opcode) {
563 case ZEND_ASSIGN:
564 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) {
565 ssa_ops[k].op2_def = ssa_vars_count;
566 var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
567 ssa_vars_count++;
568 //NEW_SSA_VAR(opline->op2.var)
569 }
570 if (opline->op1_type == IS_CV) {
571 add_op1_def:
572 ssa_ops[k].op1_def = ssa_vars_count;
573 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
574 ssa_vars_count++;
575 //NEW_SSA_VAR(opline->op1.var)
576 }
577 break;
578 case ZEND_ASSIGN_REF:
579 if (opline->op2_type == IS_CV) {
580 ssa_ops[k].op2_def = ssa_vars_count;
581 var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
582 ssa_vars_count++;
583 //NEW_SSA_VAR(opline->op2.var)
584 }
585 if (opline->op1_type == IS_CV) {
586 goto add_op1_def;
587 }
588 break;
589 case ZEND_ASSIGN_DIM:
590 case ZEND_ASSIGN_OBJ:
591 next = opline + 1;
592 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
593 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
594 //USE_SSA_VAR(op_array->last_var + next->op1.var);
595 if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) {
596 ssa_ops[k + 1].op1_def = ssa_vars_count;
597 var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
598 ssa_vars_count++;
599 //NEW_SSA_VAR(next->op1.var)
600 }
601 }
602 if (opline->op1_type == IS_CV) {
603 ssa_ops[k].op1_def = ssa_vars_count;
604 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
605 ssa_vars_count++;
606 //NEW_SSA_VAR(opline->op1.var)
607 }
608 break;
609 case ZEND_ASSIGN_OBJ_REF:
610 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
611 ssa_ops[k].op1_def = ssa_vars_count;
612 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
613 ssa_vars_count++;
614 //NEW_SSA_VAR(opline->op1.var)
615 }
616 next = opline + 1;
617 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
618 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
619 //USE_SSA_VAR(op_array->last_var + next->op1.var);
620 if (next->op1_type == IS_CV) {
621 ssa_ops[k + 1].op1_def = ssa_vars_count;
622 var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
623 ssa_vars_count++;
624 //NEW_SSA_VAR(next->op1.var)
625 }
626 }
627 break;
628 case ZEND_ASSIGN_STATIC_PROP:
629 next = opline + 1;
630 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
631 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
632 //USE_SSA_VAR(op_array->last_var + next->op1.var);
633 if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) {
634 ssa_ops[k + 1].op1_def = ssa_vars_count;
635 var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
636 ssa_vars_count++;
637 //NEW_SSA_VAR(next->op1.var)
638 }
639 }
640 break;
641 case ZEND_ASSIGN_STATIC_PROP_REF:
642 next = opline + 1;
643 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
644 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
645 //USE_SSA_VAR(op_array->last_var + next->op1.var);
646 if (next->op1_type == IS_CV) {
647 ssa_ops[k + 1].op1_def = ssa_vars_count;
648 var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
649 ssa_vars_count++;
650 //NEW_SSA_VAR(next->op1.var)
651 }
652 }
653 break;
654 case ZEND_ASSIGN_STATIC_PROP_OP:
655 next = opline + 1;
656 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
657 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
658 //USE_SSA_VAR(op_array->last_var + next->op1.var);
659 }
660 break;
661 case ZEND_ASSIGN_DIM_OP:
662 case ZEND_ASSIGN_OBJ_OP:
663 if (opline->op1_type == IS_CV) {
664 ssa_ops[k].op1_def = ssa_vars_count;
665 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
666 ssa_vars_count++;
667 //NEW_SSA_VAR(opline->op1.var)
668 }
669 next = opline + 1;
670 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
671 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
672 //USE_SSA_VAR(op_array->last_var + next->op1.var);
673 }
674 break;
675 case ZEND_ASSIGN_OP:
676 case ZEND_PRE_INC:
677 case ZEND_PRE_DEC:
678 case ZEND_POST_INC:
679 case ZEND_POST_DEC:
680 case ZEND_BIND_GLOBAL:
681 case ZEND_BIND_STATIC:
682 case ZEND_BIND_INIT_STATIC_OR_JMP:
683 case ZEND_SEND_VAR_NO_REF:
684 case ZEND_SEND_VAR_NO_REF_EX:
685 case ZEND_SEND_VAR_EX:
686 case ZEND_SEND_FUNC_ARG:
687 case ZEND_SEND_REF:
688 case ZEND_SEND_UNPACK:
689 case ZEND_FE_RESET_RW:
690 case ZEND_MAKE_REF:
691 case ZEND_PRE_INC_OBJ:
692 case ZEND_PRE_DEC_OBJ:
693 case ZEND_POST_INC_OBJ:
694 case ZEND_POST_DEC_OBJ:
695 case ZEND_UNSET_DIM:
696 case ZEND_UNSET_OBJ:
697 case ZEND_FETCH_DIM_W:
698 case ZEND_FETCH_DIM_RW:
699 case ZEND_FETCH_DIM_FUNC_ARG:
700 case ZEND_FETCH_DIM_UNSET:
701 case ZEND_FETCH_LIST_W:
702 if (opline->op1_type == IS_CV) {
703 goto add_op1_def;
704 }
705 break;
706 case ZEND_SEND_VAR:
707 case ZEND_CAST:
708 case ZEND_QM_ASSIGN:
709 case ZEND_JMP_SET:
710 case ZEND_COALESCE:
711 case ZEND_FE_RESET_R:
712 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
713 goto add_op1_def;
714 }
715 break;
716 case ZEND_ADD_ARRAY_UNPACK:
717 ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
718 break;
719 case ZEND_ADD_ARRAY_ELEMENT:
720 ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
721 ZEND_FALLTHROUGH;
722 case ZEND_INIT_ARRAY:
723 if (((build_flags & ZEND_SSA_RC_INFERENCE)
724 || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF))
725 && opline->op1_type == IS_CV) {
726 goto add_op1_def;
727 }
728 break;
729 case ZEND_YIELD:
730 if (opline->op1_type == IS_CV
731 && ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)
732 || (build_flags & ZEND_SSA_RC_INFERENCE))) {
733 goto add_op1_def;
734 }
735 break;
736 case ZEND_UNSET_CV:
737 goto add_op1_def;
738 case ZEND_VERIFY_RETURN_TYPE:
739 if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) {
740 goto add_op1_def;
741 }
742 break;
743 case ZEND_FE_FETCH_R:
744 case ZEND_FE_FETCH_RW:
745 if (opline->op2_type != IS_CV) {
746 ssa_ops[k].op2_use = -1; /* not used */
747 }
748 ssa_ops[k].op2_def = ssa_vars_count;
749 var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
750 ssa_vars_count++;
751 //NEW_SSA_VAR(opline->op2.var)
752 break;
753 case ZEND_BIND_LEXICAL:
754 if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) {
755 ssa_ops[k].op2_def = ssa_vars_count;
756 var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
757 ssa_vars_count++;
758 //NEW_SSA_VAR(opline->op2.var)
759 }
760 break;
761 case ZEND_COPY_TMP:
762 if (build_flags & ZEND_SSA_RC_INFERENCE) {
763 ssa_ops[k].op1_def = ssa_vars_count;
764 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
765 ssa_vars_count++;
766 //NEW_SSA_VAR(opline->op1.var)
767 }
768 break;
769 case ZEND_FRAMELESS_ICALL_1:
770 case ZEND_FRAMELESS_ICALL_2:
771 case ZEND_FRAMELESS_ICALL_3: {
772 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
773 ssa_ops[k].op1_def = ssa_vars_count;
774 var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
775 ssa_vars_count++;
776 //NEW_SSA_VAR(opline->op1.var)
777 }
778 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) {
779 ssa_ops[k].op2_def = ssa_vars_count;
780 var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
781 ssa_vars_count++;
782 //NEW_SSA_VAR(opline->op2.var)
783 }
784 if (opline->opcode == ZEND_FRAMELESS_ICALL_3) {
785 next = opline + 1;
786 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
787 ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
788 //USE_SSA_VAR(op_array->last_var + next->op1.var);
789 if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) {
790 ssa_ops[k + 1].op1_def = ssa_vars_count;
791 var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
792 ssa_vars_count++;
793 //NEW_SSA_VAR(next->op1.var)
794 }
795 }
796 }
797 }
798 default:
799 break;
800 }
801
802 if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
803 ssa_ops[k].result_def = ssa_vars_count;
804 var[EX_VAR_TO_NUM(opline->result.var)] = ssa_vars_count;
805 ssa_vars_count++;
806 //NEW_SSA_VAR(op_array->last_var + opline->result.var)
807 }
808
809 return ssa_vars_count;
810 }
811 /* }}} */
812
zend_ssa_rename_op(const zend_op_array * op_array,const zend_op * opline,uint32_t k,uint32_t build_flags,int ssa_vars_count,zend_ssa_op * ssa_ops,int * var)813 ZEND_API int zend_ssa_rename_op(const zend_op_array *op_array, const zend_op *opline, uint32_t k, uint32_t build_flags, int ssa_vars_count, zend_ssa_op *ssa_ops, int *var) /* {{{ */
814 {
815 return _zend_ssa_rename_op(op_array, opline, k, build_flags, ssa_vars_count, ssa_ops, var);
816 }
817 /* }}} */
818
zend_ssa_rename(const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa,int * var,int n)819 static zend_result zend_ssa_rename(const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa, int *var, int n) /* {{{ */
820 {
821 zend_basic_block *blocks = ssa->cfg.blocks;
822 zend_ssa_block *ssa_blocks = ssa->blocks;
823 zend_ssa_op *ssa_ops = ssa->ops;
824 int ssa_vars_count = ssa->vars_count;
825 int i, j;
826 zend_op *opline, *end;
827 int *tmp = NULL;
828 ALLOCA_FLAG(use_heap = 0);
829
830 // FIXME: Can we optimize this copying out in some cases?
831 if (blocks[n].next_child >= 0) {
832 tmp = do_alloca(sizeof(int) * (op_array->last_var + op_array->T), use_heap);
833 memcpy(tmp, var, sizeof(int) * (op_array->last_var + op_array->T));
834 var = tmp;
835 }
836
837 if (ssa_blocks[n].phis) {
838 zend_ssa_phi *phi = ssa_blocks[n].phis;
839 do {
840 if (phi->ssa_var < 0) {
841 phi->ssa_var = ssa_vars_count;
842 var[phi->var] = ssa_vars_count;
843 ssa_vars_count++;
844 } else {
845 var[phi->var] = phi->ssa_var;
846 }
847 phi = phi->next;
848 } while (phi);
849 }
850
851 opline = op_array->opcodes + blocks[n].start;
852 end = opline + blocks[n].len;
853 for (; opline < end; opline++) {
854 uint32_t k = opline - op_array->opcodes;
855 if (opline->opcode != ZEND_OP_DATA) {
856 ssa_vars_count = _zend_ssa_rename_op(op_array, opline, k, build_flags, ssa_vars_count, ssa_ops, var);
857 }
858 }
859
860 zend_ssa_op *fe_fetch_ssa_op = blocks[n].len != 0
861 && ((end-1)->opcode == ZEND_FE_FETCH_R || (end-1)->opcode == ZEND_FE_FETCH_RW)
862 && (end-1)->op2_type == IS_CV
863 ? &ssa_ops[blocks[n].start + blocks[n].len - 1] : NULL;
864 for (i = 0; i < blocks[n].successors_count; i++) {
865 int succ = blocks[n].successors[i];
866 zend_ssa_phi *p;
867 for (p = ssa_blocks[succ].phis; p; p = p->next) {
868 if (p->pi == n) {
869 /* e-SSA Pi */
870 if (p->has_range_constraint) {
871 if (p->constraint.range.min_var >= 0) {
872 p->constraint.range.min_ssa_var = var[p->constraint.range.min_var];
873 }
874 if (p->constraint.range.max_var >= 0) {
875 p->constraint.range.max_ssa_var = var[p->constraint.range.max_var];
876 }
877 }
878 for (j = 0; j < blocks[succ].predecessors_count; j++) {
879 p->sources[j] = var[p->var];
880 }
881 if (p->ssa_var < 0) {
882 p->ssa_var = ssa_vars_count;
883 ssa_vars_count++;
884 }
885 } else if (p->pi < 0) {
886 /* Normal Phi */
887 for (j = 0; j < blocks[succ].predecessors_count; j++)
888 if (ssa->cfg.predecessors[blocks[succ].predecessor_offset + j] == n) {
889 break;
890 }
891 ZEND_ASSERT(j < blocks[succ].predecessors_count);
892 p->sources[j] = var[p->var];
893 if (fe_fetch_ssa_op && i == 0 && p->sources[j] == fe_fetch_ssa_op->op2_def) {
894 /* On the exit edge of an FE_FETCH, use the pre-modification value instead. */
895 p->sources[j] = fe_fetch_ssa_op->op2_use;
896 }
897 }
898 }
899 for (p = ssa_blocks[succ].phis; p && (p->pi >= 0); p = p->next) {
900 if (p->pi == n) {
901 zend_ssa_phi *q = p->next;
902 while (q) {
903 if (q->pi < 0 && q->var == p->var) {
904 for (j = 0; j < blocks[succ].predecessors_count; j++) {
905 if (ssa->cfg.predecessors[blocks[succ].predecessor_offset + j] == n) {
906 break;
907 }
908 }
909 ZEND_ASSERT(j < blocks[succ].predecessors_count);
910 q->sources[j] = p->ssa_var;
911 }
912 q = q->next;
913 }
914 }
915 }
916 }
917
918 ssa->vars_count = ssa_vars_count;
919
920 j = blocks[n].children;
921 while (j >= 0) {
922 // FIXME: Tail call optimization?
923 if (zend_ssa_rename(op_array, build_flags, ssa, var, j) == FAILURE)
924 return FAILURE;
925 j = blocks[j].next_child;
926 }
927
928 if (tmp) {
929 free_alloca(tmp, use_heap);
930 }
931
932 return SUCCESS;
933 }
934 /* }}} */
935
zend_build_ssa(zend_arena ** arena,const zend_script * script,const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa)936 ZEND_API zend_result zend_build_ssa(zend_arena **arena, const zend_script *script, const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa) /* {{{ */
937 {
938 zend_basic_block *blocks = ssa->cfg.blocks;
939 zend_ssa_block *ssa_blocks;
940 int blocks_count = ssa->cfg.blocks_count;
941 uint32_t set_size;
942 zend_bitset def, in, phi;
943 int *var = NULL;
944 int i, j, k, changed;
945 zend_dfg dfg;
946 ALLOCA_FLAG(dfg_use_heap)
947 ALLOCA_FLAG(var_use_heap)
948
949 if ((blocks_count * (op_array->last_var + op_array->T)) > 4 * 1024 * 1024) {
950 /* Don't build SSA for very big functions */
951 return FAILURE;
952 }
953
954 ssa_blocks = zend_arena_calloc(arena, blocks_count, sizeof(zend_ssa_block));
955 ssa->blocks = ssa_blocks;
956
957 /* Compute Variable Liveness */
958 dfg.vars = op_array->last_var + op_array->T;
959 dfg.size = set_size = zend_bitset_len(dfg.vars);
960 dfg.tmp = do_alloca((set_size * sizeof(zend_ulong)) * (blocks_count * 4 + 1), dfg_use_heap);
961 memset(dfg.tmp, 0, (set_size * sizeof(zend_ulong)) * (blocks_count * 4 + 1));
962 dfg.def = dfg.tmp + set_size;
963 dfg.use = dfg.def + set_size * blocks_count;
964 dfg.in = dfg.use + set_size * blocks_count;
965 dfg.out = dfg.in + set_size * blocks_count;
966
967 zend_build_dfg(op_array, &ssa->cfg, &dfg, build_flags);
968
969 if (build_flags & ZEND_SSA_DEBUG_LIVENESS) {
970 zend_dump_dfg(op_array, &ssa->cfg, &dfg);
971 }
972
973 def = dfg.def;
974 in = dfg.in;
975
976 /* Reuse the "use" set, as we no longer need it */
977 phi = dfg.use;
978 zend_bitset_clear(phi, set_size * blocks_count);
979
980 /* Place e-SSA pis. This will add additional "def" points, so it must
981 * happen before def propagation. */
982 place_essa_pis(arena, script, op_array, build_flags, ssa, &dfg);
983
984 /* SSA construction, Step 1: Propagate "def" sets in merge points */
985 do {
986 changed = 0;
987 for (j = 0; j < blocks_count; j++) {
988 zend_bitset def_j = def + j * set_size, phi_j = phi + j * set_size;
989 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
990 continue;
991 }
992 if (blocks[j].predecessors_count > 1) {
993 if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) {
994 /* Prevent any values from flowing into irreducible loops by
995 replacing all incoming values with explicit phis. The
996 register allocator depends on this property. */
997 zend_bitset_union(phi_j, in + (j * set_size), set_size);
998 } else {
999 for (k = 0; k < blocks[j].predecessors_count; k++) {
1000 i = ssa->cfg.predecessors[blocks[j].predecessor_offset + k];
1001 while (i != -1 && i != blocks[j].idom) {
1002 zend_bitset_union_with_intersection(
1003 phi_j, phi_j, def + (i * set_size), in + (j * set_size), set_size);
1004 i = blocks[i].idom;
1005 }
1006 }
1007 }
1008 if (!zend_bitset_subset(phi_j, def_j, set_size)) {
1009 zend_bitset_union(def_j, phi_j, set_size);
1010 changed = 1;
1011 }
1012 }
1013 }
1014 } while (changed);
1015
1016 /* SSA construction, Step 2: Phi placement based on Dominance Frontiers */
1017 var = do_alloca(sizeof(int) * (op_array->last_var + op_array->T), var_use_heap);
1018 if (!var) {
1019 free_alloca(dfg.tmp, dfg_use_heap);
1020 return FAILURE;
1021 }
1022
1023 for (j = 0; j < blocks_count; j++) {
1024 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
1025 continue;
1026 }
1027 if (!zend_bitset_empty(phi + j * set_size, set_size)) {
1028 ZEND_BITSET_REVERSE_FOREACH(phi + j * set_size, set_size, i) {
1029 zend_ssa_phi *phi = zend_arena_calloc(arena, 1,
1030 ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)) +
1031 ZEND_MM_ALIGNED_SIZE(sizeof(int) * blocks[j].predecessors_count) +
1032 sizeof(void*) * blocks[j].predecessors_count);
1033
1034 phi->sources = (int*)(((char*)phi) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)));
1035 memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count);
1036 phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[j].predecessors_count));
1037
1038 phi->pi = -1;
1039 phi->var = i;
1040 phi->ssa_var = -1;
1041
1042 /* Place phis after pis */
1043 {
1044 zend_ssa_phi **pp = &ssa_blocks[j].phis;
1045 while (*pp) {
1046 if ((*pp)->pi < 0) {
1047 break;
1048 }
1049 pp = &(*pp)->next;
1050 }
1051 phi->next = *pp;
1052 *pp = phi;
1053 }
1054 } ZEND_BITSET_FOREACH_END();
1055 }
1056 }
1057
1058 if (build_flags & ZEND_SSA_DEBUG_PHI_PLACEMENT) {
1059 zend_dump_phi_placement(op_array, ssa);
1060 }
1061
1062 /* SSA construction, Step 3: Renaming */
1063 ssa->ops = zend_arena_calloc(arena, op_array->last, sizeof(zend_ssa_op));
1064 memset(ssa->ops, 0xff, op_array->last * sizeof(zend_ssa_op));
1065 memset(var + op_array->last_var, 0xff, op_array->T * sizeof(int));
1066 /* Create uninitialized SSA variables for each CV */
1067 for (j = 0; j < op_array->last_var; j++) {
1068 var[j] = j;
1069 }
1070 ssa->vars_count = op_array->last_var;
1071 if (zend_ssa_rename(op_array, build_flags, ssa, var, 0) == FAILURE) {
1072 free_alloca(var, var_use_heap);
1073 free_alloca(dfg.tmp, dfg_use_heap);
1074 return FAILURE;
1075 }
1076
1077 free_alloca(var, var_use_heap);
1078 free_alloca(dfg.tmp, dfg_use_heap);
1079
1080 return SUCCESS;
1081 }
1082 /* }}} */
1083
zend_ssa_compute_use_def_chains(zend_arena ** arena,const zend_op_array * op_array,zend_ssa * ssa)1084 ZEND_API void zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
1085 {
1086 zend_ssa_var *ssa_vars;
1087 int i;
1088
1089 if (!ssa->vars) {
1090 ssa->vars = zend_arena_calloc(arena, ssa->vars_count, sizeof(zend_ssa_var));
1091 }
1092 ssa_vars = ssa->vars;
1093
1094 for (i = 0; i < op_array->last_var; i++) {
1095 ssa_vars[i].var = i;
1096 ssa_vars[i].scc = -1;
1097 ssa_vars[i].definition = -1;
1098 ssa_vars[i].use_chain = -1;
1099 }
1100 for (i = op_array->last_var; i < ssa->vars_count; i++) {
1101 ssa_vars[i].var = -1;
1102 ssa_vars[i].scc = -1;
1103 ssa_vars[i].definition = -1;
1104 ssa_vars[i].use_chain = -1;
1105 }
1106
1107 for (i = op_array->last - 1; i >= 0; i--) {
1108 zend_ssa_op *op = ssa->ops + i;
1109
1110 if (op->op1_use >= 0) {
1111 op->op1_use_chain = ssa_vars[op->op1_use].use_chain;
1112 ssa_vars[op->op1_use].use_chain = i;
1113 }
1114 if (op->op2_use >= 0 && op->op2_use != op->op1_use) {
1115 op->op2_use_chain = ssa_vars[op->op2_use].use_chain;
1116 ssa_vars[op->op2_use].use_chain = i;
1117 }
1118 if (op->result_use >= 0 && op->result_use != op->op1_use && op->result_use != op->op2_use) {
1119 op->res_use_chain = ssa_vars[op->result_use].use_chain;
1120 ssa_vars[op->result_use].use_chain = i;
1121 }
1122 if (op->op1_def >= 0) {
1123 ssa_vars[op->op1_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].op1.var);
1124 ssa_vars[op->op1_def].definition = i;
1125 }
1126 if (op->op2_def >= 0) {
1127 ssa_vars[op->op2_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].op2.var);
1128 ssa_vars[op->op2_def].definition = i;
1129 }
1130 if (op->result_def >= 0) {
1131 ssa_vars[op->result_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].result.var);
1132 ssa_vars[op->result_def].definition = i;
1133 }
1134 }
1135
1136 for (i = 0; i < ssa->cfg.blocks_count; i++) {
1137 zend_ssa_phi *phi = ssa->blocks[i].phis;
1138 while (phi) {
1139 phi->block = i;
1140 ssa_vars[phi->ssa_var].var = phi->var;
1141 ssa_vars[phi->ssa_var].definition_phi = phi;
1142 if (phi->pi >= 0) {
1143 zend_ssa_phi *p;
1144
1145 ZEND_ASSERT(phi->sources[0] >= 0);
1146 p = ssa_vars[phi->sources[0]].phi_use_chain;
1147 while (p && p != phi) {
1148 p = zend_ssa_next_use_phi(ssa, phi->sources[0], p);
1149 }
1150 if (!p) {
1151 phi->use_chains[0] = ssa_vars[phi->sources[0]].phi_use_chain;
1152 ssa_vars[phi->sources[0]].phi_use_chain = phi;
1153 }
1154 if (phi->has_range_constraint) {
1155 /* min and max variables can't be used together */
1156 zend_ssa_range_constraint *constraint = &phi->constraint.range;
1157 if (constraint->min_ssa_var >= 0) {
1158 phi->sym_use_chain = ssa_vars[constraint->min_ssa_var].sym_use_chain;
1159 ssa_vars[constraint->min_ssa_var].sym_use_chain = phi;
1160 } else if (constraint->max_ssa_var >= 0) {
1161 phi->sym_use_chain = ssa_vars[constraint->max_ssa_var].sym_use_chain;
1162 ssa_vars[constraint->max_ssa_var].sym_use_chain = phi;
1163 }
1164 }
1165 } else {
1166 int j;
1167
1168 for (j = 0; j < ssa->cfg.blocks[i].predecessors_count; j++) {
1169 zend_ssa_phi *p;
1170
1171 ZEND_ASSERT(phi->sources[j] >= 0);
1172 p = ssa_vars[phi->sources[j]].phi_use_chain;
1173 while (p && p != phi) {
1174 p = zend_ssa_next_use_phi(ssa, phi->sources[j], p);
1175 }
1176 if (!p) {
1177 phi->use_chains[j] = ssa_vars[phi->sources[j]].phi_use_chain;
1178 ssa_vars[phi->sources[j]].phi_use_chain = phi;
1179 }
1180 }
1181 }
1182 phi = phi->next;
1183 }
1184 }
1185
1186 /* Mark indirectly accessed variables */
1187 for (i = 0; i < op_array->last_var; i++) {
1188 if ((ssa->cfg.flags & ZEND_FUNC_INDIRECT_VAR_ACCESS)) {
1189 ssa_vars[i].alias = SYMTABLE_ALIAS;
1190 } else if (zend_string_equals_literal(op_array->vars[i], "http_response_header")) {
1191 ssa_vars[i].alias = HTTP_RESPONSE_HEADER_ALIAS;
1192 }
1193 }
1194 for (i = op_array->last_var; i < ssa->vars_count; i++) {
1195 if (ssa_vars[i].var < op_array->last_var) {
1196 ssa_vars[i].alias = ssa_vars[ssa_vars[i].var].alias;
1197 }
1198 }
1199 }
1200 /* }}} */
1201
zend_ssa_unlink_use_chain(zend_ssa * ssa,int op,int var)1202 void zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var) /* {{{ */
1203 {
1204 if (ssa->vars[var].use_chain == op) {
1205 ssa->vars[var].use_chain = zend_ssa_next_use(ssa->ops, var, op);
1206 return;
1207 }
1208 int use = ssa->vars[var].use_chain;
1209
1210 while (use >= 0) {
1211 if (ssa->ops[use].result_use == var) {
1212 if (ssa->ops[use].res_use_chain == op) {
1213 ssa->ops[use].res_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1214 return;
1215 } else {
1216 use = ssa->ops[use].res_use_chain;
1217 }
1218 } else if (ssa->ops[use].op1_use == var) {
1219 if (ssa->ops[use].op1_use_chain == op) {
1220 ssa->ops[use].op1_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1221 return;
1222 } else {
1223 use = ssa->ops[use].op1_use_chain;
1224 }
1225 } else if (ssa->ops[use].op2_use == var) {
1226 if (ssa->ops[use].op2_use_chain == op) {
1227 ssa->ops[use].op2_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1228 return;
1229 } else {
1230 use = ssa->ops[use].op2_use_chain;
1231 }
1232 } else {
1233 break;
1234 }
1235 }
1236 /* something wrong */
1237 ZEND_UNREACHABLE();
1238 }
1239 /* }}} */
1240
zend_ssa_replace_use_chain(zend_ssa * ssa,int op,int new_op,int var)1241 void zend_ssa_replace_use_chain(zend_ssa *ssa, int op, int new_op, int var) /* {{{ */
1242 {
1243 if (ssa->vars[var].use_chain == op) {
1244 ssa->vars[var].use_chain = new_op;
1245 return;
1246 } else {
1247 int use = ssa->vars[var].use_chain;
1248
1249 while (use >= 0) {
1250 if (ssa->ops[use].result_use == var) {
1251 if (ssa->ops[use].res_use_chain == op) {
1252 ssa->ops[use].res_use_chain = new_op;
1253 return;
1254 } else {
1255 use = ssa->ops[use].res_use_chain;
1256 }
1257 } else if (ssa->ops[use].op1_use == var) {
1258 if (ssa->ops[use].op1_use_chain == op) {
1259 ssa->ops[use].op1_use_chain = new_op;
1260 return;
1261 } else {
1262 use = ssa->ops[use].op1_use_chain;
1263 }
1264 } else if (ssa->ops[use].op2_use == var) {
1265 if (ssa->ops[use].op2_use_chain == op) {
1266 ssa->ops[use].op2_use_chain = new_op;
1267 return;
1268 } else {
1269 use = ssa->ops[use].op2_use_chain;
1270 }
1271 } else {
1272 break;
1273 }
1274 }
1275 }
1276 /* something wrong */
1277 ZEND_UNREACHABLE();
1278 }
1279 /* }}} */
1280
zend_ssa_remove_instr(zend_ssa * ssa,zend_op * opline,zend_ssa_op * ssa_op)1281 void zend_ssa_remove_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op) /* {{{ */
1282 {
1283 if (ssa_op->result_use >= 0) {
1284 zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->result_use);
1285 ssa_op->result_use = -1;
1286 ssa_op->res_use_chain = -1;
1287 }
1288 if (ssa_op->op1_use >= 0) {
1289 if (ssa_op->op1_use != ssa_op->op2_use) {
1290 zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op1_use);
1291 } else {
1292 ssa_op->op2_use_chain = ssa_op->op1_use_chain;
1293 }
1294 ssa_op->op1_use = -1;
1295 ssa_op->op1_use_chain = -1;
1296 }
1297 if (ssa_op->op2_use >= 0) {
1298 zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op2_use);
1299 ssa_op->op2_use = -1;
1300 ssa_op->op2_use_chain = -1;
1301 }
1302
1303 /* We let the caller make sure that all defs are gone */
1304 ZEND_ASSERT(ssa_op->result_def == -1);
1305 ZEND_ASSERT(ssa_op->op1_def == -1);
1306 ZEND_ASSERT(ssa_op->op2_def == -1);
1307
1308 MAKE_NOP(opline);
1309 }
1310 /* }}} */
1311
zend_ssa_next_use_phi_ptr(zend_ssa * ssa,int var,zend_ssa_phi * p)1312 static inline zend_ssa_phi **zend_ssa_next_use_phi_ptr(zend_ssa *ssa, int var, zend_ssa_phi *p) /* {{{ */
1313 {
1314 if (p->pi >= 0) {
1315 return &p->use_chains[0];
1316 } else {
1317 int j;
1318 for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
1319 if (p->sources[j] == var) {
1320 return &p->use_chains[j];
1321 }
1322 }
1323 }
1324 ZEND_UNREACHABLE();
1325 return NULL;
1326 }
1327 /* }}} */
1328
1329 /* May be called even if source is not used in the phi (useful when removing uses in a phi
1330 * with multiple identical operands) */
zend_ssa_remove_use_of_phi_source(zend_ssa * ssa,zend_ssa_phi * phi,int source,zend_ssa_phi * next_use_phi)1331 static inline void zend_ssa_remove_use_of_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int source, zend_ssa_phi *next_use_phi) /* {{{ */
1332 {
1333 zend_ssa_phi **cur = &ssa->vars[source].phi_use_chain;
1334 while (*cur && *cur != phi) {
1335 cur = zend_ssa_next_use_phi_ptr(ssa, source, *cur);
1336 }
1337 if (*cur) {
1338 *cur = next_use_phi;
1339 }
1340 }
1341 /* }}} */
1342
zend_ssa_remove_uses_of_phi_sources(zend_ssa * ssa,zend_ssa_phi * phi)1343 static void zend_ssa_remove_uses_of_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1344 {
1345 int source;
1346 FOREACH_PHI_SOURCE(phi, source) {
1347 zend_ssa_remove_use_of_phi_source(ssa, phi, source, zend_ssa_next_use_phi(ssa, source, phi));
1348 } FOREACH_PHI_SOURCE_END();
1349 }
1350 /* }}} */
1351
zend_ssa_remove_phi_from_block(zend_ssa * ssa,zend_ssa_phi * phi)1352 static void zend_ssa_remove_phi_from_block(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1353 {
1354 zend_ssa_block *block = &ssa->blocks[phi->block];
1355 zend_ssa_phi **cur = &block->phis;
1356 while (*cur != phi) {
1357 ZEND_ASSERT(*cur != NULL);
1358 cur = &(*cur)->next;
1359 }
1360 *cur = (*cur)->next;
1361 }
1362 /* }}} */
1363
zend_ssa_remove_defs_of_instr(zend_ssa * ssa,zend_ssa_op * ssa_op)1364 void zend_ssa_remove_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) /* {{{ */
1365 {
1366 if (ssa_op->op1_def >= 0) {
1367 zend_ssa_remove_uses_of_var(ssa, ssa_op->op1_def);
1368 zend_ssa_remove_op1_def(ssa, ssa_op);
1369 }
1370 if (ssa_op->op2_def >= 0) {
1371 zend_ssa_remove_uses_of_var(ssa, ssa_op->op2_def);
1372 zend_ssa_remove_op2_def(ssa, ssa_op);
1373 }
1374 if (ssa_op->result_def >= 0) {
1375 zend_ssa_remove_uses_of_var(ssa, ssa_op->result_def);
1376 zend_ssa_remove_result_def(ssa, ssa_op);
1377 }
1378 }
1379 /* }}} */
1380
zend_ssa_remove_phi_source(zend_ssa * ssa,zend_ssa_phi * phi,int pred_offset,int predecessors_count)1381 static inline void zend_ssa_remove_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int pred_offset, int predecessors_count) /* {{{ */
1382 {
1383 int j, var_num = phi->sources[pred_offset];
1384 zend_ssa_phi *next_phi = phi->use_chains[pred_offset];
1385
1386 predecessors_count--;
1387 if (pred_offset < predecessors_count) {
1388 memmove(phi->sources + pred_offset, phi->sources + pred_offset + 1, (predecessors_count - pred_offset) * sizeof(uint32_t));
1389 memmove(phi->use_chains + pred_offset, phi->use_chains + pred_offset + 1, (predecessors_count - pred_offset) * sizeof(zend_ssa_phi*));
1390 }
1391
1392 /* Check if they same var is used in a different phi operand as well, in this case we don't
1393 * need to adjust the use chain (but may have to move the next pointer). */
1394 for (j = 0; j < predecessors_count; j++) {
1395 if (phi->sources[j] == var_num) {
1396 if (j < pred_offset) {
1397 ZEND_ASSERT(next_phi == NULL);
1398 } else if (j >= pred_offset) {
1399 phi->use_chains[j] = next_phi;
1400 }
1401 return;
1402 }
1403 }
1404
1405 /* Variable only used in one operand, remove the phi from the use chain. */
1406 zend_ssa_remove_use_of_phi_source(ssa, phi, var_num, next_phi);
1407 }
1408 /* }}} */
1409
zend_ssa_remove_phi(zend_ssa * ssa,zend_ssa_phi * phi)1410 void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1411 {
1412 ZEND_ASSERT(phi->ssa_var >= 0);
1413 ZEND_ASSERT(ssa->vars[phi->ssa_var].use_chain < 0
1414 && ssa->vars[phi->ssa_var].phi_use_chain == NULL);
1415 zend_ssa_remove_uses_of_phi_sources(ssa, phi);
1416 zend_ssa_remove_phi_from_block(ssa, phi);
1417 ssa->vars[phi->ssa_var].definition_phi = NULL;
1418 phi->ssa_var = -1;
1419 }
1420 /* }}} */
1421
zend_ssa_remove_uses_of_var(zend_ssa * ssa,int var_num)1422 void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num) /* {{{ */
1423 {
1424 zend_ssa_var *var = &ssa->vars[var_num];
1425 zend_ssa_phi *phi;
1426 int use;
1427 FOREACH_PHI_USE(var, phi) {
1428 int i, end = NUM_PHI_SOURCES(phi);
1429 for (i = 0; i < end; i++) {
1430 if (phi->sources[i] == var_num) {
1431 phi->use_chains[i] = NULL;
1432 }
1433 }
1434 } FOREACH_PHI_USE_END();
1435 var->phi_use_chain = NULL;
1436 FOREACH_USE(var, use) {
1437 zend_ssa_op *ssa_op = &ssa->ops[use];
1438 if (ssa_op->op1_use == var_num) {
1439 ssa_op->op1_use = -1;
1440 ssa_op->op1_use_chain = -1;
1441 }
1442 if (ssa_op->op2_use == var_num) {
1443 ssa_op->op2_use = -1;
1444 ssa_op->op2_use_chain = -1;
1445 }
1446 if (ssa_op->result_use == var_num) {
1447 ssa_op->result_use = -1;
1448 ssa_op->res_use_chain = -1;
1449 }
1450 } FOREACH_USE_END();
1451 var->use_chain = -1;
1452 }
1453 /* }}} */
1454
zend_ssa_remove_predecessor(zend_ssa * ssa,int from,int to)1455 void zend_ssa_remove_predecessor(zend_ssa *ssa, int from, int to) /* {{{ */
1456 {
1457 zend_basic_block *next_block = &ssa->cfg.blocks[to];
1458 zend_ssa_block *next_ssa_block = &ssa->blocks[to];
1459 zend_ssa_phi *phi;
1460 int j;
1461
1462 /* Find at which predecessor offset this block is referenced */
1463 int pred_offset = -1;
1464 int *predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset];
1465
1466 for (j = 0; j < next_block->predecessors_count; j++) {
1467 if (predecessors[j] == from) {
1468 pred_offset = j;
1469 break;
1470 }
1471 }
1472
1473 /* If there are duplicate successors, the predecessors may have been removed in
1474 * a previous iteration already. */
1475 if (pred_offset == -1) {
1476 return;
1477 }
1478
1479 /* For phis in successor blocks, remove the operands associated with this block */
1480 for (phi = next_ssa_block->phis; phi; phi = phi->next) {
1481 if (phi->pi >= 0) {
1482 if (phi->pi == from) {
1483 zend_ssa_rename_var_uses(ssa, phi->ssa_var, phi->sources[0], /* update_types */ 0);
1484 zend_ssa_remove_phi(ssa, phi);
1485 }
1486 } else {
1487 ZEND_ASSERT(phi->sources[pred_offset] >= 0);
1488 zend_ssa_remove_phi_source(ssa, phi, pred_offset, next_block->predecessors_count);
1489 }
1490 }
1491
1492 /* Remove this predecessor */
1493 next_block->predecessors_count--;
1494 if (pred_offset < next_block->predecessors_count) {
1495 predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset + pred_offset];
1496 memmove(predecessors, predecessors + 1, (next_block->predecessors_count - pred_offset) * sizeof(uint32_t));
1497 }
1498 }
1499 /* }}} */
1500
zend_ssa_remove_block(zend_op_array * op_array,zend_ssa * ssa,int i)1501 void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int i) /* {{{ */
1502 {
1503 zend_basic_block *block = &ssa->cfg.blocks[i];
1504 zend_ssa_block *ssa_block = &ssa->blocks[i];
1505 zend_ssa_phi *phi;
1506 int j;
1507
1508 block->flags &= ~ZEND_BB_REACHABLE;
1509
1510 /* Removes phis in this block */
1511 for (phi = ssa_block->phis; phi; phi = phi->next) {
1512 zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
1513 zend_ssa_remove_phi(ssa, phi);
1514 }
1515
1516 /* Remove instructions in this block */
1517 for (j = block->start; j < block->start + block->len; j++) {
1518 if (op_array->opcodes[j].opcode == ZEND_NOP) {
1519 continue;
1520 }
1521
1522 zend_ssa_remove_defs_of_instr(ssa, &ssa->ops[j]);
1523 zend_ssa_remove_instr(ssa, &op_array->opcodes[j], &ssa->ops[j]);
1524 }
1525
1526 zend_ssa_remove_block_from_cfg(ssa, i);
1527 }
1528 /* }}} */
1529
zend_ssa_remove_block_from_cfg(zend_ssa * ssa,int i)1530 void zend_ssa_remove_block_from_cfg(zend_ssa *ssa, int i) /* {{{ */
1531 {
1532 zend_basic_block *block = &ssa->cfg.blocks[i];
1533 int *predecessors;
1534 int j, s;
1535
1536 for (s = 0; s < block->successors_count; s++) {
1537 zend_ssa_remove_predecessor(ssa, i, block->successors[s]);
1538 }
1539
1540 /* Remove successors of predecessors */
1541 predecessors = &ssa->cfg.predecessors[block->predecessor_offset];
1542 for (j = 0; j < block->predecessors_count; j++) {
1543 if (predecessors[j] >= 0) {
1544 zend_basic_block *prev_block = &ssa->cfg.blocks[predecessors[j]];
1545
1546 for (s = 0; s < prev_block->successors_count; s++) {
1547 if (prev_block->successors[s] == i) {
1548 memmove(prev_block->successors + s,
1549 prev_block->successors + s + 1,
1550 sizeof(int) * (prev_block->successors_count - s - 1));
1551 prev_block->successors_count--;
1552 s--;
1553 }
1554 }
1555 }
1556 }
1557
1558 block->successors_count = 0;
1559 block->predecessors_count = 0;
1560
1561 /* Remove from dominators tree */
1562 if (block->idom >= 0) {
1563 j = ssa->cfg.blocks[block->idom].children;
1564 if (j == i) {
1565 ssa->cfg.blocks[block->idom].children = block->next_child;
1566 } else if (j >= 0) {
1567 while (ssa->cfg.blocks[j].next_child >= 0) {
1568 if (ssa->cfg.blocks[j].next_child == i) {
1569 ssa->cfg.blocks[j].next_child = block->next_child;
1570 break;
1571 }
1572 j = ssa->cfg.blocks[j].next_child;
1573 }
1574 }
1575 }
1576 block->idom = -1;
1577 block->level = -1;
1578 block->children = -1;
1579 block->next_child = -1;
1580 }
1581 /* }}} */
1582
propagate_phi_type_widening(zend_ssa * ssa,int var)1583 static void propagate_phi_type_widening(zend_ssa *ssa, int var) /* {{{ */
1584 {
1585 zend_ssa_phi *phi;
1586 FOREACH_PHI_USE(&ssa->vars[var], phi) {
1587 if (ssa->var_info[var].type & ~ssa->var_info[phi->ssa_var].type) {
1588 ssa->var_info[phi->ssa_var].type |= ssa->var_info[var].type;
1589 propagate_phi_type_widening(ssa, phi->ssa_var);
1590 }
1591 } FOREACH_PHI_USE_END();
1592 }
1593 /* }}} */
1594
zend_ssa_rename_var_uses(zend_ssa * ssa,int old,int new,bool update_types)1595 void zend_ssa_rename_var_uses(zend_ssa *ssa, int old, int new, bool update_types) /* {{{ */
1596 {
1597 zend_ssa_var *old_var = &ssa->vars[old];
1598 zend_ssa_var *new_var = &ssa->vars[new];
1599 int use;
1600 zend_ssa_phi *phi;
1601
1602 ZEND_ASSERT(old >= 0 && new >= 0);
1603 ZEND_ASSERT(old != new);
1604
1605 /* Only a no_val is both variables are */
1606 new_var->no_val &= old_var->no_val;
1607
1608 /* Update ssa_op use chains */
1609 FOREACH_USE(old_var, use) {
1610 zend_ssa_op *ssa_op = &ssa->ops[use];
1611
1612 /* If the op already uses the new var, don't add the op to the use
1613 * list again. Instead move the use_chain to the correct operand. */
1614 bool add_to_use_chain = 1;
1615 if (ssa_op->result_use == new) {
1616 add_to_use_chain = 0;
1617 } else if (ssa_op->op1_use == new) {
1618 if (ssa_op->result_use == old) {
1619 ssa_op->res_use_chain = ssa_op->op1_use_chain;
1620 ssa_op->op1_use_chain = -1;
1621 }
1622 add_to_use_chain = 0;
1623 } else if (ssa_op->op2_use == new) {
1624 if (ssa_op->result_use == old) {
1625 ssa_op->res_use_chain = ssa_op->op2_use_chain;
1626 ssa_op->op2_use_chain = -1;
1627 } else if (ssa_op->op1_use == old) {
1628 ssa_op->op1_use_chain = ssa_op->op2_use_chain;
1629 ssa_op->op2_use_chain = -1;
1630 }
1631 add_to_use_chain = 0;
1632 }
1633
1634 /* Perform the actual renaming */
1635 if (ssa_op->result_use == old) {
1636 ssa_op->result_use = new;
1637 }
1638 if (ssa_op->op1_use == old) {
1639 ssa_op->op1_use = new;
1640 }
1641 if (ssa_op->op2_use == old) {
1642 ssa_op->op2_use = new;
1643 }
1644
1645 /* Add op to use chain of new var (if it isn't already). We use the
1646 * first use chain of (result, op1, op2) that has the new variable. */
1647 if (add_to_use_chain) {
1648 if (ssa_op->result_use == new) {
1649 ssa_op->res_use_chain = new_var->use_chain;
1650 new_var->use_chain = use;
1651 } else if (ssa_op->op1_use == new) {
1652 ssa_op->op1_use_chain = new_var->use_chain;
1653 new_var->use_chain = use;
1654 } else {
1655 ZEND_ASSERT(ssa_op->op2_use == new);
1656 ssa_op->op2_use_chain = new_var->use_chain;
1657 new_var->use_chain = use;
1658 }
1659 }
1660 } FOREACH_USE_END();
1661 old_var->use_chain = -1;
1662
1663 /* Update phi use chains */
1664 FOREACH_PHI_USE(old_var, phi) {
1665 int j;
1666 bool after_first_new_source = 0;
1667
1668 /* If the phi already uses the new var, find its use chain, as we may
1669 * need to move it to a different source operand. */
1670 zend_ssa_phi **existing_use_chain_ptr = NULL;
1671 for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) {
1672 if (phi->sources[j] == new) {
1673 existing_use_chain_ptr = &phi->use_chains[j];
1674 break;
1675 }
1676 }
1677
1678 for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) {
1679 if (phi->sources[j] == new) {
1680 after_first_new_source = 1;
1681 } else if (phi->sources[j] == old) {
1682 phi->sources[j] = new;
1683
1684 /* Either move existing use chain to this source, or add the phi
1685 * to the phi use chain of the new variables. Do this only once. */
1686 if (!after_first_new_source) {
1687 if (existing_use_chain_ptr) {
1688 phi->use_chains[j] = *existing_use_chain_ptr;
1689 *existing_use_chain_ptr = NULL;
1690 } else {
1691 phi->use_chains[j] = new_var->phi_use_chain;
1692 new_var->phi_use_chain = phi;
1693 }
1694 after_first_new_source = 1;
1695 } else {
1696 phi->use_chains[j] = NULL;
1697 }
1698 }
1699 }
1700
1701 /* Make sure phi result types are not incorrectly narrow after renaming.
1702 * This should not normally happen, but can occur if we DCE an assignment
1703 * or unset and there is an improper phi-indirected use lateron. */
1704 // TODO Alternatively we could rerun type-inference after DCE
1705 if (update_types && (ssa->var_info[new].type & ~ssa->var_info[phi->ssa_var].type)) {
1706 ssa->var_info[phi->ssa_var].type |= ssa->var_info[new].type;
1707 propagate_phi_type_widening(ssa, phi->ssa_var);
1708 }
1709 } FOREACH_PHI_USE_END();
1710 old_var->phi_use_chain = NULL;
1711 }
1712 /* }}} */
1713
