1 /*
2 +----------------------------------------------------------------------+
3 | Zend OPcache, Escape Analysis |
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 +----------------------------------------------------------------------+
17 */
18
19 #include "Optimizer/zend_optimizer.h"
20 #include "Optimizer/zend_optimizer_internal.h"
21 #include "zend_bitset.h"
22 #include "zend_cfg.h"
23 #include "zend_ssa.h"
24 #include "zend_inference.h"
25 #include "zend_dump.h"
26
27 /*
28 * T. Kotzmann and H. Mossenbock. Escape analysis in the context of dynamic
29 * compilation and deoptimization. In Proceedings of the International
30 * Conference on Virtual Execution Environments, pages 111-120, Chicago,
31 * June 2005
32 */
33
union_find_init(int * parent,int * size,int count)34 static zend_always_inline void union_find_init(int *parent, int *size, int count) /* {{{ */
35 {
36 int i;
37
38 for (i = 0; i < count; i++) {
39 parent[i] = i;
40 size[i] = 1;
41 }
42 }
43 /* }}} */
44
union_find_root(int * parent,int i)45 static zend_always_inline int union_find_root(int *parent, int i) /* {{{ */
46 {
47 int p = parent[i];
48
49 while (i != p) {
50 p = parent[p];
51 parent[i] = p;
52 i = p;
53 p = parent[i];
54 }
55 return i;
56 }
57 /* }}} */
58
union_find_unite(int * parent,int * size,int i,int j)59 static zend_always_inline void union_find_unite(int *parent, int *size, int i, int j) /* {{{ */
60 {
61 int r1 = union_find_root(parent, i);
62 int r2 = union_find_root(parent, j);
63
64 if (r1 != r2) {
65 if (size[r1] < size[r2]) {
66 parent[r1] = r2;
67 size[r2] += size[r1];
68 } else {
69 parent[r2] = r1;
70 size[r1] += size[r2];
71 }
72 }
73 }
74 /* }}} */
75
zend_build_equi_escape_sets(int * parent,zend_op_array * op_array,zend_ssa * ssa)76 static int zend_build_equi_escape_sets(int *parent, zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
77 {
78 zend_ssa_var *ssa_vars = ssa->vars;
79 int ssa_vars_count = ssa->vars_count;
80 zend_ssa_phi *p;
81 int i, j;
82 int *size;
83 ALLOCA_FLAG(use_heap)
84
85 size = do_alloca(sizeof(int) * ssa_vars_count, use_heap);
86 if (!size) {
87 return FAILURE;
88 }
89 union_find_init(parent, size, ssa_vars_count);
90
91 for (i = 0; i < ssa_vars_count; i++) {
92 if (ssa_vars[i].definition_phi) {
93 p = ssa_vars[i].definition_phi;
94 if (p->pi >= 0) {
95 union_find_unite(parent, size, i, p->sources[0]);
96 } else {
97 for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
98 union_find_unite(parent, size, i, p->sources[j]);
99 }
100 }
101 } else if (ssa_vars[i].definition >= 0) {
102 int def = ssa_vars[i].definition;
103 zend_ssa_op *op = ssa->ops + def;
104 zend_op *opline = op_array->opcodes + def;
105
106 if (op->op1_def >= 0) {
107 if (op->op1_use >= 0) {
108 if (opline->opcode != ZEND_ASSIGN) {
109 union_find_unite(parent, size, op->op1_def, op->op1_use);
110 }
111 }
112 if (opline->opcode == ZEND_ASSIGN && op->op2_use >= 0) {
113 union_find_unite(parent, size, op->op1_def, op->op2_use);
114 }
115 }
116 if (op->op2_def >= 0) {
117 if (op->op2_use >= 0) {
118 union_find_unite(parent, size, op->op2_def, op->op2_use);
119 }
120 }
121 if (op->result_def >= 0) {
122 if (op->result_use >= 0) {
123 if (opline->opcode != ZEND_QM_ASSIGN) {
124 union_find_unite(parent, size, op->result_def, op->result_use);
125 }
126 }
127 if (opline->opcode == ZEND_QM_ASSIGN && op->op1_use >= 0) {
128 union_find_unite(parent, size, op->result_def, op->op1_use);
129 }
130 if (opline->opcode == ZEND_ASSIGN && op->op2_use >= 0) {
131 union_find_unite(parent, size, op->result_def, op->op2_use);
132 }
133 if (opline->opcode == ZEND_ASSIGN && op->op1_def >= 0) {
134 union_find_unite(parent, size, op->result_def, op->op1_def);
135 }
136 }
137 }
138 }
139
140 for (i = 0; i < ssa_vars_count; i++) {
141 parent[i] = union_find_root(parent, i);
142 }
143
144 free_alloca(size, use_heap);
145
146 return SUCCESS;
147 }
148 /* }}} */
149
is_allocation_def(zend_op_array * op_array,zend_ssa * ssa,int def,int var,const zend_script * script)150 static int is_allocation_def(zend_op_array *op_array, zend_ssa *ssa, int def, int var, const zend_script *script) /* {{{ */
151 {
152 zend_ssa_op *ssa_op = ssa->ops + def;
153 zend_op *opline = op_array->opcodes + def;
154
155 if (ssa_op->result_def == var) {
156 switch (opline->opcode) {
157 case ZEND_INIT_ARRAY:
158 return 1;
159 case ZEND_NEW:
160 /* objects with destructors should escape */
161 if (opline->op1_type == IS_CONST) {
162 zend_class_entry *ce = zend_optimizer_get_class_entry(
163 script, Z_STR_P(CRT_CONSTANT(opline->op1)+1));
164 uint32_t forbidden_flags =
165 /* These flags will always cause an exception */
166 ZEND_ACC_IMPLICIT_ABSTRACT_CLASS | ZEND_ACC_EXPLICIT_ABSTRACT_CLASS
167 | ZEND_ACC_INTERFACE | ZEND_ACC_TRAIT;
168 if (ce && !ce->parent && !ce->create_object && !ce->constructor &&
169 !ce->destructor && !ce->__get && !ce->__set &&
170 !(ce->ce_flags & forbidden_flags) &&
171 (ce->ce_flags & ZEND_ACC_CONSTANTS_UPDATED)) {
172 return 1;
173 }
174 }
175 break;
176 case ZEND_QM_ASSIGN:
177 if (opline->op1_type == IS_CONST
178 && Z_TYPE_P(CRT_CONSTANT(opline->op1)) == IS_ARRAY) {
179 return 1;
180 }
181 if (opline->op1_type == IS_CV && (OP1_INFO() & MAY_BE_ARRAY)) {
182 return 1;
183 }
184 break;
185 case ZEND_ASSIGN:
186 if (opline->op1_type == IS_CV && (OP1_INFO() & MAY_BE_ARRAY)) {
187 return 1;
188 }
189 break;
190 }
191 } else if (ssa_op->op1_def == var) {
192 switch (opline->opcode) {
193 case ZEND_ASSIGN:
194 if (opline->op2_type == IS_CONST
195 && Z_TYPE_P(CRT_CONSTANT(opline->op2)) == IS_ARRAY) {
196 return 1;
197 }
198 if (opline->op2_type == IS_CV && (OP2_INFO() & MAY_BE_ARRAY)) {
199 return 1;
200 }
201 break;
202 case ZEND_ASSIGN_DIM:
203 if (OP1_INFO() & (MAY_BE_UNDEF | MAY_BE_NULL | MAY_BE_FALSE)) {
204 /* implicit object/array allocation */
205 return 1;
206 }
207 break;
208 }
209 }
210
211 return 0;
212 }
213 /* }}} */
214
is_local_def(zend_op_array * op_array,zend_ssa * ssa,int def,int var,const zend_script * script)215 static int is_local_def(zend_op_array *op_array, zend_ssa *ssa, int def, int var, const zend_script *script) /* {{{ */
216 {
217 zend_ssa_op *op = ssa->ops + def;
218 zend_op *opline = op_array->opcodes + def;
219
220 if (op->result_def == var) {
221 switch (opline->opcode) {
222 case ZEND_INIT_ARRAY:
223 case ZEND_ADD_ARRAY_ELEMENT:
224 case ZEND_QM_ASSIGN:
225 case ZEND_ASSIGN:
226 return 1;
227 case ZEND_NEW:
228 /* objects with destructors should escape */
229 if (opline->op1_type == IS_CONST) {
230 zend_class_entry *ce = zend_optimizer_get_class_entry(
231 script, Z_STR_P(CRT_CONSTANT(opline->op1)+1));
232 if (ce && !ce->create_object && !ce->constructor &&
233 !ce->destructor && !ce->__get && !ce->__set && !ce->parent) {
234 return 1;
235 }
236 }
237 break;
238 }
239 } else if (op->op1_def == var) {
240 switch (opline->opcode) {
241 case ZEND_ASSIGN:
242 case ZEND_ASSIGN_DIM:
243 case ZEND_ASSIGN_OBJ:
244 case ZEND_ASSIGN_OBJ_REF:
245 case ZEND_ASSIGN_DIM_OP:
246 case ZEND_ASSIGN_OBJ_OP:
247 case ZEND_PRE_INC_OBJ:
248 case ZEND_PRE_DEC_OBJ:
249 case ZEND_POST_INC_OBJ:
250 case ZEND_POST_DEC_OBJ:
251 return 1;
252 }
253 }
254
255 return 0;
256 }
257 /* }}} */
258
is_escape_use(zend_op_array * op_array,zend_ssa * ssa,int use,int var)259 static int is_escape_use(zend_op_array *op_array, zend_ssa *ssa, int use, int var) /* {{{ */
260 {
261 zend_ssa_op *ssa_op = ssa->ops + use;
262 zend_op *opline = op_array->opcodes + use;
263
264 if (ssa_op->op1_use == var) {
265 switch (opline->opcode) {
266 case ZEND_ASSIGN:
267 /* no_val */
268 break;
269 case ZEND_QM_ASSIGN:
270 if (opline->op1_type == IS_CV) {
271 if (OP1_INFO() & MAY_BE_OBJECT) {
272 /* object aliasing */
273 return 1;
274 }
275 }
276 break;
277 case ZEND_ISSET_ISEMPTY_DIM_OBJ:
278 case ZEND_ISSET_ISEMPTY_PROP_OBJ:
279 case ZEND_FETCH_DIM_R:
280 case ZEND_FETCH_OBJ_R:
281 case ZEND_FETCH_DIM_IS:
282 case ZEND_FETCH_OBJ_IS:
283 break;
284 case ZEND_ASSIGN_OP:
285 return 1;
286 case ZEND_ASSIGN_DIM_OP:
287 case ZEND_ASSIGN_OBJ_OP:
288 case ZEND_ASSIGN_STATIC_PROP_OP:
289 case ZEND_ASSIGN_DIM:
290 case ZEND_ASSIGN_OBJ:
291 case ZEND_ASSIGN_OBJ_REF:
292 break;
293 case ZEND_PRE_INC_OBJ:
294 case ZEND_PRE_DEC_OBJ:
295 case ZEND_POST_INC_OBJ:
296 case ZEND_POST_DEC_OBJ:
297 break;
298 case ZEND_INIT_ARRAY:
299 case ZEND_ADD_ARRAY_ELEMENT:
300 if (opline->extended_value & ZEND_ARRAY_ELEMENT_REF) {
301 return 1;
302 }
303 if (OP1_INFO() & MAY_BE_OBJECT) {
304 /* object aliasing */
305 return 1;
306 }
307 /* reference dependencies processed separately */
308 break;
309 case ZEND_OP_DATA:
310 if ((opline-1)->opcode != ZEND_ASSIGN_DIM
311 && (opline-1)->opcode != ZEND_ASSIGN_OBJ) {
312 return 1;
313 }
314 if (OP1_INFO() & MAY_BE_OBJECT) {
315 /* object aliasing */
316 return 1;
317 }
318 opline--;
319 ssa_op--;
320 if (opline->op1_type != IS_CV
321 || (OP1_INFO() & MAY_BE_REF)
322 || (ssa_op->op1_def >= 0 && ssa->vars[ssa_op->op1_def].alias)) {
323 /* assignment into escaping structure */
324 return 1;
325 }
326 /* reference dependencies processed separately */
327 break;
328 default:
329 return 1;
330 }
331 }
332
333 if (ssa_op->op2_use == var) {
334 switch (opline->opcode) {
335 case ZEND_ASSIGN:
336 if (opline->op1_type != IS_CV
337 || (OP1_INFO() & MAY_BE_REF)
338 || (ssa_op->op1_def >= 0 && ssa->vars[ssa_op->op1_def].alias)) {
339 /* assignment into escaping variable */
340 return 1;
341 }
342 if (opline->op2_type == IS_CV || opline->result_type != IS_UNUSED) {
343 if (OP2_INFO() & MAY_BE_OBJECT) {
344 /* object aliasing */
345 return 1;
346 }
347 }
348 break;
349 default:
350 return 1;
351 }
352 }
353
354 if (ssa_op->result_use == var) {
355 switch (opline->opcode) {
356 case ZEND_ASSIGN:
357 case ZEND_QM_ASSIGN:
358 case ZEND_INIT_ARRAY:
359 case ZEND_ADD_ARRAY_ELEMENT:
360 break;
361 default:
362 return 1;
363 }
364 }
365
366 return 0;
367 }
368 /* }}} */
369
zend_ssa_escape_analysis(const zend_script * script,zend_op_array * op_array,zend_ssa * ssa)370 int zend_ssa_escape_analysis(const zend_script *script, zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
371 {
372 zend_ssa_var *ssa_vars = ssa->vars;
373 int ssa_vars_count = ssa->vars_count;
374 int i, root, use;
375 int *ees;
376 bool has_allocations;
377 int num_non_escaped;
378 ALLOCA_FLAG(use_heap)
379
380 if (!ssa_vars) {
381 return SUCCESS;
382 }
383
384 has_allocations = 0;
385 for (i = op_array->last_var; i < ssa_vars_count; i++) {
386 if (ssa_vars[i].definition >= 0
387 && (ssa->var_info[i].type & (MAY_BE_ARRAY|MAY_BE_OBJECT))
388 && is_allocation_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
389 has_allocations = 1;
390 break;
391 }
392 }
393 if (!has_allocations) {
394 return SUCCESS;
395 }
396
397
398 /* 1. Build EES (Equi-Escape Sets) */
399 ees = do_alloca(sizeof(int) * ssa_vars_count, use_heap);
400 if (!ees) {
401 return FAILURE;
402 }
403
404 if (zend_build_equi_escape_sets(ees, op_array, ssa) != SUCCESS) {
405 return FAILURE;
406 }
407
408 /* 2. Identify Allocations */
409 num_non_escaped = 0;
410 for (i = op_array->last_var; i < ssa_vars_count; i++) {
411 root = ees[i];
412 if (ssa_vars[root].escape_state > ESCAPE_STATE_NO_ESCAPE) {
413 /* already escape. skip */
414 } else if (ssa_vars[i].alias && (ssa->var_info[i].type & MAY_BE_REF)) {
415 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
416 num_non_escaped--;
417 }
418 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
419 } else if (ssa_vars[i].definition >= 0
420 && (ssa->var_info[i].type & (MAY_BE_ARRAY|MAY_BE_OBJECT))) {
421 if (!is_local_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
422 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
423 num_non_escaped--;
424 }
425 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
426 } else if (ssa_vars[root].escape_state == ESCAPE_STATE_UNKNOWN
427 && is_allocation_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
428 ssa_vars[root].escape_state = ESCAPE_STATE_NO_ESCAPE;
429 num_non_escaped++;
430 }
431 }
432 }
433
434 /* 3. Mark escaped EES */
435 if (num_non_escaped) {
436 for (i = 0; i < ssa_vars_count; i++) {
437 if (ssa_vars[i].use_chain >= 0) {
438 root = ees[i];
439 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
440 FOREACH_USE(ssa_vars + i, use) {
441 if (is_escape_use(op_array, ssa, use, i)) {
442 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
443 num_non_escaped--;
444 if (num_non_escaped == 0) {
445 i = ssa_vars_count;
446 }
447 break;
448 }
449 } FOREACH_USE_END();
450 }
451 }
452 }
453 }
454
455 /* 4. Process referential dependencies */
456 if (num_non_escaped) {
457 bool changed;
458
459 do {
460 changed = 0;
461 for (i = 0; i < ssa_vars_count; i++) {
462 if (ssa_vars[i].use_chain >= 0) {
463 root = ees[i];
464 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
465 FOREACH_USE(ssa_vars + i, use) {
466 zend_ssa_op *op = ssa->ops + use;
467 zend_op *opline = op_array->opcodes + use;
468 int enclosing_root;
469
470 if (opline->opcode == ZEND_OP_DATA &&
471 ((opline-1)->opcode == ZEND_ASSIGN_DIM ||
472 (opline-1)->opcode == ZEND_ASSIGN_OBJ ||
473 (opline-1)->opcode == ZEND_ASSIGN_OBJ_REF) &&
474 op->op1_use == i &&
475 (op-1)->op1_use >= 0) {
476 enclosing_root = ees[(op-1)->op1_use];
477 } else if ((opline->opcode == ZEND_INIT_ARRAY ||
478 opline->opcode == ZEND_ADD_ARRAY_ELEMENT) &&
479 op->op1_use == i &&
480 op->result_def >= 0) {
481 enclosing_root = ees[op->result_def];
482 } else {
483 continue;
484 }
485
486 if (ssa_vars[enclosing_root].escape_state == ESCAPE_STATE_UNKNOWN ||
487 ssa_vars[enclosing_root].escape_state > ssa_vars[root].escape_state) {
488 if (ssa_vars[enclosing_root].escape_state == ESCAPE_STATE_UNKNOWN) {
489 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
490 } else {
491 ssa_vars[root].escape_state = ssa_vars[enclosing_root].escape_state;
492 }
493 if (ssa_vars[root].escape_state == ESCAPE_STATE_GLOBAL_ESCAPE) {
494 num_non_escaped--;
495 if (num_non_escaped == 0) {
496 changed = 0;
497 } else {
498 changed = 1;
499 }
500 break;
501 } else {
502 changed = 1;
503 }
504 }
505 } FOREACH_USE_END();
506 }
507 }
508 }
509 } while (changed);
510 }
511
512 /* 5. Propagate values of escape sets to variables */
513 for (i = 0; i < ssa_vars_count; i++) {
514 root = ees[i];
515 if (i != root) {
516 ssa_vars[i].escape_state = ssa_vars[root].escape_state;
517 }
518 }
519
520 free_alloca(ees, use_heap);
521
522 return SUCCESS;
523 }
524 /* }}} */
525
