Thu Jan 13 14:46:03 2000 Jason Eckhardt <jle@cygnus.com>

                          Stan Cox  <scox@cygnus.com>

	* predict.c: New file. Preliminary infrastructure work for static
	branch prediction and basic block reordering.
	* basic-block.h: Add prototype for estimate_probability.
	* Makefile.in: Add rules for predict.o.


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

4 files changed, 158 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d1ff7358ef6..31527b57fe5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+Thu Jan 13 14:46:03 2000  Jason Eckhardt  <jle@cygnus.com>
+                          Stan Cox  <scox@cygnus.com>
+
+	* predict.c: New file. Preliminary infrastructure work for static
+	branch prediction and basic block reordering.
+	* basic-block.h: Add prototype for estimate_probability.
+	* Makefile.in: Add rules for predict.o.
+
 2000-01-13  Jason Merrill  <jason@yorick.cygnus.com>
 
 	* fixincludes (va_list): Use __not_va_list__ for the dummy.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5f50b6babea..bd7476402e5 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -673,7 +673,7 @@ OBJS = diagnostic.o \
  insn-opinit.o insn-recog.o insn-extract.o insn-output.o insn-emit.o lcm.o \
  profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \
  mbchar.o dyn-string.o splay-tree.o graph.o sbitmap.o resource.o hash.o \
- lists.o ggc-common.o $(GGC) simplify-rtx.o
+ predict.o lists.o ggc-common.o $(GGC) simplify-rtx.o
 
 # GEN files are listed separately, so they can be built before doing parallel
 #  makes for cc1 or cc1plus.  Otherwise sequent parallel make attempts to load
@@ -1620,6 +1620,9 @@ reg-stack.o : reg-stack.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) $(RECOG_H) \
    $(REGS_H) hard-reg-set.h flags.h insn-config.h insn-flags.h toplev.h \
    varray.h function.h
 dyn-string.o: dyn-string.c dyn-string.h $(CONFIG_H) system.h
+predict.o: predict.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
+   insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \
+   $(RECOG_H) insn-flags.h function.h except.h expr.h
 lists.o: lists.c $(CONFIG_H) system.h toplev.h $(RTL_H) ggc.h
 
 $(out_object_file): $(out_file) $(CONFIG_H) $(TREE_H) ggc.h \
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index d8774a279c3..0b732f67425 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -384,4 +384,7 @@ extern void compute_available		PARAMS ((sbitmap *, sbitmap *,
 extern rtx emit_block_insn_after	PARAMS ((rtx, rtx, basic_block));
 extern rtx emit_block_insn_before	PARAMS ((rtx, rtx, basic_block));
 
+/* In predict.c */
+extern void estimate_probability        PARAMS ((struct loops *));
+
 #endif /* _BASIC_BLOCK_H */
diff --git a/gcc/predict.c b/gcc/predict.c
new file mode 100644
index 00000000000..1846b4a8f7c
--- /dev/null
+++ b/gcc/predict.c
@@ -0,0 +1,143 @@
+/* Branch prediction routines for the GNU compiler.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+
+   This file is part of GNU CC.
+
+   GNU CC is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU CC is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GNU CC; see the file COPYING.  If not, write to
+   the Free Software Foundation, 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+/* References:
+
+   [1] "Branch Prediction for Free"
+       Ball and Larus; PLDI '93.
+   [2] "Static Branch Frequency and Program Profile Analysis"
+       Wu and Larus; MICRO-27.
+   [3] "Corpus-based Static Branch Prediction"
+       Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.
+*/
+
+
+#include "config.h"
+#include "system.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "basic-block.h"
+#include "insn-config.h"
+#include "regs.h"
+#include "hard-reg-set.h"
+#include "flags.h"
+#include "output.h"
+#include "function.h"
+#include "except.h"
+#include "toplev.h"
+#include "recog.h"
+#include "insn-flags.h"
+#include "expr.h"
+
+
+
+/* Statically estimate the probability that a branch will be taken.
+   ??? 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). */
+
+void
+estimate_probability (loops_info)
+     struct loops *loops_info;
+{
+  int i;
+
+  /* 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;
+	   ++j)
+	{
+	  edge e;
+	  
+	  if (! TEST_BIT (loops_info->array[i].nodes, j))
+	    for (e = BASIC_BLOCK(j)->pred; e; e = e->pred_next)
+	      if (TEST_BIT (loops_info->array[i].nodes, e->src->index))
+		{
+		  rtx last_insn = BLOCK_END (e->src->index);
+		  rtx cond, earliest;
+
+		  if (GET_CODE (last_insn) != JUMP_INSN
+		      || ! condjump_p (last_insn) || simplejump_p (last_insn))
+		    continue;
+		  cond = get_condition (last_insn, &earliest);
+		  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),
+					   REG_NOTES (last_insn));
+		}
+	}
+    }
+
+  /* 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);
+      rtx cond, earliest;
+      int prob = 0;
+
+      if (GET_CODE (last_insn) != JUMP_INSN
+	  || ! condjump_p (last_insn) || simplejump_p (last_insn))
+	continue;
+      cond = get_condition (last_insn, &earliest);
+      if (! cond)
+	continue;
+      /* EQ tests are usually false and NE tests are usually true.  Also,
+	 most quantities are positive, so we can make the appropriate guesses
+	 about signed comparisons against zero.  */
+      switch (GET_CODE (cond))
+	{
+	case CONST_INT:
+	  /* Unconditional branch.  */
+	  prob = REG_BR_PROB_BASE / 2;
+	case EQ:
+	  prob = REG_BR_PROB_BASE / 10;
+	case NE:
+	  prob = REG_BR_PROB_BASE / 2;
+	case LE:
+	case LT:
+	  if (XEXP (cond, 1) == const0_rtx)
+	    prob = REG_BR_PROB_BASE / 10;
+	  break;
+	case GE:
+	case GT:
+	  if (XEXP (cond, 1) == const0_rtx
+	      || (GET_CODE (XEXP (cond, 1)) == CONST_INT
+		  && INTVAL (XEXP (cond, 1)) == -1))
+	    prob = REG_BR_PROB_BASE / 2;
+	  break;
+
+	default:
+	  prob = 0;
+	}
+      if (! find_reg_note (last_insn, REG_BR_PROB, 0))
+	REG_NOTES (last_insn)
+	  = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
+			       REG_NOTES (last_insn));
+    }
+}
+