Subversion Repositories scarts

/* Common subexpression elimination for GNU compiler.

   Copyright (C) 1987, 1988, 1989, 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.  */

#include "config.h"

/* stdio.h must precede rtl.h for FFS.  */

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "tm_p.h"

#include "hard-reg-set.h"

#include "regs.h"

#include "basic-block.h"

#include "flags.h"

#include "real.h"

#include "insn-config.h"

#include "recog.h"

#include "function.h"

#include "expr.h"

#include "toplev.h"

#include "output.h"

#include "ggc.h"

#include "timevar.h"

#include "except.h"

#include "target.h"

#include "params.h"

#include "rtlhooks-def.h"

#include "tree-pass.h"

/* The basic idea of common subexpression elimination is to go

   through the code, keeping a record of expressions that would

   have the same value at the current scan point, and replacing

   expressions encountered with the cheapest equivalent expression.

   It is too complicated to keep track of the different possibilities

   when control paths merge in this code; so, at each label, we forget all

   that is known and start fresh.  This can be described as processing each

   extended basic block separately.  We have a separate pass to perform

   global CSE.

   Note CSE can turn a conditional or computed jump into a nop or

   an unconditional jump.  When this occurs we arrange to run the jump

   optimizer after CSE to delete the unreachable code.

   We use two data structures to record the equivalent expressions:

   a hash table for most expressions, and a vector of "quantity

   numbers" to record equivalent (pseudo) registers.

   The use of the special data structure for registers is desirable

   because it is faster.  It is possible because registers references

   contain a fairly small number, the register number, taken from

   a contiguously allocated series, and two register references are

   identical if they have the same number.  General expressions

   do not have any such thing, so the only way to retrieve the

   information recorded on an expression other than a register

   is to keep it in a hash table.

Registers and "quantity numbers":

   At the start of each basic block, all of the (hardware and pseudo)

   registers used in the function are given distinct quantity

   numbers to indicate their contents.  During scan, when the code

   copies one register into another, we copy the quantity number.

   When a register is loaded in any other way, we allocate a new

   quantity number to describe the value generated by this operation.

   `REG_QTY (N)' records what quantity register N is currently thought

   of as containing.

   All real quantity numbers are greater than or equal to zero.

   If register N has not been assigned a quantity, `REG_QTY (N)' will

   equal -N - 1, which is always negative.

   Quantity numbers below zero do not exist and none of the `qty_table'

   entries should be referenced with a negative index.

   We also maintain a bidirectional chain of registers for each

   quantity number.  The `qty_table` members `first_reg' and `last_reg',

   and `reg_eqv_table' members `next' and `prev' hold these chains.

   The first register in a chain is the one whose lifespan is least local.

   Among equals, it is the one that was seen first.

   We replace any equivalent register with that one.

   If two registers have the same quantity number, it must be true that

   REG expressions with qty_table `mode' must be in the hash table for both

   registers and must be in the same class.

   The converse is not true.  Since hard registers may be referenced in

   any mode, two REG expressions might be equivalent in the hash table

   but not have the same quantity number if the quantity number of one

   of the registers is not the same mode as those expressions.

Constants and quantity numbers

   When a quantity has a known constant value, that value is stored

   in the appropriate qty_table `const_rtx'.  This is in addition to

   putting the constant in the hash table as is usual for non-regs.

   Whether a reg or a constant is preferred is determined by the configuration

   macro CONST_COSTS and will often depend on the constant value.  In any

   event, expressions containing constants can be simplified, by fold_rtx.

   When a quantity has a known nearly constant value (such as an address

   of a stack slot), that value is stored in the appropriate qty_table

   `const_rtx'.

   Integer constants don't have a machine mode.  However, cse

   determines the intended machine mode from the destination

   of the instruction that moves the constant.  The machine mode

   is recorded in the hash table along with the actual RTL

   constant expression so that different modes are kept separate.

Other expressions:

   To record known equivalences among expressions in general

   we use a hash table called `table'.  It has a fixed number of buckets

   that contain chains of `struct table_elt' elements for expressions.

   These chains connect the elements whose expressions have the same

   hash codes.

   Other chains through the same elements connect the elements which

   currently have equivalent values.

   Register references in an expression are canonicalized before hashing

   the expression.  This is done using `reg_qty' and qty_table `first_reg'.

   The hash code of a register reference is computed using the quantity

   number, not the register number.

   When the value of an expression changes, it is necessary to remove from the

   hash table not just that expression but all expressions whose values

   could be different as a result.

     1. If the value changing is in memory, except in special cases

     ANYTHING referring to memory could be changed.  That is because

     nobody knows where a pointer does not point.

     The function `invalidate_memory' removes what is necessary.

     The special cases are when the address is constant or is

     a constant plus a fixed register such as the frame pointer

     or a static chain pointer.  When such addresses are stored in,

     we can tell exactly which other such addresses must be invalidated

     due to overlap.  `invalidate' does this.

     All expressions that refer to non-constant

     memory addresses are also invalidated.  `invalidate_memory' does this.

     2. If the value changing is a register, all expressions

     containing references to that register, and only those,

     must be removed.

   Because searching the entire hash table for expressions that contain

   a register is very slow, we try to figure out when it isn't necessary.

   Precisely, this is necessary only when expressions have been

   entered in the hash table using this register, and then the value has

   changed, and then another expression wants to be added to refer to

   the register's new value.  This sequence of circumstances is rare

   within any one basic block.

   `REG_TICK' and `REG_IN_TABLE', accessors for members of

   cse_reg_info, are used to detect this case.  REG_TICK (i) is

   incremented whenever a value is stored in register i.

   REG_IN_TABLE (i) holds -1 if no references to register i have been

   entered in the table; otherwise, it contains the value REG_TICK (i)

   had when the references were entered.  If we want to enter a

   reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and

   remove old references.  Until we want to enter a new entry, the

   mere fact that the two vectors don't match makes the entries be

   ignored if anyone tries to match them.

   Registers themselves are entered in the hash table as well as in

   the equivalent-register chains.  However, `REG_TICK' and

   `REG_IN_TABLE' do not apply to expressions which are simple

   register references.  These expressions are removed from the table

   immediately when they become invalid, and this can be done even if

   we do not immediately search for all the expressions that refer to

   the register.

   A CLOBBER rtx in an instruction invalidates its operand for further

   reuse.  A CLOBBER or SET rtx whose operand is a MEM:BLK

   invalidates everything that resides in memory.

Related expressions:

   Constant expressions that differ only by an additive integer

   are called related.  When a constant expression is put in

   the table, the related expression with no constant term

   is also entered.  These are made to point at each other

   so that it is possible to find out if there exists any

   register equivalent to an expression related to a given expression.  */

