commit gcc-4.4.3 which is used to build gcc-4.4.3 Android toolchain in master.

The source is based on fsf gcc-4.4.3 and contains local patches which
are recorded in gcc-4.4.3/README.google.

Change-Id: Id8c6d6927df274ae9749196a1cc24dbd9abc9887

1 files changed, 6625 insertions, 0 deletions

diff --git a/gcc-4.4.3/gcc/tree-ssa-loop-ivopts.c b/gcc-4.4.3/gcc/tree-ssa-loop-ivopts.c
new file mode 100644
index 000000000..144dace8f
--- /dev/null
+++ b/gcc-4.4.3/gcc/tree-ssa-loop-ivopts.c
@@ -0,0 +1,6625 @@
+/* Induction variable optimizations.
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+   Free Software Foundation, Inc.
+   
+This file is part of GCC.
+   
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+   
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+   
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* This pass tries to find the optimal set of induction variables for the loop.
+   It optimizes just the basic linear induction variables (although adding
+   support for other types should not be too hard).  It includes the
+   optimizations commonly known as strength reduction, induction variable
+   coalescing and induction variable elimination.  It does it in the
+   following steps:
+
+   1) The interesting uses of induction variables are found.  This includes
+
+      -- uses of induction variables in non-linear expressions
+      -- addresses of arrays
+      -- comparisons of induction variables
+
+   2) Candidates for the induction variables are found.  This includes
+
+      -- old induction variables
+      -- the variables defined by expressions derived from the "interesting
+	 uses" above
+
+   3) The optimal (w.r. to a cost function) set of variables is chosen.  The
+      cost function assigns a cost to sets of induction variables and consists
+      of three parts:
+
+      -- The use costs.  Each of the interesting uses chooses the best induction
+	 variable in the set and adds its cost to the sum.  The cost reflects
+	 the time spent on modifying the induction variables value to be usable
+	 for the given purpose (adding base and offset for arrays, etc.).
+      -- The variable costs.  Each of the variables has a cost assigned that
+	 reflects the costs associated with incrementing the value of the
+	 variable.  The original variables are somewhat preferred.
+      -- The set cost.  Depending on the size of the set, extra cost may be
+	 added to reflect register pressure.
+
+      All the costs are defined in a machine-specific way, using the target
+      hooks and machine descriptions to determine them.
+
+   4) The trees are transformed to use the new variables, the dead code is
+      removed.
+   
+   All of this is done loop by loop.  Doing it globally is theoretically
+   possible, it might give a better performance and it might enable us
+   to decide costs more precisely, but getting all the interactions right
+   would be complicated.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "varray.h"
+#include "expr.h"
+#include "tree-pass.h"
+#include "ggc.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "pointer-set.h"
+#include "hashtab.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+#include "cfgloop.h"
+#include "params.h"
+#include "langhooks.h"
+#include "tree-affine.h"
+#include "target.h"
+#include "tree-inline.h"
+
+/* The infinite cost.  */
+#define INFTY 10000000
+
+#define AVG_LOOP_NITER(LOOP) 5
+
+/* Returns the expected number of loop iterations for LOOP.
+   The average trip count is computed from profile data if it
+   exists. */
+
+static inline unsigned
+avg_loop_niter (struct loop *loop)
+{
+  unsigned tc;
+  if (loop->header->count || loop->latch->count)
+    tc = expected_loop_iterations (loop);
+  else
+    tc = AVG_LOOP_NITER (loop);
+  if (tc == 0)
+    tc++;
+  return tc;
+}
+
+/* Representation of the induction variable.  */
+struct iv
+{
+  tree base;		/* Initial value of the iv.  */
+  tree base_object;	/* A memory object to that the induction variable points.  */
+  tree step;		/* Step of the iv (constant only).  */
+  tree ssa_name;	/* The ssa name with the value.  */
+  bool biv_p;		/* Is it a biv?  */
+  bool have_use_for;	/* Do we already have a use for it?  */
+  unsigned use_id;	/* The identifier in the use if it is the case.  */
+};
+
+/* Per-ssa version information (induction variable descriptions, etc.).  */
+struct version_info
+{
+  tree name;		/* The ssa name.  */
+  struct iv *iv;	/* Induction variable description.  */
+  bool has_nonlin_use;	/* For a loop-level invariant, whether it is used in
+			   an expression that is not an induction variable.  */
+  unsigned inv_id;	/* Id of an invariant.  */
+  bool preserve_biv;	/* For the original biv, whether to preserve it.  */
+};
+
+/* Types of uses.  */
+enum use_type
+{
+  USE_NONLINEAR_EXPR,	/* Use in a nonlinear expression.  */
+  USE_ADDRESS,		/* Use in an address.  */
+  USE_COMPARE		/* Use is a compare.  */
+};
+
+/* Cost of a computation.  */
+typedef struct
+{
+  unsigned cost;	/* The runtime cost.  */
+  unsigned complexity;	/* The estimate of the complexity of the code for
+			   the computation (in no concrete units --
+			   complexity field should be larger for more
+			   complex expressions and addressing modes).  */
+} comp_cost;
+
+static const comp_cost zero_cost = {0, 0};
+static const comp_cost infinite_cost = {INFTY, INFTY};
+
+/* The candidate - cost pair.  */
+struct cost_pair
+{
+  struct iv_cand *cand;	/* The candidate.  */
+  comp_cost cost;	/* The cost.  */
+  bitmap depends_on;	/* The list of invariants that have to be
+			   preserved.  */
+  tree value;		/* For final value elimination, the expression for
+			   the final value of the iv.  For iv elimination,
+			   the new bound to compare with.  */
+};
+
+/* The use position for iv.  */
+enum iv_use_pos
+{
+  IU_UNKNOWN,
+  IU_OUTSIDE_LOOP_ONLY,
+  IU_INSIDE_LOOP
+};
+
+/* Use.  */
+struct iv_use
+{
+  unsigned id;		/* The id of the use.  */
+  enum use_type type;	/* Type of the use.  */
+  struct iv *iv;	/* The induction variable it is based on.  */
+  gimple stmt;		/* Statement in that it occurs.  */
+  tree *op_p;		/* The place where it occurs.  */
+  bitmap related_cands;	/* The set of "related" iv candidates, plus the common
+			   important ones.  */
+
+  unsigned n_map_members; /* Number of candidates in the cost_map list.  */
+  struct cost_pair *cost_map;
+			/* The costs wrto the iv candidates.  */
+
+  struct iv_cand *selected;
+			/* The selected candidate.  */
+  enum iv_use_pos use_pos;
+                        /* The use position.  */
+};
+
+/* The position where the iv is computed.  */
+enum iv_position
+{
+  IP_NORMAL,		/* At the end, just before the exit condition.  */
+  IP_END,		/* At the end of the latch block.  */
+  IP_ORIGINAL		/* The original biv.  */
+};
+
+/* The induction variable candidate.  */
+struct iv_cand
+{
+  unsigned id;		/* The number of the candidate.  */
+  bool important;	/* Whether this is an "important" candidate, i.e. such
+			   that it should be considered by all uses.  */
+  enum iv_position pos;	/* Where it is computed.  */
+  gimple incremented_at;/* For original biv, the statement where it is
+			   incremented.  */
+  tree var_before;	/* The variable used for it before increment.  */
+  tree var_after;	/* The variable used for it after increment.  */
+  struct iv *iv;	/* The value of the candidate.  NULL for
+			   "pseudocandidate" used to indicate the possibility
+			   to replace the final value of an iv by direct
+			   computation of the value.  */
+  unsigned cost;	/* Cost of the candidate.  */
+  bitmap depends_on;	/* The list of invariants that are used in step of the
+			   biv.  */
+};
+
+/* The data used by the induction variable optimizations.  */
+
+typedef struct iv_use *iv_use_p;
+DEF_VEC_P(iv_use_p);
+DEF_VEC_ALLOC_P(iv_use_p,heap);
+
+typedef struct iv_cand *iv_cand_p;
+DEF_VEC_P(iv_cand_p);
+DEF_VEC_ALLOC_P(iv_cand_p,heap);
+
+typedef struct version_info *version_info_p;
+DEF_VEC_P(version_info_p);
+DEF_VEC_ALLOC_P(version_info_p,heap);
+
+
+struct ivopts_data
+{
+  /* The currently optimized loop.  */
+  struct loop *current_loop;
+
+  /* Numbers of iterations for all exits of the current loop.  */
+  struct pointer_map_t *niters;
+
+  /* Number of registers used in it.  */
+  unsigned regs_used;
+
+  /* The size of version_info array allocated.  */
+  unsigned version_info_size;
+
+  /* The array of information for the ssa names.  */
+  struct version_info *version_info;
+
+
+  /* Pseudo version infos for generated loop invariants.  */
+  VEC(version_info_p,heap) *pseudo_version_info;
+
+  /* The bitmap of indices in version_info whose value was changed.  */
+  bitmap relevant;
+
+  /* The uses of induction variables.  */
+  VEC(iv_use_p,heap) *iv_uses;
+
+  /* The candidates.  */
+  VEC(iv_cand_p,heap) *iv_candidates;
+
+  /* A bitmap of important candidates.  */
+  bitmap important_candidates;
+
+  /* The maximum invariant id.  */
+  unsigned max_inv_id;
+
+  /* The minimal invariant id for pseudo invariants.  */
+  unsigned min_pseudo_inv_id;
+
+  /* Whether to consider just related and important candidates when replacing a
+     use.  */
+  bool consider_all_candidates;
+
+  /* Are we optimizing for speed?  */
+  bool speed;
+};
+
+/* An assignment of iv candidates to uses.  */
+
+struct iv_ca
+{
+  /* The number of uses covered by the assignment.  */
+  unsigned upto;
+
+  /* Number of uses that cannot be expressed by the candidates in the set.  */
+  unsigned bad_uses;
+
+  /* Candidate assigned to a use, together with the related costs.  */
+  struct cost_pair **cand_for_use;
+
+  /* Number of times each candidate is used.  */
+  unsigned *n_cand_uses;
+
+  /* The candidates used.  */
+  bitmap cands;
+
+  /* The number of candidates in the set.  */
+  unsigned n_cands;
+
+  /* Total number of registers needed.  */
+  unsigned n_regs;
+
+  /* Total number of pseudo invariants.  */
+  unsigned n_pseudos;
+
+  /* Total cost of expressing uses.  */
+  comp_cost cand_use_cost;
+
+  /* Total cost of candidates.  */
+  unsigned cand_cost;
+
+  /* Number of times each invariant is used.  */
+  unsigned *n_invariant_uses;
+
+  /* Total cost of the assignment.  */
+  comp_cost cost;
+};
+
+/* Difference of two iv candidate assignments.  */
+
+struct iv_ca_delta
+{
+  /* Changed use.  */
+  struct iv_use *use;
+
+  /* An old assignment (for rollback purposes).  */
+  struct cost_pair *old_cp;
+
+  /* A new assignment.  */
+  struct cost_pair *new_cp;
+
+  /* Next change in the list.  */
+  struct iv_ca_delta *next_change;
+};
+
+/* Bound on number of candidates below that all candidates are considered.  */
+
+#define CONSIDER_ALL_CANDIDATES_BOUND \
+  ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
+
+/* If there are more iv occurrences, we just give up (it is quite unlikely that
+   optimizing such a loop would help, and it would take ages).  */
+
+#define MAX_CONSIDERED_USES \
+  ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
+
+/* If there are at most this number of ivs in the set, try removing unnecessary
+   ivs from the set always.  */
+
+#define ALWAYS_PRUNE_CAND_SET_BOUND \
+  ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
+
+/* The list of trees for that the decl_rtl field must be reset is stored
+   here.  */
+
+static VEC(tree,heap) *decl_rtl_to_reset;
+
+static struct pointer_map_t *inverted_stmt_map;
+
+/* Number of uses recorded in DATA.  */
+
+static inline unsigned
+n_iv_uses (struct ivopts_data *data)
+{
+  return VEC_length (iv_use_p, data->iv_uses);
+}
+
+/* Ith use recorded in DATA.  */
+
+static inline struct iv_use *
+iv_use (struct ivopts_data *data, unsigned i)
+{
+  return VEC_index (iv_use_p, data->iv_uses, i);
+}
+
+/* Number of candidates recorded in DATA.  */
+
+static inline unsigned
+n_iv_cands (struct ivopts_data *data)
+{
+  return VEC_length (iv_cand_p, data->iv_candidates);
+}
+
+/* Ith candidate recorded in DATA.  */
+
+static inline struct iv_cand *
+iv_cand (struct ivopts_data *data, unsigned i)
+{
+  return VEC_index (iv_cand_p, data->iv_candidates, i);
+}
+
+/* The single loop exit if it dominates the latch, NULL otherwise.  */
+
+edge
+single_dom_exit (struct loop *loop)
+{
+  edge exit = single_exit (loop);
+
+  if (!exit)
+    return NULL;
+
+  if (!just_once_each_iteration_p (loop, exit->src))
+    return NULL;
+
+  return exit;
+}
+
+/* Dumps information about the induction variable IV to FILE.  */
+
+extern void dump_iv (FILE *, struct iv *);
+void
+dump_iv (FILE *file, struct iv *iv)
+{
+  if (iv->ssa_name)
+    {
+      fprintf (file, "ssa name ");
+      print_generic_expr (file, iv->ssa_name, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+
+  fprintf (file, "  type ");
+  print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
+  fprintf (file, "\n");
+
+  if (iv->step)
+    {
+      fprintf (file, "  base ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+
+      fprintf (file, "  step ");
+      print_generic_expr (file, iv->step, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  else
+    {
+      fprintf (file, "  invariant ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+
+  if (iv->base_object)
+    {
+      fprintf (file, "  base object ");
+      print_generic_expr (file, iv->base_object, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+
+  if (iv->biv_p)
+    fprintf (file, "  is a biv\n");
+}
+
+/* Dumps information about the USE to FILE.  */
+
+extern void dump_use (FILE *, struct iv_use *);
+void
+dump_use (FILE *file, struct iv_use *use)
+{
+  fprintf (file, "use %d\n", use->id);
+
+  switch (use->type)
+    {
+    case USE_NONLINEAR_EXPR:
+      fprintf (file, "  generic\n");
+      break;
+
+    case USE_ADDRESS:
+      fprintf (file, "  address\n");
+      break;
+
+    case USE_COMPARE:
+      fprintf (file, "  compare\n");
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  fprintf (file, "  in statement ");
+  print_gimple_stmt (file, use->stmt, 0, 0);
+  fprintf (file, "\n");
+
+  fprintf (file, "  at position ");
+  if (use->op_p)
+    print_generic_expr (file, *use->op_p, TDF_SLIM);
+  fprintf (file, "\n");
+
+  dump_iv (file, use->iv);
+
+  if (use->related_cands)
+    {
+      fprintf (file, "  related candidates ");
+      dump_bitmap (file, use->related_cands);
+    }
+}
+
+/* Dumps information about the uses to FILE.  */
+
+extern void dump_uses (FILE *, struct ivopts_data *);
+void
+dump_uses (FILE *file, struct ivopts_data *data)
+{
+  unsigned i;
+  struct iv_use *use;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+
+      dump_use (file, use);
+      fprintf (file, "\n");
+    }
+}
+
+/* Dumps information about induction variable candidate CAND to FILE.  */
+
+extern void dump_cand (FILE *, struct iv_cand *);
+void
+dump_cand (FILE *file, struct iv_cand *cand)
+{
+  struct iv *iv = cand->iv;
+
+  fprintf (file, "candidate %d%s\n",
+	   cand->id, cand->important ? " (important)" : "");
+
+  if (cand->depends_on)
+    {
+      fprintf (file, "  depends on ");
+      dump_bitmap (file, cand->depends_on);
+    }
+
+  if (!iv)
+    {
+      fprintf (file, "  final value replacement\n");
+      return;
+    }
+
+  if (cand->var_before)
+    {
+      fprintf (file, "  var_before ");
+      print_generic_expr (file, cand->var_before, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  if (cand->var_after)
+    {
+      fprintf (file, "  var_after ");
+      print_generic_expr (file, cand->var_after, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+
+  switch (cand->pos)
+    {
+    case IP_NORMAL:
+      fprintf (file, "  incremented before exit test\n");
+      break;
+
+    case IP_END:
+      fprintf (file, "  incremented at end\n");
+      break;
+
+    case IP_ORIGINAL:
+      fprintf (file, "  original biv\n");
+      break;
+    }
+
+  dump_iv (file, iv);
+}
+
+/* Returns the info for ssa version VER.  */
+
+static inline struct version_info *
+ver_info (struct ivopts_data *data, unsigned ver)
+{
+  if (ver < data->min_pseudo_inv_id)
+    return data->version_info + ver;
+  else
+    return VEC_index (version_info_p, data->pseudo_version_info,
+                      ver - data->min_pseudo_inv_id);
+}
+
+/* Returns the info for ssa name NAME.  */
+
+static inline struct version_info *
+name_info (struct ivopts_data *data, tree name)
+{
+  return ver_info (data, SSA_NAME_VERSION (name));
+}
+
+/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
+   emitted in LOOP.  */
+
+static bool
+stmt_after_ip_normal_pos (struct loop *loop, gimple stmt)
+{
+  basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
+
+  gcc_assert (bb);
+
+  if (sbb == loop->latch)
+    return true;
+
+  if (sbb != bb)
+    return false;
+
+  return stmt == last_stmt (bb);
+}
+
+/* Returns true if STMT if after the place where the original induction
+   variable CAND is incremented.  */
+
+static bool
+stmt_after_ip_original_pos (struct iv_cand *cand, gimple stmt)
+{
+  basic_block cand_bb = gimple_bb (cand->incremented_at);
+  basic_block stmt_bb = gimple_bb (stmt);
+  gimple_stmt_iterator bsi;
+
+  if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
+    return false;
+
+  if (stmt_bb != cand_bb)
+    return true;
+
+  /* Scan the block from the end, since the original ivs are usually
+     incremented at the end of the loop body.  */
+  for (bsi = gsi_last_bb (stmt_bb); ; gsi_prev (&bsi))
+    {
+      if (gsi_stmt (bsi) == cand->incremented_at)
+	return false;
+      if (gsi_stmt (bsi) == stmt)
+	return true;
+    }
+}
+
+/* Returns true if STMT if after the place where the induction variable
+   CAND is incremented in LOOP.  */
+
+static bool
+stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple stmt)
+{
+  switch (cand->pos)
+    {
+    case IP_END:
+      return false;
+
+    case IP_NORMAL:
+      return stmt_after_ip_normal_pos (loop, stmt);
+
+    case IP_ORIGINAL:
+      return stmt_after_ip_original_pos (cand, stmt);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Returns true if EXP is a ssa name that occurs in an abnormal phi node.  */
+
+static bool
+abnormal_ssa_name_p (tree exp)
+{
+  if (!exp)
+    return false;
+
+  if (TREE_CODE (exp) != SSA_NAME)
+    return false;
+
+  return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
+}
+
+/* Returns false if BASE or INDEX contains a ssa name that occurs in an
+   abnormal phi node.  Callback for for_each_index.  */
+
+static bool
+idx_contains_abnormal_ssa_name_p (tree base, tree *index,
+				  void *data ATTRIBUTE_UNUSED)
+{
+  if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
+    {
+      if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
+	return false;
+      if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
+	return false;
+    }
+
+  return !abnormal_ssa_name_p (*index);
+}
+
+/* Returns true if EXPR contains a ssa name that occurs in an
+   abnormal phi node.  */
+
+bool
+contains_abnormal_ssa_name_p (tree expr)
+{
+  enum tree_code code;
+  enum tree_code_class codeclass;
+
+  if (!expr)
+    return false;
+
+  code = TREE_CODE (expr);
+  codeclass = TREE_CODE_CLASS (code);
+
+  if (code == SSA_NAME)
+    return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
+
+  if (code == INTEGER_CST
+      || is_gimple_min_invariant (expr))
+    return false;
+
+  if (code == ADDR_EXPR)
+    return !for_each_index (&TREE_OPERAND (expr, 0),
+			    idx_contains_abnormal_ssa_name_p,
+			    NULL);
+
+  switch (codeclass)
+    {
+    case tcc_binary:
+    case tcc_comparison:
+      if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
+	return true;
+
+      /* Fallthru.  */
+    case tcc_unary:
+      if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
+	return true;
+
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  return false;
+}
+
+/*  Returns tree describing number of iterations determined from
+    EXIT of DATA->current_loop, or NULL if something goes wrong.  */
+
+static tree
+niter_for_exit (struct ivopts_data *data, edge exit)
+{
+  struct tree_niter_desc desc;
+  tree niter;
+  void **slot;
+
+  if (!data->niters)
+    {
+      data->niters = pointer_map_create ();
+      slot = NULL;
+    }
+  else
+    slot = pointer_map_contains (data->niters, exit);
+
+  if (!slot)
+    {
+      /* Try to determine number of iterations.  We must know it
+	 unconditionally (i.e., without possibility of # of iterations
+	 being zero).  Also, we cannot safely work with ssa names that
+	 appear in phi nodes on abnormal edges, so that we do not create
+	 overlapping life ranges for them (PR 27283).  */
+      if (number_of_iterations_exit (data->current_loop,
+				     exit, &desc, true)
+	  && integer_zerop (desc.may_be_zero)
+     	  && !contains_abnormal_ssa_name_p (desc.niter))
+	niter = desc.niter;
+      else
+	niter = NULL_TREE;
+
+      *pointer_map_insert (data->niters, exit) = niter;
+    }
+  else
+    niter = (tree) *slot;
+
+  return niter;
+}
+
+/* Returns tree describing number of iterations determined from
+   single dominating exit of DATA->current_loop, or NULL if something
+   goes wrong.  */
+
+static tree
+niter_for_single_dom_exit (struct ivopts_data *data)
+{
+  edge exit = single_dom_exit (data->current_loop);
+
+  if (!exit)
+    return NULL;
+
+  return niter_for_exit (data, exit);
+}
+
+/* Initializes data structures used by the iv optimization pass, stored
+   in DATA.  */
+
+static void
+tree_ssa_iv_optimize_init (struct ivopts_data *data)
+{
+  data->version_info_size = 2 * num_ssa_names;
+  data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
+  data->min_pseudo_inv_id = num_ssa_names;
+  data->pseudo_version_info = NULL;
+  data->relevant = BITMAP_ALLOC (NULL);
+  data->important_candidates = BITMAP_ALLOC (NULL);
+  data->max_inv_id = 0;
+  data->niters = NULL;
+  data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
+  data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
+  decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
+}
+
+/* Returns a memory object to that EXPR points.  In case we are able to
+   determine that it does not point to any such object, NULL is returned.  */
+
+static tree
+determine_base_object (tree expr)
+{
+  enum tree_code code = TREE_CODE (expr);
+  tree base, obj;
+
+  /* If this is a pointer casted to any type, we need to determine
+     the base object for the pointer; so handle conversions before
+     throwing away non-pointer expressions.  */
+  if (CONVERT_EXPR_P (expr))
+    return determine_base_object (TREE_OPERAND (expr, 0));
+
+  if (!POINTER_TYPE_P (TREE_TYPE (expr)))
+    return NULL_TREE;
+
+  switch (code)
+    {
+    case INTEGER_CST:
+      return NULL_TREE;
+
+    case ADDR_EXPR:
+      obj = TREE_OPERAND (expr, 0);
+      base = get_base_address (obj);
+
+      if (!base)
+	return expr;
+
+      if (TREE_CODE (base) == INDIRECT_REF)
+	return determine_base_object (TREE_OPERAND (base, 0));
+
+      return fold_convert (ptr_type_node,
+		           build_fold_addr_expr (base));
+
+    case POINTER_PLUS_EXPR:
+      return determine_base_object (TREE_OPERAND (expr, 0));
+
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      /* Pointer addition is done solely using POINTER_PLUS_EXPR.  */
+      gcc_unreachable ();
+
+    default:
+      return fold_convert (ptr_type_node, expr);
+    }
+}
+
+/* Allocates an induction variable with given initial value BASE and step STEP
+   for loop LOOP.  */
+
+static struct iv *
+alloc_iv (tree base, tree step)
+{
+  struct iv *iv = XCNEW (struct iv);
+  gcc_assert (step != NULL_TREE);
+
+  iv->base = base;
+  iv->base_object = determine_base_object (base);
+  iv->step = step;
+  iv->biv_p = false;
+  iv->have_use_for = false;
+  iv->use_id = 0;
+  iv->ssa_name = NULL_TREE;
+
+  return iv;
+}
+
+/* Sets STEP and BASE for induction variable IV.  */
+
+static void
+set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
+{
+  struct version_info *info = name_info (data, iv);
+
+  gcc_assert (!info->iv);
+
+  bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
+  info->iv = alloc_iv (base, step);
+  info->iv->ssa_name = iv;
+}
+
+/* Finds induction variable declaration for VAR.  */
+
+static struct iv *
+get_iv (struct ivopts_data *data, tree var)
+{
+  basic_block bb;
+  tree type = TREE_TYPE (var);
+
+  if (!POINTER_TYPE_P (type)
+      && !INTEGRAL_TYPE_P (type))
+    return NULL;
+
+  if (!name_info (data, var)->iv)
+    {
+      bb = gimple_bb (SSA_NAME_DEF_STMT (var));
+
+      if (!bb
+	  || !flow_bb_inside_loop_p (data->current_loop, bb))
+	set_iv (data, var, var, build_int_cst (type, 0));
+    }
+
+  return name_info (data, var)->iv;
+}
+
+/* Determines the step of a biv defined in PHI.  Returns NULL if PHI does
+   not define a simple affine biv with nonzero step.  */
+
+static tree
+determine_biv_step (gimple phi)
+{
+  struct loop *loop = gimple_bb (phi)->loop_father;
+  tree name = PHI_RESULT (phi);
+  affine_iv iv;
+
+  if (!is_gimple_reg (name))
+    return NULL_TREE;
+
+  if (!simple_iv (loop, loop, name, &iv, true))
+    return NULL_TREE;
+
+  return integer_zerop (iv.step) ? NULL_TREE : iv.step;
+}
+
+/* Finds basic ivs.  */
+
+static bool
+find_bivs (struct ivopts_data *data)
+{
+  gimple phi;
+  tree step, type, base;
+  bool found = false;
+  struct loop *loop = data->current_loop;
+  gimple_stmt_iterator psi;
+
+  for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      phi = gsi_stmt (psi);
+
+      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
+	continue;
+
+      step = determine_biv_step (phi);
+      if (!step)
+	continue;
+
+      base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+      base = expand_simple_operations (base);
+      if (contains_abnormal_ssa_name_p (base)
+	  || contains_abnormal_ssa_name_p (step))
+	continue;
+
+      type = TREE_TYPE (PHI_RESULT (phi));
+      base = fold_convert (type, base);
+      if (step)
+	{
+	  if (POINTER_TYPE_P (type))
+	    step = fold_convert (sizetype, step);
+	  else
+	    step = fold_convert (type, step);
+	}
+
+      set_iv (data, PHI_RESULT (phi), base, step);
+      found = true;
+    }
+
+  return found;
+}
+
+/* Marks basic ivs.  */
+
+static void
+mark_bivs (struct ivopts_data *data)
+{
+  gimple phi;
+  tree var;
+  struct iv *iv, *incr_iv;
+  struct loop *loop = data->current_loop;
+  basic_block incr_bb;
+  gimple_stmt_iterator psi;
+
+  for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      phi = gsi_stmt (psi);
+
+      iv = get_iv (data, PHI_RESULT (phi));
+      if (!iv)
+	continue;
+
+      var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
+      incr_iv = get_iv (data, var);
+      if (!incr_iv)
+	continue;
+
+      /* If the increment is in the subloop, ignore it.  */
+      incr_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
+      if (incr_bb->loop_father != data->current_loop
+	  || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
+	continue;
+
+      iv->biv_p = true;
+      incr_iv->biv_p = true;
+    }
+}
+
+/* Checks whether STMT defines a linear induction variable and stores its
+   parameters to IV.  */
+
+static bool
+find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv)
+{
+  tree lhs;
+  struct loop *loop = data->current_loop;
+
+  iv->base = NULL_TREE;
+  iv->step = NULL_TREE;
+
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return false;
+
+  lhs = gimple_assign_lhs (stmt);
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return false;
+
+  if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
+    return false;
+  iv->base = expand_simple_operations (iv->base);
+
+  if (contains_abnormal_ssa_name_p (iv->base)
+      || contains_abnormal_ssa_name_p (iv->step))
+    return false;
+
+  return true;
+}
+
+/* Finds general ivs in statement STMT.  */
+
+static void
+find_givs_in_stmt (struct ivopts_data *data, gimple stmt)
+{
+  affine_iv iv;
+
+  if (!find_givs_in_stmt_scev (data, stmt, &iv))
+    return;
+
+  set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step);
+}
+
+/* Finds general ivs in basic block BB.  */
+
+static void
+find_givs_in_bb (struct ivopts_data *data, basic_block bb)
+{
+  gimple_stmt_iterator bsi;
+
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+    find_givs_in_stmt (data, gsi_stmt (bsi));
+}
+
+/* Finds general ivs.  */
+
+static void
+find_givs (struct ivopts_data *data)
+{
+  struct loop *loop = data->current_loop;
+  basic_block *body = get_loop_body_in_dom_order (loop);
+  unsigned i;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    find_givs_in_bb (data, body[i]);
+  free (body);
+}
+
+/* For each ssa name defined in LOOP determines whether it is an induction
+   variable and if so, its initial value and step.  */
+
+static bool
+find_induction_variables (struct ivopts_data *data)
+{
+  unsigned i;
+  bitmap_iterator bi;
+
+  if (!find_bivs (data))
+    return false;
+
+  find_givs (data);
+  mark_bivs (data);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      tree niter = niter_for_single_dom_exit (data);
+
+      if (niter)
+	{
+	  fprintf (dump_file, "  number of iterations ");
+	  print_generic_expr (dump_file, niter, TDF_SLIM);
+	  fprintf (dump_file, "\n\n");
+    	};
+ 
+      fprintf (dump_file, "Induction variables:\n\n");
+
+      EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
+	{
+	  if (ver_info (data, i)->iv)
+	    dump_iv (dump_file, ver_info (data, i)->iv);
+	}
+    }
+
+  return true;
+}
+
+/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
+
+static struct iv_use *
+record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
+	    gimple stmt, enum use_type use_type)
+{
+  struct iv_use *use = XCNEW (struct iv_use);
+
+  use->id = n_iv_uses (data);
+  use->type = use_type;
+  use->iv = iv;
+  use->stmt = stmt;
+  use->op_p = use_p;
+  use->related_cands = BITMAP_ALLOC (NULL);
+  use->use_pos = IU_UNKNOWN;
+
+  /* To avoid showing ssa name in the dumps, if it was not reset by the
+     caller.  */
+  iv->ssa_name = NULL_TREE;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_use (dump_file, use);
+
+  VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
+
+  return use;
+}
+
+/* Checks whether OP is a loop-level invariant and if so, records it.
+   NONLINEAR_USE is true if the invariant is used in a way we do not
+   handle specially.  */
+
+static void
+record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
+{
+  basic_block bb;
+  struct version_info *info;
+
+  if (TREE_CODE (op) != SSA_NAME
+      || !is_gimple_reg (op))
+    return;
+
+  bb = gimple_bb (SSA_NAME_DEF_STMT (op));
+  if (bb
+      && flow_bb_inside_loop_p (data->current_loop, bb))
+    return;
+
+  info = name_info (data, op);
+  info->name = op;
+  info->has_nonlin_use |= nonlinear_use;
+  if (!info->inv_id)
+    info->inv_id = ++data->max_inv_id;
+  bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
+}
+
+/* Records a pseudo invariant and returns its VERSION_INFO.  */
+
+static struct version_info *
+record_pseudo_invariant (struct ivopts_data *data)
+{
+  struct version_info *info;
+
+  info = XCNEW (struct version_info);
+  info->name = NULL;
+  VEC_safe_push (version_info_p, heap, data->pseudo_version_info, info);
+  if (VEC_length (version_info_p, data->pseudo_version_info))
+    info->inv_id
+        = VEC_length (version_info_p, data->pseudo_version_info) - 1
+        + data->min_pseudo_inv_id;
+  else
+    info->inv_id = data->max_inv_id + 1;
+
+  return info;
+}
+
+/* Checks whether the use OP is interesting and if so, records it.
+   USE_POS indicates where the use comes from.  */
+
+static struct iv_use *
+find_interesting_uses_op (struct ivopts_data *data, tree op, enum iv_use_pos use_pos)
+{
+  struct iv *iv;
+  struct iv *civ;
+  gimple stmt;
+  struct iv_use *use;
+
+  if (TREE_CODE (op) != SSA_NAME)
+    return NULL;
+
+  iv = get_iv (data, op);
+  if (!iv)
+    return NULL;
+  
+  if (iv->have_use_for)
+    {
+      use = iv_use (data, iv->use_id);
+
+      gcc_assert (use->type == USE_NONLINEAR_EXPR);
+      gcc_assert (use->use_pos != IU_UNKNOWN);
+
+      if (use->use_pos == IU_OUTSIDE_LOOP_ONLY)
+        use->use_pos = use_pos;
+      return use;
+    }
+
+  if (integer_zerop (iv->step))
+    {
+      record_invariant (data, op, true);
+      return NULL;
+    }
+  iv->have_use_for = true;
+
+  civ = XNEW (struct iv);
+  *civ = *iv;
+
+  stmt = SSA_NAME_DEF_STMT (op);
+  gcc_assert (gimple_code (stmt) == GIMPLE_PHI
+	      || is_gimple_assign (stmt));
+
+  use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
+  iv->use_id = use->id;
+  use->use_pos = use_pos;
+
+  return use;
+}
+
+/* Given a condition in statement STMT, checks whether it is a compare
+   of an induction variable and an invariant.  If this is the case,
+   CONTROL_VAR is set to location of the iv, BOUND to the location of
+   the invariant, IV_VAR and IV_BOUND are set to the corresponding
+   induction variable descriptions, and true is returned.  If this is not
+   the case, CONTROL_VAR and BOUND are set to the arguments of the
+   condition and false is returned.  */
+
+static bool
+extract_cond_operands (struct ivopts_data *data, gimple stmt,
+		       tree **control_var, tree **bound,
+		       struct iv **iv_var, struct iv **iv_bound)
+{
+  /* The objects returned when COND has constant operands.  */
+  static struct iv const_iv;
+  static tree zero;
+  tree *op0 = &zero, *op1 = &zero, *tmp_op;
+  struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+  bool ret = false;
+
+  if (gimple_code (stmt) == GIMPLE_COND)
+    {
+      op0 = gimple_cond_lhs_ptr (stmt);
+      op1 = gimple_cond_rhs_ptr (stmt);
+    }
+  else
+    {
+      op0 = gimple_assign_rhs1_ptr (stmt);
+      op1 = gimple_assign_rhs2_ptr (stmt);
+    }
+
+  zero = integer_zero_node;
+  const_iv.step = integer_zero_node;
+
+  if (TREE_CODE (*op0) == SSA_NAME)
+    iv0 = get_iv (data, *op0);
+  if (TREE_CODE (*op1) == SSA_NAME)
+    iv1 = get_iv (data, *op1);
+
+  /* Exactly one of the compared values must be an iv, and the other one must
+     be an invariant.  */
+  if (!iv0 || !iv1)
+    goto end;
+
+  if (integer_zerop (iv0->step))
+    {
+      /* Control variable may be on the other side.  */
+      tmp_op = op0; op0 = op1; op1 = tmp_op;
+      tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
+    }
+  ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
+
+end:
+  if (control_var)
+    *control_var = op0;;
+  if (iv_var)
+    *iv_var = iv0;;
+  if (bound)
+    *bound = op1;
+  if (iv_bound)
+    *iv_bound = iv1;
+
+  return ret;
+}
+
+/* Checks whether the condition in STMT is interesting and if so,
+   records it.  */
+
+static void
+find_interesting_uses_cond (struct ivopts_data *data, gimple stmt)
+{
+  tree *var_p, *bound_p;
+  struct iv *var_iv, *civ;
+  struct iv_use *use;
+
+  if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
+    {
+      find_interesting_uses_op (data, *var_p, IU_INSIDE_LOOP);
+      find_interesting_uses_op (data, *bound_p, IU_INSIDE_LOOP);
+      return;
+    }
+
+  civ = XNEW (struct iv);
+  *civ = *var_iv;
+  use = record_use (data, NULL, civ, stmt, USE_COMPARE);
+  use->use_pos = IU_INSIDE_LOOP;
+}
+
+/* Returns true if expression EXPR is obviously invariant in LOOP,
+   i.e. if all its operands are defined outside of the LOOP.  LOOP
+   should not be the function body.  */
+
+bool
+expr_invariant_in_loop_p (struct loop *loop, tree expr)
+{
+  basic_block def_bb;
+  unsigned i, len;
+
+  gcc_assert (loop_depth (loop) > 0);
+
+  if (is_gimple_min_invariant (expr))
+    return true;
+
+  if (TREE_CODE (expr) == SSA_NAME)
+    {
+      def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
+      if (def_bb
+	  && flow_bb_inside_loop_p (loop, def_bb))
+	return false;
+
+      return true;
+    }
+
+  if (!EXPR_P (expr))
+    return false;
+
+  len = TREE_OPERAND_LENGTH (expr);
+  for (i = 0; i < len; i++)
+    if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
+      return false;
+
+  return true;
+}
+
+/* Returns true if statement STMT is obviously invariant in LOOP,
+   i.e. if all its operands on the RHS are defined outside of the LOOP.
+   LOOP should not be the function body.  */
+
+bool
+stmt_invariant_in_loop_p (struct loop *loop, gimple stmt)
+{
+  unsigned i;
+  tree lhs;
+
+  gcc_assert (loop_depth (loop) > 0);
+
+  lhs = gimple_get_lhs (stmt);
+  for (i = 0; i < gimple_num_ops (stmt); i++)
+    {
+      tree op = gimple_op (stmt, i);
+      if (op != lhs && !expr_invariant_in_loop_p (loop, op))
+	return false;
+    }
+
+  return true;
+}
+
+/* Cumulates the steps of indices into DATA and replaces their values with the
+   initial ones.  Returns false when the value of the index cannot be determined.
+   Callback for for_each_index.  */
+
+struct ifs_ivopts_data
+{
+  struct ivopts_data *ivopts_data;
+  gimple stmt;
+  tree step;
+};
+
+static bool
+idx_find_step (tree base, tree *idx, void *data)
+{
+  struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
+  struct iv *iv;
+  tree step, iv_base, iv_step, lbound, off;
+  struct loop *loop = dta->ivopts_data->current_loop;
+
+  if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
+      || TREE_CODE (base) == ALIGN_INDIRECT_REF)
+    return false;
+
+  /* If base is a component ref, require that the offset of the reference
+     be invariant.  */
+  if (TREE_CODE (base) == COMPONENT_REF)
+    {
+      off = component_ref_field_offset (base);
+      return expr_invariant_in_loop_p (loop, off);
+    }
+
+  /* If base is array, first check whether we will be able to move the
+     reference out of the loop (in order to take its address in strength
+     reduction).  In order for this to work we need both lower bound
+     and step to be loop invariants.  */
+  if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
+    {
+      /* Moreover, for a range, the size needs to be invariant as well.  */
+      if (TREE_CODE (base) == ARRAY_RANGE_REF
+	  && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
+	return false;
+
+      step = array_ref_element_size (base);
+      lbound = array_ref_low_bound (base);
+
+      if (!expr_invariant_in_loop_p (loop, step)
+	  || !expr_invariant_in_loop_p (loop, lbound))
+	return false;
+    }
+
+  if (TREE_CODE (*idx) != SSA_NAME)
+    return true;
+
+  iv = get_iv (dta->ivopts_data, *idx);
+  if (!iv)
+    return false;
+
+  /* XXX  We produce for a base of *D42 with iv->base being &x[0]
+	  *&x[0], which is not folded and does not trigger the
+	  ARRAY_REF path below.  */
+  *idx = iv->base;
+
+  if (integer_zerop (iv->step))
+    return true;
+
+  if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
+    {
+      step = array_ref_element_size (base);
+
+      /* We only handle addresses whose step is an integer constant.  */
+      if (TREE_CODE (step) != INTEGER_CST)
+	return false;
+    }
+  else
+    /* The step for pointer arithmetics already is 1 byte.  */
+    step = build_int_cst (sizetype, 1);
+
+  iv_base = iv->base;
+  iv_step = iv->step;
+  if (!convert_affine_scev (dta->ivopts_data->current_loop,
+			    sizetype, &iv_base, &iv_step, dta->stmt,
+			    false))
+    {
+      /* The index might wrap.  */
+      return false;
+    }
+
+  step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
+  dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
+
+  return true;
+}
+
+/* Records use in index IDX.  Callback for for_each_index.  Ivopts data
+   object is passed to it in DATA.  */
+
+static bool
+idx_record_use (tree base, tree *idx,
+		void *vdata)
+{
+  struct ivopts_data *data = (struct ivopts_data *) vdata;
+  find_interesting_uses_op (data, *idx, IU_INSIDE_LOOP);
+  if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
+    {
+      find_interesting_uses_op (data, array_ref_element_size (base),
+                                IU_INSIDE_LOOP);
+      find_interesting_uses_op (data, array_ref_low_bound (base),
+                                IU_INSIDE_LOOP);
+    }
+  return true;
+}
+
+/* If we can prove that TOP = cst * BOT for some constant cst,
+   store cst to MUL and return true.  Otherwise return false.
+   The returned value is always sign-extended, regardless of the
+   signedness of TOP and BOT.  */
+
+static bool
+constant_multiple_of (tree top, tree bot, double_int *mul)
+{
+  tree mby;
+  enum tree_code code;
+  double_int res, p0, p1;
+  unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
+
+  STRIP_NOPS (top);
+  STRIP_NOPS (bot);
+
+  if (operand_equal_p (top, bot, 0))
+    {
+      *mul = double_int_one;
+      return true;
+    }
+
+  code = TREE_CODE (top);
+  switch (code)
+    {
+    case MULT_EXPR:
+      mby = TREE_OPERAND (top, 1);
+      if (TREE_CODE (mby) != INTEGER_CST)
+	return false;
+
+      if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
+	return false;
+
+      *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
+			      precision);
+      return true;
+
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
+	  || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
+	return false;
+
+      if (code == MINUS_EXPR)
+	p1 = double_int_neg (p1);
+      *mul = double_int_sext (double_int_add (p0, p1), precision);
+      return true;
+
+    case INTEGER_CST:
+      if (TREE_CODE (bot) != INTEGER_CST)
+	return false;
+
+      p0 = double_int_sext (tree_to_double_int (top), precision);
+      p1 = double_int_sext (tree_to_double_int (bot), precision);
+      if (double_int_zero_p (p1))
+	return false;
+      *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
+			      precision);
+      return double_int_zero_p (res);
+
+    default:
+      return false;
+    }
+}
+
+/* Returns true if memory reference REF with step STEP may be unaligned.  */
+
+static bool
+may_be_unaligned_p (tree ref, tree step)
+{
+  tree base;
+  tree base_type;
+  HOST_WIDE_INT bitsize;
+  HOST_WIDE_INT bitpos;
+  tree toffset;
+  enum machine_mode mode;
+  int unsignedp, volatilep;
+  unsigned base_align;
+
+  /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
+     thus they are not misaligned.  */
+  if (TREE_CODE (ref) == TARGET_MEM_REF)
+    return false;
+
+  /* The test below is basically copy of what expr.c:normal_inner_ref
+     does to check whether the object must be loaded by parts when
+     STRICT_ALIGNMENT is true.  */
+  base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
+			      &unsignedp, &volatilep, true);
+  base_type = TREE_TYPE (base);
+  base_align = TYPE_ALIGN (base_type);
+
+  if (mode != BLKmode)
+    {
+      double_int mul;
+      tree al = build_int_cst (TREE_TYPE (step),
+			       GET_MODE_ALIGNMENT (mode) / BITS_PER_UNIT);
+
+      if (base_align < GET_MODE_ALIGNMENT (mode)
+	  || bitpos % GET_MODE_ALIGNMENT (mode) != 0
+	  || bitpos % BITS_PER_UNIT != 0)
+	return true;
+    
+      if (!constant_multiple_of (step, al, &mul))
+	return true;
+    }
+
+  return false;
+}
+
+/* Return true if EXPR may be non-addressable.   */
+
+static bool
+may_be_nonaddressable_p (tree expr)
+{
+  switch (TREE_CODE (expr))
+    {
+    case TARGET_MEM_REF:
+      /* TARGET_MEM_REFs are translated directly to valid MEMs on the
+	 target, thus they are always addressable.  */
+      return false;
+
+    case COMPONENT_REF:
+      return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
+	     || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+    case VIEW_CONVERT_EXPR:
+      /* This kind of view-conversions may wrap non-addressable objects
+	 and make them look addressable.  After some processing the
+	 non-addressability may be uncovered again, causing ADDR_EXPRs
+	 of inappropriate objects to be built.  */
+      if (is_gimple_reg (TREE_OPERAND (expr, 0))
+	  || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
+	return true;
+
+      /* ... fall through ... */
+
+    case ARRAY_REF:
+    case ARRAY_RANGE_REF:
+      return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
+
+    CASE_CONVERT:
+      return true;
+
+    default:
+      break;
+    }
+
+  return false;
+}
+
+/* Finds addresses in *OP_P inside STMT.  */
+
+static bool
+find_interesting_uses_address (struct ivopts_data *data, gimple stmt, tree *op_p)
+{
+  tree base = *op_p, step = build_int_cst (sizetype, 0);
+  struct iv *civ;
+  struct ifs_ivopts_data ifs_ivopts_data;
+  struct iv_use *use;
+
+  /* Do not play with volatile memory references.  A bit too conservative,
+     perhaps, but safe.  */
+  if (gimple_has_volatile_ops (stmt))
+    goto fail;
+
+  /* Ignore bitfields for now.  Not really something terribly complicated
+     to handle.  TODO.  */
+  if (TREE_CODE (base) == BIT_FIELD_REF)
+    goto fail;
+
+  base = unshare_expr (base);
+
+  if (TREE_CODE (base) == TARGET_MEM_REF)
+    {
+      tree type = build_pointer_type (TREE_TYPE (base));
+      tree astep;
+
+      if (TMR_BASE (base)
+	  && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
+	{
+	  civ = get_iv (data, TMR_BASE (base));
+	  if (!civ)
+	    goto fail;
+
+	  TMR_BASE (base) = civ->base;
+	  step = civ->step;
+	}
+      if (TMR_INDEX (base)
+	  && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
+	{
+	  civ = get_iv (data, TMR_INDEX (base));
+	  if (!civ)
+	    goto fail;
+
+	  TMR_INDEX (base) = civ->base;
+	  astep = civ->step;
+
+	  if (astep)
+	    {
+	      if (TMR_STEP (base))
+		astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
+
+	      step = fold_build2 (PLUS_EXPR, type, step, astep);
+	    }
+	}
+
+      if (integer_zerop (step))
+	goto fail;
+      base = tree_mem_ref_addr (type, base);
+    }
+  else
+    {
+      ifs_ivopts_data.ivopts_data = data;
+      ifs_ivopts_data.stmt = stmt;
+      ifs_ivopts_data.step = build_int_cst (sizetype, 0);
+      if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
+	  || integer_zerop (ifs_ivopts_data.step))
+	goto fail;
+      step = ifs_ivopts_data.step;
+
+      gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
+      gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
+
+      /* Check that the base expression is addressable.  This needs
+	 to be done after substituting bases of IVs into it.  */
+      if (may_be_nonaddressable_p (base))
+	goto fail;
+
+      /* Moreover, on strict alignment platforms, check that it is
+	 sufficiently aligned.  */
+      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+	goto fail;
+
+      base = build_fold_addr_expr (base);
+
+      /* Substituting bases of IVs into the base expression might
+	 have caused folding opportunities.  */
+      if (TREE_CODE (base) == ADDR_EXPR)
+	{
+	  tree *ref = &TREE_OPERAND (base, 0);
+	  while (handled_component_p (*ref))
+	    ref = &TREE_OPERAND (*ref, 0);
+	  if (TREE_CODE (*ref) == INDIRECT_REF)
+	    *ref = fold_indirect_ref (*ref);
+	}
+    }
+
+  civ = alloc_iv (base, step);
+  use = record_use (data, op_p, civ, stmt, USE_ADDRESS);
+  use->use_pos = IU_INSIDE_LOOP;
+  return true;
+
+fail:
+  for_each_index (op_p, idx_record_use, data);
+  return false;
+}
+
+/* Finds and records invariants used in STMT.  */
+
+static void
+find_invariants_stmt (struct ivopts_data *data, gimple stmt)
+{
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  tree op;
+
+  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+    {
+      op = USE_FROM_PTR (use_p);
+      record_invariant (data, op, false);
+    }
+}
+
+/* Finds interesting uses of induction variables in the statement STMT.  */
+
+static void
+find_interesting_uses_stmt (struct ivopts_data *data, gimple stmt)
+{
+  struct iv *iv;
+  tree op, *lhs, *rhs;
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  enum tree_code code;
+
+  find_invariants_stmt (data, stmt);
+
+  if (gimple_code (stmt) == GIMPLE_COND)
+    {
+      find_interesting_uses_cond (data, stmt);
+      return;
+    }
+
+  if (is_gimple_assign (stmt))
+    {
+      lhs = gimple_assign_lhs_ptr (stmt);
+      rhs = gimple_assign_rhs1_ptr (stmt);
+
+      if (TREE_CODE (*lhs) == SSA_NAME)
+	{
+	  /* If the statement defines an induction variable, the uses are not
+	     interesting by themselves.  */
+
+	  iv = get_iv (data, *lhs);
+
+	  if (iv && !integer_zerop (iv->step))
+	    return;
+	}
+
+      code = gimple_assign_rhs_code (stmt);
+      if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+	  && (REFERENCE_CLASS_P (*rhs)
+	      || is_gimple_val (*rhs)))
+	{
+	  if (REFERENCE_CLASS_P (*rhs))
+	    find_interesting_uses_address (data, stmt, rhs);
+	  else
+	    find_interesting_uses_op (data, *rhs, IU_INSIDE_LOOP);
+
+	  if (REFERENCE_CLASS_P (*lhs))
+	    find_interesting_uses_address (data, stmt, lhs);
+	  return;
+	}
+      else if (TREE_CODE_CLASS (code) == tcc_comparison)
+	{
+	  find_interesting_uses_cond (data, stmt);
+	  return;
+	}
+
+      /* TODO -- we should also handle address uses of type
+
+	 memory = call (whatever);
+
+	 and
+
+	 call (memory).  */
+    }
+
+  if (gimple_code (stmt) == GIMPLE_PHI
+      && gimple_bb (stmt) == data->current_loop->header)
+    {
+      iv = get_iv (data, PHI_RESULT (stmt));
+
+      if (iv && !integer_zerop (iv->step))
+	return;
+    }
+
+  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+    {
+      op = USE_FROM_PTR (use_p);
+
+      if (TREE_CODE (op) != SSA_NAME)
+	continue;
+
+      iv = get_iv (data, op);
+      if (!iv)
+	continue;
+
+      find_interesting_uses_op (data, op, IU_INSIDE_LOOP);
+    }
+}
+
+/* Finds interesting uses of induction variables outside of loops
+   on loop exit edge EXIT.  */
+
+static void
+find_interesting_uses_outside (struct ivopts_data *data, edge exit)
+{
+  gimple phi;
+  gimple_stmt_iterator psi;
+  tree def;
+
+  for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      phi = gsi_stmt (psi);
+      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+      if (is_gimple_reg (def))
+        {
+          if (gimple_phi_num_args (phi) == 1)
+            find_interesting_uses_op (data, def, IU_OUTSIDE_LOOP_ONLY);
+          else
+            find_interesting_uses_op (data, def, IU_INSIDE_LOOP);
+        }
+    }
+}
+
+/* Finds uses of the induction variables that are interesting.  */
+
+static void
+find_interesting_uses (struct ivopts_data *data)
+{
+  basic_block bb;
+  gimple_stmt_iterator bsi;
+  basic_block *body = get_loop_body (data->current_loop);
+  unsigned i;
+  struct version_info *info;
+  edge e;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Uses:\n\n");
+
+  for (i = 0; i < data->current_loop->num_nodes; i++)
+    {
+      edge_iterator ei;
+      bb = body[i];
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (e->dest != EXIT_BLOCK_PTR
+	    && !flow_bb_inside_loop_p (data->current_loop, e->dest))
+	  find_interesting_uses_outside (data, e);
+
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	find_interesting_uses_stmt (data, gsi_stmt (bsi));
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	find_interesting_uses_stmt (data, gsi_stmt (bsi));
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      bitmap_iterator bi;
+
+      fprintf (dump_file, "\n");
+
+      EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
+	{
+	  info = ver_info (data, i);
+	  if (info->inv_id)
+	    {
+	      fprintf (dump_file, "  ");
+	      print_generic_expr (dump_file, info->name, TDF_SLIM);
+	      fprintf (dump_file, " is invariant (%d)%s\n",
+		       info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
+	    }
+	}
+
+      fprintf (dump_file, "\n");
+    }
+
+  free (body);
+}
+
+/* Strips constant offsets from EXPR and stores them to OFFSET.  If INSIDE_ADDR
+   is true, assume we are inside an address.  If TOP_COMPREF is true, assume
+   we are at the top-level of the processed address.  */
+
+static tree
+strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
+		unsigned HOST_WIDE_INT *offset)
+{
+  tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
+  enum tree_code code;
+  tree type, orig_type = TREE_TYPE (expr);
+  unsigned HOST_WIDE_INT off0, off1, st;
+  tree orig_expr = expr;
+
+  STRIP_NOPS (expr);
+
+  type = TREE_TYPE (expr);
+  code = TREE_CODE (expr);
+  *offset = 0;
+
+  switch (code)
+    {
+    case INTEGER_CST:
+      if (!cst_and_fits_in_hwi (expr)
+	  || integer_zerop (expr))
+	return orig_expr;
+
+      *offset = int_cst_value (expr);
+      return build_int_cst (orig_type, 0);
+
+    case POINTER_PLUS_EXPR:
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      op0 = TREE_OPERAND (expr, 0);
+      op1 = TREE_OPERAND (expr, 1);
+
+      op0 = strip_offset_1 (op0, false, false, &off0);
+      op1 = strip_offset_1 (op1, false, false, &off1);
+
+      *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
+      if (op0 == TREE_OPERAND (expr, 0)
+	  && op1 == TREE_OPERAND (expr, 1))
+	return orig_expr;
+
+      if (integer_zerop (op1))
+	expr = op0;
+      else if (integer_zerop (op0))
+	{
+	  if (code == MINUS_EXPR)
+	    expr = fold_build1 (NEGATE_EXPR, type, op1);
+	  else
+	    expr = op1;
+	}
+      else
+	expr = fold_build2 (code, type, op0, op1);
+
+      return fold_convert (orig_type, expr);
+
+    case ARRAY_REF:
+    case ARRAY_RANGE_REF:
+      if (!inside_addr)
+	return orig_expr;
+
+      step = array_ref_element_size (expr);
+      if (!cst_and_fits_in_hwi (step))
+	break;
+
+      st = int_cst_value (step);
+      op1 = TREE_OPERAND (expr, 1);
+      op1 = strip_offset_1 (op1, false, false, &off1);
+      *offset = off1 * st;
+
+      if (top_compref
+	  && integer_zerop (op1))
+	{
+	  /* Strip the component reference completely.  */
+	  op0 = TREE_OPERAND (expr, 0);
+	  op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
+	  *offset += off0;
+	  return op0;
+	}
+      break;
+
+    case COMPONENT_REF:
+      if (!inside_addr)
+	return orig_expr;
+
+      tmp = component_ref_field_offset (expr);
+      if (top_compref
+	  && cst_and_fits_in_hwi (tmp))
+	{
+	  /* Strip the component reference completely.  */
+	  op0 = TREE_OPERAND (expr, 0);
+	  op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
+	  *offset = off0 + int_cst_value (tmp);
+	  return op0;
+	}
+      break;
+
+    case ADDR_EXPR:
+      op0 = TREE_OPERAND (expr, 0);
+      op0 = strip_offset_1 (op0, true, true, &off0);
+      *offset += off0;
+
+      if (op0 == TREE_OPERAND (expr, 0))
+	return orig_expr;
+
+      expr = build_fold_addr_expr (op0);
+      return fold_convert (orig_type, expr);
+
+    case INDIRECT_REF:
+      inside_addr = false;
+      break;
+
+    default:
+      return orig_expr;
+    }
+
+  /* Default handling of expressions for that we want to recurse into
+     the first operand.  */
+  op0 = TREE_OPERAND (expr, 0);
+  op0 = strip_offset_1 (op0, inside_addr, false, &off0);
+  *offset += off0;
+
+  if (op0 == TREE_OPERAND (expr, 0)
+      && (!op1 || op1 == TREE_OPERAND (expr, 1)))
+    return orig_expr;
+
+  expr = copy_node (expr);
+  TREE_OPERAND (expr, 0) = op0;
+  if (op1)
+    TREE_OPERAND (expr, 1) = op1;
+
+  /* Inside address, we might strip the top level component references,
+     thus changing type of the expression.  Handling of ADDR_EXPR
+     will fix that.  */
+  expr = fold_convert (orig_type, expr);
+
+  return expr;
+}
+
+/* Strips constant offsets from EXPR and stores them to OFFSET.  */
+
+static tree
+strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
+{
+  return strip_offset_1 (expr, false, false, offset);
+}
+
+/* Returns variant of TYPE that can be used as base for different uses.
+   We return unsigned type with the same precision, which avoids problems
+   with overflows.  */
+
+static tree
+generic_type_for (tree type)
+{
+  if (POINTER_TYPE_P (type))
+    return unsigned_type_for (type);
+
+  if (TYPE_UNSIGNED (type))
+    return type;
+
+  return unsigned_type_for (type);
+}
+
+/* Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
+   the bitmap to that we should store it.  */
+
+static struct ivopts_data *fd_ivopts_data;
+static tree
+find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
+{
+  bitmap *depends_on = (bitmap *) data;
+  struct version_info *info;
+
+  if (TREE_CODE (*expr_p) != SSA_NAME)
+    return NULL_TREE;
+  info = name_info (fd_ivopts_data, *expr_p);
+
+  if (!info->inv_id || info->has_nonlin_use)
+    return NULL_TREE;
+
+  if (!*depends_on)
+    *depends_on = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (*depends_on, info->inv_id);
+
+  return NULL_TREE;
+}
+
+/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
+   position to POS.  If USE is not NULL, the candidate is set as related to
+   it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
+   replacement of the final value of the iv by a direct computation.  */
+
+static struct iv_cand *
+add_candidate_1 (struct ivopts_data *data,
+		 tree base, tree step, bool important, enum iv_position pos,
+		 struct iv_use *use, gimple incremented_at)
+{
+  unsigned i;
+  struct iv_cand *cand = NULL;
+  tree type, orig_type;
+  
+  if (base)
+    {
+      orig_type = TREE_TYPE (base);
+      type = generic_type_for (orig_type);
+      if (type != orig_type)
+	{
+	  base = fold_convert (type, base);
+	  step = fold_convert (type, step);
+	}
+    }
+
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      cand = iv_cand (data, i);
+
+      if (cand->pos != pos)
+	continue;
+
+      if (cand->incremented_at != incremented_at)
+	continue;
+
+      if (!cand->iv)
+	{
+	  if (!base && !step)
+	    break;
+
+	  continue;
+	}
+
+      if (!base && !step)
+	continue;
+
+      if (operand_equal_p (base, cand->iv->base, 0)
+	  && operand_equal_p (step, cand->iv->step, 0)
+          && (TYPE_PRECISION (TREE_TYPE (base))
+              == TYPE_PRECISION (TREE_TYPE (cand->iv->base))))
+	break;
+    }
+
+  if (i == n_iv_cands (data))
+    {
+      cand = XCNEW (struct iv_cand);
+      cand->id = i;
+
+      if (!base && !step)
+	cand->iv = NULL;
+      else
+	cand->iv = alloc_iv (base, step);
+
+      cand->pos = pos;
+      if (pos != IP_ORIGINAL && cand->iv)
+	{
+	  cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
+	  cand->var_after = cand->var_before;
+	}
+      cand->important = important;
+      cand->incremented_at = incremented_at;
+      VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
+
+      if (step
+	  && TREE_CODE (step) != INTEGER_CST)
+	{
+	  fd_ivopts_data = data;
+	  walk_tree (&step, find_depends, &cand->depends_on, NULL);
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	dump_cand (dump_file, cand);
+    }
+
+  if (important && !cand->important)
+    {
+      cand->important = true;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Candidate %d is important\n", cand->id);
+    }
+
+  if (use)
+    {
+      bitmap_set_bit (use->related_cands, i);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Candidate %d is related to use %d\n",
+		 cand->id, use->id);
+    }
+
+  return cand;
+}
+
+/* Returns true if incrementing the induction variable at the end of the LOOP
+   is allowed.
+
+   The purpose is to avoid splitting latch edge with a biv increment, thus
+   creating a jump, possibly confusing other optimization passes and leaving
+   less freedom to scheduler.  So we allow IP_END_POS only if IP_NORMAL_POS
+   is not available (so we do not have a better alternative), or if the latch
+   edge is already nonempty.  */
+
+static bool
+allow_ip_end_pos_p (struct loop *loop)
+{
+  if (!ip_normal_pos (loop))
+    return true;
+
+  if (!empty_block_p (ip_end_pos (loop)))
+    return true;
+
+  return false;
+}
+
+/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
+   position to POS.  If USE is not NULL, the candidate is set as related to
+   it.  The candidate computation is scheduled on all available positions.  */
+
+static void
+add_candidate (struct ivopts_data *data, 
+	       tree base, tree step, bool important, struct iv_use *use)
+{
+  if (ip_normal_pos (data->current_loop))
+    add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
+  if (ip_end_pos (data->current_loop)
+      && allow_ip_end_pos_p (data->current_loop))
+    add_candidate_1 (data, base, step, important, IP_END, use, NULL);
+}
+
+/* Add a standard "0 + 1 * iteration" iv candidate for a
+   type with SIZE bits.  */
+
+static void
+add_standard_iv_candidates_for_size (struct ivopts_data *data,
+				     unsigned int size)
+{
+  tree type = lang_hooks.types.type_for_size (size, true);
+  add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
+		 true, NULL);
+}
+
+/* Adds standard iv candidates.  */
+
+static void
+add_standard_iv_candidates (struct ivopts_data *data)
+{
+  add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
+
+  /* The same for a double-integer type if it is still fast enough.  */
+  if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
+    add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
+}
+
+
+/* Adds candidates bases on the old induction variable IV.  */
+
+static void
+add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
+{
+  gimple phi;
+  tree def;
+  struct iv_cand *cand;
+
+  add_candidate (data, iv->base, iv->step, true, NULL);
+
+  /* The same, but with initial value zero.  */
+  if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
+    add_candidate (data, size_int (0), iv->step, true, NULL);
+  else
+    add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+		   iv->step, true, NULL);
+
+  phi = SSA_NAME_DEF_STMT (iv->ssa_name);
+  if (gimple_code (phi) == GIMPLE_PHI)
+    {
+      /* Additionally record the possibility of leaving the original iv
+	 untouched.  */
+      def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
+      cand = add_candidate_1 (data,
+			      iv->base, iv->step, true, IP_ORIGINAL, NULL,
+			      SSA_NAME_DEF_STMT (def));
+      cand->var_before = iv->ssa_name;
+      cand->var_after = def;
+    }
+}
+
+/* Adds candidates based on the old induction variables.  */
+
+static void
+add_old_ivs_candidates (struct ivopts_data *data)
+{
+  unsigned i;
+  struct iv *iv;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
+    {
+      iv = ver_info (data, i)->iv;
+      if (iv && iv->biv_p && !integer_zerop (iv->step))
+	add_old_iv_candidates (data, iv);
+    }
+}
+
+/* Adds candidates based on the value of the induction variable IV and USE.  */
+
+static void
+add_iv_value_candidates (struct ivopts_data *data,
+			 struct iv *iv, struct iv_use *use)
+{
+  unsigned HOST_WIDE_INT offset;
+  tree base;
+  tree basetype;
+
+  add_candidate (data, iv->base, iv->step, false, use);
+
+  /* The same, but with initial value zero.  Make such variable important,
+     since it is generic enough so that possibly many uses may be based
+     on it.  */
+  basetype = TREE_TYPE (iv->base);
+  if (POINTER_TYPE_P (basetype))
+    basetype = sizetype;
+  add_candidate (data, build_int_cst (basetype, 0),
+		 iv->step, true, use);
+
+  /* Third, try removing the constant offset.  Make sure to even
+     add a candidate for &a[0] vs. (T *)&a.  */
+  base = strip_offset (iv->base, &offset);
+  if (offset
+      || base != iv->base)
+    add_candidate (data, base, iv->step, false, use);
+}
+
+/* Adds candidates based on the uses.  */
+
+static void
+add_derived_ivs_candidates (struct ivopts_data *data)
+{
+  unsigned i;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      struct iv_use *use = iv_use (data, i);
+
+      if (!use)
+	continue;
+
+      switch (use->type)
+	{
+	case USE_NONLINEAR_EXPR:
+	case USE_COMPARE:
+	case USE_ADDRESS:
+	  /* Just add the ivs based on the value of the iv used here.  */
+	  add_iv_value_candidates (data, use->iv, use);
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+/* Record important candidates and add them to related_cands bitmaps
+   if needed.  */
+
+static void
+record_important_candidates (struct ivopts_data *data)
+{
+  unsigned i;
+  struct iv_use *use;
+
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      struct iv_cand *cand = iv_cand (data, i);
+
+      if (cand->important)
+	bitmap_set_bit (data->important_candidates, i);
+    }
+
+  data->consider_all_candidates = (n_iv_cands (data)
+				   <= CONSIDER_ALL_CANDIDATES_BOUND);
+
+  if (data->consider_all_candidates)
+    {
+      /* We will not need "related_cands" bitmaps in this case,
+	 so release them to decrease peak memory consumption.  */
+      for (i = 0; i < n_iv_uses (data); i++)
+	{
+	  use = iv_use (data, i);
+	  BITMAP_FREE (use->related_cands);
+	}
+    }
+  else
+    {
+      /* Add important candidates to the related_cands bitmaps.  */
+      for (i = 0; i < n_iv_uses (data); i++)
+	bitmap_ior_into (iv_use (data, i)->related_cands,
+			 data->important_candidates);
+    }
+}
+
+/* Finds the candidates for the induction variables.  */
+
+static void
+find_iv_candidates (struct ivopts_data *data)
+{
+  /* Add commonly used ivs.  */
+  add_standard_iv_candidates (data);
+
+  /* Add old induction variables.  */
+  add_old_ivs_candidates (data);
+
+  /* Add induction variables derived from uses.  */
+  add_derived_ivs_candidates (data);
+
+  /* Record the important candidates.  */
+  record_important_candidates (data);
+}
+
+/* Allocates the data structure mapping the (use, candidate) pairs to costs.
+   If consider_all_candidates is true, we use a two-dimensional array, otherwise
+   we allocate a simple list to every use.  */
+
+static void
+alloc_use_cost_map (struct ivopts_data *data)
+{
+  unsigned i, size, s, j;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      struct iv_use *use = iv_use (data, i);
+      bitmap_iterator bi;
+
+      if (data->consider_all_candidates)
+	size = n_iv_cands (data);
+      else
+	{
+	  s = 0;
+	  EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
+	    {
+	      s++;
+	    }
+
+	  /* Round up to the power of two, so that moduling by it is fast.  */
+	  for (size = 1; size < s; size <<= 1)
+	    continue;
+	}
+
+      use->n_map_members = size;
+      use->cost_map = XCNEWVEC (struct cost_pair, size);
+    }
+}
+
+/* Returns description of computation cost of expression whose runtime
+   cost is RUNTIME and complexity corresponds to COMPLEXITY.  */
+
+static comp_cost
+new_cost (unsigned runtime, unsigned complexity)
+{
+  comp_cost cost;
+
+  cost.cost = runtime;
+  cost.complexity = complexity;
+
+  return cost;
+}
+
+/* Adds costs COST1 and COST2.  */
+
+static comp_cost
+add_costs (comp_cost cost1, comp_cost cost2)
+{
+  cost1.cost += cost2.cost;
+  cost1.complexity += cost2.complexity;
+
+  return cost1;
+}
+/* Subtracts costs COST1 and COST2.  */
+
+static comp_cost
+sub_costs (comp_cost cost1, comp_cost cost2)
+{
+  cost1.cost -= cost2.cost;
+  cost1.complexity -= cost2.complexity;
+
+  return cost1;
+}
+
+/* Returns a negative number if COST1 < COST2, a positive number if
+   COST1 > COST2, and 0 if COST1 = COST2.  */
+
+static int
+compare_costs (comp_cost cost1, comp_cost cost2)
+{
+  if (cost1.cost == cost2.cost)
+    return cost1.complexity - cost2.complexity;
+
+  return cost1.cost - cost2.cost;
+}
+
+/* Returns true if COST is infinite.  */
+
+static bool
+infinite_cost_p (comp_cost cost)
+{
+  return cost.cost == INFTY;
+}
+
+/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
+   on invariants DEPENDS_ON and that the value used in expressing it
+   is VALUE.*/
+
+static void
+set_use_iv_cost (struct ivopts_data *data,
+		 struct iv_use *use, struct iv_cand *cand,
+		 comp_cost cost, bitmap depends_on, tree value)
+{
+  unsigned i, s;
+
+  if (infinite_cost_p (cost))
+    {
+      BITMAP_FREE (depends_on);
+      return;
+    }
+
+  if (data->consider_all_candidates)
+    {
+      use->cost_map[cand->id].cand = cand;
+      use->cost_map[cand->id].cost = cost;
+      use->cost_map[cand->id].depends_on = depends_on;
+      use->cost_map[cand->id].value = value;
+      return;
+    }
+
+  /* n_map_members is a power of two, so this computes modulo.  */
+  s = cand->id & (use->n_map_members - 1);
+  for (i = s; i < use->n_map_members; i++)
+    if (!use->cost_map[i].cand)
+      goto found;
+  for (i = 0; i < s; i++)
+    if (!use->cost_map[i].cand)
+      goto found;
+
+  gcc_unreachable ();
+
+found:
+  use->cost_map[i].cand = cand;
+  use->cost_map[i].cost = cost;
+  use->cost_map[i].depends_on = depends_on;
+  use->cost_map[i].value = value;
+}
+
+/* Gets cost of (USE, CANDIDATE) pair.  */
+
+static struct cost_pair *
+get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
+		 struct iv_cand *cand)
+{
+  unsigned i, s;
+  struct cost_pair *ret;
+
+  if (!cand)
+    return NULL;
+
+  if (data->consider_all_candidates)
+    {
+      ret = use->cost_map + cand->id;
+      if (!ret->cand)
+	return NULL;
+
+      return ret;
+    }
+      
+  /* n_map_members is a power of two, so this computes modulo.  */
+  s = cand->id & (use->n_map_members - 1);
+  for (i = s; i < use->n_map_members; i++)
+    if (use->cost_map[i].cand == cand)
+      return use->cost_map + i;
+
+  for (i = 0; i < s; i++)
+    if (use->cost_map[i].cand == cand)
+      return use->cost_map + i;
+
+  return NULL;
+}
+
+/* Returns estimate on cost of computing SEQ.  */
+
+static unsigned
+seq_cost (rtx seq, bool speed)
+{
+  unsigned cost = 0;
+  rtx set;
+
+  for (; seq; seq = NEXT_INSN (seq))
+    {
+      set = single_set (seq);
+      if (set)
+	cost += rtx_cost (set, SET,speed);
+      else
+	cost++;
+    }
+
+  return cost;
+}
+
+/* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
+static rtx
+produce_memory_decl_rtl (tree obj, int *regno)
+{
+  rtx x;
+  
+  gcc_assert (obj);
+  if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
+    {
+      const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
+      x = gen_rtx_SYMBOL_REF (Pmode, name);
+      SET_SYMBOL_REF_DECL (x, obj);
+      x = gen_rtx_MEM (DECL_MODE (obj), x);
+      targetm.encode_section_info (obj, x, true);
+    }
+  else
+    {
+      x = gen_raw_REG (Pmode, (*regno)++);
+      x = gen_rtx_MEM (DECL_MODE (obj), x);
+    }
+
+  return x;
+}
+
+/* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
+   walk_tree.  DATA contains the actual fake register number.  */
+
+static tree
+prepare_decl_rtl (tree *expr_p, int *ws, void *data)
+{
+  tree obj = NULL_TREE;
+  rtx x = NULL_RTX;
+  int *regno = (int *) data;
+
+  switch (TREE_CODE (*expr_p))
+    {
+    case ADDR_EXPR:
+      for (expr_p = &TREE_OPERAND (*expr_p, 0);
+	   handled_component_p (*expr_p);
+	   expr_p = &TREE_OPERAND (*expr_p, 0))
+	continue;
+      obj = *expr_p;
+      if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
+        x = produce_memory_decl_rtl (obj, regno);
+      break;
+
+    case SSA_NAME:
+      *ws = 0;
+      obj = SSA_NAME_VAR (*expr_p);
+      if (!DECL_RTL_SET_P (obj))
+	x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
+      break;
+
+    case VAR_DECL:
+    case PARM_DECL:
+    case RESULT_DECL:
+      *ws = 0;
+      obj = *expr_p;
+
+      if (DECL_RTL_SET_P (obj))
+	break;
+
+      if (DECL_MODE (obj) == BLKmode)
+	x = produce_memory_decl_rtl (obj, regno);
+      else
+	x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
+
+      break;
+
+    default:
+      break;
+    }
+
+  if (x)
+    {
+      VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
+      SET_DECL_RTL (obj, x);
+    }
+
+  return NULL_TREE;
+}
+
+/* Determines cost of the computation of EXPR.  */
+
+static unsigned
+computation_cost (tree expr, bool speed)
+{
+  rtx seq, rslt;
+  tree type = TREE_TYPE (expr);
+  unsigned cost;
+  /* Avoid using hard regs in ways which may be unsupported.  */
+  int regno = LAST_VIRTUAL_REGISTER + 1;
+  enum function_frequency real_frequency = cfun->function_frequency;
+
+  cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
+  crtl->maybe_hot_insn_p = speed;
+  walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
+  start_sequence ();
+  rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
+  seq = get_insns ();
+  end_sequence ();
+  default_rtl_profile ();
+  cfun->function_frequency = real_frequency;
+
+  cost = seq_cost (seq, speed);
+  if (MEM_P (rslt))
+    cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type), speed);
+
+  return cost;
+}
+
+/* Returns variable containing the value of candidate CAND at statement AT.  */
+
+static tree
+var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple stmt)
+{
+  if (stmt_after_increment (loop, cand, stmt))
+    return cand->var_after;
+  else
+    return cand->var_before;
+}
+
+/* Return the most significant (sign) bit of T.  Similar to tree_int_cst_msb,
+   but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE.  */
+
+int
+tree_int_cst_sign_bit (const_tree t)
+{
+  unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
+  unsigned HOST_WIDE_INT w;
+
+  if (bitno < HOST_BITS_PER_WIDE_INT)
+    w = TREE_INT_CST_LOW (t);
+  else
+    {
+      w = TREE_INT_CST_HIGH (t);
+      bitno -= HOST_BITS_PER_WIDE_INT;
+    }
+
+  return (w >> bitno) & 1;
+}
+
+/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
+   same precision that is at least as wide as the precision of TYPE, stores
+   BA to A and BB to B, and returns the type of BA.  Otherwise, returns the
+   type of A and B.  */
+
+static tree
+determine_common_wider_type (tree *a, tree *b)
+{
+  tree wider_type = NULL;
+  tree suba, subb;
+  tree atype = TREE_TYPE (*a);
+
+  if (CONVERT_EXPR_P (*a))
+    {
+      suba = TREE_OPERAND (*a, 0);
+      wider_type = TREE_TYPE (suba);
+      if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
+	return atype;
+    }
+  else
+    return atype;
+
+  if (CONVERT_EXPR_P (*b))
+    {
+      subb = TREE_OPERAND (*b, 0);
+      if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
+	return atype;
+    }
+  else
+    return atype;
+
+  *a = suba;
+  *b = subb;
+  return wider_type;
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+   CAND at statement AT in LOOP.  The expression is stored in a decomposed
+   form into AFF.  Returns false if USE cannot be expressed using CAND.  */
+
+static bool
+get_computation_aff (struct loop *loop,
+		     struct iv_use *use, struct iv_cand *cand, gimple at,
+		     struct affine_tree_combination *aff)
+{
+  tree ubase = use->iv->base;
+  tree ustep = use->iv->step;
+  tree cbase = cand->iv->base;
+  tree cstep = cand->iv->step, cstep_common;
+  tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
+  tree common_type, var;
+  tree uutype;
+  aff_tree cbase_aff, var_aff;
+  double_int rat;
+
+  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
+    {
+      /* We do not have a precision to express the values of use.  */
+      return false;
+    }
+
+  var = var_at_stmt (loop, cand, at);
+  uutype = unsigned_type_for (utype);
+
+  /* If the conversion is not noop, perform it.  */
+  if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
+    {
+      cstep = fold_convert (uutype, cstep);
+      cbase = fold_convert (uutype, cbase);
+      var = fold_convert (uutype, var);
+    }
+
+  if (!constant_multiple_of (ustep, cstep, &rat))
+    return false;
+
+  /* In case both UBASE and CBASE are shortened to UUTYPE from some common
+     type, we achieve better folding by computing their difference in this
+     wider type, and cast the result to UUTYPE.  We do not need to worry about
+     overflows, as all the arithmetics will in the end be performed in UUTYPE
+     anyway.  */
+  common_type = determine_common_wider_type (&ubase, &cbase);
+
+  /* use = ubase - ratio * cbase + ratio * var.  */
+  tree_to_aff_combination (ubase, common_type, aff);
+  tree_to_aff_combination (cbase, common_type, &cbase_aff);
+  tree_to_aff_combination (var, uutype, &var_aff);
+
+  /* We need to shift the value if we are after the increment.  */
+  if (stmt_after_increment (loop, cand, at))
+    {
+      aff_tree cstep_aff;
+  
+      if (common_type != uutype)
+	cstep_common = fold_convert (common_type, cstep);
+      else
+	cstep_common = cstep;
+
+      tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
+      aff_combination_add (&cbase_aff, &cstep_aff);
+    }
+
+  aff_combination_scale (&cbase_aff, double_int_neg (rat));
+  aff_combination_add (aff, &cbase_aff);
+  if (common_type != uutype)
+    aff_combination_convert (aff, uutype);
+
+  aff_combination_scale (&var_aff, rat);
+  aff_combination_add (aff, &var_aff);
+
+  return true;
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+   CAND at statement AT in LOOP.  The computation is unshared.  */
+
+static tree
+get_computation_at (struct loop *loop,
+		    struct iv_use *use, struct iv_cand *cand, gimple at)
+{
+  aff_tree aff;
+  tree type = TREE_TYPE (use->iv->base);
+
+  if (!get_computation_aff (loop, use, cand, at, &aff))
+    return NULL_TREE;
+  unshare_aff_combination (&aff);
+  return fold_convert (type, aff_combination_to_tree (&aff));
+}
+
+/* Determines the expression by that USE is expressed from induction variable
+   CAND in LOOP.  The computation is unshared.  */
+
+static tree
+get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
+{
+  return get_computation_at (loop, use, cand, use->stmt);
+}
+
+/* Returns cost of addition in MODE.  */
+
+static unsigned
+add_cost (enum machine_mode mode, bool speed)
+{
+  static unsigned costs[NUM_MACHINE_MODES];
+  rtx seq;
+  unsigned cost;
+
+  if (costs[mode])
+    return costs[mode];
+
+  start_sequence ();
+  force_operand (gen_rtx_fmt_ee (PLUS, mode,
+				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
+		 NULL_RTX);
+  seq = get_insns ();
+  end_sequence ();
+
+  cost = seq_cost (seq, speed);
+  if (!cost)
+    cost = 1;
+
+  costs[mode] = cost;
+      
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Addition in %s costs %d\n",
+	     GET_MODE_NAME (mode), cost);
+  return cost;
+}
+
+/* Entry in a hashtable of already known costs for multiplication.  */
+struct mbc_entry
+{
+  HOST_WIDE_INT cst;		/* The constant to multiply by.  */
+  enum machine_mode mode;	/* In mode.  */
+  unsigned cost;		/* The cost.  */
+};
+
+/* Counts hash value for the ENTRY.  */
+
+static hashval_t
+mbc_entry_hash (const void *entry)
+{
+  const struct mbc_entry *e = (const struct mbc_entry *) entry;
+
+  return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
+}
+
+/* Compares the hash table entries ENTRY1 and ENTRY2.  */
+
+static int
+mbc_entry_eq (const void *entry1, const void *entry2)
+{
+  const struct mbc_entry *e1 = (const struct mbc_entry *) entry1;
+  const struct mbc_entry *e2 = (const struct mbc_entry *) entry2;
+
+  return (e1->mode == e2->mode
+	  && e1->cst == e2->cst);
+}
+
+/* Returns cost of multiplication by constant CST in MODE.  */
+
+unsigned
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
+{
+  static htab_t costs;
+  struct mbc_entry **cached, act;
+  rtx seq;
+  unsigned cost;
+
+  if (!costs)
+    costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
+
+  act.mode = mode;
+  act.cst = cst;
+  cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
+  if (*cached)
+    return (*cached)->cost;
+
+  *cached = XNEW (struct mbc_entry);
+  (*cached)->mode = mode;
+  (*cached)->cst = cst;
+
+  start_sequence ();
+  expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+	       gen_int_mode (cst, mode), NULL_RTX, 0);
+  seq = get_insns ();
+  end_sequence ();
+  
+  cost = seq_cost (seq, speed);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
+	     (int) cst, GET_MODE_NAME (mode), cost);
+
+  (*cached)->cost = cost;
+
+  return cost;
+}
+
+/* Returns true if multiplying by RATIO is allowed in an address.  Test the
+   validity for a memory reference accessing memory of mode MODE.  */
+
+bool
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
+{
+#define MAX_RATIO 128
+  static sbitmap valid_mult[MAX_MACHINE_MODE];
+  
+  if (!valid_mult[mode])
+    {
+      rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+      rtx addr;
+      HOST_WIDE_INT i;
+
+      valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
+      sbitmap_zero (valid_mult[mode]);
+      addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+      for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+	{
+	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
+	  if (memory_address_p (mode, addr))
+	    SET_BIT (valid_mult[mode], i + MAX_RATIO);
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  allowed multipliers:");
+	  for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
+	    if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
+	      fprintf (dump_file, " %d", (int) i);
+	  fprintf (dump_file, "\n");
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
+    return false;
+
+  return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
+}
+
+/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
+   If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
+   variable is omitted.  Compute the cost for a memory reference that accesses
+   a memory location of mode MEM_MODE.
+
+   TODO -- there must be some better way.  This all is quite crude.  */
+
+static comp_cost
+get_address_cost (bool symbol_present, bool var_present,
+		  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
+		  enum machine_mode mem_mode,
+		  bool speed)
+{
+  static bool initialized[MAX_MACHINE_MODE];
+  static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
+  static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
+  static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
+  unsigned cost, acost, complexity;
+  bool offset_p, ratio_p;
+  HOST_WIDE_INT s_offset;
+  unsigned HOST_WIDE_INT mask;
+  unsigned bits;
+
+  if (!initialized[mem_mode])
+    {
+      HOST_WIDE_INT i;
+      HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
+      int old_cse_not_expected;
+      unsigned sym_p, var_p, off_p, rat_p, add_c;
+      rtx seq, addr, base;
+      rtx reg0, reg1;
+
+      initialized[mem_mode] = true;
+
+      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+
+      addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
+      for (i = start; i <= 1 << 20; i <<= 1)
+	{
+	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
+	  if (!memory_address_p (mem_mode, addr))
+	    break;
+	}
+      max_offset[mem_mode] = i == start ? 0 : i >> 1;
+      off[mem_mode] = max_offset[mem_mode];
+
+      for (i = start; i <= 1 << 20; i <<= 1)
+	{
+	  XEXP (addr, 1) = gen_int_mode (-i, Pmode);
+	  if (!memory_address_p (mem_mode, addr))
+	    break;
+	}
+      min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "get_address_cost:\n");
+	  fprintf (dump_file, "  min offset %s %d\n",
+		   GET_MODE_NAME (mem_mode),
+		   (int) min_offset[mem_mode]);
+	  fprintf (dump_file, "  max offset %s %d\n",
+		   GET_MODE_NAME (mem_mode),
+		   (int) max_offset[mem_mode]);
+	}
+
+      rat[mem_mode] = 1;
+      for (i = 2; i <= MAX_RATIO; i++)
+	if (multiplier_allowed_in_address_p (i, mem_mode))
+	  {
+	    rat[mem_mode] = i;
+	    break;
+	  }
+
+      /* Compute the cost of various addressing modes.  */
+      acost = 0;
+      reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+
+      for (i = 0; i < 16; i++)
+	{
+	  sym_p = i & 1;
+	  var_p = (i >> 1) & 1;
+	  off_p = (i >> 2) & 1;
+	  rat_p = (i >> 3) & 1;
+
+	  addr = reg0;
+	  if (rat_p)
+	    addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
+				   gen_int_mode (rat[mem_mode], Pmode));
+
+	  if (var_p)
+	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+
+	  if (sym_p)
+	    {
+	      base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
+	      /* ??? We can run into trouble with some backends by presenting
+		 it with symbols which haven't been properly passed through
+		 targetm.encode_section_info.  By setting the local bit, we
+		 enhance the probability of things working.  */
+	      SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
+
+	      if (off_p)
+		base = gen_rtx_fmt_e (CONST, Pmode,
+				      gen_rtx_fmt_ee (PLUS, Pmode,
+						      base,
+						      gen_int_mode (off[mem_mode],
+								    Pmode)));
+	    }
+	  else if (off_p)
+	    base = gen_int_mode (off[mem_mode], Pmode);
+	  else
+	    base = NULL_RTX;
+    
+	  if (base)
+	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
+  
+	  start_sequence ();
+	  /* To avoid splitting addressing modes, pretend that no cse will
+	     follow.  */
+	  old_cse_not_expected = cse_not_expected;
+	  cse_not_expected = true;
+	  addr = memory_address (mem_mode, addr);
+	  cse_not_expected = old_cse_not_expected;
+	  seq = get_insns ();
+	  end_sequence ();
+
+	  acost = seq_cost (seq, speed);
+	  acost += address_cost (addr, mem_mode, speed);
+
+	  if (!acost)
+	    acost = 1;
+	  costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
+	}
+
+      /* On some targets, it is quite expensive to load symbol to a register,
+	 which makes addresses that contain symbols look much more expensive.
+	 However, the symbol will have to be loaded in any case before the
+	 loop (and quite likely we have it in register already), so it does not
+	 make much sense to penalize them too heavily.  So make some final
+         tweaks for the SYMBOL_PRESENT modes:
+
+         If VAR_PRESENT is false, and the mode obtained by changing symbol to
+	 var is cheaper, use this mode with small penalty.
+	 If VAR_PRESENT is true, try whether the mode with
+	 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
+	 if this is the case, use it.  */
+      add_c = add_cost (Pmode, speed);
+      for (i = 0; i < 8; i++)
+	{
+	  var_p = i & 1;
+	  off_p = (i >> 1) & 1;
+	  rat_p = (i >> 2) & 1;
+
+	  acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
+	  if (var_p)
+	    acost += add_c;
+
+	  if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
+	    costs[mem_mode][1][var_p][off_p][rat_p] = acost;
+	}
+  
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Address costs:\n");
+      
+	  for (i = 0; i < 16; i++)
+	    {
+	      sym_p = i & 1;
+	      var_p = (i >> 1) & 1;
+	      off_p = (i >> 2) & 1;
+	      rat_p = (i >> 3) & 1;
+
+	      fprintf (dump_file, "  ");
+	      if (sym_p)
+		fprintf (dump_file, "sym + ");
+	      if (var_p)
+		fprintf (dump_file, "var + ");
+	      if (off_p)
+		fprintf (dump_file, "cst + ");
+	      if (rat_p)
+		fprintf (dump_file, "rat * ");
+
+	      acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
+	      fprintf (dump_file, "index costs %d\n", acost);
+	    }
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  bits = GET_MODE_BITSIZE (Pmode);
+  mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+  offset &= mask;
+  if ((offset >> (bits - 1) & 1))
+    offset |= ~mask;
+  s_offset = offset;
+
+  cost = 0;
+  offset_p = (s_offset != 0
+	      && min_offset[mem_mode] <= s_offset
+	      && s_offset <= max_offset[mem_mode]);
+  ratio_p = (ratio != 1
+	     && multiplier_allowed_in_address_p (ratio, mem_mode));
+
+  if (ratio != 1 && !ratio_p)
+    cost += multiply_by_cost (ratio, Pmode, speed);
+
+  if (s_offset && !offset_p && !symbol_present)
+    cost += add_cost (Pmode, speed);
+
+  acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
+  complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
+  return new_cost (cost + acost, complexity);
+}
+
+/* Estimates cost of forcing expression EXPR into a variable.  */
+
+static comp_cost
+force_expr_to_var_cost (tree expr, bool speed)
+{
+  static bool costs_initialized = false;
+  static unsigned integer_cost [2];
+  static unsigned symbol_cost [2];
+  static unsigned address_cost [2];
+  tree op0, op1;
+  comp_cost cost0, cost1, cost;
+  enum machine_mode mode;
+
+  if (!costs_initialized)
+    {
+      tree type = build_pointer_type (integer_type_node);
+      tree var, addr;
+      rtx x;
+      int i;
+
+      var = create_tmp_var_raw (integer_type_node, "test_var");
+      TREE_STATIC (var) = 1;
+      x = produce_memory_decl_rtl (var, NULL);
+      SET_DECL_RTL (var, x);
+
+      addr = build1 (ADDR_EXPR, type, var);
+
+
+      for (i = 0; i < 2; i++)
+	{
+	  integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
+							     2000), i);
+
+	  symbol_cost[i] = computation_cost (addr, i) + 1;
+
+	  address_cost[i]
+	    = computation_cost (build2 (POINTER_PLUS_EXPR, type,
+					addr,
+					build_int_cst (sizetype, 2000)), i) + 1;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
+	      fprintf (dump_file, "  integer %d\n", (int) integer_cost[i]);
+	      fprintf (dump_file, "  symbol %d\n", (int) symbol_cost[i]);
+	      fprintf (dump_file, "  address %d\n", (int) address_cost[i]);
+	      fprintf (dump_file, "  other %d\n", (int) target_spill_cost[i]);
+	      fprintf (dump_file, "\n");
+	    }
+	}
+
+      costs_initialized = true;
+    }
+
+  STRIP_NOPS (expr);
+
+  if (SSA_VAR_P (expr))
+    return zero_cost;
+
+  if (is_gimple_min_invariant (expr))
+    {
+      if (TREE_CODE (expr) == INTEGER_CST)
+	return new_cost (integer_cost [speed], 0);
+
+      if (TREE_CODE (expr) == ADDR_EXPR)
+	{
+	  tree obj = TREE_OPERAND (expr, 0);
+
+	  if (TREE_CODE (obj) == VAR_DECL
+	      || TREE_CODE (obj) == PARM_DECL
+	      || TREE_CODE (obj) == RESULT_DECL)
+	    return new_cost (symbol_cost [speed], 0);
+	}
+
+      return new_cost (address_cost [speed], 0);
+    }
+
+  switch (TREE_CODE (expr))
+    {
+    case POINTER_PLUS_EXPR:
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+    case MULT_EXPR:
+      op0 = TREE_OPERAND (expr, 0);
+      op1 = TREE_OPERAND (expr, 1);
+      STRIP_NOPS (op0);
+      STRIP_NOPS (op1);
+
+      if (is_gimple_val (op0))
+	cost0 = zero_cost;
+      else
+	cost0 = force_expr_to_var_cost (op0, speed);
+
+      if (is_gimple_val (op1))
+	cost1 = zero_cost;
+      else
+	cost1 = force_expr_to_var_cost (op1, speed);
+
+      break;
+
+    default:
+      /* Just an arbitrary value, FIXME.  */
+      return new_cost (target_spill_cost[speed], 0);
+    }
+
+  mode = TYPE_MODE (TREE_TYPE (expr));
+  switch (TREE_CODE (expr))
+    {
+    case POINTER_PLUS_EXPR:
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      cost = new_cost (add_cost (mode, speed), 0);
+      break;
+
+    case MULT_EXPR:
+      if (cst_and_fits_in_hwi (op0))
+	cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
+      else if (cst_and_fits_in_hwi (op1))                                  
+	cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
+      else
+	return new_cost (target_spill_cost [speed], 0);
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  cost = add_costs (cost, cost0);
+  cost = add_costs (cost, cost1);
+
+  /* Bound the cost by target_spill_cost.  The parts of complicated
+     computations often are either loop invariant or at least can
+     be shared between several iv uses, so letting this grow without
+     limits would not give reasonable results.  */
+  if (cost.cost > target_spill_cost [speed])
+    cost.cost = target_spill_cost [speed];
+
+  return cost;
+}
+
+/* Estimates cost of forcing EXPR into a variable.  DEPENDS_ON is a set of the
+   invariants the computation depends on.  */
+
+static comp_cost
+force_var_cost (struct ivopts_data *data,
+		tree expr, bitmap *depends_on)
+{
+  if (depends_on)
+    {
+      fd_ivopts_data = data;
+      walk_tree (&expr, find_depends, depends_on, NULL);
+    }
+
+  return force_expr_to_var_cost (expr, data->speed);
+}
+
+/* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
+   value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
+   to false if the corresponding part is missing.  DEPENDS_ON is a set of the
+   invariants the computation depends on.  */
+
+static comp_cost
+split_address_cost (struct ivopts_data *data,
+		    tree addr, bool *symbol_present, bool *var_present,
+		    unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
+{
+  tree core;
+  HOST_WIDE_INT bitsize;
+  HOST_WIDE_INT bitpos;
+  tree toffset;
+  enum machine_mode mode;
+  int unsignedp, volatilep;
+  
+  core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
+			      &unsignedp, &volatilep, false);
+
+  if (toffset != 0
+      || bitpos % BITS_PER_UNIT != 0
+      || TREE_CODE (core) != VAR_DECL)
+    {
+      *symbol_present = false;
+      *var_present = true;
+      fd_ivopts_data = data;
+      walk_tree (&addr, find_depends, depends_on, NULL);
+      return new_cost (target_spill_cost[data->speed], 0);
+    }
+
+  *offset += bitpos / BITS_PER_UNIT;
+  if (TREE_STATIC (core)
+      || DECL_EXTERNAL (core))
+    {
+      *symbol_present = true;
+      *var_present = false;
+      return zero_cost;
+    }
+      
+  *symbol_present = false;
+  *var_present = true;
+  return zero_cost;
+}
+
+/* Estimates cost of expressing difference of addresses E1 - E2 as
+   var + symbol + offset.  The value of offset is added to OFFSET,
+   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
+   part is missing.  DEPENDS_ON is a set of the invariants the computation
+   depends on.  */
+
+static comp_cost
+ptr_difference_cost (struct ivopts_data *data,
+		     tree e1, tree e2, bool *symbol_present, bool *var_present,
+		     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
+{
+  HOST_WIDE_INT diff = 0;
+  comp_cost cost;
+  bool speed = optimize_loop_for_speed_p (data->current_loop);
+
+  gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
+
+  if (ptr_difference_const (e1, e2, &diff))
+    {
+      *offset += diff;
+      *symbol_present = false;
+      *var_present = false;
+      return zero_cost;
+    }
+
+  if (integer_zerop (e2))
+    return split_address_cost (data, TREE_OPERAND (e1, 0),
+			       symbol_present, var_present, offset, depends_on);
+
+  *symbol_present = false;
+  *var_present = true;
+  
+  cost = force_var_cost (data, e1, depends_on);
+  cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+  cost.cost += add_cost (Pmode, speed);
+
+  return cost;
+}
+
+/* Estimates cost of expressing difference E1 - E2 as
+   var + symbol + offset.  The value of offset is added to OFFSET,
+   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
+   part is missing.  DEPENDS_ON is a set of the invariants the computation
+   depends on.  */
+
+static comp_cost
+difference_cost (struct ivopts_data *data,
+		 tree e1, tree e2, bool *symbol_present, bool *var_present,
+		 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
+{
+  comp_cost cost;
+  enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
+  unsigned HOST_WIDE_INT off1, off2;
+
+  e1 = strip_offset (e1, &off1);
+  e2 = strip_offset (e2, &off2);
+  *offset += off1 - off2;
+
+  STRIP_NOPS (e1);
+  STRIP_NOPS (e2);
+
+  if (TREE_CODE (e1) == ADDR_EXPR)
+    return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
+				depends_on);
+  *symbol_present = false;
+
+  if (operand_equal_p (e1, e2, 0))
+    {
+      *var_present = false;
+      return zero_cost;
+    }
+  *var_present = true;
+  if (integer_zerop (e2))
+    return force_var_cost (data, e1, depends_on);
+
+  if (integer_zerop (e1))
+    {
+      cost = force_var_cost (data, e2, depends_on);
+      cost.cost += multiply_by_cost (-1, mode, data->speed);
+
+      return cost;
+    }
+
+  cost = force_var_cost (data, e1, depends_on);
+  cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+  cost.cost += add_cost (mode, data->speed);
+
+  return cost;
+}
+
+/* Returns true if AFF1 and AFF2 are identical.  */
+
+static bool
+compare_aff_trees (aff_tree *aff1, aff_tree *aff2)
+{
+  unsigned i;
+
+  if (aff1->n != aff2->n)
+    return false;
+
+  for (i = 0; i < aff1->n; i++)
+    {
+      if (double_int_cmp (aff1->elts[i].coef, aff2->elts[i].coef, 0) != 0)
+        return false;
+
+      if (!operand_equal_p (aff1->elts[i].val, aff2->elts[i].val, 0))
+        return false;
+    }
+  return true;
+}
+
+/* Returns true if expression UBASE - RATIO * CBASE requires a new compiler
+   generated temporary.  */
+
+static bool
+create_loop_invariant_temp (tree ubase, tree cbase, HOST_WIDE_INT ratio)
+{
+  aff_tree ubase_aff, cbase_aff;
+
+  STRIP_NOPS (ubase);
+  STRIP_NOPS (cbase);
+
+  if ((TREE_CODE (ubase) == INTEGER_CST)
+      && (TREE_CODE (cbase) == INTEGER_CST))
+    return false;
+
+  if (((TREE_CODE (ubase) == SSA_NAME)
+       || (TREE_CODE (ubase) == ADDR_EXPR))
+      && (TREE_CODE (cbase) == INTEGER_CST))
+    return false;
+
+  if (((TREE_CODE (cbase) == SSA_NAME)
+       || (TREE_CODE (cbase) == ADDR_EXPR))
+      && (TREE_CODE (ubase) == INTEGER_CST))
+    return false;
+
+  if (ratio == 1)
+    {
+      if(operand_equal_p (ubase, cbase, 0))
+        return false;
+      if (TREE_CODE (ubase) == ADDR_EXPR
+        && TREE_CODE (cbase) == ADDR_EXPR)
+        {
+          tree usym, csym;
+
+          usym = TREE_OPERAND (ubase, 0);
+          csym = TREE_OPERAND (cbase, 0);
+          if (TREE_CODE (usym) == ARRAY_REF)
+            {
+              tree ind = TREE_OPERAND (usym, 1);
+              if (TREE_CODE (ind) == INTEGER_CST
+                  && host_integerp (ind, 0)
+                  && TREE_INT_CST_LOW (ind) == 0)
+                usym = TREE_OPERAND (usym, 0);
+            }
+          if (TREE_CODE (csym) == ARRAY_REF)
+            {
+              tree ind = TREE_OPERAND (csym, 1);
+              if (TREE_CODE (ind) == INTEGER_CST
+                  && host_integerp (ind, 0)
+                  && TREE_INT_CST_LOW (ind) == 0)
+                csym = TREE_OPERAND (csym, 0);
+            }
+          if (usym == csym)
+            return false;
+        }
+      /* Now do more complex comparison  */
+      tree_to_aff_combination (ubase, TREE_TYPE (ubase), &ubase_aff);
+      tree_to_aff_combination (cbase, TREE_TYPE (cbase), &cbase_aff);
+      if (compare_aff_trees (&ubase_aff, &cbase_aff))
+        return false;
+    }
+
+  return true;
+}
+
+
+
+/* Determines the cost of the computation by that USE is expressed
+   from induction variable CAND.  If ADDRESS_P is true, we just need
+   to create an address from it, otherwise we want to get it into
+   register.  A set of invariants we depend on is stored in
+   DEPENDS_ON.  AT is the statement at that the value is computed.  */
+
+static comp_cost
+get_computation_cost_at (struct ivopts_data *data,
+			 struct iv_use *use, struct iv_cand *cand,
+			 bool address_p, bitmap *depends_on, gimple at)
+{
+  tree ubase = use->iv->base, ustep = use->iv->step;
+  tree cbase, cstep;
+  tree utype = TREE_TYPE (ubase), ctype;
+  unsigned HOST_WIDE_INT cstepi, offset = 0;
+  HOST_WIDE_INT ratio, aratio;
+  bool var_present, symbol_present;
+  comp_cost cost;
+  unsigned n_sums;
+  double_int rat;
+  bool speed = optimize_bb_for_speed_p (gimple_bb (at));
+
+  *depends_on = NULL;
+
+  /* Only consider real candidates.  */
+  if (!cand->iv)
+    return infinite_cost;
+
+  cbase = cand->iv->base;
+  cstep = cand->iv->step;
+  ctype = TREE_TYPE (cbase);
+
+  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
+    {
+      /* We do not have a precision to express the values of use.  */
+      return infinite_cost;
+    }
+
+  if (address_p)
+    {
+      /* Do not try to express address of an object with computation based
+	 on address of a different object.  This may cause problems in rtl
+	 level alias analysis (that does not expect this to be happening,
+	 as this is illegal in C), and would be unlikely to be useful
+	 anyway.  */
+      if (use->iv->base_object
+	  && cand->iv->base_object
+	  && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
+	return infinite_cost;
+    }
+
+  if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+    {
+      /* TODO -- add direct handling of this case.  */
+      goto fallback;
+    }
+
+  /* CSTEPI is removed from the offset in case statement is after the
+     increment.  If the step is not constant, we use zero instead.
+     This is a bit imprecise (there is the extra addition), but
+     redundancy elimination is likely to transform the code so that
+     it uses value of the variable before increment anyway,
+     so it is not that much unrealistic.  */
+  if (cst_and_fits_in_hwi (cstep))
+    cstepi = int_cst_value (cstep);
+  else
+    cstepi = 0;
+
+  if (!constant_multiple_of (ustep, cstep, &rat))
+    return infinite_cost;
+    
+  if (double_int_fits_in_shwi_p (rat))
+    ratio = double_int_to_shwi (rat);
+  else
+    return infinite_cost;
+
+  /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
+     or ratio == 1, it is better to handle this like
+     
+     ubase - ratio * cbase + ratio * var
+     
+     (also holds in the case ratio == -1, TODO.  */
+
+  if (cst_and_fits_in_hwi (cbase))
+    {
+      offset = - ratio * int_cst_value (cbase); 
+      cost = difference_cost (data,
+			      ubase, build_int_cst (utype, 0),
+			      &symbol_present, &var_present, &offset,
+			      depends_on);
+    }
+  else if (ratio == 1)
+    {
+      cost = difference_cost (data,
+			      ubase, cbase,
+			      &symbol_present, &var_present, &offset,
+			      depends_on);
+    }
+  else
+    {
+      cost = force_var_cost (data, cbase, depends_on);
+      cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
+      cost = add_costs (cost,
+			difference_cost (data,
+					 ubase, build_int_cst (utype, 0),
+					 &symbol_present, &var_present,
+					 &offset, depends_on));
+    }
+
+  /* Loop invariant computation  */
+  cost.cost /= avg_loop_niter (data->current_loop);
+
+  if (create_loop_invariant_temp (ubase, cbase, ratio))
+    {
+      struct version_info *pv = record_pseudo_invariant (data);
+       if (!*depends_on)
+         *depends_on = BITMAP_ALLOC (NULL);
+       bitmap_set_bit (*depends_on, pv->inv_id);
+    }
+
+  /* If we are after the increment, the value of the candidate is higher by
+     one iteration.  */
+  if (stmt_after_increment (data->current_loop, cand, at))
+    offset -= ratio * cstepi;
+
+  /* Now the computation is in shape symbol + var1 + const + ratio * var2.
+     (symbol/var/const parts may be omitted).  If we are looking for an address,
+     find the cost of addressing this.  */
+  if (address_p)
+    return add_costs (cost, get_address_cost (symbol_present, var_present,
+				offset, ratio,
+				TYPE_MODE (TREE_TYPE (*use->op_p)), speed));
+
+  /* Otherwise estimate the costs for computing the expression.  */
+  aratio = ratio > 0 ? ratio : -ratio;
+  if (!symbol_present && !var_present && !offset)
+    {
+      if (ratio != 1)
+	cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
+
+      return cost;
+    }
+
+  if (aratio != 1)
+    cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
+
+  n_sums = 1;
+  if (var_present
+      /* Symbol + offset should be compile-time computable.  */
+      && (symbol_present || offset))
+    n_sums++;
+
+  /* Having offset does not affect runtime cost in case it is added to
+     symbol, but it increases complexity.  */
+  if (offset)
+    cost.complexity++;
+
+  cost.cost += n_sums * add_cost (TYPE_MODE (ctype), speed);
+  return cost;
+
+fallback:
+  {
+    /* Just get the expression, expand it and measure the cost.  */
+    tree comp = get_computation_at (data->current_loop, use, cand, at);
+
+    if (!comp)
+      return infinite_cost;
+
+    if (address_p)
+      comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
+
+    return new_cost (computation_cost (comp, speed), 0);
+  }
+}
+
+/* Determines the cost of the computation by that USE is expressed
+   from induction variable CAND.  If ADDRESS_P is true, we just need
+   to create an address from it, otherwise we want to get it into
+   register.  A set of invariants we depend on is stored in
+   DEPENDS_ON.  */
+
+static comp_cost
+get_computation_cost (struct ivopts_data *data,
+		      struct iv_use *use, struct iv_cand *cand,
+		      bool address_p, bitmap *depends_on)
+{
+  return get_computation_cost_at (data,
+				  use, cand, address_p, depends_on, use->stmt);
+}
+
+/* Determines cost of basing replacement of USE on CAND in a generic
+   expression.  */
+
+static bool
+determine_use_iv_cost_generic (struct ivopts_data *data,
+			       struct iv_use *use, struct iv_cand *cand)
+{
+  bitmap depends_on;
+  comp_cost cost;
+
+  /* The simple case first -- if we need to express value of the preserved
+     original biv, the cost is 0.  This also prevents us from counting the
+     cost of increment twice -- once at this use and once in the cost of
+     the candidate.  */
+  if (cand->pos == IP_ORIGINAL
+      && cand->incremented_at == use->stmt)
+    {
+      set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
+      return true;
+    }
+
+  cost = get_computation_cost (data, use, cand, false, &depends_on);
+
+  if (use->use_pos == IU_OUTSIDE_LOOP_ONLY && !infinite_cost_p (cost))
+    cost.cost /= avg_loop_niter (data->current_loop);
+
+  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
+
+  return !infinite_cost_p (cost);
+}
+
+/* Determines cost of basing replacement of USE on CAND in an address.  */
+
+static bool
+determine_use_iv_cost_address (struct ivopts_data *data,
+			       struct iv_use *use, struct iv_cand *cand)
+{
+  bitmap depends_on;
+  comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on);
+
+  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
+
+  return !infinite_cost_p (cost);
+}
+
+/* Computes value of candidate CAND at position AT in iteration NITER, and
+   stores it to VAL.  */
+
+static void
+cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter,
+	       aff_tree *val)
+{
+  aff_tree step, delta, nit;
+  struct iv *iv = cand->iv;
+  tree type = TREE_TYPE (iv->base);
+  tree steptype = type;
+  if (POINTER_TYPE_P (type))
+    steptype = sizetype;
+
+  tree_to_aff_combination (iv->step, steptype, &step);
+  tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
+  aff_combination_convert (&nit, steptype);
+  aff_combination_mult (&nit, &step, &delta);
+  if (stmt_after_increment (loop, cand, at))
+    aff_combination_add (&delta, &step);
+
+  tree_to_aff_combination (iv->base, type, val);
+  aff_combination_add (val, &delta);
+}
+
+/* Returns period of induction variable iv.  */
+
+static tree
+iv_period (struct iv *iv)
+{
+  tree step = iv->step, period, type;
+  tree pow2div;
+
+  gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+
+  /* Period of the iv is gcd (step, type range).  Since type range is power
+     of two, it suffices to determine the maximum power of two that divides
+     step.  */
+  pow2div = num_ending_zeros (step);
+  type = unsigned_type_for (TREE_TYPE (step));
+
+  period = build_low_bits_mask (type,
+				(TYPE_PRECISION (type)
+				 - tree_low_cst (pow2div, 1)));
+
+  return period;
+}
+
+/* Returns the comparison operator used when eliminating the iv USE.  */
+
+static enum tree_code
+iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
+{
+  struct loop *loop = data->current_loop;
+  basic_block ex_bb;
+  edge exit;
+
+  ex_bb = gimple_bb (use->stmt);
+  exit = EDGE_SUCC (ex_bb, 0);
+  if (flow_bb_inside_loop_p (loop, exit->dest))
+    exit = EDGE_SUCC (ex_bb, 1);
+
+  return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
+}
+
+/* Check whether it is possible to express the condition in USE by comparison
+   of candidate CAND.  If so, store the value compared with to BOUND.  */
+
+static bool
+may_eliminate_iv (struct ivopts_data *data,
+		  struct iv_use *use, struct iv_cand *cand, tree *bound)
+{
+  basic_block ex_bb;
+  edge exit;
+  tree nit, period;
+  struct loop *loop = data->current_loop;
+  aff_tree bnd;
+
+  if (TREE_CODE (cand->iv->step) != INTEGER_CST)
+    return false;
+
+  /* For now works only for exits that dominate the loop latch.
+     TODO: extend to other conditions inside loop body.  */
+  ex_bb = gimple_bb (use->stmt);
+  if (use->stmt != last_stmt (ex_bb)
+      || gimple_code (use->stmt) != GIMPLE_COND
+      || !dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
+    return false;
+
+  exit = EDGE_SUCC (ex_bb, 0);
+  if (flow_bb_inside_loop_p (loop, exit->dest))
+    exit = EDGE_SUCC (ex_bb, 1);
+  if (flow_bb_inside_loop_p (loop, exit->dest))
+    return false;
+
+  nit = niter_for_exit (data, exit);
+  if (!nit)
+    return false;
+
+  /* Determine whether we can use the variable to test the exit condition.
+     This is the case iff the period of the induction variable is greater
+     than the number of iterations for which the exit condition is true.  */
+  period = iv_period (cand->iv);
+
+  /* If the number of iterations is constant, compare against it directly.  */
+  if (TREE_CODE (nit) == INTEGER_CST)
+    {
+      if (!tree_int_cst_lt (nit, period))
+	return false;
+    }
+
+  /* If not, and if this is the only possible exit of the loop, see whether
+     we can get a conservative estimate on the number of iterations of the
+     entire loop and compare against that instead.  */
+  else
+    {
+      double_int period_value, max_niter;
+      if (!estimated_loop_iterations (loop, true, &max_niter))
+	return false;
+      period_value = tree_to_double_int (period);
+      if (double_int_ucmp (max_niter, period_value) > 0)
+	return false;
+    }
+
+  cand_value_at (loop, cand, use->stmt, nit, &bnd);
+
+  *bound = aff_combination_to_tree (&bnd);
+  /* It is unlikely that computing the number of iterations using division
+     would be more profitable than keeping the original induction variable.  */
+  if (expression_expensive_p (*bound))
+    return false;
+  return true;
+}
+
+/* Determines cost of basing replacement of USE on CAND in a condition.  */
+
+static bool
+determine_use_iv_cost_condition (struct ivopts_data *data,
+				 struct iv_use *use, struct iv_cand *cand)
+{
+  tree bound = NULL_TREE;
+  struct iv *cmp_iv;
+  bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
+  comp_cost elim_cost, express_cost, cost;
+  bool ok;
+
+  /* Only consider real candidates.  */
+  if (!cand->iv)
+    {
+      set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE);
+      return false;
+    }
+
+  /* Try iv elimination.  */
+  if (may_eliminate_iv (data, use, cand, &bound))
+    {
+      elim_cost = force_var_cost (data, bound, &depends_on_elim);
+      /* The bound is a loop invariant, so it will be only computed
+	 once.  */
+      elim_cost.cost /= avg_loop_niter (data->current_loop);
+    }
+  else
+    elim_cost = infinite_cost;
+
+  /* Try expressing the original giv.  If it is compared with an invariant,
+     note that we cannot get rid of it.  */
+  ok = extract_cond_operands (data, use->stmt, NULL, NULL, NULL, &cmp_iv);
+  gcc_assert (ok);
+
+  express_cost = get_computation_cost (data, use, cand, false,
+				       &depends_on_express);
+  fd_ivopts_data = data;
+  walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
+
+  /* Choose the better approach, preferring the eliminated IV. */
+  if (compare_costs (elim_cost, express_cost) <= 0)
+    {
+      cost = elim_cost;
+      depends_on = depends_on_elim;
+      depends_on_elim = NULL;
+    }
+  else
+    {
+      cost = express_cost;
+      depends_on = depends_on_express;
+      depends_on_express = NULL;
+      bound = NULL_TREE;
+    }
+
+  set_use_iv_cost (data, use, cand, cost, depends_on, bound);
+
+  if (depends_on_elim)
+    BITMAP_FREE (depends_on_elim);
+  if (depends_on_express)
+    BITMAP_FREE (depends_on_express);
+
+  return !infinite_cost_p (cost);
+}
+
+/* Determines cost of basing replacement of USE on CAND.  Returns false
+   if USE cannot be based on CAND.  */
+
+static bool
+determine_use_iv_cost (struct ivopts_data *data,
+		       struct iv_use *use, struct iv_cand *cand)
+{
+  switch (use->type)
+    {
+    case USE_NONLINEAR_EXPR:
+      return determine_use_iv_cost_generic (data, use, cand);
+
+    case USE_ADDRESS:
+      return determine_use_iv_cost_address (data, use, cand);
+
+    case USE_COMPARE:
+      return determine_use_iv_cost_condition (data, use, cand);
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Determines costs of basing the use of the iv on an iv candidate.  */
+
+static void
+determine_use_iv_costs (struct ivopts_data *data)
+{
+  unsigned i, j;
+  struct iv_use *use;
+  struct iv_cand *cand;
+  bitmap to_clear = BITMAP_ALLOC (NULL);
+
+  alloc_use_cost_map (data);
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+
+      if (data->consider_all_candidates)
+	{
+	  for (j = 0; j < n_iv_cands (data); j++)
+	    {
+	      cand = iv_cand (data, j);
+	      determine_use_iv_cost (data, use, cand);
+	    }
+	}
+      else
+	{
+	  bitmap_iterator bi;
+
+	  EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
+	    {
+	      cand = iv_cand (data, j);
+	      if (!determine_use_iv_cost (data, use, cand))
+		bitmap_set_bit (to_clear, j);
+	    }
+
+	  /* Remove the candidates for that the cost is infinite from
+	     the list of related candidates.  */
+	  bitmap_and_compl_into (use->related_cands, to_clear);
+	  bitmap_clear (to_clear);
+	}
+    }
+
+  BITMAP_FREE (to_clear);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Use-candidate costs:\n");
+
+      for (i = 0; i < n_iv_uses (data); i++)
+	{
+	  use = iv_use (data, i);
+
+	  fprintf (dump_file, "Use %d:\n", i);
+	  fprintf (dump_file, "  cand\tcost\tcompl.\tdepends on\n");
+	  for (j = 0; j < use->n_map_members; j++)
+	    {
+	      if (!use->cost_map[j].cand
+		  || infinite_cost_p (use->cost_map[j].cost))
+		continue;
+
+	      fprintf (dump_file, "  %d\t%d\t%d\t",
+		       use->cost_map[j].cand->id,
+		       use->cost_map[j].cost.cost,
+		       use->cost_map[j].cost.complexity);
+	      if (use->cost_map[j].depends_on)
+		bitmap_print (dump_file,
+			      use->cost_map[j].depends_on, "","");
+	      fprintf (dump_file, "\n");
+	    }
+
+	  fprintf (dump_file, "\n");
+	}
+      fprintf (dump_file, "\n");
+    }
+}
+
+/* Determines cost of the candidate CAND.  */
+
+static void
+determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
+{
+  comp_cost cost_base;
+  unsigned cost, cost_step;
+  tree base;
+
+  if (!cand->iv)
+    {
+      cand->cost = 0;
+      return;
+    }
+
+  /* There are two costs associated with the candidate -- its increment
+     and its initialization.  The second is almost negligible for any loop
+     that rolls enough, so we take it just very little into account.  */
+
+  base = cand->iv->base;
+  cost_base = force_var_cost (data, base, NULL);
+  cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
+
+  cost = cost_step + cost_base.cost / avg_loop_niter (data->current_loop);
+
+  /* Prefer the original ivs unless we may gain something by replacing it.
+     The reason is to make debugging simpler; so this is not relevant for
+     artificial ivs created by other optimization passes.  */
+  if (cand->pos != IP_ORIGINAL
+      || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
+    cost++;
+  
+  /* Prefer not to insert statements into latch unless there are some
+     already (so that we do not create unnecessary jumps).  */
+  if (cand->pos == IP_END
+      && empty_block_p (ip_end_pos (data->current_loop)))
+    cost++;
+
+  cand->cost = cost;
+}
+
+/* Determines costs of computation of the candidates.  */
+
+static void
+determine_iv_costs (struct ivopts_data *data)
+{
+  unsigned i;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Candidate costs:\n");
+      fprintf (dump_file, "  cand\tcost\n");
+    }
+
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      struct iv_cand *cand = iv_cand (data, i);
+
+      determine_iv_cost (data, cand);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  %d\t%d\n", i, cand->cost);
+    }
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n");
+}
+
+/* Calculates cost for having SIZE induction variables.  */
+
+static unsigned
+ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
+{
+  /* We add size to the cost, so that we prefer eliminating ivs
+     if possible.  */
+  return size + estimate_reg_pressure_cost (size, data->regs_used, data->speed);
+}
+
+/* For each size of the induction variable set determine the penalty.  */
+
+static void
+determine_set_costs (struct ivopts_data *data)
+{
+  unsigned j, n;
+  gimple phi;
+  gimple_stmt_iterator psi;
+  tree op;
+  struct loop *loop = data->current_loop;
+  bitmap_iterator bi;
+
+  /* We use the following model (definitely improvable, especially the
+     cost function -- TODO):
+
+     We estimate the number of registers available (using MD data), name it A.
+
+     We estimate the number of registers used by the loop, name it U.  This
+     number is obtained as the number of loop phi nodes (not counting virtual
+     registers and bivs) + the number of variables from outside of the loop.
+
+     We set a reserve R (free regs that are used for temporary computations,
+     etc.).  For now the reserve is a constant 3.
+
+     Let I be the number of induction variables.
+     
+     -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
+	make a lot of ivs without a reason).
+     -- if A - R < U + I <= A, the cost is I * PRES_COST
+     -- if U + I > A, the cost is I * PRES_COST and
+        number of uses * SPILL_COST * (U + I - A) / (U + I) is added.  */
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Global costs:\n");
+      fprintf (dump_file, "  target_avail_regs %d\n", target_avail_regs);
+      fprintf (dump_file, "  target_reg_cost %d\n", target_reg_cost[data->speed]);
+      fprintf (dump_file, "  target_spill_cost %d\n", target_spill_cost[data->speed]);
+    }
+
+  n = 0;
+  for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      phi = gsi_stmt (psi);
+      op = PHI_RESULT (phi);
+
+      if (!is_gimple_reg (op))
+	continue;
+
+      if (get_iv (data, op))
+	continue;
+
+      n++;
+    }
+
+  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
+    {
+      struct version_info *info = ver_info (data, j);
+
+      if (info->inv_id && info->has_nonlin_use)
+	n++;
+    }
+
+  data->regs_used = n;
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  regs_used %d\n", n);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  cost for size:\n");
+      fprintf (dump_file, "  ivs\tcost\n");
+      for (j = 0; j <= 2 * target_avail_regs; j++)
+	fprintf (dump_file, "  %d\t%d\n", j,
+		 ivopts_global_cost_for_size (data, j));
+      fprintf (dump_file, "\n");
+    }
+}
+
+/* Returns true if A is a cheaper cost pair than B.  */
+
+static bool
+cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
+{
+  int cmp;
+
+  if (!a)
+    return false;
+
+  if (!b)
+    return true;
+
+  cmp = compare_costs (a->cost, b->cost);
+  if (cmp < 0)
+    return true;
+
+  if (cmp > 0)
+    return false;
+
+  /* In case the costs are the same, prefer the cheaper candidate.  */
+  if (a->cand->cost < b->cand->cost)
+    return true;
+
+  return false;
+}
+
+/* Computes the cost field of IVS structure.  */
+
+static void
+iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
+{
+  comp_cost cost = ivs->cand_use_cost;
+  cost.cost += ivs->cand_cost;
+  cost.cost += ivopts_global_cost_for_size (data,
+                                            ivs->n_regs + (ivs->n_pseudos * 30) / 100);
+
+  ivs->cost = cost;
+}
+
+/* Remove invariants in set INVS to set IVS.  */
+
+static void
+iv_ca_set_remove_invariants (struct ivopts_data *data,
+                             struct iv_ca *ivs, bitmap invs)
+{
+  bitmap_iterator bi;
+  unsigned iid;
+  unsigned pseudo_id_start = data->min_pseudo_inv_id;
+
+  if (!invs)
+    return;
+
+  EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
+    {
+      ivs->n_invariant_uses[iid]--;
+      if (ivs->n_invariant_uses[iid] == 0)
+        {
+          if (iid < pseudo_id_start)
+            ivs->n_regs--;
+          else
+            ivs->n_pseudos--;
+        }
+    }
+}
+
+/* Set USE not to be expressed by any candidate in IVS.  */
+
+static void
+iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
+		 struct iv_use *use)
+{
+  unsigned uid = use->id, cid;
+  struct cost_pair *cp;
+
+  cp = ivs->cand_for_use[uid];
+  if (!cp)
+    return;
+  cid = cp->cand->id;
+
+  ivs->bad_uses++;
+  ivs->cand_for_use[uid] = NULL;
+  ivs->n_cand_uses[cid]--;
+
+  if (ivs->n_cand_uses[cid] == 0)
+    {
+      bitmap_clear_bit (ivs->cands, cid);
+      /* Do not count the pseudocandidates.  */
+      if (cp->cand->iv)
+	ivs->n_regs--;
+      ivs->n_cands--;
+      ivs->cand_cost -= cp->cand->cost;
+
+      iv_ca_set_remove_invariants (data, ivs, cp->cand->depends_on);
+    }
+
+  ivs->cand_use_cost = sub_costs (ivs->cand_use_cost, cp->cost);
+
+  iv_ca_set_remove_invariants (data, ivs, cp->depends_on);
+  iv_ca_recount_cost (data, ivs);
+}
+
+/* Add invariants in set INVS to set IVS.  */
+
+static void
+iv_ca_set_add_invariants (struct ivopts_data *data,
+                          struct iv_ca *ivs, bitmap invs)
+{
+  bitmap_iterator bi;
+  unsigned iid;
+  unsigned pseudo_id_start = data->min_pseudo_inv_id;
+
+  if (!invs)
+    return;
+
+  EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
+    {
+      ivs->n_invariant_uses[iid]++;
+      if (ivs->n_invariant_uses[iid] == 1)
+        {
+          if (iid < pseudo_id_start)
+            ivs->n_regs++;
+          else
+            ivs->n_pseudos++;
+        }
+    }
+}
+
+/* Set cost pair for USE in set IVS to CP.  */
+
+static void
+iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
+	      struct iv_use *use, struct cost_pair *cp)
+{
+  unsigned uid = use->id, cid;
+
+  if (ivs->cand_for_use[uid] == cp)
+    return;
+
+  if (ivs->cand_for_use[uid])
+    iv_ca_set_no_cp (data, ivs, use);
+
+  if (cp)
+    {
+      cid = cp->cand->id;
+
+      ivs->bad_uses--;
+      ivs->cand_for_use[uid] = cp;
+      ivs->n_cand_uses[cid]++;
+      if (ivs->n_cand_uses[cid] == 1)
+	{
+	  bitmap_set_bit (ivs->cands, cid);
+	  /* Do not count the pseudocandidates.  */
+	  if (cp->cand->iv)
+	    ivs->n_regs++;
+	  ivs->n_cands++;
+	  ivs->cand_cost += cp->cand->cost;
+
+	  iv_ca_set_add_invariants (data, ivs, cp->cand->depends_on);
+	}
+
+      ivs->cand_use_cost = add_costs (ivs->cand_use_cost, cp->cost);
+      iv_ca_set_add_invariants (data, ivs, cp->depends_on);
+      iv_ca_recount_cost (data, ivs);
+    }
+}
+
+/* Extend set IVS by expressing USE by some of the candidates in it
+   if possible.  */
+
+static void
+iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
+	       struct iv_use *use)
+{
+  struct cost_pair *best_cp = NULL, *cp;
+  bitmap_iterator bi;
+  unsigned i;
+
+  gcc_assert (ivs->upto >= use->id);
+
+  if (ivs->upto == use->id)
+    {
+      ivs->upto++;
+      ivs->bad_uses++;
+    }
+
+  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+    {
+      cp = get_use_iv_cost (data, use, iv_cand (data, i));
+
+      if (cheaper_cost_pair (cp, best_cp))
+	best_cp = cp;
+    }
+
+  iv_ca_set_cp (data, ivs, use, best_cp);
+}
+
+/* Get cost for assignment IVS.  */
+
+static comp_cost
+iv_ca_cost (struct iv_ca *ivs)
+{
+  /* This was a conditional expression but it triggered a bug in
+     Sun C 5.5.  */
+  if (ivs->bad_uses)
+    return infinite_cost;
+  else
+    return ivs->cost;
+}
+
+/* Returns true if all dependences of CP are among invariants in IVS.  */
+
+static bool
+iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
+{
+  unsigned i;
+  bitmap_iterator bi;
+
+  if (!cp->depends_on)
+    return true;
+
+  EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
+    {
+      if (ivs->n_invariant_uses[i] == 0)
+	return false;
+    }
+
+  return true;
+}
+
+/* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
+   it before NEXT_CHANGE.  */
+
+static struct iv_ca_delta *
+iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
+		 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
+{
+  struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
+
+  change->use = use;
+  change->old_cp = old_cp;
+  change->new_cp = new_cp;
+  change->next_change = next_change;
+
+  return change;
+}
+
+/* Joins two lists of changes L1 and L2.  Destructive -- old lists
+   are rewritten.  */
+
+static struct iv_ca_delta *
+iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
+{
+  struct iv_ca_delta *last;
+
+  if (!l2)
+    return l1;
+
+  if (!l1)
+    return l2;
+
+  for (last = l1; last->next_change; last = last->next_change)
+    continue;
+  last->next_change = l2;
+
+  return l1;
+}
+
+/* Returns candidate by that USE is expressed in IVS.  */
+
+static struct cost_pair *
+iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
+{
+  return ivs->cand_for_use[use->id];
+}
+
+/* Reverse the list of changes DELTA, forming the inverse to it.  */
+
+static struct iv_ca_delta *
+iv_ca_delta_reverse (struct iv_ca_delta *delta)
+{
+  struct iv_ca_delta *act, *next, *prev = NULL;
+  struct cost_pair *tmp;
+
+  for (act = delta; act; act = next)
+    {
+      next = act->next_change;
+      act->next_change = prev;
+      prev = act;
+
+      tmp = act->old_cp;
+      act->old_cp = act->new_cp;
+      act->new_cp = tmp;
+    }
+
+  return prev;
+}
+
+/* Commit changes in DELTA to IVS.  If FORWARD is false, the changes are
+   reverted instead.  */
+
+static void
+iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
+		    struct iv_ca_delta *delta, bool forward)
+{
+  struct cost_pair *from, *to;
+  struct iv_ca_delta *act;
+
+  if (!forward)
+    delta = iv_ca_delta_reverse (delta);
+
+  for (act = delta; act; act = act->next_change)
+    {
+      from = act->old_cp;
+      to = act->new_cp;
+      gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
+      iv_ca_set_cp (data, ivs, act->use, to);
+    }
+
+  if (!forward)
+    iv_ca_delta_reverse (delta);
+}
+
+/* Returns true if CAND is used in IVS.  */
+
+static bool
+iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
+{
+  return ivs->n_cand_uses[cand->id] > 0;
+}
+
+/* Returns number of induction variable candidates in the set IVS.  */
+
+static unsigned
+iv_ca_n_cands (struct iv_ca *ivs)
+{
+  return ivs->n_cands;
+}
+
+/* Free the list of changes DELTA.  */
+
+static void
+iv_ca_delta_free (struct iv_ca_delta **delta)
+{
+  struct iv_ca_delta *act, *next;
+
+  for (act = *delta; act; act = next)
+    {
+      next = act->next_change;
+      free (act);
+    }
+
+  *delta = NULL;
+}
+
+/* Allocates new iv candidates assignment.  */
+
+static struct iv_ca *
+iv_ca_new (struct ivopts_data *data)
+{
+  struct iv_ca *nw = XNEW (struct iv_ca);
+
+  nw->upto = 0;
+  nw->bad_uses = 0;
+  nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
+  nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
+  nw->cands = BITMAP_ALLOC (NULL);
+  nw->n_cands = 0;
+  nw->n_regs = 0;
+  nw->n_pseudos = 0;
+  nw->cand_use_cost = zero_cost;
+  nw->cand_cost = 0;
+  nw->n_invariant_uses = XCNEWVEC (unsigned,
+                                   data->min_pseudo_inv_id
+                                   + VEC_length (version_info_p,
+                                                 data->pseudo_version_info));
+  nw->cost = zero_cost;
+
+  return nw;
+}
+
+/* Free memory occupied by the set IVS.  */
+
+static void
+iv_ca_free (struct iv_ca **ivs)
+{
+  free ((*ivs)->cand_for_use);
+  free ((*ivs)->n_cand_uses);
+  BITMAP_FREE ((*ivs)->cands);
+  free ((*ivs)->n_invariant_uses);
+  free (*ivs);
+  *ivs = NULL;
+}
+
+/* Dumps IVS to FILE.  */
+
+static void
+iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
+{
+  const char *pref = "  invariants ";
+  unsigned i;
+  comp_cost cost = iv_ca_cost (ivs);
+
+  fprintf (file, "  cost: %d (complexity %d)\n", cost.cost, cost.complexity);
+  fprintf (file, "  cand_cost: %d\n  cand_use_cost: %d (complexity %d)\n",
+           ivs->cand_cost, ivs->cand_use_cost.cost, ivs->cand_use_cost.complexity);
+  bitmap_print (file, ivs->cands, "  candidates: ","\n");
+
+   for (i = 0; i < ivs->upto; i++)
+    {
+      struct iv_use *use = iv_use (data, i);
+      struct cost_pair *cp = iv_ca_cand_for_use (ivs, use);
+      if (cp)
+        fprintf (file, "   use:%d --> iv_cand:%d, cost=(%d,%d)\n",
+                 use->id, cp->cand->id, cp->cost.cost, cp->cost.complexity);
+      else
+        fprintf (file, "   use:%d --> ??\n", use->id);
+    }
+
+  for (i = 1; i <= data->max_inv_id; i++)
+    if (ivs->n_invariant_uses[i])
+      {
+	fprintf (file, "%s%d", pref, i);
+	pref = ", ";
+      }
+  fprintf (file, "\n\n");
+  fprintf (file, "nregs: %d\nnpseudos: %d\n\n",
+           ivs->n_regs, ivs->n_pseudos);
+}
+
+/* Try changing candidate in IVS to CAND for each use.  Return cost of the
+   new set, and store differences in DELTA.  Number of induction variables
+   in the new set is stored to N_IVS. if MIN_NCANDS is true, try to change
+   all candidates in IVS to CAND if possible.  */
+
+static comp_cost
+iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
+	      struct iv_cand *cand, struct iv_ca_delta **delta,
+	      unsigned *n_ivs, bool min_ncand)
+{
+  unsigned i;
+  comp_cost cost;
+  struct iv_use *use;
+  struct cost_pair *old_cp, *new_cp;
+
+  *delta = NULL;
+  for (i = 0; i < ivs->upto; i++)
+    {
+      use = iv_use (data, i);
+      old_cp = iv_ca_cand_for_use (ivs, use);
+
+      if (old_cp
+	  && old_cp->cand == cand)
+	continue;
+
+      new_cp = get_use_iv_cost (data, use, cand);
+      if (!new_cp)
+	continue;
+
+      if (!iv_ca_has_deps (ivs, new_cp))
+	continue;
+
+      if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp))
+        continue;
+
+      *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
+    }
+
+  iv_ca_delta_commit (data, ivs, *delta, true);
+  cost = iv_ca_cost (ivs);
+  if (n_ivs)
+    *n_ivs = iv_ca_n_cands (ivs);
+  iv_ca_delta_commit (data, ivs, *delta, false);
+
+  return cost;
+}
+
+/* Try narrowing set IVS by removing CAND.  Return the cost of
+   the new set and store the differences in DELTA.  */
+
+static comp_cost
+iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
+	      struct iv_cand *cand, struct iv_ca_delta **delta)
+{
+  unsigned i, ci;
+  struct iv_use *use;
+  struct cost_pair *old_cp, *new_cp, *cp;
+  bitmap_iterator bi;
+  struct iv_cand *cnd;
+  comp_cost cost;
+
+  *delta = NULL;
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+
+      old_cp = iv_ca_cand_for_use (ivs, use);
+      if (old_cp->cand != cand)
+	continue;
+
+      new_cp = NULL;
+
+      if (data->consider_all_candidates)
+	{
+	  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
+	    {
+	      if (ci == cand->id)
+		continue;
+
+	      cnd = iv_cand (data, ci);
+
+	      cp = get_use_iv_cost (data, use, cnd);
+	      if (!cp)
+		continue;
+	      if (!iv_ca_has_deps (ivs, cp))
+		continue;
+      
+	      if (!cheaper_cost_pair (cp, new_cp))
+		continue;
+
+	      new_cp = cp;
+	    }
+	}
+      else
+	{
+	  EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
+	    {
+	      if (ci == cand->id)
+		continue;
+
+	      cnd = iv_cand (data, ci);
+
+	      cp = get_use_iv_cost (data, use, cnd);
+	      if (!cp)
+		continue;
+	      if (!iv_ca_has_deps (ivs, cp))
+		continue;
+      
+	      if (!cheaper_cost_pair (cp, new_cp))
+		continue;
+
+	      new_cp = cp;
+	    }
+	}
+
+      if (!new_cp)
+	{
+	  iv_ca_delta_free (delta);
+	  return infinite_cost;
+	}
+
+      *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
+    }
+
+  iv_ca_delta_commit (data, ivs, *delta, true);
+  cost = iv_ca_cost (ivs);
+  iv_ca_delta_commit (data, ivs, *delta, false);
+
+  return cost;
+}
+
+/* Try optimizing the set of candidates IVS by removing candidates different
+   from to EXCEPT_CAND from it.  Return cost of the new set, and store
+   differences in DELTA.  */
+
+static comp_cost
+iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
+	     struct iv_cand *except_cand, struct iv_ca_delta **delta)
+{
+  bitmap_iterator bi;
+  struct iv_ca_delta *act_delta, *best_delta;
+  unsigned i;
+  comp_cost best_cost, acost;
+  struct iv_cand *cand;
+
+  best_delta = NULL;
+  best_cost = iv_ca_cost (ivs);
+
+  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+    {
+      cand = iv_cand (data, i);
+
+      if (cand == except_cand)
+	continue;
+
+      acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+
+      if (compare_costs (acost, best_cost) < 0)
+	{
+	  best_cost = acost;
+	  iv_ca_delta_free (&best_delta);
+	  best_delta = act_delta;
+	}
+      else
+	iv_ca_delta_free (&act_delta);
+    }
+
+  if (!best_delta)
+    {
+      *delta = NULL;
+      return best_cost;
+    }
+
+  /* Recurse to possibly remove other unnecessary ivs.  */
+  iv_ca_delta_commit (data, ivs, best_delta, true);
+  best_cost = iv_ca_prune (data, ivs, except_cand, delta);
+  iv_ca_delta_commit (data, ivs, best_delta, false);
+  *delta = iv_ca_delta_join (best_delta, *delta);
+  return best_cost;
+}
+
+/* Tries to extend the sets IVS in the best possible way in order
+   to express the USE.  */
+
+static bool
+try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
+		  struct iv_use *use)
+{
+  comp_cost best_cost, act_cost;
+  unsigned i;
+  bitmap_iterator bi;
+  struct iv_cand *cand;
+  struct iv_ca_delta *best_delta = NULL, *act_delta;
+  struct cost_pair *cp;
+
+  iv_ca_add_use (data, ivs, use);
+  best_cost = iv_ca_cost (ivs);
+
+  cp = iv_ca_cand_for_use (ivs, use);
+  if (cp)
+    {
+      best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
+      iv_ca_set_no_cp (data, ivs, use);
+    }
+
+  /* First try important candidates not based on any memory object.  Only if
+     this fails, try the specific ones.  Rationale -- in loops with many
+     variables the best choice often is to use just one generic biv.  If we
+     added here many ivs specific to the uses, the optimization algorithm later
+     would be likely to get stuck in a local minimum, thus causing us to create
+     too many ivs.  The approach from few ivs to more seems more likely to be
+     successful -- starting from few ivs, replacing an expensive use by a
+     specific iv should always be a win.  */
+  EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
+    {
+      cand = iv_cand (data, i);
+
+      if (cand->iv->base_object != NULL_TREE)
+	continue;
+
+      if (iv_ca_cand_used_p (ivs, cand))
+	continue;
+
+      cp = get_use_iv_cost (data, use, cand);
+      if (!cp)
+	continue;
+
+      iv_ca_set_cp (data, ivs, use, cp);
+      act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL,
+                               true);
+      iv_ca_set_no_cp (data, ivs, use);
+      act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
+
+      if (compare_costs (act_cost, best_cost) < 0)
+	{
+	  best_cost = act_cost;
+
+	  iv_ca_delta_free (&best_delta);
+	  best_delta = act_delta;
+	}
+      else
+	iv_ca_delta_free (&act_delta);
+    }
+
+  if (infinite_cost_p (best_cost))
+    {
+      for (i = 0; i < use->n_map_members; i++)
+	{
+	  cp = use->cost_map + i;
+	  cand = cp->cand;
+	  if (!cand)
+	    continue;
+
+	  /* Already tried this.  */
+	  if (cand->important && cand->iv->base_object == NULL_TREE)
+	    continue;
+      
+	  if (iv_ca_cand_used_p (ivs, cand))
+	    continue;
+
+	  act_delta = NULL;
+	  iv_ca_set_cp (data, ivs, use, cp);
+	  act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL, true);
+	  iv_ca_set_no_cp (data, ivs, use);
+	  act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
+				       cp, act_delta);
+
+	  if (compare_costs (act_cost, best_cost) < 0)
+	    {
+	      best_cost = act_cost;
+
+	      if (best_delta)
+		iv_ca_delta_free (&best_delta);
+	      best_delta = act_delta;
+	    }
+	  else
+	    iv_ca_delta_free (&act_delta);
+	}
+    }
+
+  iv_ca_delta_commit (data, ivs, best_delta, true);
+  iv_ca_delta_free (&best_delta);
+
+  return !infinite_cost_p (best_cost);
+}
+
+/* Finds an initial assignment of candidates to uses.  */
+
+static struct iv_ca *
+get_initial_solution (struct ivopts_data *data)
+{
+  struct iv_ca *ivs = iv_ca_new (data);
+  unsigned i;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    if (!try_add_cand_for (data, ivs, iv_use (data, i)))
+      {
+	iv_ca_free (&ivs);
+	return NULL;
+      }
+
+  return ivs;
+}
+
+/* Tries to improve set of induction variables IVS.  */
+
+static bool
+try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
+{
+  unsigned i, n_ivs;
+  comp_cost acost, best_cost = iv_ca_cost (ivs);
+  struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
+  struct iv_cand *cand;
+
+  /* Try extending the set of induction variables by one.  */
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      cand = iv_cand (data, i);
+      
+      if (iv_ca_cand_used_p (ivs, cand))
+	continue;
+
+      acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs, false);
+      if (!act_delta)
+	continue;
+
+      /* If we successfully added the candidate and the set is small enough,
+	 try optimizing it by removing other candidates.  */
+      if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
+      	{
+	  iv_ca_delta_commit (data, ivs, act_delta, true);
+	  acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
+	  iv_ca_delta_commit (data, ivs, act_delta, false);
+	  act_delta = iv_ca_delta_join (act_delta, tmp_delta);
+	}
+
+      if (compare_costs (acost, best_cost) < 0)
+	{
+	  best_cost = acost;
+	  iv_ca_delta_free (&best_delta);
+	  best_delta = act_delta;
+	}
+      else
+	iv_ca_delta_free (&act_delta);
+    }
+
+  if (!best_delta)
+    {
+      /* Try removing the candidates from the set instead.  */
+      best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
+
+      /* Nothing more we can do.  */
+      if (!best_delta)
+	return false;
+    }
+
+  iv_ca_delta_commit (data, ivs, best_delta, true);
+  gcc_assert (compare_costs (best_cost, iv_ca_cost (ivs)) == 0);
+  iv_ca_delta_free (&best_delta);
+  return true;
+}
+
+/* Attempts to find the optimal set of induction variables.  We do simple
+   greedy heuristic -- we try to replace at most one candidate in the selected
+   solution and remove the unused ivs while this improves the cost.  */
+
+static struct iv_ca *
+find_optimal_iv_set (struct ivopts_data *data)
+{
+  unsigned i;
+  struct iv_ca *set;
+  struct iv_use *use;
+
+  /* Get the initial solution.  */
+  set = get_initial_solution (data);
+  if (!set)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
+      return NULL;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Initial set of candidates:\n");
+      iv_ca_dump (data, dump_file, set);
+    }
+
+  while (try_improve_iv_set (data, set))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Improved to:\n");
+	  iv_ca_dump (data, dump_file, set);
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      comp_cost cost = iv_ca_cost (set);
+      fprintf (dump_file, "Final cost %d (complexity %d)\n\n", cost.cost, cost.complexity);
+    }
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+      use->selected = iv_ca_cand_for_use (set, use)->cand;
+    }
+
+  return set;
+}
+
+/* Returns a statement that undoes the operation in INCREMENT
+   on value OLD_VAL.  */
+
+static gimple
+get_inverted_increment_1 (gimple increment, tree old_val)
+{
+  tree new_assign_def;
+  gimple inverted_increment;
+  enum tree_code incr_op;
+  tree step;
+
+  new_assign_def = make_ssa_name (SSA_NAME_VAR (old_val), NULL);
+  step = unshare_expr (gimple_assign_rhs2 (increment));
+  incr_op = gimple_assign_rhs_code (increment);
+  if (incr_op == PLUS_EXPR)
+    incr_op = MINUS_EXPR;
+  else
+    {
+      gcc_assert (incr_op == MINUS_EXPR);
+      incr_op = PLUS_EXPR;
+    }
+  inverted_increment
+      = gimple_build_assign_with_ops (incr_op, new_assign_def,
+                                      old_val, step);
+
+  return inverted_increment;
+}
+
+/* Returns a statement that undos the operation in INCREMENT
+   on the result of phi NEW_PHI.  */
+
+static gimple
+get_inverted_increment (gimple reaching_increment, gimple new_phi)
+{
+  basic_block bb;
+  gimple_stmt_iterator gsi;
+  gimple inverted_increment;
+  tree phi_result;
+  void **slot;
+
+  gcc_assert (gimple_assign_lhs (reaching_increment)
+              == PHI_ARG_DEF (new_phi, 0));
+
+  if (!inverted_stmt_map)
+    inverted_stmt_map = pointer_map_create ();
+
+  slot = pointer_map_insert (inverted_stmt_map, new_phi);
+  if (*slot)
+    return (gimple) *slot;
+
+  phi_result = PHI_RESULT (new_phi);
+  bb = gimple_bb (new_phi);
+  gsi = gsi_after_labels (bb);
+
+  inverted_increment = get_inverted_increment_1 (reaching_increment,
+                                                 phi_result);
+  gsi_insert_before (&gsi, inverted_increment, GSI_NEW_STMT);
+  *slot = (void *) inverted_increment;
+  return inverted_increment;
+}
+
+/* Performs a peephole optimization to reorder the iv update statement with
+   a mem ref to enable instruction combining in later phases. The mem ref uses
+   the iv value before the update, so the reordering transformation requires
+   adjustment of the offset. CAND is the selected IV_CAND.
+
+   Example:
+
+   t = MEM_REF (base, iv1, 8, 16);  // base, index, stride, offset
+   iv2 = iv1 + 1;
+
+   if (t < val)      (1)
+     goto L;
+   goto Head;
+
+
+   directly propagating t over to (1) will introduce overlapping live range
+   thus increase register pressure. This peephole transform it into:
+
+
+   iv2 = iv1 + 1;
+   t = MEM_REF (base, iv2, 8, 8);
+   if (t < val)
+     goto L;
+   goto Head;
+*/
+
+static void
+adjust_iv_update_pos (struct ivopts_data *data ATTRIBUTE_UNUSED, struct iv_cand *cand)
+{
+  tree var_after, step, stride, index, offset_adjust, offset, mem_ref_op;
+  gimple iv_update, stmt, cond, mem_ref, index_to_base, use_stmt;
+  basic_block bb;
+  gimple_stmt_iterator gsi, gsi_iv;
+  use_operand_p use_p;
+  enum tree_code incr_op;
+  imm_use_iterator iter;
+  bool found = false;
+
+  var_after = cand->var_after;
+  iv_update = SSA_NAME_DEF_STMT (var_after);
+
+  /* Do not handle complicated iv update case.  */
+  incr_op = gimple_assign_rhs_code (iv_update);
+  if (incr_op != PLUS_EXPR && incr_op != MINUS_EXPR)
+    return;
+
+  step = gimple_assign_rhs2 (iv_update);
+  if (!CONSTANT_CLASS_P (step))
+    return;
+
+  bb = gimple_bb (iv_update);
+  gsi = gsi_last_bb (bb);
+  stmt = gsi_stmt (gsi);
+
+  /* Only handle conditional statement for now.  */
+  if (gimple_code (stmt) != GIMPLE_COND)
+    return;
+
+  cond = stmt;
+
+  gsi_prev (&gsi);
+  stmt = gsi_stmt (gsi);
+  if (stmt != iv_update)
+    return;
+
+  gsi_prev (&gsi);
+  if (gsi_end_p (gsi))
+    return;
+
+  stmt = gsi_stmt (gsi);
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return;
+
+  if (gimple_assign_rhs_code (stmt) != TARGET_MEM_REF)
+    return;
+
+  mem_ref = stmt;
+  mem_ref_op = gimple_assign_rhs1 (mem_ref);
+
+  if (TREE_CODE (gimple_assign_lhs (mem_ref)) != SSA_NAME)
+    return;
+
+  if (!single_imm_use (gimple_assign_lhs (mem_ref), &use_p, &use_stmt))
+    return;
+
+  if (use_stmt != cond)
+    return;
+
+  /* Found code motion candidate -- the statement with mem_ref.  */
+
+  index = TMR_INDEX (mem_ref_op);
+  index_to_base = NULL;
+  if (index)
+    {
+      if (index != cand->var_before)
+        return;
+    }
+  else
+    {
+      /* Index used as base.  */
+      tree base = TMR_BASE (mem_ref_op);
+
+      if (TREE_CODE (base) != SSA_NAME)
+        return;
+
+      if (!has_single_use (base))
+        return;
+
+      index_to_base = SSA_NAME_DEF_STMT (base);
+      if (gimple_code (index_to_base) != GIMPLE_ASSIGN)
+        return;
+      if (gimple_assign_rhs_code (index_to_base) != NOP_EXPR)
+        return;
+      if (gimple_assign_rhs1 (index_to_base) != cand->var_before)
+        return;
+    }
+
+  stride = TMR_STEP (mem_ref_op);
+  offset = TMR_OFFSET (mem_ref_op);
+  if (stride && index)
+    offset_adjust = int_const_binop (MULT_EXPR, stride, step, 0);
+  else
+    offset_adjust = step;
+
+  if (offset_adjust == NULL)
+    return;
+
+  offset = int_const_binop ((incr_op == PLUS_EXPR
+                             ? MINUS_EXPR : PLUS_EXPR),
+                            (offset ? offset : integer_zero_node),
+                            offset_adjust, 0);
+
+  if (offset == NULL)
+    return;
+
+  if (index_to_base)
+    gsi = gsi_for_stmt (index_to_base);
+  else
+    gsi = gsi_for_stmt (mem_ref);
+  gsi_iv = gsi_for_stmt (iv_update);
+  gsi_move_before (&gsi_iv, &gsi);
+
+  /* Now fix up the mem_ref.  */
+  FOR_EACH_IMM_USE_FAST (use_p, iter, cand->var_before)
+    {
+      if (USE_STMT (use_p) == mem_ref || USE_STMT (use_p) == index_to_base)
+        {
+          set_ssa_use_from_ptr (use_p, var_after);
+          if (index_to_base)
+            *gimple_assign_rhs1_ptr (index_to_base) = var_after;
+          else
+            TMR_INDEX (mem_ref_op) = var_after;
+
+          found = true;
+          break;
+        }
+    }
+  gcc_assert (found);
+  TMR_OFFSET (mem_ref_op) = offset;
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Reordering \n");
+      print_gimple_stmt (dump_file, iv_update, 0, 0);
+      print_gimple_stmt (dump_file, mem_ref, 0, 0);
+      fprintf (dump_file, "\n");
+    }
+}
+
+/* Performs reordering peep hole optimization for all selected ivs in SET.  */
+
+static void
+adjust_update_pos_for_ivs (struct ivopts_data *data, struct iv_ca *set)
+{
+  unsigned i;
+  struct iv_cand *cand;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
+    {
+      cand = iv_cand (data, i);
+      adjust_iv_update_pos (data, cand);
+    }
+}
+
+/* Creates a new induction variable corresponding to CAND.  */
+
+static void
+create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
+{
+  gimple_stmt_iterator incr_pos;
+  tree base;
+  bool after = false;
+
+  if (!cand->iv)
+    return;
+
+  switch (cand->pos)
+    {
+    case IP_NORMAL:
+      incr_pos = gsi_last_bb (ip_normal_pos (data->current_loop));
+      break;
+
+    case IP_END:
+      incr_pos = gsi_last_bb (ip_end_pos (data->current_loop));
+      after = true;
+      break;
+
+    case IP_ORIGINAL:
+      /* Mark that the iv is preserved.  */
+      name_info (data, cand->var_before)->preserve_biv = true;
+      name_info (data, cand->var_after)->preserve_biv = true;
+
+      /* Rewrite the increment so that it uses var_before directly.  */
+      find_interesting_uses_op (data, cand->var_after,
+                                IU_INSIDE_LOOP)->selected = cand;
+
+      return;
+    }
+ 
+  gimple_add_tmp_var (cand->var_before);
+  add_referenced_var (cand->var_before);
+
+  base = unshare_expr (cand->iv->base);
+
+  create_iv (base, unshare_expr (cand->iv->step),
+	     cand->var_before, data->current_loop,
+	     &incr_pos, after, &cand->var_before, &cand->var_after);
+}
+
+/* Creates new induction variables described in SET.  */
+
+static void
+create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
+{
+  unsigned i;
+  struct iv_cand *cand;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
+    {
+      cand = iv_cand (data, i);
+      create_new_iv (data, cand);
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "\nSelected IV set: \n");
+      EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
+        {
+          cand = iv_cand (data, i);
+          dump_cand (dump_file, cand);
+        }
+      fprintf (dump_file, "\n");
+    }
+}
+
+/* Callback function in the tree walk to fix up old live out
+   names to loop exit phi's result.  */
+
+static tree
+fixup_use (tree *op,
+           int *unused ATTRIBUTE_UNUSED,
+           void *data)
+{
+  struct pointer_map_t *nm_to_def_map
+      = (struct pointer_map_t *) data;
+
+  if (TREE_CODE (*op) == SSA_NAME && is_gimple_reg (*op))
+    {
+      void **slot;
+      slot = pointer_map_contains (nm_to_def_map, *op);
+      if (slot)
+        {
+          enum gimple_code gc;
+          gimple def = (gimple) (*slot);
+          gc = gimple_code (def);
+          if (gc == GIMPLE_PHI)
+            *op = PHI_RESULT (def);
+          else
+            *op = gimple_assign_lhs (def);
+        }
+    }
+
+  return 0;
+}
+
+/* Callback function in the tree walk to collect used ssa names
+   in the tree.  */
+
+static tree
+collect_ssa_names (tree *op,
+                   int *unused ATTRIBUTE_UNUSED,
+                   void *data)
+{
+  VEC(tree, heap) ** used_names = (VEC(tree, heap) **) data;
+  if (TREE_CODE (*op) == SSA_NAME && is_gimple_reg (*op))
+    VEC_safe_push (tree, heap, *used_names, *op);
+
+  return 0;
+}
+
+
+/* The function fixes up live out ssa names used in tree *VAL to
+   the matching loop exit phi's results. */
+
+static void
+fixup_iv_out_val (tree *val, struct pointer_map_t *nm_to_phi_map)
+{
+  walk_tree (val, fixup_use, nm_to_phi_map, NULL);
+}
+
+/* Returns the iv update statement if USE's cand variable is
+   the version before the update; otherwise returns NULL.  */
+
+static gimple
+cause_overlapping_lr (struct ivopts_data *data,
+                      tree nm_used, struct iv_use *use,
+                      basic_block use_bb)
+{
+  tree selected_iv_nm;
+  edge e;
+  gimple increment;
+  enum tree_code incr_op;
+
+  selected_iv_nm = var_at_stmt (data->current_loop,
+                                use->selected,
+                                use->stmt);
+
+  if (nm_used != selected_iv_nm)
+    return NULL;
+
+  if (selected_iv_nm == use->selected->var_after)
+    return NULL;
+
+  /* Check if def of var_after reaches use_bb.  */
+  gcc_assert (single_pred_p (use_bb));
+  e = single_pred_edge (use_bb);
+
+  increment = SSA_NAME_DEF_STMT (use->selected->var_after);
+
+  if (e->src != gimple_bb (increment))
+    return NULL;
+
+  /* Only handle simple increments  */
+  if (gimple_code (increment) != GIMPLE_ASSIGN)
+    return NULL;
+
+  incr_op = gimple_assign_rhs_code (increment);
+  if (incr_op != PLUS_EXPR && incr_op != MINUS_EXPR)
+    return NULL;
+
+  if (!CONSTANT_CLASS_P (gimple_assign_rhs2 (increment)))
+    return NULL;
+
+  return increment;
+}
+
+/* Returns the loop closing phi for LIVE_OUT_IV in basic block TGT_BB.
+   IV_UPDATE_STMT is the update statement for LIVE_OUT_IV, and
+   *FOR_UPDATED_VAL is set to true if the argument of the phi is defined
+   by IV_UPDATE_STMT.  */
+
+static gimple
+find_closing_phi (basic_block tgt_bb, tree live_out_iv,
+                  gimple iv_update_stmt, bool *for_updated_val)
+{
+  gimple_stmt_iterator psi;
+  gimple phi = NULL;
+
+  *for_updated_val = false;
+
+  /* Now try to find the existing matching phi.  */
+  for (psi = gsi_start_phis (tgt_bb); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      gimple p;
+      p = gsi_stmt (psi);
+
+      if (SSA_NAME_VAR (PHI_ARG_DEF (p, 0))
+          == SSA_NAME_VAR (live_out_iv))
+        {
+          phi = p;
+          break;
+        }
+    }
+
+  if (!phi)
+    return NULL;
+
+  if (PHI_ARG_DEF (phi, 0) == live_out_iv)
+    {
+      *for_updated_val = false;
+      /* Found exact match.  */
+      return phi;
+    }
+  else if (iv_update_stmt &&
+           PHI_ARG_DEF (phi, 0) == gimple_assign_lhs (iv_update_stmt))
+    {
+      *for_updated_val = true;
+      return phi;
+    }
+
+  return NULL;
+}
+
+
+/* The function ensures closed SSA form for moving use statement from USE
+   across the loop exit. LIVE_OUT_NM is the original ssa name that is live out,
+   TGT_BB is the destination bb of the code motion, and NM_TO_DEF_MAP maps
+   the original name to the result of the closing phi.
+
+   Scenario 1:
+   ----------------
+   Loop:
+
+   Loop_exit:
+
+     closed_iv_val = PHI (live_out_iv)
+
+     Uses of (live_out_iv) get replaced with closed_iv_val
+
+
+
+   Scenario 2:
+   ----------------
+   Loop:
+
+     updated_iv_val = live_out_iv + 1
+   Loop_exit:
+
+     closed_iv_val = PHI (updated_iv_val)
+     updated_iv_val2 = closed_iv_val - 1
+
+     Uses of live_out_iv get replaced with updated_iv_val2
+*/
+
+static gimple
+ensure_closed_ssa_form_for (struct ivopts_data *data,
+                            tree live_out_nm, basic_block tgt_bb,
+                            struct iv_use *use,
+                            struct pointer_map_t *nm_to_def_map)
+{
+  gimple closing_phi = NULL;
+  bool closing_phi_for_updated_val = false;
+
+  gimple def_stmt, new_def_stmt = NULL;
+  basic_block def_bb;
+  gimple iv_update_stmt;
+  void **slot;
+
+  def_stmt = SSA_NAME_DEF_STMT (live_out_nm);
+  def_bb = gimple_bb (def_stmt);
+
+  if (!def_bb
+      || flow_bb_inside_loop_p (def_bb->loop_father, tgt_bb))
+    return NULL;;
+
+  iv_update_stmt
+      = cause_overlapping_lr (data, live_out_nm, use, tgt_bb);
+
+  gcc_assert (!iv_update_stmt ||
+              gimple_code (iv_update_stmt) == GIMPLE_ASSIGN);
+
+  closing_phi = find_closing_phi (tgt_bb, live_out_nm,
+                                  iv_update_stmt, &closing_phi_for_updated_val);
+
+
+  /* No closing phi is found.  */
+  if (!closing_phi)
+    {
+      edge e;
+      edge_iterator ei;
+
+      closing_phi = create_phi_node (live_out_nm, tgt_bb);
+      create_new_def_for (gimple_phi_result (closing_phi), closing_phi,
+                          gimple_phi_result_ptr (closing_phi));
+      gcc_assert (single_pred_p (tgt_bb));
+      if (!iv_update_stmt)
+        {
+          FOR_EACH_EDGE (e, ei, tgt_bb->preds)
+            add_phi_arg (closing_phi, live_out_nm, e, UNKNOWN_LOCATION);
+          new_def_stmt = closing_phi;
+        }
+      else
+        {
+          FOR_EACH_EDGE (e, ei, tgt_bb->preds)
+            add_phi_arg (closing_phi, gimple_assign_lhs (iv_update_stmt),
+                         e, UNKNOWN_LOCATION);
+          /* Now make the value adjustment.  */
+          new_def_stmt = get_inverted_increment (iv_update_stmt, closing_phi);
+        }
+    }
+  else if (!closing_phi_for_updated_val)
+    /* Scenario 1 above.  */
+    new_def_stmt = closing_phi;
+  else
+    {
+      /* Scenario 2 above.  */
+      gcc_assert (iv_update_stmt);
+      new_def_stmt = get_inverted_increment (iv_update_stmt, closing_phi);
+    }
+
+  /* Now map it.  */
+  slot = pointer_map_insert (nm_to_def_map, live_out_nm);
+  *slot = (void *) new_def_stmt;
+
+  return (new_def_stmt != closing_phi ? new_def_stmt : NULL);
+}
+
+/* The function ensures closed ssa form for all names used in
+   REPLACED_IV_OUT_VAL. TGT_BB is the target bb where the new
+   computation is going to be, USE is the nonlinear use to be
+   rewritten (at loop exits), and *FIXED_UP_VAL holds the live out
+   value after name fixup. It returns the inverted iv update
+   statement if it is created.  */
+
+static gimple
+ensure_closed_ssa_form (struct ivopts_data *data,
+                        basic_block tgt_bb,
+                        struct iv_use *use,
+                        tree replaced_iv_out_val,
+                        tree *fixed_up_val)
+{
+  unsigned i;
+  tree nm;
+  VEC(tree, heap) *used_ssa_names = NULL;
+  struct pointer_map_t *nm_to_def_map = NULL;
+  gimple inverted_incr = NULL;
+
+  nm_to_def_map = pointer_map_create ();
+  *fixed_up_val = unshare_expr (replaced_iv_out_val);
+  walk_tree_without_duplicates (fixed_up_val,
+                                collect_ssa_names, &used_ssa_names);
+
+  for (i = 0;
+       VEC_iterate (tree, used_ssa_names, i, nm); i++)
+    {
+      gimple inv_incr;
+      if ((inv_incr
+           = ensure_closed_ssa_form_for (data, nm, tgt_bb,
+                                         use, nm_to_def_map)))
+        {
+          gcc_assert (!inverted_incr);
+          inverted_incr = inv_incr;
+        }
+    }
+
+  /* Now fix up the references in val.  */
+  fixup_iv_out_val (fixed_up_val, nm_to_def_map);
+  pointer_map_destroy (nm_to_def_map);
+  return inverted_incr;
+}
+
+/* The function returns true if it is possible to sink final value
+   computation for REPLACED_IV_OUT_NAME at loop exits.  */
+
+static bool
+can_compute_final_value_at_exits_p (struct ivopts_data *data,
+                                    tree replaced_iv_out_name)
+{
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  gimple use_stmt;
+
+  /* Walk through all nonlinear uses in all loop exit blocks
+     to see if the sinking transformation is doable.  */
+
+  FOR_EACH_IMM_USE_FAST (use_p, iter, replaced_iv_out_name)
+    {
+      basic_block exit_bb;
+      edge e;
+      edge_iterator ei;
+      bool found_exit_edge = false;
+
+      use_stmt = USE_STMT (use_p);
+      exit_bb = gimple_bb (use_stmt);
+
+      /* The use_stmt is another iv update
+         statement that also defines a liveout value and
+         has been removed.  */
+      if (!exit_bb)
+        continue;
+
+      if (flow_bb_inside_loop_p (data->current_loop, exit_bb))
+        continue;
+
+      if (single_pred_p (exit_bb))
+        continue;
+
+      FOR_EACH_EDGE (e, ei, exit_bb->preds)
+        {
+          if (!flow_bb_inside_loop_p (data->current_loop,
+                                      e->src))
+            continue;
+          /* Can not split the edge.  */
+          if (e->flags & EDGE_ABNORMAL)
+            return false;
+
+          /* Do not handle the case where the exit bb has
+             multiple incoming exit edges from the same loop.  */
+          if (found_exit_edge)
+            return false;
+
+          found_exit_edge = true;
+        }
+      if (!found_exit_edge)
+        return false;
+    }
+  return true;
+}
+
+/* The function splits the loop exit edge targeting EXIT_BB if EXIT_BB
+    and returns the newly split bb.  REPLACED_IV_OUT_NAME is the original
+    ssa name that is live out, and the new use statement (new phi) will
+    be stored in *USE_STMT.  */
+
+static basic_block
+split_exit_edge (struct ivopts_data* data, basic_block exit_bb,
+                 tree replaced_iv_out_name, gimple *use_stmt)
+{
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, exit_bb->preds)
+    {
+      edge exit_edge;
+      gimple_stmt_iterator psi;
+      gimple new_use_phi = NULL;
+
+      if (!flow_bb_inside_loop_p (data->current_loop, e->src))
+        continue;
+
+      gcc_assert (!(e->flags & EDGE_ABNORMAL));
+      exit_bb = split_loop_exit_edge (e);
+      exit_edge = single_pred_edge (exit_bb);
+
+      /* Now update the use stmt.  */
+      for (psi = gsi_start_phis (exit_bb);
+           !gsi_end_p (psi); gsi_next (&psi))
+        {
+          tree phi_arg;
+          gimple new_phi = gsi_stmt (psi);
+
+          phi_arg
+              = PHI_ARG_DEF_FROM_EDGE (new_phi, exit_edge);
+          if (phi_arg == replaced_iv_out_name)
+            {
+              new_use_phi = new_phi;
+              break;
+            }
+        }
+      gcc_assert (new_use_phi);
+      *use_stmt = new_use_phi;
+
+      /* There is only one exit edge to split.  */
+      break;
+    }
+
+  return exit_bb;
+}
+
+/* For a non linear use USE that is used outside the loop DATA->current_loop
+   only, try to evaluate the live out value at the exits of the loop.
+   REPLACED_IV_OUT_NAME is the original ssa name that is live out, and
+   REPLACED_IV_OUT_VAL is the expression (in terms of the selected iv cand)
+   to evaluate the live out value. The function tries to sink the computation
+   of replaced_iv_out_val into loop exits, and returns true if successful.  */
+
+static bool
+compute_final_value_at_exits (struct ivopts_data *data,
+                              struct iv_use *use,
+                              tree replaced_iv_out_name,
+                              tree replaced_iv_out_val)
+{
+  imm_use_iterator iter;
+  gimple use_stmt;
+  struct iv* replaced_iv;
+
+  if (!can_compute_final_value_at_exits_p (data, replaced_iv_out_name))
+    return false;
+
+  FOR_EACH_IMM_USE_STMT (use_stmt, iter, replaced_iv_out_name)
+    {
+      basic_block exit_bb;
+      gimple new_assign;
+      gimple_stmt_iterator gsi, bsi;
+      tree phi_rslt, new_assign_rhs;
+      tree fixed_up_val;
+      gimple inverted_increment;
+
+      exit_bb = gimple_bb (use_stmt);
+
+      /* The use_stmt is another iv update
+         statement that also defines a liveout value and
+         has been removed.  */
+      if (!exit_bb)
+        continue;
+
+      if (flow_bb_inside_loop_p (data->current_loop, exit_bb))
+        continue;
+
+      if (!single_pred_p (exit_bb))
+        exit_bb = split_exit_edge (data, exit_bb,
+                                   replaced_iv_out_name, &use_stmt);
+
+      gcc_assert (single_pred_p (exit_bb));
+
+      inverted_increment
+          = ensure_closed_ssa_form (data, exit_bb, use,
+                                    replaced_iv_out_val,
+                                    &fixed_up_val);
+
+      gcc_assert (gimple_code (use_stmt) == GIMPLE_PHI);
+      gsi = gsi_for_stmt (use_stmt);
+      phi_rslt = PHI_RESULT (use_stmt);
+      bsi = (inverted_increment
+             ? gsi_for_stmt (inverted_increment)
+             : gsi_after_labels (exit_bb));
+
+      /* Now convert the original loop exit phi (for closed SSA form)
+         into an assignment statement.  */
+      remove_phi_node (&gsi, false);
+      new_assign_rhs = force_gimple_operand_gsi (&bsi, fixed_up_val,
+                                                 false, NULL_TREE,
+                                                 (inverted_increment == NULL),
+                                                 (inverted_increment == NULL
+                                                  ? GSI_SAME_STMT
+                                                  : GSI_CONTINUE_LINKING));
+      new_assign = gimple_build_assign (phi_rslt, new_assign_rhs);
+      if (inverted_increment)
+        gsi_insert_after (&bsi, new_assign, GSI_SAME_STMT);
+      else
+        gsi_insert_before (&bsi, new_assign, GSI_SAME_STMT);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+        {
+          fprintf (dump_file, "Sinking computation into exit bb %d\n",
+                   exit_bb->index);
+          print_gimple_stmt (dump_file, new_assign, 0, 0);
+          fprintf (dump_file, "\n");
+	}
+    }
+
+  /* Now the original stmt that defines the liveout value can be removed */
+
+  replaced_iv = get_iv (data, replaced_iv_out_name);
+  gcc_assert (replaced_iv);
+  replaced_iv->have_use_for = false;
+
+  return true;
+}
+
+/* Returns the phi-node in BB with result RESULT.  */
+
+static gimple
+get_phi_with_result (basic_block bb, tree result)
+{
+  gimple_stmt_iterator i = gsi_start_phis (bb);
+
+  for (; !gsi_end_p (i); gsi_next (&i))
+    if (gimple_phi_result (gsi_stmt (i)) == result)
+      return gsi_stmt (i);
+
+  gcc_unreachable ();
+  return NULL;
+}
+
+
+/* Removes statement STMT (real or a phi node).  If INCLUDING_DEFINED_NAME
+   is true, remove also the ssa name defined by the statement.  */
+
+static void
+remove_statement (gimple stmt, bool including_defined_name)
+{
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    {
+      gimple bb_phi = get_phi_with_result (gimple_bb (stmt), 
+					 gimple_phi_result (stmt));
+      gimple_stmt_iterator bsi = gsi_for_stmt (bb_phi);
+      remove_phi_node (&bsi, including_defined_name);
+    }
+  else
+    {
+      gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
+      gsi_remove (&bsi, true);
+      release_defs (stmt); 
+    }
+}
+
+/* Rewrites USE (definition of iv used in a nonlinear expression)
+   using candidate CAND.  */
+
+static void
+rewrite_use_nonlinear_expr (struct ivopts_data *data,
+			    struct iv_use *use, struct iv_cand *cand)
+{
+  tree comp;
+  tree op, tgt;
+  gimple ass;
+  gimple_stmt_iterator bsi;
+
+  /* An important special case -- if we are asked to express value of
+     the original iv by itself, just exit; there is no need to
+     introduce a new computation (that might also need casting the
+     variable to unsigned and back).  */
+  if (cand->pos == IP_ORIGINAL
+      && cand->incremented_at == use->stmt)
+    {
+      tree step, ctype, utype;
+      enum tree_code incr_code = PLUS_EXPR, old_code;
+
+      gcc_assert (is_gimple_assign (use->stmt));
+      gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
+
+      step = cand->iv->step;
+      ctype = TREE_TYPE (step);
+      utype = TREE_TYPE (cand->var_after);
+      if (TREE_CODE (step) == NEGATE_EXPR)
+	{
+	  incr_code = MINUS_EXPR;
+	  step = TREE_OPERAND (step, 0);
+	}
+
+      /* Check whether we may leave the computation unchanged.
+	 This is the case only if it does not rely on other
+	 computations in the loop -- otherwise, the computation
+	 we rely upon may be removed in remove_unused_ivs,
+	 thus leading to ICE.  */
+      old_code = gimple_assign_rhs_code (use->stmt);
+      if (old_code == PLUS_EXPR
+	  || old_code == MINUS_EXPR
+	  || old_code == POINTER_PLUS_EXPR)
+	{
+	  if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
+	    op = gimple_assign_rhs2 (use->stmt);
+	  else if (old_code != MINUS_EXPR
+		   && gimple_assign_rhs2 (use->stmt) == cand->var_before)
+	    op = gimple_assign_rhs1 (use->stmt);
+	  else
+	    op = NULL_TREE;
+	}
+      else
+	op = NULL_TREE;
+
+      if (op
+	  && (TREE_CODE (op) == INTEGER_CST
+	      || operand_equal_p (op, step, 0)))
+	return;
+
+      /* Otherwise, add the necessary computations to express
+	 the iv.  */
+      op = fold_convert (ctype, cand->var_before);
+      comp = fold_convert (utype,
+			   build2 (incr_code, ctype, op,
+				   unshare_expr (step)));
+    }
+  else
+    {
+      comp = get_computation (data->current_loop, use, cand);
+      gcc_assert (comp != NULL_TREE);
+    }
+
+  switch (gimple_code (use->stmt))
+    {
+    case GIMPLE_PHI:
+      tgt = PHI_RESULT (use->stmt);
+
+      /* If we should keep the biv, do not replace it.  */
+      if (name_info (data, tgt)->preserve_biv)
+	return;
+
+      bsi = gsi_after_labels (gimple_bb (use->stmt));
+      break;
+
+    case GIMPLE_ASSIGN:
+      tgt = gimple_assign_lhs (use->stmt);
+      bsi = gsi_for_stmt (use->stmt);
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  if (use->use_pos == IU_OUTSIDE_LOOP_ONLY)
+    {
+      if (compute_final_value_at_exits (data, use, tgt, comp))
+        return;
+    }
+  op = force_gimple_operand_gsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
+				 true, GSI_SAME_STMT);
+
+  if (gimple_code (use->stmt) == GIMPLE_PHI)
+    {
+      ass = gimple_build_assign (tgt, op);
+      gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
+      remove_statement (use->stmt, false);
+    }
+  else
+    {
+      gimple_assign_set_rhs_from_tree (&bsi, op);
+      use->stmt = gsi_stmt (bsi);
+    }
+}
+
+/* Replaces ssa name in index IDX by its basic variable.  Callback for
+   for_each_index.  */
+
+static bool
+idx_remove_ssa_names (tree base, tree *idx,
+		      void *data ATTRIBUTE_UNUSED)
+{
+  tree *op;
+
+  if (TREE_CODE (*idx) == SSA_NAME)
+    *idx = SSA_NAME_VAR (*idx);
+
+  if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
+    {
+      op = &TREE_OPERAND (base, 2);
+      if (*op
+	  && TREE_CODE (*op) == SSA_NAME)
+	*op = SSA_NAME_VAR (*op);
+      op = &TREE_OPERAND (base, 3);
+      if (*op
+	  && TREE_CODE (*op) == SSA_NAME)
+	*op = SSA_NAME_VAR (*op);
+    }
+
+  return true;
+}
+
+/* Unshares REF and replaces ssa names inside it by their basic variables.  */
+
+static tree
+unshare_and_remove_ssa_names (tree ref)
+{
+  ref = unshare_expr (ref);
+  for_each_index (&ref, idx_remove_ssa_names, NULL);
+
+  return ref;
+}
+
+/* Extract the alias analysis info for the memory reference REF.  There are
+   several ways how this information may be stored and what precisely is
+   its semantics depending on the type of the reference, but there always is
+   somewhere hidden one _DECL node that is used to determine the set of
+   virtual operands for the reference.  The code below deciphers this jungle
+   and extracts this single useful piece of information.  */
+
+static tree
+get_ref_tag (tree ref, tree orig)
+{
+  tree var = get_base_address (ref);
+  tree aref = NULL_TREE, tag, sv;
+  HOST_WIDE_INT offset, size, maxsize;
+
+  for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
+    {
+      aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
+      if (ref)
+	break;
+    }
+
+  if (!var)
+    return NULL_TREE;
+
+  if (TREE_CODE (var) == INDIRECT_REF)
+    {
+      /* If the base is a dereference of a pointer, first check its name memory
+	 tag.  If it does not have one, use its symbol memory tag.  */
+      var = TREE_OPERAND (var, 0);
+      if (TREE_CODE (var) != SSA_NAME)
+	return NULL_TREE;
+
+      if (SSA_NAME_PTR_INFO (var))
+	{
+	  tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
+	  if (tag)
+	    return tag;
+	}
+ 
+      var = SSA_NAME_VAR (var);
+      tag = symbol_mem_tag (var);
+      gcc_assert (tag != NULL_TREE);
+      return tag;
+    }
+  else
+    { 
+      if (!DECL_P (var))
+	return NULL_TREE;
+
+      tag = symbol_mem_tag (var);
+      if (tag)
+	return tag;
+
+      return var;
+    }
+}
+
+/* Copies the reference information from OLD_REF to NEW_REF.  */
+
+static void
+copy_ref_info (tree new_ref, tree old_ref)
+{
+  if (TREE_CODE (old_ref) == TARGET_MEM_REF)
+    copy_mem_ref_info (new_ref, old_ref);
+  else
+    {
+      TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
+      TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
+    }
+}
+
+/* Rewrites USE (address that is an iv) using candidate CAND.  */
+
+static void
+rewrite_use_address (struct ivopts_data *data,
+		     struct iv_use *use, struct iv_cand *cand)
+{
+  aff_tree aff;
+  gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+  tree ref, iv;
+  bool ok;
+
+  ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
+  gcc_assert (ok);
+  unshare_aff_combination (&aff);
+
+  iv = var_at_stmt (data->current_loop, cand, use->stmt);
+  ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff,
+                        iv, (cand->iv->base_object != NULL), data->speed);
+  copy_ref_info (ref, *use->op_p);
+  *use->op_p = ref;
+}
+
+/* Rewrites USE (the condition such that one of the arguments is an iv) using
+   candidate CAND.  */
+
+static void
+rewrite_use_compare (struct ivopts_data *data,
+		     struct iv_use *use, struct iv_cand *cand)
+{
+  tree comp, *var_p, op, bound;
+  gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+  enum tree_code compare;
+  struct cost_pair *cp = get_use_iv_cost (data, use, cand);
+  bool ok;
+
+  bound = cp->value;
+  if (bound)
+    {
+      tree var = var_at_stmt (data->current_loop, cand, use->stmt);
+      tree var_type = TREE_TYPE (var);
+      gimple_seq stmts;
+
+      compare = iv_elimination_compare (data, use);
+      bound = unshare_expr (fold_convert (var_type, bound));
+      op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
+      if (stmts)
+	gsi_insert_seq_on_edge_immediate (
+		loop_preheader_edge (data->current_loop),
+		stmts);
+
+      gimple_cond_set_lhs (use->stmt, var);
+      gimple_cond_set_code (use->stmt, compare);
+      gimple_cond_set_rhs (use->stmt, op);
+      return;
+    }
+
+  /* The induction variable elimination failed; just express the original
+     giv.  */
+  comp = get_computation (data->current_loop, use, cand);
+  gcc_assert (comp != NULL_TREE);
+
+  ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
+  gcc_assert (ok);
+
+  *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
+				     true, GSI_SAME_STMT);
+}
+
+/* Rewrites USE using candidate CAND.  */
+
+static void
+rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
+{
+  push_stmt_changes (&use->stmt);
+
+  switch (use->type)
+    {
+      case USE_NONLINEAR_EXPR:
+	rewrite_use_nonlinear_expr (data, use, cand);
+	break;
+
+      case USE_ADDRESS:
+	rewrite_use_address (data, use, cand);
+	break;
+
+      case USE_COMPARE:
+	rewrite_use_compare (data, use, cand);
+	break;
+
+      default:
+	gcc_unreachable ();
+    }
+
+  pop_stmt_changes (&use->stmt);
+}
+
+/* Rewrite the uses using the selected induction variables.  */
+
+static void
+rewrite_uses (struct ivopts_data *data)
+{
+  unsigned i;
+  struct iv_cand *cand;
+  struct iv_use *use;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+      cand = use->selected;
+      gcc_assert (cand);
+
+      rewrite_use (data, use, cand);
+    }
+}
+
+/* Removes the ivs that are not used after rewriting.  */
+
+static void
+remove_unused_ivs (struct ivopts_data *data)
+{
+  unsigned j;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
+    {
+      struct version_info *info;
+
+      info = ver_info (data, j);
+      if (info->iv
+	  && !integer_zerop (info->iv->step)
+	  && !info->inv_id
+	  && !info->iv->have_use_for
+	  && !info->preserve_biv)
+	remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
+    }
+}
+
+/* Frees data allocated by the optimization of a single loop.  */
+
+static void
+free_loop_data (struct ivopts_data *data)
+{
+  unsigned i, j;
+  bitmap_iterator bi;
+  tree obj;
+  struct version_info *vi;
+
+  if (data->niters)
+    {
+      pointer_map_destroy (data->niters);
+      data->niters = NULL;
+    }
+
+  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
+    {
+      struct version_info *info;
+
+      info = ver_info (data, i);
+      if (info->iv)
+	free (info->iv);
+      info->iv = NULL;
+      info->has_nonlin_use = false;
+      info->preserve_biv = false;
+      info->inv_id = 0;
+    }
+  bitmap_clear (data->relevant);
+  bitmap_clear (data->important_candidates);
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      struct iv_use *use = iv_use (data, i);
+
+      free (use->iv);
+      BITMAP_FREE (use->related_cands);
+      for (j = 0; j < use->n_map_members; j++)
+	if (use->cost_map[j].depends_on)
+	  BITMAP_FREE (use->cost_map[j].depends_on);
+      free (use->cost_map);
+      free (use);
+    }
+  VEC_truncate (iv_use_p, data->iv_uses, 0);
+
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      struct iv_cand *cand = iv_cand (data, i);
+
+      if (cand->iv)
+	free (cand->iv);
+      if (cand->depends_on)
+	BITMAP_FREE (cand->depends_on);
+      free (cand);
+    }
+  VEC_truncate (iv_cand_p, data->iv_candidates, 0);
+
+  if (data->version_info_size < num_ssa_names)
+    {
+      data->version_info_size = 2 * num_ssa_names;
+      free (data->version_info);
+      data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
+    }
+
+  data->max_inv_id = 0;
+
+  for (i = 0; VEC_iterate (version_info_p,
+                           data->pseudo_version_info, i, vi); i++)
+    free (vi);
+  VEC_truncate (version_info_p, data->pseudo_version_info, 0);
+  data->min_pseudo_inv_id = num_ssa_names;
+
+
+  for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
+    SET_DECL_RTL (obj, NULL_RTX);
+
+  VEC_truncate (tree, decl_rtl_to_reset, 0);
+}
+
+/* Finalizes data structures used by the iv optimization pass.  LOOPS is the
+   loop tree.  */
+
+static void
+tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
+{
+  free_loop_data (data);
+  free (data->version_info);
+  BITMAP_FREE (data->relevant);
+  BITMAP_FREE (data->important_candidates);
+
+  VEC_free (tree, heap, decl_rtl_to_reset);
+  VEC_free (iv_use_p, heap, data->iv_uses);
+  VEC_free (iv_cand_p, heap, data->iv_candidates);
+  if (inverted_stmt_map)
+    {
+      pointer_map_destroy (inverted_stmt_map);
+      inverted_stmt_map = NULL;
+    }
+}
+
+/* Optimizes the LOOP.  Returns true if anything changed.  */
+
+static bool
+tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
+{
+  bool changed = false;
+  struct iv_ca *iv_ca;
+  edge exit;
+
+  gcc_assert (!data->niters);
+  data->current_loop = loop;
+  data->speed = optimize_loop_for_speed_p (loop);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Processing loop %d\n", loop->num);
+      
+      exit = single_dom_exit (loop);
+      if (exit)
+	{
+	  fprintf (dump_file, "  single exit %d -> %d, exit condition ",
+		   exit->src->index, exit->dest->index);
+	  print_gimple_stmt (dump_file, last_stmt (exit->src), 0, TDF_SLIM);
+	  fprintf (dump_file, "\n");
+	}
+
+      fprintf (dump_file, "\n");
+    }
+
+  /* For each ssa name determines whether it behaves as an induction variable
+     in some loop.  */
+  if (!find_induction_variables (data))
+    goto finish;
+
+  /* Finds interesting uses (item 1).  */
+  find_interesting_uses (data);
+  if (n_iv_uses (data) > MAX_CONSIDERED_USES)
+    goto finish;
+
+  /* Finds candidates for the induction variables (item 2).  */
+  find_iv_candidates (data);
+
+  /* Calculates the costs (item 3, part 1).  */
+  determine_use_iv_costs (data);
+  determine_iv_costs (data);
+  determine_set_costs (data);
+
+  /* Find the optimal set of induction variables (item 3, part 2).  */
+  iv_ca = find_optimal_iv_set (data);
+  if (!iv_ca)
+    goto finish;
+  changed = true;
+
+  /* Create the new induction variables (item 4, part 1).  */
+  create_new_ivs (data, iv_ca);
+  
+  /* Rewrite the uses (item 4, part 2).  */
+  rewrite_uses (data);
+
+  /* Remove the ivs that are unused after rewriting.  */
+  remove_unused_ivs (data);
+
+  adjust_update_pos_for_ivs (data, iv_ca);
+
+  iv_ca_free (&iv_ca);
+
+  /* We have changed the structure of induction variables; it might happen
+     that definitions in the scev database refer to some of them that were
+     eliminated.  */
+  scev_reset ();
+
+finish:
+  free_loop_data (data);
+
+  return changed;
+}
+
+/* Main entry point.  Optimizes induction variables in loops.  */
+
+void
+tree_ssa_iv_optimize (void)
+{
+  struct loop *loop;
+  struct ivopts_data data;
+  loop_iterator li;
+
+  tree_ssa_iv_optimize_init (&data);
+
+  /* Optimize the loops starting with the innermost ones.  */
+  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	flow_loop_dump (loop, dump_file, NULL, 1);
+
+      tree_ssa_iv_optimize_loop (&data, loop);
+    }
+
+  tree_ssa_iv_optimize_finalize (&data);
+
+}