[PATCH] Value profile based optimizations, part 1

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

there are several optimizations that may benefit from some knowledge
about values of expressions in the program, e.g specialization of
operations/standard functions, prefetching, decision heuristics for
some optimizations, etc.  We have implemented and tested some of them
on hammer-3_3-branch; I think they are ready to be merged to mainline
now.

This patch brings in the means to instrument the program to obtain
data about values of expressions.

Zdenek

	* vpt.c: New.
	* vpt.h: New.
	* Makefile.in (vpt.o): New.
	(LIBGCOV): Add _gcov_merge_one and _gcov_merge_const
	(profile.o): Add vpt.h and tree.h dependency.
	* flags.h (flag_value_histograms): Declare.
	* gcov-io.h (GCOV_COUNTERS, GCOV_COUNTER_NAMES, GCOV_MERGE_FUNCTIONS):
	Add new counters.
	(GCOV_COUNTER_V_INTERVAL, GCOV_COUNTER_V_POW2, GCOV_COUNTER_V_ONE,
	GCOV_COUNTER_V_DELTA): New counter sections.
	(__gcov_merge_one, __gcov_merge_const): Declare.
	* libgcov.c (__gcov_merge_one, __gcov_merge_const): New functions.
	* profile.c: Include vpt.h and tree.h.
	(gen_interval_profiler, gen_pow2_profiler, gen_one_value_profiler,
	gen_const_delta_profiler, instrument_values): New static functions.
	(get_exec_counts): Fix comment.
	(branch_prob): Invoke instrument_values.
	* toplev.c (flag_value_histograms): New flag.
	* doc/invoke.texi (-fvalue-histograms): Document.


vpt.c:
================================
/* Transformations based on profile information for values.
   Copyright (C) 2003 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.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "expr.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "vpt.h"
#include "output.h"
#include "flags.h"
#include "insn-config.h"
#include "recog.h"
#include "optabs.h"

static void insn_values_to_profile	PARAMS ((rtx, unsigned *,
					    	 struct histogram_value **));

/* Release the list of VALUES of length N_VALUES for that we want to measure
   histograms.  */
void
free_profiled_values (unsigned n_values ATTRIBUTE_UNUSED,
		      struct histogram_value *values)
{
  free (values);
}

/* Find values inside INSN for that we want to measure histograms and adds
   them to list VALUES (increasing the record of its length in N_VALUES).  */
static void
insn_values_to_profile (rtx insn ATTRIBUTE_UNUSED,
			unsigned *n_values ATTRIBUTE_UNUSED,
			struct histogram_value **values ATTRIBUTE_UNUSED)
{
}

/* Find list of values for that we want to measure histograms.  */
void
find_values_to_profile (n_values, values)
     unsigned *n_values;
     struct histogram_value **values;
{
  rtx insn;
  unsigned i;

  *n_values = 0;
  *values = NULL;
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    insn_values_to_profile (insn, n_values, values);

  for (i = 0; i < *n_values; i++)
    {
      switch ((*values)[i].type)
	{
	case HIST_TYPE_INTERVAL:
	  (*values)[i].n_counters = (*values)[i].hdata.intvl.steps +
		  ((*values)[i].hdata.intvl.may_be_less ? 1 : 0) +
		  ((*values)[i].hdata.intvl.may_be_more ? 1 : 0);
	  break;

	case HIST_TYPE_POW2:
	  (*values)[i].n_counters = GET_MODE_BITSIZE ((*values)[i].mode) +
		  ((*values)[i].hdata.pow2.may_be_other ? 1 : 0);
	  break;

	case HIST_TYPE_ONE_VALUE:
	  (*values)[i].n_counters = 3;
	  break;

	case HIST_TYPE_CONST_DELTA:
	  (*values)[i].n_counters = 4;
	  break;

	default:
	  abort ();
	}
    }
}

vpt.h:
================================
/* Definitions for transformations based on profile information for values.
   Copyright (C) 2003 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.  */

/* Supported histogram types.  */
enum hist_type
{
  HIST_TYPE_INTERVAL,	/* Measures histogram of values inside a specified
			   interval.  */
  HIST_TYPE_POW2,	/* Histogram of power of 2 values.  */
  HIST_TYPE_ONE_VALUE,	/* Tries to identify the value that is (almost)
			   always constant.  */
  HIST_TYPE_CONST_DELTA	/* Tries to identify the (almost) always constant
			   difference between two evaluations of a value.  */
};

