Subversion Repositories scarts

/* Optimize by combining instructions for GNU compiler.

   Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,

   1999, 2000, 2001, 2002, 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 module is essentially the "combiner" phase of the U. of Arizona

   Portable Optimizer, but redone to work on our list-structured

   representation for RTL instead of their string representation.

   The LOG_LINKS of each insn identify the most recent assignment

   to each REG used in the insn.  It is a list of previous insns,

   each of which contains a SET for a REG that is used in this insn

   and not used or set in between.  LOG_LINKs never cross basic blocks.

   They were set up by the preceding pass (lifetime analysis).

   We try to combine each pair of insns joined by a logical link.

   We also try to combine triples of insns A, B and C when

   C has a link back to B and B has a link back to A.

   LOG_LINKS does not have links for use of the CC0.  They don't

   need to, because the insn that sets the CC0 is always immediately

   before the insn that tests it.  So we always regard a branch

   insn as having a logical link to the preceding insn.  The same is true

   for an insn explicitly using CC0.

   We check (with use_crosses_set_p) to avoid combining in such a way

   as to move a computation to a place where its value would be different.

   Combination is done by mathematically substituting the previous

   insn(s) values for the regs they set into the expressions in

   the later insns that refer to these regs.  If the result is a valid insn

   for our target machine, according to the machine description,

   we install it, delete the earlier insns, and update the data flow

   information (LOG_LINKS and REG_NOTES) for what we did.

   There are a few exceptions where the dataflow information created by

   flow.c aren't completely updated:

   - reg_live_length is not updated

   - reg_n_refs is not adjusted in the rare case when a register is

     no longer required in a computation

   - there are extremely rare cases (see distribute_regnotes) when a

     REG_DEAD note is lost

   - a LOG_LINKS entry that refers to an insn with multiple SETs may be

     removed because there is no way to know which register it was

     linking

   To simplify substitution, we combine only when the earlier insn(s)

   consist of only a single assignment.  To simplify updating afterward,

   we never combine when a subroutine call appears in the middle.

   Since we do not represent assignments to CC0 explicitly except when that

   is all an insn does, there is no LOG_LINKS entry in an insn that uses

   the condition code for the insn that set the condition code.

   Fortunately, these two insns must be consecutive.

   Therefore, every JUMP_INSN is taken to have an implicit logical link

   to the preceding insn.  This is not quite right, since non-jumps can

   also use the condition code; but in practice such insns would not

   combine anyway.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "tree.h"

#include "tm_p.h"

#include "flags.h"

#include "regs.h"

#include "hard-reg-set.h"

#include "basic-block.h"

#include "insn-config.h"

#include "function.h"

/* Include expr.h after insn-config.h so we get HAVE_conditional_move.  */

#include "expr.h"

#include "insn-attr.h"

#include "recog.h"

#include "real.h"

#include "toplev.h"

#include "target.h"

#include "optabs.h"

#include "insn-codes.h"

#include "rtlhooks-def.h"

/* Include output.h for dump_file.  */

#include "output.h"

#include "params.h"

#include "timevar.h"

#include "tree-pass.h"

/* Number of attempts to combine instructions in this function.  */

static int combine_attempts;

/* Number of attempts that got as far as substitution in this function.  */

static int combine_merges;

/* Number of instructions combined with added SETs in this function.  */

static int combine_extras;

/* Number of instructions combined in this function.  */

static int combine_successes;

/* Totals over entire compilation.  */

static int total_attempts, total_merges, total_extras, total_successes;

/* Vector mapping INSN_UIDs to cuids.

   The cuids are like uids but increase monotonically always.

   Combine always uses cuids so that it can compare them.

   But actually renumbering the uids, which we used to do,

   proves to be a bad idea because it makes it hard to compare

   the dumps produced by earlier passes with those from later passes.  */

static int *uid_cuid;

static int max_uid_cuid;

/* Get the cuid of an insn.  */

#define INSN_CUID(INSN) \

(INSN_UID (INSN) > max_uid_cuid ? insn_cuid (INSN) : uid_cuid[INSN_UID (INSN)])

/* In case BITS_PER_WORD == HOST_BITS_PER_WIDE_INT, shifting by

   BITS_PER_WORD would invoke undefined behavior.  Work around it.  */

