* tree-inline.c (copy_tree_r): Also copy OMP_CLAUSE nodes.

[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-ivopts.c

/* Induction variable optimizations.
   Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  */

/* 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 "hashtab.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "cfgloop.h"
#include "params.h"
#include "langhooks.h"

/* The infinite cost.  */
#define INFTY 10000000

/* The expected number of loop iterations.  TODO -- use profiling instead of
   this.  */
#define AVG_LOOP_NITER(LOOP) 5


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

/* Information attached to loop.  */
struct loop_data
{
  unsigned regs_used;   /* Number of registers used.  */
};

/* Types of uses.  */
enum use_type
{
  USE_NONLINEAR_EXPR,   /* Use in a nonlinear expression.  */
  USE_OUTER,            /* The induction variable is used outside the loop.  */
  USE_ADDRESS,          /* Use in an address.  */
  USE_COMPARE           /* Use is a compare.  */
};

/* The candidate - cost pair.  */
struct cost_pair
{
  struct iv_cand *cand; /* The candidate.  */
  unsigned 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.  */
};

/* 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.  */
  tree 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.  */
};

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

struct ivopts_data
{
  /* The currently optimized loop.  */
  struct loop *current_loop;

  /* Numbers of iterations for all exits of the current loop.  */
  htab_t niters;

  /* The size of version_info array allocated.  */
  unsigned version_info_size;

  /* The array of information for the ssa names.  */
  struct version_info *version_info;

  /* The bitmap of indices in version_info whose value was changed.  */
  bitmap relevant;

  /* The maximum invariant id.  */
  unsigned max_inv_id;

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

  /* Whether to consider just related and important candidates when replacing a
     use.  */
  bool consider_all_candidates;
};

/* 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 cost of expressing uses.  */
  unsigned 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.  */
  unsigned 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;

/* 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 data for LOOP.  */

static inline struct loop_data *
loop_data (struct loop *loop)
{
  return loop->aux;
}

/* The single loop exit if it dominates the latch, NULL otherwise.  */

edge
single_dom_exit (struct loop *loop)
{
  edge exit = loop->single_exit;

  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_OUTER:
      fprintf (file, "  outside\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_generic_expr (file, use->stmt, TDF_SLIM);
  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;
    }

  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)
{
  return data->version_info + ver;
}

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

/* Checks whether there exists number X such that X * B = A, counting modulo
   2^BITS.  */

static bool
divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
        HOST_WIDE_INT *x)
{
  unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
  unsigned HOST_WIDE_INT inv, ex, val;
  unsigned i;

  a &= mask;
  b &= mask;

  /* First divide the whole equation by 2 as long as possible.  */
  while (!(a & 1) && !(b & 1))
    {
      a >>= 1;
      b >>= 1;
      bits--;
      mask >>= 1;
    }

  if (!(b & 1))
    {
      /* If b is still even, a is odd and there is no such x.  */
      return false;
    }

  /* Find the inverse of b.  We compute it as
     b^(2^(bits - 1) - 1) (mod 2^bits).  */
  inv = 1;
  ex = b;
  for (i = 0; i < bits - 1; i++)
    {
      inv = (inv * ex) & mask;
      ex = (ex * ex) & mask;
    }

  val = (a * inv) & mask;

  gcc_assert (((val * b) & mask) == a);

  if ((val >> (bits - 1)) & 1)
    val |= ~mask;

  *x = val;

  return true;
}

/* 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, tree stmt)
{
  basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (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, tree stmt)
{
  basic_block cand_bb = bb_for_stmt (cand->incremented_at);
  basic_block stmt_bb = bb_for_stmt (stmt);
  block_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 = bsi_last (stmt_bb); ; bsi_prev (&bsi))
    {
      if (bsi_stmt (bsi) == cand->incremented_at)
        return false;
      if (bsi_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, tree 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 ();
    }
}

/* Element of the table in that we cache the numbers of iterations obtained
   from exits of the loop.  */

struct nfe_cache_elt
{
  /* The edge for that the number of iterations is cached.  */
  edge exit;

  /* True if the # of iterations was successfully determined.  */
  bool valid_p;

  /* Description of # of iterations.  */
  struct tree_niter_desc niter;
};

/* Hash function for nfe_cache_elt E.  */

static hashval_t
nfe_hash (const void *e)
{
  const struct nfe_cache_elt *elt = e;

  return htab_hash_pointer (elt->exit);
}

/* Equality function for nfe_cache_elt E1 and edge E2.  */

static int
nfe_eq (const void *e1, const void *e2)
{
  const struct nfe_cache_elt *elt1 = e1;

  return elt1->exit == e2;
}

/*  Returns structure describing number of iterations determined from
    EXIT of DATA->current_loop, or NULL if something goes wrong.  */

static struct tree_niter_desc *
niter_for_exit (struct ivopts_data *data, edge exit)
{
  struct nfe_cache_elt *nfe_desc;
  PTR *slot;

  slot = htab_find_slot_with_hash (data->niters, exit,
                                   htab_hash_pointer (exit),
                                   INSERT);

  if (!*slot)
    {
      nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
      nfe_desc->exit = exit;
      nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
                                                     exit, &nfe_desc->niter,
                                                     true);
      *slot = nfe_desc;
    }
  else
    nfe_desc = *slot;

  if (!nfe_desc->valid_p)
    return NULL;

  return &nfe_desc->niter;
}

