OSDN Git Service

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