Subversion Repositories openrisc

/* SSA-PRE for trees.

   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010

   Free Software Foundation, Inc.

   Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher

   <stevenb@suse.de>

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 "ggc.h"

#include "tree.h"

#include "basic-block.h"

#include "diagnostic.h"

#include "tree-inline.h"

#include "tree-flow.h"

#include "gimple.h"

#include "tree-dump.h"

#include "timevar.h"

#include "fibheap.h"

#include "hashtab.h"

#include "tree-iterator.h"

#include "real.h"

#include "alloc-pool.h"

#include "obstack.h"

#include "tree-pass.h"

#include "flags.h"

#include "bitmap.h"

#include "langhooks.h"

#include "cfgloop.h"

#include "tree-ssa-sccvn.h"

#include "tree-scalar-evolution.h"

#include "params.h"

#include "dbgcnt.h"

/* TODO:

   1. Avail sets can be shared by making an avail_find_leader that

      walks up the dominator tree and looks in those avail sets.

      This might affect code optimality, it's unclear right now.

   2. Strength reduction can be performed by anticipating expressions

      we can repair later on.

   3. We can do back-substitution or smarter value numbering to catch

      commutative expressions split up over multiple statements.

*/

/* For ease of terminology, "expression node" in the below refers to

   every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs

   represent the actual statement containing the expressions we care about,

   and we cache the value number by putting it in the expression.  */

/* Basic algorithm

   First we walk the statements to generate the AVAIL sets, the

   EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the

   generation of values/expressions by a given block.  We use them

   when computing the ANTIC sets.  The AVAIL sets consist of

   SSA_NAME's that represent values, so we know what values are

   available in what blocks.  AVAIL is a forward dataflow problem.  In

   SSA, values are never killed, so we don't need a kill set, or a

   fixpoint iteration, in order to calculate the AVAIL sets.  In

   traditional parlance, AVAIL sets tell us the downsafety of the

   expressions/values.

   Next, we generate the ANTIC sets.  These sets represent the

   anticipatable expressions.  ANTIC is a backwards dataflow

   problem.  An expression is anticipatable in a given block if it could

   be generated in that block.  This means that if we had to perform

   an insertion in that block, of the value of that expression, we

   could.  Calculating the ANTIC sets requires phi translation of

   expressions, because the flow goes backwards through phis.  We must

   iterate to a fixpoint of the ANTIC sets, because we have a kill

   set.  Even in SSA form, values are not live over the entire

   function, only from their definition point onwards.  So we have to

   remove values from the ANTIC set once we go past the definition

   point of the leaders that make them up.

   compute_antic/compute_antic_aux performs this computation.

   Third, we perform insertions to make partially redundant

   expressions fully redundant.

   An expression is partially redundant (excluding partial

   anticipation) if:

   1. It is AVAIL in some, but not all, of the predecessors of a

      given block.

   2. It is ANTIC in all the predecessors.

   In order to make it fully redundant, we insert the expression into

   the predecessors where it is not available, but is ANTIC.

   For the partial anticipation case, we only perform insertion if it

   is partially anticipated in some block, and fully available in all

   of the predecessors.

   insert/insert_aux/do_regular_insertion/do_partial_partial_insertion

   performs these steps.

   Fourth, we eliminate fully redundant expressions.

   This is a simple statement walk that replaces redundant

   calculations with the now available values.  */

/* Representations of value numbers:

   Value numbers are represented by a representative SSA_NAME.  We

   will create fake SSA_NAME's in situations where we need a

   representative but do not have one (because it is a complex

   expression).  In order to facilitate storing the value numbers in

   bitmaps, and keep the number of wasted SSA_NAME's down, we also

   associate a value_id with each value number, and create full blown

   ssa_name's only where we actually need them (IE in operands of

   existing expressions).

   Theoretically you could replace all the value_id's with

   SSA_NAME_VERSION, but this would allocate a large number of

   SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.

   It would also require an additional indirection at each point we

   use the value id.  */