/* The value to measure.  */
struct histogram_value
{
  rtx value;		/* The value.  */
  enum machine_mode mode; /* And its mode.  */
  rtx seq;		/* Insns requiered to count the value.  */
  rtx insn;		/* Insn before that to measure.  */
  enum hist_type type;	/* Type of histogram to measure.  */
  unsigned n_counters;	/* Number of requiered counters.  */
  union
    {
      struct
	{
	  int int_start;	/* First value in interval.  */
	  int steps;		/* Number of values in it.  */
	  int may_be_less;	/* May the value be below?  */
	  int may_be_more;	/* Or above.  */
	} intvl;	/* Interval histogram data.  */
      struct
	{
	  int may_be_other;	/* If the value may be non-positive or not 2^k.  */
	} pow2;		/* Power of 2 histogram data.  */
    } hdata;		/* Histogram data.  */
};

extern void find_values_to_profile (unsigned *, struct histogram_value **);
extern void free_profiled_values (unsigned, struct histogram_value *);

================================

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1076
diff -c -3 -p -r1.1076 Makefile.in
*** Makefile.in	8 Jun 2003 19:35:46 -0000	1.1076
--- Makefile.in	8 Jun 2003 20:35:52 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 821,827 ****
   sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o	   \
   stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
   tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
!  alloc-pool.o et-forest.o cgraph.o cgraphunit.o cfghooks.o		   \
   $(GGC) $(out_object_file) $(EXTRA_OBJS) $(host_hook_obj)
  
  BACKEND = main.o libbackend.a
--- 821,827 ----
   sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o	   \
   stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
   tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
!  alloc-pool.o et-forest.o cgraph.o cgraphunit.o cfghooks.o vpt.o	   \
   $(GGC) $(out_object_file) $(EXTRA_OBJS) $(host_hook_obj)
  
  BACKEND = main.o libbackend.a
*************** STAGESTUFF = *$(objext) insn-flags.h ins
*** 853,859 ****
  LIB2FUNCS_ST = _eprintf __gcc_bcmp
  
  # Defined in libgcov.c, included only in gcov library
! LIBGCOV = _gcov _gcov_merge_add
  
  FPBIT_FUNCS = _pack_sf _unpack_sf _addsub_sf _mul_sf _div_sf \
      _fpcmp_parts_sf _compare_sf _eq_sf _ne_sf _gt_sf _ge_sf \
--- 853,859 ----
  LIB2FUNCS_ST = _eprintf __gcc_bcmp
  
  # Defined in libgcov.c, included only in gcov library
! LIBGCOV = _gcov _gcov_merge_add _gcov_merge_one _gcov_merge_const
  
  FPBIT_FUNCS = _pack_sf _unpack_sf _addsub_sf _mul_sf _div_sf \
      _fpcmp_parts_sf _compare_sf _eq_sf _ne_sf _gt_sf _ge_sf \
