xref: /PHP-8.3/Zend/Optimizer/escape_analysis.c (revision 03d73182)
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