Merge branch 'PHP-7.1'

2 files changed, 76 insertions, 67 deletions

diff --git a/ext/opcache/Optimizer/zend_cfg.c b/ext/opcache/Optimizer/zend_cfg.c
index 55e30545ef..c9d951b403 100644
--- a/ext/opcache/Optimizer/zend_cfg.c
+++ b/ext/opcache/Optimizer/zend_cfg.c
@@ -749,31 +749,51 @@ static int dominates(zend_basic_block *blocks, int a, int b) /* {{{ */
 }
 /* }}} */
 
+typedef struct {
+	int id;
+	int level;
+} block_info;
+static int compare_block_level(const block_info *a, const block_info *b) {
+	return b->level - a->level;
+}
+static void swap_blocks(block_info *a, block_info *b) {
+	block_info tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
 int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg, uint32_t *flags) /* {{{ */
 {
-	int i, j, k;
-	int depth;
+	int i, j, k, n;
+	int depth, time;
 	zend_basic_block *blocks = cfg->blocks;
-	int *dj_spanning_tree;
+	int *entry_times, *exit_times;
 	zend_worklist work;
 	int flag = ZEND_FUNC_NO_LOOPS;
+	block_info *sorted_blocks;
 	ALLOCA_FLAG(list_use_heap)
 	ALLOCA_FLAG(tree_use_heap)
+	ALLOCA_FLAG(sorted_blocks_use_heap)
 
 	ZEND_WORKLIST_ALLOCA(&work, cfg->blocks_count, list_use_heap);
-	dj_spanning_tree = do_alloca(sizeof(int) * cfg->blocks_count, tree_use_heap);
 
-	for (i = 0; i < cfg->blocks_count; i++) {
-		dj_spanning_tree[i] = -1;
-	}
+	/* We don't materialize the DJ spanning tree explicitly, as we are only interested in ancestor
+	 * querties. These are implemented by checking entry/exit times of the DFS search. */
+	entry_times = do_alloca(2 * sizeof(int) * cfg->blocks_count, tree_use_heap);
+	exit_times = entry_times + cfg->blocks_count;
+	memset(entry_times, -1, 2 * sizeof(int) * cfg->blocks_count);
+
 	zend_worklist_push(&work, 0);
+	time = 0;
 	while (zend_worklist_len(&work)) {
 	next:
 		i = zend_worklist_peek(&work);
+		if (entry_times[i] == -1) {
+			entry_times[i] = time++;
+		}
 		/* Visit blocks immediately dominated by i. */
 		for (j = blocks[i].children; j >= 0; j = blocks[j].next_child) {
 			if (zend_worklist_push(&work, j)) {
-				dj_spanning_tree[j] = i;
 				goto next;
 			}
 		}
@@ -785,72 +805,67 @@ int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg, uint32
 			} else if (blocks[succ].idom == i) {
 				continue;
 			} else if (zend_worklist_push(&work, succ)) {
-				dj_spanning_tree[succ] = i;
 				goto next;
 			}
 		}
+		exit_times[i] = time++;
 		zend_worklist_pop(&work);
 	}
 
+	/* Sort blocks by decreasing level, which is the order in which we want to process them */
+	sorted_blocks = do_alloca(sizeof(block_info) * cfg->blocks_count, sorted_blocks_use_heap);
+	for (i = 0; i < cfg->blocks_count; i++) {
+		sorted_blocks[i].id = i;
+		sorted_blocks[i].level = blocks[i].level;
+	}
+	zend_sort(sorted_blocks, cfg->blocks_count, sizeof(block_info),
+		(compare_func_t) compare_block_level, (swap_func_t) swap_blocks);
+
 	/* Identify loops.  See Sreedhar et al, "Identifying Loops Using DJ
 	   Graphs".  */
 
