Check dominator info in compute_dominance_frontiers

Hi,

during development of a patch I ran into a case where 
compute_dominance_frontiers was called with incorrect dominance info.

The result was a segmentation violation somewhere in the bitmap code 
while executing this bitmap_set_bit in compute_dominance_frontiers_1:
...
                   if (!bitmap_set_bit (&frontiers[runner->index],
                                        b->index))
                     break;
...

The segmentation violation happens because runner->index is 0, and 
frontiers[0] is uninitialized.

[ The initialization in update_ssa looks like this:
...
      dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
       FOR_EACH_BB_FN (bb, cfun)
         bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
       compute_dominance_frontiers (dfs);
...

FOR_EACH_BB_FN skips over the entry-block and the exit-block, so dfs[0] 
(frontiers[0] in compute_dominance_frontiers_1) is not initialized.

We could add initialization by making the entry/exit-block bitmap_heads 
empty and setting the obstack to a reserved obstack bitmap_no_obstack 
for which allocation results in an assert. ]

AFAIU, the immediate problem is not that frontiers[0] is uninitialized, 
but that the loop reaches the state of runner->index == 0, due to the 
incorrect dominance info.

The patch adds an assert to the loop in compute_dominance_frontiers_1, 
to make the failure mode cleaner and easier to understand.

I think we wouldn't catch all errors in dominance info with this assert. 
So the patch also contains an ENABLE_CHECKING-enabled verify_dominators 
call at the start of compute_dominance_frontiers. I'm not sure if:
- adding the verify_dominators call is too costly in runtime.
- the verify_dominators call should be inside or outside the
   TV_DOM_FRONTIERS measurement.
- there is a level of ENABLE_CHECKING that is more appropriate for the
   verify_dominators call.

Is this ok for trunk if bootstrap and reg-test on x86_64 succeeds?

Thanks,
- Tom

On Mon, Jun 22, 2015 at 10:04 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Hi,
>
> during development of a patch I ran into a case where
> compute_dominance_frontiers was called with incorrect dominance info.
>
> The result was a segmentation violation somewhere in the bitmap code while
> executing this bitmap_set_bit in compute_dominance_frontiers_1:
> ...
>                   if (!bitmap_set_bit (&frontiers[runner->index],
>                                        b->index))
>                     break;
> ...
>
> The segmentation violation happens because runner->index is 0, and
> frontiers[0] is uninitialized.
>
> [ The initialization in update_ssa looks like this:
> ...
>      dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
>       FOR_EACH_BB_FN (bb, cfun)
>         bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
>       compute_dominance_frontiers (dfs);
> ...
>
> FOR_EACH_BB_FN skips over the entry-block and the exit-block, so dfs[0]
> (frontiers[0] in compute_dominance_frontiers_1) is not initialized.
>
> We could add initialization by making the entry/exit-block bitmap_heads
> empty and setting the obstack to a reserved obstack bitmap_no_obstack for
> which allocation results in an assert. ]
>
> AFAIU, the immediate problem is not that frontiers[0] is uninitialized, but
> that the loop reaches the state of runner->index == 0, due to the incorrect
> dominance info.
>
> The patch adds an assert to the loop in compute_dominance_frontiers_1, to
> make the failure mode cleaner and easier to understand.
>
> I think we wouldn't catch all errors in dominance info with this assert. So
> the patch also contains an ENABLE_CHECKING-enabled verify_dominators call at
> the start of compute_dominance_frontiers. I'm not sure if:
> - adding the verify_dominators call is too costly in runtime.
> - the verify_dominators call should be inside or outside the
>   TV_DOM_FRONTIERS measurement.
> - there is a level of ENABLE_CHECKING that is more appropriate for the
>   verify_dominators call.
>
> Is this ok for trunk if bootstrap and reg-test on x86_64 succeeds?

I don't think these kind of asserts are good.  A segfault is good by itself
(so you can just add the comment if you like).

Likewise the verify_dominators call is too expensive and misplaced.

If then the call belongs in the dom_computed[] == DOM_OK early-out
in calculate_dominance_info (eventually also for the case where we
end up only computing the fast-query stuff).

Richard.

> Thanks,
> - Tom