GCC 4.2.0 release.

1 files changed, 717 insertions, 551 deletions

diff --git a/contrib/gcc/value-prof.c b/contrib/gcc/value-prof.c
index 4f6f3da..6c64e3c 100644
--- a/contrib/gcc/value-prof.c
+++ b/contrib/gcc/value-prof.c
@@ -1,5 +1,5 @@
 /* Transformations based on profile information for values.
-   Copyright (C) 2003 Free Software Foundation, Inc.
+   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -15,8 +15,8 @@ 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.  */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
 
 #include "config.h"
 #include "system.h"
@@ -33,676 +33,842 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "recog.h"
 #include "optabs.h"
 #include "regs.h"
-
-/* In this file value profile based optimizations will be placed (none are
-   here just now, but they are hopefully coming soon).
+#include "ggc.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "diagnostic.h"
+#include "coverage.h"
+#include "tree.h"
+#include "gcov-io.h"
+#include "timevar.h"
+#include "tree-pass.h"
+#include "toplev.h"
+
+static struct value_prof_hooks *value_prof_hooks;
+
+/* In this file value profile based optimizations are placed.  Currently the
+   following optimizations are implemented (for more detailed descriptions
+   see comments at value_profile_transformations):
+
+   1) Division/modulo specialization.  Provided that we can determine that the
+      operands of the division have some special properties, we may use it to
+      produce more effective code.
+   2) Speculative prefetching.  If we are able to determine that the difference
+      between addresses accessed by a memory reference is usually constant, we
+      may add the prefetch instructions.
+      FIXME: This transformation was removed together with RTL based value
+      profiling.
 
    Every such optimization should add its requirements for profiled values to
    insn_values_to_profile function.  This function is called from branch_prob
    in profile.c and the requested values are instrumented by it in the first
    compilation with -fprofile-arcs.  The optimization may then read the
    gathered data in the second compilation with -fbranch-probabilities.
-   The measured data is appended as REG_VALUE_PROFILE note to the instrumented
-   insn.  The argument to the note consists of an EXPR_LIST where its
-   members have the following meaning (from the first to the last):
-   
-   -- type of information gathered (HIST_TYPE*)
-   -- the expression that is profiled
-   -- list of counters starting from the first one.  */
-
-static void insn_divmod_values_to_profile (rtx, unsigned *,
-					   struct histogram_value **);
-static void insn_values_to_profile (rtx, unsigned *, struct histogram_value **);
-static rtx gen_divmod_fixed_value (enum machine_mode, enum rtx_code, rtx, rtx,
-				   rtx, gcov_type);
-static rtx gen_mod_pow2 (enum machine_mode, enum rtx_code, rtx, rtx, rtx);
-static rtx gen_mod_subtract (enum machine_mode, enum rtx_code, rtx, rtx, rtx,
-			     int);
-static bool divmod_fixed_value_transform (rtx insn);
-static bool mod_pow2_value_transform (rtx);
-static bool mod_subtract_transform (rtx);
-
-/* 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 for
-   division/modulo optimization.  */
-static void
-insn_divmod_values_to_profile (rtx insn, unsigned *n_values,
-			       struct histogram_value **values)
-{
-  rtx set, set_src, op1, op2;
-  enum machine_mode mode;
-
-  if (!INSN_P (insn))
-    return;
-
-  set = single_set (insn);
-  if (!set)
-    return;
-
-  mode = GET_MODE (SET_DEST (set));
-  if (!INTEGRAL_MODE_P (mode))
-    return;
-
-  set_src = SET_SRC (set);
-  switch (GET_CODE (set_src))
-    {
-    case DIV:
-    case MOD:
-    case UDIV:
-    case UMOD:
-      op1 = XEXP (set_src, 0);
-      op2 = XEXP (set_src, 1);
-      if (side_effects_p (op2))
-	return;
-
-      /* Check for a special case where the divisor is power of 2.  */
-      if ((GET_CODE (set_src) == UMOD) && !CONSTANT_P (op2))
-	{
-	  *values = xrealloc (*values,
-			      (*n_values + 1)
-				* sizeof (struct histogram_value));
-	  (*values)[*n_values].value = op2;
-	  (*values)[*n_values].seq = NULL_RTX;
-	  (*values)[*n_values].mode = mode;
-	  (*values)[*n_values].insn = insn;
-	  (*values)[*n_values].type = HIST_TYPE_POW2;
-	  (*values)[*n_values].hdata.pow2.may_be_other = 1;
-	  (*n_values)++;
-	}
-
-      /* Check whether the divisor is not in fact a constant.  */
-      if (!CONSTANT_P (op2))
-	{
-	  *values = xrealloc (*values,
-			      (*n_values + 1)
-				* sizeof (struct histogram_value));
-	  (*values)[*n_values].value = op2;
-	  (*values)[*n_values].mode = mode;
-	  (*values)[*n_values].seq = NULL_RTX;
-	  (*values)[*n_values].insn = insn;
-	  (*values)[*n_values].type = HIST_TYPE_SINGLE_VALUE;
-	  (*n_values)++;
-	}
 
-      /* For mod, check whether it is not often a noop (or replaceable by
-	 a few subtractions).  */
-      if (GET_CODE (set_src) == UMOD && !side_effects_p (op1))
-	{
-	  rtx tmp;
-
-	  *values = xrealloc (*values,
-			      (*n_values + 1)
-				* sizeof (struct histogram_value));
-	  start_sequence ();
-	  tmp = simplify_gen_binary (DIV, mode, copy_rtx (op1), copy_rtx (op2));
-	  (*values)[*n_values].value = force_operand (tmp, NULL_RTX);
-	  (*values)[*n_values].seq = get_insns ();
-	  end_sequence ();
-	  (*values)[*n_values].mode = mode;
-	  (*values)[*n_values].insn = insn;
-	  (*values)[*n_values].type = HIST_TYPE_INTERVAL;
-	  (*values)[*n_values].hdata.intvl.int_start = 0;
-	  (*values)[*n_values].hdata.intvl.steps = 2;
-	  (*values)[*n_values].hdata.intvl.may_be_less = 1;
-	  (*values)[*n_values].hdata.intvl.may_be_more = 1;
-	  (*n_values)++;
-	}
-      return;
+   The measured data is pointed to from the histograms
+   field of the statement annotation of the instrumented insns.  It is
+   kept as a linked list of struct histogram_value_t's, which contain the
+   same information as above.  */
 
-    default:
-      return;
-    }
-}
 