/* Returns structure describing number of iterations determined from
   single dominating exit of DATA->current_loop, or NULL if something
   goes wrong.  */

static struct tree_niter_desc *
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.  LOOPS is the loop tree.  */

static void
tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
{
  unsigned i;

  data->version_info_size = 2 * num_ssa_names;
  data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
  data->relevant = BITMAP_ALLOC (NULL);
  data->important_candidates = BITMAP_ALLOC (NULL);
  data->max_inv_id = 0;
  data->niters = htab_create (10, nfe_hash, nfe_eq, free);

  for (i = 1; i < loops->num; i++)
    if (loops->parray[i])
      loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));

  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, op0, op1;

  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 PLUS_EXPR:
    case MINUS_EXPR:
      op0 = determine_base_object (TREE_OPERAND (expr, 0));
      op1 = determine_base_object (TREE_OPERAND (expr, 1));
      
      if (!op1)
        return op0;

      if (!op0)
        return (code == PLUS_EXPR
                ? op1
                : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));

      return fold_build2 (code, ptr_type_node, op0, op1);

    case NOP_EXPR:
    case CONVERT_EXPR:
      return determine_base_object (TREE_OPERAND (expr, 0));

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

  if (step && integer_zerop (step))
    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;
  
  if (!name_info (data, var)->iv)
    {
      bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));

      if (!bb
          || !flow_bb_inside_loop_p (data->current_loop, bb))
        set_iv (data, var, var, NULL_TREE);
    }

  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 (tree phi)
{
  struct loop *loop = bb_for_stmt (phi)->loop_father;
  tree name = PHI_RESULT (phi);
  affine_iv iv;

  if (!is_gimple_reg (name))
    return NULL_TREE;

  if (!simple_iv (loop, phi, name, &iv, true))
    return NULL_TREE;

  return (zero_p (iv.step) ? NULL_TREE : iv.step);
}

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

