Subversion Repositories openrisc

/* Transformations based on profile information for values.

   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009  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 3, 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 COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#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 "value-prof.h"

#include "output.h"

#include "flags.h"

#include "insn-config.h"

#include "recog.h"

#include "optabs.h"

#include "regs.h"

#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 "cgraph.h"

#include "timevar.h"

#include "tree-pass.h"

#include "toplev.h"

#include "pointer-set.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.

   3) Indirect/virtual call specialization. If we can determine most

      common function callee in indirect/virtual call. We can use this

      information to improve code effectiveness (especially info for

      inliner).

   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 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.  */

static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type);

static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type);

static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type,

                                 gcov_type);

static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);

static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);

static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);

static bool gimple_stringops_transform (gimple_stmt_iterator *);

static bool gimple_ic_transform (gimple);

/* Allocate histogram value.  */

static histogram_value

gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,

                              enum hist_type type, gimple stmt, tree value)

{

   histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));

   hist->hvalue.value = value;

   hist->hvalue.stmt = stmt;

   hist->type = type;

   return hist;

}

/* Hash value for histogram.  */

static hashval_t

histogram_hash (const void *x)

{

  return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);

}

/* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */

static int

histogram_eq (const void *x, const void *y)

{

  return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;

}

/* Set histogram for STMT.  */

static void

set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)

{

  void **loc;

  if (!hist && !VALUE_HISTOGRAMS (fun))

    return;

  if (!VALUE_HISTOGRAMS (fun))

    VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,

                                           histogram_eq, NULL);

  loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,

                                  htab_hash_pointer (stmt),

                                  hist ? INSERT : NO_INSERT);

  if (!hist)

    {

      if (loc)

        htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);

      return;

    }

  *loc = hist;

}

/* Get histogram list for STMT.  */

histogram_value

gimple_histogram_value (struct function *fun, gimple stmt)

{

  if (!VALUE_HISTOGRAMS (fun))

    return NULL;

  return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,

                                                htab_hash_pointer (stmt));

}

/* Add histogram for STMT.  */

void

gimple_add_histogram_value (struct function *fun, gimple stmt,

                            histogram_value hist)

{

  hist->hvalue.next = gimple_histogram_value (fun, stmt);

  set_histogram_value (fun, stmt, hist);

}

/* Remove histogram HIST from STMT's histogram list.  */

void

gimple_remove_histogram_value (struct function *fun, gimple stmt,

                               histogram_value hist)

{

  histogram_value hist2 = gimple_histogram_value (fun, stmt);

  if (hist == hist2)

    {

      set_histogram_value (fun, stmt, hist->hvalue.next);

    }

  else

    {

      while (hist2->hvalue.next != hist)

        hist2 = hist2->hvalue.next;

      hist2->hvalue.next = hist->hvalue.next;

    }

  free (hist->hvalue.counters);

#ifdef ENABLE_CHECKING

  memset (hist, 0xab, sizeof (*hist));

#endif

  free (hist);

}

/* Lookup histogram of type TYPE in the STMT.  */

histogram_value

gimple_histogram_value_of_type (struct function *fun, gimple stmt,

                                enum hist_type type)

{

  histogram_value hist;

  for (hist = gimple_histogram_value (fun, stmt); hist;

       hist = hist->hvalue.next)

    if (hist->type == type)

      return hist;

  return NULL;

}

/* Dump information about HIST to DUMP_FILE.  */

static void

dump_histogram_value (FILE *dump_file, histogram_value hist)