-/* 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,
-			unsigned *n_values,
-			struct histogram_value **values)
-{
-  if (flag_value_profile_transformations)
-    insn_divmod_values_to_profile (insn, n_values, values);
-}
+static tree tree_divmod_fixed_value (tree, tree, tree, tree, 
+				    tree, int, gcov_type, gcov_type);
+static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type);
+static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int,
+				gcov_type, gcov_type, gcov_type);
+static bool tree_divmod_fixed_value_transform (tree);
+static bool tree_mod_pow2_value_transform (tree);
+static bool tree_mod_subtract_transform (tree);
 
-/* Find list of values for that we want to measure histograms.  */
-void
-find_values_to_profile (unsigned *n_values, struct histogram_value **values)
+/* The overall number of invocations of the counter should match execution count
+   of basic block.  Report it as error rather than internal error as it might
+   mean that user has misused the profile somehow.  */
+static bool
+check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
 {
-  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++)
+  if (all != bb_count)
     {
-      switch ((*values)[i].type)
-	{
-	case HIST_TYPE_INTERVAL:
-	  if (rtl_dump_file)
-	    fprintf (rtl_dump_file,
-		     "Interval counter for insn %d, range %d -- %d.\n",
-		     INSN_UID ((*values)[i].insn),
-		     (*values)[i].hdata.intvl.int_start,
-		     ((*values)[i].hdata.intvl.int_start
-		      + (*values)[i].hdata.intvl.steps - 1));
-	  (*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:
-	  if (rtl_dump_file)
-	    fprintf (rtl_dump_file,
-		     "Pow2 counter for insn %d.\n",
-		     INSN_UID ((*values)[i].insn));
-	  (*values)[i].n_counters = GET_MODE_BITSIZE ((*values)[i].mode) +
-		  ((*values)[i].hdata.pow2.may_be_other ? 1 : 0);
-	  break;
-
-	case HIST_TYPE_SINGLE_VALUE:
-	  if (rtl_dump_file)
-	    fprintf (rtl_dump_file,
-		     "Single value counter for insn %d.\n",
-		     INSN_UID ((*values)[i].insn));
-	  (*values)[i].n_counters = 3;
-	  break;
-
-	case HIST_TYPE_CONST_DELTA:
-	  if (rtl_dump_file)
-	    fprintf (rtl_dump_file,
-		     "Constant delta counter for insn %d.\n",
-		     INSN_UID ((*values)[i].insn));
-	  (*values)[i].n_counters = 4;
-	  break;
-
-	default:
-	  abort ();
-	}
+      location_t * locus;
+      locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
+	       ? EXPR_LOCUS (stmt)
+	       : &DECL_SOURCE_LOCATION (current_function_decl));
+      error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
+	     locus, name, (int)all, (int)bb_count);
+      return true;
     }
+  return false;
 }
 
-/* Main entry point.  Finds REG_VALUE_PROFILE notes from profiler and uses
-   them to identify and exploit properties of values that are hard to analyze
-   statically.
-
-   We do following transformations:
-
-   1)
-
-   x = a / b;
-
-   where b is almost always a constant N is transformed to
-
-   if (b == N)
-     x = a / N;
-   else
-     x = a / b;
-
-   Analogically with %
-
-   2)
-
-   x = a % b
-
-   where b is almost always a power of 2 and the division is unsigned
-   TODO -- handle signed case as well
-
-   if ((b & (b - 1)) == 0)
-     x = a & (b - 1);
-   else
-     x = x % b;
-
-   Note that when b = 0, no error will occur and x = a; this is correct,
-   as result of such operation is undefined.
-
-   3)
-
-   x = a % b
-
-   where a is almost always less then b and the division is unsigned
-   TODO -- handle signed case as well
-
-   x = a;
-   if (x >= b)
-     x %= b;
-
-   4)
-
-   x = a % b
-
-   where a is almost always less then 2 * b and the division is unsigned
-   TODO -- handle signed case as well
-
-   x = a;
-   if (x >= b)
-     x -= b;
-   if (x >= b)
-     x %= b;
-
-   It would be possible to continue analogically for K * b for other small
-   K's, but it is probably not useful.
-
-   TODO:
-
-   There are other useful cases that could be handled by a similar mechanism,
-   for example:
-   
-   for (i = 0; i < n; i++)
-     ...
-   
-   transform to (for constant N):
-   
-   if (n == N)
-     for (i = 0; i < N; i++)
-       ...
-   else
-     for (i = 0; i < n; i++)
-       ...
-   making unroller happy.  Since this may grow the code significantly,
-   we would have to be very careful here.  */
-
-bool
-value_profile_transformations (void)
+/* Tree based transformations. */
+static bool
+tree_value_profile_transformations (void)
 {
-  rtx insn, next;
-  int changed = false;
+  basic_block bb;
+  block_stmt_iterator bsi;
+  bool changed = false;
 
-  for (insn = get_insns (); insn; insn = next)
+  FOR_EACH_BB (bb)
     {
-      next = NEXT_INSN (insn);
-
-      if (!INSN_P (insn))
-	continue;
-
-      /* Scan for insn carrying a histogram.  */
-      if (!find_reg_note (insn, REG_VALUE_PROFILE, 0))
-	continue;
-
-      /* Ignore cold areas -- we are growing a code.  */
-      if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn)))
+      /* Ignore cold areas -- we are enlarging the code.  */
+      if (!maybe_hot_bb_p (bb))
 	continue;
 
