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

[Pohjolainen, Topi]

On Tue, Aug 19, 2014 at 12:03:01PM -0700, Matt Turner wrote:
> 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.

Oh, so sorry Matt, I somehow forgot to send my r-b, they are just fine.