* basic-block.h (EDGE_IRREDUCIBLE_LOOP, EDGE_ALL_FLAGS): New.

	* cfg.c (dump_edge_info): Add EDGE_IRREDUCIBLE_LOOP flag dump.
	* cfgloop.c (flow_loop_free): Made global.
	(establish_preds): New static function.
	(flow_loop_tree_node_add): Handle subloops of added loop correctly.
	(get_loop_exit_edges): New.
	(verify_loop_structure): Verify EDGE_IRREDUCIBLE_LOOP flags.
	* cfgloop.h (flow_loop_free, get_loop_exit_edges, unloop): Declare.
	* cfgloopanal.c (mark_irreducible_loops): Mark edges in irreducible
	loops.
	* cfgloopmanip.c (loop_delete_branch_edge): Allow to test for
	removability of an edge.
	(fix_irreducible_loops): New static function.
	(find_path, remove_path): Add ability to remove enclosing loops.
	(unloop): New.
	(copy_bbs, duplicate_loop_to_header_edge): Use EDGE_IRREDUCIBLE_LOOP
	flags.
	* cfgrtl.c (verify_flow_info): Handle EDGE_IRREDUCIBLE_LOOP flag.
	* loop-unroll.c (peel_loops_completely): Do not duplicate loop if
	not neccessary.
	(decide_peel_completely, peel_loops_completely): Allow complete peeling
	of non-duplicable once rolling loops.
	* loop-unswitch.c (unswitch_loop): Update EDGE_IRREDUCIBLE_LOOP flags.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@63864 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 39 insertions, 12 deletions

diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c
index 1c2a57d182c..5e00d43259f 100644
--- a/gcc/cfgloopanal.c
+++ b/gcc/cfgloopanal.c
@@ -819,12 +819,12 @@ simple_loop_p (loops, loop, desc)
   return any;
 }
 
-/* Marks blocks that are part of non-recognized loops; i.e. we throw away
-   all latch edges and mark blocks inside any remaining cycle.  Everything
-   is a bit complicated due to fact we do not want to do this for parts of
-   cycles that only "pass" through some loop -- i.e. for each cycle, we want
-   to mark blocks that belong directly to innermost loop containing the whole
-   cycle.  */
+/* Marks blocks and edges that are part of non-recognized loops; i.e. we
+   throw away all latch edges and mark blocks inside any remaining cycle.
+   Everything is a bit complicated due to fact we do not want to do this
+   for parts of cycles that only "pass" through some loop -- i.e. for
+   each cycle, we want to mark blocks that belong directly to innermost
+   loop containing the whole cycle.  */
 void
 mark_irreducible_loops (loops)
      struct loops *loops;
@@ -832,10 +832,19 @@ mark_irreducible_loops (loops)
   int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
   unsigned i;
   edge **edges, e;
+  edge *estack;
   basic_block act;
   int stack_top, tick, depth;
   struct loop *cloop;
 
+  /* Reset the flags.  */
+  FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+    {
+      act->flags &= ~BB_IRREDUCIBLE_LOOP;
+      for (e = act->succ; e; e = e->succ_next)
+	e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+    }
+
   /* The first last_basic_block + 1 entries are for real blocks (including
      entry); then we have loops->num - 1 fake blocks for loops to that we
      assign edges leading from loops (fake loop 0 is not interesting).  */
@@ -846,6 +855,7 @@ mark_irreducible_loops (loops)
   n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
   edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
   stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
+  estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
 
   /* Create the edge lists.  */
   for (i = 0; i < last_basic_block + loops->num; i++)
@@ -923,7 +933,11 @@ mark_irreducible_loops (loops)
   stack_top = 0;
   for (i = 0; i < loops->num; i++)
     if (loops->parray[i])
-      stack[stack_top++] = loops->parray[i]->header->index + 1;
+      {
+	stack[stack_top] = loops->parray[i]->header->index + 1;
+	estack[stack_top] = NULL;
+	stack_top++;
+      }
 
   while (stack_top)
     {
@@ -941,16 +955,24 @@ mark_irreducible_loops (loops)
 	           : e->dest->index + 1;
           if (closed[sidx])
 	    {
-	      if (mr[sidx] < mr[idx] && !closed[mri[sidx]])
+	      if (!closed[mri[sidx]])
 		{
-		  mr[idx] = mr[sidx];
-		  mri[idx] = mri[sidx];
+		  if (mr[sidx] < mr[idx])
+		    {
+		      mr[idx] = mr[sidx];
+		      mri[idx] = mri[sidx];
+		    }
+
+		  if (mr[sidx] <= dfs_in[idx])
+		    e->flags |= EDGE_IRREDUCIBLE_LOOP;
 		}
 	      continue;
 	    }
 	  if (dfs_in[sidx] < 0)
 	    {
-	      stack[stack_top++] = sidx;
+	      stack[stack_top] = sidx;
+	      estack[stack_top] = e;
+	      stack_top++;
 	      goto next;
 	    }
 	  if (dfs_in[sidx] < mr[idx])
@@ -958,12 +980,14 @@ mark_irreducible_loops (loops)
 	      mr[idx] = dfs_in[sidx];
 	      mri[idx] = sidx;
 	    }
+	  e->flags |= EDGE_IRREDUCIBLE_LOOP;
 	}
 
       /* Return back.  */
       closed[idx] = 1;
+      e = estack[stack_top - 1];
       stack_top--;
-      if (stack_top && dfs_in[stack[stack_top - 1]] >= 0)
+      if (e)
         {
 	  /* Propagate information back.  */
 	  sidx = stack[stack_top - 1];
@@ -972,6 +996,8 @@ mark_irreducible_loops (loops)
 	      mr[sidx] = mr[idx];
 	      mri[sidx] = mri[idx];
 	    }
+	  if (mr[idx] <= dfs_in[sidx])
+	    e->flags |= EDGE_IRREDUCIBLE_LOOP;
 	}
       /* Mark the block if relevant.  */
       if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
@@ -980,6 +1006,7 @@ next:;
     }
 
   free (stack);
+  free (estack);
   free (dfs_in);
   free (closed);
   free (mr);