xref: /PHP-8.1/Zend/Optimizer/scdf.c (revision c3766c08)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine, Sparse Conditional Data Flow Propagation Framework      |
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: Nikita Popov <nikic@php.net>                                |
16    +----------------------------------------------------------------------+
17 */
18 
19 #include "Optimizer/zend_optimizer_internal.h"
20 #include "Optimizer/scdf.h"
21 
22 /* This defines a generic framework for sparse conditional dataflow propagation. The algorithm is
23  * based on "Sparse conditional constant propagation" by Wegman and Zadeck. We're using a
24  * generalized implementation as described in chapter 8.3 of the SSA book.
25  *
26  * Every SSA variable is associated with an element on a finite-height lattice, those value can only
27  * ever be lowered during the operation of the algorithm. If a value is lowered all instructions and
28  * phis using that value need to be reconsidered (this is done by adding the variable to a
29  * worklist). For phi functions the result is computed by applying the meet operation to the
30  * operands. This continues until a fixed point is reached.
31  *
32  * The algorithm is control-flow sensitive: All blocks except the start block are initially assumed
33  * to be unreachable. When considering a branch instruction, we determine the feasible successors
34  * based on the current state of the variable lattice. If a new edge becomes feasible we either have
35  * to mark the successor block executable and consider all instructions in it, or, if the target is
36  * already executable, we only have to reconsider the phi functions (as we only consider phi
37  * operands which are associated with a feasible edge).
38  *
39  * The generic framework requires the definition of three functions:
40  * * visit_instr() should recompute the lattice values of all SSA variables defined by an
41  *   instruction.
42  * * visit_phi() should recompute the lattice value of the SSA variable defined by the phi. While
43  *   doing this it should only consider operands for which scfg_is_edge_feasible() returns true.
44  * * get_feasible_successors() should determine the feasible successors for a branch instruction.
45  *   Note that this callback only needs to handle conditional branches (with two successors).
46  */
47 
48 #if 0
49 #define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__)
50 #else
51 #define DEBUG_PRINT(...)
52 #endif
53 
scdf_mark_edge_feasible(scdf_ctx * scdf,int from,int to)54 void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) {
55 	uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);
56 
57 	if (zend_bitset_in(scdf->feasible_edges, edge)) {
58 		/* We already handled this edge */
59 		return;
60 	}
61 
62 	DEBUG_PRINT("Marking edge %d->%d feasible\n", from, to);
63 	zend_bitset_incl(scdf->feasible_edges, edge);
64 
65 	if (!zend_bitset_in(scdf->executable_blocks, to)) {
66 		if (!zend_bitset_in(scdf->block_worklist, to)) {
67 			DEBUG_PRINT("Adding block %d to worklist\n", to);
68 		}
69 		zend_bitset_incl(scdf->block_worklist, to);
70 	} else {
71 		/* Block is already executable, only a new edge became feasible.
72 		 * Reevaluate phi nodes to account for changed source operands. */
73 		zend_ssa_block *ssa_block = &scdf->ssa->blocks[to];
74 		zend_ssa_phi *phi;
75 		for (phi = ssa_block->phis; phi; phi = phi->next) {
76 			zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
77 			scdf->handlers.visit_phi(scdf, phi);
78 		}
79 	}
80 }
81 
scdf_init(zend_optimizer_ctx * ctx,scdf_ctx * scdf,zend_op_array * op_array,zend_ssa * ssa)82 void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) {
83 	scdf->op_array = op_array;
84 	scdf->ssa = ssa;
85 
86 	scdf->instr_worklist_len = zend_bitset_len(op_array->last);
87 	scdf->phi_var_worklist_len = zend_bitset_len(ssa->vars_count);
88 	scdf->block_worklist_len = zend_bitset_len(ssa->cfg.blocks_count);
89 
90 	scdf->instr_worklist = zend_arena_calloc(&ctx->arena,
91 		scdf->instr_worklist_len + scdf->phi_var_worklist_len + 2 * scdf->block_worklist_len + zend_bitset_len(ssa->cfg.edges_count),
92 		sizeof(zend_ulong));
93 
94 	scdf->phi_var_worklist = scdf->instr_worklist + scdf->instr_worklist_len;
95 	scdf->block_worklist = scdf->phi_var_worklist + scdf->phi_var_worklist_len;
96 	scdf->executable_blocks = scdf->block_worklist + scdf->block_worklist_len;
97 	scdf->feasible_edges = scdf->executable_blocks + scdf->block_worklist_len;
98 
99 	zend_bitset_incl(scdf->block_worklist, 0);
100 	zend_bitset_incl(scdf->executable_blocks, 0);
101 }
102 
scdf_solve(scdf_ctx * scdf,const char * name)103 void scdf_solve(scdf_ctx *scdf, const char *name) {
104 	zend_ssa *ssa = scdf->ssa;
105 	DEBUG_PRINT("Start SCDF solve (%s)\n", name);
106 	while (!zend_bitset_empty(scdf->instr_worklist, scdf->instr_worklist_len)
107 		|| !zend_bitset_empty(scdf->phi_var_worklist, scdf->phi_var_worklist_len)
108 		|| !zend_bitset_empty(scdf->block_worklist, scdf->block_worklist_len)
109 	) {
110 		int i;
111 		while ((i = zend_bitset_pop_first(scdf->phi_var_worklist, scdf->phi_var_worklist_len)) >= 0) {
112 			zend_ssa_phi *phi = ssa->vars[i].definition_phi;
113 			ZEND_ASSERT(phi);
114 			if (zend_bitset_in(scdf->executable_blocks, phi->block)) {
115 				scdf->handlers.visit_phi(scdf, phi);
116 			}
117 		}
118 
119 		while ((i = zend_bitset_pop_first(scdf->instr_worklist, scdf->instr_worklist_len)) >= 0) {
120 			int block_num = ssa->cfg.map[i];
121 			if (zend_bitset_in(scdf->executable_blocks, block_num)) {
122 				zend_basic_block *block = &ssa->cfg.blocks[block_num];
123 				zend_op *opline = &scdf->op_array->opcodes[i];
124 				zend_ssa_op *ssa_op = &ssa->ops[i];
125 				if (opline->opcode == ZEND_OP_DATA) {
126 					opline--;
127 					ssa_op--;
128 				}
129 				scdf->handlers.visit_instr(scdf, opline, ssa_op);
130 				if (i == block->start + block->len - 1) {
131 					if (block->successors_count == 1) {
132 						scdf_mark_edge_feasible(scdf, block_num, block->successors[0]);
133 					} else if (block->successors_count > 1) {
134 						scdf->handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op);
135 					}
136 				}
137 			}
138 		}
139 
140 		while ((i = zend_bitset_pop_first(scdf->block_worklist, scdf->block_worklist_len)) >= 0) {
141 			/* This block is now live. Interpret phis and instructions in it. */
142 			zend_basic_block *block = &ssa->cfg.blocks[i];
143 			zend_ssa_block *ssa_block = &ssa->blocks[i];
144 
145 			DEBUG_PRINT("Pop block %d from worklist\n", i);
146 			zend_bitset_incl(scdf->executable_blocks, i);
147 
148 			{
149 				zend_ssa_phi *phi;
150 				for (phi = ssa_block->phis; phi; phi = phi->next) {
151 					zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
152 					scdf->handlers.visit_phi(scdf, phi);
153 				}
154 			}
155 
156 			if (block->len == 0) {
157 				/* Zero length blocks don't have a last instruction that would normally do this */
158 				scdf_mark_edge_feasible(scdf, i, block->successors[0]);
159 			} else {
160 				zend_op *opline = NULL;
161 				int j, end = block->start + block->len;
162 				for (j = block->start; j < end; j++) {
163 					opline = &scdf->op_array->opcodes[j];
164 					zend_bitset_excl(scdf->instr_worklist, j);
165 					if (opline->opcode != ZEND_OP_DATA) {
166 						scdf->handlers.visit_instr(scdf, opline, &ssa->ops[j]);
167 					}
168 				}
169 				if (block->successors_count == 1) {
170 					scdf_mark_edge_feasible(scdf, i, block->successors[0]);
171 				} else if (block->successors_count > 1) {
172 					ZEND_ASSERT(opline && "Should have opline in non-empty block");
173 					if (opline->opcode == ZEND_OP_DATA) {
174 						opline--;
175 						j--;
176 					}
177 					scdf->handlers.mark_feasible_successors(scdf, i, block, opline, &ssa->ops[j-1]);
178 				}
179 			}
180 		}
181 	}
182 }
183 
184 /* If a live range starts in a reachable block and ends in an unreachable block, we should
185  * not eliminate the latter. While it cannot be reached, the FREE opcode of the loop var
186  * is necessary for the correctness of temporary compaction. */
is_live_loop_var_free(scdf_ctx * scdf,const zend_op * opline,const zend_ssa_op * ssa_op)187 static bool is_live_loop_var_free(
188 		scdf_ctx *scdf, const zend_op *opline, const zend_ssa_op *ssa_op) {
189 	if (!zend_optimizer_is_loop_var_free(opline)) {
190 		return false;
191 	}
192 
193 	int var = ssa_op->op1_use;
194 	if (var < 0) {
195 		return false;
196 	}
197 
198 	zend_ssa_var *ssa_var = &scdf->ssa->vars[var];
199 	uint32_t def_block;
200 	if (ssa_var->definition >= 0) {
201 		def_block = scdf->ssa->cfg.map[ssa_var->definition];
202 	} else {
203 		def_block = ssa_var->definition_phi->block;
204 	}
205 	return zend_bitset_in(scdf->executable_blocks, def_block);
206 }
207 
kept_alive_by_loop_var_free(scdf_ctx * scdf,const zend_basic_block * block)208 static bool kept_alive_by_loop_var_free(scdf_ctx *scdf, const zend_basic_block *block) {
209 	const zend_op_array *op_array = scdf->op_array;
210 	const zend_cfg *cfg = &scdf->ssa->cfg;
211 	if (!(cfg->flags & ZEND_FUNC_FREE_LOOP_VAR)) {
212 		return false;
213 	}
214 
215 	for (uint32_t i = block->start; i < block->start + block->len; i++) {
216 		if (is_live_loop_var_free(scdf, &op_array->opcodes[i], &scdf->ssa->ops[i])) {
217 			return true;
218 		}
219 	}
220 	return false;
221 }
222 
cleanup_loop_var_free_block(scdf_ctx * scdf,zend_basic_block * block)223 static uint32_t cleanup_loop_var_free_block(scdf_ctx *scdf, zend_basic_block *block) {
224 	zend_ssa *ssa = scdf->ssa;
225 	const zend_op_array *op_array = scdf->op_array;
226 	const zend_cfg *cfg = &ssa->cfg;
227 	int block_num = block - cfg->blocks;
228 	uint32_t removed_ops = 0;
229 
230 	/* Removes phi nodes */
231 	for (zend_ssa_phi *phi = ssa->blocks[block_num].phis; phi; phi = phi->next) {
232 		zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
233 		zend_ssa_remove_phi(ssa, phi);
234 	}
235 
236 	for (uint32_t i = block->start; i < block->start + block->len; i++) {
237 		zend_op *opline = &op_array->opcodes[i];
238 		zend_ssa_op *ssa_op = &scdf->ssa->ops[i];
239 		if (opline->opcode == ZEND_NOP
240 		 || is_live_loop_var_free(scdf, opline, ssa_op)) {
241 			continue;
242 		}
243 
244 		/* While we have to preserve the loop var free, we can still remove other instructions
245 		 * in the block. */
246 		zend_ssa_remove_defs_of_instr(ssa, ssa_op);
247 		zend_ssa_remove_instr(ssa, opline, ssa_op);
248 		removed_ops++;
249 	}
250 
251 	zend_ssa_remove_block_from_cfg(ssa, block_num);
252 
253 	return removed_ops;
254 }
255 
256 /* Removes unreachable blocks. This will remove both the instructions (and phis) in the
257  * blocks, as well as remove them from the successor / predecessor lists and mark them
258  * unreachable. Blocks already marked unreachable are not removed. */
scdf_remove_unreachable_blocks(scdf_ctx * scdf)259 int scdf_remove_unreachable_blocks(scdf_ctx *scdf) {
260 	zend_ssa *ssa = scdf->ssa;
261 	int i;
262 	int removed_ops = 0;
263 	for (i = 0; i < ssa->cfg.blocks_count; i++) {
264 		zend_basic_block *block = &ssa->cfg.blocks[i];
265 		if (!zend_bitset_in(scdf->executable_blocks, i) && (block->flags & ZEND_BB_REACHABLE)) {
266 			if (!kept_alive_by_loop_var_free(scdf, block)) {
267 				removed_ops += block->len;
268 				zend_ssa_remove_block(scdf->op_array, ssa, i);
269 			} else {
270 				removed_ops += cleanup_loop_var_free_block(scdf, block);
271 			}
272 		}
273 	}
274 	return removed_ops;
275 }
276