static bool
contains_abnormal_ssa_name_p (tree expr)
{
  enum tree_code code;
  enum tree_code_class class;

  if (!expr)
    return false;

  code = TREE_CODE (expr);
  class = 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 (class)
    {
    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;
}

/* Finds basic ivs.  */

static bool
find_bivs (struct ivopts_data *data)
{
  tree phi, step, type, base;
  bool found = false;
  struct loop *loop = data->current_loop;

  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
    {
      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)
        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)
{
  tree phi, var;
  struct iv *iv, *incr_iv;
  struct loop *loop = data->current_loop;
  basic_block incr_bb;

  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
    {
      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 = bb_for_stmt (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, tree stmt, affine_iv *iv)
{
  tree lhs;
  struct loop *loop = data->current_loop;

  iv->base = NULL_TREE;
  iv->step = NULL_TREE;

  if (TREE_CODE (stmt) != MODIFY_EXPR)
    return false;

  lhs = TREE_OPERAND (stmt, 0);
  if (TREE_CODE (lhs) != SSA_NAME)
    return false;

  if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), 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, tree stmt)
{
  affine_iv iv;

  if (!find_givs_in_stmt_scev (data, stmt, &iv))
    return;

  set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
}

/* Finds general ivs in basic block BB.  */

static void
find_givs_in_bb (struct ivopts_data *data, basic_block bb)
{
  block_stmt_iterator bsi;

  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
    find_givs_in_stmt (data, bsi_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))
    {
      struct tree_niter_desc *niter;

      niter = niter_for_single_dom_exit (data);

      if (niter)
        {
          fprintf (dump_file, "  number of iterations ");
          print_generic_expr (dump_file, niter->niter, TDF_SLIM);
          fprintf (dump_file, "\n");

          fprintf (dump_file, "  may be zero if ");
          print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
          fprintf (dump_file, "\n");
          fprintf (dump_file, "\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,
            tree 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);

  /* 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 = bb_for_stmt (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));
}

/* Checks whether the use OP is interesting and if so, records it
   as TYPE.  */

static struct iv_use *
find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
                                       enum use_type type)
{
  struct iv *iv;
  struct iv *civ;
  tree 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
                  || use->type == USE_OUTER);

      if (type == USE_NONLINEAR_EXPR)
        use->type = USE_NONLINEAR_EXPR;
      return use;
    }

  if (zero_p (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 (TREE_CODE (stmt) == PHI_NODE
              || TREE_CODE (stmt) == MODIFY_EXPR);

  use = record_use (data, NULL, civ, stmt, type);
  iv->use_id = use->id;

  return use;
}

/* Checks whether the use OP is interesting and if so, records it.  */

static struct iv_use *
find_interesting_uses_op (struct ivopts_data *data, tree op)
{
  return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
}

/* Records a definition of induction variable OP that is used outside of the
   loop.  */

static struct iv_use *
find_interesting_uses_outer (struct ivopts_data *data, tree op)
{
  return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
}

/* Checks whether the condition *COND_P in STMT is interesting
   and if so, records it.  */

static void
find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
{
  tree *op0_p;
  tree *op1_p;
  struct iv *iv0 = NULL, *iv1 = NULL, *civ;
  struct iv const_iv;
  tree zero = integer_zero_node;

  const_iv.step = NULL_TREE;

  if (TREE_CODE (*cond_p) != SSA_NAME
      && !COMPARISON_CLASS_P (*cond_p))
    return;

  if (TREE_CODE (*cond_p) == SSA_NAME)
    {
      op0_p = cond_p;
      op1_p = &zero;
    }
  else
    {
      op0_p = &TREE_OPERAND (*cond_p, 0);
      op1_p = &TREE_OPERAND (*cond_p, 1);
    }

  if (TREE_CODE (*op0_p) == SSA_NAME)
    iv0 = get_iv (data, *op0_p);
  else
    iv0 = &const_iv;

  if (TREE_CODE (*op1_p) == SSA_NAME)
    iv1 = get_iv (data, *op1_p);
  else
    iv1 = &const_iv;

  if (/* When comparing with non-invariant value, we may not do any senseful
         induction variable elimination.  */
      (!iv0 || !iv1)
      /* Eliminating condition based on two ivs would be nontrivial.
         ??? TODO -- it is not really important to handle this case.  */
      || (!zero_p (iv0->step) && !zero_p (iv1->step)))
    {
      find_interesting_uses_op (data, *op0_p);
      find_interesting_uses_op (data, *op1_p);
      return;
    }

  if (zero_p (iv0->step) && zero_p (iv1->step))
    {
      /* If both are invariants, this is a work for unswitching.  */
      return;
    }

  civ = XNEW (struct iv);
  *civ = zero_p (iv0->step) ? *iv1: *iv0;
  record_use (data, cond_p, civ, stmt, USE_COMPARE);
}

/* Returns true if expression EXPR is obviously invariant in LOOP,
   i.e. if all its operands are defined outside of the LOOP.  */

bool
expr_invariant_in_loop_p (struct loop *loop, tree expr)
{
  basic_block def_bb;
  unsigned i, len;

  if (is_gimple_min_invariant (expr))
    return true;

  if (TREE_CODE (expr) == SSA_NAME)
    {
      def_bb = bb_for_stmt (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_CODE_LENGTH (TREE_CODE (expr));
  for (i = 0; i < len; i++)
    if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
      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;
  tree stmt;
  tree *step_p;
};

static bool
idx_find_step (tree base, tree *idx, void *data)
{
  struct ifs_ivopts_data *dta = data;
  struct iv *iv;
  tree step, 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)
    {
      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;

  *idx = iv->base;

  if (!iv->step)
    return true;

  if (TREE_CODE (base) == ARRAY_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);

  /* FIXME: convert_step should not be used outside chrec_convert: fix
     this by calling chrec_convert.  */
  iv_step = convert_step (dta->ivopts_data->current_loop,
                          sizetype, iv->base, iv->step, dta->stmt);

  if (!iv_step)
    {
      /* The index might wrap.  */
      return false;
    }

  step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);

  if (!*dta->step_p)
    *dta->step_p = step;
  else
    *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, 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 *data)
{
  find_interesting_uses_op (data, *idx);
  if (TREE_CODE (base) == ARRAY_REF)
    {
      find_interesting_uses_op (data, array_ref_element_size (base));
      find_interesting_uses_op (data, array_ref_low_bound (base));
    }
  return true;
}

/* Returns true if memory reference REF may be unaligned.  */

static bool
may_be_unaligned_p (tree ref)
{
  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
      && (base_align < GET_MODE_ALIGNMENT (mode)
          || bitpos % GET_MODE_ALIGNMENT (mode) != 0
          || bitpos % BITS_PER_UNIT != 0))
    return true;

  return false;
}

/* Finds addresses in *OP_P inside STMT.  */

static void
find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
{
  tree base = *op_p, step = NULL;
  struct iv *civ;
  struct ifs_ivopts_data ifs_ivopts_data;

  /* Do not play with volatile memory references.  A bit too conservative,
     perhaps, but safe.  */
  if (stmt_ann (stmt)->has_volatile_ops)
    goto fail;

  /* Ignore bitfields for now.  Not really something terribly complicated
     to handle.  TODO.  */
  if (TREE_CODE (base) == COMPONENT_REF
      && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
    goto fail;

  if (STRICT_ALIGNMENT
      && may_be_unaligned_p (base))
    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);

              if (step)
                step = fold_build2 (PLUS_EXPR, type, step, astep);
              else
                step = astep;
            }
        }

      if (zero_p (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_p = &step;
      if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
          || zero_p (step))
        goto fail;

      gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
      gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);

      base = build_fold_addr_expr (base);
    }

  civ = alloc_iv (base, step);
  record_use (data, op_p, civ, stmt, USE_ADDRESS);
  return;

fail:
  for_each_index (op_p, idx_record_use, data);
}

