OSDN Git Service

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