[PATCH] Check dominator info in compute_dominance_frontiers

[Tom de Vries]

On 22/06/15 13:47, Richard Biener wrote:
> 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.
>

Bootstrapped and reg-tested on x86_64. Committed as attached.

Thanks,
- Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0005-Verify-dominators-in-early-out-calculate_dominance_i.patch
Type: text/x-patch
Size: 759 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150622/7464b5bf/attachment.bin>