/* Finds and records invariants used in STMT.  */

static void
find_invariants_stmt (struct ivopts_data *data, tree 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, tree stmt)
{
  struct iv *iv;
  tree op, lhs, rhs;
  ssa_op_iter iter;
  use_operand_p use_p;

  find_invariants_stmt (data, stmt);

  if (TREE_CODE (stmt) == COND_EXPR)
    {
      find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
      return;
    }

  if (TREE_CODE (stmt) == MODIFY_EXPR)
    {
      lhs = TREE_OPERAND (stmt, 0);
      rhs = TREE_OPERAND (stmt, 1);

      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 && !zero_p (iv->step))
            return;
        }

      switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
        {
        case tcc_comparison:
          find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
          return;

        case tcc_reference:
          find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
          if (REFERENCE_CLASS_P (lhs))
            find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
          return;

        default: ;
        }

      if (REFERENCE_CLASS_P (lhs)
          && is_gimple_val (rhs))
        {
          find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
          find_interesting_uses_op (data, rhs);
          return;
        }

      /* TODO -- we should also handle address uses of type

         memory = call (whatever);

         and

         call (memory).  */
    }

  if (TREE_CODE (stmt) == PHI_NODE
      && bb_for_stmt (stmt) == data->current_loop->header)
    {
      lhs = PHI_RESULT (stmt);
      iv = get_iv (data, lhs);

      if (iv && !zero_p (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);
    }
}

/* 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)
{
  tree phi, def;

  for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
    {
      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
      find_interesting_uses_outer (data, def);
    }
}

/* Finds uses of the induction variables that are interesting.  */

static void
find_interesting_uses (struct ivopts_data *data)
{
  basic_block bb;
  block_stmt_iterator bsi;
  tree phi;
  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 (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
        find_interesting_uses_stmt (data, phi);
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
        find_interesting_uses_stmt (data, bsi_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)
          || zero_p (expr))
        return orig_expr;

      *offset = int_cst_value (expr);
      return build_int_cst_type (orig_type, 0);

    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 == PLUS_EXPR ? off0 + off1 : off0 - off1);
      if (op0 == TREE_OPERAND (expr, 0)
          && op1 == TREE_OPERAND (expr, 1))
        return orig_expr;

      if (zero_p (op1))
        expr = op0;
      else if (zero_p (op0))
        {
          if (code == PLUS_EXPR)
            expr = op1;
          else
            expr = fold_build1 (NEGATE_EXPR, type, op1);
        }
      else
        expr = fold_build2 (code, type, op0, op1);

      return fold_convert (orig_type, expr);

    case ARRAY_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
          && zero_p (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.
   For integer types, we return unsigned variant of the type, which
   avoids problems with overflows.  For pointer types, we return void *.  */

static tree
generic_type_for (tree type)
{
  if (POINTER_TYPE_P (type))
    return ptr_type_node;

  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 = 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, tree 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);
          if (step)
            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))
        continue;

      if (zero_p (cand->iv->step))
        {
          if (zero_p (step))
            break;
        }
      else
        {
          if (step && operand_equal_p (step, cand->iv->step, 0))
            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_TREE);
  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_TREE);
}

/* 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)
{
  tree phi, def;
  struct iv_cand *cand;

  add_candidate (data, iv->base, iv->step, true, NULL);

  /* The same, but with initial value zero.  */
  add_candidate (data,
                 build_int_cst (TREE_TYPE (iv->base), 0),
                 iv->step, true, NULL);

  phi = SSA_NAME_DEF_STMT (iv->ssa_name);
  if (TREE_CODE (phi) == PHI_NODE)
    {
      /* 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 && !zero_p (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;

  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.  */
  add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
                 iv->step, true, use);

  /* Third, try removing the constant offset.  */
  base = strip_offset (iv->base, &offset);
  if (offset)
    add_candidate (data, base, iv->step, false, use);
}

/* Possibly adds pseudocandidate for replacing the final value of USE by
   a direct computation.  */

static void
add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
{
  struct tree_niter_desc *niter;

  /* We must know where we exit the loop and how many times does it roll.  */
  niter = niter_for_single_dom_exit (data);
  if (!niter
      || !zero_p (niter->may_be_zero))
    return;

  add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
}

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

        case USE_OUTER:
          add_iv_value_candidates (data, use->iv, use);

          /* Additionally, add the pseudocandidate for the possibility to
             replace the final value by a direct computation.  */
          add_iv_outer_candidates (data, 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);
    }
}

/* 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, unsigned cost,
                 bitmap depends_on, tree value)
{
  unsigned i, s;

  if (cost == INFTY)
    {
      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)
{
  unsigned cost = 0;
  rtx set;

  for (; seq; seq = NEXT_INSN (seq))
    {
      set = single_set (seq);
      if (set)
        cost += rtx_cost (set, SET);
      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);
    }
  else
    x = gen_raw_REG (Pmode, (*regno)++);

  return gen_rtx_MEM (DECL_MODE (obj), 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 = 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))
        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)
{
  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;

  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 ();

  cost = seq_cost (seq);
  if (MEM_P (rslt))
    cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));

  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, tree 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 (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 we can prove that TOP = cst * BOT for some constant cst in TYPE,
   return cst.  Otherwise return NULL_TREE.  */

