OSDN Git Service

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