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