OSDN Git Service

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