[PATCH] Check headers in verify_loop_structure

[Marek Polacek <polacek at redhat dot com>]

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);
+		err = 1;
+	      }
+	}
+    }
+
   /* Check sizes.  */
   sizes = XCNEWVEC (unsigned, num);
   sizes[0] = 2;

	Marek