[multiple changes]

Fri Jan  7 19:48:04 CET 2000  Jan Hubicka  <jh@suse.cz>
	* sbitmap.c (sbitmap_first_set_bit, sbitmap_last_set_bit): New
	function.
	* sbitmap.h (sbitmap_first_set_bit, sbitmap_last_set_bit): Declare.
	* basic_block.h (FLOW_LOOP_FIRST_BLOCK): New macro.
	(FLOW_LOOP_LAST_BLOCK): Likewise.

2000-01-21  Michael Hayes  <m.hayes@elec.canterbury.ac.nz>

	* basic-block.h (struct loop): New fields 'first' and 'last'.
	* flow.c (flow_loops_find): Compute loop->first and loop->last.
	(flow_loops_dump): Use loop->first to check for NOTE_INSN_LOOP_BEG
	and loop->last to check for NOTE_INSN_LOOP_END.

Fri Jan 28 10:57:58 2000  Jason Eckhardt  <jle@cygnus.com>

	* predict.c (estimate_probability): Use the new FIRST and LAST fields
	of the loop descriptor rather than HEADER and LATCH. Also added
	missing break statements as well making some coding style modifications
	as suggested by Michael Hayes.

From-SVN: r31679

6 files changed, 100 insertions, 14 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8f43f07..fa19a6d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,24 @@
+Fri Jan  7 19:48:04 CET 2000  Jan Hubicka  <jh@suse.cz>
+	* sbitmap.c (sbitmap_first_set_bit, sbitmap_last_set_bit): New
+	function.
+	* sbitmap.h (sbitmap_first_set_bit, sbitmap_last_set_bit): Declare.
+	* basic_block.h (FLOW_LOOP_FIRST_BLOCK): New macro.
+	(FLOW_LOOP_LAST_BLOCK): Likewise.
+
+2000-01-21  Michael Hayes  <m.hayes@elec.canterbury.ac.nz>
+
+	* basic-block.h (struct loop): New fields 'first' and 'last'.
+	* flow.c (flow_loops_find): Compute loop->first and loop->last.
+	(flow_loops_dump): Use loop->first to check for NOTE_INSN_LOOP_BEG
+	and loop->last to check for NOTE_INSN_LOOP_END.
+
+Fri Jan 28 10:57:58 2000  Jason Eckhardt  <jle@cygnus.com>
+
+	* predict.c (estimate_probability): Use the new FIRST and LAST fields
+	of the loop descriptor rather than HEADER and LATCH. Also added
+	missing break statements as well making some coding style modifications
+	as suggested by Michael Hayes.
+
 2000-01-28  Richard Henderson  <rth@cygnus.com>
 
 	* flow.c (find_basic_blocks): Remove do_cleanup argument.
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index a4e970d..57fb2a7f 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -239,6 +239,14 @@ struct loop
   /* Basic block of loop pre-header or NULL if it does not exist.  */
   basic_block pre_header;
 
+  /* The first block in the loop.  This is not necessarily the same as
+     the loop header.  */
+  basic_block first;
+
+  /* The last block in the loop.  This is not necessarily the same as
+     the loop latch.  */
+  basic_block last;
+
   /* Bitmap of blocks contained within the loop.  */
   sbitmap nodes;
 
@@ -318,6 +326,8 @@ struct loop
   int exit_count;
 };
 
+#define FLOW_LOOP_FIRST_BLOCK(loop) sbitmap_first_set_bit ((loop).nodes)
+#define FLOW_LOOP_LAST_BLOCK(loop) sbitmap_last_set_bit ((loop).nodes)
 
 /* Structure to hold CFG information about natural loops within a function.  */
 struct loops
diff --git a/gcc/flow.c b/gcc/flow.c
index 0578bef..73a967b 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -6465,16 +6465,16 @@ flow_loops_dump (loops, file, verbose)
 	{
 	  /* Print diagnostics to compare our concept of a loop with
 	     what the loop notes say.  */
-	  if (GET_CODE (PREV_INSN (loop->header->head)) != NOTE
-	      || NOTE_LINE_NUMBER (PREV_INSN (loop->header->head))
+	  if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
+	      || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
 	      != NOTE_INSN_LOOP_BEG)
 	    fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n", 
-		     INSN_UID (PREV_INSN (loop->header->head)));
-	  if (GET_CODE (NEXT_INSN (loop->latch->end)) != NOTE
-	      || NOTE_LINE_NUMBER (NEXT_INSN (loop->latch->end))
+		     INSN_UID (PREV_INSN (loop->first->head)));
+	  if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
+	      || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
 	      != NOTE_INSN_LOOP_END)
 	    fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
-		     INSN_UID (NEXT_INSN (loop->latch->end)));
+		     INSN_UID (NEXT_INSN (loop->last->end)));
 	}
     }
 
