Coverage Report

Created: 2025-06-13 06:43

/src/php-src/Zend/Optimizer/scdf.c
Line
Count
Source (jump to first uncovered line)
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
54
211k
void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) {
55
211k
  uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);
56
57
211k
  if (zend_bitset_in(scdf->feasible_edges, edge)) {
58
    /* We already handled this edge */
59
3.25k
    return;
60
3.25k
  }
61
62
207k
  DEBUG_PRINT("Marking edge %d->%d feasible\n", from, to);
63
207k
  zend_bitset_incl(scdf->feasible_edges, edge);
64
65
207k
  if (!zend_bitset_in(scdf->executable_blocks, to)) {
66
197k
    if (!zend_bitset_in(scdf->block_worklist, to)) {
67
140k
      DEBUG_PRINT("Adding block %d to worklist\n", to);
68
140k
    }
69
197k
    zend_bitset_incl(scdf->block_worklist, to);
70
197k
  } else {
71
    /* Block is already executable, only a new edge became feasible.
72
     * Reevaluate phi nodes to account for changed source operands. */
73
10.4k
    zend_ssa_block *ssa_block = &scdf->ssa->blocks[to];
74
10.4k
    zend_ssa_phi *phi;
75
36.0k
    for (phi = ssa_block->phis; phi; phi = phi->next) {
76
25.6k
      zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
77
25.6k
      scdf->handlers.visit_phi(scdf, phi);
78
25.6k
    }
79
10.4k
  }
80
207k
}
81
82
74.1k
void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) {
83
74.1k
  scdf->op_array = op_array;
84
74.1k
  scdf->ssa = ssa;
85
86
74.1k
  scdf->instr_worklist_len = zend_bitset_len(op_array->last);
87
74.1k
  scdf->phi_var_worklist_len = zend_bitset_len(ssa->vars_count);
88
74.1k
  scdf->block_worklist_len = zend_bitset_len(ssa->cfg.blocks_count);
89
90
74.1k
  scdf->instr_worklist = zend_arena_calloc(&ctx->arena,
91
74.1k
    scdf->instr_worklist_len + scdf->phi_var_worklist_len + 2 * scdf->block_worklist_len + zend_bitset_len(ssa->cfg.edges_count),
92
74.1k
    sizeof(zend_ulong));
93
94
74.1k
  scdf->phi_var_worklist = scdf->instr_worklist + scdf->instr_worklist_len;
95
74.1k
  scdf->block_worklist = scdf->phi_var_worklist + scdf->phi_var_worklist_len;
96
74.1k
  scdf->executable_blocks = scdf->block_worklist + scdf->block_worklist_len;
97
74.1k
  scdf->feasible_edges = scdf->executable_blocks + scdf->block_worklist_len;
98
99
74.1k
  zend_bitset_incl(scdf->block_worklist, 0);
100
74.1k
  zend_bitset_incl(scdf->executable_blocks, 0);
101
74.1k
}
102
103
74.1k
void scdf_solve(scdf_ctx *scdf, const char *name) {
104
74.1k
  zend_ssa *ssa = scdf->ssa;
105
74.1k
  DEBUG_PRINT("Start SCDF solve (%s)\n", name);
106
151k
  while (!zend_bitset_empty(scdf->instr_worklist, scdf->instr_worklist_len)
107
151k
    || !zend_bitset_empty(scdf->phi_var_worklist, scdf->phi_var_worklist_len)
108
151k
    || !zend_bitset_empty(scdf->block_worklist, scdf->block_worklist_len)
109
77.1k
  ) {
110
77.1k
    int i;
111
82.2k
    while ((i = zend_bitset_pop_first(scdf->phi_var_worklist, scdf->phi_var_worklist_len)) >= 0) {
112
5.14k
      zend_ssa_phi *phi = ssa->vars[i].definition_phi;
113
5.14k
      ZEND_ASSERT(phi);
114
5.14k
      if (zend_bitset_in(scdf->executable_blocks, phi->block)) {
115
4.08k
        scdf->handlers.visit_phi(scdf, phi);
116
4.08k
      }
117
5.14k
    }
118
119
86.7k
    while ((i = zend_bitset_pop_first(scdf->instr_worklist, scdf->instr_worklist_len)) >= 0) {
120
9.66k
      int block_num = ssa->cfg.map[i];
121
9.66k
      if (zend_bitset_in(scdf->executable_blocks, block_num)) {
122
7.84k
        zend_basic_block *block = &ssa->cfg.blocks[block_num];
123
7.84k
        zend_op *opline = &scdf->op_array->opcodes[i];
124
7.84k
        zend_ssa_op *ssa_op = &ssa->ops[i];
125
7.84k
        if (opline->opcode == ZEND_OP_DATA) {
126
24
          opline--;
127
24
          ssa_op--;
128
24
        }
129
7.84k
        scdf->handlers.visit_instr(scdf, opline, ssa_op);
130
7.84k
        if (i == block->start + block->len - 1) {
131
3.01k
          if (block->successors_count == 1) {
132
1.21k
            scdf_mark_edge_feasible(scdf, block_num, block->successors[0]);
133
1.80k
          } else if (block->successors_count > 1) {
134
1.79k
            scdf->handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op);
135
1.79k
          }
136
3.01k
        }
137
7.84k
      }
138
9.66k
    }
139
140
292k
    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
214k
      zend_basic_block *block = &ssa->cfg.blocks[i];
143
214k
      zend_ssa_block *ssa_block = &ssa->blocks[i];
144
145
214k
      DEBUG_PRINT("Pop block %d from worklist\n", i);
146
214k
      zend_bitset_incl(scdf->executable_blocks, i);
147
148
214k
      {
149
214k
        zend_ssa_phi *phi;
150
390k
        for (phi = ssa_block->phis; phi; phi = phi->next) {
151
176k
          zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var);
152
176k
          scdf->handlers.visit_phi(scdf, phi);
153
176k
        }
154
214k
      }
