Check headers in verify_loop_structure

This patch extends verify_loop_structure by checking that header's
are really its own headers (this proved as useful in PR56181).
The bulk of the code is taken from flow_loops_find.

Bootstrapped on x86_64 linux.  The only fallout now is (for C/C++):
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer  (internal compiler error)
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer  (test for excess errors)
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-loops  (internal compiler error)
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-loops  (test for excess errors)
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions  (internal compiler error)
FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions  (test for excess errors)
FAIL: gcc.dg/torture/pr54458.c  -O3 -g  (internal compiler error)                  
FAIL: gcc.dg/torture/pr54458.c  -O3 -g  (test for excess errors)

which is only because -O3 means -funswitch-loops as well.  What happens
here is quite interesting situation, we have three analogical loops
which look like below.  BB7 is marked as IRREDUCIBLE_LOOP.

			    |
          +---------------+ |
	  |		  | |
	  |   	      +---+-+-+
	  |   	      |   6   |
	  |  	      +---+---+
	  |  		  |        ---|
	  |  		  |  -----/   |
	  |  	      +-----/-+       |
	  |           |	  7   |	      |
	  |           +-------+	      |
	  |  	       /  \	      |
	  | 	      /	   \	      |
	  |   +------+	  +------+    |
	  |   |	 9   |	  |   8	 |    |
	  |   +--+---+	  +---+--+    |
	  | 	 |	      |	      |
	  | 	 |	      +-------+
	  |   +-------+
          |   |   10  |
	  |   +---+---+
          |       |
          +-------+

Thus, we basically have two headers in a loop.
So, shall I skip the BB_IRREDUCIBLE_LOOP blocks?  (Although this leads to
another crash: we get into the same situation in another pass, just
the BB isn't marked as BB_IRREDUCIBLE_LOOP, so we don't skip it.  Perhaps
this could be sorted out by just calling mark_irreducible_loops somewhere.)

Comments?

2013-02-06  Marek Polacek  <polacek@redhat.com>

	* cfgloop.c (verify_loop_structure): Check that header
	BBs are really its own headers.


	Marek

On Wed, 6 Feb 2013, Marek Polacek wrote:

> This patch extends verify_loop_structure by checking that header's
> are really its own headers (this proved as useful in PR56181).
> The bulk of the code is taken from flow_loops_find.
> 
> Bootstrapped on x86_64 linux.  The only fallout now is (for C/C++):
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer  (internal compiler error)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer  (test for excess errors)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-loops  (internal compiler error)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-loops  (test for excess errors)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions  (internal compiler error)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -fomit-frame-pointer -funroll-all-loops -finline-functions  (test for excess errors)
> FAIL: gcc.dg/torture/pr54458.c  -O3 -g  (internal compiler error)                  
> FAIL: gcc.dg/torture/pr54458.c  -O3 -g  (test for excess errors)
> 
> which is only because -O3 means -funswitch-loops as well.  What happens
> here is quite interesting situation, we have three analogical loops
> which look like below.  BB7 is marked as IRREDUCIBLE_LOOP.
> 
> 			    |
>           +---------------+ |
> 	  |		  | |
> 	  |   	      +---+-+-+
> 	  |   	      |   6   |
> 	  |  	      +---+---+
> 	  |  		  |        ---|
> 	  |  		  |  -----/   |
> 	  |  	      +-----/-+       |
> 	  |           |	  7   |	      |
> 	  |           +-------+	      |
> 	  |  	       /  \	      |
> 	  | 	      /	   \	      |
> 	  |   +------+	  +------+    |
> 	  |   |	 9   |	  |   8	 |    |
> 	  |   +--+---+	  +---+--+    |
> 	  | 	 |	      |	      |
> 	  | 	 |	      +-------+
> 	  |   +-------+
>           |   |   10  |
> 	  |   +---+---+
>           |       |
>           +-------+
> 
> Thus, we basically have two headers in a loop.
> So, shall I skip the BB_IRREDUCIBLE_LOOP blocks?  (Although this leads to
> another crash: we get into the same situation in another pass, just
> the BB isn't marked as BB_IRREDUCIBLE_LOOP, so we don't skip it.  Perhaps
> this could be sorted out by just calling mark_irreducible_loops somewhere.)
> 
> Comments?
> 
> 2013-02-06  Marek Polacek  <polacek@redhat.com>
> 
> 	* cfgloop.c (verify_loop_structure): Check that header
> 	BBs are really its own headers.
> 
> --- gcc/cfgloop.c.mp	2013-02-06 12:08:01.536918761 +0100
> +++ gcc/cfgloop.c	2013-02-06 18:32:59.957027313 +0100
> @@ -1316,6 +1316,41 @@ verify_loop_structure (void)
>    else
>      verify_dominators (CDI_DOMINATORS);
>  
> +  /* Check the loop headers.  */
> +  FOR_EACH_BB (bb)
> +    {
> +      edge_iterator ei;
> +
> +      /* If we have an abnormal predecessor, do not consider the
> +	 loop (not worth the problems).  */
> +      if (bb_has_abnormal_pred (bb))
> +	continue;
> +
> +      if (bb->loop_father == current_loops->tree_root)
> +        continue;
> +
> +      FOR_EACH_EDGE (e, ei, bb->preds)
> +	{
> +	  basic_block latch = e->src;
> +
> +	  gcc_assert (!(e->flags & EDGE_ABNORMAL));
> +
> +	  /* Look for back edges where a predecessor is dominated
> +	     by this block.  A natural loop has a single entry
> +	     node (header) that dominates all the nodes in the
> +	     loop.  It also has single back edge to the header
> +	     from a latch node.  */
> +	  if (latch != ENTRY_BLOCK_PTR
> +	      && bb != latch
> +	      && dominated_by_p (CDI_DOMINATORS, latch, bb))
> +	    if (bb->loop_father->header != bb)
> +	      {
> +		error ("header %d is not its own header", bb->index);

I'd say "loop with header %d not in loop tree" here.  Eventually
the header detection should be shared with the code in flow_loops_find
to avoid divergence.  I'm making changes to the flow_loops_find code
at the moment and will look at splitting out that part properly to
be re-used by the verifier.

Richard.

> +		err = 1;
> +	      }
> +	}
> +    }
> +
>    /* Check sizes.  */
>    sizes = XCNEWVEC (unsigned, num);
>    sizes[0] = 2;
> 
> 	Marek
> 
>