{

  switch (hist->type)

    {

    case HIST_TYPE_INTERVAL:

      fprintf (dump_file, "Interval counter range %d -- %d",

               hist->hdata.intvl.int_start,

               (hist->hdata.intvl.int_start

                + hist->hdata.intvl.steps - 1));

      if (hist->hvalue.counters)

        {

           unsigned int i;

           fprintf(dump_file, " [");

           for (i = 0; i < hist->hdata.intvl.steps; i++)

             fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,

                      hist->hdata.intvl.int_start + i,

                      (HOST_WIDEST_INT) hist->hvalue.counters[i]);

           fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[i]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_POW2:

      fprintf (dump_file, "Pow2 counter ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC

                    " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0],

                    (HOST_WIDEST_INT) hist->hvalue.counters[1]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_SINGLE_VALUE:

      fprintf (dump_file, "Single value ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC

                    " match:"HOST_WIDEST_INT_PRINT_DEC

                    " wrong:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0],

                    (HOST_WIDEST_INT) hist->hvalue.counters[1],

                    (HOST_WIDEST_INT) hist->hvalue.counters[2]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_AVERAGE:

      fprintf (dump_file, "Average value ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC

                    " times:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0],

                    (HOST_WIDEST_INT) hist->hvalue.counters[1]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_IOR:

      fprintf (dump_file, "IOR value ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_CONST_DELTA:

      fprintf (dump_file, "Constant delta ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC

                    " match:"HOST_WIDEST_INT_PRINT_DEC

                    " wrong:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0],

                    (HOST_WIDEST_INT) hist->hvalue.counters[1],

                    (HOST_WIDEST_INT) hist->hvalue.counters[2]);

        }

      fprintf (dump_file, ".\n");

      break;

    case HIST_TYPE_INDIR_CALL:

      fprintf (dump_file, "Indirect call ");

      if (hist->hvalue.counters)

        {

           fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC

                    " match:"HOST_WIDEST_INT_PRINT_DEC

                    " all:"HOST_WIDEST_INT_PRINT_DEC,

                    (HOST_WIDEST_INT) hist->hvalue.counters[0],

                    (HOST_WIDEST_INT) hist->hvalue.counters[1],

                    (HOST_WIDEST_INT) hist->hvalue.counters[2]);

        }

      fprintf (dump_file, ".\n");

      break;

   }

}

/* Dump all histograms attached to STMT to DUMP_FILE.  */

void

dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)

{

  histogram_value hist;

  for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)

   dump_histogram_value (dump_file, hist);

}

/* Remove all histograms associated with STMT.  */

void

gimple_remove_stmt_histograms (struct function *fun, gimple stmt)

{

  histogram_value val;

  while ((val = gimple_histogram_value (fun, stmt)) != NULL)

    gimple_remove_histogram_value (fun, stmt, val);

}

/* Duplicate all histograms associates with OSTMT to STMT.  */

void

gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,

                                  struct function *ofun, gimple ostmt)

{

  histogram_value val;

  for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)

    {

      histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);

      memcpy (new_val, val, sizeof (*val));

      new_val->hvalue.stmt = stmt;

      new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);

      memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);

      gimple_add_histogram_value (fun, stmt, new_val);

    }

}

/* Move all histograms associated with OSTMT to STMT.  */

void

gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)

{

  histogram_value val = gimple_histogram_value (fun, ostmt);

  if (val)

    {

      /* The following three statements can't be reordered,

         because histogram hashtab relies on stmt field value

         for finding the exact slot. */

      set_histogram_value (fun, ostmt, NULL);

      for (; val != NULL; val = val->hvalue.next)

        val->hvalue.stmt = stmt;

      set_histogram_value (fun, stmt, val);

    }

}

static bool error_found = false;

/* Helper function for verify_histograms.  For each histogram reachable via htab

   walk verify that it was reached via statement walk.  */

static int

visit_hist (void **slot, void *data)

{

  struct pointer_set_t *visited = (struct pointer_set_t *) data;

  histogram_value hist = *(histogram_value *) slot;

  if (!pointer_set_contains (visited, hist))

    {

      error ("Dead histogram");

      dump_histogram_value (stderr, hist);

      debug_gimple_stmt (hist->hvalue.stmt);

      error_found = true;

    }

  return 1;

}

/* Verify sanity of the histograms.  */

void

verify_histograms (void)

{

  basic_block bb;

  gimple_stmt_iterator gsi;

  histogram_value hist;

  struct pointer_set_t *visited_hists;

  error_found = false;

  visited_hists = pointer_set_create ();

  FOR_EACH_BB (bb)

    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

      {

        gimple stmt = gsi_stmt (gsi);

        for (hist = gimple_histogram_value (cfun, stmt); hist;

             hist = hist->hvalue.next)

          {

            if (hist->hvalue.stmt != stmt)

              {

                error ("Histogram value statement does not correspond to "

                       "the statement it is associated with");

                debug_gimple_stmt (stmt);

                dump_histogram_value (stderr, hist);

                error_found = true;

              }

            pointer_set_insert (visited_hists, hist);

          }

      }

  if (VALUE_HISTOGRAMS (cfun))

    htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);

  pointer_set_destroy (visited_hists);

  if (error_found)

    internal_error ("verify_histograms failed");

}

/* Helper function for verify_histograms.  For each histogram reachable via htab

   walk verify that it was reached via statement walk.  */

static int

free_hist (void **slot, void *data ATTRIBUTE_UNUSED)

{

  histogram_value hist = *(histogram_value *) slot;

  free (hist->hvalue.counters);

#ifdef ENABLE_CHECKING

  memset (hist, 0xab, sizeof (*hist));

#endif

  free (hist);

  return 1;

}

void

free_histograms (void)