*************** conflict.o : conflict.c $(CONFIG_H) $(SY
*** 1634,1640 ****
     $(HASHTAB_H) $(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H)
  profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(TREE_H) flags.h output.h $(REGS_H) $(EXPR_H) function.h \
!    toplev.h $(BASIC_BLOCK_H) $(COVERAGE_H)
  loop.o : loop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h $(LOOP_H) \
     insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
     real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h cfgloop.h \
--- 1634,1643 ----
     $(HASHTAB_H) $(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H)
  profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(TREE_H) flags.h output.h $(REGS_H) $(EXPR_H) function.h \
!    toplev.h $(BASIC_BLOCK_H) $(COVERAGE_H) $(TREE_H) vpt.h
! vpt.o : vpt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
!    $(BASIC_BLOCK_H) hard-reg-set.h vpt.h $(EXPR_H) output.h flags.h \
!    $(RECOG_H) insn-config.h $(OPTABS_H)
  loop.o : loop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h $(LOOP_H) \
     insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
     real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h cfgloop.h \
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.110
diff -c -3 -p -r1.110 flags.h
*** flags.h	3 Jun 2003 09:06:46 -0000	1.110
--- flags.h	8 Jun 2003 20:35:52 -0000
*************** extern int profile_flag;
*** 197,202 ****
--- 197,206 ----
  
  extern int profile_arc_flag;
  
+ /* Nonzero if value histograms should be measured.  */
+ 
+ extern int flag_value_histograms;
+ 
  /* Nonzero if generating info for gcov to calculate line test coverage.  */
  
  extern int flag_test_coverage;
Index: gcov-io.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcov-io.h,v
retrieving revision 1.34
diff -c -3 -p -r1.34 gcov-io.h
*** gcov-io.h	14 May 2003 16:01:18 -0000	1.34
--- gcov-io.h	8 Jun 2003 20:35:52 -0000
*************** typedef HOST_WIDEST_INT gcov_type;
*** 269,281 ****
  #define GCOV_COUNTER_ARCS 	0  /* Arc transitions.  */
  #define GCOV_COUNTERS_SUMMABLE	1  /* Counters which can be
  				      summaried. */
! #define GCOV_COUNTERS		1
  
  /* A list of human readable names of the counters */
! #define GCOV_COUNTER_NAMES	{"arcs"}
  
  /* Names of merge functions for counters.  */
! #define GCOV_MERGE_FUNCTIONS	{"__gcov_merge_add"}
  
  /* Convert a counter index to a tag. */
  #define GCOV_TAG_FOR_COUNTER(COUNT)				\
--- 269,291 ----
  #define GCOV_COUNTER_ARCS 	0  /* Arc transitions.  */
  #define GCOV_COUNTERS_SUMMABLE	1  /* Counters which can be
  				      summaried. */
! #define GCOV_COUNTER_V_INTERVAL	2  /* Histogram of value inside an interval.  */
! #define GCOV_COUNTER_V_POW2	3  /* Histogram of exact power2 logarithm
! 				      of a value.  */
! #define GCOV_COUNTER_V_ONE	4  /* The most common value of expression.  */
! #define GCOV_COUNTER_V_DELTA	5  /* The most common difference between
! 				      consecutive values of expression.  */
! #define GCOV_COUNTERS		5
  
  /* A list of human readable names of the counters */
! #define GCOV_COUNTER_NAMES	{"arcs", "interval", "pow2", "one", "delta"}
  
  /* Names of merge functions for counters.  */
! #define GCOV_MERGE_FUNCTIONS	{"__gcov_merge_add",	\
! 				 "__gcov_merge_add",	\
! 				 "__gcov_merge_add",	\
! 				 "__gcov_merge_one",	\
! 				 "__gcov_merge_delta"}
  
  /* Convert a counter index to a tag. */
  #define GCOV_TAG_FOR_COUNTER(COUNT)				\
*************** extern void __gcov_flush (void);
*** 380,385 ****
--- 390,402 ----
  
  /* The merge function that just sums the counters.  */
  extern void __gcov_merge_add (gcov_type *, unsigned);
+ 
+ /* The merge function to choose the most often value.  */
+ extern void __gcov_merge_one (gcov_type *, unsigned);
+ 
+ /* The merge function to choose the most often difference between consecutive
+    values.  */
+ extern void __gcov_merge_const (gcov_type *, unsigned);
  #endif /* IN_LIBGCOV */
  
  #if IN_LIBGCOV >= 0
Index: libgcov.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/libgcov.c,v
retrieving revision 1.15
diff -c -3 -p -r1.15 libgcov.c
*** libgcov.c	14 May 2003 16:01:20 -0000	1.15
--- libgcov.c	8 Jun 2003 20:35:52 -0000
*************** void __gcov_merge_add (gcov_type *counte
*** 63,68 ****
--- 63,78 ----
  		       unsigned n_counters __attribute__ ((unused))) {}
  #endif
  
+ #ifdef L_gcov_merge_one
+ void __gcov_merge_one (gcov_type *counters  __attribute__ ((unused)),
+ 		       unsigned n_counters __attribute__ ((unused))) {}
+ #endif
+ 
+ #ifdef L_gcov_merge_const
+ void __gcov_merge_const (gcov_type *counters  __attribute__ ((unused)),
+ 		       unsigned n_counters __attribute__ ((unused))) {}
+ #endif
+ 
  #else
  
  #include <string.h>
