summaryrefslogtreecommitdiff
path: root/ext/opcache/Optimizer/zend_inference.c
diff options
context:
space:
mode:
Diffstat (limited to 'ext/opcache/Optimizer/zend_inference.c')
-rw-r--r--ext/opcache/Optimizer/zend_inference.c127
1 files changed, 58 insertions, 69 deletions
diff --git a/ext/opcache/Optimizer/zend_inference.c b/ext/opcache/Optimizer/zend_inference.c
index 6276746bf4..afae8a7959 100644
--- a/ext/opcache/Optimizer/zend_inference.c
+++ b/ext/opcache/Optimizer/zend_inference.c
@@ -24,11 +24,39 @@
#include "zend_call_graph.h"
#include "zend_worklist.h"
-//#define LOG_SSA_RANGE
-//#define LOG_NEG_RANGE
+/* The used range inference algorithm is described in:
+ * V. Campos, R. Rodrigues, I. de Assis Costa and F. Pereira.
+ * "Speed and Precision in Range Analysis", SBLP'12.
+ *
+ * There are a couple degrees of freedom, we use:
+ * * Propagation on SCCs.
+ * * e-SSA for live range splitting.
+ * * Only intra-procedural inference.
+ * * Widening with warmup passes, but without jump sets.
+ */
+
+/* Whether to handle symbolic range constraints */
#define SYM_RANGE
+
+/* Whether to handle negative range constraints */
#define NEG_RANGE
-#define RANGE_WARMAP_PASSES 16
+
+/* Number of warmup passes to use prior to widening */
+#define RANGE_WARMUP_PASSES 16
+
+/* Logging for range inference in general */
+#if 0
+#define LOG_SSA_RANGE(...) fprintf(stderr, __VA_ARGS__)
+#else
+#define LOG_SSA_RANGE(...)
+#endif
+
+/* Logging for negative range constraints */
+#if 0
+#define LOG_NEG_RANGE(...) fprintf(stderr, __VA_ARGS__)
+#else
+#define LOG_NEG_RANGE(...)
+#endif
#define CHECK_SCC_VAR(var2) \
do { \
@@ -167,14 +195,14 @@ int zend_ssa_find_sccs(const zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
root = do_alloca(sizeof(int) * ssa->vars_count, root_use_heap);
ZEND_WORKLIST_STACK_ALLOCA(&stack, ssa->vars_count, stack_use_heap);
- /* Find SCCs */
+ /* Find SCCs using Tarjan's algorithm. */
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);
}
}
- /* Revert SCC order */
+ /* 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);
@@ -490,56 +518,41 @@ int zend_inference_calc_range(const zend_op_array *op_array, zend_ssa *ssa, int
zend_ssa_range_constraint *constraint = &p->constraint.range;
if (constraint->negative) {
if (ssa->var_info[p->sources[0]].has_range) {
- tmp->underflow = ssa->var_info[p->sources[0]].range.underflow;
- tmp->min = ssa->var_info[p->sources[0]].range.min;
- tmp->max = ssa->var_info[p->sources[0]].range.max;
- tmp->overflow = ssa->var_info[p->sources[0]].range.overflow;
+ *tmp = ssa->var_info[p->sources[0]].range;
} else if (narrowing) {
tmp->underflow = 1;
tmp->min = ZEND_LONG_MIN;
tmp->max = ZEND_LONG_MAX;
tmp->overflow = 1;
}
+
#ifdef NEG_RANGE
if (constraint->min_ssa_var < 0 &&
- constraint->min_ssa_var < 0 &&
+ constraint->max_ssa_var < 0 &&
ssa->var_info[p->ssa_var].has_range) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "%s() #%d [%ld..%ld] -> [%ld..%ld]?\n",
- op_array->function_name,
+ LOG_NEG_RANGE("%s() #%d [%ld..%ld] -> [%ld..%ld]?\n",
+ ZSTR_VAL(op_array->function_name),
p->ssa_var,
ssa->var_info[p->ssa_var].range.min,
ssa->var_info[p->ssa_var].range.max,
tmp->min,
tmp->max);
-#endif
if (constraint->negative == NEG_USE_LT &&
tmp->max >= constraint->range.min) {
tmp->overflow = 0;
tmp->max = constraint->range.min - 1;
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, " => [%ld..%ld]\n",
- tmp->min,
- tmp->max);
-#endif
+ LOG_NEG_RANGE(" => [%ld..%ld]\n", tmp->min, tmp->max);
} else if (constraint->negative == NEG_USE_GT &&
tmp->min <= constraint->range.max) {
tmp->underflow = 0;
tmp->min = constraint->range.max + 1;
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, " => [%ld..%ld]\n",
- tmp->min,
- tmp->max);
-#endif
+ LOG_NEG_RANGE(" => [%ld..%ld]\n", tmp->min, tmp->max);
}
}
#endif
} else if (ssa->var_info[p->sources[0]].has_range) {
/* intersection */
- tmp->underflow = ssa->var_info[p->sources[0]].range.underflow;
- tmp->min = ssa->var_info[p->sources[0]].range.min;
- tmp->max = ssa->var_info[p->sources[0]].range.max;
- tmp->overflow = ssa->var_info[p->sources[0]].range.overflow;
+ *tmp = ssa->var_info[p->sources[0]].range;
if (constraint->min_ssa_var < 0) {
tmp->underflow = constraint->range.underflow && tmp->underflow;
tmp->min = MAX(constraint->range.min, tmp->min);
@@ -1694,9 +1707,7 @@ void zend_inference_init_range(const zend_op_array *op_array, zend_ssa *ssa, int
ssa->var_info[var].range.min = min;
ssa->var_info[var].range.max = max;
ssa->var_info[var].range.overflow = overflow;
-#ifdef LOG_SSA_RANGE
- fprintf(stderr, " change range (init SCC %2d) %2d [%s%ld..%ld%s]\n", ssa->vars[var].scc, var, (underflow?"-- ":""), min, max, (overflow?" ++":""));
-#endif
+ LOG_SSA_RANGE(" change range (init SCC %2d) %2d [%s%ld..%ld%s]\n", ssa->vars[var].scc, var, (underflow?"-- ":""), min, max, (overflow?" ++":""));
}
int zend_inference_widening_meet(zend_ssa_var_info *var_info, zend_ssa_range *r)
@@ -1733,9 +1744,7 @@ static int zend_ssa_range_widening(const zend_op_array *op_array, zend_ssa *ssa,
if (zend_inference_calc_range(op_array, ssa, var, 1, 0, &tmp)) {
if (zend_inference_widening_meet(&ssa->var_info[var], &tmp)) {
-#ifdef LOG_SSA_RANGE
- fprintf(stderr, " change range (widening SCC %2d) %2d [%s%ld..%ld%s]\n", scc, var, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
-#endif
+ LOG_SSA_RANGE(" change range (widening SCC %2d) %2d [%s%ld..%ld%s]\n", scc, var, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
return 1;
}
}
@@ -1780,9 +1789,7 @@ static int zend_ssa_range_narrowing(const zend_op_array *op_array, zend_ssa *ssa
if (zend_inference_calc_range(op_array, ssa, var, 0, 1, &tmp)) {
if (zend_inference_narrowing_meet(&ssa->var_info[var], &tmp)) {
-#ifdef LOG_SSA_RANGE
- fprintf(stderr, " change range (narrowing SCC %2d) %2d [%s%ld..%ld%s]\n", scc, var, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
-#endif
+ LOG_SSA_RANGE(" change range (narrowing SCC %2d) %2d [%s%ld..%ld%s]\n", scc, var, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
return 1;
}
}
@@ -1815,19 +1822,17 @@ static int zend_check_inner_cycles(const zend_op_array *op_array, zend_ssa *ssa,
static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ssa, int *scc_var, int *next_scc_var, int scc)
{
int worklist_len = zend_bitset_len(ssa->vars_count);
- zend_bitset worklist;
- zend_bitset visited;
int j, n;
zend_ssa_range tmp;
+ ALLOCA_FLAG(use_heap);
+ zend_bitset worklist = do_alloca(sizeof(zend_ulong) * worklist_len * 2, use_heap);
+ zend_bitset visited = worklist + worklist_len;
#ifdef NEG_RANGE
int has_inner_cycles = 0;
- ALLOCA_FLAG(use_heap);
- worklist = do_alloca(sizeof(zend_ulong) * worklist_len * 2, use_heap);
- visited = worklist + worklist_len;
memset(worklist, 0, sizeof(zend_ulong) * worklist_len);
memset(visited, 0, sizeof(zend_ulong) * worklist_len);
- j= scc_var[scc];
+ j = scc_var[scc];
while (j >= 0) {
if (!zend_bitset_in(visited, j) &&
zend_check_inner_cycles(op_array, ssa, worklist, visited, j)) {
@@ -1840,7 +1845,7 @@ static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ss
memset(worklist, 0, sizeof(zend_ulong) * worklist_len);
- for (n = 0; n < RANGE_WARMAP_PASSES; n++) {
+ for (n = 0; n < RANGE_WARMUP_PASSES; n++) {
j= scc_var[scc];
while (j >= 0) {
if (ssa->vars[j].scc_entry) {
@@ -1869,9 +1874,7 @@ static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ss
if (tmp.min == ssa->var_info[j].range.min &&
tmp.max == ssa->var_info[j].range.max) {
if (constraint->negative == NEG_INIT) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d INVARIANT\n", j);
-#endif
+ LOG_NEG_RANGE("#%d INVARIANT\n", j);
constraint->negative = NEG_INVARIANT;
}
} else if (tmp.min == ssa->var_info[j].range.min &&
@@ -1879,15 +1882,11 @@ static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ss
tmp.max < constraint->range.min) {
if (constraint->negative == NEG_INIT ||
constraint->negative == NEG_INVARIANT) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d LT\n", j);
-#endif
+ LOG_NEG_RANGE("#%d LT\n", j);
constraint->negative = NEG_USE_LT;
//???NEG
} else if (constraint->negative == NEG_USE_GT) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d UNKNOWN\n", j);
-#endif
+ LOG_NEG_RANGE("#%d UNKNOWN\n", j);
constraint->negative = NEG_UNKNOWN;
}
} else if (tmp.max == ssa->var_info[j].range.max &&
@@ -1895,29 +1894,21 @@ static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ss
tmp.min > constraint->range.max) {
if (constraint->negative == NEG_INIT ||
constraint->negative == NEG_INVARIANT) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d GT\n", j);
-#endif
+ LOG_NEG_RANGE("#%d GT\n", j);
constraint->negative = NEG_USE_GT;
//???NEG
} else if (constraint->negative == NEG_USE_LT) {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d UNKNOWN\n", j);
-#endif
+ LOG_NEG_RANGE("#%d UNKNOWN\n", j);
constraint->negative = NEG_UNKNOWN;
}
} else {
-#ifdef LOG_NEG_RANGE
- fprintf(stderr, "#%d UNKNOWN\n", j);
-#endif
+ LOG_NEG_RANGE("#%d UNKNOWN\n", j);
constraint->negative = NEG_UNKNOWN;
}
}
#endif
if (zend_inference_narrowing_meet(&ssa->var_info[j], &tmp)) {
-#ifdef LOG_SSA_RANGE
- fprintf(stderr, " change range (warmup %d SCC %2d) %2d [%s%ld..%ld%s]\n", n, scc, j, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
-#endif
+ LOG_SSA_RANGE(" change range (warmup %2d SCC %2d) %2d [%s%ld..%ld%s]\n", n, scc, j, (tmp.underflow?"-- ":""), tmp.min, tmp.max, (tmp.overflow?" ++":""));
zend_bitset_incl(visited, j);
FOR_EACH_VAR_USAGE(j, ADD_SCC_VAR_1);
}
@@ -1945,9 +1936,7 @@ static int zend_infer_ranges(const zend_op_array *op_array, zend_ssa *ssa) /* {{
next_scc_var = (int*)(worklist + worklist_len);
scc_var = next_scc_var + ssa->vars_count;
-#ifdef LOG_SSA_RANGE
- fprintf(stderr, "Range Inference\n");
-#endif
+ LOG_SSA_RANGE("Range Inference\n");
/* Create linked lists of SSA variables for each SCC */
memset(scc_var, -1, sizeof(int) * ssa->sccs);
@@ -1977,7 +1966,7 @@ static int zend_infer_ranges(const zend_op_array *op_array, zend_ssa *ssa) /* {{
j = next_scc_var[j];
} while (j >= 0);
-#if RANGE_WARMAP_PASSES > 0
+#if RANGE_WARMUP_PASSES > 0
zend_infer_ranges_warmup(op_array, ssa, scc_var, next_scc_var, scc);
j = scc_var[scc];
do {
View Lorry Controller Status