/* Length of qty_table vector.  We know in advance we will not need

   a quantity number this big.  */

static int max_qty;

/* Next quantity number to be allocated.

   This is 1 + the largest number needed so far.  */

static int next_qty;

/* Per-qty information tracking.

   `first_reg' and `last_reg' track the head and tail of the

   chain of registers which currently contain this quantity.

   `mode' contains the machine mode of this quantity.

   `const_rtx' holds the rtx of the constant value of this

   quantity, if known.  A summations of the frame/arg pointer

   and a constant can also be entered here.  When this holds

   a known value, `const_insn' is the insn which stored the

   constant value.

   `comparison_{code,const,qty}' are used to track when a

   comparison between a quantity and some constant or register has

   been passed.  In such a case, we know the results of the comparison

   in case we see it again.  These members record a comparison that

   is known to be true.  `comparison_code' holds the rtx code of such

   a comparison, else it is set to UNKNOWN and the other two

   comparison members are undefined.  `comparison_const' holds

   the constant being compared against, or zero if the comparison

   is not against a constant.  `comparison_qty' holds the quantity

   being compared against when the result is known.  If the comparison

   is not with a register, `comparison_qty' is -1.  */

struct qty_table_elem

{

  rtx const_rtx;

  rtx const_insn;

  rtx comparison_const;

  int comparison_qty;

