Check dominator info in compute_dominance_frontiers

On 22/06/15 12:14, Richard Biener wrote:
> 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).
>

The segfault is not guaranteed to trigger, because it works on 
uninitialized data. Instead, we may end up modifying valid memory and 
silently generating wrong code or causing sigsegvs (which will be 
difficult to track back this error). So I don't think doing nothing is 
an option here. If we're not going to add this assert, we should 
initialize the uninitialized data in such a way that we are guaranteed 
to detect the error. The scheme I proposed above would take care of 
that. Should I implement that instead?

> 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

OK, like this:
...
...

I didn't fully understand your comment, do you want me to test this?

Thanks,
- Tom

> (eventually also for the case where we
> end up only computing the fast-query stuff).

On Mon, Jun 22, 2015 at 1:33 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 22/06/15 12:14, Richard Biener wrote:
>>
>> 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).
>>
>
> The segfault is not guaranteed to trigger, because it works on uninitialized
> data. Instead, we may end up modifying valid memory and silently generating
> wrong code or causing sigsegvs (which will be difficult to track back this
> error). So I don't think doing nothing is an option here. If we're not going
> to add this assert, we should initialize the uninitialized data in such a
> way that we are guaranteed to detect the error. The scheme I proposed above
> would take care of that. Should I implement that instead?

No, instead the check below should catch the error much earlier.

>> 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
>
>
> OK, like this:
> ...
> diff --git a/gcc/dominance.c b/gcc/dominance.c
> index a9e042e..1827eda9 100644
> --- a/gcc/dominance.c
> +++ b/gcc/dominance.c
> @@ -646,7 +646,12 @@ calculate_dominance_info (enum cdi_direction dir)
>    bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
>
>    if (dom_computed[dir_index] == DOM_OK)
> -    return;
> +    {
> +#if ENABLE_CHECKING
> +      verify_dominators (CDI_DOMINATORS);
> +#endif
> +      return;
> +    }
>
>    timevar_push (TV_DOMINANCE);
>    if (!dom_info_available_p (dir))
> ...

Yes.

> I didn't fully understand your comment, do you want me to test this?

Sure, it should catch the error.

Richard.

> Thanks,
> - Tom
>
>
>> (eventually also for the case where we
>> end up only computing the fast-query stuff).
>
>