#define UWIDE_SHIFT_LEFT_BY_BITS_PER_WORD(val) \

  (((unsigned HOST_WIDE_INT) (val) << (BITS_PER_WORD - 1)) << 1)

/* Maximum register number, which is the size of the tables below.  */

static unsigned int combine_max_regno;

struct reg_stat {

  /* Record last point of death of (hard or pseudo) register n.  */

  rtx                           last_death;

  /* Record last point of modification of (hard or pseudo) register n.  */

  rtx                           last_set;

  /* The next group of fields allows the recording of the last value assigned

     to (hard or pseudo) register n.  We use this information to see if an

     operation being processed is redundant given a prior operation performed

     on the register.  For example, an `and' with a constant is redundant if

     all the zero bits are already known to be turned off.

     We use an approach similar to that used by cse, but change it in the

     following ways:

     (1) We do not want to reinitialize at each label.

     (2) It is useful, but not critical, to know the actual value assigned

         to a register.  Often just its form is helpful.

     Therefore, we maintain the following fields:

     last_set_value             the last value assigned

     last_set_label             records the value of label_tick when the

                                register was assigned

     last_set_table_tick        records the value of label_tick when a

                                value using the register is assigned

     last_set_invalid           set to nonzero when it is not valid

                                to use the value of this register in some

                                register's value

     To understand the usage of these tables, it is important to understand

     the distinction between the value in last_set_value being valid and

     the register being validly contained in some other expression in the

     table.

     (The next two parameters are out of date).

     reg_stat[i].last_set_value is valid if it is nonzero, and either

     reg_n_sets[i] is 1 or reg_stat[i].last_set_label == label_tick.

     Register I may validly appear in any expression returned for the value

     of another register if reg_n_sets[i] is 1.  It may also appear in the

     value for register J if reg_stat[j].last_set_invalid is zero, or

     reg_stat[i].last_set_label < reg_stat[j].last_set_label.

     If an expression is found in the table containing a register which may

     not validly appear in an expression, the register is replaced by

     something that won't match, (clobber (const_int 0)).  */

  /* Record last value assigned to (hard or pseudo) register n.  */

  rtx                           last_set_value;

  /* Record the value of label_tick when an expression involving register n

     is placed in last_set_value.  */

  int                           last_set_table_tick;

  /* Record the value of label_tick when the value for register n is placed in

     last_set_value.  */

  int                           last_set_label;

  /* These fields are maintained in parallel with last_set_value and are

     used to store the mode in which the register was last set, the bits

     that were known to be zero when it was last set, and the number of

     sign bits copies it was known to have when it was last set.  */

  unsigned HOST_WIDE_INT        last_set_nonzero_bits;

  char                          last_set_sign_bit_copies;

  ENUM_BITFIELD(machine_mode)   last_set_mode : 8;

  /* Set nonzero if references to register n in expressions should not be

     used.  last_set_invalid is set nonzero when this register is being

     assigned to and last_set_table_tick == label_tick.  */

  char                          last_set_invalid;

  /* Some registers that are set more than once and used in more than one

     basic block are nevertheless always set in similar ways.  For example,

     a QImode register may be loaded from memory in two places on a machine

     where byte loads zero extend.

     We record in the following fields if a register has some leading bits

     that are always equal to the sign bit, and what we know about the

     nonzero bits of a register, specifically which bits are known to be

     zero.

     If an entry is zero, it means that we don't know anything special.  */

  unsigned char                 sign_bit_copies;

  unsigned HOST_WIDE_INT        nonzero_bits;

};

static struct reg_stat *reg_stat;

/* Record the cuid of the last insn that invalidated memory

   (anything that writes memory, and subroutine calls, but not pushes).  */

static int mem_last_set;

/* Record the cuid of the last CALL_INSN

   so we can tell whether a potential combination crosses any calls.  */

static int last_call_cuid;

/* When `subst' is called, this is the insn that is being modified

   (by combining in a previous insn).  The PATTERN of this insn

   is still the old pattern partially modified and it should not be

   looked at, but this may be used to examine the successors of the insn

   to judge whether a simplification is valid.  */

static rtx subst_insn;

/* This is the lowest CUID that `subst' is currently dealing with.

   get_last_value will not return a value if the register was set at or

   after this CUID.  If not for this mechanism, we could get confused if

   I2 or I1 in try_combine were an insn that used the old value of a register

   to obtain a new value.  In that case, we might erroneously get the

   new value of the register when we wanted the old one.  */