  unsigned int first_reg, last_reg;

  /* The sizes of these fields should match the sizes of the

     code and mode fields of struct rtx_def (see rtl.h).  */

  ENUM_BITFIELD(rtx_code) comparison_code : 16;

  ENUM_BITFIELD(machine_mode) mode : 8;

};

/* The table of all qtys, indexed by qty number.  */

static struct qty_table_elem *qty_table;

/* Structure used to pass arguments via for_each_rtx to function

   cse_change_cc_mode.  */

struct change_cc_mode_args

{

  rtx insn;

  rtx newreg;

};

#ifdef HAVE_cc0

/* For machines that have a CC0, we do not record its value in the hash

   table since its use is guaranteed to be the insn immediately following

   its definition and any other insn is presumed to invalidate it.

   Instead, we store below the value last assigned to CC0.  If it should

   happen to be a constant, it is stored in preference to the actual

   assigned value.  In case it is a constant, we store the mode in which

   the constant should be interpreted.  */

static rtx prev_insn_cc0;

static enum machine_mode prev_insn_cc0_mode;

/* Previous actual insn.  0 if at first insn of basic block.  */

static rtx prev_insn;

#endif

/* Insn being scanned.  */

static rtx this_insn;

/* Index by register number, gives the number of the next (or

   previous) register in the chain of registers sharing the same

   value.

   Or -1 if this register is at the end of the chain.

   If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined.  */

/* Per-register equivalence chain.  */

struct reg_eqv_elem

{

  int next, prev;

};

/* The table of all register equivalence chains.  */

static struct reg_eqv_elem *reg_eqv_table;

struct cse_reg_info

{

  /* The timestamp at which this register is initialized.  */

  unsigned int timestamp;

  /* The quantity number of the register's current contents.  */

  int reg_qty;

  /* The number of times the register has been altered in the current

     basic block.  */

  int reg_tick;

  /* The REG_TICK value at which rtx's containing this register are

     valid in the hash table.  If this does not equal the current

     reg_tick value, such expressions existing in the hash table are

     invalid.  */

  int reg_in_table;

  /* The SUBREG that was set when REG_TICK was last incremented.  Set

     to -1 if the last store was to the whole register, not a subreg.  */

  unsigned int subreg_ticked;

};

/* A table of cse_reg_info indexed by register numbers.  */

static struct cse_reg_info *cse_reg_info_table;

/* The size of the above table.  */

static unsigned int cse_reg_info_table_size;

/* The index of the first entry that has not been initialized.  */

static unsigned int cse_reg_info_table_first_uninitialized;

/* The timestamp at the beginning of the current run of

   cse_basic_block.  We increment this variable at the beginning of

   the current run of cse_basic_block.  The timestamp field of a

   cse_reg_info entry matches the value of this variable if and only

   if the entry has been initialized during the current run of

   cse_basic_block.  */

static unsigned int cse_reg_info_timestamp;

/* A HARD_REG_SET containing all the hard registers for which there is

   currently a REG expression in the hash table.  Note the difference

   from the above variables, which indicate if the REG is mentioned in some

   expression in the table.  */

static HARD_REG_SET hard_regs_in_table;

/* CUID of insn that starts the basic block currently being cse-processed.  */

static int cse_basic_block_start;

/* CUID of insn that ends the basic block currently being cse-processed.  */

static int cse_basic_block_end;

/* Vector mapping INSN_UIDs to cuids.

   The cuids are like uids but increase monotonically always.

   We use them to see whether a reg is used outside a given basic block.  */

static int *uid_cuid;

/* Highest UID in UID_CUID.  */

static int max_uid;

/* Get the cuid of an insn.  */

#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])

/* Nonzero if this pass has made changes, and therefore it's

   worthwhile to run the garbage collector.  */

static int cse_altered;

/* Nonzero if cse has altered conditional jump insns

   in such a way that jump optimization should be redone.  */

static int cse_jumps_altered;

/* Nonzero if we put a LABEL_REF into the hash table for an INSN without a

   REG_LABEL, we have to rerun jump after CSE to put in the note.  */