155
156
214k
      if (block->len == 0) {
157
        /* Zero length blocks don't have a last instruction that would normally do this */
158
139
        scdf_mark_edge_feasible(scdf, i, block->successors[0]);
159
214k
      } else {
160
214k
        zend_op *opline = NULL;
161
214k
        int j, end = block->start + block->len;
162
1.55M
        for (j = block->start; j < end; j++) {
163
1.34M
          opline = &scdf->op_array->opcodes[j];
164
1.34M
          zend_bitset_excl(scdf->instr_worklist, j);
165
1.34M
          if (opline->opcode != ZEND_OP_DATA) {
166
1.32M
            scdf->handlers.visit_instr(scdf, opline, &ssa->ops[j]);
167
1.32M
          }
168
1.34M
        }
169
214k
        if (block->successors_count == 1) {
170
71.0k
          scdf_mark_edge_feasible(scdf, i, block->successors[0]);
171
143k
        } else if (block->successors_count > 1) {
172
68.8k
          ZEND_ASSERT(opline && "Should have opline in non-empty block");
173
68.8k
          if (opline->opcode == ZEND_OP_DATA) {
174
0
            opline--;
175
0
            j--;
176
0
          }
177
68.8k
          scdf->handlers.mark_feasible_successors(scdf, i, block, opline, &ssa->ops[j-1]);
178
68.8k
        }
179
214k
      }
180
214k
    }
181
77.1k
  }
