Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Francisco Jerez]

Chema Casanova  writes:

> El 08/09/17 a las 11:06, Alejandro Piñeiro escribió:
>> On 08/09/17 02:50, Francisco Jerez wrote:
>>> Currently the liveness analysis pass would extend a live interval up
>>> to the top of the program when no unconditional and complete
>>> definition of the variable is found that dominates all of its uses.
>>>
>>> This can lead to a serious performance problem in shaders containing
>>> many partial writes, like scalar arithmetic, FP64 and soon FP16
>>> operations.  
>> Just tested with the VK_KHR_16bit_storage implementation. Works really
>> fine with the most problematic tests, so we can drop the "i965/fs: Add
>> reuse_16bit_conversions_register optimization" patch (that was already
>> NAKed by both you and Connor).
>>
>> My test was limited to that extension CTS tests, but in case it helps:
>> Tested-by: Alejandro Piñeiro 
>
> I've seen one regression on a full VK-CTS run with this patch over the
> VK_KHR_16bit_storage branch, but I can reproduce the same regression
> applying it on master.
>
> Failing test is:
> dEQP-VK.glsl.return.return_in_dynamic_loop_dynamic_vertex
>

Good finding!  I've been digging into this regression some more and it
looks like the inaccuracy of the liveness analysis pass was protecting
us from a long-standing bug of the dataflow analysis code related to
cross-channel variable interference in non-uniformly executed loops.

I had been ranting about exactly this problem for years, but never
bothered to fix it.  Of course it had to come back to bite me as if
destiny wanted to teach me some sort of distasteful lesson.  :P

I'm amazed that *none* of the GL CTS, dEQP or Piglit test suite managed
to expose this issue, and that the one dEQP-VK test that could have
triggered the problem was passing basically by luck (with a small,
seemingly harmless change to the source code of the test case it would
have exploded regardless of this patch).

Anyway, will come back with a fix, probably next week.

>>> The number of oversize live intervals in such workloads
>>> can cause the compilation time of the shader to explode because of the
>>> worse than quadratic behavior of the register allocator and scheduler
>>> when running out of registers, and it can also cause the running time
>>> of the shader to explode due to the amount of spilling it leads to,
>>> which is orders of magnitude slower than GRF memory.
>>>
>>> This patch fixes it by computing the intersection of our current live
>>> intervals with the subset of the program that can possibly be reached
>>> from any definition of the variable.  Extending the storage allocation
>>> of the variable beyond that is pretty useless because its value is
>>> guaranteed to be undefined at a point that cannot be reached from any
>>> definition.
>>>
>>> No significant change in the running time of shader-db (with 5%
>>> statistical significance).
>>>
>>> shader-db results on IVB:
>>>
>>>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>>>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>>>   helped: 5121
>>>   HURT: 4347
>>>
>>>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>>>   spills in affected programs: 249 -> 228 (-8.43%)
>>>   helped: 3
>>>   HURT: 0
>>>
>>>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>>>   fills in affected programs: 262 -> 207 (-20.99%)
>>>   helped: 4
>>>   HURT: 0
>>>
>>>   LOST:   2
>>>   GAINED: 209
>>>
>>> shader-db results on BDW:
>>>
>>>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>>>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>>>   helped: 8045
>>>   HURT: 6488
>>>
>>>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>>>   spills in affected programs: 465 -> 261 (-43.87%)
>>>   helped: 3
>>>   HURT: 0
>>>
>>>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>>>   fills in affected programs: 471 -> 216 (-54.14%)
>>>   helped: 4
>>>   HURT: 0
>>>
>>>   LOST:   2
>>>   GAINED: 162
>>>
>>> shader-db results on SKL:
>>>
>>>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>>>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>>>   helped: 8457
>>>   HURT: 6247
>>>
>>>   total spills in shared programs: 437 -> 437 (0.00%)
>>>   spills in affected programs: 0 -> 0
>>>   helped: 0
>>>   HURT: 0
>>>
>>>   total fills in shared programs: 870 -> 854 (-1.84%)
>>>   fills in affected programs: 16 -> 0
>>>   helped: 1
>>>   HURT: 0
>>>
>>>   LOST:   0
>>>   GAINED: 107
>>> ---
>>>  src/intel/compiler/brw_fs_live_variables.cpp | 34 
>>> 
>>>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>>>  2 files changed, 42 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp 
>>> b/src/intel/compiler/brw_fs_live_variables.cpp
>>> index c449672a519..059f076fa51 100644
>>> --- a/src/intel/compiler/brw_fs_live_variables.cpp
>>> +++ 

Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Connor Abbott]