static int recorded_label_ref;

/* canon_hash stores 1 in do_not_record

   if it notices a reference to CC0, PC, or some other volatile

   subexpression.  */

static int do_not_record;

/* canon_hash stores 1 in hash_arg_in_memory

   if it notices a reference to memory within the expression being hashed.  */

static int hash_arg_in_memory;

/* The hash table contains buckets which are chains of `struct table_elt's,

   each recording one expression's information.

   That expression is in the `exp' field.

   The canon_exp field contains a canonical (from the point of view of

   alias analysis) version of the `exp' field.

   Those elements with the same hash code are chained in both directions

   through the `next_same_hash' and `prev_same_hash' fields.

   Each set of expressions with equivalent values

   are on a two-way chain through the `next_same_value'

   and `prev_same_value' fields, and all point with

   the `first_same_value' field at the first element in

   that chain.  The chain is in order of increasing cost.

   Each element's cost value is in its `cost' field.

   The `in_memory' field is nonzero for elements that

   involve any reference to memory.  These elements are removed

   whenever a write is done to an unidentified location in memory.

   To be safe, we assume that a memory address is unidentified unless

   the address is either a symbol constant or a constant plus

   the frame pointer or argument pointer.

   The `related_value' field is used to connect related expressions

   (that differ by adding an integer).

   The related expressions are chained in a circular fashion.

   `related_value' is zero for expressions for which this

   chain is not useful.

   The `cost' field stores the cost of this element's expression.

   The `regcost' field stores the value returned by approx_reg_cost for

   this element's expression.

   The `is_const' flag is set if the element is a constant (including

   a fixed address).

   The `flag' field is used as a temporary during some search routines.

   The `mode' field is usually the same as GET_MODE (`exp'), but

   if `exp' is a CONST_INT and has no machine mode then the `mode'

   field is the mode it was being used as.  Each constant is

   recorded separately for each mode it is used with.  */

struct table_elt

{

  rtx exp;

  rtx canon_exp;

  struct table_elt *next_same_hash;

  struct table_elt *prev_same_hash;

  struct table_elt *next_same_value;

  struct table_elt *prev_same_value;

  struct table_elt *first_same_value;

  struct table_elt *related_value;

  int cost;

  int regcost;

  /* The size of this field should match the size

     of the mode field of struct rtx_def (see rtl.h).  */

  ENUM_BITFIELD(machine_mode) mode : 8;

  char in_memory;

  char is_const;

  char flag;

};

/* We don't want a lot of buckets, because we rarely have very many

   things stored in the hash table, and a lot of buckets slows

   down a lot of loops that happen frequently.  */

#define HASH_SHIFT      5

#define HASH_SIZE       (1 << HASH_SHIFT)

#define HASH_MASK       (HASH_SIZE - 1)

/* Compute hash code of X in mode M.  Special-case case where X is a pseudo

   register (hard registers may require `do_not_record' to be set).  */

#define HASH(X, M)      \

 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER      \

  ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X)))    \

  : canon_hash (X, M)) & HASH_MASK)

/* Like HASH, but without side-effects.  */

#define SAFE_HASH(X, M) \

 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER      \

  ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X)))    \

  : safe_hash (X, M)) & HASH_MASK)

/* Determine whether register number N is considered a fixed register for the

   purpose of approximating register costs.

   It is desirable to replace other regs with fixed regs, to reduce need for

   non-fixed hard regs.

   A reg wins if it is either the frame pointer or designated as fixed.  */

#define FIXED_REGNO_P(N)  \

  ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \

   || fixed_regs[N] || global_regs[N])

/* Compute cost of X, as stored in the `cost' field of a table_elt.  Fixed

   hard registers and pointers into the frame are the cheapest with a cost

   of 0.  Next come pseudos with a cost of one and other hard registers with

   a cost of 2.  Aside from these special cases, call `rtx_cost'.  */

#define CHEAP_REGNO(N)                                                  \

  (REGNO_PTR_FRAME_P(N)                                                 \

   || (HARD_REGISTER_NUM_P (N)                                          \

       && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))