/* Representation of expressions on value numbers:

   Expressions consisting of value numbers are represented the same

   way as our VN internally represents them, with an additional

   "pre_expr" wrapping around them in order to facilitate storing all

   of the expressions in the same sets.  */

/* Representation of sets:

   The dataflow sets do not need to be sorted in any particular order

   for the majority of their lifetime, are simply represented as two

   bitmaps, one that keeps track of values present in the set, and one

   that keeps track of expressions present in the set.

   When we need them in topological order, we produce it on demand by

   transforming the bitmap into an array and sorting it into topo

   order.  */

/* Type of expression, used to know which member of the PRE_EXPR union

   is valid.  */

enum pre_expr_kind

{

    NAME,

    NARY,

    REFERENCE,

    CONSTANT

};

typedef union pre_expr_union_d

{

  tree name;

  tree constant;

  vn_nary_op_t nary;

  vn_reference_t reference;

} pre_expr_union;

typedef struct pre_expr_d

{

  enum pre_expr_kind kind;

  unsigned int id;

  pre_expr_union u;

} *pre_expr;

#define PRE_EXPR_NAME(e) (e)->u.name

#define PRE_EXPR_NARY(e) (e)->u.nary

#define PRE_EXPR_REFERENCE(e) (e)->u.reference

#define PRE_EXPR_CONSTANT(e) (e)->u.constant

static int

pre_expr_eq (const void *p1, const void *p2)

{

  const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;

  const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;

  if (e1->kind != e2->kind)

    return false;

  switch (e1->kind)

    {

    case CONSTANT:

      return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),

                                       PRE_EXPR_CONSTANT (e2));

    case NAME:

      return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);

    case NARY:

      return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));

    case REFERENCE:

      return vn_reference_eq (PRE_EXPR_REFERENCE (e1),

                              PRE_EXPR_REFERENCE (e2));

    default:

      gcc_unreachable ();

    }

}

static hashval_t

pre_expr_hash (const void *p1)

{

  const struct pre_expr_d *e = (const struct pre_expr_d *) p1;

  switch (e->kind)

    {

    case CONSTANT:

      return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));

    case NAME:

      return SSA_NAME_VERSION (PRE_EXPR_NAME (e));

    case NARY:

      return PRE_EXPR_NARY (e)->hashcode;

    case REFERENCE:

      return PRE_EXPR_REFERENCE (e)->hashcode;

    default:

      gcc_unreachable ();

    }

}

/* Next global expression id number.  */

static unsigned int next_expression_id;

/* Mapping from expression to id number we can use in bitmap sets.  */

DEF_VEC_P (pre_expr);

DEF_VEC_ALLOC_P (pre_expr, heap);

static VEC(pre_expr, heap) *expressions;

static htab_t expression_to_id;

static VEC(unsigned, heap) *name_to_id;

/* Allocate an expression id for EXPR.  */

static inline unsigned int

alloc_expression_id (pre_expr expr)

{

  void **slot;

  /* Make sure we won't overflow. */

  gcc_assert (next_expression_id + 1 > next_expression_id);

  expr->id = next_expression_id++;

  VEC_safe_push (pre_expr, heap, expressions, expr);

  if (expr->kind == NAME)

    {

      unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));

      /* VEC_safe_grow_cleared allocates no headroom.  Avoid frequent

         re-allocations by using VEC_reserve upfront.  There is no

         VEC_quick_grow_cleared unfortunately.  */

      VEC_reserve (unsigned, heap, name_to_id, num_ssa_names);

      VEC_safe_grow_cleared (unsigned, heap, name_to_id, num_ssa_names);

      gcc_assert (VEC_index (unsigned, name_to_id, version) == 0);

      VEC_replace (unsigned, name_to_id, version, expr->id);

    }

  else

    {

      slot = htab_find_slot (expression_to_id, expr, INSERT);

      gcc_assert (!*slot);

      *slot = expr;

    }

  return next_expression_id - 1;

}

/* Return the expression id for tree EXPR.  */

