* basic-block.h (struct basic_block_def): New field loop_father.

	(BB_VISITED): New flag.
	(struct loop): New field pred, removed field shared.
	(struct loops): New field parray.
	(LOOP_EXITS_DOMS): Removed.
	(flow_loop_tree_node_add, flow_loop_tree_node_remove,
	flow_loop_nested_p, flow_bb_inside_loop_p, get_loop_body,
	dfs_enumerate_from, loop_preheader_edge, loop_latch_edge,
	add_bb_to_loop, remove_bb_from_loops, find_common_loop,
	verify_loop_structure): Declare.
	* cfg.c (entry_exit_blocks): Initialize loop_father field.
	* cfganal.c (dfs_enumerate_from): New function.
	* cfgloop.c (HEAVY_EDGE_RATIO): New constant.
	(flow_loop_entry_edges_find, flow_loop_exit_edges_find,
	flow_loop_nodes_find, flow_loop_level_compute, flow_loop_nested_p,
	flow_loop_dump, flow_loops_dump, flow_loops_free,
	flow_loop_tree_node_add, flow_loop_level_compute,
	flow_loops_level_compute, flow_loop_scan, flow_loops_update,
	flow_loop_outside_edge_p): Modified for new infrastructure.
	(make_forwarder_block, canonicalize_loop_headers, glb_enum_p,
	redirect_edge_with_latch_update, flow_loop_free): New static functions.
	(flow_loop_tree_node_remove, flow_bb_inside_loop_p,
	get_loop_body, add_bb_to_loop, remove_bb_from_loops,
	find_common_loop, verify_loop_structure, loop_latch_edge,
	loop_preheader_edge): New functions.
	(flow_loops_cfg_dump): Do not show dominators, as this information
	does not remain up to date long.
	(flow_loops_find): Store results in new format.
	* predict.c (propagate_freq, estimate_probability,
	estimate_loops_at_level, estimate_bb_frequencies): Use new loop
	infrastructure.


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

1 files changed, 52 insertions, 66 deletions

diff --git a/gcc/predict.c b/gcc/predict.c
index a5131d4a475..c00c86409f3 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -70,7 +70,7 @@ static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
 static void dump_prediction		 PARAMS ((enum br_predictor, int,
 						  basic_block, int));
 static void estimate_loops_at_level	 PARAMS ((struct loop *loop));