@@ -6975,7 +6975,16 @@ flow_loops_find (loops)
 		  loop->nodes = sbitmap_alloc (n_basic_blocks);
 		  loop->num_nodes
 		    = flow_loop_nodes_find (header, latch, loop->nodes);
-		  
+
+		  /* Compute first and last blocks within the loop.
+		     These are often the same as the loop header and
+		     loop latch respectively, but this is not always
+		     the case.  */
+		  loop->first
+		    = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
+		  loop->last
+		    = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));	
+	  
 		  /* Find edges which exit the loop.  Note that a node
 		     may have several exit edges.  */
 		  loop->num_exits
diff --git a/gcc/predict.c b/gcc/predict.c
index 1846b4a..d8a588f 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -53,7 +53,7 @@
    ??? In the next revision there will be a number of other predictors added
    from the above references. Further, each heuristic will be factored out
    into its own function for clarity (and to facilitate the combination of
-   predictions). */
+   predictions).  */
 
 void
 estimate_probability (loops_info)
@@ -61,13 +61,14 @@ estimate_probability (loops_info)
 {
   int i;
 
-  /* Try to predict out blocks in a loop that are not part of a natural loop */
+  /* Try to predict out blocks in a loop that are not part of a
+     natural loop.  */
   for (i = 0; i < loops_info->num; i++)
     {
       int j;
 
-      for (j = loops_info->array[i].header->index;
-	   j <= loops_info->array[i].latch->index;
+      for (j = loops_info->array[i].first->index;
+	   j <= loops_info->array[i].last->index;
 	   ++j)
 	{
 	  edge e;
@@ -83,17 +84,18 @@ estimate_probability (loops_info)
 		      || ! condjump_p (last_insn) || simplejump_p (last_insn))
 		    continue;
 		  cond = get_condition (last_insn, &earliest);
-		  if (!cond)
+		  if (! cond)
 		    continue;
 		  if (! find_reg_note (last_insn, REG_BR_PROB, 0))
 		    REG_NOTES (last_insn)
-		      = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (REG_BR_PROB_BASE),
+		      = gen_rtx_EXPR_LIST (REG_BR_PROB,
+					   GEN_INT (REG_BR_PROB_BASE),
 					   REG_NOTES (last_insn));
 		}
 	}
     }
 
-  /* Try to predict condjumps using same algorithm as mostly_true_jump */
+  /* Try to predict condjumps using same algorithm as mostly_true_jump.  */
   for (i = 0; i < n_basic_blocks - 1; i++)
     {
       rtx last_insn = BLOCK_END (i);
@@ -114,10 +116,13 @@ estimate_probability (loops_info)
 	case CONST_INT:
 	  /* Unconditional branch.  */
 	  prob = REG_BR_PROB_BASE / 2;
+	  break;
 	case EQ:
 	  prob = REG_BR_PROB_BASE / 10;
+	  break;
 	case NE:
 	  prob = REG_BR_PROB_BASE / 2;
+	  break;
 	case LE:
 	case LT:
 	  if (XEXP (cond, 1) == const0_rtx)
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index dece5e5..0046c57 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -497,6 +497,44 @@ sbitmap_union_of_preds (dst, src, bb)
     }
 }
 
+/* Return number of first bit set in the bitmap, -1 if none.  */
+
+int
+sbitmap_first_set_bit (bmap)
+     sbitmap bmap;
+{
+  int n;
+  EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; });
+  return -1;
+}
+
+/* Return number of last bit set in the bitmap, -1 if none.  */
+
+int
+sbitmap_last_set_bit (bmap)
+     sbitmap bmap;
+{
+  int i;
+  SBITMAP_ELT_TYPE *ptr = bmap->elms;
+  for (i = bmap->size - 1; i >= 0; i--)
+    {
+      SBITMAP_ELT_TYPE word = ptr[i];
+      if (word)
+      {
+        int index = (i + 1) * SBITMAP_ELT_BITS - 1;
+        SBITMAP_ELT_TYPE mask = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
+        while (1)
+          {
+            if (word & mask)
+              return index;
+            mask >>= 1;
+            index--;
+          }
+      }
+    }
+  return -1;
+}
+
 void
 dump_sbitmap (file, bmap)
      FILE *file;
diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
index f459ed0..d506546 100644
--- a/gcc/sbitmap.h
+++ b/gcc/sbitmap.h
@@ -114,6 +114,9 @@ extern int sbitmap_a_and_b PARAMS ((sbitmap, sbitmap, sbitmap));
 extern int sbitmap_a_or_b PARAMS ((sbitmap, sbitmap, sbitmap));
 extern int sbitmap_a_subset_b_p PARAMS ((sbitmap, sbitmap));
 
+extern int sbitmap_first_set_bit PROTO ((sbitmap));
+extern int sbitmap_last_set_bit PROTO ((sbitmap));
+
 struct int_list;
 extern void sbitmap_intersect_of_predsucc PARAMS ((sbitmap, sbitmap *,
 						  int, struct int_list **));