Mesa (master): i965/fs_live_variables: Do liveness analysis bottom-to-top
Jason Ekstrand
jekstrand at kemper.freedesktop.org
Wed Jun 24 20:12:24 UTC 2015
Module: Mesa
Branch: master
Commit: b2c6ba0c4b21391dc35018e1c8c4f7f7d8952bea
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=b2c6ba0c4b21391dc35018e1c8c4f7f7d8952bea
Author: Jason Ekstrand <jason.ekstrand at intel.com>
Date: Mon Jun 8 16:03:19 2015 -0700
i965/fs_live_variables: Do liveness analysis bottom-to-top
>From Muchnick's Advanced Compiler Design and Implementation:
"To determine which variables are live at each point in a flowgraph, we
perform a backward data-flow analysis"
Previously, we were walking the blocks forwards and updating the livein and
then the liveout. However, the livein calculation depends on the liveout
and the liveout depends on the successor blocks. The net result is that it
takes one full iteration to go from liveout to livein and then another
full iteration to propagate to the predecessors. This works out to an
O(n^2) computation where n is the number of blocks. If we run things in
the other order, it's O(nl) where l is the maximum loop depth which is
practically bounded by 3.
On my HSW desktop, one particular shadertoy test gets a 20% improvement in
compile times:
N Min Max Median Avg Stddev
x 10 15.965 16.884 16.026 16.1822 0.34736846
+ 10 12.813 13.052 12.876 12.8891 0.06913666
Difference at 95.0% confidence
-3.2931 +/- 0.235316
-20.3501% +/- 1.45417%
(Student's t, pooled s = 0.250444)
Reviewed-by: Matt Turner <mattst88 at gmail.com>
---
.../drivers/dri/i965/brw_fs_live_variables.cpp | 38 ++++++++++----------
1 file changed, 19 insertions(+), 19 deletions(-)
diff --git a/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
index 502161d..19aec92 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
@@ -204,27 +204,9 @@ fs_live_variables::compute_live_variables()
while (cont) {
cont = false;
- foreach_block (block, cfg) {
+ foreach_block_reverse (block, cfg) {
struct block_data *bd = &block_data[block->num];
- /* Update livein */
- for (int i = 0; i < bitset_words; i++) {
- BITSET_WORD new_livein = (bd->use[i] |
- (bd->liveout[i] &
- ~bd->def[i]));
- if (new_livein & ~bd->livein[i]) {
- bd->livein[i] |= new_livein;
- cont = true;
- }
- }
- BITSET_WORD new_livein = (bd->flag_use[0] |
- (bd->flag_liveout[0] &
- ~bd->flag_def[0]));
- if (new_livein & ~bd->flag_livein[0]) {
- bd->flag_livein[0] |= new_livein;
- cont = true;
- }
-
/* Update liveout */
foreach_list_typed(bblock_link, child_link, link, &block->children) {
struct block_data *child_bd = &block_data[child_link->block->num];
@@ -244,6 +226,24 @@ fs_live_variables::compute_live_variables()
cont = true;
}
}
+
+ /* Update livein */
+ for (int i = 0; i < bitset_words; i++) {
+ BITSET_WORD new_livein = (bd->use[i] |
+ (bd->liveout[i] &
+ ~bd->def[i]));
+ if (new_livein & ~bd->livein[i]) {
+ bd->livein[i] |= new_livein;
+ cont = true;
+ }
+ }
+ BITSET_WORD new_livein = (bd->flag_use[0] |
+ (bd->flag_liveout[0] &
+ ~bd->flag_def[0]));
+ if (new_livein & ~bd->flag_livein[0]) {
+ bd->flag_livein[0] |= new_livein;
+ cont = true;
+ }
}
}
}
More information about the mesa-commit
mailing list