-      if (rtl_dump_file)
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 	{
-	  fprintf (rtl_dump_file, "Trying transformations on insn %d\n",
-		   INSN_UID (insn));
-	  print_rtl_single (rtl_dump_file, insn);
-	}
-
-      /* Transformations:  */
-      if (flag_value_profile_transformations
-	  && (mod_subtract_transform (insn)
-	      || divmod_fixed_value_transform (insn)
-	      || mod_pow2_value_transform (insn)))
-	changed = true;
+	  tree stmt = bsi_stmt (bsi);
+	  stmt_ann_t ann = get_stmt_ann (stmt);
+	  histogram_value th = ann->histograms;
+	  if (!th)
+	    continue;
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Trying transformations on insn ");
+	      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+	    }
+
+	  /* Transformations:  */
+	  /* The order of things in this conditional controls which
+	     transformation is used when more than one is applicable.  */
+	  /* It is expected that any code added by the transformations
+	     will be added before the current statement, and that the
+	     current statement remain valid (although possibly
+	     modified) upon return.  */
+	  if (flag_value_profile_transformations
+	      && (tree_mod_subtract_transform (stmt)
+		  || tree_divmod_fixed_value_transform (stmt)
+		  || tree_mod_pow2_value_transform (stmt)))
+	    {
+	      changed = true;
+	      /* Original statement may no longer be in the same block. */
+	      if (bb != bb_for_stmt (stmt))
+		{
+	          bb = bb_for_stmt (stmt);
+		  bsi = bsi_for_stmt (stmt);
+		}
+	    }
+
+	  /* Free extra storage from compute_value_histograms.  */
+	  while (th)
+	    {
+	      free (th->hvalue.counters);
+	      th = th->hvalue.next;
+	    }
+	  ann->histograms = 0;
+        }
     }
 
   if (changed)
     {
-      commit_edge_insertions ();
-      allocate_reg_info (max_reg_num (), FALSE, FALSE);
+      counts_to_freqs ();
     }
 
   return changed;
 }
 
-/* Generate code for transformation 1 (with MODE and OPERATION, operands OP1
-   and OP2 whose value is expected to be VALUE and result TARGET).  */
-static rtx
-gen_divmod_fixed_value (enum machine_mode mode, enum rtx_code operation,
-			rtx target, rtx op1, rtx op2, gcov_type value)
+/* Generate code for transformation 1 (with OPERATION, operands OP1
+   and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
+   probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
+   within roundoff error).  This generates the result into a temp and returns 
+   the temp; it does not replace or alter the original STMT.  */
+static tree
+tree_divmod_fixed_value (tree stmt, tree operation, 
+			 tree op1, tree op2, tree value, int prob, gcov_type count,
+			 gcov_type all)
 {
-  rtx tmp, tmp1;
-  rtx neq_label = gen_label_rtx ();
-  rtx end_label = gen_label_rtx ();
-  rtx sequence;
-
-  start_sequence ();
-  
-  if (!REG_P (op2))
-    {
-      tmp = gen_reg_rtx (mode);
-      emit_move_insn (tmp, copy_rtx (op2));
-    }
-  else
-    tmp = op2;
-
-  do_compare_rtx_and_jump (tmp, GEN_INT (value), NE, 0, mode, NULL_RTX,
-			   NULL_RTX, neq_label);
-  tmp1 = simplify_gen_binary (operation, mode, copy_rtx (op1), GEN_INT (value));
-  tmp1 = force_operand (tmp1, target);
-  if (tmp1 != target)
-    emit_move_insn (copy_rtx (target), copy_rtx (tmp1));
-
-  emit_jump_insn (gen_jump (end_label));
-  emit_barrier ();
-
-  emit_label (neq_label);
-  tmp1 = simplify_gen_binary (operation, mode, copy_rtx (op1), copy_rtx (tmp));
-  tmp1 = force_operand (tmp1, target);
-  if (tmp1 != target)
-    emit_move_insn (copy_rtx (target), copy_rtx (tmp1));
+  tree stmt1, stmt2, stmt3;
+  tree tmp1, tmp2, tmpv;
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+  tree bb1end, bb2end, bb3end;
+  basic_block bb, bb2, bb3, bb4;
+  tree optype = TREE_TYPE (operation);
+  edge e12, e13, e23, e24, e34;
+  block_stmt_iterator bsi;
+
+  bb = bb_for_stmt (stmt);
+  bsi = bsi_for_stmt (stmt);
+
+  tmpv = create_tmp_var (optype, "PROF");
+  tmp1 = create_tmp_var (optype, "PROF");
+  stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value));
+  stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
+  stmt3 = build3 (COND_EXPR, void_type_node,
+	    build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
+	    build1 (GOTO_EXPR, void_type_node, label_decl2),
+	    build1 (GOTO_EXPR, void_type_node, label_decl1));
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
+  bb1end = stmt3;
+
+  tmp2 = create_tmp_var (optype, "PROF");
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
+		  build2 (TREE_CODE (operation), optype, op1, tmpv));
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb2end = stmt1;
+
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
+		  build2 (TREE_CODE (operation), optype, op1, op2));
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb3end = stmt1;
+
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* Fix CFG. */
+  /* Edge e23 connects bb2 to bb3, etc. */
+  e12 = split_block (bb, bb1end);
+  bb2 = e12->dest;
+  bb2->count = count;
+  e23 = split_block (bb2, bb2end);
+  bb3 = e23->dest;
+  bb3->count = all - count;
+  e34 = split_block (bb3, bb3end);
+  bb4 = e34->dest;
+  bb4->count = all;
+
+  e12->flags &= ~EDGE_FALLTHRU;
+  e12->flags |= EDGE_FALSE_VALUE;
+  e12->probability = prob;
+  e12->count = count;
+
+  e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
+  e13->probability = REG_BR_PROB_BASE - prob;
+  e13->count = all - count;
+
+  remove_edge (e23);
   
