[PATCH] Check dominator info in compute_dominance_frontiers

[Tom de Vries <Tom_deVries@mentor.com>]

[-- Attachment #1: Type: text/plain, Size: 1986 bytes --]

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

[-- Attachment #2: 0002-Check-dominator-info-in-compute_dominance_frontiers.patch --]
[-- Type: text/x-patch, Size: 1227 bytes --]

Check dominator info in compute_dominance_frontiers

2015-06-22  Tom de Vries  <tom@codesourcery.com>

	* cfganal.c (compute_dominance_frontiers_1): Add assert.
	(compute_dominance_frontiers): Verify dominators if ENABLE_CHECKING.
---
 gcc/cfganal.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index b8d67bc..0e0e2bb 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -1261,6 +1261,11 @@ compute_dominance_frontiers_1 (bitmap_head *frontiers)
 	      domsb = get_immediate_dominator (CDI_DOMINATORS, b);
 	      while (runner != domsb)
 		{
+		  /* If you're running into this assert, the dominator info is
+		     incorrect.  Try enabling the verify_dominators call at the
+		     start of compute_dominance_frontiers.  */
+		  gcc_assert (runner != ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
 		  if (!bitmap_set_bit (&frontiers[runner->index],
 				       b->index))
 		    break;
@@ -1276,6 +1281,10 @@ compute_dominance_frontiers_1 (bitmap_head *frontiers)
 void
 compute_dominance_frontiers (bitmap_head *frontiers)
 {
+#if ENABLE_CHECKING
+  verify_dominators (CDI_DOMINATORS);
+#endif
+
   timevar_push (TV_DOM_FRONTIERS);
 
   compute_dominance_frontiers_1 (frontiers);
-- 
1.9.1