Subversion Repositories openrisc

/* SSA-PRE for trees.

   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007

   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 "tree-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 "tree-pass.h"

#include "flags.h"

#include "bitmap.h"

#include "langhooks.h"

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

   4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.

      Right now, it is simply calculating loads that occur before

      any store in a block, instead of loads that occur before

      stores that affect them.  This is relatively more expensive, and

      it's not clear how much more it will buy us.

*/

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

   every expression node but MODIFY_EXPR, because MODIFY_EXPR's 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.

   insert/insert_aux performs this insertion.

   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 using the "value handle" approach.

   This means that each SSA_NAME (and for other reasons to be

   disclosed in a moment, expression nodes) has a value handle that

   can be retrieved through get_value_handle.  This value handle, *is*

   the value number of the SSA_NAME.  You can pointer compare the

   value handles for equivalence purposes.

   For debugging reasons, the value handle is internally more than

   just a number, it is a VAR_DECL named "value.x", where x is a

   unique number for each value number in use.  This allows

   expressions with SSA_NAMES replaced by value handles to still be

   pretty printed in a sane way.  They simply print as "value.3 *

   value.5", etc.

   Expression nodes have value handles associated with them as a

   cache.  Otherwise, we'd have to look them up again in the hash

   table This makes significant difference (factor of two or more) on

   some test cases.  They can be thrown away after the pass is

   finished.  */

/* Representation of expressions on value numbers:

   In some portions of this code, you will notice we allocate "fake"

   analogues to the expression we are value numbering, and replace the

   operands with the values of the expression.  Since we work on

   values, and not just names, we canonicalize expressions to value

   expressions for use in the ANTIC sets, the EXP_GEN set, etc.

   This is theoretically unnecessary, it just saves a bunch of

   repeated get_value_handle and find_leader calls in the remainder of

   the code, trading off temporary memory usage for speed.  The tree

   nodes aren't actually creating more garbage, since they are

   allocated in a special pools which are thrown away at the end of

   this pass.

   All of this also means that if you print the EXP_GEN or ANTIC sets,

   you will see "value.5 + value.7" in the set, instead of "a_55 +

   b_66" or something.  The only thing that actually cares about

   seeing the value leaders is phi translation, and it needs to be

   able to find the leader for a value in an arbitrary block, so this

   "value expression" form is perfect for it (otherwise you'd do

   get_value_handle->find_leader->translate->get_value_handle->find_leader).*/

/* Representation of sets:

   There are currently two types of sets used, hopefully to be unified soon.

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

   and thus, 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.

   The other sets are represented as doubly linked lists kept in topological

   order, with an optional supporting bitmap of values present in the

   set.  The sets represent values, and the elements can be values or

   expressions.  The elements can appear in different sets, but each

   element can only appear once in each set.

   Since each node in the set represents a value, we also want to be

   able to map expression, set pairs to something that tells us

   whether the value is present is a set.  We use a per-set bitmap for

   that.  The value handles also point to a linked list of the

   expressions they represent via a tree annotation.  This is mainly

   useful only for debugging, since we don't do identity lookups.  */

static bool in_fre = false;

/* A value set element.  Basically a single linked list of

   expressions/values.  */

typedef struct value_set_node

{

  /* An expression.  */

  tree expr;

  /* A pointer to the next element of the value set.  */

  struct value_set_node *next;

} *value_set_node_t;

/* A value set.  This is a singly linked list of value_set_node

   elements with a possible bitmap that tells us what values exist in

   the set.  This set must be kept in topologically sorted order.  */

typedef struct value_set

{

  /* The head of the list.  Used for iterating over the list in

     order.  */

  value_set_node_t head;

  /* The tail of the list.  Used for tail insertions, which are

     necessary to keep the set in topologically sorted order because

     of how the set is built.  */

  value_set_node_t tail;

  /* The length of the list.  */

  size_t length;

  /* True if the set is indexed, which means it contains a backing

     bitmap for quick determination of whether certain values exist in the

     set.  */

  bool indexed;

  /* The bitmap of values that exist in the set.  May be NULL in an

     empty or non-indexed set.  */

  bitmap values;

} *value_set_t;

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

   expressions.  */

typedef struct bitmap_set

{

  bitmap expressions;

  bitmap values;

} *bitmap_set_t;

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

typedef struct bb_value_sets

{

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

     a basic block.  */

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

  value_set_t antic_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;

  /* The RVUSE sets, which are used during ANTIC computation to ensure

     that we don't mark loads ANTIC once they have died.  */

  bitmap rvuse_in;

  bitmap rvuse_out;

  bitmap rvuse_gen;

  bitmap rvuse_kill;

  /* For actually occurring loads, as long as they occur before all the

     other stores in the block, we know they are antic at the top of

     the block, regardless of RVUSE_KILL.  */

  value_set_t antic_safe_loads;

} *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 RVUSE_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->rvuse_in

