From 721be3e0c13bc73b98b89ddd15620f236432e14e Mon Sep 17 00:00:00 2001
From: Nikita Popov <nikic@php.net>
Date: Tue, 2 Feb 2016 17:12:16 +0100
Subject: [PATCH] Make pi placement independent of phi placement

This interdependence is problematic because we can't propagate pi
def points in the initial dominance frontier propagation. The used
rule for multiple-predecessor blocks may also miss cases where
placing the pi would have been useful.

The new heuristic for pi placement checks that a) the variable is
live-in and b) for the "from" block that generated the pi, the
other successor does not dominate all other predecessors of the
"to" block.

The purpose of case b) may be illustrated with an example:

    if (is_int($i)) {
        // place pi here
    }
    // but don't place pi here

The reason we do not want to place the second pi is that we generally
place pis in positive+negative pairs, and in this case the pair
would merge in a phi and cancel out, so we get no useful information
out of it.
---
 ext/opcache/Optimizer/zend_ssa.c | 50 +++++++++++++++++++++++++-------
 1 file changed, 39 insertions(+), 11 deletions(-)

diff --git a/ext/opcache/Optimizer/zend_ssa.c b/ext/opcache/Optimizer/zend_ssa.c
index 9a865efdeb..c158f7a731 100644
--- a/ext/opcache/Optimizer/zend_ssa.c
+++ b/ext/opcache/Optimizer/zend_ssa.c
@@ -23,19 +23,47 @@
 #include "zend_dump.h"
 #include "zend_inference.h"
 
-static int needs_pi(const zend_op_array *op_array, zend_dfg *dfg, zend_ssa *ssa, int from, int to, int var) /* {{{ */
-{
-	if (from == to || ssa->cfg.blocks[to].predecessors_count != 1) {
-		zend_ssa_phi *p = ssa->blocks[to].phis;
-		while (p) {
-			if (p->pi < 0 && p->var == var) {
-				return 1;
-			}
-			p = p->next;
+static zend_bool dominates(const zend_basic_block *blocks, int a, int b) {
+	while (blocks[b].level > blocks[a].level) {
+		b = blocks[b].idom;
+	}
+	return a == b;
+}
+
+static zend_bool dominates_other_predecessors(
+		const zend_cfg *cfg, const zend_basic_block *block, int check, int exclude) {
+	int i;
+	for (i = 0; i < block->predecessors_count; i++) {
+		int predecessor = cfg->predecessors[block->predecessor_offset + i];
+		if (predecessor != exclude && !dominates(cfg->blocks, check, predecessor)) {
+			return 0;
 		}
+	}
+	return 1;
+}
+
+static zend_bool needs_pi(const zend_op_array *op_array, zend_dfg *dfg, zend_ssa *ssa, int from, int to, int var) /* {{{ */
+{
+	zend_basic_block *from_block, *to_block;
+	int other_successor;
+
+	if (!DFG_ISSET(dfg->in, dfg->size, to, var)) {
+		/* Variable is not live, certainly won't benefit from pi */
 		return 0;
 	}
-	return DFG_ISSET(dfg->in, dfg->size, to, var);
+
+	to_block = &ssa->cfg.blocks[to];
+	if (to_block->predecessors_count == 1) {
+		/* Always place pi if one predecessor (an if branch) */
+		return 1;
+	}
+
+	/* Check that the other successor of the from block does not dominate all other predecessors.
+	 * If it does, we'd probably end up annihilating a positive+negative pi assertion. */
+	from_block = &ssa->cfg.blocks[from];
+	other_successor = from_block->successors[0] == to
+		? from_block->successors[1] : from_block->successors[0];
+	return !dominates_other_predecessors(&ssa->cfg, to_block, other_successor, from);
 }
 /* }}} */
 
@@ -917,7 +945,7 @@ int zend_build_ssa(zend_arena **arena, const zend_op_array *op_array, uint32_t b
 				ZEND_BITSET_REVERSE_FOREACH(tmp, set_size, i) {
 					zend_ssa_phi **pp = &ssa_blocks[j].phis;
 					while (*pp) {
-						if ((*pp)->pi <= 0 && (*pp)->var == i) {
+						if ((*pp)->pi < 0 && (*pp)->var == i) {
 							break;
 						}
 						pp = &(*pp)->next;
-- 
2.50.1