[Mesa-dev] [PATCH 17/20] i965: Preserve CFG when deleting dead control flow.

[Matt Turner]

On Tue, Aug 19, 2014 at 12:49 AM, Pohjolainen, Topi
<topi.pohjolainen at intel.com> wrote:
> On Thu, Jul 24, 2014 at 07:54:24PM -0700, Matt Turner wrote:
>> This pass deletes an IF/ELSE/ENDIF or IF/ENDIF sequence, or the ELSE in
>> an ELSE/ENDIF sequence.
>>
>> In the typical case (where IF and ENDIF) aren't the only instructions in
>> their basic blocks, we can simply remove the instructions (implicitly
>> deleting the block containing only the ELSE), and attempt to merge
>> blocks B0 and B2 together.
>>
>> B0: ...
>>     (+f0) if(8)
>> B1: else(8)
>> B2: endif(8)
>>     ...
>>
>> If the IF or ENDIF instructions are the only instructions in their
>> respective basic blocks (which are deleted by the removal of the
>> instructions), we'll want to instead merge the next blocks.
>>
>> Both B0 and B2 are possibly removed by the removal of if & endif.
>> Same situation for if/endif. E.g., in the following example we'd remove
>> blocks B1 and B2, and then attempt to combine B0 and B3.
>>
>> B0: ...
>> B1: (+f0) if(8)
>> B2: endif(8)
>> B3: ...
>> ---
>>  .../drivers/dri/i965/brw_dead_control_flow.cpp     | 44 ++++++++++++++++++----
>>  1 file changed, 36 insertions(+), 8 deletions(-)
>>
>> diff --git a/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp b/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
>> index e6ace5c..56dc79e 100644
>> --- a/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
>> +++ b/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
>> @@ -42,7 +42,8 @@ dead_control_flow_eliminate(backend_visitor *v)
>>
>>     v->calculate_cfg();
>>
>> -   foreach_block (block, v->cfg) {
>> +   foreach_block_safe (block, v->cfg) {
>> +      bblock_t *if_block = NULL, *else_block = NULL, *endif_block = block;
>>        bool found = false;
>>
>>        /* ENDIF instructions, by definition, can only be found at the start of
>> @@ -56,6 +57,7 @@ dead_control_flow_eliminate(backend_visitor *v)
>>        backend_instruction *prev_inst = (backend_instruction *) endif_inst->prev;
>>        if (prev_inst->opcode == BRW_OPCODE_ELSE) {
>>           else_inst = prev_inst;
>> +         else_block = (bblock_t *)endif_block->link.prev;
>>           found = true;
>>
>>           prev_inst = (backend_instruction *) prev_inst->prev;
>> @@ -63,6 +65,8 @@ dead_control_flow_eliminate(backend_visitor *v)
>>
>>        if (prev_inst->opcode == BRW_OPCODE_IF) {
>>           if_inst = prev_inst;
>> +         if_block = else_block != NULL ? (bblock_t *)else_block->link.prev
>> +                                       : (bblock_t *)endif_block->link.prev;
>>           found = true;
>>        } else {
>>           /* Don't remove the ENDIF if we didn't find a dead IF. */
>> @@ -70,18 +74,42 @@ dead_control_flow_eliminate(backend_visitor *v)
>>        }
>>
>>        if (found) {
>> -         if (if_inst)
>> -            if_inst->remove();
>> -         if (else_inst)
>> -            else_inst->remove();
>> -         if (endif_inst)
>> -            endif_inst->remove();
>> +         bblock_t *earlier_block = NULL, *later_block = NULL;
>> +
>> +         if (if_inst) {
>> +            if (if_block->start_ip == if_block->end_ip) {
>> +               earlier_block = (bblock_t *)if_block->link.prev;
>> +            } else {
>> +               earlier_block = if_block;
>> +            }
>> +            if_inst->remove(if_block);
>> +         }
>> +
>> +         if (else_inst) {
>> +            else_block->if_block->else_block = NULL;
>> +            else_inst->remove(else_block);
>> +         }
>> +
>> +         if (endif_inst) {
>> +            if (endif_block->start_ip == endif_block->end_ip) {
>> +               later_block = (bblock_t *)endif_block->link.next;
>> +            } else {
>> +               later_block = endif_block;
>> +            }
>> +            endif_inst->remove(endif_block);
>> +         }
>> +
>> +         assert((earlier_block == NULL) == (later_block == NULL));
>> +         if (earlier_block && earlier_block->can_combine_with(later_block)) {
>> +            earlier_block->combine_with(later_block);
>
> Now that we are using foreach_block_safe(), isn't next pointing to later_block
> which gets removed here when its merged into earlier_block? I could be missing
> something as I had some difficulty with the documentation in the previous
> patch.

Good find. You're exactly right. Take this for example:

    B0: ...
        (+f0) if(8)
    B1: endif(8)            <- block
    B2: ...                 <- next

After deleting if/endif (and therefore the endif block B1)

    B0: ...
    B2: ...                 <- next
                            <- block points to dead block

After combining B0 and B2:

    B0: ...
                            <- next points to dead block
                            <- block points to dead block

I'll add this:

   /* If ENDIF was in its own block, then we've now deleted it and
    * merged the two surrounding blocks, the latter of which the
    * __next block pointer was pointing to.
    */
   if (endif_block != later_block) {
      __next = (bblock_t *)earlier_block->link.next;
   }

immediately after earlier_block->combine_with(later_block).

By the way, I committed the first 6 patches of the series (the one
touching the generators had started to rot). I think other than 16 and
17, the only ones missing review are the patches that add the
insertion and removal methods. I sent new versions of them based on
your feedback a few days ago.