[PR68715] Add missing single_pred_p test in scop_detection::merge_sese

Hi,

this patch fixes graphite PR68715, a 6 regression.

In scop_detection::merge_sese, we check if the exit bb of the merged 
sese region is dominated by the entry bb:
...
   if (...
       || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
                           get_entry_bb (combined)))
     {
       ...
       return invalid_sese;
     }
...

Subsequently, we check for an empty exit bb, and if that one's not 
empty, we try to merge an empty successor block into the sese:
...
   /* FIXME: We should remove this piece of code once
      canonicalize_loop_closed_ssa has been removed, because that
      function adds a BB with single exit.  */
   if (!trivially_empty_bb_p (get_exit_bb (combined)))
     {
       /* Find the first empty succ (with single exit) of
          combined.exit.  */
       basic_block imm_succ = combined.exit->dest;
       if (single_succ_p (imm_succ)
           && trivially_empty_bb_p (imm_succ))
         combined.exit = single_succ_edge (imm_succ);
       else
         {
           ...
           return invalid_sese;
         }
     }
...

However, when the imm_succ block has more than one predecessor, merging 
the block into the sese region breaks the property that the exit bb is 
dominated by the entry bb. We then run into an ICE in 
harmful_loop_in_region a bit later, when re-checking that property.

The patch fixes this by adding a test for 'single_pred_p (imm_succ)' in 
the empty-block-merge condition.

Bootstrapped and reg-tested on x86_64.

OK for stage4 trunk?

Thanks,
- Tom

On Wed, 16 Mar 2016, Tom de Vries wrote:

> Hi,
> 
> this patch fixes graphite PR68715, a 6 regression.
> 
> In scop_detection::merge_sese, we check if the exit bb of the merged sese
> region is dominated by the entry bb:
> ...
>   if (...
>       || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
>                           get_entry_bb (combined)))
>     {
>       ...
>       return invalid_sese;
>     }
> ...
> 
> Subsequently, we check for an empty exit bb, and if that one's not empty, we
> try to merge an empty successor block into the sese:
> ...
>   /* FIXME: We should remove this piece of code once
>      canonicalize_loop_closed_ssa has been removed, because that
>      function adds a BB with single exit.  */
>   if (!trivially_empty_bb_p (get_exit_bb (combined)))
>     {
>       /* Find the first empty succ (with single exit) of
>          combined.exit.  */
>       basic_block imm_succ = combined.exit->dest;
>       if (single_succ_p (imm_succ)
>           && trivially_empty_bb_p (imm_succ))
>         combined.exit = single_succ_edge (imm_succ);
>       else
>         {
>           ...
>           return invalid_sese;
>         }
>     }
> ...
> 
> However, when the imm_succ block has more than one predecessor, merging the
> block into the sese region breaks the property that the exit bb is dominated
> by the entry bb. We then run into an ICE in harmful_loop_in_region a bit
> later, when re-checking that property.
> 
> The patch fixes this by adding a test for 'single_pred_p (imm_succ)' in the
> empty-block-merge condition.
> 
> Bootstrapped and reg-tested on x86_64.
> 
> OK for stage4 trunk?

Hmm, it looks like for all what this function does this effectively
pessimizes scop merging and it would be easier to split 'exit'
in case its destination is unsuitable (not trivially empty).

The

  /* For now we just want to bail out when exit does not post-dominate 
entry.
     TODO: We might just add a basic_block at the exit to make exit
     post-dominate entry (the entire region).  */
  if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
                       get_exit_bb (combined))
      || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),

comment also suggests that splitting the get_nearest_pdom_with_single_exit
edge and including the new BB in the combined region would also always fix
the dominance relation (though I don't see how it could do that and
the comment looks wrong and by construction the check should never
trigger).

Otherwise the patch is certainly fine of course.

Thanks,
Richard.