On Thu, Sep 7, 2017 at 9:30 PM, Jason Ekstrand  wrote:
> On Thu, Sep 7, 2017 at 5:50 PM, Francisco Jerez 
> wrote:
>>
>> Currently the liveness analysis pass would extend a live interval up
>> to the top of the program when no unconditional and complete
>> definition of the variable is found that dominates all of its uses.
>>
>> This can lead to a serious performance problem in shaders containing
>> many partial writes, like scalar arithmetic, FP64 and soon FP16
>> operations.  The number of oversize live intervals in such workloads
>> can cause the compilation time of the shader to explode because of the
>> worse than quadratic behavior of the register allocator and scheduler
>> when running out of registers, and it can also cause the running time
>> of the shader to explode due to the amount of spilling it leads to,
>> which is orders of magnitude slower than GRF memory.
>>
>> This patch fixes it by computing the intersection of our current live
>> intervals with the subset of the program that can possibly be reached
>> from any definition of the variable.  Extending the storage allocation
>> of the variable beyond that is pretty useless because its value is
>> guaranteed to be undefined at a point that cannot be reached from any
>> definition.
>>
>> No significant change in the running time of shader-db (with 5%
>> statistical significance).
>>
>> shader-db results on IVB:
>>
>>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>>   helped: 5121
>>   HURT: 4347
>>
>>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>>   spills in affected programs: 249 -> 228 (-8.43%)
>>   helped: 3
>>   HURT: 0
>>
>>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>>   fills in affected programs: 262 -> 207 (-20.99%)
>>   helped: 4
>>   HURT: 0
>>
>>   LOST:   2
>>   GAINED: 209
>>
>> shader-db results on BDW:
>>
>>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>>   helped: 8045
>>   HURT: 6488
>>
>>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>>   spills in affected programs: 465 -> 261 (-43.87%)
>>   helped: 3
>>   HURT: 0
>>
>>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>>   fills in affected programs: 471 -> 216 (-54.14%)
>>   helped: 4
>>   HURT: 0
>>
>>   LOST:   2
>>   GAINED: 162
>>
>> shader-db results on SKL:
>>
>>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>>   helped: 8457
>>   HURT: 6247
>
>
> I'm a but surprised at how many programs this affected.  For something that
> doesn't do any partial writes before a  full write, it should have no effect
> whatsoever.

Not quite. For example, in something like:

if (...) {
   foo = ...;
}
// later, maybe in other control flow
... = foo;

originally, the live range of foo would extend to the beginning of the
program, but with this change it wouldn't since no definitions reach
there and foo is undefined anyways. This sort of happens automatically
in SSA with phi nodes and undef instructions, but not post-SSA.
Something like it probably explains most of the changes.

