Patch: Installed preliminary branch pred/block reordering code.

Jason Eckhardt jle@cygnus.com
Thu Jan 13 18:08:00 GMT 2000


Reviewed and accepted by Jeff Law and Richard Henderson.

This is a patch in preparation for static branch prediction and basic block
reordering. The new file uses a couple of structure-based branch
predictors similar to those described in the Ball/Larus PLDI '93 paper. More 
heuristics from that paper and others will be added in the next couple weeks
along with the basic block reordering code that utilizes this information.

This is preliminary infrastructure work and the new code is not invoked yet.

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.


Index: Makefile.in
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/Makefile.in,v
retrieving revision 1.811
diff -c -3 -p -r1.811 Makefile.in
*** Makefile.in	2000/01/11 14:58:53	1.811
--- Makefile.in	2000/01/13 19:26:10
*************** OBJS = diagnostic.o \
*** 711,717 ****
   $(end-sanitize-ssa) \
   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
  
  # 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
--- 711,717 ----
   $(end-sanitize-ssa) \
   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 \
!  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
*************** reg-stack.o : reg-stack.c $(CONFIG_H) sy
*** 1719,1724 ****
--- 1719,1727 ----
     $(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 \
Index: basic-block.h
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/basic-block.h,v
retrieving revision 1.52
diff -c -3 -p -r1.52 basic-block.h
*** basic-block.h	2000/01/11 14:58:54	1.52
--- basic-block.h	2000/01/13 19:26:11
*************** extern void compute_available		PROTO ((s
*** 384,387 ****
--- 384,390 ----
  extern rtx emit_block_insn_after	PROTO((rtx, rtx, basic_block));
  extern rtx emit_block_insn_before	PROTO((rtx, rtx, basic_block));
  
+ /* In predict.c */
+ extern void estimate_probability        PROTO ((struct loops *));
+ 
  #endif /* _BASIC_BLOCK_H */






*** /dev/null	Tue May  5 15:32:27 1998
--- predict.c	Thu Jan 13 12:32:56 2000
***************
*** 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));
+     }
+ }
+ 


More information about the Gcc-patches mailing list