{

  if (VALUE_HISTOGRAMS (cfun))

    {

      htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);

      htab_delete (VALUE_HISTOGRAMS (cfun));

      VALUE_HISTOGRAMS (cfun) = NULL;

    }

}

/* 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 (gimple stmt, const char * name,

               gcov_type *count, gcov_type *all, gcov_type bb_count)

{

  if (*all != bb_count || *count > *all)

    {

      location_t locus;

      locus = (stmt != NULL)

              ? gimple_location (stmt)

              : DECL_SOURCE_LOCATION (current_function_decl);

      if (flag_profile_correction)

        {

          inform (locus, "Correcting inconsistent value profile: "

                  "%s profiler overall count (%d) does not match BB count "

                  "(%d)", name, (int)*all, (int)bb_count);

          *all = bb_count;

          if (*count > *all)

            *count = *all;

          return false;

        }

      else

        {

          error_at (locus, "Corrupted value profile: %s "

                    "profiler overall count (%d) does not match BB count (%d)",

                    name, (int)*all, (int)bb_count);

          return true;

        }

    }

  return false;

}

/* GIMPLE based transformations. */

static bool

gimple_value_profile_transformations (void)

{

  basic_block bb;

  gimple_stmt_iterator gsi;

  bool changed = false;

  FOR_EACH_BB (bb)

    {

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

        {

          gimple stmt = gsi_stmt (gsi);

          histogram_value th = gimple_histogram_value (cfun, stmt);

          if (!th)

            continue;

          if (dump_file)

            {

              fprintf (dump_file, "Trying transformations on stmt ");

              print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);

              dump_histograms_for_stmt (cfun, dump_file, stmt);

            }

          /* 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

              && (gimple_mod_subtract_transform (&gsi)

                  || gimple_divmod_fixed_value_transform (&gsi)

                  || gimple_mod_pow2_value_transform (&gsi)

                  || gimple_stringops_transform (&gsi)

                  || gimple_ic_transform (stmt)))

            {

              stmt = gsi_stmt (gsi);

              changed = true;

              /* Original statement may no longer be in the same block. */

              if (bb != gimple_bb (stmt))

                {

                  bb = gimple_bb (stmt);

                  gsi = gsi_for_stmt (stmt);

                }

            }

        }

    }

  if (changed)

    {

      counts_to_freqs ();

    }

  return changed;

}

/* Generate code for transformation 1 (with parent gimple assignment

   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

gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count,

                           gcov_type all)

{

  gimple stmt1, stmt2, stmt3;

  tree tmp1, tmp2, tmpv;

  gimple bb1end, bb2end, bb3end;

  basic_block bb, bb2, bb3, bb4;

  tree optype, op1, op2;

  edge e12, e13, e23, e24, e34;

  gimple_stmt_iterator gsi;

  gcc_assert (is_gimple_assign (stmt)

              && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR

                  || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));

  optype = TREE_TYPE (gimple_assign_lhs (stmt));

  op1 = gimple_assign_rhs1 (stmt);

  op2 = gimple_assign_rhs2 (stmt);

  bb = gimple_bb (stmt);

  gsi = gsi_for_stmt (stmt);

  tmpv = create_tmp_var (optype, "PROF");

  tmp1 = create_tmp_var (optype, "PROF");

  stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value));

  stmt2 = gimple_build_assign (tmp1, op2);

  stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);

  gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);

  gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);

  gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);

  bb1end = stmt3;

  tmp2 = create_tmp_var (optype, "PROF");

  stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,

                                        op1, tmpv);

  gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);

  bb2end = stmt1;

  stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,

                                        op1, op2);

  gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);

  bb3end = stmt1;

  /* 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);

  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;

  return tmp2;

}

/* Do transform 1) on INSN if applicable.  */

static bool

gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)

{

  histogram_value histogram;

  enum tree_code code;

  gcov_type val, count, all;

  tree result, value, tree_val;

  gcov_type prob;

  gimple stmt;

  stmt = gsi_stmt (*si);

  if (gimple_code (stmt) != GIMPLE_ASSIGN)

    return false;

  if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))

    return false;

  code = gimple_assign_rhs_code (stmt);

  if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)

    return false;

  histogram = gimple_histogram_value_of_type (cfun, stmt,

                                              HIST_TYPE_SINGLE_VALUE);

  if (!histogram)

    return false;

  value = histogram->hvalue.value;

  val = histogram->hvalue.counters[0];

  count = histogram->hvalue.counters[1];

  all = histogram->hvalue.counters[2];

  gimple_remove_histogram_value (cfun, stmt, histogram);

  /* 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 (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1

      || 2 * count < all

      || optimize_bb_for_size_p (gimple_bb (stmt)))

    return false;

  if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))

    return false;