static tree
constant_multiple_of (tree type, tree top, tree bot)
{
  tree res, mby, p0, p1;
  enum tree_code code;
  bool negate;

  STRIP_NOPS (top);
  STRIP_NOPS (bot);

  if (operand_equal_p (top, bot, 0))
    return build_int_cst (type, 1);

  code = TREE_CODE (top);
  switch (code)
    {
    case MULT_EXPR:
      mby = TREE_OPERAND (top, 1);
      if (TREE_CODE (mby) != INTEGER_CST)
        return NULL_TREE;

      res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
      if (!res)
        return NULL_TREE;

      return fold_binary_to_constant (MULT_EXPR, type, res,
                                      fold_convert (type, mby));

    case PLUS_EXPR:
    case MINUS_EXPR:
      p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
      if (!p0)
        return NULL_TREE;
      p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
      if (!p1)
        return NULL_TREE;

      return fold_binary_to_constant (code, type, p0, p1);

    case INTEGER_CST:
      if (TREE_CODE (bot) != INTEGER_CST)
        return NULL_TREE;

      bot = fold_convert (type, bot);
      top = fold_convert (type, top);

      /* If BOT seems to be negative, try dividing by -BOT instead, and negate
         the result afterwards.  */
      if (tree_int_cst_sign_bit (bot))
        {
          negate = true;
          bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
        }
      else
        negate = false;

      /* Ditto for TOP.  */
      if (tree_int_cst_sign_bit (top))
        {
          negate = !negate;
          top = fold_unary_to_constant (NEGATE_EXPR, type, top);
        }

      if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
        return NULL_TREE;

      res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
      if (negate)
        res = fold_unary_to_constant (NEGATE_EXPR, type, res);
      return res;

    default:
      return NULL_TREE;
    }
}

/* Sets COMB to CST.  */

static void
aff_combination_const (struct affine_tree_combination *comb, tree type,
                       unsigned HOST_WIDE_INT cst)
{
  unsigned prec = TYPE_PRECISION (type);

  comb->type = type;
  comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);

  comb->n = 0;
  comb->rest = NULL_TREE;
  comb->offset = cst & comb->mask;
}

/* Sets COMB to single element ELT.  */

static void
aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
{
  unsigned prec = TYPE_PRECISION (type);

  comb->type = type;
  comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);

  comb->n = 1;
  comb->elts[0] = elt;
  comb->coefs[0] = 1;
  comb->rest = NULL_TREE;
  comb->offset = 0;
}

/* Scales COMB by SCALE.  */

static void
aff_combination_scale (struct affine_tree_combination *comb,
                       unsigned HOST_WIDE_INT scale)
{
  unsigned i, j;

  if (scale == 1)
    return;

  if (scale == 0)
    {
      aff_combination_const (comb, comb->type, 0);
      return;
    }

  comb->offset = (scale * comb->offset) & comb->mask;
  for (i = 0, j = 0; i < comb->n; i++)
    {
      comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
      comb->elts[j] = comb->elts[i];
      if (comb->coefs[j] != 0)
        j++;
    }
  comb->n = j;

  if (comb->rest)
    {
      if (comb->n < MAX_AFF_ELTS)
        {
          comb->coefs[comb->n] = scale;
          comb->elts[comb->n] = comb->rest;
          comb->rest = NULL_TREE;
          comb->n++;
        }
      else
        comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
                                  build_int_cst_type (comb->type, scale));
    }
}

/* Adds ELT * SCALE to COMB.  */

static void
aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
                         unsigned HOST_WIDE_INT scale)
{
  unsigned i;

  if (scale == 0)
    return;

  for (i = 0; i < comb->n; i++)
    if (operand_equal_p (comb->elts[i], elt, 0))
      {
        comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
        if (comb->coefs[i])
          return;

        comb->n--;
        comb->coefs[i] = comb->coefs[comb->n];
        comb->elts[i] = comb->elts[comb->n];

        if (comb->rest)
          {
            gcc_assert (comb->n == MAX_AFF_ELTS - 1);
            comb->coefs[comb->n] = 1;
            comb->elts[comb->n] = comb->rest;
            comb->rest = NULL_TREE;
            comb->n++;
          }
        return;
      }
  if (comb->n < MAX_AFF_ELTS)
    {
      comb->coefs[comb->n] = scale;
      comb->elts[comb->n] = elt;
      comb->n++;
      return;
    }

  if (scale == 1)
    elt = fold_convert (comb->type, elt);
  else
    elt = fold_build2 (MULT_EXPR, comb->type,
                       fold_convert (comb->type, elt),
                       build_int_cst_type (comb->type, scale)); 

  if (comb->rest)
    comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
  else
    comb->rest = elt;
}

/* Adds COMB2 to COMB1.  */

static void
aff_combination_add (struct affine_tree_combination *comb1,
                     struct affine_tree_combination *comb2)
{
  unsigned i;

  comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
  for (i = 0; i < comb2->n; i++)
    aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
  if (comb2->rest)
    aff_combination_add_elt (comb1, comb2->rest, 1);
}

/* Splits EXPR into an affine combination of parts.  */

static void
tree_to_aff_combination (tree expr, tree type,
                         struct affine_tree_combination *comb)
{
  struct affine_tree_combination tmp;
  enum tree_code code;
  tree cst, core, toffset;
  HOST_WIDE_INT bitpos, bitsize;
  enum machine_mode mode;
  int unsignedp, volatilep;

  STRIP_NOPS (expr);

  code = TREE_CODE (expr);
  switch (code)
    {
    case INTEGER_CST:
      aff_combination_const (comb, type, int_cst_value (expr));
      return;

    case PLUS_EXPR:
    case MINUS_EXPR:
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
      if (code == MINUS_EXPR)
        aff_combination_scale (&tmp, -1);
      aff_combination_add (comb, &tmp);
      return;

    case MULT_EXPR:
      cst = TREE_OPERAND (expr, 1);
      if (TREE_CODE (cst) != INTEGER_CST)
        break;
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      aff_combination_scale (comb, int_cst_value (cst));
      return;

    case NEGATE_EXPR:
      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
      aff_combination_scale (comb, -1);
      return;

    case ADDR_EXPR:
      core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
                                  &toffset, &mode, &unsignedp, &volatilep,
                                  false);
      if (bitpos % BITS_PER_UNIT != 0)
        break;
      aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
      core = build_fold_addr_expr (core);
      if (TREE_CODE (core) == ADDR_EXPR)
        aff_combination_add_elt (comb, core, 1);
      else
        {
          tree_to_aff_combination (core, type, &tmp);
          aff_combination_add (comb, &tmp);
        }
      if (toffset)
        {
          tree_to_aff_combination (toffset, type, &tmp);
          aff_combination_add (comb, &tmp);
        }
      return;

    default:
      break;
    }

  aff_combination_elt (comb, type, expr);
}

/* Creates EXPR + ELT * SCALE in TYPE.  MASK is the mask for width of TYPE.  */

static tree
add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
                 unsigned HOST_WIDE_INT mask)
{
  enum tree_code code;

  scale &= mask;
  elt = fold_convert (type, elt);

  if (scale == 1)
    {
      if (!expr)
        return elt;

      return fold_build2 (PLUS_EXPR, type, expr, elt);
    }

  if (scale == mask)
    {
      if (!expr)
        return fold_build1 (NEGATE_EXPR, type, elt);

      return fold_build2 (MINUS_EXPR, type, expr, elt);
    }

  if (!expr)
    return fold_build2 (MULT_EXPR, type, elt,
                        build_int_cst_type (type, scale));

  if ((scale | (mask >> 1)) == mask)
    {
      /* Scale is negative.  */
      code = MINUS_EXPR;
      scale = (-scale) & mask;
    }
  else
    code = PLUS_EXPR;

  elt = fold_build2 (MULT_EXPR, type, elt,
                     build_int_cst_type (type, scale));
  return fold_build2 (code, type, expr, elt);
}

/* Copies the tree elements of COMB to ensure that they are not shared.  */

static void
unshare_aff_combination (struct affine_tree_combination *comb)
{
  unsigned i;

  for (i = 0; i < comb->n; i++)
    comb->elts[i] = unshare_expr (comb->elts[i]);
  if (comb->rest)
    comb->rest = unshare_expr (comb->rest);
}

/* Makes tree from the affine combination COMB.  */

static tree
aff_combination_to_tree (struct affine_tree_combination *comb)
{
  tree type = comb->type;
  tree expr = comb->rest;
  unsigned i;
  unsigned HOST_WIDE_INT off, sgn;

  /* Handle the special case produced by get_computation_aff when
     the type does not fit in HOST_WIDE_INT.  */
  if (comb->n == 0 && comb->offset == 0)
    return fold_convert (type, expr);

  gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);

  for (i = 0; i < comb->n; i++)
    expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
                            comb->mask);

  if ((comb->offset | (comb->mask >> 1)) == comb->mask)
    {
      /* Offset is negative.  */
      off = (-comb->offset) & comb->mask;
      sgn = comb->mask;
    }
  else
    {
      off = comb->offset;
      sgn = 1;
    }
  return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
                          comb->mask);
}

