[Mesa-dev] [PATCH 09/16] i965/fs: Calculate interference better in register_coalesce.

[Connor Abbott]

I'm sorry, the text I was thinking of was on page 20 of the Iterated
Register Coalescing paper (
http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/george.pdf),
"Move instructions are given special consideration...", but it's still the
same idea.


On Fri, Dec 27, 2013 at 7:38 PM, Connor Abbott <cwabbott0 at gmail.com> wrote:

> I'm not sure if this is relevant to the i965 fs backend in particular, but
> Briggs in his thesis [1] recommended simply ignoring the liveness of any
> register read by a copy instruction immediately after said instruction when
> computing the interference graph in order to solve this exact problem (see
> section 2.2.2).
>
> [1]  http://www.cs.utexas.edu/~mckinley/380C/lecs/briggs-thesis-1992.pdf
> On Dec 19, 2013 4:40 PM, "Matt Turner" <mattst88 at gmail.com> wrote:
>
>> Previously we simply considered two registers whose live ranges
>> overlapped to interfere. Cases such as
>>
>>    set A     ------
>>    ...             |
>>    mov B, A  --    |
>>    ...         | B | A
>>    use B     --    |
>>    ...             |
>>    use A     ------
>>
>> would be considered to interfere, even though B is an unmodified copy of
>> A whose live range fit wholly inside that of A.
>>
>> If no writes to A or B occur between the mov B, A and the use of B then
>> we can safely coalesce them.
>>
>> Instead of removing MOV instructions, we make them NOPs and remove them
>> at once after the main pass is finished in order to avoid recomputing
>> live intervals (which are needed to perform the previous step).
>>
>> total instructions in shared programs: 1543768 -> 1513077 (-1.99%)
>> instructions in affected programs:     951563 -> 920872 (-3.23%)
>> GAINED:                                46
>> LOST:                                  22
>> ---
>>  src/mesa/drivers/dri/i965/brw_fs.cpp | 69
>> ++++++++++++++++++++++++++++++++----
>>  1 file changed, 62 insertions(+), 7 deletions(-)
>>
>> diff --git a/src/mesa/drivers/dri/i965/brw_fs.cpp
>> b/src/mesa/drivers/dri/i965/brw_fs.cpp
>> index e4ac0a5..ad56b87 100644
>> --- a/src/mesa/drivers/dri/i965/brw_fs.cpp
>> +++ b/src/mesa/drivers/dri/i965/brw_fs.cpp
>> @@ -2273,7 +2273,7 @@ fs_visitor::register_coalesce()
>>     int last_use[MAX_SAMPLER_MESSAGE_SIZE];
>>     int next_ip = 0;
>>
>> -   foreach_list_safe(node, &this->instructions) {
>> +   foreach_list(node, &this->instructions) {
>>        fs_inst *inst = (fs_inst *)node;
>>
>>        int ip = next_ip;
>> @@ -2299,8 +2299,39 @@ fs_visitor::register_coalesce()
>>        int var_to = live_intervals->var_from_reg(&inst->dst);
>>
>>        if (live_intervals->vars_interfere(var_from, var_to) &&
>> -          !inst->dst.equals(inst->src[0]))
>> -         continue;
>> +          !inst->dst.equals(inst->src[0])) {
>> +
>> +         if (live_intervals->end[var_to] > live_intervals->end[var_from])
>> +            continue;
>> +
>> +         bool overwritten = false;
>> +         int scan_ip = -1;
>> +
>> +         foreach_list(n, &this->instructions) {
>> +           fs_inst *scan_inst = (fs_inst *)n;
>> +            scan_ip++;
>> +
>> +            if (scan_inst->is_control_flow()) {
>> +               overwritten = true;
>> +               break;
>> +            }
>> +
>> +            if (scan_ip <= live_intervals->start[var_to])
>> +               continue;
>> +
>> +            if (scan_ip > live_intervals->end[var_to])
>> +               break;
>> +
>> +            if (scan_inst->dst.equals(inst->dst) ||
>> +                scan_inst->dst.equals(inst->src[0])) {
>> +               overwritten = true;
>> +               break;
>> +            }
>> +         }
>> +
>> +         if (overwritten)
>> +            continue;
>> +      }
>>
>>        if (reg_from != inst->src[0].reg) {
>>           reg_from = inst->src[0].reg;
>> @@ -2342,9 +2373,18 @@ fs_visitor::register_coalesce()
>>        if (live_channels_remaining)
>>           continue;
>>
>> +      bool removed = false;
>>        for (int i = 0; i < src_size; i++) {
>> -         if (mov[i])
>> -            mov[i]->remove();
>> +         if (mov[i]) {
>> +            removed = true;
>> +
>> +            mov[i]->opcode = BRW_OPCODE_NOP;
>> +            mov[i]->conditional_mod = BRW_CONDITIONAL_NONE;
>> +            mov[i]->dst = reg_undef;
>> +            mov[i]->src[0] = reg_undef;
>> +            mov[i]->src[1] = reg_undef;
>> +            mov[i]->src[2] = reg_undef;
>> +         }
>>        }
>>
>>        foreach_list(node, &this->instructions) {
>> @@ -2366,11 +2406,26 @@ fs_visitor::register_coalesce()
>>                       scan_inst->src[j].reg_offset = reg_to_offset[i];
>>                    }
>>                 }
>> -
>> -               progress = true;
>>              }
>>           }
>>        }
>> +
>> +      if (removed) {
>> +         live_intervals->start[var_to] =
>> MIN2(live_intervals->start[var_to],
>> +
>>  live_intervals->start[var_from]);
>> +         live_intervals->end[var_to] = MAX2(live_intervals->end[var_to],
>> +
>>  live_intervals->end[var_from]);
>> +         reg_from = -1;
>> +      }
>> +   }
>> +
>> +   foreach_list_safe(node, &this->instructions) {
>> +      fs_inst *inst = (fs_inst *)node;
>> +
>> +      if (inst->opcode == BRW_OPCODE_NOP) {
>> +         inst->remove();
>> +         progress = true;
>> +      }
>>     }
>>
>>     if (progress)
>> --
>> 1.8.3.2
>>
>> _______________________________________________
>> mesa-dev mailing list
>> mesa-dev at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20131228/95e50755/attachment.html>