[prev in list] [next in list] [prev in thread] [next in thread]
List: php-cvs
Subject: [PHP-CVS] [php-src] PHP-8.3: Merge branch 'PHP-8.2' into PHP-8.3
From: Dmitry Stogov <noreply () php ! net>
Date: 2023-10-31 6:58:32
Message-ID: ImbPdOdkmsp8xVrAdr5n83H4A0p66NsRkEIZh7gAqE () main ! php ! net
[Download RAW message or body]
Author: Dmitry Stogov (dstogov)
Date: 2023-10-31T09:59:47+03:00
Commit: https://github.com/php/php-src/commit/76112a15ae2f7dcd5754ce37b1bbd2848afb2571
Raw diff: https://github.com/php/php-src/commit/76112a15ae2f7dcd5754ce37b1bbd2848afb2571.diff
Merge branch 'PHP-8.2' into PHP-8.3
* PHP-8.2:
Backport implementation of iterative Pearce's SCC finding algoritm (#12528)
Changed paths:
M Zend/Optimizer/zend_inference.c
Diff:
diff --git a/Zend/Optimizer/zend_inference.c b/Zend/Optimizer/zend_inference.c
index 82c91ebd879c..d9ae75e1cdcf 100644
--- a/Zend/Optimizer/zend_inference.c
+++ b/Zend/Optimizer/zend_inference.c
@@ -77,11 +77,12 @@
#define CHECK_SCC_VAR(var2) \
do { \
if (!ssa->vars[var2].no_val) { \
- if (dfs[var2] < 0) { \
- zend_ssa_check_scc_var(op_array, ssa, var2, index, dfs, root, stack); \
+ if (ssa->vars[var2].scc < 0) { \
+ zend_ssa_check_scc_var(op_array, ssa, var2, index, stack); \
} \
- if (ssa->vars[var2].scc < 0 && dfs[root[var]] >= dfs[root[var2]]) { \
- root[var] = root[var2]; \
+ if (ssa->vars[var2].scc < ssa->vars[var].scc) { \
+ ssa->vars[var].scc = ssa->vars[var2].scc; \
+ is_root = 0; \
} \
} \
} while (0)
@@ -172,15 +173,17 @@ static inline bool sub_will_overflow(zend_long a, zend_long b) \
{ }
#endif
-static void zend_ssa_check_scc_var(const zend_op_array *op_array, zend_ssa *ssa, int \
var, int *index, int *dfs, int *root, zend_worklist_stack *stack) /* {{{ */ +#if 0
+/* Recursive Pearce's SCC algorithm implementation */
+static void zend_ssa_check_scc_var(const zend_op_array *op_array, zend_ssa *ssa, int \
var, int *index, zend_worklist_stack *stack) /* {{{ */ {
+ int is_root = 1;
#ifdef SYM_RANGE
zend_ssa_phi *p;
#endif
- dfs[var] = *index;
+ ssa->vars[var].scc = *index;
(*index)++;
- root[var] = var;
FOR_EACH_VAR_USAGE(var, CHECK_SCC_VAR);
@@ -193,17 +196,20 @@ static void zend_ssa_check_scc_var(const zend_op_array \
*op_array, zend_ssa *ssa, }
#endif
- if (root[var] == var) {
- ssa->vars[var].scc = ssa->sccs;
+ if (is_root) {
+ ssa->sccs--;
while (stack->len > 0) {
int var2 = zend_worklist_stack_peek(stack);
- if (dfs[var2] <= dfs[var]) {
+ if (ssa->vars[var2].scc < ssa->vars[var].scc) {
break;
}
zend_worklist_stack_pop(stack);
ssa->vars[var2].scc = ssa->sccs;
+ (*index)--;
}
- ssa->sccs++;
+ ssa->vars[var].scc = ssa->sccs;
+ ssa->vars[var].scc_entry = 1;
+ (*index)--;
} else {
zend_worklist_stack_push(stack, var);
}
@@ -212,48 +218,275 @@ static void zend_ssa_check_scc_var(const zend_op_array \
*op_array, zend_ssa *ssa,
ZEND_API void zend_ssa_find_sccs(const zend_op_array *op_array, zend_ssa *ssa) /* \
{{{ */ {
- int index = 0, *dfs, *root;
+ int index = 0;
zend_worklist_stack stack;
int j;
- ALLOCA_FLAG(dfs_use_heap)
- ALLOCA_FLAG(root_use_heap)
ALLOCA_FLAG(stack_use_heap)
- dfs = do_alloca(sizeof(int) * ssa->vars_count, dfs_use_heap);
- memset(dfs, -1, sizeof(int) * ssa->vars_count);
- root = do_alloca(sizeof(int) * ssa->vars_count, root_use_heap);
ZEND_WORKLIST_STACK_ALLOCA(&stack, ssa->vars_count, stack_use_heap);
- /* Find SCCs using Tarjan's algorithm. */
+ /* Find SCCs using Pearce's algorithm. */
+ ssa->sccs = ssa->vars_count;
for (j = 0; j < ssa->vars_count; j++) {
- if (!ssa->vars[j].no_val && dfs[j] < 0) {
- zend_ssa_check_scc_var(op_array, ssa, j, &index, dfs, root, &stack);
+ if (!ssa->vars[j].no_val && ssa->vars[j].scc < 0) {
+ zend_ssa_check_scc_var(op_array, ssa, j, &index, &stack);
+ }
+ }
+
+ if (ssa->sccs) {
+ /* Shift SCC indexes. */
+ for (j = 0; j < ssa->vars_count; j++) {
+ if (ssa->vars[j].scc >= 0) {
+ ssa->vars[j].scc -= ssa->sccs;
+ }
}
}
+ ssa->sccs = ssa->vars_count - ssa->sccs;
- /* Revert SCC order. This results in a topological order. */
for (j = 0; j < ssa->vars_count; j++) {
if (ssa->vars[j].scc >= 0) {
- ssa->vars[j].scc = ssa->sccs - (ssa->vars[j].scc + 1);
+ int var = j;
+ FOR_EACH_VAR_USAGE(var, CHECK_SCC_ENTRY);
+ }
+ }
+
+ ZEND_WORKLIST_STACK_FREE_ALLOCA(&stack, stack_use_heap);
+}
+/* }}} */
+
+#else
+/* Iterative Pearce's SCC algorithm implementation */
+
+typedef struct _zend_scc_iterator {
+ int state;
+ int last;
+ union {
+ int use;
+ zend_ssa_phi *phi;
+ };
+} zend_scc_iterator;
+
+static int zend_scc_next(const zend_op_array *op_array, zend_ssa *ssa, int var, \
zend_scc_iterator *iterator) /* {{{ */ +{
+ zend_ssa_phi *phi;
+ int use, var2;
+
+ switch (iterator->state) {
+ case 0: goto state_0;
+ case 1: use = iterator->use; goto state_1;
+ case 2: use = iterator->use; goto state_2;
+ case 3: use = iterator->use; goto state_3;
+ case 4: use = iterator->use; goto state_4;
+ case 5: use = iterator->use; goto state_5;
+ case 6: use = iterator->use; goto state_6;
+ case 7: use = iterator->use; goto state_7;
+ case 8: use = iterator->use; goto state_8;
+ case 9: phi = iterator->phi; goto state_9;
+#ifdef SYM_RANGE
+ case 10: phi = iterator->phi; goto state_10;
+#endif
+ case 11: goto state_11;
+ }
+
+state_0:
+ use = ssa->vars[var].use_chain;
+ while (use >= 0) {
+ iterator->use = use;
+ var2 = ssa->ops[use].op1_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 1;
+ return var2;
+ }
+state_1:
+ var2 = ssa->ops[use].op2_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 2;
+ return var2;
}
+state_2:
+ var2 = ssa->ops[use].result_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 3;
+ return var2;
+ }
+state_3:
+ if (op_array->opcodes[use].opcode == ZEND_OP_DATA) {
+ var2 = ssa->ops[use-1].op1_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 4;
+ return var2;
+ }
+state_4:
+ var2 = ssa->ops[use-1].op2_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 5;
+ return var2;
+ }
+state_5:
+ var2 = ssa->ops[use-1].result_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 8;
+ return var2;
+ }
+ } else if ((uint32_t)use+1 < op_array->last &&
+ op_array->opcodes[use+1].opcode == ZEND_OP_DATA) {
+ var2 = ssa->ops[use+1].op1_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 6;
+ return var2;
+ }
+state_6:
+ var2 = ssa->ops[use+1].op2_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 7;
+ return var2;
+ }
+state_7:
+ var2 = ssa->ops[use+1].result_def;
+ if (var2 >= 0 && !ssa->vars[var2].no_val) {
+ iterator->state = 8;
+ return var2;
+ }
+ }
+state_8:
+ use = zend_ssa_next_use(ssa->ops, var, use);
}
+ phi = ssa->vars[var].phi_use_chain;
+ while (phi) {
+ var2 = phi->ssa_var;
+ if (!ssa->vars[var2].no_val) {
+ iterator->state = 9;
+ iterator->phi = phi;
+ return var2;
+ }
+state_9:
+ phi = zend_ssa_next_use_phi(ssa, var, phi);
+ }
+
+#ifdef SYM_RANGE
+ /* Process symbolic control-flow constraints */
+ phi = ssa->vars[var].sym_use_chain;
+ while (phi) {
+ var2 = phi->ssa_var;
+ if (!ssa->vars[var2].no_val) {
+ iterator->state = 10;
+ iterator->phi = phi;
+ return var2;
+ }
+state_10:
+ phi = phi->sym_use_chain;
+ }
+#endif
+
+ iterator->state = 11;
+state_11:
+ return -1;
+}
+/* }}} */
+
+static void zend_ssa_check_scc_var(const zend_op_array *op_array, zend_ssa *ssa, int \
var, int *index, zend_worklist_stack *stack, zend_worklist_stack *vstack, \
zend_scc_iterator *iterators) /* {{{ */ +{
+restart:
+ zend_worklist_stack_push(vstack, var);
+ iterators[var].state = 0;
+ iterators[var].last = -1;
+ ssa->vars[var].scc_entry = 1;
+ ssa->vars[var].scc = *index;
+ (*index)++;
+
+ while (vstack->len > 0) {
+ var = zend_worklist_stack_peek(vstack);
+ while (1) {
+ int var2;
+
+ if (iterators[var].last >= 0) {
+ /* finish edge */
+ var2 = iterators[var].last;
+ if (ssa->vars[var2].scc < ssa->vars[var].scc) {
+ ssa->vars[var].scc = ssa->vars[var2].scc;
+ ssa->vars[var].scc_entry = 0;
+ }
+ }
+ var2 = zend_scc_next(op_array, ssa, var, iterators + var);
+ iterators[var].last = var2;
+ if (var2 < 0) break;
+ /* begin edge */
+ if (ssa->vars[var2].scc < 0) {
+ var = var2;
+ goto restart;
+ }
+ }
+
+ /* finish visiting */
+ zend_worklist_stack_pop(vstack);
+ if (ssa->vars[var].scc_entry) {
+ ssa->sccs--;
+ while (stack->len > 0) {
+ int var2 = zend_worklist_stack_peek(stack);
+ if (ssa->vars[var2].scc < ssa->vars[var].scc) {
+ break;
+ }
+ zend_worklist_stack_pop(stack);
+ ssa->vars[var2].scc = ssa->sccs;
+ (*index)--;
+ }
+ ssa->vars[var].scc = ssa->sccs;
+ (*index)--;
+ } else {
+ zend_worklist_stack_push(stack, var);
+ }
+ }
+}
+/* }}} */
+
+ZEND_API void zend_ssa_find_sccs(const zend_op_array *op_array, zend_ssa *ssa) /* \
{{{ */ +{
+ int index = 0;
+ zend_worklist_stack stack, vstack;
+ zend_scc_iterator *iterators;
+ int j;
+ ALLOCA_FLAG(stack_use_heap)
+ ALLOCA_FLAG(vstack_use_heap)
+ ALLOCA_FLAG(iterators_use_heap)
+
+ iterators = do_alloca(sizeof(zend_scc_iterator) * ssa->vars_count, \
iterators_use_heap); + ZEND_WORKLIST_STACK_ALLOCA(&vstack, ssa->vars_count, \
vstack_use_heap); + ZEND_WORKLIST_STACK_ALLOCA(&stack, ssa->vars_count, \
stack_use_heap); +
+ /* Find SCCs using Pearce's algorithm. */
+ ssa->sccs = ssa->vars_count;
+ for (j = 0; j < ssa->vars_count; j++) {
+ if (!ssa->vars[j].no_val && ssa->vars[j].scc < 0) {
+ zend_ssa_check_scc_var(op_array, ssa, j, &index, &stack, &vstack, iterators);
+ }
+ }
+
+ if (ssa->sccs) {
+ /* Shift SCC indexes. */
+ for (j = 0; j < ssa->vars_count; j++) {
+ if (ssa->vars[j].scc >= 0) {
+ ssa->vars[j].scc -= ssa->sccs;
+ }
+ }
+ }
+ ssa->sccs = ssa->vars_count - ssa->sccs;
+
for (j = 0; j < ssa->vars_count; j++) {
if (ssa->vars[j].scc >= 0) {
int var = j;
- if (root[j] == j) {
- ssa->vars[j].scc_entry = 1;
- }
FOR_EACH_VAR_USAGE(var, CHECK_SCC_ENTRY);
}
}
ZEND_WORKLIST_STACK_FREE_ALLOCA(&stack, stack_use_heap);
- free_alloca(root, root_use_heap);
- free_alloca(dfs, dfs_use_heap);
+ ZEND_WORKLIST_STACK_FREE_ALLOCA(&vstack, vstack_use_heap);
+ free_alloca(iterators, iterators_use_heap);
}
/* }}} */
+#endif
+
ZEND_API void zend_ssa_find_false_dependencies(const zend_op_array *op_array, \
zend_ssa *ssa) /* {{{ */ {
zend_ssa_var *ssa_vars = ssa->vars;
--
PHP CVS Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic