[PATCH] Fix PR56181, rewrite fix_loop_structure

Richard Biener rguenther@suse.de
Thu Feb 7 11:39:00 GMT 2013


This rewrites fix_loop_structure to be equivalent to loop
detection from scratch via flow_loops_find with re-using
of existing loop tree entries.

This addresses a few shortcomings of fix_loop_structure. First,
as shown by the testcase in PR56181, fix_loop_structure does
not handle loop nesting changes.  Second, fix_loop_structure
does no attempt to discover new loops (such as when an irreducible
region becomes reducible by a CFG manipulation), nor does it
try to detect when a loop becomes no longer a loop (but it relies
on passes to set loop->header to NULL for this).

The patch changes flow_loops_find to work incrementally on an
existing loop tree so that it can be used by fix_loop_structure
(and we avoid duplicating it).  flow_loops_find after the patch
only assumes that basic-block -> loop association is valid
for loop headers in the loop tree and that there are no dead
loops in the loop tree.  The latter assumption is the reason
that the patch makes fix_loop_structure automatically discover
dead loops (RTL cfg-cleanup removes loops without removing them
on g++.dg/torture/pr54838.C for example).

Loop verification now verifies that there are no "dead" loops
in the loop tree.

With this change in place it would be possible to defer all
loop "fixing" to the point an up-to-date loop tree is required
(thus, to loop_optimizer_init).  The patch doesn't go that far
as doing that reduces the amount of loop checking we can
perform and it would require that all passes touching any
of the loop information (even bb<->loop association for headers)
to properly initialize the loop optimizer.  I'm still considering
this option for 4.9 or for 4.8 if other road-blocks for the
current scheme appear.

Note that a side-effect of this patch is that we no longer
regress in the number of discovered loops as compared to
before preserving of loop structures.  This is especially
true for loops introduced by RTL expansion or loops formed
by formerly irreducible regions.

Another side-effect is that fix_loop_structure now provides
an easy way out for passes to not care about loops.  Which
is probably more bad than good.

Loops incrementally removed / discovered are now reported
in the current dump-file in detailed mode, so it should be
possible to grep for such cases and investigate them
(much as we handle the BB / edge counter mismatches).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

If there are no comments I plan to install this tomorrow
(double-ICK to the way IRA does not use current_loops).

Thanks,
Richard.

2013-02-07  Richard Biener  <rguenther@suse.de>

	PR middle-end/56181
	* cfgloop.h (flow_loops_find): Adjust.
	(bb_loop_header_p): Declare.
	* cfgloop.c (bb_loop_header_p): New function split out from ...
	(flow_loops_find): ... here.  Adjust function signature,
	support incremental loop structure update.
	(verify_loop_structure): Cleanup.  Verify a loop is a loop.
	* cfgloopmanip.c (fix_loop_structure): Move ...
	* loop-init.c (fix_loop_structure): ... here.
	(apply_loop_flags): Split out from ...
	(loop_optimizer_init): ... here.
	(fix_loop_structure): Use apply_loop_flags.  Use flow_loops_find
	in incremental mode, only remove dead loops here.
	* ira.c (ira): Adjust.

	* gcc.dg/torture/pr56181.c: New testcase.

Index: gcc/cfgloop.h
===================================================================
*** gcc/cfgloop.h.orig	2013-02-07 10:14:25.000000000 +0100
--- gcc/cfgloop.h	2013-02-07 11:19:55.228983431 +0100
*************** struct GTY (()) loops {
*** 205,211 ****
  };
  
  /* Loop recognition.  */
! extern int flow_loops_find (struct loops *);
  extern void disambiguate_loops_with_multiple_latches (void);
  extern void flow_loops_free (struct loops *);
  extern void flow_loops_dump (FILE *,
--- 205,212 ----
  };
  
  /* Loop recognition.  */