static int subst_low_cuid;

/* This contains any hard registers that are used in newpat; reg_dead_at_p

   must consider all these registers to be always live.  */

static HARD_REG_SET newpat_used_regs;

/* This is an insn to which a LOG_LINKS entry has been added.  If this

   insn is the earlier than I2 or I3, combine should rescan starting at

   that location.  */

static rtx added_links_insn;

/* Basic block in which we are performing combines.  */

static basic_block this_basic_block;

/* A bitmap indicating which blocks had registers go dead at entry.

   After combine, we'll need to re-do global life analysis with

   those blocks as starting points.  */

static sbitmap refresh_blocks;

/* The following array records the insn_rtx_cost for every insn

   in the instruction stream.  */

static int *uid_insn_cost;

/* Length of the currently allocated uid_insn_cost array.  */

static int last_insn_cost;

/* Incremented for each label.  */

static int label_tick;

/* Mode used to compute significance in reg_stat[].nonzero_bits.  It is the

   largest integer mode that can fit in HOST_BITS_PER_WIDE_INT.  */

static enum machine_mode nonzero_bits_mode;

/* Nonzero when reg_stat[].nonzero_bits and reg_stat[].sign_bit_copies can

   be safely used.  It is zero while computing them and after combine has

   completed.  This former test prevents propagating values based on

   previously set values, which can be incorrect if a variable is modified

   in a loop.  */

static int nonzero_sign_valid;

/* Record one modification to rtl structure

   to be undone by storing old_contents into *where.

   is_int is 1 if the contents are an int.  */

struct undo

{

  struct undo *next;

  int is_int;

  union {rtx r; int i;} old_contents;

  union {rtx *r; int *i;} where;

};

/* Record a bunch of changes to be undone, up to MAX_UNDO of them.

   num_undo says how many are currently recorded.

   other_insn is nonzero if we have modified some other insn in the process

   of working on subst_insn.  It must be verified too.  */

struct undobuf

{

  struct undo *undos;

  struct undo *frees;

  rtx other_insn;

};

static struct undobuf undobuf;

/* Number of times the pseudo being substituted for

   was found and replaced.  */

static int n_occurrences;

static rtx reg_nonzero_bits_for_combine (rtx, enum machine_mode, rtx,

                                         enum machine_mode,

                                         unsigned HOST_WIDE_INT,

                                         unsigned HOST_WIDE_INT *);

static rtx reg_num_sign_bit_copies_for_combine (rtx, enum machine_mode, rtx,

                                                enum machine_mode,

                                                unsigned int, unsigned int *);

static void do_SUBST (rtx *, rtx);

static void do_SUBST_INT (int *, int);

static void init_reg_last (void);

static void setup_incoming_promotions (void);

static void set_nonzero_bits_and_sign_copies (rtx, rtx, void *);

static int cant_combine_insn_p (rtx);

static int can_combine_p (rtx, rtx, rtx, rtx, rtx *, rtx *);

static int combinable_i3pat (rtx, rtx *, rtx, rtx, int, rtx *);

static int contains_muldiv (rtx);

static rtx try_combine (rtx, rtx, rtx, int *);

static void undo_all (void);

static void undo_commit (void);

static rtx *find_split_point (rtx *, rtx);

static rtx subst (rtx, rtx, rtx, int, int);

static rtx combine_simplify_rtx (rtx, enum machine_mode, int);

static rtx simplify_if_then_else (rtx);

static rtx simplify_set (rtx);

static rtx simplify_logical (rtx);

static rtx expand_compound_operation (rtx);

static rtx expand_field_assignment (rtx);

static rtx make_extraction (enum machine_mode, rtx, HOST_WIDE_INT,

                            rtx, unsigned HOST_WIDE_INT, int, int, int);

static rtx extract_left_shift (rtx, int);

static rtx make_compound_operation (rtx, enum rtx_code);

static int get_pos_from_mask (unsigned HOST_WIDE_INT,

                              unsigned HOST_WIDE_INT *);

static rtx force_to_mode (rtx, enum machine_mode,

                          unsigned HOST_WIDE_INT, rtx, int);

static rtx if_then_else_cond (rtx, rtx *, rtx *);

static rtx known_cond (rtx, enum rtx_code, rtx, rtx);