/* 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, tree 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;
  tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
  tree uutype;
  tree expr, delta;
  tree ratio;
  unsigned HOST_WIDE_INT ustepi, cstepi;
  HOST_WIDE_INT ratioi;
  struct affine_tree_combination cbase_aff, expr_aff;
  tree cstep_orig = cstep, ustep_orig = ustep;

  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
    {
      /* We do not have a precision to express the values of use.  */
      return false;
    }

  expr = var_at_stmt (loop, cand, at);

  if (TREE_TYPE (expr) != ctype)
    {
      /* This may happen with the original ivs.  */
      expr = fold_convert (ctype, expr);
    }

  if (TYPE_UNSIGNED (utype))
    uutype = utype;
  else
    {
      uutype = unsigned_type_for (utype);
      ubase = fold_convert (uutype, ubase);
      ustep = fold_convert (uutype, ustep);
    }

  if (uutype != ctype)
    {
      expr = fold_convert (uutype, expr);
      cbase = fold_convert (uutype, cbase);
      cstep = fold_convert (uutype, cstep);

      /* If the conversion is not noop, we must take it into account when
         considering the value of the step.  */
      if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
        cstep_orig = cstep;
    }

  if (cst_and_fits_in_hwi (cstep_orig)
      && cst_and_fits_in_hwi (ustep_orig))
    {
      ustepi = int_cst_value (ustep_orig);
      cstepi = int_cst_value (cstep_orig);

      if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
        {
          /* TODO maybe consider case when ustep divides cstep and the ratio is
             a power of 2 (so that the division is fast to execute)?  We would
             need to be much more careful with overflows etc. then.  */
          return false;
        }

      ratio = build_int_cst_type (uutype, ratioi);
    }
  else
    {
      ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
      if (!ratio)
        return false;

      /* Ratioi is only used to detect special cases when the multiplicative
         factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
         we may set it to 0.  We prefer cst_and_fits_in_hwi/int_cst_value
         to integer_onep/integer_all_onesp, since the former ignores
         TREE_OVERFLOW.  */
      if (cst_and_fits_in_hwi (ratio))
        ratioi = int_cst_value (ratio);
      else if (integer_onep (ratio))
        ratioi = 1;
      else if (integer_all_onesp (ratio))
        ratioi = -1;
      else
        ratioi = 0;
    }

  /* We may need to shift the value if we are after the increment.  */
  if (stmt_after_increment (loop, cand, at))
    cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);

  /* use = ubase - ratio * cbase + ratio * var.

     In general case ubase + ratio * (var - cbase) could be better (one less
     multiplication), but often it is possible to eliminate redundant parts
     of computations from (ubase - ratio * cbase) term, and if it does not
     happen, fold is able to apply the distributive law to obtain this form
     anyway.  */

  if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
    {
      /* Let's compute in trees and just return the result in AFF.  This case
         should not be very common, and fold itself is not that bad either,
         so making the aff. functions more complicated to handle this case
         is not that urgent.  */
      if (ratioi == 1)
        {
          delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
          expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
        }
      else if (ratioi == -1)
        {
          delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
          expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
        }
      else
        {
          delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
          delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
          expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
          expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
        }

      aff->type = uutype;
      aff->n = 0;
      aff->offset = 0;
      aff->mask = 0;
      aff->rest = expr;
      return true;
    }

  /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
     possible to compute ratioi.  */
  gcc_assert (ratioi);

  tree_to_aff_combination (ubase, uutype, aff);
  tree_to_aff_combination (cbase, uutype, &cbase_aff);
  tree_to_aff_combination (expr, uutype, &expr_aff);
  aff_combination_scale (&cbase_aff, -ratioi);
  aff_combination_scale (&expr_aff, ratioi);
  aff_combination_add (aff, &cbase_aff);
  aff_combination_add (aff, &expr_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, tree at)
{
  struct affine_tree_combination 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)
{
  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);
  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 = 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 = entry1;
  const struct mbc_entry *e2 = 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)
{
  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);

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

bool
multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
{
#define MAX_RATIO 128
  static sbitmap valid_mult;
  
  if (!valid_mult)
    {
      rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
      rtx addr;
      HOST_WIDE_INT i;

      valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
      sbitmap_zero (valid_mult);
      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 (Pmode, addr))
            SET_BIT (valid_mult, 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, 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, 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.  The created memory accesses MODE.
   
   TODO -- there must be some better way.  This all is quite crude.  */

static unsigned
get_address_cost (bool symbol_present, bool var_present,
                  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
{
  static bool initialized = false;
  static HOST_WIDE_INT rat, off;
  static HOST_WIDE_INT min_offset, max_offset;
  static unsigned costs[2][2][2][2];
  unsigned cost, acost;
  rtx seq, addr, base;
  bool offset_p, ratio_p;
  rtx reg1;
  HOST_WIDE_INT s_offset;
  unsigned HOST_WIDE_INT mask;
  unsigned bits;

  if (!initialized)
    {
      HOST_WIDE_INT i;
      initialized = true;

      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);

      addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
      for (i = 1; i <= 1 << 20; i <<= 1)
        {
          XEXP (addr, 1) = gen_int_mode (i, Pmode);
          if (!memory_address_p (Pmode, addr))
            break;
        }
      max_offset = i >> 1;
      off = max_offset;

      for (i = 1; i <= 1 << 20; i <<= 1)
        {
          XEXP (addr, 1) = gen_int_mode (-i, Pmode);
          if (!memory_address_p (Pmode, addr))
            break;
        }
      min_offset = -(i >> 1);

      if (dump_file && (dump_flags & TDF_DETAILS))
        {
          fprintf (dump_file, "get_address_cost:\n");
          fprintf (dump_file, "  min offset %d\n", (int) min_offset);
          fprintf (dump_file, "  max offset %d\n", (int) max_offset);
        }

      rat = 1;
      for (i = 2; i <= MAX_RATIO; i++)
        if (multiplier_allowed_in_address_p (i))
          {
            rat = i;
            break;
          }
    }

  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 <= s_offset && s_offset <= max_offset);
  ratio_p = (ratio != 1
             && multiplier_allowed_in_address_p (ratio));

  if (ratio != 1 && !ratio_p)
    cost += multiply_by_cost (ratio, Pmode);

  if (s_offset && !offset_p && !symbol_present)
    {
      cost += add_cost (Pmode);
      var_present = true;
    }

  acost = costs[symbol_present][var_present][offset_p][ratio_p];
  if (!acost)
    {
      int old_cse_not_expected;
      acost = 0;
      
      addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
      if (ratio_p)
        addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));

      if (var_present)
        addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);

      if (symbol_present)
        {
          base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
          if (offset_p)
            base = gen_rtx_fmt_e (CONST, Pmode,
                                  gen_rtx_fmt_ee (PLUS, Pmode,
                                                  base,
                                                  gen_int_mode (off, Pmode)));
        }
      else if (offset_p)
        base = gen_int_mode (off, 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 (Pmode, addr);
      cse_not_expected = old_cse_not_expected;
      seq = get_insns ();
      end_sequence ();
  
      acost = seq_cost (seq);
      acost += address_cost (addr, Pmode);

      if (!acost)
        acost = 1;
      costs[symbol_present][var_present][offset_p][ratio_p] = acost;
    }

  return cost + acost;
}

