<div dir="ltr">On 29 October 2013 00:28, Eric Anholt <span dir="ltr"><<a href="mailto:eric@anholt.net" target="_blank">eric@anholt.net</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">Paul Berry <<a href="mailto:stereotype441@gmail.com">stereotype441@gmail.com</a>> writes:<br>
<br>
> On 21 October 2013 11:20, Eric Anholt <<a href="mailto:eric@anholt.net">eric@anholt.net</a>> wrote:<br>
><br>
>> Orbital Explorer was generating a 4000 instruction geometry shader, which<br>
>> was taking 275 trips through dead code elimination and register<br>
>> coalescing, each of which updated live variables to get its work done, and<br>
>> invalidated those live variables afterwards.<br>
>><br>
>> By using bitfields instead of bools (reducing the working set size by a<br>
>> factor of 8) in live variables analysis, it drops from 88% of the profile<br>
>> to 57%, and reduces overall runtime from I-got-bored-and-killed-it (Paul<br>
>> says 3+ minutes) to 10.5 seconds.<br>
>><br>
>> Compare to f179f419d1d0a03fad36c2b0a58e8b853bae6118 on the FS side.<br>
>> ---<br>
>> .../drivers/dri/i965/brw_vec4_live_variables.cpp | 41<br>
>> ++++++++++++----------<br>
>> .../drivers/dri/i965/brw_vec4_live_variables.h | 10 +++---<br>
>> 2 files changed, 28 insertions(+), 23 deletions(-)<br>
>><br>
>> diff --git a/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp<br>
>> b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp<br>
>> index db3787b..f6675c8 100644<br>
>> --- a/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp<br>
>> +++ b/src/mesa/drivers/dri/i965/brw_vec4_live_variables.cpp<br>
>> @@ -83,8 +83,8 @@ vec4_live_variables::setup_def_use()<br>
>><br>
>> for (int j = 0; j < 4; j++) {<br>
>> int c = BRW_GET_SWZ(inst->src[i].swizzle, j);<br>
>> - if (!bd[b].def[reg * 4 + c])<br>
>> - bd[b].use[reg * 4 + c] = true;<br>
>> + if (!BITSET_TEST(bd[b].def, reg * 4 + c))<br>
>> + BITSET_SET(bd[b].use, reg * 4 + c);<br>
>> }<br>
>> }<br>
>> }<br>
>> @@ -99,8 +99,8 @@ vec4_live_variables::setup_def_use()<br>
>> for (int c = 0; c < 4; c++) {<br>
>> if (inst->dst.writemask & (1 << c)) {<br>
>> int reg = inst->dst.reg;<br>
>> - if (!bd[b].use[reg * 4 + c])<br>
>> - bd[b].def[reg * 4 + c] = true;<br>
>> + if (!BITSET_TEST(bd[b].use, reg * 4 + c))<br>
>> + BITSET_SET(bd[b].def, reg * 4 + c);<br>
>> }<br>
>> }<br>
>> }<br>
>> @@ -126,12 +126,12 @@ vec4_live_variables::compute_live_variables()<br>
>><br>
>> for (int b = 0; b < cfg->num_blocks; b++) {<br>
>> /* Update livein */<br>
>> - for (int i = 0; i < num_vars; i++) {<br>
>> - if (bd[b].use[i] || (bd[b].liveout[i] && !bd[b].def[i])) {<br>
>> - if (!bd[b].livein[i]) {<br>
>> - bd[b].livein[i] = true;<br>
>> - cont = true;<br>
>> - }<br>
>> + for (int i = 0; i < bitset_words; i++) {<br>
>> + BITSET_WORD new_livein = (bd[b].use[i] |<br>
>> + (bd[b].liveout[i] & ~bd[b].def[i]));<br>
>> + if (new_livein & ~bd[b].livein[i]) {<br>
>> + bd[b].livein[i] |= new_livein;<br>
>> + cont = true;<br>
>><br>
><br>
> Personally, I think this would be slightly clearer as:<br>
><br>
> BITSET_WORD new_livein = bd[b].livein[i] | bd[b].use[i] | (bd[b].liveout[i]<br>
> & ~bd[b].def[i]);<br>
> if (new_livein != bd[b].livein[i]) {<br>
> bd[b].livein[i] = new_livein;<br>
> cont = true;<br>
> }<br>
><br>
><br>
>> }<br>
>> }<br>
>><br>
>> @@ -140,9 +140,11 @@ vec4_live_variables::compute_live_variables()<br>
>> bblock_link *link = (bblock_link *)block_node;<br>
>> bblock_t *block = link->block;<br>
>><br>
>> - for (int i = 0; i < num_vars; i++) {<br>
>> - if (bd[block->block_num].livein[i] && !bd[b].liveout[i]) {<br>
>> - bd[b].liveout[i] = true;<br>
>> + for (int i = 0; i < bitset_words; i++) {<br>
>> + BITSET_WORD new_liveout = (bd[block->block_num].livein[i] &<br>
>> + ~bd[b].liveout[i]);<br>
>> + if (new_liveout) {<br>
>> + bd[b].liveout[i] |= new_liveout;<br>
>> cont = true;<br>
>> }<br>
>><br>
><br>
> Similarly, here I think it would be clearer to do:<br>
><br>
> BITSET_WORD new_liveout = bd[block->block_num].livein[i];<br>
> if (new_liveout != bd[b].liveout[i]) {<br>
> bd[b].liveout[i] |= new_liveout;<br>
> cont = true;<br>
> }<br>
<br>
</div></div>I don't think this second block is correct -- you're missing a<br>
"bd[b].liveout | " in setting up new_liveout. I'm leaving it as is to<br>
keep it matching the FS side for now, at least.<br></blockquote><div><br></div><div>Yeah, you're right. I changed my approach halfway through writing it and failed to update it properly. FTR, what I was going for was:</div>
<div><br></div><div>BITSET_WORD new_liveout = bd[b].liveout[i] | bd[block->block_num].livein[i];</div><div>if (new_liveout != bd[b].liveout[i]) {</div><div> bd[b].liveout[i] = new_liveout;</div><div> cont = true;</div>
<div>}</div><div><br></div><div>I'm fine leaving it as is, though.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5"><br>
> Either way, the patch is:<br>
><br>
> Reviewed-by: Paul Berry <<a href="mailto:stereotype441@gmail.com">stereotype441@gmail.com</a>><br>
<br>
</div></div></blockquote></div><br></div></div>