#define RVUSE_GEN(BB)   ((bb_value_sets_t) ((BB)->aux))->rvuse_gen

#define RVUSE_KILL(BB)   ((bb_value_sets_t) ((BB)->aux))->rvuse_kill

#define RVUSE_OUT(BB)    ((bb_value_sets_t) ((BB)->aux))->rvuse_out

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

#define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads

/* 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 new PHI nodes added by PRE.  */

  int phis;

  /* The number of values found constant.  */

  int constified;

} pre_stats;

static tree bitmap_find_leader (bitmap_set_t, tree);

static tree find_leader (value_set_t, tree);

static void value_insert_into_set (value_set_t, tree);

static void bitmap_value_insert_into_set (bitmap_set_t, tree);

static void bitmap_value_replace_in_set (bitmap_set_t, tree);

static void insert_into_set (value_set_t, tree);

static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);

static bool bitmap_set_contains_value (bitmap_set_t, tree);

static bitmap_set_t bitmap_set_new (void);

static value_set_t set_new  (bool);

static bool is_undefined_value (tree);

static tree create_expression_by_pieces (basic_block, tree, tree);

static tree find_or_generate_expression (basic_block, tree, tree);

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

static alloc_pool bitmap_set_pool;

static alloc_pool value_set_node_pool;

static alloc_pool binary_node_pool;

static alloc_pool unary_node_pool;

static alloc_pool reference_node_pool;

static alloc_pool comparison_node_pool;

static alloc_pool expression_node_pool;

static alloc_pool list_node_pool;

static alloc_pool modify_expr_node_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 mergephitemp;

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

  tree e;

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

  basic_block pred;

  /* vuses associated with the expression.  */

  VEC (tree, gc) *vuses;

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

  tree v;

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

     speed reasons.  */

  hashval_t hashcode;

} *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 ve = (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 ve1 = (expr_pred_trans_t) p1;

  const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;

  basic_block b1 = ve1->pred;

  basic_block b2 = ve2->pred;

  int i;

  tree vuse1;

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

     be equal.  */

  if (b1 != b2)

    return false;

  /* If they are for the same basic block, determine if the

     expressions are equal.  */

  if (!expressions_equal_p (ve1->e, ve2->e))

    return false;

  /* Make sure the vuses are equivalent.  */

  if (ve1->vuses == ve2->vuses)

    return true;

  if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))

    return false;

  for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)

    {

      if (VEC_index (tree, ve2->vuses, i) != vuse1)

        return false;

    }

  return true;

}

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

   expression E in basic block PRED with vuses VUSES.

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

static inline tree

phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)

{

  void **slot;

  struct expr_pred_trans_d ept;

  ept.e = e;

  ept.pred = pred;

  ept.vuses = vuses;

  ept.hashcode = vn_compute (e, (unsigned long) pred);

  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, vuses VUSES} to

   value V, to the phi translation table.  */

static inline void

phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)

{

  void **slot;

  expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);

  new_pair->e = e;

  new_pair->pred = pred;

  new_pair->vuses = vuses;

  new_pair->v = v;

  new_pair->hashcode = vn_compute (e, (unsigned long) pred);

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

void

add_to_value (tree v, tree e)

{

  /* Constants have no expression sets.  */

  if (is_gimple_min_invariant (v))

    return;

  if (VALUE_HANDLE_EXPR_SET (v) == NULL)

    VALUE_HANDLE_EXPR_SET (v) = set_new (false);

  insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);

}

/* Return true if value V exists in the bitmap for SET.  */

static inline bool

value_exists_in_set_bitmap (value_set_t set, tree v)

{

  if (!set->values)

    return false;

  return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));

}

/* Remove value V from the bitmap for SET.  */

static void

value_remove_from_set_bitmap (value_set_t set, tree v)

{

  gcc_assert (set->indexed);

  if (!set->values)

    return;

  bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));

}

/* Insert the value number V into the bitmap of values existing in

   SET.  */

static inline void

value_insert_into_set_bitmap (value_set_t set, tree v)

{

  gcc_assert (set->indexed);

  if (set->values == NULL)

    set->values = BITMAP_ALLOC (&grand_bitmap_obstack);

  bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));

}

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

}

/* Create a new set.  */

static value_set_t

set_new  (bool indexed)

{

  value_set_t ret;

  ret = (value_set_t) pool_alloc (value_set_pool);

  ret->head = ret->tail = NULL;

  ret->length = 0;

  ret->indexed = indexed;

  ret->values = NULL;

  return ret;

}

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

