[PATCH][RFC] Fix PR53695

[Richard Guenther <rguenther at suse dot de>]

This fixes PR53695 where we recognize a loop which has only an
abnormal goto edge from its header to its tail.  We already reject
loops during recognition that have at least a single abnormal
predecessor of its head so it seems reasonable to at least require
one regular CFG path from its header to its latch (thus only have
abnormal extra entries / exists).

Not entirely trivial to test as one can see below.

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Any comments?

Thanks,
Richard.

2012-06-27  Richard Guenther  <rguenther@suse.de>

	PR middle-end/53695
	* cfgloop.c (path_without_edge_flags_1): New function.
	(path_without_edge_flags): Likewise.
	(flow_loops_find): Require at least one regular path from
	loop header to latch.

Index: gcc/cfgloop.c
===================================================================
*** gcc/cfgloop.c	(revision 188987)
--- gcc/cfgloop.c	(working copy)
*************** init_loops_structure (struct loops *loop
*** 365,370 ****
--- 365,424 ----
    loops->tree_root = root;
  }
  
+ /* Return true if there is a path from FROM to the dominated TO where no
+    edge on that path contains FLAGS.  */
+ 
+ static bool
+ path_without_edge_flags_1 (basic_block from, basic_block to, int flags,
+ 			   bitmap *visited)
+ {
+   while (to != from)
+     {
+       /* At least one such path to the immediate dominator.  */
+       if (single_pred_p (to))
+ 	{
+ 	  edge e = single_pred_edge (to);
+ 	  if (e->flags & flags)
+ 	    return false;
+ 	  to = e->src;
+ 	}
+       else
+ 	{
+ 	  basic_block dom;
+ 	  edge_iterator ei;
+ 	  edge e;
+ 
+ 	  /* We have to guard ourselves to not loop in the face of subloops.  */
+ 	  if (!*visited)
+ 	    *visited = BITMAP_ALLOC (NULL);
+ 	  if (!bitmap_set_bit (*visited, to->index))
+ 	    return false;
+ 
+ 	  dom = get_immediate_dominator (CDI_DOMINATORS, to);
+ 	  FOR_EACH_EDGE(e, ei, to->preds)
+ 	    if (!(e->flags & flags)
+ 		&& (e->src == dom
+ 		    || path_without_edge_flags_1 (dom, e->src, flags, visited)))
+ 	      break;
+ 
+ 	  to = dom;
+ 	}
+     }
+ 
+   return true;
+ }
+ 
+ static bool
+ path_without_edge_flags (basic_block from, basic_block to, int flags)
+ {
+   bitmap visited = NULL;
+   bool res;
+   res = path_without_edge_flags_1 (from, to, flags, &visited);
+   if (visited)
+     BITMAP_FREE (visited);
+   return res;
+ }
+ 
  /* Find all the natural loops in the function and save in LOOPS structure and
     recalculate loop_depth information in basic block structures.
     Return the number of natural loops found.  */
*************** flow_loops_find (struct loops *loops)
*** 422,430 ****
  	     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
! 	      && dominated_by_p (CDI_DOMINATORS, latch, header))
  	    {
  	      /* Shared headers should be eliminated by now.  */
  	      SET_BIT (headers, header->index);
--- 476,488 ----
  	     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 there is no regular path from the header to the
! 	     latch do not consider this latch (not worth the
! 	     problems).  */
  	  if (latch != ENTRY_BLOCK_PTR
! 	      && dominated_by_p (CDI_DOMINATORS, latch, header)
! 	      && path_without_edge_flags (header, latch, EDGE_COMPLEX))
  	    {
  	      /* Shared headers should be eliminated by now.  */
  	      SET_BIT (headers, header->index);
*************** verify_loop_structure (void)
*** 1388,1393 ****
--- 1446,1460 ----
  	      err = 1;
  	    }
  	}
+       else if (loop->latch)
+ 	{
+ 	  if (find_edge (loop->latch, loop->header) == NULL)
+ 	    {
+ 	      error ("loop %d%'s latch has no edge to the header", i);
+ 	      err = 1;
+ 	    }
+ 	}
+ 
        if (loop->header->loop_father != loop)
  	{
  	  error ("loop %d%'s header does not belong directly to it", i);
Index: gcc/testsuite/gcc.dg/torture/pr53695.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr53695.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr53695.c	(working copy)
***************
*** 0 ****
--- 1,14 ----
+ /* { dg-do compile } */
+ /* { dg-options "-ftracer" } */
+ 
+ void
+ foo (const void **p)
+ {
+   void *labs[] = { &&l1, &&l2, &&l3 };
+ l1:
+   goto *p++;
+ l2:
+   goto *p;
+ l3:
+   ;
+ }