! bool bb_loop_header_p (basic_block);
! extern struct loops *flow_loops_find (struct loops *);
  extern void disambiguate_loops_with_multiple_latches (void);
  extern void flow_loops_free (struct loops *);
  extern void flow_loops_dump (FILE *,
Index: gcc/cfgloop.c
===================================================================
*** gcc/cfgloop.c.orig	2013-02-07 10:14:25.000000000 +0100
--- gcc/cfgloop.c	2013-02-07 11:38:26.168190690 +0100
*************** init_loops_structure (struct loops *loop
*** 359,497 ****
    loops->tree_root = root;
  }
  
  /* Find all the natural loops in the function and save in LOOPS structure and
     recalculate loop_father information in basic block structures.
!    Return the number of natural loops found.  */
  
! int
  flow_loops_find (struct loops *loops)
  {
!   int b;
!   int num_loops;
!   edge e;
!   sbitmap headers;
!   int *dfs_order;
    int *rc_order;
!   basic_block header;
!   basic_block bb;
  
    /* Ensure that the dominators are computed.  */
    calculate_dominance_info (CDI_DOMINATORS);
  
!   /* Taking care of this degenerate case makes the rest of
!      this code simpler.  */
!   if (n_basic_blocks == NUM_FIXED_BLOCKS)
      {
        init_loops_structure (loops, 1);
-       return 1;
      }
  
!   dfs_order = NULL;
!   rc_order = NULL;
  
!   /* Count the number of loop headers.  This should be the
!      same as the number of natural loops.  */
!   headers = sbitmap_alloc (last_basic_block);
!   bitmap_clear (headers);
! 
!   num_loops = 0;
!   FOR_EACH_BB (header)
!     {
!       edge_iterator ei;
  
!       /* If we have an abnormal predecessor, do not consider the
! 	 loop (not worth the problems).  */
!       if (bb_has_abnormal_pred (header))
! 	continue;
  
!       FOR_EACH_EDGE (e, ei, header->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
! 	      && dominated_by_p (CDI_DOMINATORS, latch, header))
  	    {
! 	      /* Shared headers should be eliminated by now.  */
! 	      bitmap_set_bit (headers, header->index);
! 	      num_loops++;
  	    }
  	}
      }
  
!   /* Allocate loop structures.  */
!   init_loops_structure (loops, num_loops + 1);
  
!   /* Find and record information about all the natural loops
!      in the CFG.  */
!   FOR_EACH_BB (bb)
!     bb->loop_father = loops->tree_root;
! 
!   if (num_loops)
      {
!       /* Compute depth first search order of the CFG so that outer
! 	 natural loops will be found before inner natural loops.  */
!       dfs_order = XNEWVEC (int, n_basic_blocks);
!       rc_order = XNEWVEC (int, n_basic_blocks);
!       pre_and_rev_post_order_compute (dfs_order, rc_order, false);
  
!       num_loops = 1;
  
!       for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
  	{
! 	  struct loop *loop;
! 	  edge_iterator ei;
! 
! 	  /* Search the nodes of the CFG in reverse completion order
! 	     so that we can find outer loops first.  */
! 	  if (!bitmap_bit_p (headers, rc_order[b]))
! 	    continue;
! 
! 	  header = BASIC_BLOCK (rc_order[b]);
! 
! 	  loop = alloc_loop ();
! 	  loops->larray->quick_push (loop);
! 
! 	  loop->header = header;
! 	  loop->num = num_loops;
! 	  num_loops++;
! 
! 	  flow_loop_tree_node_add (header->loop_father, loop);
! 	  loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
  
! 	  /* Look for the latch for this header block, if it has just a
! 	     single one.  */
! 	  FOR_EACH_EDGE (e, ei, header->preds)
  	    {
! 	      basic_block latch = e->src;
! 
! 	      if (flow_bb_inside_loop_p (loop, latch))
  		{
! 		  if (loop->latch != NULL)
! 		    {
! 		      /* More than one latch edge.  */
! 		      loop->latch = NULL;
! 		      break;
! 		    }
! 		  loop->latch = latch;
  		}
  	    }
  	}
- 
-       free (dfs_order);
-       free (rc_order);
      }
  
!   sbitmap_free (headers);
  
!   loops->exits = NULL;
!   return loops->larray->length ();
  }
  
  /* Ratio of frequencies of edges so that one of more latch edges is
--- 359,514 ----
    loops->tree_root = root;
  }
  
+ /* Returns whether HEADER is a loop header.  */
+ 
+ bool
+ bb_loop_header_p (basic_block header)
+ {
+   edge_iterator ei;
+   edge e;
+ 
+   /* If we have an abnormal predecessor, do not consider the
+      loop (not worth the problems).  */
+   if (bb_has_abnormal_pred (header))
+     return false;
+ 
+   /* 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.  */
+   FOR_EACH_EDGE (e, ei, header->preds)
+     {
+       basic_block latch = e->src;
+       if (latch != ENTRY_BLOCK_PTR
+ 	  && dominated_by_p (CDI_DOMINATORS, latch, header))
+ 	return true;
+     }
+ 
+   return false;
+ }
+ 
  /* Find all the natural loops in the function and save in LOOPS structure and
     recalculate loop_father information in basic block structures.
!    If LOOPS is non-NULL then the loop structures for already recorded loops
!    will be re-used and their number will not change.  We assume that no
!    stale loops exist in LOOPS.
!    When LOOPS is NULL it is allocated and re-built from scratch.
!    Return the built LOOPS structure.  */
  