static inline unsigned int

get_expression_id (const pre_expr expr)

{

  return expr->id;

}

static inline unsigned int

lookup_expression_id (const pre_expr expr)

{

  void **slot;

  if (expr->kind == NAME)

    {

      unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));

      if (VEC_length (unsigned, name_to_id) <= version)

        return 0;

      return VEC_index (unsigned, name_to_id, version);

    }

  else

    {

      slot = htab_find_slot (expression_to_id, expr, NO_INSERT);

      if (!slot)

        return 0;

      return ((pre_expr)*slot)->id;

    }

}

/* Return the existing expression id for EXPR, or create one if one

   does not exist yet.  */

static inline unsigned int

get_or_alloc_expression_id (pre_expr expr)

{

  unsigned int id = lookup_expression_id (expr);

  if (id == 0)

    return alloc_expression_id (expr);

  return expr->id = id;

}

/* Return the expression that has expression id ID */

static inline pre_expr

expression_for_id (unsigned int id)

{

  return VEC_index (pre_expr, expressions, id);

}

/* Free the expression id field in all of our expressions,

   and then destroy the expressions array.  */

static void

clear_expression_ids (void)

{

  VEC_free (pre_expr, heap, expressions);

}

static alloc_pool pre_expr_pool;

/* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */

static pre_expr

get_or_alloc_expr_for_name (tree name)

{

  struct pre_expr_d expr;

  pre_expr result;

  unsigned int result_id;

  expr.kind = NAME;

  expr.id = 0;

  PRE_EXPR_NAME (&expr) = name;

  result_id = lookup_expression_id (&expr);

  if (result_id != 0)

    return expression_for_id (result_id);

  result = (pre_expr) pool_alloc (pre_expr_pool);

  result->kind = NAME;

  PRE_EXPR_NAME (result) = name;

  alloc_expression_id (result);

  return result;

}

static bool in_fre = false;

/* An unordered bitmap set.  One bitmap tracks values, the other,

   expressions.  */

typedef struct bitmap_set

{

  bitmap expressions;

  bitmap values;

} *bitmap_set_t;

#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)            \

  EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))

#define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)           \

  EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))

/* Mapping from value id to expressions with that value_id.  */

DEF_VEC_P (bitmap_set_t);

DEF_VEC_ALLOC_P (bitmap_set_t, heap);

static VEC(bitmap_set_t, heap) *value_expressions;

/* Sets that we need to keep track of.  */

typedef struct bb_bitmap_sets

{

  /* The EXP_GEN set, which represents expressions/values generated in

     a basic block.  */

  bitmap_set_t exp_gen;

  /* The PHI_GEN set, which represents PHI results generated in a

     basic block.  */

  bitmap_set_t phi_gen;

  /* The TMP_GEN set, which represents results/temporaries generated

     in a basic block. IE the LHS of an expression.  */

  bitmap_set_t tmp_gen;

  /* The AVAIL_OUT set, which represents which values are available in

     a given basic block.  */

  bitmap_set_t avail_out;

  /* The ANTIC_IN set, which represents which values are anticipatable

     in a given basic block.  */

  bitmap_set_t antic_in;

  /* The PA_IN set, which represents which values are

     partially anticipatable in a given basic block.  */

  bitmap_set_t pa_in;

  /* The NEW_SETS set, which is used during insertion to augment the

     AVAIL_OUT set of blocks with the new insertions performed during

     the current iteration.  */

  bitmap_set_t new_sets;

  /* A cache for value_dies_in_block_x.  */

  bitmap expr_dies;

  /* True if we have visited this block during ANTIC calculation.  */

  unsigned int visited : 1;

  /* True we have deferred processing this block during ANTIC

     calculation until its successor is processed.  */

  unsigned int deferred : 1;

  /* True when the block contains a call that might not return.  */

  unsigned int contains_may_not_return_call : 1;

} *bb_value_sets_t;

#define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen

#define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen

#define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen

#define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out

#define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in

