* config/xtensa/lib1funcs.asm (__umulsidi3): Restore a12-a15 on exit.
[official-gcc.git] / gcc / cse.c
blob452757a3e4743914816f0c344d9d88f1bdd553e8
1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
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"
48 /* The basic idea of common subexpression elimination is to go
49 through the code, keeping a record of expressions that would
50 have the same value at the current scan point, and replacing
51 expressions encountered with the cheapest equivalent expression.
53 It is too complicated to keep track of the different possibilities
54 when control paths merge in this code; so, at each label, we forget all
55 that is known and start fresh. This can be described as processing each
56 extended basic block separately. We have a separate pass to perform
57 global CSE.
59 Note CSE can turn a conditional or computed jump into a nop or
60 an unconditional jump. When this occurs we arrange to run the jump
61 optimizer after CSE to delete the unreachable code.
63 We use two data structures to record the equivalent expressions:
64 a hash table for most expressions, and a vector of "quantity
65 numbers" to record equivalent (pseudo) registers.
67 The use of the special data structure for registers is desirable
68 because it is faster. It is possible because registers references
69 contain a fairly small number, the register number, taken from
70 a contiguously allocated series, and two register references are
71 identical if they have the same number. General expressions
72 do not have any such thing, so the only way to retrieve the
73 information recorded on an expression other than a register
74 is to keep it in a hash table.
76 Registers and "quantity numbers":
78 At the start of each basic block, all of the (hardware and pseudo)
79 registers used in the function are given distinct quantity
80 numbers to indicate their contents. During scan, when the code
81 copies one register into another, we copy the quantity number.
82 When a register is loaded in any other way, we allocate a new
83 quantity number to describe the value generated by this operation.
84 `REG_QTY (N)' records what quantity register N is currently thought
85 of as containing.
87 All real quantity numbers are greater than or equal to zero.
88 If register N has not been assigned a quantity, `REG_QTY (N)' will
89 equal -N - 1, which is always negative.
91 Quantity numbers below zero do not exist and none of the `qty_table'
92 entries should be referenced with a negative index.
94 We also maintain a bidirectional chain of registers for each
95 quantity number. The `qty_table` members `first_reg' and `last_reg',
96 and `reg_eqv_table' members `next' and `prev' hold these chains.
98 The first register in a chain is the one whose lifespan is least local.
99 Among equals, it is the one that was seen first.
100 We replace any equivalent register with that one.
102 If two registers have the same quantity number, it must be true that
103 REG expressions with qty_table `mode' must be in the hash table for both
104 registers and must be in the same class.
106 The converse is not true. Since hard registers may be referenced in
107 any mode, two REG expressions might be equivalent in the hash table
108 but not have the same quantity number if the quantity number of one
109 of the registers is not the same mode as those expressions.
111 Constants and quantity numbers
113 When a quantity has a known constant value, that value is stored
114 in the appropriate qty_table `const_rtx'. This is in addition to
115 putting the constant in the hash table as is usual for non-regs.
117 Whether a reg or a constant is preferred is determined by the configuration
118 macro CONST_COSTS and will often depend on the constant value. In any
119 event, expressions containing constants can be simplified, by fold_rtx.
121 When a quantity has a known nearly constant value (such as an address
122 of a stack slot), that value is stored in the appropriate qty_table
123 `const_rtx'.
125 Integer constants don't have a machine mode. However, cse
126 determines the intended machine mode from the destination
127 of the instruction that moves the constant. The machine mode
128 is recorded in the hash table along with the actual RTL
129 constant expression so that different modes are kept separate.
131 Other expressions:
133 To record known equivalences among expressions in general
134 we use a hash table called `table'. It has a fixed number of buckets
135 that contain chains of `struct table_elt' elements for expressions.
136 These chains connect the elements whose expressions have the same
137 hash codes.
139 Other chains through the same elements connect the elements which
140 currently have equivalent values.
142 Register references in an expression are canonicalized before hashing
143 the expression. This is done using `reg_qty' and qty_table `first_reg'.
144 The hash code of a register reference is computed using the quantity
145 number, not the register number.
147 When the value of an expression changes, it is necessary to remove from the
148 hash table not just that expression but all expressions whose values
149 could be different as a result.
151 1. If the value changing is in memory, except in special cases
152 ANYTHING referring to memory could be changed. That is because
153 nobody knows where a pointer does not point.
154 The function `invalidate_memory' removes what is necessary.
156 The special cases are when the address is constant or is
157 a constant plus a fixed register such as the frame pointer
158 or a static chain pointer. When such addresses are stored in,
159 we can tell exactly which other such addresses must be invalidated
160 due to overlap. `invalidate' does this.
161 All expressions that refer to non-constant
162 memory addresses are also invalidated. `invalidate_memory' does this.
164 2. If the value changing is a register, all expressions
165 containing references to that register, and only those,
166 must be removed.
168 Because searching the entire hash table for expressions that contain
169 a register is very slow, we try to figure out when it isn't necessary.
170 Precisely, this is necessary only when expressions have been
171 entered in the hash table using this register, and then the value has
172 changed, and then another expression wants to be added to refer to
173 the register's new value. This sequence of circumstances is rare
174 within any one basic block.
176 `REG_TICK' and `REG_IN_TABLE', accessors for members of
177 cse_reg_info, are used to detect this case. REG_TICK (i) is
178 incremented whenever a value is stored in register i.
179 REG_IN_TABLE (i) holds -1 if no references to register i have been
180 entered in the table; otherwise, it contains the value REG_TICK (i)
181 had when the references were entered. If we want to enter a
182 reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and
183 remove old references. Until we want to enter a new entry, the
184 mere fact that the two vectors don't match makes the entries be
185 ignored if anyone tries to match them.
187 Registers themselves are entered in the hash table as well as in
188 the equivalent-register chains. However, `REG_TICK' and
189 `REG_IN_TABLE' do not apply to expressions which are simple
190 register references. These expressions are removed from the table
191 immediately when they become invalid, and this can be done even if
192 we do not immediately search for all the expressions that refer to
193 the register.
195 A CLOBBER rtx in an instruction invalidates its operand for further
196 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
197 invalidates everything that resides in memory.
199 Related expressions:
201 Constant expressions that differ only by an additive integer
202 are called related. When a constant expression is put in
203 the table, the related expression with no constant term
204 is also entered. These are made to point at each other
205 so that it is possible to find out if there exists any
206 register equivalent to an expression related to a given expression. */
208 /* Length of qty_table vector. We know in advance we will not need
209 a quantity number this big. */
211 static int max_qty;
213 /* Next quantity number to be allocated.
214 This is 1 + the largest number needed so far. */
216 static int next_qty;
218 /* Per-qty information tracking.
220 `first_reg' and `last_reg' track the head and tail of the
221 chain of registers which currently contain this quantity.
223 `mode' contains the machine mode of this quantity.
225 `const_rtx' holds the rtx of the constant value of this
226 quantity, if known. A summations of the frame/arg pointer
227 and a constant can also be entered here. When this holds
228 a known value, `const_insn' is the insn which stored the
229 constant value.
231 `comparison_{code,const,qty}' are used to track when a
232 comparison between a quantity and some constant or register has
233 been passed. In such a case, we know the results of the comparison
234 in case we see it again. These members record a comparison that
235 is known to be true. `comparison_code' holds the rtx code of such
236 a comparison, else it is set to UNKNOWN and the other two
237 comparison members are undefined. `comparison_const' holds
238 the constant being compared against, or zero if the comparison
239 is not against a constant. `comparison_qty' holds the quantity
240 being compared against when the result is known. If the comparison
241 is not with a register, `comparison_qty' is -1. */
243 struct qty_table_elem
245 rtx const_rtx;
246 rtx const_insn;
247 rtx comparison_const;
248 int comparison_qty;
249 unsigned int first_reg, last_reg;
250 /* The sizes of these fields should match the sizes of the
251 code and mode fields of struct rtx_def (see rtl.h). */
252 ENUM_BITFIELD(rtx_code) comparison_code : 16;
253 ENUM_BITFIELD(machine_mode) mode : 8;
256 /* The table of all qtys, indexed by qty number. */
257 static struct qty_table_elem *qty_table;
259 /* Structure used to pass arguments via for_each_rtx to function
260 cse_change_cc_mode. */
261 struct change_cc_mode_args
263 rtx insn;
264 rtx newreg;
267 #ifdef HAVE_cc0
268 /* For machines that have a CC0, we do not record its value in the hash
269 table since its use is guaranteed to be the insn immediately following
270 its definition and any other insn is presumed to invalidate it.
272 Instead, we store below the value last assigned to CC0. If it should
273 happen to be a constant, it is stored in preference to the actual
274 assigned value. In case it is a constant, we store the mode in which
275 the constant should be interpreted. */
277 static rtx prev_insn_cc0;
278 static enum machine_mode prev_insn_cc0_mode;
280 /* Previous actual insn. 0 if at first insn of basic block. */
282 static rtx prev_insn;
283 #endif
285 /* Insn being scanned. */
287 static rtx this_insn;
289 /* Index by register number, gives the number of the next (or
290 previous) register in the chain of registers sharing the same
291 value.
293 Or -1 if this register is at the end of the chain.
295 If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined. */
297 /* Per-register equivalence chain. */
298 struct reg_eqv_elem
300 int next, prev;
303 /* The table of all register equivalence chains. */
304 static struct reg_eqv_elem *reg_eqv_table;
306 struct cse_reg_info
308 /* The timestamp at which this register is initialized. */
309 unsigned int timestamp;
311 /* The quantity number of the register's current contents. */
312 int reg_qty;
314 /* The number of times the register has been altered in the current
315 basic block. */
316 int reg_tick;
318 /* The REG_TICK value at which rtx's containing this register are
319 valid in the hash table. If this does not equal the current
320 reg_tick value, such expressions existing in the hash table are
321 invalid. */
322 int reg_in_table;
324 /* The SUBREG that was set when REG_TICK was last incremented. Set
325 to -1 if the last store was to the whole register, not a subreg. */
326 unsigned int subreg_ticked;
329 /* A table of cse_reg_info indexed by register numbers. */
330 static struct cse_reg_info *cse_reg_info_table;
332 /* The size of the above table. */
333 static unsigned int cse_reg_info_table_size;
335 /* The index of the first entry that has not been initialized. */
336 static unsigned int cse_reg_info_table_first_uninitialized;
338 /* The timestamp at the beginning of the current run of
339 cse_basic_block. We increment this variable at the beginning of
340 the current run of cse_basic_block. The timestamp field of a
341 cse_reg_info entry matches the value of this variable if and only
342 if the entry has been initialized during the current run of
343 cse_basic_block. */
344 static unsigned int cse_reg_info_timestamp;
346 /* A HARD_REG_SET containing all the hard registers for which there is
347 currently a REG expression in the hash table. Note the difference
348 from the above variables, which indicate if the REG is mentioned in some
349 expression in the table. */
351 static HARD_REG_SET hard_regs_in_table;
353 /* CUID of insn that starts the basic block currently being cse-processed. */
355 static int cse_basic_block_start;
357 /* CUID of insn that ends the basic block currently being cse-processed. */
359 static int cse_basic_block_end;
361 /* Vector mapping INSN_UIDs to cuids.
362 The cuids are like uids but increase monotonically always.
363 We use them to see whether a reg is used outside a given basic block. */
365 static int *uid_cuid;
367 /* Highest UID in UID_CUID. */
368 static int max_uid;
370 /* Get the cuid of an insn. */
372 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
374 /* Nonzero if cse has altered conditional jump insns
375 in such a way that jump optimization should be redone. */
377 static int cse_jumps_altered;
379 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
380 REG_LABEL, we have to rerun jump after CSE to put in the note. */
381 static int recorded_label_ref;
383 /* canon_hash stores 1 in do_not_record
384 if it notices a reference to CC0, PC, or some other volatile
385 subexpression. */
387 static int do_not_record;
389 /* canon_hash stores 1 in hash_arg_in_memory
390 if it notices a reference to memory within the expression being hashed. */
392 static int hash_arg_in_memory;
394 /* The hash table contains buckets which are chains of `struct table_elt's,
395 each recording one expression's information.
396 That expression is in the `exp' field.
398 The canon_exp field contains a canonical (from the point of view of
399 alias analysis) version of the `exp' field.
401 Those elements with the same hash code are chained in both directions
402 through the `next_same_hash' and `prev_same_hash' fields.
404 Each set of expressions with equivalent values
405 are on a two-way chain through the `next_same_value'
406 and `prev_same_value' fields, and all point with
407 the `first_same_value' field at the first element in
408 that chain. The chain is in order of increasing cost.
409 Each element's cost value is in its `cost' field.
411 The `in_memory' field is nonzero for elements that
412 involve any reference to memory. These elements are removed
413 whenever a write is done to an unidentified location in memory.
414 To be safe, we assume that a memory address is unidentified unless
415 the address is either a symbol constant or a constant plus
416 the frame pointer or argument pointer.
418 The `related_value' field is used to connect related expressions
419 (that differ by adding an integer).
420 The related expressions are chained in a circular fashion.
421 `related_value' is zero for expressions for which this
422 chain is not useful.
424 The `cost' field stores the cost of this element's expression.
425 The `regcost' field stores the value returned by approx_reg_cost for
426 this element's expression.
428 The `is_const' flag is set if the element is a constant (including
429 a fixed address).
431 The `flag' field is used as a temporary during some search routines.
433 The `mode' field is usually the same as GET_MODE (`exp'), but
434 if `exp' is a CONST_INT and has no machine mode then the `mode'
435 field is the mode it was being used as. Each constant is
436 recorded separately for each mode it is used with. */
438 struct table_elt
440 rtx exp;
441 rtx canon_exp;
442 struct table_elt *next_same_hash;
443 struct table_elt *prev_same_hash;
444 struct table_elt *next_same_value;
445 struct table_elt *prev_same_value;
446 struct table_elt *first_same_value;
447 struct table_elt *related_value;
448 int cost;
449 int regcost;
450 /* The size of this field should match the size
451 of the mode field of struct rtx_def (see rtl.h). */
452 ENUM_BITFIELD(machine_mode) mode : 8;
453 char in_memory;
454 char is_const;
455 char flag;
458 /* We don't want a lot of buckets, because we rarely have very many
459 things stored in the hash table, and a lot of buckets slows
460 down a lot of loops that happen frequently. */
461 #define HASH_SHIFT 5
462 #define HASH_SIZE (1 << HASH_SHIFT)
463 #define HASH_MASK (HASH_SIZE - 1)
465 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
466 register (hard registers may require `do_not_record' to be set). */
468 #define HASH(X, M) \
469 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
470 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
471 : canon_hash (X, M)) & HASH_MASK)
473 /* Like HASH, but without side-effects. */
474 #define SAFE_HASH(X, M) \
475 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
476 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
477 : safe_hash (X, M)) & HASH_MASK)
479 /* Determine whether register number N is considered a fixed register for the
480 purpose of approximating register costs.
481 It is desirable to replace other regs with fixed regs, to reduce need for
482 non-fixed hard regs.
483 A reg wins if it is either the frame pointer or designated as fixed. */
484 #define FIXED_REGNO_P(N) \
485 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
486 || fixed_regs[N] || global_regs[N])
488 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
489 hard registers and pointers into the frame are the cheapest with a cost
490 of 0. Next come pseudos with a cost of one and other hard registers with
491 a cost of 2. Aside from these special cases, call `rtx_cost'. */
493 #define CHEAP_REGNO(N) \
494 (REGNO_PTR_FRAME_P(N) \
495 || (HARD_REGISTER_NUM_P (N) \
496 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
498 #define COST(X) (REG_P (X) ? 0 : notreg_cost (X, SET))
499 #define COST_IN(X,OUTER) (REG_P (X) ? 0 : notreg_cost (X, OUTER))
501 /* Get the number of times this register has been updated in this
502 basic block. */
504 #define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)
506 /* Get the point at which REG was recorded in the table. */
508 #define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)
510 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
511 SUBREG). */
513 #define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)
515 /* Get the quantity number for REG. */
517 #define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)
519 /* Determine if the quantity number for register X represents a valid index
520 into the qty_table. */
522 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
524 static struct table_elt *table[HASH_SIZE];
526 /* Chain of `struct table_elt's made so far for this function
527 but currently removed from the table. */
529 static struct table_elt *free_element_chain;
531 /* Set to the cost of a constant pool reference if one was found for a
532 symbolic constant. If this was found, it means we should try to
533 convert constants into constant pool entries if they don't fit in
534 the insn. */
536 static int constant_pool_entries_cost;
537 static int constant_pool_entries_regcost;
539 /* This data describes a block that will be processed by cse_basic_block. */
541 struct cse_basic_block_data
543 /* Lowest CUID value of insns in block. */
544 int low_cuid;
545 /* Highest CUID value of insns in block. */
546 int high_cuid;
547 /* Total number of SETs in block. */
548 int nsets;
549 /* Last insn in the block. */
550 rtx last;
551 /* Size of current branch path, if any. */
552 int path_size;
553 /* Current branch path, indicating which branches will be taken. */
554 struct branch_path
556 /* The branch insn. */
557 rtx branch;
558 /* Whether it should be taken or not. */
559 enum taken {PATH_TAKEN, PATH_NOT_TAKEN} status;
560 } *path;
563 static bool fixed_base_plus_p (rtx x);
564 static int notreg_cost (rtx, enum rtx_code);
565 static int approx_reg_cost_1 (rtx *, void *);
566 static int approx_reg_cost (rtx);
567 static int preferable (int, int, int, int);
568 static void new_basic_block (void);
569 static void make_new_qty (unsigned int, enum machine_mode);
570 static void make_regs_eqv (unsigned int, unsigned int);
571 static void delete_reg_equiv (unsigned int);
572 static int mention_regs (rtx);
573 static int insert_regs (rtx, struct table_elt *, int);
574 static void remove_from_table (struct table_elt *, unsigned);
575 static struct table_elt *lookup (rtx, unsigned, enum machine_mode);
576 static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);
577 static rtx lookup_as_function (rtx, enum rtx_code);
578 static struct table_elt *insert (rtx, struct table_elt *, unsigned,
579 enum machine_mode);
580 static void merge_equiv_classes (struct table_elt *, struct table_elt *);
581 static void invalidate (rtx, enum machine_mode);
582 static int cse_rtx_varies_p (rtx, int);
583 static void remove_invalid_refs (unsigned int);
584 static void remove_invalid_subreg_refs (unsigned int, unsigned int,
585 enum machine_mode);
586 static void rehash_using_reg (rtx);
587 static void invalidate_memory (void);
588 static void invalidate_for_call (void);
589 static rtx use_related_value (rtx, struct table_elt *);
591 static inline unsigned canon_hash (rtx, enum machine_mode);
592 static inline unsigned safe_hash (rtx, enum machine_mode);
593 static unsigned hash_rtx_string (const char *);
595 static rtx canon_reg (rtx, rtx);
596 static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
597 enum machine_mode *,
598 enum machine_mode *);
599 static rtx fold_rtx (rtx, rtx);
600 static rtx equiv_constant (rtx);
601 static void record_jump_equiv (rtx, bool);
602 static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
603 int);
604 static void cse_insn (rtx, rtx);
605 static void cse_end_of_basic_block (rtx, struct cse_basic_block_data *,
606 int);
607 static void invalidate_from_clobbers (rtx);
608 static rtx cse_process_notes (rtx, rtx);
609 static rtx cse_basic_block (rtx, rtx, struct branch_path *);
610 static void count_reg_usage (rtx, int *, rtx, int);
611 static int check_for_label_ref (rtx *, void *);
612 extern void dump_class (struct table_elt*);
613 static void get_cse_reg_info_1 (unsigned int regno);
614 static struct cse_reg_info * get_cse_reg_info (unsigned int regno);
615 static int check_dependence (rtx *, void *);
617 static void flush_hash_table (void);
618 static bool insn_live_p (rtx, int *);
619 static bool set_live_p (rtx, rtx, int *);
620 static bool dead_libcall_p (rtx, int *);
621 static int cse_change_cc_mode (rtx *, void *);
622 static void cse_change_cc_mode_insn (rtx, rtx);
623 static void cse_change_cc_mode_insns (rtx, rtx, rtx);
624 static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);
627 #undef RTL_HOOKS_GEN_LOWPART
628 #define RTL_HOOKS_GEN_LOWPART gen_lowpart_if_possible
630 static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;
632 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
633 virtual regs here because the simplify_*_operation routines are called
634 by integrate.c, which is called before virtual register instantiation. */
636 static bool
637 fixed_base_plus_p (rtx x)
639 switch (GET_CODE (x))
641 case REG:
642 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
643 return true;
644 if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
645 return true;
646 if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
647 && REGNO (x) <= LAST_VIRTUAL_REGISTER)
648 return true;
649 return false;
651 case PLUS:
652 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
653 return false;
654 return fixed_base_plus_p (XEXP (x, 0));
656 default:
657 return false;
661 /* Dump the expressions in the equivalence class indicated by CLASSP.
662 This function is used only for debugging. */
663 void
664 dump_class (struct table_elt *classp)
666 struct table_elt *elt;
668 fprintf (stderr, "Equivalence chain for ");
669 print_rtl (stderr, classp->exp);
670 fprintf (stderr, ": \n");
672 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
674 print_rtl (stderr, elt->exp);
675 fprintf (stderr, "\n");
679 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
681 static int
682 approx_reg_cost_1 (rtx *xp, void *data)
684 rtx x = *xp;
685 int *cost_p = data;
687 if (x && REG_P (x))
689 unsigned int regno = REGNO (x);
691 if (! CHEAP_REGNO (regno))
693 if (regno < FIRST_PSEUDO_REGISTER)
695 if (SMALL_REGISTER_CLASSES)
696 return 1;
697 *cost_p += 2;
699 else
700 *cost_p += 1;
704 return 0;
707 /* Return an estimate of the cost of the registers used in an rtx.
708 This is mostly the number of different REG expressions in the rtx;
709 however for some exceptions like fixed registers we use a cost of
710 0. If any other hard register reference occurs, return MAX_COST. */
712 static int
713 approx_reg_cost (rtx x)
715 int cost = 0;
717 if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
718 return MAX_COST;
720 return cost;
723 /* Return a negative value if an rtx A, whose costs are given by COST_A
724 and REGCOST_A, is more desirable than an rtx B.
725 Return a positive value if A is less desirable, or 0 if the two are
726 equally good. */
727 static int
728 preferable (int cost_a, int regcost_a, int cost_b, int regcost_b)
730 /* First, get rid of cases involving expressions that are entirely
731 unwanted. */
732 if (cost_a != cost_b)
734 if (cost_a == MAX_COST)
735 return 1;
736 if (cost_b == MAX_COST)
737 return -1;
740 /* Avoid extending lifetimes of hardregs. */
741 if (regcost_a != regcost_b)
743 if (regcost_a == MAX_COST)
744 return 1;
745 if (regcost_b == MAX_COST)
746 return -1;
749 /* Normal operation costs take precedence. */
750 if (cost_a != cost_b)
751 return cost_a - cost_b;
752 /* Only if these are identical consider effects on register pressure. */
753 if (regcost_a != regcost_b)
754 return regcost_a - regcost_b;
755 return 0;
758 /* Internal function, to compute cost when X is not a register; called
759 from COST macro to keep it simple. */
761 static int
762 notreg_cost (rtx x, enum rtx_code outer)
764 return ((GET_CODE (x) == SUBREG
765 && REG_P (SUBREG_REG (x))
766 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
767 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
768 && (GET_MODE_SIZE (GET_MODE (x))
769 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
770 && subreg_lowpart_p (x)
771 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
772 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
774 : rtx_cost (x, outer) * 2);
778 /* Initialize CSE_REG_INFO_TABLE. */
780 static void
781 init_cse_reg_info (unsigned int nregs)
783 /* Do we need to grow the table? */
784 if (nregs > cse_reg_info_table_size)
786 unsigned int new_size;
788 if (cse_reg_info_table_size < 2048)
790 /* Compute a new size that is a power of 2 and no smaller
791 than the large of NREGS and 64. */
792 new_size = (cse_reg_info_table_size
793 ? cse_reg_info_table_size : 64);
795 while (new_size < nregs)
796 new_size *= 2;
798 else
800 /* If we need a big table, allocate just enough to hold
801 NREGS registers. */
802 new_size = nregs;
805 /* Reallocate the table with NEW_SIZE entries. */
806 if (cse_reg_info_table)
807 free (cse_reg_info_table);
808 cse_reg_info_table = XNEWVEC (struct cse_reg_info, new_size);
809 cse_reg_info_table_size = new_size;
810 cse_reg_info_table_first_uninitialized = 0;
813 /* Do we have all of the first NREGS entries initialized? */
814 if (cse_reg_info_table_first_uninitialized < nregs)
816 unsigned int old_timestamp = cse_reg_info_timestamp - 1;
817 unsigned int i;
819 /* Put the old timestamp on newly allocated entries so that they
820 will all be considered out of date. We do not touch those
821 entries beyond the first NREGS entries to be nice to the
822 virtual memory. */
823 for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
824 cse_reg_info_table[i].timestamp = old_timestamp;
826 cse_reg_info_table_first_uninitialized = nregs;
830 /* Given REGNO, initialize the cse_reg_info entry for REGNO. */
832 static void
833 get_cse_reg_info_1 (unsigned int regno)
835 /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
836 entry will be considered to have been initialized. */
837 cse_reg_info_table[regno].timestamp = cse_reg_info_timestamp;
839 /* Initialize the rest of the entry. */
840 cse_reg_info_table[regno].reg_tick = 1;
841 cse_reg_info_table[regno].reg_in_table = -1;
842 cse_reg_info_table[regno].subreg_ticked = -1;
843 cse_reg_info_table[regno].reg_qty = -regno - 1;
846 /* Find a cse_reg_info entry for REGNO. */
848 static inline struct cse_reg_info *
849 get_cse_reg_info (unsigned int regno)
851 struct cse_reg_info *p = &cse_reg_info_table[regno];
853 /* If this entry has not been initialized, go ahead and initialize
854 it. */
855 if (p->timestamp != cse_reg_info_timestamp)
856 get_cse_reg_info_1 (regno);
858 return p;
861 /* Clear the hash table and initialize each register with its own quantity,
862 for a new basic block. */
864 static void
865 new_basic_block (void)
867 int i;
869 next_qty = 0;
871 /* Invalidate cse_reg_info_table. */
872 cse_reg_info_timestamp++;
874 /* Clear out hash table state for this pass. */
875 CLEAR_HARD_REG_SET (hard_regs_in_table);
877 /* The per-quantity values used to be initialized here, but it is
878 much faster to initialize each as it is made in `make_new_qty'. */
880 for (i = 0; i < HASH_SIZE; i++)
882 struct table_elt *first;
884 first = table[i];
885 if (first != NULL)
887 struct table_elt *last = first;
889 table[i] = NULL;
891 while (last->next_same_hash != NULL)
892 last = last->next_same_hash;
894 /* Now relink this hash entire chain into
895 the free element list. */
897 last->next_same_hash = free_element_chain;
898 free_element_chain = first;
902 #ifdef HAVE_cc0
903 prev_insn = 0;
904 prev_insn_cc0 = 0;
905 #endif
908 /* Say that register REG contains a quantity in mode MODE not in any
909 register before and initialize that quantity. */
911 static void
912 make_new_qty (unsigned int reg, enum machine_mode mode)
914 int q;
915 struct qty_table_elem *ent;
916 struct reg_eqv_elem *eqv;
918 gcc_assert (next_qty < max_qty);
920 q = REG_QTY (reg) = next_qty++;
921 ent = &qty_table[q];
922 ent->first_reg = reg;
923 ent->last_reg = reg;
924 ent->mode = mode;
925 ent->const_rtx = ent->const_insn = NULL_RTX;
926 ent->comparison_code = UNKNOWN;
928 eqv = &reg_eqv_table[reg];
929 eqv->next = eqv->prev = -1;
932 /* Make reg NEW equivalent to reg OLD.
933 OLD is not changing; NEW is. */
935 static void
936 make_regs_eqv (unsigned int new, unsigned int old)
938 unsigned int lastr, firstr;
939 int q = REG_QTY (old);
940 struct qty_table_elem *ent;
942 ent = &qty_table[q];
944 /* Nothing should become eqv until it has a "non-invalid" qty number. */
945 gcc_assert (REGNO_QTY_VALID_P (old));
947 REG_QTY (new) = q;
948 firstr = ent->first_reg;
949 lastr = ent->last_reg;
951 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
952 hard regs. Among pseudos, if NEW will live longer than any other reg
953 of the same qty, and that is beyond the current basic block,
954 make it the new canonical replacement for this qty. */
955 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
956 /* Certain fixed registers might be of the class NO_REGS. This means
957 that not only can they not be allocated by the compiler, but
958 they cannot be used in substitutions or canonicalizations
959 either. */
960 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
961 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
962 || (new >= FIRST_PSEUDO_REGISTER
963 && (firstr < FIRST_PSEUDO_REGISTER
964 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
965 || (uid_cuid[REGNO_FIRST_UID (new)]
966 < cse_basic_block_start))
967 && (uid_cuid[REGNO_LAST_UID (new)]
968 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
970 reg_eqv_table[firstr].prev = new;
971 reg_eqv_table[new].next = firstr;
972 reg_eqv_table[new].prev = -1;
973 ent->first_reg = new;
975 else
977 /* If NEW is a hard reg (known to be non-fixed), insert at end.
978 Otherwise, insert before any non-fixed hard regs that are at the
979 end. Registers of class NO_REGS cannot be used as an
980 equivalent for anything. */
981 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
982 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
983 && new >= FIRST_PSEUDO_REGISTER)
984 lastr = reg_eqv_table[lastr].prev;
985 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
986 if (reg_eqv_table[lastr].next >= 0)
987 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
988 else
989 qty_table[q].last_reg = new;
990 reg_eqv_table[lastr].next = new;
991 reg_eqv_table[new].prev = lastr;
995 /* Remove REG from its equivalence class. */
997 static void
998 delete_reg_equiv (unsigned int reg)
1000 struct qty_table_elem *ent;
1001 int q = REG_QTY (reg);
1002 int p, n;
1004 /* If invalid, do nothing. */
1005 if (! REGNO_QTY_VALID_P (reg))
1006 return;
1008 ent = &qty_table[q];
1010 p = reg_eqv_table[reg].prev;
1011 n = reg_eqv_table[reg].next;
1013 if (n != -1)
1014 reg_eqv_table[n].prev = p;
1015 else
1016 ent->last_reg = p;
1017 if (p != -1)
1018 reg_eqv_table[p].next = n;
1019 else
1020 ent->first_reg = n;
1022 REG_QTY (reg) = -reg - 1;
1025 /* Remove any invalid expressions from the hash table
1026 that refer to any of the registers contained in expression X.
1028 Make sure that newly inserted references to those registers
1029 as subexpressions will be considered valid.
1031 mention_regs is not called when a register itself
1032 is being stored in the table.
1034 Return 1 if we have done something that may have changed the hash code
1035 of X. */
1037 static int
1038 mention_regs (rtx x)
1040 enum rtx_code code;
1041 int i, j;
1042 const char *fmt;
1043 int changed = 0;
1045 if (x == 0)
1046 return 0;
1048 code = GET_CODE (x);
1049 if (code == REG)
1051 unsigned int regno = REGNO (x);
1052 unsigned int endregno
1053 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1054 : hard_regno_nregs[regno][GET_MODE (x)]);
1055 unsigned int i;
1057 for (i = regno; i < endregno; i++)
1059 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1060 remove_invalid_refs (i);
1062 REG_IN_TABLE (i) = REG_TICK (i);
1063 SUBREG_TICKED (i) = -1;
1066 return 0;
1069 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1070 pseudo if they don't use overlapping words. We handle only pseudos
1071 here for simplicity. */
1072 if (code == SUBREG && REG_P (SUBREG_REG (x))
1073 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1075 unsigned int i = REGNO (SUBREG_REG (x));
1077 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1079 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1080 the last store to this register really stored into this
1081 subreg, then remove the memory of this subreg.
1082 Otherwise, remove any memory of the entire register and
1083 all its subregs from the table. */
1084 if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1085 || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1086 remove_invalid_refs (i);
1087 else
1088 remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1091 REG_IN_TABLE (i) = REG_TICK (i);
1092 SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1093 return 0;
1096 /* If X is a comparison or a COMPARE and either operand is a register
1097 that does not have a quantity, give it one. This is so that a later
1098 call to record_jump_equiv won't cause X to be assigned a different
1099 hash code and not found in the table after that call.
1101 It is not necessary to do this here, since rehash_using_reg can
1102 fix up the table later, but doing this here eliminates the need to
1103 call that expensive function in the most common case where the only
1104 use of the register is in the comparison. */
1106 if (code == COMPARE || COMPARISON_P (x))
1108 if (REG_P (XEXP (x, 0))
1109 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1110 if (insert_regs (XEXP (x, 0), NULL, 0))
1112 rehash_using_reg (XEXP (x, 0));
1113 changed = 1;
1116 if (REG_P (XEXP (x, 1))
1117 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1118 if (insert_regs (XEXP (x, 1), NULL, 0))
1120 rehash_using_reg (XEXP (x, 1));
1121 changed = 1;
1125 fmt = GET_RTX_FORMAT (code);
1126 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1127 if (fmt[i] == 'e')
1128 changed |= mention_regs (XEXP (x, i));
1129 else if (fmt[i] == 'E')
1130 for (j = 0; j < XVECLEN (x, i); j++)
1131 changed |= mention_regs (XVECEXP (x, i, j));
1133 return changed;
1136 /* Update the register quantities for inserting X into the hash table
1137 with a value equivalent to CLASSP.
1138 (If the class does not contain a REG, it is irrelevant.)
1139 If MODIFIED is nonzero, X is a destination; it is being modified.
1140 Note that delete_reg_equiv should be called on a register
1141 before insert_regs is done on that register with MODIFIED != 0.
1143 Nonzero value means that elements of reg_qty have changed
1144 so X's hash code may be different. */
1146 static int
1147 insert_regs (rtx x, struct table_elt *classp, int modified)
1149 if (REG_P (x))
1151 unsigned int regno = REGNO (x);
1152 int qty_valid;
1154 /* If REGNO is in the equivalence table already but is of the
1155 wrong mode for that equivalence, don't do anything here. */
1157 qty_valid = REGNO_QTY_VALID_P (regno);
1158 if (qty_valid)
1160 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1162 if (ent->mode != GET_MODE (x))
1163 return 0;
1166 if (modified || ! qty_valid)
1168 if (classp)
1169 for (classp = classp->first_same_value;
1170 classp != 0;
1171 classp = classp->next_same_value)
1172 if (REG_P (classp->exp)
1173 && GET_MODE (classp->exp) == GET_MODE (x))
1175 unsigned c_regno = REGNO (classp->exp);
1177 gcc_assert (REGNO_QTY_VALID_P (c_regno));
1179 /* Suppose that 5 is hard reg and 100 and 101 are
1180 pseudos. Consider
1182 (set (reg:si 100) (reg:si 5))
1183 (set (reg:si 5) (reg:si 100))
1184 (set (reg:di 101) (reg:di 5))
1186 We would now set REG_QTY (101) = REG_QTY (5), but the
1187 entry for 5 is in SImode. When we use this later in
1188 copy propagation, we get the register in wrong mode. */
1189 if (qty_table[REG_QTY (c_regno)].mode != GET_MODE (x))
1190 continue;
1192 make_regs_eqv (regno, c_regno);
1193 return 1;
1196 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1197 than REG_IN_TABLE to find out if there was only a single preceding
1198 invalidation - for the SUBREG - or another one, which would be
1199 for the full register. However, if we find here that REG_TICK
1200 indicates that the register is invalid, it means that it has
1201 been invalidated in a separate operation. The SUBREG might be used
1202 now (then this is a recursive call), or we might use the full REG
1203 now and a SUBREG of it later. So bump up REG_TICK so that
1204 mention_regs will do the right thing. */
1205 if (! modified
1206 && REG_IN_TABLE (regno) >= 0
1207 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1208 REG_TICK (regno)++;
1209 make_new_qty (regno, GET_MODE (x));
1210 return 1;
1213 return 0;
1216 /* If X is a SUBREG, we will likely be inserting the inner register in the
1217 table. If that register doesn't have an assigned quantity number at
1218 this point but does later, the insertion that we will be doing now will
1219 not be accessible because its hash code will have changed. So assign
1220 a quantity number now. */
1222 else if (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))
1223 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1225 insert_regs (SUBREG_REG (x), NULL, 0);
1226 mention_regs (x);
1227 return 1;
1229 else
1230 return mention_regs (x);
1233 /* Look in or update the hash table. */
1235 /* Remove table element ELT from use in the table.
1236 HASH is its hash code, made using the HASH macro.
1237 It's an argument because often that is known in advance
1238 and we save much time not recomputing it. */
1240 static void
1241 remove_from_table (struct table_elt *elt, unsigned int hash)
1243 if (elt == 0)
1244 return;
1246 /* Mark this element as removed. See cse_insn. */
1247 elt->first_same_value = 0;
1249 /* Remove the table element from its equivalence class. */
1252 struct table_elt *prev = elt->prev_same_value;
1253 struct table_elt *next = elt->next_same_value;
1255 if (next)
1256 next->prev_same_value = prev;
1258 if (prev)
1259 prev->next_same_value = next;
1260 else
1262 struct table_elt *newfirst = next;
1263 while (next)
1265 next->first_same_value = newfirst;
1266 next = next->next_same_value;
1271 /* Remove the table element from its hash bucket. */
1274 struct table_elt *prev = elt->prev_same_hash;
1275 struct table_elt *next = elt->next_same_hash;
1277 if (next)
1278 next->prev_same_hash = prev;
1280 if (prev)
1281 prev->next_same_hash = next;
1282 else if (table[hash] == elt)
1283 table[hash] = next;
1284 else
1286 /* This entry is not in the proper hash bucket. This can happen
1287 when two classes were merged by `merge_equiv_classes'. Search
1288 for the hash bucket that it heads. This happens only very
1289 rarely, so the cost is acceptable. */
1290 for (hash = 0; hash < HASH_SIZE; hash++)
1291 if (table[hash] == elt)
1292 table[hash] = next;
1296 /* Remove the table element from its related-value circular chain. */
1298 if (elt->related_value != 0 && elt->related_value != elt)
1300 struct table_elt *p = elt->related_value;
1302 while (p->related_value != elt)
1303 p = p->related_value;
1304 p->related_value = elt->related_value;
1305 if (p->related_value == p)
1306 p->related_value = 0;
1309 /* Now add it to the free element chain. */
1310 elt->next_same_hash = free_element_chain;
1311 free_element_chain = elt;
1314 /* Look up X in the hash table and return its table element,
1315 or 0 if X is not in the table.
1317 MODE is the machine-mode of X, or if X is an integer constant
1318 with VOIDmode then MODE is the mode with which X will be used.
1320 Here we are satisfied to find an expression whose tree structure
1321 looks like X. */
1323 static struct table_elt *
1324 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1326 struct table_elt *p;
1328 for (p = table[hash]; p; p = p->next_same_hash)
1329 if (mode == p->mode && ((x == p->exp && REG_P (x))
1330 || exp_equiv_p (x, p->exp, !REG_P (x), false)))
1331 return p;
1333 return 0;
1336 /* Like `lookup' but don't care whether the table element uses invalid regs.
1337 Also ignore discrepancies in the machine mode of a register. */
1339 static struct table_elt *
1340 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1342 struct table_elt *p;
1344 if (REG_P (x))
1346 unsigned int regno = REGNO (x);
1348 /* Don't check the machine mode when comparing registers;
1349 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1350 for (p = table[hash]; p; p = p->next_same_hash)
1351 if (REG_P (p->exp)
1352 && REGNO (p->exp) == regno)
1353 return p;
1355 else
1357 for (p = table[hash]; p; p = p->next_same_hash)
1358 if (mode == p->mode
1359 && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
1360 return p;
1363 return 0;
1366 /* Look for an expression equivalent to X and with code CODE.
1367 If one is found, return that expression. */
1369 static rtx
1370 lookup_as_function (rtx x, enum rtx_code code)
1372 struct table_elt *p
1373 = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
1375 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1376 long as we are narrowing. So if we looked in vain for a mode narrower
1377 than word_mode before, look for word_mode now. */
1378 if (p == 0 && code == CONST_INT
1379 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1381 x = copy_rtx (x);
1382 PUT_MODE (x, word_mode);
1383 p = lookup (x, SAFE_HASH (x, VOIDmode), word_mode);
1386 if (p == 0)
1387 return 0;
1389 for (p = p->first_same_value; p; p = p->next_same_value)
1390 if (GET_CODE (p->exp) == code
1391 /* Make sure this is a valid entry in the table. */
1392 && exp_equiv_p (p->exp, p->exp, 1, false))
1393 return p->exp;
1395 return 0;
1398 /* Insert X in the hash table, assuming HASH is its hash code
1399 and CLASSP is an element of the class it should go in
1400 (or 0 if a new class should be made).
1401 It is inserted at the proper position to keep the class in
1402 the order cheapest first.
1404 MODE is the machine-mode of X, or if X is an integer constant
1405 with VOIDmode then MODE is the mode with which X will be used.
1407 For elements of equal cheapness, the most recent one
1408 goes in front, except that the first element in the list
1409 remains first unless a cheaper element is added. The order of
1410 pseudo-registers does not matter, as canon_reg will be called to
1411 find the cheapest when a register is retrieved from the table.
1413 The in_memory field in the hash table element is set to 0.
1414 The caller must set it nonzero if appropriate.
1416 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1417 and if insert_regs returns a nonzero value
1418 you must then recompute its hash code before calling here.
1420 If necessary, update table showing constant values of quantities. */
1422 #define CHEAPER(X, Y) \
1423 (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1425 static struct table_elt *
1426 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1428 struct table_elt *elt;
1430 /* If X is a register and we haven't made a quantity for it,
1431 something is wrong. */
1432 gcc_assert (!REG_P (x) || REGNO_QTY_VALID_P (REGNO (x)));
1434 /* If X is a hard register, show it is being put in the table. */
1435 if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1437 unsigned int regno = REGNO (x);
1438 unsigned int endregno = regno + hard_regno_nregs[regno][GET_MODE (x)];
1439 unsigned int i;
1441 for (i = regno; i < endregno; i++)
1442 SET_HARD_REG_BIT (hard_regs_in_table, i);
1445 /* Put an element for X into the right hash bucket. */
1447 elt = free_element_chain;
1448 if (elt)
1449 free_element_chain = elt->next_same_hash;
1450 else
1451 elt = XNEW (struct table_elt);
1453 elt->exp = x;
1454 elt->canon_exp = NULL_RTX;
1455 elt->cost = COST (x);
1456 elt->regcost = approx_reg_cost (x);
1457 elt->next_same_value = 0;
1458 elt->prev_same_value = 0;
1459 elt->next_same_hash = table[hash];
1460 elt->prev_same_hash = 0;
1461 elt->related_value = 0;
1462 elt->in_memory = 0;
1463 elt->mode = mode;
1464 elt->is_const = (CONSTANT_P (x) || fixed_base_plus_p (x));
1466 if (table[hash])
1467 table[hash]->prev_same_hash = elt;
1468 table[hash] = elt;
1470 /* Put it into the proper value-class. */
1471 if (classp)
1473 classp = classp->first_same_value;
1474 if (CHEAPER (elt, classp))
1475 /* Insert at the head of the class. */
1477 struct table_elt *p;
1478 elt->next_same_value = classp;
1479 classp->prev_same_value = elt;
1480 elt->first_same_value = elt;
1482 for (p = classp; p; p = p->next_same_value)
1483 p->first_same_value = elt;
1485 else
1487 /* Insert not at head of the class. */
1488 /* Put it after the last element cheaper than X. */
1489 struct table_elt *p, *next;
1491 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1492 p = next);
1494 /* Put it after P and before NEXT. */
1495 elt->next_same_value = next;
1496 if (next)
1497 next->prev_same_value = elt;
1499 elt->prev_same_value = p;
1500 p->next_same_value = elt;
1501 elt->first_same_value = classp;
1504 else
1505 elt->first_same_value = elt;
1507 /* If this is a constant being set equivalent to a register or a register
1508 being set equivalent to a constant, note the constant equivalence.
1510 If this is a constant, it cannot be equivalent to a different constant,
1511 and a constant is the only thing that can be cheaper than a register. So
1512 we know the register is the head of the class (before the constant was
1513 inserted).
1515 If this is a register that is not already known equivalent to a
1516 constant, we must check the entire class.
1518 If this is a register that is already known equivalent to an insn,
1519 update the qtys `const_insn' to show that `this_insn' is the latest
1520 insn making that quantity equivalent to the constant. */
1522 if (elt->is_const && classp && REG_P (classp->exp)
1523 && !REG_P (x))
1525 int exp_q = REG_QTY (REGNO (classp->exp));
1526 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1528 exp_ent->const_rtx = gen_lowpart (exp_ent->mode, x);
1529 exp_ent->const_insn = this_insn;
1532 else if (REG_P (x)
1533 && classp
1534 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1535 && ! elt->is_const)
1537 struct table_elt *p;
1539 for (p = classp; p != 0; p = p->next_same_value)
1541 if (p->is_const && !REG_P (p->exp))
1543 int x_q = REG_QTY (REGNO (x));
1544 struct qty_table_elem *x_ent = &qty_table[x_q];
1546 x_ent->const_rtx
1547 = gen_lowpart (GET_MODE (x), p->exp);
1548 x_ent->const_insn = this_insn;
1549 break;
1554 else if (REG_P (x)
1555 && qty_table[REG_QTY (REGNO (x))].const_rtx
1556 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1557 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1559 /* If this is a constant with symbolic value,
1560 and it has a term with an explicit integer value,
1561 link it up with related expressions. */
1562 if (GET_CODE (x) == CONST)
1564 rtx subexp = get_related_value (x);
1565 unsigned subhash;
1566 struct table_elt *subelt, *subelt_prev;
1568 if (subexp != 0)
1570 /* Get the integer-free subexpression in the hash table. */
1571 subhash = SAFE_HASH (subexp, mode);
1572 subelt = lookup (subexp, subhash, mode);
1573 if (subelt == 0)
1574 subelt = insert (subexp, NULL, subhash, mode);
1575 /* Initialize SUBELT's circular chain if it has none. */
1576 if (subelt->related_value == 0)
1577 subelt->related_value = subelt;
1578 /* Find the element in the circular chain that precedes SUBELT. */
1579 subelt_prev = subelt;
1580 while (subelt_prev->related_value != subelt)
1581 subelt_prev = subelt_prev->related_value;
1582 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1583 This way the element that follows SUBELT is the oldest one. */
1584 elt->related_value = subelt_prev->related_value;
1585 subelt_prev->related_value = elt;
1589 return elt;
1592 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1593 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1594 the two classes equivalent.
1596 CLASS1 will be the surviving class; CLASS2 should not be used after this
1597 call.
1599 Any invalid entries in CLASS2 will not be copied. */
1601 static void
1602 merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1604 struct table_elt *elt, *next, *new;
1606 /* Ensure we start with the head of the classes. */
1607 class1 = class1->first_same_value;
1608 class2 = class2->first_same_value;
1610 /* If they were already equal, forget it. */
1611 if (class1 == class2)
1612 return;
1614 for (elt = class2; elt; elt = next)
1616 unsigned int hash;
1617 rtx exp = elt->exp;
1618 enum machine_mode mode = elt->mode;
1620 next = elt->next_same_value;
1622 /* Remove old entry, make a new one in CLASS1's class.
1623 Don't do this for invalid entries as we cannot find their
1624 hash code (it also isn't necessary). */
1625 if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
1627 bool need_rehash = false;
1629 hash_arg_in_memory = 0;
1630 hash = HASH (exp, mode);
1632 if (REG_P (exp))
1634 need_rehash = REGNO_QTY_VALID_P (REGNO (exp));
1635 delete_reg_equiv (REGNO (exp));
1638 remove_from_table (elt, hash);
1640 if (insert_regs (exp, class1, 0) || need_rehash)
1642 rehash_using_reg (exp);
1643 hash = HASH (exp, mode);
1645 new = insert (exp, class1, hash, mode);
1646 new->in_memory = hash_arg_in_memory;
1651 /* Flush the entire hash table. */
1653 static void
1654 flush_hash_table (void)
1656 int i;
1657 struct table_elt *p;
1659 for (i = 0; i < HASH_SIZE; i++)
1660 for (p = table[i]; p; p = table[i])
1662 /* Note that invalidate can remove elements
1663 after P in the current hash chain. */
1664 if (REG_P (p->exp))
1665 invalidate (p->exp, VOIDmode);
1666 else
1667 remove_from_table (p, i);
1671 /* Function called for each rtx to check whether true dependence exist. */
1672 struct check_dependence_data
1674 enum machine_mode mode;
1675 rtx exp;
1676 rtx addr;
1679 static int
1680 check_dependence (rtx *x, void *data)
1682 struct check_dependence_data *d = (struct check_dependence_data *) data;
1683 if (*x && MEM_P (*x))
1684 return canon_true_dependence (d->exp, d->mode, d->addr, *x,
1685 cse_rtx_varies_p);
1686 else
1687 return 0;
1690 /* Remove from the hash table, or mark as invalid, all expressions whose
1691 values could be altered by storing in X. X is a register, a subreg, or
1692 a memory reference with nonvarying address (because, when a memory
1693 reference with a varying address is stored in, all memory references are
1694 removed by invalidate_memory so specific invalidation is superfluous).
1695 FULL_MODE, if not VOIDmode, indicates that this much should be
1696 invalidated instead of just the amount indicated by the mode of X. This
1697 is only used for bitfield stores into memory.
1699 A nonvarying address may be just a register or just a symbol reference,
1700 or it may be either of those plus a numeric offset. */
1702 static void
1703 invalidate (rtx x, enum machine_mode full_mode)
1705 int i;
1706 struct table_elt *p;
1707 rtx addr;
1709 switch (GET_CODE (x))
1711 case REG:
1713 /* If X is a register, dependencies on its contents are recorded
1714 through the qty number mechanism. Just change the qty number of
1715 the register, mark it as invalid for expressions that refer to it,
1716 and remove it itself. */
1717 unsigned int regno = REGNO (x);
1718 unsigned int hash = HASH (x, GET_MODE (x));
1720 /* Remove REGNO from any quantity list it might be on and indicate
1721 that its value might have changed. If it is a pseudo, remove its
1722 entry from the hash table.
1724 For a hard register, we do the first two actions above for any
1725 additional hard registers corresponding to X. Then, if any of these
1726 registers are in the table, we must remove any REG entries that
1727 overlap these registers. */
1729 delete_reg_equiv (regno);
1730 REG_TICK (regno)++;
1731 SUBREG_TICKED (regno) = -1;
1733 if (regno >= FIRST_PSEUDO_REGISTER)
1735 /* Because a register can be referenced in more than one mode,
1736 we might have to remove more than one table entry. */
1737 struct table_elt *elt;
1739 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1740 remove_from_table (elt, hash);
1742 else
1744 HOST_WIDE_INT in_table
1745 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1746 unsigned int endregno
1747 = regno + hard_regno_nregs[regno][GET_MODE (x)];
1748 unsigned int tregno, tendregno, rn;
1749 struct table_elt *p, *next;
1751 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1753 for (rn = regno + 1; rn < endregno; rn++)
1755 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1756 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1757 delete_reg_equiv (rn);
1758 REG_TICK (rn)++;
1759 SUBREG_TICKED (rn) = -1;
1762 if (in_table)
1763 for (hash = 0; hash < HASH_SIZE; hash++)
1764 for (p = table[hash]; p; p = next)
1766 next = p->next_same_hash;
1768 if (!REG_P (p->exp)
1769 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1770 continue;
1772 tregno = REGNO (p->exp);
1773 tendregno
1774 = tregno + hard_regno_nregs[tregno][GET_MODE (p->exp)];
1775 if (tendregno > regno && tregno < endregno)
1776 remove_from_table (p, hash);
1780 return;
1782 case SUBREG:
1783 invalidate (SUBREG_REG (x), VOIDmode);
1784 return;
1786 case PARALLEL:
1787 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1788 invalidate (XVECEXP (x, 0, i), VOIDmode);
1789 return;
1791 case EXPR_LIST:
1792 /* This is part of a disjoint return value; extract the location in
1793 question ignoring the offset. */
1794 invalidate (XEXP (x, 0), VOIDmode);
1795 return;
1797 case MEM:
1798 addr = canon_rtx (get_addr (XEXP (x, 0)));
1799 /* Calculate the canonical version of X here so that
1800 true_dependence doesn't generate new RTL for X on each call. */
1801 x = canon_rtx (x);
1803 /* Remove all hash table elements that refer to overlapping pieces of
1804 memory. */
1805 if (full_mode == VOIDmode)
1806 full_mode = GET_MODE (x);
1808 for (i = 0; i < HASH_SIZE; i++)
1810 struct table_elt *next;
1812 for (p = table[i]; p; p = next)
1814 next = p->next_same_hash;
1815 if (p->in_memory)
1817 struct check_dependence_data d;
1819 /* Just canonicalize the expression once;
1820 otherwise each time we call invalidate
1821 true_dependence will canonicalize the
1822 expression again. */
1823 if (!p->canon_exp)
1824 p->canon_exp = canon_rtx (p->exp);
1825 d.exp = x;
1826 d.addr = addr;
1827 d.mode = full_mode;
1828 if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1829 remove_from_table (p, i);
1833 return;
1835 default:
1836 gcc_unreachable ();
1840 /* Remove all expressions that refer to register REGNO,
1841 since they are already invalid, and we are about to
1842 mark that register valid again and don't want the old
1843 expressions to reappear as valid. */
1845 static void
1846 remove_invalid_refs (unsigned int regno)
1848 unsigned int i;
1849 struct table_elt *p, *next;
1851 for (i = 0; i < HASH_SIZE; i++)
1852 for (p = table[i]; p; p = next)
1854 next = p->next_same_hash;
1855 if (!REG_P (p->exp)
1856 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1857 remove_from_table (p, i);
1861 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1862 and mode MODE. */
1863 static void
1864 remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1865 enum machine_mode mode)
1867 unsigned int i;
1868 struct table_elt *p, *next;
1869 unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
1871 for (i = 0; i < HASH_SIZE; i++)
1872 for (p = table[i]; p; p = next)
1874 rtx exp = p->exp;
1875 next = p->next_same_hash;
1877 if (!REG_P (exp)
1878 && (GET_CODE (exp) != SUBREG
1879 || !REG_P (SUBREG_REG (exp))
1880 || REGNO (SUBREG_REG (exp)) != regno
1881 || (((SUBREG_BYTE (exp)
1882 + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
1883 && SUBREG_BYTE (exp) <= end))
1884 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1885 remove_from_table (p, i);
1889 /* Recompute the hash codes of any valid entries in the hash table that
1890 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1892 This is called when we make a jump equivalence. */
1894 static void
1895 rehash_using_reg (rtx x)
1897 unsigned int i;
1898 struct table_elt *p, *next;
1899 unsigned hash;
1901 if (GET_CODE (x) == SUBREG)
1902 x = SUBREG_REG (x);
1904 /* If X is not a register or if the register is known not to be in any
1905 valid entries in the table, we have no work to do. */
1907 if (!REG_P (x)
1908 || REG_IN_TABLE (REGNO (x)) < 0
1909 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
1910 return;
1912 /* Scan all hash chains looking for valid entries that mention X.
1913 If we find one and it is in the wrong hash chain, move it. */
1915 for (i = 0; i < HASH_SIZE; i++)
1916 for (p = table[i]; p; p = next)
1918 next = p->next_same_hash;
1919 if (reg_mentioned_p (x, p->exp)
1920 && exp_equiv_p (p->exp, p->exp, 1, false)
1921 && i != (hash = SAFE_HASH (p->exp, p->mode)))
1923 if (p->next_same_hash)
1924 p->next_same_hash->prev_same_hash = p->prev_same_hash;
1926 if (p->prev_same_hash)
1927 p->prev_same_hash->next_same_hash = p->next_same_hash;
1928 else
1929 table[i] = p->next_same_hash;
1931 p->next_same_hash = table[hash];
1932 p->prev_same_hash = 0;
1933 if (table[hash])
1934 table[hash]->prev_same_hash = p;
1935 table[hash] = p;
1940 /* Remove from the hash table any expression that is a call-clobbered
1941 register. Also update their TICK values. */
1943 static void
1944 invalidate_for_call (void)
1946 unsigned int regno, endregno;
1947 unsigned int i;
1948 unsigned hash;
1949 struct table_elt *p, *next;
1950 int in_table = 0;
1952 /* Go through all the hard registers. For each that is clobbered in
1953 a CALL_INSN, remove the register from quantity chains and update
1954 reg_tick if defined. Also see if any of these registers is currently
1955 in the table. */
1957 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1958 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1960 delete_reg_equiv (regno);
1961 if (REG_TICK (regno) >= 0)
1963 REG_TICK (regno)++;
1964 SUBREG_TICKED (regno) = -1;
1967 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
1970 /* In the case where we have no call-clobbered hard registers in the
1971 table, we are done. Otherwise, scan the table and remove any
1972 entry that overlaps a call-clobbered register. */
1974 if (in_table)
1975 for (hash = 0; hash < HASH_SIZE; hash++)
1976 for (p = table[hash]; p; p = next)
1978 next = p->next_same_hash;
1980 if (!REG_P (p->exp)
1981 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1982 continue;
1984 regno = REGNO (p->exp);
1985 endregno = regno + hard_regno_nregs[regno][GET_MODE (p->exp)];
1987 for (i = regno; i < endregno; i++)
1988 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1990 remove_from_table (p, hash);
1991 break;
1996 /* Given an expression X of type CONST,
1997 and ELT which is its table entry (or 0 if it
1998 is not in the hash table),
1999 return an alternate expression for X as a register plus integer.
2000 If none can be found, return 0. */
2002 static rtx
2003 use_related_value (rtx x, struct table_elt *elt)
2005 struct table_elt *relt = 0;
2006 struct table_elt *p, *q;
2007 HOST_WIDE_INT offset;
2009 /* First, is there anything related known?
2010 If we have a table element, we can tell from that.
2011 Otherwise, must look it up. */
2013 if (elt != 0 && elt->related_value != 0)
2014 relt = elt;
2015 else if (elt == 0 && GET_CODE (x) == CONST)
2017 rtx subexp = get_related_value (x);
2018 if (subexp != 0)
2019 relt = lookup (subexp,
2020 SAFE_HASH (subexp, GET_MODE (subexp)),
2021 GET_MODE (subexp));
2024 if (relt == 0)
2025 return 0;
2027 /* Search all related table entries for one that has an
2028 equivalent register. */
2030 p = relt;
2031 while (1)
2033 /* This loop is strange in that it is executed in two different cases.
2034 The first is when X is already in the table. Then it is searching
2035 the RELATED_VALUE list of X's class (RELT). The second case is when
2036 X is not in the table. Then RELT points to a class for the related
2037 value.
2039 Ensure that, whatever case we are in, that we ignore classes that have
2040 the same value as X. */
2042 if (rtx_equal_p (x, p->exp))
2043 q = 0;
2044 else
2045 for (q = p->first_same_value; q; q = q->next_same_value)
2046 if (REG_P (q->exp))
2047 break;
2049 if (q)
2050 break;
2052 p = p->related_value;
2054 /* We went all the way around, so there is nothing to be found.
2055 Alternatively, perhaps RELT was in the table for some other reason
2056 and it has no related values recorded. */
2057 if (p == relt || p == 0)
2058 break;
2061 if (q == 0)
2062 return 0;
2064 offset = (get_integer_term (x) - get_integer_term (p->exp));
2065 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2066 return plus_constant (q->exp, offset);
2069 /* Hash a string. Just add its bytes up. */
2070 static inline unsigned
2071 hash_rtx_string (const char *ps)
2073 unsigned hash = 0;
2074 const unsigned char *p = (const unsigned char *) ps;
2076 if (p)
2077 while (*p)
2078 hash += *p++;
2080 return hash;
2083 /* Hash an rtx. We are careful to make sure the value is never negative.
2084 Equivalent registers hash identically.
2085 MODE is used in hashing for CONST_INTs only;
2086 otherwise the mode of X is used.
2088 Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2090 If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2091 a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
2093 Note that cse_insn knows that the hash code of a MEM expression
2094 is just (int) MEM plus the hash code of the address. */
2096 unsigned
2097 hash_rtx (rtx x, enum machine_mode mode, int *do_not_record_p,
2098 int *hash_arg_in_memory_p, bool have_reg_qty)
2100 int i, j;
2101 unsigned hash = 0;
2102 enum rtx_code code;
2103 const char *fmt;
2105 /* Used to turn recursion into iteration. We can't rely on GCC's
2106 tail-recursion elimination since we need to keep accumulating values
2107 in HASH. */
2108 repeat:
2109 if (x == 0)
2110 return hash;
2112 code = GET_CODE (x);
2113 switch (code)
2115 case REG:
2117 unsigned int regno = REGNO (x);
2119 if (!reload_completed)
2121 /* On some machines, we can't record any non-fixed hard register,
2122 because extending its life will cause reload problems. We
2123 consider ap, fp, sp, gp to be fixed for this purpose.
2125 We also consider CCmode registers to be fixed for this purpose;
2126 failure to do so leads to failure to simplify 0<100 type of
2127 conditionals.
2129 On all machines, we can't record any global registers.
2130 Nor should we record any register that is in a small
2131 class, as defined by CLASS_LIKELY_SPILLED_P. */
2132 bool record;
2134 if (regno >= FIRST_PSEUDO_REGISTER)
2135 record = true;
2136 else if (x == frame_pointer_rtx
2137 || x == hard_frame_pointer_rtx
2138 || x == arg_pointer_rtx
2139 || x == stack_pointer_rtx
2140 || x == pic_offset_table_rtx)
2141 record = true;
2142 else if (global_regs[regno])
2143 record = false;
2144 else if (fixed_regs[regno])
2145 record = true;
2146 else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2147 record = true;
2148 else if (SMALL_REGISTER_CLASSES)
2149 record = false;
2150 else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
2151 record = false;
2152 else
2153 record = true;
2155 if (!record)
2157 *do_not_record_p = 1;
2158 return 0;
2162 hash += ((unsigned int) REG << 7);
2163 hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2164 return hash;
2167 /* We handle SUBREG of a REG specially because the underlying
2168 reg changes its hash value with every value change; we don't
2169 want to have to forget unrelated subregs when one subreg changes. */
2170 case SUBREG:
2172 if (REG_P (SUBREG_REG (x)))
2174 hash += (((unsigned int) SUBREG << 7)
2175 + REGNO (SUBREG_REG (x))
2176 + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2177 return hash;
2179 break;
2182 case CONST_INT:
2183 hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2184 + (unsigned int) INTVAL (x));
2185 return hash;
2187 case CONST_DOUBLE:
2188 /* This is like the general case, except that it only counts
2189 the integers representing the constant. */
2190 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2191 if (GET_MODE (x) != VOIDmode)
2192 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2193 else
2194 hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2195 + (unsigned int) CONST_DOUBLE_HIGH (x));
2196 return hash;
2198 case CONST_VECTOR:
2200 int units;
2201 rtx elt;
2203 units = CONST_VECTOR_NUNITS (x);
2205 for (i = 0; i < units; ++i)
2207 elt = CONST_VECTOR_ELT (x, i);
2208 hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
2209 hash_arg_in_memory_p, have_reg_qty);
2212 return hash;
2215 /* Assume there is only one rtx object for any given label. */
2216 case LABEL_REF:
2217 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2218 differences and differences between each stage's debugging dumps. */
2219 hash += (((unsigned int) LABEL_REF << 7)
2220 + CODE_LABEL_NUMBER (XEXP (x, 0)));
2221 return hash;
2223 case SYMBOL_REF:
2225 /* Don't hash on the symbol's address to avoid bootstrap differences.
2226 Different hash values may cause expressions to be recorded in
2227 different orders and thus different registers to be used in the
2228 final assembler. This also avoids differences in the dump files
2229 between various stages. */
2230 unsigned int h = 0;
2231 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
2233 while (*p)
2234 h += (h << 7) + *p++; /* ??? revisit */
2236 hash += ((unsigned int) SYMBOL_REF << 7) + h;
2237 return hash;
2240 case MEM:
2241 /* We don't record if marked volatile or if BLKmode since we don't
2242 know the size of the move. */
2243 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2245 *do_not_record_p = 1;
2246 return 0;
2248 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2249 *hash_arg_in_memory_p = 1;
2251 /* Now that we have already found this special case,
2252 might as well speed it up as much as possible. */
2253 hash += (unsigned) MEM;
2254 x = XEXP (x, 0);
2255 goto repeat;
2257 case USE:
2258 /* A USE that mentions non-volatile memory needs special
2259 handling since the MEM may be BLKmode which normally
2260 prevents an entry from being made. Pure calls are
2261 marked by a USE which mentions BLKmode memory.
2262 See calls.c:emit_call_1. */
2263 if (MEM_P (XEXP (x, 0))
2264 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2266 hash += (unsigned) USE;
2267 x = XEXP (x, 0);
2269 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2270 *hash_arg_in_memory_p = 1;
2272 /* Now that we have already found this special case,
2273 might as well speed it up as much as possible. */
2274 hash += (unsigned) MEM;
2275 x = XEXP (x, 0);
2276 goto repeat;
2278 break;
2280 case PRE_DEC:
2281 case PRE_INC:
2282 case POST_DEC:
2283 case POST_INC:
2284 case PRE_MODIFY:
2285 case POST_MODIFY:
2286 case PC:
2287 case CC0:
2288 case CALL:
2289 case UNSPEC_VOLATILE:
2290 *do_not_record_p = 1;
2291 return 0;
2293 case ASM_OPERANDS:
2294 if (MEM_VOLATILE_P (x))
2296 *do_not_record_p = 1;
2297 return 0;
2299 else
2301 /* We don't want to take the filename and line into account. */
2302 hash += (unsigned) code + (unsigned) GET_MODE (x)
2303 + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
2304 + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2305 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2307 if (ASM_OPERANDS_INPUT_LENGTH (x))
2309 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2311 hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
2312 GET_MODE (ASM_OPERANDS_INPUT (x, i)),
2313 do_not_record_p, hash_arg_in_memory_p,
2314 have_reg_qty)
2315 + hash_rtx_string
2316 (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
2319 hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2320 x = ASM_OPERANDS_INPUT (x, 0);
2321 mode = GET_MODE (x);
2322 goto repeat;
2325 return hash;
2327 break;
2329 default:
2330 break;
2333 i = GET_RTX_LENGTH (code) - 1;
2334 hash += (unsigned) code + (unsigned) GET_MODE (x);
2335 fmt = GET_RTX_FORMAT (code);
2336 for (; i >= 0; i--)
2338 switch (fmt[i])
2340 case 'e':
2341 /* If we are about to do the last recursive call
2342 needed at this level, change it into iteration.
2343 This function is called enough to be worth it. */
2344 if (i == 0)
2346 x = XEXP (x, i);
2347 goto repeat;
2350 hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
2351 hash_arg_in_memory_p, have_reg_qty);
2352 break;
2354 case 'E':
2355 for (j = 0; j < XVECLEN (x, i); j++)
2356 hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
2357 hash_arg_in_memory_p, have_reg_qty);
2358 break;
2360 case 's':
2361 hash += hash_rtx_string (XSTR (x, i));
2362 break;
2364 case 'i':
2365 hash += (unsigned int) XINT (x, i);
2366 break;
2368 case '0': case 't':
2369 /* Unused. */
2370 break;
2372 default:
2373 gcc_unreachable ();
2377 return hash;
2380 /* Hash an rtx X for cse via hash_rtx.
2381 Stores 1 in do_not_record if any subexpression is volatile.
2382 Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2383 does not have the RTX_UNCHANGING_P bit set. */
2385 static inline unsigned
2386 canon_hash (rtx x, enum machine_mode mode)
2388 return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
2391 /* Like canon_hash but with no side effects, i.e. do_not_record
2392 and hash_arg_in_memory are not changed. */
2394 static inline unsigned
2395 safe_hash (rtx x, enum machine_mode mode)
2397 int dummy_do_not_record;
2398 return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
2401 /* Return 1 iff X and Y would canonicalize into the same thing,
2402 without actually constructing the canonicalization of either one.
2403 If VALIDATE is nonzero,
2404 we assume X is an expression being processed from the rtl
2405 and Y was found in the hash table. We check register refs
2406 in Y for being marked as valid.
2408 If FOR_GCSE is true, we compare X and Y for equivalence for GCSE. */
2411 exp_equiv_p (rtx x, rtx y, int validate, bool for_gcse)
2413 int i, j;
2414 enum rtx_code code;
2415 const char *fmt;
2417 /* Note: it is incorrect to assume an expression is equivalent to itself
2418 if VALIDATE is nonzero. */
2419 if (x == y && !validate)
2420 return 1;
2422 if (x == 0 || y == 0)
2423 return x == y;
2425 code = GET_CODE (x);
2426 if (code != GET_CODE (y))
2427 return 0;
2429 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2430 if (GET_MODE (x) != GET_MODE (y))
2431 return 0;
2433 switch (code)
2435 case PC:
2436 case CC0:
2437 case CONST_INT:
2438 case CONST_DOUBLE:
2439 return x == y;
2441 case LABEL_REF:
2442 return XEXP (x, 0) == XEXP (y, 0);
2444 case SYMBOL_REF:
2445 return XSTR (x, 0) == XSTR (y, 0);
2447 case REG:
2448 if (for_gcse)
2449 return REGNO (x) == REGNO (y);
2450 else
2452 unsigned int regno = REGNO (y);
2453 unsigned int i;
2454 unsigned int endregno
2455 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2456 : hard_regno_nregs[regno][GET_MODE (y)]);
2458 /* If the quantities are not the same, the expressions are not
2459 equivalent. If there are and we are not to validate, they
2460 are equivalent. Otherwise, ensure all regs are up-to-date. */
2462 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2463 return 0;
2465 if (! validate)
2466 return 1;
2468 for (i = regno; i < endregno; i++)
2469 if (REG_IN_TABLE (i) != REG_TICK (i))
2470 return 0;
2472 return 1;
2475 case MEM:
2476 if (for_gcse)
2478 /* A volatile mem should not be considered equivalent to any
2479 other. */
2480 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2481 return 0;
2483 /* Can't merge two expressions in different alias sets, since we
2484 can decide that the expression is transparent in a block when
2485 it isn't, due to it being set with the different alias set.
2487 Also, can't merge two expressions with different MEM_ATTRS.
2488 They could e.g. be two different entities allocated into the
2489 same space on the stack (see e.g. PR25130). In that case, the
2490 MEM addresses can be the same, even though the two MEMs are
2491 absolutely not equivalent.
2493 But because really all MEM attributes should be the same for
2494 equivalent MEMs, we just use the invariant that MEMs that have
2495 the same attributes share the same mem_attrs data structure. */
2496 if (MEM_ATTRS (x) != MEM_ATTRS (y))
2497 return 0;
2499 break;
2501 /* For commutative operations, check both orders. */
2502 case PLUS:
2503 case MULT:
2504 case AND:
2505 case IOR:
2506 case XOR:
2507 case NE:
2508 case EQ:
2509 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
2510 validate, for_gcse)
2511 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2512 validate, for_gcse))
2513 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2514 validate, for_gcse)
2515 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2516 validate, for_gcse)));
2518 case ASM_OPERANDS:
2519 /* We don't use the generic code below because we want to
2520 disregard filename and line numbers. */
2522 /* A volatile asm isn't equivalent to any other. */
2523 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2524 return 0;
2526 if (GET_MODE (x) != GET_MODE (y)
2527 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2528 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2529 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2530 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2531 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2532 return 0;
2534 if (ASM_OPERANDS_INPUT_LENGTH (x))
2536 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2537 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2538 ASM_OPERANDS_INPUT (y, i),
2539 validate, for_gcse)
2540 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2541 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2542 return 0;
2545 return 1;
2547 default:
2548 break;
2551 /* Compare the elements. If any pair of corresponding elements
2552 fail to match, return 0 for the whole thing. */
2554 fmt = GET_RTX_FORMAT (code);
2555 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2557 switch (fmt[i])
2559 case 'e':
2560 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
2561 validate, for_gcse))
2562 return 0;
2563 break;
2565 case 'E':
2566 if (XVECLEN (x, i) != XVECLEN (y, i))
2567 return 0;
2568 for (j = 0; j < XVECLEN (x, i); j++)
2569 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2570 validate, for_gcse))
2571 return 0;
2572 break;
2574 case 's':
2575 if (strcmp (XSTR (x, i), XSTR (y, i)))
2576 return 0;
2577 break;
2579 case 'i':
2580 if (XINT (x, i) != XINT (y, i))
2581 return 0;
2582 break;
2584 case 'w':
2585 if (XWINT (x, i) != XWINT (y, i))
2586 return 0;
2587 break;
2589 case '0':
2590 case 't':
2591 break;
2593 default:
2594 gcc_unreachable ();
2598 return 1;
2601 /* Return 1 if X has a value that can vary even between two
2602 executions of the program. 0 means X can be compared reliably
2603 against certain constants or near-constants. */
2605 static int
2606 cse_rtx_varies_p (rtx x, int from_alias)
2608 /* We need not check for X and the equivalence class being of the same
2609 mode because if X is equivalent to a constant in some mode, it
2610 doesn't vary in any mode. */
2612 if (REG_P (x)
2613 && REGNO_QTY_VALID_P (REGNO (x)))
2615 int x_q = REG_QTY (REGNO (x));
2616 struct qty_table_elem *x_ent = &qty_table[x_q];
2618 if (GET_MODE (x) == x_ent->mode
2619 && x_ent->const_rtx != NULL_RTX)
2620 return 0;
2623 if (GET_CODE (x) == PLUS
2624 && GET_CODE (XEXP (x, 1)) == CONST_INT
2625 && REG_P (XEXP (x, 0))
2626 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2628 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2629 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2631 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2632 && x0_ent->const_rtx != NULL_RTX)
2633 return 0;
2636 /* This can happen as the result of virtual register instantiation, if
2637 the initial constant is too large to be a valid address. This gives
2638 us a three instruction sequence, load large offset into a register,
2639 load fp minus a constant into a register, then a MEM which is the
2640 sum of the two `constant' registers. */
2641 if (GET_CODE (x) == PLUS
2642 && REG_P (XEXP (x, 0))
2643 && REG_P (XEXP (x, 1))
2644 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2645 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2647 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2648 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2649 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2650 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2652 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2653 && x0_ent->const_rtx != NULL_RTX
2654 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2655 && x1_ent->const_rtx != NULL_RTX)
2656 return 0;
2659 return rtx_varies_p (x, from_alias);
2662 /* Subroutine of canon_reg. Pass *XLOC through canon_reg, and validate
2663 the result if necessary. INSN is as for canon_reg. */
2665 static void
2666 validate_canon_reg (rtx *xloc, rtx insn)
2668 rtx new = canon_reg (*xloc, insn);
2670 /* If replacing pseudo with hard reg or vice versa, ensure the
2671 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2672 if (insn != 0 && new != 0)
2673 validate_change (insn, xloc, new, 1);
2674 else
2675 *xloc = new;
2678 /* Canonicalize an expression:
2679 replace each register reference inside it
2680 with the "oldest" equivalent register.
2682 If INSN is nonzero validate_change is used to ensure that INSN remains valid
2683 after we make our substitution. The calls are made with IN_GROUP nonzero
2684 so apply_change_group must be called upon the outermost return from this
2685 function (unless INSN is zero). The result of apply_change_group can
2686 generally be discarded since the changes we are making are optional. */
2688 static rtx
2689 canon_reg (rtx x, rtx insn)
2691 int i;
2692 enum rtx_code code;
2693 const char *fmt;
2695 if (x == 0)
2696 return x;
2698 code = GET_CODE (x);
2699 switch (code)
2701 case PC:
2702 case CC0:
2703 case CONST:
2704 case CONST_INT:
2705 case CONST_DOUBLE:
2706 case CONST_VECTOR:
2707 case SYMBOL_REF:
2708 case LABEL_REF:
2709 case ADDR_VEC:
2710 case ADDR_DIFF_VEC:
2711 return x;
2713 case REG:
2715 int first;
2716 int q;
2717 struct qty_table_elem *ent;
2719 /* Never replace a hard reg, because hard regs can appear
2720 in more than one machine mode, and we must preserve the mode
2721 of each occurrence. Also, some hard regs appear in
2722 MEMs that are shared and mustn't be altered. Don't try to
2723 replace any reg that maps to a reg of class NO_REGS. */
2724 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2725 || ! REGNO_QTY_VALID_P (REGNO (x)))
2726 return x;
2728 q = REG_QTY (REGNO (x));
2729 ent = &qty_table[q];
2730 first = ent->first_reg;
2731 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2732 : REGNO_REG_CLASS (first) == NO_REGS ? x
2733 : gen_rtx_REG (ent->mode, first));
2736 default:
2737 break;
2740 fmt = GET_RTX_FORMAT (code);
2741 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2743 int j;
2745 if (fmt[i] == 'e')
2746 validate_canon_reg (&XEXP (x, i), insn);
2747 else if (fmt[i] == 'E')
2748 for (j = 0; j < XVECLEN (x, i); j++)
2749 validate_canon_reg (&XVECEXP (x, i, j), insn);
2752 return x;
2755 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2756 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2757 what values are being compared.
2759 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2760 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2761 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2762 compared to produce cc0.
2764 The return value is the comparison operator and is either the code of
2765 A or the code corresponding to the inverse of the comparison. */
2767 static enum rtx_code
2768 find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
2769 enum machine_mode *pmode1, enum machine_mode *pmode2)
2771 rtx arg1, arg2;
2773 arg1 = *parg1, arg2 = *parg2;
2775 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2777 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2779 /* Set nonzero when we find something of interest. */
2780 rtx x = 0;
2781 int reverse_code = 0;
2782 struct table_elt *p = 0;
2784 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2785 On machines with CC0, this is the only case that can occur, since
2786 fold_rtx will return the COMPARE or item being compared with zero
2787 when given CC0. */
2789 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2790 x = arg1;
2792 /* If ARG1 is a comparison operator and CODE is testing for
2793 STORE_FLAG_VALUE, get the inner arguments. */
2795 else if (COMPARISON_P (arg1))
2797 #ifdef FLOAT_STORE_FLAG_VALUE
2798 REAL_VALUE_TYPE fsfv;
2799 #endif
2801 if (code == NE
2802 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2803 && code == LT && STORE_FLAG_VALUE == -1)
2804 #ifdef FLOAT_STORE_FLAG_VALUE
2805 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2806 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2807 REAL_VALUE_NEGATIVE (fsfv)))
2808 #endif
2810 x = arg1;
2811 else if (code == EQ
2812 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2813 && code == GE && STORE_FLAG_VALUE == -1)
2814 #ifdef FLOAT_STORE_FLAG_VALUE
2815 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2816 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2817 REAL_VALUE_NEGATIVE (fsfv)))
2818 #endif
2820 x = arg1, reverse_code = 1;
2823 /* ??? We could also check for
2825 (ne (and (eq (...) (const_int 1))) (const_int 0))
2827 and related forms, but let's wait until we see them occurring. */
2829 if (x == 0)
2830 /* Look up ARG1 in the hash table and see if it has an equivalence
2831 that lets us see what is being compared. */
2832 p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
2833 if (p)
2835 p = p->first_same_value;
2837 /* If what we compare is already known to be constant, that is as
2838 good as it gets.
2839 We need to break the loop in this case, because otherwise we
2840 can have an infinite loop when looking at a reg that is known
2841 to be a constant which is the same as a comparison of a reg
2842 against zero which appears later in the insn stream, which in
2843 turn is constant and the same as the comparison of the first reg
2844 against zero... */
2845 if (p->is_const)
2846 break;
2849 for (; p; p = p->next_same_value)
2851 enum machine_mode inner_mode = GET_MODE (p->exp);
2852 #ifdef FLOAT_STORE_FLAG_VALUE
2853 REAL_VALUE_TYPE fsfv;
2854 #endif
2856 /* If the entry isn't valid, skip it. */
2857 if (! exp_equiv_p (p->exp, p->exp, 1, false))
2858 continue;
2860 if (GET_CODE (p->exp) == COMPARE
2861 /* Another possibility is that this machine has a compare insn
2862 that includes the comparison code. In that case, ARG1 would
2863 be equivalent to a comparison operation that would set ARG1 to
2864 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2865 ORIG_CODE is the actual comparison being done; if it is an EQ,
2866 we must reverse ORIG_CODE. On machine with a negative value
2867 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2868 || ((code == NE
2869 || (code == LT
2870 && GET_MODE_CLASS (inner_mode) == MODE_INT
2871 && (GET_MODE_BITSIZE (inner_mode)
2872 <= HOST_BITS_PER_WIDE_INT)
2873 && (STORE_FLAG_VALUE
2874 & ((HOST_WIDE_INT) 1
2875 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2876 #ifdef FLOAT_STORE_FLAG_VALUE
2877 || (code == LT
2878 && SCALAR_FLOAT_MODE_P (inner_mode)
2879 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2880 REAL_VALUE_NEGATIVE (fsfv)))
2881 #endif
2883 && COMPARISON_P (p->exp)))
2885 x = p->exp;
2886 break;
2888 else if ((code == EQ
2889 || (code == GE
2890 && GET_MODE_CLASS (inner_mode) == MODE_INT
2891 && (GET_MODE_BITSIZE (inner_mode)
2892 <= HOST_BITS_PER_WIDE_INT)
2893 && (STORE_FLAG_VALUE
2894 & ((HOST_WIDE_INT) 1
2895 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2896 #ifdef FLOAT_STORE_FLAG_VALUE
2897 || (code == GE
2898 && SCALAR_FLOAT_MODE_P (inner_mode)
2899 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2900 REAL_VALUE_NEGATIVE (fsfv)))
2901 #endif
2903 && COMPARISON_P (p->exp))
2905 reverse_code = 1;
2906 x = p->exp;
2907 break;
2910 /* If this non-trapping address, e.g. fp + constant, the
2911 equivalent is a better operand since it may let us predict
2912 the value of the comparison. */
2913 else if (!rtx_addr_can_trap_p (p->exp))
2915 arg1 = p->exp;
2916 continue;
2920 /* If we didn't find a useful equivalence for ARG1, we are done.
2921 Otherwise, set up for the next iteration. */
2922 if (x == 0)
2923 break;
2925 /* If we need to reverse the comparison, make sure that that is
2926 possible -- we can't necessarily infer the value of GE from LT
2927 with floating-point operands. */
2928 if (reverse_code)
2930 enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
2931 if (reversed == UNKNOWN)
2932 break;
2933 else
2934 code = reversed;
2936 else if (COMPARISON_P (x))
2937 code = GET_CODE (x);
2938 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
2941 /* Return our results. Return the modes from before fold_rtx
2942 because fold_rtx might produce const_int, and then it's too late. */
2943 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
2944 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
2946 return code;
2949 /* If X is a nontrivial arithmetic operation on an argument for which
2950 a constant value can be determined, return the result of operating
2951 on that value, as a constant. Otherwise, return X, possibly with
2952 one or more operands changed to a forward-propagated constant.
2954 If X is a register whose contents are known, we do NOT return
2955 those contents here; equiv_constant is called to perform that task.
2956 For SUBREGs and MEMs, we do that both here and in equiv_constant.
2958 INSN is the insn that we may be modifying. If it is 0, make a copy
2959 of X before modifying it. */
2961 static rtx
2962 fold_rtx (rtx x, rtx insn)
2964 enum rtx_code code;
2965 enum machine_mode mode;
2966 const char *fmt;
2967 int i;
2968 rtx new = 0;
2969 int changed = 0;
2971 /* Operands of X. */
2972 rtx folded_arg0;
2973 rtx folded_arg1;
2975 /* Constant equivalents of first three operands of X;
2976 0 when no such equivalent is known. */
2977 rtx const_arg0;
2978 rtx const_arg1;
2979 rtx const_arg2;
2981 /* The mode of the first operand of X. We need this for sign and zero
2982 extends. */
2983 enum machine_mode mode_arg0;
2985 if (x == 0)
2986 return x;
2988 /* Try to perform some initial simplifications on X. */
2989 code = GET_CODE (x);
2990 switch (code)
2992 case MEM:
2993 case SUBREG:
2994 if ((new = equiv_constant (x)) != NULL_RTX)
2995 return new;
2996 return x;
2998 case CONST:
2999 case CONST_INT:
3000 case CONST_DOUBLE:
3001 case CONST_VECTOR:
3002 case SYMBOL_REF:
3003 case LABEL_REF:
3004 case REG:
3005 case PC:
3006 /* No use simplifying an EXPR_LIST
3007 since they are used only for lists of args
3008 in a function call's REG_EQUAL note. */
3009 case EXPR_LIST:
3010 return x;
3012 #ifdef HAVE_cc0
3013 case CC0:
3014 return prev_insn_cc0;
3015 #endif
3017 case ASM_OPERANDS:
3018 if (insn)
3020 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3021 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3022 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3024 return x;
3026 #ifdef NO_FUNCTION_CSE
3027 case CALL:
3028 if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3029 return x;
3030 break;
3031 #endif
3033 /* Anything else goes through the loop below. */
3034 default:
3035 break;
3038 mode = GET_MODE (x);
3039 const_arg0 = 0;
3040 const_arg1 = 0;
3041 const_arg2 = 0;
3042 mode_arg0 = VOIDmode;
3044 /* Try folding our operands.
3045 Then see which ones have constant values known. */
3047 fmt = GET_RTX_FORMAT (code);
3048 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3049 if (fmt[i] == 'e')
3051 rtx folded_arg = XEXP (x, i), const_arg;
3052 enum machine_mode mode_arg = GET_MODE (folded_arg);
3053 #ifdef HAVE_cc0
3054 if (CC0_P (folded_arg))
3055 folded_arg = prev_insn_cc0, mode_arg = prev_insn_cc0_mode;
3056 #endif
3057 const_arg = equiv_constant (folded_arg);
3059 /* For the first three operands, see if the operand
3060 is constant or equivalent to a constant. */
3061 switch (i)
3063 case 0:
3064 folded_arg0 = folded_arg;
3065 const_arg0 = const_arg;
3066 mode_arg0 = mode_arg;
3067 break;
3068 case 1:
3069 folded_arg1 = folded_arg;
3070 const_arg1 = const_arg;
3071 break;
3072 case 2:
3073 const_arg2 = const_arg;
3074 break;
3077 /* Pick the least expensive of the argument and an equivalent constant
3078 argument. */
3079 if (const_arg != 0
3080 && const_arg != folded_arg
3081 && COST_IN (const_arg, code) <= COST_IN (folded_arg, code)
3083 /* It's not safe to substitute the operand of a conversion
3084 operator with a constant, as the conversion's identity
3085 depends upon the mode of its operand. This optimization
3086 is handled by the call to simplify_unary_operation. */
3087 && (GET_RTX_CLASS (code) != RTX_UNARY
3088 || GET_MODE (const_arg) == mode_arg0
3089 || (code != ZERO_EXTEND
3090 && code != SIGN_EXTEND
3091 && code != TRUNCATE
3092 && code != FLOAT_TRUNCATE
3093 && code != FLOAT_EXTEND
3094 && code != FLOAT
3095 && code != FIX
3096 && code != UNSIGNED_FLOAT
3097 && code != UNSIGNED_FIX)))
3098 folded_arg = const_arg;
3100 if (folded_arg == XEXP (x, i))
3101 continue;
3103 if (insn == NULL_RTX && !changed)
3104 x = copy_rtx (x);
3105 changed = 1;
3106 validate_change (insn, &XEXP (x, i), folded_arg, 1);
3109 if (changed)
3111 /* Canonicalize X if necessary, and keep const_argN and folded_argN
3112 consistent with the order in X. */
3113 if (canonicalize_change_group (insn, x))
3115 rtx tem;
3116 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3117 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3120 apply_change_group ();
3123 /* If X is an arithmetic operation, see if we can simplify it. */
3125 switch (GET_RTX_CLASS (code))
3127 case RTX_UNARY:
3129 int is_const = 0;
3131 /* We can't simplify extension ops unless we know the
3132 original mode. */
3133 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3134 && mode_arg0 == VOIDmode)
3135 break;
3137 /* If we had a CONST, strip it off and put it back later if we
3138 fold. */
3139 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3140 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3142 new = simplify_unary_operation (code, mode,
3143 const_arg0 ? const_arg0 : folded_arg0,
3144 mode_arg0);
3145 /* NEG of PLUS could be converted into MINUS, but that causes
3146 expressions of the form
3147 (CONST (MINUS (CONST_INT) (SYMBOL_REF)))
3148 which many ports mistakenly treat as LEGITIMATE_CONSTANT_P.
3149 FIXME: those ports should be fixed. */
3150 if (new != 0 && is_const
3151 && GET_CODE (new) == PLUS
3152 && (GET_CODE (XEXP (new, 0)) == SYMBOL_REF
3153 || GET_CODE (XEXP (new, 0)) == LABEL_REF)
3154 && GET_CODE (XEXP (new, 1)) == CONST_INT)
3155 new = gen_rtx_CONST (mode, new);
3157 break;
3159 case RTX_COMPARE:
3160 case RTX_COMM_COMPARE:
3161 /* See what items are actually being compared and set FOLDED_ARG[01]
3162 to those values and CODE to the actual comparison code. If any are
3163 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3164 do anything if both operands are already known to be constant. */
3166 /* ??? Vector mode comparisons are not supported yet. */
3167 if (VECTOR_MODE_P (mode))
3168 break;
3170 if (const_arg0 == 0 || const_arg1 == 0)
3172 struct table_elt *p0, *p1;
3173 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3174 enum machine_mode mode_arg1;
3176 #ifdef FLOAT_STORE_FLAG_VALUE
3177 if (SCALAR_FLOAT_MODE_P (mode))
3179 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3180 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3181 false_rtx = CONST0_RTX (mode);
3183 #endif
3185 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3186 &mode_arg0, &mode_arg1);
3188 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3189 what kinds of things are being compared, so we can't do
3190 anything with this comparison. */
3192 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3193 break;
3195 const_arg0 = equiv_constant (folded_arg0);
3196 const_arg1 = equiv_constant (folded_arg1);
3198 /* If we do not now have two constants being compared, see
3199 if we can nevertheless deduce some things about the
3200 comparison. */
3201 if (const_arg0 == 0 || const_arg1 == 0)
3203 if (const_arg1 != NULL)
3205 rtx cheapest_simplification;
3206 int cheapest_cost;
3207 rtx simp_result;
3208 struct table_elt *p;
3210 /* See if we can find an equivalent of folded_arg0
3211 that gets us a cheaper expression, possibly a
3212 constant through simplifications. */
3213 p = lookup (folded_arg0, SAFE_HASH (folded_arg0, mode_arg0),
3214 mode_arg0);
3216 if (p != NULL)
3218 cheapest_simplification = x;
3219 cheapest_cost = COST (x);
3221 for (p = p->first_same_value; p != NULL; p = p->next_same_value)
3223 int cost;
3225 /* If the entry isn't valid, skip it. */
3226 if (! exp_equiv_p (p->exp, p->exp, 1, false))
3227 continue;
3229 /* Try to simplify using this equivalence. */
3230 simp_result
3231 = simplify_relational_operation (code, mode,
3232 mode_arg0,
3233 p->exp,
3234 const_arg1);
3236 if (simp_result == NULL)
3237 continue;
3239 cost = COST (simp_result);
3240 if (cost < cheapest_cost)
3242 cheapest_cost = cost;
3243 cheapest_simplification = simp_result;
3247 /* If we have a cheaper expression now, use that
3248 and try folding it further, from the top. */
3249 if (cheapest_simplification != x)
3250 return fold_rtx (cheapest_simplification, insn);
3254 /* Some addresses are known to be nonzero. We don't know
3255 their sign, but equality comparisons are known. */
3256 if (const_arg1 == const0_rtx
3257 && nonzero_address_p (folded_arg0))
3259 if (code == EQ)
3260 return false_rtx;
3261 else if (code == NE)
3262 return true_rtx;
3265 /* See if the two operands are the same. */
3267 if (folded_arg0 == folded_arg1
3268 || (REG_P (folded_arg0)
3269 && REG_P (folded_arg1)
3270 && (REG_QTY (REGNO (folded_arg0))
3271 == REG_QTY (REGNO (folded_arg1))))
3272 || ((p0 = lookup (folded_arg0,
3273 SAFE_HASH (folded_arg0, mode_arg0),
3274 mode_arg0))
3275 && (p1 = lookup (folded_arg1,
3276 SAFE_HASH (folded_arg1, mode_arg0),
3277 mode_arg0))
3278 && p0->first_same_value == p1->first_same_value))
3280 /* Sadly two equal NaNs are not equivalent. */
3281 if (!HONOR_NANS (mode_arg0))
3282 return ((code == EQ || code == LE || code == GE
3283 || code == LEU || code == GEU || code == UNEQ
3284 || code == UNLE || code == UNGE
3285 || code == ORDERED)
3286 ? true_rtx : false_rtx);
3287 /* Take care for the FP compares we can resolve. */
3288 if (code == UNEQ || code == UNLE || code == UNGE)
3289 return true_rtx;
3290 if (code == LTGT || code == LT || code == GT)
3291 return false_rtx;
3294 /* If FOLDED_ARG0 is a register, see if the comparison we are
3295 doing now is either the same as we did before or the reverse
3296 (we only check the reverse if not floating-point). */
3297 else if (REG_P (folded_arg0))
3299 int qty = REG_QTY (REGNO (folded_arg0));
3301 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3303 struct qty_table_elem *ent = &qty_table[qty];
3305 if ((comparison_dominates_p (ent->comparison_code, code)
3306 || (! FLOAT_MODE_P (mode_arg0)
3307 && comparison_dominates_p (ent->comparison_code,
3308 reverse_condition (code))))
3309 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3310 || (const_arg1
3311 && rtx_equal_p (ent->comparison_const,
3312 const_arg1))
3313 || (REG_P (folded_arg1)
3314 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3315 return (comparison_dominates_p (ent->comparison_code, code)
3316 ? true_rtx : false_rtx);
3322 /* If we are comparing against zero, see if the first operand is
3323 equivalent to an IOR with a constant. If so, we may be able to
3324 determine the result of this comparison. */
3326 if (const_arg1 == const0_rtx)
3328 rtx y = lookup_as_function (folded_arg0, IOR);
3329 rtx inner_const;
3331 if (y != 0
3332 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3333 && GET_CODE (inner_const) == CONST_INT
3334 && INTVAL (inner_const) != 0)
3336 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
3337 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
3338 && (INTVAL (inner_const)
3339 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
3340 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3342 #ifdef FLOAT_STORE_FLAG_VALUE
3343 if (SCALAR_FLOAT_MODE_P (mode))
3345 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3346 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3347 false_rtx = CONST0_RTX (mode);
3349 #endif
3351 switch (code)
3353 case EQ:
3354 return false_rtx;
3355 case NE:
3356 return true_rtx;
3357 case LT: case LE:
3358 if (has_sign)
3359 return true_rtx;
3360 break;
3361 case GT: case GE:
3362 if (has_sign)
3363 return false_rtx;
3364 break;
3365 default:
3366 break;
3372 rtx op0 = const_arg0 ? const_arg0 : folded_arg0;
3373 rtx op1 = const_arg1 ? const_arg1 : folded_arg1;
3374 new = simplify_relational_operation (code, mode, mode_arg0, op0, op1);
3376 break;
3378 case RTX_BIN_ARITH:
3379 case RTX_COMM_ARITH:
3380 switch (code)
3382 case PLUS:
3383 /* If the second operand is a LABEL_REF, see if the first is a MINUS
3384 with that LABEL_REF as its second operand. If so, the result is
3385 the first operand of that MINUS. This handles switches with an
3386 ADDR_DIFF_VEC table. */
3387 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
3389 rtx y
3390 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
3391 : lookup_as_function (folded_arg0, MINUS);
3393 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3394 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
3395 return XEXP (y, 0);
3397 /* Now try for a CONST of a MINUS like the above. */
3398 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
3399 : lookup_as_function (folded_arg0, CONST))) != 0
3400 && GET_CODE (XEXP (y, 0)) == MINUS
3401 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3402 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
3403 return XEXP (XEXP (y, 0), 0);
3406 /* Likewise if the operands are in the other order. */
3407 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
3409 rtx y
3410 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
3411 : lookup_as_function (folded_arg1, MINUS);
3413 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3414 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
3415 return XEXP (y, 0);
3417 /* Now try for a CONST of a MINUS like the above. */
3418 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
3419 : lookup_as_function (folded_arg1, CONST))) != 0
3420 && GET_CODE (XEXP (y, 0)) == MINUS
3421 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3422 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
3423 return XEXP (XEXP (y, 0), 0);
3426 /* If second operand is a register equivalent to a negative
3427 CONST_INT, see if we can find a register equivalent to the
3428 positive constant. Make a MINUS if so. Don't do this for
3429 a non-negative constant since we might then alternate between
3430 choosing positive and negative constants. Having the positive
3431 constant previously-used is the more common case. Be sure
3432 the resulting constant is non-negative; if const_arg1 were
3433 the smallest negative number this would overflow: depending
3434 on the mode, this would either just be the same value (and
3435 hence not save anything) or be incorrect. */
3436 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
3437 && INTVAL (const_arg1) < 0
3438 /* This used to test
3440 -INTVAL (const_arg1) >= 0
3442 But The Sun V5.0 compilers mis-compiled that test. So
3443 instead we test for the problematic value in a more direct
3444 manner and hope the Sun compilers get it correct. */
3445 && INTVAL (const_arg1) !=
3446 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
3447 && REG_P (folded_arg1))
3449 rtx new_const = GEN_INT (-INTVAL (const_arg1));
3450 struct table_elt *p
3451 = lookup (new_const, SAFE_HASH (new_const, mode), mode);
3453 if (p)
3454 for (p = p->first_same_value; p; p = p->next_same_value)
3455 if (REG_P (p->exp))
3456 return simplify_gen_binary (MINUS, mode, folded_arg0,
3457 canon_reg (p->exp, NULL_RTX));
3459 goto from_plus;
3461 case MINUS:
3462 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3463 If so, produce (PLUS Z C2-C). */
3464 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
3466 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
3467 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
3468 return fold_rtx (plus_constant (copy_rtx (y),
3469 -INTVAL (const_arg1)),
3470 NULL_RTX);
3473 /* Fall through. */
3475 from_plus:
3476 case SMIN: case SMAX: case UMIN: case UMAX:
3477 case IOR: case AND: case XOR:
3478 case MULT:
3479 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
3480 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3481 is known to be of similar form, we may be able to replace the
3482 operation with a combined operation. This may eliminate the
3483 intermediate operation if every use is simplified in this way.
3484 Note that the similar optimization done by combine.c only works
3485 if the intermediate operation's result has only one reference. */
3487 if (REG_P (folded_arg0)
3488 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
3490 int is_shift
3491 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
3492 rtx y, inner_const, new_const;
3493 enum rtx_code associate_code;
3495 if (is_shift
3496 && (INTVAL (const_arg1) >= GET_MODE_BITSIZE (mode)
3497 || INTVAL (const_arg1) < 0))
3499 if (SHIFT_COUNT_TRUNCATED)
3500 const_arg1 = GEN_INT (INTVAL (const_arg1)
3501 & (GET_MODE_BITSIZE (mode) - 1));
3502 else
3503 break;
3506 y = lookup_as_function (folded_arg0, code);
3507 if (y == 0)
3508 break;
3510 /* If we have compiled a statement like
3511 "if (x == (x & mask1))", and now are looking at
3512 "x & mask2", we will have a case where the first operand
3513 of Y is the same as our first operand. Unless we detect
3514 this case, an infinite loop will result. */
3515 if (XEXP (y, 0) == folded_arg0)
3516 break;
3518 inner_const = equiv_constant (fold_rtx (XEXP (y, 1), 0));
3519 if (!inner_const || GET_CODE (inner_const) != CONST_INT)
3520 break;
3522 /* Don't associate these operations if they are a PLUS with the
3523 same constant and it is a power of two. These might be doable
3524 with a pre- or post-increment. Similarly for two subtracts of
3525 identical powers of two with post decrement. */
3527 if (code == PLUS && const_arg1 == inner_const
3528 && ((HAVE_PRE_INCREMENT
3529 && exact_log2 (INTVAL (const_arg1)) >= 0)
3530 || (HAVE_POST_INCREMENT
3531 && exact_log2 (INTVAL (const_arg1)) >= 0)
3532 || (HAVE_PRE_DECREMENT
3533 && exact_log2 (- INTVAL (const_arg1)) >= 0)
3534 || (HAVE_POST_DECREMENT
3535 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
3536 break;
3538 if (is_shift
3539 && (INTVAL (inner_const) >= GET_MODE_BITSIZE (mode)
3540 || INTVAL (inner_const) < 0))
3542 if (SHIFT_COUNT_TRUNCATED)
3543 inner_const = GEN_INT (INTVAL (inner_const)
3544 & (GET_MODE_BITSIZE (mode) - 1));
3545 else
3546 break;
3549 /* Compute the code used to compose the constants. For example,
3550 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
3552 associate_code = (is_shift || code == MINUS ? PLUS : code);
3554 new_const = simplify_binary_operation (associate_code, mode,
3555 const_arg1, inner_const);
3557 if (new_const == 0)
3558 break;
3560 /* If we are associating shift operations, don't let this
3561 produce a shift of the size of the object or larger.
3562 This could occur when we follow a sign-extend by a right
3563 shift on a machine that does a sign-extend as a pair
3564 of shifts. */
3566 if (is_shift
3567 && GET_CODE (new_const) == CONST_INT
3568 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
3570 /* As an exception, we can turn an ASHIFTRT of this
3571 form into a shift of the number of bits - 1. */
3572 if (code == ASHIFTRT)
3573 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
3574 else if (!side_effects_p (XEXP (y, 0)))
3575 return CONST0_RTX (mode);
3576 else
3577 break;
3580 y = copy_rtx (XEXP (y, 0));
3582 /* If Y contains our first operand (the most common way this
3583 can happen is if Y is a MEM), we would do into an infinite
3584 loop if we tried to fold it. So don't in that case. */
3586 if (! reg_mentioned_p (folded_arg0, y))
3587 y = fold_rtx (y, insn);
3589 return simplify_gen_binary (code, mode, y, new_const);
3591 break;
3593 case DIV: case UDIV:
3594 /* ??? The associative optimization performed immediately above is
3595 also possible for DIV and UDIV using associate_code of MULT.
3596 However, we would need extra code to verify that the
3597 multiplication does not overflow, that is, there is no overflow
3598 in the calculation of new_const. */
3599 break;
3601 default:
3602 break;
3605 new = simplify_binary_operation (code, mode,
3606 const_arg0 ? const_arg0 : folded_arg0,
3607 const_arg1 ? const_arg1 : folded_arg1);
3608 break;
3610 case RTX_OBJ:
3611 /* (lo_sum (high X) X) is simply X. */
3612 if (code == LO_SUM && const_arg0 != 0
3613 && GET_CODE (const_arg0) == HIGH
3614 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
3615 return const_arg1;
3616 break;
3618 case RTX_TERNARY:
3619 case RTX_BITFIELD_OPS:
3620 new = simplify_ternary_operation (code, mode, mode_arg0,
3621 const_arg0 ? const_arg0 : folded_arg0,
3622 const_arg1 ? const_arg1 : folded_arg1,
3623 const_arg2 ? const_arg2 : XEXP (x, 2));
3624 break;
3626 default:
3627 break;
3630 return new ? new : x;
3633 /* Return a constant value currently equivalent to X.
3634 Return 0 if we don't know one. */
3636 static rtx
3637 equiv_constant (rtx x)
3639 if (REG_P (x)
3640 && REGNO_QTY_VALID_P (REGNO (x)))
3642 int x_q = REG_QTY (REGNO (x));
3643 struct qty_table_elem *x_ent = &qty_table[x_q];
3645 if (x_ent->const_rtx)
3646 x = gen_lowpart (GET_MODE (x), x_ent->const_rtx);
3649 if (x == 0 || CONSTANT_P (x))
3650 return x;
3652 if (GET_CODE (x) == SUBREG)
3654 rtx new;
3656 /* See if we previously assigned a constant value to this SUBREG. */
3657 if ((new = lookup_as_function (x, CONST_INT)) != 0
3658 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3659 return new;
3661 if (REG_P (SUBREG_REG (x))
3662 && (new = equiv_constant (SUBREG_REG (x))) != 0)
3663 return simplify_subreg (GET_MODE (x), SUBREG_REG (x),
3664 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3666 return 0;
3669 /* If X is a MEM, see if it is a constant-pool reference, or look it up in
3670 the hash table in case its value was seen before. */
3672 if (MEM_P (x))
3674 struct table_elt *elt;
3676 x = avoid_constant_pool_reference (x);
3677 if (CONSTANT_P (x))
3678 return x;
3680 elt = lookup (x, SAFE_HASH (x, GET_MODE (x)), GET_MODE (x));
3681 if (elt == 0)
3682 return 0;
3684 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3685 if (elt->is_const && CONSTANT_P (elt->exp))
3686 return elt->exp;
3689 return 0;
3692 /* Given INSN, a jump insn, TAKEN indicates if we are following the
3693 "taken" branch.
3695 In certain cases, this can cause us to add an equivalence. For example,
3696 if we are following the taken case of
3697 if (i == 2)
3698 we can add the fact that `i' and '2' are now equivalent.
3700 In any case, we can record that this comparison was passed. If the same
3701 comparison is seen later, we will know its value. */
3703 static void
3704 record_jump_equiv (rtx insn, bool taken)
3706 int cond_known_true;
3707 rtx op0, op1;
3708 rtx set;
3709 enum machine_mode mode, mode0, mode1;
3710 int reversed_nonequality = 0;
3711 enum rtx_code code;
3713 /* Ensure this is the right kind of insn. */
3714 gcc_assert (any_condjump_p (insn));
3716 set = pc_set (insn);
3718 /* See if this jump condition is known true or false. */
3719 if (taken)
3720 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
3721 else
3722 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
3724 /* Get the type of comparison being done and the operands being compared.
3725 If we had to reverse a non-equality condition, record that fact so we
3726 know that it isn't valid for floating-point. */
3727 code = GET_CODE (XEXP (SET_SRC (set), 0));
3728 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
3729 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
3731 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
3732 if (! cond_known_true)
3734 code = reversed_comparison_code_parts (code, op0, op1, insn);
3736 /* Don't remember if we can't find the inverse. */
3737 if (code == UNKNOWN)
3738 return;
3741 /* The mode is the mode of the non-constant. */
3742 mode = mode0;
3743 if (mode1 != VOIDmode)
3744 mode = mode1;
3746 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
3749 /* Yet another form of subreg creation. In this case, we want something in
3750 MODE, and we should assume OP has MODE iff it is naturally modeless. */
3752 static rtx
3753 record_jump_cond_subreg (enum machine_mode mode, rtx op)
3755 enum machine_mode op_mode = GET_MODE (op);
3756 if (op_mode == mode || op_mode == VOIDmode)
3757 return op;
3758 return lowpart_subreg (mode, op, op_mode);
3761 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
3762 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
3763 Make any useful entries we can with that information. Called from
3764 above function and called recursively. */
3766 static void
3767 record_jump_cond (enum rtx_code code, enum machine_mode mode, rtx op0,
3768 rtx op1, int reversed_nonequality)
3770 unsigned op0_hash, op1_hash;
3771 int op0_in_memory, op1_in_memory;
3772 struct table_elt *op0_elt, *op1_elt;
3774 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
3775 we know that they are also equal in the smaller mode (this is also
3776 true for all smaller modes whether or not there is a SUBREG, but
3777 is not worth testing for with no SUBREG). */
3779 /* Note that GET_MODE (op0) may not equal MODE. */
3780 if (code == EQ && GET_CODE (op0) == SUBREG
3781 && (GET_MODE_SIZE (GET_MODE (op0))
3782 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3784 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3785 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3786 if (tem)
3787 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3788 reversed_nonequality);
3791 if (code == EQ && GET_CODE (op1) == SUBREG
3792 && (GET_MODE_SIZE (GET_MODE (op1))
3793 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3795 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3796 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3797 if (tem)
3798 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3799 reversed_nonequality);
3802 /* Similarly, if this is an NE comparison, and either is a SUBREG
3803 making a smaller mode, we know the whole thing is also NE. */
3805 /* Note that GET_MODE (op0) may not equal MODE;
3806 if we test MODE instead, we can get an infinite recursion
3807 alternating between two modes each wider than MODE. */
3809 if (code == NE && GET_CODE (op0) == SUBREG
3810 && subreg_lowpart_p (op0)
3811 && (GET_MODE_SIZE (GET_MODE (op0))
3812 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3814 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3815 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3816 if (tem)
3817 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3818 reversed_nonequality);
3821 if (code == NE && GET_CODE (op1) == SUBREG
3822 && subreg_lowpart_p (op1)
3823 && (GET_MODE_SIZE (GET_MODE (op1))
3824 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3826 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3827 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3828 if (tem)
3829 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3830 reversed_nonequality);
3833 /* Hash both operands. */
3835 do_not_record = 0;
3836 hash_arg_in_memory = 0;
3837 op0_hash = HASH (op0, mode);
3838 op0_in_memory = hash_arg_in_memory;
3840 if (do_not_record)
3841 return;
3843 do_not_record = 0;
3844 hash_arg_in_memory = 0;
3845 op1_hash = HASH (op1, mode);
3846 op1_in_memory = hash_arg_in_memory;
3848 if (do_not_record)
3849 return;
3851 /* Look up both operands. */
3852 op0_elt = lookup (op0, op0_hash, mode);
3853 op1_elt = lookup (op1, op1_hash, mode);
3855 /* If both operands are already equivalent or if they are not in the
3856 table but are identical, do nothing. */
3857 if ((op0_elt != 0 && op1_elt != 0
3858 && op0_elt->first_same_value == op1_elt->first_same_value)
3859 || op0 == op1 || rtx_equal_p (op0, op1))
3860 return;
3862 /* If we aren't setting two things equal all we can do is save this
3863 comparison. Similarly if this is floating-point. In the latter
3864 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
3865 If we record the equality, we might inadvertently delete code
3866 whose intent was to change -0 to +0. */
3868 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
3870 struct qty_table_elem *ent;
3871 int qty;
3873 /* If we reversed a floating-point comparison, if OP0 is not a
3874 register, or if OP1 is neither a register or constant, we can't
3875 do anything. */
3877 if (!REG_P (op1))
3878 op1 = equiv_constant (op1);
3880 if ((reversed_nonequality && FLOAT_MODE_P (mode))
3881 || !REG_P (op0) || op1 == 0)
3882 return;
3884 /* Put OP0 in the hash table if it isn't already. This gives it a
3885 new quantity number. */
3886 if (op0_elt == 0)
3888 if (insert_regs (op0, NULL, 0))
3890 rehash_using_reg (op0);
3891 op0_hash = HASH (op0, mode);
3893 /* If OP0 is contained in OP1, this changes its hash code
3894 as well. Faster to rehash than to check, except
3895 for the simple case of a constant. */
3896 if (! CONSTANT_P (op1))
3897 op1_hash = HASH (op1,mode);
3900 op0_elt = insert (op0, NULL, op0_hash, mode);
3901 op0_elt->in_memory = op0_in_memory;
3904 qty = REG_QTY (REGNO (op0));
3905 ent = &qty_table[qty];
3907 ent->comparison_code = code;
3908 if (REG_P (op1))
3910 /* Look it up again--in case op0 and op1 are the same. */
3911 op1_elt = lookup (op1, op1_hash, mode);
3913 /* Put OP1 in the hash table so it gets a new quantity number. */
3914 if (op1_elt == 0)
3916 if (insert_regs (op1, NULL, 0))
3918 rehash_using_reg (op1);
3919 op1_hash = HASH (op1, mode);
3922 op1_elt = insert (op1, NULL, op1_hash, mode);
3923 op1_elt->in_memory = op1_in_memory;
3926 ent->comparison_const = NULL_RTX;
3927 ent->comparison_qty = REG_QTY (REGNO (op1));
3929 else
3931 ent->comparison_const = op1;
3932 ent->comparison_qty = -1;
3935 return;
3938 /* If either side is still missing an equivalence, make it now,
3939 then merge the equivalences. */
3941 if (op0_elt == 0)
3943 if (insert_regs (op0, NULL, 0))
3945 rehash_using_reg (op0);
3946 op0_hash = HASH (op0, mode);
3949 op0_elt = insert (op0, NULL, op0_hash, mode);
3950 op0_elt->in_memory = op0_in_memory;
3953 if (op1_elt == 0)
3955 if (insert_regs (op1, NULL, 0))
3957 rehash_using_reg (op1);
3958 op1_hash = HASH (op1, mode);
3961 op1_elt = insert (op1, NULL, op1_hash, mode);
3962 op1_elt->in_memory = op1_in_memory;
3965 merge_equiv_classes (op0_elt, op1_elt);
3968 /* CSE processing for one instruction.
3969 First simplify sources and addresses of all assignments
3970 in the instruction, using previously-computed equivalents values.
3971 Then install the new sources and destinations in the table
3972 of available values.
3974 If LIBCALL_INSN is nonzero, don't record any equivalence made in
3975 the insn. It means that INSN is inside libcall block. In this
3976 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
3978 /* Data on one SET contained in the instruction. */
3980 struct set
3982 /* The SET rtx itself. */
3983 rtx rtl;
3984 /* The SET_SRC of the rtx (the original value, if it is changing). */
3985 rtx src;
3986 /* The hash-table element for the SET_SRC of the SET. */
3987 struct table_elt *src_elt;
3988 /* Hash value for the SET_SRC. */
3989 unsigned src_hash;
3990 /* Hash value for the SET_DEST. */
3991 unsigned dest_hash;
3992 /* The SET_DEST, with SUBREG, etc., stripped. */
3993 rtx inner_dest;
3994 /* Nonzero if the SET_SRC is in memory. */
3995 char src_in_memory;
3996 /* Nonzero if the SET_SRC contains something
3997 whose value cannot be predicted and understood. */
3998 char src_volatile;
3999 /* Original machine mode, in case it becomes a CONST_INT.
4000 The size of this field should match the size of the mode
4001 field of struct rtx_def (see rtl.h). */
4002 ENUM_BITFIELD(machine_mode) mode : 8;
4003 /* A constant equivalent for SET_SRC, if any. */
4004 rtx src_const;
4005 /* Original SET_SRC value used for libcall notes. */
4006 rtx orig_src;
4007 /* Hash value of constant equivalent for SET_SRC. */
4008 unsigned src_const_hash;
4009 /* Table entry for constant equivalent for SET_SRC, if any. */
4010 struct table_elt *src_const_elt;
4011 /* Table entry for the destination address. */
4012 struct table_elt *dest_addr_elt;
4015 static void
4016 cse_insn (rtx insn, rtx libcall_insn)
4018 rtx x = PATTERN (insn);
4019 int i;
4020 rtx tem;
4021 int n_sets = 0;
4023 #ifdef HAVE_cc0
4024 /* Records what this insn does to set CC0. */
4025 rtx this_insn_cc0 = 0;
4026 enum machine_mode this_insn_cc0_mode = VOIDmode;
4027 #endif
4029 rtx src_eqv = 0;
4030 struct table_elt *src_eqv_elt = 0;
4031 int src_eqv_volatile = 0;
4032 int src_eqv_in_memory = 0;
4033 unsigned src_eqv_hash = 0;
4035 struct set *sets = (struct set *) 0;
4037 this_insn = insn;
4039 /* Find all the SETs and CLOBBERs in this instruction.
4040 Record all the SETs in the array `set' and count them.
4041 Also determine whether there is a CLOBBER that invalidates
4042 all memory references, or all references at varying addresses. */
4044 if (CALL_P (insn))
4046 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4048 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4049 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4050 XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4054 if (GET_CODE (x) == SET)
4056 sets = alloca (sizeof (struct set));
4057 sets[0].rtl = x;
4059 /* Ignore SETs that are unconditional jumps.
4060 They never need cse processing, so this does not hurt.
4061 The reason is not efficiency but rather
4062 so that we can test at the end for instructions
4063 that have been simplified to unconditional jumps
4064 and not be misled by unchanged instructions
4065 that were unconditional jumps to begin with. */
4066 if (SET_DEST (x) == pc_rtx
4067 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4070 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4071 The hard function value register is used only once, to copy to
4072 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4073 Ensure we invalidate the destination register. On the 80386 no
4074 other code would invalidate it since it is a fixed_reg.
4075 We need not check the return of apply_change_group; see canon_reg. */
4077 else if (GET_CODE (SET_SRC (x)) == CALL)
4079 canon_reg (SET_SRC (x), insn);
4080 apply_change_group ();
4081 fold_rtx (SET_SRC (x), insn);
4082 invalidate (SET_DEST (x), VOIDmode);
4084 else
4085 n_sets = 1;
4087 else if (GET_CODE (x) == PARALLEL)
4089 int lim = XVECLEN (x, 0);
4091 sets = alloca (lim * sizeof (struct set));
4093 /* Find all regs explicitly clobbered in this insn,
4094 and ensure they are not replaced with any other regs
4095 elsewhere in this insn.
4096 When a reg that is clobbered is also used for input,
4097 we should presume that that is for a reason,
4098 and we should not substitute some other register
4099 which is not supposed to be clobbered.
4100 Therefore, this loop cannot be merged into the one below
4101 because a CALL may precede a CLOBBER and refer to the
4102 value clobbered. We must not let a canonicalization do
4103 anything in that case. */
4104 for (i = 0; i < lim; i++)
4106 rtx y = XVECEXP (x, 0, i);
4107 if (GET_CODE (y) == CLOBBER)
4109 rtx clobbered = XEXP (y, 0);
4111 if (REG_P (clobbered)
4112 || GET_CODE (clobbered) == SUBREG)
4113 invalidate (clobbered, VOIDmode);
4114 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4115 || GET_CODE (clobbered) == ZERO_EXTRACT)
4116 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4120 for (i = 0; i < lim; i++)
4122 rtx y = XVECEXP (x, 0, i);
4123 if (GET_CODE (y) == SET)
4125 /* As above, we ignore unconditional jumps and call-insns and
4126 ignore the result of apply_change_group. */
4127 if (GET_CODE (SET_SRC (y)) == CALL)
4129 canon_reg (SET_SRC (y), insn);
4130 apply_change_group ();
4131 fold_rtx (SET_SRC (y), insn);
4132 invalidate (SET_DEST (y), VOIDmode);
4134 else if (SET_DEST (y) == pc_rtx
4135 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4137 else
4138 sets[n_sets++].rtl = y;
4140 else if (GET_CODE (y) == CLOBBER)
4142 /* If we clobber memory, canon the address.
4143 This does nothing when a register is clobbered
4144 because we have already invalidated the reg. */
4145 if (MEM_P (XEXP (y, 0)))
4146 canon_reg (XEXP (y, 0), NULL_RTX);
4148 else if (GET_CODE (y) == USE
4149 && ! (REG_P (XEXP (y, 0))
4150 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4151 canon_reg (y, NULL_RTX);
4152 else if (GET_CODE (y) == CALL)
4154 /* The result of apply_change_group can be ignored; see
4155 canon_reg. */
4156 canon_reg (y, insn);
4157 apply_change_group ();
4158 fold_rtx (y, insn);
4162 else if (GET_CODE (x) == CLOBBER)
4164 if (MEM_P (XEXP (x, 0)))
4165 canon_reg (XEXP (x, 0), NULL_RTX);
4168 /* Canonicalize a USE of a pseudo register or memory location. */
4169 else if (GET_CODE (x) == USE
4170 && ! (REG_P (XEXP (x, 0))
4171 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4172 canon_reg (XEXP (x, 0), NULL_RTX);
4173 else if (GET_CODE (x) == CALL)
4175 /* The result of apply_change_group can be ignored; see canon_reg. */
4176 canon_reg (x, insn);
4177 apply_change_group ();
4178 fold_rtx (x, insn);
4181 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4182 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4183 is handled specially for this case, and if it isn't set, then there will
4184 be no equivalence for the destination. */
4185 if (n_sets == 1 && REG_NOTES (insn) != 0
4186 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4187 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4188 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4190 src_eqv = fold_rtx (canon_reg (XEXP (tem, 0), NULL_RTX), insn);
4191 XEXP (tem, 0) = src_eqv;
4194 /* Canonicalize sources and addresses of destinations.
4195 We do this in a separate pass to avoid problems when a MATCH_DUP is
4196 present in the insn pattern. In that case, we want to ensure that
4197 we don't break the duplicate nature of the pattern. So we will replace
4198 both operands at the same time. Otherwise, we would fail to find an
4199 equivalent substitution in the loop calling validate_change below.
4201 We used to suppress canonicalization of DEST if it appears in SRC,
4202 but we don't do this any more. */
4204 for (i = 0; i < n_sets; i++)
4206 rtx dest = SET_DEST (sets[i].rtl);
4207 rtx src = SET_SRC (sets[i].rtl);
4208 rtx new = canon_reg (src, insn);
4210 sets[i].orig_src = src;
4211 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4213 if (GET_CODE (dest) == ZERO_EXTRACT)
4215 validate_change (insn, &XEXP (dest, 1),
4216 canon_reg (XEXP (dest, 1), insn), 1);
4217 validate_change (insn, &XEXP (dest, 2),
4218 canon_reg (XEXP (dest, 2), insn), 1);
4221 while (GET_CODE (dest) == SUBREG
4222 || GET_CODE (dest) == ZERO_EXTRACT
4223 || GET_CODE (dest) == STRICT_LOW_PART)
4224 dest = XEXP (dest, 0);
4226 if (MEM_P (dest))
4227 canon_reg (dest, insn);
4230 /* Now that we have done all the replacements, we can apply the change
4231 group and see if they all work. Note that this will cause some
4232 canonicalizations that would have worked individually not to be applied
4233 because some other canonicalization didn't work, but this should not
4234 occur often.
4236 The result of apply_change_group can be ignored; see canon_reg. */
4238 apply_change_group ();
4240 /* Set sets[i].src_elt to the class each source belongs to.
4241 Detect assignments from or to volatile things
4242 and set set[i] to zero so they will be ignored
4243 in the rest of this function.
4245 Nothing in this loop changes the hash table or the register chains. */
4247 for (i = 0; i < n_sets; i++)
4249 rtx src, dest;
4250 rtx src_folded;
4251 struct table_elt *elt = 0, *p;
4252 enum machine_mode mode;
4253 rtx src_eqv_here;
4254 rtx src_const = 0;
4255 rtx src_related = 0;
4256 struct table_elt *src_const_elt = 0;
4257 int src_cost = MAX_COST;
4258 int src_eqv_cost = MAX_COST;
4259 int src_folded_cost = MAX_COST;
4260 int src_related_cost = MAX_COST;
4261 int src_elt_cost = MAX_COST;
4262 int src_regcost = MAX_COST;
4263 int src_eqv_regcost = MAX_COST;
4264 int src_folded_regcost = MAX_COST;
4265 int src_related_regcost = MAX_COST;
4266 int src_elt_regcost = MAX_COST;
4267 /* Set nonzero if we need to call force_const_mem on with the
4268 contents of src_folded before using it. */
4269 int src_folded_force_flag = 0;
4271 dest = SET_DEST (sets[i].rtl);
4272 src = SET_SRC (sets[i].rtl);
4274 /* If SRC is a constant that has no machine mode,
4275 hash it with the destination's machine mode.
4276 This way we can keep different modes separate. */
4278 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4279 sets[i].mode = mode;
4281 if (src_eqv)
4283 enum machine_mode eqvmode = mode;
4284 if (GET_CODE (dest) == STRICT_LOW_PART)
4285 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4286 do_not_record = 0;
4287 hash_arg_in_memory = 0;
4288 src_eqv_hash = HASH (src_eqv, eqvmode);
4290 /* Find the equivalence class for the equivalent expression. */
4292 if (!do_not_record)
4293 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4295 src_eqv_volatile = do_not_record;
4296 src_eqv_in_memory = hash_arg_in_memory;
4299 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4300 value of the INNER register, not the destination. So it is not
4301 a valid substitution for the source. But save it for later. */
4302 if (GET_CODE (dest) == STRICT_LOW_PART)
4303 src_eqv_here = 0;
4304 else
4305 src_eqv_here = src_eqv;
4307 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4308 simplified result, which may not necessarily be valid. */
4309 src_folded = fold_rtx (src, insn);
4311 #if 0
4312 /* ??? This caused bad code to be generated for the m68k port with -O2.
4313 Suppose src is (CONST_INT -1), and that after truncation src_folded
4314 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4315 At the end we will add src and src_const to the same equivalence
4316 class. We now have 3 and -1 on the same equivalence class. This
4317 causes later instructions to be mis-optimized. */
4318 /* If storing a constant in a bitfield, pre-truncate the constant
4319 so we will be able to record it later. */
4320 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT)
4322 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
4324 if (GET_CODE (src) == CONST_INT
4325 && GET_CODE (width) == CONST_INT
4326 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
4327 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
4328 src_folded
4329 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
4330 << INTVAL (width)) - 1));
4332 #endif
4334 /* Compute SRC's hash code, and also notice if it
4335 should not be recorded at all. In that case,
4336 prevent any further processing of this assignment. */
4337 do_not_record = 0;
4338 hash_arg_in_memory = 0;
4340 sets[i].src = src;
4341 sets[i].src_hash = HASH (src, mode);
4342 sets[i].src_volatile = do_not_record;
4343 sets[i].src_in_memory = hash_arg_in_memory;
4345 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4346 a pseudo, do not record SRC. Using SRC as a replacement for
4347 anything else will be incorrect in that situation. Note that
4348 this usually occurs only for stack slots, in which case all the
4349 RTL would be referring to SRC, so we don't lose any optimization
4350 opportunities by not having SRC in the hash table. */
4352 if (MEM_P (src)
4353 && find_reg_note (insn, REG_EQUIV, NULL_RTX) != 0
4354 && REG_P (dest)
4355 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
4356 sets[i].src_volatile = 1;
4358 #if 0
4359 /* It is no longer clear why we used to do this, but it doesn't
4360 appear to still be needed. So let's try without it since this
4361 code hurts cse'ing widened ops. */
4362 /* If source is a paradoxical subreg (such as QI treated as an SI),
4363 treat it as volatile. It may do the work of an SI in one context
4364 where the extra bits are not being used, but cannot replace an SI
4365 in general. */
4366 if (GET_CODE (src) == SUBREG
4367 && (GET_MODE_SIZE (GET_MODE (src))
4368 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
4369 sets[i].src_volatile = 1;
4370 #endif
4372 /* Locate all possible equivalent forms for SRC. Try to replace
4373 SRC in the insn with each cheaper equivalent.
4375 We have the following types of equivalents: SRC itself, a folded
4376 version, a value given in a REG_EQUAL note, or a value related
4377 to a constant.
4379 Each of these equivalents may be part of an additional class
4380 of equivalents (if more than one is in the table, they must be in
4381 the same class; we check for this).
4383 If the source is volatile, we don't do any table lookups.
4385 We note any constant equivalent for possible later use in a
4386 REG_NOTE. */
4388 if (!sets[i].src_volatile)
4389 elt = lookup (src, sets[i].src_hash, mode);
4391 sets[i].src_elt = elt;
4393 if (elt && src_eqv_here && src_eqv_elt)
4395 if (elt->first_same_value != src_eqv_elt->first_same_value)
4397 /* The REG_EQUAL is indicating that two formerly distinct
4398 classes are now equivalent. So merge them. */
4399 merge_equiv_classes (elt, src_eqv_elt);
4400 src_eqv_hash = HASH (src_eqv, elt->mode);
4401 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
4404 src_eqv_here = 0;
4407 else if (src_eqv_elt)
4408 elt = src_eqv_elt;
4410 /* Try to find a constant somewhere and record it in `src_const'.
4411 Record its table element, if any, in `src_const_elt'. Look in
4412 any known equivalences first. (If the constant is not in the
4413 table, also set `sets[i].src_const_hash'). */
4414 if (elt)
4415 for (p = elt->first_same_value; p; p = p->next_same_value)
4416 if (p->is_const)
4418 src_const = p->exp;
4419 src_const_elt = elt;
4420 break;
4423 if (src_const == 0
4424 && (CONSTANT_P (src_folded)
4425 /* Consider (minus (label_ref L1) (label_ref L2)) as
4426 "constant" here so we will record it. This allows us
4427 to fold switch statements when an ADDR_DIFF_VEC is used. */
4428 || (GET_CODE (src_folded) == MINUS
4429 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
4430 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
4431 src_const = src_folded, src_const_elt = elt;
4432 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
4433 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
4435 /* If we don't know if the constant is in the table, get its
4436 hash code and look it up. */
4437 if (src_const && src_const_elt == 0)
4439 sets[i].src_const_hash = HASH (src_const, mode);
4440 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
4443 sets[i].src_const = src_const;
4444 sets[i].src_const_elt = src_const_elt;
4446 /* If the constant and our source are both in the table, mark them as
4447 equivalent. Otherwise, if a constant is in the table but the source
4448 isn't, set ELT to it. */
4449 if (src_const_elt && elt
4450 && src_const_elt->first_same_value != elt->first_same_value)
4451 merge_equiv_classes (elt, src_const_elt);
4452 else if (src_const_elt && elt == 0)
4453 elt = src_const_elt;
4455 /* See if there is a register linearly related to a constant
4456 equivalent of SRC. */
4457 if (src_const
4458 && (GET_CODE (src_const) == CONST
4459 || (src_const_elt && src_const_elt->related_value != 0)))
4461 src_related = use_related_value (src_const, src_const_elt);
4462 if (src_related)
4464 struct table_elt *src_related_elt
4465 = lookup (src_related, HASH (src_related, mode), mode);
4466 if (src_related_elt && elt)
4468 if (elt->first_same_value
4469 != src_related_elt->first_same_value)
4470 /* This can occur when we previously saw a CONST
4471 involving a SYMBOL_REF and then see the SYMBOL_REF
4472 twice. Merge the involved classes. */
4473 merge_equiv_classes (elt, src_related_elt);
4475 src_related = 0;
4476 src_related_elt = 0;
4478 else if (src_related_elt && elt == 0)
4479 elt = src_related_elt;
4483 /* See if we have a CONST_INT that is already in a register in a
4484 wider mode. */
4486 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
4487 && GET_MODE_CLASS (mode) == MODE_INT
4488 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
4490 enum machine_mode wider_mode;
4492 for (wider_mode = GET_MODE_WIDER_MODE (mode);
4493 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
4494 && src_related == 0;
4495 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
4497 struct table_elt *const_elt
4498 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
4500 if (const_elt == 0)
4501 continue;
4503 for (const_elt = const_elt->first_same_value;
4504 const_elt; const_elt = const_elt->next_same_value)
4505 if (REG_P (const_elt->exp))
4507 src_related = gen_lowpart (mode,
4508 const_elt->exp);
4509 break;
4514 /* Another possibility is that we have an AND with a constant in
4515 a mode narrower than a word. If so, it might have been generated
4516 as part of an "if" which would narrow the AND. If we already
4517 have done the AND in a wider mode, we can use a SUBREG of that
4518 value. */
4520 if (flag_expensive_optimizations && ! src_related
4521 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
4522 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4524 enum machine_mode tmode;
4525 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
4527 for (tmode = GET_MODE_WIDER_MODE (mode);
4528 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
4529 tmode = GET_MODE_WIDER_MODE (tmode))
4531 rtx inner = gen_lowpart (tmode, XEXP (src, 0));
4532 struct table_elt *larger_elt;
4534 if (inner)
4536 PUT_MODE (new_and, tmode);
4537 XEXP (new_and, 0) = inner;
4538 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
4539 if (larger_elt == 0)
4540 continue;
4542 for (larger_elt = larger_elt->first_same_value;
4543 larger_elt; larger_elt = larger_elt->next_same_value)
4544 if (REG_P (larger_elt->exp))
4546 src_related
4547 = gen_lowpart (mode, larger_elt->exp);
4548 break;
4551 if (src_related)
4552 break;
4557 #ifdef LOAD_EXTEND_OP
4558 /* See if a MEM has already been loaded with a widening operation;
4559 if it has, we can use a subreg of that. Many CISC machines
4560 also have such operations, but this is only likely to be
4561 beneficial on these machines. */
4563 if (flag_expensive_optimizations && src_related == 0
4564 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4565 && GET_MODE_CLASS (mode) == MODE_INT
4566 && MEM_P (src) && ! do_not_record
4567 && LOAD_EXTEND_OP (mode) != UNKNOWN)
4569 struct rtx_def memory_extend_buf;
4570 rtx memory_extend_rtx = &memory_extend_buf;
4571 enum machine_mode tmode;
4573 /* Set what we are trying to extend and the operation it might
4574 have been extended with. */
4575 memset (memory_extend_rtx, 0, sizeof(*memory_extend_rtx));
4576 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
4577 XEXP (memory_extend_rtx, 0) = src;
4579 for (tmode = GET_MODE_WIDER_MODE (mode);
4580 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
4581 tmode = GET_MODE_WIDER_MODE (tmode))
4583 struct table_elt *larger_elt;
4585 PUT_MODE (memory_extend_rtx, tmode);
4586 larger_elt = lookup (memory_extend_rtx,
4587 HASH (memory_extend_rtx, tmode), tmode);
4588 if (larger_elt == 0)
4589 continue;
4591 for (larger_elt = larger_elt->first_same_value;
4592 larger_elt; larger_elt = larger_elt->next_same_value)
4593 if (REG_P (larger_elt->exp))
4595 src_related = gen_lowpart (mode,
4596 larger_elt->exp);
4597 break;
4600 if (src_related)
4601 break;
4604 #endif /* LOAD_EXTEND_OP */
4606 if (src == src_folded)
4607 src_folded = 0;
4609 /* At this point, ELT, if nonzero, points to a class of expressions
4610 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
4611 and SRC_RELATED, if nonzero, each contain additional equivalent
4612 expressions. Prune these latter expressions by deleting expressions
4613 already in the equivalence class.
4615 Check for an equivalent identical to the destination. If found,
4616 this is the preferred equivalent since it will likely lead to
4617 elimination of the insn. Indicate this by placing it in
4618 `src_related'. */
4620 if (elt)
4621 elt = elt->first_same_value;
4622 for (p = elt; p; p = p->next_same_value)
4624 enum rtx_code code = GET_CODE (p->exp);
4626 /* If the expression is not valid, ignore it. Then we do not
4627 have to check for validity below. In most cases, we can use
4628 `rtx_equal_p', since canonicalization has already been done. */
4629 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, false))
4630 continue;
4632 /* Also skip paradoxical subregs, unless that's what we're
4633 looking for. */
4634 if (code == SUBREG
4635 && (GET_MODE_SIZE (GET_MODE (p->exp))
4636 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
4637 && ! (src != 0
4638 && GET_CODE (src) == SUBREG
4639 && GET_MODE (src) == GET_MODE (p->exp)
4640 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
4641 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
4642 continue;
4644 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
4645 src = 0;
4646 else if (src_folded && GET_CODE (src_folded) == code
4647 && rtx_equal_p (src_folded, p->exp))
4648 src_folded = 0;
4649 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
4650 && rtx_equal_p (src_eqv_here, p->exp))
4651 src_eqv_here = 0;
4652 else if (src_related && GET_CODE (src_related) == code
4653 && rtx_equal_p (src_related, p->exp))
4654 src_related = 0;
4656 /* This is the same as the destination of the insns, we want
4657 to prefer it. Copy it to src_related. The code below will
4658 then give it a negative cost. */
4659 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
4660 src_related = dest;
4663 /* Find the cheapest valid equivalent, trying all the available
4664 possibilities. Prefer items not in the hash table to ones
4665 that are when they are equal cost. Note that we can never
4666 worsen an insn as the current contents will also succeed.
4667 If we find an equivalent identical to the destination, use it as best,
4668 since this insn will probably be eliminated in that case. */
4669 if (src)
4671 if (rtx_equal_p (src, dest))
4672 src_cost = src_regcost = -1;
4673 else
4675 src_cost = COST (src);
4676 src_regcost = approx_reg_cost (src);
4680 if (src_eqv_here)
4682 if (rtx_equal_p (src_eqv_here, dest))
4683 src_eqv_cost = src_eqv_regcost = -1;
4684 else
4686 src_eqv_cost = COST (src_eqv_here);
4687 src_eqv_regcost = approx_reg_cost (src_eqv_here);
4691 if (src_folded)
4693 if (rtx_equal_p (src_folded, dest))
4694 src_folded_cost = src_folded_regcost = -1;
4695 else
4697 src_folded_cost = COST (src_folded);
4698 src_folded_regcost = approx_reg_cost (src_folded);
4702 if (src_related)
4704 if (rtx_equal_p (src_related, dest))
4705 src_related_cost = src_related_regcost = -1;
4706 else
4708 src_related_cost = COST (src_related);
4709 src_related_regcost = approx_reg_cost (src_related);
4713 /* If this was an indirect jump insn, a known label will really be
4714 cheaper even though it looks more expensive. */
4715 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
4716 src_folded = src_const, src_folded_cost = src_folded_regcost = -1;
4718 /* Terminate loop when replacement made. This must terminate since
4719 the current contents will be tested and will always be valid. */
4720 while (1)
4722 rtx trial;
4724 /* Skip invalid entries. */
4725 while (elt && !REG_P (elt->exp)
4726 && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
4727 elt = elt->next_same_value;
4729 /* A paradoxical subreg would be bad here: it'll be the right
4730 size, but later may be adjusted so that the upper bits aren't
4731 what we want. So reject it. */
4732 if (elt != 0
4733 && GET_CODE (elt->exp) == SUBREG
4734 && (GET_MODE_SIZE (GET_MODE (elt->exp))
4735 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
4736 /* It is okay, though, if the rtx we're trying to match
4737 will ignore any of the bits we can't predict. */
4738 && ! (src != 0
4739 && GET_CODE (src) == SUBREG
4740 && GET_MODE (src) == GET_MODE (elt->exp)
4741 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
4742 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
4744 elt = elt->next_same_value;
4745 continue;
4748 if (elt)
4750 src_elt_cost = elt->cost;
4751 src_elt_regcost = elt->regcost;
4754 /* Find cheapest and skip it for the next time. For items
4755 of equal cost, use this order:
4756 src_folded, src, src_eqv, src_related and hash table entry. */
4757 if (src_folded
4758 && preferable (src_folded_cost, src_folded_regcost,
4759 src_cost, src_regcost) <= 0
4760 && preferable (src_folded_cost, src_folded_regcost,
4761 src_eqv_cost, src_eqv_regcost) <= 0
4762 && preferable (src_folded_cost, src_folded_regcost,
4763 src_related_cost, src_related_regcost) <= 0
4764 && preferable (src_folded_cost, src_folded_regcost,
4765 src_elt_cost, src_elt_regcost) <= 0)
4767 trial = src_folded, src_folded_cost = MAX_COST;
4768 if (src_folded_force_flag)
4770 rtx forced = force_const_mem (mode, trial);
4771 if (forced)
4772 trial = forced;
4775 else if (src
4776 && preferable (src_cost, src_regcost,
4777 src_eqv_cost, src_eqv_regcost) <= 0
4778 && preferable (src_cost, src_regcost,
4779 src_related_cost, src_related_regcost) <= 0
4780 && preferable (src_cost, src_regcost,
4781 src_elt_cost, src_elt_regcost) <= 0)
4782 trial = src, src_cost = MAX_COST;
4783 else if (src_eqv_here
4784 && preferable (src_eqv_cost, src_eqv_regcost,
4785 src_related_cost, src_related_regcost) <= 0
4786 && preferable (src_eqv_cost, src_eqv_regcost,
4787 src_elt_cost, src_elt_regcost) <= 0)
4788 trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
4789 else if (src_related
4790 && preferable (src_related_cost, src_related_regcost,
4791 src_elt_cost, src_elt_regcost) <= 0)
4792 trial = copy_rtx (src_related), src_related_cost = MAX_COST;
4793 else
4795 trial = copy_rtx (elt->exp);
4796 elt = elt->next_same_value;
4797 src_elt_cost = MAX_COST;
4800 /* We don't normally have an insn matching (set (pc) (pc)), so
4801 check for this separately here. We will delete such an
4802 insn below.
4804 For other cases such as a table jump or conditional jump
4805 where we know the ultimate target, go ahead and replace the
4806 operand. While that may not make a valid insn, we will
4807 reemit the jump below (and also insert any necessary
4808 barriers). */
4809 if (n_sets == 1 && dest == pc_rtx
4810 && (trial == pc_rtx
4811 || (GET_CODE (trial) == LABEL_REF
4812 && ! condjump_p (insn))))
4814 /* Don't substitute non-local labels, this confuses CFG. */
4815 if (GET_CODE (trial) == LABEL_REF
4816 && LABEL_REF_NONLOCAL_P (trial))
4817 continue;
4819 SET_SRC (sets[i].rtl) = trial;
4820 cse_jumps_altered = 1;
4821 break;
4824 /* Reject certain invalid forms of CONST that we create. */
4825 else if (CONSTANT_P (trial)
4826 && GET_CODE (trial) == CONST
4827 /* Reject cases that will cause decode_rtx_const to
4828 die. On the alpha when simplifying a switch, we
4829 get (const (truncate (minus (label_ref)
4830 (label_ref)))). */
4831 && (GET_CODE (XEXP (trial, 0)) == TRUNCATE
4832 /* Likewise on IA-64, except without the
4833 truncate. */
4834 || (GET_CODE (XEXP (trial, 0)) == MINUS
4835 && GET_CODE (XEXP (XEXP (trial, 0), 0)) == LABEL_REF
4836 && GET_CODE (XEXP (XEXP (trial, 0), 1)) == LABEL_REF)))
4837 /* Do nothing for this case. */
4840 /* Look for a substitution that makes a valid insn. */
4841 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
4843 rtx new = canon_reg (SET_SRC (sets[i].rtl), insn);
4845 /* If we just made a substitution inside a libcall, then we
4846 need to make the same substitution in any notes attached
4847 to the RETVAL insn. */
4848 if (libcall_insn
4849 && (REG_P (sets[i].orig_src)
4850 || GET_CODE (sets[i].orig_src) == SUBREG
4851 || MEM_P (sets[i].orig_src)))
4853 rtx note = find_reg_equal_equiv_note (libcall_insn);
4854 if (note != 0)
4855 XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0),
4856 sets[i].orig_src,
4857 copy_rtx (new));
4860 /* The result of apply_change_group can be ignored; see
4861 canon_reg. */
4863 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4864 apply_change_group ();
4865 break;
4868 /* If we previously found constant pool entries for
4869 constants and this is a constant, try making a
4870 pool entry. Put it in src_folded unless we already have done
4871 this since that is where it likely came from. */
4873 else if (constant_pool_entries_cost
4874 && CONSTANT_P (trial)
4875 && (src_folded == 0
4876 || (!MEM_P (src_folded)
4877 && ! src_folded_force_flag))
4878 && GET_MODE_CLASS (mode) != MODE_CC
4879 && mode != VOIDmode)
4881 src_folded_force_flag = 1;
4882 src_folded = trial;
4883 src_folded_cost = constant_pool_entries_cost;
4884 src_folded_regcost = constant_pool_entries_regcost;
4888 src = SET_SRC (sets[i].rtl);
4890 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
4891 However, there is an important exception: If both are registers
4892 that are not the head of their equivalence class, replace SET_SRC
4893 with the head of the class. If we do not do this, we will have
4894 both registers live over a portion of the basic block. This way,
4895 their lifetimes will likely abut instead of overlapping. */
4896 if (REG_P (dest)
4897 && REGNO_QTY_VALID_P (REGNO (dest)))
4899 int dest_q = REG_QTY (REGNO (dest));
4900 struct qty_table_elem *dest_ent = &qty_table[dest_q];
4902 if (dest_ent->mode == GET_MODE (dest)
4903 && dest_ent->first_reg != REGNO (dest)
4904 && REG_P (src) && REGNO (src) == REGNO (dest)
4905 /* Don't do this if the original insn had a hard reg as
4906 SET_SRC or SET_DEST. */
4907 && (!REG_P (sets[i].src)
4908 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
4909 && (!REG_P (dest) || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
4910 /* We can't call canon_reg here because it won't do anything if
4911 SRC is a hard register. */
4913 int src_q = REG_QTY (REGNO (src));
4914 struct qty_table_elem *src_ent = &qty_table[src_q];
4915 int first = src_ent->first_reg;
4916 rtx new_src
4917 = (first >= FIRST_PSEUDO_REGISTER
4918 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
4920 /* We must use validate-change even for this, because this
4921 might be a special no-op instruction, suitable only to
4922 tag notes onto. */
4923 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
4925 src = new_src;
4926 /* If we had a constant that is cheaper than what we are now
4927 setting SRC to, use that constant. We ignored it when we
4928 thought we could make this into a no-op. */
4929 if (src_const && COST (src_const) < COST (src)
4930 && validate_change (insn, &SET_SRC (sets[i].rtl),
4931 src_const, 0))
4932 src = src_const;
4937 /* If we made a change, recompute SRC values. */
4938 if (src != sets[i].src)
4940 do_not_record = 0;
4941 hash_arg_in_memory = 0;
4942 sets[i].src = src;
4943 sets[i].src_hash = HASH (src, mode);
4944 sets[i].src_volatile = do_not_record;
4945 sets[i].src_in_memory = hash_arg_in_memory;
4946 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
4949 /* If this is a single SET, we are setting a register, and we have an
4950 equivalent constant, we want to add a REG_NOTE. We don't want
4951 to write a REG_EQUAL note for a constant pseudo since verifying that
4952 that pseudo hasn't been eliminated is a pain. Such a note also
4953 won't help anything.
4955 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
4956 which can be created for a reference to a compile time computable
4957 entry in a jump table. */
4959 if (n_sets == 1 && src_const && REG_P (dest)
4960 && !REG_P (src_const)
4961 && ! (GET_CODE (src_const) == CONST
4962 && GET_CODE (XEXP (src_const, 0)) == MINUS
4963 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
4964 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
4966 /* We only want a REG_EQUAL note if src_const != src. */
4967 if (! rtx_equal_p (src, src_const))
4969 /* Make sure that the rtx is not shared. */
4970 src_const = copy_rtx (src_const);
4972 /* Record the actual constant value in a REG_EQUAL note,
4973 making a new one if one does not already exist. */
4974 set_unique_reg_note (insn, REG_EQUAL, src_const);
4978 /* Now deal with the destination. */
4979 do_not_record = 0;
4981 /* Look within any ZERO_EXTRACT to the MEM or REG within it. */
4982 while (GET_CODE (dest) == SUBREG
4983 || GET_CODE (dest) == ZERO_EXTRACT
4984 || GET_CODE (dest) == STRICT_LOW_PART)
4985 dest = XEXP (dest, 0);
4987 sets[i].inner_dest = dest;
4989 if (MEM_P (dest))
4991 #ifdef PUSH_ROUNDING
4992 /* Stack pushes invalidate the stack pointer. */
4993 rtx addr = XEXP (dest, 0);
4994 if (GET_RTX_CLASS (GET_CODE (addr)) == RTX_AUTOINC
4995 && XEXP (addr, 0) == stack_pointer_rtx)
4996 invalidate (stack_pointer_rtx, VOIDmode);
4997 #endif
4998 dest = fold_rtx (dest, insn);
5001 /* Compute the hash code of the destination now,
5002 before the effects of this instruction are recorded,
5003 since the register values used in the address computation
5004 are those before this instruction. */
5005 sets[i].dest_hash = HASH (dest, mode);
5007 /* Don't enter a bit-field in the hash table
5008 because the value in it after the store
5009 may not equal what was stored, due to truncation. */
5011 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT)
5013 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5015 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5016 && GET_CODE (width) == CONST_INT
5017 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5018 && ! (INTVAL (src_const)
5019 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5020 /* Exception: if the value is constant,
5021 and it won't be truncated, record it. */
5023 else
5025 /* This is chosen so that the destination will be invalidated
5026 but no new value will be recorded.
5027 We must invalidate because sometimes constant
5028 values can be recorded for bitfields. */
5029 sets[i].src_elt = 0;
5030 sets[i].src_volatile = 1;
5031 src_eqv = 0;
5032 src_eqv_elt = 0;
5036 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5037 the insn. */
5038 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5040 /* One less use of the label this insn used to jump to. */
5041 delete_insn_and_edges (insn);
5042 cse_jumps_altered = 1;
5043 /* No more processing for this set. */
5044 sets[i].rtl = 0;
5047 /* If this SET is now setting PC to a label, we know it used to
5048 be a conditional or computed branch. */
5049 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF
5050 && !LABEL_REF_NONLOCAL_P (src))
5052 /* Now emit a BARRIER after the unconditional jump. */
5053 if (NEXT_INSN (insn) == 0
5054 || !BARRIER_P (NEXT_INSN (insn)))
5055 emit_barrier_after (insn);
5057 /* We reemit the jump in as many cases as possible just in
5058 case the form of an unconditional jump is significantly
5059 different than a computed jump or conditional jump.
5061 If this insn has multiple sets, then reemitting the
5062 jump is nontrivial. So instead we just force rerecognition
5063 and hope for the best. */
5064 if (n_sets == 1)
5066 rtx new, note;
5068 new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
5069 JUMP_LABEL (new) = XEXP (src, 0);
5070 LABEL_NUSES (XEXP (src, 0))++;
5072 /* Make sure to copy over REG_NON_LOCAL_GOTO. */
5073 note = find_reg_note (insn, REG_NON_LOCAL_GOTO, 0);
5074 if (note)
5076 XEXP (note, 1) = NULL_RTX;
5077 REG_NOTES (new) = note;
5080 delete_insn_and_edges (insn);
5081 insn = new;
5083 /* Now emit a BARRIER after the unconditional jump. */
5084 if (NEXT_INSN (insn) == 0
5085 || !BARRIER_P (NEXT_INSN (insn)))
5086 emit_barrier_after (insn);
5088 else
5089 INSN_CODE (insn) = -1;
5091 /* Do not bother deleting any unreachable code,
5092 let jump/flow do that. */
5094 cse_jumps_altered = 1;
5095 sets[i].rtl = 0;
5098 /* If destination is volatile, invalidate it and then do no further
5099 processing for this assignment. */
5101 else if (do_not_record)
5103 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5104 invalidate (dest, VOIDmode);
5105 else if (MEM_P (dest))
5106 invalidate (dest, VOIDmode);
5107 else if (GET_CODE (dest) == STRICT_LOW_PART
5108 || GET_CODE (dest) == ZERO_EXTRACT)
5109 invalidate (XEXP (dest, 0), GET_MODE (dest));
5110 sets[i].rtl = 0;
5113 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5114 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5116 #ifdef HAVE_cc0
5117 /* If setting CC0, record what it was set to, or a constant, if it
5118 is equivalent to a constant. If it is being set to a floating-point
5119 value, make a COMPARE with the appropriate constant of 0. If we
5120 don't do this, later code can interpret this as a test against
5121 const0_rtx, which can cause problems if we try to put it into an
5122 insn as a floating-point operand. */
5123 if (dest == cc0_rtx)
5125 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5126 this_insn_cc0_mode = mode;
5127 if (FLOAT_MODE_P (mode))
5128 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5129 CONST0_RTX (mode));
5131 #endif
5134 /* Now enter all non-volatile source expressions in the hash table
5135 if they are not already present.
5136 Record their equivalence classes in src_elt.
5137 This way we can insert the corresponding destinations into
5138 the same classes even if the actual sources are no longer in them
5139 (having been invalidated). */
5141 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5142 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5144 struct table_elt *elt;
5145 struct table_elt *classp = sets[0].src_elt;
5146 rtx dest = SET_DEST (sets[0].rtl);
5147 enum machine_mode eqvmode = GET_MODE (dest);
5149 if (GET_CODE (dest) == STRICT_LOW_PART)
5151 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5152 classp = 0;
5154 if (insert_regs (src_eqv, classp, 0))
5156 rehash_using_reg (src_eqv);
5157 src_eqv_hash = HASH (src_eqv, eqvmode);
5159 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5160 elt->in_memory = src_eqv_in_memory;
5161 src_eqv_elt = elt;
5163 /* Check to see if src_eqv_elt is the same as a set source which
5164 does not yet have an elt, and if so set the elt of the set source
5165 to src_eqv_elt. */
5166 for (i = 0; i < n_sets; i++)
5167 if (sets[i].rtl && sets[i].src_elt == 0
5168 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5169 sets[i].src_elt = src_eqv_elt;
5172 for (i = 0; i < n_sets; i++)
5173 if (sets[i].rtl && ! sets[i].src_volatile
5174 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5176 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5178 /* REG_EQUAL in setting a STRICT_LOW_PART
5179 gives an equivalent for the entire destination register,
5180 not just for the subreg being stored in now.
5181 This is a more interesting equivalence, so we arrange later
5182 to treat the entire reg as the destination. */
5183 sets[i].src_elt = src_eqv_elt;
5184 sets[i].src_hash = src_eqv_hash;
5186 else
5188 /* Insert source and constant equivalent into hash table, if not
5189 already present. */
5190 struct table_elt *classp = src_eqv_elt;
5191 rtx src = sets[i].src;
5192 rtx dest = SET_DEST (sets[i].rtl);
5193 enum machine_mode mode
5194 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5196 /* It's possible that we have a source value known to be
5197 constant but don't have a REG_EQUAL note on the insn.
5198 Lack of a note will mean src_eqv_elt will be NULL. This
5199 can happen where we've generated a SUBREG to access a
5200 CONST_INT that is already in a register in a wider mode.
5201 Ensure that the source expression is put in the proper
5202 constant class. */
5203 if (!classp)
5204 classp = sets[i].src_const_elt;
5206 if (sets[i].src_elt == 0)
5208 /* Don't put a hard register source into the table if this is
5209 the last insn of a libcall. In this case, we only need
5210 to put src_eqv_elt in src_elt. */
5211 if (! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5213 struct table_elt *elt;
5215 /* Note that these insert_regs calls cannot remove
5216 any of the src_elt's, because they would have failed to
5217 match if not still valid. */
5218 if (insert_regs (src, classp, 0))
5220 rehash_using_reg (src);
5221 sets[i].src_hash = HASH (src, mode);
5223 elt = insert (src, classp, sets[i].src_hash, mode);
5224 elt->in_memory = sets[i].src_in_memory;
5225 sets[i].src_elt = classp = elt;
5227 else
5228 sets[i].src_elt = classp;
5230 if (sets[i].src_const && sets[i].src_const_elt == 0
5231 && src != sets[i].src_const
5232 && ! rtx_equal_p (sets[i].src_const, src))
5233 sets[i].src_elt = insert (sets[i].src_const, classp,
5234 sets[i].src_const_hash, mode);
5237 else if (sets[i].src_elt == 0)
5238 /* If we did not insert the source into the hash table (e.g., it was
5239 volatile), note the equivalence class for the REG_EQUAL value, if any,
5240 so that the destination goes into that class. */
5241 sets[i].src_elt = src_eqv_elt;
5243 /* Record destination addresses in the hash table. This allows us to
5244 check if they are invalidated by other sets. */
5245 for (i = 0; i < n_sets; i++)
5247 if (sets[i].rtl)
5249 rtx x = sets[i].inner_dest;
5250 struct table_elt *elt;
5251 enum machine_mode mode;
5252 unsigned hash;
5254 if (MEM_P (x))
5256 x = XEXP (x, 0);
5257 mode = GET_MODE (x);
5258 hash = HASH (x, mode);
5259 elt = lookup (x, hash, mode);
5260 if (!elt)
5262 if (insert_regs (x, NULL, 0))
5264 rehash_using_reg (x);
5265 hash = HASH (x, mode);
5267 elt = insert (x, NULL, hash, mode);
5270 sets[i].dest_addr_elt = elt;
5272 else
5273 sets[i].dest_addr_elt = NULL;
5277 invalidate_from_clobbers (x);
5279 /* Some registers are invalidated by subroutine calls. Memory is
5280 invalidated by non-constant calls. */
5282 if (CALL_P (insn))
5284 if (! CONST_OR_PURE_CALL_P (insn))
5285 invalidate_memory ();
5286 invalidate_for_call ();
5289 /* Now invalidate everything set by this instruction.
5290 If a SUBREG or other funny destination is being set,
5291 sets[i].rtl is still nonzero, so here we invalidate the reg
5292 a part of which is being set. */
5294 for (i = 0; i < n_sets; i++)
5295 if (sets[i].rtl)
5297 /* We can't use the inner dest, because the mode associated with
5298 a ZERO_EXTRACT is significant. */
5299 rtx dest = SET_DEST (sets[i].rtl);
5301 /* Needed for registers to remove the register from its
5302 previous quantity's chain.
5303 Needed for memory if this is a nonvarying address, unless
5304 we have just done an invalidate_memory that covers even those. */
5305 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5306 invalidate (dest, VOIDmode);
5307 else if (MEM_P (dest))
5308 invalidate (dest, VOIDmode);
5309 else if (GET_CODE (dest) == STRICT_LOW_PART
5310 || GET_CODE (dest) == ZERO_EXTRACT)
5311 invalidate (XEXP (dest, 0), GET_MODE (dest));
5314 /* A volatile ASM invalidates everything. */
5315 if (NONJUMP_INSN_P (insn)
5316 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5317 && MEM_VOLATILE_P (PATTERN (insn)))
5318 flush_hash_table ();
5320 /* Make sure registers mentioned in destinations
5321 are safe for use in an expression to be inserted.
5322 This removes from the hash table
5323 any invalid entry that refers to one of these registers.
5325 We don't care about the return value from mention_regs because
5326 we are going to hash the SET_DEST values unconditionally. */
5328 for (i = 0; i < n_sets; i++)
5330 if (sets[i].rtl)
5332 rtx x = SET_DEST (sets[i].rtl);
5334 if (!REG_P (x))
5335 mention_regs (x);
5336 else
5338 /* We used to rely on all references to a register becoming
5339 inaccessible when a register changes to a new quantity,
5340 since that changes the hash code. However, that is not
5341 safe, since after HASH_SIZE new quantities we get a
5342 hash 'collision' of a register with its own invalid
5343 entries. And since SUBREGs have been changed not to
5344 change their hash code with the hash code of the register,
5345 it wouldn't work any longer at all. So we have to check
5346 for any invalid references lying around now.
5347 This code is similar to the REG case in mention_regs,
5348 but it knows that reg_tick has been incremented, and
5349 it leaves reg_in_table as -1 . */
5350 unsigned int regno = REGNO (x);
5351 unsigned int endregno
5352 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
5353 : hard_regno_nregs[regno][GET_MODE (x)]);
5354 unsigned int i;
5356 for (i = regno; i < endregno; i++)
5358 if (REG_IN_TABLE (i) >= 0)
5360 remove_invalid_refs (i);
5361 REG_IN_TABLE (i) = -1;
5368 /* We may have just removed some of the src_elt's from the hash table.
5369 So replace each one with the current head of the same class.
5370 Also check if destination addresses have been removed. */
5372 for (i = 0; i < n_sets; i++)
5373 if (sets[i].rtl)
5375 if (sets[i].dest_addr_elt
5376 && sets[i].dest_addr_elt->first_same_value == 0)
5378 /* The elt was removed, which means this destination is not
5379 valid after this instruction. */
5380 sets[i].rtl = NULL_RTX;
5382 else if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
5383 /* If elt was removed, find current head of same class,
5384 or 0 if nothing remains of that class. */
5386 struct table_elt *elt = sets[i].src_elt;
5388 while (elt && elt->prev_same_value)
5389 elt = elt->prev_same_value;
5391 while (elt && elt->first_same_value == 0)
5392 elt = elt->next_same_value;
5393 sets[i].src_elt = elt ? elt->first_same_value : 0;
5397 /* Now insert the destinations into their equivalence classes. */
5399 for (i = 0; i < n_sets; i++)
5400 if (sets[i].rtl)
5402 rtx dest = SET_DEST (sets[i].rtl);
5403 struct table_elt *elt;
5405 /* Don't record value if we are not supposed to risk allocating
5406 floating-point values in registers that might be wider than
5407 memory. */
5408 if ((flag_float_store
5409 && MEM_P (dest)
5410 && FLOAT_MODE_P (GET_MODE (dest)))
5411 /* Don't record BLKmode values, because we don't know the
5412 size of it, and can't be sure that other BLKmode values
5413 have the same or smaller size. */
5414 || GET_MODE (dest) == BLKmode
5415 /* Don't record values of destinations set inside a libcall block
5416 since we might delete the libcall. Things should have been set
5417 up so we won't want to reuse such a value, but we play it safe
5418 here. */
5419 || libcall_insn
5420 /* If we didn't put a REG_EQUAL value or a source into the hash
5421 table, there is no point is recording DEST. */
5422 || sets[i].src_elt == 0
5423 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
5424 or SIGN_EXTEND, don't record DEST since it can cause
5425 some tracking to be wrong.
5427 ??? Think about this more later. */
5428 || (GET_CODE (dest) == SUBREG
5429 && (GET_MODE_SIZE (GET_MODE (dest))
5430 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5431 && (GET_CODE (sets[i].src) == SIGN_EXTEND
5432 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
5433 continue;
5435 /* STRICT_LOW_PART isn't part of the value BEING set,
5436 and neither is the SUBREG inside it.
5437 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
5438 if (GET_CODE (dest) == STRICT_LOW_PART)
5439 dest = SUBREG_REG (XEXP (dest, 0));
5441 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5442 /* Registers must also be inserted into chains for quantities. */
5443 if (insert_regs (dest, sets[i].src_elt, 1))
5445 /* If `insert_regs' changes something, the hash code must be
5446 recalculated. */
5447 rehash_using_reg (dest);
5448 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
5451 elt = insert (dest, sets[i].src_elt,
5452 sets[i].dest_hash, GET_MODE (dest));
5454 elt->in_memory = (MEM_P (sets[i].inner_dest)
5455 && !MEM_READONLY_P (sets[i].inner_dest));
5457 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
5458 narrower than M2, and both M1 and M2 are the same number of words,
5459 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
5460 make that equivalence as well.
5462 However, BAR may have equivalences for which gen_lowpart
5463 will produce a simpler value than gen_lowpart applied to
5464 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
5465 BAR's equivalences. If we don't get a simplified form, make
5466 the SUBREG. It will not be used in an equivalence, but will
5467 cause two similar assignments to be detected.
5469 Note the loop below will find SUBREG_REG (DEST) since we have
5470 already entered SRC and DEST of the SET in the table. */
5472 if (GET_CODE (dest) == SUBREG
5473 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
5474 / UNITS_PER_WORD)
5475 == (GET_MODE_SIZE (GET_MODE (dest)) - 1) / UNITS_PER_WORD)
5476 && (GET_MODE_SIZE (GET_MODE (dest))
5477 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5478 && sets[i].src_elt != 0)
5480 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
5481 struct table_elt *elt, *classp = 0;
5483 for (elt = sets[i].src_elt->first_same_value; elt;
5484 elt = elt->next_same_value)
5486 rtx new_src = 0;
5487 unsigned src_hash;
5488 struct table_elt *src_elt;
5489 int byte = 0;
5491 /* Ignore invalid entries. */
5492 if (!REG_P (elt->exp)
5493 && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
5494 continue;
5496 /* We may have already been playing subreg games. If the
5497 mode is already correct for the destination, use it. */
5498 if (GET_MODE (elt->exp) == new_mode)
5499 new_src = elt->exp;
5500 else
5502 /* Calculate big endian correction for the SUBREG_BYTE.
5503 We have already checked that M1 (GET_MODE (dest))
5504 is not narrower than M2 (new_mode). */
5505 if (BYTES_BIG_ENDIAN)
5506 byte = (GET_MODE_SIZE (GET_MODE (dest))
5507 - GET_MODE_SIZE (new_mode));
5509 new_src = simplify_gen_subreg (new_mode, elt->exp,
5510 GET_MODE (dest), byte);
5513 /* The call to simplify_gen_subreg fails if the value
5514 is VOIDmode, yet we can't do any simplification, e.g.
5515 for EXPR_LISTs denoting function call results.
5516 It is invalid to construct a SUBREG with a VOIDmode
5517 SUBREG_REG, hence a zero new_src means we can't do
5518 this substitution. */
5519 if (! new_src)
5520 continue;
5522 src_hash = HASH (new_src, new_mode);
5523 src_elt = lookup (new_src, src_hash, new_mode);
5525 /* Put the new source in the hash table is if isn't
5526 already. */
5527 if (src_elt == 0)
5529 if (insert_regs (new_src, classp, 0))
5531 rehash_using_reg (new_src);
5532 src_hash = HASH (new_src, new_mode);
5534 src_elt = insert (new_src, classp, src_hash, new_mode);
5535 src_elt->in_memory = elt->in_memory;
5537 else if (classp && classp != src_elt->first_same_value)
5538 /* Show that two things that we've seen before are
5539 actually the same. */
5540 merge_equiv_classes (src_elt, classp);
5542 classp = src_elt->first_same_value;
5543 /* Ignore invalid entries. */
5544 while (classp
5545 && !REG_P (classp->exp)
5546 && ! exp_equiv_p (classp->exp, classp->exp, 1, false))
5547 classp = classp->next_same_value;
5552 /* Special handling for (set REG0 REG1) where REG0 is the
5553 "cheapest", cheaper than REG1. After cse, REG1 will probably not
5554 be used in the sequel, so (if easily done) change this insn to
5555 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
5556 that computed their value. Then REG1 will become a dead store
5557 and won't cloud the situation for later optimizations.
5559 Do not make this change if REG1 is a hard register, because it will
5560 then be used in the sequel and we may be changing a two-operand insn
5561 into a three-operand insn.
5563 Also do not do this if we are operating on a copy of INSN.
5565 Also don't do this if INSN ends a libcall; this would cause an unrelated
5566 register to be set in the middle of a libcall, and we then get bad code
5567 if the libcall is deleted. */
5569 if (n_sets == 1 && sets[0].rtl && REG_P (SET_DEST (sets[0].rtl))
5570 && NEXT_INSN (PREV_INSN (insn)) == insn
5571 && REG_P (SET_SRC (sets[0].rtl))
5572 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
5573 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
5575 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
5576 struct qty_table_elem *src_ent = &qty_table[src_q];
5578 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
5579 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5581 rtx prev = insn;
5582 /* Scan for the previous nonnote insn, but stop at a basic
5583 block boundary. */
5586 prev = PREV_INSN (prev);
5588 while (prev && NOTE_P (prev)
5589 && NOTE_LINE_NUMBER (prev) != NOTE_INSN_BASIC_BLOCK);
5591 /* Do not swap the registers around if the previous instruction
5592 attaches a REG_EQUIV note to REG1.
5594 ??? It's not entirely clear whether we can transfer a REG_EQUIV
5595 from the pseudo that originally shadowed an incoming argument
5596 to another register. Some uses of REG_EQUIV might rely on it
5597 being attached to REG1 rather than REG2.
5599 This section previously turned the REG_EQUIV into a REG_EQUAL
5600 note. We cannot do that because REG_EQUIV may provide an
5601 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
5603 if (prev != 0 && NONJUMP_INSN_P (prev)
5604 && GET_CODE (PATTERN (prev)) == SET
5605 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
5606 && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
5608 rtx dest = SET_DEST (sets[0].rtl);
5609 rtx src = SET_SRC (sets[0].rtl);
5610 rtx note;
5612 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
5613 validate_change (insn, &SET_DEST (sets[0].rtl), src, 1);
5614 validate_change (insn, &SET_SRC (sets[0].rtl), dest, 1);
5615 apply_change_group ();
5617 /* If INSN has a REG_EQUAL note, and this note mentions
5618 REG0, then we must delete it, because the value in
5619 REG0 has changed. If the note's value is REG1, we must
5620 also delete it because that is now this insn's dest. */
5621 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5622 if (note != 0
5623 && (reg_mentioned_p (dest, XEXP (note, 0))
5624 || rtx_equal_p (src, XEXP (note, 0))))
5625 remove_note (insn, note);
5630 /* If this is a conditional jump insn, record any known equivalences due to
5631 the condition being tested. */
5633 if (n_sets == 1 && any_condjump_p (insn))
5634 record_jump_equiv (insn, false);
5636 #ifdef HAVE_cc0
5637 /* If the previous insn set CC0 and this insn no longer references CC0,
5638 delete the previous insn. Here we use the fact that nothing expects CC0
5639 to be valid over an insn, which is true until the final pass. */
5640 if (prev_insn && NONJUMP_INSN_P (prev_insn)
5641 && (tem = single_set (prev_insn)) != 0
5642 && SET_DEST (tem) == cc0_rtx
5643 && ! reg_mentioned_p (cc0_rtx, x))
5644 delete_insn_and_edges (prev_insn);
5646 prev_insn_cc0 = this_insn_cc0;
5647 prev_insn_cc0_mode = this_insn_cc0_mode;
5648 prev_insn = insn;
5649 #endif
5652 /* Remove from the hash table all expressions that reference memory. */
5654 static void
5655 invalidate_memory (void)
5657 int i;
5658 struct table_elt *p, *next;
5660 for (i = 0; i < HASH_SIZE; i++)
5661 for (p = table[i]; p; p = next)
5663 next = p->next_same_hash;
5664 if (p->in_memory)
5665 remove_from_table (p, i);
5669 /* Perform invalidation on the basis of everything about an insn
5670 except for invalidating the actual places that are SET in it.
5671 This includes the places CLOBBERed, and anything that might
5672 alias with something that is SET or CLOBBERed.
5674 X is the pattern of the insn. */
5676 static void
5677 invalidate_from_clobbers (rtx x)
5679 if (GET_CODE (x) == CLOBBER)
5681 rtx ref = XEXP (x, 0);
5682 if (ref)
5684 if (REG_P (ref) || GET_CODE (ref) == SUBREG
5685 || MEM_P (ref))
5686 invalidate (ref, VOIDmode);
5687 else if (GET_CODE (ref) == STRICT_LOW_PART
5688 || GET_CODE (ref) == ZERO_EXTRACT)
5689 invalidate (XEXP (ref, 0), GET_MODE (ref));
5692 else if (GET_CODE (x) == PARALLEL)
5694 int i;
5695 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
5697 rtx y = XVECEXP (x, 0, i);
5698 if (GET_CODE (y) == CLOBBER)
5700 rtx ref = XEXP (y, 0);
5701 if (REG_P (ref) || GET_CODE (ref) == SUBREG
5702 || MEM_P (ref))
5703 invalidate (ref, VOIDmode);
5704 else if (GET_CODE (ref) == STRICT_LOW_PART
5705 || GET_CODE (ref) == ZERO_EXTRACT)
5706 invalidate (XEXP (ref, 0), GET_MODE (ref));
5712 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
5713 and replace any registers in them with either an equivalent constant
5714 or the canonical form of the register. If we are inside an address,
5715 only do this if the address remains valid.
5717 OBJECT is 0 except when within a MEM in which case it is the MEM.
5719 Return the replacement for X. */
5721 static rtx
5722 cse_process_notes (rtx x, rtx object)
5724 enum rtx_code code = GET_CODE (x);
5725 const char *fmt = GET_RTX_FORMAT (code);
5726 int i;
5728 switch (code)
5730 case CONST_INT:
5731 case CONST:
5732 case SYMBOL_REF:
5733 case LABEL_REF:
5734 case CONST_DOUBLE:
5735 case CONST_VECTOR:
5736 case PC:
5737 case CC0:
5738 case LO_SUM:
5739 return x;
5741 case MEM:
5742 validate_change (x, &XEXP (x, 0),
5743 cse_process_notes (XEXP (x, 0), x), 0);
5744 return x;
5746 case EXPR_LIST:
5747 case INSN_LIST:
5748 if (REG_NOTE_KIND (x) == REG_EQUAL)
5749 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
5750 if (XEXP (x, 1))
5751 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
5752 return x;
5754 case SIGN_EXTEND:
5755 case ZERO_EXTEND:
5756 case SUBREG:
5758 rtx new = cse_process_notes (XEXP (x, 0), object);
5759 /* We don't substitute VOIDmode constants into these rtx,
5760 since they would impede folding. */
5761 if (GET_MODE (new) != VOIDmode)
5762 validate_change (object, &XEXP (x, 0), new, 0);
5763 return x;
5766 case REG:
5767 i = REG_QTY (REGNO (x));
5769 /* Return a constant or a constant register. */
5770 if (REGNO_QTY_VALID_P (REGNO (x)))
5772 struct qty_table_elem *ent = &qty_table[i];
5774 if (ent->const_rtx != NULL_RTX
5775 && (CONSTANT_P (ent->const_rtx)
5776 || REG_P (ent->const_rtx)))
5778 rtx new = gen_lowpart (GET_MODE (x), ent->const_rtx);
5779 if (new)
5780 return copy_rtx (new);
5784 /* Otherwise, canonicalize this register. */
5785 return canon_reg (x, NULL_RTX);
5787 default:
5788 break;
5791 for (i = 0; i < GET_RTX_LENGTH (code); i++)
5792 if (fmt[i] == 'e')
5793 validate_change (object, &XEXP (x, i),
5794 cse_process_notes (XEXP (x, i), object), 0);
5796 return x;
5799 /* Find the end of INSN's basic block and return its range,
5800 the total number of SETs in all the insns of the block, the last insn of the
5801 block, and the branch path.
5803 The branch path indicates which branches should be followed. If a nonzero
5804 path size is specified, the block should be rescanned and a different set
5805 of branches will be taken. The branch path is only used if
5806 FLAG_CSE_FOLLOW_JUMPS is nonzero.
5808 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
5809 used to describe the block. It is filled in with the information about
5810 the current block. The incoming structure's branch path, if any, is used
5811 to construct the output branch path. */
5813 static void
5814 cse_end_of_basic_block (rtx insn, struct cse_basic_block_data *data,
5815 int follow_jumps)
5817 rtx p = insn, q;
5818 int nsets = 0;
5819 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
5820 rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
5821 int path_size = data->path_size;
5822 int path_entry = 0;
5823 int i;
5825 /* Update the previous branch path, if any. If the last branch was
5826 previously PATH_TAKEN, mark it PATH_NOT_TAKEN.
5827 If it was previously PATH_NOT_TAKEN,
5828 shorten the path by one and look at the previous branch. We know that
5829 at least one branch must have been taken if PATH_SIZE is nonzero. */
5830 while (path_size > 0)
5832 if (data->path[path_size - 1].status != PATH_NOT_TAKEN)
5834 data->path[path_size - 1].status = PATH_NOT_TAKEN;
5835 break;
5837 else
5838 path_size--;
5841 /* If the first instruction is marked with QImode, that means we've
5842 already processed this block. Our caller will look at DATA->LAST
5843 to figure out where to go next. We want to return the next block
5844 in the instruction stream, not some branched-to block somewhere
5845 else. We accomplish this by pretending our called forbid us to
5846 follow jumps. */
5847 if (GET_MODE (insn) == QImode)
5848 follow_jumps = 0;
5850 /* Scan to end of this basic block. */
5851 while (p && !LABEL_P (p))
5853 /* Don't cse over a call to setjmp; on some machines (eg VAX)
5854 the regs restored by the longjmp come from
5855 a later time than the setjmp. */
5856 if (PREV_INSN (p) && CALL_P (PREV_INSN (p))
5857 && find_reg_note (PREV_INSN (p), REG_SETJMP, NULL))
5858 break;
5860 /* A PARALLEL can have lots of SETs in it,
5861 especially if it is really an ASM_OPERANDS. */
5862 if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
5863 nsets += XVECLEN (PATTERN (p), 0);
5864 else if (!NOTE_P (p))
5865 nsets += 1;
5867 /* Ignore insns made by CSE; they cannot affect the boundaries of
5868 the basic block. */
5870 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
5871 high_cuid = INSN_CUID (p);
5872 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
5873 low_cuid = INSN_CUID (p);
5875 /* See if this insn is in our branch path. If it is and we are to
5876 take it, do so. */
5877 if (path_entry < path_size && data->path[path_entry].branch == p)
5879 if (data->path[path_entry].status != PATH_NOT_TAKEN)
5880 p = JUMP_LABEL (p);
5882 /* Point to next entry in path, if any. */
5883 path_entry++;
5886 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
5887 was specified, we haven't reached our maximum path length, there are
5888 insns following the target of the jump, this is the only use of the
5889 jump label, and the target label is preceded by a BARRIER. */
5890 else if (follow_jumps
5891 && path_size < PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH) - 1
5892 && JUMP_P (p)
5893 && GET_CODE (PATTERN (p)) == SET
5894 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
5895 && JUMP_LABEL (p) != 0
5896 && LABEL_NUSES (JUMP_LABEL (p)) == 1
5897 && NEXT_INSN (JUMP_LABEL (p)) != 0)
5899 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
5900 if ((!NOTE_P (q)
5901 || (PREV_INSN (q) && CALL_P (PREV_INSN (q))
5902 && find_reg_note (PREV_INSN (q), REG_SETJMP, NULL)))
5903 && (!LABEL_P (q) || LABEL_NUSES (q) != 0))
5904 break;
5906 /* If we ran into a BARRIER, this code is an extension of the
5907 basic block when the branch is taken. */
5908 if (follow_jumps && q != 0 && BARRIER_P (q))
5910 /* Don't allow ourself to keep walking around an
5911 always-executed loop. */
5912 if (next_real_insn (q) == next)
5914 p = NEXT_INSN (p);
5915 continue;
5918 /* Similarly, don't put a branch in our path more than once. */
5919 for (i = 0; i < path_entry; i++)
5920 if (data->path[i].branch == p)
5921 break;
5923 if (i != path_entry)
5924 break;
5926 data->path[path_entry].branch = p;
5927 data->path[path_entry++].status = PATH_TAKEN;
5929 /* This branch now ends our path. It was possible that we
5930 didn't see this branch the last time around (when the
5931 insn in front of the target was a JUMP_INSN that was
5932 turned into a no-op). */
5933 path_size = path_entry;
5935 p = JUMP_LABEL (p);
5936 /* Mark block so we won't scan it again later. */
5937 PUT_MODE (NEXT_INSN (p), QImode);
5940 p = NEXT_INSN (p);
5943 data->low_cuid = low_cuid;
5944 data->high_cuid = high_cuid;
5945 data->nsets = nsets;
5946 data->last = p;
5948 /* If all jumps in the path are not taken, set our path length to zero
5949 so a rescan won't be done. */
5950 for (i = path_size - 1; i >= 0; i--)
5951 if (data->path[i].status != PATH_NOT_TAKEN)
5952 break;
5954 if (i == -1)
5955 data->path_size = 0;
5956 else
5957 data->path_size = path_size;
5959 /* End the current branch path. */
5960 data->path[path_size].branch = 0;
5963 /* Perform cse on the instructions of a function.
5964 F is the first instruction.
5965 NREGS is one plus the highest pseudo-reg number used in the instruction.
5967 Returns 1 if jump_optimize should be redone due to simplifications
5968 in conditional jump instructions. */
5971 cse_main (rtx f, int nregs)
5973 struct cse_basic_block_data val;
5974 rtx insn = f;
5975 int i;
5977 init_cse_reg_info (nregs);
5979 val.path = XNEWVEC (struct branch_path, PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
5981 cse_jumps_altered = 0;
5982 recorded_label_ref = 0;
5983 constant_pool_entries_cost = 0;
5984 constant_pool_entries_regcost = 0;
5985 val.path_size = 0;
5986 rtl_hooks = cse_rtl_hooks;
5988 init_recog ();
5989 init_alias_analysis ();
5991 reg_eqv_table = XNEWVEC (struct reg_eqv_elem, nregs);
5993 /* Find the largest uid. */
5995 max_uid = get_max_uid ();
5996 uid_cuid = XCNEWVEC (int, max_uid + 1);
5998 /* Compute the mapping from uids to cuids.
5999 CUIDs are numbers assigned to insns, like uids,
6000 except that cuids increase monotonically through the code. */
6002 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
6003 INSN_CUID (insn) = ++i;
6005 /* Loop over basic blocks.
6006 Compute the maximum number of qty's needed for each basic block
6007 (which is 2 for each SET). */
6008 insn = f;
6009 while (insn)
6011 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps);
6013 /* If this basic block was already processed or has no sets, skip it. */
6014 if (val.nsets == 0 || GET_MODE (insn) == QImode)
6016 PUT_MODE (insn, VOIDmode);
6017 insn = (val.last ? NEXT_INSN (val.last) : 0);
6018 val.path_size = 0;
6019 continue;
6022 cse_basic_block_start = val.low_cuid;
6023 cse_basic_block_end = val.high_cuid;
6024 max_qty = val.nsets * 2;
6026 if (dump_file)
6027 fprintf (dump_file, ";; Processing block from %d to %d, %d sets.\n",
6028 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
6029 val.nsets);
6031 /* Make MAX_QTY bigger to give us room to optimize
6032 past the end of this basic block, if that should prove useful. */
6033 if (max_qty < 500)
6034 max_qty = 500;
6036 /* If this basic block is being extended by following certain jumps,
6037 (see `cse_end_of_basic_block'), we reprocess the code from the start.
6038 Otherwise, we start after this basic block. */
6039 if (val.path_size > 0)
6040 cse_basic_block (insn, val.last, val.path);
6041 else
6043 int old_cse_jumps_altered = cse_jumps_altered;
6044 rtx temp;
6046 /* When cse changes a conditional jump to an unconditional
6047 jump, we want to reprocess the block, since it will give
6048 us a new branch path to investigate. */
6049 cse_jumps_altered = 0;
6050 temp = cse_basic_block (insn, val.last, val.path);
6051 if (cse_jumps_altered == 0 || flag_cse_follow_jumps)
6052 insn = temp;
6054 cse_jumps_altered |= old_cse_jumps_altered;
6058 /* Clean up. */
6059 end_alias_analysis ();
6060 free (uid_cuid);
6061 free (reg_eqv_table);
6062 free (val.path);
6063 rtl_hooks = general_rtl_hooks;
6065 return cse_jumps_altered || recorded_label_ref;
6068 /* Process a single basic block. FROM and TO and the limits of the basic
6069 block. NEXT_BRANCH points to the branch path when following jumps or
6070 a null path when not following jumps. */
6072 static rtx
6073 cse_basic_block (rtx from, rtx to, struct branch_path *next_branch)
6075 rtx insn;
6076 int to_usage = 0;
6077 rtx libcall_insn = NULL_RTX;
6078 int num_insns = 0;
6079 int no_conflict = 0;
6081 /* Allocate the space needed by qty_table. */
6082 qty_table = XNEWVEC (struct qty_table_elem, max_qty);
6084 new_basic_block ();
6086 /* TO might be a label. If so, protect it from being deleted. */
6087 if (to != 0 && LABEL_P (to))
6088 ++LABEL_NUSES (to);
6090 for (insn = from; insn != to; insn = NEXT_INSN (insn))
6092 enum rtx_code code = GET_CODE (insn);
6094 /* If we have processed 1,000 insns, flush the hash table to
6095 avoid extreme quadratic behavior. We must not include NOTEs
6096 in the count since there may be more of them when generating
6097 debugging information. If we clear the table at different
6098 times, code generated with -g -O might be different than code
6099 generated with -O but not -g.
6101 ??? This is a real kludge and needs to be done some other way.
6102 Perhaps for 2.9. */
6103 if (code != NOTE && num_insns++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS))
6105 flush_hash_table ();
6106 num_insns = 0;
6109 /* See if this is a branch that is part of the path. If so, and it is
6110 to be taken, do so. */
6111 if (next_branch->branch == insn)
6113 enum taken status = next_branch++->status;
6114 if (status != PATH_NOT_TAKEN)
6116 gcc_assert (status == PATH_TAKEN);
6117 if (any_condjump_p (insn))
6118 record_jump_equiv (insn, true);
6120 /* Set the last insn as the jump insn; it doesn't affect cc0.
6121 Then follow this branch. */
6122 #ifdef HAVE_cc0
6123 prev_insn_cc0 = 0;
6124 prev_insn = insn;
6125 #endif
6126 insn = JUMP_LABEL (insn);
6127 continue;
6131 if (GET_MODE (insn) == QImode)
6132 PUT_MODE (insn, VOIDmode);
6134 if (GET_RTX_CLASS (code) == RTX_INSN)
6136 rtx p;
6138 /* Process notes first so we have all notes in canonical forms when
6139 looking for duplicate operations. */
6141 if (REG_NOTES (insn))
6142 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
6144 /* Track when we are inside in LIBCALL block. Inside such a block,
6145 we do not want to record destinations. The last insn of a
6146 LIBCALL block is not considered to be part of the block, since
6147 its destination is the result of the block and hence should be
6148 recorded. */
6150 if (REG_NOTES (insn) != 0)
6152 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
6153 libcall_insn = XEXP (p, 0);
6154 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
6156 /* Keep libcall_insn for the last SET insn of a no-conflict
6157 block to prevent changing the destination. */
6158 if (! no_conflict)
6159 libcall_insn = 0;
6160 else
6161 no_conflict = -1;
6163 else if (find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
6164 no_conflict = 1;
6167 cse_insn (insn, libcall_insn);
6169 if (no_conflict == -1)
6171 libcall_insn = 0;
6172 no_conflict = 0;
6175 /* If we haven't already found an insn where we added a LABEL_REF,
6176 check this one. */
6177 if (NONJUMP_INSN_P (insn) && ! recorded_label_ref
6178 && for_each_rtx (&PATTERN (insn), check_for_label_ref,
6179 (void *) insn))
6180 recorded_label_ref = 1;
6183 /* If INSN is now an unconditional jump, skip to the end of our
6184 basic block by pretending that we just did the last insn in the
6185 basic block. If we are jumping to the end of our block, show
6186 that we can have one usage of TO. */
6188 if (any_uncondjump_p (insn))
6190 if (to == 0)
6192 free (qty_table);
6193 return 0;
6196 if (JUMP_LABEL (insn) == to)
6197 to_usage = 1;
6199 /* Maybe TO was deleted because the jump is unconditional.
6200 If so, there is nothing left in this basic block. */
6201 /* ??? Perhaps it would be smarter to set TO
6202 to whatever follows this insn,
6203 and pretend the basic block had always ended here. */
6204 if (INSN_DELETED_P (to))
6205 break;
6207 insn = PREV_INSN (to);
6211 gcc_assert (next_qty <= max_qty);
6213 free (qty_table);
6215 return to ? NEXT_INSN (to) : 0;
6218 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
6219 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
6221 static int
6222 check_for_label_ref (rtx *rtl, void *data)
6224 rtx insn = (rtx) data;
6226 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
6227 we must rerun jump since it needs to place the note. If this is a
6228 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
6229 since no REG_LABEL will be added. */
6230 return (GET_CODE (*rtl) == LABEL_REF
6231 && ! LABEL_REF_NONLOCAL_P (*rtl)
6232 && LABEL_P (XEXP (*rtl, 0))
6233 && INSN_UID (XEXP (*rtl, 0)) != 0
6234 && ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)));
6237 /* Count the number of times registers are used (not set) in X.
6238 COUNTS is an array in which we accumulate the count, INCR is how much
6239 we count each register usage.
6241 Don't count a usage of DEST, which is the SET_DEST of a SET which
6242 contains X in its SET_SRC. This is because such a SET does not
6243 modify the liveness of DEST.
6244 DEST is set to pc_rtx for a trapping insn, which means that we must count
6245 uses of a SET_DEST regardless because the insn can't be deleted here. */
6247 static void
6248 count_reg_usage (rtx x, int *counts, rtx dest, int incr)
6250 enum rtx_code code;
6251 rtx note;
6252 const char *fmt;
6253 int i, j;
6255 if (x == 0)
6256 return;
6258 switch (code = GET_CODE (x))
6260 case REG:
6261 if (x != dest)
6262 counts[REGNO (x)] += incr;
6263 return;
6265 case PC:
6266 case CC0:
6267 case CONST:
6268 case CONST_INT:
6269 case CONST_DOUBLE:
6270 case CONST_VECTOR:
6271 case SYMBOL_REF:
6272 case LABEL_REF:
6273 return;
6275 case CLOBBER:
6276 /* If we are clobbering a MEM, mark any registers inside the address
6277 as being used. */
6278 if (MEM_P (XEXP (x, 0)))
6279 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
6280 return;
6282 case SET:
6283 /* Unless we are setting a REG, count everything in SET_DEST. */
6284 if (!REG_P (SET_DEST (x)))
6285 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
6286 count_reg_usage (SET_SRC (x), counts,
6287 dest ? dest : SET_DEST (x),
6288 incr);
6289 return;
6291 case CALL_INSN:
6292 case INSN:
6293 case JUMP_INSN:
6294 /* We expect dest to be NULL_RTX here. If the insn may trap, mark
6295 this fact by setting DEST to pc_rtx. */
6296 if (flag_non_call_exceptions && may_trap_p (PATTERN (x)))
6297 dest = pc_rtx;
6298 if (code == CALL_INSN)
6299 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, dest, incr);
6300 count_reg_usage (PATTERN (x), counts, dest, incr);
6302 /* Things used in a REG_EQUAL note aren't dead since loop may try to
6303 use them. */
6305 note = find_reg_equal_equiv_note (x);
6306 if (note)
6308 rtx eqv = XEXP (note, 0);
6310 if (GET_CODE (eqv) == EXPR_LIST)
6311 /* This REG_EQUAL note describes the result of a function call.
6312 Process all the arguments. */
6315 count_reg_usage (XEXP (eqv, 0), counts, dest, incr);
6316 eqv = XEXP (eqv, 1);
6318 while (eqv && GET_CODE (eqv) == EXPR_LIST);
6319 else
6320 count_reg_usage (eqv, counts, dest, incr);
6322 return;
6324 case EXPR_LIST:
6325 if (REG_NOTE_KIND (x) == REG_EQUAL
6326 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE)
6327 /* FUNCTION_USAGE expression lists may include (CLOBBER (mem /u)),
6328 involving registers in the address. */
6329 || GET_CODE (XEXP (x, 0)) == CLOBBER)
6330 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
6332 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
6333 return;
6335 case ASM_OPERANDS:
6336 /* If the asm is volatile, then this insn cannot be deleted,
6337 and so the inputs *must* be live. */
6338 if (MEM_VOLATILE_P (x))
6339 dest = NULL_RTX;
6340 /* Iterate over just the inputs, not the constraints as well. */
6341 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
6342 count_reg_usage (ASM_OPERANDS_INPUT (x, i), counts, dest, incr);
6343 return;
6345 case INSN_LIST:
6346 gcc_unreachable ();
6348 default:
6349 break;
6352 fmt = GET_RTX_FORMAT (code);
6353 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
6355 if (fmt[i] == 'e')
6356 count_reg_usage (XEXP (x, i), counts, dest, incr);
6357 else if (fmt[i] == 'E')
6358 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6359 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
6363 /* Return true if set is live. */
6364 static bool
6365 set_live_p (rtx set, rtx insn ATTRIBUTE_UNUSED, /* Only used with HAVE_cc0. */
6366 int *counts)
6368 #ifdef HAVE_cc0
6369 rtx tem;
6370 #endif
6372 if (set_noop_p (set))
6375 #ifdef HAVE_cc0
6376 else if (GET_CODE (SET_DEST (set)) == CC0
6377 && !side_effects_p (SET_SRC (set))
6378 && ((tem = next_nonnote_insn (insn)) == 0
6379 || !INSN_P (tem)
6380 || !reg_referenced_p (cc0_rtx, PATTERN (tem))))
6381 return false;
6382 #endif
6383 else if (!REG_P (SET_DEST (set))
6384 || REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
6385 || counts[REGNO (SET_DEST (set))] != 0
6386 || side_effects_p (SET_SRC (set)))
6387 return true;
6388 return false;
6391 /* Return true if insn is live. */
6393 static bool
6394 insn_live_p (rtx insn, int *counts)
6396 int i;
6397 if (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
6398 return true;
6399 else if (GET_CODE (PATTERN (insn)) == SET)
6400 return set_live_p (PATTERN (insn), insn, counts);
6401 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
6403 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6405 rtx elt = XVECEXP (PATTERN (insn), 0, i);
6407 if (GET_CODE (elt) == SET)
6409 if (set_live_p (elt, insn, counts))
6410 return true;
6412 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
6413 return true;
6415 return false;
6417 else
6418 return true;
6421 /* Return true if libcall is dead as a whole. */
6423 static bool
6424 dead_libcall_p (rtx insn, int *counts)
6426 rtx note, set, new;
6428 /* See if there's a REG_EQUAL note on this insn and try to
6429 replace the source with the REG_EQUAL expression.
6431 We assume that insns with REG_RETVALs can only be reg->reg
6432 copies at this point. */
6433 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6434 if (!note)
6435 return false;
6437 set = single_set (insn);
6438 if (!set)
6439 return false;
6441 new = simplify_rtx (XEXP (note, 0));
6442 if (!new)
6443 new = XEXP (note, 0);
6445 /* While changing insn, we must update the counts accordingly. */
6446 count_reg_usage (insn, counts, NULL_RTX, -1);
6448 if (validate_change (insn, &SET_SRC (set), new, 0))
6450 count_reg_usage (insn, counts, NULL_RTX, 1);
6451 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
6452 remove_note (insn, note);
6453 return true;
6456 if (CONSTANT_P (new))
6458 new = force_const_mem (GET_MODE (SET_DEST (set)), new);
6459 if (new && validate_change (insn, &SET_SRC (set), new, 0))
6461 count_reg_usage (insn, counts, NULL_RTX, 1);
6462 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
6463 remove_note (insn, note);
6464 return true;
6468 count_reg_usage (insn, counts, NULL_RTX, 1);
6469 return false;
6472 /* Scan all the insns and delete any that are dead; i.e., they store a register
6473 that is never used or they copy a register to itself.
6475 This is used to remove insns made obviously dead by cse, loop or other
6476 optimizations. It improves the heuristics in loop since it won't try to
6477 move dead invariants out of loops or make givs for dead quantities. The
6478 remaining passes of the compilation are also sped up. */
6481 delete_trivially_dead_insns (rtx insns, int nreg)
6483 int *counts;
6484 rtx insn, prev;
6485 int in_libcall = 0, dead_libcall = 0;
6486 int ndead = 0;
6488 timevar_push (TV_DELETE_TRIVIALLY_DEAD);
6489 /* First count the number of times each register is used. */
6490 counts = XCNEWVEC (int, nreg);
6491 for (insn = insns; insn; insn = NEXT_INSN (insn))
6492 if (INSN_P (insn))
6493 count_reg_usage (insn, counts, NULL_RTX, 1);
6495 /* Go from the last insn to the first and delete insns that only set unused
6496 registers or copy a register to itself. As we delete an insn, remove
6497 usage counts for registers it uses.
6499 The first jump optimization pass may leave a real insn as the last
6500 insn in the function. We must not skip that insn or we may end
6501 up deleting code that is not really dead. */
6502 for (insn = get_last_insn (); insn; insn = prev)
6504 int live_insn = 0;
6506 prev = PREV_INSN (insn);
6507 if (!INSN_P (insn))
6508 continue;
6510 /* Don't delete any insns that are part of a libcall block unless
6511 we can delete the whole libcall block.
6513 Flow or loop might get confused if we did that. Remember
6514 that we are scanning backwards. */
6515 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
6517 in_libcall = 1;
6518 live_insn = 1;
6519 dead_libcall = dead_libcall_p (insn, counts);
6521 else if (in_libcall)
6522 live_insn = ! dead_libcall;
6523 else
6524 live_insn = insn_live_p (insn, counts);
6526 /* If this is a dead insn, delete it and show registers in it aren't
6527 being used. */
6529 if (! live_insn)
6531 count_reg_usage (insn, counts, NULL_RTX, -1);
6532 delete_insn_and_edges (insn);
6533 ndead++;
6536 if (in_libcall && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
6538 in_libcall = 0;
6539 dead_libcall = 0;
6543 if (dump_file && ndead)
6544 fprintf (dump_file, "Deleted %i trivially dead insns\n",
6545 ndead);
6546 /* Clean up. */
6547 free (counts);
6548 timevar_pop (TV_DELETE_TRIVIALLY_DEAD);
6549 return ndead;
6552 /* This function is called via for_each_rtx. The argument, NEWREG, is
6553 a condition code register with the desired mode. If we are looking
6554 at the same register in a different mode, replace it with
6555 NEWREG. */
6557 static int
6558 cse_change_cc_mode (rtx *loc, void *data)
6560 struct change_cc_mode_args* args = (struct change_cc_mode_args*)data;
6562 if (*loc
6563 && REG_P (*loc)
6564 && REGNO (*loc) == REGNO (args->newreg)
6565 && GET_MODE (*loc) != GET_MODE (args->newreg))
6567 validate_change (args->insn, loc, args->newreg, 1);
6569 return -1;
6571 return 0;
6574 /* Change the mode of any reference to the register REGNO (NEWREG) to
6575 GET_MODE (NEWREG) in INSN. */
6577 static void
6578 cse_change_cc_mode_insn (rtx insn, rtx newreg)
6580 struct change_cc_mode_args args;
6581 int success;
6583 if (!INSN_P (insn))
6584 return;
6586 args.insn = insn;
6587 args.newreg = newreg;
6589 for_each_rtx (&PATTERN (insn), cse_change_cc_mode, &args);
6590 for_each_rtx (&REG_NOTES (insn), cse_change_cc_mode, &args);
6592 /* If the following assertion was triggered, there is most probably
6593 something wrong with the cc_modes_compatible back end function.
6594 CC modes only can be considered compatible if the insn - with the mode
6595 replaced by any of the compatible modes - can still be recognized. */
6596 success = apply_change_group ();
6597 gcc_assert (success);
6600 /* Change the mode of any reference to the register REGNO (NEWREG) to
6601 GET_MODE (NEWREG), starting at START. Stop before END. Stop at
6602 any instruction which modifies NEWREG. */
6604 static void
6605 cse_change_cc_mode_insns (rtx start, rtx end, rtx newreg)
6607 rtx insn;
6609 for (insn = start; insn != end; insn = NEXT_INSN (insn))
6611 if (! INSN_P (insn))
6612 continue;
6614 if (reg_set_p (newreg, insn))
6615 return;
6617 cse_change_cc_mode_insn (insn, newreg);
6621 /* BB is a basic block which finishes with CC_REG as a condition code
6622 register which is set to CC_SRC. Look through the successors of BB
6623 to find blocks which have a single predecessor (i.e., this one),
6624 and look through those blocks for an assignment to CC_REG which is
6625 equivalent to CC_SRC. CAN_CHANGE_MODE indicates whether we are
6626 permitted to change the mode of CC_SRC to a compatible mode. This
6627 returns VOIDmode if no equivalent assignments were found.
6628 Otherwise it returns the mode which CC_SRC should wind up with.
6630 The main complexity in this function is handling the mode issues.
6631 We may have more than one duplicate which we can eliminate, and we
6632 try to find a mode which will work for multiple duplicates. */
6634 static enum machine_mode
6635 cse_cc_succs (basic_block bb, rtx cc_reg, rtx cc_src, bool can_change_mode)
6637 bool found_equiv;
6638 enum machine_mode mode;
6639 unsigned int insn_count;
6640 edge e;
6641 rtx insns[2];
6642 enum machine_mode modes[2];
6643 rtx last_insns[2];
6644 unsigned int i;
6645 rtx newreg;
6646 edge_iterator ei;
6648 /* We expect to have two successors. Look at both before picking
6649 the final mode for the comparison. If we have more successors
6650 (i.e., some sort of table jump, although that seems unlikely),
6651 then we require all beyond the first two to use the same
6652 mode. */
6654 found_equiv = false;
6655 mode = GET_MODE (cc_src);
6656 insn_count = 0;
6657 FOR_EACH_EDGE (e, ei, bb->succs)
6659 rtx insn;
6660 rtx end;
6662 if (e->flags & EDGE_COMPLEX)
6663 continue;
6665 if (EDGE_COUNT (e->dest->preds) != 1
6666 || e->dest == EXIT_BLOCK_PTR)
6667 continue;
6669 end = NEXT_INSN (BB_END (e->dest));
6670 for (insn = BB_HEAD (e->dest); insn != end; insn = NEXT_INSN (insn))
6672 rtx set;
6674 if (! INSN_P (insn))
6675 continue;
6677 /* If CC_SRC is modified, we have to stop looking for
6678 something which uses it. */
6679 if (modified_in_p (cc_src, insn))
6680 break;
6682 /* Check whether INSN sets CC_REG to CC_SRC. */
6683 set = single_set (insn);
6684 if (set
6685 && REG_P (SET_DEST (set))
6686 && REGNO (SET_DEST (set)) == REGNO (cc_reg))
6688 bool found;
6689 enum machine_mode set_mode;
6690 enum machine_mode comp_mode;
6692 found = false;
6693 set_mode = GET_MODE (SET_SRC (set));
6694 comp_mode = set_mode;
6695 if (rtx_equal_p (cc_src, SET_SRC (set)))
6696 found = true;
6697 else if (GET_CODE (cc_src) == COMPARE
6698 && GET_CODE (SET_SRC (set)) == COMPARE
6699 && mode != set_mode
6700 && rtx_equal_p (XEXP (cc_src, 0),
6701 XEXP (SET_SRC (set), 0))
6702 && rtx_equal_p (XEXP (cc_src, 1),
6703 XEXP (SET_SRC (set), 1)))
6706 comp_mode = targetm.cc_modes_compatible (mode, set_mode);
6707 if (comp_mode != VOIDmode
6708 && (can_change_mode || comp_mode == mode))
6709 found = true;
6712 if (found)
6714 found_equiv = true;
6715 if (insn_count < ARRAY_SIZE (insns))
6717 insns[insn_count] = insn;
6718 modes[insn_count] = set_mode;
6719 last_insns[insn_count] = end;
6720 ++insn_count;
6722 if (mode != comp_mode)
6724 gcc_assert (can_change_mode);
6725 mode = comp_mode;
6727 /* The modified insn will be re-recognized later. */
6728 PUT_MODE (cc_src, mode);
6731 else
6733 if (set_mode != mode)
6735 /* We found a matching expression in the
6736 wrong mode, but we don't have room to
6737 store it in the array. Punt. This case
6738 should be rare. */
6739 break;
6741 /* INSN sets CC_REG to a value equal to CC_SRC
6742 with the right mode. We can simply delete
6743 it. */
6744 delete_insn (insn);
6747 /* We found an instruction to delete. Keep looking,
6748 in the hopes of finding a three-way jump. */
6749 continue;
6752 /* We found an instruction which sets the condition
6753 code, so don't look any farther. */
6754 break;
6757 /* If INSN sets CC_REG in some other way, don't look any
6758 farther. */
6759 if (reg_set_p (cc_reg, insn))
6760 break;
6763 /* If we fell off the bottom of the block, we can keep looking
6764 through successors. We pass CAN_CHANGE_MODE as false because
6765 we aren't prepared to handle compatibility between the
6766 further blocks and this block. */
6767 if (insn == end)
6769 enum machine_mode submode;
6771 submode = cse_cc_succs (e->dest, cc_reg, cc_src, false);
6772 if (submode != VOIDmode)
6774 gcc_assert (submode == mode);
6775 found_equiv = true;
6776 can_change_mode = false;
6781 if (! found_equiv)
6782 return VOIDmode;
6784 /* Now INSN_COUNT is the number of instructions we found which set
6785 CC_REG to a value equivalent to CC_SRC. The instructions are in
6786 INSNS. The modes used by those instructions are in MODES. */
6788 newreg = NULL_RTX;
6789 for (i = 0; i < insn_count; ++i)
6791 if (modes[i] != mode)
6793 /* We need to change the mode of CC_REG in INSNS[i] and
6794 subsequent instructions. */
6795 if (! newreg)
6797 if (GET_MODE (cc_reg) == mode)
6798 newreg = cc_reg;
6799 else
6800 newreg = gen_rtx_REG (mode, REGNO (cc_reg));
6802 cse_change_cc_mode_insns (NEXT_INSN (insns[i]), last_insns[i],
6803 newreg);
6806 delete_insn (insns[i]);
6809 return mode;
6812 /* If we have a fixed condition code register (or two), walk through
6813 the instructions and try to eliminate duplicate assignments. */
6815 static void
6816 cse_condition_code_reg (void)
6818 unsigned int cc_regno_1;
6819 unsigned int cc_regno_2;
6820 rtx cc_reg_1;
6821 rtx cc_reg_2;
6822 basic_block bb;
6824 if (! targetm.fixed_condition_code_regs (&cc_regno_1, &cc_regno_2))
6825 return;
6827 cc_reg_1 = gen_rtx_REG (CCmode, cc_regno_1);
6828 if (cc_regno_2 != INVALID_REGNUM)
6829 cc_reg_2 = gen_rtx_REG (CCmode, cc_regno_2);
6830 else
6831 cc_reg_2 = NULL_RTX;
6833 FOR_EACH_BB (bb)
6835 rtx last_insn;
6836 rtx cc_reg;
6837 rtx insn;
6838 rtx cc_src_insn;
6839 rtx cc_src;
6840 enum machine_mode mode;
6841 enum machine_mode orig_mode;
6843 /* Look for blocks which end with a conditional jump based on a
6844 condition code register. Then look for the instruction which
6845 sets the condition code register. Then look through the
6846 successor blocks for instructions which set the condition
6847 code register to the same value. There are other possible
6848 uses of the condition code register, but these are by far the
6849 most common and the ones which we are most likely to be able
6850 to optimize. */
6852 last_insn = BB_END (bb);
6853 if (!JUMP_P (last_insn))
6854 continue;
6856 if (reg_referenced_p (cc_reg_1, PATTERN (last_insn)))
6857 cc_reg = cc_reg_1;
6858 else if (cc_reg_2 && reg_referenced_p (cc_reg_2, PATTERN (last_insn)))
6859 cc_reg = cc_reg_2;
6860 else
6861 continue;
6863 cc_src_insn = NULL_RTX;
6864 cc_src = NULL_RTX;
6865 for (insn = PREV_INSN (last_insn);
6866 insn && insn != PREV_INSN (BB_HEAD (bb));
6867 insn = PREV_INSN (insn))
6869 rtx set;
6871 if (! INSN_P (insn))
6872 continue;
6873 set = single_set (insn);
6874 if (set
6875 && REG_P (SET_DEST (set))
6876 && REGNO (SET_DEST (set)) == REGNO (cc_reg))
6878 cc_src_insn = insn;
6879 cc_src = SET_SRC (set);
6880 break;
6882 else if (reg_set_p (cc_reg, insn))
6883 break;
6886 if (! cc_src_insn)
6887 continue;
6889 if (modified_between_p (cc_src, cc_src_insn, NEXT_INSN (last_insn)))
6890 continue;
6892 /* Now CC_REG is a condition code register used for a
6893 conditional jump at the end of the block, and CC_SRC, in
6894 CC_SRC_INSN, is the value to which that condition code
6895 register is set, and CC_SRC is still meaningful at the end of
6896 the basic block. */
6898 orig_mode = GET_MODE (cc_src);
6899 mode = cse_cc_succs (bb, cc_reg, cc_src, true);
6900 if (mode != VOIDmode)
6902 gcc_assert (mode == GET_MODE (cc_src));
6903 if (mode != orig_mode)
6905 rtx newreg = gen_rtx_REG (mode, REGNO (cc_reg));
6907 cse_change_cc_mode_insn (cc_src_insn, newreg);
6909 /* Do the same in the following insns that use the
6910 current value of CC_REG within BB. */
6911 cse_change_cc_mode_insns (NEXT_INSN (cc_src_insn),
6912 NEXT_INSN (last_insn),
6913 newreg);
6920 /* Perform common subexpression elimination. Nonzero value from
6921 `cse_main' means that jumps were simplified and some code may now
6922 be unreachable, so do jump optimization again. */
6923 static bool
6924 gate_handle_cse (void)
6926 return optimize > 0;
6929 static unsigned int
6930 rest_of_handle_cse (void)
6932 int tem;
6934 if (dump_file)
6935 dump_flow_info (dump_file, dump_flags);
6937 reg_scan (get_insns (), max_reg_num ());
6939 tem = cse_main (get_insns (), max_reg_num ());
6940 if (tem)
6941 rebuild_jump_labels (get_insns ());
6942 if (purge_all_dead_edges ())
6943 delete_unreachable_blocks ();
6945 delete_trivially_dead_insns (get_insns (), max_reg_num ());
6947 /* If we are not running more CSE passes, then we are no longer
6948 expecting CSE to be run. But always rerun it in a cheap mode. */
6949 cse_not_expected = !flag_rerun_cse_after_loop && !flag_gcse;
6951 if (tem)
6952 delete_dead_jumptables ();
6954 if (tem || optimize > 1)
6955 cleanup_cfg (CLEANUP_EXPENSIVE);
6956 return 0;
6959 struct tree_opt_pass pass_cse =
6961 "cse1", /* name */
6962 gate_handle_cse, /* gate */
6963 rest_of_handle_cse, /* execute */
6964 NULL, /* sub */
6965 NULL, /* next */
6966 0, /* static_pass_number */
6967 TV_CSE, /* tv_id */
6968 0, /* properties_required */
6969 0, /* properties_provided */
6970 0, /* properties_destroyed */
6971 0, /* todo_flags_start */
6972 TODO_dump_func |
6973 TODO_ggc_collect, /* todo_flags_finish */
6974 's' /* letter */
6978 static bool
6979 gate_handle_cse2 (void)
6981 return optimize > 0 && flag_rerun_cse_after_loop;
6984 /* Run second CSE pass after loop optimizations. */
6985 static unsigned int
6986 rest_of_handle_cse2 (void)
6988 int tem;
6990 if (dump_file)
6991 dump_flow_info (dump_file, dump_flags);
6993 tem = cse_main (get_insns (), max_reg_num ());
6995 /* Run a pass to eliminate duplicated assignments to condition code
6996 registers. We have to run this after bypass_jumps, because it
6997 makes it harder for that pass to determine whether a jump can be
6998 bypassed safely. */
6999 cse_condition_code_reg ();
7001 purge_all_dead_edges ();
7002 delete_trivially_dead_insns (get_insns (), max_reg_num ());
7004 if (tem)
7006 timevar_push (TV_JUMP);
7007 rebuild_jump_labels (get_insns ());
7008 delete_dead_jumptables ();
7009 cleanup_cfg (CLEANUP_EXPENSIVE);
7010 timevar_pop (TV_JUMP);
7012 reg_scan (get_insns (), max_reg_num ());
7013 cse_not_expected = 1;
7014 return 0;
7018 struct tree_opt_pass pass_cse2 =
7020 "cse2", /* name */
7021 gate_handle_cse2, /* gate */
7022 rest_of_handle_cse2, /* execute */
7023 NULL, /* sub */
7024 NULL, /* next */
7025 0, /* static_pass_number */
7026 TV_CSE2, /* tv_id */
7027 0, /* properties_required */
7028 0, /* properties_provided */
7029 0, /* properties_destroyed */
7030 0, /* todo_flags_start */
7031 TODO_dump_func |
7032 TODO_ggc_collect, /* todo_flags_finish */
7033 't' /* letter */