! struct loops *
  flow_loops_find (struct loops *loops)
  {
!   bool from_scratch = (loops == NULL);
    int *rc_order;
!   int b;
!   unsigned i;
!   vec<loop_p> larray;
  
    /* Ensure that the dominators are computed.  */
    calculate_dominance_info (CDI_DOMINATORS);
  
!   if (!loops)
      {
+       loops = ggc_alloc_cleared_loops ();
        init_loops_structure (loops, 1);
      }
  
!   /* Ensure that loop exits were released.  */
!   gcc_assert (loops->exits == NULL);
  
!   /* Taking care of this degenerate case makes the rest of
!      this code simpler.  */
!   if (n_basic_blocks == NUM_FIXED_BLOCKS)
!     return loops;
  
!   /* The root loop node contains all basic-blocks.  */
!   loops->tree_root->num_nodes = n_basic_blocks;
  
!   /* Compute depth first search order of the CFG so that outer
!      natural loops will be found before inner natural loops.  */
!   rc_order = XNEWVEC (int, n_basic_blocks);
!   pre_and_rev_post_order_compute (NULL, rc_order, false);
! 
!   /* Gather all loop headers in reverse completion order and allocate
!      loop structures for loops that are not already present.  */
!   larray.create (loops->larray->length());
!   for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
!     {
!       basic_block header = BASIC_BLOCK (rc_order[b]);
!       if (bb_loop_header_p (header))
  	{
! 	  struct loop *loop;
  
! 	  /* The current active loop tree has valid loop-fathers for
! 	     header blocks.  */
! 	  if (!from_scratch
! 	      && header->loop_father->header == header)
! 	    {
! 	      loop = header->loop_father;
! 	      /* If we found an existing loop remove it from the
! 		 loop tree.  It is going to be inserted again
! 		 below.  */
! 	      flow_loop_tree_node_remove (loop);
! 	    }
! 	  else
  	    {
! 	      /* Otherwise allocate a new loop structure for the loop.  */
! 	      loop = alloc_loop ();
! 	      /* ???  We could re-use unused loop slots here.  */
! 	      loop->num = loops->larray->length ();
! 	      vec_safe_push (loops->larray, loop);
! 	      loop->header = header;
! 
! 	      if (!from_scratch
! 		  && dump_file && (dump_flags & TDF_DETAILS))
! 		fprintf (dump_file, "flow_loops_find: discovered new "
! 			 "loop %d with header %d\n",
! 			 loop->num, header->index);
  	    }
+ 	  larray.safe_push (loop);
  	}
+ 
+       /* Make blocks part of the loop root node at start.  */
+       header->loop_father = loops->tree_root;
      }
  
!   free (rc_order);
  
!   /* Now iterate over the loops found, insert them into the loop tree
!      and assign basic-block ownership.  */
!   for (i = 0; i < larray.length (); ++i)
      {
!       struct loop *loop = larray[i];
!       basic_block header = loop->header;
!       edge_iterator ei;
!       edge e;
  
!       flow_loop_tree_node_add (header->loop_father, loop);
!       loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
  
!       /* Look for the latch for this header block, if it has just a
! 	 single one.  */
!       FOR_EACH_EDGE (e, ei, header->preds)
  	{
! 	  basic_block latch = e->src;
  
! 	  if (flow_bb_inside_loop_p (loop, latch))
  	    {
! 	      if (loop->latch != NULL)
  		{
! 		  /* More than one latch edge.  */
! 		  loop->latch = NULL;
! 		  break;
  		}
+ 	      loop->latch = latch;
  	    }
  	}
      }
  
!   larray.release();
  
!   return loops;
  }
  
  /* Ratio of frequencies of edges so that one of more latch edges is
*************** verify_loop_structure (void)
*** 1300,1306 ****
  {
    unsigned *sizes, i, j;
    sbitmap irreds;
!   basic_block *bbs, bb;
    struct loop *loop;
    int err = 0;
    edge e;
--- 1317,1323 ----
  {
    unsigned *sizes, i, j;
    sbitmap irreds;
!   basic_block bb;
    struct loop *loop;
    int err = 0;
    edge e;
*************** verify_loop_structure (void)
*** 1308,1314 ****
    loop_iterator li;
    struct loop_exit *exit, *mexit;
    bool dom_available = dom_info_available_p (CDI_DOMINATORS);
!   sbitmap visited = sbitmap_alloc (last_basic_block);
  
    /* We need up-to-date dominators, compute or verify them.  */
    if (!dom_available)