/* Estimates cost of forcing expression EXPR into a variable.  */

unsigned
force_expr_to_var_cost (tree expr)
{
  static bool costs_initialized = false;
  static unsigned integer_cost;
  static unsigned symbol_cost;
  static unsigned address_cost;
  tree op0, op1;
  unsigned cost0, cost1, cost;
  enum machine_mode mode;

  if (!costs_initialized)
    {
      tree var = create_tmp_var_raw (integer_type_node, "test_var");
      rtx x = gen_rtx_MEM (DECL_MODE (var),
                           gen_rtx_SYMBOL_REF (Pmode, "test_var"));
      tree addr;
      tree type = build_pointer_type (integer_type_node);

      integer_cost = computation_cost (build_int_cst_type (integer_type_node,
                                                           2000));

      SET_DECL_RTL (var, x);
      TREE_STATIC (var) = 1;
      addr = build1 (ADDR_EXPR, type, var);
      symbol_cost = computation_cost (addr) + 1;

      address_cost
        = computation_cost (build2 (PLUS_EXPR, type,
                                    addr,
                                    build_int_cst_type (type, 2000))) + 1;
      if (dump_file && (dump_flags & TDF_DETAILS))
        {
          fprintf (dump_file, "force_expr_to_var_cost:\n");
          fprintf (dump_file, "  integer %d\n", (int) integer_cost);
          fprintf (dump_file, "  symbol %d\n", (int) symbol_cost);
          fprintf (dump_file, "  address %d\n", (int) address_cost);
          fprintf (dump_file, "  other %d\n", (int) target_spill_cost);
          fprintf (dump_file, "\n");
        }

      costs_initialized = true;
    }

  STRIP_NOPS (expr);

  if (SSA_VAR_P (expr))
    return 0;

  if (TREE_INVARIANT (expr))
    {
      if (TREE_CODE (expr) == INTEGER_CST)
        return integer_cost;

      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 symbol_cost;
        }

      return address_cost;
    }

  switch (TREE_CODE (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 = 0;
      else
        cost0 = force_expr_to_var_cost (op0);

      if (is_gimple_val (op1))
        cost1 = 0;
      else
        cost1 = force_expr_to_var_cost (op1);

      break;

    default:
      /* Just an arbitrary value, FIXME.  */
      return target_spill_cost;
    }

  mode = TYPE_MODE (TREE_TYPE (expr));
  switch (TREE_CODE (expr))
    {
    case PLUS_EXPR:
    case MINUS_EXPR:
      cost = add_cost (mode);
      break;

    case MULT_EXPR:
      if (cst_and_fits_in_hwi (op0))
        cost = multiply_by_cost (int_cst_value (op0), mode);
      else if (cst_and_fits_in_hwi (op1))
        cost = multiply_by_cost (int_cst_value (op1), mode);
      else
        return target_spill_cost;
      break;

    default:
      gcc_unreachable ();
    }

  cost += cost0;
  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.  */
  return cost < target_spill_cost ? cost : target_spill_cost;
}

/* Estimates cost of forcing EXPR into a variable.  DEPENDS_ON is a set of the
   invariants the computation depends on.  */

static unsigned
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);
}

/* 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 unsigned
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 target_spill_cost;
    }

  *offset += bitpos / BITS_PER_UNIT;
  if (TREE_STATIC (core)
      || DECL_EXTERNAL (core))
    {
      *symbol_present = true;
      *var_present = false;
      return 0;
    }
      
  *symbol_present = false;
  *var_present = true;
  return 0;
}

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