/src/php-src/Zend/Optimizer/dce.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine, DCE - Dead Code Elimination | |
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 | | | Dmitry Stogov <dmitry@php.net> | |
17 | | +----------------------------------------------------------------------+ |
18 | | */ |
19 | | |
20 | | #include "Optimizer/zend_optimizer_internal.h" |
21 | | #include "Optimizer/zend_inference.h" |
22 | | #include "Optimizer/zend_ssa.h" |
23 | | #include "Optimizer/zend_func_info.h" |
24 | | #include "Optimizer/zend_call_graph.h" |
25 | | #include "zend_bitset.h" |
26 | | |
27 | | /* This pass implements a form of dead code elimination (DCE). The algorithm optimistically assumes |
28 | | * that all instructions and phis are dead. Instructions with immediate side-effects are then marked |
29 | | * as live. We then recursively (using a worklist) propagate liveness to the instructions that def |
30 | | * the used operands. |
31 | | * |
32 | | * Notes: |
33 | | * * This pass does not perform unreachable code elimination. This happens as part of the SCCP |
34 | | * pass. |
35 | | * * The DCE is performed without taking control-dependence into account, i.e. all conditional |
36 | | * branches are assumed to be live. It's possible to take control-dependence into account using |
37 | | * the DCE algorithm described by Cytron et al., however it requires the construction of a |
38 | | * postdominator tree and of postdominance frontiers, which does not seem worthwhile at this |
39 | | * point. |
40 | | * * We separate intrinsic side-effects from potential side-effects in the form of notices thrown |
41 | | * by the instruction (in case we want to make this configurable). See may_have_side_effects() and |
42 | | * zend_may_throw(). |
43 | | * * We often cannot DCE assignments and unsets while guaranteeing that dtors run in the same |
44 | | * order. There is an optimization option to allow reordering of dtor effects. |
45 | | * * The algorithm is able to eliminate dead modifications of non-escaping arrays |
46 | | * and objects as well as dead arrays and objects allocations. |
47 | | */ |
48 | | |
49 | | typedef struct { |
50 | | zend_ssa *ssa; |
51 | | zend_op_array *op_array; |
52 | | zend_bitset instr_dead; |
53 | | zend_bitset phi_dead; |
54 | | zend_bitset instr_worklist; |
55 | | zend_bitset phi_worklist; |
56 | | zend_bitset phi_worklist_no_val; |
57 | | uint32_t instr_worklist_len; |
58 | | uint32_t phi_worklist_len; |
59 | | unsigned reorder_dtor_effects : 1; |
60 | | } context; |
61 | | |
62 | 31.5k | static inline bool is_bad_mod(const zend_ssa *ssa, int use, int def) { |
63 | 31.5k | if (def < 0) { |
64 | | /* This modification is not tracked by SSA, assume the worst */ |
65 | 5.70k | return 1; |
66 | 5.70k | } |
67 | 25.8k | if (ssa->var_info[use].type & MAY_BE_REF) { |
68 | | /* Modification of reference may have side-effect */ |
69 | 11.0k | return 1; |
70 | 11.0k | } |
71 | 14.8k | return 0; |
72 | 25.8k | } |
73 | | |
74 | | static inline bool may_have_side_effects( |
75 | | zend_op_array *op_array, zend_ssa *ssa, |
76 | | const zend_op *opline, const zend_ssa_op *ssa_op, |
77 | 569k | bool reorder_dtor_effects) { |
78 | 569k | switch (opline->opcode) { |
79 | 2.59k | case ZEND_NOP: |
80 | 2.67k | case ZEND_IS_IDENTICAL: |
81 | 2.70k | case ZEND_IS_NOT_IDENTICAL: |
82 | 5.31k | case ZEND_QM_ASSIGN: |
83 | 8.63k | case ZEND_FE_FREE: |
84 | 8.77k | case ZEND_TYPE_CHECK: |
85 | 8.78k | case ZEND_DEFINED: |
86 | 10.1k | case ZEND_ADD: |
87 | 10.3k | case ZEND_SUB: |
88 | 11.0k | case ZEND_MUL: |
89 | 11.0k | case ZEND_POW: |
90 | 11.1k | case ZEND_BW_OR: |
91 | 11.3k | case ZEND_BW_AND: |
92 | 11.4k | case ZEND_BW_XOR: |
93 | 12.6k | case ZEND_CONCAT: |
94 | 12.8k | case ZEND_FAST_CONCAT: |
95 | 12.8k | case ZEND_DIV: |
96 | 13.2k | case ZEND_MOD: |
97 | 13.3k | case ZEND_BOOL_XOR: |
98 | 13.7k | case ZEND_BOOL: |
99 | 14.0k | case ZEND_BOOL_NOT: |
100 | 14.4k | case ZEND_BW_NOT: |
101 | 14.4k | case ZEND_SL: |
102 | 14.5k | case ZEND_SR: |
103 | 14.8k | case ZEND_IS_EQUAL: |
104 | 15.2k | case ZEND_IS_NOT_EQUAL: |
105 | 16.7k | case ZEND_IS_SMALLER: |
106 | 16.7k | case ZEND_IS_SMALLER_OR_EQUAL: |
107 | 16.7k | case ZEND_CASE: |
108 | 16.7k | case ZEND_CASE_STRICT: |
109 | 16.8k | case ZEND_CAST: |
110 | 16.8k | case ZEND_ROPE_INIT: |
111 | 16.8k | case ZEND_ROPE_ADD: |
112 | 16.9k | case ZEND_INIT_ARRAY: |
113 | 16.9k | case ZEND_SPACESHIP: |
114 | 16.9k | case ZEND_STRLEN: |
115 | 17.0k | case ZEND_COUNT: |
116 | 17.0k | case ZEND_GET_TYPE: |
117 | 17.0k | case ZEND_ISSET_ISEMPTY_THIS: |
118 | 17.2k | case ZEND_ISSET_ISEMPTY_DIM_OBJ: |
119 | 17.3k | case ZEND_FETCH_DIM_IS: |
120 | 17.3k | case ZEND_ISSET_ISEMPTY_CV: |
121 | 17.3k | case ZEND_ISSET_ISEMPTY_VAR: |
122 | 17.3k | case ZEND_FETCH_IS: |
123 | 17.3k | case ZEND_IN_ARRAY: |
124 | 17.3k | case ZEND_FUNC_NUM_ARGS: |
125 | 17.3k | case ZEND_FUNC_GET_ARGS: |
126 | 17.3k | case ZEND_ARRAY_KEY_EXISTS: |
127 | | /* No side effects */ |
128 | 17.3k | return 0; |
129 | 17.6k | case ZEND_FREE: |
130 | 17.6k | return opline->extended_value == ZEND_FREE_VOID_CAST; |
131 | 173 | case ZEND_ADD_ARRAY_ELEMENT: |
132 | | /* TODO: We can't free two vars. Keep instruction alive. <?php [0, "$a" => "$b"]; */ |
133 | 173 | if ((opline->op1_type & (IS_VAR|IS_TMP_VAR)) && (opline->op2_type & (IS_VAR|IS_TMP_VAR))) { |
134 | 10 | return 1; |
135 | 10 | } |
136 | 163 | return 0; |
137 | 252 | case ZEND_ROPE_END: |
138 | | /* TODO: Rope dce optimization, see #76446 */ |
139 | 252 | return 1; |
140 | 12.2k | case ZEND_JMP: |
141 | 17.5k | case ZEND_JMPZ: |
142 | 24.4k | case ZEND_JMPNZ: |
143 | 24.6k | case ZEND_JMPZ_EX: |
144 | 24.9k | case ZEND_JMPNZ_EX: |
145 | 25.6k | case ZEND_JMP_SET: |
146 | 25.6k | case ZEND_COALESCE: |
147 | 26.4k | case ZEND_ASSERT_CHECK: |
148 | 28.2k | case ZEND_JMP_NULL: |
149 | 28.3k | case ZEND_BIND_INIT_STATIC_OR_JMP: |
150 | 28.3k | case ZEND_JMP_FRAMELESS: |
151 | | /* For our purposes a jumps and branches are side effects. */ |
152 | 28.3k | return 1; |
153 | 0 | case ZEND_BEGIN_SILENCE: |
154 | 2.53k | case ZEND_END_SILENCE: |
155 | 36.9k | case ZEND_ECHO: |
156 | 36.9k | case ZEND_INCLUDE_OR_EVAL: |
157 | 38.6k | case ZEND_THROW: |
158 | 38.9k | case ZEND_MATCH_ERROR: |
159 | 38.9k | case ZEND_EXT_STMT: |
160 | 38.9k | case ZEND_EXT_FCALL_BEGIN: |
161 | 38.9k | case ZEND_EXT_FCALL_END: |
162 | 39.1k | case ZEND_TICKS: |
163 | 40.4k | case ZEND_YIELD: |
164 | 40.4k | case ZEND_YIELD_FROM: |
165 | 40.5k | case ZEND_VERIFY_NEVER_TYPE: |
166 | | /* Intrinsic side effects */ |
167 | 40.5k | return 1; |
168 | 90.2k | case ZEND_DO_FCALL: |
169 | 90.2k | case ZEND_DO_FCALL_BY_NAME: |
170 | 90.2k | case ZEND_DO_ICALL: |
171 | 95.6k | case ZEND_DO_UCALL: |
172 | 95.6k | case ZEND_FRAMELESS_ICALL_0: |
173 | 95.6k | case ZEND_FRAMELESS_ICALL_1: |
174 | 95.6k | case ZEND_FRAMELESS_ICALL_2: |
175 | 95.6k | case ZEND_FRAMELESS_ICALL_3: |
176 | | /* For now assume all calls have side effects */ |
177 | 95.6k | return 1; |
178 | 7.88k | case ZEND_RECV: |
179 | 9.16k | case ZEND_RECV_INIT: |
180 | | /* Even though RECV_INIT can be side-effect free, these cannot be simply dropped |
181 | | * due to the prologue skipping code. */ |
182 | 9.16k | return 1; |
183 | 593 | case ZEND_ASSIGN_REF: |
184 | 593 | return 1; |
185 | 19.0k | case ZEND_ASSIGN: |
186 | 19.0k | { |
187 | 19.0k | if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)) { |
188 | 8.84k | return 1; |
189 | 8.84k | } |
190 | 10.2k | if (!reorder_dtor_effects) { |
191 | 10.2k | if (opline->op2_type != IS_CONST |
192 | 10.2k | && (OP2_INFO() & MAY_HAVE_DTOR) |
193 | 10.2k | && ssa->vars[ssa_op->op2_use].escape_state != ESCAPE_STATE_NO_ESCAPE) { |
194 | | /* DCE might shorten lifetime */ |
195 | 746 | return 1; |
196 | 746 | } |
197 | 10.2k | } |
198 | 9.49k | return 0; |
199 | 10.2k | } |
200 | 82 | case ZEND_UNSET_VAR: |
201 | 82 | return 1; |
202 | 1.20k | case ZEND_UNSET_CV: |
203 | 1.20k | { |
204 | 1.20k | uint32_t t1 = OP1_INFO(); |
205 | 1.20k | if (t1 & MAY_BE_REF) { |
206 | | /* We don't consider uses as the LHS of an assignment as real uses during DCE, so |
207 | | * an unset may be considered dead even if there is a later assignment to the |
208 | | * variable. Removing the unset in this case would not be correct if the variable |
209 | | * is a reference, because unset breaks references. */ |
210 | 801 | return 1; |
211 | 801 | } |
212 | 399 | return 0; |
213 | 1.20k | } |
214 | 3.18k | case ZEND_PRE_INC: |
215 | 3.50k | case ZEND_POST_INC: |
216 | 3.60k | case ZEND_PRE_DEC: |
217 | 3.72k | case ZEND_POST_DEC: |
218 | 3.72k | return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def); |
219 | 1.14k | case ZEND_ASSIGN_OP: |
220 | 1.14k | return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def) |
221 | 1.14k | || ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE; |
222 | 2.99k | case ZEND_ASSIGN_DIM: |
223 | 7.47k | case ZEND_ASSIGN_OBJ: |
224 | 7.47k | if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def) |
225 | 7.47k | || ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) { |
226 | 7.01k | return 1; |
227 | 7.01k | } |
228 | 461 | if (!reorder_dtor_effects) { |
229 | 461 | opline++; |
230 | 461 | ssa_op++; |
231 | 461 | if (opline->op1_type != IS_CONST |
232 | 461 | && (OP1_INFO() & MAY_HAVE_DTOR)) { |
233 | | /* DCE might shorten lifetime */ |
234 | 106 | return 1; |
235 | 106 | } |
236 | 461 | } |
237 | 355 | return 0; |
238 | 126 | case ZEND_PRE_INC_OBJ: |
239 | 168 | case ZEND_PRE_DEC_OBJ: |
240 | 172 | case ZEND_POST_INC_OBJ: |
241 | 172 | case ZEND_POST_DEC_OBJ: |
242 | 172 | if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def) |
243 | 172 | || ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) { |
244 | 164 | return 1; |
245 | 164 | } |
246 | 8 | return 0; |
247 | 418 | case ZEND_BIND_STATIC: |
248 | 418 | if (op_array->static_variables) { |
249 | | /* Implicit and Explicit bind static is effectively prologue of closure so |
250 | | report it has side effects like RECV, RECV_INIT; This allows us to |
251 | | reflect on the closure and discover used variable at runtime */ |
252 | 418 | if ((opline->extended_value & (ZEND_BIND_IMPLICIT|ZEND_BIND_EXPLICIT))) { |
253 | 206 | return 1; |
254 | 206 | } |
255 | | /* Modifies static variables which are observable through reflection */ |
256 | 212 | if ((opline->extended_value & ZEND_BIND_REF) && opline->op2_type != IS_UNUSED) { |
257 | 166 | return 1; |
258 | 166 | } |
259 | 212 | } |
260 | 46 | return 0; |
261 | 68 | case ZEND_CHECK_VAR: |
262 | 68 | return (OP1_INFO() & MAY_BE_UNDEF) != 0; |
263 | 0 | case ZEND_FE_RESET_R: |
264 | 0 | case ZEND_FE_RESET_RW: |
265 | | /* Model as not having side-effects -- let the side-effect be introduced by |
266 | | * FE_FETCH if the array is not known to be non-empty. */ |
267 | 0 | return (OP1_INFO() & MAY_BE_ANY) != MAY_BE_ARRAY; |
268 | 326k | default: |
269 | | /* For everything we didn't handle, assume a side-effect */ |
270 | 326k | return 1; |
271 | 569k | } |
272 | 569k | } |
273 | | |
274 | 1.42M | static zend_always_inline void add_to_worklists(context *ctx, int var_num, int check) { |
275 | 1.42M | zend_ssa_var *var = &ctx->ssa->vars[var_num]; |
276 | 1.42M | if (var->definition >= 0) { |
277 | 954k | if (!check || zend_bitset_in(ctx->instr_dead, var->definition)) { |
278 | 840k | zend_bitset_incl(ctx->instr_worklist, var->definition); |
279 | 840k | } |
280 | 954k | } else if (var->definition_phi) { |
281 | 372k | if (!check || zend_bitset_in(ctx->phi_dead, var_num)) { |
282 | 230k | zend_bitset_incl(ctx->phi_worklist, var_num); |
283 | 230k | } |
284 | 372k | } |
285 | 1.42M | } |
286 | | |
287 | 33.6k | static inline void add_to_phi_worklist_no_val(context *ctx, int var_num) { |
288 | 33.6k | zend_ssa_var *var = &ctx->ssa->vars[var_num]; |
289 | 33.6k | if (var->definition_phi && zend_bitset_in(ctx->phi_dead, var_num)) { |
290 | 5.47k | zend_bitset_incl(ctx->phi_worklist_no_val, var_num); |
291 | 5.47k | } |
292 | 33.6k | } |
293 | | |
294 | 1.32M | static zend_always_inline void add_operands_to_worklists(context *ctx, zend_op *opline, zend_ssa_op *ssa_op, zend_ssa *ssa, int check) { |
295 | 1.32M | if (ssa_op->result_use >= 0) { |
296 | 17.3k | add_to_worklists(ctx, ssa_op->result_use, check); |
297 | 17.3k | } |
298 | 1.32M | if (ssa_op->op1_use >= 0) { |
299 | 788k | if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op1_use) |
300 | 788k | || (opline->opcode == ZEND_ASSIGN |
301 | 765k | && (ssa->var_info[ssa_op->op1_use].type & MAY_BE_REF) != 0)) { |
302 | 765k | add_to_worklists(ctx, ssa_op->op1_use, check); |
303 | 765k | } else { |
304 | 22.9k | add_to_phi_worklist_no_val(ctx, ssa_op->op1_use); |
305 | 22.9k | } |
306 | 788k | } |
307 | 1.32M | if (ssa_op->op2_use >= 0) { |
308 | 266k | if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op2_use) |
309 | 266k | || (opline->opcode == ZEND_FE_FETCH_R |
310 | 264k | && (ssa->var_info[ssa_op->op2_use].type & MAY_BE_REF) != 0)) { |
311 | 264k | add_to_worklists(ctx, ssa_op->op2_use, check); |
312 | 264k | } else { |
313 | 1.52k | add_to_phi_worklist_no_val(ctx, ssa_op->op2_use); |
314 | 1.52k | } |
315 | 266k | } |
316 | 1.32M | } |
317 | | |
318 | 212k | static zend_always_inline void add_phi_sources_to_worklists(context *ctx, zend_ssa_phi *phi, int check) { |
319 | 212k | zend_ssa *ssa = ctx->ssa; |
320 | 212k | int source; |
321 | 958k | FOREACH_PHI_SOURCE(phi, source) { |
322 | 958k | add_to_worklists(ctx, source, check); |
323 | 958k | } FOREACH_PHI_SOURCE_END(); |
324 | 212k | } |
325 | | |
326 | 10.9k | static inline bool is_var_dead(context *ctx, int var_num) { |
327 | 10.9k | zend_ssa_var *var = &ctx->ssa->vars[var_num]; |
328 | 10.9k | if (var->definition_phi) { |
329 | 718 | return zend_bitset_in(ctx->phi_dead, var_num); |
330 | 10.2k | } else if (var->definition >= 0) { |
331 | 6.43k | return zend_bitset_in(ctx->instr_dead, var->definition); |
332 | 6.43k | } else { |
333 | | /* Variable has no definition, so either the definition has already been removed (var is |
334 | | * dead) or this is one of the implicit variables at the start of the function (for our |
335 | | * purposes live) */ |
336 | 3.76k | return var_num >= ctx->op_array->last_var; |
337 | 3.76k | } |
338 | 10.9k | } |
339 | | |
340 | | // Sometimes we can mark the var as EXT_UNUSED |
341 | 5.02k | static bool try_remove_var_def(context *ctx, int free_var, int use_chain, zend_op *opline) { |
342 | 5.02k | if (use_chain >= 0) { |
343 | 0 | return 0; |
344 | 0 | } |
345 | 5.02k | zend_ssa_var *var = &ctx->ssa->vars[free_var]; |
346 | 5.02k | int def = var->definition; |
347 | | |
348 | 5.02k | if (def >= 0) { |
349 | 4.97k | zend_ssa_op *def_op = &ctx->ssa->ops[def]; |
350 | | |
351 | 4.97k | if (def_op->result_def == free_var |
352 | 4.97k | && var->phi_use_chain == NULL |
353 | 4.97k | && var->use_chain == (opline - ctx->op_array->opcodes)) { |
354 | 4.87k | zend_op *def_opline = &ctx->op_array->opcodes[def]; |
355 | | |
356 | 4.87k | switch (def_opline->opcode) { |
357 | 155 | case ZEND_ASSIGN: |
358 | 155 | case ZEND_ASSIGN_REF: |
359 | 164 | case ZEND_ASSIGN_DIM: |
360 | 170 | case ZEND_ASSIGN_OBJ: |
361 | 170 | case ZEND_ASSIGN_OBJ_REF: |
362 | 170 | case ZEND_ASSIGN_STATIC_PROP: |
363 | 170 | case ZEND_ASSIGN_STATIC_PROP_REF: |
364 | 323 | case ZEND_ASSIGN_OP: |
365 | 333 | case ZEND_ASSIGN_DIM_OP: |
366 | 333 | case ZEND_ASSIGN_OBJ_OP: |
367 | 333 | case ZEND_ASSIGN_STATIC_PROP_OP: |
368 | 333 | case ZEND_PRE_INC: |
369 | 333 | case ZEND_PRE_DEC: |
370 | 333 | case ZEND_PRE_INC_OBJ: |
371 | 333 | case ZEND_PRE_DEC_OBJ: |
372 | 333 | case ZEND_DO_ICALL: |
373 | 335 | case ZEND_DO_UCALL: |
374 | 335 | case ZEND_DO_FCALL_BY_NAME: |
375 | 697 | case ZEND_DO_FCALL: |
376 | 697 | case ZEND_INCLUDE_OR_EVAL: |
377 | 697 | case ZEND_YIELD: |
378 | 697 | case ZEND_YIELD_FROM: |
379 | 697 | case ZEND_ASSERT_CHECK: |
380 | 697 | def_opline->result_type = IS_UNUSED; |
381 | 697 | def_opline->result.var = 0; |
382 | 697 | def_op->result_def = -1; |
383 | 697 | var->definition = -1; |
384 | 697 | return 1; |
385 | 4.17k | default: |
386 | 4.17k | break; |
387 | 4.87k | } |
388 | 4.87k | } |
389 | 4.97k | } |
390 | 4.32k | return 0; |
391 | 5.02k | } |
392 | | |
393 | 59.5k | static zend_always_inline bool may_be_refcounted(uint32_t type) { |
394 | 59.5k | return (type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)) != 0; |
395 | 59.5k | } |
396 | | |
397 | 14.4k | static inline bool is_free_of_live_var(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) { |
398 | 14.4k | switch (opline->opcode) { |
399 | 5.41k | case ZEND_FREE: |
400 | | /* It is always safe to remove FREEs of non-refcounted values, even if they are live. */ |
401 | 5.41k | if ((ctx->ssa->var_info[ssa_op->op1_use].type & (MAY_BE_REF|MAY_BE_ANY|MAY_BE_UNDEF)) != 0 |
402 | 5.41k | && !may_be_refcounted(ctx->ssa->var_info[ssa_op->op1_use].type)) { |
403 | 4.01k | return 0; |
404 | 4.01k | } |
405 | 1.39k | ZEND_FALLTHROUGH; |
406 | 2.07k | case ZEND_FE_FREE: |
407 | 2.07k | return !is_var_dead(ctx, ssa_op->op1_use); |
408 | 8.37k | default: |
409 | 8.37k | return 0; |
410 | 14.4k | } |
411 | 14.4k | } |
412 | | |
413 | | /* Returns whether the instruction has been DCEd */ |
414 | 17.0k | static bool dce_instr(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) { |
415 | 17.0k | zend_ssa *ssa = ctx->ssa; |
416 | 17.0k | int free_var = -1; |
417 | 17.0k | uint8_t free_var_type; |
418 | | |
419 | 17.0k | if (opline->opcode == ZEND_NOP) { |
420 | 2.59k | return 0; |
421 | 2.59k | } |
422 | | |
423 | | /* We mark FREEs as dead, but they're only really dead if the destroyed var is dead */ |
424 | 14.4k | if (is_free_of_live_var(ctx, opline, ssa_op)) { |
425 | 1.52k | return 0; |
426 | 1.52k | } |
427 | | |
428 | 12.9k | if ((opline->op1_type & (IS_VAR|IS_TMP_VAR))&& !is_var_dead(ctx, ssa_op->op1_use)) { |
429 | 3.69k | if (!try_remove_var_def(ctx, ssa_op->op1_use, ssa_op->op1_use_chain, opline)) { |
430 | 3.51k | if (may_be_refcounted(ssa->var_info[ssa_op->op1_use].type) |
431 | 3.51k | && opline->opcode != ZEND_CASE && opline->opcode != ZEND_CASE_STRICT) { |
432 | 179 | free_var = ssa_op->op1_use; |
433 | 179 | free_var_type = opline->op1_type; |
434 | 179 | } |
435 | 3.51k | } |
436 | 3.69k | } |
437 | 12.9k | if ((opline->op2_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op2_use)) { |
438 | 1.32k | if (!try_remove_var_def(ctx, ssa_op->op2_use, ssa_op->op2_use_chain, opline)) { |
439 | 814 | if (may_be_refcounted(ssa->var_info[ssa_op->op2_use].type)) { |
440 | 326 | if (free_var >= 0) { |
441 | | // TODO: We can't free two vars. Keep instruction alive. |
442 | 113 | zend_bitset_excl(ctx->instr_dead, opline - ctx->op_array->opcodes); |
443 | 113 | return 0; |
444 | 113 | } |
445 | 213 | free_var = ssa_op->op2_use; |
446 | 213 | free_var_type = opline->op2_type; |
447 | 213 | } |
448 | 814 | } |
449 | 1.32k | } |
450 | | |
451 | 12.8k | zend_ssa_rename_defs_of_instr(ctx->ssa, ssa_op); |
452 | 12.8k | zend_ssa_remove_instr(ctx->ssa, opline, ssa_op); |
453 | | |
454 | 12.8k | if (free_var >= 0) { |
455 | 279 | opline->opcode = ZEND_FREE; |
456 | 279 | opline->op1.var = EX_NUM_TO_VAR(ssa->vars[free_var].var); |
457 | 279 | opline->op1_type = free_var_type; |
458 | | |
459 | 279 | ssa_op->op1_use = free_var; |
460 | 279 | ssa_op->op1_use_chain = ssa->vars[free_var].use_chain; |
461 | 279 | ssa->vars[free_var].use_chain = ssa_op - ssa->ops; |
462 | 279 | return 0; |
463 | 279 | } |
464 | 12.5k | return 1; |
465 | 12.8k | } |
466 | | |
467 | 117k | static inline int get_common_phi_source(zend_ssa *ssa, zend_ssa_phi *phi) { |
468 | 117k | int common_source = -1; |
469 | 117k | int source; |
470 | 587k | FOREACH_PHI_SOURCE(phi, source) { |
471 | 587k | if (source == phi->ssa_var) { |
472 | 1.28k | continue; |
473 | 1.28k | } |
474 | 233k | if (common_source == -1) { |
475 | 117k | common_source = source; |
476 | 117k | } else if (common_source != source) { |
477 | 116k | return -1; |
478 | 116k | } |
479 | 233k | } FOREACH_PHI_SOURCE_END(); |
480 | | |
481 | | /* If all sources are phi->ssa_var this phi must be in an unreachable cycle. |
482 | | * We can't easily drop the phi in that case, as we don't have something to replace it with. |
483 | | * Ideally SCCP would eliminate the whole cycle. */ |
484 | 545 | return common_source; |
485 | 117k | } |
486 | | |
487 | 171k | static void try_remove_trivial_phi(context *ctx, zend_ssa_phi *phi) { |
488 | 171k | zend_ssa *ssa = ctx->ssa; |
489 | 171k | if (phi->pi < 0) { |
490 | | /* Phi assignment with identical source operands */ |
491 | 117k | int common_source = get_common_phi_source(ssa, phi); |
492 | 117k | if (common_source >= 0) { |
493 | 545 | zend_ssa_rename_var_uses(ssa, phi->ssa_var, common_source, 1); |
494 | 545 | zend_ssa_remove_phi(ssa, phi); |
495 | 545 | } |
496 | 117k | } else { |
497 | | /* Pi assignment that is only used in Phi/Pi assignments */ |
498 | | // TODO What if we want to rerun type inference after DCE? Maybe separate this? |
499 | | /*ZEND_ASSERT(phi->sources[0] != -1); |
500 | | if (ssa->vars[phi->ssa_var].use_chain < 0) { |
501 | | zend_ssa_rename_var_uses_keep_types(ssa, phi->ssa_var, phi->sources[0], 1); |
502 | | zend_ssa_remove_phi(ssa, phi); |
503 | | }*/ |
504 | 53.9k | } |
505 | 171k | } |
506 | | |
507 | 0 | static inline bool may_break_varargs(const zend_op_array *op_array, const zend_ssa *ssa, const zend_ssa_op *ssa_op) { |
508 | 0 | if (ssa_op->op1_def >= 0 |
509 | 0 | && ssa->vars[ssa_op->op1_def].var < op_array->num_args) { |
510 | 0 | return 1; |
511 | 0 | } |
512 | 0 | if (ssa_op->op2_def >= 0 |
513 | 0 | && ssa->vars[ssa_op->op2_def].var < op_array->num_args) { |
514 | 0 | return 1; |
515 | 0 | } |
516 | 0 | if (ssa_op->result_def >= 0 |
517 | 0 | && ssa->vars[ssa_op->result_def].var < op_array->num_args) { |
518 | 0 | return 1; |
519 | 0 | } |
520 | 0 | return 0; |
521 | 0 | } |
522 | | |
523 | 23.3k | static inline bool may_throw_dce_exception(const zend_op *opline) { |
524 | 23.3k | return opline->opcode == ZEND_ADD_ARRAY_ELEMENT && opline->op2_type == IS_UNUSED; |
525 | 23.3k | } |
526 | | |
527 | 74.1k | int dce_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *optimizer_ctx, zend_ssa *ssa, bool reorder_dtor_effects) { |
528 | 74.1k | int i; |
529 | 74.1k | zend_ssa_phi *phi; |
530 | 74.1k | int removed_ops = 0; |
531 | | |
532 | | /* DCE of CV operations that changes arguments may affect vararg functions. */ |
533 | 74.1k | bool has_varargs = (ssa->cfg.flags & ZEND_FUNC_VARARG) != 0; |
534 | | |
535 | 74.1k | context ctx; |
536 | 74.1k | ctx.ssa = ssa; |
537 | 74.1k | ctx.op_array = op_array; |
538 | 74.1k | ctx.reorder_dtor_effects = reorder_dtor_effects; |
539 | | |
540 | 74.1k | void *checkpoint = zend_arena_checkpoint(optimizer_ctx->arena); |
541 | | /* We have no dedicated phi vector, so we use the whole ssa var vector instead */ |
542 | 74.1k | ctx.instr_worklist_len = zend_bitset_len(op_array->last); |
543 | 74.1k | ctx.instr_worklist = zend_arena_calloc(&optimizer_ctx->arena, ctx.instr_worklist_len, sizeof(zend_ulong)); |
544 | 74.1k | ctx.phi_worklist_len = zend_bitset_len(ssa->vars_count); |
545 | 74.1k | ctx.phi_worklist = zend_arena_calloc(&optimizer_ctx->arena, ctx.phi_worklist_len, sizeof(zend_ulong)); |
546 | 74.1k | ctx.phi_worklist_no_val = zend_arena_calloc(&optimizer_ctx->arena, ctx.phi_worklist_len, sizeof(zend_ulong)); |
547 | | |
548 | | /* Optimistically assume all instructions and phis to be dead */ |
549 | 74.1k | ctx.instr_dead = zend_arena_calloc(&optimizer_ctx->arena, ctx.instr_worklist_len, sizeof(zend_ulong)); |
550 | 74.1k | ctx.phi_dead = zend_arena_alloc(&optimizer_ctx->arena, ctx.phi_worklist_len * sizeof(zend_ulong)); |
551 | 74.1k | memset(ctx.phi_dead, 0xff, sizeof(zend_ulong) * ctx.phi_worklist_len); |
552 | | |
553 | | /* Mark non-CV phis as live. Even if the result is unused, we generally cannot remove one |
554 | | * of the producing instructions, as it combines producing the result with control flow. |
555 | | * This can be made more precise if there are any cases where this is not the case. */ |
556 | 466k | FOREACH_PHI(phi) { |
557 | 466k | if (phi->var >= op_array->last_var |
558 | 175k | && may_be_refcounted(ssa->var_info[phi->ssa_var].type)) { |
559 | 45.7k | zend_bitset_excl(ctx.phi_dead, phi->ssa_var); |
560 | 45.7k | add_phi_sources_to_worklists(&ctx, phi, 0); |
561 | 45.7k | } |
562 | 466k | } FOREACH_PHI_END(); |
563 | | |
564 | | /* Mark reachable instruction without side effects as dead */ |
565 | 74.1k | int b = ssa->cfg.blocks_count; |
566 | 290k | while (b > 0) { |
567 | 216k | int op_data = -1; |
568 | | |
569 | 216k | b--; |
570 | 216k | zend_basic_block *block = &ssa->cfg.blocks[b]; |
571 | 216k | if (!(block->flags & ZEND_BB_REACHABLE)) { |
572 | 2.19k | continue; |
573 | 2.19k | } |
574 | 214k | i = block->start + block->len; |
575 | 1.55M | while (i > block->start) { |
576 | 1.34M | i--; |
577 | | |
578 | 1.34M | if (op_array->opcodes[i].opcode == ZEND_OP_DATA) { |
579 | 17.3k | op_data = i; |
580 | 17.3k | continue; |
581 | 17.3k | } |
582 | | |
583 | 1.32M | if (zend_bitset_in(ctx.instr_worklist, i)) { |
584 | 755k | zend_bitset_excl(ctx.instr_worklist, i); |
585 | 755k | add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 0); |
586 | 755k | if (op_data >= 0) { |
587 | 7.90k | add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], ssa, 0); |
588 | 7.90k | } |
589 | 755k | } else if (may_have_side_effects(op_array, ssa, &op_array->opcodes[i], &ssa->ops[i], ctx.reorder_dtor_effects) |
590 | 569k | || (zend_may_throw(&op_array->opcodes[i], &ssa->ops[i], op_array, ssa) |
591 | 47.8k | && !may_throw_dce_exception(&op_array->opcodes[i])) |
592 | 569k | || (has_varargs && may_break_varargs(op_array, ssa, &ssa->ops[i]))) { |
593 | 545k | if (op_array->opcodes[i].opcode == ZEND_NEW |
594 | 545k | && op_array->opcodes[i+1].opcode == ZEND_DO_FCALL |
595 | 545k | && ssa->ops[i].result_def >= 0 |
596 | 545k | && ssa->vars[ssa->ops[i].result_def].escape_state == ESCAPE_STATE_NO_ESCAPE) { |
597 | 90 | zend_bitset_incl(ctx.instr_dead, i); |
598 | 90 | zend_bitset_incl(ctx.instr_dead, i+1); |
599 | 544k | } else { |
600 | 544k | add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 0); |
601 | 544k | if (op_data >= 0) { |
602 | 9.35k | add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], ssa, 0); |
603 | 9.35k | } |
604 | 544k | } |
605 | 545k | } else { |
606 | 24.5k | zend_bitset_incl(ctx.instr_dead, i); |
607 | 24.5k | if (op_data >= 0) { |
608 | 80 | zend_bitset_incl(ctx.instr_dead, op_data); |
609 | 80 | } |
610 | 24.5k | } |
611 | 1.32M | op_data = -1; |
612 | 1.32M | } |
613 | 214k | } |
614 | | |
615 | | /* Propagate liveness backwards to all definitions of used vars */ |
616 | 85.2k | while (!zend_bitset_empty(ctx.instr_worklist, ctx.instr_worklist_len) |
617 | 85.2k | || !zend_bitset_empty(ctx.phi_worklist, ctx.phi_worklist_len)) { |
618 | 18.8k | while ((i = zend_bitset_pop_first(ctx.instr_worklist, ctx.instr_worklist_len)) >= 0) { |
619 | 7.77k | zend_bitset_excl(ctx.instr_dead, i); |
620 | 7.77k | add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 1); |
621 | 7.77k | if (i < op_array->last |
622 | 7.77k | && (op_array->opcodes[i+1].opcode == ZEND_OP_DATA |
623 | 7.77k | || (op_array->opcodes[i].opcode == ZEND_NEW |
624 | 7.72k | && op_array->opcodes[i+1].opcode == ZEND_DO_FCALL))) { |
625 | 64 | zend_bitset_excl(ctx.instr_dead, i+1); |
626 | 64 | add_operands_to_worklists(&ctx, &op_array->opcodes[i+1], &ssa->ops[i+1], ssa, 1); |
627 | 64 | } |
628 | 7.77k | } |
629 | 177k | while ((i = zend_bitset_pop_first(ctx.phi_worklist, ctx.phi_worklist_len)) >= 0) { |
630 | 166k | zend_bitset_excl(ctx.phi_dead, i); |
631 | 166k | zend_bitset_excl(ctx.phi_worklist_no_val, i); |
632 | 166k | add_phi_sources_to_worklists(&ctx, ssa->vars[i].definition_phi, 1); |
633 | 166k | } |
634 | 11.1k | } |
635 | | |
636 | | /* Eliminate dead instructions */ |
637 | 273k | ZEND_BITSET_FOREACH(ctx.instr_dead, ctx.instr_worklist_len, i) { |
638 | 17.0k | removed_ops += dce_instr(&ctx, &op_array->opcodes[i], &ssa->ops[i]); |
639 | 17.0k | } ZEND_BITSET_FOREACH_END(); |
640 | | |
641 | | /* Improper uses don't count as "uses" for the purpose of instruction elimination, |
642 | | * but we have to retain phis defining them. |
643 | | * Propagate this information backwards, marking any phi with an improperly used |
644 | | * target as non-dead. */ |
645 | 78.8k | while ((i = zend_bitset_pop_first(ctx.phi_worklist_no_val, ctx.phi_worklist_len)) >= 0) { |
646 | 4.71k | zend_ssa_phi *phi = ssa->vars[i].definition_phi; |
647 | 4.71k | int source; |
648 | 4.71k | zend_bitset_excl(ctx.phi_dead, i); |
649 | 23.0k | FOREACH_PHI_SOURCE(phi, source) { |
650 | 23.0k | add_to_phi_worklist_no_val(&ctx, source); |
651 | 23.0k | } FOREACH_PHI_SOURCE_END(); |
652 | 4.71k | } |
653 | | |
654 | | /* Now collect the actually dead phis */ |
655 | 466k | FOREACH_PHI(phi) { |
656 | 466k | if (zend_bitset_in(ctx.phi_dead, phi->ssa_var)) { |
657 | 4.36k | zend_ssa_remove_uses_of_var(ssa, phi->ssa_var); |
658 | 4.36k | zend_ssa_remove_phi(ssa, phi); |
659 | 171k | } else { |
660 | | /* Remove trivial phis (phis with identical source operands) */ |
661 | 171k | try_remove_trivial_phi(&ctx, phi); |
662 | 171k | } |
663 | 466k | } FOREACH_PHI_END(); |
664 | | |
665 | 74.1k | zend_arena_release(&optimizer_ctx->arena, checkpoint); |
666 | | |
667 | 74.1k | return removed_ops; |
668 | 74.1k | } |