Explicitly sort live ranges by start opnum

Instead of moving live ranges around to maintain the start opnum
invariant, add an explicit sorting step in pass two.

2 files changed, 18 insertions, 46 deletions

diff --git a/Zend/zend_compile.c b/Zend/zend_compile.c
index 1190cef1b4..9ce33737af 100644
--- a/Zend/zend_compile.c
+++ b/Zend/zend_compile.c
@@ -605,50 +605,6 @@ static uint32_t zend_start_live_range(zend_op_array *op_array, uint32_t start) /
 }
 /* }}} */
 
-static uint32_t zend_start_live_range_ex(zend_op_array *op_array, uint32_t start) /* {{{ */
-{
-	if (op_array->last_live_range == 0 ||
-	    op_array->live_range[op_array->last_live_range - 1].start <= start) {
-		return zend_start_live_range(op_array, start);
-	} else {
-		/* Live ranges have to be sorted by "start" field */
-		uint32_t n = op_array->last_live_range;
-
-		/* move early ranges to make a room */
-		op_array->last_live_range = n + 1;
-		op_array->live_range = erealloc(op_array->live_range, sizeof(zend_live_range) * op_array->last_live_range);
-		do {
-			op_array->live_range[n] = op_array->live_range[n-1];
-			n--;
-		} while (n != 0 && op_array->live_range[n-1].start > start);
-
-	    /* initialize new range */
-		op_array->live_range[n].start = start;
-
-		/* update referens to live-ranges from stack */
-		if (!zend_stack_is_empty(&CG(loop_var_stack))) {
-			zend_loop_var *loop_var = zend_stack_top(&CG(loop_var_stack));
-			zend_loop_var *base = zend_stack_base(&CG(loop_var_stack));
-
-			for (; loop_var >= base; loop_var--) {
-				if (loop_var->opcode == ZEND_RETURN) {
-					/* Stack separator */
-					break;
-				} else if (loop_var->opcode == ZEND_FREE ||
-			           loop_var->opcode == ZEND_FE_FREE) {
-					if (loop_var->u.live_range_offset >= n) {
-						loop_var->u.live_range_offset++;
-					} else {
-						break;
-					}
-				}
-			}
-		}
-		return n;
-	}
-}
-/* }}} */
-
 static void zend_end_live_range(zend_op_array *op_array, uint32_t offset, uint32_t end, uint32_t kind, uint32_t var) /* {{{ */
 {
 	zend_live_range *range = op_array->live_range + offset;
@@ -2041,7 +1997,7 @@ static void zend_find_live_range(zend_op *opline, zend_uchar type, uint32_t var)
 			}
 
 	        zend_end_live_range(CG(active_op_array),
-				zend_start_live_range_ex(CG(active_op_array),
+				zend_start_live_range(CG(active_op_array),
 					def + 1 - CG(active_op_array)->opcodes),
 				opline - CG(active_op_array)->opcodes,
 				ZEND_LIVE_TMPVAR, var);
@@ -7944,7 +7900,7 @@ static void zend_compile_encaps_list(znode *result, zend_ast *ast) /* {{{ */
 		GET_NODE(result, opline->result);
 	} else {
 		uint32_t var;
-		uint32_t range = zend_start_live_range_ex(CG(active_op_array), rope_init_lineno);
+		uint32_t range = zend_start_live_range(CG(active_op_array), rope_init_lineno);
 
 		init_opline->extended_value = j;
 		opline->opcode = ZEND_ROPE_END;
diff --git a/Zend/zend_opcode.c b/Zend/zend_opcode.c
index 48f1e4785c..11194bc51c 100644
--- a/Zend/zend_opcode.c
+++ b/Zend/zend_opcode.c
@@ -27,6 +27,7 @@
 #include "zend_compile.h"
 #include "zend_extensions.h"
 #include "zend_API.h"
+#include "zend_sort.h"
 
 #include "zend_vm.h"
 
@@ -553,6 +554,20 @@ static uint32_t zend_get_brk_cont_target(const zend_op_array *op_array, const ze
 	return opline->opcode == ZEND_BRK ? jmp_to->brk : jmp_to->cont;
 }
 
+/* Live ranges must be sorted by increasing start opline */
+static int cmp_live_range(const zend_live_range *a, const zend_live_range *b) {
+	return a->start - b->start;
+}
+static void swap_live_range(zend_live_range *a, zend_live_range *b) {
+	zend_live_range tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+static void zend_sort_live_ranges(zend_op_array *op_array) {
+	zend_sort(op_array->live_range, op_array->last_live_range, sizeof(zend_live_range),
+			(compare_func_t) cmp_live_range, (swap_func_t) swap_live_range);
+}
+
 ZEND_API int pass_two(zend_op_array *op_array)
 {
 	zend_op *opline, *end;
@@ -707,6 +722,7 @@ ZEND_API int pass_two(zend_op_array *op_array)
 	if (op_array->live_range) {
 		int i;
 
+		zend_sort_live_ranges(op_array);
 		for (i = 0; i < op_array->last_live_range; i++) {
 			op_array->live_range[i].var =
 				(uint32_t)(zend_intptr_t)ZEND_CALL_VAR_NUM(NULL, op_array->last_var + (op_array->live_range[i].var / sizeof(zval))) |