Re: com php-src: Use worklist for DFG construction: ext/opcache/Optimizer/zend_dfg.c
| From: | Dmitry Stogov | Date: | Tue, 12 Jan 2016 08:07:34 +0000 |
| Subject: | Re: com php-src: Use worklist for DFG construction: ext/opcache/Optimizer/zend_dfg.c | ||
| References: | 1 | Groups: | php.cvs |
| Request: | Send a blank email to php-cvs+get-90608@lists.php.net to get a copy of this message | ||
Hi Nikita,
Cool and obvious improvement.
I noticed that DFG calculation slowness and thought about switching to minimal-SSA instead of
pruned.
Now it's not necessary anymore.
Did you get the idea yourself or read somewhere?
Thanks. Dmitry.
________________________________________
From: Nikita Popov <nikic@php.net>
Sent: Monday, January 11, 2016 23:53
To: php-cvs@lists.php.net
Subject: [PHP-CVS] com php-src: Use worklist for DFG construction: ext/opcache/Optimizer/zend_dfg.c
Commit: c817ac4d521ee46dd20dab3dc23259039d7e1a15
Author: Nikita Popov <nikic@php.net> Sat, 9 Jan 2016 13:28:16 +0100
Parents: 765c5ca745220fa996aea6b2c41cdaef0934a449
Branches: master
Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=c817ac4d521ee46dd20dab3dc23259039d7e1a15
Log:
Use worklist for DFG construction
About 40x faster.
Changed paths:
M ext/opcache/Optimizer/zend_dfg.c
Diff:
diff --git a/ext/opcache/Optimizer/zend_dfg.c b/ext/opcache/Optimizer/zend_dfg.c
index 1266ae5..65c19b2 100644
--- a/ext/opcache/Optimizer/zend_dfg.c
+++ b/ext/opcache/Optimizer/zend_dfg.c
@@ -28,7 +28,7 @@ int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg
zend_bitset tmp, gen, def, use, in, out;
zend_op *opline;
uint32_t k;
- int j, changed;
+ int j;
/* FIXME: can we use "gen" instead of "def" for flow analyzing? */
set_size = dfg->size;
@@ -205,9 +205,20 @@ int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg
}
/* Calculate "in" and "out" sets */
- do {
- changed = 0;
+ {
+ uint32_t worklist_len = zend_bitset_len(blocks_count);
+ ALLOCA_FLAG(use_heap);
+ zend_bitset worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap);
+ memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE);
for (j = 0; j < blocks_count; j++) {
+ zend_bitset_incl(worklist, j);
+ }
+ while (!zend_bitset_empty(worklist, worklist_len)) {
+ /* We use the last block on the worklist, because predecessors tend to be
located
+ * before the succeeding block, so this converges faster. */
+ j = zend_bitset_last(worklist, worklist_len);
+ zend_bitset_excl(worklist, j);
+
if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
continue;
}
@@ -222,10 +233,19 @@ int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg,
zend_dfg
zend_bitset_union_with_difference(tmp, DFG_BITSET(use, set_size, j),
DFG_BITSET(out, set_size, j), DFG_BITSET(def, set_size, j), set_size);
if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) {
zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size);
- changed = 1;
+
+ /* Add predecessors of changed block to worklist */
+ {
+ int *predecessors =
&cfg->predecessors[blocks[j].predecessor_offset];
+ for (k = 0; k < blocks[j].predecessors_count; k++) {
+ zend_bitset_incl(worklist, predecessors[k]);
+ }
+ }
}
}
- } while (changed);
+
+ free_alloca(worklist, use_heap);
+ }
return SUCCESS;
}
--
PHP CVS Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php