OSDN Git Service

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