> Maybe this is because of constant combining or something?
>
> FYI, I applied this on top of my subgroups series and the dvec2 broadcast
> test went from around 1k fills per shader to 0 and the test run time (mostly
> compile time) goes from 130s to 7.5s.  I'll let you immagine how long the
> dvec4 test takes to compile. :-)
>
> --Jason
>
>>
>>   total spills in shared programs: 437 -> 437 (0.00%)
>>   spills in affected programs: 0 -> 0
>>   helped: 0
>>   HURT: 0
>>
>>   total fills in shared programs: 870 -> 854 (-1.84%)
>>   fills in affected programs: 16 -> 0
>>   helped: 1
>>   HURT: 0
>>
>>   LOST:   0
>>   GAINED: 107
>> ---
>>  src/intel/compiler/brw_fs_live_variables.cpp | 34
>> 
>>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>>  2 files changed, 42 insertions(+), 4 deletions(-)
>>
>> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp
>> b/src/intel/compiler/brw_fs_live_variables.cpp
>> index c449672a519..059f076fa51 100644
>> --- a/src/intel/compiler/brw_fs_live_variables.cpp
>> +++ b/src/intel/compiler/brw_fs_live_variables.cpp
>> @@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data
>> *bd, fs_inst *inst,
>> /* The def[] bitset marks when an initialization in a block completely
>>  * screens off previous updates of that variable (VGRF channel).
>>  */
>> -   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
>> -  if (!BITSET_TEST(bd->use, var))
>> +   if (inst->dst.file == VGRF) {
>> +  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
>>   BITSET_SET(bd->def, var);
>> +
>> +  BITSET_SET(bd->defout, var);
>> }
>>  }
>>
>> @@ -199,6 

Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Chema Casanova]

El 08/09/17 a las 11:06, Alejandro Piñeiro escribió:
> On 08/09/17 02:50, Francisco Jerez wrote:
>> Currently the liveness analysis pass would extend a live interval up
>> to the top of the program when no unconditional and complete
>> definition of the variable is found that dominates all of its uses.
>>
>> This can lead to a serious performance problem in shaders containing
>> many partial writes, like scalar arithmetic, FP64 and soon FP16
>> operations.  
> Just tested with the VK_KHR_16bit_storage implementation. Works really
> fine with the most problematic tests, so we can drop the "i965/fs: Add
> reuse_16bit_conversions_register optimization" patch (that was already
> NAKed by both you and Connor).
>
> My test was limited to that extension CTS tests, but in case it helps:
> Tested-by: Alejandro Piñeiro 

I've seen one regression on a full VK-CTS run with this patch over the
VK_KHR_16bit_storage branch, but I can reproduce the same regression
applying it on master.

Failing test is:
dEQP-VK.glsl.return.return_in_dynamic_loop_dynamic_vertex

