com php-src: Optimize DJ spanning tree back-edge check: ext/opcache/Optimizer/zend_cfg.c
| From: | Nikita Popov | Date: | Thu, 16 Mar 2017 16:26:20 +0000 |
| Subject: | com php-src: Optimize DJ spanning tree back-edge check: ext/opcache/Optimizer/zend_cfg.c | ||
| Groups: | php.cvs | ||
| Request: | Send a blank email to php-cvs+get-97334@lists.php.net to get a copy of this message | ||
Commit: f1f68b60f5e6f75002560b44211f3449b25f918d
Author: Nikita Popov <nikita.ppv@gmail.com> Thu, 16 Mar 2017 17:02:11 +0100
Parents: 6633e8492e6195c4085b04c65fb18addd0ac33a6
Branches: PHP-7.1 master
Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=f1f68b60f5e6f75002560b44211f3449b25f918d
Log:
Optimize DJ spanning tree back-edge check
Instead of walking the DJ spanning tree upwards, record entry and
exit times during the DFS and use these to determine whether CJ
edges are sp-back edges.
Changed paths:
M ext/opcache/Optimizer/zend_cfg.c
Diff:
diff --git a/ext/opcache/Optimizer/zend_cfg.c b/ext/opcache/Optimizer/zend_cfg.c
index ad0c118..c9d951b 100644
--- a/ext/opcache/Optimizer/zend_cfg.c
+++ b/ext/opcache/Optimizer/zend_cfg.c
@@ -765,9 +765,9 @@ static void swap_blocks(block_info *a, block_info *b) {
int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg, uint32_t *flags) /* {{{
*/
{
int i, j, k, n;
- int depth;
+ 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;
@@ -776,19 +776,24 @@ int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg,
uint32
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;
}
}
@@ -800,10 +805,10 @@ 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);
}
@@ -840,18 +845,11 @@ int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg,
uint32
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];
- }
+ 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;
}
}
}
@@ -867,7 +865,7 @@ int zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg, uint32
}
free_alloca(sorted_blocks, sorted_blocks_use_heap);
- free_alloca(dj_spanning_tree, tree_use_heap);
+ free_alloca(entry_times, tree_use_heap);
ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap);
*flags |= flag;