*************** __gcov_merge_add (gcov_type *counters, u
*** 465,469 ****
--- 475,558 ----
      *counters += gcov_read_counter ();
  }
  #endif /* L_gcov_merge_add */
+ 
+ #ifdef L_gcov_merge_one
+ /* The profile merging function for choosing the most common value.  It is given
+    an array COUNTERS of N_COUNTERS old counters and it reads the same number
+    of counters from the gcov file.  The counters are split into 3-tuples
+    where the members of the tuple have meanings:
+    -- the stored candidate on the most common value of the measured entity
+    -- counter
+    -- total number of evaluations of the value  */
+ void
+ __gcov_merge_one (gcov_type *counters, unsigned n_counters)
+ {
+   unsigned i, n_measures;
+   gcov_type value, counter, all;
+ 
+   if (n_counters % 3)
+     abort ();
+ 
+   n_measures = n_counters / 3;
+   for (i = 0; i < n_measures; i++, counters += 3)
+     {
+       value = gcov_read_counter ();
+       counter = gcov_read_counter ();
+       all = gcov_read_counter ();
+ 
+       if (counters[0] == value)
+ 	counters[1] += counter;
+       else if (counter > counters[1])
+ 	{
+ 	  counters[0] = value;
+ 	  counters[1] = counter - counters[1];
+ 	}
+       else
+ 	counters[1] -= counter;
+       counters[2] += all;
+     }
+ }
+ #endif /* L_gcov_merge_one */
+ 
+ #ifdef L_gcov_merge_const
+ /* The profile merging function for choosing the most common difference between
+    two consecutive evaluations of the value.  It is given an array COUNTERS of
+    N_COUNTERS old counters and it reads the same number of counters from the
+    gcov file.  The counters are split into 4-tuples where the members of the
+    tuple have meanings:
+    -- the last value of the measured entity
+    -- the stored candidate on the most common difference
+    -- counter
+    -- total number of evaluations of the value  */
+ void
+ __gcov_merge_const (gcov_type *counters, unsigned n_counters)
+ {
+   unsigned i, n_measures;
+   gcov_type last, value, counter, all;
+ 
+   if (n_counters % 4)
+     abort ();
+ 
+   n_measures = n_counters / 4;
+   for (i = 0; i < n_measures; i++, counters += 4)
+     {
+       last = gcov_read_counter ();
+       value = gcov_read_counter ();
+       counter = gcov_read_counter ();
+       all = gcov_read_counter ();
+ 
+       if (counters[1] == value)
+ 	counters[2] += counter;
+       else if (counter > counters[2])
+ 	{
+ 	  counters[1] = value;
+ 	  counters[2] = counter - counters[2];
+ 	}
+       else
+ 	counters[2] -= counter;
+       counters[3] += all;
+     }
+ }
+ #endif /* L_gcov_merge_const */
  
  #endif /* inhibit_libc */
Index: profile.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/profile.c,v
retrieving revision 1.120
diff -c -3 -p -r1.120 profile.c
*** profile.c	11 May 2003 19:21:32 -0000	1.120
--- profile.c	8 Jun 2003 20:35:52 -0000
*************** Software Foundation, 59 Temple Place - S
*** 60,65 ****
--- 60,67 ----
  #include "function.h"
  #include "toplev.h"
  #include "coverage.h"
+ #include "vpt.h"
+ #include "tree.h"
  
  /* Additional information about the edges we need.  */
  struct edge_info {
*************** static int total_num_branches;
*** 105,111 ****
--- 107,118 ----
  /* Forward declarations.  */
  static void find_spanning_tree PARAMS ((struct edge_list *));
  static rtx gen_edge_profiler PARAMS ((int));
+ static rtx gen_interval_profiler (struct histogram_value *, unsigned, unsigned);
+ static rtx gen_pow2_profiler (struct histogram_value *, unsigned, unsigned);
+ static rtx gen_one_value_profiler (struct histogram_value *, unsigned, unsigned);
+ static rtx gen_const_delta_profiler (struct histogram_value *, unsigned, unsigned);
  static unsigned instrument_edges PARAMS ((struct edge_list *));
+ static void instrument_values (unsigned, struct histogram_value *);
  static void compute_branch_probabilities PARAMS ((void));
  static gcov_type * get_exec_counts PARAMS ((void));
  static basic_block find_group PARAMS ((basic_block));
*************** instrument_edges (el)
*** 157,166 ****
      fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
    return num_instr_edges;
  }
  
  