>> The number of oversize live intervals in such workloads
>> can cause the compilation time of the shader to explode because of the
>> worse than quadratic behavior of the register allocator and scheduler
>> when running out of registers, and it can also cause the running time
>> of the shader to explode due to the amount of spilling it leads to,
>> which is orders of magnitude slower than GRF memory.
>>
>> This patch fixes it by computing the intersection of our current live
>> intervals with the subset of the program that can possibly be reached
>> from any definition of the variable.  Extending the storage allocation
>> of the variable beyond that is pretty useless because its value is
>> guaranteed to be undefined at a point that cannot be reached from any
>> definition.
>>
>> No significant change in the running time of shader-db (with 5%
>> statistical significance).
>>
>> shader-db results on IVB:
>>
>>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>>   helped: 5121
>>   HURT: 4347
>>
>>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>>   spills in affected programs: 249 -> 228 (-8.43%)
>>   helped: 3
>>   HURT: 0
>>
>>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>>   fills in affected programs: 262 -> 207 (-20.99%)
>>   helped: 4
>>   HURT: 0
>>
>>   LOST:   2
>>   GAINED: 209
>>
>> shader-db results on BDW:
>>
>>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>>   helped: 8045
>>   HURT: 6488
>>
>>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>>   spills in affected programs: 465 -> 261 (-43.87%)
>>   helped: 3
>>   HURT: 0
>>
>>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>>   fills in affected programs: 471 -> 216 (-54.14%)
>>   helped: 4
>>   HURT: 0
>>
>>   LOST:   2
>>   GAINED: 162
>>
>> shader-db results on SKL:
>>
>>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>>   helped: 8457
>>   HURT: 6247
>>
>>   total spills in shared programs: 437 -> 437 (0.00%)
>>   spills in affected programs: 0 -> 0
>>   helped: 0
>>   HURT: 0
>>
>>   total fills in shared programs: 870 -> 854 (-1.84%)
>>   fills in affected programs: 16 -> 0
>>   helped: 1
>>   HURT: 0
>>
>>   LOST:   0
>>   GAINED: 107
>> ---
>>  src/intel/compiler/brw_fs_live_variables.cpp | 34 
>> 
>>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>>  2 files changed, 42 insertions(+), 4 deletions(-)
>>
>> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp 
>> b/src/intel/compiler/brw_fs_live_variables.cpp
>> index c449672a519..059f076fa51 100644
>> --- a/src/intel/compiler/brw_fs_live_variables.cpp
>> +++ b/src/intel/compiler/brw_fs_live_variables.cpp
>> @@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data *bd, 
>> fs_inst *inst,
>> /* The def[] bitset marks when an initialization in a block completely
>>  * screens off previous updates of that variable (VGRF channel).
>>  */
>> -   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
>> -  if (!BITSET_TEST(bd->use, var))
>> +   if (inst->dst.file == VGRF) {
>> +  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
>>   BITSET_SET(bd->def, var);
>> +
>> +  BITSET_SET(bd->defout, var);
>> }
>>  }
>>  
>> @@ -199,6 +201,28 @@ fs_live_variables::compute_live_variables()
>>   }
>>}
>> }
>> +
>> +   /* Propagate defin and defout down the CFG to calculate the union of live
>> +* variables potentially defined along any possible control flow path.
>> +*/
>> +   do {
>> +  cont = false;
>> +
>> +  foreach_block (block, cfg) {
>> + const struct block_data *bd = _data[block->num];
>> 

Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Alejandro Piñeiro]

On 08/09/17 02:50, Francisco Jerez wrote:
> Currently the liveness analysis pass would extend a live interval up
> to the top of the program when no unconditional and complete
> definition of the variable is found that dominates all of its uses.
>
> This can lead to a serious performance problem in shaders containing
> many partial writes, like scalar arithmetic, FP64 and soon FP16
> operations.  

Just tested with the VK_KHR_16bit_storage implementation. Works really
fine with the most problematic tests, so we can drop the "i965/fs: Add
reuse_16bit_conversions_register optimization" patch (that was already
NAKed by both you and Connor).

My test was limited to that extension CTS tests, but in case it helps:
Tested-by: Alejandro Piñeiro 