182
74.1k
}
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. */
187
static bool is_live_loop_var_free(
188
724
    scdf_ctx *scdf, const zend_op *opline, const zend_ssa_op *ssa_op) {
189
724
  if (!zend_optimizer_is_loop_var_free(opline)) {
190
680
    return false;
191
680
  }
192
193
44
  int var = ssa_op->op1_use;
194
44
  if (var < 0) {
195
0
    return false;
196
0
  }
197
198
44
  zend_ssa_var *ssa_var = &scdf->ssa->vars[var];
199
44
  uint32_t def_block;
200
44
  if (ssa_var->definition >= 0) {
201
12
    def_block = scdf->ssa->cfg.map[ssa_var->definition];
202
32
  } else {
203
32
    def_block = ssa_var->definition_phi->block;
204
32
  }
205
44
  return zend_bitset_in(scdf->executable_blocks, def_block);
206
44
}
207
208
1.69k
static bool kept_alive_by_loop_var_free(scdf_ctx *scdf, const zend_basic_block *block) {
209
1.69k
  const zend_op_array *op_array = scdf->op_array;
210
1.69k
  const zend_cfg *cfg = &scdf->ssa->cfg;
211
1.69k
  if (!(cfg->flags & ZEND_FUNC_FREE_LOOP_VAR)) {
212
1.38k
    return false;
213
1.38k
  }
214
215
959
  for (uint32_t i = block->start; i < block->start + block->len; i++) {
216
666
    if (is_live_loop_var_free(scdf, &op_array->opcodes[i], &scdf->ssa->ops[i])) {
217
22
      return true;
218
22
    }
219
666
  }
220
293
  return false;
221
315
}
222
223
22
static uint32_t cleanup_loop_var_free_block(scdf_ctx *scdf, zend_basic_block *block) {
224
22
  zend_ssa *ssa = scdf->ssa;
225
22
  const zend_op_array *op_array = scdf->op_array;
226
22
  const zend_cfg *cfg = &ssa->cfg;
227
22
  int block_num = block - cfg->blocks;
228
22
  uint32_t removed_ops = 0;
229
230
  /* Removes phi nodes */
231
24
  for (zend_ssa_phi *phi = ssa->blocks[block_num].phis; phi; phi = phi->next) {
232
2
    zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
233
2
    zend_ssa_remove_phi(ssa, phi);
234
2
  }
235
236
80
  for (uint32_t i = block->start; i < block->start + block->len; i++) {
237
58
    zend_op *opline = &op_array->opcodes[i];
238
58
    zend_ssa_op *ssa_op = &scdf->ssa->ops[i];
239
58
    if (opline->opcode == ZEND_NOP
240
58
     || is_live_loop_var_free(scdf, opline, ssa_op)) {
241
22
      continue;
242
22
    }
243
244
    /* While we have to preserve the loop var free, we can still remove other instructions
245
     * in the block. */
246
36
    zend_ssa_remove_defs_of_instr(ssa, ssa_op);
247
36
    zend_ssa_remove_instr(ssa, opline, ssa_op);
248
36
    removed_ops++;
249
36
  }
250
251
22
  zend_ssa_remove_block_from_cfg(ssa, block_num);
252
253
22
  return removed_ops;
254
22
}
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. */
259
74.1k
uint32_t scdf_remove_unreachable_blocks(scdf_ctx *scdf) {
260
74.1k
  zend_ssa *ssa = scdf->ssa;
261
74.1k
  int i;
262
74.1k
  uint32_t removed_ops = 0;
263
290k
  for (i = 0; i < ssa->cfg.blocks_count; i++) {
264
216k
    zend_basic_block *block = &ssa->cfg.blocks[i];
265
216k
    if (!zend_bitset_in(scdf->executable_blocks, i) && (block->flags & ZEND_BB_REACHABLE)) {
266
1.69k
      if (!kept_alive_by_loop_var_free(scdf, block)) {
267
1.67k
        removed_ops += block->len;
268
1.67k
        zend_ssa_remove_block(scdf->op_array, ssa, i);
269
1.67k
      } else {
270
22
        removed_ops += cleanup_loop_var_free_block(scdf, block);
271
22
      }
272
1.69k
    }
273
216k
  }
274
74.1k
  return removed_ops;
275
74.1k
}