Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0.

These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST.

1 files changed, 271 insertions, 0 deletions

diff --git a/contrib/gcc/bb-reorder.c b/contrib/gcc/bb-reorder.c
new file mode 100644
index 0000000..97ad142
--- /dev/null
+++ b/contrib/gcc/bb-reorder.c
@@ -0,0 +1,271 @@
+/* Basic block reordering routines for the GNU compiler.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+
+   This file is part of GCC.
+
+   GCC 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.
+
+   GCC 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 GCC; see the file COPYING.  If not, write to the Free
+   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+   02111-1307, USA.  */
+
+/* References:
+
+   "Profile Guided Code Positioning"
+   Pettis and Hanson; PLDI '90.
+
+   TODO:
+
+   (1) Consider:
+
+		if (p) goto A;		// predict taken
+		foo ();
+	      A:
+		if (q) goto B;		// predict taken
+		bar ();
+	      B:
+		baz ();
+		return;
+
+       We'll currently reorder this as
+
+		if (!p) goto C;
+	      A:
+		if (!q) goto D;
+	      B:
+		baz ();
+		return;
+	      D:
+		bar ();
+		goto B;
+	      C:
+		foo ();
+		goto A;
+
+       A better ordering is
+
+		if (!p) goto C;
+		if (!q) goto D;
+	      B:
+		baz ();
+		return;
+	      C:
+		foo ();
+		if (q) goto B;
+	      D:
+		bar ();
+		goto B;
+
+       This requires that we be able to duplicate the jump at A, and
+       adjust the graph traversal such that greedy placement doesn't
+       fix D before C is considered.
+
+   (2) Coordinate with shorten_branches to minimize the number of
+       long branches.
+
+   (3) Invent a method by which sufficiently non-predicted code can
+       be moved to either the end of the section or another section
+       entirely.  Some sort of NOTE_INSN note would work fine.
+
+       This completely scroggs all debugging formats, so the user
+       would have to explicitly ask for it.
+*/
+
+#include "config.h"
+#include "system.h"
+#include "tree.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "flags.h"
+#include "output.h"
+#include "cfglayout.h"
+
+/* Local function prototypes.  */
+static void make_reorder_chain		PARAMS ((void));
+static basic_block make_reorder_chain_1	PARAMS ((basic_block, basic_block));
+
+/* Compute an ordering for a subgraph beginning with block BB.  Record the
+   ordering in RBI()->index and chained through RBI()->next.  */
+
+static void
+make_reorder_chain ()
+{
+  basic_block prev = NULL;
+  int nbb_m1 = n_basic_blocks - 1;
+  basic_block next;
+
+  /* Loop until we've placed every block.  */
+  do
+    {
+      int i;
+
+      next = NULL;
+
+      /* Find the next unplaced block.  */
+      /* ??? Get rid of this loop, and track which blocks are not yet
+	 placed more directly, so as to avoid the O(N^2) worst case.
+	 Perhaps keep a doubly-linked list of all to-be-placed blocks;
+	 remove from the list as we place.  The head of that list is
+	 what we're looking for here.  */
+
+      for (i = 0; i <= nbb_m1 && !next; ++i)
+	{
+	  basic_block bb = BASIC_BLOCK (i);
+	  if (! RBI (bb)->visited)
+	    next = bb;
+	}
+      if (next)
+        prev = make_reorder_chain_1 (next, prev);
+    }
+  while (next);
+  RBI (prev)->next = NULL;
+}
+
+/* A helper function for make_reorder_chain.
+
+   We do not follow EH edges, or non-fallthru edges to noreturn blocks.
+   These are assumed to be the error condition and we wish to cluster
+   all of them at the very end of the function for the benefit of cache
+   locality for the rest of the function.
+
+   ??? We could do slightly better by noticing earlier that some subgraph
+   has all paths leading to noreturn functions, but for there to be more
+   than one block in such a subgraph is rare.  */
+
+static basic_block
+make_reorder_chain_1 (bb, prev)
+     basic_block bb;
+     basic_block prev;
+{
+  edge e;
+  basic_block next;
+  rtx note;
+
+  /* Mark this block visited.  */
+  if (prev)
+    {
+ restart:
+      RBI (prev)->next = bb;
+
+      if (rtl_dump_file && prev->index + 1 != bb->index)
+	fprintf (rtl_dump_file, "Reordering block %d after %d\n",
+		 bb->index, prev->index);
+    }
+  else
+    {
+      if (bb->index != 0)
+	abort ();
+    }
+  RBI (bb)->visited = 1;
+  prev = bb;
+
+  if (bb->succ == NULL)
+    return prev;
+
+  /* Find the most probable block.  */
+
+  next = NULL;
+  if (any_condjump_p (bb->end)
+      && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
+    {
+      int taken, probability;
+      edge e_taken, e_fall;
+
+      probability = INTVAL (XEXP (note, 0));
+      taken = probability > REG_BR_PROB_BASE / 2;
+
+      /* Find the normal taken edge and the normal fallthru edge.
+
+	 Note, conditional jumps with other side effects may not
+	 be fully optimized.  In this case it is possible for
+	 the conditional jump to branch to the same location as
+	 the fallthru path.
+
+	 We should probably work to improve optimization of that
+	 case; however, it seems silly not to also deal with such
+	 problems here if they happen to occur.  */
+
+      e_taken = e_fall = NULL;
+      for (e = bb->succ; e ; e = e->succ_next)
+	{
+	  if (e->flags & EDGE_FALLTHRU)
+	    e_fall = e;
+	  else if (! (e->flags & EDGE_EH))
+	    e_taken = e;
+	}
+
+      next = (taken ? e_taken : e_fall)->dest;
+    }
+
+  /* In the absence of a prediction, disturb things as little as possible
+     by selecting the old "next" block from the list of successors.  If
+     there had been a fallthru edge, that will be the one.  */
+  if (! next)
+    {
+      for (e = bb->succ; e ; e = e->succ_next)
+	if (e->dest->index == bb->index + 1)
+	  {
+	    if ((e->flags & EDGE_FALLTHRU)
+	        || (e->dest->succ
+	            && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
+	      next = e->dest;
+	    break;
+	  }
+    }
+
+  /* Make sure we didn't select a silly next block.  */
+  if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
+    next = NULL;
+
+  /* Recurse on the successors.  Unroll the last call, as the normal
+     case is exactly one or two edges, and we can tail recurse.  */
+  for (e = bb->succ; e; e = e->succ_next)
+    if (e->dest != EXIT_BLOCK_PTR
+	&& ! RBI (e->dest)->visited
+	&& e->dest->succ
+	&& ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
+      {
+	if (next)
+	  {
+	    prev = make_reorder_chain_1 (next, prev);
+	    next = RBI (e->dest)->visited ? NULL : e->dest;
+	  }
+	else
+	  next = e->dest;
+      }
+  if (next)
+    {
+      bb = next;
+      goto restart;
+    }
+
+  return prev;
+}
+
+/* Reorder basic blocks.  The main entry point to this file.  */
+
+void
+reorder_basic_blocks ()
+{
+  if (n_basic_blocks <= 1)
+    return;
+
+  cfg_layout_initialize ();
+
+  make_reorder_chain ();
+
+  if (rtl_dump_file)
+    dump_flow_info (rtl_dump_file);
+
+  cfg_layout_finalize ();
+}