#define PA_IN(BB)       ((bb_value_sets_t) ((BB)->aux))->pa_in

#define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets

#define EXPR_DIES(BB)   ((bb_value_sets_t) ((BB)->aux))->expr_dies

#define BB_VISITED(BB)  ((bb_value_sets_t) ((BB)->aux))->visited

#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred

#define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call

/* Basic block list in postorder.  */

static int *postorder;

/* This structure is used to keep track of statistics on what

   optimization PRE was able to perform.  */

static struct

{

  /* The number of RHS computations eliminated by PRE.  */

  int eliminations;

  /* The number of new expressions/temporaries generated by PRE.  */

  int insertions;

  /* The number of inserts found due to partial anticipation  */

  int pa_insert;

  /* The number of new PHI nodes added by PRE.  */

  int phis;

  /* The number of values found constant.  */

  int constified;

} pre_stats;

static bool do_partial_partial;

static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);

static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);

static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);

static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);

static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);

static void bitmap_insert_into_set (bitmap_set_t, pre_expr);

static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,

                                      unsigned int, bool);

static bitmap_set_t bitmap_set_new (void);

static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,

                                         gimple, tree);

static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,

                                         gimple);

static unsigned int get_expr_value_id (pre_expr);

/* We can add and remove elements and entries to and from sets

   and hash tables, so we use alloc pools for them.  */

static alloc_pool bitmap_set_pool;

static bitmap_obstack grand_bitmap_obstack;

/* To avoid adding 300 temporary variables when we only need one, we

   only create one temporary variable, on demand, and build ssa names

   off that.  We do have to change the variable if the types don't

   match the current variable's type.  */

static tree pretemp;

static tree storetemp;

static tree prephitemp;

/* Set of blocks with statements that have had its EH information

   cleaned up.  */

static bitmap need_eh_cleanup;

/* The phi_translate_table caches phi translations for a given

   expression and predecessor.  */

static htab_t phi_translate_table;

/* A three tuple {e, pred, v} used to cache phi translations in the

   phi_translate_table.  */

typedef struct expr_pred_trans_d

{

  /* The expression.  */

  pre_expr e;

  /* The predecessor block along which we translated the expression.  */

  basic_block pred;

  /* The value that resulted from the translation.  */

  pre_expr v;

  /* The hashcode for the expression, pred pair. This is cached for

     speed reasons.  */

  hashval_t hashcode;

} *expr_pred_trans_t;

typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;

/* Return the hash value for a phi translation table entry.  */

static hashval_t

expr_pred_trans_hash (const void *p)

{

  const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;

  return ve->hashcode;

}

/* Return true if two phi translation table entries are the same.

   P1 and P2 should point to the expr_pred_trans_t's to be compared.*/

static int

expr_pred_trans_eq (const void *p1, const void *p2)

{

  const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;

  const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;

  basic_block b1 = ve1->pred;

  basic_block b2 = ve2->pred;

  /* If they are not translations for the same basic block, they can't

     be equal.  */

  if (b1 != b2)

    return false;

  return pre_expr_eq (ve1->e, ve2->e);

}

/* Search in the phi translation table for the translation of

   expression E in basic block PRED.

   Return the translated value, if found, NULL otherwise.  */

static inline pre_expr

phi_trans_lookup (pre_expr e, basic_block pred)

{

  void **slot;

  struct expr_pred_trans_d ept;

  ept.e = e;

  ept.pred = pred;

  ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);

  slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,

                                   NO_INSERT);

  if (!slot)

    return NULL;

  else

    return ((expr_pred_trans_t) *slot)->v;

}

/* Add the tuple mapping from {expression E, basic block PRED} to

   value V, to the phi translation table.  */

static inline void

phi_trans_add (pre_expr e, pre_expr v, basic_block pred)

{

  void **slot;

  expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);

  new_pair->e = e;

  new_pair->pred = pred;

  new_pair->v = v;

  new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),

                                                 pred->index);

  slot = htab_find_slot_with_hash (phi_translate_table, new_pair,

                                   new_pair->hashcode, INSERT);

  if (*slot)

    free (*slot);

  *slot = (void *) new_pair;

}