static int rtx_equal_for_field_assignment_p (rtx, rtx);

static rtx make_field_assignment (rtx);

static rtx apply_distributive_law (rtx);

static rtx distribute_and_simplify_rtx (rtx, int);

static rtx simplify_and_const_int (rtx, enum machine_mode, rtx,

                                   unsigned HOST_WIDE_INT);

static int merge_outer_ops (enum rtx_code *, HOST_WIDE_INT *, enum rtx_code,

                            HOST_WIDE_INT, enum machine_mode, int *);

static rtx simplify_shift_const (rtx, enum rtx_code, enum machine_mode, rtx,

                                 int);

static int recog_for_combine (rtx *, rtx, rtx *);

static rtx gen_lowpart_for_combine (enum machine_mode, rtx);

static enum rtx_code simplify_comparison (enum rtx_code, rtx *, rtx *);

static void update_table_tick (rtx);

static void record_value_for_reg (rtx, rtx, rtx);

static void check_promoted_subreg (rtx, rtx);

static void record_dead_and_set_regs_1 (rtx, rtx, void *);

static void record_dead_and_set_regs (rtx);

static int get_last_value_validate (rtx *, rtx, int, int);

static rtx get_last_value (rtx);

static int use_crosses_set_p (rtx, int);

static void reg_dead_at_p_1 (rtx, rtx, void *);

static int reg_dead_at_p (rtx, rtx);

static void move_deaths (rtx, rtx, int, rtx, rtx *);

static int reg_bitfield_target_p (rtx, rtx);

static void distribute_notes (rtx, rtx, rtx, rtx, rtx, rtx);

static void distribute_links (rtx);

static void mark_used_regs_combine (rtx);

static int insn_cuid (rtx);

static void record_promoted_value (rtx, rtx);

static int unmentioned_reg_p_1 (rtx *, void *);

static bool unmentioned_reg_p (rtx, rtx);

/* It is not safe to use ordinary gen_lowpart in combine.

   See comments in gen_lowpart_for_combine.  */

#undef RTL_HOOKS_GEN_LOWPART

#define RTL_HOOKS_GEN_LOWPART              gen_lowpart_for_combine

/* Our implementation of gen_lowpart never emits a new pseudo.  */

#undef RTL_HOOKS_GEN_LOWPART_NO_EMIT

#define RTL_HOOKS_GEN_LOWPART_NO_EMIT      gen_lowpart_for_combine

#undef RTL_HOOKS_REG_NONZERO_REG_BITS

#define RTL_HOOKS_REG_NONZERO_REG_BITS     reg_nonzero_bits_for_combine

#undef RTL_HOOKS_REG_NUM_SIGN_BIT_COPIES

#define RTL_HOOKS_REG_NUM_SIGN_BIT_COPIES  reg_num_sign_bit_copies_for_combine

static const struct rtl_hooks combine_rtl_hooks = RTL_HOOKS_INITIALIZER;

/* Substitute NEWVAL, an rtx expression, into INTO, a place in some

   insn.  The substitution can be undone by undo_all.  If INTO is already

   set to NEWVAL, do not record this change.  Because computing NEWVAL might

   also call SUBST, we have to compute it before we put anything into

   the undo table.  */

static void

do_SUBST (rtx *into, rtx newval)

{

  struct undo *buf;

  rtx oldval = *into;

  if (oldval == newval)

    return;

  /* We'd like to catch as many invalid transformations here as

     possible.  Unfortunately, there are way too many mode changes

     that are perfectly valid, so we'd waste too much effort for

     little gain doing the checks here.  Focus on catching invalid

     transformations involving integer constants.  */

  if (GET_MODE_CLASS (GET_MODE (oldval)) == MODE_INT

      && GET_CODE (newval) == CONST_INT)

    {

      /* Sanity check that we're replacing oldval with a CONST_INT

         that is a valid sign-extension for the original mode.  */

      gcc_assert (INTVAL (newval)

                  == trunc_int_for_mode (INTVAL (newval), GET_MODE (oldval)));

      /* Replacing the operand of a SUBREG or a ZERO_EXTEND with a

         CONST_INT is not valid, because after the replacement, the

         original mode would be gone.  Unfortunately, we can't tell

         when do_SUBST is called to replace the operand thereof, so we

         perform this test on oldval instead, checking whether an

         invalid replacement took place before we got here.  */

      gcc_assert (!(GET_CODE (oldval) == SUBREG

                    && GET_CODE (SUBREG_REG (oldval)) == CONST_INT));

      gcc_assert (!(GET_CODE (oldval) == ZERO_EXTEND

                    && GET_CODE (XEXP (oldval, 0)) == CONST_INT));

    }

  if (undobuf.frees)

    buf = undobuf.frees, undobuf.frees = buf->next;

  else

    buf = xmalloc (sizeof (struct undo));

  buf->is_int = 0;

  buf->where.r = into;

  buf->old_contents.r = oldval;

  *into = newval;

  buf->next = undobuf.undos, undobuf.undos = buf;

}