-  emit_label (end_label);
+  e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
+  e24->probability = REG_BR_PROB_BASE;
+  e24->count = count;
+
+  e34->probability = REG_BR_PROB_BASE;
+  e34->count = all - count;
 
-  sequence = get_insns ();
-  end_sequence ();
-  rebuild_jump_labels (sequence);
-  return sequence;
+  return tmp2;
 }
 
 /* Do transform 1) on INSN if applicable.  */
 static bool
-divmod_fixed_value_transform (rtx insn)
+tree_divmod_fixed_value_transform (tree stmt)
 {
-  rtx set, set_src, set_dest, op1, op2, value, histogram;
-  enum rtx_code code;
-  enum machine_mode mode;
+  stmt_ann_t ann = get_stmt_ann (stmt);
+  histogram_value histogram;
+  enum tree_code code;
   gcov_type val, count, all;
-  edge e;
-
-  set = single_set (insn);
-  if (!set)
+  tree modify, op, op1, op2, result, value, tree_val;
+  int prob;
+
+  modify = stmt;
+  if (TREE_CODE (stmt) == RETURN_EXPR
+      && TREE_OPERAND (stmt, 0)
+      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+    modify = TREE_OPERAND (stmt, 0);
+  if (TREE_CODE (modify) != MODIFY_EXPR)
     return false;
-
-  set_src = SET_SRC (set);
-  set_dest = SET_DEST (set);
-  code = GET_CODE (set_src);
-  mode = GET_MODE (set_dest);
+  op = TREE_OPERAND (modify, 1);
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
+    return false;
+  code = TREE_CODE (op);
   
-  if (code != DIV && code != MOD && code != UDIV && code != UMOD)
+  if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
     return false;
-  op1 = XEXP (set_src, false);
-  op2 = XEXP (set_src, 1);
-
-  for (histogram = REG_NOTES (insn);
-       histogram;
-       histogram = XEXP (histogram, 1))
-    if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
-	&& XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_SINGLE_VALUE))
+
+  op1 = TREE_OPERAND (op, 0);
+  op2 = TREE_OPERAND (op, 1);
+  if (!ann->histograms)
+    return false;
+
+  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
+    if (histogram->type == HIST_TYPE_SINGLE_VALUE)
       break;
 
   if (!histogram)
     return false;
 
-  histogram = XEXP (XEXP (histogram, 0), 1);
-  value = XEXP (histogram, 0);
-  histogram = XEXP (histogram, 1);
-  val = INTVAL (XEXP (histogram, 0));
-  histogram = XEXP (histogram, 1);
-  count = INTVAL (XEXP (histogram, 0));
-  histogram = XEXP (histogram, 1);
-  all = INTVAL (XEXP (histogram, 0));
+  value = histogram->hvalue.value;
+  val = histogram->hvalue.counters[0];
+  count = histogram->hvalue.counters[1];
+  all = histogram->hvalue.counters[2];
 
   /* We require that count is at least half of all; this means
      that for the transformation to fire the value must be constant
      at least 50% of time (and 75% gives the guarantee of usage).  */
-  if (!rtx_equal_p (op2, value) || 2 * count < all)
+  if (simple_cst_equal (op2, value) != 1 || 2 * count < all)
     return false;
 
-  if (rtl_dump_file)
-    fprintf (rtl_dump_file, "Div/mod by constant transformation on insn %d\n",
-	     INSN_UID (insn));
+  if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
+    return false;
 
-  e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
-  delete_insn (insn);
-  
-  insert_insn_on_edge (
-	gen_divmod_fixed_value (mode, code, set_dest, op1, op2, val), e);
+  /* Compute probability of taking the optimal path.  */
+  prob = (count * REG_BR_PROB_BASE + all / 2) / all;
+
+  tree_val = build_int_cst_wide (get_gcov_type (),
+				 (unsigned HOST_WIDE_INT) val,
+				 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
+  result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "Div/mod by constant ");
+      print_generic_expr (dump_file, value, TDF_SLIM);
+      fprintf (dump_file, "=");
+      print_generic_expr (dump_file, tree_val, TDF_SLIM);
+      fprintf (dump_file, " transformation on insn ");
+      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+    }
+
+  TREE_OPERAND (modify, 1) = result;
 
   return true;
 }
 
