From b1c3c9a525763ae9cd6e599bf061d7114d48aab0 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Thu, 12 May 2016 21:41:24 +0200 Subject: [PATCH] Explicitly construct phi set during def propagation Previously the phi set was first computed during def propagation and then computed again (per-block) during actual phi placement. This commit changes this to store the phi set computed during def propagation. This makes SSA construction slightly faster (5%), but the main purpose here is to pave the way for the next commit. This also fixes a potential issue with the handling of irreducible loops -- they generated additional phis, but these were not accounted for in def propagation. (Though I'm not sure if we can even have any irreducible loops right now.) --- Zend/zend_bitset.h | 12 ++++ ext/opcache/Optimizer/zend_ssa.c | 104 ++++++++++++++----------------- 2 files changed, 60 insertions(+), 56 deletions(-) diff --git a/Zend/zend_bitset.h b/Zend/zend_bitset.h index fb19b54329..e1a95466b8 100644 --- a/Zend/zend_bitset.h +++ b/Zend/zend_bitset.h @@ -137,6 +137,18 @@ static inline void zend_bitset_union_with_difference(zend_bitset set1, zend_bits } } +static inline zend_bool zend_bitset_subset(zend_bitset set1, zend_bitset set2, uint32_t len) +{ + uint32_t i; + + for (i = 0; i < len; i++) { + if (set1[i] & ~set2[i]) { + return 0; + } + } + return 1; +} + static inline int zend_bitset_first(zend_bitset set, uint32_t len) { uint32_t i; diff --git a/ext/opcache/Optimizer/zend_ssa.c b/ext/opcache/Optimizer/zend_ssa.c index 201317f207..3b5e45b315 100644 --- a/ext/opcache/Optimizer/zend_ssa.c +++ b/ext/opcache/Optimizer/zend_ssa.c @@ -798,7 +798,7 @@ int zend_build_ssa(zend_arena **arena, const zend_op_array *op_array, uint32_t b zend_ssa_block *ssa_blocks; int blocks_count = ssa->cfg.blocks_count; uint32_t set_size; - zend_bitset tmp, def, in; + zend_bitset def, in, phi; int *var = NULL; int i, j, k, changed; zend_dfg dfg; @@ -831,10 +831,13 @@ int zend_build_ssa(zend_arena **arena, const zend_op_array *op_array, uint32_t b zend_dump_dfg(op_array, &ssa->cfg, &dfg); } - tmp = dfg.tmp; def = dfg.def; in = dfg.in; + /* Reuse the "use" set, as we no longer need it */ + phi = dfg.use; + zend_bitset_clear(phi, set_size * blocks_count); + /* Place e-SSA pis. This will add additional "def" points, so it must * happen before def propagation. */ place_essa_pis(arena, op_array, build_flags, ssa, &dfg); @@ -843,20 +846,28 @@ int zend_build_ssa(zend_arena **arena, const zend_op_array *op_array, uint32_t b do { changed = 0; for (j = 0; j < blocks_count; j++) { + zend_bitset def_j = def + j * set_size, phi_j = phi + j * set_size; if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { continue; } - if (blocks[j].predecessors_count > 1 || j == 0) { - zend_bitset_copy(tmp, def + (j * set_size), set_size); - for (k = 0; k < blocks[j].predecessors_count; k++) { - i = ssa->cfg.predecessors[blocks[j].predecessor_offset + k]; - while (i != -1 && i != blocks[j].idom) { - zend_bitset_union_with_intersection(tmp, tmp, def + (i * set_size), in + (j * set_size), set_size); - i = blocks[i].idom; + if (blocks[j].predecessors_count > 1) { + if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) { + /* Prevent any values from flowing into irreducible loops by + replacing all incoming values with explicit phis. The + register allocator depends on this property. */ + zend_bitset_union(phi_j, in + (j * set_size), set_size); + } else { + for (k = 0; k < blocks[j].predecessors_count; k++) { + i = ssa->cfg.predecessors[blocks[j].predecessor_offset + k]; + while (i != -1 && i != blocks[j].idom) { + zend_bitset_union_with_intersection( + phi_j, phi_j, def + (i * set_size), in + (j * set_size), set_size); + i = blocks[i].idom; + } } } - if (!zend_bitset_equal(def + (j * set_size), tmp, set_size)) { - zend_bitset_copy(def + (j * set_size), tmp, set_size); + if (!zend_bitset_subset(phi_j, def_j, set_size)) { + zend_bitset_union(def_j, phi_j, set_size); changed = 1; } } @@ -869,58 +880,39 @@ int zend_build_ssa(zend_arena **arena, const zend_op_array *op_array, uint32_t b free_alloca(dfg.tmp, dfg_use_heap); return FAILURE; } - zend_bitset_clear(tmp, set_size); for (j = 0; j < blocks_count; j++) { if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { continue; } - if (blocks[j].predecessors_count > 1) { - zend_bitset_clear(tmp, set_size); - if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) { - /* Prevent any values from flowing into irreducible loops by - replacing all incoming values with explicit phis. The - register allocator depends on this property. */ - zend_bitset_copy(tmp, in + (j * set_size), set_size); - } else { - for (k = 0; k < blocks[j].predecessors_count; k++) { - i = ssa->cfg.predecessors[blocks[j].predecessor_offset + k]; - while (i != -1 && i != blocks[j].idom) { - zend_bitset_union_with_intersection(tmp, tmp, def + (i * set_size), in + (j * set_size), set_size); - i = blocks[i].idom; - } - } - } - - if (!zend_bitset_empty(tmp, set_size)) { - ZEND_BITSET_REVERSE_FOREACH(tmp, set_size, i) { - zend_ssa_phi *phi = zend_arena_calloc(arena, 1, - sizeof(zend_ssa_phi) + - sizeof(int) * blocks[j].predecessors_count + - sizeof(void*) * blocks[j].predecessors_count); - - phi->sources = (int*)(((char*)phi) + sizeof(zend_ssa_phi)); - memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count); - phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + sizeof(int) * ssa->cfg.blocks[j].predecessors_count); - - phi->pi = -1; - phi->var = i; - phi->ssa_var = -1; - - /* Place phis after pis */ - { - zend_ssa_phi **pp = &ssa_blocks[j].phis; - while (*pp) { - if ((*pp)->pi < 0) { - break; - } - pp = &(*pp)->next; + if (!zend_bitset_empty(phi + j * set_size, set_size)) { + ZEND_BITSET_REVERSE_FOREACH(phi + j * set_size, set_size, i) { + zend_ssa_phi *phi = zend_arena_calloc(arena, 1, + sizeof(zend_ssa_phi) + + sizeof(int) * blocks[j].predecessors_count + + sizeof(void*) * blocks[j].predecessors_count); + + phi->sources = (int*)(((char*)phi) + sizeof(zend_ssa_phi)); + memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count); + phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + sizeof(int) * ssa->cfg.blocks[j].predecessors_count); + + phi->pi = -1; + phi->var = i; + phi->ssa_var = -1; + + /* Place phis after pis */ + { + zend_ssa_phi **pp = &ssa_blocks[j].phis; + while (*pp) { + if ((*pp)->pi < 0) { + break; } - phi->next = *pp; - *pp = phi; + pp = &(*pp)->next; } - } ZEND_BITSET_FOREACH_END(); - } + phi->next = *pp; + *pp = phi; + } + } ZEND_BITSET_FOREACH_END(); } } -- 2.40.0