OSDN Git Service

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