-	for (i = 0, depth = 0; i < cfg->blocks_count; i++) {
-		if (blocks[i].level > depth) {
-			depth = blocks[i].level;
-		}
-	}
-	for (; depth >= 0; depth--) {
-		for (i = 0; i < cfg->blocks_count; i++) {
-			if (blocks[i].level != depth) {
+	for (n = 0; n < cfg->blocks_count; n++) {
+		i = sorted_blocks[n].id;
+
+		zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count));
+		for (j = 0; j < blocks[i].predecessors_count; j++) {
+			int pred = cfg->predecessors[blocks[i].predecessor_offset + j];
+
+			/* A join edge is one for which the predecessor does not
+			   immediately dominate the successor.  */
+			if (blocks[i].idom == pred) {
 				continue;
 			}
-			zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count));
-			for (j = 0; j < blocks[i].predecessors_count; j++) {
-				int pred = cfg->predecessors[blocks[i].predecessor_offset + j];
-
-				/* A join edge is one for which the predecessor does not
-				   immediately dominate the successor.  */
-				if (blocks[i].idom == pred) {
-					continue;
-				}
 
-				/* In a loop back-edge (back-join edge), the successor dominates
-				   the predecessor.  */
-				if (dominates(blocks, i, pred)) {
-					blocks[i].flags |= ZEND_BB_LOOP_HEADER;
+			/* In a loop back-edge (back-join edge), the successor dominates
+			   the predecessor.  */
+			if (dominates(blocks, i, pred)) {
+				blocks[i].flags |= ZEND_BB_LOOP_HEADER;
+				flag &= ~ZEND_FUNC_NO_LOOPS;
+				zend_worklist_push(&work, pred);
+			} else {
+				/* Otherwise it's a cross-join edge.  See if it's a branch
+				   to an ancestor on the DJ spanning tree.  */
+				if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) {
+					blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP;
+					flag |= ZEND_FUNC_IRREDUCIBLE;
 					flag &= ~ZEND_FUNC_NO_LOOPS;
-					zend_worklist_push(&work, pred);
-				} else {
-					/* Otherwise it's a cross-join edge.  See if it's a branch
-					   to an ancestor on the dominator spanning tree.  */
-					int dj_parent = pred;
-					while (dj_parent >= 0) {
-						if (dj_parent == i) {
-							/* An sp-back edge: mark as irreducible.  */
-							blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP;
-							flag |= ZEND_FUNC_IRREDUCIBLE;
-							flag &= ~ZEND_FUNC_NO_LOOPS;
-							break;
-						} else {
-							dj_parent = dj_spanning_tree[dj_parent];
-						}
-					}
 				}
 			}
-			while (zend_worklist_len(&work)) {
-				j = zend_worklist_pop(&work);
-				if (blocks[j].loop_header < 0 && j != i) {
-					blocks[j].loop_header = i;
-					for (k = 0; k < blocks[j].predecessors_count; k++) {
-						zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]);
-					}
+		}
+		while (zend_worklist_len(&work)) {
+			j = zend_worklist_pop(&work);
+			if (blocks[j].loop_header < 0 && j != i) {
+				blocks[j].loop_header = i;
+				for (k = 0; k < blocks[j].predecessors_count; k++) {
+					zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]);
 				}
 			}
 		}
 	}
 
-	free_alloca(dj_spanning_tree, tree_use_heap);
+	free_alloca(sorted_blocks, sorted_blocks_use_heap);
+	free_alloca(entry_times, tree_use_heap);
 	ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap);
 	*flags |= flag;
 
diff --git a/ext/opcache/Optimizer/zend_inference.c b/ext/opcache/Optimizer/zend_inference.c
index d0f1ce43ca..a5c2313e3c 100644
--- a/ext/opcache/Optimizer/zend_inference.c
+++ b/ext/opcache/Optimizer/zend_inference.c
@@ -269,8 +269,7 @@ int zend_ssa_find_false_dependencies(const zend_op_array *op_array, zend_ssa *ss
 		}
 	}
 