#define SUBST(INTO, NEWVAL)     do_SUBST(&(INTO), (NEWVAL))

/* Similar to SUBST, but NEWVAL is an int expression.  Note that substitution

   for the value of a HOST_WIDE_INT value (including CONST_INT) is

   not safe.  */

static void

do_SUBST_INT (int *into, int newval)

{

  struct undo *buf;

  int oldval = *into;

  if (oldval == newval)

    return;

  if (undobuf.frees)

    buf = undobuf.frees, undobuf.frees = buf->next;

  else

    buf = xmalloc (sizeof (struct undo));

  buf->is_int = 1;

  buf->where.i = into;

  buf->old_contents.i = oldval;

  *into = newval;

  buf->next = undobuf.undos, undobuf.undos = buf;

}

#define SUBST_INT(INTO, NEWVAL)  do_SUBST_INT(&(INTO), (NEWVAL))

/* Subroutine of try_combine.  Determine whether the combine replacement

   patterns NEWPAT and NEWI2PAT are cheaper according to insn_rtx_cost

   that the original instruction sequence I1, I2 and I3.  Note that I1

   and/or NEWI2PAT may be NULL_RTX.  This function returns false, if the

   costs of all instructions can be estimated, and the replacements are

   more expensive than the original sequence.  */

static bool

combine_validate_cost (rtx i1, rtx i2, rtx i3, rtx newpat, rtx newi2pat)

{

  int i1_cost, i2_cost, i3_cost;

  int new_i2_cost, new_i3_cost;

  int old_cost, new_cost;

  /* Lookup the original insn_rtx_costs.  */

  i2_cost = INSN_UID (i2) <= last_insn_cost

            ? uid_insn_cost[INSN_UID (i2)] : 0;

  i3_cost = INSN_UID (i3) <= last_insn_cost

            ? uid_insn_cost[INSN_UID (i3)] : 0;

  if (i1)

    {

      i1_cost = INSN_UID (i1) <= last_insn_cost

                ? uid_insn_cost[INSN_UID (i1)] : 0;

      old_cost = (i1_cost > 0 && i2_cost > 0 && i3_cost > 0)

                 ? i1_cost + i2_cost + i3_cost : 0;

    }

  else

    {

      old_cost = (i2_cost > 0 && i3_cost > 0) ? i2_cost + i3_cost : 0;

      i1_cost = 0;

    }

  /* Calculate the replacement insn_rtx_costs.  */

  new_i3_cost = insn_rtx_cost (newpat);

  if (newi2pat)

    {

      new_i2_cost = insn_rtx_cost (newi2pat);

      new_cost = (new_i2_cost > 0 && new_i3_cost > 0)

                 ? new_i2_cost + new_i3_cost : 0;

    }

  else

    {

      new_cost = new_i3_cost;

      new_i2_cost = 0;

    }

  if (undobuf.other_insn)

    {

      int old_other_cost, new_other_cost;

      old_other_cost = (INSN_UID (undobuf.other_insn) <= last_insn_cost

                        ? uid_insn_cost[INSN_UID (undobuf.other_insn)] : 0);

      new_other_cost = insn_rtx_cost (PATTERN (undobuf.other_insn));

      if (old_other_cost > 0 && new_other_cost > 0)

        {

          old_cost += old_other_cost;

          new_cost += new_other_cost;

        }

      else

        old_cost = 0;

    }

  /* Disallow this recombination if both new_cost and old_cost are

     greater than zero, and new_cost is greater than old cost.  */

  if (old_cost > 0

      && new_cost > old_cost)

    {

      if (dump_file)

        {

          if (i1)

            {

              fprintf (dump_file,

                       "rejecting combination of insns %d, %d and %d\n",

                       INSN_UID (i1), INSN_UID (i2), INSN_UID (i3));

              fprintf (dump_file, "original costs %d + %d + %d = %d\n",

                       i1_cost, i2_cost, i3_cost, old_cost);

            }

          else

            {

              fprintf (dump_file,

                       "rejecting combination of insns %d and %d\n",

                       INSN_UID (i2), INSN_UID (i3));

              fprintf (dump_file, "original costs %d + %d = %d\n",

                       i2_cost, i3_cost, old_cost);

            }

          if (newi2pat)

            {

              fprintf (dump_file, "replacement costs %d + %d = %d\n",

                       new_i2_cost, new_i3_cost, new_cost);

            }

          else

            fprintf (dump_file, "replacement cost %d\n", new_cost);

        }

      return false;

    }

  /* Update the uid_insn_cost array with the replacement costs.  */

  uid_insn_cost[INSN_UID (i2)] = new_i2_cost;

  uid_insn_cost[INSN_UID (i3)] = new_i3_cost;

  if (i1)

    uid_insn_cost[INSN_UID (i1)] = 0;

  return true;

}

