Coverage Report

Created: 2025-06-13 06:43

/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
}