> The number of oversize live intervals in such workloads
> can cause the compilation time of the shader to explode because of the
> worse than quadratic behavior of the register allocator and scheduler
> when running out of registers, and it can also cause the running time
> of the shader to explode due to the amount of spilling it leads to,
> which is orders of magnitude slower than GRF memory.
>
> This patch fixes it by computing the intersection of our current live
> intervals with the subset of the program that can possibly be reached
> from any definition of the variable.  Extending the storage allocation
> of the variable beyond that is pretty useless because its value is
> guaranteed to be undefined at a point that cannot be reached from any
> definition.
>
> No significant change in the running time of shader-db (with 5%
> statistical significance).
>
> shader-db results on IVB:
>
>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>   helped: 5121
>   HURT: 4347
>
>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>   spills in affected programs: 249 -> 228 (-8.43%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>   fills in affected programs: 262 -> 207 (-20.99%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 209
>
> shader-db results on BDW:
>
>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>   helped: 8045
>   HURT: 6488
>
>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>   spills in affected programs: 465 -> 261 (-43.87%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>   fills in affected programs: 471 -> 216 (-54.14%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 162
>
> shader-db results on SKL:
>
>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>   helped: 8457
>   HURT: 6247
>
>   total spills in shared programs: 437 -> 437 (0.00%)
>   spills in affected programs: 0 -> 0
>   helped: 0
>   HURT: 0
>
>   total fills in shared programs: 870 -> 854 (-1.84%)
>   fills in affected programs: 16 -> 0
>   helped: 1
>   HURT: 0
>
>   LOST:   0
>   GAINED: 107
> ---
>  src/intel/compiler/brw_fs_live_variables.cpp | 34 
> 
>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>  2 files changed, 42 insertions(+), 4 deletions(-)
>
> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp 
> b/src/intel/compiler/brw_fs_live_variables.cpp
> index c449672a519..059f076fa51 100644
> --- a/src/intel/compiler/brw_fs_live_variables.cpp
> +++ b/src/intel/compiler/brw_fs_live_variables.cpp
> @@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data *bd, 
> fs_inst *inst,
> /* The def[] bitset marks when an initialization in a block completely
>  * screens off previous updates of that variable (VGRF channel).
>  */
> -   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
> -  if (!BITSET_TEST(bd->use, var))
> +   if (inst->dst.file == VGRF) {
> +  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
>   BITSET_SET(bd->def, var);
> +
> +  BITSET_SET(bd->defout, var);
> }
>  }
>  
> @@ -199,6 +201,28 @@ fs_live_variables::compute_live_variables()
>   }
>}
> }
> +
> +   /* Propagate defin and defout down the CFG to calculate the union of live
> +* variables potentially defined along any possible control flow path.
> +*/
> +   do {
> +  cont = false;
> +
> +  foreach_block (block, cfg) {
> + const struct block_data *bd = _data[block->num];
> +
> +  foreach_list_typed(bblock_link, child_link, link, >children) {
> +struct block_data *child_bd = 
> _data[child_link->block->num];
> +
> + for (int i = 0; i < bitset_words; i++) {
> +   const BITSET_WORD new_def = bd->defout[i] & 
> ~child_bd->defin[i];
> +   child_bd->defin[i] |= new_def;
> +   child_bd->defout[i] |= new_def;
> +   cont |= new_def;

Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Jason Ekstrand]

On Thu, Sep 7, 2017 at 5:50 PM, Francisco Jerez 
wrote:

> Currently the liveness analysis pass would extend a live interval up
> to the top of the program when no unconditional and complete
> definition of the variable is found that dominates all of its uses.
>
> This can lead to a serious performance problem in shaders containing
> many partial writes, like scalar arithmetic, FP64 and soon FP16
> operations.  The number of oversize live intervals in such workloads
> can cause the compilation time of the shader to explode because of the
> worse than quadratic behavior of the register allocator and scheduler
> when running out of registers, and it can also cause the running time
> of the shader to explode due to the amount of spilling it leads to,
> which is orders of magnitude slower than GRF memory.
>
> This patch fixes it by computing the intersection of our current live
> intervals with the subset of the program that can possibly be reached
> from any definition of the variable.  Extending the storage allocation
> of the variable beyond that is pretty useless because its value is
> guaranteed to be undefined at a point that cannot be reached from any
> definition.
>
> No significant change in the running time of shader-db (with 5%
> statistical significance).
>
> shader-db results on IVB:
>
>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>   helped: 5121
>   HURT: 4347
>
>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>   spills in affected programs: 249 -> 228 (-8.43%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>   fills in affected programs: 262 -> 207 (-20.99%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 209
>
> shader-db results on BDW:
>
>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>   helped: 8045
>   HURT: 6488
>
>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>   spills in affected programs: 465 -> 261 (-43.87%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>   fills in affected programs: 471 -> 216 (-54.14%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 162
>
> shader-db results on SKL:
>
>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>   helped: 8457
>   HURT: 6247
>

I'm a but surprised at how many programs this affected.  For something that
doesn't do any partial writes before a  full write, it should have no
effect whatsoever.  Maybe this is because of constant combining or
something?

FYI, I applied this on top of my subgroups series and the dvec2 broadcast
test went from around 1k fills per shader to 0 and the test run time
(mostly compile time) goes from 130s to 7.5s.  I'll let you immagine how
long the dvec4 test takes to compile. :-)

--Jason


>   total spills in shared programs: 437 -> 437 (0.00%)
>   spills in affected programs: 0 -> 0
>   helped: 0
>   HURT: 0
>
>   total fills in shared programs: 870 -> 854 (-1.84%)
>   fills in affected programs: 16 -> 0
>   helped: 1
>   HURT: 0
>
>   LOST:   0
>   GAINED: 107
> ---
>  src/intel/compiler/brw_fs_live_variables.cpp | 34
> 
>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>  2 files changed, 42 insertions(+), 4 deletions(-)
>
> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp
> b/src/intel/compiler/brw_fs_live_variables.cpp
> index c449672a519..059f076fa51 100644
> --- a/src/intel/compiler/brw_fs_live_variables.cpp
> +++ b/src/intel/compiler/brw_fs_live_variables.cpp
> @@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data
> *bd, fs_inst *inst,
> /* The def[] bitset marks when an initialization in a block completely
>  * screens off previous updates of that variable (VGRF channel).
>  */
> -   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
> -  if (!BITSET_TEST(bd->use, var))
> +   if (inst->dst.file == VGRF) {
> +  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
>   BITSET_SET(bd->def, var);
> +
> +  BITSET_SET(bd->defout, var);
> }
>  }
>
> @@ -199,6 +201,28 @@ fs_live_variables::compute_live_variables()
>   }
>}
> }
> +
> +   /* Propagate defin and defout down the CFG to calculate the union of
> live
> +* variables potentially defined along any possible control flow path.
> +*/
> +   do {
> +  cont = false;
> +
> +  foreach_block (block, cfg) {
> + const struct block_data *bd = _data[block->num];
> +
> +foreach_list_typed(bblock_link, child_link, link,
> >children) {
> +struct block_data *child_bd = _data[child_link->block-
> >num];
> +
> +   for (int i = 0; i < bitset_words; i++) {
> +   const BITSET_WORD new_def = 

Re: [Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Jason Ekstrand]

On Thu, Sep 7, 2017 at 5:50 PM, Francisco Jerez 
wrote:

> Currently the liveness analysis pass would extend a live interval up
> to the top of the program when no unconditional and complete
> definition of the variable is found that dominates all of its uses.
>
> This can lead to a serious performance problem in shaders containing
> many partial writes, like scalar arithmetic, FP64 and soon FP16
> operations.  The number of oversize live intervals in such workloads
> can cause the compilation time of the shader to explode because of the
> worse than quadratic behavior of the register allocator and scheduler
> when running out of registers, and it can also cause the running time
> of the shader to explode due to the amount of spilling it leads to,
> which is orders of magnitude slower than GRF memory.
>
> This patch fixes it by computing the intersection of our current live
> intervals with the subset of the program that can possibly be reached
> from any definition of the variable.  Extending the storage allocation
> of the variable beyond that is pretty useless because its value is
> guaranteed to be undefined at a point that cannot be reached from any
> definition.
>
> No significant change in the running time of shader-db (with 5%
> statistical significance).
>
> shader-db results on IVB:
>
>   total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
>   cycles in affected programs: 16335482 -> 16159558 (-1.08%)
>   helped: 5121
>   HURT: 4347
>
>   total spills in shared programs: 1309 -> 1288 (-1.60%)
>   spills in affected programs: 249 -> 228 (-8.43%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1652 -> 1597 (-3.33%)
>   fills in affected programs: 262 -> 207 (-20.99%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 209
>
> shader-db results on BDW:
>
>   total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
>   cycles in affected programs: 23397142 -> 23141100 (-1.09%)
>   helped: 8045
>   HURT: 6488
>
>   total spills in shared programs: 1456 -> 1252 (-14.01%)
>   spills in affected programs: 465 -> 261 (-43.87%)
>   helped: 3
>   HURT: 0
>
>   total fills in shared programs: 1720 -> 1465 (-14.83%)
>   fills in affected programs: 471 -> 216 (-54.14%)
>   helped: 4
>   HURT: 0
>
>   LOST:   2
>   GAINED: 162
>
> shader-db results on SKL:
>
>   total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
>   cycles in affected programs: 22560936 -> 22369874 (-0.85%)
>   helped: 8457
>   HURT: 6247
>
>   total spills in shared programs: 437 -> 437 (0.00%)
>   spills in affected programs: 0 -> 0
>   helped: 0
>   HURT: 0
>
>   total fills in shared programs: 870 -> 854 (-1.84%)
>   fills in affected programs: 16 -> 0
>   helped: 1
>   HURT: 0
>
>   LOST:   0
>   GAINED: 107
> ---
>  src/intel/compiler/brw_fs_live_variables.cpp | 34
> 
>  src/intel/compiler/brw_fs_live_variables.h   | 12 ++
>  2 files changed, 42 insertions(+), 4 deletions(-)
>
> diff --git a/src/intel/compiler/brw_fs_live_variables.cpp
> b/src/intel/compiler/brw_fs_live_variables.cpp
> index c449672a519..059f076fa51 100644
> --- a/src/intel/compiler/brw_fs_live_variables.cpp
> +++ b/src/intel/compiler/brw_fs_live_variables.cpp
> @@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data
> *bd, fs_inst *inst,
> /* The def[] bitset marks when an initialization in a block completely
>  * screens off previous updates of that variable (VGRF channel).
>  */
> -   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
> -  if (!BITSET_TEST(bd->use, var))
> +   if (inst->dst.file == VGRF) {
> +  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
>   BITSET_SET(bd->def, var);
> +
> +  BITSET_SET(bd->defout, var);
> }
>  }
>
> @@ -199,6 +201,28 @@ fs_live_variables::compute_live_variables()
>   }
>}
> }
> +
> +   /* Propagate defin and defout down the CFG to calculate the union of
> live
> +* variables potentially defined along any possible control flow path.
> +*/
> +   do {
> +  cont = false;
> +
> +  foreach_block (block, cfg) {
> + const struct block_data *bd = _data[block->num];
> +
> +foreach_list_typed(bblock_link, child_link, link,
> >children) {
> +struct block_data *child_bd = _data[child_link->block-
> >num];
> +
> +   for (int i = 0; i < bitset_words; i++) {
> +   const BITSET_WORD new_def = bd->defout[i] &
> ~child_bd->defin[i];
>

Mind adding a comment here:

/* defin is a subset of defout so if we make progress on defout we must
make progress on defin as well. */

Other than that, looks good to me.  I don't think this adds all that muc
complication.

Reviewed-by: Jason Ekstrand 


> +   child_bd->defin[i] |= new_def;
> +   child_bd->defout[i] |= new_def;
> +   cont |= new_def;
> +   }
> +}
> +  }
> +   } 

[Mesa-dev] [PATCH] intel/fs: Restrict live intervals to the subset possibly reachable from any definition.

[Francisco Jerez]

Currently the liveness analysis pass would extend a live interval up
to the top of the program when no unconditional and complete
definition of the variable is found that dominates all of its uses.

This can lead to a serious performance problem in shaders containing
many partial writes, like scalar arithmetic, FP64 and soon FP16
operations.  The number of oversize live intervals in such workloads
can cause the compilation time of the shader to explode because of the
worse than quadratic behavior of the register allocator and scheduler
when running out of registers, and it can also cause the running time
of the shader to explode due to the amount of spilling it leads to,
which is orders of magnitude slower than GRF memory.

This patch fixes it by computing the intersection of our current live
intervals with the subset of the program that can possibly be reached
from any definition of the variable.  Extending the storage allocation
of the variable beyond that is pretty useless because its value is
guaranteed to be undefined at a point that cannot be reached from any
definition.

No significant change in the running time of shader-db (with 5%
statistical significance).

shader-db results on IVB:

  total cycles in shared programs: 61108780 -> 60932856 (-0.29%)
  cycles in affected programs: 16335482 -> 16159558 (-1.08%)
  helped: 5121
  HURT: 4347

  total spills in shared programs: 1309 -> 1288 (-1.60%)
  spills in affected programs: 249 -> 228 (-8.43%)
  helped: 3
  HURT: 0

  total fills in shared programs: 1652 -> 1597 (-3.33%)
  fills in affected programs: 262 -> 207 (-20.99%)
  helped: 4
  HURT: 0

  LOST:   2
  GAINED: 209

shader-db results on BDW:

  total cycles in shared programs: 67617262 -> 67361220 (-0.38%)
  cycles in affected programs: 23397142 -> 23141100 (-1.09%)
  helped: 8045
  HURT: 6488

  total spills in shared programs: 1456 -> 1252 (-14.01%)
  spills in affected programs: 465 -> 261 (-43.87%)
  helped: 3
  HURT: 0

  total fills in shared programs: 1720 -> 1465 (-14.83%)
  fills in affected programs: 471 -> 216 (-54.14%)
  helped: 4
  HURT: 0

  LOST:   2
  GAINED: 162

shader-db results on SKL:

  total cycles in shared programs: 65436248 -> 65245186 (-0.29%)
  cycles in affected programs: 22560936 -> 22369874 (-0.85%)
  helped: 8457
  HURT: 6247

  total spills in shared programs: 437 -> 437 (0.00%)
  spills in affected programs: 0 -> 0
  helped: 0
  HURT: 0

  total fills in shared programs: 870 -> 854 (-1.84%)
  fills in affected programs: 16 -> 0
  helped: 1
  HURT: 0

  LOST:   0
  GAINED: 107
---
 src/intel/compiler/brw_fs_live_variables.cpp | 34 
 src/intel/compiler/brw_fs_live_variables.h   | 12 ++
 2 files changed, 42 insertions(+), 4 deletions(-)

diff --git a/src/intel/compiler/brw_fs_live_variables.cpp 
b/src/intel/compiler/brw_fs_live_variables.cpp
index c449672a519..059f076fa51 100644
--- a/src/intel/compiler/brw_fs_live_variables.cpp
+++ b/src/intel/compiler/brw_fs_live_variables.cpp
@@ -83,9 +83,11 @@ fs_live_variables::setup_one_write(struct block_data *bd, 
fs_inst *inst,
/* The def[] bitset marks when an initialization in a block completely
 * screens off previous updates of that variable (VGRF channel).
 */
-   if (inst->dst.file == VGRF && !inst->is_partial_write()) {
-  if (!BITSET_TEST(bd->use, var))
+   if (inst->dst.file == VGRF) {
+  if (!inst->is_partial_write() && !BITSET_TEST(bd->use, var))
  BITSET_SET(bd->def, var);
+
+  BITSET_SET(bd->defout, var);
}
 }
 
@@ -199,6 +201,28 @@ fs_live_variables::compute_live_variables()
  }
   }
}
+
+   /* Propagate defin and defout down the CFG to calculate the union of live
+* variables potentially defined along any possible control flow path.
+*/
+   do {
+  cont = false;
+
+  foreach_block (block, cfg) {
+ const struct block_data *bd = _data[block->num];
+
+foreach_list_typed(bblock_link, child_link, link, >children) {
+struct block_data *child_bd = _data[child_link->block->num];
+
+   for (int i = 0; i < bitset_words; i++) {
+   const BITSET_WORD new_def = bd->defout[i] & ~child_bd->defin[i];
+   child_bd->defin[i] |= new_def;
+   child_bd->defout[i] |= new_def;
+   cont |= new_def;
+   }
+}
+  }
+   } while (cont);
 }
 
 /**
@@ -212,12 +236,12 @@ fs_live_variables::compute_start_end()
   struct block_data *bd = _data[block->num];
 
   for (int i = 0; i < num_vars; i++) {
- if (BITSET_TEST(bd->livein, i)) {
+ if (BITSET_TEST(bd->livein, i) && BITSET_TEST(bd->defin, i)) {
 start[i] = MIN2(start[i], block->start_ip);
 end[i] = MAX2(end[i], block->start_ip);
  }
 
- if (BITSET_TEST(bd->liveout, i)) {
+ if (BITSET_TEST(bd->liveout, i) && BITSET_TEST(bd->defout, i)) {
 start[i] = MIN2(start[i], block->end_ip);
 end[i] =