-/* Generate code for transformation 2 (with MODE and OPERATION, operands OP1
-   and OP2 and result TARGET).  */
-static rtx
-gen_mod_pow2 (enum machine_mode mode, enum rtx_code operation, rtx target,
-	      rtx op1, rtx op2)
+/* Generate code for transformation 2 (with OPERATION, operands OP1
+   and OP2, parent modify-expr STMT and probability of taking the optimal 
+   path PROB, which is equivalent to COUNT/ALL within roundoff error).  
+   This generates the result into a temp and returns 
+   the temp; it does not replace or alter the original STMT.  */
+static tree
+tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, 
+	       gcov_type count, gcov_type all)
 {
-  rtx tmp, tmp1, tmp2, tmp3;
-  rtx neq_label = gen_label_rtx ();
-  rtx end_label = gen_label_rtx ();
-  rtx sequence;
-
-  start_sequence ();
+  tree stmt1, stmt2, stmt3, stmt4;
+  tree tmp2, tmp3;
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+  tree bb1end, bb2end, bb3end;
+  basic_block bb, bb2, bb3, bb4;
+  tree optype = TREE_TYPE (operation);
+  edge e12, e13, e23, e24, e34;
+  block_stmt_iterator bsi;
+  tree result = create_tmp_var (optype, "PROF");
+
+  bb = bb_for_stmt (stmt);
+  bsi = bsi_for_stmt (stmt);
+
+  tmp2 = create_tmp_var (optype, "PROF");
+  tmp3 = create_tmp_var (optype, "PROF");
+  stmt2 = build2 (MODIFY_EXPR, optype, tmp2, 
+		  build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
+  stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
+		  build2 (BIT_AND_EXPR, optype, tmp2, op2));
+  stmt4 = build3 (COND_EXPR, void_type_node,
+		  build2 (NE_EXPR, boolean_type_node,
+			  tmp3, build_int_cst (optype, 0)),
+		  build1 (GOTO_EXPR, void_type_node, label_decl2),
+	 	  build1 (GOTO_EXPR, void_type_node, label_decl1));
+  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
+  bb1end = stmt4;
+
+  /* tmp2 == op2-1 inherited from previous block */
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  stmt1 = build2 (MODIFY_EXPR, optype, result,
+		  build2 (BIT_AND_EXPR, optype, op1, tmp2));
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb2end = stmt1;
+
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  stmt1 = build2 (MODIFY_EXPR, optype, result,
+		  build2 (TREE_CODE (operation), optype, op1, op2));
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb3end = stmt1;
+
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* Fix CFG. */
+  /* Edge e23 connects bb2 to bb3, etc. */
+  e12 = split_block (bb, bb1end);
+  bb2 = e12->dest;
+  bb2->count = count;
+  e23 = split_block (bb2, bb2end);
+  bb3 = e23->dest;
+  bb3->count = all - count;
+  e34 = split_block (bb3, bb3end);
+  bb4 = e34->dest;
+  bb4->count = all;
+
+  e12->flags &= ~EDGE_FALLTHRU;
+  e12->flags |= EDGE_FALSE_VALUE;
+  e12->probability = prob;
+  e12->count = count;
+
+  e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
+  e13->probability = REG_BR_PROB_BASE - prob;
+  e13->count = all - count;
+
+  remove_edge (e23);
   
-  if (!REG_P (op2))
-    {
-      tmp = gen_reg_rtx (mode);
-      emit_move_insn (tmp, copy_rtx (op2));
-    }
-  else
-    tmp = op2;
-
-  tmp1 = expand_simple_binop (mode, PLUS, tmp, constm1_rtx, NULL_RTX,
-			      0, OPTAB_WIDEN);
-  tmp2 = expand_simple_binop (mode, AND, tmp, tmp1, NULL_RTX,
-			      0, OPTAB_WIDEN);
-  do_compare_rtx_and_jump (tmp2, const0_rtx, NE, 0, mode, NULL_RTX,
-			   NULL_RTX, neq_label);
-  tmp3 = expand_simple_binop (mode, AND, op1, tmp1, target,
-			      0, OPTAB_WIDEN);
-  if (tmp3 != target)
-    emit_move_insn (copy_rtx (target), tmp3);
-  emit_jump_insn (gen_jump (end_label));
-  emit_barrier ();
-
-  emit_label (neq_label);
-  tmp1 = simplify_gen_binary (operation, mode, copy_rtx (op1), copy_rtx (tmp));
-  tmp1 = force_operand (tmp1, target);
-  if (tmp1 != target)
-    emit_move_insn (target, tmp1);
-  
-  emit_label (end_label);
+  e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
+  e24->probability = REG_BR_PROB_BASE;
+  e24->count = count;
+
+  e34->probability = REG_BR_PROB_BASE;
+  e34->count = all - count;
 
-  sequence = get_insns ();
-  end_sequence ();
-  rebuild_jump_labels (sequence);
-  return sequence;
+  return result;
 }
 
 /* Do transform 2) on INSN if applicable.  */
 static bool
-mod_pow2_value_transform (rtx insn)
+tree_mod_pow2_value_transform (tree stmt)
 {
-  rtx set, set_src, set_dest, op1, op2, value, histogram;
-  enum rtx_code code;
-  enum machine_mode mode;
-  gcov_type wrong_values, count;
-  edge e;
-  int i;
-
-  set = single_set (insn);
-  if (!set)
+  stmt_ann_t ann = get_stmt_ann (stmt);
+  histogram_value histogram;
+  enum tree_code code;
+  gcov_type count, wrong_values, all;
+  tree modify, op, op1, op2, result, value;
+  int prob;
+
+  modify = stmt;
+  if (TREE_CODE (stmt) == RETURN_EXPR
+      && TREE_OPERAND (stmt, 0)
+      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+    modify = TREE_OPERAND (stmt, 0);
+  if (TREE_CODE (modify) != MODIFY_EXPR)
     return false;
-
-  set_src = SET_SRC (set);
-  set_dest = SET_DEST (set);
-  code = GET_CODE (set_src);
-  mode = GET_MODE (set_dest);
+  op = TREE_OPERAND (modify, 1);
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
+    return false;
+  code = TREE_CODE (op);
   
-  if (code != UMOD)
+  if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
     return false;
-  op1 = XEXP (set_src, 0);
-  op2 = XEXP (set_src, 1);
-
-  for (histogram = REG_NOTES (insn);
-       histogram;
-       histogram = XEXP (histogram, 1))
-    if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
-	&& XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_POW2))
+
+  op1 = TREE_OPERAND (op, 0);
+  op2 = TREE_OPERAND (op, 1);
+  if (!ann->histograms)
+    return false;
+
+  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
+    if (histogram->type == HIST_TYPE_POW2)
       break;
 
   if (!histogram)
     return false;
 