--- 1325,1331 ----
    loop_iterator li;
    struct loop_exit *exit, *mexit;
    bool dom_available = dom_info_available_p (CDI_DOMINATORS);
!   sbitmap visited;
  
    /* We need up-to-date dominators, compute or verify them.  */
    if (!dom_available)
*************** verify_loop_structure (void)
*** 1337,1364 ****
      }
  
    /* Check get_loop_body.  */
!   FOR_EACH_LOOP (li, loop, 0)
!     {
!       bbs = get_loop_body (loop);
! 
!       for (j = 0; j < loop->num_nodes; j++)
! 	if (!flow_bb_inside_loop_p (loop, bbs[j]))
! 	  {
! 	    error ("bb %d does not belong to loop %d",
! 		   bbs[j]->index, loop->num);
! 	    err = 1;
! 	  }
!       free (bbs);
!     }
    bitmap_clear (visited);
    FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
      {
!       bbs = get_loop_body (loop);
  
        for (j = 0; j < loop->num_nodes; j++)
  	{
  	  bb = bbs[j];
  
  	  /* Ignore this block if it is in an inner loop.  */
  	  if (bitmap_bit_p (visited, bb->index))
  	    continue;
--- 1354,1376 ----
      }
  
    /* Check get_loop_body.  */
!   visited = sbitmap_alloc (last_basic_block);
    bitmap_clear (visited);
    FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
      {
!       basic_block *bbs = get_loop_body (loop);
  
        for (j = 0; j < loop->num_nodes; j++)
  	{
  	  bb = bbs[j];
  
+ 	  if (!flow_bb_inside_loop_p (loop, bb))
+ 	    {
+ 	      error ("bb %d does not belong to loop %d",
+ 		     bb->index, loop->num);
+ 	      err = 1;
+ 	    }
+ 
  	  /* Ignore this block if it is in an inner loop.  */
  	  if (bitmap_bit_p (visited, bb->index))
  	    continue;
*************** verify_loop_structure (void)
*** 1371,1384 ****
--- 1383,1403 ----
  	      err = 1;
  	    }
  	}
+ 
        free (bbs);
      }
