Merge tree-ssa-20020619-branch into mainline.

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

1 files changed, 424 insertions, 0 deletions

diff --git a/gcc/rtl-profile.c b/gcc/rtl-profile.c
new file mode 100644
index 00000000000..a53a00464a9
--- /dev/null
+++ b/gcc/rtl-profile.c
@@ -0,0 +1,424 @@
+/* Calculate branch probabilities, and basic block execution counts.
+   Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
+   2000, 2001, 2002, 2003  Free Software Foundation, Inc.
+   Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
+   based on some ideas from Dain Samples of UC Berkeley.
+   Further mangling by Bob Manson, Cygnus Support.
+
+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.  */
+
+/* Generate basic block profile instrumentation and auxiliary files.
+   Profile generation is optimized, so that not all arcs in the basic
+   block graph need instrumenting. First, the BB graph is closed with
+   one entry (function start), and one exit (function exit).  Any
+   ABNORMAL_EDGE cannot be instrumented (because there is no control
+   path to place the code). We close the graph by inserting fake
+   EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
+   edges that do not go to the exit_block. We ignore such abnormal
+   edges.  Naturally these fake edges are never directly traversed,
+   and so *cannot* be directly instrumented.  Some other graph
+   massaging is done. To optimize the instrumentation we generate the
+   BB minimal span tree, only edges that are not on the span tree
+   (plus the entry point) need instrumenting. From that information
+   all other edge counts can be deduced.  By construction all fake
+   edges must be on the spanning tree. We also attempt to place
+   EDGE_CRITICAL edges on the spanning tree.
+
+   The auxiliary file generated is <dumpbase>.bbg. The format is
+   described in full in gcov-io.h.  */
+
+/* ??? Register allocation should use basic block execution counts to
+   give preference to the most commonly executed blocks.  */
+
+/* ??? Should calculate branch probabilities before instrumenting code, since
+   then we can use arc counts to help decide which arcs to instrument.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "flags.h"
+#include "output.h"
+#include "regs.h"
+#include "expr.h"
+#include "function.h"
+#include "toplev.h"
+#include "coverage.h"
+#include "value-prof.h"
+#include "tree.h"
+
+/* Output instructions as RTL to increment the edge execution count.  */
+
+static void
+rtl_gen_edge_profiler (int edgeno, edge e)
+{
+  rtx ref = rtl_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
+  rtx tmp;
+  enum machine_mode mode = GET_MODE (ref);
+  rtx sequence;
+
+  start_sequence ();
+  ref = validize_mem (ref);
+
+  tmp = expand_simple_binop (mode, PLUS, ref, const1_rtx,
+			     ref, 0, OPTAB_WIDEN);
+
+  if (tmp != ref)
+    emit_move_insn (copy_rtx (ref), tmp);
+
+  sequence = get_insns ();
+  end_sequence ();
+  insert_insn_on_edge (sequence, e);
+  rebuild_jump_labels (e->insns.r);
+}
+
+/* Output instructions as RTL to increment the interval histogram counter.
+   VALUE is the expression whose value is profiled.  TAG is the tag of the
+   section for counters, BASE is offset of the counter position.  */
+
+static void
+rtl_gen_interval_profiler (struct histogram_value *value, unsigned tag,
+		       unsigned base)
+{
+  unsigned gcov_size = tree_low_cst (TYPE_SIZE (GCOV_TYPE_NODE), 1);
+  enum machine_mode mode = mode_for_size (gcov_size, MODE_INT, 0);
+  rtx mem_ref, tmp, tmp1, mr, val;
+  rtx sequence;
+  rtx more_label = gen_label_rtx ();
+  rtx less_label = gen_label_rtx ();
+  rtx end_of_code_label = gen_label_rtx ();
+  int per_counter = gcov_size / BITS_PER_UNIT;
+  edge e = split_block (BLOCK_FOR_INSN ((rtx)value->insn),
+		   PREV_INSN ((rtx)value->insn));
+
+  start_sequence ();
+
+  if (value->seq)
+    emit_insn (value->seq);
+
+  mr = gen_reg_rtx (Pmode);
+
+  tmp = rtl_coverage_counter_ref (tag, base);
+  tmp = force_reg (Pmode, XEXP (tmp, 0));
+
+  val = expand_simple_binop (value->mode, MINUS,
+			     copy_rtx (value->value),
+			     GEN_INT (value->hdata.intvl.int_start),
+			     NULL_RTX, 0, OPTAB_WIDEN);
+
+  if (value->hdata.intvl.may_be_more)
+    do_compare_rtx_and_jump (copy_rtx (val), GEN_INT (value->hdata.intvl.steps),
+			     GE, 0, value->mode, NULL_RTX, NULL_RTX, more_label);
+  if (value->hdata.intvl.may_be_less)
+    do_compare_rtx_and_jump (copy_rtx (val), const0_rtx, LT, 0, value->mode,
+			     NULL_RTX, NULL_RTX, less_label);
+
+  /* We are in range.  */
+  tmp1 = expand_simple_binop (value->mode, MULT,
+			      copy_rtx (val), GEN_INT (per_counter),
+			      NULL_RTX, 0, OPTAB_WIDEN);
+  tmp1 = expand_simple_binop (Pmode, PLUS, copy_rtx (tmp), tmp1, mr,
+			      0, OPTAB_WIDEN);
+  if (tmp1 != mr)
+    emit_move_insn (copy_rtx (mr), tmp1);
+
+  if (value->hdata.intvl.may_be_more
+      || value->hdata.intvl.may_be_less)
+    {
+      emit_jump_insn (gen_jump (end_of_code_label));
+      emit_barrier ();
+    }
+
+  /* Above the interval.  */
+  if (value->hdata.intvl.may_be_more)
+    {
+      emit_label (more_label);
+      tmp1 = expand_simple_binop (Pmode, PLUS, copy_rtx (tmp),
+				  GEN_INT (per_counter * value->hdata.intvl.steps),
+				  mr, 0, OPTAB_WIDEN);
+      if (tmp1 != mr)
+	emit_move_insn (copy_rtx (mr), tmp1);
+      if (value->hdata.intvl.may_be_less)
+	{
+	  emit_jump_insn (gen_jump (end_of_code_label));
+	  emit_barrier ();
+	}
+    }
+
+  /* Below the interval.  */
+  if (value->hdata.intvl.may_be_less)
+    {
+      emit_label (less_label);
+      tmp1 = expand_simple_binop (Pmode, PLUS, copy_rtx (tmp),
+		GEN_INT (per_counter * (value->hdata.intvl.steps
+					+ (value->hdata.intvl.may_be_more ? 1 : 0))),
+		mr, 0, OPTAB_WIDEN);
+      if (tmp1 != mr)
+	emit_move_insn (copy_rtx (mr), tmp1);
+    }
+
+  if (value->hdata.intvl.may_be_more
+      || value->hdata.intvl.may_be_less)
+    emit_label (end_of_code_label);
+
+  mem_ref = validize_mem (gen_rtx_MEM (mode, mr));
+
+  tmp = expand_simple_binop (mode, PLUS, copy_rtx (mem_ref), const1_rtx,
+			     mem_ref, 0, OPTAB_WIDEN);
+
+  if (tmp != mem_ref)
+    emit_move_insn (copy_rtx (mem_ref), tmp);
+
+  sequence = get_insns ();
+  end_sequence ();
+  rebuild_jump_labels (sequence);
+  safe_insert_insn_on_edge (sequence, e);
+}
+
+/* Output instructions as RTL to increment the power of two histogram counter.
+   VALUE is the expression whose value is profiled.  TAG is the tag of the
+   section for counters, BASE is offset of the counter position.  */
+
+static void
+rtl_gen_pow2_profiler (struct histogram_value *value, unsigned tag, 
+			unsigned base)
+{
+  unsigned gcov_size = tree_low_cst (TYPE_SIZE (GCOV_TYPE_NODE), 1);
+  enum machine_mode mode = mode_for_size (gcov_size, MODE_INT, 0);
+  rtx mem_ref, tmp, mr, uval;
+  rtx sequence;
+  rtx end_of_code_label = gen_label_rtx ();
+  rtx loop_label = gen_label_rtx ();
+  int per_counter = gcov_size / BITS_PER_UNIT;
+  edge e = split_block (BLOCK_FOR_INSN ((rtx)value->insn),
+		   PREV_INSN ((rtx)value->insn));
+
+  start_sequence ();
+
+  if (value->seq)
+    emit_insn (value->seq);
+
+  mr = gen_reg_rtx (Pmode);
+  tmp = rtl_coverage_counter_ref (tag, base);
+  tmp = force_reg (Pmode, XEXP (tmp, 0));
+  emit_move_insn (mr, tmp);
+
+  uval = gen_reg_rtx (value->mode);
+  emit_move_insn (uval, copy_rtx (value->value));
+
+  /* Check for non-power of 2.  */
+  if (value->hdata.pow2.may_be_other)
+    {
+      do_compare_rtx_and_jump (copy_rtx (uval), const0_rtx, LE, 0, value->mode,
+			       NULL_RTX, NULL_RTX, end_of_code_label);
+      tmp = expand_simple_binop (value->mode, PLUS, copy_rtx (uval),
+				 constm1_rtx, NULL_RTX, 0, OPTAB_WIDEN);
+      tmp = expand_simple_binop (value->mode, AND, copy_rtx (uval), tmp,
+				 NULL_RTX, 0, OPTAB_WIDEN);
+      do_compare_rtx_and_jump (tmp, const0_rtx, NE, 0, value->mode, NULL_RTX,
+			       NULL_RTX, end_of_code_label);
+    }
+
+  /* Count log_2(value).  */
+  emit_label (loop_label);
+
+  tmp = expand_simple_binop (Pmode, PLUS, copy_rtx (mr), GEN_INT (per_counter), mr, 0, OPTAB_WIDEN);
+  if (tmp != mr)
+    emit_move_insn (copy_rtx (mr), tmp);
+
+  tmp = expand_simple_binop (value->mode, ASHIFTRT, copy_rtx (uval), const1_rtx,
+			     uval, 0, OPTAB_WIDEN);
+  if (tmp != uval)
+    emit_move_insn (copy_rtx (uval), tmp);
+
+  do_compare_rtx_and_jump (copy_rtx (uval), const0_rtx, NE, 0, value->mode,
+			   NULL_RTX, NULL_RTX, loop_label);
+
+  /* Increase the counter.  */
+  emit_label (end_of_code_label);
+
+  mem_ref = validize_mem (gen_rtx_MEM (mode, mr));
+
+  tmp = expand_simple_binop (mode, PLUS, copy_rtx (mem_ref), const1_rtx,
+			     mem_ref, 0, OPTAB_WIDEN);
+
+  if (tmp != mem_ref)
+    emit_move_insn (copy_rtx (mem_ref), tmp);
+
+  sequence = get_insns ();
+  end_sequence ();
+  rebuild_jump_labels (sequence);
+  safe_insert_insn_on_edge (sequence, e);
+}
+
+/* Output instructions as RTL for code to find the most common value.
+   VALUE is the expression whose value is profiled.  TAG is the tag of the
+   section for counters, BASE is offset of the counter position.  */
+
+static rtx
+rtl_gen_one_value_profiler_no_edge_manipulation (struct histogram_value *value,
+						unsigned tag, unsigned base)
+{
+  unsigned gcov_size = tree_low_cst (TYPE_SIZE (GCOV_TYPE_NODE), 1);
+  enum machine_mode mode = mode_for_size (gcov_size, MODE_INT, 0);
+  rtx stored_value_ref, counter_ref, all_ref, stored_value, counter, all;
+  rtx tmp, uval;
+  rtx sequence;
+  rtx same_label = gen_label_rtx ();
+  rtx zero_label = gen_label_rtx ();
+  rtx end_of_code_label = gen_label_rtx ();
+
+  start_sequence ();
+
+  if (value->seq)
+    emit_insn (value->seq);
+
+  stored_value_ref = rtl_coverage_counter_ref (tag, base);
+  counter_ref = rtl_coverage_counter_ref (tag, base + 1);
+  all_ref = rtl_coverage_counter_ref (tag, base + 2);
+  stored_value = validize_mem (stored_value_ref);
+  counter = validize_mem (counter_ref);
+  all = validize_mem (all_ref);
+
+  uval = gen_reg_rtx (mode);
+  convert_move (uval, copy_rtx (value->value), 0);
+
+  /* Check if the stored value matches.  */
+  do_compare_rtx_and_jump (copy_rtx (uval), copy_rtx (stored_value), EQ,
+			   0, mode, NULL_RTX, NULL_RTX, same_label);
+
+  /* Does not match; check whether the counter is zero.  */
+  do_compare_rtx_and_jump (copy_rtx (counter), const0_rtx, EQ, 0, mode,
+			   NULL_RTX, NULL_RTX, zero_label);
+
+  /* The counter is not zero yet.  */
+  tmp = expand_simple_binop (mode, PLUS, copy_rtx (counter), constm1_rtx,
+			     counter, 0, OPTAB_WIDEN);
+
+  if (tmp != counter)
+    emit_move_insn (copy_rtx (counter), tmp);
+
+  emit_jump_insn (gen_jump (end_of_code_label));
+  emit_barrier ();
+
+  emit_label (zero_label);
+  /* Set new value.  */
+  emit_move_insn (copy_rtx (stored_value), copy_rtx (uval));
+
+  emit_label (same_label);
+  /* Increase the counter.  */
+  tmp = expand_simple_binop (mode, PLUS, copy_rtx (counter), const1_rtx,
+			     counter, 0, OPTAB_WIDEN);
+
+  if (tmp != counter)
+    emit_move_insn (copy_rtx (counter), tmp);
+
+  emit_label (end_of_code_label);
+
+  /* Increase the counter of all executions; this seems redundant given
+     that ve have counts for edges in cfg, but it may happen that some
+     optimization will change the counts for the block (either because
+     it is unable to update them correctly, or because it will duplicate
+     the block or its part).  */
+  tmp = expand_simple_binop (mode, PLUS, copy_rtx (all), const1_rtx,
+			     all, 0, OPTAB_WIDEN);
+
+  if (tmp != all)
+    emit_move_insn (copy_rtx (all), tmp);
+  sequence = get_insns ();
+  end_sequence ();
+  return sequence;
+}
+
+/* Output instructions as RTL for code to find the most common value.
+   VALUE is the expression whose value is profiled.  TAG is the tag of the
+   section for counters, BASE is offset of the counter position.  */
+
+static void
+rtl_gen_one_value_profiler (struct histogram_value *value, unsigned tag,
+			unsigned base)
+{
+  edge e = split_block (BLOCK_FOR_INSN ((rtx)value->insn),
+		   PREV_INSN ((rtx)value->insn));
+  rtx sequence = rtl_gen_one_value_profiler_no_edge_manipulation (value, 
+			tag, base);
+  rebuild_jump_labels (sequence);
+  safe_insert_insn_on_edge (sequence, e);
+}
+
+/* Output instructions as RTL for code to find the most common value of
+   a difference between two evaluations of an expression.
+   VALUE is the expression whose value is profiled.  TAG is the tag of the
+   section for counters, BASE is offset of the counter position.  */
+
+static void
+rtl_gen_const_delta_profiler (struct histogram_value *value, unsigned tag,
+			  unsigned base)
+{
+  struct histogram_value one_value_delta;
+  unsigned gcov_size = tree_low_cst (TYPE_SIZE (GCOV_TYPE_NODE), 1);
+  enum machine_mode mode = mode_for_size (gcov_size, MODE_INT, 0);
+  rtx stored_value_ref, stored_value, tmp, uval;
+  rtx sequence;
+  edge e = split_block (BLOCK_FOR_INSN ((rtx)value->insn),
+		   PREV_INSN ((rtx)value->insn));
+
+  start_sequence ();
+
+  if (value->seq)
+    emit_insn (value->seq);
+
+  stored_value_ref = rtl_coverage_counter_ref (tag, base);
+  stored_value = validize_mem (stored_value_ref);
+
+  uval = gen_reg_rtx (mode);
+  convert_move (uval, copy_rtx (value->value), 0);
+  tmp = expand_simple_binop (mode, MINUS,
+			     copy_rtx (uval), copy_rtx (stored_value),
+			     NULL_RTX, 0, OPTAB_WIDEN);
+
+  one_value_delta.value = tmp;
+  one_value_delta.mode = mode;
+  one_value_delta.seq = NULL_RTX;
+  one_value_delta.insn = value->insn;
+  one_value_delta.type = HIST_TYPE_SINGLE_VALUE;
+  emit_insn (rtl_gen_one_value_profiler_no_edge_manipulation (&one_value_delta,
+					     tag, base + 1));
+  emit_move_insn (copy_rtx (stored_value), uval);
+  sequence = get_insns ();
+  end_sequence ();
+  rebuild_jump_labels (sequence);
+  safe_insert_insn_on_edge (sequence, e);
+}
+
+/* Return the file on which profile dump output goes, if any.  */
+
+static FILE *rtl_profile_dump_file (void) {
+  return dump_file;
+}
+
+struct profile_hooks rtl_profile_hooks =
+{
+  rtl_gen_edge_profiler,
+  rtl_gen_interval_profiler,
+  rtl_gen_pow2_profiler,
+  rtl_gen_one_value_profiler,
+  rtl_gen_const_delta_profiler,
+  rtl_profile_dump_file
+};