OSDN Git Service

2006-02-15 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / cse.c
1 /* Common subexpression elimination for GNU compiler.
2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 #include "config.h"
23 /* stdio.h must precede rtl.h for FFS.  */
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "hard-reg-set.h"
30 #include "regs.h"
31 #include "basic-block.h"
32 #include "flags.h"
33 #include "real.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "function.h"
37 #include "expr.h"
38 #include "toplev.h"
39 #include "output.h"
40 #include "ggc.h"
41 #include "timevar.h"
42 #include "except.h"
43 #include "target.h"
44 #include "params.h"
45 #include "rtlhooks-def.h"
46 #include "tree-pass.h"
47
48 /* The basic idea of common subexpression elimination is to go
49    through the code, keeping a record of expressions that would
50    have the same value at the current scan point, and replacing
51    expressions encountered with the cheapest equivalent expression.
52
53    It is too complicated to keep track of the different possibilities
54    when control paths merge in this code; so, at each label, we forget all
55    that is known and start fresh.  This can be described as processing each
56    extended basic block separately.  We have a separate pass to perform
57    global CSE.
58
59    Note CSE can turn a conditional or computed jump into a nop or
60    an unconditional jump.  When this occurs we arrange to run the jump
61    optimizer after CSE to delete the unreachable code.
62
63    We use two data structures to record the equivalent expressions:
64    a hash table for most expressions, and a vector of "quantity
65    numbers" to record equivalent (pseudo) registers.
66
67    The use of the special data structure for registers is desirable
68    because it is faster.  It is possible because registers references
69    contain a fairly small number, the register number, taken from
70    a contiguously allocated series, and two register references are
71    identical if they have the same number.  General expressions
72    do not have any such thing, so the only way to retrieve the
73    information recorded on an expression other than a register
74    is to keep it in a hash table.
75
76 Registers and "quantity numbers":
77
78    At the start of each basic block, all of the (hardware and pseudo)
79    registers used in the function are given distinct quantity
80    numbers to indicate their contents.  During scan, when the code
81    copies one register into another, we copy the quantity number.
82    When a register is loaded in any other way, we allocate a new
83    quantity number to describe the value generated by this operation.
84    `REG_QTY (N)' records what quantity register N is currently thought
85    of as containing.
86
87    All real quantity numbers are greater than or equal to zero.
88    If register N has not been assigned a quantity, `REG_QTY (N)' will
89    equal -N - 1, which is always negative.
90
91    Quantity numbers below zero do not exist and none of the `qty_table'
92    entries should be referenced with a negative index.
93
94    We also maintain a bidirectional chain of registers for each
95    quantity number.  The `qty_table` members `first_reg' and `last_reg',
96    and `reg_eqv_table' members `next' and `prev' hold these chains.
97
98    The first register in a chain is the one whose lifespan is least local.
99    Among equals, it is the one that was seen first.
100    We replace any equivalent register with that one.
101
102    If two registers have the same quantity number, it must be true that
103    REG expressions with qty_table `mode' must be in the hash table for both
104    registers and must be in the same class.
105
106    The converse is not true.  Since hard registers may be referenced in
107    any mode, two REG expressions might be equivalent in the hash table
108    but not have the same quantity number if the quantity number of one
109    of the registers is not the same mode as those expressions.
110
111 Constants and quantity numbers
112
113    When a quantity has a known constant value, that value is stored
114    in the appropriate qty_table `const_rtx'.  This is in addition to
115    putting the constant in the hash table as is usual for non-regs.
116
117    Whether a reg or a constant is preferred is determined by the configuration
118    macro CONST_COSTS and will often depend on the constant value.  In any
119    event, expressions containing constants can be simplified, by fold_rtx.
120
121    When a quantity has a known nearly constant value (such as an address
122    of a stack slot), that value is stored in the appropriate qty_table
123    `const_rtx'.
124
125    Integer constants don't have a machine mode.  However, cse
126    determines the intended machine mode from the destination
127    of the instruction that moves the constant.  The machine mode
128    is recorded in the hash table along with the actual RTL
129    constant expression so that different modes are kept separate.
130
131 Other expressions:
132
133    To record known equivalences among expressions in general
134    we use a hash table called `table'.  It has a fixed number of buckets
135    that contain chains of `struct table_elt' elements for expressions.
136    These chains connect the elements whose expressions have the same
137    hash codes.
138
139    Other chains through the same elements connect the elements which
140    currently have equivalent values.
141
142    Register references in an expression are canonicalized before hashing
143    the expression.  This is done using `reg_qty' and qty_table `first_reg'.
144    The hash code of a register reference is computed using the quantity
145    number, not the register number.
146
147    When the value of an expression changes, it is necessary to remove from the
148    hash table not just that expression but all expressions whose values
149    could be different as a result.
150
151      1. If the value changing is in memory, except in special cases
152      ANYTHING referring to memory could be changed.  That is because
153      nobody knows where a pointer does not point.
154      The function `invalidate_memory' removes what is necessary.
155
156      The special cases are when the address is constant or is
157      a constant plus a fixed register such as the frame pointer
158      or a static chain pointer.  When such addresses are stored in,
159      we can tell exactly which other such addresses must be invalidated
160      due to overlap.  `invalidate' does this.
161      All expressions that refer to non-constant
162      memory addresses are also invalidated.  `invalidate_memory' does this.
163
164      2. If the value changing is a register, all expressions
165      containing references to that register, and only those,
166      must be removed.
167
168    Because searching the entire hash table for expressions that contain
169    a register is very slow, we try to figure out when it isn't necessary.
170    Precisely, this is necessary only when expressions have been
171    entered in the hash table using this register, and then the value has
172    changed, and then another expression wants to be added to refer to
173    the register's new value.  This sequence of circumstances is rare
174    within any one basic block.
175
176    `REG_TICK' and `REG_IN_TABLE', accessors for members of
177    cse_reg_info, are used to detect this case.  REG_TICK (i) is
178    incremented whenever a value is stored in register i.
179    REG_IN_TABLE (i) holds -1 if no references to register i have been
180    entered in the table; otherwise, it contains the value REG_TICK (i)
181    had when the references were entered.  If we want to enter a
182    reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and
183    remove old references.  Until we want to enter a new entry, the
184    mere fact that the two vectors don't match makes the entries be
185    ignored if anyone tries to match them.
186
187    Registers themselves are entered in the hash table as well as in
188    the equivalent-register chains.  However, `REG_TICK' and
189    `REG_IN_TABLE' do not apply to expressions which are simple
190    register references.  These expressions are removed from the table
191    immediately when they become invalid, and this can be done even if
192    we do not immediately search for all the expressions that refer to
193    the register.
194
195    A CLOBBER rtx in an instruction invalidates its operand for further
196    reuse.  A CLOBBER or SET rtx whose operand is a MEM:BLK
197    invalidates everything that resides in memory.
198
199 Related expressions:
200
201    Constant expressions that differ only by an additive integer
202    are called related.  When a constant expression is put in
203    the table, the related expression with no constant term
204    is also entered.  These are made to point at each other
205    so that it is possible to find out if there exists any
206    register equivalent to an expression related to a given expression.  */
207
208 /* Length of qty_table vector.  We know in advance we will not need
209    a quantity number this big.  */
210
211 static int max_qty;
212
213 /* Next quantity number to be allocated.
214    This is 1 + the largest number needed so far.  */
215
216 static int next_qty;
217
218 /* Per-qty information tracking.
219
220    `first_reg' and `last_reg' track the head and tail of the
221    chain of registers which currently contain this quantity.
222
223    `mode' contains the machine mode of this quantity.
224
225    `const_rtx' holds the rtx of the constant value of this
226    quantity, if known.  A summations of the frame/arg pointer
227    and a constant can also be entered here.  When this holds
228    a known value, `const_insn' is the insn which stored the
229    constant value.
230
231    `comparison_{code,const,qty}' are used to track when a
232    comparison between a quantity and some constant or register has
233    been passed.  In such a case, we know the results of the comparison
234    in case we see it again.  These members record a comparison that
235    is known to be true.  `comparison_code' holds the rtx code of such
236    a comparison, else it is set to UNKNOWN and the other two
237    comparison members are undefined.  `comparison_const' holds
238    the constant being compared against, or zero if the comparison
239    is not against a constant.  `comparison_qty' holds the quantity
240    being compared against when the result is known.  If the comparison
241    is not with a register, `comparison_qty' is -1.  */
242
243 struct qty_table_elem
244 {
245   rtx const_rtx;
246   rtx const_insn;
247   rtx comparison_const;
248   int comparison_qty;
249   unsigned int first_reg, last_reg;
250   /* The sizes of these fields should match the sizes of the
251      code and mode fields of struct rtx_def (see rtl.h).  */
252   ENUM_BITFIELD(rtx_code) comparison_code : 16;
253   ENUM_BITFIELD(machine_mode) mode : 8;
254 };
255
256 /* The table of all qtys, indexed by qty number.  */
257 static struct qty_table_elem *qty_table;
258
259 /* Structure used to pass arguments via for_each_rtx to function
260    cse_change_cc_mode.  */
261 struct change_cc_mode_args
262 {
263   rtx insn;
264   rtx newreg;
265 };
266
267 #ifdef HAVE_cc0
268 /* For machines that have a CC0, we do not record its value in the hash
269    table since its use is guaranteed to be the insn immediately following
270    its definition and any other insn is presumed to invalidate it.
271
272    Instead, we store below the value last assigned to CC0.  If it should
273    happen to be a constant, it is stored in preference to the actual
274    assigned value.  In case it is a constant, we store the mode in which
275    the constant should be interpreted.  */
276
277 static rtx prev_insn_cc0;
278 static enum machine_mode prev_insn_cc0_mode;
279
280 /* Previous actual insn.  0 if at first insn of basic block.  */
281
282 static rtx prev_insn;
283 #endif
284
285 /* Insn being scanned.  */
286
287 static rtx this_insn;
288
289 /* Index by register number, gives the number of the next (or
290    previous) register in the chain of registers sharing the same
291    value.
292
293    Or -1 if this register is at the end of the chain.
294
295    If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined.  */
296
297 /* Per-register equivalence chain.  */
298 struct reg_eqv_elem
299 {
300   int next, prev;
301 };
302
303 /* The table of all register equivalence chains.  */
304 static struct reg_eqv_elem *reg_eqv_table;
305
306 struct cse_reg_info
307 {
308   /* The timestamp at which this register is initialized.  */
309   unsigned int timestamp;
310
311   /* The quantity number of the register's current contents.  */
312   int reg_qty;
313
314   /* The number of times the register has been altered in the current
315      basic block.  */
316   int reg_tick;
317
318   /* The REG_TICK value at which rtx's containing this register are
319      valid in the hash table.  If this does not equal the current
320      reg_tick value, such expressions existing in the hash table are
321      invalid.  */
322   int reg_in_table;
323
324   /* The SUBREG that was set when REG_TICK was last incremented.  Set
325      to -1 if the last store was to the whole register, not a subreg.  */
326   unsigned int subreg_ticked;
327 };
328
329 /* A table of cse_reg_info indexed by register numbers.  */
330 static struct cse_reg_info *cse_reg_info_table;
331
332 /* The size of the above table.  */
333 static unsigned int cse_reg_info_table_size;
334
335 /* The index of the first entry that has not been initialized.  */
336 static unsigned int cse_reg_info_table_first_uninitialized;
337
338 /* The timestamp at the beginning of the current run of
339    cse_basic_block.  We increment this variable at the beginning of
340    the current run of cse_basic_block.  The timestamp field of a
341    cse_reg_info entry matches the value of this variable if and only
342    if the entry has been initialized during the current run of
343    cse_basic_block.  */
344 static unsigned int cse_reg_info_timestamp;
345
346 /* A HARD_REG_SET containing all the hard registers for which there is
347    currently a REG expression in the hash table.  Note the difference
348    from the above variables, which indicate if the REG is mentioned in some
349    expression in the table.  */
350
351 static HARD_REG_SET hard_regs_in_table;
352
353 /* CUID of insn that starts the basic block currently being cse-processed.  */
354
355 static int cse_basic_block_start;
356
357 /* CUID of insn that ends the basic block currently being cse-processed.  */
358
359 static int cse_basic_block_end;
360
361 /* Vector mapping INSN_UIDs to cuids.
362    The cuids are like uids but increase monotonically always.
363    We use them to see whether a reg is used outside a given basic block.  */
364
365 static int *uid_cuid;
366
367 /* Highest UID in UID_CUID.  */
368 static int max_uid;
369
370 /* Get the cuid of an insn.  */
371
372 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
373
374 /* Nonzero if this pass has made changes, and therefore it's
375    worthwhile to run the garbage collector.  */
376
377 static int cse_altered;
378
379 /* Nonzero if cse has altered conditional jump insns
380    in such a way that jump optimization should be redone.  */
381
382 static int cse_jumps_altered;
383
384 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
385    REG_LABEL, we have to rerun jump after CSE to put in the note.  */
386 static int recorded_label_ref;
387
388 /* canon_hash stores 1 in do_not_record
389    if it notices a reference to CC0, PC, or some other volatile
390    subexpression.  */
391
392 static int do_not_record;
393
394 /* canon_hash stores 1 in hash_arg_in_memory
395    if it notices a reference to memory within the expression being hashed.  */
396
397 static int hash_arg_in_memory;
398
399 /* The hash table contains buckets which are chains of `struct table_elt's,
400    each recording one expression's information.
401    That expression is in the `exp' field.
402
403    The canon_exp field contains a canonical (from the point of view of
404    alias analysis) version of the `exp' field.
405
406    Those elements with the same hash code are chained in both directions
407    through the `next_same_hash' and `prev_same_hash' fields.
408
409    Each set of expressions with equivalent values
410    are on a two-way chain through the `next_same_value'
411    and `prev_same_value' fields, and all point with
412    the `first_same_value' field at the first element in
413    that chain.  The chain is in order of increasing cost.
414    Each element's cost value is in its `cost' field.
415
416    The `in_memory' field is nonzero for elements that
417    involve any reference to memory.  These elements are removed
418    whenever a write is done to an unidentified location in memory.
419    To be safe, we assume that a memory address is unidentified unless
420    the address is either a symbol constant or a constant plus
421    the frame pointer or argument pointer.
422
423    The `related_value' field is used to connect related expressions
424    (that differ by adding an integer).
425    The related expressions are chained in a circular fashion.
426    `related_value' is zero for expressions for which this
427    chain is not useful.
428
429    The `cost' field stores the cost of this element's expression.
430    The `regcost' field stores the value returned by approx_reg_cost for
431    this element's expression.
432
433    The `is_const' flag is set if the element is a constant (including
434    a fixed address).
435
436    The `flag' field is used as a temporary during some search routines.
437
438    The `mode' field is usually the same as GET_MODE (`exp'), but
439    if `exp' is a CONST_INT and has no machine mode then the `mode'
440    field is the mode it was being used as.  Each constant is
441    recorded separately for each mode it is used with.  */
442
443 struct table_elt
444 {
445   rtx exp;
446   rtx canon_exp;
447   struct table_elt *next_same_hash;
448   struct table_elt *prev_same_hash;
449   struct table_elt *next_same_value;
450   struct table_elt *prev_same_value;
451   struct table_elt *first_same_value;
452   struct table_elt *related_value;
453   int cost;
454   int regcost;
455   /* The size of this field should match the size
456      of the mode field of struct rtx_def (see rtl.h).  */
457   ENUM_BITFIELD(machine_mode) mode : 8;
458   char in_memory;
459   char is_const;
460   char flag;
461 };
462
463 /* We don't want a lot of buckets, because we rarely have very many
464    things stored in the hash table, and a lot of buckets slows
465    down a lot of loops that happen frequently.  */
466 #define HASH_SHIFT      5
467 #define HASH_SIZE       (1 << HASH_SHIFT)
468 #define HASH_MASK       (HASH_SIZE - 1)
469
470 /* Compute hash code of X in mode M.  Special-case case where X is a pseudo
471    register (hard registers may require `do_not_record' to be set).  */
472
473 #define HASH(X, M)      \
474  ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER      \
475   ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X)))    \
476   : canon_hash (X, M)) & HASH_MASK)
477
478 /* Like HASH, but without side-effects.  */
479 #define SAFE_HASH(X, M) \
480  ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER      \
481   ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X)))    \
482   : safe_hash (X, M)) & HASH_MASK)
483
484 /* Determine whether register number N is considered a fixed register for the
485    purpose of approximating register costs.
486    It is desirable to replace other regs with fixed regs, to reduce need for
487    non-fixed hard regs.
488    A reg wins if it is either the frame pointer or designated as fixed.  */
489 #define FIXED_REGNO_P(N)  \
490   ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
491    || fixed_regs[N] || global_regs[N])
492
493 /* Compute cost of X, as stored in the `cost' field of a table_elt.  Fixed
494    hard registers and pointers into the frame are the cheapest with a cost
495    of 0.  Next come pseudos with a cost of one and other hard registers with
496    a cost of 2.  Aside from these special cases, call `rtx_cost'.  */
497
498 #define CHEAP_REGNO(N)                                                  \
499   (REGNO_PTR_FRAME_P(N)                                                 \
500    || (HARD_REGISTER_NUM_P (N)                                          \
501        && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
502
503 #define COST(X) (REG_P (X) ? 0 : notreg_cost (X, SET))
504 #define COST_IN(X,OUTER) (REG_P (X) ? 0 : notreg_cost (X, OUTER))
505
506 /* Get the number of times this register has been updated in this
507    basic block.  */
508
509 #define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)
510
511 /* Get the point at which REG was recorded in the table.  */
512
513 #define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)
514
515 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
516    SUBREG).  */
517
518 #define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)
519
520 /* Get the quantity number for REG.  */
521
522 #define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)
523
524 /* Determine if the quantity number for register X represents a valid index
525    into the qty_table.  */
526
527 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
528
529 static struct table_elt *table[HASH_SIZE];
530
531 /* Chain of `struct table_elt's made so far for this function
532    but currently removed from the table.  */
533
534 static struct table_elt *free_element_chain;
535
536 /* Set to the cost of a constant pool reference if one was found for a
537    symbolic constant.  If this was found, it means we should try to
538    convert constants into constant pool entries if they don't fit in
539    the insn.  */
540
541 static int constant_pool_entries_cost;
542 static int constant_pool_entries_regcost;
543
544 /* This data describes a block that will be processed by cse_basic_block.  */
545
546 struct cse_basic_block_data
547 {
548   /* Lowest CUID value of insns in block.  */
549   int low_cuid;
550   /* Highest CUID value of insns in block.  */
551   int high_cuid;
552   /* Total number of SETs in block.  */
553   int nsets;
554   /* Last insn in the block.  */
555   rtx last;
556   /* Size of current branch path, if any.  */
557   int path_size;
558   /* Current branch path, indicating which branches will be taken.  */
559   struct branch_path
560     {
561       /* The branch insn.  */
562       rtx branch;
563       /* Whether it should be taken or not.  AROUND is the same as taken
564          except that it is used when the destination label is not preceded
565        by a BARRIER.  */
566       enum taken {PATH_TAKEN, PATH_NOT_TAKEN, PATH_AROUND} status;
567     } *path;
568 };
569
570 static bool fixed_base_plus_p (rtx x);
571 static int notreg_cost (rtx, enum rtx_code);
572 static int approx_reg_cost_1 (rtx *, void *);
573 static int approx_reg_cost (rtx);
574 static int preferable (int, int, int, int);
575 static void new_basic_block (void);
576 static void make_new_qty (unsigned int, enum machine_mode);
577 static void make_regs_eqv (unsigned int, unsigned int);
578 static void delete_reg_equiv (unsigned int);
579 static int mention_regs (rtx);
580 static int insert_regs (rtx, struct table_elt *, int);
581 static void remove_from_table (struct table_elt *, unsigned);
582 static struct table_elt *lookup (rtx, unsigned, enum machine_mode);
583 static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);
584 static rtx lookup_as_function (rtx, enum rtx_code);
585 static struct table_elt *insert (rtx, struct table_elt *, unsigned,
586                                  enum machine_mode);
587 static void merge_equiv_classes (struct table_elt *, struct table_elt *);
588 static void invalidate (rtx, enum machine_mode);
589 static int cse_rtx_varies_p (rtx, int);
590 static void remove_invalid_refs (unsigned int);
591 static void remove_invalid_subreg_refs (unsigned int, unsigned int,
592                                         enum machine_mode);
593 static void rehash_using_reg (rtx);
594 static void invalidate_memory (void);
595 static void invalidate_for_call (void);
596 static rtx use_related_value (rtx, struct table_elt *);
597
598 static inline unsigned canon_hash (rtx, enum machine_mode);
599 static inline unsigned safe_hash (rtx, enum machine_mode);
600 static unsigned hash_rtx_string (const char *);
601
602 static rtx canon_reg (rtx, rtx);
603 static void find_best_addr (rtx, rtx *, enum machine_mode);
604 static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
605                                            enum machine_mode *,
606                                            enum machine_mode *);
607 static rtx fold_rtx (rtx, rtx);
608 static rtx equiv_constant (rtx);
609 static void record_jump_equiv (rtx, int);
610 static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
611                               int);
612 static void cse_insn (rtx, rtx);
613 static void cse_end_of_basic_block (rtx, struct cse_basic_block_data *,
614                                     int, int);
615 static int addr_affects_sp_p (rtx);
616 static void invalidate_from_clobbers (rtx);
617 static rtx cse_process_notes (rtx, rtx);
618 static void invalidate_skipped_set (rtx, rtx, void *);
619 static void invalidate_skipped_block (rtx);
620 static rtx cse_basic_block (rtx, rtx, struct branch_path *);
621 static void count_reg_usage (rtx, int *, rtx, int);
622 static int check_for_label_ref (rtx *, void *);
623 extern void dump_class (struct table_elt*);
624 static void get_cse_reg_info_1 (unsigned int regno);
625 static struct cse_reg_info * get_cse_reg_info (unsigned int regno);
626 static int check_dependence (rtx *, void *);
627
628 static void flush_hash_table (void);
629 static bool insn_live_p (rtx, int *);
630 static bool set_live_p (rtx, rtx, int *);
631 static bool dead_libcall_p (rtx, int *);
632 static int cse_change_cc_mode (rtx *, void *);
633 static void cse_change_cc_mode_insn (rtx, rtx);
634 static void cse_change_cc_mode_insns (rtx, rtx, rtx);
635 static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);
636 \f
637
638 #undef RTL_HOOKS_GEN_LOWPART
639 #define RTL_HOOKS_GEN_LOWPART           gen_lowpart_if_possible
640
641 static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;
642 \f
643 /* Nonzero if X has the form (PLUS frame-pointer integer).  We check for
644    virtual regs here because the simplify_*_operation routines are called
645    by integrate.c, which is called before virtual register instantiation.  */
646
647 static bool
648 fixed_base_plus_p (rtx x)
649 {
650   switch (GET_CODE (x))
651     {
652     case REG:
653       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
654         return true;
655       if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
656         return true;
657       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
658           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
659         return true;
660       return false;
661
662     case PLUS:
663       if (GET_CODE (XEXP (x, 1)) != CONST_INT)
664         return false;
665       return fixed_base_plus_p (XEXP (x, 0));
666
667     default:
668       return false;
669     }
670 }
671
672 /* Dump the expressions in the equivalence class indicated by CLASSP.
673    This function is used only for debugging.  */
674 void
675 dump_class (struct table_elt *classp)
676 {
677   struct table_elt *elt;
678
679   fprintf (stderr, "Equivalence chain for ");
680   print_rtl (stderr, classp->exp);
681   fprintf (stderr, ": \n");
682
683   for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
684     {
685       print_rtl (stderr, elt->exp);
686       fprintf (stderr, "\n");
687     }
688 }
689
690 /* Subroutine of approx_reg_cost; called through for_each_rtx.  */
691
692 static int
693 approx_reg_cost_1 (rtx *xp, void *data)
694 {
695   rtx x = *xp;
696   int *cost_p = data;
697
698   if (x && REG_P (x))
699     {
700       unsigned int regno = REGNO (x);
701
702       if (! CHEAP_REGNO (regno))
703         {
704           if (regno < FIRST_PSEUDO_REGISTER)
705             {
706               if (SMALL_REGISTER_CLASSES)
707                 return 1;
708               *cost_p += 2;
709             }
710           else
711             *cost_p += 1;
712         }
713     }
714
715   return 0;
716 }
717
718 /* Return an estimate of the cost of the registers used in an rtx.
719    This is mostly the number of different REG expressions in the rtx;
720    however for some exceptions like fixed registers we use a cost of
721    0.  If any other hard register reference occurs, return MAX_COST.  */
722
723 static int
724 approx_reg_cost (rtx x)
725 {
726   int cost = 0;
727
728   if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
729     return MAX_COST;
730
731   return cost;
732 }
733
734 /* Returns a canonical version of X for the address, from the point of view,
735    that all multiplications are represented as MULT instead of the multiply
736    by a power of 2 being represented as ASHIFT.  */
737
738 static rtx
739 canon_for_address (rtx x)
740 {
741   enum rtx_code code;
742   enum machine_mode mode;
743   rtx new = 0;
744   int i;
745   const char *fmt;
746   
747   if (!x)
748     return x;
749   
750   code = GET_CODE (x);
751   mode = GET_MODE (x);
752   
753   switch (code)
754     {
755     case ASHIFT:
756       if (GET_CODE (XEXP (x, 1)) == CONST_INT
757           && INTVAL (XEXP (x, 1)) < GET_MODE_BITSIZE (mode)
758           && INTVAL (XEXP (x, 1)) >= 0)
759         {
760           new = canon_for_address (XEXP (x, 0));
761           new = gen_rtx_MULT (mode, new,
762                               gen_int_mode ((HOST_WIDE_INT) 1
763                                             << INTVAL (XEXP (x, 1)),
764                                             mode));
765         }
766       break;
767     default:
768       break;
769       
770     }
771   if (new)
772     return new;
773   
774   /* Now recursively process each operand of this operation.  */
775   fmt = GET_RTX_FORMAT (code);
776   for (i = 0; i < GET_RTX_LENGTH (code); i++)
777     if (fmt[i] == 'e')
778       {
779         new = canon_for_address (XEXP (x, i));
780         XEXP (x, i) = new;
781       }
782   return x;
783 }
784
785 /* Return a negative value if an rtx A, whose costs are given by COST_A
786    and REGCOST_A, is more desirable than an rtx B.
787    Return a positive value if A is less desirable, or 0 if the two are
788    equally good.  */
789 static int
790 preferable (int cost_a, int regcost_a, int cost_b, int regcost_b)
791 {
792   /* First, get rid of cases involving expressions that are entirely
793      unwanted.  */
794   if (cost_a != cost_b)
795     {
796       if (cost_a == MAX_COST)
797         return 1;
798       if (cost_b == MAX_COST)
799         return -1;
800     }
801
802   /* Avoid extending lifetimes of hardregs.  */
803   if (regcost_a != regcost_b)
804     {
805       if (regcost_a == MAX_COST)
806         return 1;
807       if (regcost_b == MAX_COST)
808         return -1;
809     }
810
811   /* Normal operation costs take precedence.  */
812   if (cost_a != cost_b)
813     return cost_a - cost_b;
814   /* Only if these are identical consider effects on register pressure.  */
815   if (regcost_a != regcost_b)
816     return regcost_a - regcost_b;
817   return 0;
818 }
819
820 /* Internal function, to compute cost when X is not a register; called
821    from COST macro to keep it simple.  */
822
823 static int
824 notreg_cost (rtx x, enum rtx_code outer)
825 {
826   return ((GET_CODE (x) == SUBREG
827            && REG_P (SUBREG_REG (x))
828            && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
829            && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
830            && (GET_MODE_SIZE (GET_MODE (x))
831                < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
832            && subreg_lowpart_p (x)
833            && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
834                                      GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
835           ? 0
836           : rtx_cost (x, outer) * 2);
837 }
838
839 \f
840 /* Initialize CSE_REG_INFO_TABLE.  */
841
842 static void
843 init_cse_reg_info (unsigned int nregs)
844 {
845   /* Do we need to grow the table?  */
846   if (nregs > cse_reg_info_table_size)
847     {
848       unsigned int new_size;
849
850       if (cse_reg_info_table_size < 2048)
851         {
852           /* Compute a new size that is a power of 2 and no smaller
853              than the large of NREGS and 64.  */
854           new_size = (cse_reg_info_table_size
855                       ? cse_reg_info_table_size : 64);
856
857           while (new_size < nregs)
858             new_size *= 2;
859         }
860       else
861         {
862           /* If we need a big table, allocate just enough to hold
863              NREGS registers.  */
864           new_size = nregs;
865         }
866
867       /* Reallocate the table with NEW_SIZE entries.  */
868       if (cse_reg_info_table)
869         free (cse_reg_info_table);
870       cse_reg_info_table = XNEWVEC (struct cse_reg_info, new_size);
871       cse_reg_info_table_size = new_size;
872       cse_reg_info_table_first_uninitialized = 0;
873     }
874
875   /* Do we have all of the first NREGS entries initialized?  */
876   if (cse_reg_info_table_first_uninitialized < nregs)
877     {
878       unsigned int old_timestamp = cse_reg_info_timestamp - 1;
879       unsigned int i;
880
881       /* Put the old timestamp on newly allocated entries so that they
882          will all be considered out of date.  We do not touch those
883          entries beyond the first NREGS entries to be nice to the
884          virtual memory.  */
885       for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
886         cse_reg_info_table[i].timestamp = old_timestamp;
887
888       cse_reg_info_table_first_uninitialized = nregs;
889     }
890 }
891
892 /* Given REGNO, initialize the cse_reg_info entry for REGNO.  */
893
894 static void
895 get_cse_reg_info_1 (unsigned int regno)
896 {
897   /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
898      entry will be considered to have been initialized.  */
899   cse_reg_info_table[regno].timestamp = cse_reg_info_timestamp;
900
901   /* Initialize the rest of the entry.  */
902   cse_reg_info_table[regno].reg_tick = 1;
903   cse_reg_info_table[regno].reg_in_table = -1;
904   cse_reg_info_table[regno].subreg_ticked = -1;
905   cse_reg_info_table[regno].reg_qty = -regno - 1;
906 }
907
908 /* Find a cse_reg_info entry for REGNO.  */
909
910 static inline struct cse_reg_info *
911 get_cse_reg_info (unsigned int regno)
912 {
913   struct cse_reg_info *p = &cse_reg_info_table[regno];
914
915   /* If this entry has not been initialized, go ahead and initialize
916      it.  */
917   if (p->timestamp != cse_reg_info_timestamp)
918     get_cse_reg_info_1 (regno);
919
920   return p;
921 }
922
923 /* Clear the hash table and initialize each register with its own quantity,
924    for a new basic block.  */
925
926 static void
927 new_basic_block (void)
928 {
929   int i;
930
931   next_qty = 0;
932
933   /* Invalidate cse_reg_info_table.  */
934   cse_reg_info_timestamp++;
935
936   /* Clear out hash table state for this pass.  */
937   CLEAR_HARD_REG_SET (hard_regs_in_table);
938
939   /* The per-quantity values used to be initialized here, but it is
940      much faster to initialize each as it is made in `make_new_qty'.  */
941
942   for (i = 0; i < HASH_SIZE; i++)
943     {
944       struct table_elt *first;
945
946       first = table[i];
947       if (first != NULL)
948         {
949           struct table_elt *last = first;
950
951           table[i] = NULL;
952
953           while (last->next_same_hash != NULL)
954             last = last->next_same_hash;
955
956           /* Now relink this hash entire chain into
957              the free element list.  */
958
959           last->next_same_hash = free_element_chain;
960           free_element_chain = first;
961         }
962     }
963
964 #ifdef HAVE_cc0
965   prev_insn = 0;
966   prev_insn_cc0 = 0;
967 #endif
968 }
969
970 /* Say that register REG contains a quantity in mode MODE not in any
971    register before and initialize that quantity.  */
972
973 static void
974 make_new_qty (unsigned int reg, enum machine_mode mode)
975 {
976   int q;
977   struct qty_table_elem *ent;
978   struct reg_eqv_elem *eqv;
979
980   gcc_assert (next_qty < max_qty);
981
982   q = REG_QTY (reg) = next_qty++;
983   ent = &qty_table[q];
984   ent->first_reg = reg;
985   ent->last_reg = reg;
986   ent->mode = mode;
987   ent->const_rtx = ent->const_insn = NULL_RTX;
988   ent->comparison_code = UNKNOWN;
989
990   eqv = &reg_eqv_table[reg];
991   eqv->next = eqv->prev = -1;
992 }
993
994 /* Make reg NEW equivalent to reg OLD.
995    OLD is not changing; NEW is.  */
996
997 static void
998 make_regs_eqv (unsigned int new, unsigned int old)
999 {
1000   unsigned int lastr, firstr;
1001   int q = REG_QTY (old);
1002   struct qty_table_elem *ent;
1003
1004   ent = &qty_table[q];
1005
1006   /* Nothing should become eqv until it has a "non-invalid" qty number.  */
1007   gcc_assert (REGNO_QTY_VALID_P (old));
1008
1009   REG_QTY (new) = q;
1010   firstr = ent->first_reg;
1011   lastr = ent->last_reg;
1012
1013   /* Prefer fixed hard registers to anything.  Prefer pseudo regs to other
1014      hard regs.  Among pseudos, if NEW will live longer than any other reg
1015      of the same qty, and that is beyond the current basic block,
1016      make it the new canonical replacement for this qty.  */
1017   if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
1018       /* Certain fixed registers might be of the class NO_REGS.  This means
1019          that not only can they not be allocated by the compiler, but
1020          they cannot be used in substitutions or canonicalizations
1021          either.  */
1022       && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
1023       && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
1024           || (new >= FIRST_PSEUDO_REGISTER
1025               && (firstr < FIRST_PSEUDO_REGISTER
1026                   || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
1027                        || (uid_cuid[REGNO_FIRST_UID (new)]
1028                            < cse_basic_block_start))
1029                       && (uid_cuid[REGNO_LAST_UID (new)]
1030                           > uid_cuid[REGNO_LAST_UID (firstr)]))))))
1031     {
1032       reg_eqv_table[firstr].prev = new;
1033       reg_eqv_table[new].next = firstr;
1034       reg_eqv_table[new].prev = -1;
1035       ent->first_reg = new;
1036     }
1037   else
1038     {
1039       /* If NEW is a hard reg (known to be non-fixed), insert at end.
1040          Otherwise, insert before any non-fixed hard regs that are at the
1041          end.  Registers of class NO_REGS cannot be used as an
1042          equivalent for anything.  */
1043       while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
1044              && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
1045              && new >= FIRST_PSEUDO_REGISTER)
1046         lastr = reg_eqv_table[lastr].prev;
1047       reg_eqv_table[new].next = reg_eqv_table[lastr].next;
1048       if (reg_eqv_table[lastr].next >= 0)
1049         reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
1050       else
1051         qty_table[q].last_reg = new;
1052       reg_eqv_table[lastr].next = new;
1053       reg_eqv_table[new].prev = lastr;
1054     }
1055 }
1056
1057 /* Remove REG from its equivalence class.  */
1058
1059 static void
1060 delete_reg_equiv (unsigned int reg)
1061 {
1062   struct qty_table_elem *ent;
1063   int q = REG_QTY (reg);
1064   int p, n;
1065
1066   /* If invalid, do nothing.  */
1067   if (! REGNO_QTY_VALID_P (reg))
1068     return;
1069
1070   ent = &qty_table[q];
1071
1072   p = reg_eqv_table[reg].prev;
1073   n = reg_eqv_table[reg].next;
1074
1075   if (n != -1)
1076     reg_eqv_table[n].prev = p;
1077   else
1078     ent->last_reg = p;
1079   if (p != -1)
1080     reg_eqv_table[p].next = n;
1081   else
1082     ent->first_reg = n;
1083
1084   REG_QTY (reg) = -reg - 1;
1085 }
1086
1087 /* Remove any invalid expressions from the hash table
1088    that refer to any of the registers contained in expression X.
1089
1090    Make sure that newly inserted references to those registers
1091    as subexpressions will be considered valid.
1092
1093    mention_regs is not called when a register itself
1094    is being stored in the table.
1095
1096    Return 1 if we have done something that may have changed the hash code
1097    of X.  */
1098
1099 static int
1100 mention_regs (rtx x)
1101 {
1102   enum rtx_code code;
1103   int i, j;
1104   const char *fmt;
1105   int changed = 0;
1106
1107   if (x == 0)
1108     return 0;
1109
1110   code = GET_CODE (x);
1111   if (code == REG)
1112     {
1113       unsigned int regno = REGNO (x);
1114       unsigned int endregno
1115         = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1116                    : hard_regno_nregs[regno][GET_MODE (x)]);
1117       unsigned int i;
1118
1119       for (i = regno; i < endregno; i++)
1120         {
1121           if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1122             remove_invalid_refs (i);
1123
1124           REG_IN_TABLE (i) = REG_TICK (i);
1125           SUBREG_TICKED (i) = -1;
1126         }
1127
1128       return 0;
1129     }
1130
1131   /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1132      pseudo if they don't use overlapping words.  We handle only pseudos
1133      here for simplicity.  */
1134   if (code == SUBREG && REG_P (SUBREG_REG (x))
1135       && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1136     {
1137       unsigned int i = REGNO (SUBREG_REG (x));
1138
1139       if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1140         {
1141           /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1142              the last store to this register really stored into this
1143              subreg, then remove the memory of this subreg.
1144              Otherwise, remove any memory of the entire register and
1145              all its subregs from the table.  */
1146           if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1147               || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1148             remove_invalid_refs (i);
1149           else
1150             remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1151         }
1152
1153       REG_IN_TABLE (i) = REG_TICK (i);
1154       SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1155       return 0;
1156     }
1157
1158   /* If X is a comparison or a COMPARE and either operand is a register
1159      that does not have a quantity, give it one.  This is so that a later
1160      call to record_jump_equiv won't cause X to be assigned a different
1161      hash code and not found in the table after that call.
1162
1163      It is not necessary to do this here, since rehash_using_reg can
1164      fix up the table later, but doing this here eliminates the need to
1165      call that expensive function in the most common case where the only
1166      use of the register is in the comparison.  */
1167
1168   if (code == COMPARE || COMPARISON_P (x))
1169     {
1170       if (REG_P (XEXP (x, 0))
1171           && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1172         if (insert_regs (XEXP (x, 0), NULL, 0))
1173           {
1174             rehash_using_reg (XEXP (x, 0));
1175             changed = 1;
1176           }
1177
1178       if (REG_P (XEXP (x, 1))
1179           && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1180         if (insert_regs (XEXP (x, 1), NULL, 0))
1181           {
1182             rehash_using_reg (XEXP (x, 1));
1183             changed = 1;
1184           }
1185     }
1186
1187   fmt = GET_RTX_FORMAT (code);
1188   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1189     if (fmt[i] == 'e')
1190       changed |= mention_regs (XEXP (x, i));
1191     else if (fmt[i] == 'E')
1192       for (j = 0; j < XVECLEN (x, i); j++)
1193         changed |= mention_regs (XVECEXP (x, i, j));
1194
1195   return changed;
1196 }
1197
1198 /* Update the register quantities for inserting X into the hash table
1199    with a value equivalent to CLASSP.
1200    (If the class does not contain a REG, it is irrelevant.)
1201    If MODIFIED is nonzero, X is a destination; it is being modified.
1202    Note that delete_reg_equiv should be called on a register
1203    before insert_regs is done on that register with MODIFIED != 0.
1204
1205    Nonzero value means that elements of reg_qty have changed
1206    so X's hash code may be different.  */
1207
1208 static int
1209 insert_regs (rtx x, struct table_elt *classp, int modified)
1210 {
1211   if (REG_P (x))
1212     {
1213       unsigned int regno = REGNO (x);
1214       int qty_valid;
1215
1216       /* If REGNO is in the equivalence table already but is of the
1217          wrong mode for that equivalence, don't do anything here.  */
1218
1219       qty_valid = REGNO_QTY_VALID_P (regno);
1220       if (qty_valid)
1221         {
1222           struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1223
1224           if (ent->mode != GET_MODE (x))
1225             return 0;
1226         }
1227
1228       if (modified || ! qty_valid)
1229         {
1230           if (classp)
1231             for (classp = classp->first_same_value;
1232                  classp != 0;
1233                  classp = classp->next_same_value)
1234               if (REG_P (classp->exp)
1235                   && GET_MODE (classp->exp) == GET_MODE (x))
1236                 {
1237                   unsigned c_regno = REGNO (classp->exp);
1238
1239                   gcc_assert (REGNO_QTY_VALID_P (c_regno));
1240
1241                   /* Suppose that 5 is hard reg and 100 and 101 are
1242                      pseudos.  Consider
1243
1244                      (set (reg:si 100) (reg:si 5))
1245                      (set (reg:si 5) (reg:si 100))
1246                      (set (reg:di 101) (reg:di 5))
1247
1248                      We would now set REG_QTY (101) = REG_QTY (5), but the
1249                      entry for 5 is in SImode.  When we use this later in
1250                      copy propagation, we get the register in wrong mode.  */
1251                   if (qty_table[REG_QTY (c_regno)].mode != GET_MODE (x))
1252                     continue;
1253
1254                   make_regs_eqv (regno, c_regno);
1255                   return 1;
1256                 }
1257
1258           /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1259              than REG_IN_TABLE to find out if there was only a single preceding
1260              invalidation - for the SUBREG - or another one, which would be
1261              for the full register.  However, if we find here that REG_TICK
1262              indicates that the register is invalid, it means that it has
1263              been invalidated in a separate operation.  The SUBREG might be used
1264              now (then this is a recursive call), or we might use the full REG
1265              now and a SUBREG of it later.  So bump up REG_TICK so that
1266              mention_regs will do the right thing.  */
1267           if (! modified
1268               && REG_IN_TABLE (regno) >= 0
1269               && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1270             REG_TICK (regno)++;
1271           make_new_qty (regno, GET_MODE (x));
1272           return 1;
1273         }
1274
1275       return 0;
1276     }
1277
1278   /* If X is a SUBREG, we will likely be inserting the inner register in the
1279      table.  If that register doesn't have an assigned quantity number at
1280      this point but does later, the insertion that we will be doing now will
1281      not be accessible because its hash code will have changed.  So assign
1282      a quantity number now.  */
1283
1284   else if (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))
1285            && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1286     {
1287       insert_regs (SUBREG_REG (x), NULL, 0);
1288       mention_regs (x);
1289       return 1;
1290     }
1291   else
1292     return mention_regs (x);
1293 }
1294 \f
1295 /* Look in or update the hash table.  */
1296
1297 /* Remove table element ELT from use in the table.
1298    HASH is its hash code, made using the HASH macro.
1299    It's an argument because often that is known in advance
1300    and we save much time not recomputing it.  */
1301
1302 static void
1303 remove_from_table (struct table_elt *elt, unsigned int hash)
1304 {
1305   if (elt == 0)
1306     return;
1307
1308   /* Mark this element as removed.  See cse_insn.  */
1309   elt->first_same_value = 0;
1310
1311   /* Remove the table element from its equivalence class.  */
1312
1313   {
1314     struct table_elt *prev = elt->prev_same_value;
1315     struct table_elt *next = elt->next_same_value;
1316
1317     if (next)
1318       next->prev_same_value = prev;
1319
1320     if (prev)
1321       prev->next_same_value = next;
1322     else
1323       {
1324         struct table_elt *newfirst = next;
1325         while (next)
1326           {
1327             next->first_same_value = newfirst;
1328             next = next->next_same_value;
1329           }
1330       }
1331   }
1332
1333   /* Remove the table element from its hash bucket.  */
1334
1335   {
1336     struct table_elt *prev = elt->prev_same_hash;
1337     struct table_elt *next = elt->next_same_hash;
1338
1339     if (next)
1340       next->prev_same_hash = prev;
1341
1342     if (prev)
1343       prev->next_same_hash = next;
1344     else if (table[hash] == elt)
1345       table[hash] = next;
1346     else
1347       {
1348         /* This entry is not in the proper hash bucket.  This can happen
1349            when two classes were merged by `merge_equiv_classes'.  Search
1350            for the hash bucket that it heads.  This happens only very
1351            rarely, so the cost is acceptable.  */
1352         for (hash = 0; hash < HASH_SIZE; hash++)
1353           if (table[hash] == elt)
1354             table[hash] = next;
1355       }
1356   }
1357
1358   /* Remove the table element from its related-value circular chain.  */
1359
1360   if (elt->related_value != 0 && elt->related_value != elt)
1361     {
1362       struct table_elt *p = elt->related_value;
1363
1364       while (p->related_value != elt)
1365         p = p->related_value;
1366       p->related_value = elt->related_value;
1367       if (p->related_value == p)
1368         p->related_value = 0;
1369     }
1370
1371   /* Now add it to the free element chain.  */
1372   elt->next_same_hash = free_element_chain;
1373   free_element_chain = elt;
1374 }
1375
1376 /* Look up X in the hash table and return its table element,
1377    or 0 if X is not in the table.
1378
1379    MODE is the machine-mode of X, or if X is an integer constant
1380    with VOIDmode then MODE is the mode with which X will be used.
1381
1382    Here we are satisfied to find an expression whose tree structure
1383    looks like X.  */
1384
1385 static struct table_elt *
1386 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1387 {
1388   struct table_elt *p;
1389
1390   for (p = table[hash]; p; p = p->next_same_hash)
1391     if (mode == p->mode && ((x == p->exp && REG_P (x))
1392                             || exp_equiv_p (x, p->exp, !REG_P (x), false)))
1393       return p;
1394
1395   return 0;
1396 }
1397
1398 /* Like `lookup' but don't care whether the table element uses invalid regs.
1399    Also ignore discrepancies in the machine mode of a register.  */
1400
1401 static struct table_elt *
1402 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1403 {
1404   struct table_elt *p;
1405
1406   if (REG_P (x))
1407     {
1408       unsigned int regno = REGNO (x);
1409
1410       /* Don't check the machine mode when comparing registers;
1411          invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
1412       for (p = table[hash]; p; p = p->next_same_hash)
1413         if (REG_P (p->exp)
1414             && REGNO (p->exp) == regno)
1415           return p;
1416     }
1417   else
1418     {
1419       for (p = table[hash]; p; p = p->next_same_hash)
1420         if (mode == p->mode
1421             && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
1422           return p;
1423     }
1424
1425   return 0;
1426 }
1427
1428 /* Look for an expression equivalent to X and with code CODE.
1429    If one is found, return that expression.  */
1430
1431 static rtx
1432 lookup_as_function (rtx x, enum rtx_code code)
1433 {
1434   struct table_elt *p
1435     = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
1436
1437   /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1438      long as we are narrowing.  So if we looked in vain for a mode narrower
1439      than word_mode before, look for word_mode now.  */
1440   if (p == 0 && code == CONST_INT
1441       && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1442     {
1443       x = copy_rtx (x);
1444       PUT_MODE (x, word_mode);
1445       p = lookup (x, SAFE_HASH (x, VOIDmode), word_mode);
1446     }
1447
1448   if (p == 0)
1449     return 0;
1450
1451   for (p = p->first_same_value; p; p = p->next_same_value)
1452     if (GET_CODE (p->exp) == code
1453         /* Make sure this is a valid entry in the table.  */
1454         && exp_equiv_p (p->exp, p->exp, 1, false))
1455       return p->exp;
1456
1457   return 0;
1458 }
1459
1460 /* Insert X in the hash table, assuming HASH is its hash code
1461    and CLASSP is an element of the class it should go in
1462    (or 0 if a new class should be made).
1463    It is inserted at the proper position to keep the class in
1464    the order cheapest first.
1465
1466    MODE is the machine-mode of X, or if X is an integer constant
1467    with VOIDmode then MODE is the mode with which X will be used.
1468
1469    For elements of equal cheapness, the most recent one
1470    goes in front, except that the first element in the list
1471    remains first unless a cheaper element is added.  The order of
1472    pseudo-registers does not matter, as canon_reg will be called to
1473    find the cheapest when a register is retrieved from the table.
1474
1475    The in_memory field in the hash table element is set to 0.
1476    The caller must set it nonzero if appropriate.
1477
1478    You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1479    and if insert_regs returns a nonzero value
1480    you must then recompute its hash code before calling here.
1481
1482    If necessary, update table showing constant values of quantities.  */
1483
1484 #define CHEAPER(X, Y) \
1485  (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1486
1487 static struct table_elt *
1488 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1489 {
1490   struct table_elt *elt;
1491
1492   /* If X is a register and we haven't made a quantity for it,
1493      something is wrong.  */
1494   gcc_assert (!REG_P (x) || REGNO_QTY_VALID_P (REGNO (x)));
1495
1496   /* If X is a hard register, show it is being put in the table.  */
1497   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1498     {
1499       unsigned int regno = REGNO (x);
1500       unsigned int endregno = regno + hard_regno_nregs[regno][GET_MODE (x)];
1501       unsigned int i;
1502
1503       for (i = regno; i < endregno; i++)
1504         SET_HARD_REG_BIT (hard_regs_in_table, i);
1505     }
1506
1507   /* Put an element for X into the right hash bucket.  */
1508
1509   elt = free_element_chain;
1510   if (elt)
1511     free_element_chain = elt->next_same_hash;
1512   else
1513     elt = XNEW (struct table_elt);
1514
1515   elt->exp = x;
1516   elt->canon_exp = NULL_RTX;
1517   elt->cost = COST (x);
1518   elt->regcost = approx_reg_cost (x);
1519   elt->next_same_value = 0;
1520   elt->prev_same_value = 0;
1521   elt->next_same_hash = table[hash];
1522   elt->prev_same_hash = 0;
1523   elt->related_value = 0;
1524   elt->in_memory = 0;
1525   elt->mode = mode;
1526   elt->is_const = (CONSTANT_P (x) || fixed_base_plus_p (x));
1527
1528   if (table[hash])
1529     table[hash]->prev_same_hash = elt;
1530   table[hash] = elt;
1531
1532   /* Put it into the proper value-class.  */
1533   if (classp)
1534     {
1535       classp = classp->first_same_value;
1536       if (CHEAPER (elt, classp))
1537         /* Insert at the head of the class.  */
1538         {
1539           struct table_elt *p;
1540           elt->next_same_value = classp;
1541           classp->prev_same_value = elt;
1542           elt->first_same_value = elt;
1543
1544           for (p = classp; p; p = p->next_same_value)
1545             p->first_same_value = elt;
1546         }
1547       else
1548         {
1549           /* Insert not at head of the class.  */
1550           /* Put it after the last element cheaper than X.  */
1551           struct table_elt *p, *next;
1552
1553           for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1554                p = next);
1555
1556           /* Put it after P and before NEXT.  */
1557           elt->next_same_value = next;
1558           if (next)
1559             next->prev_same_value = elt;
1560
1561           elt->prev_same_value = p;
1562           p->next_same_value = elt;
1563           elt->first_same_value = classp;
1564         }
1565     }
1566   else
1567     elt->first_same_value = elt;
1568
1569   /* If this is a constant being set equivalent to a register or a register
1570      being set equivalent to a constant, note the constant equivalence.
1571
1572      If this is a constant, it cannot be equivalent to a different constant,
1573      and a constant is the only thing that can be cheaper than a register.  So
1574      we know the register is the head of the class (before the constant was
1575      inserted).
1576
1577      If this is a register that is not already known equivalent to a
1578      constant, we must check the entire class.
1579
1580      If this is a register that is already known equivalent to an insn,
1581      update the qtys `const_insn' to show that `this_insn' is the latest
1582      insn making that quantity equivalent to the constant.  */
1583
1584   if (elt->is_const && classp && REG_P (classp->exp)
1585       && !REG_P (x))
1586     {
1587       int exp_q = REG_QTY (REGNO (classp->exp));
1588       struct qty_table_elem *exp_ent = &qty_table[exp_q];
1589
1590       exp_ent->const_rtx = gen_lowpart (exp_ent->mode, x);
1591       exp_ent->const_insn = this_insn;
1592     }
1593
1594   else if (REG_P (x)
1595            && classp
1596            && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1597            && ! elt->is_const)
1598     {
1599       struct table_elt *p;
1600
1601       for (p = classp; p != 0; p = p->next_same_value)
1602         {
1603           if (p->is_const && !REG_P (p->exp))
1604             {
1605               int x_q = REG_QTY (REGNO (x));
1606               struct qty_table_elem *x_ent = &qty_table[x_q];
1607
1608               x_ent->const_rtx
1609                 = gen_lowpart (GET_MODE (x), p->exp);
1610               x_ent->const_insn = this_insn;
1611               break;
1612             }
1613         }
1614     }
1615
1616   else if (REG_P (x)
1617            && qty_table[REG_QTY (REGNO (x))].const_rtx
1618            && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1619     qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1620
1621   /* If this is a constant with symbolic value,
1622      and it has a term with an explicit integer value,
1623      link it up with related expressions.  */
1624   if (GET_CODE (x) == CONST)
1625     {
1626       rtx subexp = get_related_value (x);
1627       unsigned subhash;
1628       struct table_elt *subelt, *subelt_prev;
1629
1630       if (subexp != 0)
1631         {
1632           /* Get the integer-free subexpression in the hash table.  */
1633           subhash = SAFE_HASH (subexp, mode);
1634           subelt = lookup (subexp, subhash, mode);
1635           if (subelt == 0)
1636             subelt = insert (subexp, NULL, subhash, mode);
1637           /* Initialize SUBELT's circular chain if it has none.  */
1638           if (subelt->related_value == 0)
1639             subelt->related_value = subelt;
1640           /* Find the element in the circular chain that precedes SUBELT.  */
1641           subelt_prev = subelt;
1642           while (subelt_prev->related_value != subelt)
1643             subelt_prev = subelt_prev->related_value;
1644           /* Put new ELT into SUBELT's circular chain just before SUBELT.
1645              This way the element that follows SUBELT is the oldest one.  */
1646           elt->related_value = subelt_prev->related_value;
1647           subelt_prev->related_value = elt;
1648         }
1649     }
1650
1651   return elt;
1652 }
1653 \f
1654 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1655    CLASS2 into CLASS1.  This is done when we have reached an insn which makes
1656    the two classes equivalent.
1657
1658    CLASS1 will be the surviving class; CLASS2 should not be used after this
1659    call.
1660
1661    Any invalid entries in CLASS2 will not be copied.  */
1662
1663 static void
1664 merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1665 {
1666   struct table_elt *elt, *next, *new;
1667
1668   /* Ensure we start with the head of the classes.  */
1669   class1 = class1->first_same_value;
1670   class2 = class2->first_same_value;
1671
1672   /* If they were already equal, forget it.  */
1673   if (class1 == class2)
1674     return;
1675
1676   for (elt = class2; elt; elt = next)
1677     {
1678       unsigned int hash;
1679       rtx exp = elt->exp;
1680       enum machine_mode mode = elt->mode;
1681
1682       next = elt->next_same_value;
1683
1684       /* Remove old entry, make a new one in CLASS1's class.
1685          Don't do this for invalid entries as we cannot find their
1686          hash code (it also isn't necessary).  */
1687       if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
1688         {
1689           bool need_rehash = false;
1690
1691           hash_arg_in_memory = 0;
1692           hash = HASH (exp, mode);
1693
1694           if (REG_P (exp))
1695             {
1696               need_rehash = REGNO_QTY_VALID_P (REGNO (exp));
1697               delete_reg_equiv (REGNO (exp));
1698             }
1699
1700           remove_from_table (elt, hash);
1701
1702           if (insert_regs (exp, class1, 0) || need_rehash)
1703             {
1704               rehash_using_reg (exp);
1705               hash = HASH (exp, mode);
1706             }
1707           new = insert (exp, class1, hash, mode);
1708           new->in_memory = hash_arg_in_memory;
1709         }
1710     }
1711 }
1712 \f
1713 /* Flush the entire hash table.  */
1714
1715 static void
1716 flush_hash_table (void)
1717 {
1718   int i;
1719   struct table_elt *p;
1720
1721   for (i = 0; i < HASH_SIZE; i++)
1722     for (p = table[i]; p; p = table[i])
1723       {
1724         /* Note that invalidate can remove elements
1725            after P in the current hash chain.  */
1726         if (REG_P (p->exp))
1727           invalidate (p->exp, p->mode);
1728         else
1729           remove_from_table (p, i);
1730       }
1731 }
1732 \f
1733 /* Function called for each rtx to check whether true dependence exist.  */
1734 struct check_dependence_data
1735 {
1736   enum machine_mode mode;
1737   rtx exp;
1738   rtx addr;
1739 };
1740
1741 static int
1742 check_dependence (rtx *x, void *data)
1743 {
1744   struct check_dependence_data *d = (struct check_dependence_data *) data;
1745   if (*x && MEM_P (*x))
1746     return canon_true_dependence (d->exp, d->mode, d->addr, *x,
1747                                   cse_rtx_varies_p);
1748   else
1749     return 0;
1750 }
1751 \f
1752 /* Remove from the hash table, or mark as invalid, all expressions whose
1753    values could be altered by storing in X.  X is a register, a subreg, or
1754    a memory reference with nonvarying address (because, when a memory
1755    reference with a varying address is stored in, all memory references are
1756    removed by invalidate_memory so specific invalidation is superfluous).
1757    FULL_MODE, if not VOIDmode, indicates that this much should be
1758    invalidated instead of just the amount indicated by the mode of X.  This
1759    is only used for bitfield stores into memory.
1760
1761    A nonvarying address may be just a register or just a symbol reference,
1762    or it may be either of those plus a numeric offset.  */
1763
1764 static void
1765 invalidate (rtx x, enum machine_mode full_mode)
1766 {
1767   int i;
1768   struct table_elt *p;
1769   rtx addr;
1770
1771   switch (GET_CODE (x))
1772     {
1773     case REG:
1774       {
1775         /* If X is a register, dependencies on its contents are recorded
1776            through the qty number mechanism.  Just change the qty number of
1777            the register, mark it as invalid for expressions that refer to it,
1778            and remove it itself.  */
1779         unsigned int regno = REGNO (x);
1780         unsigned int hash = HASH (x, GET_MODE (x));
1781
1782         /* Remove REGNO from any quantity list it might be on and indicate
1783            that its value might have changed.  If it is a pseudo, remove its
1784            entry from the hash table.
1785
1786            For a hard register, we do the first two actions above for any
1787            additional hard registers corresponding to X.  Then, if any of these
1788            registers are in the table, we must remove any REG entries that
1789            overlap these registers.  */
1790
1791         delete_reg_equiv (regno);
1792         REG_TICK (regno)++;
1793         SUBREG_TICKED (regno) = -1;
1794
1795         if (regno >= FIRST_PSEUDO_REGISTER)
1796           {
1797             /* Because a register can be referenced in more than one mode,
1798                we might have to remove more than one table entry.  */
1799             struct table_elt *elt;
1800
1801             while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1802               remove_from_table (elt, hash);
1803           }
1804         else
1805           {
1806             HOST_WIDE_INT in_table
1807               = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1808             unsigned int endregno
1809               = regno + hard_regno_nregs[regno][GET_MODE (x)];
1810             unsigned int tregno, tendregno, rn;
1811             struct table_elt *p, *next;
1812
1813             CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1814
1815             for (rn = regno + 1; rn < endregno; rn++)
1816               {
1817                 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1818                 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1819                 delete_reg_equiv (rn);
1820                 REG_TICK (rn)++;
1821                 SUBREG_TICKED (rn) = -1;
1822               }
1823
1824             if (in_table)
1825               for (hash = 0; hash < HASH_SIZE; hash++)
1826                 for (p = table[hash]; p; p = next)
1827                   {
1828                     next = p->next_same_hash;
1829
1830                     if (!REG_P (p->exp)
1831                         || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1832                       continue;
1833
1834                     tregno = REGNO (p->exp);
1835                     tendregno
1836                       = tregno + hard_regno_nregs[tregno][GET_MODE (p->exp)];
1837                     if (tendregno > regno && tregno < endregno)
1838                       remove_from_table (p, hash);
1839                   }
1840           }
1841       }
1842       return;
1843
1844     case SUBREG:
1845       invalidate (SUBREG_REG (x), VOIDmode);
1846       return;
1847
1848     case PARALLEL:
1849       for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1850         invalidate (XVECEXP (x, 0, i), VOIDmode);
1851       return;
1852
1853     case EXPR_LIST:
1854       /* This is part of a disjoint return value; extract the location in
1855          question ignoring the offset.  */
1856       invalidate (XEXP (x, 0), VOIDmode);
1857       return;
1858
1859     case MEM:
1860       addr = canon_rtx (get_addr (XEXP (x, 0)));
1861       /* Calculate the canonical version of X here so that
1862          true_dependence doesn't generate new RTL for X on each call.  */
1863       x = canon_rtx (x);
1864
1865       /* Remove all hash table elements that refer to overlapping pieces of
1866          memory.  */
1867       if (full_mode == VOIDmode)
1868         full_mode = GET_MODE (x);
1869
1870       for (i = 0; i < HASH_SIZE; i++)
1871         {
1872           struct table_elt *next;
1873
1874           for (p = table[i]; p; p = next)
1875             {
1876               next = p->next_same_hash;
1877               if (p->in_memory)
1878                 {
1879                   struct check_dependence_data d;
1880
1881                   /* Just canonicalize the expression once;
1882                      otherwise each time we call invalidate
1883                      true_dependence will canonicalize the
1884                      expression again.  */
1885                   if (!p->canon_exp)
1886                     p->canon_exp = canon_rtx (p->exp);
1887                   d.exp = x;
1888                   d.addr = addr;
1889                   d.mode = full_mode;
1890                   if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1891                     remove_from_table (p, i);
1892                 }
1893             }
1894         }
1895       return;
1896
1897     default:
1898       gcc_unreachable ();
1899     }
1900 }
1901 \f
1902 /* Remove all expressions that refer to register REGNO,
1903    since they are already invalid, and we are about to
1904    mark that register valid again and don't want the old
1905    expressions to reappear as valid.  */
1906
1907 static void
1908 remove_invalid_refs (unsigned int regno)
1909 {
1910   unsigned int i;
1911   struct table_elt *p, *next;
1912
1913   for (i = 0; i < HASH_SIZE; i++)
1914     for (p = table[i]; p; p = next)
1915       {
1916         next = p->next_same_hash;
1917         if (!REG_P (p->exp)
1918             && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1919           remove_from_table (p, i);
1920       }
1921 }
1922
1923 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1924    and mode MODE.  */
1925 static void
1926 remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1927                             enum machine_mode mode)
1928 {
1929   unsigned int i;
1930   struct table_elt *p, *next;
1931   unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
1932
1933   for (i = 0; i < HASH_SIZE; i++)
1934     for (p = table[i]; p; p = next)
1935       {
1936         rtx exp = p->exp;
1937         next = p->next_same_hash;
1938
1939         if (!REG_P (exp)
1940             && (GET_CODE (exp) != SUBREG
1941                 || !REG_P (SUBREG_REG (exp))
1942                 || REGNO (SUBREG_REG (exp)) != regno
1943                 || (((SUBREG_BYTE (exp)
1944                       + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
1945                     && SUBREG_BYTE (exp) <= end))
1946             && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1947           remove_from_table (p, i);
1948       }
1949 }
1950 \f
1951 /* Recompute the hash codes of any valid entries in the hash table that
1952    reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1953
1954    This is called when we make a jump equivalence.  */
1955
1956 static void
1957 rehash_using_reg (rtx x)
1958 {
1959   unsigned int i;
1960   struct table_elt *p, *next;
1961   unsigned hash;
1962
1963   if (GET_CODE (x) == SUBREG)
1964     x = SUBREG_REG (x);
1965
1966   /* If X is not a register or if the register is known not to be in any
1967      valid entries in the table, we have no work to do.  */
1968
1969   if (!REG_P (x)
1970       || REG_IN_TABLE (REGNO (x)) < 0
1971       || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
1972     return;
1973
1974   /* Scan all hash chains looking for valid entries that mention X.
1975      If we find one and it is in the wrong hash chain, move it.  */
1976
1977   for (i = 0; i < HASH_SIZE; i++)
1978     for (p = table[i]; p; p = next)
1979       {
1980         next = p->next_same_hash;
1981         if (reg_mentioned_p (x, p->exp)
1982             && exp_equiv_p (p->exp, p->exp, 1, false)
1983             && i != (hash = SAFE_HASH (p->exp, p->mode)))
1984           {
1985             if (p->next_same_hash)
1986               p->next_same_hash->prev_same_hash = p->prev_same_hash;
1987
1988             if (p->prev_same_hash)
1989               p->prev_same_hash->next_same_hash = p->next_same_hash;
1990             else
1991               table[i] = p->next_same_hash;
1992
1993             p->next_same_hash = table[hash];
1994             p->prev_same_hash = 0;
1995             if (table[hash])
1996               table[hash]->prev_same_hash = p;
1997             table[hash] = p;
1998           }
1999       }
2000 }
2001 \f
2002 /* Remove from the hash table any expression that is a call-clobbered
2003    register.  Also update their TICK values.  */
2004
2005 static void
2006 invalidate_for_call (void)
2007 {
2008   unsigned int regno, endregno;
2009   unsigned int i;
2010   unsigned hash;
2011   struct table_elt *p, *next;
2012   int in_table = 0;
2013
2014   /* Go through all the hard registers.  For each that is clobbered in
2015      a CALL_INSN, remove the register from quantity chains and update
2016      reg_tick if defined.  Also see if any of these registers is currently
2017      in the table.  */
2018
2019   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2020     if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2021       {
2022         delete_reg_equiv (regno);
2023         if (REG_TICK (regno) >= 0)
2024           {
2025             REG_TICK (regno)++;
2026             SUBREG_TICKED (regno) = -1;
2027           }
2028
2029         in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2030       }
2031
2032   /* In the case where we have no call-clobbered hard registers in the
2033      table, we are done.  Otherwise, scan the table and remove any
2034      entry that overlaps a call-clobbered register.  */
2035
2036   if (in_table)
2037     for (hash = 0; hash < HASH_SIZE; hash++)
2038       for (p = table[hash]; p; p = next)
2039         {
2040           next = p->next_same_hash;
2041
2042           if (!REG_P (p->exp)
2043               || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2044             continue;
2045
2046           regno = REGNO (p->exp);
2047           endregno = regno + hard_regno_nregs[regno][GET_MODE (p->exp)];
2048
2049           for (i = regno; i < endregno; i++)
2050             if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2051               {
2052                 remove_from_table (p, hash);
2053                 break;
2054               }
2055         }
2056 }
2057 \f
2058 /* Given an expression X of type CONST,
2059    and ELT which is its table entry (or 0 if it
2060    is not in the hash table),
2061    return an alternate expression for X as a register plus integer.
2062    If none can be found, return 0.  */
2063
2064 static rtx
2065 use_related_value (rtx x, struct table_elt *elt)
2066 {
2067   struct table_elt *relt = 0;
2068   struct table_elt *p, *q;
2069   HOST_WIDE_INT offset;
2070
2071   /* First, is there anything related known?
2072      If we have a table element, we can tell from that.
2073      Otherwise, must look it up.  */
2074
2075   if (elt != 0 && elt->related_value != 0)
2076     relt = elt;
2077   else if (elt == 0 && GET_CODE (x) == CONST)
2078     {
2079       rtx subexp = get_related_value (x);
2080       if (subexp != 0)
2081         relt = lookup (subexp,
2082                        SAFE_HASH (subexp, GET_MODE (subexp)),
2083                        GET_MODE (subexp));
2084     }
2085
2086   if (relt == 0)
2087     return 0;
2088
2089   /* Search all related table entries for one that has an
2090      equivalent register.  */
2091
2092   p = relt;
2093   while (1)
2094     {
2095       /* This loop is strange in that it is executed in two different cases.
2096          The first is when X is already in the table.  Then it is searching
2097          the RELATED_VALUE list of X's class (RELT).  The second case is when
2098          X is not in the table.  Then RELT points to a class for the related
2099          value.
2100
2101          Ensure that, whatever case we are in, that we ignore classes that have
2102          the same value as X.  */
2103
2104       if (rtx_equal_p (x, p->exp))
2105         q = 0;
2106       else
2107         for (q = p->first_same_value; q; q = q->next_same_value)
2108           if (REG_P (q->exp))
2109             break;
2110
2111       if (q)
2112         break;
2113
2114       p = p->related_value;
2115
2116       /* We went all the way around, so there is nothing to be found.
2117          Alternatively, perhaps RELT was in the table for some other reason
2118          and it has no related values recorded.  */
2119       if (p == relt || p == 0)
2120         break;
2121     }
2122
2123   if (q == 0)
2124     return 0;
2125
2126   offset = (get_integer_term (x) - get_integer_term (p->exp));
2127   /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
2128   return plus_constant (q->exp, offset);
2129 }
2130 \f
2131 /* Hash a string.  Just add its bytes up.  */
2132 static inline unsigned
2133 hash_rtx_string (const char *ps)
2134 {
2135   unsigned hash = 0;
2136   const unsigned char *p = (const unsigned char *) ps;
2137
2138   if (p)
2139     while (*p)
2140       hash += *p++;
2141
2142   return hash;
2143 }
2144
2145 /* Hash an rtx.  We are careful to make sure the value is never negative.
2146    Equivalent registers hash identically.
2147    MODE is used in hashing for CONST_INTs only;
2148    otherwise the mode of X is used.
2149
2150    Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2151
2152    If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2153    a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
2154
2155    Note that cse_insn knows that the hash code of a MEM expression
2156    is just (int) MEM plus the hash code of the address.  */
2157
2158 unsigned
2159 hash_rtx (rtx x, enum machine_mode mode, int *do_not_record_p,
2160           int *hash_arg_in_memory_p, bool have_reg_qty)
2161 {
2162   int i, j;
2163   unsigned hash = 0;
2164   enum rtx_code code;
2165   const char *fmt;
2166
2167   /* Used to turn recursion into iteration.  We can't rely on GCC's
2168      tail-recursion elimination since we need to keep accumulating values
2169      in HASH.  */
2170  repeat:
2171   if (x == 0)
2172     return hash;
2173
2174   code = GET_CODE (x);
2175   switch (code)
2176     {
2177     case REG:
2178       {
2179         unsigned int regno = REGNO (x);
2180
2181         if (!reload_completed)
2182           {
2183             /* On some machines, we can't record any non-fixed hard register,
2184                because extending its life will cause reload problems.  We
2185                consider ap, fp, sp, gp to be fixed for this purpose.
2186
2187                We also consider CCmode registers to be fixed for this purpose;
2188                failure to do so leads to failure to simplify 0<100 type of
2189                conditionals.
2190
2191                On all machines, we can't record any global registers.
2192                Nor should we record any register that is in a small
2193                class, as defined by CLASS_LIKELY_SPILLED_P.  */
2194             bool record;
2195
2196             if (regno >= FIRST_PSEUDO_REGISTER)
2197               record = true;
2198             else if (x == frame_pointer_rtx
2199                      || x == hard_frame_pointer_rtx
2200                      || x == arg_pointer_rtx
2201                      || x == stack_pointer_rtx
2202                      || x == pic_offset_table_rtx)
2203               record = true;
2204             else if (global_regs[regno])
2205               record = false;
2206             else if (fixed_regs[regno])
2207               record = true;
2208             else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2209               record = true;
2210             else if (SMALL_REGISTER_CLASSES)
2211               record = false;
2212             else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
2213               record = false;
2214             else
2215               record = true;
2216
2217             if (!record)
2218               {
2219                 *do_not_record_p = 1;
2220                 return 0;
2221               }
2222           }
2223
2224         hash += ((unsigned int) REG << 7);
2225         hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2226         return hash;
2227       }
2228
2229     /* We handle SUBREG of a REG specially because the underlying
2230        reg changes its hash value with every value change; we don't
2231        want to have to forget unrelated subregs when one subreg changes.  */
2232     case SUBREG:
2233       {
2234         if (REG_P (SUBREG_REG (x)))
2235           {
2236             hash += (((unsigned int) SUBREG << 7)
2237                      + REGNO (SUBREG_REG (x))
2238                      + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2239             return hash;
2240           }
2241         break;
2242       }
2243
2244     case CONST_INT:
2245       hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2246                + (unsigned int) INTVAL (x));
2247       return hash;
2248
2249     case CONST_DOUBLE:
2250       /* This is like the general case, except that it only counts
2251          the integers representing the constant.  */
2252       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2253       if (GET_MODE (x) != VOIDmode)
2254         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2255       else
2256         hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2257                  + (unsigned int) CONST_DOUBLE_HIGH (x));
2258       return hash;
2259
2260     case CONST_VECTOR:
2261       {
2262         int units;
2263         rtx elt;
2264
2265         units = CONST_VECTOR_NUNITS (x);
2266
2267         for (i = 0; i < units; ++i)
2268           {
2269             elt = CONST_VECTOR_ELT (x, i);
2270             hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
2271                               hash_arg_in_memory_p, have_reg_qty);
2272           }
2273
2274         return hash;
2275       }
2276
2277       /* Assume there is only one rtx object for any given label.  */
2278     case LABEL_REF:
2279       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2280          differences and differences between each stage's debugging dumps.  */
2281          hash += (((unsigned int) LABEL_REF << 7)
2282                   + CODE_LABEL_NUMBER (XEXP (x, 0)));
2283       return hash;
2284
2285     case SYMBOL_REF:
2286       {
2287         /* Don't hash on the symbol's address to avoid bootstrap differences.
2288            Different hash values may cause expressions to be recorded in
2289            different orders and thus different registers to be used in the
2290            final assembler.  This also avoids differences in the dump files
2291            between various stages.  */
2292         unsigned int h = 0;
2293         const unsigned char *p = (const unsigned char *) XSTR (x, 0);
2294
2295         while (*p)
2296           h += (h << 7) + *p++; /* ??? revisit */
2297
2298         hash += ((unsigned int) SYMBOL_REF << 7) + h;
2299         return hash;
2300       }
2301
2302     case MEM:
2303       /* We don't record if marked volatile or if BLKmode since we don't
2304          know the size of the move.  */
2305       if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2306         {
2307           *do_not_record_p = 1;
2308           return 0;
2309         }
2310       if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2311         *hash_arg_in_memory_p = 1;
2312
2313       /* Now that we have already found this special case,
2314          might as well speed it up as much as possible.  */
2315       hash += (unsigned) MEM;
2316       x = XEXP (x, 0);
2317       goto repeat;
2318
2319     case USE:
2320       /* A USE that mentions non-volatile memory needs special
2321          handling since the MEM may be BLKmode which normally
2322          prevents an entry from being made.  Pure calls are
2323          marked by a USE which mentions BLKmode memory.
2324          See calls.c:emit_call_1.  */
2325       if (MEM_P (XEXP (x, 0))
2326           && ! MEM_VOLATILE_P (XEXP (x, 0)))
2327         {
2328           hash += (unsigned) USE;
2329           x = XEXP (x, 0);
2330
2331           if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2332             *hash_arg_in_memory_p = 1;
2333
2334           /* Now that we have already found this special case,
2335              might as well speed it up as much as possible.  */
2336           hash += (unsigned) MEM;
2337           x = XEXP (x, 0);
2338           goto repeat;
2339         }
2340       break;
2341
2342     case PRE_DEC:
2343     case PRE_INC:
2344     case POST_DEC:
2345     case POST_INC:
2346     case PRE_MODIFY:
2347     case POST_MODIFY:
2348     case PC:
2349     case CC0:
2350     case CALL:
2351     case UNSPEC_VOLATILE:
2352       *do_not_record_p = 1;
2353       return 0;
2354
2355     case ASM_OPERANDS:
2356       if (MEM_VOLATILE_P (x))
2357         {
2358           *do_not_record_p = 1;
2359           return 0;
2360         }
2361       else
2362         {
2363           /* We don't want to take the filename and line into account.  */
2364           hash += (unsigned) code + (unsigned) GET_MODE (x)
2365             + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
2366             + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2367             + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2368
2369           if (ASM_OPERANDS_INPUT_LENGTH (x))
2370             {
2371               for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2372                 {
2373                   hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
2374                                      GET_MODE (ASM_OPERANDS_INPUT (x, i)),
2375                                      do_not_record_p, hash_arg_in_memory_p,
2376                                      have_reg_qty)
2377                            + hash_rtx_string
2378                                 (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
2379                 }
2380
2381               hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2382               x = ASM_OPERANDS_INPUT (x, 0);
2383               mode = GET_MODE (x);
2384               goto repeat;
2385             }
2386
2387           return hash;
2388         }
2389       break;
2390
2391     default:
2392       break;
2393     }
2394
2395   i = GET_RTX_LENGTH (code) - 1;
2396   hash += (unsigned) code + (unsigned) GET_MODE (x);
2397   fmt = GET_RTX_FORMAT (code);
2398   for (; i >= 0; i--)
2399     {
2400       switch (fmt[i])
2401         {
2402         case 'e':
2403           /* If we are about to do the last recursive call
2404              needed at this level, change it into iteration.
2405              This function  is called enough to be worth it.  */
2406           if (i == 0)
2407             {
2408               x = XEXP (x, i);
2409               goto repeat;
2410             }
2411
2412           hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
2413                             hash_arg_in_memory_p, have_reg_qty);
2414           break;
2415
2416         case 'E':
2417           for (j = 0; j < XVECLEN (x, i); j++)
2418             hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
2419                               hash_arg_in_memory_p, have_reg_qty);
2420           break;
2421
2422         case 's':
2423           hash += hash_rtx_string (XSTR (x, i));
2424           break;
2425
2426         case 'i':
2427           hash += (unsigned int) XINT (x, i);
2428           break;
2429
2430         case '0': case 't':
2431           /* Unused.  */
2432           break;
2433
2434         default:
2435           gcc_unreachable ();
2436         }
2437     }
2438
2439   return hash;
2440 }
2441
2442 /* Hash an rtx X for cse via hash_rtx.
2443    Stores 1 in do_not_record if any subexpression is volatile.
2444    Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2445    does not have the RTX_UNCHANGING_P bit set.  */
2446
2447 static inline unsigned
2448 canon_hash (rtx x, enum machine_mode mode)
2449 {
2450   return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
2451 }
2452
2453 /* Like canon_hash but with no side effects, i.e. do_not_record
2454    and hash_arg_in_memory are not changed.  */
2455
2456 static inline unsigned
2457 safe_hash (rtx x, enum machine_mode mode)
2458 {
2459   int dummy_do_not_record;
2460   return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
2461 }
2462 \f
2463 /* Return 1 iff X and Y would canonicalize into the same thing,
2464    without actually constructing the canonicalization of either one.
2465    If VALIDATE is nonzero,
2466    we assume X is an expression being processed from the rtl
2467    and Y was found in the hash table.  We check register refs
2468    in Y for being marked as valid.
2469
2470    If FOR_GCSE is true, we compare X and Y for equivalence for GCSE.  */
2471
2472 int
2473 exp_equiv_p (rtx x, rtx y, int validate, bool for_gcse)
2474 {
2475   int i, j;
2476   enum rtx_code code;
2477   const char *fmt;
2478
2479   /* Note: it is incorrect to assume an expression is equivalent to itself
2480      if VALIDATE is nonzero.  */
2481   if (x == y && !validate)
2482     return 1;
2483
2484   if (x == 0 || y == 0)
2485     return x == y;
2486
2487   code = GET_CODE (x);
2488   if (code != GET_CODE (y))
2489     return 0;
2490
2491   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
2492   if (GET_MODE (x) != GET_MODE (y))
2493     return 0;
2494
2495   switch (code)
2496     {
2497     case PC:
2498     case CC0:
2499     case CONST_INT:
2500     case CONST_DOUBLE:
2501       return x == y;
2502
2503     case LABEL_REF:
2504       return XEXP (x, 0) == XEXP (y, 0);
2505
2506     case SYMBOL_REF:
2507       return XSTR (x, 0) == XSTR (y, 0);
2508
2509     case REG:
2510       if (for_gcse)
2511         return REGNO (x) == REGNO (y);
2512       else
2513         {
2514           unsigned int regno = REGNO (y);
2515           unsigned int i;
2516           unsigned int endregno
2517             = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2518                        : hard_regno_nregs[regno][GET_MODE (y)]);
2519
2520           /* If the quantities are not the same, the expressions are not
2521              equivalent.  If there are and we are not to validate, they
2522              are equivalent.  Otherwise, ensure all regs are up-to-date.  */
2523
2524           if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2525             return 0;
2526
2527           if (! validate)
2528             return 1;
2529
2530           for (i = regno; i < endregno; i++)
2531             if (REG_IN_TABLE (i) != REG_TICK (i))
2532               return 0;
2533
2534           return 1;
2535         }
2536
2537     case MEM:
2538       if (for_gcse)
2539         {
2540           /* A volatile mem should not be considered equivalent to any
2541              other.  */
2542           if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2543             return 0;
2544
2545           /* Can't merge two expressions in different alias sets, since we
2546              can decide that the expression is transparent in a block when
2547              it isn't, due to it being set with the different alias set.
2548
2549              Also, can't merge two expressions with different MEM_ATTRS.
2550              They could e.g. be two different entities allocated into the
2551              same space on the stack (see e.g. PR25130).  In that case, the
2552              MEM addresses can be the same, even though the two MEMs are
2553              absolutely not equivalent.  
2554    
2555              But because really all MEM attributes should be the same for
2556              equivalent MEMs, we just use the invariant that MEMs that have
2557              the same attributes share the same mem_attrs data structure.  */
2558           if (MEM_ATTRS (x) != MEM_ATTRS (y))
2559             return 0;
2560         }
2561       break;
2562
2563     /*  For commutative operations, check both orders.  */
2564     case PLUS:
2565     case MULT:
2566     case AND:
2567     case IOR:
2568     case XOR:
2569     case NE:
2570     case EQ:
2571       return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
2572                              validate, for_gcse)
2573                && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2574                                 validate, for_gcse))
2575               || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2576                                 validate, for_gcse)
2577                   && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2578                                    validate, for_gcse)));
2579
2580     case ASM_OPERANDS:
2581       /* We don't use the generic code below because we want to
2582          disregard filename and line numbers.  */
2583
2584       /* A volatile asm isn't equivalent to any other.  */
2585       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2586         return 0;
2587
2588       if (GET_MODE (x) != GET_MODE (y)
2589           || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2590           || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2591                      ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2592           || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2593           || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2594         return 0;
2595
2596       if (ASM_OPERANDS_INPUT_LENGTH (x))
2597         {
2598           for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2599             if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2600                                ASM_OPERANDS_INPUT (y, i),
2601                                validate, for_gcse)
2602                 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2603                            ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2604               return 0;
2605         }
2606
2607       return 1;
2608
2609     default:
2610       break;
2611     }
2612
2613   /* Compare the elements.  If any pair of corresponding elements
2614      fail to match, return 0 for the whole thing.  */
2615
2616   fmt = GET_RTX_FORMAT (code);
2617   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2618     {
2619       switch (fmt[i])
2620         {
2621         case 'e':
2622           if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
2623                               validate, for_gcse))
2624             return 0;
2625           break;
2626
2627         case 'E':
2628           if (XVECLEN (x, i) != XVECLEN (y, i))
2629             return 0;
2630           for (j = 0; j < XVECLEN (x, i); j++)
2631             if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2632                                 validate, for_gcse))
2633               return 0;
2634           break;
2635
2636         case 's':
2637           if (strcmp (XSTR (x, i), XSTR (y, i)))
2638             return 0;
2639           break;
2640
2641         case 'i':
2642           if (XINT (x, i) != XINT (y, i))
2643             return 0;
2644           break;
2645
2646         case 'w':
2647           if (XWINT (x, i) != XWINT (y, i))
2648             return 0;
2649           break;
2650
2651         case '0':
2652         case 't':
2653           break;
2654
2655         default:
2656           gcc_unreachable ();
2657         }
2658     }
2659
2660   return 1;
2661 }
2662 \f
2663 /* Return 1 if X has a value that can vary even between two
2664    executions of the program.  0 means X can be compared reliably
2665    against certain constants or near-constants.  */
2666
2667 static int
2668 cse_rtx_varies_p (rtx x, int from_alias)
2669 {
2670   /* We need not check for X and the equivalence class being of the same
2671      mode because if X is equivalent to a constant in some mode, it
2672      doesn't vary in any mode.  */
2673
2674   if (REG_P (x)
2675       && REGNO_QTY_VALID_P (REGNO (x)))
2676     {
2677       int x_q = REG_QTY (REGNO (x));
2678       struct qty_table_elem *x_ent = &qty_table[x_q];
2679
2680       if (GET_MODE (x) == x_ent->mode
2681           && x_ent->const_rtx != NULL_RTX)
2682         return 0;
2683     }
2684
2685   if (GET_CODE (x) == PLUS
2686       && GET_CODE (XEXP (x, 1)) == CONST_INT
2687       && REG_P (XEXP (x, 0))
2688       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2689     {
2690       int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2691       struct qty_table_elem *x0_ent = &qty_table[x0_q];
2692
2693       if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2694           && x0_ent->const_rtx != NULL_RTX)
2695         return 0;
2696     }
2697
2698   /* This can happen as the result of virtual register instantiation, if
2699      the initial constant is too large to be a valid address.  This gives
2700      us a three instruction sequence, load large offset into a register,
2701      load fp minus a constant into a register, then a MEM which is the
2702      sum of the two `constant' registers.  */
2703   if (GET_CODE (x) == PLUS
2704       && REG_P (XEXP (x, 0))
2705       && REG_P (XEXP (x, 1))
2706       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2707       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2708     {
2709       int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2710       int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2711       struct qty_table_elem *x0_ent = &qty_table[x0_q];
2712       struct qty_table_elem *x1_ent = &qty_table[x1_q];
2713
2714       if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2715           && x0_ent->const_rtx != NULL_RTX
2716           && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2717           && x1_ent->const_rtx != NULL_RTX)
2718         return 0;
2719     }
2720
2721   return rtx_varies_p (x, from_alias);
2722 }
2723 \f
2724 /* Subroutine of canon_reg.  Pass *XLOC through canon_reg, and validate
2725    the result if necessary.  INSN is as for canon_reg.  */
2726
2727 static void
2728 validate_canon_reg (rtx *xloc, rtx insn)
2729 {
2730   rtx new = canon_reg (*xloc, insn);
2731   int insn_code;
2732
2733   /* If replacing pseudo with hard reg or vice versa, ensure the
2734      insn remains valid.  Likewise if the insn has MATCH_DUPs.  */
2735   if (insn != 0 && new != 0
2736       && REG_P (new) && REG_P (*xloc)
2737       && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2738            != (REGNO (*xloc) < FIRST_PSEUDO_REGISTER))
2739           || GET_MODE (new) != GET_MODE (*xloc)
2740           || (insn_code = recog_memoized (insn)) < 0
2741           || insn_data[insn_code].n_dups > 0))
2742     validate_change (insn, xloc, new, 1);
2743   else
2744     *xloc = new;
2745 }
2746
2747 /* Canonicalize an expression:
2748    replace each register reference inside it
2749    with the "oldest" equivalent register.
2750
2751    If INSN is nonzero and we are replacing a pseudo with a hard register
2752    or vice versa, validate_change is used to ensure that INSN remains valid
2753    after we make our substitution.  The calls are made with IN_GROUP nonzero
2754    so apply_change_group must be called upon the outermost return from this
2755    function (unless INSN is zero).  The result of apply_change_group can
2756    generally be discarded since the changes we are making are optional.  */
2757
2758 static rtx
2759 canon_reg (rtx x, rtx insn)
2760 {
2761   int i;
2762   enum rtx_code code;
2763   const char *fmt;
2764
2765   if (x == 0)
2766     return x;
2767
2768   code = GET_CODE (x);
2769   switch (code)
2770     {
2771     case PC:
2772     case CC0:
2773     case CONST:
2774     case CONST_INT:
2775     case CONST_DOUBLE:
2776     case CONST_VECTOR:
2777     case SYMBOL_REF:
2778     case LABEL_REF:
2779     case ADDR_VEC:
2780     case ADDR_DIFF_VEC:
2781       return x;
2782
2783     case REG:
2784       {
2785         int first;
2786         int q;
2787         struct qty_table_elem *ent;
2788
2789         /* Never replace a hard reg, because hard regs can appear
2790            in more than one machine mode, and we must preserve the mode
2791            of each occurrence.  Also, some hard regs appear in
2792            MEMs that are shared and mustn't be altered.  Don't try to
2793            replace any reg that maps to a reg of class NO_REGS.  */
2794         if (REGNO (x) < FIRST_PSEUDO_REGISTER
2795             || ! REGNO_QTY_VALID_P (REGNO (x)))
2796           return x;
2797
2798         q = REG_QTY (REGNO (x));
2799         ent = &qty_table[q];
2800         first = ent->first_reg;
2801         return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2802                 : REGNO_REG_CLASS (first) == NO_REGS ? x
2803                 : gen_rtx_REG (ent->mode, first));
2804       }
2805
2806     default:
2807       break;
2808     }
2809
2810   fmt = GET_RTX_FORMAT (code);
2811   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2812     {
2813       int j;
2814
2815       if (fmt[i] == 'e')
2816         validate_canon_reg (&XEXP (x, i), insn);
2817       else if (fmt[i] == 'E')
2818         for (j = 0; j < XVECLEN (x, i); j++)
2819           validate_canon_reg (&XVECEXP (x, i, j), insn);
2820     }
2821
2822   return x;
2823 }
2824 \f
2825 /* LOC is a location within INSN that is an operand address (the contents of
2826    a MEM).  Find the best equivalent address to use that is valid for this
2827    insn.
2828
2829    On most CISC machines, complicated address modes are costly, and rtx_cost
2830    is a good approximation for that cost.  However, most RISC machines have
2831    only a few (usually only one) memory reference formats.  If an address is
2832    valid at all, it is often just as cheap as any other address.  Hence, for
2833    RISC machines, we use `address_cost' to compare the costs of various
2834    addresses.  For two addresses of equal cost, choose the one with the
2835    highest `rtx_cost' value as that has the potential of eliminating the
2836    most insns.  For equal costs, we choose the first in the equivalence
2837    class.  Note that we ignore the fact that pseudo registers are cheaper than
2838    hard registers here because we would also prefer the pseudo registers.  */
2839
2840 static void
2841 find_best_addr (rtx insn, rtx *loc, enum machine_mode mode)
2842 {
2843   struct table_elt *elt;
2844   rtx addr = *loc;
2845   struct table_elt *p;
2846   int found_better = 1;
2847   int save_do_not_record = do_not_record;
2848   int save_hash_arg_in_memory = hash_arg_in_memory;
2849   int addr_volatile;
2850   int regno;
2851   unsigned hash;
2852
2853   /* Do not try to replace constant addresses or addresses of local and
2854      argument slots.  These MEM expressions are made only once and inserted
2855      in many instructions, as well as being used to control symbol table
2856      output.  It is not safe to clobber them.
2857
2858      There are some uncommon cases where the address is already in a register
2859      for some reason, but we cannot take advantage of that because we have
2860      no easy way to unshare the MEM.  In addition, looking up all stack
2861      addresses is costly.  */
2862   if ((GET_CODE (addr) == PLUS
2863        && REG_P (XEXP (addr, 0))
2864        && GET_CODE (XEXP (addr, 1)) == CONST_INT
2865        && (regno = REGNO (XEXP (addr, 0)),
2866            regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2867            || regno == ARG_POINTER_REGNUM))
2868       || (REG_P (addr)
2869           && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2870               || regno == HARD_FRAME_POINTER_REGNUM
2871               || regno == ARG_POINTER_REGNUM))
2872       || CONSTANT_ADDRESS_P (addr))
2873     return;
2874
2875   /* If this address is not simply a register, try to fold it.  This will
2876      sometimes simplify the expression.  Many simplifications
2877      will not be valid, but some, usually applying the associative rule, will
2878      be valid and produce better code.  */
2879   if (!REG_P (addr))
2880     {
2881       rtx folded = canon_for_address (fold_rtx (addr, NULL_RTX));
2882
2883       if (folded != addr)
2884         {
2885           int addr_folded_cost = address_cost (folded, mode);
2886           int addr_cost = address_cost (addr, mode);
2887
2888           if ((addr_folded_cost < addr_cost
2889                || (addr_folded_cost == addr_cost
2890                    /* ??? The rtx_cost comparison is left over from an older
2891                       version of this code.  It is probably no longer helpful.*/
2892                    && (rtx_cost (folded, MEM) > rtx_cost (addr, MEM)
2893                        || approx_reg_cost (folded) < approx_reg_cost (addr))))
2894               && validate_change (insn, loc, folded, 0))
2895             addr = folded;
2896         }
2897     }
2898
2899   /* If this address is not in the hash table, we can't look for equivalences
2900      of the whole address.  Also, ignore if volatile.  */
2901
2902   do_not_record = 0;
2903   hash = HASH (addr, Pmode);
2904   addr_volatile = do_not_record;
2905   do_not_record = save_do_not_record;
2906   hash_arg_in_memory = save_hash_arg_in_memory;
2907
2908   if (addr_volatile)
2909     return;
2910
2911   elt = lookup (addr, hash, Pmode);
2912
2913   if (elt)
2914     {
2915       /* We need to find the best (under the criteria documented above) entry
2916          in the class that is valid.  We use the `flag' field to indicate
2917          choices that were invalid and iterate until we can't find a better
2918          one that hasn't already been tried.  */
2919
2920       for (p = elt->first_same_value; p; p = p->next_same_value)
2921         p->flag = 0;
2922
2923       while (found_better)
2924         {
2925           int best_addr_cost = address_cost (*loc, mode);
2926           int best_rtx_cost = (elt->cost + 1) >> 1;
2927           int exp_cost;
2928           struct table_elt *best_elt = elt;
2929
2930           found_better = 0;
2931           for (p = elt->first_same_value; p; p = p->next_same_value)
2932             if (! p->flag)
2933               {
2934                 if ((REG_P (p->exp)
2935                      || exp_equiv_p (p->exp, p->exp, 1, false))
2936                     && ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
2937                         || (exp_cost == best_addr_cost
2938                             && ((p->cost + 1) >> 1) > best_rtx_cost)))
2939                   {
2940                     found_better = 1;
2941                     best_addr_cost = exp_cost;
2942                     best_rtx_cost = (p->cost + 1) >> 1;
2943                     best_elt = p;
2944                   }
2945               }
2946
2947           if (found_better)
2948             {
2949               if (validate_change (insn, loc,
2950                                    canon_reg (copy_rtx (best_elt->exp),
2951                                               NULL_RTX), 0))
2952                 return;
2953               else
2954                 best_elt->flag = 1;
2955             }
2956         }
2957     }
2958
2959   /* If the address is a binary operation with the first operand a register
2960      and the second a constant, do the same as above, but looking for
2961      equivalences of the register.  Then try to simplify before checking for
2962      the best address to use.  This catches a few cases:  First is when we
2963      have REG+const and the register is another REG+const.  We can often merge
2964      the constants and eliminate one insn and one register.  It may also be
2965      that a machine has a cheap REG+REG+const.  Finally, this improves the
2966      code on the Alpha for unaligned byte stores.  */
2967
2968   if (flag_expensive_optimizations
2969       && ARITHMETIC_P (*loc)
2970       && REG_P (XEXP (*loc, 0)))
2971     {
2972       rtx op1 = XEXP (*loc, 1);
2973
2974       do_not_record = 0;
2975       hash = HASH (XEXP (*loc, 0), Pmode);
2976       do_not_record = save_do_not_record;
2977       hash_arg_in_memory = save_hash_arg_in_memory;
2978
2979       elt = lookup (XEXP (*loc, 0), hash, Pmode);
2980       if (elt == 0)
2981         return;
2982
2983       /* We need to find the best (under the criteria documented above) entry
2984          in the class that is valid.  We use the `flag' field to indicate
2985          choices that were invalid and iterate until we can't find a better
2986          one that hasn't already been tried.  */
2987
2988       for (p = elt->first_same_value; p; p = p->next_same_value)
2989         p->flag = 0;
2990
2991       while (found_better)
2992         {
2993           int best_addr_cost = address_cost (*loc, mode);
2994           int best_rtx_cost = (COST (*loc) + 1) >> 1;
2995           struct table_elt *best_elt = elt;
2996           rtx best_rtx = *loc;
2997           int count;
2998
2999           /* This is at worst case an O(n^2) algorithm, so limit our search
3000              to the first 32 elements on the list.  This avoids trouble
3001              compiling code with very long basic blocks that can easily
3002              call simplify_gen_binary so many times that we run out of
3003              memory.  */
3004
3005           found_better = 0;
3006           for (p = elt->first_same_value, count = 0;
3007                p && count < 32;
3008                p = p->next_same_value, count++)
3009             if (! p->flag
3010                 && (REG_P (p->exp)
3011                     || (GET_CODE (p->exp) != EXPR_LIST
3012                         && exp_equiv_p (p->exp, p->exp, 1, false))))
3013
3014               {
3015                 rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
3016                                                p->exp, op1);
3017                 int new_cost;
3018                 
3019                 /* Get the canonical version of the address so we can accept
3020                    more.  */
3021                 new = canon_for_address (new);
3022                 
3023                 new_cost = address_cost (new, mode);
3024
3025                 if (new_cost < best_addr_cost
3026                     || (new_cost == best_addr_cost
3027                         && (COST (new) + 1) >> 1 > best_rtx_cost))
3028                   {
3029                     found_better = 1;
3030                     best_addr_cost = new_cost;
3031                     best_rtx_cost = (COST (new) + 1) >> 1;
3032                     best_elt = p;
3033                     best_rtx = new;
3034                   }
3035               }
3036
3037           if (found_better)
3038             {
3039               if (validate_change (insn, loc,
3040                                    canon_reg (copy_rtx (best_rtx),
3041                                               NULL_RTX), 0))
3042                 return;
3043               else
3044                 best_elt->flag = 1;
3045             }
3046         }
3047     }
3048 }
3049 \f
3050 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
3051    operation (EQ, NE, GT, etc.), follow it back through the hash table and
3052    what values are being compared.
3053
3054    *PARG1 and *PARG2 are updated to contain the rtx representing the values
3055    actually being compared.  For example, if *PARG1 was (cc0) and *PARG2
3056    was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
3057    compared to produce cc0.
3058
3059    The return value is the comparison operator and is either the code of
3060    A or the code corresponding to the inverse of the comparison.  */
3061
3062 static enum rtx_code
3063 find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
3064                       enum machine_mode *pmode1, enum machine_mode *pmode2)
3065 {
3066   rtx arg1, arg2;
3067
3068   arg1 = *parg1, arg2 = *parg2;
3069
3070   /* If ARG2 is const0_rtx, see what ARG1 is equivalent to.  */
3071
3072   while (arg2 == CONST0_RTX (GET_MODE (arg1)))
3073     {
3074       /* Set nonzero when we find something of interest.  */
3075       rtx x = 0;
3076       int reverse_code = 0;
3077       struct table_elt *p = 0;
3078
3079       /* If arg1 is a COMPARE, extract the comparison arguments from it.
3080          On machines with CC0, this is the only case that can occur, since
3081          fold_rtx will return the COMPARE or item being compared with zero
3082          when given CC0.  */
3083
3084       if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
3085         x = arg1;
3086
3087       /* If ARG1 is a comparison operator and CODE is testing for
3088          STORE_FLAG_VALUE, get the inner arguments.  */
3089
3090       else if (COMPARISON_P (arg1))
3091         {
3092 #ifdef FLOAT_STORE_FLAG_VALUE
3093           REAL_VALUE_TYPE fsfv;
3094 #endif
3095
3096           if (code == NE
3097               || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3098                   && code == LT && STORE_FLAG_VALUE == -1)
3099 #ifdef FLOAT_STORE_FLAG_VALUE
3100               || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
3101                   && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3102                       REAL_VALUE_NEGATIVE (fsfv)))
3103 #endif
3104               )
3105             x = arg1;
3106           else if (code == EQ
3107                    || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3108                        && code == GE && STORE_FLAG_VALUE == -1)
3109 #ifdef FLOAT_STORE_FLAG_VALUE
3110                    || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
3111                        && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3112                            REAL_VALUE_NEGATIVE (fsfv)))
3113 #endif
3114                    )
3115             x = arg1, reverse_code = 1;
3116         }
3117
3118       /* ??? We could also check for
3119
3120          (ne (and (eq (...) (const_int 1))) (const_int 0))
3121
3122          and related forms, but let's wait until we see them occurring.  */
3123
3124       if (x == 0)
3125         /* Look up ARG1 in the hash table and see if it has an equivalence
3126            that lets us see what is being compared.  */
3127         p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
3128       if (p)
3129         {
3130           p = p->first_same_value;
3131
3132           /* If what we compare is already known to be constant, that is as
3133              good as it gets.
3134              We need to break the loop in this case, because otherwise we
3135              can have an infinite loop when looking at a reg that is known
3136              to be a constant which is the same as a comparison of a reg
3137              against zero which appears later in the insn stream, which in
3138              turn is constant and the same as the comparison of the first reg
3139              against zero...  */
3140           if (p->is_const)
3141             break;
3142         }
3143
3144       for (; p; p = p->next_same_value)
3145         {
3146           enum machine_mode inner_mode = GET_MODE (p->exp);
3147 #ifdef FLOAT_STORE_FLAG_VALUE
3148           REAL_VALUE_TYPE fsfv;
3149 #endif
3150
3151           /* If the entry isn't valid, skip it.  */
3152           if (! exp_equiv_p (p->exp, p->exp, 1, false))
3153             continue;
3154
3155           if (GET_CODE (p->exp) == COMPARE
3156               /* Another possibility is that this machine has a compare insn
3157                  that includes the comparison code.  In that case, ARG1 would
3158                  be equivalent to a comparison operation that would set ARG1 to
3159                  either STORE_FLAG_VALUE or zero.  If this is an NE operation,
3160                  ORIG_CODE is the actual comparison being done; if it is an EQ,
3161                  we must reverse ORIG_CODE.  On machine with a negative value
3162                  for STORE_FLAG_VALUE, also look at LT and GE operations.  */
3163               || ((code == NE
3164                    || (code == LT
3165                        && GET_MODE_CLASS (inner_mode) == MODE_INT
3166                        && (GET_MODE_BITSIZE (inner_mode)
3167                            <= HOST_BITS_PER_WIDE_INT)
3168                        && (STORE_FLAG_VALUE
3169                            & ((HOST_WIDE_INT) 1
3170                               << (GET_MODE_BITSIZE (inner_mode) - 1))))
3171 #ifdef FLOAT_STORE_FLAG_VALUE
3172                    || (code == LT
3173                        && SCALAR_FLOAT_MODE_P (inner_mode)
3174                        && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3175                            REAL_VALUE_NEGATIVE (fsfv)))
3176 #endif
3177                    )
3178                   && COMPARISON_P (p->exp)))
3179             {
3180               x = p->exp;
3181               break;
3182             }
3183           else if ((code == EQ
3184                     || (code == GE
3185                         && GET_MODE_CLASS (inner_mode) == MODE_INT
3186                         && (GET_MODE_BITSIZE (inner_mode)
3187                             <= HOST_BITS_PER_WIDE_INT)
3188                         && (STORE_FLAG_VALUE
3189                             & ((HOST_WIDE_INT) 1
3190                                << (GET_MODE_BITSIZE (inner_mode) - 1))))
3191 #ifdef FLOAT_STORE_FLAG_VALUE
3192                     || (code == GE
3193                         && SCALAR_FLOAT_MODE_P (inner_mode)
3194                         && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3195                             REAL_VALUE_NEGATIVE (fsfv)))
3196 #endif
3197                     )
3198                    && COMPARISON_P (p->exp))
3199             {
3200               reverse_code = 1;
3201               x = p->exp;
3202               break;
3203             }
3204
3205           /* If this non-trapping address, e.g. fp + constant, the
3206              equivalent is a better operand since it may let us predict
3207              the value of the comparison.  */
3208           else if (!rtx_addr_can_trap_p (p->exp))
3209             {
3210               arg1 = p->exp;
3211               continue;
3212             }
3213         }
3214
3215       /* If we didn't find a useful equivalence for ARG1, we are done.
3216          Otherwise, set up for the next iteration.  */
3217       if (x == 0)
3218         break;
3219
3220       /* If we need to reverse the comparison, make sure that that is
3221          possible -- we can't necessarily infer the value of GE from LT
3222          with floating-point operands.  */
3223       if (reverse_code)
3224         {
3225           enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
3226           if (reversed == UNKNOWN)
3227             break;
3228           else
3229             code = reversed;
3230         }
3231       else if (COMPARISON_P (x))
3232         code = GET_CODE (x);
3233       arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3234     }
3235
3236   /* Return our results.  Return the modes from before fold_rtx
3237      because fold_rtx might produce const_int, and then it's too late.  */
3238   *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3239   *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3240
3241   return code;
3242 }
3243 \f
3244 /* Fold SUBREG.  */
3245
3246 static rtx
3247 fold_rtx_subreg (rtx x, rtx insn)
3248 {
3249   enum machine_mode mode = GET_MODE (x);
3250   rtx folded_arg0;
3251   rtx const_arg0;
3252   rtx new;
3253
3254   /* See if we previously assigned a constant value to this SUBREG.  */
3255   if ((new = lookup_as_function (x, CONST_INT)) != 0
3256       || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3257     return new;
3258
3259   /* If this is a paradoxical SUBREG, we have no idea what value the
3260      extra bits would have.  However, if the operand is equivalent to
3261      a SUBREG whose operand is the same as our mode, and all the modes
3262      are within a word, we can just use the inner operand because
3263      these SUBREGs just say how to treat the register.
3264
3265      Similarly if we find an integer constant.  */
3266
3267   if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3268     {
3269       enum machine_mode imode = GET_MODE (SUBREG_REG (x));
3270       struct table_elt *elt;
3271
3272       if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
3273           && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
3274           && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
3275                             imode)) != 0)
3276         for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3277           {
3278             if (CONSTANT_P (elt->exp)
3279                 && GET_MODE (elt->exp) == VOIDmode)
3280               return elt->exp;
3281
3282             if (GET_CODE (elt->exp) == SUBREG
3283                 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3284                 && exp_equiv_p (elt->exp, elt->exp, 1, false))
3285               return copy_rtx (SUBREG_REG (elt->exp));
3286           }
3287
3288       return x;
3289     }
3290
3291   /* Fold SUBREG_REG.  If it changed, see if we can simplify the
3292      SUBREG.  We might be able to if the SUBREG is extracting a single
3293      word in an integral mode or extracting the low part.  */
3294
3295   folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
3296   const_arg0 = equiv_constant (folded_arg0);
3297   if (const_arg0)
3298     folded_arg0 = const_arg0;
3299
3300   if (folded_arg0 != SUBREG_REG (x))
3301     {
3302       new = simplify_subreg (mode, folded_arg0,
3303                              GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3304       if (new)
3305         return new;
3306     }
3307
3308   if (REG_P (folded_arg0)
3309       && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0)))
3310     {
3311       struct table_elt *elt;
3312
3313       elt = lookup (folded_arg0,
3314                     HASH (folded_arg0, GET_MODE (folded_arg0)),
3315                     GET_MODE (folded_arg0));
3316
3317       if (elt)
3318         elt = elt->first_same_value;
3319
3320       if (subreg_lowpart_p (x))
3321         /* If this is a narrowing SUBREG and our operand is a REG, see
3322            if we can find an equivalence for REG that is an arithmetic
3323            operation in a wider mode where both operands are
3324            paradoxical SUBREGs from objects of our result mode.  In
3325            that case, we couldn-t report an equivalent value for that
3326            operation, since we don't know what the extra bits will be.
3327            But we can find an equivalence for this SUBREG by folding
3328            that operation in the narrow mode.  This allows us to fold
3329            arithmetic in narrow modes when the machine only supports
3330            word-sized arithmetic.
3331
3332            Also look for a case where we have a SUBREG whose operand
3333            is the same as our result.  If both modes are smaller than
3334            a word, we are simply interpreting a register in different
3335            modes and we can use the inner value.  */
3336
3337         for (; elt; elt = elt->next_same_value)
3338           {
3339             enum rtx_code eltcode = GET_CODE (elt->exp);
3340
3341             /* Just check for unary and binary operations.  */
3342             if (UNARY_P (elt->exp)
3343                 && eltcode != SIGN_EXTEND
3344                 && eltcode != ZERO_EXTEND
3345                 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3346                 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode
3347                 && (GET_MODE_CLASS (mode)
3348                     == GET_MODE_CLASS (GET_MODE (XEXP (elt->exp, 0)))))
3349               {
3350                 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
3351
3352                 if (!REG_P (op0) && ! CONSTANT_P (op0))
3353                   op0 = fold_rtx (op0, NULL_RTX);
3354
3355                 op0 = equiv_constant (op0);
3356                 if (op0)
3357                   new = simplify_unary_operation (GET_CODE (elt->exp), mode,
3358                                                   op0, mode);
3359               }
3360             else if (ARITHMETIC_P (elt->exp)
3361                      && eltcode != DIV && eltcode != MOD
3362                      && eltcode != UDIV && eltcode != UMOD
3363                      && eltcode != ASHIFTRT && eltcode != LSHIFTRT
3364                      && eltcode != ROTATE && eltcode != ROTATERT
3365                      && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3366                           && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
3367                               == mode))
3368                          || CONSTANT_P (XEXP (elt->exp, 0)))
3369                      && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
3370                           && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
3371                               == mode))
3372                          || CONSTANT_P (XEXP (elt->exp, 1))))
3373               {
3374                 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
3375                 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
3376
3377                 if (op0 && !REG_P (op0) && ! CONSTANT_P (op0))
3378                   op0 = fold_rtx (op0, NULL_RTX);
3379
3380                 if (op0)
3381                   op0 = equiv_constant (op0);
3382
3383                 if (op1 && !REG_P (op1) && ! CONSTANT_P (op1))
3384                   op1 = fold_rtx (op1, NULL_RTX);
3385
3386                 if (op1)
3387                   op1 = equiv_constant (op1);
3388
3389                 /* If we are looking for the low SImode part of
3390                    (ashift:DI c (const_int 32)), it doesn't work to
3391                    compute that in SImode, because a 32-bit shift in
3392                    SImode is unpredictable.  We know the value is
3393                    0.  */
3394                 if (op0 && op1
3395                     && GET_CODE (elt->exp) == ASHIFT
3396                     && GET_CODE (op1) == CONST_INT
3397                     && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
3398                   {
3399                     if (INTVAL (op1)
3400                         < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
3401                       /* If the count fits in the inner mode's width,
3402                          but exceeds the outer mode's width, the value
3403                          will get truncated to 0 by the subreg.  */
3404                       new = CONST0_RTX (mode);
3405                     else
3406                       /* If the count exceeds even the inner mode's width,
3407                          don't fold this expression.  */
3408                       new = 0;
3409                   }
3410                 else if (op0 && op1)
3411                   new = simplify_binary_operation (GET_CODE (elt->exp),
3412                                                    mode, op0, op1);
3413               }
3414
3415             else if (GET_CODE (elt->exp) == SUBREG
3416                      && GET_MODE (SUBREG_REG (elt->exp)) == mode
3417                      && (GET_MODE_SIZE (GET_MODE (folded_arg0))
3418                          <= UNITS_PER_WORD)
3419                      && exp_equiv_p (elt->exp, elt->exp, 1, false))
3420               new = copy_rtx (SUBREG_REG (elt->exp));
3421
3422             if (new)
3423               return new;
3424           }
3425       else
3426         /* A SUBREG resulting from a zero extension may fold to zero
3427            if it extracts higher bits than the ZERO_EXTEND's source
3428            bits.  FIXME: if combine tried to, er, combine these
3429            instructions, this transformation may be moved to
3430            simplify_subreg.  */
3431         for (; elt; elt = elt->next_same_value)
3432           {
3433             if (GET_CODE (elt->exp) == ZERO_EXTEND
3434                 && subreg_lsb (x)
3435                 >= GET_MODE_BITSIZE (GET_MODE (XEXP (elt->exp, 0))))
3436               return CONST0_RTX (mode);
3437           }
3438     }
3439
3440   return x;
3441 }
3442
3443 /* Fold MEM.  */
3444
3445 static rtx
3446 fold_rtx_mem (rtx x, rtx insn)
3447 {
3448   enum machine_mode mode = GET_MODE (x);
3449   rtx new;
3450
3451   /* If we are not actually processing an insn, don't try to find the
3452      best address.  Not only don't we care, but we could modify the
3453      MEM in an invalid way since we have no insn to validate
3454      against.  */
3455   if (insn != 0)
3456     find_best_addr (insn, &XEXP (x, 0), mode);
3457
3458   {
3459     /* Even if we don't fold in the insn itself, we can safely do so
3460        here, in hopes of getting a constant.  */
3461     rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
3462     rtx base = 0;
3463     HOST_WIDE_INT offset = 0;
3464
3465     if (REG_P (addr)
3466         && REGNO_QTY_VALID_P (REGNO (addr)))
3467       {
3468         int addr_q = REG_QTY (REGNO (addr));
3469         struct qty_table_elem *addr_ent = &qty_table[addr_q];
3470
3471         if (GET_MODE (addr) == addr_ent->mode
3472             && addr_ent->const_rtx != NULL_RTX)
3473           addr = addr_ent->const_rtx;
3474       }
3475
3476     /* Call target hook to avoid the effects of -fpic etc....  */
3477     addr = targetm.delegitimize_address (addr);
3478
3479     /* If address is constant, split it into a base and integer
3480        offset.  */
3481     if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
3482       base = addr;
3483     else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
3484              && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
3485       {
3486         base = XEXP (XEXP (addr, 0), 0);
3487         offset = INTVAL (XEXP (XEXP (addr, 0), 1));
3488       }
3489     else if (GET_CODE (addr) == LO_SUM
3490              && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
3491       base = XEXP (addr, 1);
3492
3493     /* If this is a constant pool reference, we can fold it into its
3494        constant to allow better value tracking.  */
3495     if (base && GET_CODE (base) == SYMBOL_REF
3496         && CONSTANT_POOL_ADDRESS_P (base))
3497       {
3498         rtx constant = get_pool_constant (base);
3499         enum machine_mode const_mode = get_pool_mode (base);
3500         rtx new;
3501
3502         if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
3503           {
3504             constant_pool_entries_cost = COST (constant);
3505             constant_pool_entries_regcost = approx_reg_cost (constant);
3506           }
3507
3508         /* If we are loading the full constant, we have an
3509            equivalence.  */
3510         if (offset == 0 && mode == const_mode)
3511           return constant;
3512
3513         /* If this actually isn't a constant (weird!), we can't do
3514            anything.  Otherwise, handle the two most common cases:
3515            extracting a word from a multi-word constant, and
3516            extracting the low-order bits.  Other cases don't seem
3517            common enough to worry about.  */
3518         if (! CONSTANT_P (constant))
3519           return x;
3520
3521         if (GET_MODE_CLASS (mode) == MODE_INT
3522             && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3523             && offset % UNITS_PER_WORD == 0
3524             && (new = operand_subword (constant,
3525                                        offset / UNITS_PER_WORD,
3526                                        0, const_mode)) != 0)
3527           return new;
3528
3529         if (((BYTES_BIG_ENDIAN
3530               && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
3531              || (! BYTES_BIG_ENDIAN && offset == 0))
3532             &