+   sbitmap_free (visited);
  
    /* Check headers and latches.  */
    FOR_EACH_LOOP (li, loop, 0)
      {
        i = loop->num;
  
+       if (!bb_loop_header_p (loop->header))
+ 	{
+ 	  error ("loop %d%'s header is not a loop header", i);
+ 	  err = 1;
+ 	}
        if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
  	  && EDGE_COUNT (loop->header->preds) != 2)
  	{
*************** verify_loop_structure (void)
*** 1580,1586 ****
  
    gcc_assert (!err);
  
-   sbitmap_free (visited);
    free (sizes);
    if (!dom_available)
      free_dominance_info (CDI_DOMINATORS);
--- 1599,1604 ----
Index: gcc/loop-init.c
===================================================================
*** gcc/loop-init.c.orig	2013-02-07 10:14:25.000000000 +0100
--- gcc/loop-init.c	2013-02-07 12:07:32.444709386 +0100
*************** along with GCC; see the file COPYING3.
*** 32,68 ****
  #include "ggc.h"
  
  
! /* Initialize loop structures.  This is used by the tree and RTL loop
!    optimizers.  FLAGS specify what properties to compute and/or ensure for
!    loops.  */
  
! void
! loop_optimizer_init (unsigned flags)
  {
-   timevar_push (TV_LOOP_INIT);
-   if (!current_loops)
-     {
-       struct loops *loops = ggc_alloc_cleared_loops ();
- 
-       gcc_assert (!(cfun->curr_properties & PROP_loops));
- 
-       /* Find the loops.  */
- 
-       flow_loops_find (loops);
-       current_loops = loops;
-     }
-   else
-     {
-       gcc_assert (cfun->curr_properties & PROP_loops);
- 
-       /* Ensure that the dominators are computed, like flow_loops_find does.  */
-       calculate_dominance_info (CDI_DOMINATORS);
- 
- #ifdef ENABLE_CHECKING
-       verify_loop_structure ();
- #endif
-     }
- 
    if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
      {
        /* If the loops may have multiple latches, we cannot canonicalize
--- 32,42 ----
  #include "ggc.h"
  
  
! /* Apply FLAGS to the loop state.  */
  
! static void
! apply_loop_flags (unsigned flags)
  {
    if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
      {
        /* If the loops may have multiple latches, we cannot canonicalize
*************** loop_optimizer_init (unsigned flags)
*** 97,102 ****
--- 71,108 ----
  
    if (flags & LOOPS_HAVE_RECORDED_EXITS)
      record_loop_exits ();
+ }
+ 
+ /* Initialize loop structures.  This is used by the tree and RTL loop
+    optimizers.  FLAGS specify what properties to compute and/or ensure for
+    loops.  */
+ 
+ void
+ loop_optimizer_init (unsigned flags)
+ {
+   timevar_push (TV_LOOP_INIT);
+ 
+   if (!current_loops)
+     {
+       gcc_assert (!(cfun->curr_properties & PROP_loops));
+ 
+       /* Find the loops.  */
+       current_loops = flow_loops_find (NULL);
+     }
+   else
+     {
+       gcc_assert (cfun->curr_properties & PROP_loops);
+ 
+       /* Ensure that the dominators are computed, like flow_loops_find does.  */
+       calculate_dominance_info (CDI_DOMINATORS);
+ 
+ #ifdef ENABLE_CHECKING
+       verify_loop_structure ();
+ #endif
+     }
+ 
+   /* Apply flags to loops.  */
+   apply_loop_flags (flags);
  
    /* Dump loops.  */
    flow_loops_dump (dump_file, NULL, 1);
*************** loop_fini_done:
*** 157,162 ****
--- 163,259 ----
    timevar_pop (TV_LOOP_FINI);
  }
  
+ /* The structure of loops might have changed.  Some loops might get removed
+    (and their headers and latches were set to NULL), loop exists might get
+    removed (thus the loop nesting may be wrong), and some blocks and edges
+    were changed (so the information about bb --> loop mapping does not have
+    to be correct).  But still for the remaining loops the header dominates
+    the latch, and loops did not get new subloops (new loops might possibly
+    get created, but we are not interested in them).  Fix up the mess.
+ 
+    If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
+    marked in it.  */
+ 
+ void
+ fix_loop_structure (bitmap changed_bbs)
+ {
+   basic_block bb;
+   int record_exits = 0;
+   loop_iterator li;
+   struct loop *loop;
+ 
+   timevar_push (TV_LOOP_INIT);
+ 
+   /* We need exact and fast dominance info to be available.  */
+   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
+ 
+   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+     {
+       release_recorded_exits ();
+       record_exits = LOOPS_HAVE_RECORDED_EXITS;
+     }
+ 
+   /* Remember the depth of the blocks in the loop hierarchy, so that we can
+      recognize blocks whose loop nesting relationship has changed.  */
+   if (changed_bbs)
+     FOR_EACH_BB (bb)
+       bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
+ 
+   /* Remove the dead loops from structures.  We start from the innermost
+      loops, so that when we remove the loops, we know that the loops inside
+      are preserved, and do not waste time relinking loops that will be
+      removed later.  */
+   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+     {
+       /* Detect the case that the loop is no longer present even though
+          it wasn't marked for removal.
+ 	 ???  If we do that we can get away with not marking loops for
+ 	 removal at all.  And possibly avoid some spurious removals.  */
+       if (loop->header
+ 	  && bb_loop_header_p (loop->header))
+ 	continue;
+ 
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
+ 		 loop->num);
+ 
+       while (loop->inner)
+ 	{
+ 	  struct loop *ploop = loop->inner;
+ 	  flow_loop_tree_node_remove (ploop);
+ 	  flow_loop_tree_node_add (loop_outer (loop), ploop);
+ 	}
+ 
+       /* Remove the loop and free its data.  */
+       delete_loop (loop);
+     }
+ 
+   /* Re-compute loop structure in-place.  */
+   flow_loops_find (current_loops);
+ 
+   /* Mark the blocks whose loop has changed.  */
+   if (changed_bbs)
+     {
+       FOR_EACH_BB (bb)
+ 	{
+ 	  if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
+ 	    bitmap_set_bit (changed_bbs, bb->index);
+ 
+     	  bb->aux = NULL;
+ 	}
+     }
+ 
+   loops_state_clear (LOOPS_NEED_FIXUP);
+ 
+   /* Apply flags to loops.  */
+   apply_loop_flags (current_loops->state | record_exits);
+ 
+ #ifdef ENABLE_CHECKING
+   verify_loop_structure ();
+ #endif
+ 
+   timevar_pop (TV_LOOP_INIT);
+ }
  
  /* Gate for the RTL loop superpass.  The actual passes are subpasses.
     See passes.c for more on that.  */
Index: gcc/cfgloopmanip.c
===================================================================
*** gcc/cfgloopmanip.c.orig	2013-02-07 10:14:25.000000000 +0100
--- gcc/cfgloopmanip.c	2013-02-07 10:14:56.066414887 +0100
*************** loop_version (struct loop *loop,
*** 1760,1918 ****
  
    return nloop;
  }
- 
- /* The structure of loops might have changed.  Some loops might get removed
-    (and their headers and latches were set to NULL), loop exists might get
-    removed (thus the loop nesting may be wrong), and some blocks and edges
-    were changed (so the information about bb --> loop mapping does not have
-    to be correct).  But still for the remaining loops the header dominates
-    the latch, and loops did not get new subloops (new loops might possibly
-    get created, but we are not interested in them).  Fix up the mess.
- 
-    If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
-    marked in it.  */
- 
- void
- fix_loop_structure (bitmap changed_bbs)
- {
-   basic_block bb;
-   struct loop *loop, *ploop;
-   loop_iterator li;
-   bool record_exits = false;
-   struct loop **superloop = XNEWVEC (struct loop *, number_of_loops ());
- 
-   /* We need exact and fast dominance info to be available.  */
-   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
- 
-   /* Remove the old bb -> loop mapping.  Remember the depth of the blocks in
-      the loop hierarchy, so that we can recognize blocks whose loop nesting
-      relationship has changed.  */
-   FOR_EACH_BB (bb)
-     {
-       if (changed_bbs)
- 	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
-       bb->loop_father = current_loops->tree_root;
-     }
- 
-   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
-     {
-       release_recorded_exits ();
-       record_exits = true;
-     }
- 
-   /* First re-compute loop latches.  */
-   FOR_EACH_LOOP (li, loop, 0)
-     {
-       edge_iterator ei;
-       edge e, first_latch = NULL, latch = NULL;
- 
-       if (!loop->header)
- 	continue;
- 
-       FOR_EACH_EDGE (e, ei, loop->header->preds)
- 	if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
- 	  {
- 	    if (!first_latch)
- 	      first_latch = latch = e;
- 	    else
- 	      {
- 		latch = NULL;
- 		break;
- 	      }
- 	  }
-       /* If there was no latch, schedule the loop for removal.  */
-       if (!first_latch)
- 	loop->header = NULL;
-       /* If there was a single latch, record it.  */
-       else if (latch)
- 	loop->latch = latch->src;
-       /* Otherwise there are multiple latches which are eventually
-          disambiguated below.  */
-       else
- 	loop->latch = NULL;
-     }
- 
-   /* Remove the dead loops from structures.  We start from the innermost
-      loops, so that when we remove the loops, we know that the loops inside
-      are preserved, and do not waste time relinking loops that will be
-      removed later.  */
-   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
-     {
-       if (loop->header)
- 	continue;
- 
-       while (loop->inner)
- 	{
- 	  ploop = loop->inner;
- 	  flow_loop_tree_node_remove (ploop);
- 	  flow_loop_tree_node_add (loop_outer (loop), ploop);
- 	}
- 
-       /* Remove the loop and free its data.  */
-       delete_loop (loop);
-     }
- 
-   /* Rescan the bodies of loops, starting from the outermost ones.  We assume
-      that no optimization interchanges the order of the loops, i.e., it cannot
-      happen that L1 was superloop of L2 before and it is subloop of L2 now
-      (without explicitly updating loop information).  At the same time, we also
-      determine the new loop structure.  */
-   current_loops->tree_root->num_nodes = n_basic_blocks;
-   FOR_EACH_LOOP (li, loop, 0)
-     {
-       superloop[loop->num] = loop->header->loop_father;
-       loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
-     }
- 
-   /* Now fix the loop nesting.  */
-   FOR_EACH_LOOP (li, loop, 0)
-     {
-       ploop = superloop[loop->num];
-       if (ploop != loop_outer (loop))
- 	{
- 	  flow_loop_tree_node_remove (loop);
- 	  flow_loop_tree_node_add (ploop, loop);
- 	}
-     }
-   free (superloop);
- 
-   /* Mark the blocks whose loop has changed.  */
-   if (changed_bbs)
-     {
-       FOR_EACH_BB (bb)
- 	{
- 	  if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
- 	    bitmap_set_bit (changed_bbs, bb->index);
- 
-     	  bb->aux = NULL;
- 	}
-     }
- 
-   if (!loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES))
-     disambiguate_loops_with_multiple_latches ();
- 
-   if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
-     {
-       int cp_flags = CP_SIMPLE_PREHEADERS;
- 
-       if (loops_state_satisfies_p (LOOPS_HAVE_FALLTHRU_PREHEADERS))
- 	cp_flags |= CP_FALLTHRU_PREHEADERS;
- 
-       create_preheaders (cp_flags);
-     }
- 
-   if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
-     force_single_succ_latches ();
- 
-   if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
-     mark_irreducible_loops ();
- 
-   if (record_exits)
-     record_loop_exits ();
- 
-   loops_state_clear (LOOPS_NEED_FIXUP);
- 
- #ifdef ENABLE_CHECKING
-   verify_loop_structure ();
- #endif
- }
--- 1760,1762 ----
Index: gcc/ira.c
===================================================================
*** gcc/ira.c.orig	2013-02-07 10:14:25.000000000 +0100
--- gcc/ira.c	2013-02-07 10:14:56.067414898 +0100
*************** ira (FILE *f)
*** 4465,4471 ****
    ira_assert (current_loops == NULL);
    if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
      {
!       flow_loops_find (&ira_loops);
        current_loops = &ira_loops;
        record_loop_exits ();
      }
--- 4465,4471 ----
    ira_assert (current_loops == NULL);
    if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
      {
!       ira_loops = *flow_loops_find (NULL);
        current_loops = &ira_loops;
        record_loop_exits ();
      }
*************** ira (FILE *f)
*** 4528,4534 ****
  	     by updating the loop tree incrementally?  */
  	  release_recorded_exits ();
  	  flow_loops_free (&ira_loops);
! 	  flow_loops_find (&ira_loops);
  	  current_loops = &ira_loops;
  	  record_loop_exits ();
  
--- 4528,4534 ----
  	     by updating the loop tree incrementally?  */
  	  release_recorded_exits ();
  	  flow_loops_free (&ira_loops);
! 	  ira_loops = *flow_loops_find (NULL);
  	  current_loops = &ira_loops;
  	  record_loop_exits ();
  
Index: gcc/testsuite/gcc.dg/torture/pr56181.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/torture/pr56181.c	2013-02-07 11:53:36.051181886 +0100
***************
*** 0 ****
--- 1,25 ----
+ /* { dg-do compile } */
+ /* { dg-options "-ftracer" } */
+ 
+ int a, b;
+ 
+ void f(void)
+ {
+   if(a++)
+     {
+       for(a = 0; a < 1;)
+ 	{
+ 	  for(b = 0; b < 1; b++)
+ 	    {
+ 	      while(a++ < 0);
+ lbl:
+ 	      ;
+ 	    }
+ 
+ 	  if(a)
+ 	    goto lbl;
+ 	}
+ 
+       goto lbl;
+     }
+ }



More information about the Gcc-patches mailing list