OSDN Git Service

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