-static void propagate_freq		 PARAMS ((basic_block));
+static void propagate_freq		 PARAMS ((struct loop *));
 static void estimate_bb_frequencies	 PARAMS ((struct loops *));
 static void counts_to_freqs		 PARAMS ((void));
 static void process_note_predictions	 PARAMS ((basic_block, int *, int *,
@@ -419,19 +419,23 @@ estimate_probability (loops_info)
 
   /* Try to predict out blocks in a loop that are not part of a
      natural loop.  */
-  for (i = 0; i < loops_info->num; i++)
+  for (i = 1; i < loops_info->num; i++)
     {
+      basic_block bb, *bbs;
+      int j;
       int exits;
-      struct loop *loop = &loops_info->array[i];
+      struct loop *loop = loops_info->parray[i];
 
       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
       exits = loop->num_exits;
 
-      FOR_BB_BETWEEN (bb, loop->first, loop->last->next_bb, next_bb)
-	if (TEST_BIT (loop->nodes, bb->index))
-	  {
-	    int header_found = 0;
-	    edge e;
+      bbs = get_loop_body (loop);
+      for (j = 0; j < loop->num_nodes; j++)
+	{
+	  int header_found = 0;
+	  edge e;
+
+	  bb = bbs[j];
 
 	  /* Bypass loop heuristics on continue statement.  These
 	     statements construct loops via "non-loop" constructs
@@ -440,28 +444,28 @@ estimate_probability (loops_info)
 	  if (predicted_by_p (bb, PRED_CONTINUE))
 	    continue;
 
-	    /* Loop branch heuristics - predict an edge back to a
-	       loop's head as taken.  */
-	    for (e = bb->succ; e; e = e->succ_next)
-	      if (e->dest == loop->header
-		  && e->src == loop->latch)
-		{
-		  header_found = 1;
-		  predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
-		}
+	  /* Loop branch heuristics - predict an edge back to a
+	     loop's head as taken.  */
+	  for (e = bb->succ; e; e = e->succ_next)
+	    if (e->dest == loop->header
+		&& e->src == loop->latch)
+	      {
+		header_found = 1;
+		predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
+	      }
 
-	    /* Loop exit heuristics - predict an edge exiting the loop if the
-	       conditinal has no loop header successors as not taken.  */
-	    if (!header_found)
-	      for (e = bb->succ; e; e = e->succ_next)
-		if (e->dest->index < 0
-		    || !TEST_BIT (loop->nodes, e->dest->index))
-		  predict_edge
-		    (e, PRED_LOOP_EXIT,
-		     (REG_BR_PROB_BASE
-		      - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
-		     / exits);
-	  }
+	  /* Loop exit heuristics - predict an edge exiting the loop if the
+	     conditinal has no loop header successors as not taken.  */
+	  if (!header_found)
+	    for (e = bb->succ; e; e = e->succ_next)
+	      if (e->dest->index < 0
+		  || !flow_bb_inside_loop_p (loop, e->dest))
+		predict_edge
+		  (e, PRED_LOOP_EXIT,
+		   (REG_BR_PROB_BASE
+		    - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
+		   / exits);
+	}
     }
 
   /* Attempt to predict conditional jumps using a number of heuristics.  */
@@ -896,12 +900,13 @@ typedef struct edge_info_def
 #define EDGE_INFO(E)	((edge_info) (E)->aux)
 
 /* Helper function for estimate_bb_frequencies.
-   Propagate the frequencies for loops headed by HEAD.  */
+   Propagate the frequencies for LOOP.  */
 
 static void
-propagate_freq (head)
-     basic_block head;
+propagate_freq (loop)
+     struct loop *loop;
 {
+  basic_block head = loop->header;
   basic_block bb;
   basic_block last;
   edge e;
@@ -1028,41 +1033,28 @@ static void
 estimate_loops_at_level (first_loop)
      struct loop *first_loop;
 {
-  struct loop *l, *loop = first_loop;
+  struct loop *loop;
 
   for (loop = first_loop; loop; loop = loop->next)
     {
-      int n;
       edge e;
+      basic_block *bbs;
+      int i;
 
       estimate_loops_at_level (loop->inner);
-
-      /* Find current loop back edge and mark it.  */
-      for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next)
-	;
-
-      EDGE_INFO (e)->back_edge = 1;
-
-      /* In case the loop header is shared, ensure that it is the last
-	 one sharing the same header, so we avoid redundant work.  */
-      if (loop->shared)
+      
+      if (loop->latch->succ)  /* Do not do this for dummy function loop.  */
 	{
-	  for (l = loop->next; l; l = l->next)
-	    if (l->header == loop->header)
-	      break;
-
-	  if (l)
-	    continue;
-	}
-
-      /* Now merge all nodes of all loops with given header as not visited.  */
-      for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
-	if (loop->header == l->header)
-	  EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
-				     BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
-				     );
-
-      propagate_freq (loop->header);
+	  /* Find current loop back edge and mark it.  */
+	  e = loop_latch_edge (loop);
+	  EDGE_INFO (e)->back_edge = 1;
+       }
+
+      bbs = get_loop_body (loop);
+      for (i = 0; i < loop->num_nodes; i++)
+	BLOCK_INFO (bbs[i])->tovisit = 1;
+      free (bbs);
+      propagate_freq (loop);
     }
 }
 
@@ -1202,12 +1194,6 @@ estimate_bb_frequencies (loops)
          to outermost to examine probabilities for back edges.  */
       estimate_loops_at_level (loops->tree_root);
 
-      /* Now fake loop around whole function to finalize probabilities.  */
-      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
-	BLOCK_INFO (bb)->tovisit = 1;
-
-      propagate_freq (ENTRY_BLOCK_PTR);
-
       memcpy (&freq_max, &real_zero, sizeof (real_zero));
       FOR_EACH_BB (bb)
 	if (REAL_VALUES_LESS