/* Add expression E to the expression set of value id V.  */

void

add_to_value (unsigned int v, pre_expr e)

{

  bitmap_set_t set;

  gcc_assert (get_expr_value_id (e) == v);

  if (v >= VEC_length (bitmap_set_t, value_expressions))

    {

      VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,

                             v + 1);

    }

  set = VEC_index (bitmap_set_t, value_expressions, v);

  if (!set)

    {

      set = bitmap_set_new ();

      VEC_replace (bitmap_set_t, value_expressions, v, set);

    }

  bitmap_insert_into_set_1 (set, e, v, true);

}

/* Create a new bitmap set and return it.  */

static bitmap_set_t

bitmap_set_new (void)

{

  bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);

  ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);

  ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);

  return ret;

}

/* Return the value id for a PRE expression EXPR.  */

static unsigned int

get_expr_value_id (pre_expr expr)

{

  switch (expr->kind)

    {

    case CONSTANT:

      {

        unsigned int id;

        id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));

        if (id == 0)

          {

            id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));

            add_to_value (id, expr);

          }

        return id;

      }

    case NAME:

      return VN_INFO (PRE_EXPR_NAME (expr))->value_id;

    case NARY:

      return PRE_EXPR_NARY (expr)->value_id;

    case REFERENCE:

      return PRE_EXPR_REFERENCE (expr)->value_id;

    default:

      gcc_unreachable ();

    }

}

/* Remove an expression EXPR from a bitmapped set.  */

static void

bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)

{

  unsigned int val  = get_expr_value_id (expr);

  if (!value_id_constant_p (val))

    {

      bitmap_clear_bit (set->values, val);

      bitmap_clear_bit (set->expressions, get_expression_id (expr));

    }

}

static void

bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,

                          unsigned int val, bool allow_constants)

{

  if (allow_constants || !value_id_constant_p (val))

    {

      /* We specifically expect this and only this function to be able to

         insert constants into a set.  */

      bitmap_set_bit (set->values, val);

      bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));

    }

}

/* Insert an expression EXPR into a bitmapped set.  */

static void

bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)

{

  bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);

}

/* Copy a bitmapped set ORIG, into bitmapped set DEST.  */

static void

bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)

{

  bitmap_copy (dest->expressions, orig->expressions);

  bitmap_copy (dest->values, orig->values);

}

/* Free memory used up by SET.  */

static void

bitmap_set_free (bitmap_set_t set)

{

  BITMAP_FREE (set->expressions);

  BITMAP_FREE (set->values);

}

/* Generate an topological-ordered array of bitmap set SET.  */

static VEC(pre_expr, heap) *

sorted_array_from_bitmap_set (bitmap_set_t set)

{

  unsigned int i, j;

  bitmap_iterator bi, bj;

  VEC(pre_expr, heap) *result;

  /* Pre-allocate roughly enough space for the array.  */

  result = VEC_alloc (pre_expr, heap, bitmap_count_bits (set->values));

  FOR_EACH_VALUE_ID_IN_SET (set, i, bi)

    {

      /* The number of expressions having a given value is usually

         relatively small.  Thus, rather than making a vector of all

         the expressions and sorting it by value-id, we walk the values

         and check in the reverse mapping that tells us what expressions

         have a given value, to filter those in our set.  As a result,

         the expressions are inserted in value-id order, which means

         topological order.

         If this is somehow a significant lose for some cases, we can

         choose which set to walk based on the set size.  */

      bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);

      FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)

        {

          if (bitmap_bit_p (set->expressions, j))

            VEC_safe_push (pre_expr, heap, result, expression_for_id (j));

        }

    }

  return result;

}

/* Perform bitmapped set operation DEST &= ORIG.  */

static void

bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)

{

  bitmap_iterator bi;

  unsigned int i;

  if (dest != orig)

    {