Patch for finer grained loop discovery

[Michael Hayes <mhayes at redhat dot com>]

This patch here allows for loop information to be collected on a per
loop basis to avoid unnecessary computation.

2001-01-08  Michael Hayes  <mhayes@redhat.com>

	* flow.c (flow_loop_scan): Break out of ...
	(flow_loops_find) ... here.
	* basic-block.h (flow_loop_scan): New.
	(LOOP_ENTRY_EDGES, LOOP_EXIT_EDGES): Add.
	(LOOP_EDGES, LOOP_EXITS_DOMS, LOOP_ALL): Redefine.

Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.364
diff -c -3 -p -r1.364 flow.c
*** flow.c	2001/01/02 07:00:47	1.364
--- flow.c	2001/01/08 01:35:48
*************** flow_loops_level_compute (loops)
*** 8125,8130 ****
--- 8125,8194 ----
  }
  
  
+ /* Scan a single natural loop specified by LOOP collecting information
+    about it specified by FLAGS.  */
+ 
+ int
+ flow_loop_scan (loops, loop, flags)
+      struct loops *loops;
+      struct loop *loop;
+      int flags;
+ {
+   /* Determine prerequisites.  */
+   if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
+     flags |= LOOP_EXIT_EDGES;
+ 
+   if (flags & LOOP_ENTRY_EDGES)
+     {
+       /* Find edges which enter the loop header.
+ 	 Note that the entry edges should only
+ 	 enter the header of a natural loop.  */
+       loop->num_entries
+ 	= flow_loop_entry_edges_find (loop->header,
+ 				      loop->nodes,
+ 				      &loop->entry_edges);
+     }
+ 
+   if (flags & LOOP_EXIT_EDGES)
+     {
+       /* Find edges which exit the loop.  */
+       loop->num_exits
+ 	= flow_loop_exit_edges_find (loop->nodes,
+ 				     &loop->exit_edges);
+     }
+ 
+   if (flags & LOOP_EXITS_DOMS)
+     {
+       int j;
+ 
+       /* Determine which loop nodes dominate all the exits
+ 	 of the loop.  */
+       loop->exits_doms = sbitmap_alloc (n_basic_blocks);
+       sbitmap_copy (loop->exits_doms, loop->nodes);
+       for (j = 0; j < loop->num_exits; j++)
+ 	sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
+ 			 loops->cfg.dom[loop->exit_edges[j]->src->index]);
+       
+       /* The header of a natural loop must dominate
+ 	 all exits.  */
+       if (! TEST_BIT (loop->exits_doms, loop->header->index))
+ 	abort ();
+     }
+   
+   if (flags & LOOP_PRE_HEADER)
+     {
+       /* Look to see if the loop has a pre-header node.  */
+       loop->pre_header
+ 	= flow_loop_pre_header_find (loop->header, loops->cfg.dom);
+ 
+       /* Find the blocks within the extended basic block of
+ 	 the loop pre-header.  */
+       flow_loop_pre_header_scan (loop);
+     }
+   return 1;
+ }
+ 
+ 
  /* Find all the natural loops in the function and save in LOOPS structure
     and recalculate loop_depth information in basic block structures.
     FLAGS controls which loop information is collected.
*************** flow_loops_find (loops, flags)
*** 8201,8206 ****
--- 8265,8275 ----
        rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
        flow_depth_first_order_compute (dfs_order, rc_order);
  
+       /* Save CFG derived information to avoid recomputing it.  */
+       loops->cfg.dom = dom;
+       loops->cfg.dfs_order = dfs_order;
+       loops->cfg.rc_order = rc_order;
+ 
        /* Allocate loop structures.  */
        loops->array
  	= (struct loop *) xcalloc (num_loops, sizeof (struct loop));
