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 zend_result 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 bool 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 zend_class_entry *ce = zend_optimizer_get_class_entry_from_op1(
162 script, op_array, opline);
163 uint32_t forbidden_flags =
164 /* These flags will always cause an exception */
165 ZEND_ACC_IMPLICIT_ABSTRACT_CLASS | ZEND_ACC_EXPLICIT_ABSTRACT_CLASS
166 | ZEND_ACC_INTERFACE | ZEND_ACC_TRAIT;
167 if (ce
168 && !ce->parent
169 && !ce->create_object
170 && ce->default_object_handlers->get_constructor == zend_std_get_constructor
171 && ce->default_object_handlers->dtor_obj == zend_objects_destroy_object
172 && !ce->constructor
173 && !ce->destructor
174 && !ce->__get
175 && !ce->__set
176 && !(ce->ce_flags & forbidden_flags)
177 && (ce->ce_flags & ZEND_ACC_CONSTANTS_UPDATED)) {
178 return 1;
179 }
180 break;
181 }
182 case ZEND_QM_ASSIGN:
183 if (opline->op1_type == IS_CONST
184 && Z_TYPE_P(CRT_CONSTANT(opline->op1)) == IS_ARRAY) {
185 return 1;
186 }
187 if (opline->op1_type == IS_CV && (OP1_INFO() & MAY_BE_ARRAY)) {
188 return 1;
189 }
190 break;
191 case ZEND_ASSIGN:
192 if (opline->op1_type == IS_CV && (OP1_INFO() & MAY_BE_ARRAY)) {
193 return 1;
194 }
195 break;
196 }
197 } else if (ssa_op->op1_def == var) {
198 switch (opline->opcode) {
199 case ZEND_ASSIGN:
200 if (opline->op2_type == IS_CONST
201 && Z_TYPE_P(CRT_CONSTANT(opline->op2)) == IS_ARRAY) {
202 return 1;
203 }
204 if (opline->op2_type == IS_CV && (OP2_INFO() & MAY_BE_ARRAY)) {
205 return 1;
206 }
207 break;
208 case ZEND_ASSIGN_DIM:
209 if (OP1_INFO() & (MAY_BE_UNDEF | MAY_BE_NULL | MAY_BE_FALSE)) {
210 /* implicit object/array allocation */
211 return 1;
212 }
213 break;
214 }
215 }
216
217 return 0;
218 }
219 /* }}} */
220
is_local_def(zend_op_array * op_array,zend_ssa * ssa,int def,int var,const zend_script * script)221 static bool is_local_def(zend_op_array *op_array, zend_ssa *ssa, int def, int var, const zend_script *script) /* {{{ */
222 {
223 zend_ssa_op *op = ssa->ops + def;
224 zend_op *opline = op_array->opcodes + def;
225
226 if (op->result_def == var) {
227 switch (opline->opcode) {
228 case ZEND_INIT_ARRAY:
229 case ZEND_ADD_ARRAY_ELEMENT:
230 case ZEND_QM_ASSIGN:
231 case ZEND_ASSIGN:
232 return 1;
233 case ZEND_NEW: {
234 /* objects with destructors should escape */
235 zend_class_entry *ce = zend_optimizer_get_class_entry_from_op1(
236 script, op_array, opline);
237 if (ce
238 && !ce->create_object
239 && ce->default_object_handlers->get_constructor == zend_std_get_constructor
240 && ce->default_object_handlers->dtor_obj == zend_objects_destroy_object
241 && !ce->constructor
242 && !ce->destructor
243 && !ce->__get
244 && !ce->__set
245 && !ce->parent) {
246 return 1;
247 }
248 break;
249 }
250 }
251 } else if (op->op1_def == var) {
252 switch (opline->opcode) {
253 case ZEND_ASSIGN:
254 case ZEND_ASSIGN_DIM:
255 case ZEND_ASSIGN_OBJ:
256 case ZEND_ASSIGN_OBJ_REF:
257 case ZEND_ASSIGN_DIM_OP:
258 case ZEND_ASSIGN_OBJ_OP:
259 case ZEND_PRE_INC_OBJ:
260 case ZEND_PRE_DEC_OBJ:
261 case ZEND_POST_INC_OBJ:
262 case ZEND_POST_DEC_OBJ:
263 return 1;
264 }
265 }
266
267 return 0;
268 }
269 /* }}} */
270
is_escape_use(zend_op_array * op_array,zend_ssa * ssa,int use,int var)271 static bool is_escape_use(zend_op_array *op_array, zend_ssa *ssa, int use, int var) /* {{{ */
272 {
273 zend_ssa_op *ssa_op = ssa->ops + use;
274 zend_op *opline = op_array->opcodes + use;
275
276 if (ssa_op->op1_use == var) {
277 switch (opline->opcode) {
278 case ZEND_ASSIGN:
279 /* no_val */
280 break;
281 case ZEND_QM_ASSIGN:
282 if (opline->op1_type == IS_CV) {
283 if (OP1_INFO() & MAY_BE_OBJECT) {
284 /* object aliasing */
285 return 1;
286 }
287 }
288 break;
289 case ZEND_ISSET_ISEMPTY_DIM_OBJ:
290 case ZEND_ISSET_ISEMPTY_PROP_OBJ:
291 case ZEND_FETCH_DIM_R:
292 case ZEND_FETCH_OBJ_R:
293 case ZEND_FETCH_DIM_IS:
294 case ZEND_FETCH_OBJ_IS:
295 break;
296 case ZEND_ASSIGN_OP:
297 return 1;
298 case ZEND_ASSIGN_DIM_OP:
299 case ZEND_ASSIGN_OBJ_OP:
300 case ZEND_ASSIGN_STATIC_PROP_OP:
301 case ZEND_ASSIGN_DIM:
302 case ZEND_ASSIGN_OBJ:
303 case ZEND_ASSIGN_OBJ_REF:
304 break;
305 case ZEND_PRE_INC_OBJ:
306 case ZEND_PRE_DEC_OBJ:
307 case ZEND_POST_INC_OBJ:
308 case ZEND_POST_DEC_OBJ:
309 break;
310 case ZEND_INIT_ARRAY:
311 case ZEND_ADD_ARRAY_ELEMENT:
312 if (opline->extended_value & ZEND_ARRAY_ELEMENT_REF) {
313 return 1;
314 }
315 if (OP1_INFO() & MAY_BE_OBJECT) {
316 /* object aliasing */
317 return 1;
318 }
319 /* reference dependencies processed separately */
320 break;
321 case ZEND_OP_DATA:
322 if ((opline-1)->opcode != ZEND_ASSIGN_DIM
323 && (opline-1)->opcode != ZEND_ASSIGN_OBJ) {
324 return 1;
325 }
326 if (OP1_INFO() & MAY_BE_OBJECT) {
327 /* object aliasing */
328 return 1;
329 }
330 opline--;
331 ssa_op--;
332 if (opline->op1_type != IS_CV
333 || (OP1_INFO() & MAY_BE_REF)
334 || (ssa_op->op1_def >= 0 && ssa->vars[ssa_op->op1_def].alias)) {
335 /* assignment into escaping structure */
336 return 1;
337 }
338 /* reference dependencies processed separately */
339 break;
340 default:
341 return 1;
342 }
343 }
344
345 if (ssa_op->op2_use == var) {
346 switch (opline->opcode) {
347 case ZEND_ASSIGN:
348 if (opline->op1_type != IS_CV
349 || (OP1_INFO() & MAY_BE_REF)
350 || (ssa_op->op1_def >= 0 && ssa->vars[ssa_op->op1_def].alias)) {
351 /* assignment into escaping variable */
352 return 1;
353 }
354 if (opline->op2_type == IS_CV || opline->result_type != IS_UNUSED) {
355 if (OP2_INFO() & MAY_BE_OBJECT) {
356 /* object aliasing */
357 return 1;
358 }
359 }
360 break;
361 default:
362 return 1;
363 }
364 }
365
366 if (ssa_op->result_use == var) {
367 switch (opline->opcode) {
368 case ZEND_ASSIGN:
369 case ZEND_QM_ASSIGN:
370 case ZEND_INIT_ARRAY:
371 case ZEND_ADD_ARRAY_ELEMENT:
372 break;
373 default:
374 return 1;
375 }
376 }
377
378 return 0;
379 }
380 /* }}} */
381
zend_ssa_escape_analysis(const zend_script * script,zend_op_array * op_array,zend_ssa * ssa)382 zend_result zend_ssa_escape_analysis(const zend_script *script, zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
383 {
384 zend_ssa_var *ssa_vars = ssa->vars;
385 int ssa_vars_count = ssa->vars_count;
386 int i, root, use;
387 int *ees;
388 bool has_allocations;
389 int num_non_escaped;
390 ALLOCA_FLAG(use_heap)
391
392 if (!ssa_vars) {
393 return SUCCESS;
394 }
395
396 has_allocations = 0;
397 for (i = op_array->last_var; i < ssa_vars_count; i++) {
398 if (ssa_vars[i].definition >= 0
399 && (ssa->var_info[i].type & (MAY_BE_ARRAY|MAY_BE_OBJECT))
400 && is_allocation_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
401 has_allocations = 1;
402 break;
403 }
404 }
405 if (!has_allocations) {
406 return SUCCESS;
407 }
408
409
410 /* 1. Build EES (Equi-Escape Sets) */
411 ees = do_alloca(sizeof(int) * ssa_vars_count, use_heap);
412 if (!ees) {
413 return FAILURE;
414 }
415
416 if (zend_build_equi_escape_sets(ees, op_array, ssa) == FAILURE) {
417 free_alloca(ees, use_heap);
418 return FAILURE;
419 }
420
421 /* 2. Identify Allocations */
422 num_non_escaped = 0;
423 for (i = op_array->last_var; i < ssa_vars_count; i++) {
424 root = ees[i];
425 if (ssa_vars[root].escape_state > ESCAPE_STATE_NO_ESCAPE) {
426 /* already escape. skip */
427 } else if (ssa_vars[i].alias && (ssa->var_info[i].type & MAY_BE_REF)) {
428 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
429 num_non_escaped--;
430 }
431 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
432 } else if (ssa_vars[i].definition >= 0
433 && (ssa->var_info[i].type & (MAY_BE_ARRAY|MAY_BE_OBJECT))) {
434 if (!is_local_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
435 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
436 num_non_escaped--;
437 }
438 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
439 } else if (ssa_vars[root].escape_state == ESCAPE_STATE_UNKNOWN
440 && is_allocation_def(op_array, ssa, ssa_vars[i].definition, i, script)) {
441 ssa_vars[root].escape_state = ESCAPE_STATE_NO_ESCAPE;
442 num_non_escaped++;
443 }
444 }
445 }
446
447 /* 3. Mark escaped EES */
448 if (num_non_escaped) {
449 for (i = 0; i < ssa_vars_count; i++) {
450 if (ssa_vars[i].use_chain >= 0) {
451 root = ees[i];
452 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
453 FOREACH_USE(ssa_vars + i, use) {
454 if (is_escape_use(op_array, ssa, use, i)) {
455 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
456 num_non_escaped--;
457 if (num_non_escaped == 0) {
458 i = ssa_vars_count;
459 }
460 break;
461 }
462 } FOREACH_USE_END();
463 }
464 }
465 }
466 }
467
468 /* 4. Process referential dependencies */
469 if (num_non_escaped) {
470 bool changed;
471
472 do {
473 changed = 0;
474 for (i = 0; i < ssa_vars_count; i++) {
475 if (ssa_vars[i].use_chain >= 0) {
476 root = ees[i];
477 if (ssa_vars[root].escape_state == ESCAPE_STATE_NO_ESCAPE) {
478 FOREACH_USE(ssa_vars + i, use) {
479 zend_ssa_op *op = ssa->ops + use;
480 zend_op *opline = op_array->opcodes + use;
481 int enclosing_root;
482
483 if (opline->opcode == ZEND_OP_DATA &&
484 ((opline-1)->opcode == ZEND_ASSIGN_DIM ||
485 (opline-1)->opcode == ZEND_ASSIGN_OBJ ||
486 (opline-1)->opcode == ZEND_ASSIGN_OBJ_REF) &&
487 op->op1_use == i &&
488 (op-1)->op1_use >= 0) {
489 enclosing_root = ees[(op-1)->op1_use];
490 } else if ((opline->opcode == ZEND_INIT_ARRAY ||
491 opline->opcode == ZEND_ADD_ARRAY_ELEMENT) &&
492 op->op1_use == i &&
493 op->result_def >= 0) {
494 enclosing_root = ees[op->result_def];
495 } else {
496 continue;
497 }
498
499 if (ssa_vars[enclosing_root].escape_state == ESCAPE_STATE_UNKNOWN ||
500 ssa_vars[enclosing_root].escape_state > ssa_vars[root].escape_state) {
501 if (ssa_vars[enclosing_root].escape_state == ESCAPE_STATE_UNKNOWN) {
502 ssa_vars[root].escape_state = ESCAPE_STATE_GLOBAL_ESCAPE;
503 } else {
504 ssa_vars[root].escape_state = ssa_vars[enclosing_root].escape_state;
505 }
506 if (ssa_vars[root].escape_state == ESCAPE_STATE_GLOBAL_ESCAPE) {
507 num_non_escaped--;
508 if (num_non_escaped == 0) {
509 changed = 0;
510 } else {
511 changed = 1;
512 }
513 break;
514 } else {
515 changed = 1;
516 }
517 }
518 } FOREACH_USE_END();
519 }
520 }
521 }
522 } while (changed);
523 }
524
525 /* 5. Propagate values of escape sets to variables */
526 for (i = 0; i < ssa_vars_count; i++) {
527 root = ees[i];
528 if (i != root) {
529 ssa_vars[i].escape_state = ssa_vars[root].escape_state;
530 }
531 }
532
533 free_alloca(ees, use_heap);
534
535 return SUCCESS;
536 }
537 /* }}} */
538
