Check in gcc sources for prebuilt toolchains in Eclair.

1 files changed, 2080 insertions, 0 deletions

diff --git a/gcc-4.4.0/gcc/tree-ssa-reassoc.c b/gcc-4.4.0/gcc/tree-ssa-reassoc.c
new file mode 100644
index 000000000..d28e1b620
--- /dev/null
+++ b/gcc-4.4.0/gcc/tree-ssa-reassoc.c
@@ -0,0 +1,2080 @@
+/* Reassociation for trees.
+   Copyright (C) 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@dberlin.org>
+
+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 "tree-iterator.h"
+#include "tree-pass.h"
+#include "alloc-pool.h"
+#include "vec.h"
+#include "langhooks.h"
+#include "pointer-set.h"
+#include "cfgloop.h"
+#include "flags.h"
+
+/*  This is a simple global reassociation pass.  It is, in part, based
+    on the LLVM pass of the same name (They do some things more/less
+    than we do, in different orders, etc).
+
+    It consists of five steps:
+
+    1. Breaking up subtract operations into addition + negate, where
+    it would promote the reassociation of adds.
+
+    2. Left linearization of the expression trees, so that (A+B)+(C+D)
+    becomes (((A+B)+C)+D), which is easier for us to rewrite later.
+    During linearization, we place the operands of the binary
+    expressions into a vector of operand_entry_t
+
+    3. Optimization of the operand lists, eliminating things like a +
+    -a, a & a, etc.
+
+    4. Rewrite the expression trees we linearized and optimized so
+    they are in proper rank order.
+
+    5. Repropagate negates, as nothing else will clean it up ATM.
+
+    A bit of theory on #4, since nobody seems to write anything down
+    about why it makes sense to do it the way they do it:
+
+    We could do this much nicer theoretically, but don't (for reasons
+    explained after how to do it theoretically nice :P).
+
+    In order to promote the most redundancy elimination, you want
+    binary expressions whose operands are the same rank (or
+    preferably, the same value) exposed to the redundancy eliminator,
+    for possible elimination.
+
+    So the way to do this if we really cared, is to build the new op
+    tree from the leaves to the roots, merging as you go, and putting the
+    new op on the end of the worklist, until you are left with one
+    thing on the worklist.
+
+    IE if you have to rewrite the following set of operands (listed with
+    rank in parentheses), with opcode PLUS_EXPR:
+
+    a (1),  b (1),  c (1),  d (2), e (2)
+
+
+    We start with our merge worklist empty, and the ops list with all of
+    those on it.
+
+    You want to first merge all leaves of the same rank, as much as
+    possible.
+
+    So first build a binary op of
+
+    mergetmp = a + b, and put "mergetmp" on the merge worklist.
+
+    Because there is no three operand form of PLUS_EXPR, c is not going to
+    be exposed to redundancy elimination as a rank 1 operand.
+
+    So you might as well throw it on the merge worklist (you could also
+    consider it to now be a rank two operand, and merge it with d and e,
+    but in this case, you then have evicted e from a binary op. So at
+    least in this situation, you can't win.)
+
+    Then build a binary op of d + e
+    mergetmp2 = d + e
+
+    and put mergetmp2 on the merge worklist.
+    
+    so merge worklist = {mergetmp, c, mergetmp2}
+    
+    Continue building binary ops of these operations until you have only
+    one operation left on the worklist.
+    
+    So we have
+    
+    build binary op
+    mergetmp3 = mergetmp + c
+    
+    worklist = {mergetmp2, mergetmp3}
+    
+    mergetmp4 = mergetmp2 + mergetmp3
+    
+    worklist = {mergetmp4}
+    
+    because we have one operation left, we can now just set the original
+    statement equal to the result of that operation.
+    
+    This will at least expose a + b  and d + e to redundancy elimination
+    as binary operations.
+    
+    For extra points, you can reuse the old statements to build the
+    mergetmps, since you shouldn't run out.
+
+    So why don't we do this?
+    
+    Because it's expensive, and rarely will help.  Most trees we are
+    reassociating have 3 or less ops.  If they have 2 ops, they already
+    will be written into a nice single binary op.  If you have 3 ops, a
+    single simple check suffices to tell you whether the first two are of the
+    same rank.  If so, you know to order it
+
+    mergetmp = op1 + op2
+    newstmt = mergetmp + op3
+    
+    instead of
+    mergetmp = op2 + op3
+    newstmt = mergetmp + op1
+    
+    If all three are of the same rank, you can't expose them all in a
+    single binary operator anyway, so the above is *still* the best you
+    can do.
+    
+    Thus, this is what we do.  When we have three ops left, we check to see
+    what order to put them in, and call it a day.  As a nod to vector sum
+    reduction, we check if any of the ops are really a phi node that is a
+    destructive update for the associating op, and keep the destructive
+    update together for vector sum reduction recognition.  */
+
+
+/* Statistics */
+static struct
+{
+  int linearized;
+  int constants_eliminated;
+  int ops_eliminated;
+  int rewritten;
+} reassociate_stats;
+
+/* Operator, rank pair.  */
+typedef struct operand_entry
+{
+  unsigned int rank;
+  tree op;
+} *operand_entry_t;
+
+static alloc_pool operand_entry_pool;
+
+
+/* Starting rank number for a given basic block, so that we can rank
+   operations using unmovable instructions in that BB based on the bb
+   depth.  */
+static long *bb_rank;
+
+/* Operand->rank hashtable.  */
+static struct pointer_map_t *operand_rank;
+
+
+/* Look up the operand rank structure for expression E.  */
+
+static inline long
+find_operand_rank (tree e)
+{
+  void **slot = pointer_map_contains (operand_rank, e);
+  return slot ? (long) *slot : -1;
+}
+
+/* Insert {E,RANK} into the operand rank hashtable.  */
+
+static inline void
+insert_operand_rank (tree e, long rank)
+{
+  void **slot;
+  gcc_assert (rank > 0);
+  slot = pointer_map_insert (operand_rank, e);
+  gcc_assert (!*slot);
+  *slot = (void *) rank;
+}
+
+/* Given an expression E, return the rank of the expression.  */
+
+static long
+get_rank (tree e)
+{
+  /* Constants have rank 0.  */
+  if (is_gimple_min_invariant (e))
+    return 0;
+
+  /* SSA_NAME's have the rank of the expression they are the result
+     of.
+     For globals and uninitialized values, the rank is 0.
+     For function arguments, use the pre-setup rank.
+     For PHI nodes, stores, asm statements, etc, we use the rank of
+     the BB.
+     For simple operations, the rank is the maximum rank of any of
+     its operands, or the bb_rank, whichever is less.
+     I make no claims that this is optimal, however, it gives good
+     results.  */
+
+  if (TREE_CODE (e) == SSA_NAME)
+    {
+      gimple stmt;
+      long rank, maxrank;
+      int i, n;
+
+      if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
+	  && SSA_NAME_IS_DEFAULT_DEF (e))
+	return find_operand_rank (e);
+
+      stmt = SSA_NAME_DEF_STMT (e);
+      if (gimple_bb (stmt) == NULL)
+	return 0;
+
+      if (!is_gimple_assign (stmt)
+	  || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
+	return bb_rank[gimple_bb (stmt)->index];
+
+      /* If we already have a rank for this expression, use that.  */
+      rank = find_operand_rank (e);
+      if (rank != -1)
+	return rank;
+
+      /* Otherwise, find the maximum rank for the operands, or the bb
+	 rank, whichever is less.   */
+      rank = 0;
+      maxrank = bb_rank[gimple_bb(stmt)->index];
+      if (gimple_assign_single_p (stmt))
+	{
+	  tree rhs = gimple_assign_rhs1 (stmt);
+	  n = TREE_OPERAND_LENGTH (rhs);
+	  if (n == 0)
+	    rank = MAX (rank, get_rank (rhs));
+	  else
+	    {
+	      for (i = 0;
+		   i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++)
+		rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
+	    }
+	}
+      else
+	{
+	  n = gimple_num_ops (stmt);
+	  for (i = 1; i < n && rank != maxrank; i++)
+	    {
+	      gcc_assert (gimple_op (stmt, i));
+	      rank = MAX(rank, get_rank (gimple_op (stmt, i)));
+	    }
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Rank for ");
+	  print_generic_expr (dump_file, e, 0);
+	  fprintf (dump_file, " is %ld\n", (rank + 1));
+	}
+
+      /* Note the rank in the hashtable so we don't recompute it.  */
+      insert_operand_rank (e, (rank + 1));
+      return (rank + 1);
+    }
+
+  /* Globals, etc,  are rank 0 */
+  return 0;
+}
+
+DEF_VEC_P(operand_entry_t);
+DEF_VEC_ALLOC_P(operand_entry_t, heap);
+
+/* We want integer ones to end up last no matter what, since they are
+   the ones we can do the most with.  */
+#define INTEGER_CONST_TYPE 1 << 3
+#define FLOAT_CONST_TYPE 1 << 2
+#define OTHER_CONST_TYPE 1 << 1
+
+/* Classify an invariant tree into integer, float, or other, so that
+   we can sort them to be near other constants of the same type.  */
+static inline int
+constant_type (tree t)
+{
+  if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
+    return INTEGER_CONST_TYPE;
+  else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
+    return FLOAT_CONST_TYPE;
+  else
+    return OTHER_CONST_TYPE;
+}
+
+/* qsort comparison function to sort operand entries PA and PB by rank
+   so that the sorted array is ordered by rank in decreasing order.  */
+static int
+sort_by_operand_rank (const void *pa, const void *pb)
+{
+  const operand_entry_t oea = *(const operand_entry_t *)pa;
+  const operand_entry_t oeb = *(const operand_entry_t *)pb;
+
+  /* It's nicer for optimize_expression if constants that are likely
+     to fold when added/multiplied//whatever are put next to each
+     other.  Since all constants have rank 0, order them by type.  */
+  if (oeb->rank == 0 &&  oea->rank == 0)
+    return constant_type (oeb->op) - constant_type (oea->op);
+
+  /* Lastly, make sure the versions that are the same go next to each
+     other.  We use SSA_NAME_VERSION because it's stable.  */
+  if ((oeb->rank - oea->rank == 0)
+      && TREE_CODE (oea->op) == SSA_NAME
+      && TREE_CODE (oeb->op) == SSA_NAME)
+    return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
+
+  return oeb->rank - oea->rank;
+}
+
+/* Add an operand entry to *OPS for the tree operand OP.  */
+
+static void
+add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
+{
+  operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+  oe->op = op;
+  oe->rank = get_rank (op);
+  VEC_safe_push (operand_entry_t, heap, *ops, oe);
+}
+
+/* Return true if STMT is reassociable operation containing a binary
+   operation with tree code CODE, and is inside LOOP.  */
+
+static bool
+is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
+{
+  basic_block bb = gimple_bb (stmt);
+
+  if (gimple_bb (stmt) == NULL)
+    return false;
+
+  if (!flow_bb_inside_loop_p (loop, bb))
+    return false;
+
+  if (is_gimple_assign (stmt)
+      && gimple_assign_rhs_code (stmt) == code
+      && has_single_use (gimple_assign_lhs (stmt)))
+    return true;
+
+  return false;
+}
+
+
+/* Given NAME, if NAME is defined by a unary operation OPCODE, return the
+   operand of the negate operation.  Otherwise, return NULL.  */
+
+static tree
+get_unary_op (tree name, enum tree_code opcode)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (name);
+
+  if (!is_gimple_assign (stmt))
+    return NULL_TREE;
+
+  if (gimple_assign_rhs_code (stmt) == opcode)
+    return gimple_assign_rhs1 (stmt);
+  return NULL_TREE;
+}
+
+/* If CURR and LAST are a pair of ops that OPCODE allows us to
+   eliminate through equivalences, do so, remove them from OPS, and
+   return true.  Otherwise, return false.  */
+
+static bool
+eliminate_duplicate_pair (enum tree_code opcode,
+			  VEC (operand_entry_t, heap) **ops,
+			  bool *all_done,
+			  unsigned int i,
+			  operand_entry_t curr,
+			  operand_entry_t last)
+{
+
+  /* If we have two of the same op, and the opcode is & |, min, or max,
+     we can eliminate one of them.
+     If we have two of the same op, and the opcode is ^, we can
+     eliminate both of them.  */
+
+  if (last && last->op == curr->op)
+    {
+      switch (opcode)
+	{
+	case MAX_EXPR:
+	case MIN_EXPR:
+	case BIT_IOR_EXPR:
+	case BIT_AND_EXPR:
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Equivalence: ");
+	      print_generic_expr (dump_file, curr->op, 0);
+	      fprintf (dump_file, " [&|minmax] ");
+	      print_generic_expr (dump_file, last->op, 0);
+	      fprintf (dump_file, " -> ");
+	      print_generic_stmt (dump_file, last->op, 0);
+	    }
+
+	  VEC_ordered_remove (operand_entry_t, *ops, i);
+	  reassociate_stats.ops_eliminated ++;
+
+	  return true;
+
+	case BIT_XOR_EXPR:
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Equivalence: ");
+	      print_generic_expr (dump_file, curr->op, 0);
+	      fprintf (dump_file, " ^ ");
+	      print_generic_expr (dump_file, last->op, 0);
+	      fprintf (dump_file, " -> nothing\n");
+	    }
+
+	  reassociate_stats.ops_eliminated += 2;
+
+	  if (VEC_length (operand_entry_t, *ops) == 2)
+	    {
+	      VEC_free (operand_entry_t, heap, *ops);
+	      *ops = NULL;
+	      add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op), 
+						 integer_zero_node));
+	      *all_done = true;
+	    }
+	  else
+	    {
+	      VEC_ordered_remove (operand_entry_t, *ops, i-1);
+	      VEC_ordered_remove (operand_entry_t, *ops, i-1);
+	    }
+
+	  return true;
+
+	default:
+	  break;
+	}
+    }
+  return false;
+}
+
+/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
+   look in OPS for a corresponding positive operation to cancel it
+   out.  If we find one, remove the other from OPS, replace
+   OPS[CURRINDEX] with 0, and return true.  Otherwise, return
+   false. */
+
+static bool
+eliminate_plus_minus_pair (enum tree_code opcode,
+			   VEC (operand_entry_t, heap) **ops,
+			   unsigned int currindex,
+			   operand_entry_t curr)
+{
+  tree negateop;
+  unsigned int i;
+  operand_entry_t oe;
+
+  if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
+    return false;
+
+  negateop = get_unary_op (curr->op, NEGATE_EXPR);
+  if (negateop == NULL_TREE)
+    return false;
+
+  /* Any non-negated version will have a rank that is one less than
+     the current rank.  So once we hit those ranks, if we don't find
+     one, we can stop.  */
+
+  for (i = currindex + 1;
+       VEC_iterate (operand_entry_t, *ops, i, oe)
+       && oe->rank >= curr->rank - 1 ;
+       i++)
+    {
+      if (oe->op == negateop)
+	{
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Equivalence: ");
+	      print_generic_expr (dump_file, negateop, 0);
+	      fprintf (dump_file, " + -");
+	      print_generic_expr (dump_file, oe->op, 0);
+	      fprintf (dump_file, " -> 0\n");
+	    }
+
+	  VEC_ordered_remove (operand_entry_t, *ops, i);
+	  add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op), 
+					    integer_zero_node));
+	  VEC_ordered_remove (operand_entry_t, *ops, currindex);
+	  reassociate_stats.ops_eliminated ++;
+
+	  return true;
+	}
+    }
+
+  return false;
+}
+
+/* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
+   bitwise not expression, look in OPS for a corresponding operand to
+   cancel it out.  If we find one, remove the other from OPS, replace
+   OPS[CURRINDEX] with 0, and return true.  Otherwise, return
+   false. */
+
+static bool
+eliminate_not_pairs (enum tree_code opcode,
+		     VEC (operand_entry_t, heap) **ops,
+		     unsigned int currindex,
+		     operand_entry_t curr)
+{
+  tree notop;
+  unsigned int i;
+  operand_entry_t oe;
+
+  if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
+      || TREE_CODE (curr->op) != SSA_NAME)
+    return false;
+
+  notop = get_unary_op (curr->op, BIT_NOT_EXPR);
+  if (notop == NULL_TREE)
+    return false;
+
+  /* Any non-not version will have a rank that is one less than
+     the current rank.  So once we hit those ranks, if we don't find
+     one, we can stop.  */
+
+  for (i = currindex + 1;
+       VEC_iterate (operand_entry_t, *ops, i, oe)
+       && oe->rank >= curr->rank - 1;
+       i++)
+    {
+      if (oe->op == notop)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Equivalence: ");
+	      print_generic_expr (dump_file, notop, 0);
+	      if (opcode == BIT_AND_EXPR)
+		fprintf (dump_file, " & ~");
+	      else if (opcode == BIT_IOR_EXPR)
+		fprintf (dump_file, " | ~");
+	      print_generic_expr (dump_file, oe->op, 0);
+	      if (opcode == BIT_AND_EXPR)
+		fprintf (dump_file, " -> 0\n");
+	      else if (opcode == BIT_IOR_EXPR)
+		fprintf (dump_file, " -> -1\n");
+	    }
+
+	  if (opcode == BIT_AND_EXPR)
+	    oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
+	  else if (opcode == BIT_IOR_EXPR)
+	    oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
+					  TYPE_PRECISION (TREE_TYPE (oe->op)));
+
+	  reassociate_stats.ops_eliminated 
+	    += VEC_length (operand_entry_t, *ops) - 1;
+	  VEC_free (operand_entry_t, heap, *ops);
+	  *ops = NULL;
+	  VEC_safe_push (operand_entry_t, heap, *ops, oe);
+	  return true;
+	}
+    }
+
+  return false;
+}
+
+/* Use constant value that may be present in OPS to try to eliminate
+   operands.  Note that this function is only really used when we've
+   eliminated ops for other reasons, or merged constants.  Across
+   single statements, fold already does all of this, plus more.  There
+   is little point in duplicating logic, so I've only included the
+   identities that I could ever construct testcases to trigger.  */
+
+static void
+eliminate_using_constants (enum tree_code opcode,
+			   VEC(operand_entry_t, heap) **ops)
+{
+  operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
+  tree type = TREE_TYPE (oelast->op);
+
+  if (oelast->rank == 0
+      && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
+    {
+      switch (opcode)
+	{
+	case BIT_AND_EXPR:
+	  if (integer_zerop (oelast->op))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found & 0, removing all other ops\n");
+
+		  reassociate_stats.ops_eliminated 
+		    += VEC_length (operand_entry_t, *ops) - 1;
+		  
+		  VEC_free (operand_entry_t, heap, *ops);
+		  *ops = NULL;
+		  VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+		  return;
+		}
+	    }
+	  else if (integer_all_onesp (oelast->op))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found & -1, removing\n");
+		  VEC_pop (operand_entry_t, *ops);
+		  reassociate_stats.ops_eliminated++;
+		}
+	    }
+	  break;
+	case BIT_IOR_EXPR:
+	  if (integer_all_onesp (oelast->op))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found | -1, removing all other ops\n");
+
+		  reassociate_stats.ops_eliminated 
+		    += VEC_length (operand_entry_t, *ops) - 1;
+		  
+		  VEC_free (operand_entry_t, heap, *ops);
+		  *ops = NULL;
+		  VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+		  return;
+		}
+	    }	  
+	  else if (integer_zerop (oelast->op))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found | 0, removing\n");
+		  VEC_pop (operand_entry_t, *ops);
+		  reassociate_stats.ops_eliminated++;
+		}
+	    }
+	  break;
+	case MULT_EXPR:
+	  if (integer_zerop (oelast->op)
+	      || (FLOAT_TYPE_P (type)
+		  && !HONOR_NANS (TYPE_MODE (type))
+		  && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
+		  && real_zerop (oelast->op)))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found * 0, removing all other ops\n");
+		  
+		  reassociate_stats.ops_eliminated 
+		    += VEC_length (operand_entry_t, *ops) - 1;
+		  VEC_free (operand_entry_t, heap, *ops);
+		  *ops = NULL;
+		  VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+		  return;
+		}
+	    }
+	  else if (integer_onep (oelast->op)
+		   || (FLOAT_TYPE_P (type)
+		       && !HONOR_SNANS (TYPE_MODE (type))
+		       && real_onep (oelast->op)))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found * 1, removing\n");
+		  VEC_pop (operand_entry_t, *ops);
+		  reassociate_stats.ops_eliminated++;
+		  return;
+		}
+	    }
+	  break;
+	case BIT_XOR_EXPR:
+	case PLUS_EXPR:
+	case MINUS_EXPR:
+	  if (integer_zerop (oelast->op)
+	      || (FLOAT_TYPE_P (type)
+		  && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
+		  && fold_real_zero_addition_p (type, oelast->op,
+						opcode == MINUS_EXPR)))
+	    {
+	      if (VEC_length (operand_entry_t, *ops) != 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Found [|^+] 0, removing\n");
+		  VEC_pop (operand_entry_t, *ops);
+		  reassociate_stats.ops_eliminated++;
+		  return;
+		}
+	    }
+	  break;
+	default:
+	  break;
+	}
+    }
+}
+
+
+static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
+				 bool, bool);
+
+/* Structure for tracking and counting operands.  */
+typedef struct oecount_s {
+  int cnt;
+  enum tree_code oecode;
+  tree op;
+} oecount;
+
+DEF_VEC_O(oecount);
+DEF_VEC_ALLOC_O(oecount,heap);
+
+/* The heap for the oecount hashtable and the sorted list of operands.  */
+static VEC (oecount, heap) *cvec;
+
+/* Hash function for oecount.  */
+
+static hashval_t
+oecount_hash (const void *p)
+{
+  const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
+  return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
+}
+
+/* Comparison function for oecount.  */
+
+static int
+oecount_eq (const void *p1, const void *p2)
+{
+  const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
+  const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
+  return (c1->oecode == c2->oecode
+	  && c1->op == c2->op);
+}
+
+/* Comparison function for qsort sorting oecount elements by count.  */
+
+static int
+oecount_cmp (const void *p1, const void *p2)
+{
+  const oecount *c1 = (const oecount *)p1;
+  const oecount *c2 = (const oecount *)p2;
+  return c1->cnt - c2->cnt;
+}
+
+/* Walks the linear chain with result *DEF searching for an operation
+   with operand OP and code OPCODE removing that from the chain.  *DEF
+   is updated if there is only one operand but no operation left.  */
+
+static void
+zero_one_operation (tree *def, enum tree_code opcode, tree op)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (*def);
+
+  do
+    {
+      tree name = gimple_assign_rhs1 (stmt);
+
+      /* If this is the operation we look for and one of the operands
+         is ours simply propagate the other operand into the stmts
+	 single use.  */
+      if (gimple_assign_rhs_code (stmt) == opcode
+	  && (name == op
+	      || gimple_assign_rhs2 (stmt) == op))
+	{
+	  gimple use_stmt;
+	  use_operand_p use;
+	  gimple_stmt_iterator gsi;
+	  if (name == op)
+	    name = gimple_assign_rhs2 (stmt);
+	  gcc_assert (has_single_use (gimple_assign_lhs (stmt)));
+	  single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt);
+	  if (gimple_assign_lhs (stmt) == *def)
+	    *def = name;
+	  SET_USE (use, name);
+	  if (TREE_CODE (name) != SSA_NAME)
+	    update_stmt (use_stmt);
+	  gsi = gsi_for_stmt (stmt);
+	  gsi_remove (&gsi, true);
+	  release_defs (stmt);
+	  return;
+	}
+
+      /* Continue walking the chain.  */
+      gcc_assert (name != op
+		  && TREE_CODE (name) == SSA_NAME);
+      stmt = SSA_NAME_DEF_STMT (name);
+    }
+  while (1);
+}
+
+/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
+   the result.  Places the statement after the definition of either
+   OP1 or OP2.  Returns the new statement.  */
+
+static gimple
+build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode)
+{
+  gimple op1def = NULL, op2def = NULL;
+  gimple_stmt_iterator gsi;
+  tree op;
+  gimple sum;
+
+  /* Create the addition statement.  */
+  sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2);
+  op = make_ssa_name (tmpvar, sum);
+  gimple_assign_set_lhs (sum, op);
+
+  /* Find an insertion place and insert.  */
+  if (TREE_CODE (op1) == SSA_NAME)
+    op1def = SSA_NAME_DEF_STMT (op1);
+  if (TREE_CODE (op2) == SSA_NAME)
+    op2def = SSA_NAME_DEF_STMT (op2);
+  if ((!op1def || gimple_nop_p (op1def))
+      && (!op2def || gimple_nop_p (op2def)))
+    {
+      gsi = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR));
+      gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+    }
+  else if ((!op1def || gimple_nop_p (op1def))
+	   || (op2def && !gimple_nop_p (op2def)
+	       && stmt_dominates_stmt_p (op1def, op2def)))
+    {
+      if (gimple_code (op2def) == GIMPLE_PHI)
+	{
+	  gsi = gsi_start_bb (gimple_bb (op2def));
+	  gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+	}
+      else
+	{
+	  if (!stmt_ends_bb_p (op2def))
+	    {
+	      gsi = gsi_for_stmt (op2def);
+	      gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
+	    }
+	  else
+	    {
+	      edge e;
+	      edge_iterator ei;
+
+	      FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
+		if (e->flags & EDGE_FALLTHRU)
+		  gsi_insert_on_edge_immediate (e, sum);
+	    }
+	}
+    }
+  else
+    {
+      if (gimple_code (op1def) == GIMPLE_PHI)
+	{
+	  gsi = gsi_start_bb (gimple_bb (op1def));
+	  gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+	}
+      else
+	{
+	  if (!stmt_ends_bb_p (op1def))
+	    {
+	      gsi = gsi_for_stmt (op1def);
+	      gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
+	    }
+	  else
+	    {
+	      edge e;
+	      edge_iterator ei;
+
+	      FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
+		if (e->flags & EDGE_FALLTHRU)
+		  gsi_insert_on_edge_immediate (e, sum);
+	    }
+	}
+    }
+  update_stmt (sum);
+
+  return sum;
+}
+
+/* Perform un-distribution of divisions and multiplications.
+   A * X + B * X is transformed into (A + B) * X and A / X + B / X
+   to (A + B) / X for real X.
+
+   The algorithm is organized as follows.
+
+    - First we walk the addition chain *OPS looking for summands that
+      are defined by a multiplication or a real division.  This results
+      in the candidates bitmap with relevant indices into *OPS.
+
+    - Second we build the chains of multiplications or divisions for
+      these candidates, counting the number of occurences of (operand, code)
+      pairs in all of the candidates chains.
+
+    - Third we sort the (operand, code) pairs by number of occurence and
+      process them starting with the pair with the most uses.
+
+      * For each such pair we walk the candidates again to build a
+        second candidate bitmap noting all multiplication/division chains
+	that have at least one occurence of (operand, code).
+
+      * We build an alternate addition chain only covering these
+        candidates with one (operand, code) operation removed from their
+	multiplication/division chain.
+
+      * The first candidate gets replaced by the alternate addition chain
+        multiplied/divided by the operand.
+
+      * All candidate chains get disabled for further processing and
+        processing of (operand, code) pairs continues.
+
+  The alternate addition chains built are re-processed by the main
+  reassociation algorithm which allows optimizing a * x * y + b * y * x
+  to (a + b ) * x * y in one invocation of the reassociation pass.  */
+
+static bool
+undistribute_ops_list (enum tree_code opcode,
+		       VEC (operand_entry_t, heap) **ops, struct loop *loop)
+{
+  unsigned int length = VEC_length (operand_entry_t, *ops);
+  operand_entry_t oe1;
+  unsigned i, j;
+  sbitmap candidates, candidates2;
+  unsigned nr_candidates, nr_candidates2;
+  sbitmap_iterator sbi0;
+  VEC (operand_entry_t, heap) **subops;
+  htab_t ctable;
+  bool changed = false;
+
+  if (length <= 1
+      || opcode != PLUS_EXPR)
+    return false;
+
+  /* Build a list of candidates to process.  */
+  candidates = sbitmap_alloc (length);
+  sbitmap_zero (candidates);
+  nr_candidates = 0;
+  for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i)
+    {
+      enum tree_code dcode;
+      gimple oe1def;
+
+      if (TREE_CODE (oe1->op) != SSA_NAME)
+	continue;
+      oe1def = SSA_NAME_DEF_STMT (oe1->op);
+      if (!is_gimple_assign (oe1def))
+	continue;
+      dcode = gimple_assign_rhs_code (oe1def);
+      if ((dcode != MULT_EXPR
+	   && dcode != RDIV_EXPR)
+	  || !is_reassociable_op (oe1def, dcode, loop))
+	continue;
+
+      SET_BIT (candidates, i);
+      nr_candidates++;
+    }
+
+  if (nr_candidates < 2)
+    {
+      sbitmap_free (candidates);
+      return false;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "searching for un-distribute opportunities ");
+      print_generic_expr (dump_file,
+	VEC_index (operand_entry_t, *ops,
+		   sbitmap_first_set_bit (candidates))->op, 0);
+      fprintf (dump_file, " %d\n", nr_candidates);
+    }
+
+  /* Build linearized sub-operand lists and the counting table.  */
+  cvec = NULL;
+  ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
+  subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
+		     VEC_length (operand_entry_t, *ops));
+  EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+    {
+      gimple oedef;
+      enum tree_code oecode;
+      unsigned j;
+
+      oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
+      oecode = gimple_assign_rhs_code (oedef);
+      linearize_expr_tree (&subops[i], oedef,
+			   associative_tree_code (oecode), false);
+
+      for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+	{
+	  oecount c;
+	  void **slot;
+	  size_t idx;
+	  c.oecode = oecode;
+	  c.cnt = 1;
+	  c.op = oe1->op;
+	  VEC_safe_push (oecount, heap, cvec, &c);
+	  idx = VEC_length (oecount, cvec) + 41;
+	  slot = htab_find_slot (ctable, (void *)idx, INSERT);
+	  if (!*slot)
+	    {
+	      *slot = (void *)idx;
+	    }
+	  else
+	    {
+	      VEC_pop (oecount, cvec);
+	      VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
+	    }
+	}
+    }
+  htab_delete (ctable);
+
+  /* Sort the counting table.  */
+  qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec),
+	 sizeof (oecount), oecount_cmp);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      oecount *c;
+      fprintf (dump_file, "Candidates:\n");
+      for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j)
+	{
+	  fprintf (dump_file, "  %u %s: ", c->cnt,
+		   c->oecode == MULT_EXPR
+		   ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
+	  print_generic_expr (dump_file, c->op, 0);
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  /* Process the (operand, code) pairs in order of most occurence.  */
+  candidates2 = sbitmap_alloc (length);
+  while (!VEC_empty (oecount, cvec))
+    {
+      oecount *c = VEC_last (oecount, cvec);
+      if (c->cnt < 2)
+	break;
+
+      /* Now collect the operands in the outer chain that contain
+         the common operand in their inner chain.  */
+      sbitmap_zero (candidates2);
+      nr_candidates2 = 0;
+      EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+	{
+	  gimple oedef;
+	  enum tree_code oecode;
+	  unsigned j;
+	  tree op = VEC_index (operand_entry_t, *ops, i)->op;
+
+	  /* If we undistributed in this chain already this may be
+	     a constant.  */
+	  if (TREE_CODE (op) != SSA_NAME)
+	    continue;
+
+	  oedef = SSA_NAME_DEF_STMT (op);
+	  oecode = gimple_assign_rhs_code (oedef);
+	  if (oecode != c->oecode)
+	    continue;
+
+	  for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+	    {
+	      if (oe1->op == c->op)
+		{
+		  SET_BIT (candidates2, i);
+		  ++nr_candidates2;
+		  break;
+		}
+	    }
+	}
+
+      if (nr_candidates2 >= 2)
+	{
+	  operand_entry_t oe1, oe2;
+	  tree tmpvar;
+	  gimple prod;
+	  int first = sbitmap_first_set_bit (candidates2);
+
+	  /* Build the new addition chain.  */
+	  oe1 = VEC_index (operand_entry_t, *ops, first);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Building (");
+	      print_generic_expr (dump_file, oe1->op, 0);
+	    }
+	  tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
+	  add_referenced_var (tmpvar);
+	  zero_one_operation (&oe1->op, c->oecode, c->op);
+	  EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
+	    {
+	      gimple sum;
+	      oe2 = VEC_index (operand_entry_t, *ops, i);
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, " + ");
+		  print_generic_expr (dump_file, oe2->op, 0);
+		}
+	      zero_one_operation (&oe2->op, c->oecode, c->op);
+	      sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
+	      oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node);
+	      oe2->rank = 0;
+	      oe1->op = gimple_get_lhs (sum);
+	    }
+
+	  /* Apply the multiplication/division.  */
+	  prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
+	      print_generic_expr (dump_file, c->op, 0);
+	      fprintf (dump_file, "\n");
+	    }
+
+	  /* Record it in the addition chain and disable further
+	     undistribution with this op.  */
+	  oe1->op = gimple_assign_lhs (prod);
+	  oe1->rank = get_rank (oe1->op);
+	  VEC_free (operand_entry_t, heap, subops[first]);
+
+	  changed = true;
+	}
+
+      VEC_pop (oecount, cvec);
+    }
+
+  for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
+    VEC_free (operand_entry_t, heap, subops[i]);
+  free (subops);
+  VEC_free (oecount, heap, cvec);
+  sbitmap_free (candidates);
+  sbitmap_free (candidates2);
+
+  return changed;
+}
+
+
+/* Perform various identities and other optimizations on the list of
+   operand entries, stored in OPS.  The tree code for the binary
+   operation between all the operands is OPCODE.  */
+
+static void
+optimize_ops_list (enum tree_code opcode,
+		   VEC (operand_entry_t, heap) **ops)
+{
+  unsigned int length = VEC_length (operand_entry_t, *ops);
+  unsigned int i;
+  operand_entry_t oe;
+  operand_entry_t oelast = NULL;
+  bool iterate = false;
+
+  if (length == 1)
+    return;
+
+  oelast = VEC_last (operand_entry_t, *ops);
+
+  /* If the last two are constants, pop the constants off, merge them
+     and try the next two.  */
+  if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
+    {
+      operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
+
+      if (oelm1->rank == 0
+	  && is_gimple_min_invariant (oelm1->op)
+	  && useless_type_conversion_p (TREE_TYPE (oelm1->op),
+				       TREE_TYPE (oelast->op)))
+	{
+	  tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
+				     oelm1->op, oelast->op);
+
+	  if (folded && is_gimple_min_invariant (folded))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Merging constants\n");
+
+	      VEC_pop (operand_entry_t, *ops);
+	      VEC_pop (operand_entry_t, *ops);
+
+	      add_to_ops_vec (ops, folded);
+	      reassociate_stats.constants_eliminated++;
+
+	      optimize_ops_list (opcode, ops);
+	      return;
+	    }
+	}
+    }
+
+  eliminate_using_constants (opcode, ops);
+  oelast = NULL;
+
+  for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
+    {
+      bool done = false;
+
+      if (eliminate_not_pairs (opcode, ops, i, oe))
+	return;
+      if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
+	  || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
+	{
+	  if (done)
+	    return;
+	  iterate = true;
+	  oelast = NULL;
+	  continue;
+	}
+      oelast = oe;
+      i++;
+    }
+
+  length  = VEC_length (operand_entry_t, *ops);
+  oelast = VEC_last (operand_entry_t, *ops);
+
+  if (iterate)
+    optimize_ops_list (opcode, ops);
+}
+
+/* Return true if OPERAND is defined by a PHI node which uses the LHS
+   of STMT in it's operands.  This is also known as a "destructive
+   update" operation.  */
+
+static bool
+is_phi_for_stmt (gimple stmt, tree operand)
+{
+  gimple def_stmt;
+  tree lhs;
+  use_operand_p arg_p;
+  ssa_op_iter i;
+
+  if (TREE_CODE (operand) != SSA_NAME)
+    return false;
+
+  lhs = gimple_assign_lhs (stmt);
+
+  def_stmt = SSA_NAME_DEF_STMT (operand);
+  if (gimple_code (def_stmt) != GIMPLE_PHI)
+    return false;
+
+  FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
+    if (lhs == USE_FROM_PTR (arg_p))
+      return true;
+  return false;
+}
+
+/* Remove def stmt of VAR if VAR has zero uses and recurse
+   on rhs1 operand if so.  */
+
+static void
+remove_visited_stmt_chain (tree var)
+{
+  gimple stmt;
+  gimple_stmt_iterator gsi;
+
+  while (1)
+    {
+      if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
+	return;
+      stmt = SSA_NAME_DEF_STMT (var);
+      if (!is_gimple_assign (stmt)
+	  || !gimple_visited_p (stmt))
+	return;
+      var = gimple_assign_rhs1 (stmt);
+      gsi = gsi_for_stmt (stmt);
+      gsi_remove (&gsi, true);
+      release_defs (stmt);
+    }
+}
+
+/* Recursively rewrite our linearized statements so that the operators
+   match those in OPS[OPINDEX], putting the computation in rank
+   order.  */
+
+static void
+rewrite_expr_tree (gimple stmt, unsigned int opindex,
+		   VEC(operand_entry_t, heap) * ops, bool moved)
+{
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree rhs2 = gimple_assign_rhs2 (stmt);
+  operand_entry_t oe;
+
+  /* If we have three operands left, then we want to make sure the one
+     that gets the double binary op are the ones with the same rank.
+
+     The alternative we try is to see if this is a destructive
+     update style statement, which is like:
+     b = phi (a, ...)
+     a = c + b;
+     In that case, we want to use the destructive update form to
+     expose the possible vectorizer sum reduction opportunity.
+     In that case, the third operand will be the phi node.
+
+     We could, of course, try to be better as noted above, and do a
+     lot of work to try to find these opportunities in >3 operand
+     cases, but it is unlikely to be worth it.  */
+  if (opindex + 3 == VEC_length (operand_entry_t, ops))
+    {
+      operand_entry_t oe1, oe2, oe3;
+
+      oe1 = VEC_index (operand_entry_t, ops, opindex);
+      oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
+      oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
+
+      if ((oe1->rank == oe2->rank
+	   && oe2->rank != oe3->rank)
+	  || (is_phi_for_stmt (stmt, oe3->op)
+	      && !is_phi_for_stmt (stmt, oe1->op)
+	      && !is_phi_for_stmt (stmt, oe2->op)))
+	{
+	  struct operand_entry temp = *oe3;
+	  oe3->op = oe1->op;
+	  oe3->rank = oe1->rank;
+	  oe1->op = temp.op;
+	  oe1->rank= temp.rank;
+	}
+      else if ((oe1->rank == oe3->rank
+		&& oe2->rank != oe3->rank)
+	       || (is_phi_for_stmt (stmt, oe2->op)
+		   && !is_phi_for_stmt (stmt, oe1->op)
+		   && !is_phi_for_stmt (stmt, oe3->op)))
+	{
+	  struct operand_entry temp = *oe2;
+	  oe2->op = oe1->op;
+	  oe2->rank = oe1->rank;
+	  oe1->op = temp.op;
+	  oe1->rank= temp.rank;
+	}
+    }
+
+  /* The final recursion case for this function is that you have
+     exactly two operations left.
+     If we had one exactly one op in the entire list to start with, we
+     would have never called this function, and the tail recursion
+     rewrites them one at a time.  */
+  if (opindex + 2 == VEC_length (operand_entry_t, ops))
+    {
+      operand_entry_t oe1, oe2;
+
+      oe1 = VEC_index (operand_entry_t, ops, opindex);
+      oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
+
+      if (rhs1 != oe1->op || rhs2 != oe2->op)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Transforming ");
+	      print_gimple_stmt (dump_file, stmt, 0, 0);
+	    }
+
+	  gimple_assign_set_rhs1 (stmt, oe1->op);
+	  gimple_assign_set_rhs2 (stmt, oe2->op);
+	  update_stmt (stmt);
+	  if (rhs1 != oe1->op && rhs1 != oe2->op)
+	    remove_visited_stmt_chain (rhs1);
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, " into ");
+	      print_gimple_stmt (dump_file, stmt, 0, 0);
+	    }
+
+	}
+      return;
+    }
+
+  /* If we hit here, we should have 3 or more ops left.  */
+  gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
+
+  /* Rewrite the next operator.  */
+  oe = VEC_index (operand_entry_t, ops, opindex);
+
+  if (oe->op != rhs2)
+    {
+      if (!moved)
+	{
+	  gimple_stmt_iterator gsinow, gsirhs1;
+	  gimple stmt1 = stmt, stmt2;
+	  unsigned int count;
+
+	  gsinow = gsi_for_stmt (stmt);
+	  count = VEC_length (operand_entry_t, ops) - opindex - 2;
+	  while (count-- != 0)
+	    {
+	      stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
+	      gsirhs1 = gsi_for_stmt (stmt2);
+	      gsi_move_before (&gsirhs1, &gsinow);
+	      gsi_prev (&gsinow);
+	      stmt1 = stmt2;
+	    }
+	  moved = true;
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Transforming ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      gimple_assign_set_rhs2 (stmt, oe->op);
+      update_stmt (stmt);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, " into ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+    }
+  /* Recurse on the LHS of the binary operator, which is guaranteed to
+     be the non-leaf side.  */
+  rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved);
+}
+
+/* Transform STMT, which is really (A +B) + (C + D) into the left
+   linear form, ((A+B)+C)+D.
+   Recurse on D if necessary.  */
+
+static void
+linearize_expr (gimple stmt)
+{
+  gimple_stmt_iterator gsinow, gsirhs;
+  gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
+  gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
+  enum tree_code rhscode = gimple_assign_rhs_code (stmt);
+  gimple newbinrhs = NULL;
+  struct loop *loop = loop_containing_stmt (stmt);
+
+  gcc_assert (is_reassociable_op (binlhs, rhscode, loop)
+	      && is_reassociable_op (binrhs, rhscode, loop));
+
+  gsinow = gsi_for_stmt (stmt);
+  gsirhs = gsi_for_stmt (binrhs);
+  gsi_move_before (&gsirhs, &gsinow);
+
+  gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
+  gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
+  gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
+
+  if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
+    newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Linearized: ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+    }
+
+  reassociate_stats.linearized++;
+  update_stmt (binrhs);
+  update_stmt (binlhs);
+  update_stmt (stmt);
+
+  gimple_set_visited (stmt, true);
+  gimple_set_visited (binlhs, true);
+  gimple_set_visited (binrhs, true);
+
+  /* Tail recurse on the new rhs if it still needs reassociation.  */
+  if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
+    /* ??? This should probably be linearize_expr (newbinrhs) but I don't
+	   want to change the algorithm while converting to tuples.  */
+    linearize_expr (stmt);
+}
+
+/* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
+   it.  Otherwise, return NULL.  */
+
+static gimple
+get_single_immediate_use (tree lhs)
+{
+  use_operand_p immuse;
+  gimple immusestmt;
+
+  if (TREE_CODE (lhs) == SSA_NAME
+      && single_imm_use (lhs, &immuse, &immusestmt)
+      && is_gimple_assign (immusestmt))
+    return immusestmt;
+
+  return NULL;
+}
+
+static VEC(tree, heap) *broken_up_subtracts;
+
+/* Recursively negate the value of TONEGATE, and return the SSA_NAME
+   representing the negated value.  Insertions of any necessary
+   instructions go before GSI.
+   This function is recursive in that, if you hand it "a_5" as the
+   value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
+   transform b_3 + b_4 into a_5 = -b_3 + -b_4.  */
+
+static tree
+negate_value (tree tonegate, gimple_stmt_iterator *gsi)
+{
+  gimple negatedefstmt= NULL;
+  tree resultofnegate;
+
+  /* If we are trying to negate a name, defined by an add, negate the
+     add operands instead.  */
+  if (TREE_CODE (tonegate) == SSA_NAME)
+    negatedefstmt = SSA_NAME_DEF_STMT (tonegate);
+  if (TREE_CODE (tonegate) == SSA_NAME
+      && is_gimple_assign (negatedefstmt)
+      && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME
+      && has_single_use (gimple_assign_lhs (negatedefstmt))
+      && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
+    {
+      gimple_stmt_iterator gsi;
+      tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
+      tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
+
+      gsi = gsi_for_stmt (negatedefstmt);
+      rhs1 = negate_value (rhs1, &gsi);
+      gimple_assign_set_rhs1 (negatedefstmt, rhs1);
+
+      gsi = gsi_for_stmt (negatedefstmt);
+      rhs2 = negate_value (rhs2, &gsi);
+      gimple_assign_set_rhs2 (negatedefstmt, rhs2);
+
+      update_stmt (negatedefstmt);
+      return gimple_assign_lhs (negatedefstmt);
+    }
+
+  tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
+  resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
+					     NULL_TREE, true, GSI_SAME_STMT);
+  VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
+  return resultofnegate;
+}
+
+/* Return true if we should break up the subtract in STMT into an add
+   with negate.  This is true when we the subtract operands are really
+   adds, or the subtract itself is used in an add expression.  In
+   either case, breaking up the subtract into an add with negate
+   exposes the adds to reassociation.  */
+
+static bool
+should_break_up_subtract (gimple stmt)
+{
+  tree lhs = gimple_assign_lhs (stmt);
+  tree binlhs = gimple_assign_rhs1 (stmt);
+  tree binrhs = gimple_assign_rhs2 (stmt);
+  gimple immusestmt;
+  struct loop *loop = loop_containing_stmt (stmt);
+
+  if (TREE_CODE (binlhs) == SSA_NAME
+      && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
+    return true;
+
+  if (TREE_CODE (binrhs) == SSA_NAME
+      && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
+    return true;
+
+  if (TREE_CODE (lhs) == SSA_NAME
+      && (immusestmt = get_single_immediate_use (lhs))
+      && is_gimple_assign (immusestmt)
+      && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
+	  ||  gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
+    return true;
+  return false;
+}
+
+/* Transform STMT from A - B into A + -B.  */
+
+static void
+break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
+{
+  tree rhs1 = gimple_assign_rhs1 (stmt);
+  tree rhs2 = gimple_assign_rhs2 (stmt);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Breaking up subtract ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+    }
+
+  rhs2 = negate_value (rhs2, gsip);
+  gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2);
+  update_stmt (stmt);
+}
+
+/* Recursively linearize a binary expression that is the RHS of STMT.
+   Place the operands of the expression tree in the vector named OPS.  */
+
+static void
+linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
+		     bool is_associative, bool set_visited)
+{
+  tree binlhs = gimple_assign_rhs1 (stmt);
+  tree binrhs = gimple_assign_rhs2 (stmt);
+  gimple binlhsdef, binrhsdef;
+  bool binlhsisreassoc = false;
+  bool binrhsisreassoc = false;
+  enum tree_code rhscode = gimple_assign_rhs_code (stmt);
+  struct loop *loop = loop_containing_stmt (stmt);
+
+  if (set_visited)
+    gimple_set_visited (stmt, true);
+
+  if (TREE_CODE (binlhs) == SSA_NAME)
+    {
+      binlhsdef = SSA_NAME_DEF_STMT (binlhs);
+      binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
+    }
+
+  if (TREE_CODE (binrhs) == SSA_NAME)
+    {
+      binrhsdef = SSA_NAME_DEF_STMT (binrhs);
+      binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
+    }
+
+  /* If the LHS is not reassociable, but the RHS is, we need to swap
+     them.  If neither is reassociable, there is nothing we can do, so
+     just put them in the ops vector.  If the LHS is reassociable,
+     linearize it.  If both are reassociable, then linearize the RHS
+     and the LHS.  */
+
+  if (!binlhsisreassoc)
+    {
+      tree temp;
+
+      /* If this is not a associative operation like division, give up.  */
+      if (!is_associative)
+	{
+	  add_to_ops_vec (ops, binrhs);
+	  return;
+	}
+
+      if (!binrhsisreassoc)
+	{
+	  add_to_ops_vec (ops, binrhs);
+	  add_to_ops_vec (ops, binlhs);
+	  return;
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "swapping operands of ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      swap_tree_operands (stmt,
+			  gimple_assign_rhs1_ptr (stmt),
+			  gimple_assign_rhs2_ptr (stmt));
+      update_stmt (stmt);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, " is now ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      /* We want to make it so the lhs is always the reassociative op,
+	 so swap.  */
+      temp = binlhs;
+      binlhs = binrhs;
+      binrhs = temp;
+    }
+  else if (binrhsisreassoc)
+    {
+      linearize_expr (stmt);
+      binlhs = gimple_assign_rhs1 (stmt);
+      binrhs = gimple_assign_rhs2 (stmt);
+    }
+
+  gcc_assert (TREE_CODE (binrhs) != SSA_NAME
+	      || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
+				      rhscode, loop));
+  linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
+		       is_associative, set_visited);
+  add_to_ops_vec (ops, binrhs);
+}
+
+/* Repropagate the negates back into subtracts, since no other pass
+   currently does it.  */
+
+static void
+repropagate_negates (void)
+{
+  unsigned int i = 0;
+  tree negate;
+
+  for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
+    {
+      gimple user = get_single_immediate_use (negate);
+
+      /* The negate operand can be either operand of a PLUS_EXPR
+	 (it can be the LHS if the RHS is a constant for example).
+
+	 Force the negate operand to the RHS of the PLUS_EXPR, then
+	 transform the PLUS_EXPR into a MINUS_EXPR.  */
+      if (user
+	  && is_gimple_assign (user)
+	  && gimple_assign_rhs_code (user) == PLUS_EXPR)
+	{
+	  /* If the negated operand appears on the LHS of the
+	     PLUS_EXPR, exchange the operands of the PLUS_EXPR
+	     to force the negated operand to the RHS of the PLUS_EXPR.  */
+	  if (gimple_assign_rhs1 (user) == negate)
+	    {
+	      swap_tree_operands (user,
+				  gimple_assign_rhs1_ptr (user),
+				  gimple_assign_rhs2_ptr (user));
+	    }
+
+	  /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
+	     the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR.  */
+	  if (gimple_assign_rhs2 (user) == negate)
+	    {
+	      tree rhs1 = gimple_assign_rhs1 (user);
+	      tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
+	      gimple_stmt_iterator gsi = gsi_for_stmt (user);
+	      gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
+	      update_stmt (user);
+	    }
+	}
+    }
+}
+
+/* Break up subtract operations in block BB.
+
+   We do this top down because we don't know whether the subtract is
+   part of a possible chain of reassociation except at the top.
+ 
+   IE given
+   d = f + g
+   c = a + e
+   b = c - d
+   q = b - r
+   k = t - q
+   
+   we want to break up k = t - q, but we won't until we've transformed q
+   = b - r, which won't be broken up until we transform b = c - d.
+
+   En passant, clear the GIMPLE visited flag on every statement.  */
+
+static void
+break_up_subtract_bb (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  basic_block son;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+      gimple_set_visited (stmt, false);
+
+      /* Look for simple gimple subtract operations.  */
+      if (is_gimple_assign (stmt)
+	  && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
+	{
+	  tree lhs = gimple_assign_lhs (stmt);
+	  tree rhs1 = gimple_assign_rhs1 (stmt);
+	  tree rhs2 = gimple_assign_rhs2 (stmt);
+
+	  /* If associative-math we can do reassociation for
+	     non-integral types.  Or, we can do reassociation for
+	     non-saturating fixed-point types.  */
+	  if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
+	      && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
+		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
+		  || !flag_associative_math)
+	      && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
+		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
+		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
+	    continue;
+
+	  /* Check for a subtract used only in an addition.  If this
+	     is the case, transform it into add of a negate for better
+	     reassociation.  IE transform C = A-B into C = A + -B if C
+	     is only used in an addition.  */
+	  if (should_break_up_subtract (stmt))
+	    break_up_subtract (stmt, &gsi);
+	}
+    }
+  for (son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    break_up_subtract_bb (son);
+}
+
+/* Reassociate expressions in basic block BB and its post-dominator as
+   children.  */
+
+static void
+reassociate_bb (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  basic_block son;
+
+  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+
+      if (is_gimple_assign (stmt))
+	{
+	  tree lhs, rhs1, rhs2;
+	  enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+
+	  /* If this is not a gimple binary expression, there is
+	     nothing for us to do with it.  */
+	  if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS)
+	    continue;
+
+	  /* If this was part of an already processed statement,
+	     we don't need to touch it again. */
+	  if (gimple_visited_p (stmt))
+	    {
+	      /* This statement might have become dead because of previous
+		 reassociations.  */
+	      if (has_zero_uses (gimple_get_lhs (stmt)))
+		{
+		  gsi_remove (&gsi, true);
+		  release_defs (stmt);
+		  /* We might end up removing the last stmt above which
+		     places the iterator to the end of the sequence.
+		     Reset it to the last stmt in this case which might
+		     be the end of the sequence as well if we removed
+		     the last statement of the sequence.  In which case
+		     we need to bail out.  */
+		  if (gsi_end_p (gsi))
+		    {
+		      gsi = gsi_last_bb (bb);
+		      if (gsi_end_p (gsi))
+			break;
+		    }
+		}
+	      continue;
+	    }
+
+	  lhs = gimple_assign_lhs (stmt);
+	  rhs1 = gimple_assign_rhs1 (stmt);
+	  rhs2 = gimple_assign_rhs2 (stmt);
+
+	  /* If associative-math we can do reassociation for
+	     non-integral types.  Or, we can do reassociation for
+	     non-saturating fixed-point types.  */
+	  if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
+	      && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
+		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
+		  || !flag_associative_math)
+	      && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
+		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
+		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
+	    continue;
+
+	  if (associative_tree_code (rhs_code))
+	    {
+	      VEC(operand_entry_t, heap) *ops = NULL;
+
+	      /* There may be no immediate uses left by the time we
+		 get here because we may have eliminated them all.  */
+	      if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
+		continue;
+
+	      gimple_set_visited (stmt, true);
+	      linearize_expr_tree (&ops, stmt, true, true);
+	      qsort (VEC_address (operand_entry_t, ops),
+		     VEC_length (operand_entry_t, ops),
+		     sizeof (operand_entry_t),
+		     sort_by_operand_rank);
+	      optimize_ops_list (rhs_code, &ops);
+	      if (undistribute_ops_list (rhs_code, &ops,
+					 loop_containing_stmt (stmt)))
+		{
+		  qsort (VEC_address (operand_entry_t, ops),
+			 VEC_length (operand_entry_t, ops),
+			 sizeof (operand_entry_t),
+			 sort_by_operand_rank);
+		  optimize_ops_list (rhs_code, &ops);
+		}
+
+	      if (VEC_length (operand_entry_t, ops) == 1)
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file, "Transforming ");
+		      print_gimple_stmt (dump_file, stmt, 0, 0);
+		    }
+
+		  rhs1 = gimple_assign_rhs1 (stmt);
+		  gimple_assign_set_rhs_from_tree (&gsi,
+						   VEC_last (operand_entry_t,
+							     ops)->op);
+		  update_stmt (stmt);
+		  remove_visited_stmt_chain (rhs1);
+
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file, " into ");
+		      print_gimple_stmt (dump_file, stmt, 0, 0);
+		    }
+		}
+	      else
+		rewrite_expr_tree (stmt, 0, ops, false);
+
+	      VEC_free (operand_entry_t, heap, ops);
+	    }
+	}
+    }
+  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_POST_DOMINATORS, son))
+    reassociate_bb (son);
+}
+
+void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
+void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
+
+/* Dump the operand entry vector OPS to FILE.  */
+
+void
+dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
+{
+  operand_entry_t oe;
+  unsigned int i;
+
+  for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
+    {
+      fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
+      print_generic_expr (file, oe->op, 0);
+    }
+}
+
+/* Dump the operand entry vector OPS to STDERR.  */
+
+void
+debug_ops_vector (VEC (operand_entry_t, heap) *ops)
+{
+  dump_ops_vector (stderr, ops);
+}
+
+static void
+do_reassoc (void)
+{
+  break_up_subtract_bb (ENTRY_BLOCK_PTR);
+  reassociate_bb (EXIT_BLOCK_PTR);
+}
+
+/* Initialize the reassociation pass.  */
+
+static void
+init_reassoc (void)
+{
+  int i;
+  long rank = 2;
+  tree param;
+  int *bbs = XNEWVEC (int, last_basic_block + 1);
+
+  /* Find the loops, so that we can prevent moving calculations in
+     them.  */
+  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+
+  memset (&reassociate_stats, 0, sizeof (reassociate_stats));
+
+  operand_entry_pool = create_alloc_pool ("operand entry pool",
+					  sizeof (struct operand_entry), 30);
+
+  /* Reverse RPO (Reverse Post Order) will give us something where
+     deeper loops come later.  */
+  pre_and_rev_post_order_compute (NULL, bbs, false);
+  bb_rank = XCNEWVEC (long, last_basic_block + 1);
+  operand_rank = pointer_map_create ();
+
+  /* Give each argument a distinct rank.   */
+  for (param = DECL_ARGUMENTS (current_function_decl);
+       param;
+       param = TREE_CHAIN (param))
+    {
+      if (gimple_default_def (cfun, param) != NULL)
+	{
+	  tree def = gimple_default_def (cfun, param);
+	  insert_operand_rank (def, ++rank);
+	}
+    }
+
+  /* Give the chain decl a distinct rank. */
+  if (cfun->static_chain_decl != NULL)
+    {
+      tree def = gimple_default_def (cfun, cfun->static_chain_decl);
+      if (def != NULL)
+	insert_operand_rank (def, ++rank);
+    }
+
+  /* Set up rank for each BB  */
+  for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+    bb_rank[bbs[i]] = ++rank  << 16;
+
+  free (bbs);
+  calculate_dominance_info (CDI_POST_DOMINATORS);
+  broken_up_subtracts = NULL;
+}
+
+/* Cleanup after the reassociation pass, and print stats if
+   requested.  */
+
+static void
+fini_reassoc (void)
+{
+  statistics_counter_event (cfun, "Linearized",
+			    reassociate_stats.linearized);
+  statistics_counter_event (cfun, "Constants eliminated",
+			    reassociate_stats.constants_eliminated);
+  statistics_counter_event (cfun, "Ops eliminated",
+			    reassociate_stats.ops_eliminated);
+  statistics_counter_event (cfun, "Statements rewritten",
+			    reassociate_stats.rewritten);
+
+  pointer_map_destroy (operand_rank);
+  free_alloc_pool (operand_entry_pool);
+  free (bb_rank);
+  VEC_free (tree, heap, broken_up_subtracts);
+  free_dominance_info (CDI_POST_DOMINATORS);
+  loop_optimizer_finalize ();
+}
+
+/* Gate and execute functions for Reassociation.  */
+
+static unsigned int
+execute_reassoc (void)
+{
+  init_reassoc ();
+
+  do_reassoc ();
+  repropagate_negates ();
+
+  fini_reassoc ();
+  return 0;
+}
+
+static bool
+gate_tree_ssa_reassoc (void)
+{
+  return flag_tree_reassoc != 0;
+}
+
+struct gimple_opt_pass pass_reassoc =
+{
+ {
+  GIMPLE_PASS,
+  "reassoc",				/* name */
+  gate_tree_ssa_reassoc,		/* gate */
+  execute_reassoc,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_REASSOC,			/* tv_id */
+  PROP_cfg | PROP_ssa | PROP_alias,	/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ }
+};
+