*************** flow_loops_find (loops, flags)
*** 8252,8258 ****
        for (i = 0; i < num_loops; i++)
  	{
  	  struct loop *loop = &loops->array[i];
- 	  int j;
  
  	  /* Keep track of blocks that are loop headers so
  	     that we can tell which loops should be merged.  */
--- 8321,8326 ----
*************** flow_loops_find (loops, flags)
*** 8274,8316 ****
  	  loop->last
  	    = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
  
! 	  if (flags & LOOP_EDGES)
! 	    {
! 	      /* Find edges which enter the loop header.
! 		 Note that the entry edges should only
! 		 enter the header of a natural loop.  */
! 	      loop->num_entries
! 		= flow_loop_entry_edges_find (loop->header,
! 					      loop->nodes,
! 					      &loop->entry_edges);
! 
! 	      /* Find edges which exit the loop.  */
! 	      loop->num_exits
! 		= flow_loop_exit_edges_find (loop->nodes,
! 					     &loop->exit_edges);
! 
! 	      /* Determine which loop nodes dominate all the exits
! 		 of the loop.  */
! 	      loop->exits_doms = sbitmap_alloc (n_basic_blocks);
! 	      sbitmap_copy (loop->exits_doms, loop->nodes);
! 	      for (j = 0; j < loop->num_exits; j++)
! 		sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
! 				 dom[loop->exit_edges[j]->src->index]);
! 
! 	      /* The header of a natural loop must dominate
! 		 all exits.  */
! 	      if (! TEST_BIT (loop->exits_doms, loop->header->index))
! 		abort ();
! 	    }
! 
! 	  if (flags & LOOP_PRE_HEADER)
! 	    {
! 	      /* Look to see if the loop has a pre-header node.  */
! 	      loop->pre_header
! 		= flow_loop_pre_header_find (loop->header, dom);
! 
! 	      flow_loop_pre_header_scan (loop);
! 	    }
  	}
  
        /* Natural loops with shared headers may either be disjoint or
--- 8342,8348 ----
  	  loop->last
  	    = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
  
! 	  flow_loop_scan (loops, loop, flags);
  	}
  
        /* Natural loops with shared headers may either be disjoint or
*************** flow_loops_find (loops, flags)
*** 8325,8335 ****
      }
  
    loops->num = num_loops;
- 
-   /* Save CFG derived information to avoid recomputing it.  */
-   loops->cfg.dom = dom;
-   loops->cfg.dfs_order = dfs_order;
-   loops->cfg.rc_order = rc_order;
  
    /* Build the loop hierarchy tree.  */
    flow_loops_tree_build (loops);
--- 8357,8362 ----
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.83
diff -c -3 -p -r1.83 basic-block.h
*** basic-block.h	2000/12/29 17:52:57	1.83
--- basic-block.h	2001/01/08 01:35:49
*************** extern void flow_loops_dump PARAMS ((con
*** 425,430 ****
--- 425,431 ----
  extern void flow_loop_dump PARAMS ((const struct loop *, FILE *,
  				    void (*)(const struct loop *,
  					     FILE *, int), int));
+ extern int flow_loop_scan PARAMS ((struct loops *, struct loop *, int));
  
  /* This structure maintains an edge list vector.  */
  struct edge_list 
*************** enum update_life_extent
*** 482,490 ****
  
  #define LOOP_TREE		1 	/* Build loop hierarchy tree.  */
  #define LOOP_PRE_HEADER		2	/* Analyse loop pre-header.  */
! #define LOOP_EDGES		4 	/* Find entry and exit edges.  */
! #define LOOP_EXITS_DOMS		8 	/* Find nodes that dom. all exits.  */
! #define LOOP_ALL	       15 	/* All of the above  */
  
  extern void life_analysis	PARAMS ((rtx, FILE *, int));
  extern void update_life_info	PARAMS ((sbitmap, enum update_life_extent,
--- 483,493 ----
  
  #define LOOP_TREE		1 	/* Build loop hierarchy tree.  */
  #define LOOP_PRE_HEADER		2	/* Analyse loop pre-header.  */
! #define LOOP_ENTRY_EDGES	4 	/* Find entry edges.  */
! #define LOOP_EXIT_EDGES		8 	/* Find exit edges.  */
! #define LOOP_EDGES		(LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
! #define LOOP_EXITS_DOMS	       16 	/* Find nodes that dom. all exits.  */
! #define LOOP_ALL	       31 	/* All of the above  */
  
  extern void life_analysis	PARAMS ((rtx, FILE *, int));
  extern void update_life_info	PARAMS ((sbitmap, enum update_life_extent,