OSDN Git Service

73eb1c6805b554b2be31dbf876d49555b6996f70
[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, 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 bool dead_libcall_p (rtx, int *);
603 static int cse_change_cc_mode (rtx *, void *);
604 static void cse_change_cc_mode_insn (rtx, rtx);
605 static void cse_change_cc_mode_insns (rtx, rtx, rtx);
606 static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);
607 \f
608
609 #undef RTL_HOOKS_GEN_LOWPART
610 #define RTL_HOOKS_GEN_LOWPART           gen_lowpart_if_possible
611
612 static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;
613 \f
614 /* Nonzero if X has the form (PLUS frame-pointer integer).  We check for
615    virtual regs here because the simplify_*_operation routines are called
616    by integrate.c, which is called before virtual register instantiation.  */
617
618 static bool
619 fixed_base_plus_p (rtx x)
620 {
621   switch (GET_CODE (x))
622     {
623     case REG:
624       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
625         return true;
626       if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
627         return true;
628       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
629           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
630         return true;
631       return false;
632
633     case PLUS:
634       if (GET_CODE (XEXP (x, 1)) != CONST_INT)
635         return false;
636       return fixed_base_plus_p (XEXP (x, 0));
637
638     default:
639       return false;
640     }
641 }
642
643 /* Dump the expressions in the equivalence class indicated by CLASSP.
644    This function is used only for debugging.  */
645 void
646 dump_class (struct table_elt *classp)
647 {
648   struct table_elt *elt;
649
650   fprintf (stderr, "Equivalence chain for ");
651   print_rtl (stderr, classp->exp);
652   fprintf (stderr, ": \n");
653
654   for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
655     {
656       print_rtl (stderr, elt->exp);
657       fprintf (stderr, "\n");
658     }
659 }
660
661 /* Subroutine of approx_reg_cost; called through for_each_rtx.  */
662
663 static int
664 approx_reg_cost_1 (rtx *xp, void *data)
665 {
666   rtx x = *xp;
667   int *cost_p = data;
668
669   if (x && REG_P (x))
670     {
671       unsigned int regno = REGNO (x);
672
673       if (! CHEAP_REGNO (regno))
674         {
675           if (regno < FIRST_PSEUDO_REGISTER)
676             {
677               if (SMALL_REGISTER_CLASSES)
678                 return 1;
679               *cost_p += 2;
680             }
681           else
682             *cost_p += 1;
683         }
684     }
685
686   return 0;
687 }
688
689 /* Return an estimate of the cost of the registers used in an rtx.
690    This is mostly the number of different REG expressions in the rtx;
691    however for some exceptions like fixed registers we use a cost of
692    0.  If any other hard register reference occurs, return MAX_COST.  */
693
694 static int
695 approx_reg_cost (rtx x)
696 {
697   int cost = 0;
698
699   if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
700     return MAX_COST;
701
702   return cost;
703 }
704
705 /* Return a negative value if an rtx A, whose costs are given by COST_A
706    and REGCOST_A, is more desirable than an rtx B.
707    Return a positive value if A is less desirable, or 0 if the two are
708    equally good.  */
709 static int
710 preferable (int cost_a, int regcost_a, int cost_b, int regcost_b)
711 {
712   /* First, get rid of cases involving expressions that are entirely
713      unwanted.  */
714   if (cost_a != cost_b)
715     {
716       if (cost_a == MAX_COST)
717         return 1;
718       if (cost_b == MAX_COST)
719         return -1;
720     }
721
722   /* Avoid extending lifetimes of hardregs.  */
723   if (regcost_a != regcost_b)
724     {
725       if (regcost_a == MAX_COST)
726         return 1;
727       if (regcost_b == MAX_COST)
728         return -1;
729     }
730
731   /* Normal operation costs take precedence.  */
732   if (cost_a != cost_b)
733     return cost_a - cost_b;
734   /* Only if these are identical consider effects on register pressure.  */
735   if (regcost_a != regcost_b)
736     return regcost_a - regcost_b;
737   return 0;
738 }
739
740 /* Internal function, to compute cost when X is not a register; called
741    from COST macro to keep it simple.  */
742
743 static int
744 notreg_cost (rtx x, enum rtx_code outer)
745 {
746   return ((GET_CODE (x) == SUBREG
747            && REG_P (SUBREG_REG (x))
748            && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
749            && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
750            && (GET_MODE_SIZE (GET_MODE (x))
751                < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
752            && subreg_lowpart_p (x)
753            && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
754                                      GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
755           ? 0
756           : rtx_cost (x, outer) * 2);
757 }
758
759 \f
760 /* Initialize CSE_REG_INFO_TABLE.  */
761
762 static void
763 init_cse_reg_info (unsigned int nregs)
764 {
765   /* Do we need to grow the table?  */
766   if (nregs > cse_reg_info_table_size)
767     {
768       unsigned int new_size;
769
770       if (cse_reg_info_table_size < 2048)
771         {
772           /* Compute a new size that is a power of 2 and no smaller
773              than the large of NREGS and 64.  */
774           new_size = (cse_reg_info_table_size
775                       ? cse_reg_info_table_size : 64);
776
777           while (new_size < nregs)
778             new_size *= 2;
779         }
780       else
781         {
782           /* If we need a big table, allocate just enough to hold
783              NREGS registers.  */
784           new_size = nregs;
785         }
786
787       /* Reallocate the table with NEW_SIZE entries.  */
788       if (cse_reg_info_table)
789         free (cse_reg_info_table);
790       cse_reg_info_table = XNEWVEC (struct cse_reg_info, new_size);
791       cse_reg_info_table_size = new_size;
792       cse_reg_info_table_first_uninitialized = 0;
793     }
794
795   /* Do we have all of the first NREGS entries initialized?  */
796   if (cse_reg_info_table_first_uninitialized < nregs)
797     {
798       unsigned int old_timestamp = cse_reg_info_timestamp - 1;
799       unsigned int i;
800
801       /* Put the old timestamp on newly allocated entries so that they
802          will all be considered out of date.  We do not touch those
803          entries beyond the first NREGS entries to be nice to the
804          virtual memory.  */
805       for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
806         cse_reg_info_table[i].timestamp = old_timestamp;
807
808       cse_reg_info_table_first_uninitialized = nregs;
809     }
810 }
811
812 /* Given REGNO, initialize the cse_reg_info entry for REGNO.  */
813
814 static void
815 get_cse_reg_info_1 (unsigned int regno)
816 {
817   /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
818      entry will be considered to have been initialized.  */
819   cse_reg_info_table[regno].timestamp = cse_reg_info_timestamp;
820
821   /* Initialize the rest of the entry.  */
822   cse_reg_info_table[regno].reg_tick = 1;
823   cse_reg_info_table[regno].reg_in_table = -1;
824   cse_reg_info_table[regno].subreg_ticked = -1;
825   cse_reg_info_table[regno].reg_qty = -regno - 1;
826 }
827
828 /* Find a cse_reg_info entry for REGNO.  */
829
830 static inline struct cse_reg_info *
831 get_cse_reg_info (unsigned int regno)
832 {
833   struct cse_reg_info *p = &cse_reg_info_table[regno];
834
835   /* If this entry has not been initialized, go ahead and initialize
836      it.  */
837   if (p->timestamp != cse_reg_info_timestamp)
838     get_cse_reg_info_1 (regno);
839
840   return p;
841 }
842
843 /* Clear the hash table and initialize each register with its own quantity,
844    for a new basic block.  */
845
846 static void
847 new_basic_block (void)
848 {
849   int i;
850
851   next_qty = 0;
852
853   /* Invalidate cse_reg_info_table.  */
854   cse_reg_info_timestamp++;
855
856   /* Clear out hash table state for this pass.  */
857   CLEAR_HARD_REG_SET (hard_regs_in_table);
858
859   /* The per-quantity values used to be initialized here, but it is
860      much faster to initialize each as it is made in `make_new_qty'.  */
861
862   for (i = 0; i < HASH_SIZE; i++)
863     {
864       struct table_elt *first;
865
866       first = table[i];
867       if (first != NULL)
868         {
869           struct table_elt *last = first;
870
871           table[i] = NULL;
872
873           while (last->next_same_hash != NULL)
874             last = last->next_same_hash;
875
876           /* Now relink this hash entire chain into
877              the free element list.  */
878
879           last->next_same_hash = free_element_chain;
880           free_element_chain = first;
881         }
882     }
883
884 #ifdef HAVE_cc0
885   prev_insn_cc0 = 0;
886 #endif
887 }
888
889 /* Say that register REG contains a quantity in mode MODE not in any
890    register before and initialize that quantity.  */
891
892 static void
893 make_new_qty (unsigned int reg, enum machine_mode mode)
894 {
895   int q;
896   struct qty_table_elem *ent;
897   struct reg_eqv_elem *eqv;
898
899   gcc_assert (next_qty < max_qty);
900
901   q = REG_QTY (reg) = next_qty++;
902   ent = &qty_table[q];
903   ent->first_reg = reg;
904   ent->last_reg = reg;
905   ent->mode = mode;
906   ent->const_rtx = ent->const_insn = NULL_RTX;
907   ent->comparison_code = UNKNOWN;
908
909   eqv = &reg_eqv_table[reg];
910   eqv->next = eqv->prev = -1;
911 }
912
913 /* Make reg NEW equivalent to reg OLD.
914    OLD is not changing; NEW is.  */
915
916 static void
917 make_regs_eqv (unsigned int new, unsigned int old)
918 {
919   unsigned int lastr, firstr;
920   int q = REG_QTY (old);
921   struct qty_table_elem *ent;
922
923   ent = &qty_table[q];
924
925   /* Nothing should become eqv until it has a "non-invalid" qty number.  */
926   gcc_assert (REGNO_QTY_VALID_P (old));
927
928   REG_QTY (new) = q;
929   firstr = ent->first_reg;
930   lastr = ent->last_reg;
931
932   /* Prefer fixed hard registers to anything.  Prefer pseudo regs to other
933      hard regs.  Among pseudos, if NEW will live longer than any other reg
934      of the same qty, and that is beyond the current basic block,
935      make it the new canonical replacement for this qty.  */
936   if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
937       /* Certain fixed registers might be of the class NO_REGS.  This means
938          that not only can they not be allocated by the compiler, but
939          they cannot be used in substitutions or canonicalizations
940          either.  */
941       && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
942       && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
943           || (new >= FIRST_PSEUDO_REGISTER
944               && (firstr < FIRST_PSEUDO_REGISTER
945                   || (bitmap_bit_p (cse_ebb_live_out, new)
946                       && !bitmap_bit_p (cse_ebb_live_out, firstr))
947                   || (bitmap_bit_p (cse_ebb_live_in, new)
948                       && !bitmap_bit_p (cse_ebb_live_in, firstr))))))
949     {
950       reg_eqv_table[firstr].prev = new;
951       reg_eqv_table[new].next = firstr;
952       reg_eqv_table[new].prev = -1;
953       ent->first_reg = new;
954     }
955   else
956     {
957       /* If NEW is a hard reg (known to be non-fixed), insert at end.
958          Otherwise, insert before any non-fixed hard regs that are at the
959          end.  Registers of class NO_REGS cannot be used as an
960          equivalent for anything.  */
961       while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
962              && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
963              && new >= FIRST_PSEUDO_REGISTER)
964         lastr = reg_eqv_table[lastr].prev;
965       reg_eqv_table[new].next = reg_eqv_table[lastr].next;
966       if (reg_eqv_table[lastr].next >= 0)
967         reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
968       else
969         qty_table[q].last_reg = new;
970       reg_eqv_table[lastr].next = new;
971       reg_eqv_table[new].prev = lastr;
972     }
973 }
974
975 /* Remove REG from its equivalence class.  */
976
977 static void
978 delete_reg_equiv (unsigned int reg)
979 {
980   struct qty_table_elem *ent;
981   int q = REG_QTY (reg);
982   int p, n;
983
984   /* If invalid, do nothing.  */
985   if (! REGNO_QTY_VALID_P (reg))
986     return;
987
988   ent = &qty_table[q];
989
990   p = reg_eqv_table[reg].prev;
991   n = reg_eqv_table[reg].next;
992
993   if (n != -1)
994     reg_eqv_table[n].prev = p;
995   else
996     ent->last_reg = p;
997   if (p != -1)
998     reg_eqv_table[p].next = n;
999   else
1000     ent->first_reg = n;
1001
1002   REG_QTY (reg) = -reg - 1;
1003 }
1004
1005 /* Remove any invalid expressions from the hash table
1006    that refer to any of the registers contained in expression X.
1007
1008    Make sure that newly inserted references to those registers
1009    as subexpressions will be considered valid.
1010
1011    mention_regs is not called when a register itself
1012    is being stored in the table.
1013
1014    Return 1 if we have done something that may have changed the hash code
1015    of X.  */
1016
1017 static int
1018 mention_regs (rtx x)
1019 {
1020   enum rtx_code code;
1021   int i, j;
1022   const char *fmt;
1023   int changed = 0;
1024
1025   if (x == 0)
1026     return 0;
1027
1028   code = GET_CODE (x);
1029   if (code == REG)
1030     {
1031       unsigned int regno = REGNO (x);
1032       unsigned int endregno = END_REGNO (x);
1033       unsigned int i;
1034
1035       for (i = regno; i < endregno; i++)
1036         {
1037           if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1038             remove_invalid_refs (i);
1039
1040           REG_IN_TABLE (i) = REG_TICK (i);
1041           SUBREG_TICKED (i) = -1;
1042         }
1043
1044       return 0;
1045     }
1046
1047   /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1048      pseudo if they don't use overlapping words.  We handle only pseudos
1049      here for simplicity.  */
1050   if (code == SUBREG && REG_P (SUBREG_REG (x))
1051       && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1052     {
1053       unsigned int i = REGNO (SUBREG_REG (x));
1054
1055       if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1056         {
1057           /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1058              the last store to this register really stored into this
1059              subreg, then remove the memory of this subreg.
1060              Otherwise, remove any memory of the entire register and
1061              all its subregs from the table.  */
1062           if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1063               || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1064             remove_invalid_refs (i);
1065           else
1066             remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1067         }
1068
1069       REG_IN_TABLE (i) = REG_TICK (i);
1070       SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1071       return 0;
1072     }
1073
1074   /* If X is a comparison or a COMPARE and either operand is a register
1075      that does not have a quantity, give it one.  This is so that a later
1076      call to record_jump_equiv won't cause X to be assigned a different
1077      hash code and not found in the table after that call.
1078
1079      It is not necessary to do this here, since rehash_using_reg can
1080      fix up the table later, but doing this here eliminates the need to
1081      call that expensive function in the most common case where the only
1082      use of the register is in the comparison.  */
1083
1084   if (code == COMPARE || COMPARISON_P (x))
1085     {
1086       if (REG_P (XEXP (x, 0))
1087           && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1088         if (insert_regs (XEXP (x, 0), NULL, 0))
1089           {
1090             rehash_using_reg (XEXP (x, 0));
1091             changed = 1;
1092           }
1093
1094       if (REG_P (XEXP (x, 1))
1095           && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1096         if (insert_regs (XEXP (x, 1), NULL, 0))
1097           {
1098             rehash_using_reg (XEXP (x, 1));
1099             changed = 1;
1100           }
1101     }
1102
1103   fmt = GET_RTX_FORMAT (code);
1104   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1105     if (fmt[i] == 'e')
1106       changed |= mention_regs (XEXP (x, i));
1107     else if (fmt[i] == 'E')
1108       for (j = 0; j < XVECLEN (x, i); j++)
1109         changed |= mention_regs (XVECEXP (x, i, j));
1110
1111   return changed;
1112 }
1113
1114 /* Update the register quantities for inserting X into the hash table
1115    with a value equivalent to CLASSP.
1116    (If the class does not contain a REG, it is irrelevant.)
1117    If MODIFIED is nonzero, X is a destination; it is being modified.
1118    Note that delete_reg_equiv should be called on a register
1119    before insert_regs is done on that register with MODIFIED != 0.
1120
1121    Nonzero value means that elements of reg_qty have changed
1122    so X's hash code may be different.  */
1123
1124 static int
1125 insert_regs (rtx x, struct table_elt *classp, int modified)
1126 {
1127   if (REG_P (x))
1128     {
1129       unsigned int regno = REGNO (x);
1130       int qty_valid;
1131
1132       /* If REGNO is in the equivalence table already but is of the
1133          wrong mode for that equivalence, don't do anything here.  */
1134
1135       qty_valid = REGNO_QTY_VALID_P (regno);
1136       if (qty_valid)
1137         {
1138           struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1139
1140           if (ent->mode != GET_MODE (x))
1141             return 0;
1142         }
1143
1144       if (modified || ! qty_valid)
1145         {
1146           if (classp)
1147             for (classp = classp->first_same_value;
1148                  classp != 0;
1149                  classp = classp->next_same_value)
1150               if (REG_P (classp->exp)
1151                   && GET_MODE (classp->exp) == GET_MODE (x))
1152                 {
1153                   unsigned c_regno = REGNO (classp->exp);
1154
1155                   gcc_assert (REGNO_QTY_VALID_P (c_regno));
1156
1157                   /* Suppose that 5 is hard reg and 100 and 101 are
1158                      pseudos.  Consider
1159
1160                      (set (reg:si 100) (reg:si 5))
1161                      (set (reg:si 5) (reg:si 100))
1162                      (set (reg:di 101) (reg:di 5))
1163
1164                      We would now set REG_QTY (101) = REG_QTY (5), but the
1165                      entry for 5 is in SImode.  When we use this later in
1166                      copy propagation, we get the register in wrong mode.  */
1167                   if (qty_table[REG_QTY (c_regno)].mode != GET_MODE (x))
1168                     continue;
1169
1170                   make_regs_eqv (regno, c_regno);
1171                   return 1;
1172                 }
1173
1174           /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1175              than REG_IN_TABLE to find out if there was only a single preceding
1176              invalidation - for the SUBREG - or another one, which would be
1177              for the full register.  However, if we find here that REG_TICK
1178              indicates that the register is invalid, it means that it has
1179              been invalidated in a separate operation.  The SUBREG might be used
1180              now (then this is a recursive call), or we might use the full REG
1181              now and a SUBREG of it later.  So bump up REG_TICK so that
1182              mention_regs will do the right thing.  */
1183           if (! modified
1184               && REG_IN_TABLE (regno) >= 0
1185               && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1186             REG_TICK (regno)++;
1187           make_new_qty (regno, GET_MODE (x));
1188           return 1;
1189         }
1190
1191       return 0;
1192     }
1193
1194   /* If X is a SUBREG, we will likely be inserting the inner register in the
1195      table.  If that register doesn't have an assigned quantity number at
1196      this point but does later, the insertion that we will be doing now will
1197      not be accessible because its hash code will have changed.  So assign
1198      a quantity number now.  */
1199
1200   else if (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))
1201            && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1202     {
1203       insert_regs (SUBREG_REG (x), NULL, 0);
1204       mention_regs (x);
1205       return 1;
1206     }
1207   else
1208     return mention_regs (x);
1209 }
1210 \f
1211 /* Look in or update the hash table.  */
1212
1213 /* Remove table element ELT from use in the table.
1214    HASH is its hash code, made using the HASH macro.
1215    It's an argument because often that is known in advance
1216    and we save much time not recomputing it.  */
1217
1218 static void
1219 remove_from_table (struct table_elt *elt, unsigned int hash)
1220 {
1221   if (elt == 0)
1222     return;
1223
1224   /* Mark this element as removed.  See cse_insn.  */
1225   elt->first_same_value = 0;
1226
1227   /* Remove the table element from its equivalence class.  */
1228
1229   {
1230     struct table_elt *prev = elt->prev_same_value;
1231     struct table_elt *next = elt->next_same_value;
1232
1233     if (next)
1234       next->prev_same_value = prev;
1235
1236     if (prev)
1237       prev->next_same_value = next;
1238     else
1239       {
1240         struct table_elt *newfirst = next;
1241         while (next)
1242           {
1243             next->first_same_value = newfirst;
1244             next = next->next_same_value;
1245           }
1246       }
1247   }
1248
1249   /* Remove the table element from its hash bucket.  */
1250
1251   {
1252     struct table_elt *prev = elt->prev_same_hash;
1253     struct table_elt *next = elt->next_same_hash;
1254
1255     if (next)
1256       next->prev_same_hash = prev;
1257
1258     if (prev)
1259       prev->next_same_hash = next;
1260     else if (table[hash] == elt)
1261       table[hash] = next;
1262     else
1263       {
1264         /* This entry is not in the proper hash bucket.  This can happen
1265            when two classes were merged by `merge_equiv_classes'.  Search
1266            for the hash bucket that it heads.  This happens only very
1267            rarely, so the cost is acceptable.  */
1268         for (hash = 0; hash < HASH_SIZE; hash++)
1269           if (table[hash] == elt)
1270             table[hash] = next;
1271       }
1272   }
1273
1274   /* Remove the table element from its related-value circular chain.  */
1275
1276   if (elt->related_value != 0 && elt->related_value != elt)
1277     {
1278       struct table_elt *p = elt->related_value;
1279
1280       while (p->related_value != elt)
1281         p = p->related_value;
1282       p->related_value = elt->related_value;
1283       if (p->related_value == p)
1284         p->related_value = 0;
1285     }
1286
1287   /* Now add it to the free element chain.  */
1288   elt->next_same_hash = free_element_chain;
1289   free_element_chain = elt;
1290 }
1291
1292 /* Same as above, but X is a pseudo-register.  */
1293
1294 static void
1295 remove_pseudo_from_table (rtx x, unsigned int hash)
1296 {
1297   struct table_elt *elt;
1298
1299   /* Because a pseudo-register can be referenced in more than one
1300      mode, we might have to remove more than one table entry.  */
1301   while ((elt = lookup_for_remove (x, hash, VOIDmode)))
1302     remove_from_table (elt, hash);
1303 }
1304
1305 /* Look up X in the hash table and return its table element,
1306    or 0 if X is not in the table.
1307
1308    MODE is the machine-mode of X, or if X is an integer constant
1309    with VOIDmode then MODE is the mode with which X will be used.
1310
1311    Here we are satisfied to find an expression whose tree structure
1312    looks like X.  */
1313
1314 static struct table_elt *
1315 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1316 {
1317   struct table_elt *p;
1318
1319   for (p = table[hash]; p; p = p->next_same_hash)
1320     if (mode == p->mode && ((x == p->exp && REG_P (x))
1321                             || exp_equiv_p (x, p->exp, !REG_P (x), false)))
1322       return p;
1323
1324   return 0;
1325 }
1326
1327 /* Like `lookup' but don't care whether the table element uses invalid regs.
1328    Also ignore discrepancies in the machine mode of a register.  */
1329
1330 static struct table_elt *
1331 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1332 {
1333   struct table_elt *p;
1334
1335   if (REG_P (x))
1336     {
1337       unsigned int regno = REGNO (x);
1338
1339       /* Don't check the machine mode when comparing registers;
1340          invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
1341       for (p = table[hash]; p; p = p->next_same_hash)
1342         if (REG_P (p->exp)
1343             && REGNO (p->exp) == regno)
1344           return p;
1345     }
1346   else
1347     {
1348       for (p = table[hash]; p; p = p->next_same_hash)
1349         if (mode == p->mode
1350             && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
1351           return p;
1352     }
1353
1354   return 0;
1355 }
1356
1357 /* Look for an expression equivalent to X and with code CODE.
1358    If one is found, return that expression.  */
1359
1360 static rtx
1361 lookup_as_function (rtx x, enum rtx_code code)
1362 {
1363   struct table_elt *p
1364     = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
1365
1366   /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1367      long as we are narrowing.  So if we looked in vain for a mode narrower
1368      than word_mode before, look for word_mode now.  */
1369   if (p == 0 && code == CONST_INT
1370       && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1371     {
1372       x = copy_rtx (x);
1373       PUT_MODE (x, word_mode);
1374       p = lookup (x, SAFE_HASH (x, VOIDmode), word_mode);
1375     }
1376
1377   if (p == 0)
1378     return 0;
1379
1380   for (p = p->first_same_value; p; p = p->next_same_value)
1381     if (GET_CODE (p->exp) == code
1382         /* Make sure this is a valid entry in the table.  */
1383         && exp_equiv_p (p->exp, p->exp, 1, false))
1384       return p->exp;
1385
1386   return 0;
1387 }
1388
1389 /* Insert X in the hash table, assuming HASH is its hash code
1390    and CLASSP is an element of the class it should go in
1391    (or 0 if a new class should be made).
1392    It is inserted at the proper position to keep the class in
1393    the order cheapest first.
1394
1395    MODE is the machine-mode of X, or if X is an integer constant
1396    with VOIDmode then MODE is the mode with which X will be used.
1397
1398    For elements of equal cheapness, the most recent one
1399    goes in front, except that the first element in the list
1400    remains first unless a cheaper element is added.  The order of
1401    pseudo-registers does not matter, as canon_reg will be called to
1402    find the cheapest when a register is retrieved from the table.
1403
1404    The in_memory field in the hash table element is set to 0.
1405    The caller must set it nonzero if appropriate.
1406
1407    You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1408    and if insert_regs returns a nonzero value
1409    you must then recompute its hash code before calling here.
1410
1411    If necessary, update table showing constant values of quantities.  */
1412
1413 #define CHEAPER(X, Y) \
1414  (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1415
1416 static struct table_elt *
1417 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1418 {
1419   struct table_elt *elt;
1420
1421   /* If X is a register and we haven't made a quantity for it,
1422      something is wrong.  */
1423   gcc_assert (!REG_P (x) || REGNO_QTY_VALID_P (REGNO (x)));
1424
1425   /* If X is a hard register, show it is being put in the table.  */
1426   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1427     add_to_hard_reg_set (&hard_regs_in_table, GET_MODE (x), REGNO (x));
1428
1429   /* Put an element for X into the right hash bucket.  */
1430
1431   elt = free_element_chain;
1432   if (elt)
1433     free_element_chain = elt->next_same_hash;
1434   else
1435     elt = XNEW (struct table_elt);
1436
1437   elt->exp = x;
1438   elt->canon_exp = NULL_RTX;
1439   elt->cost = COST (x);
1440   elt->regcost = approx_reg_cost (x);
1441   elt->next_same_value = 0;
1442   elt->prev_same_value = 0;
1443   elt->next_same_hash = table[hash];
1444   elt->prev_same_hash = 0;
1445   elt->related_value = 0;
1446   elt->in_memory = 0;
1447   elt->mode = mode;
1448   elt->is_const = (CONSTANT_P (x) || fixed_base_plus_p (x));
1449
1450   if (table[hash])
1451     table[hash]->prev_same_hash = elt;
1452   table[hash] = elt;
1453
1454   /* Put it into the proper value-class.  */
1455   if (classp)
1456     {
1457       classp = classp->first_same_value;
1458       if (CHEAPER (elt, classp))
1459         /* Insert at the head of the class.  */
1460         {
1461           struct table_elt *p;
1462           elt->next_same_value = classp;
1463           classp->prev_same_value = elt;
1464           elt->first_same_value = elt;
1465
1466           for (p = classp; p; p = p->next_same_value)
1467             p->first_same_value = elt;
1468         }
1469       else
1470         {
1471           /* Insert not at head of the class.  */
1472           /* Put it after the last element cheaper than X.  */
1473           struct table_elt *p, *next;
1474
1475           for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1476                p = next);
1477
1478           /* Put it after P and before NEXT.  */
1479           elt->next_same_value = next;
1480           if (next)
1481             next->prev_same_value = elt;
1482
1483           elt->prev_same_value = p;
1484           p->next_same_value = elt;
1485           elt->first_same_value = classp;
1486         }
1487     }
1488   else
1489     elt->first_same_value = elt;
1490
1491   /* If this is a constant being set equivalent to a register or a register
1492      being set equivalent to a constant, note the constant equivalence.
1493
1494      If this is a constant, it cannot be equivalent to a different constant,
1495      and a constant is the only thing that can be cheaper than a register.  So
1496      we know the register is the head of the class (before the constant was
1497      inserted).
1498
1499      If this is a register that is not already known equivalent to a
1500      constant, we must check the entire class.
1501
1502      If this is a register that is already known equivalent to an insn,
1503      update the qtys `const_insn' to show that `this_insn' is the latest
1504      insn making that quantity equivalent to the constant.  */
1505
1506   if (elt->is_const && classp && REG_P (classp->exp)
1507       && !REG_P (x))
1508     {
1509       int exp_q = REG_QTY (REGNO (classp->exp));
1510       struct qty_table_elem *exp_ent = &qty_table[exp_q];
1511
1512       exp_ent->const_rtx = gen_lowpart (exp_ent->mode, x);
1513       exp_ent->const_insn = this_insn;
1514     }
1515
1516   else if (REG_P (x)
1517            && classp
1518            && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1519            && ! elt->is_const)
1520     {
1521       struct table_elt *p;
1522
1523       for (p = classp; p != 0; p = p->next_same_value)
1524         {
1525           if (p->is_const && !REG_P (p->exp))
1526             {
1527               int x_q = REG_QTY (REGNO (x));
1528               struct qty_table_elem *x_ent = &qty_table[x_q];
1529
1530               x_ent->const_rtx
1531                 = gen_lowpart (GET_MODE (x), p->exp);
1532               x_ent->const_insn = this_insn;
1533               break;
1534             }
1535         }
1536     }
1537
1538   else if (REG_P (x)
1539            && qty_table[REG_QTY (REGNO (x))].const_rtx
1540            && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1541     qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1542
1543   /* If this is a constant with symbolic value,
1544      and it has a term with an explicit integer value,
1545      link it up with related expressions.  */
1546   if (GET_CODE (x) == CONST)
1547     {
1548       rtx subexp = get_related_value (x);
1549       unsigned subhash;
1550       struct table_elt *subelt, *subelt_prev;
1551
1552       if (subexp != 0)
1553         {
1554           /* Get the integer-free subexpression in the hash table.  */
1555           subhash = SAFE_HASH (subexp, mode);
1556           subelt = lookup (subexp, subhash, mode);
1557           if (subelt == 0)
1558             subelt = insert (subexp, NULL, subhash, mode);
1559           /* Initialize SUBELT's circular chain if it has none.  */
1560           if (subelt->related_value == 0)
1561             subelt->related_value = subelt;
1562           /* Find the element in the circular chain that precedes SUBELT.  */
1563           subelt_prev = subelt;
1564           while (subelt_prev->related_value != subelt)
1565             subelt_prev = subelt_prev->related_value;
1566           /* Put new ELT into SUBELT's circular chain just before SUBELT.
1567              This way the element that follows SUBELT is the oldest one.  */
1568           elt->related_value = subelt_prev->related_value;
1569           subelt_prev->related_value = elt;
1570         }
1571     }
1572
1573   return elt;
1574 }
1575 \f
1576 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1577    CLASS2 into CLASS1.  This is done when we have reached an insn which makes
1578    the two classes equivalent.
1579
1580    CLASS1 will be the surviving class; CLASS2 should not be used after this
1581    call.
1582
1583    Any invalid entries in CLASS2 will not be copied.  */
1584
1585 static void
1586 merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1587 {
1588   struct table_elt *elt, *next, *new;
1589
1590   /* Ensure we start with the head of the classes.  */
1591   class1 = class1->first_same_value;
1592   class2 = class2->first_same_value;
1593
1594   /* If they were already equal, forget it.  */
1595   if (class1 == class2)
1596     return;
1597
1598   for (elt = class2; elt; elt = next)
1599     {
1600       unsigned int hash;
1601       rtx exp = elt->exp;
1602       enum machine_mode mode = elt->mode;
1603
1604       next = elt->next_same_value;
1605
1606       /* Remove old entry, make a new one in CLASS1's class.
1607          Don't do this for invalid entries as we cannot find their
1608          hash code (it also isn't necessary).  */
1609       if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
1610         {
1611           bool need_rehash = false;
1612
1613           hash_arg_in_memory = 0;
1614           hash = HASH (exp, mode);
1615
1616           if (REG_P (exp))
1617             {
1618               need_rehash = REGNO_QTY_VALID_P (REGNO (exp));
1619               delete_reg_equiv (REGNO (exp));
1620             }
1621
1622           if (REG_P (exp) && REGNO (exp) >= FIRST_PSEUDO_REGISTER)
1623             remove_pseudo_from_table (exp, hash);
1624           else
1625             remove_from_table (elt, hash);
1626
1627           if (insert_regs (exp, class1, 0) || need_rehash)
1628             {
1629               rehash_using_reg (exp);
1630               hash = HASH (exp, mode);
1631             }
1632           new = insert (exp, class1, hash, mode);
1633           new->in_memory = hash_arg_in_memory;
1634         }
1635     }
1636 }
1637 \f
1638 /* Flush the entire hash table.  */
1639
1640 static void
1641 flush_hash_table (void)
1642 {
1643   int i;
1644   struct table_elt *p;
1645
1646   for (i = 0; i < HASH_SIZE; i++)
1647     for (p = table[i]; p; p = table[i])
1648       {
1649         /* Note that invalidate can remove elements
1650            after P in the current hash chain.  */
1651         if (REG_P (p->exp))
1652           invalidate (p->exp, VOIDmode);
1653         else
1654           remove_from_table (p, i);
1655       }
1656 }
1657 \f
1658 /* Function called for each rtx to check whether true dependence exist.  */
1659 struct check_dependence_data
1660 {
1661   enum machine_mode mode;
1662   rtx exp;
1663   rtx addr;
1664 };
1665
1666 static int
1667 check_dependence (rtx *x, void *data)
1668 {
1669   struct check_dependence_data *d = (struct check_dependence_data *) data;
1670   if (*x && MEM_P (*x))
1671     return canon_true_dependence (d->exp, d->mode, d->addr, *x,
1672                                   cse_rtx_varies_p);
1673   else
1674     return 0;
1675 }
1676 \f
1677 /* Remove from the hash table, or mark as invalid, all expressions whose
1678    values could be altered by storing in X.  X is a register, a subreg, or
1679    a memory reference with nonvarying address (because, when a memory
1680    reference with a varying address is stored in, all memory references are
1681    removed by invalidate_memory so specific invalidation is superfluous).
1682    FULL_MODE, if not VOIDmode, indicates that this much should be
1683    invalidated instead of just the amount indicated by the mode of X.  This
1684    is only used for bitfield stores into memory.
1685
1686    A nonvarying address may be just a register or just a symbol reference,
1687    or it may be either of those plus a numeric offset.  */
1688
1689 static void
1690 invalidate (rtx x, enum machine_mode full_mode)
1691 {
1692   int i;
1693   struct table_elt *p;
1694   rtx addr;
1695
1696   switch (GET_CODE (x))
1697     {
1698     case REG:
1699       {
1700         /* If X is a register, dependencies on its contents are recorded
1701            through the qty number mechanism.  Just change the qty number of
1702            the register, mark it as invalid for expressions that refer to it,
1703            and remove it itself.  */
1704         unsigned int regno = REGNO (x);
1705         unsigned int hash = HASH (x, GET_MODE (x));
1706
1707         /* Remove REGNO from any quantity list it might be on and indicate
1708            that its value might have changed.  If it is a pseudo, remove its
1709            entry from the hash table.
1710
1711            For a hard register, we do the first two actions above for any
1712            additional hard registers corresponding to X.  Then, if any of these
1713            registers are in the table, we must remove any REG entries that
1714            overlap these registers.  */
1715
1716         delete_reg_equiv (regno);
1717         REG_TICK (regno)++;
1718         SUBREG_TICKED (regno) = -1;
1719
1720         if (regno >= FIRST_PSEUDO_REGISTER)
1721           remove_pseudo_from_table (x, hash);
1722         else
1723           {
1724             HOST_WIDE_INT in_table
1725               = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1726             unsigned int endregno = END_HARD_REGNO (x);
1727             unsigned int tregno, tendregno, rn;
1728             struct table_elt *p, *next;
1729
1730             CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1731
1732             for (rn = regno + 1; rn < endregno; rn++)
1733               {
1734                 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1735                 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1736                 delete_reg_equiv (rn);
1737                 REG_TICK (rn)++;
1738                 SUBREG_TICKED (rn) = -1;
1739               }
1740
1741             if (in_table)
1742               for (hash = 0; hash < HASH_SIZE; hash++)
1743                 for (p = table[hash]; p; p = next)
1744                   {
1745                     next = p->next_same_hash;
1746
1747                     if (!REG_P (p->exp)
1748                         || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1749                       continue;
1750
1751                     tregno = REGNO (p->exp);
1752                     tendregno = END_HARD_REGNO (p->exp);
1753                     if (tendregno > regno && tregno < endregno)
1754                       remove_from_table (p, hash);
1755                   }
1756           }
1757       }
1758       return;
1759
1760     case SUBREG:
1761       invalidate (SUBREG_REG (x), VOIDmode);
1762       return;
1763
1764     case PARALLEL:
1765       for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1766         invalidate (XVECEXP (x, 0, i), VOIDmode);
1767       return;
1768
1769     case EXPR_LIST:
1770       /* This is part of a disjoint return value; extract the location in
1771          question ignoring the offset.  */
1772       invalidate (XEXP (x, 0), VOIDmode);
1773       return;
1774
1775     case MEM:
1776       addr = canon_rtx (get_addr (XEXP (x, 0)));
1777       /* Calculate the canonical version of X here so that
1778          true_dependence doesn't generate new RTL for X on each call.  */
1779       x = canon_rtx (x);
1780
1781       /* Remove all hash table elements that refer to overlapping pieces of
1782          memory.  */
1783       if (full_mode == VOIDmode)
1784         full_mode = GET_MODE (x);
1785
1786       for (i = 0; i < HASH_SIZE; i++)
1787         {
1788           struct table_elt *next;
1789
1790           for (p = table[i]; p; p = next)
1791             {
1792               next = p->next_same_hash;
1793               if (p->in_memory)
1794                 {
1795                   struct check_dependence_data d;
1796
1797                   /* Just canonicalize the expression once;
1798                      otherwise each time we call invalidate
1799                      true_dependence will canonicalize the
1800                      expression again.  */
1801                   if (!p->canon_exp)
1802                     p->canon_exp = canon_rtx (p->exp);
1803                   d.exp = x;
1804                   d.addr = addr;
1805                   d.mode = full_mode;
1806                   if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1807                     remove_from_table (p, i);
1808                 }
1809             }
1810         }
1811       return;
1812
1813     default:
1814       gcc_unreachable ();
1815     }
1816 }
1817 \f
1818 /* Remove all expressions that refer to register REGNO,
1819    since they are already invalid, and we are about to
1820    mark that register valid again and don't want the old
1821    expressions to reappear as valid.  */
1822
1823 static void
1824 remove_invalid_refs (unsigned int regno)
1825 {
1826   unsigned int i;
1827   struct table_elt *p, *next;
1828
1829   for (i = 0; i < HASH_SIZE; i++)
1830     for (p = table[i]; p; p = next)
1831       {
1832         next = p->next_same_hash;
1833         if (!REG_P (p->exp)
1834             && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1835           remove_from_table (p, i);
1836       }
1837 }
1838
1839 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1840    and mode MODE.  */
1841 static void
1842 remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1843                             enum machine_mode mode)
1844 {
1845   unsigned int i;
1846   struct table_elt *p, *next;
1847   unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
1848
1849   for (i = 0; i < HASH_SIZE; i++)
1850     for (p = table[i]; p; p = next)
1851       {
1852         rtx exp = p->exp;
1853         next = p->next_same_hash;
1854
1855         if (!REG_P (exp)
1856             && (GET_CODE (exp) != SUBREG
1857                 || !REG_P (SUBREG_REG (exp))
1858                 || REGNO (SUBREG_REG (exp)) != regno
1859                 || (((SUBREG_BYTE (exp)
1860                       + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
1861                     && SUBREG_BYTE (exp) <= end))
1862             && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1863           remove_from_table (p, i);
1864       }
1865 }
1866 \f
1867 /* Recompute the hash codes of any valid entries in the hash table that
1868    reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1869
1870    This is called when we make a jump equivalence.  */
1871
1872 static void
1873 rehash_using_reg (rtx x)
1874 {
1875   unsigned int i;
1876   struct table_elt *p, *next;
1877   unsigned hash;
1878
1879   if (GET_CODE (x) == SUBREG)
1880     x = SUBREG_REG (x);
1881
1882   /* If X is not a register or if the register is known not to be in any
1883      valid entries in the table, we have no work to do.  */
1884
1885   if (!REG_P (x)
1886       || REG_IN_TABLE (REGNO (x)) < 0
1887       || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
1888     return;
1889
1890   /* Scan all hash chains looking for valid entries that mention X.
1891      If we find one and it is in the wrong hash chain, move it.  */
1892
1893   for (i = 0; i < HASH_SIZE; i++)
1894     for (p = table[i]; p; p = next)
1895       {
1896         next = p->next_same_hash;
1897         if (reg_mentioned_p (x, p->exp)
1898             && exp_equiv_p (p->exp, p->exp, 1, false)
1899             && i != (hash = SAFE_HASH (p->exp, p->mode)))
1900           {
1901             if (p->next_same_hash)
1902               p->next_same_hash->prev_same_hash = p->prev_same_hash;
1903
1904             if (p->prev_same_hash)
1905               p->prev_same_hash->next_same_hash = p->next_same_hash;
1906             else
1907               table[i] = p->next_same_hash;
1908
1909             p->next_same_hash = table[hash];
1910             p->prev_same_hash = 0;
1911             if (table[hash])
1912               table[hash]->prev_same_hash = p;
1913             table[hash] = p;
1914           }
1915       }
1916 }
1917 \f
1918 /* Remove from the hash table any expression that is a call-clobbered
1919    register.  Also update their TICK values.  */
1920
1921 static void
1922 invalidate_for_call (void)
1923 {
1924   unsigned int regno, endregno;
1925   unsigned int i;
1926   unsigned hash;
1927   struct table_elt *p, *next;
1928   int in_table = 0;
1929
1930   /* Go through all the hard registers.  For each that is clobbered in
1931      a CALL_INSN, remove the register from quantity chains and update
1932      reg_tick if defined.  Also see if any of these registers is currently
1933      in the table.  */
1934
1935   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1936     if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1937       {
1938         delete_reg_equiv (regno);
1939         if (REG_TICK (regno) >= 0)
1940           {
1941             REG_TICK (regno)++;
1942             SUBREG_TICKED (regno) = -1;
1943           }
1944
1945         in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
1946       }
1947
1948   /* In the case where we have no call-clobbered hard registers in the
1949      table, we are done.  Otherwise, scan the table and remove any
1950      entry that overlaps a call-clobbered register.  */
1951
1952   if (in_table)
1953     for (hash = 0; hash < HASH_SIZE; hash++)
1954       for (p = table[hash]; p; p = next)
1955         {
1956           next = p->next_same_hash;
1957
1958           if (!REG_P (p->exp)
1959               || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1960             continue;
1961
1962           regno = REGNO (p->exp);
1963           endregno = END_HARD_REGNO (p->exp);
1964
1965           for (i = regno; i < endregno; i++)
1966             if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1967               {
1968                 remove_from_table (p, hash);
1969                 break;
1970               }
1971         }
1972 }
1973 \f
1974 /* Given an expression X of type CONST,
1975    and ELT which is its table entry (or 0 if it
1976    is not in the hash table),
1977    return an alternate expression for X as a register plus integer.
1978    If none can be found, return 0.  */
1979
1980 static rtx
1981 use_related_value (rtx x, struct table_elt *elt)
1982 {
1983   struct table_elt *relt = 0;
1984   struct table_elt *p, *q;
1985   HOST_WIDE_INT offset;
1986
1987   /* First, is there anything related known?
1988      If we have a table element, we can tell from that.
1989      Otherwise, must look it up.  */
1990
1991   if (elt != 0 && elt->related_value != 0)
1992     relt = elt;
1993   else if (elt == 0 && GET_CODE (x) == CONST)
1994     {
1995       rtx subexp = get_related_value (x);
1996       if (subexp != 0)
1997         relt = lookup (subexp,
1998                        SAFE_HASH (subexp, GET_MODE (subexp)),
1999                        GET_MODE (subexp));
2000     }
2001
2002   if (relt == 0)
2003     return 0;
2004
2005   /* Search all related table entries for one that has an
2006      equivalent register.  */
2007
2008   p = relt;
2009   while (1)
2010     {
2011       /* This loop is strange in that it is executed in two different cases.
2012          The first is when X is already in the table.  Then it is searching
2013          the RELATED_VALUE list of X's class (RELT).  The second case is when
2014          X is not in the table.  Then RELT points to a class for the related
2015          value.
2016
2017          Ensure that, whatever case we are in, that we ignore classes that have
2018          the same value as X.  */
2019
2020       if (rtx_equal_p (x, p->exp))
2021         q = 0;
2022       else
2023         for (q = p->first_same_value; q; q = q->next_same_value)
2024           if (REG_P (q->exp))
2025             break;
2026
2027       if (q)
2028         break;
2029
2030       p = p->related_value;
2031
2032       /* We went all the way around, so there is nothing to be found.
2033          Alternatively, perhaps RELT was in the table for some other reason
2034          and it has no related values recorded.  */
2035       if (p == relt || p == 0)
2036         break;
2037     }
2038
2039   if (q == 0)
2040     return 0;
2041
2042   offset = (get_integer_term (x) - get_integer_term (p->exp));
2043   /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
2044   return plus_constant (q->exp, offset);
2045 }
2046 \f
2047 /* Hash a string.  Just add its bytes up.  */
2048 static inline unsigned
2049 hash_rtx_string (const char *ps)
2050 {
2051   unsigned hash = 0;
2052   const unsigned char *p = (const unsigned char *) ps;
2053
2054   if (p)
2055     while (*p)
2056       hash += *p++;
2057
2058   return hash;
2059 }
2060
2061 /* Hash an rtx.  We are careful to make sure the value is never negative.
2062    Equivalent registers hash identically.
2063    MODE is used in hashing for CONST_INTs only;
2064    otherwise the mode of X is used.
2065
2066    Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2067
2068    If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2069    a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
2070
2071    Note that cse_insn knows that the hash code of a MEM expression
2072    is just (int) MEM plus the hash code of the address.  */
2073
2074 unsigned
2075 hash_rtx (const_rtx x, enum machine_mode mode, int *do_not_record_p,
2076           int *hash_arg_in_memory_p, bool have_reg_qty)
2077 {
2078   int i, j;
2079   unsigned hash = 0;
2080   enum rtx_code code;
2081   const char *fmt;
2082
2083   /* Used to turn recursion into iteration.  We can't rely on GCC's
2084      tail-recursion elimination since we need to keep accumulating values
2085      in HASH.  */
2086  repeat:
2087   if (x == 0)
2088     return hash;
2089
2090   code = GET_CODE (x);
2091   switch (code)
2092     {
2093     case REG:
2094       {
2095         unsigned int regno = REGNO (x);
2096
2097         if (!reload_completed)
2098           {
2099             /* On some machines, we can't record any non-fixed hard register,
2100                because extending its life will cause reload problems.  We
2101                consider ap, fp, sp, gp to be fixed for this purpose.
2102
2103                We also consider CCmode registers to be fixed for this purpose;
2104                failure to do so leads to failure to simplify 0<100 type of
2105                conditionals.
2106
2107                On all machines, we can't record any global registers.
2108                Nor should we record any register that is in a small
2109                class, as defined by CLASS_LIKELY_SPILLED_P.  */
2110             bool record;
2111
2112             if (regno >= FIRST_PSEUDO_REGISTER)
2113               record = true;
2114             else if (x == frame_pointer_rtx
2115                      || x == hard_frame_pointer_rtx
2116                      || x == arg_pointer_rtx
2117                      || x == stack_pointer_rtx
2118                      || x == pic_offset_table_rtx)
2119               record = true;
2120             else if (global_regs[regno])
2121               record = false;
2122             else if (fixed_regs[regno])
2123               record = true;
2124             else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2125               record = true;
2126             else if (SMALL_REGISTER_CLASSES)
2127               record = false;
2128             else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
2129               record = false;
2130             else
2131               record = true;
2132
2133             if (!record)
2134               {
2135                 *do_not_record_p = 1;
2136                 return 0;
2137               }
2138           }
2139
2140         hash += ((unsigned int) REG << 7);
2141         hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2142         return hash;
2143       }
2144
2145     /* We handle SUBREG of a REG specially because the underlying
2146        reg changes its hash value with every value change; we don't
2147        want to have to forget unrelated subregs when one subreg changes.  */
2148     case SUBREG:
2149       {
2150         if (REG_P (SUBREG_REG (x)))
2151           {
2152             hash += (((unsigned int) SUBREG << 7)
2153                      + REGNO (SUBREG_REG (x))
2154                      + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2155             return hash;
2156           }
2157         break;
2158       }
2159
2160     case CONST_INT:
2161       hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2162                + (unsigned int) INTVAL (x));
2163       return hash;
2164
2165     case CONST_DOUBLE:
2166       /* This is like the general case, except that it only counts
2167          the integers representing the constant.  */
2168       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2169       if (GET_MODE (x) != VOIDmode)
2170         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2171       else
2172         hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2173                  + (unsigned int) CONST_DOUBLE_HIGH (x));
2174       return hash;
2175
2176     case CONST_FIXED:
2177       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2178       hash += fixed_hash (CONST_FIXED_VALUE (x));
2179       return hash;
2180
2181     case CONST_VECTOR:
2182       {
2183         int units;
2184         rtx elt;
2185
2186         units = CONST_VECTOR_NUNITS (x);
2187
2188         for (i = 0; i < units; ++i)
2189           {
2190             elt = CONST_VECTOR_ELT (x, i);
2191             hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
2192                               hash_arg_in_memory_p, have_reg_qty);
2193           }
2194
2195         return hash;
2196       }
2197
2198       /* Assume there is only one rtx object for any given label.  */
2199     case LABEL_REF:
2200       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2201          differences and differences between each stage's debugging dumps.  */
2202          hash += (((unsigned int) LABEL_REF << 7)
2203                   + CODE_LABEL_NUMBER (XEXP (x, 0)));
2204       return hash;
2205
2206     case SYMBOL_REF:
2207       {
2208         /* Don't hash on the symbol's address to avoid bootstrap differences.
2209            Different hash values may cause expressions to be recorded in
2210            different orders and thus different registers to be used in the
2211            final assembler.  This also avoids differences in the dump files
2212            between various stages.  */
2213         unsigned int h = 0;
2214         const unsigned char *p = (const unsigned char *) XSTR (x, 0);
2215
2216         while (*p)
2217           h += (h << 7) + *p++; /* ??? revisit */
2218
2219         hash += ((unsigned int) SYMBOL_REF << 7) + h;
2220         return hash;
2221       }
2222
2223     case MEM:
2224       /* We don't record if marked volatile or if BLKmode since we don't
2225          know the size of the move.  */
2226       if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2227         {
2228           *do_not_record_p = 1;
2229           return 0;
2230         }
2231       if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2232         *hash_arg_in_memory_p = 1;
2233
2234       /* Now that we have already found this special case,
2235          might as well speed it up as much as possible.  */
2236       hash += (unsigned) MEM;
2237       x = XEXP (x, 0);
2238       goto repeat;
2239
2240     case USE:
2241       /* A USE that mentions non-volatile memory needs special
2242          handling since the MEM may be BLKmode which normally
2243          prevents an entry from being made.  Pure calls are
2244          marked by a USE which mentions BLKmode memory.
2245          See calls.c:emit_call_1.  */
2246       if (MEM_P (XEXP (x, 0))
2247           && ! MEM_VOLATILE_P (XEXP (x, 0)))
2248         {
2249           hash += (unsigned) USE;
2250           x = XEXP (x, 0);
2251
2252           if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2253             *hash_arg_in_memory_p = 1;
2254
2255           /* Now that we have already found this special case,
2256              might as well speed it up as much as possible.  */
2257           hash += (unsigned) MEM;
2258           x = XEXP (x, 0);
2259           goto repeat;
2260         }
2261       break;
2262
2263     case PRE_DEC:
2264     case PRE_INC:
2265     case POST_DEC:
2266     case POST_INC:
2267     case PRE_MODIFY:
2268     case POST_MODIFY:
2269     case PC:
2270     case CC0:
2271     case CALL:
2272     case UNSPEC_VOLATILE:
2273       *do_not_record_p = 1;
2274       return 0;
2275
2276     case ASM_OPERANDS:
2277       if (MEM_VOLATILE_P (x))
2278         {
2279           *do_not_record_p = 1;
2280           return 0;
2281         }
2282       else
2283         {
2284           /* We don't want to take the filename and line into account.  */
2285           hash += (unsigned) code + (unsigned) GET_MODE (x)
2286             + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
2287             + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2288             + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2289
2290           if (ASM_OPERANDS_INPUT_LENGTH (x))
2291             {
2292               for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2293                 {
2294                   hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
2295                                      GET_MODE (ASM_OPERANDS_INPUT (x, i)),
2296                                      do_not_record_p, hash_arg_in_memory_p,
2297                                      have_reg_qty)
2298                            + hash_rtx_string
2299                                 (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
2300                 }
2301
2302               hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2303               x = ASM_OPERANDS_INPUT (x, 0);
2304               mode = GET_MODE (x);
2305               goto repeat;
2306             }
2307
2308           return hash;
2309         }
2310       break;
2311
2312     default:
2313       break;
2314     }
2315
2316   i = GET_RTX_LENGTH (code) - 1;
2317   hash += (unsigned) code + (unsigned) GET_MODE (x);
2318   fmt = GET_RTX_FORMAT (code);
2319   for (; i >= 0; i--)
2320     {
2321       switch (fmt[i])
2322         {
2323         case 'e':
2324           /* If we are about to do the last recursive call
2325              needed at this level, change it into iteration.
2326              This function  is called enough to be worth it.  */
2327           if (i == 0)
2328             {
2329               x = XEXP (x, i);
2330               goto repeat;
2331             }
2332
2333           hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
2334                             hash_arg_in_memory_p, have_reg_qty);
2335           break;
2336
2337         case 'E':
2338           for (j = 0; j < XVECLEN (x, i); j++)
2339             hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
2340                               hash_arg_in_memory_p, have_reg_qty);
2341           break;
2342
2343         case 's':
2344           hash += hash_rtx_string (XSTR (x, i));
2345           break;
2346
2347         case 'i':
2348           hash += (unsigned int) XINT (x, i);
2349           break;
2350
2351         case '0': case 't':
2352           /* Unused.  */
2353           break;
2354
2355         default:
2356           gcc_unreachable ();
2357         }
2358     }
2359
2360   return hash;
2361 }
2362
2363 /* Hash an rtx X for cse via hash_rtx.
2364    Stores 1 in do_not_record if any subexpression is volatile.
2365    Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2366    does not have the RTX_UNCHANGING_P bit set.  */
2367
2368 static inline unsigned
2369 canon_hash (rtx x, enum machine_mode mode)
2370 {
2371   return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
2372 }
2373
2374 /* Like canon_hash but with no side effects, i.e. do_not_record
2375    and hash_arg_in_memory are not changed.  */
2376
2377 static inline unsigned
2378 safe_hash (rtx x, enum machine_mode mode)
2379 {
2380   int dummy_do_not_record;
2381   return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
2382 }
2383 \f
2384 /* Return 1 iff X and Y would canonicalize into the same thing,
2385    without actually constructing the canonicalization of either one.
2386    If VALIDATE is nonzero,
2387    we assume X is an expression being processed from the rtl
2388    and Y was found in the hash table.  We check register refs
2389    in Y for being marked as valid.
2390
2391    If FOR_GCSE is true, we compare X and Y for equivalence for GCSE.  */
2392
2393 int
2394 exp_equiv_p (const_rtx x, const_rtx y, int validate, bool for_gcse)
2395 {
2396   int i, j;
2397   enum rtx_code code;
2398   const char *fmt;
2399
2400   /* Note: it is incorrect to assume an expression is equivalent to itself
2401      if VALIDATE is nonzero.  */
2402   if (x == y && !validate)
2403     return 1;
2404
2405   if (x == 0 || y == 0)
2406     return x == y;
2407
2408   code = GET_CODE (x);
2409   if (code != GET_CODE (y))
2410     return 0;
2411
2412   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
2413   if (GET_MODE (x) != GET_MODE (y))
2414     return 0;
2415
2416   switch (code)
2417     {
2418     case PC:
2419     case CC0:
2420     case CONST_INT:
2421     case CONST_DOUBLE:
2422     case CONST_FIXED:
2423       return x == y;
2424
2425     case LABEL_REF:
2426       return XEXP (x, 0) == XEXP (y, 0);
2427
2428     case SYMBOL_REF:
2429       return XSTR (x, 0) == XSTR (y, 0);
2430
2431     case REG:
2432       if (for_gcse)
2433         return REGNO (x) == REGNO (y);
2434       else
2435         {
2436           unsigned int regno = REGNO (y);
2437           unsigned int i;
2438           unsigned int endregno = END_REGNO (y);
2439
2440           /* If the quantities are not the same, the expressions are not
2441              equivalent.  If there are and we are not to validate, they
2442              are equivalent.  Otherwise, ensure all regs are up-to-date.  */
2443
2444           if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2445             return 0;
2446
2447           if (! validate)
2448             return 1;
2449
2450           for (i = regno; i < endregno; i++)
2451             if (REG_IN_TABLE (i) != REG_TICK (i))
2452               return 0;
2453
2454           return 1;
2455         }
2456
2457     case MEM:
2458       if (for_gcse)
2459         {
2460           /* A volatile mem should not be considered equivalent to any
2461              other.  */
2462           if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2463             return 0;
2464
2465           /* Can't merge two expressions in different alias sets, since we
2466              can decide that the expression is transparent in a block when
2467              it isn't, due to it being set with the different alias set.
2468
2469              Also, can't merge two expressions with different MEM_ATTRS.
2470              They could e.g. be two different entities allocated into the
2471              same space on the stack (see e.g. PR25130).  In that case, the
2472              MEM addresses can be the same, even though the two MEMs are
2473              absolutely not equivalent.  
2474    
2475              But because really all MEM attributes should be the same for
2476              equivalent MEMs, we just use the invariant that MEMs that have
2477              the same attributes share the same mem_attrs data structure.  */
2478           if (MEM_ATTRS (x) != MEM_ATTRS (y))
2479             return 0;
2480         }
2481       break;
2482
2483     /*  For commutative operations, check both orders.  */
2484     case PLUS:
2485     case MULT:
2486     case AND:
2487     case IOR:
2488     case XOR:
2489     case NE:
2490     case EQ:
2491       return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
2492                              validate, for_gcse)
2493                && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2494                                 validate, for_gcse))
2495               || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2496                                 validate, for_gcse)
2497                   && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2498                                    validate, for_gcse)));
2499
2500     case ASM_OPERANDS:
2501       /* We don't use the generic code below because we want to
2502          disregard filename and line numbers.  */
2503
2504       /* A volatile asm isn't equivalent to any other.  */
2505       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2506         return 0;
2507
2508       if (GET_MODE (x) != GET_MODE (y)
2509           || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2510           || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2511                      ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2512           || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2513           || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2514         return 0;
2515
2516       if (ASM_OPERANDS_INPUT_LENGTH (x))
2517         {
2518           for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2519             if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2520                                ASM_OPERANDS_INPUT (y, i),
2521                                validate, for_gcse)
2522                 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2523                            ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2524               return 0;
2525         }
2526
2527       return 1;
2528
2529     default:
2530       break;
2531     }
2532
2533   /* Compare the elements.  If any pair of corresponding elements
2534      fail to match, return 0 for the whole thing.  */
2535
2536   fmt = GET_RTX_FORMAT (code);
2537   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2538     {
2539       switch (fmt[i])
2540         {
2541         case 'e':
2542           if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
2543                               validate, for_gcse))
2544             return 0;
2545           break;
2546
2547         case 'E':
2548           if (XVECLEN (x, i) != XVECLEN (y, i))
2549             return 0;
2550           for (j = 0; j < XVECLEN (x, i); j++)
2551             if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2552                                 validate, for_gcse))
2553               return 0;
2554           break;
2555
2556         case 's':
2557           if (strcmp (XSTR (x, i), XSTR (y, i)))
2558             return 0;
2559           break;
2560
2561         case 'i':
2562           if (XINT (x, i) != XINT (y, i))
2563             return 0;
2564           break;
2565
2566         case 'w':
2567           if (XWINT (x, i) != XWINT (y, i))
2568             return 0;
2569           break;
2570
2571         case '0':
2572         case 't':
2573           break;
2574
2575         default:
2576           gcc_unreachable ();
2577         }
2578     }
2579
2580   return 1;
2581 }
2582 \f
2583 /* Return 1 if X has a value that can vary even between two
2584    executions of the program.  0 means X can be compared reliably
2585    against certain constants or near-constants.  */
2586
2587 static bool
2588 cse_rtx_varies_p (const_rtx x, bool from_alias)
2589 {
2590   /* We need not check for X and the equivalence class being of the same
2591      mode because if X is equivalent to a constant in some mode, it
2592      doesn't vary in any mode.  */
2593
2594   if (REG_P (x)
2595       && REGNO_QTY_VALID_P (REGNO (x)))
2596     {
2597       int x_q = REG_QTY (REGNO (x));
2598       struct qty_table_elem *x_ent = &qty_table[x_q];
2599
2600       if (GET_MODE (x) == x_ent->mode
2601           && x_ent->const_rtx != NULL_RTX)
2602         return 0;
2603     }
2604
2605   if (GET_CODE (x) == PLUS
2606       && GET_CODE (XEXP (x, 1)) == CONST_INT
2607       && REG_P (XEXP (x, 0))
2608       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2609     {
2610       int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2611       struct qty_table_elem *x0_ent = &qty_table[x0_q];
2612
2613       if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2614           && x0_ent->const_rtx != NULL_RTX)
2615         return 0;
2616     }
2617
2618   /* This can happen as the result of virtual register instantiation, if
2619      the initial constant is too large to be a valid address.  This gives
2620      us a three instruction sequence, load large offset into a register,
2621      load fp minus a constant into a register, then a MEM which is the
2622      sum of the two `constant' registers.  */
2623   if (GET_CODE (x) == PLUS
2624       && REG_P (XEXP (x, 0))
2625       && REG_P (XEXP (x, 1))
2626       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2627       && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2628     {
2629       int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2630       int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2631       struct qty_table_elem *x0_ent = &qty_table[x0_q];
2632       struct qty_table_elem *x1_ent = &qty_table[x1_q];
2633
2634       if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2635           && x0_ent->const_rtx != NULL_RTX
2636           && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2637           && x1_ent->const_rtx != NULL_RTX)
2638         return 0;
2639     }
2640
2641   return rtx_varies_p (x, from_alias);
2642 }
2643 \f
2644 /* Subroutine of canon_reg.  Pass *XLOC through canon_reg, and validate
2645    the result if necessary.  INSN is as for canon_reg.  */
2646
2647 static void
2648 validate_canon_reg (rtx *xloc, rtx insn)
2649 {
2650   if (*xloc)
2651     {
2652       rtx new = canon_reg (*xloc, insn);
2653
2654       /* If replacing pseudo with hard reg or vice versa, ensure the
2655          insn remains valid.  Likewise if the insn has MATCH_DUPs.  */
2656       gcc_assert (insn && new);
2657       validate_change (insn, xloc, new, 1);
2658     }
2659 }
2660
2661 /* Canonicalize an expression:
2662    replace each register reference inside it
2663    with the "oldest" equivalent register.
2664
2665    If INSN is nonzero validate_change is used to ensure that INSN remains valid
2666    after we make our substitution.  The calls are made with IN_GROUP nonzero
2667    so apply_change_group must be called upon the outermost return from this
2668    function (unless INSN is zero).  The result of apply_change_group can
2669    generally be discarded since the changes we are making are optional.  */
2670
2671 static rtx
2672 canon_reg (rtx x, rtx insn)
2673 {
2674   int i;
2675   enum rtx_code code;
2676   const char *fmt;
2677
2678   if (x == 0)
2679     return x;
2680
2681   code = GET_CODE (x);
2682   switch (code)
2683     {
2684     case PC:
2685     case CC0:
2686     case CONST:
2687     case CONST_INT:
2688     case CONST_DOUBLE:
2689     case CONST_FIXED:
2690     case CONST_VECTOR:
2691     case SYMBOL_REF:
2692     case LABEL_REF:
2693     case ADDR_VEC:
2694     case ADDR_DIFF_VEC:
2695       return x;
2696
2697     case REG:
2698       {
2699         int first;
2700         int q;
2701         struct qty_table_elem *ent;
2702
2703         /* Never replace a hard reg, because hard regs can appear
2704            in more than one machine mode, and we must preserve the mode
2705            of each occurrence.  Also, some hard regs appear in
2706            MEMs that are shared and mustn't be altered.  Don't try to
2707            replace any reg that maps to a reg of class NO_REGS.  */
2708         if (REGNO (x) < FIRST_PSEUDO_REGISTER
2709             || ! REGNO_QTY_VALID_P (REGNO (x)))
2710           return x;
2711
2712         q = REG_QTY (REGNO (x));
2713         ent = &qty_table[q];
2714         first = ent->first_reg;
2715         return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2716                 : REGNO_REG_CLASS (first) == NO_REGS ? x
2717                 : gen_rtx_REG (ent->mode, first));
2718       }
2719
2720     default:
2721       break;
2722     }
2723
2724   fmt = GET_RTX_FORMAT (code);
2725   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2726     {
2727       int j;
2728
2729       if (fmt[i] == 'e')
2730         validate_canon_reg (&XEXP (x, i), insn);
2731       else if (fmt[i] == 'E')
2732         for (j = 0; j < XVECLEN (x, i); j++)
2733           validate_canon_reg (&XVECEXP (x, i, j), insn);
2734     }
2735
2736   return x;
2737 }
2738 \f
2739 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2740    operation (EQ, NE, GT, etc.), follow it back through the hash table and
2741    what values are being compared.
2742
2743    *PARG1 and *PARG2 are updated to contain the rtx representing the values
2744    actually being compared.  For example, if *PARG1 was (cc0) and *PARG2
2745    was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2746    compared to produce cc0.
2747
2748    The return value is the comparison operator and is either the code of
2749    A or the code corresponding to the inverse of the comparison.  */
2750
2751 static enum rtx_code
2752 find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
2753                       enum machine_mode *pmode1, enum machine_mode *pmode2)
2754 {
2755   rtx arg1, arg2;
2756
2757   arg1 = *parg1, arg2 = *parg2;
2758
2759   /* If ARG2 is const0_rtx, see what ARG1 is equivalent to.  */
2760
2761   while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2762     {
2763       /* Set nonzero when we find something of interest.  */
2764       rtx x = 0;
2765       int reverse_code = 0;
2766       struct table_elt *p = 0;
2767
2768       /* If arg1 is a COMPARE, extract the comparison arguments from it.
2769          On machines with CC0, this is the only case that can occur, since
2770          fold_rtx will return the COMPARE or item being compared with zero
2771          when given CC0.  */
2772
2773       if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2774         x = arg1;
2775
2776       /* If ARG1 is a comparison operator and CODE is testing for
2777          STORE_FLAG_VALUE, get the inner arguments.  */
2778
2779       else if (COMPARISON_P (arg1))
2780         {
2781 #ifdef FLOAT_STORE_FLAG_VALUE
2782           REAL_VALUE_TYPE fsfv;
2783 #endif
2784
2785           if (code == NE
2786               || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2787                   && code == LT && STORE_FLAG_VALUE == -1)
2788 #ifdef FLOAT_STORE_FLAG_VALUE
2789               || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2790                   && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2791                       REAL_VALUE_NEGATIVE (fsfv)))
2792 #endif
2793               )
2794             x = arg1;
2795           else if (code == EQ
2796                    || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2797                        && code == GE && STORE_FLAG_VALUE == -1)
2798 #ifdef FLOAT_STORE_FLAG_VALUE
2799                    || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2800                        && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2801                            REAL_VALUE_NEGATIVE (fsfv)))
2802 #endif
2803                    )
2804             x = arg1, reverse_code = 1;
2805         }
2806
2807       /* ??? We could also check for
2808
2809          (ne (and (eq (...) (const_int 1))) (const_int 0))
2810
2811          and related forms, but let's wait until we see them occurring.  */
2812
2813       if (x == 0)
2814         /* Look up ARG1 in the hash table and see if it has an equivalence
2815            that lets us see what is being compared.  */
2816         p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
2817       if (p)
2818         {
2819           p = p->first_same_value;
2820
2821           /* If what we compare is already known to be constant, that is as
2822              good as it gets.
2823              We need to break the loop in this case, because otherwise we
2824              can have an infinite loop when looking at a reg that is known
2825              to be a constant which is the same as a comparison of a reg
2826              against zero which appears later in the insn stream, which in
2827              turn is constant and the same as the comparison of the first reg
2828              against zero...  */
2829           if (p->is_const)
2830             break;
2831         }
2832
2833       for (; p; p = p->next_same_value)
2834         {
2835           enum machine_mode inner_mode = GET_MODE (p->exp);
2836 #ifdef FLOAT_STORE_FLAG_VALUE
2837           REAL_VALUE_TYPE fsfv;
2838 #endif
2839
2840           /* If the entry isn't valid, skip it.  */
2841           if (! exp_equiv_p (p->exp, p->exp, 1, false))
2842             continue;
2843
2844           if (GET_CODE (p->exp) == COMPARE
2845               /* Another possibility is that this machine has a compare insn
2846                  that includes the comparison code.  In that case, ARG1 would
2847                  be equivalent to a comparison operation that would set ARG1 to
2848                  either STORE_FLAG_VALUE or zero.  If this is an NE operation,
2849                  ORIG_CODE is the actual comparison being done; if it is an EQ,
2850                  we must reverse ORIG_CODE.  On machine with a negative value
2851                  for STORE_FLAG_VALUE, also look at LT and GE operations.  */
2852               || ((code == NE
2853                    || (code == LT
2854                        && GET_MODE_CLASS (inner_mode) == MODE_INT
2855                        && (GET_MODE_BITSIZE (inner_mode)
2856                            <= HOST_BITS_PER_WIDE_INT)
2857                        && (STORE_FLAG_VALUE
2858                            & ((HOST_WIDE_INT) 1
2859                               << (GET_MODE_BITSIZE (inner_mode) - 1))))
2860 #ifdef FLOAT_STORE_FLAG_VALUE
2861                    || (code == LT
2862                        && SCALAR_FLOAT_MODE_P (inner_mode)
2863                        && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2864                            REAL_VALUE_NEGATIVE (fsfv)))
2865 #endif
2866                    )
2867                   && COMPARISON_P (p->exp)))
2868             {
2869               x = p->exp;
2870               break;
2871             }
2872           else if ((code == EQ
2873                     || (code == GE
2874                         && GET_MODE_CLASS (inner_mode) == MODE_INT
2875                         && (GET_MODE_BITSIZE (inner_mode)
2876                             <= HOST_BITS_PER_WIDE_INT)
2877                         && (STORE_FLAG_VALUE
2878                             & ((HOST_WIDE_INT) 1
2879                                << (GET_MODE_BITSIZE (inner_mode) - 1))))
2880 #ifdef FLOAT_STORE_FLAG_VALUE
2881                     || (code == GE
2882                         && SCALAR_FLOAT_MODE_P (inner_mode)
2883                         && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2884                             REAL_VALUE_NEGATIVE (fsfv)))
2885 #endif
2886                     )
2887                    && COMPARISON_P (p->exp))
2888             {
2889               reverse_code = 1;
2890               x = p->exp;
2891               break;
2892             }
2893
2894           /* If this non-trapping address, e.g. fp + constant, the
2895              equivalent is a better operand since it may let us predict
2896              the value of the comparison.  */
2897           else if (!rtx_addr_can_trap_p (p->exp))
2898             {
2899               arg1 = p->exp;
2900               continue;
2901             }
2902         }
2903
2904       /* If we didn't find a useful equivalence for ARG1, we are done.
2905          Otherwise, set up for the next iteration.  */
2906       if (x == 0)
2907         break;
2908
2909       /* If we need to reverse the comparison, make sure that that is
2910          possible -- we can't necessarily infer the value of GE from LT
2911          with floating-point operands.  */
2912       if (reverse_code)
2913         {
2914           enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
2915           if (reversed == UNKNOWN)
2916             break;
2917           else
2918             code = reversed;
2919         }
2920       else if (COMPARISON_P (x))
2921         code = GET_CODE (x);
2922       arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
2923     }
2924
2925   /* Return our results.  Return the modes from before fold_rtx
2926      because fold_rtx might produce const_int, and then it's too late.  */
2927   *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
2928   *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
2929
2930   return code;
2931 }
2932 \f
2933 /* If X is a nontrivial arithmetic operation on an argument for which
2934    a constant value can be determined, return the result of operating
2935    on that value, as a constant.  Otherwise, return X, possibly with
2936    one or more operands changed to a forward-propagated constant.
2937
2938    If X is a register whose contents are known, we do NOT return
2939    those contents here; equiv_constant is called to perform that task.
2940    For SUBREGs and MEMs, we do that both here and in equiv_constant.
2941
2942    INSN is the insn that we may be modifying.  If it is 0, make a copy
2943    of X before modifying it.  */
2944
2945 static rtx
2946 fold_rtx (rtx x, rtx insn)
2947 {
2948   enum rtx_code code;
2949   enum machine_mode mode;
2950   const char *fmt;
2951   int i;
2952   rtx new = 0;
2953   int changed = 0;
2954
2955   /* Operands of X.  */
2956   rtx folded_arg0;
2957   rtx folded_arg1;
2958
2959   /* Constant equivalents of first three operands of X;
2960      0 when no such equivalent is known.  */
2961   rtx const_arg0;
2962   rtx const_arg1;
2963   rtx const_arg2;
2964
2965   /* The mode of the first operand of X.  We need this for sign and zero
2966      extends.  */
2967   enum machine_mode mode_arg0;
2968
2969   if (x == 0)
2970     return x;
2971
2972   /* Try to perform some initial simplifications on X.  */
2973   code = GET_CODE (x);
2974   switch (code)
2975     {
2976     case MEM:
2977     case SUBREG:
2978       if ((new = equiv_constant (x)) != NULL_RTX)
2979         return new;
2980       return x;
2981
2982     case CONST:
2983     case CONST_INT:
2984     case CONST_DOUBLE:
2985     case CONST_FIXED:
2986     case CONST_VECTOR:
2987     case SYMBOL_REF:
2988     case LABEL_REF:
2989     case REG:
2990     case PC:
2991       /* No use simplifying an EXPR_LIST
2992          since they are used only for lists of args
2993          in a function call's REG_EQUAL note.  */
2994     case EXPR_LIST:
2995       return x;
2996
2997 #ifdef HAVE_cc0
2998     case CC0:
2999       return prev_insn_cc0;
3000 #endif
3001
3002     case ASM_OPERANDS:
3003       if (insn)
3004         {
3005           for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3006             validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3007                              fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3008         }
3009       return x;
3010
3011 #ifdef NO_FUNCTION_CSE
3012     case CALL:
3013       if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3014         return x;
3015       break;
3016 #endif
3017
3018     /* Anything else goes through the loop below.  */
3019     default:
3020       break;
3021     }
3022
3023   mode = GET_MODE (x);
3024   const_arg0 = 0;
3025   const_arg1 = 0;
3026   const_arg2 = 0;
3027   mode_arg0 = VOIDmode;
3028
3029   /* Try folding our operands.
3030      Then see which ones have constant values known.  */
3031
3032   fmt = GET_RTX_FORMAT (code);
3033   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3034     if (fmt[i] == 'e')
3035       {
3036         rtx folded_arg = XEXP (x, i), const_arg;
3037         enum machine_mode mode_arg = GET_MODE (folded_arg);
3038
3039         switch (GET_CODE (folded_arg))
3040           {
3041           case MEM:
3042           case REG:
3043           case SUBREG:
3044             const_arg = equiv_constant (folded_arg);
3045             break;
3046
3047           case CONST:
3048           case CONST_INT:
3049           case SYMBOL_REF:
3050           case LABEL_REF:
3051           case CONST_DOUBLE:
3052           case CONST_FIXED:
3053           case CONST_VECTOR:
3054             const_arg = folded_arg;
3055             break;
3056
3057 #ifdef HAVE_cc0
3058           case CC0:
3059             folded_arg = prev_insn_cc0;
3060             mode_arg = prev_insn_cc0_mode;
3061             const_arg = equiv_constant (folded_arg);
3062             break;
3063 #endif
3064
3065           default:
3066             folded_arg = fold_rtx (folded_arg, insn);
3067             const_arg = equiv_constant (folded_arg);
3068             break;
3069           }
3070
3071         /* For the first three operands, see if the operand
3072            is constant or equivalent to a constant.  */
3073         switch (i)
3074           {
3075           case 0:
3076             folded_arg0 = folded_arg;
3077             const_arg0 = const_arg;
3078             mode_arg0 = mode_arg;
3079             break;
3080           case 1:
3081             folded_arg1 = folded_arg;
3082             const_arg1 = const_arg;
3083             break;
3084           case 2:
3085             const_arg2 = const_arg;
3086             break;
3087           }
3088
3089         /* Pick the least expensive of the argument and an equivalent constant
3090            argument.  */
3091         if (const_arg != 0
3092             && const_arg != folded_arg
3093             && COST_IN (const_arg, code) <= COST_IN (folded_arg, code)
3094
3095             /* It's not safe to substitute the operand of a conversion
3096                operator with a constant, as the conversion's identity
3097                depends upon the mode of its operand.  This optimization
3098                is handled by the call to simplify_unary_operation.  */
3099             && (GET_RTX_CLASS (code) != RTX_UNARY
3100                 || GET_MODE (const_arg) == mode_arg0
3101                 || (code != ZERO_EXTEND
3102                     && code != SIGN_EXTEND
3103                     && code != TRUNCATE
3104                     && code != FLOAT_TRUNCATE
3105                     && code != FLOAT_EXTEND
3106                     && code != FLOAT
3107                     && code != FIX
3108                     && code != UNSIGNED_FLOAT
3109                     && code != UNSIGNED_FIX)))
3110           folded_arg = const_arg;
3111
3112         if (folded_arg == XEXP (x, i))
3113           continue;
3114
3115         if (insn == NULL_RTX && !changed)
3116           x = copy_rtx (x);
3117         changed = 1;
3118         validate_unshare_change (insn, &XEXP (x, i), folded_arg, 1);
3119       }
3120
3121   if (changed)
3122     {
3123       /* Canonicalize X if necessary, and keep const_argN and folded_argN
3124          consistent with the order in X.  */
3125       if (canonicalize_change_group (insn, x))
3126         {
3127           rtx tem;
3128           tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3129           tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3130         }
3131
3132       apply_change_group ();
3133     }
3134
3135   /* If X is an arithmetic operation, see if we can simplify it.  */
3136
3137   switch (GET_RTX_CLASS (code))
3138     {
3139     case RTX_UNARY:
3140       {
3141         int is_const = 0;
3142
3143         /* We can't simplify extension ops unless we know the
3144            original mode.  */
3145         if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3146             && mode_arg0 == VOIDmode)
3147           break;
3148
3149         /* If we had a CONST, strip it off and put it back later if we
3150            fold.  */
3151         if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3152           is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3153
3154         new = simplify_unary_operation (code, mode,
3155                                         const_arg0 ? const_arg0 : folded_arg0,
3156                                         mode_arg0);
3157         /* NEG of PLUS could be converted into MINUS, but that causes
3158            expressions of the form
3159            (CONST (MINUS (CONST_INT) (SYMBOL_REF)))
3160            which many ports mistakenly treat as LEGITIMATE_CONSTANT_P.
3161            FIXME: those ports should be fixed.  */
3162         if (new != 0 && is_const
3163             && GET_CODE (new) == PLUS
3164             && (GET_CODE (XEXP (new, 0)) == SYMBOL_REF
3165                 || GET_CODE (XEXP (new, 0)) == LABEL_REF)
3166             && GET_CODE (XEXP (new, 1)) == CONST_INT)
3167           new = gen_rtx_CONST (mode, new);
3168       }
3169       break;
3170
3171     case RTX_COMPARE:
3172     case RTX_COMM_COMPARE:
3173       /* See what items are actually being compared and set FOLDED_ARG[01]
3174          to those values and CODE to the actual comparison code.  If any are
3175          constant, set CONST_ARG0 and CONST_ARG1 appropriately.  We needn't
3176          do anything if both operands are already known to be constant.  */
3177
3178       /* ??? Vector mode comparisons are not supported yet.  */
3179       if (VECTOR_MODE_P (mode))
3180         break;
3181
3182       if (const_arg0 == 0 || const_arg1 == 0)
3183         {
3184           struct table_elt *p0, *p1;
3185           rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3186           enum machine_mode mode_arg1;
3187
3188 #ifdef FLOAT_STORE_FLAG_VALUE
3189           if (SCALAR_FLOAT_MODE_P (mode))
3190             {
3191               true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3192                           (FLOAT_STORE_FLAG_VALUE (mode), mode));
3193               false_rtx = CONST0_RTX (mode);
3194             }
3195 #endif
3196
3197           code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3198                                        &mode_arg0, &mode_arg1);
3199
3200           /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3201              what kinds of things are being compared, so we can't do
3202              anything with this comparison.  */
3203
3204           if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3205             break;
3206
3207           const_arg0 = equiv_constant (folded_arg0);
3208           const_arg1 = equiv_constant (folded_arg1);
3209
3210           /* If we do not now have two constants being compared, see
3211              if we can nevertheless deduce some things about the
3212              comparison.  */
3213           if (const_arg0 == 0 || const_arg1 == 0)
3214             {
3215               if (const_arg1 != NULL)
3216                 {
3217                   rtx cheapest_simplification;
3218                   int cheapest_cost;
3219                   rtx simp_result;
3220                   struct table_elt *p;
3221
3222                   /* See if we can find an equivalent of folded_arg0
3223                      that gets us a cheaper expression, possibly a
3224                      constant through simplifications.  */
3225                   p = lookup (folded_arg0, SAFE_HASH (folded_arg0, mode_arg0),
3226                               mode_arg0);
3227                   
3228                   if (p != NULL)
3229                     {
3230                       cheapest_simplification = x;
3231                       cheapest_cost = COST (x);
3232
3233                       for (p = p->first_same_value; p != NULL; p = p->next_same_value)
3234                         {
3235                           int cost;
3236
3237                           /* If the entry isn't valid, skip it.  */
3238                           if (! exp_equiv_p (p->exp, p->exp, 1, false))
3239                             continue;
3240
3241                           /* Try to simplify using this equivalence.  */
3242                           simp_result
3243                             = simplify_relational_operation (code, mode,
3244                                                              mode_arg0,
3245                                                              p->exp,
3246                                                              const_arg1);
3247
3248                           if (simp_result == NULL)
3249                             continue;
3250
3251                           cost = COST (simp_result);
3252                           if (cost < cheapest_cost)
3253                             {
3254                               cheapest_cost = cost;
3255                               cheapest_simplification = simp_result;
3256                             }
3257                         }
3258
3259                       /* If we have a cheaper expression now, use that
3260                          and try folding it further, from the top.  */
3261                       if (cheapest_simplification != x)
3262                         return fold_rtx (copy_rtx (cheapest_simplification),
3263                                          insn);
3264                     }
3265                 }
3266
3267               /* See if the two operands are the same.  */
3268
3269               if ((REG_P (folded_arg0)
3270                    && REG_P (folded_arg1)
3271                    && (REG_QTY (REGNO (folded_arg0))
3272                        == REG_QTY (REGNO (folded_arg1))))
3273                   || ((p0 = lookup (folded_arg0,
3274                                     SAFE_HASH (folded_arg0, mode_arg0),
3275                                     mode_arg0))
3276                       && (p1 = lookup (folded_arg1,
3277                                        SAFE_HASH (folded_arg1, mode_arg0),
3278                                        mode_arg0))
3279                       && p0->first_same_value == p1->first_same_value))
3280                 folded_arg1 = folded_arg0;
3281
3282               /* If FOLDED_ARG0 is a register, see if the comparison we are
3283                  doing now is either the same as we did before or the reverse
3284                  (we only check the reverse if not floating-point).  */
3285               else if (REG_P (folded_arg0))
3286                 {
3287                   int qty = REG_QTY (REGNO (folded_arg0));
3288
3289                   if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3290                     {
3291                       struct qty_table_elem *ent = &qty_table[qty];
3292
3293                       if ((comparison_dominates_p (ent->comparison_code, code)
3294                            || (! FLOAT_MODE_P (mode_arg0)
3295                                && comparison_dominates_p (ent->comparison_code,
3296                                                           reverse_condition (code))))
3297                           && (rtx_equal_p (ent->comparison_const, folded_arg1)
3298                               || (const_arg1
3299                                   && rtx_equal_p (ent->comparison_const,
3300                                                   const_arg1))
3301                               || (REG_P (folded_arg1)
3302                                   && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3303                         return (comparison_dominates_p (ent->comparison_code, code)
3304                                 ? true_rtx : false_rtx);
3305                     }
3306                 }
3307             }
3308         }
3309
3310       /* If we are comparing against zero, see if the first operand is
3311          equivalent to an IOR with a constant.  If so, we may be able to
3312          determine the result of this comparison.  */
3313       if (const_arg1 == const0_rtx && !const_arg0)
3314         {
3315           rtx y = lookup_as_function (folded_arg0, IOR);
3316           rtx inner_const;
3317
3318           if (y != 0
3319               && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3320               && GET_CODE (inner_const) == CONST_INT
3321               && INTVAL (inner_const) != 0)
3322             folded_arg0 = gen_rtx_IOR (mode_arg0, XEXP (y, 0), inner_const);
3323         }
3324
3325       {
3326         rtx op0 = const_arg0 ? const_arg0 : folded_arg0;
3327         rtx op1 = const_arg1 ? const_arg1 : folded_arg1;
3328         new = simplify_relational_operation (code, mode, mode_arg0, op0, op1);
3329       }
3330       break;
3331
3332     case RTX_BIN_ARITH:
3333     case RTX_COMM_ARITH:
3334       switch (code)
3335         {
3336         case PLUS:
3337           /* If the second operand is a LABEL_REF, see if the first is a MINUS
3338              with that LABEL_REF as its second operand.  If so, the result is
3339              the first operand of that MINUS.  This handles switches with an
3340              ADDR_DIFF_VEC table.  */
3341           if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
3342             {
3343               rtx y
3344                 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
3345                 : lookup_as_function (folded_arg0, MINUS);
3346
3347               if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3348                   && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
3349                 return XEXP (y, 0);
3350
3351               /* Now try for a CONST of a MINUS like the above.  */
3352               if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
3353                         : lookup_as_function (folded_arg0, CONST))) != 0
3354                   && GET_CODE (XEXP (y, 0)) == MINUS
3355                   && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3356                   && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
3357                 return XEXP (XEXP (y, 0), 0);
3358             }
3359
3360           /* Likewise if the operands are in the other order.  */
3361           if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
3362             {
3363               rtx y
3364                 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
3365                 : lookup_as_function (folded_arg1, MINUS);
3366
3367               if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3368                   && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
3369                 return XEXP (y, 0);
3370
3371               /* Now try for a CONST of a MINUS like the above.  */
3372               if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
3373                         : lookup_as_function (folded_arg1, CONST))) != 0
3374                   && GET_CODE (XEXP (y, 0)) == MINUS
3375                   && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3376                   && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
3377                 return XEXP (XEXP (y, 0), 0);
3378             }
3379
3380           /* If second operand is a register equivalent to a negative
3381              CONST_INT, see if we can find a register equivalent to the
3382              positive constant.  Make a MINUS if so.  Don't do this for
3383              a non-negative constant since we might then alternate between
3384              choosing positive and negative constants.  Having the positive
3385              constant previously-used is the more common case.  Be sure
3386              the resulting constant is non-negative; if const_arg1 were
3387              the smallest negative number this would overflow: depending
3388              on the mode, this would either just be the same value (and
3389              hence not save anything) or be incorrect.  */
3390           if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
3391               && INTVAL (const_arg1) < 0
3392               /* This used to test
3393
3394                  -INTVAL (const_arg1) >= 0
3395
3396                  But The Sun V5.0 compilers mis-compiled that test.  So
3397                  instead we test for the problematic value in a more direct
3398                  manner and hope the Sun compilers get it correct.  */
3399               && INTVAL (const_arg1) !=
3400                 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
3401               && REG_P (folded_arg1))
3402             {
3403               rtx new_const = GEN_INT (-INTVAL (const_arg1));
3404               struct table_elt *p
3405                 = lookup (new_const, SAFE_HASH (new_const, mode), mode);
3406
3407               if (p)
3408                 for (p = p->first_same_value; p; p = p->next_same_value)
3409                   if (REG_P (p->exp))
3410                     return simplify_gen_binary (MINUS, mode, folded_arg0,
3411                                                 canon_reg (p->exp, NULL_RTX));
3412             }
3413           goto from_plus;
3414
3415         case MINUS:
3416           /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3417              If so, produce (PLUS Z C2-C).  */
3418           if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
3419             {
3420               rtx y = lookup_as_function (XEXP (x, 0), PLUS);
3421               if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
3422                 return fold_rtx (plus_constant (copy_rtx (y),
3423                                                 -INTVAL (const_arg1)),
3424                                  NULL_RTX);
3425             }
3426
3427           /* Fall through.  */
3428
3429         from_plus:
3430         case SMIN:    case SMAX:      case UMIN:    case UMAX:
3431         case IOR:     case AND:       case XOR:
3432         case MULT:
3433         case ASHIFT:  case LSHIFTRT:  case ASHIFTRT:
3434           /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3435              is known to be of similar form, we may be able to replace the
3436              operation with a combined operation.  This may eliminate the
3437              intermediate operation if every use is simplified in this way.
3438              Note that the similar optimization done by combine.c only works
3439              if the intermediate operation's result has only one reference.  */
3440
3441           if (REG_P (folded_arg0)
3442               && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
3443             {
3444               int is_shift
3445                 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
3446               rtx y, inner_const, new_const;
3447               enum rtx_code associate_code;
3448
3449               if (is_shift
3450                   && (INTVAL (const_arg1) >= GET_MODE_BITSIZE (mode)
3451                       || INTVAL (const_arg1) < 0))
3452                 {
3453                   if (SHIFT_COUNT_TRUNCATED)
3454                     const_arg1 = GEN_INT (INTVAL (const_arg1)
3455                                           & (GET_MODE_BITSIZE (mode) - 1));
3456                   else
3457                     break;
3458                 }
3459
3460               y = lookup_as_function (folded_arg0, code);
3461               if (y == 0)
3462                 break;
3463
3464               /* If we have compiled a statement like
3465                  "if (x == (x & mask1))", and now are looking at
3466                  "x & mask2", we will have a case where the first operand
3467                  of Y is the same as our first operand.  Unless we detect
3468                  this case, an infinite loop will result.  */
3469               if (XEXP (y, 0) == folded_arg0)
3470                 break;
3471
3472               inner_const = equiv_constant (fold_rtx (XEXP (y, 1), 0));
3473               if (!inner_const || GET_CODE (inner_const) != CONST_INT)
3474                 break;
3475
3476               /* Don't associate these operations if they are a PLUS with the
3477                  same constant and it is a power of two.  These might be doable
3478                  with a pre- or post-increment.  Similarly for two subtracts of
3479                  identical powers of two with post decrement.  */
3480
3481               if (code == PLUS && const_arg1 == inner_const
3482                   && ((HAVE_PRE_INCREMENT
3483                           && exact_log2 (INTVAL (const_arg1)) >= 0)
3484                       || (HAVE_POST_INCREMENT
3485                           && exact_log2 (INTVAL (const_arg1)) >= 0)
3486                       || (HAVE_PRE_DECREMENT
3487                           && exact_log2 (- INTVAL (const_arg1)) >= 0)
3488                       || (HAVE_POST_DECREMENT
3489                           && exact_log2 (- INTVAL (const_arg1)) >= 0)))
3490                 break;
3491
3492               /* ??? Vector mode shifts by scalar
3493                  shift operand are not supported yet.  */
3494               if (is_shift && VECTOR_MODE_P (mode))
3495                 break;
3496
3497               if (is_shift
3498                   && (INTVAL (inner_const) >= GET_MODE_BITSIZE (mode)
3499                       || INTVAL (inner_const) < 0))
3500                 {
3501                   if (SHIFT_COUNT_TRUNCATED)
3502                     inner_const = GEN_INT (INTVAL (inner_const)
3503                                            & (GET_MODE_BITSIZE (mode) - 1));
3504                   else
3505                     break;
3506                 }
3507
3508               /* Compute the code used to compose the constants.  For example,
3509                  A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS.  */
3510
3511               associate_code = (is_shift || code == MINUS ? PLUS : code);
3512
3513               new_const = simplify_binary_operation (associate_code, mode,
3514                                                      const_arg1, inner_const);
3515
3516               if (new_const == 0)
3517                 break;
3518
3519               /* If we are associating shift operations, don't let this
3520                  produce a shift of the size of the object or larger.
3521                  This could occur when we follow a sign-extend by a right
3522                  shift on a machine that does a sign-extend as a pair
3523                  of shifts.  */
3524
3525               if (is_shift
3526                   && GET_CODE (new_const) == CONST_INT
3527                   && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
3528                 {
3529                   /* As an exception, we can turn an ASHIFTRT of this
3530                      form into a shift of the number of bits - 1.  */
3531                   if (code == ASHIFTRT)
3532                     new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
3533                   else if (!side_effects_p (XEXP (y, 0)))
3534                     return CONST0_RTX (mode);
3535                   else
3536                     break;
3537                 }
3538
3539               y = copy_rtx (XEXP (y, 0));
3540
3541               /* If Y contains our first operand (the most common way this
3542                  can happen is if Y is a MEM), we would do into an infinite
3543                  loop if we tried to fold it.  So don't in that case.  */
3544
3545               if (! reg_mentioned_p (folded_arg0, y))
3546                 y = fold_rtx (y, insn);
3547
3548               return simplify_gen_binary (code, mode, y, new_const);
3549             }
3550           break;
3551
3552         case DIV:       case UDIV:
3553           /* ??? The associative optimization performed immediately above is
3554              also possible for DIV and UDIV using associate_code of MULT.
3555              However, we would need extra code to verify that the
3556              multiplication does not overflow, that is, there is no overflow
3557              in the calculation of new_const.  */
3558           break;
3559
3560         default:
3561           break;
3562         }
3563
3564       new = simplify_binary_operation (code, mode,
3565                                        const_arg0 ? const_arg0 : folded_arg0,
3566                                        const_arg1 ? const_arg1 : folded_arg1);
3567       break;
3568
3569     case RTX_OBJ:
3570       /* (lo_sum (high X) X) is simply X.  */
3571       if (code == LO_SUM && const_arg0 != 0
3572           && GET_CODE (const_arg0) == HIGH
3573           && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
3574         return const_arg1;
3575       break;
3576
3577     case RTX_TERNARY:
3578     case RTX_BITFIELD_OPS:
3579       new = simplify_ternary_operation (code, mode, mode_arg0,
3580                                         const_arg0 ? const_arg0 : folded_arg0,
3581                                         const_arg1 ? const_arg1 : folded_arg1,
3582                                         const_arg2 ? const_arg2 : XEXP (x, 2));
3583       break;
3584
3585     default:
3586       break;
3587     }
3588
3589   return new ? new : x;
3590 }
3591 \f
3592 /* Return a constant value currently equivalent to X.
3593    Return 0 if we don't know one.  */
3594
3595 static rtx
3596 equiv_constant (rtx x)
3597 {
3598   if (REG_P (x)
3599       && REGNO_QTY_VALID_P (REGNO (x)))
3600     {
3601       int x_q = REG_QTY (REGNO (x));
3602       struct qty_table_elem *x_ent = &qty_table[x_q];
3603
3604       if (x_ent->const_rtx)
3605         x = gen_lowpart (GET_MODE (x), x_ent->const_rtx);
3606     }
3607
3608   if (x == 0 || CONSTANT_P (x))
3609     return x;
3610
3611   if (GET_CODE (x) == SUBREG)
3612     {
3613       rtx new;
3614
3615       /* See if we previously assigned a constant value to this SUBREG.  */
3616       if ((new = lookup_as_function (x, CONST_INT)) != 0
3617           || (new = lookup_as_function (x, CONST_DOUBLE)) != 0
3618           || (new = lookup_as_function (x, CONST_FIXED)) != 0)
3619         return new;
3620
3621       if (REG_P (SUBREG_REG (x))
3622           && (new = equiv_constant (SUBREG_REG (x))) != 0)
3623         return simplify_subreg (GET_MODE (x), SUBREG_REG (x),
3624                                 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3625
3626       return 0;
3627     }
3628
3629   /* If X is a MEM, see if it is a constant-pool reference, or look it up in
3630      the hash table in case its value was seen before.  */
3631
3632   if (MEM_P (x))
3633     {
3634       struct table_elt *elt;
3635
3636       x = avoid_constant_pool_reference (x);
3637       if (CONSTANT_P (x))
3638         return x;
3639
3640       elt = lookup (x, SAFE_HASH (x, GET_MODE (x)), GET_MODE (x));
3641       if (elt == 0)
3642         return 0;
3643
3644       for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3645         if (elt->is_const && CONSTANT_P (elt->exp))
3646           return elt->exp;
3647     }
3648
3649   return 0;
3650 }
3651 \f
3652 /* Given INSN, a jump insn, TAKEN indicates if we are following the
3653    "taken" branch.
3654
3655    In certain cases, this can cause us to add an equivalence.  For example,
3656    if we are following the taken case of
3657         if (i == 2)
3658    we can add the fact that `i' and '2' are now equivalent.
3659
3660    In any case, we can record that this comparison was passed.  If the same
3661    comparison is seen later, we will know its value.  */
3662
3663 static void
3664 record_jump_equiv (rtx insn, bool taken)
3665 {
3666   int cond_known_true;
3667   rtx op0, op1;
3668   rtx set;
3669   enum machine_mode mode, mode0, mode1;
3670   int reversed_nonequality = 0;
3671   enum rtx_code code;
3672
3673   /* Ensure this is the right kind of insn.  */
3674   gcc_assert (any_condjump_p (insn));
3675
3676   set = pc_set (insn);
3677
3678   /* See if this jump condition is known true or false.  */
3679   if (taken)
3680     cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
3681   else
3682     cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
3683
3684   /* Get the type of comparison being done and the operands being compared.
3685      If we had to reverse a non-equality condition, record that fact so we
3686      know that it isn't valid for floating-point.  */
3687   code = GET_CODE (XEXP (SET_SRC (set), 0));
3688   op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
3689   op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
3690
3691   code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
3692   if (! cond_known_true)
3693     {
3694       code = reversed_comparison_code_parts (code, op0, op1, insn);
3695
3696       /* Don't remember if we can't find the inverse.  */
3697       if (code == UNKNOWN)
3698         return;
3699     }
3700
3701   /* The mode is the mode of the non-constant.  */
3702   mode = mode0;
3703   if (mode1 != VOIDmode)
3704     mode = mode1;
3705
3706   record_jump_cond (code, mode, op0, op1, reversed_nonequality);
3707 }
3708
3709 /* Yet another form of subreg creation.  In this case, we want something in
3710    MODE, and we should assume OP has MODE iff it is naturally modeless.  */
3711
3712 static rtx
3713 record_jump_cond_subreg (enum machine_mode mode, rtx op)
3714 {
3715   enum machine_mode op_mode = GET_MODE (op);
3716   if (op_mode == mode || op_mode == VOIDmode)
3717     return op;
3718   return lowpart_subreg (mode, op, op_mode);
3719 }
3720
3721 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
3722    REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
3723    Make any useful entries we can with that information.  Called from
3724    above function and called recursively.  */
3725
3726 static void
3727 record_jump_cond (enum rtx_code code, enum machine_mode mode, rtx op0,
3728                   rtx op1, int reversed_nonequality)
3729 {
3730   unsigned op0_hash, op1_hash;
3731   int op0_in_memory, op1_in_memory;
3732   struct table_elt *op0_elt, *op1_elt;
3733
3734   /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
3735      we know that they are also equal in the smaller mode (this is also
3736      true for all smaller modes whether or not there is a SUBREG, but
3737      is not worth testing for with no SUBREG).  */
3738
3739   /* Note that GET_MODE (op0) may not equal MODE.  */
3740   if (code == EQ && GET_CODE (op0) == SUBREG
3741       && (GET_MODE_SIZE (GET_MODE (op0))
3742           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3743     {
3744       enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3745       rtx tem = record_jump_cond_subreg (inner_mode, op1);
3746       if (tem)
3747         record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3748                           reversed_nonequality);
3749     }
3750
3751   if (code == EQ && GET_CODE (op1) == SUBREG
3752       && (GET_MODE_SIZE (GET_MODE (op1))
3753           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3754     {
3755       enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3756       rtx tem = record_jump_cond_subreg (inner_mode, op0);
3757       if (tem)
3758         record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3759                           reversed_nonequality);
3760     }
3761
3762   /* Similarly, if this is an NE comparison, and either is a SUBREG
3763      making a smaller mode, we know the whole thing is also NE.  */
3764
3765   /* Note that GET_MODE (op0) may not equal MODE;
3766      if we test MODE instead, we can get an infinite recursion
3767      alternating between two modes each wider than MODE.  */
3768
3769   if (code == NE && GET_CODE (op0) == SUBREG
3770       && subreg_lowpart_p (op0)
3771       && (GET_MODE_SIZE (GET_MODE (op0))
3772           < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3773     {
3774       enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3775       rtx tem = record_jump_cond_subreg (inner_mode, op1);
3776       if (tem)
3777         record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3778                           reversed_nonequality);
3779     }
3780
3781   if (code == NE && GET_CODE (op1) == SUBREG
3782       && subreg_lowpart_p (op1)
3783       && (GET_MODE_SIZE (GET_MODE (op1))
3784           < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3785     {
3786       enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3787       rtx tem = record_jump_cond_subreg (inner_mode, op0);
3788       if (tem)
3789         record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3790                           reversed_nonequality);
3791     }
3792
3793   /* Hash both operands.  */
3794
3795   do_not_record = 0;
3796   hash_arg_in_memory = 0;
3797   op0_hash = HASH (op0, mode);
3798   op0_in_memory = hash_arg_in_memory;
3799
3800   if (do_not_record)
3801     return;
3802
3803   do_not_record = 0;
3804   hash_arg_in_memory = 0;
3805   op1_hash = HASH (op1, mode);
3806   op1_in_memory = hash_arg_in_memory;
3807
3808   if (do_not_record)
3809     return;
3810
3811   /* Look up both operands.  */
3812   op0_elt = lookup (op0, op0_hash, mode);
3813   op1_elt = lookup (op1, op1_hash, mode);
3814
3815   /* If both operands are already equivalent or if they are not in the
3816      table but are identical, do nothing.  */
3817   if ((op0_elt != 0 && op1_elt != 0
3818        && op0_elt->first_same_value == op1_elt->first_same_value)
3819       || op0 == op1 || rtx_equal_p (op0, op1))
3820     return;
3821
3822   /* If we aren't setting two things equal all we can do is save this
3823      comparison.   Similarly if this is floating-point.  In the latter
3824      case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
3825      If we record the equality, we might inadvertently delete code
3826      whose intent was to change -0 to +0.  */
3827
3828   if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
3829     {
3830       struct qty_table_elem *ent;
3831       int qty;
3832
3833       /* If we reversed a floating-point comparison, if OP0 is not a
3834          register, or if OP1 is neither a register or constant, we can't
3835          do anything.  */
3836
3837       if (!REG_P (op1))
3838         op1 = equiv_constant (op1);
3839
3840       if ((reversed_nonequality && FLOAT_MODE_P (mode))
3841           || !REG_P (op0) || op1 == 0)
3842         return;
3843
3844       /* Put OP0 in the hash table if it isn't already.  This gives it a
3845          new quantity number.  */
3846       if (op0_elt == 0)
3847         {
3848           if (insert_regs (op0, NULL, 0))
3849             {
3850               rehash_using_reg (op0);
3851               op0_hash = HASH (op0, mode);
3852
3853               /* If OP0 is contained in OP1, this changes its hash code
3854                  as well.  Faster to rehash than to check, except
3855                  for the simple case of a constant.  */
3856               if (! CONSTANT_P (op1))
3857                 op1_hash = HASH (op1,mode);
3858             }
3859
3860           op0_elt = insert (op0, NULL, op0_hash, mode);
3861           op0_elt->in_memory = op0_in_memory;
3862         }
3863
3864       qty = REG_QTY (REGNO (op0));
3865       ent = &qty_table[qty];
3866
3867       ent->comparison_code = code;
3868       if (REG_P (op1))
3869         {
3870           /* Look it up again--in case op0 and op1 are the same.  */
3871           op1_elt = lookup (op1, op1_hash, mode);
3872
3873           /* Put OP1 in the hash table so it gets a new quantity number.  */
3874           if (op1_elt == 0)
3875             {
3876               if (insert_regs (op1, NULL, 0))
3877                 {
3878                   rehash_using_reg (op1);
3879                   op1_hash = HASH (op1, mode);
3880                 }
3881
3882               op1_elt = insert (op1, NULL, op1_hash, mode);
3883               op1_elt->in_memory = op1_in_memory;
3884             }
3885
3886           ent->comparison_const = NULL_RTX;
3887           ent->comparison_qty = REG_QTY (REGNO (op1));
3888         }
3889       else
3890         {
3891           ent->comparison_const = op1;
3892           ent->comparison_qty = -1;
3893         }
3894
3895       return;
3896     }
3897
3898   /* If either side is still missing an equivalence, make it now,
3899      then merge the equivalences.  */
3900
3901   if (op0_elt == 0)
3902     {
3903       if (insert_regs (op0, NULL, 0))
3904         {
3905           rehash_using_reg (op0);
3906           op0_hash = HASH (op0, mode);
3907         }
3908
3909       op0_elt = insert (op0, NULL, op0_hash, mode);
3910       op0_elt->in_memory = op0_in_memory;
3911     }
3912
3913   if (op1_elt == 0)
3914     {
3915       if (insert_regs (op1, NULL, 0))
3916         {
3917           rehash_using_reg (op1);
3918           op1_hash = HASH (op1, mode);
3919         }
3920
3921       op1_elt = insert (op1, NULL, op1_hash, mode);
3922       op1_elt->in_memory = op1_in_memory;
3923     }
3924
3925   merge_equiv_classes (op0_elt, op1_elt);
3926 }
3927 \f
3928 /* CSE processing for one instruction.
3929    First simplify sources and addresses of all assignments
3930    in the instruction, using previously-computed equivalents values.
3931    Then install the new sources and destinations in the table
3932    of available values.
3933
3934    If LIBCALL_INSN is nonzero, don't record any equivalence made in
3935    the insn.  It means that INSN is inside libcall block.  In this
3936    case LIBCALL_INSN is the corresponding insn with REG_LIBCALL.  */
3937
3938 /* Data on one SET contained in the instruction.  */
3939
3940 struct set
3941 {
3942   /* The SET rtx itself.  */
3943   rtx rtl;
3944   /* The SET_SRC of the rtx (the original value, if it is changing).  */
3945   rtx src;
3946   /* The hash-table element for the SET_SRC of the SET.  */
3947   struct table_elt *src_elt;
3948   /* Hash value for the SET_SRC.  */
3949   unsigned src_hash;
3950   /* Hash value for the SET_DEST.  */
3951   unsigned dest_hash;
3952   /* The SET_DEST, with SUBREG, etc., stripped.  */
3953   rtx inner_dest;
3954   /* Nonzero if the SET_SRC is in memory.  */
3955   char src_in_memory;
3956   /* Nonzero if the SET_SRC contains something
3957      whose value cannot be predicted and understood.  */
3958   char src_volatile;
3959   /* Original machine mode, in case it becomes a CONST_INT.
3960      The size of this field should match the size of the mode
3961      field of struct rtx_def (see rtl.h).  */
3962   ENUM_BITFIELD(machine_mode) mode : 8;
3963   /* A constant equivalent for SET_SRC, if any.  */
3964   rtx src_const;
3965   /* Original SET_SRC value used for libcall notes.  */
3966   rtx orig_src;
3967   /* Hash value of constant equivalent for SET_SRC.  */
3968   unsigned src_const_hash;
3969   /* Table entry for constant equivalent for SET_SRC, if any.  */
3970   struct table_elt *src_const_elt;
3971   /* Table entry for the destination address.  */
3972   struct table_elt *dest_addr_elt;
3973 };
3974
3975 static void
3976 cse_insn (rtx insn, rtx libcall_insn)
3977 {
3978   rtx x = PATTERN (insn);
3979   int i;
3980   rtx tem;
3981   int n_sets = 0;
3982
3983   rtx src_eqv = 0;
3984   struct table_elt *src_eqv_elt = 0;
3985   int src_eqv_volatile = 0;
3986   int src_eqv_in_memory = 0;
3987   unsigned src_eqv_hash = 0;
3988
3989   struct set *sets = (struct set *) 0;
3990
3991   this_insn = insn;
3992 #ifdef HAVE_cc0
3993   /* Records what this insn does to set CC0.  */
3994   this_insn_cc0 = 0;
3995   this_insn_cc0_mode = VOIDmode;
3996 #endif
3997
3998   /* Find all the SETs and CLOBBERs in this instruction.
3999      Record all the SETs in the array `set' and count them.
4000      Also determine whether there is a CLOBBER that invalidates
4001      all memory references, or all references at varying addresses.  */
4002
4003   if (CALL_P (insn))
4004     {
4005       for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4006         {
4007           if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4008             invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4009           XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4010         }
4011     }
4012
4013   if (GET_CODE (x) == SET)
4014     {
4015       sets = alloca (sizeof (struct set));
4016       sets[0].rtl = x;
4017
4018       /* Ignore SETs that are unconditional jumps.
4019          They never need cse processing, so this does not hurt.
4020          The reason is not efficiency but rather
4021          so that we can test at the end for instructions
4022          that have been simplified to unconditional jumps
4023          and not be misled by unchanged instructions
4024          that were unconditional jumps to begin with.  */
4025       if (SET_DEST (x) == pc_rtx
4026           && GET_CODE (SET_SRC (x)) == LABEL_REF)
4027         ;
4028
4029       /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4030          The hard function value register is used only once, to copy to
4031          someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4032          Ensure we invalidate the destination register.  On the 80386 no
4033          other code would invalidate it since it is a fixed_reg.
4034          We need not check the return of apply_change_group; see canon_reg.  */
4035
4036       else if (GET_CODE (SET_SRC (x)) == CALL)
4037         {
4038           canon_reg (SET_SRC (x), insn);
4039           apply_change_group ();
4040           fold_rtx (SET_SRC (x), insn);
4041           invalidate (SET_DEST (x), VOIDmode);
4042         }
4043       else
4044         n_sets = 1;
4045     }
4046   else if (GET_CODE (x) == PARALLEL)
4047     {
4048       int lim = XVECLEN (x, 0);
4049
4050       sets = alloca (lim * sizeof (struct set));
4051
4052       /* Find all regs explicitly clobbered in this insn,
4053          and ensure they are not replaced with any other regs
4054          elsewhere in this insn.
4055          When a reg that is clobbered is also used for input,
4056          we should presume that that is for a reason,
4057          and we should not substitute some other register
4058          which is not supposed to be clobbered.
4059          Therefore, this loop cannot be merged into the one below
4060          because a CALL may precede a CLOBBER and refer to the
4061          value clobbered.  We must not let a canonicalization do
4062          anything in that case.  */
4063       for (i = 0; i < lim; i++)
4064         {
4065           rtx y = XVECEXP (x, 0, i);
4066           if (GET_CODE (y) == CLOBBER)
4067             {
4068               rtx clobbered = XEXP (y, 0);
4069
4070               if (REG_P (clobbered)
4071                   || GET_CODE (clobbered) == SUBREG)
4072                 invalidate (clobbered, VOIDmode);
4073               else if (GET_CODE (clobbered) == STRICT_LOW_PART
4074                        || GET_CODE (clobbered) == ZERO_EXTRACT)
4075                 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4076             }
4077         }
4078
4079       for (i = 0; i < lim; i++)
4080         {
4081           rtx y = XVECEXP (x, 0, i);
4082           if (GET_CODE (y) == SET)
4083             {
4084               /* As above, we ignore unconditional jumps and call-insns and
4085                  ignore the result of apply_change_group.  */
4086               if (GET_CODE (SET_SRC (y)) == CALL)
4087                 {
4088                   canon_reg (SET_SRC (y), insn);
4089                   apply_change_group ();
4090                   fold_rtx (SET_SRC (y), insn);
4091                   invalidate (SET_DEST (y), VOIDmode);
4092                 }
4093               else if (SET_DEST (y) == pc_rtx
4094                        && GET_CODE (SET_SRC (y)) == LABEL_REF)
4095                 ;
4096               else
4097                 sets[n_sets++].rtl = y;
4098             }
4099           else if (GET_CODE (y) == CLOBBER)
4100             {
4101               /* If we clobber memory, canon the address.
4102                  This does nothing when a register is clobbered
4103                  because we have already invalidated the reg.  */
4104               if (MEM_P (XEXP (y, 0)))
4105                 canon_reg (XEXP (y, 0), insn);
4106             }
4107           else if (GET_CODE (y) == USE
4108                    && ! (REG_P (XEXP (y, 0))
4109                          && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4110             canon_reg (y, insn);
4111           else if (GET_CODE (y) == CALL)
4112             {
4113               /* The result of apply_change_group can be ignored; see
4114                  canon_reg.  */
4115               canon_reg (y, insn);
4116               apply_change_group ();
4117               fold_rtx (y, insn);
4118             }
4119         }
4120     }
4121   else if (GET_CODE (x) == CLOBBER)
4122     {
4123       if (MEM_P (XEXP (x, 0)))
4124         canon_reg (XEXP (x, 0), insn);
4125     }
4126
4127   /* Canonicalize a USE of a pseudo register or memory location.  */