-	while (!zend_bitset_empty(worklist, zend_bitset_len(ssa_vars_count))) {
-		i = zend_bitset_first(worklist, zend_bitset_len(ssa_vars_count));
+	while ((i = zend_bitset_first(worklist, zend_bitset_len(ssa_vars_count))) >= 0) {
 		zend_bitset_excl(worklist, i);
 		if (ssa_vars[i].definition_phi) {
 			/* mark all possible sources as used */
@@ -1568,8 +1567,7 @@ static void zend_infer_ranges_warmup(const zend_op_array *op_array, zend_ssa *ss
 
 		memset(visited, 0, sizeof(zend_ulong) * worklist_len);
 
-		while (!zend_bitset_empty(worklist, worklist_len)) {
-			j = zend_bitset_first(worklist, worklist_len);
+		while ((j = zend_bitset_first(worklist, worklist_len)) >= 0) {
 			zend_bitset_excl(worklist, j);
 			if (zend_inference_calc_range(op_array, ssa, j, 0, 0, &tmp)) {
 #ifdef NEG_RANGE
@@ -1688,8 +1686,7 @@ static int zend_infer_ranges(const zend_op_array *op_array, zend_ssa *ssa) /* {{
 #endif
 
 			/* widening */
-			while (!zend_bitset_empty(worklist, worklist_len)) {
-				j = zend_bitset_first(worklist, worklist_len);
+			while ((j = zend_bitset_first(worklist, worklist_len)) >= 0) {
 				zend_bitset_excl(worklist, j);
 				if (zend_ssa_range_widening(op_array, ssa, j, scc)) {
 					FOR_EACH_VAR_USAGE(j, ADD_SCC_VAR);
@@ -1705,8 +1702,7 @@ static int zend_infer_ranges(const zend_op_array *op_array, zend_ssa *ssa) /* {{
 			}
 
 			/* narrowing */
-			while (!zend_bitset_empty(worklist, worklist_len)) {
-				j = zend_bitset_first(worklist, worklist_len);
+			while ((j = zend_bitset_first(worklist, worklist_len)) >= 0) {
 				zend_bitset_excl(worklist, j);
 				if (zend_ssa_range_narrowing(op_array, ssa, j, scc)) {
 					FOR_EACH_VAR_USAGE(j, ADD_SCC_VAR);
@@ -3270,8 +3266,7 @@ int zend_infer_types_ex(const zend_op_array *op_array, const zend_script *script
 	int i, j;
 	uint32_t tmp;
 
-	while (!zend_bitset_empty(worklist, zend_bitset_len(ssa_vars_count))) {
-		j = zend_bitset_first(worklist, zend_bitset_len(ssa_vars_count));
+	while ((j = zend_bitset_first(worklist, zend_bitset_len(ssa_vars_count))) >= 0) {
 		zend_bitset_excl(worklist, j);
 		if (ssa_vars[j].definition_phi) {
 			zend_ssa_phi *p = ssa_vars[j].definition_phi;
@@ -3884,7 +3879,7 @@ void zend_inference_check_recursive_dependencies(zend_op_array *op_array)
 	zend_func_info *info = ZEND_FUNC_INFO(op_array);
 	zend_call_info *call_info;
 	zend_bitset worklist;
-	int worklist_len;
+	int worklist_len, i;
 	ALLOCA_FLAG(use_heap);
 
 	if (!info->ssa.var_info || !(info->flags & ZEND_FUNC_RECURSIVE)) {
@@ -3901,8 +3896,7 @@ void zend_inference_check_recursive_dependencies(zend_op_array *op_array)
 		}
 		call_info = call_info->next_callee;
 	}
-	while (!zend_bitset_empty(worklist, worklist_len)) {
-		int i = zend_bitset_first(worklist, worklist_len);
+	while ((i = zend_bitset_first(worklist, worklist_len)) >= 0) {
 		zend_bitset_excl(worklist, i);
 		if (!info->ssa.var_info[i].recursive) {
 			info->ssa.var_info[i].recursive = 1;