-  histogram = XEXP (XEXP (histogram, 0), 1);
-  value = XEXP (histogram, 0);
-  histogram = XEXP (histogram, 1);
-  wrong_values =INTVAL (XEXP (histogram, 0));
-  histogram = XEXP (histogram, 1);
+  value = histogram->hvalue.value;
+  wrong_values = histogram->hvalue.counters[0];
+  count = histogram->hvalue.counters[1];
 
-  count = 0;
-  for (i = 0; i < GET_MODE_BITSIZE (mode); i++)
+  /* We require that we hit a power of 2 at least half of all evaluations.  */
+  if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
+    return false;
+
+  if (dump_file)
     {
-      count += INTVAL (XEXP (histogram, 0));
-      histogram = XEXP (histogram, 1);
+      fprintf (dump_file, "Mod power of 2 transformation on insn ");
+      print_generic_stmt (dump_file, stmt, TDF_SLIM);
     }
 
-  if (!rtx_equal_p (op2, value))
+  /* Compute probability of taking the optimal path.  */
+  all = count + wrong_values;
+  if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
     return false;
 
-  /* We require that we hit a power of two at least half of all evaluations.  */
-  if (count < wrong_values)
-    return false;
+  prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 
-  if (rtl_dump_file)
-    fprintf (rtl_dump_file, "Mod power of 2 transformation on insn %d\n",
-	     INSN_UID (insn));
+  result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 
-  e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
-  delete_insn (insn);
-  
-  insert_insn_on_edge (
-	gen_mod_pow2 (mode, code, set_dest, op1, op2), e);
+  TREE_OPERAND (modify, 1) = result;
 
   return true;
 }
 
-/* Generate code for transformations 3 and 4 (with MODE and OPERATION,
-   operands OP1 and OP2, result TARGET and at most SUB subtractions).  */
-static rtx
-gen_mod_subtract (enum machine_mode mode, enum rtx_code operation,
-		  rtx target, rtx op1, rtx op2, int sub)
+/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
+   and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
+   support.  Currently only NCOUNTS==0 or 1 is supported and this is
+   built into this interface.  The probabilities of taking the optimal 
+   paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
+   COUNT2/ALL respectively within roundoff error).  This generates the 
+   result into a temp and returns the temp; it does not replace or alter 
+   the original STMT.  */
+/* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
+
+static tree
+tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, 
+		    int prob1, int prob2, int ncounts,
+		    gcov_type count1, gcov_type count2, gcov_type all)
 {
-  rtx tmp, tmp1;
-  rtx end_label = gen_label_rtx ();
-  rtx sequence;
-  int i;
+  tree stmt1, stmt2, stmt3;
+  tree tmp1;
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+  tree bb1end, bb2end = NULL_TREE, bb3end;
+  basic_block bb, bb2, bb3, bb4;
+  tree optype = TREE_TYPE (operation);
+  edge e12, e23 = 0, e24, e34, e14;
+  block_stmt_iterator bsi;
+  tree result = create_tmp_var (optype, "PROF");
+
+  bb = bb_for_stmt (stmt);
+  bsi = bsi_for_stmt (stmt);
+
+  tmp1 = create_tmp_var (optype, "PROF");
+  stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
+  stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
+  stmt3 = build3 (COND_EXPR, void_type_node,
+	    build2 (LT_EXPR, boolean_type_node, result, tmp1),
+	    build1 (GOTO_EXPR, void_type_node, label_decl3),
+	    build1 (GOTO_EXPR, void_type_node, 
+		    ncounts ? label_decl1 : label_decl2));
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
+  bb1end = stmt3;
+
+  if (ncounts)	/* Assumed to be 0 or 1 */
+    {
+      label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+      stmt1 = build2 (MODIFY_EXPR, optype, result,
+		      build2 (MINUS_EXPR, optype, result, tmp1));
+      stmt2 = build3 (COND_EXPR, void_type_node,
+		build2 (LT_EXPR, boolean_type_node, result, tmp1),
+		build1 (GOTO_EXPR, void_type_node, label_decl3),
+		build1 (GOTO_EXPR, void_type_node, label_decl2));
+      bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+      bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+      bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+      bb2end = stmt2;
+    }
 
-  start_sequence ();
-  
-  if (!REG_P (op2))
+  /* Fallback case. */
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  stmt1 = build2 (MODIFY_EXPR, optype, result,
+		    build2 (TREE_CODE (operation), optype, result, tmp1));
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb3end = stmt1;
+
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* Fix CFG. */
+  /* Edge e23 connects bb2 to bb3, etc. */
+  /* However block 3 is optional; if it is not there, references
+     to 3 really refer to block 2. */
+  e12 = split_block (bb, bb1end);
+  bb2 = e12->dest;
+  bb2->count = all - count1;
+    
+  if (ncounts)	/* Assumed to be 0 or 1.  */
     {
-      tmp = gen_reg_rtx (mode);
-      emit_move_insn (tmp, copy_rtx (op2));
+      e23 = split_block (bb2, bb2end);
+      bb3 = e23->dest;
+      bb3->count = all - count1 - count2;
     }
-  else
-    tmp = op2;
 
-  emit_move_insn (target, copy_rtx (op1));
-  do_compare_rtx_and_jump (target, tmp, LTU, 0, mode, NULL_RTX,
-			   NULL_RTX, end_label);
-  
+  e34 = split_block (ncounts ? bb3 : bb2, bb3end);
+  bb4 = e34->dest;
+  bb4->count = all;
+
+  e12->flags &= ~EDGE_FALLTHRU;
+  e12->flags |= EDGE_FALSE_VALUE;
+  e12->probability = REG_BR_PROB_BASE - prob1;
+  e12->count = all - count1;
 
