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

1 files changed, 143 insertions, 0 deletions

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));
+    }
+}
+