/* Main entry point for combiner.  F is the first insn of the function.

   NREGS is the first unused pseudo-reg number.

   Return nonzero if the combiner has turned an indirect jump

   instruction into a direct jump.  */

int

combine_instructions (rtx f, unsigned int nregs)

{

  rtx insn, next;

#ifdef HAVE_cc0

  rtx prev;

#endif

  int i;

  unsigned int j = 0;

  rtx links, nextlinks;

  sbitmap_iterator sbi;

  int new_direct_jump_p = 0;

  combine_attempts = 0;

  combine_merges = 0;

  combine_extras = 0;

  combine_successes = 0;

  combine_max_regno = nregs;

  rtl_hooks = combine_rtl_hooks;

  reg_stat = xcalloc (nregs, sizeof (struct reg_stat));

  init_recog_no_volatile ();

  /* Compute maximum uid value so uid_cuid can be allocated.  */

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))

    if (INSN_UID (insn) > i)

      i = INSN_UID (insn);

  uid_cuid = xmalloc ((i + 1) * sizeof (int));

  max_uid_cuid = i;

  nonzero_bits_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);

  /* Don't use reg_stat[].nonzero_bits when computing it.  This can cause

     problems when, for example, we have j <<= 1 in a loop.  */

  nonzero_sign_valid = 0;

  /* Compute the mapping from uids to cuids.

     Cuids are numbers assigned to insns, like uids,

     except that cuids increase monotonically through the code.

     Scan all SETs and see if we can deduce anything about what

     bits are known to be zero for some registers and how many copies

     of the sign bit are known to exist for those registers.

     Also set any known values so that we can use it while searching

     for what bits are known to be set.  */

  label_tick = 1;

  setup_incoming_promotions ();

  refresh_blocks = sbitmap_alloc (last_basic_block);

  sbitmap_zero (refresh_blocks);

  /* Allocate array of current insn_rtx_costs.  */

  uid_insn_cost = xcalloc (max_uid_cuid + 1, sizeof (int));

  last_insn_cost = max_uid_cuid;

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))

    {

      uid_cuid[INSN_UID (insn)] = ++i;

      subst_low_cuid = i;

      subst_insn = insn;

      if (INSN_P (insn))

        {

          note_stores (PATTERN (insn), set_nonzero_bits_and_sign_copies,

                       NULL);

          record_dead_and_set_regs (insn);

#ifdef AUTO_INC_DEC

          for (links = REG_NOTES (insn); links; links = XEXP (links, 1))

            if (REG_NOTE_KIND (links) == REG_INC)

              set_nonzero_bits_and_sign_copies (XEXP (links, 0), NULL_RTX,

                                                NULL);

#endif

          /* Record the current insn_rtx_cost of this instruction.  */

          if (NONJUMP_INSN_P (insn))

            uid_insn_cost[INSN_UID (insn)] = insn_rtx_cost (PATTERN (insn));

          if (dump_file)

            fprintf(dump_file, "insn_cost %d: %d\n",

                    INSN_UID (insn), uid_insn_cost[INSN_UID (insn)]);

        }

      if (LABEL_P (insn))

        label_tick++;

    }

  nonzero_sign_valid = 1;