-  for (i = 0; i < sub; i++)
+  e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
+  e14->probability = prob1;
+  e14->count = count1;
+
+  if (ncounts)  /* Assumed to be 0 or 1.  */
     {
-      tmp1 = expand_simple_binop (mode, MINUS, target, tmp, target,
-	    			  0, OPTAB_WIDEN);
-      if (tmp1 != target)
-	emit_move_insn (target, tmp1);
-      do_compare_rtx_and_jump (target, tmp, LTU, 0, mode, NULL_RTX,
-    			       NULL_RTX, end_label);
+      e23->flags &= ~EDGE_FALLTHRU;
+      e23->flags |= EDGE_FALSE_VALUE;
+      e23->count = all - count1 - count2;
+      e23->probability = REG_BR_PROB_BASE - prob2;
+
+      e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
+      e24->probability = prob2;
+      e24->count = count2;
     }
 
-  tmp1 = simplify_gen_binary (operation, mode, copy_rtx (target), copy_rtx (tmp));
-  tmp1 = force_operand (tmp1, target);
-  if (tmp1 != target)
-    emit_move_insn (target, tmp1);
-  
-  emit_label (end_label);
+  e34->probability = REG_BR_PROB_BASE;
+  e34->count = all - count1 - count2;
 
-  sequence = get_insns ();
-  end_sequence ();
-  rebuild_jump_labels (sequence);
-  return sequence;
+  return result;
 }
 
 /* Do transforms 3) and 4) on INSN if applicable.  */
 static bool
-mod_subtract_transform (rtx insn)
+tree_mod_subtract_transform (tree stmt)
 {
-  rtx set, set_src, set_dest, op1, op2, value, histogram;
-  enum rtx_code code;
-  enum machine_mode mode;
-  gcov_type wrong_values, counts[2], count, all;
-  edge e;
-  int i;
-
-  set = single_set (insn);
-  if (!set)
+  stmt_ann_t ann = get_stmt_ann (stmt);
+  histogram_value histogram;
+  enum tree_code code;
+  gcov_type count, wrong_values, all;
+  tree modify, op, op1, op2, result, value;
+  int prob1, prob2;
+  unsigned int i;
+
+  modify = stmt;
+  if (TREE_CODE (stmt) == RETURN_EXPR
+      && TREE_OPERAND (stmt, 0)
+      && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+    modify = TREE_OPERAND (stmt, 0);
+  if (TREE_CODE (modify) != MODIFY_EXPR)
     return false;
-
-  set_src = SET_SRC (set);
-  set_dest = SET_DEST (set);
-  code = GET_CODE (set_src);
-  mode = GET_MODE (set_dest);
+  op = TREE_OPERAND (modify, 1);
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
+    return false;
+  code = TREE_CODE (op);
   
-  if (code != UMOD)
+  if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
+    return false;
+
+  op1 = TREE_OPERAND (op, 0);
+  op2 = TREE_OPERAND (op, 1);
+  if (!ann->histograms)
     return false;
-  op1 = XEXP (set_src, 0);
-  op2 = XEXP (set_src, 1);
-
-  for (histogram = REG_NOTES (insn);
-       histogram;
-       histogram = XEXP (histogram, 1))
-    if (REG_NOTE_KIND (histogram) == REG_VALUE_PROFILE
-	&& XEXP (XEXP (histogram, 0), 0) == GEN_INT (HIST_TYPE_INTERVAL))
+
+  for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
+    if (histogram->type == HIST_TYPE_INTERVAL)
       break;
 
   if (!histogram)
     return false;
 
-  histogram = XEXP (XEXP (histogram, 0), 1);
-  value = XEXP (histogram, 0);
-  histogram = XEXP (histogram, 1);
-
+  value = histogram->hvalue.value;
   all = 0;
-  for (i = 0; i < 2; i++)
-    {
-      counts[i] = INTVAL (XEXP (histogram, 0));
-      all += counts[i];
-      histogram = XEXP (histogram, 1);
-    }
-  wrong_values = INTVAL (XEXP (histogram, 0));
-  histogram = XEXP (histogram, 1);
-  wrong_values += INTVAL (XEXP (histogram, 0));
+  wrong_values = 0;
+  for (i = 0; i < histogram->hdata.intvl.steps; i++)
+    all += histogram->hvalue.counters[i];
+
+  wrong_values += histogram->hvalue.counters[i];
+  wrong_values += histogram->hvalue.counters[i+1];
   all += wrong_values;
 
+  /* Compute probability of taking the optimal path.  */
+  if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
+    return false;
+
   /* We require that we use just subtractions in at least 50% of all
      evaluations.  */
   count = 0;
-  for (i = 0; i < 2; i++)
+  for (i = 0; i < histogram->hdata.intvl.steps; i++)
     {
-      count += counts[i];
+      count += histogram->hvalue.counters[i];
       if (count * 2 >= all)
 	break;
     }
-  
-  if (i == 2)
+  if (i == histogram->hdata.intvl.steps)
     return false;
 
-  if (rtl_dump_file)
-    fprintf (rtl_dump_file, "Mod subtract transformation on insn %d\n",
-	     INSN_UID (insn));
+  if (dump_file)
+    {
+      fprintf (dump_file, "Mod subtract transformation on insn ");
+      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+    }
 
-  e = split_block (BLOCK_FOR_INSN (insn), PREV_INSN (insn));
-  delete_insn (insn);
-  
-  insert_insn_on_edge (
-	gen_mod_subtract (mode, code, set_dest, op1, op2, i), e);
+  /* Compute probability of taking the optimal path(s).  */
+  prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
+  prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
+
+  /* In practice, "steps" is always 2.  This interface reflects this,
+     and will need to be changed if "steps" can change.  */
+  result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
+			    histogram->hvalue.counters[0], 
+			    histogram->hvalue.counters[1], all);
+
+  TREE_OPERAND (modify, 1) = result;
 
   return true;
 }