#define COST(X) (REG_P (X) ? 0 : notreg_cost (X, SET))

#define COST_IN(X,OUTER) (REG_P (X) ? 0 : notreg_cost (X, OUTER))

/* Get the number of times this register has been updated in this

   basic block.  */

#define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)

/* Get the point at which REG was recorded in the table.  */

#define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)

/* Get the SUBREG set at the last increment to REG_TICK (-1 if not a

   SUBREG).  */

#define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)

/* Get the quantity number for REG.  */

#define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)

/* Determine if the quantity number for register X represents a valid index

   into the qty_table.  */

#define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)

static struct table_elt *table[HASH_SIZE];

/* Chain of `struct table_elt's made so far for this function

   but currently removed from the table.  */

static struct table_elt *free_element_chain;

/* Set to the cost of a constant pool reference if one was found for a

   symbolic constant.  If this was found, it means we should try to

   convert constants into constant pool entries if they don't fit in

   the insn.  */

static int constant_pool_entries_cost;

static int constant_pool_entries_regcost;

/* This data describes a block that will be processed by cse_basic_block.  */

struct cse_basic_block_data

{

  /* Lowest CUID value of insns in block.  */

  int low_cuid;

  /* Highest CUID value of insns in block.  */

  int high_cuid;

  /* Total number of SETs in block.  */

  int nsets;

  /* Last insn in the block.  */

  rtx last;

  /* Size of current branch path, if any.  */

  int path_size;

  /* Current branch path, indicating which branches will be taken.  */

  struct branch_path

    {

      /* The branch insn.  */

      rtx branch;

      /* Whether it should be taken or not.  AROUND is the same as taken

         except that it is used when the destination label is not preceded

       by a BARRIER.  */

      enum taken {PATH_TAKEN, PATH_NOT_TAKEN, PATH_AROUND} status;

    } *path;

};

static bool fixed_base_plus_p (rtx x);

static int notreg_cost (rtx, enum rtx_code);

static int approx_reg_cost_1 (rtx *, void *);

static int approx_reg_cost (rtx);

static int preferable (int, int, int, int);

static void new_basic_block (void);

static void make_new_qty (unsigned int, enum machine_mode);

static void make_regs_eqv (unsigned int, unsigned int);

static void delete_reg_equiv (unsigned int);

static int mention_regs (rtx);

static int insert_regs (rtx, struct table_elt *, int);

static void remove_from_table (struct table_elt *, unsigned);

static struct table_elt *lookup (rtx, unsigned, enum machine_mode);

static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);

static rtx lookup_as_function (rtx, enum rtx_code);

static struct table_elt *insert (rtx, struct table_elt *, unsigned,

                                 enum machine_mode);

static void merge_equiv_classes (struct table_elt *, struct table_elt *);

static void invalidate (rtx, enum machine_mode);

static int cse_rtx_varies_p (rtx, int);

static void remove_invalid_refs (unsigned int);

static void remove_invalid_subreg_refs (unsigned int, unsigned int,

                                        enum machine_mode);

static void rehash_using_reg (rtx);

static void invalidate_memory (void);

static void invalidate_for_call (void);

static rtx use_related_value (rtx, struct table_elt *);

static inline unsigned canon_hash (rtx, enum machine_mode);

static inline unsigned safe_hash (rtx, enum machine_mode);

static unsigned hash_rtx_string (const char *);

static rtx canon_reg (rtx, rtx);

static void find_best_addr (rtx, rtx *, enum machine_mode);

static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,

                                           enum machine_mode *,

                                           enum machine_mode *);

static rtx fold_rtx (rtx, rtx);

static rtx equiv_constant (rtx);

static void record_jump_equiv (rtx, int);

static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,

                              int);

static void cse_insn (rtx, rtx);

static void cse_end_of_basic_block (rtx, struct cse_basic_block_data *,

                                    int, int);

static int addr_affects_sp_p (rtx);

static void invalidate_from_clobbers (rtx);

static rtx cse_process_notes (rtx, rtx);

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

static void invalidate_skipped_block (rtx);