! /* Computes hybrid profile for all matching entries in da_file.
!    Sets max_counter_in_program as a side effect.  */
  
  static gcov_type *
  get_exec_counts ()
--- 164,236 ----
      fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
    return num_instr_edges;
  }
+ 
+ /* Add code to measure histograms list of VALUES of length N_VALUES.  */
+ static void
+ instrument_values (unsigned n_values, struct histogram_value *values)
+ {
+   rtx sequence;
+   unsigned i, t;
+   edge e;
+  
+   /* Emit code to generate the histograms before the insns.  */
+ 
+   for (i = 0; i < n_values; i++)
+     {
+       e = split_block (BLOCK_FOR_INSN (values[i].insn),
+ 		       PREV_INSN (values[i].insn));
+       switch (values[i].type)
+ 	{
+ 	case HIST_TYPE_INTERVAL:
+ 	  t = GCOV_COUNTER_V_INTERVAL;
+ 	  break;
+ 
+ 	case HIST_TYPE_POW2:
+ 	  t = GCOV_COUNTER_V_POW2;
+ 	  break;
+ 
+ 	case HIST_TYPE_ONE_VALUE:
+ 	  t = GCOV_COUNTER_V_ONE;
+ 	  break;
+ 
+ 	case HIST_TYPE_CONST_DELTA:
+ 	  t = GCOV_COUNTER_V_DELTA;
+ 	  break;
+ 
+ 	default:
+ 	  abort ();
+ 	}
+       if (!coverage_counter_alloc (t, values[i].n_counters))
+ 	continue;
+ 
+       switch (values[i].type)
+ 	{
+ 	case HIST_TYPE_INTERVAL:
+ 	  sequence = gen_interval_profiler (values + i, t, 0);
+ 	  break;
+ 
+ 	case HIST_TYPE_POW2:
+ 	  sequence = gen_pow2_profiler (values + i, t, 0);
+ 	  break;
+ 
+ 	case HIST_TYPE_ONE_VALUE:
+ 	  sequence = gen_one_value_profiler (values + i, t, 0);
+ 	  break;
+ 
+ 	case HIST_TYPE_CONST_DELTA:
+ 	  sequence = gen_const_delta_profiler (values + i, t, 0);
+ 	  break;
+ 
+ 	default:
+ 	  abort ();
+ 	}
+ 
+       insert_insn_on_edge (sequence, e);
+     }
+ }
  
  
! /* Computes hybrid profile for all matching entries in da_file.  */
  
  static gcov_type *
  get_exec_counts ()
*************** branch_prob ()
*** 553,558 ****
--- 623,630 ----
    unsigned num_edges, ignored_edges;
    unsigned num_instrumented;
    struct edge_list *el;
+   unsigned n_values = 0;
+   struct histogram_value *values = NULL;
  
    total_num_times_called++;
  
*************** branch_prob ()
*** 804,809 ****
--- 876,887 ----
    EXIT_BLOCK_PTR->index = EXIT_BLOCK;
  #undef BB_TO_GCOV_INDEX
  
+   if (flag_value_histograms)
+     {
+       find_values_to_profile (&n_values, &values);
+       allocate_reg_info (max_reg_num (), FALSE, FALSE);
+     }
+ 
    if (flag_branch_probabilities)
      compute_branch_probabilities ();
  
*************** branch_prob ()
*** 816,821 ****
--- 894,902 ----
        if (n_instrumented != num_instrumented)
  	abort ();
  
+       if (flag_value_histograms)
+ 	instrument_values (n_values, values);
+ 
        /* Commit changes done by instrumentation.  */
        commit_edge_insertions_watch_calls ();
        allocate_reg_info (max_reg_num (), FALSE, FALSE);
*************** gen_edge_profiler (edgeno)
*** 1027,1031 ****
--- 1108,1410 ----
  
    sequence = get_insns ();
    end_sequence ();