static void

bitmap_insert_into_set (bitmap_set_t set, tree expr)

{

  tree val;

  /* XXX: For now, we only let SSA_NAMES into the bitmap sets.  */

  gcc_assert (TREE_CODE (expr) == SSA_NAME);

  val = get_value_handle (expr);

  gcc_assert (val);

  if (!is_gimple_min_invariant (val))

  {

    bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));

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

  }

}

/* Insert EXPR into SET.  */

static void

insert_into_set (value_set_t set, tree expr)

{

  value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool);

  tree val = get_value_handle (expr);

  gcc_assert (val);

  if (is_gimple_min_invariant (val))

    return;

  /* For indexed sets, insert the value into the set value bitmap.

     For all sets, add it to the linked list and increment the list

     length.  */

  if (set->indexed)

    value_insert_into_set_bitmap (set, val);

  newnode->next = NULL;

  newnode->expr = expr;

  set->length ++;

  if (set->head == NULL)

    {

      set->head = set->tail = newnode;

    }

  else

    {

      set->tail->next = newnode;

      set->tail = newnode;

    }

}

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

}

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

  bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);

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

  bitmap_copy (temp, dest->expressions);

  EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)

    {

      tree name = ssa_name (i);

      tree val = get_value_handle (name);

      if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))

        bitmap_clear_bit (dest->expressions, i);

    }

  BITMAP_FREE (temp);

}

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

static void

bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig)

{

  bitmap_iterator bi;

  unsigned int i;

  bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);

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

  bitmap_copy (temp, dest->expressions);

  EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)

    {

      tree name = ssa_name (i);

      tree val = get_value_handle (name);

      if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))

        bitmap_clear_bit (dest->expressions, i);

    }

  BITMAP_FREE (temp);

}

/* Return true if the bitmap set SET is empty.  */

static bool

bitmap_set_empty_p (bitmap_set_t set)

{

  return bitmap_empty_p (set->values);

}

/* Copy the set ORIG to the set DEST.  */

static void

set_copy (value_set_t dest, value_set_t orig)

{

  value_set_node_t node;

  if (!orig || !orig->head)

    return;

  for (node = orig->head;

       node;

       node = node->next)

    {

      insert_into_set (dest, node->expr);

    }

}

/* Remove EXPR from SET.  */

static void

set_remove (value_set_t set, tree expr)

{

  value_set_node_t node, prev;

  /* Remove the value of EXPR from the bitmap, decrement the set

     length, and remove it from the actual double linked list.  */

  value_remove_from_set_bitmap (set, get_value_handle (expr));

  set->length--;

  prev = NULL;

  for (node = set->head;

       node != NULL;

       prev = node, node = node->next)

    {

      if (node->expr == expr)

        {

          if (prev == NULL)

            set->head = node->next;

          else

            prev->next= node->next;

          if (node == set->tail)

            set->tail = prev;

          pool_free (value_set_node_pool, node);

          return;

        }

    }

}

/* Return true if SET contains the value VAL.  */

static bool

set_contains_value (value_set_t set, tree val)

{

  /* All constants are in every set.  */

  if (is_gimple_min_invariant (val))

    return true;

  if (!set || set->length == 0)

    return false;

  return value_exists_in_set_bitmap (set, val);

}

/* Return true if bitmapped set SET contains the expression EXPR.  */

static bool

bitmap_set_contains (bitmap_set_t set, tree expr)

{

  /* All constants are in every set.  */

  if (is_gimple_min_invariant (get_value_handle (expr)))

    return true;

  /* XXX: Bitmapped sets only contain SSA_NAME's for now.  */

  if (TREE_CODE (expr) != SSA_NAME)

    return false;

  return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));

}

/* Return true if bitmapped set SET contains the value VAL.  */

static bool

bitmap_set_contains_value (bitmap_set_t set, tree val)

{

  if (is_gimple_min_invariant (val))

    return true;

  return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));

}

/* Replace an instance of value LOOKFOR with expression EXPR in SET.  */

static void

bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)

{

  value_set_t exprset;

  value_set_node_t node;

  if (is_gimple_min_invariant (lookfor))

    return;

  if (!bitmap_set_contains_value (set, lookfor))

    return;

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

     significantly less than the total number of expressions in SET.

     Thus, rather than check, for each expression in SET, whether it

     has the value LOOKFOR, we walk the reverse mapping that tells us

     what expressions have a given value, and see if any of those

     expressions are in our set.  For large testcases, this is about

     5-10x faster than walking the bitmap.  If this is somehow a

     significant lose for some cases, we can choose which set to walk

     based on the set size.  */

  exprset = VALUE_HANDLE_EXPR_SET (lookfor);