static rtx cse_basic_block (rtx, rtx, struct branch_path *);

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

static int check_for_label_ref (rtx *, void *);

extern void dump_class (struct table_elt*);

static void get_cse_reg_info_1 (unsigned int regno);

static struct cse_reg_info * get_cse_reg_info (unsigned int regno);

static int check_dependence (rtx *, void *);

static void flush_hash_table (void);

static bool insn_live_p (rtx, int *);

static bool set_live_p (rtx, rtx, int *);

static bool dead_libcall_p (rtx, int *);

static int cse_change_cc_mode (rtx *, void *);

static void cse_change_cc_mode_insn (rtx, rtx);

static void cse_change_cc_mode_insns (rtx, rtx, rtx);

static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);

#undef RTL_HOOKS_GEN_LOWPART

#define RTL_HOOKS_GEN_LOWPART           gen_lowpart_if_possible

static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;

/* Nonzero if X has the form (PLUS frame-pointer integer).  We check for

   virtual regs here because the simplify_*_operation routines are called

   by integrate.c, which is called before virtual register instantiation.  */

static bool

fixed_base_plus_p (rtx x)

{

  switch (GET_CODE (x))

    {

    case REG:

      if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)

        return true;

      if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])

        return true;

      if (REGNO (x) >= FIRST_VIRTUAL_REGISTER

          && REGNO (x) <= LAST_VIRTUAL_REGISTER)

        return true;

      return false;

    case PLUS:

      if (GET_CODE (XEXP (x, 1)) != CONST_INT)

        return false;

      return fixed_base_plus_p (XEXP (x, 0));

    default:

      return false;

    }

}

/* Dump the expressions in the equivalence class indicated by CLASSP.

   This function is used only for debugging.  */

void

dump_class (struct table_elt *classp)

{

  struct table_elt *elt;

  fprintf (stderr, "Equivalence chain for ");

  print_rtl (stderr, classp->exp);

  fprintf (stderr, ": \n");

  for (elt = classp->first_same_value; elt; elt = elt->next_same_value)

    {

      print_rtl (stderr, elt->exp);

      fprintf (stderr, "\n");

    }

}

/* Subroutine of approx_reg_cost; called through for_each_rtx.  */

static int

approx_reg_cost_1 (rtx *xp, void *data)

{

  rtx x = *xp;

  int *cost_p = data;

  if (x && REG_P (x))

    {

      unsigned int regno = REGNO (x);

      if (! CHEAP_REGNO (regno))

        {

          if (regno < FIRST_PSEUDO_REGISTER)

            {

              if (SMALL_REGISTER_CLASSES)

                return 1;

              *cost_p += 2;

            }

          else

            *cost_p += 1;

        }

    }

  return 0;

}

/* Return an estimate of the cost of the registers used in an rtx.

   This is mostly the number of different REG expressions in the rtx;

   however for some exceptions like fixed registers we use a cost of

   0.  If any other hard register reference occurs, return MAX_COST.  */

static int

approx_reg_cost (rtx x)

{

  int cost = 0;

  if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))

    return MAX_COST;

  return cost;

}

/* Returns a canonical version of X for the address, from the point of view,

   that all multiplications are represented as MULT instead of the multiply

   by a power of 2 being represented as ASHIFT.  */

static rtx

canon_for_address (rtx x)

{

  enum rtx_code code;

  enum machine_mode mode;

  rtx new = 0;

  int i;

  const char *fmt;

  if (!x)

    return x;

  code = GET_CODE (x);

  mode = GET_MODE (x);

  switch (code)

    {

    case ASHIFT:

      if (GET_CODE (XEXP (x, 1)) == CONST_INT

          && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (mode)

          && INTVAL (XEXP (x, 1)) >= 0)

        {

          new = canon_for_address (XEXP (x, 0));

          new = gen_rtx_MULT (mode, new,

                              gen_int_mode ((HOST_WIDE_INT) 1

                                            << INTVAL (XEXP (x, 1)),

                                            mode));

        }

      break;

    default:

      break;

    }

  if (new)

    return new;