+
+struct value_prof_hooks {
+  /* Find list of values for which we want to measure histograms.  */
+  void (*find_values_to_profile) (histogram_values *);
+
+  /* Identify and exploit properties of values that are hard to analyze
+     statically.  See value-prof.c for more detail.  */
+  bool (*value_profile_transformations) (void);  
+};
+
+/* Find values inside STMT for that we want to measure histograms for
+   division/modulo optimization.  */
+static void
+tree_divmod_values_to_profile (tree stmt, histogram_values *values)
+{
+  tree assign, lhs, rhs, divisor, op0, type;
+  histogram_value hist;
+
+  if (TREE_CODE (stmt) == RETURN_EXPR)
+    assign = TREE_OPERAND (stmt, 0);
+  else
+    assign = stmt;
+
+  if (!assign
+      || TREE_CODE (assign) != MODIFY_EXPR)
+    return;
+  lhs = TREE_OPERAND (assign, 0);
+  type = TREE_TYPE (lhs);
+  if (!INTEGRAL_TYPE_P (type))
+    return;
+
+  rhs = TREE_OPERAND (assign, 1);
+  switch (TREE_CODE (rhs))
+    {
+    case TRUNC_DIV_EXPR:
+    case TRUNC_MOD_EXPR:
+      divisor = TREE_OPERAND (rhs, 1);
+      op0 = TREE_OPERAND (rhs, 0);
+
+      VEC_reserve (histogram_value, heap, *values, 3);
+
+      if (is_gimple_reg (divisor))
+	{
+	  /* Check for the case where the divisor is the same value most
+	     of the time.  */
+	  hist = ggc_alloc (sizeof (*hist));
+	  hist->hvalue.value = divisor;
+	  hist->hvalue.stmt = stmt;
+	  hist->type = HIST_TYPE_SINGLE_VALUE;
+	  VEC_quick_push (histogram_value, *values, hist);
+	}
+
+      /* For mod, check whether it is not often a noop (or replaceable by
+	 a few subtractions).  */
+      if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
+	  && TYPE_UNSIGNED (type))
+	{
+          /* Check for a special case where the divisor is power of 2.  */
+	  hist = ggc_alloc (sizeof (*hist));
+	  hist->hvalue.value = divisor;
+	  hist->hvalue.stmt = stmt;
+	  hist->type = HIST_TYPE_POW2;
+	  VEC_quick_push (histogram_value, *values, hist);
+
+	  hist = ggc_alloc (sizeof (*hist));
+	  hist->hvalue.stmt = stmt;
+	  hist->hvalue.value
+		  = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
+	  hist->type = HIST_TYPE_INTERVAL;
+	  hist->hdata.intvl.int_start = 0;
+	  hist->hdata.intvl.steps = 2;
+	  VEC_quick_push (histogram_value, *values, hist);
+	}
+      return;
+
+    default:
+      return;
+    }
+}
+
+/* Find values inside STMT for that we want to measure histograms and adds
+   them to list VALUES.  */
+
+static void
+tree_values_to_profile (tree stmt, histogram_values *values)
+{
+  if (flag_value_profile_transformations)
+    tree_divmod_values_to_profile (stmt, values);
+}
+
+static void
+tree_find_values_to_profile (histogram_values *values)
+{
+  basic_block bb;
+  block_stmt_iterator bsi;
+  unsigned i;
+  histogram_value hist;
+
+  *values = NULL;
+  FOR_EACH_BB (bb)
+    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+      tree_values_to_profile (bsi_stmt (bsi), values);
+  
+  for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
+    {
+      switch (hist->type)
+        {
+	case HIST_TYPE_INTERVAL:
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Interval counter for tree ");
+	      print_generic_expr (dump_file, hist->hvalue.stmt, 
+				  TDF_SLIM);
+	      fprintf (dump_file, ", range %d -- %d.\n",
+		     hist->hdata.intvl.int_start,
+		     (hist->hdata.intvl.int_start
+		      + hist->hdata.intvl.steps - 1));
+	    }
+	  hist->n_counters = hist->hdata.intvl.steps + 2;
+	  break;
+
+	case HIST_TYPE_POW2:
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Pow2 counter for tree ");
+	      print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
+	      fprintf (dump_file, ".\n");
+	    }
+	  hist->n_counters = 2;
+	  break;
+
+	case HIST_TYPE_SINGLE_VALUE:
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Single value counter for tree ");
+	      print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
+	      fprintf (dump_file, ".\n");
+	    }
+	  hist->n_counters = 3;
+	  break;
+
+	case HIST_TYPE_CONST_DELTA:
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Constant delta counter for tree ");
+	      print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
+	      fprintf (dump_file, ".\n");
+	    }
+	  hist->n_counters = 4;
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+static struct value_prof_hooks tree_value_prof_hooks = {
+  tree_find_values_to_profile,
+  tree_value_profile_transformations
+};
+
+void
+tree_register_value_prof_hooks (void)
+{
+  value_prof_hooks = &tree_value_prof_hooks;
+  gcc_assert (ir_type ());
+}
+
+/* IR-independent entry points.  */
+void
+find_values_to_profile (histogram_values *values)
+{
+  (value_prof_hooks->find_values_to_profile) (values);
+}
+
+bool
+value_profile_transformations (void)
+{
+  return (value_prof_hooks->value_profile_transformations) ();
+}
+
+