OSDN Git Service

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