+   return sequence;
+ }
+ 
+ /* 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 rtx
+ 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;
+ 
+   start_sequence ();
+ 
+   if (value->seq)
+     emit_insn (value->seq);
+ 
+   mr = gen_reg_rtx (Pmode);
+ 
+   tmp = 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);
+   return sequence;
+ }
+ 
+ /* 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 rtx
+ 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;
+ 
+   start_sequence ();
+ 
+   if (value->seq)
+     emit_insn (value->seq);
+ 
+   mr = gen_reg_rtx (Pmode);
+   tmp = 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);
+   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 rtx
+ gen_one_value_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 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 = coverage_counter_ref (tag, base);
+   counter_ref = coverage_counter_ref (tag, base + 1);
+   all_ref = 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 ();
+   rebuild_jump_labels (sequence);
+   return sequence;
+ }
+ 
+ /* 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 rtx
+ 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;
+ 
+   start_sequence ();
+ 
+   if (value->seq)
+     emit_insn (value->seq);
+ 
+   stored_value_ref = 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_ONE_VALUE;
+   emit_insn (gen_one_value_profiler (&one_value_delta, tag, base + 1));
+ 
+   emit_move_insn (copy_rtx (stored_value), uval);
+   sequence = get_insns ();
+   end_sequence ();
+   rebuild_jump_labels (sequence);
    return sequence;
  }
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.769
diff -c -3 -p -r1.769 toplev.c
*** toplev.c	8 Jun 2003 19:35:53 -0000	1.769
--- toplev.c	8 Jun 2003 20:35:52 -0000
*************** int profile_flag = 0;
*** 428,433 ****
--- 428,437 ----
  
  int profile_arc_flag = 0;
  
+ /* Nonzero if value histograms should be measured.  */
+ 
+ int flag_value_histograms = 0;
+ 
  /* Nonzero if generating info for gcov to calculate line test coverage.  */
  
  int flag_test_coverage = 0;
*************** static const lang_independent_options f_
*** 1185,1190 ****
--- 1189,1196 ----
     N_("Create data files needed by gcov") },
    {"branch-probabilities", &flag_branch_probabilities, 1,
     N_("Use profiling information for branch probabilities") },
+   {"value-histograms", &flag_value_histograms, 1,
+    N_("Insert code to measure value histograms") },
    {"profile", &profile_flag, 1,
     N_("Enable basic program profiling code") },
    {"reorder-blocks", &flag_reorder_blocks, 1,
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.290
diff -c -3 -p -r1.290 invoke.texi
*** doc/invoke.texi	6 Jun 2003 04:33:01 -0000	1.290
--- doc/invoke.texi	8 Jun 2003 20:35:53 -0000
*************** in the following sections.
*** 258,265 ****
  @xref{Optimize Options,,Options that Control Optimization}.
  @gccoptlist{-falign-functions=@var{n}  -falign-jumps=@var{n} @gol
  -falign-labels=@var{n}  -falign-loops=@var{n}  @gol
! -fbranch-probabilities  -fcaller-saves  -fcprop-registers @gol
! -fcse-follow-jumps  -fcse-skip-blocks  -fdata-sections @gol
  -fdelayed-branch  -fdelete-null-pointer-checks @gol
  -fexpensive-optimizations  -ffast-math  -ffloat-store @gol
  -fforce-addr  -fforce-mem  -ffunction-sections @gol
--- 258,265 ----
  @xref{Optimize Options,,Options that Control Optimization}.
  @gccoptlist{-falign-functions=@var{n}  -falign-jumps=@var{n} @gol
  -falign-labels=@var{n}  -falign-loops=@var{n}  @gol
! -fbranch-probabilities -fvalue-histograms -fcaller-saves  @gol
! -fcprop-registers -fcse-follow-jumps  -fcse-skip-blocks  -fdata-sections @gol
  -fdelayed-branch  -fdelete-null-pointer-checks @gol
  -fexpensive-optimizations  -ffast-math  -ffloat-store @gol
  -fforce-addr  -fforce-mem  -ffunction-sections @gol
*************** These can be used to improve optimizatio
*** 4304,4309 ****
--- 4304,4314 ----
  used in one place: in @file{reorg.c}, instead of guessing which path a
  branch is mostly to take, the @samp{REG_BR_PROB} values are used to
  exactly determine which path is taken more often.
+ 
+ @item -fvalue-histograms
+ @opindex fvalue-histograms
+ If combined with @option{-fprofile-arcs}, it adds code so that some
+ data about values of expressions in the program is gathered.
  
  @item -fnew-ra
  @opindex fnew-ra