1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 /* stdio.h must precede rtl.h for FFS. */
26 #include "coretypes.h"
30 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "insn-config.h"
46 #include "rtlhooks-def.h"
47 #include "tree-pass.h"
49 /* The basic idea of common subexpression elimination is to go
50 through the code, keeping a record of expressions that would
51 have the same value at the current scan point, and replacing
52 expressions encountered with the cheapest equivalent expression.
54 It is too complicated to keep track of the different possibilities
55 when control paths merge in this code; so, at each label, we forget all
56 that is known and start fresh. This can be described as processing each
57 extended basic block separately. We have a separate pass to perform
60 Note CSE can turn a conditional or computed jump into a nop or
61 an unconditional jump. When this occurs we arrange to run the jump
62 optimizer after CSE to delete the unreachable code.
64 We use two data structures to record the equivalent expressions:
65 a hash table for most expressions, and a vector of "quantity
66 numbers" to record equivalent (pseudo) registers.
68 The use of the special data structure for registers is desirable
69 because it is faster. It is possible because registers references
70 contain a fairly small number, the register number, taken from
71 a contiguously allocated series, and two register references are
72 identical if they have the same number. General expressions
73 do not have any such thing, so the only way to retrieve the
74 information recorded on an expression other than a register
75 is to keep it in a hash table.
77 Registers and "quantity numbers":
79 At the start of each basic block, all of the (hardware and pseudo)
80 registers used in the function are given distinct quantity
81 numbers to indicate their contents. During scan, when the code
82 copies one register into another, we copy the quantity number.
83 When a register is loaded in any other way, we allocate a new
84 quantity number to describe the value generated by this operation.
85 `REG_QTY (N)' records what quantity register N is currently thought
88 All real quantity numbers are greater than or equal to zero.
89 If register N has not been assigned a quantity, `REG_QTY (N)' will
90 equal -N - 1, which is always negative.
92 Quantity numbers below zero do not exist and none of the `qty_table'
93 entries should be referenced with a negative index.
95 We also maintain a bidirectional chain of registers for each
96 quantity number. The `qty_table` members `first_reg' and `last_reg',
97 and `reg_eqv_table' members `next' and `prev' hold these chains.
99 The first register in a chain is the one whose lifespan is least local.
100 Among equals, it is the one that was seen first.
101 We replace any equivalent register with that one.
103 If two registers have the same quantity number, it must be true that
104 REG expressions with qty_table `mode' must be in the hash table for both
105 registers and must be in the same class.
107 The converse is not true. Since hard registers may be referenced in
108 any mode, two REG expressions might be equivalent in the hash table
109 but not have the same quantity number if the quantity number of one
110 of the registers is not the same mode as those expressions.
112 Constants and quantity numbers
114 When a quantity has a known constant value, that value is stored
115 in the appropriate qty_table `const_rtx'. This is in addition to
116 putting the constant in the hash table as is usual for non-regs.
118 Whether a reg or a constant is preferred is determined by the configuration
119 macro CONST_COSTS and will often depend on the constant value. In any
120 event, expressions containing constants can be simplified, by fold_rtx.
122 When a quantity has a known nearly constant value (such as an address
123 of a stack slot), that value is stored in the appropriate qty_table
126 Integer constants don't have a machine mode. However, cse
127 determines the intended machine mode from the destination
128 of the instruction that moves the constant. The machine mode
129 is recorded in the hash table along with the actual RTL
130 constant expression so that different modes are kept separate.
134 To record known equivalences among expressions in general
135 we use a hash table called `table'. It has a fixed number of buckets
136 that contain chains of `struct table_elt' elements for expressions.
137 These chains connect the elements whose expressions have the same
140 Other chains through the same elements connect the elements which
141 currently have equivalent values.
143 Register references in an expression are canonicalized before hashing
144 the expression. This is done using `reg_qty' and qty_table `first_reg'.
145 The hash code of a register reference is computed using the quantity
146 number, not the register number.
148 When the value of an expression changes, it is necessary to remove from the
149 hash table not just that expression but all expressions whose values
150 could be different as a result.
152 1. If the value changing is in memory, except in special cases
153 ANYTHING referring to memory could be changed. That is because
154 nobody knows where a pointer does not point.
155 The function `invalidate_memory' removes what is necessary.
157 The special cases are when the address is constant or is
158 a constant plus a fixed register such as the frame pointer
159 or a static chain pointer. When such addresses are stored in,
160 we can tell exactly which other such addresses must be invalidated
161 due to overlap. `invalidate' does this.
162 All expressions that refer to non-constant
163 memory addresses are also invalidated. `invalidate_memory' does this.
165 2. If the value changing is a register, all expressions
166 containing references to that register, and only those,
169 Because searching the entire hash table for expressions that contain
170 a register is very slow, we try to figure out when it isn't necessary.
171 Precisely, this is necessary only when expressions have been
172 entered in the hash table using this register, and then the value has
173 changed, and then another expression wants to be added to refer to
174 the register's new value. This sequence of circumstances is rare
175 within any one basic block.
177 `REG_TICK' and `REG_IN_TABLE', accessors for members of
178 cse_reg_info, are used to detect this case. REG_TICK (i) is
179 incremented whenever a value is stored in register i.
180 REG_IN_TABLE (i) holds -1 if no references to register i have been
181 entered in the table; otherwise, it contains the value REG_TICK (i)
182 had when the references were entered. If we want to enter a
183 reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and
184 remove old references. Until we want to enter a new entry, the
185 mere fact that the two vectors don't match makes the entries be
186 ignored if anyone tries to match them.
188 Registers themselves are entered in the hash table as well as in
189 the equivalent-register chains. However, `REG_TICK' and
190 `REG_IN_TABLE' do not apply to expressions which are simple
191 register references. These expressions are removed from the table
192 immediately when they become invalid, and this can be done even if
193 we do not immediately search for all the expressions that refer to
196 A CLOBBER rtx in an instruction invalidates its operand for further
197 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
198 invalidates everything that resides in memory.
202 Constant expressions that differ only by an additive integer
203 are called related. When a constant expression is put in
204 the table, the related expression with no constant term
205 is also entered. These are made to point at each other
206 so that it is possible to find out if there exists any
207 register equivalent to an expression related to a given expression. */
209 /* Length of qty_table vector. We know in advance we will not need
210 a quantity number this big. */
214 /* Next quantity number to be allocated.
215 This is 1 + the largest number needed so far. */
219 /* Per-qty information tracking.
221 `first_reg' and `last_reg' track the head and tail of the
222 chain of registers which currently contain this quantity.
224 `mode' contains the machine mode of this quantity.
226 `const_rtx' holds the rtx of the constant value of this
227 quantity, if known. A summations of the frame/arg pointer
228 and a constant can also be entered here. When this holds
229 a known value, `const_insn' is the insn which stored the
232 `comparison_{code,const,qty}' are used to track when a
233 comparison between a quantity and some constant or register has
234 been passed. In such a case, we know the results of the comparison
235 in case we see it again. These members record a comparison that
236 is known to be true. `comparison_code' holds the rtx code of such
237 a comparison, else it is set to UNKNOWN and the other two
238 comparison members are undefined. `comparison_const' holds
239 the constant being compared against, or zero if the comparison
240 is not against a constant. `comparison_qty' holds the quantity
241 being compared against when the result is known. If the comparison
242 is not with a register, `comparison_qty' is -1. */
244 struct qty_table_elem
248 rtx comparison_const;
250 unsigned int first_reg, last_reg;
251 /* The sizes of these fields should match the sizes of the
252 code and mode fields of struct rtx_def (see rtl.h). */
253 ENUM_BITFIELD(rtx_code) comparison_code : 16;
254 ENUM_BITFIELD(machine_mode) mode : 8;
257 /* The table of all qtys, indexed by qty number. */
258 static struct qty_table_elem *qty_table;
260 /* Structure used to pass arguments via for_each_rtx to function
261 cse_change_cc_mode. */
262 struct change_cc_mode_args
269 /* For machines that have a CC0, we do not record its value in the hash
270 table since its use is guaranteed to be the insn immediately following
271 its definition and any other insn is presumed to invalidate it.
273 Instead, we store below the current and last value assigned to CC0.
274 If it should happen to be a constant, it is stored in preference
275 to the actual assigned value. In case it is a constant, we store
276 the mode in which the constant should be interpreted. */
278 static rtx this_insn_cc0, prev_insn_cc0;
279 static enum machine_mode this_insn_cc0_mode, prev_insn_cc0_mode;
282 /* Insn being scanned. */
284 static rtx this_insn;
286 /* Index by register number, gives the number of the next (or
287 previous) register in the chain of registers sharing the same
290 Or -1 if this register is at the end of the chain.
292 If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined. */
294 /* Per-register equivalence chain. */
300 /* The table of all register equivalence chains. */
301 static struct reg_eqv_elem *reg_eqv_table;
305 /* The timestamp at which this register is initialized. */
306 unsigned int timestamp;
308 /* The quantity number of the register's current contents. */
311 /* The number of times the register has been altered in the current
315 /* The REG_TICK value at which rtx's containing this register are
316 valid in the hash table. If this does not equal the current
317 reg_tick value, such expressions existing in the hash table are
321 /* The SUBREG that was set when REG_TICK was last incremented. Set
322 to -1 if the last store was to the whole register, not a subreg. */
323 unsigned int subreg_ticked;
326 /* A table of cse_reg_info indexed by register numbers. */
327 static struct cse_reg_info *cse_reg_info_table;
329 /* The size of the above table. */
330 static unsigned int cse_reg_info_table_size;
332 /* The index of the first entry that has not been initialized. */
333 static unsigned int cse_reg_info_table_first_uninitialized;
335 /* The timestamp at the beginning of the current run of
336 cse_extended_basic_block. We increment this variable at the beginning of
337 the current run of cse_extended_basic_block. The timestamp field of a
338 cse_reg_info entry matches the value of this variable if and only
339 if the entry has been initialized during the current run of
340 cse_extended_basic_block. */
341 static unsigned int cse_reg_info_timestamp;
343 /* A HARD_REG_SET containing all the hard registers for which there is
344 currently a REG expression in the hash table. Note the difference
345 from the above variables, which indicate if the REG is mentioned in some
346 expression in the table. */
348 static HARD_REG_SET hard_regs_in_table;
350 /* CUID of insn that starts the basic block currently being cse-processed. */
352 static int cse_basic_block_start;
354 /* CUID of insn that ends the basic block currently being cse-processed. */
356 static int cse_basic_block_end;
358 /* Vector mapping INSN_UIDs to cuids.
359 The cuids are like uids but increase monotonically always.
360 We use them to see whether a reg is used outside a given basic block. */
362 static int *uid_cuid;
364 /* Highest UID in UID_CUID. */
367 /* Get the cuid of an insn. */
369 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
371 /* Nonzero if cse has altered conditional jump insns
372 in such a way that jump optimization should be redone. */
374 static int cse_jumps_altered;
376 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
377 REG_LABEL, we have to rerun jump after CSE to put in the note. */
378 static int recorded_label_ref;
380 /* canon_hash stores 1 in do_not_record
381 if it notices a reference to CC0, PC, or some other volatile
384 static int do_not_record;
386 /* canon_hash stores 1 in hash_arg_in_memory
387 if it notices a reference to memory within the expression being hashed. */
389 static int hash_arg_in_memory;
391 /* The hash table contains buckets which are chains of `struct table_elt's,
392 each recording one expression's information.
393 That expression is in the `exp' field.
395 The canon_exp field contains a canonical (from the point of view of
396 alias analysis) version of the `exp' field.
398 Those elements with the same hash code are chained in both directions
399 through the `next_same_hash' and `prev_same_hash' fields.
401 Each set of expressions with equivalent values
402 are on a two-way chain through the `next_same_value'
403 and `prev_same_value' fields, and all point with
404 the `first_same_value' field at the first element in
405 that chain. The chain is in order of increasing cost.
406 Each element's cost value is in its `cost' field.
408 The `in_memory' field is nonzero for elements that
409 involve any reference to memory. These elements are removed
410 whenever a write is done to an unidentified location in memory.
411 To be safe, we assume that a memory address is unidentified unless
412 the address is either a symbol constant or a constant plus
413 the frame pointer or argument pointer.
415 The `related_value' field is used to connect related expressions
416 (that differ by adding an integer).
417 The related expressions are chained in a circular fashion.
418 `related_value' is zero for expressions for which this
421 The `cost' field stores the cost of this element's expression.
422 The `regcost' field stores the value returned by approx_reg_cost for
423 this element's expression.
425 The `is_const' flag is set if the element is a constant (including
428 The `flag' field is used as a temporary during some search routines.
430 The `mode' field is usually the same as GET_MODE (`exp'), but
431 if `exp' is a CONST_INT and has no machine mode then the `mode'
432 field is the mode it was being used as. Each constant is
433 recorded separately for each mode it is used with. */
439 struct table_elt *next_same_hash;
440 struct table_elt *prev_same_hash;
441 struct table_elt *next_same_value;
442 struct table_elt *prev_same_value;
443 struct table_elt *first_same_value;
444 struct table_elt *related_value;
447 /* The size of this field should match the size
448 of the mode field of struct rtx_def (see rtl.h). */
449 ENUM_BITFIELD(machine_mode) mode : 8;
455 /* We don't want a lot of buckets, because we rarely have very many
456 things stored in the hash table, and a lot of buckets slows
457 down a lot of loops that happen frequently. */
459 #define HASH_SIZE (1 << HASH_SHIFT)
460 #define HASH_MASK (HASH_SIZE - 1)
462 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
463 register (hard registers may require `do_not_record' to be set). */
466 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
467 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
468 : canon_hash (X, M)) & HASH_MASK)
470 /* Like HASH, but without side-effects. */
471 #define SAFE_HASH(X, M) \
472 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
473 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
474 : safe_hash (X, M)) & HASH_MASK)
476 /* Determine whether register number N is considered a fixed register for the
477 purpose of approximating register costs.
478 It is desirable to replace other regs with fixed regs, to reduce need for
480 A reg wins if it is either the frame pointer or designated as fixed. */
481 #define FIXED_REGNO_P(N) \
482 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
483 || fixed_regs[N] || global_regs[N])
485 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
486 hard registers and pointers into the frame are the cheapest with a cost
487 of 0. Next come pseudos with a cost of one and other hard registers with
488 a cost of 2. Aside from these special cases, call `rtx_cost'. */
490 #define CHEAP_REGNO(N) \
491 (REGNO_PTR_FRAME_P(N) \
492 || (HARD_REGISTER_NUM_P (N) \
493 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
495 #define COST(X) (REG_P (X) ? 0 : notreg_cost (X, SET))
496 #define COST_IN(X,OUTER) (REG_P (X) ? 0 : notreg_cost (X, OUTER))
498 /* Get the number of times this register has been updated in this
501 #define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)
503 /* Get the point at which REG was recorded in the table. */
505 #define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)
507 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
510 #define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)
512 /* Get the quantity number for REG. */
514 #define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)
516 /* Determine if the quantity number for register X represents a valid index
517 into the qty_table. */
519 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
521 static struct table_elt *table[HASH_SIZE];
523 /* Chain of `struct table_elt's made so far for this function
524 but currently removed from the table. */
526 static struct table_elt *free_element_chain;
528 /* Set to the cost of a constant pool reference if one was found for a
529 symbolic constant. If this was found, it means we should try to
530 convert constants into constant pool entries if they don't fit in
533 static int constant_pool_entries_cost;
534 static int constant_pool_entries_regcost;
536 /* This data describes a block that will be processed by
537 cse_extended_basic_block. */
539 struct cse_basic_block_data
541 /* Lowest CUID value of insns in block. */
543 /* Highest CUID value of insns in block. */
545 /* Total number of SETs in block. */
547 /* Size of current branch path, if any. */
549 /* Current path, indicating which basic_blocks will be processed. */
552 /* The basic block for this path entry. */
557 /* A simple bitmap to track which basic blocks have been visited
558 already as part of an already processed extended basic block. */
559 static sbitmap cse_visited_basic_blocks;
561 static bool fixed_base_plus_p (rtx x);
562 static int notreg_cost (rtx, enum rtx_code);
563 static int approx_reg_cost_1 (rtx *, void *);
564 static int approx_reg_cost (rtx);
565 static int preferable (int, int, int, int);
566 static void new_basic_block (void);
567 static void make_new_qty (unsigned int, enum machine_mode);
568 static void make_regs_eqv (unsigned int, unsigned int);
569 static void delete_reg_equiv (unsigned int);
570 static int mention_regs (rtx);
571 static int insert_regs (rtx, struct table_elt *, int);
572 static void remove_from_table (struct table_elt *, unsigned);
573 static struct table_elt *lookup (rtx, unsigned, enum machine_mode);
574 static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);
575 static rtx lookup_as_function (rtx, enum rtx_code);
576 static struct table_elt *insert (rtx, struct table_elt *, unsigned,
578 static void merge_equiv_classes (struct table_elt *, struct table_elt *);
579 static void invalidate (rtx, enum machine_mode);
580 static int cse_rtx_varies_p (rtx, int);
581 static void remove_invalid_refs (unsigned int);
582 static void remove_invalid_subreg_refs (unsigned int, unsigned int,
584 static void rehash_using_reg (rtx);
585 static void invalidate_memory (void);
586 static void invalidate_for_call (void);
587 static rtx use_related_value (rtx, struct table_elt *);
589 static inline unsigned canon_hash (rtx, enum machine_mode);
590 static inline unsigned safe_hash (rtx, enum machine_mode);
591 static unsigned hash_rtx_string (const char *);
593 static rtx canon_reg (rtx, rtx);
594 static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
596 enum machine_mode *);
597 static rtx fold_rtx (rtx, rtx);
598 static rtx equiv_constant (rtx);
599 static void record_jump_equiv (rtx, bool);
600 static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
602 static void cse_insn (rtx, rtx);
603 static void cse_prescan_path (struct cse_basic_block_data *);
604 static void invalidate_from_clobbers (rtx);
605 static rtx cse_process_notes (rtx, rtx);
606 static void cse_extended_basic_block (struct cse_basic_block_data *);
607 static void count_reg_usage (rtx, int *, rtx, int);
608 static int check_for_label_ref (rtx *, void *);
609 extern void dump_class (struct table_elt*);
610 static void get_cse_reg_info_1 (unsigned int regno);
611 static struct cse_reg_info * get_cse_reg_info (unsigned int regno);
612 static int check_dependence (rtx *, void *);
614 static void flush_hash_table (void);
615 static bool insn_live_p (rtx, int *);
616 static bool set_live_p (rtx, rtx, int *);
617 static bool dead_libcall_p (rtx, int *);
618 static int cse_change_cc_mode (rtx *, void *);
619 static void cse_change_cc_mode_insn (rtx, rtx);
620 static void cse_change_cc_mode_insns (rtx, rtx, rtx);
621 static enum machine_mode cse_cc_succs (basic_block, rtx, rtx, bool);
624 #undef RTL_HOOKS_GEN_LOWPART
625 #define RTL_HOOKS_GEN_LOWPART gen_lowpart_if_possible
627 static const struct rtl_hooks cse_rtl_hooks = RTL_HOOKS_INITIALIZER;
629 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
630 virtual regs here because the simplify_*_operation routines are called
631 by integrate.c, which is called before virtual register instantiation. */
634 fixed_base_plus_p (rtx x)
636 switch (GET_CODE (x))
639 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
641 if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
643 if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
644 && REGNO (x) <= LAST_VIRTUAL_REGISTER)
649 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
651 return fixed_base_plus_p (XEXP (x, 0));
658 /* Dump the expressions in the equivalence class indicated by CLASSP.
659 This function is used only for debugging. */
661 dump_class (struct table_elt *classp)
663 struct table_elt *elt;
665 fprintf (stderr, "Equivalence chain for ");
666 print_rtl (stderr, classp->exp);
667 fprintf (stderr, ": \n");
669 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
671 print_rtl (stderr, elt->exp);
672 fprintf (stderr, "\n");
676 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
679 approx_reg_cost_1 (rtx *xp, void *data)
686 unsigned int regno = REGNO (x);
688 if (! CHEAP_REGNO (regno))
690 if (regno < FIRST_PSEUDO_REGISTER)
692 if (SMALL_REGISTER_CLASSES)
704 /* Return an estimate of the cost of the registers used in an rtx.
705 This is mostly the number of different REG expressions in the rtx;
706 however for some exceptions like fixed registers we use a cost of
707 0. If any other hard register reference occurs, return MAX_COST. */
710 approx_reg_cost (rtx x)
714 if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
720 /* Return a negative value if an rtx A, whose costs are given by COST_A
721 and REGCOST_A, is more desirable than an rtx B.
722 Return a positive value if A is less desirable, or 0 if the two are
725 preferable (int cost_a, int regcost_a, int cost_b, int regcost_b)
727 /* First, get rid of cases involving expressions that are entirely
729 if (cost_a != cost_b)
731 if (cost_a == MAX_COST)
733 if (cost_b == MAX_COST)
737 /* Avoid extending lifetimes of hardregs. */
738 if (regcost_a != regcost_b)
740 if (regcost_a == MAX_COST)
742 if (regcost_b == MAX_COST)
746 /* Normal operation costs take precedence. */
747 if (cost_a != cost_b)
748 return cost_a - cost_b;
749 /* Only if these are identical consider effects on register pressure. */
750 if (regcost_a != regcost_b)
751 return regcost_a - regcost_b;
755 /* Internal function, to compute cost when X is not a register; called
756 from COST macro to keep it simple. */
759 notreg_cost (rtx x, enum rtx_code outer)
761 return ((GET_CODE (x) == SUBREG
762 && REG_P (SUBREG_REG (x))
763 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
764 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
765 && (GET_MODE_SIZE (GET_MODE (x))
766 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
767 && subreg_lowpart_p (x)
768 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
769 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
771 : rtx_cost (x, outer) * 2);
775 /* Initialize CSE_REG_INFO_TABLE. */
778 init_cse_reg_info (unsigned int nregs)
780 /* Do we need to grow the table? */
781 if (nregs > cse_reg_info_table_size)
783 unsigned int new_size;
785 if (cse_reg_info_table_size < 2048)
787 /* Compute a new size that is a power of 2 and no smaller
788 than the large of NREGS and 64. */
789 new_size = (cse_reg_info_table_size
790 ? cse_reg_info_table_size : 64);
792 while (new_size < nregs)
797 /* If we need a big table, allocate just enough to hold
802 /* Reallocate the table with NEW_SIZE entries. */
803 if (cse_reg_info_table)
804 free (cse_reg_info_table);
805 cse_reg_info_table = XNEWVEC (struct cse_reg_info, new_size);
806 cse_reg_info_table_size = new_size;
807 cse_reg_info_table_first_uninitialized = 0;
810 /* Do we have all of the first NREGS entries initialized? */
811 if (cse_reg_info_table_first_uninitialized < nregs)
813 unsigned int old_timestamp = cse_reg_info_timestamp - 1;
816 /* Put the old timestamp on newly allocated entries so that they
817 will all be considered out of date. We do not touch those
818 entries beyond the first NREGS entries to be nice to the
820 for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
821 cse_reg_info_table[i].timestamp = old_timestamp;
823 cse_reg_info_table_first_uninitialized = nregs;
827 /* Given REGNO, initialize the cse_reg_info entry for REGNO. */
830 get_cse_reg_info_1 (unsigned int regno)
832 /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
833 entry will be considered to have been initialized. */
834 cse_reg_info_table[regno].timestamp = cse_reg_info_timestamp;
836 /* Initialize the rest of the entry. */
837 cse_reg_info_table[regno].reg_tick = 1;
838 cse_reg_info_table[regno].reg_in_table = -1;
839 cse_reg_info_table[regno].subreg_ticked = -1;
840 cse_reg_info_table[regno].reg_qty = -regno - 1;
843 /* Find a cse_reg_info entry for REGNO. */
845 static inline struct cse_reg_info *
846 get_cse_reg_info (unsigned int regno)
848 struct cse_reg_info *p = &cse_reg_info_table[regno];
850 /* If this entry has not been initialized, go ahead and initialize
852 if (p->timestamp != cse_reg_info_timestamp)
853 get_cse_reg_info_1 (regno);
858 /* Clear the hash table and initialize each register with its own quantity,
859 for a new basic block. */
862 new_basic_block (void)
868 /* Invalidate cse_reg_info_table. */
869 cse_reg_info_timestamp++;
871 /* Clear out hash table state for this pass. */
872 CLEAR_HARD_REG_SET (hard_regs_in_table);
874 /* The per-quantity values used to be initialized here, but it is
875 much faster to initialize each as it is made in `make_new_qty'. */
877 for (i = 0; i < HASH_SIZE; i++)
879 struct table_elt *first;
884 struct table_elt *last = first;
888 while (last->next_same_hash != NULL)
889 last = last->next_same_hash;
891 /* Now relink this hash entire chain into
892 the free element list. */
894 last->next_same_hash = free_element_chain;
895 free_element_chain = first;
904 /* Say that register REG contains a quantity in mode MODE not in any
905 register before and initialize that quantity. */
908 make_new_qty (unsigned int reg, enum machine_mode mode)
911 struct qty_table_elem *ent;
912 struct reg_eqv_elem *eqv;
914 gcc_assert (next_qty < max_qty);
916 q = REG_QTY (reg) = next_qty++;
918 ent->first_reg = reg;
921 ent->const_rtx = ent->const_insn = NULL_RTX;
922 ent->comparison_code = UNKNOWN;
924 eqv = ®_eqv_table[reg];
925 eqv->next = eqv->prev = -1;
928 /* Make reg NEW equivalent to reg OLD.
929 OLD is not changing; NEW is. */
932 make_regs_eqv (unsigned int new, unsigned int old)
934 unsigned int lastr, firstr;
935 int q = REG_QTY (old);
936 struct qty_table_elem *ent;
940 /* Nothing should become eqv until it has a "non-invalid" qty number. */
941 gcc_assert (REGNO_QTY_VALID_P (old));
944 firstr = ent->first_reg;
945 lastr = ent->last_reg;
947 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
948 hard regs. Among pseudos, if NEW will live longer than any other reg
949 of the same qty, and that is beyond the current basic block,
950 make it the new canonical replacement for this qty. */
951 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
952 /* Certain fixed registers might be of the class NO_REGS. This means
953 that not only can they not be allocated by the compiler, but
954 they cannot be used in substitutions or canonicalizations
956 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
957 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
958 || (new >= FIRST_PSEUDO_REGISTER
959 && (firstr < FIRST_PSEUDO_REGISTER
960 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
961 || (uid_cuid[REGNO_FIRST_UID (new)]
962 < cse_basic_block_start))
963 && (uid_cuid[REGNO_LAST_UID (new)]
964 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
966 reg_eqv_table[firstr].prev = new;
967 reg_eqv_table[new].next = firstr;
968 reg_eqv_table[new].prev = -1;
969 ent->first_reg = new;
973 /* If NEW is a hard reg (known to be non-fixed), insert at end.
974 Otherwise, insert before any non-fixed hard regs that are at the
975 end. Registers of class NO_REGS cannot be used as an
976 equivalent for anything. */
977 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
978 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
979 && new >= FIRST_PSEUDO_REGISTER)
980 lastr = reg_eqv_table[lastr].prev;
981 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
982 if (reg_eqv_table[lastr].next >= 0)
983 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
985 qty_table[q].last_reg = new;
986 reg_eqv_table[lastr].next = new;
987 reg_eqv_table[new].prev = lastr;
991 /* Remove REG from its equivalence class. */
994 delete_reg_equiv (unsigned int reg)
996 struct qty_table_elem *ent;
997 int q = REG_QTY (reg);
1000 /* If invalid, do nothing. */
1001 if (! REGNO_QTY_VALID_P (reg))
1004 ent = &qty_table[q];
1006 p = reg_eqv_table[reg].prev;
1007 n = reg_eqv_table[reg].next;
1010 reg_eqv_table[n].prev = p;
1014 reg_eqv_table[p].next = n;
1018 REG_QTY (reg) = -reg - 1;
1021 /* Remove any invalid expressions from the hash table
1022 that refer to any of the registers contained in expression X.
1024 Make sure that newly inserted references to those registers
1025 as subexpressions will be considered valid.
1027 mention_regs is not called when a register itself
1028 is being stored in the table.
1030 Return 1 if we have done something that may have changed the hash code
1034 mention_regs (rtx x)
1044 code = GET_CODE (x);
1047 unsigned int regno = REGNO (x);
1048 unsigned int endregno = END_REGNO (x);
1051 for (i = regno; i < endregno; i++)
1053 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1054 remove_invalid_refs (i);
1056 REG_IN_TABLE (i) = REG_TICK (i);
1057 SUBREG_TICKED (i) = -1;
1063 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1064 pseudo if they don't use overlapping words. We handle only pseudos
1065 here for simplicity. */
1066 if (code == SUBREG && REG_P (SUBREG_REG (x))
1067 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1069 unsigned int i = REGNO (SUBREG_REG (x));
1071 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1073 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1074 the last store to this register really stored into this
1075 subreg, then remove the memory of this subreg.
1076 Otherwise, remove any memory of the entire register and
1077 all its subregs from the table. */
1078 if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1079 || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1080 remove_invalid_refs (i);
1082 remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1085 REG_IN_TABLE (i) = REG_TICK (i);
1086 SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1090 /* If X is a comparison or a COMPARE and either operand is a register
1091 that does not have a quantity, give it one. This is so that a later
1092 call to record_jump_equiv won't cause X to be assigned a different
1093 hash code and not found in the table after that call.
1095 It is not necessary to do this here, since rehash_using_reg can
1096 fix up the table later, but doing this here eliminates the need to
1097 call that expensive function in the most common case where the only
1098 use of the register is in the comparison. */
1100 if (code == COMPARE || COMPARISON_P (x))
1102 if (REG_P (XEXP (x, 0))
1103 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1104 if (insert_regs (XEXP (x, 0), NULL, 0))
1106 rehash_using_reg (XEXP (x, 0));
1110 if (REG_P (XEXP (x, 1))
1111 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1112 if (insert_regs (XEXP (x, 1), NULL, 0))
1114 rehash_using_reg (XEXP (x, 1));
1119 fmt = GET_RTX_FORMAT (code);
1120 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1122 changed |= mention_regs (XEXP (x, i));
1123 else if (fmt[i] == 'E')
1124 for (j = 0; j < XVECLEN (x, i); j++)
1125 changed |= mention_regs (XVECEXP (x, i, j));
1130 /* Update the register quantities for inserting X into the hash table
1131 with a value equivalent to CLASSP.
1132 (If the class does not contain a REG, it is irrelevant.)
1133 If MODIFIED is nonzero, X is a destination; it is being modified.
1134 Note that delete_reg_equiv should be called on a register
1135 before insert_regs is done on that register with MODIFIED != 0.
1137 Nonzero value means that elements of reg_qty have changed
1138 so X's hash code may be different. */
1141 insert_regs (rtx x, struct table_elt *classp, int modified)
1145 unsigned int regno = REGNO (x);
1148 /* If REGNO is in the equivalence table already but is of the
1149 wrong mode for that equivalence, don't do anything here. */
1151 qty_valid = REGNO_QTY_VALID_P (regno);
1154 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1156 if (ent->mode != GET_MODE (x))
1160 if (modified || ! qty_valid)
1163 for (classp = classp->first_same_value;
1165 classp = classp->next_same_value)
1166 if (REG_P (classp->exp)
1167 && GET_MODE (classp->exp) == GET_MODE (x))
1169 unsigned c_regno = REGNO (classp->exp);
1171 gcc_assert (REGNO_QTY_VALID_P (c_regno));
1173 /* Suppose that 5 is hard reg and 100 and 101 are
1176 (set (reg:si 100) (reg:si 5))
1177 (set (reg:si 5) (reg:si 100))
1178 (set (reg:di 101) (reg:di 5))
1180 We would now set REG_QTY (101) = REG_QTY (5), but the
1181 entry for 5 is in SImode. When we use this later in
1182 copy propagation, we get the register in wrong mode. */
1183 if (qty_table[REG_QTY (c_regno)].mode != GET_MODE (x))
1186 make_regs_eqv (regno, c_regno);
1190 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1191 than REG_IN_TABLE to find out if there was only a single preceding
1192 invalidation - for the SUBREG - or another one, which would be
1193 for the full register. However, if we find here that REG_TICK
1194 indicates that the register is invalid, it means that it has
1195 been invalidated in a separate operation. The SUBREG might be used
1196 now (then this is a recursive call), or we might use the full REG
1197 now and a SUBREG of it later. So bump up REG_TICK so that
1198 mention_regs will do the right thing. */
1200 && REG_IN_TABLE (regno) >= 0
1201 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1203 make_new_qty (regno, GET_MODE (x));
1210 /* If X is a SUBREG, we will likely be inserting the inner register in the
1211 table. If that register doesn't have an assigned quantity number at
1212 this point but does later, the insertion that we will be doing now will
1213 not be accessible because its hash code will have changed. So assign
1214 a quantity number now. */
1216 else if (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))
1217 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1219 insert_regs (SUBREG_REG (x), NULL, 0);
1224 return mention_regs (x);
1227 /* Look in or update the hash table. */
1229 /* Remove table element ELT from use in the table.
1230 HASH is its hash code, made using the HASH macro.
1231 It's an argument because often that is known in advance
1232 and we save much time not recomputing it. */
1235 remove_from_table (struct table_elt *elt, unsigned int hash)
1240 /* Mark this element as removed. See cse_insn. */
1241 elt->first_same_value = 0;
1243 /* Remove the table element from its equivalence class. */
1246 struct table_elt *prev = elt->prev_same_value;
1247 struct table_elt *next = elt->next_same_value;
1250 next->prev_same_value = prev;
1253 prev->next_same_value = next;
1256 struct table_elt *newfirst = next;
1259 next->first_same_value = newfirst;
1260 next = next->next_same_value;
1265 /* Remove the table element from its hash bucket. */
1268 struct table_elt *prev = elt->prev_same_hash;
1269 struct table_elt *next = elt->next_same_hash;
1272 next->prev_same_hash = prev;
1275 prev->next_same_hash = next;
1276 else if (table[hash] == elt)
1280 /* This entry is not in the proper hash bucket. This can happen
1281 when two classes were merged by `merge_equiv_classes'. Search
1282 for the hash bucket that it heads. This happens only very
1283 rarely, so the cost is acceptable. */
1284 for (hash = 0; hash < HASH_SIZE; hash++)
1285 if (table[hash] == elt)
1290 /* Remove the table element from its related-value circular chain. */
1292 if (elt->related_value != 0 && elt->related_value != elt)
1294 struct table_elt *p = elt->related_value;
1296 while (p->related_value != elt)
1297 p = p->related_value;
1298 p->related_value = elt->related_value;
1299 if (p->related_value == p)
1300 p->related_value = 0;
1303 /* Now add it to the free element chain. */
1304 elt->next_same_hash = free_element_chain;
1305 free_element_chain = elt;
1308 /* Look up X in the hash table and return its table element,
1309 or 0 if X is not in the table.
1311 MODE is the machine-mode of X, or if X is an integer constant
1312 with VOIDmode then MODE is the mode with which X will be used.
1314 Here we are satisfied to find an expression whose tree structure
1317 static struct table_elt *
1318 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1320 struct table_elt *p;
1322 for (p = table[hash]; p; p = p->next_same_hash)
1323 if (mode == p->mode && ((x == p->exp && REG_P (x))
1324 || exp_equiv_p (x, p->exp, !REG_P (x), false)))
1330 /* Like `lookup' but don't care whether the table element uses invalid regs.
1331 Also ignore discrepancies in the machine mode of a register. */
1333 static struct table_elt *
1334 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1336 struct table_elt *p;
1340 unsigned int regno = REGNO (x);
1342 /* Don't check the machine mode when comparing registers;
1343 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1344 for (p = table[hash]; p; p = p->next_same_hash)
1346 && REGNO (p->exp) == regno)
1351 for (p = table[hash]; p; p = p->next_same_hash)
1353 && (x == p->exp || exp_equiv_p (x, p->exp, 0, false)))
1360 /* Look for an expression equivalent to X and with code CODE.
1361 If one is found, return that expression. */
1364 lookup_as_function (rtx x, enum rtx_code code)
1367 = lookup (x, SAFE_HASH (x, VOIDmode), GET_MODE (x));
1369 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1370 long as we are narrowing. So if we looked in vain for a mode narrower
1371 than word_mode before, look for word_mode now. */
1372 if (p == 0 && code == CONST_INT
1373 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1376 PUT_MODE (x, word_mode);
1377 p = lookup (x, SAFE_HASH (x, VOIDmode), word_mode);
1383 for (p = p->first_same_value; p; p = p->next_same_value)
1384 if (GET_CODE (p->exp) == code
1385 /* Make sure this is a valid entry in the table. */
1386 && exp_equiv_p (p->exp, p->exp, 1, false))
1392 /* Insert X in the hash table, assuming HASH is its hash code
1393 and CLASSP is an element of the class it should go in
1394 (or 0 if a new class should be made).
1395 It is inserted at the proper position to keep the class in
1396 the order cheapest first.
1398 MODE is the machine-mode of X, or if X is an integer constant
1399 with VOIDmode then MODE is the mode with which X will be used.
1401 For elements of equal cheapness, the most recent one
1402 goes in front, except that the first element in the list
1403 remains first unless a cheaper element is added. The order of
1404 pseudo-registers does not matter, as canon_reg will be called to
1405 find the cheapest when a register is retrieved from the table.
1407 The in_memory field in the hash table element is set to 0.
1408 The caller must set it nonzero if appropriate.
1410 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1411 and if insert_regs returns a nonzero value
1412 you must then recompute its hash code before calling here.
1414 If necessary, update table showing constant values of quantities. */
1416 #define CHEAPER(X, Y) \
1417 (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1419 static struct table_elt *
1420 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1422 struct table_elt *elt;
1424 /* If X is a register and we haven't made a quantity for it,
1425 something is wrong. */
1426 gcc_assert (!REG_P (x) || REGNO_QTY_VALID_P (REGNO (x)));
1428 /* If X is a hard register, show it is being put in the table. */
1429 if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1430 add_to_hard_reg_set (&hard_regs_in_table, GET_MODE (x), REGNO (x));
1432 /* Put an element for X into the right hash bucket. */
1434 elt = free_element_chain;
1436 free_element_chain = elt->next_same_hash;
1438 elt = XNEW (struct table_elt);
1441 elt->canon_exp = NULL_RTX;
1442 elt->cost = COST (x);
1443 elt->regcost = approx_reg_cost (x);
1444 elt->next_same_value = 0;
1445 elt->prev_same_value = 0;
1446 elt->next_same_hash = table[hash];
1447 elt->prev_same_hash = 0;
1448 elt->related_value = 0;
1451 elt->is_const = (CONSTANT_P (x) || fixed_base_plus_p (x));
1454 table[hash]->prev_same_hash = elt;
1457 /* Put it into the proper value-class. */
1460 classp = classp->first_same_value;
1461 if (CHEAPER (elt, classp))
1462 /* Insert at the head of the class. */
1464 struct table_elt *p;
1465 elt->next_same_value = classp;
1466 classp->prev_same_value = elt;
1467 elt->first_same_value = elt;
1469 for (p = classp; p; p = p->next_same_value)
1470 p->first_same_value = elt;
1474 /* Insert not at head of the class. */
1475 /* Put it after the last element cheaper than X. */
1476 struct table_elt *p, *next;
1478 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1481 /* Put it after P and before NEXT. */
1482 elt->next_same_value = next;
1484 next->prev_same_value = elt;
1486 elt->prev_same_value = p;
1487 p->next_same_value = elt;
1488 elt->first_same_value = classp;
1492 elt->first_same_value = elt;
1494 /* If this is a constant being set equivalent to a register or a register
1495 being set equivalent to a constant, note the constant equivalence.
1497 If this is a constant, it cannot be equivalent to a different constant,
1498 and a constant is the only thing that can be cheaper than a register. So
1499 we know the register is the head of the class (before the constant was
1502 If this is a register that is not already known equivalent to a
1503 constant, we must check the entire class.
1505 If this is a register that is already known equivalent to an insn,
1506 update the qtys `const_insn' to show that `this_insn' is the latest
1507 insn making that quantity equivalent to the constant. */
1509 if (elt->is_const && classp && REG_P (classp->exp)
1512 int exp_q = REG_QTY (REGNO (classp->exp));
1513 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1515 exp_ent->const_rtx = gen_lowpart (exp_ent->mode, x);
1516 exp_ent->const_insn = this_insn;
1521 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1524 struct table_elt *p;
1526 for (p = classp; p != 0; p = p->next_same_value)
1528 if (p->is_const && !REG_P (p->exp))
1530 int x_q = REG_QTY (REGNO (x));
1531 struct qty_table_elem *x_ent = &qty_table[x_q];
1534 = gen_lowpart (GET_MODE (x), p->exp);
1535 x_ent->const_insn = this_insn;
1542 && qty_table[REG_QTY (REGNO (x))].const_rtx
1543 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1544 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1546 /* If this is a constant with symbolic value,
1547 and it has a term with an explicit integer value,
1548 link it up with related expressions. */
1549 if (GET_CODE (x) == CONST)
1551 rtx subexp = get_related_value (x);
1553 struct table_elt *subelt, *subelt_prev;
1557 /* Get the integer-free subexpression in the hash table. */
1558 subhash = SAFE_HASH (subexp, mode);
1559 subelt = lookup (subexp, subhash, mode);
1561 subelt = insert (subexp, NULL, subhash, mode);
1562 /* Initialize SUBELT's circular chain if it has none. */
1563 if (subelt->related_value == 0)
1564 subelt->related_value = subelt;
1565 /* Find the element in the circular chain that precedes SUBELT. */
1566 subelt_prev = subelt;
1567 while (subelt_prev->related_value != subelt)
1568 subelt_prev = subelt_prev->related_value;
1569 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1570 This way the element that follows SUBELT is the oldest one. */
1571 elt->related_value = subelt_prev->related_value;
1572 subelt_prev->related_value = elt;
1579 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1580 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1581 the two classes equivalent.
1583 CLASS1 will be the surviving class; CLASS2 should not be used after this
1586 Any invalid entries in CLASS2 will not be copied. */
1589 merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1591 struct table_elt *elt, *next, *new;
1593 /* Ensure we start with the head of the classes. */
1594 class1 = class1->first_same_value;
1595 class2 = class2->first_same_value;
1597 /* If they were already equal, forget it. */
1598 if (class1 == class2)
1601 for (elt = class2; elt; elt = next)
1605 enum machine_mode mode = elt->mode;
1607 next = elt->next_same_value;
1609 /* Remove old entry, make a new one in CLASS1's class.
1610 Don't do this for invalid entries as we cannot find their
1611 hash code (it also isn't necessary). */
1612 if (REG_P (exp) || exp_equiv_p (exp, exp, 1, false))
1614 bool need_rehash = false;
1616 hash_arg_in_memory = 0;
1617 hash = HASH (exp, mode);
1621 need_rehash = REGNO_QTY_VALID_P (REGNO (exp));
1622 delete_reg_equiv (REGNO (exp));
1625 remove_from_table (elt, hash);
1627 if (insert_regs (exp, class1, 0) || need_rehash)
1629 rehash_using_reg (exp);
1630 hash = HASH (exp, mode);
1632 new = insert (exp, class1, hash, mode);
1633 new->in_memory = hash_arg_in_memory;
1638 /* Flush the entire hash table. */
1641 flush_hash_table (void)
1644 struct table_elt *p;
1646 for (i = 0; i < HASH_SIZE; i++)
1647 for (p = table[i]; p; p = table[i])
1649 /* Note that invalidate can remove elements
1650 after P in the current hash chain. */
1652 invalidate (p->exp, VOIDmode);
1654 remove_from_table (p, i);
1658 /* Function called for each rtx to check whether true dependence exist. */
1659 struct check_dependence_data
1661 enum machine_mode mode;
1667 check_dependence (rtx *x, void *data)
1669 struct check_dependence_data *d = (struct check_dependence_data *) data;
1670 if (*x && MEM_P (*x))
1671 return canon_true_dependence (d->exp, d->mode, d->addr, *x,
1677 /* Remove from the hash table, or mark as invalid, all expressions whose
1678 values could be altered by storing in X. X is a register, a subreg, or
1679 a memory reference with nonvarying address (because, when a memory
1680 reference with a varying address is stored in, all memory references are
1681 removed by invalidate_memory so specific invalidation is superfluous).
1682 FULL_MODE, if not VOIDmode, indicates that this much should be
1683 invalidated instead of just the amount indicated by the mode of X. This
1684 is only used for bitfield stores into memory.
1686 A nonvarying address may be just a register or just a symbol reference,
1687 or it may be either of those plus a numeric offset. */
1690 invalidate (rtx x, enum machine_mode full_mode)
1693 struct table_elt *p;
1696 switch (GET_CODE (x))
1700 /* If X is a register, dependencies on its contents are recorded
1701 through the qty number mechanism. Just change the qty number of
1702 the register, mark it as invalid for expressions that refer to it,
1703 and remove it itself. */
1704 unsigned int regno = REGNO (x);
1705 unsigned int hash = HASH (x, GET_MODE (x));
1707 /* Remove REGNO from any quantity list it might be on and indicate
1708 that its value might have changed. If it is a pseudo, remove its
1709 entry from the hash table.
1711 For a hard register, we do the first two actions above for any
1712 additional hard registers corresponding to X. Then, if any of these
1713 registers are in the table, we must remove any REG entries that
1714 overlap these registers. */
1716 delete_reg_equiv (regno);
1718 SUBREG_TICKED (regno) = -1;
1720 if (regno >= FIRST_PSEUDO_REGISTER)
1722 /* Because a register can be referenced in more than one mode,
1723 we might have to remove more than one table entry. */
1724 struct table_elt *elt;
1726 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1727 remove_from_table (elt, hash);
1731 HOST_WIDE_INT in_table
1732 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1733 unsigned int endregno = END_HARD_REGNO (x);
1734 unsigned int tregno, tendregno, rn;
1735 struct table_elt *p, *next;
1737 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1739 for (rn = regno + 1; rn < endregno; rn++)
1741 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1742 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1743 delete_reg_equiv (rn);
1745 SUBREG_TICKED (rn) = -1;
1749 for (hash = 0; hash < HASH_SIZE; hash++)
1750 for (p = table[hash]; p; p = next)
1752 next = p->next_same_hash;
1755 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1758 tregno = REGNO (p->exp);
1759 tendregno = END_HARD_REGNO (p->exp);
1760 if (tendregno > regno && tregno < endregno)
1761 remove_from_table (p, hash);
1768 invalidate (SUBREG_REG (x), VOIDmode);
1772 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1773 invalidate (XVECEXP (x, 0, i), VOIDmode);
1777 /* This is part of a disjoint return value; extract the location in
1778 question ignoring the offset. */
1779 invalidate (XEXP (x, 0), VOIDmode);
1783 addr = canon_rtx (get_addr (XEXP (x, 0)));
1784 /* Calculate the canonical version of X here so that
1785 true_dependence doesn't generate new RTL for X on each call. */
1788 /* Remove all hash table elements that refer to overlapping pieces of
1790 if (full_mode == VOIDmode)
1791 full_mode = GET_MODE (x);
1793 for (i = 0; i < HASH_SIZE; i++)
1795 struct table_elt *next;
1797 for (p = table[i]; p; p = next)
1799 next = p->next_same_hash;
1802 struct check_dependence_data d;
1804 /* Just canonicalize the expression once;
1805 otherwise each time we call invalidate
1806 true_dependence will canonicalize the
1807 expression again. */
1809 p->canon_exp = canon_rtx (p->exp);
1813 if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1814 remove_from_table (p, i);
1825 /* Remove all expressions that refer to register REGNO,
1826 since they are already invalid, and we are about to
1827 mark that register valid again and don't want the old
1828 expressions to reappear as valid. */
1831 remove_invalid_refs (unsigned int regno)
1834 struct table_elt *p, *next;
1836 for (i = 0; i < HASH_SIZE; i++)
1837 for (p = table[i]; p; p = next)
1839 next = p->next_same_hash;
1841 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1842 remove_from_table (p, i);
1846 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1849 remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1850 enum machine_mode mode)
1853 struct table_elt *p, *next;
1854 unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
1856 for (i = 0; i < HASH_SIZE; i++)
1857 for (p = table[i]; p; p = next)
1860 next = p->next_same_hash;
1863 && (GET_CODE (exp) != SUBREG
1864 || !REG_P (SUBREG_REG (exp))
1865 || REGNO (SUBREG_REG (exp)) != regno
1866 || (((SUBREG_BYTE (exp)
1867 + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
1868 && SUBREG_BYTE (exp) <= end))
1869 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1870 remove_from_table (p, i);
1874 /* Recompute the hash codes of any valid entries in the hash table that
1875 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1877 This is called when we make a jump equivalence. */
1880 rehash_using_reg (rtx x)
1883 struct table_elt *p, *next;
1886 if (GET_CODE (x) == SUBREG)
1889 /* If X is not a register or if the register is known not to be in any
1890 valid entries in the table, we have no work to do. */
1893 || REG_IN_TABLE (REGNO (x)) < 0
1894 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
1897 /* Scan all hash chains looking for valid entries that mention X.
1898 If we find one and it is in the wrong hash chain, move it. */
1900 for (i = 0; i < HASH_SIZE; i++)
1901 for (p = table[i]; p; p = next)
1903 next = p->next_same_hash;
1904 if (reg_mentioned_p (x, p->exp)
1905 && exp_equiv_p (p->exp, p->exp, 1, false)
1906 && i != (hash = SAFE_HASH (p->exp, p->mode)))
1908 if (p->next_same_hash)
1909 p->next_same_hash->prev_same_hash = p->prev_same_hash;
1911 if (p->prev_same_hash)
1912 p->prev_same_hash->next_same_hash = p->next_same_hash;
1914 table[i] = p->next_same_hash;
1916 p->next_same_hash = table[hash];
1917 p->prev_same_hash = 0;
1919 table[hash]->prev_same_hash = p;
1925 /* Remove from the hash table any expression that is a call-clobbered
1926 register. Also update their TICK values. */
1929 invalidate_for_call (void)
1931 unsigned int regno, endregno;
1934 struct table_elt *p, *next;
1937 /* Go through all the hard registers. For each that is clobbered in
1938 a CALL_INSN, remove the register from quantity chains and update
1939 reg_tick if defined. Also see if any of these registers is currently
1942 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1943 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1945 delete_reg_equiv (regno);
1946 if (REG_TICK (regno) >= 0)
1949 SUBREG_TICKED (regno) = -1;
1952 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
1955 /* In the case where we have no call-clobbered hard registers in the
1956 table, we are done. Otherwise, scan the table and remove any
1957 entry that overlaps a call-clobbered register. */
1960 for (hash = 0; hash < HASH_SIZE; hash++)
1961 for (p = table[hash]; p; p = next)
1963 next = p->next_same_hash;
1966 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1969 regno = REGNO (p->exp);
1970 endregno = END_HARD_REGNO (p->exp);
1972 for (i = regno; i < endregno; i++)
1973 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1975 remove_from_table (p, hash);
1981 /* Given an expression X of type CONST,
1982 and ELT which is its table entry (or 0 if it
1983 is not in the hash table),
1984 return an alternate expression for X as a register plus integer.
1985 If none can be found, return 0. */
1988 use_related_value (rtx x, struct table_elt *elt)
1990 struct table_elt *relt = 0;
1991 struct table_elt *p, *q;
1992 HOST_WIDE_INT offset;
1994 /* First, is there anything related known?
1995 If we have a table element, we can tell from that.
1996 Otherwise, must look it up. */
1998 if (elt != 0 && elt->related_value != 0)
2000 else if (elt == 0 && GET_CODE (x) == CONST)
2002 rtx subexp = get_related_value (x);
2004 relt = lookup (subexp,
2005 SAFE_HASH (subexp, GET_MODE (subexp)),
2012 /* Search all related table entries for one that has an
2013 equivalent register. */
2018 /* This loop is strange in that it is executed in two different cases.
2019 The first is when X is already in the table. Then it is searching
2020 the RELATED_VALUE list of X's class (RELT). The second case is when
2021 X is not in the table. Then RELT points to a class for the related
2024 Ensure that, whatever case we are in, that we ignore classes that have
2025 the same value as X. */
2027 if (rtx_equal_p (x, p->exp))
2030 for (q = p->first_same_value; q; q = q->next_same_value)
2037 p = p->related_value;
2039 /* We went all the way around, so there is nothing to be found.
2040 Alternatively, perhaps RELT was in the table for some other reason
2041 and it has no related values recorded. */
2042 if (p == relt || p == 0)
2049 offset = (get_integer_term (x) - get_integer_term (p->exp));
2050 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2051 return plus_constant (q->exp, offset);
2054 /* Hash a string. Just add its bytes up. */
2055 static inline unsigned
2056 hash_rtx_string (const char *ps)
2059 const unsigned char *p = (const unsigned char *) ps;
2068 /* Hash an rtx. We are careful to make sure the value is never negative.
2069 Equivalent registers hash identically.
2070 MODE is used in hashing for CONST_INTs only;
2071 otherwise the mode of X is used.
2073 Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2075 If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2076 a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
2078 Note that cse_insn knows that the hash code of a MEM expression
2079 is just (int) MEM plus the hash code of the address. */
2082 hash_rtx (rtx x, enum machine_mode mode, int *do_not_record_p,
2083 int *hash_arg_in_memory_p, bool have_reg_qty)
2090 /* Used to turn recursion into iteration. We can't rely on GCC's
2091 tail-recursion elimination since we need to keep accumulating values
2097 code = GET_CODE (x);
2102 unsigned int regno = REGNO (x);
2104 if (!reload_completed)
2106 /* On some machines, we can't record any non-fixed hard register,
2107 because extending its life will cause reload problems. We
2108 consider ap, fp, sp, gp to be fixed for this purpose.
2110 We also consider CCmode registers to be fixed for this purpose;
2111 failure to do so leads to failure to simplify 0<100 type of
2114 On all machines, we can't record any global registers.
2115 Nor should we record any register that is in a small
2116 class, as defined by CLASS_LIKELY_SPILLED_P. */
2119 if (regno >= FIRST_PSEUDO_REGISTER)
2121 else if (x == frame_pointer_rtx
2122 || x == hard_frame_pointer_rtx
2123 || x == arg_pointer_rtx
2124 || x == stack_pointer_rtx
2125 || x == pic_offset_table_rtx)
2127 else if (global_regs[regno])
2129 else if (fixed_regs[regno])
2131 else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2133 else if (SMALL_REGISTER_CLASSES)
2135 else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
2142 *do_not_record_p = 1;
2147 hash += ((unsigned int) REG << 7);
2148 hash += (have_reg_qty ? (unsigned) REG_QTY (regno) : regno);
2152 /* We handle SUBREG of a REG specially because the underlying
2153 reg changes its hash value with every value change; we don't
2154 want to have to forget unrelated subregs when one subreg changes. */
2157 if (REG_P (SUBREG_REG (x)))
2159 hash += (((unsigned int) SUBREG << 7)
2160 + REGNO (SUBREG_REG (x))
2161 + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2168 hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
2169 + (unsigned int) INTVAL (x));
2173 /* This is like the general case, except that it only counts
2174 the integers representing the constant. */
2175 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
2176 if (GET_MODE (x) != VOIDmode)
2177 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2179 hash += ((unsigned int) CONST_DOUBLE_LOW (x)
2180 + (unsigned int) CONST_DOUBLE_HIGH (x));
2188 units = CONST_VECTOR_NUNITS (x);
2190 for (i = 0; i < units; ++i)
2192 elt = CONST_VECTOR_ELT (x, i);
2193 hash += hash_rtx (elt, GET_MODE (elt), do_not_record_p,
2194 hash_arg_in_memory_p, have_reg_qty);
2200 /* Assume there is only one rtx object for any given label. */
2202 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2203 differences and differences between each stage's debugging dumps. */
2204 hash += (((unsigned int) LABEL_REF << 7)
2205 + CODE_LABEL_NUMBER (XEXP (x, 0)));
2210 /* Don't hash on the symbol's address to avoid bootstrap differences.
2211 Different hash values may cause expressions to be recorded in
2212 different orders and thus different registers to be used in the
2213 final assembler. This also avoids differences in the dump files
2214 between various stages. */
2216 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
2219 h += (h << 7) + *p++; /* ??? revisit */
2221 hash += ((unsigned int) SYMBOL_REF << 7) + h;
2226 /* We don't record if marked volatile or if BLKmode since we don't
2227 know the size of the move. */
2228 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2230 *do_not_record_p = 1;
2233 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2234 *hash_arg_in_memory_p = 1;
2236 /* Now that we have already found this special case,
2237 might as well speed it up as much as possible. */
2238 hash += (unsigned) MEM;
2243 /* A USE that mentions non-volatile memory needs special
2244 handling since the MEM may be BLKmode which normally
2245 prevents an entry from being made. Pure calls are
2246 marked by a USE which mentions BLKmode memory.
2247 See calls.c:emit_call_1. */
2248 if (MEM_P (XEXP (x, 0))
2249 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2251 hash += (unsigned) USE;
2254 if (hash_arg_in_memory_p && !MEM_READONLY_P (x))
2255 *hash_arg_in_memory_p = 1;
2257 /* Now that we have already found this special case,
2258 might as well speed it up as much as possible. */
2259 hash += (unsigned) MEM;
2274 case UNSPEC_VOLATILE:
2275 *do_not_record_p = 1;
2279 if (MEM_VOLATILE_P (x))
2281 *do_not_record_p = 1;
2286 /* We don't want to take the filename and line into account. */
2287 hash += (unsigned) code + (unsigned) GET_MODE (x)
2288 + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
2289 + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2290 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2292 if (ASM_OPERANDS_INPUT_LENGTH (x))
2294 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2296 hash += (hash_rtx (ASM_OPERANDS_INPUT (x, i),
2297 GET_MODE (ASM_OPERANDS_INPUT (x, i)),
2298 do_not_record_p, hash_arg_in_memory_p,
2301 (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
2304 hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2305 x = ASM_OPERANDS_INPUT (x, 0);
2306 mode = GET_MODE (x);
2318 i = GET_RTX_LENGTH (code) - 1;
2319 hash += (unsigned) code + (unsigned) GET_MODE (x);
2320 fmt = GET_RTX_FORMAT (code);
2326 /* If we are about to do the last recursive call
2327 needed at this level, change it into iteration.
2328 This function is called enough to be worth it. */
2335 hash += hash_rtx (XEXP (x, i), 0, do_not_record_p,
2336 hash_arg_in_memory_p, have_reg_qty);
2340 for (j = 0; j < XVECLEN (x, i); j++)
2341 hash += hash_rtx (XVECEXP (x, i, j), 0, do_not_record_p,
2342 hash_arg_in_memory_p, have_reg_qty);
2346 hash += hash_rtx_string (XSTR (x, i));
2350 hash += (unsigned int) XINT (x, i);
2365 /* Hash an rtx X for cse via hash_rtx.
2366 Stores 1 in do_not_record if any subexpression is volatile.
2367 Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2368 does not have the RTX_UNCHANGING_P bit set. */
2370 static inline unsigned
2371 canon_hash (rtx x, enum machine_mode mode)
2373 return hash_rtx (x, mode, &do_not_record, &hash_arg_in_memory, true);
2376 /* Like canon_hash but with no side effects, i.e. do_not_record
2377 and hash_arg_in_memory are not changed. */
2379 static inline unsigned
2380 safe_hash (rtx x, enum machine_mode mode)
2382 int dummy_do_not_record;
2383 return hash_rtx (x, mode, &dummy_do_not_record, NULL, true);
2386 /* Return 1 iff X and Y would canonicalize into the same thing,
2387 without actually constructing the canonicalization of either one.
2388 If VALIDATE is nonzero,
2389 we assume X is an expression being processed from the rtl
2390 and Y was found in the hash table. We check register refs
2391 in Y for being marked as valid.
2393 If FOR_GCSE is true, we compare X and Y for equivalence for GCSE. */
2396 exp_equiv_p (rtx x, rtx y, int validate, bool for_gcse)
2402 /* Note: it is incorrect to assume an expression is equivalent to itself
2403 if VALIDATE is nonzero. */
2404 if (x == y && !validate)
2407 if (x == 0 || y == 0)
2410 code = GET_CODE (x);
2411 if (code != GET_CODE (y))
2414 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2415 if (GET_MODE (x) != GET_MODE (y))
2427 return XEXP (x, 0) == XEXP (y, 0);
2430 return XSTR (x, 0) == XSTR (y, 0);
2434 return REGNO (x) == REGNO (y);
2437 unsigned int regno = REGNO (y);
2439 unsigned int endregno = END_REGNO (y);
2441 /* If the quantities are not the same, the expressions are not
2442 equivalent. If there are and we are not to validate, they
2443 are equivalent. Otherwise, ensure all regs are up-to-date. */
2445 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2451 for (i = regno; i < endregno; i++)
2452 if (REG_IN_TABLE (i) != REG_TICK (i))
2461 /* A volatile mem should not be considered equivalent to any
2463 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2466 /* Can't merge two expressions in different alias sets, since we
2467 can decide that the expression is transparent in a block when
2468 it isn't, due to it being set with the different alias set.
2470 Also, can't merge two expressions with different MEM_ATTRS.
2471 They could e.g. be two different entities allocated into the
2472 same space on the stack (see e.g. PR25130). In that case, the
2473 MEM addresses can be the same, even though the two MEMs are
2474 absolutely not equivalent.
2476 But because really all MEM attributes should be the same for
2477 equivalent MEMs, we just use the invariant that MEMs that have
2478 the same attributes share the same mem_attrs data structure. */
2479 if (MEM_ATTRS (x) != MEM_ATTRS (y))
2484 /* For commutative operations, check both orders. */
2492 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0),
2494 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2495 validate, for_gcse))
2496 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2498 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2499 validate, for_gcse)));
2502 /* We don't use the generic code below because we want to
2503 disregard filename and line numbers. */
2505 /* A volatile asm isn't equivalent to any other. */
2506 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2509 if (GET_MODE (x) != GET_MODE (y)
2510 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2511 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2512 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2513 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2514 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2517 if (ASM_OPERANDS_INPUT_LENGTH (x))
2519 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2520 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2521 ASM_OPERANDS_INPUT (y, i),
2523 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2524 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2534 /* Compare the elements. If any pair of corresponding elements
2535 fail to match, return 0 for the whole thing. */
2537 fmt = GET_RTX_FORMAT (code);
2538 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2543 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i),
2544 validate, for_gcse))
2549 if (XVECLEN (x, i) != XVECLEN (y, i))
2551 for (j = 0; j < XVECLEN (x, i); j++)
2552 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2553 validate, for_gcse))
2558 if (strcmp (XSTR (x, i), XSTR (y, i)))
2563 if (XINT (x, i) != XINT (y, i))
2568 if (XWINT (x, i) != XWINT (y, i))
2584 /* Return 1 if X has a value that can vary even between two
2585 executions of the program. 0 means X can be compared reliably
2586 against certain constants or near-constants. */
2589 cse_rtx_varies_p (rtx x, int from_alias)
2591 /* We need not check for X and the equivalence class being of the same
2592 mode because if X is equivalent to a constant in some mode, it
2593 doesn't vary in any mode. */
2596 && REGNO_QTY_VALID_P (REGNO (x)))
2598 int x_q = REG_QTY (REGNO (x));
2599 struct qty_table_elem *x_ent = &qty_table[x_q];
2601 if (GET_MODE (x) == x_ent->mode
2602 && x_ent->const_rtx != NULL_RTX)
2606 if (GET_CODE (x) == PLUS
2607 && GET_CODE (XEXP (x, 1)) == CONST_INT
2608 && REG_P (XEXP (x, 0))
2609 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2611 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2612 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2614 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2615 && x0_ent->const_rtx != NULL_RTX)
2619 /* This can happen as the result of virtual register instantiation, if
2620 the initial constant is too large to be a valid address. This gives
2621 us a three instruction sequence, load large offset into a register,
2622 load fp minus a constant into a register, then a MEM which is the
2623 sum of the two `constant' registers. */
2624 if (GET_CODE (x) == PLUS
2625 && REG_P (XEXP (x, 0))
2626 && REG_P (XEXP (x, 1))
2627 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2628 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2630 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2631 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2632 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2633 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2635 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2636 && x0_ent->const_rtx != NULL_RTX
2637 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2638 && x1_ent->const_rtx != NULL_RTX)
2642 return rtx_varies_p (x, from_alias);
2645 /* Subroutine of canon_reg. Pass *XLOC through canon_reg, and validate
2646 the result if necessary. INSN is as for canon_reg. */
2649 validate_canon_reg (rtx *xloc, rtx insn)
2651 rtx new = canon_reg (*xloc, insn);
2653 /* If replacing pseudo with hard reg or vice versa, ensure the
2654 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2655 if (insn != 0 && new != 0)
2656 validate_change (insn, xloc, new, 1);
2661 /* Canonicalize an expression:
2662 replace each register reference inside it
2663 with the "oldest" equivalent register.
2665 If INSN is nonzero validate_change is used to ensure that INSN remains valid
2666 after we make our substitution. The calls are made with IN_GROUP nonzero
2667 so apply_change_group must be called upon the outermost return from this
2668 function (unless INSN is zero). The result of apply_change_group can
2669 generally be discarded since the changes we are making are optional. */
2672 canon_reg (rtx x, rtx insn)
2681 code = GET_CODE (x);
2700 struct qty_table_elem *ent;
2702 /* Never replace a hard reg, because hard regs can appear
2703 in more than one machine mode, and we must preserve the mode
2704 of each occurrence. Also, some hard regs appear in
2705 MEMs that are shared and mustn't be altered. Don't try to
2706 replace any reg that maps to a reg of class NO_REGS. */
2707 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2708 || ! REGNO_QTY_VALID_P (REGNO (x)))
2711 q = REG_QTY (REGNO (x));
2712 ent = &qty_table[q];
2713 first = ent->first_reg;
2714 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2715 : REGNO_REG_CLASS (first) == NO_REGS ? x
2716 : gen_rtx_REG (ent->mode, first));
2723 fmt = GET_RTX_FORMAT (code);
2724 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2729 validate_canon_reg (&XEXP (x, i), insn);
2730 else if (fmt[i] == 'E')
2731 for (j = 0; j < XVECLEN (x, i); j++)
2732 validate_canon_reg (&XVECEXP (x, i, j), insn);
2738 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2739 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2740 what values are being compared.
2742 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2743 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2744 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2745 compared to produce cc0.
2747 The return value is the comparison operator and is either the code of
2748 A or the code corresponding to the inverse of the comparison. */
2750 static enum rtx_code
2751 find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
2752 enum machine_mode *pmode1, enum machine_mode *pmode2)
2756 arg1 = *parg1, arg2 = *parg2;
2758 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2760 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2762 /* Set nonzero when we find something of interest. */
2764 int reverse_code = 0;
2765 struct table_elt *p = 0;
2767 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2768 On machines with CC0, this is the only case that can occur, since
2769 fold_rtx will return the COMPARE or item being compared with zero
2772 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2775 /* If ARG1 is a comparison operator and CODE is testing for
2776 STORE_FLAG_VALUE, get the inner arguments. */
2778 else if (COMPARISON_P (arg1))
2780 #ifdef FLOAT_STORE_FLAG_VALUE
2781 REAL_VALUE_TYPE fsfv;
2785 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2786 && code == LT && STORE_FLAG_VALUE == -1)
2787 #ifdef FLOAT_STORE_FLAG_VALUE
2788 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2789 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2790 REAL_VALUE_NEGATIVE (fsfv)))
2795 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2796 && code == GE && STORE_FLAG_VALUE == -1)
2797 #ifdef FLOAT_STORE_FLAG_VALUE
2798 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1))
2799 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2800 REAL_VALUE_NEGATIVE (fsfv)))
2803 x = arg1, reverse_code = 1;
2806 /* ??? We could also check for
2808 (ne (and (eq (...) (const_int 1))) (const_int 0))
2810 and related forms, but let's wait until we see them occurring. */
2813 /* Look up ARG1 in the hash table and see if it has an equivalence
2814 that lets us see what is being compared. */
2815 p = lookup (arg1, SAFE_HASH (arg1, GET_MODE (arg1)), GET_MODE (arg1));
2818 p = p->first_same_value;
2820 /* If what we compare is already known to be constant, that is as
2822 We need to break the loop in this case, because otherwise we
2823 can have an infinite loop when looking at a reg that is known
2824 to be a constant which is the same as a comparison of a reg
2825 against zero which appears later in the insn stream, which in
2826 turn is constant and the same as the comparison of the first reg
2832 for (; p; p = p->next_same_value)
2834 enum machine_mode inner_mode = GET_MODE (p->exp);
2835 #ifdef FLOAT_STORE_FLAG_VALUE
2836 REAL_VALUE_TYPE fsfv;
2839 /* If the entry isn't valid, skip it. */
2840 if (! exp_equiv_p (p->exp, p->exp, 1, false))
2843 if (GET_CODE (p->exp) == COMPARE
2844 /* Another possibility is that this machine has a compare insn
2845 that includes the comparison code. In that case, ARG1 would
2846 be equivalent to a comparison operation that would set ARG1 to
2847 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2848 ORIG_CODE is the actual comparison being done; if it is an EQ,
2849 we must reverse ORIG_CODE. On machine with a negative value
2850 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2853 && GET_MODE_CLASS (inner_mode) == MODE_INT
2854 && (GET_MODE_BITSIZE (inner_mode)
2855 <= HOST_BITS_PER_WIDE_INT)
2856 && (STORE_FLAG_VALUE
2857 & ((HOST_WIDE_INT) 1
2858 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2859 #ifdef FLOAT_STORE_FLAG_VALUE
2861 && SCALAR_FLOAT_MODE_P (inner_mode)
2862 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2863 REAL_VALUE_NEGATIVE (fsfv)))
2866 && COMPARISON_P (p->exp)))
2871 else if ((code == EQ
2873 && GET_MODE_CLASS (inner_mode) == MODE_INT
2874 && (GET_MODE_BITSIZE (inner_mode)
2875 <= HOST_BITS_PER_WIDE_INT)
2876 && (STORE_FLAG_VALUE
2877 & ((HOST_WIDE_INT) 1
2878 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2879 #ifdef FLOAT_STORE_FLAG_VALUE
2881 && SCALAR_FLOAT_MODE_P (inner_mode)
2882 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
2883 REAL_VALUE_NEGATIVE (fsfv)))
2886 && COMPARISON_P (p->exp))
2893 /* If this non-trapping address, e.g. fp + constant, the
2894 equivalent is a better operand since it may let us predict
2895 the value of the comparison. */
2896 else if (!rtx_addr_can_trap_p (p->exp))
2903 /* If we didn't find a useful equivalence for ARG1, we are done.
2904 Otherwise, set up for the next iteration. */
2908 /* If we need to reverse the comparison, make sure that that is
2909 possible -- we can't necessarily infer the value of GE from LT
2910 with floating-point operands. */
2913 enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
2914 if (reversed == UNKNOWN)
2919 else if (COMPARISON_P (x))
2920 code = GET_CODE (x);
2921 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
2924 /* Return our results. Return the modes from before fold_rtx
2925 because fold_rtx might produce const_int, and then it's too late. */
2926 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
2927 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
2932 /* If X is a nontrivial arithmetic operation on an argument for which
2933 a constant value can be determined, return the result of operating
2934 on that value, as a constant. Otherwise, return X, possibly with
2935 one or more operands changed to a forward-propagated constant.
2937 If X is a register whose contents are known, we do NOT return
2938 those contents here; equiv_constant is called to perform that task.
2939 For SUBREGs and MEMs, we do that both here and in equiv_constant.
2941 INSN is the insn that we may be modifying. If it is 0, make a copy
2942 of X before modifying it. */
2945 fold_rtx (rtx x, rtx insn)
2948 enum machine_mode mode;
2954 /* Operands of X. */
2958 /* Constant equivalents of first three operands of X;
2959 0 when no such equivalent is known. */
2964 /* The mode of the first operand of X. We need this for sign and zero
2966 enum machine_mode mode_arg0;
2971 /* Try to perform some initial simplifications on X. */
2972 code = GET_CODE (x);
2977 if ((new = equiv_constant (x)) != NULL_RTX)
2989 /* No use simplifying an EXPR_LIST
2990 since they are used only for lists of args
2991 in a function call's REG_EQUAL note. */
2997 return prev_insn_cc0;
3003 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3004 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3005 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3009 #ifdef NO_FUNCTION_CSE
3011 if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3016 /* Anything else goes through the loop below. */
3021 mode = GET_MODE (x);
3025 mode_arg0 = VOIDmode;
3027 /* Try folding our operands.
3028 Then see which ones have constant values known. */
3030 fmt = GET_RTX_FORMAT (code);
3031 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3034 rtx folded_arg = XEXP (x, i), const_arg;
3035 enum machine_mode mode_arg = GET_MODE (folded_arg);
3037 switch (GET_CODE (folded_arg))
3042 const_arg = equiv_constant (folded_arg);
3051 const_arg = folded_arg;
3056 folded_arg = prev_insn_cc0;
3057 mode_arg = prev_insn_cc0_mode;
3058 const_arg = equiv_constant (folded_arg);
3063 folded_arg = fold_rtx (folded_arg, insn);
3064 const_arg = equiv_constant (folded_arg);
3068 /* For the first three operands, see if the operand
3069 is constant or equivalent to a constant. */
3073 folded_arg0 = folded_arg;
3074 const_arg0 = const_arg;
3075 mode_arg0 = mode_arg;
3078 folded_arg1 = folded_arg;
3079 const_arg1 = const_arg;
3082 const_arg2 = const_arg;
3086 /* Pick the least expensive of the argument and an equivalent constant
3089 && const_arg != folded_arg
3090 && COST_IN (const_arg, code) <= COST_IN (folded_arg, code)
3092 /* It's not safe to substitute the operand of a conversion
3093 operator with a constant, as the conversion's identity
3094 depends upon the mode of its operand. This optimization
3095 is handled by the call to simplify_unary_operation. */
3096 && (GET_RTX_CLASS (code) != RTX_UNARY
3097 || GET_MODE (const_arg) == mode_arg0
3098 || (code != ZERO_EXTEND
3099 && code != SIGN_EXTEND
3101 && code != FLOAT_TRUNCATE
3102 && code != FLOAT_EXTEND
3105 && code != UNSIGNED_FLOAT
3106 && code != UNSIGNED_FIX)))
3107 folded_arg = const_arg;
3109 if (folded_arg == XEXP (x, i))
3112 if (insn == NULL_RTX && !changed)
3115 validate_change (insn, &XEXP (x, i), folded_arg, 1);
3120 /* Canonicalize X if necessary, and keep const_argN and folded_argN
3121 consistent with the order in X. */
3122 if (canonicalize_change_group (insn, x))
3125 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3126 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3129 apply_change_group ();
3132 /* If X is an arithmetic operation, see if we can simplify it. */
3134 switch (GET_RTX_CLASS (code))
3140 /* We can't simplify extension ops unless we know the
3142 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3143 && mode_arg0 == VOIDmode)
3146 /* If we had a CONST, strip it off and put it back later if we
3148 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3149 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3151 new = simplify_unary_operation (code, mode,
3152 const_arg0 ? const_arg0 : folded_arg0,
3154 /* NEG of PLUS could be converted into MINUS, but that causes
3155 expressions of the form
3156 (CONST (MINUS (CONST_INT) (SYMBOL_REF)))
3157 which many ports mistakenly treat as LEGITIMATE_CONSTANT_P.
3158 FIXME: those ports should be fixed. */
3159 if (new != 0 && is_const
3160 && GET_CODE (new) == PLUS
3161 && (GET_CODE (XEXP (new, 0)) == SYMBOL_REF
3162 || GET_CODE (XEXP (new, 0)) == LABEL_REF)
3163 && GET_CODE (XEXP (new, 1)) == CONST_INT)
3164 new = gen_rtx_CONST (mode, new);
3169 case RTX_COMM_COMPARE:
3170 /* See what items are actually being compared and set FOLDED_ARG[01]
3171 to those values and CODE to the actual comparison code. If any are
3172 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3173 do anything if both operands are already known to be constant. */
3175 /* ??? Vector mode comparisons are not supported yet. */
3176 if (VECTOR_MODE_P (mode))
3179 if (const_arg0 == 0 || const_arg1 == 0)
3181 struct table_elt *p0, *p1;
3182 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3183 enum machine_mode mode_arg1;
3185 #ifdef FLOAT_STORE_FLAG_VALUE
3186 if (SCALAR_FLOAT_MODE_P (mode))
3188 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3189 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3190 false_rtx = CONST0_RTX (mode);
3194 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3195 &mode_arg0, &mode_arg1);
3197 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3198 what kinds of things are being compared, so we can't do
3199 anything with this comparison. */
3201 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3204 const_arg0 = equiv_constant (folded_arg0);
3205 const_arg1 = equiv_constant (folded_arg1);
3207 /* If we do not now have two constants being compared, see
3208 if we can nevertheless deduce some things about the
3210 if (const_arg0 == 0 || const_arg1 == 0)
3212 if (const_arg1 != NULL)
3214 rtx cheapest_simplification;
3217 struct table_elt *p;
3219 /* See if we can find an equivalent of folded_arg0
3220 that gets us a cheaper expression, possibly a
3221 constant through simplifications. */
3222 p = lookup (folded_arg0, SAFE_HASH (folded_arg0, mode_arg0),
3227 cheapest_simplification = x;
3228 cheapest_cost = COST (x);
3230 for (p = p->first_same_value; p != NULL; p = p->next_same_value)
3234 /* If the entry isn't valid, skip it. */
3235 if (! exp_equiv_p (p->exp, p->exp, 1, false))
3238 /* Try to simplify using this equivalence. */
3240 = simplify_relational_operation (code, mode,
3245 if (simp_result == NULL)
3248 cost = COST (simp_result);
3249 if (cost < cheapest_cost)
3251 cheapest_cost = cost;
3252 cheapest_simplification = simp_result;
3256 /* If we have a cheaper expression now, use that
3257 and try folding it further, from the top. */
3258 if (cheapest_simplification != x)
3259 return fold_rtx (cheapest_simplification, insn);
3263 /* Some addresses are known to be nonzero. We don't know
3264 their sign, but equality comparisons are known. */
3265 if (const_arg1 == const0_rtx
3266 && nonzero_address_p (folded_arg0))
3270 else if (code == NE)
3274 /* See if the two operands are the same. */
3276 if (folded_arg0 == folded_arg1
3277 || (REG_P (folded_arg0)
3278 && REG_P (folded_arg1)
3279 && (REG_QTY (REGNO (folded_arg0))
3280 == REG_QTY (REGNO (folded_arg1))))
3281 || ((p0 = lookup (folded_arg0,
3282 SAFE_HASH (folded_arg0, mode_arg0),
3284 && (p1 = lookup (folded_arg1,
3285 SAFE_HASH (folded_arg1, mode_arg0),
3287 && p0->first_same_value == p1->first_same_value))
3289 /* Sadly two equal NaNs are not equivalent. */
3290 if (!HONOR_NANS (mode_arg0))
3291 return ((code == EQ || code == LE || code == GE
3292 || code == LEU || code == GEU || code == UNEQ
3293 || code == UNLE || code == UNGE
3295 ? true_rtx : false_rtx);
3296 /* Take care for the FP compares we can resolve. */
3297 if (code == UNEQ || code == UNLE || code == UNGE)
3299 if (code == LTGT || code == LT || code == GT)
3303 /* If FOLDED_ARG0 is a register, see if the comparison we are
3304 doing now is either the same as we did before or the reverse
3305 (we only check the reverse if not floating-point). */
3306 else if (REG_P (folded_arg0))
3308 int qty = REG_QTY (REGNO (folded_arg0));
3310 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3312 struct qty_table_elem *ent = &qty_table[qty];
3314 if ((comparison_dominates_p (ent->comparison_code, code)
3315 || (! FLOAT_MODE_P (mode_arg0)
3316 && comparison_dominates_p (ent->comparison_code,
3317 reverse_condition (code))))
3318 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3320 && rtx_equal_p (ent->comparison_const,
3322 || (REG_P (folded_arg1)
3323 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3324 return (comparison_dominates_p (ent->comparison_code, code)
3325 ? true_rtx : false_rtx);
3331 /* If we are comparing against zero, see if the first operand is
3332 equivalent to an IOR with a constant. If so, we may be able to
3333 determine the result of this comparison. */
3335 if (const_arg1 == const0_rtx)
3337 rtx y = lookup_as_function (folded_arg0, IOR);
3341 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3342 && GET_CODE (inner_const) == CONST_INT
3343 && INTVAL (inner_const) != 0)
3345 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
3346 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
3347 && (INTVAL (inner_const)
3348 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
3349 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3351 #ifdef FLOAT_STORE_FLAG_VALUE
3352 if (SCALAR_FLOAT_MODE_P (mode))
3354 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3355 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3356 false_rtx = CONST0_RTX (mode);
3381 rtx op0 = const_arg0 ? const_arg0 : folded_arg0;
3382 rtx op1 = const_arg1 ? const_arg1 : folded_arg1;
3383 new = simplify_relational_operation (code, mode, mode_arg0, op0, op1);
3388 case RTX_COMM_ARITH:
3392 /* If the second operand is a LABEL_REF, see if the first is a MINUS
3393 with that LABEL_REF as its second operand. If so, the result is
3394 the first operand of that MINUS. This handles switches with an
3395 ADDR_DIFF_VEC table. */
3396 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
3399 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
3400 : lookup_as_function (folded_arg0, MINUS);
3402 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3403 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
3406 /* Now try for a CONST of a MINUS like the above. */
3407 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
3408 : lookup_as_function (folded_arg0, CONST))) != 0
3409 && GET_CODE (XEXP (y, 0)) == MINUS
3410 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3411 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
3412 return XEXP (XEXP (y, 0), 0);
3415 /* Likewise if the operands are in the other order. */
3416 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
3419 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
3420 : lookup_as_function (folded_arg1, MINUS);
3422 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3423 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
3426 /* Now try for a CONST of a MINUS like the above. */
3427 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
3428 : lookup_as_function (folded_arg1, CONST))) != 0
3429 && GET_CODE (XEXP (y, 0)) == MINUS
3430 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3431 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
3432 return XEXP (XEXP (y, 0), 0);
3435 /* If second operand is a register equivalent to a negative
3436 CONST_INT, see if we can find a register equivalent to the
3437 positive constant. Make a MINUS if so. Don't do this for
3438 a non-negative constant since we might then alternate between
3439 choosing positive and negative constants. Having the positive
3440 constant previously-used is the more common case. Be sure
3441 the resulting constant is non-negative; if const_arg1 were
3442 the smallest negative number this would overflow: depending
3443 on the mode, this would either just be the same value (and
3444 hence not save anything) or be incorrect. */
3445 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
3446 && INTVAL (const_arg1) < 0
3447 /* This used to test
3449 -INTVAL (const_arg1) >= 0
3451 But The Sun V5.0 compilers mis-compiled that test. So
3452 instead we test for the problematic value in a more direct
3453 manner and hope the Sun compilers get it correct. */
3454 && INTVAL (const_arg1) !=
3455 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
3456 && REG_P (folded_arg1))
3458 rtx new_const = GEN_INT (-INTVAL (const_arg1));
3460 = lookup (new_const, SAFE_HASH (new_const, mode), mode);
3463 for (p = p->first_same_value; p; p = p->next_same_value)
3465 return simplify_gen_binary (MINUS, mode, folded_arg0,
3466 canon_reg (p->exp, NULL_RTX));
3471 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3472 If so, produce (PLUS Z C2-C). */
3473 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
3475 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
3476 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
3477 return fold_rtx (plus_constant (copy_rtx (y),
3478 -INTVAL (const_arg1)),
3485 case SMIN: case SMAX: case UMIN: case UMAX:
3486 case IOR: case AND: case XOR:
3488 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
3489 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3490 is known to be of similar form, we may be able to replace the
3491 operation with a combined operation. This may eliminate the
3492 intermediate operation if every use is simplified in this way.
3493 Note that the similar optimization done by combine.c only works
3494 if the intermediate operation's result has only one reference. */
3496 if (REG_P (folded_arg0)
3497 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
3500 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
3501 rtx y, inner_const, new_const;
3502 enum rtx_code associate_code;
3505 && (INTVAL (const_arg1) >= GET_MODE_BITSIZE (mode)
3506 || INTVAL (const_arg1) < 0))
3508 if (SHIFT_COUNT_TRUNCATED)
3509 const_arg1 = GEN_INT (INTVAL (const_arg1)
3510 & (GET_MODE_BITSIZE (mode) - 1));
3515 y = lookup_as_function (folded_arg0, code);
3519 /* If we have compiled a statement like
3520 "if (x == (x & mask1))", and now are looking at
3521 "x & mask2", we will have a case where the first operand
3522 of Y is the same as our first operand. Unless we detect
3523 this case, an infinite loop will result. */
3524 if (XEXP (y, 0) == folded_arg0)
3527 inner_const = equiv_constant (fold_rtx (XEXP (y, 1), 0));
3528 if (!inner_const || GET_CODE (inner_const) != CONST_INT)
3531 /* Don't associate these operations if they are a PLUS with the
3532 same constant and it is a power of two. These might be doable
3533 with a pre- or post-increment. Similarly for two subtracts of
3534 identical powers of two with post decrement. */
3536 if (code == PLUS && const_arg1 == inner_const
3537 && ((HAVE_PRE_INCREMENT
3538 && exact_log2 (INTVAL (const_arg1)) >= 0)
3539 || (HAVE_POST_INCREMENT
3540 && exact_log2 (INTVAL (const_arg1)) >= 0)
3541 || (HAVE_PRE_DECREMENT
3542 && exact_log2 (- INTVAL (const_arg1)) >= 0)
3543 || (HAVE_POST_DECREMENT
3544 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
3548 && (INTVAL (inner_const) >= GET_MODE_BITSIZE (mode)
3549 || INTVAL (inner_const) < 0))
3551 if (SHIFT_COUNT_TRUNCATED)
3552 inner_const = GEN_INT (INTVAL (inner_const)
3553 & (GET_MODE_BITSIZE (mode) - 1));
3558 /* Compute the code used to compose the constants. For example,
3559 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
3561 associate_code = (is_shift || code == MINUS ? PLUS : code);
3563 new_const = simplify_binary_operation (associate_code, mode,
3564 const_arg1, inner_const);
3569 /* If we are associating shift operations, don't let this
3570 produce a shift of the size of the object or larger.
3571 This could occur when we follow a sign-extend by a right
3572 shift on a machine that does a sign-extend as a pair
3576 && GET_CODE (new_const) == CONST_INT
3577 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
3579 /* As an exception, we can turn an ASHIFTRT of this
3580 form into a shift of the number of bits - 1. */
3581 if (code == ASHIFTRT)
3582 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
3583 else if (!side_effects_p (XEXP (y, 0)))
3584 return CONST0_RTX (mode);
3589 y = copy_rtx (XEXP (y, 0));
3591 /* If Y contains our first operand (the most common way this
3592 can happen is if Y is a MEM), we would do into an infinite
3593 loop if we tried to fold it. So don't in that case. */
3595 if (! reg_mentioned_p (folded_arg0, y))
3596 y = fold_rtx (y, insn);
3598 return simplify_gen_binary (code, mode, y, new_const);
3602 case DIV: case UDIV:
3603 /* ??? The associative optimization performed immediately above is
3604 also possible for DIV and UDIV using associate_code of MULT.
3605 However, we would need extra code to verify that the
3606 multiplication does not overflow, that is, there is no overflow
3607 in the calculation of new_const. */
3614 new = simplify_binary_operation (code, mode,
3615 const_arg0 ? const_arg0 : folded_arg0,
3616 const_arg1 ? const_arg1 : folded_arg1);
3620 /* (lo_sum (high X) X) is simply X. */
3621 if (code == LO_SUM && const_arg0 != 0
3622 && GET_CODE (const_arg0) == HIGH
3623 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
3628 case RTX_BITFIELD_OPS:
3629 new = simplify_ternary_operation (code, mode, mode_arg0,
3630 const_arg0 ? const_arg0 : folded_arg0,
3631 const_arg1 ? const_arg1 : folded_arg1,
3632 const_arg2 ? const_arg2 : XEXP (x, 2));
3639 return new ? new : x;
3642 /* Return a constant value currently equivalent to X.
3643 Return 0 if we don't know one. */
3646 equiv_constant (rtx x)
3649 && REGNO_QTY_VALID_P (REGNO (x)))
3651 int x_q = REG_QTY (REGNO (x));
3652 struct qty_table_elem *x_ent = &qty_table[x_q];
3654 if (x_ent->const_rtx)
3655 x = gen_lowpart (GET_MODE (x), x_ent->const_rtx);
3658 if (x == 0 || CONSTANT_P (x))
3661 if (GET_CODE (x) == SUBREG)
3665 /* See if we previously assigned a constant value to this SUBREG. */
3666 if ((new = lookup_as_function (x, CONST_INT)) != 0
3667 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3670 if (REG_P (SUBREG_REG (x))
3671 && (new = equiv_constant (SUBREG_REG (x))) != 0)
3672 return simplify_subreg (GET_MODE (x), SUBREG_REG (x),
3673 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3678 /* If X is a MEM, see if it is a constant-pool reference, or look it up in
3679 the hash table in case its value was seen before. */
3683 struct table_elt *elt;
3685 x = avoid_constant_pool_reference (x);
3689 elt = lookup (x, SAFE_HASH (x, GET_MODE (x)), GET_MODE (x));
3693 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3694 if (elt->is_const && CONSTANT_P (elt->exp))
3701 /* Given INSN, a jump insn, TAKEN indicates if we are following the
3704 In certain cases, this can cause us to add an equivalence. For example,
3705 if we are following the taken case of
3707 we can add the fact that `i' and '2' are now equivalent.
3709 In any case, we can record that this comparison was passed. If the same
3710 comparison is seen later, we will know its value. */
3713 record_jump_equiv (rtx insn, bool taken)
3715 int cond_known_true;
3718 enum machine_mode mode, mode0, mode1;
3719 int reversed_nonequality = 0;
3722 /* Ensure this is the right kind of insn. */
3723 gcc_assert (any_condjump_p (insn));
3725 set = pc_set (insn);
3727 /* See if this jump condition is known true or false. */
3729 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
3731 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
3733 /* Get the type of comparison being done and the operands being compared.
3734 If we had to reverse a non-equality condition, record that fact so we
3735 know that it isn't valid for floating-point. */
3736 code = GET_CODE (XEXP (SET_SRC (set), 0));
3737 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
3738 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
3740 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
3741 if (! cond_known_true)
3743 code = reversed_comparison_code_parts (code, op0, op1, insn);
3745 /* Don't remember if we can't find the inverse. */
3746 if (code == UNKNOWN)
3750 /* The mode is the mode of the non-constant. */
3752 if (mode1 != VOIDmode)
3755 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
3758 /* Yet another form of subreg creation. In this case, we want something in
3759 MODE, and we should assume OP has MODE iff it is naturally modeless. */
3762 record_jump_cond_subreg (enum machine_mode mode, rtx op)
3764 enum machine_mode op_mode = GET_MODE (op);
3765 if (op_mode == mode || op_mode == VOIDmode)
3767 return lowpart_subreg (mode, op, op_mode);
3770 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
3771 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
3772 Make any useful entries we can with that information. Called from
3773 above function and called recursively. */
3776 record_jump_cond (enum rtx_code code, enum machine_mode mode, rtx op0,
3777 rtx op1, int reversed_nonequality)
3779 unsigned op0_hash, op1_hash;
3780 int op0_in_memory, op1_in_memory;
3781 struct table_elt *op0_elt, *op1_elt;
3783 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
3784 we know that they are also equal in the smaller mode (this is also
3785 true for all smaller modes whether or not there is a SUBREG, but
3786 is not worth testing for with no SUBREG). */
3788 /* Note that GET_MODE (op0) may not equal MODE. */
3789 if (code == EQ && GET_CODE (op0) == SUBREG
3790 && (GET_MODE_SIZE (GET_MODE (op0))
3791 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3793 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3794 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3796 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3797 reversed_nonequality);
3800 if (code == EQ && GET_CODE (op1) == SUBREG
3801 && (GET_MODE_SIZE (GET_MODE (op1))
3802 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3804 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3805 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3807 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3808 reversed_nonequality);
3811 /* Similarly, if this is an NE comparison, and either is a SUBREG
3812 making a smaller mode, we know the whole thing is also NE. */
3814 /* Note that GET_MODE (op0) may not equal MODE;
3815 if we test MODE instead, we can get an infinite recursion
3816 alternating between two modes each wider than MODE. */
3818 if (code == NE && GET_CODE (op0) == SUBREG
3819 && subreg_lowpart_p (op0)
3820 && (GET_MODE_SIZE (GET_MODE (op0))
3821 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
3823 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
3824 rtx tem = record_jump_cond_subreg (inner_mode, op1);
3826 record_jump_cond (code, mode, SUBREG_REG (op0), tem,
3827 reversed_nonequality);
3830 if (code == NE && GET_CODE (op1) == SUBREG
3831 && subreg_lowpart_p (op1)
3832 && (GET_MODE_SIZE (GET_MODE (op1))
3833 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
3835 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
3836 rtx tem = record_jump_cond_subreg (inner_mode, op0);
3838 record_jump_cond (code, mode, SUBREG_REG (op1), tem,
3839 reversed_nonequality);
3842 /* Hash both operands. */
3845 hash_arg_in_memory = 0;
3846 op0_hash = HASH (op0, mode);
3847 op0_in_memory = hash_arg_in_memory;
3853 hash_arg_in_memory = 0;
3854 op1_hash = HASH (op1, mode);
3855 op1_in_memory = hash_arg_in_memory;
3860 /* Look up both operands. */
3861 op0_elt = lookup (op0, op0_hash, mode);
3862 op1_elt = lookup (op1, op1_hash, mode);
3864 /* If both operands are already equivalent or if they are not in the
3865 table but are identical, do nothing. */
3866 if ((op0_elt != 0 && op1_elt != 0
3867 && op0_elt->first_same_value == op1_elt->first_same_value)
3868 || op0 == op1 || rtx_equal_p (op0, op1))
3871 /* If we aren't setting two things equal all we can do is save this
3872 comparison. Similarly if this is floating-point. In the latter
3873 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
3874 If we record the equality, we might inadvertently delete code
3875 whose intent was to change -0 to +0. */
3877 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
3879 struct qty_table_elem *ent;
3882 /* If we reversed a floating-point comparison, if OP0 is not a
3883 register, or if OP1 is neither a register or constant, we can't
3887 op1 = equiv_constant (op1);
3889 if ((reversed_nonequality && FLOAT_MODE_P (mode))
3890 || !REG_P (op0) || op1 == 0)
3893 /* Put OP0 in the hash table if it isn't already. This gives it a
3894 new quantity number. */
3897 if (insert_regs (op0, NULL, 0))
3899 rehash_using_reg (op0);
3900 op0_hash = HASH (op0, mode);
3902 /* If OP0 is contained in OP1, this changes its hash code
3903 as well. Faster to rehash than to check, except
3904 for the simple case of a constant. */
3905 if (! CONSTANT_P (op1))
3906 op1_hash = HASH (op1,mode);
3909 op0_elt = insert (op0, NULL, op0_hash, mode);
3910 op0_elt->in_memory = op0_in_memory;
3913 qty = REG_QTY (REGNO (op0));
3914 ent = &qty_table[qty];
3916 ent->comparison_code = code;
3919 /* Look it up again--in case op0 and op1 are the same. */
3920 op1_elt = lookup (op1, op1_hash, mode);
3922 /* Put OP1 in the hash table so it gets a new quantity number. */
3925 if (insert_regs (op1, NULL, 0))
3927 rehash_using_reg (op1);
3928 op1_hash = HASH (op1, mode);
3931 op1_elt = insert (op1, NULL, op1_hash, mode);
3932 op1_elt->in_memory = op1_in_memory;
3935 ent->comparison_const = NULL_RTX;
3936 ent->comparison_qty = REG_QTY (REGNO (op1));
3940 ent->comparison_const = op1;
3941 ent->comparison_qty = -1;
3947 /* If either side is still missing an equivalence, make it now,
3948 then merge the equivalences. */
3952 if (insert_regs (op0, NULL, 0))
3954 rehash_using_reg (op0);
3955 op0_hash = HASH (op0, mode);
3958 op0_elt = insert (op0, NULL, op0_hash, mode);
3959 op0_elt->in_memory = op0_in_memory;
3964 if (insert_regs (op1, NULL, 0))
3966 rehash_using_reg (op1);
3967 op1_hash = HASH (op1, mode);
3970 op1_elt = insert (op1, NULL, op1_hash, mode);
3971 op1_elt->in_memory = op1_in_memory;
3974 merge_equiv_classes (op0_elt, op1_elt);
3977 /* CSE processing for one instruction.
3978 First simplify sources and addresses of all assignments
3979 in the instruction, using previously-computed equivalents values.
3980 Then install the new sources and destinations in the table
3981 of available values.
3983 If LIBCALL_INSN is nonzero, don't record any equivalence made in
3984 the insn. It means that INSN is inside libcall block. In this
3985 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
3987 /* Data on one SET contained in the instruction. */
3991 /* The SET rtx itself. */
3993 /* The SET_SRC of the rtx (the original value, if it is changing). */
3995 /* The hash-table element for the SET_SRC of the SET. */
3996 struct table_elt *src_elt;
3997 /* Hash value for the SET_SRC. */
3999 /* Hash value for the SET_DEST. */
4001 /* The SET_DEST, with SUBREG, etc., stripped. */
4003 /* Nonzero if the SET_SRC is in memory. */
4005 /* Nonzero if the SET_SRC contains something
4006 whose value cannot be predicted and understood. */
4008 /* Original machine mode, in case it becomes a CONST_INT.
4009 The size of this field should match the size of the mode
4010 field of struct rtx_def (see rtl.h). */
4011 ENUM_BITFIELD(machine_mode) mode : 8;
4012 /* A constant equivalent for SET_SRC, if any. */
4014 /* Original SET_SRC value used for libcall notes. */
4016 /* Hash value of constant equivalent for SET_SRC. */
4017 unsigned src_const_hash;
4018 /* Table entry for constant equivalent for SET_SRC, if any. */
4019 struct table_elt *src_const_elt;
4020 /* Table entry for the destination address. */
4021 struct table_elt *dest_addr_elt;
4025 cse_insn (rtx insn, rtx libcall_insn)
4027 rtx x = PATTERN (insn);
4033 struct table_elt *src_eqv_elt = 0;
4034 int src_eqv_volatile = 0;
4035 int src_eqv_in_memory = 0;
4036 unsigned src_eqv_hash = 0;
4038 struct set *sets = (struct set *) 0;
4042 /* Records what this insn does to set CC0. */
4044 this_insn_cc0_mode = VOIDmode;
4047 /* Find all the SETs and CLOBBERs in this instruction.
4048 Record all the SETs in the array `set' and count them.
4049 Also determine whether there is a CLOBBER that invalidates
4050 all memory references, or all references at varying addresses. */
4054 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4056 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4057 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4058 XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4062 if (GET_CODE (x) == SET)
4064 sets = alloca (sizeof (struct set));
4067 /* Ignore SETs that are unconditional jumps.
4068 They never need cse processing, so this does not hurt.
4069 The reason is not efficiency but rather
4070 so that we can test at the end for instructions
4071 that have been simplified to unconditional jumps
4072 and not be misled by unchanged instructions
4073 that were unconditional jumps to begin with. */
4074 if (SET_DEST (x) == pc_rtx
4075 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4078 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4079 The hard function value register is used only once, to copy to
4080 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4081 Ensure we invalidate the destination register. On the 80386 no
4082 other code would invalidate it since it is a fixed_reg.
4083 We need not check the return of apply_change_group; see canon_reg. */
4085 else if (GET_CODE (SET_SRC (x)) == CALL)
4087 canon_reg (SET_SRC (x), insn);
4088 apply_change_group ();
4089 fold_rtx (SET_SRC (x), insn);
4090 invalidate (SET_DEST (x), VOIDmode);
4095 else if (GET_CODE (x) == PARALLEL)
4097 int lim = XVECLEN (x, 0);
4099 sets = alloca (lim * sizeof (struct set));
4101 /* Find all regs explicitly clobbered in this insn,
4102 and ensure they are not replaced with any other regs
4103 elsewhere in this insn.
4104 When a reg that is clobbered is also used for input,
4105 we should presume that that is for a reason,
4106 and we should not substitute some other register
4107 which is not supposed to be clobbered.
4108 Therefore, this loop cannot be merged into the one below
4109 because a CALL may precede a CLOBBER and refer to the
4110 value clobbered. We must not let a canonicalization do
4111 anything in that case. */
4112 for (i = 0; i < lim; i++)
4114 rtx y = XVECEXP (x, 0, i);
4115 if (GET_CODE (y) == CLOBBER)
4117 rtx clobbered = XEXP (y, 0);
4119 if (REG_P (clobbered)
4120 || GET_CODE (clobbered) == SUBREG)
4121 invalidate (clobbered, VOIDmode);
4122 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4123 || GET_CODE (clobbered) == ZERO_EXTRACT)
4124 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4128 for (i = 0; i < lim; i++)
4130 rtx y = XVECEXP (x, 0, i);
4131 if (GET_CODE (y) == SET)
4133 /* As above, we ignore unconditional jumps and call-insns and
4134 ignore the result of apply_change_group. */
4135 if (GET_CODE (SET_SRC (y)) == CALL)
4137 canon_reg (SET_SRC (y), insn);
4138 apply_change_group ();
4139 fold_rtx (SET_SRC (y), insn);
4140 invalidate (SET_DEST (y), VOIDmode);
4142 else if (SET_DEST (y) == pc_rtx
4143 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4146 sets[n_sets++].rtl = y;
4148 else if (GET_CODE (y) == CLOBBER)
4150 /* If we clobber memory, canon the address.
4151 This does nothing when a register is clobbered
4152 because we have already invalidated the reg. */
4153 if (MEM_P (XEXP (y, 0)))
4154 canon_reg (XEXP (y, 0), NULL_RTX);
4156 else if (GET_CODE (y) == USE
4157 && ! (REG_P (XEXP (y, 0))
4158 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4159 canon_reg (y, NULL_RTX);
4160 else if (GET_CODE (y) == CALL)
4162 /* The result of apply_change_group can be ignored; see
4164 canon_reg (y, insn);
4165 apply_change_group ();
4170 else if (GET_CODE (x) == CLOBBER)
4172 if (MEM_P (XEXP (x, 0)))
4173 canon_reg (XEXP (x, 0), NULL_RTX);
4176 /* Canonicalize a USE of a pseudo register or memory location. */
4177 else if (GET_CODE (x) == USE
4178 && ! (REG_P (XEXP (x, 0))
4179 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4180 canon_reg (XEXP (x, 0), NULL_RTX);
4181 else if (GET_CODE (x) == CALL)
4183 /* The result of apply_change_group can be ignored; see canon_reg. */
4184 canon_reg (x, insn);
4185 apply_change_group ();
4189 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4190 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4191 is handled specially for this case, and if it isn't set, then there will
4192 be no equivalence for the destination. */
4193 if (n_sets == 1 && REG_NOTES (insn) != 0
4194 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4195 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4196 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4198 src_eqv = fold_rtx (canon_reg (XEXP (tem, 0), NULL_RTX), insn);
4199 XEXP (tem, 0) = src_eqv;
4202 /* Canonicalize sources and addresses of destinations.
4203 We do this in a separate pass to avoid problems when a MATCH_DUP is
4204 present in the insn pattern. In that case, we want to ensure that
4205 we don't break the duplicate nature of the pattern. So we will replace
4206 both operands at the same time. Otherwise, we would fail to find an
4207 equivalent substitution in the loop calling validate_change below.
4209 We used to suppress canonicalization of DEST if it appears in SRC,
4210 but we don't do this any more. */
4212 for (i = 0; i < n_sets; i++)
4214 rtx dest = SET_DEST (sets[i].rtl);
4215 rtx src = SET_SRC (sets[i].rtl);
4216 rtx new = canon_reg (src, insn);
4218 sets[i].orig_src = src;
4219 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4221 if (GET_CODE (dest) == ZERO_EXTRACT)
4223 validate_change (insn, &XEXP (dest, 1),
4224 canon_reg (XEXP (dest, 1), insn), 1);
4225 validate_change (insn, &XEXP (dest, 2),
4226 canon_reg (XEXP (dest, 2), insn), 1);
4229 while (GET_CODE (dest) == SUBREG
4230 || GET_CODE (dest) == ZERO_EXTRACT
4231 || GET_CODE (dest) == STRICT_LOW_PART)
4232 dest = XEXP (dest, 0);
4235 canon_reg (dest, insn);
4238 /* Now that we have done all the replacements, we can apply the change
4239 group and see if they all work. Note that this will cause some
4240 canonicalizations that would have worked individually not to be applied
4241 because some other canonicalization didn't work, but this should not
4244 The result of apply_change_group can be ignored; see canon_reg. */
4246 apply_change_group ();
4248 /* Set sets[i].src_elt to the class each source belongs to.
4249 Detect assignments from or to volatile things
4250 and set set[i] to zero so they will be ignored
4251 in the rest of this function.
4253 Nothing in this loop changes the hash table or the register chains. */
4255 for (i = 0; i < n_sets; i++)
4259 struct table_elt *elt = 0, *p;
4260 enum machine_mode mode;
4263 rtx src_related = 0;
4264 struct table_elt *src_const_elt = 0;
4265 int src_cost = MAX_COST;
4266 int src_eqv_cost = MAX_COST;
4267 int src_folded_cost = MAX_COST;
4268 int src_related_cost = MAX_COST;
4269 int src_elt_cost = MAX_COST;
4270 int src_regcost = MAX_COST;
4271 int src_eqv_regcost = MAX_COST;
4272 int src_folded_regcost = MAX_COST;
4273 int src_related_regcost = MAX_COST;
4274 int src_elt_regcost = MAX_COST;
4275 /* Set nonzero if we need to call force_const_mem on with the
4276 contents of src_folded before using it. */
4277 int src_folded_force_flag = 0;
4279 dest = SET_DEST (sets[i].rtl);
4280 src = SET_SRC (sets[i].rtl);
4282 /* If SRC is a constant that has no machine mode,
4283 hash it with the destination's machine mode.
4284 This way we can keep different modes separate. */
4286 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4287 sets[i].mode = mode;
4291 enum machine_mode eqvmode = mode;
4292 if (GET_CODE (dest) == STRICT_LOW_PART)
4293 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4295 hash_arg_in_memory = 0;
4296 src_eqv_hash = HASH (src_eqv, eqvmode);
4298 /* Find the equivalence class for the equivalent expression. */
4301 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4303 src_eqv_volatile = do_not_record;
4304 src_eqv_in_memory = hash_arg_in_memory;
4307 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4308 value of the INNER register, not the destination. So it is not
4309 a valid substitution for the source. But save it for later. */
4310 if (GET_CODE (dest) == STRICT_LOW_PART)
4313 src_eqv_here = src_eqv;
4315 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4316 simplified result, which may not necessarily be valid. */
4317 src_folded = fold_rtx (src, insn);
4320 /* ??? This caused bad code to be generated for the m68k port with -O2.
4321 Suppose src is (CONST_INT -1), and that after truncation src_folded
4322 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4323 At the end we will add src and src_const to the same equivalence
4324 class. We now have 3 and -1 on the same equivalence class. This
4325 causes later instructions to be mis-optimized. */
4326 /* If storing a constant in a bitfield, pre-truncate the constant
4327 so we will be able to record it later. */
4328 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT)
4330 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
4332 if (GET_CODE (src) == CONST_INT
4333 && GET_CODE (width) == CONST_INT
4334 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
4335 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
4337 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
4338 << INTVAL (width)) - 1));
4342 /* Compute SRC's hash code, and also notice if it
4343 should not be recorded at all. In that case,
4344 prevent any further processing of this assignment. */
4346 hash_arg_in_memory = 0;
4349 sets[i].src_hash = HASH (src, mode);
4350 sets[i].src_volatile = do_not_record;
4351 sets[i].src_in_memory = hash_arg_in_memory;
4353 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4354 a pseudo, do not record SRC. Using SRC as a replacement for
4355 anything else will be incorrect in that situation. Note that
4356 this usually occurs only for stack slots, in which case all the
4357 RTL would be referring to SRC, so we don't lose any optimization
4358 opportunities by not having SRC in the hash table. */
4361 && find_reg_note (insn, REG_EQUIV, NULL_RTX) != 0
4363 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
4364 sets[i].src_volatile = 1;
4367 /* It is no longer clear why we used to do this, but it doesn't
4368 appear to still be needed. So let's try without it since this
4369 code hurts cse'ing widened ops. */
4370 /* If source is a paradoxical subreg (such as QI treated as an SI),
4371 treat it as volatile. It may do the work of an SI in one context
4372 where the extra bits are not being used, but cannot replace an SI
4374 if (GET_CODE (src) == SUBREG
4375 && (GET_MODE_SIZE (GET_MODE (src))
4376 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
4377 sets[i].src_volatile = 1;
4380 /* Locate all possible equivalent forms for SRC. Try to replace
4381 SRC in the insn with each cheaper equivalent.
4383 We have the following types of equivalents: SRC itself, a folded
4384 version, a value given in a REG_EQUAL note, or a value related
4387 Each of these equivalents may be part of an additional class
4388 of equivalents (if more than one is in the table, they must be in
4389 the same class; we check for this).
4391 If the source is volatile, we don't do any table lookups.
4393 We note any constant equivalent for possible later use in a
4396 if (!sets[i].src_volatile)
4397 elt = lookup (src, sets[i].src_hash, mode);
4399 sets[i].src_elt = elt;
4401 if (elt && src_eqv_here && src_eqv_elt)
4403 if (elt->first_same_value != src_eqv_elt->first_same_value)
4405 /* The REG_EQUAL is indicating that two formerly distinct
4406 classes are now equivalent. So merge them. */
4407 merge_equiv_classes (elt, src_eqv_elt);
4408 src_eqv_hash = HASH (src_eqv, elt->mode);
4409 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
4415 else if (src_eqv_elt)
4418 /* Try to find a constant somewhere and record it in `src_const'.
4419 Record its table element, if any, in `src_const_elt'. Look in
4420 any known equivalences first. (If the constant is not in the
4421 table, also set `sets[i].src_const_hash'). */
4423 for (p = elt->first_same_value; p; p = p->next_same_value)
4427 src_const_elt = elt;
4432 && (CONSTANT_P (src_folded)
4433 /* Consider (minus (label_ref L1) (label_ref L2)) as
4434 "constant" here so we will record it. This allows us
4435 to fold switch statements when an ADDR_DIFF_VEC is used. */
4436 || (GET_CODE (src_folded) == MINUS
4437 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
4438 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
4439 src_const = src_folded, src_const_elt = elt;
4440 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
4441 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
4443 /* If we don't know if the constant is in the table, get its
4444 hash code and look it up. */
4445 if (src_const && src_const_elt == 0)
4447 sets[i].src_const_hash = HASH (src_const, mode);
4448 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
4451 sets[i].src_const = src_const;
4452 sets[i].src_const_elt = src_const_elt;
4454 /* If the constant and our source are both in the table, mark them as
4455 equivalent. Otherwise, if a constant is in the table but the source
4456 isn't, set ELT to it. */
4457 if (src_const_elt && elt
4458 && src_const_elt->first_same_value != elt->first_same_value)
4459 merge_equiv_classes (elt, src_const_elt);
4460 else if (src_const_elt && elt == 0)
4461 elt = src_const_elt;
4463 /* See if there is a register linearly related to a constant
4464 equivalent of SRC. */
4466 && (GET_CODE (src_const) == CONST
4467 || (src_const_elt && src_const_elt->related_value != 0)))
4469 src_related = use_related_value (src_const, src_const_elt);
4472 struct table_elt *src_related_elt
4473 = lookup (src_related, HASH (src_related, mode), mode);
4474 if (src_related_elt && elt)
4476 if (elt->first_same_value
4477 != src_related_elt->first_same_value)
4478 /* This can occur when we previously saw a CONST
4479 involving a SYMBOL_REF and then see the SYMBOL_REF
4480 twice. Merge the involved classes. */
4481 merge_equiv_classes (elt, src_related_elt);
4484 src_related_elt = 0;
4486 else if (src_related_elt && elt == 0)
4487 elt = src_related_elt;
4491 /* See if we have a CONST_INT that is already in a register in a
4494 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
4495 && GET_MODE_CLASS (mode) == MODE_INT
4496 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
4498 enum machine_mode wider_mode;
4500 for (wider_mode = GET_MODE_WIDER_MODE (mode);
4501 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
4502 && src_related == 0;
4503 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
4505 struct table_elt *const_elt
4506 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
4511 for (const_elt = const_elt->first_same_value;
4512 const_elt; const_elt = const_elt->next_same_value)
4513 if (REG_P (const_elt->exp))
4515 src_related = gen_lowpart (mode, const_elt->exp);
4521 /* Another possibility is that we have an AND with a constant in
4522 a mode narrower than a word. If so, it might have been generated
4523 as part of an "if" which would narrow the AND. If we already
4524 have done the AND in a wider mode, we can use a SUBREG of that
4527 if (flag_expensive_optimizations && ! src_related
4528 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
4529 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4531 enum machine_mode tmode;
4532 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
4534 for (tmode = GET_MODE_WIDER_MODE (mode);
4535 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
4536 tmode = GET_MODE_WIDER_MODE (tmode))
4538 rtx inner = gen_lowpart (tmode, XEXP (src, 0));
4539 struct table_elt *larger_elt;
4543 PUT_MODE (new_and, tmode);
4544 XEXP (new_and, 0) = inner;
4545 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
4546 if (larger_elt == 0)
4549 for (larger_elt = larger_elt->first_same_value;
4550 larger_elt; larger_elt = larger_elt->next_same_value)
4551 if (REG_P (larger_elt->exp))
4554 = gen_lowpart (mode, larger_elt->exp);
4564 #ifdef LOAD_EXTEND_OP
4565 /* See if a MEM has already been loaded with a widening operation;
4566 if it has, we can use a subreg of that. Many CISC machines
4567 also have such operations, but this is only likely to be
4568 beneficial on these machines. */
4570 if (flag_expensive_optimizations && src_related == 0
4571 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4572 && GET_MODE_CLASS (mode) == MODE_INT
4573 && MEM_P (src) && ! do_not_record
4574 && LOAD_EXTEND_OP (mode) != UNKNOWN)
4576 struct rtx_def memory_extend_buf;
4577 rtx memory_extend_rtx = &memory_extend_buf;
4578 enum machine_mode tmode;
4580 /* Set what we are trying to extend and the operation it might
4581 have been extended with. */
4582 memset (memory_extend_rtx, 0, sizeof(*memory_extend_rtx));
4583 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
4584 XEXP (memory_extend_rtx, 0) = src;
4586 for (tmode = GET_MODE_WIDER_MODE (mode);
4587 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
4588 tmode = GET_MODE_WIDER_MODE (tmode))
4590 struct table_elt *larger_elt;
4592 PUT_MODE (memory_extend_rtx, tmode);
4593 larger_elt = lookup (memory_extend_rtx,
4594 HASH (memory_extend_rtx, tmode), tmode);
4595 if (larger_elt == 0)
4598 for (larger_elt = larger_elt->first_same_value;
4599 larger_elt; larger_elt = larger_elt->next_same_value)
4600 if (REG_P (larger_elt->exp))
4602 src_related = gen_lowpart (mode, larger_elt->exp);
4610 #endif /* LOAD_EXTEND_OP */
4612 if (src == src_folded)
4615 /* At this point, ELT, if nonzero, points to a class of expressions
4616 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
4617 and SRC_RELATED, if nonzero, each contain additional equivalent
4618 expressions. Prune these latter expressions by deleting expressions
4619 already in the equivalence class.
4621 Check for an equivalent identical to the destination. If found,
4622 this is the preferred equivalent since it will likely lead to
4623 elimination of the insn. Indicate this by placing it in
4627 elt = elt->first_same_value;
4628 for (p = elt; p; p = p->next_same_value)
4630 enum rtx_code code = GET_CODE (p->exp);
4632 /* If the expression is not valid, ignore it. Then we do not
4633 have to check for validity below. In most cases, we can use
4634 `rtx_equal_p', since canonicalization has already been done. */
4635 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, false))
4638 /* Also skip paradoxical subregs, unless that's what we're
4641 && (GET_MODE_SIZE (GET_MODE (p->exp))
4642 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
4644 && GET_CODE (src) == SUBREG
4645 && GET_MODE (src) == GET_MODE (p->exp)
4646 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
4647 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
4650 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
4652 else if (src_folded && GET_CODE (src_folded) == code
4653 && rtx_equal_p (src_folded, p->exp))
4655 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
4656 && rtx_equal_p (src_eqv_here, p->exp))
4658 else if (src_related && GET_CODE (src_related) == code
4659 && rtx_equal_p (src_related, p->exp))
4662 /* This is the same as the destination of the insns, we want
4663 to prefer it. Copy it to src_related. The code below will
4664 then give it a negative cost. */
4665 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
4669 /* Find the cheapest valid equivalent, trying all the available
4670 possibilities. Prefer items not in the hash table to ones
4671 that are when they are equal cost. Note that we can never
4672 worsen an insn as the current contents will also succeed.
4673 If we find an equivalent identical to the destination, use it as best,
4674 since this insn will probably be eliminated in that case. */
4677 if (rtx_equal_p (src, dest))
4678 src_cost = src_regcost = -1;
4681 src_cost = COST (src);
4682 src_regcost = approx_reg_cost (src);
4688 if (rtx_equal_p (src_eqv_here, dest))
4689 src_eqv_cost = src_eqv_regcost = -1;
4692 src_eqv_cost = COST (src_eqv_here);
4693 src_eqv_regcost = approx_reg_cost (src_eqv_here);
4699 if (rtx_equal_p (src_folded, dest))
4700 src_folded_cost = src_folded_regcost = -1;
4703 src_folded_cost = COST (src_folded);
4704 src_folded_regcost = approx_reg_cost (src_folded);
4710 if (rtx_equal_p (src_related, dest))
4711 src_related_cost = src_related_regcost = -1;
4714 src_related_cost = COST (src_related);
4715 src_related_regcost = approx_reg_cost (src_related);
4719 /* If this was an indirect jump insn, a known label will really be
4720 cheaper even though it looks more expensive. */
4721 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
4722 src_folded = src_const, src_folded_cost = src_folded_regcost = -1;
4724 /* Terminate loop when replacement made. This must terminate since
4725 the current contents will be tested and will always be valid. */
4730 /* Skip invalid entries. */
4731 while (elt && !REG_P (elt->exp)
4732 && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
4733 elt = elt->next_same_value;
4735 /* A paradoxical subreg would be bad here: it'll be the right
4736 size, but later may be adjusted so that the upper bits aren't
4737 what we want. So reject it. */
4739 && GET_CODE (elt->exp) == SUBREG
4740 && (GET_MODE_SIZE (GET_MODE (elt->exp))
4741 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
4742 /* It is okay, though, if the rtx we're trying to match
4743 will ignore any of the bits we can't predict. */
4745 && GET_CODE (src) == SUBREG
4746 && GET_MODE (src) == GET_MODE (elt->exp)
4747 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
4748 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
4750 elt = elt->next_same_value;
4756 src_elt_cost = elt->cost;
4757 src_elt_regcost = elt->regcost;
4760 /* Find cheapest and skip it for the next time. For items
4761 of equal cost, use this order:
4762 src_folded, src, src_eqv, src_related and hash table entry. */
4764 && preferable (src_folded_cost, src_folded_regcost,
4765 src_cost, src_regcost) <= 0
4766 && preferable (src_folded_cost, src_folded_regcost,
4767 src_eqv_cost, src_eqv_regcost) <= 0
4768 && preferable (src_folded_cost, src_folded_regcost,
4769 src_related_cost, src_related_regcost) <= 0
4770 && preferable (src_folded_cost, src_folded_regcost,
4771 src_elt_cost, src_elt_regcost) <= 0)
4773 trial = src_folded, src_folded_cost = MAX_COST;
4774 if (src_folded_force_flag)
4776 rtx forced = force_const_mem (mode, trial);
4782 && preferable (src_cost, src_regcost,
4783 src_eqv_cost, src_eqv_regcost) <= 0
4784 && preferable (src_cost, src_regcost,
4785 src_related_cost, src_related_regcost) <= 0
4786 && preferable (src_cost, src_regcost,
4787 src_elt_cost, src_elt_regcost) <= 0)
4788 trial = src, src_cost = MAX_COST;
4789 else if (src_eqv_here
4790 && preferable (src_eqv_cost, src_eqv_regcost,
4791 src_related_cost, src_related_regcost) <= 0
4792 && preferable (src_eqv_cost, src_eqv_regcost,
4793 src_elt_cost, src_elt_regcost) <= 0)
4794 trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
4795 else if (src_related
4796 && preferable (src_related_cost, src_related_regcost,
4797 src_elt_cost, src_elt_regcost) <= 0)
4798 trial = copy_rtx (src_related), src_related_cost = MAX_COST;
4801 trial = copy_rtx (elt->exp);
4802 elt = elt->next_same_value;
4803 src_elt_cost = MAX_COST;
4806 /* We don't normally have an insn matching (set (pc) (pc)), so
4807 check for this separately here. We will delete such an
4810 For other cases such as a table jump or conditional jump
4811 where we know the ultimate target, go ahead and replace the
4812 operand. While that may not make a valid insn, we will
4813 reemit the jump below (and also insert any necessary
4815 if (n_sets == 1 && dest == pc_rtx
4817 || (GET_CODE (trial) == LABEL_REF
4818 && ! condjump_p (insn))))
4820 /* Don't substitute non-local labels, this confuses CFG. */
4821 if (GET_CODE (trial) == LABEL_REF
4822 && LABEL_REF_NONLOCAL_P (trial))
4825 SET_SRC (sets[i].rtl) = trial;
4826 cse_jumps_altered = 1;
4830 /* Reject certain invalid forms of CONST that we create. */
4831 else if (CONSTANT_P (trial)
4832 && GET_CODE (trial) == CONST
4833 /* Reject cases that will cause decode_rtx_const to
4834 die. On the alpha when simplifying a switch, we
4835 get (const (truncate (minus (label_ref)
4837 && (GET_CODE (XEXP (trial, 0)) == TRUNCATE
4838 /* Likewise on IA-64, except without the
4840 || (GET_CODE (XEXP (trial, 0)) == MINUS
4841 && GET_CODE (XEXP (XEXP (trial, 0), 0)) == LABEL_REF
4842 && GET_CODE (XEXP (XEXP (trial, 0), 1)) == LABEL_REF)))
4843 /* Do nothing for this case. */
4846 /* Look for a substitution that makes a valid insn. */
4847 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
4849 rtx new = canon_reg (SET_SRC (sets[i].rtl), insn);
4851 /* If we just made a substitution inside a libcall, then we
4852 need to make the same substitution in any notes attached
4853 to the RETVAL insn. */
4855 && (REG_P (sets[i].orig_src)
4856 || GET_CODE (sets[i].orig_src) == SUBREG
4857 || MEM_P (sets[i].orig_src)))
4859 rtx note = find_reg_equal_equiv_note (libcall_insn);
4861 XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0),
4866 /* The result of apply_change_group can be ignored; see
4869 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4870 apply_change_group ();
4875 /* If we previously found constant pool entries for
4876 constants and this is a constant, try making a
4877 pool entry. Put it in src_folded unless we already have done
4878 this since that is where it likely came from. */
4880 else if (constant_pool_entries_cost
4881 && CONSTANT_P (trial)
4883 || (!MEM_P (src_folded)
4884 && ! src_folded_force_flag))
4885 && GET_MODE_CLASS (mode) != MODE_CC
4886 && mode != VOIDmode)
4888 src_folded_force_flag = 1;
4890 src_folded_cost = constant_pool_entries_cost;
4891 src_folded_regcost = constant_pool_entries_regcost;
4895 src = SET_SRC (sets[i].rtl);
4897 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
4898 However, there is an important exception: If both are registers
4899 that are not the head of their equivalence class, replace SET_SRC
4900 with the head of the class. If we do not do this, we will have
4901 both registers live over a portion of the basic block. This way,
4902 their lifetimes will likely abut instead of overlapping. */
4904 && REGNO_QTY_VALID_P (REGNO (dest)))
4906 int dest_q = REG_QTY (REGNO (dest));
4907 struct qty_table_elem *dest_ent = &qty_table[dest_q];
4909 if (dest_ent->mode == GET_MODE (dest)
4910 && dest_ent->first_reg != REGNO (dest)
4911 && REG_P (src) && REGNO (src) == REGNO (dest)
4912 /* Don't do this if the original insn had a hard reg as
4913 SET_SRC or SET_DEST. */
4914 && (!REG_P (sets[i].src)
4915 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
4916 && (!REG_P (dest) || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
4917 /* We can't call canon_reg here because it won't do anything if
4918 SRC is a hard register. */
4920 int src_q = REG_QTY (REGNO (src));
4921 struct qty_table_elem *src_ent = &qty_table[src_q];
4922 int first = src_ent->first_reg;
4924 = (first >= FIRST_PSEUDO_REGISTER
4925 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
4927 /* We must use validate-change even for this, because this
4928 might be a special no-op instruction, suitable only to
4930 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
4933 /* If we had a constant that is cheaper than what we are now
4934 setting SRC to, use that constant. We ignored it when we
4935 thought we could make this into a no-op. */
4936 if (src_const && COST (src_const) < COST (src)
4937 && validate_change (insn, &SET_SRC (sets[i].rtl),
4944 /* If we made a change, recompute SRC values. */
4945 if (src != sets[i].src)
4948 hash_arg_in_memory = 0;
4950 sets[i].src_hash = HASH (src, mode);
4951 sets[i].src_volatile = do_not_record;
4952 sets[i].src_in_memory = hash_arg_in_memory;
4953 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
4956 /* If this is a single SET, we are setting a register, and we have an
4957 equivalent constant, we want to add a REG_NOTE. We don't want
4958 to write a REG_EQUAL note for a constant pseudo since verifying that
4959 that pseudo hasn't been eliminated is a pain. Such a note also
4960 won't help anything.
4962 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
4963 which can be created for a reference to a compile time computable
4964 entry in a jump table. */
4966 if (n_sets == 1 && src_const && REG_P (dest)
4967 && !REG_P (src_const)
4968 && ! (GET_CODE (src_const) == CONST
4969 && GET_CODE (XEXP (src_const, 0)) == MINUS
4970 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
4971 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
4973 /* We only want a REG_EQUAL note if src_const != src. */
4974 if (! rtx_equal_p (src, src_const))
4976 /* Make sure that the rtx is not shared. */
4977 src_const = copy_rtx (src_const);
4979 /* Record the actual constant value in a REG_EQUAL note,
4980 making a new one if one does not already exist. */
4981 set_unique_reg_note (insn, REG_EQUAL, src_const);
4985 /* Now deal with the destination. */
4988 /* Look within any ZERO_EXTRACT to the MEM or REG within it. */
4989 while (GET_CODE (dest) == SUBREG
4990 || GET_CODE (dest) == ZERO_EXTRACT
4991 || GET_CODE (dest) == STRICT_LOW_PART)
4992 dest = XEXP (dest, 0);
4994 sets[i].inner_dest = dest;
4998 #ifdef PUSH_ROUNDING
4999 /* Stack pushes invalidate the stack pointer. */
5000 rtx addr = XEXP (dest, 0);
5001 if (GET_RTX_CLASS (GET_CODE (addr)) == RTX_AUTOINC
5002 && XEXP (addr, 0) == stack_pointer_rtx)
5003 invalidate (stack_pointer_rtx, VOIDmode);
5005 dest = fold_rtx (dest, insn);
5008 /* Compute the hash code of the destination now,
5009 before the effects of this instruction are recorded,
5010 since the register values used in the address computation
5011 are those before this instruction. */
5012 sets[i].dest_hash = HASH (dest, mode);
5014 /* Don't enter a bit-field in the hash table
5015 because the value in it after the store
5016 may not equal what was stored, due to truncation. */
5018 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT)
5020 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5022 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5023 && GET_CODE (width) == CONST_INT
5024 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5025 && ! (INTVAL (src_const)
5026 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5027 /* Exception: if the value is constant,
5028 and it won't be truncated, record it. */
5032 /* This is chosen so that the destination will be invalidated
5033 but no new value will be recorded.
5034 We must invalidate because sometimes constant
5035 values can be recorded for bitfields. */
5036 sets[i].src_elt = 0;
5037 sets[i].src_volatile = 1;
5043 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5045 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5047 /* One less use of the label this insn used to jump to. */
5048 delete_insn_and_edges (insn);
5049 cse_jumps_altered = 1;
5050 /* No more processing for this set. */
5054 /* If this SET is now setting PC to a label, we know it used to
5055 be a conditional or computed branch. */
5056 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF
5057 && !LABEL_REF_NONLOCAL_P (src))
5059 /* Now emit a BARRIER after the unconditional jump. */
5060 if (NEXT_INSN (insn) == 0
5061 || !BARRIER_P (NEXT_INSN (insn)))
5062 emit_barrier_after (insn);
5064 /* We reemit the jump in as many cases as possible just in
5065 case the form of an unconditional jump is significantly
5066 different than a computed jump or conditional jump.
5068 If this insn has multiple sets, then reemitting the
5069 jump is nontrivial. So instead we just force rerecognition
5070 and hope for the best. */
5075 new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
5076 JUMP_LABEL (new) = XEXP (src, 0);
5077 LABEL_NUSES (XEXP (src, 0))++;
5079 /* Make sure to copy over REG_NON_LOCAL_GOTO. */
5080 note = find_reg_note (insn, REG_NON_LOCAL_GOTO, 0);
5083 XEXP (note, 1) = NULL_RTX;
5084 REG_NOTES (new) = note;
5087 delete_insn_and_edges (insn);
5090 /* Now emit a BARRIER after the unconditional jump. */
5091 if (NEXT_INSN (insn) == 0
5092 || !BARRIER_P (NEXT_INSN (insn)))
5093 emit_barrier_after (insn);
5096 INSN_CODE (insn) = -1;
5098 /* Do not bother deleting any unreachable code,
5099 let jump/flow do that. */
5101 cse_jumps_altered = 1;
5105 /* If destination is volatile, invalidate it and then do no further
5106 processing for this assignment. */
5108 else if (do_not_record)
5110 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5111 invalidate (dest, VOIDmode);
5112 else if (MEM_P (dest))
5113 invalidate (dest, VOIDmode);
5114 else if (GET_CODE (dest) == STRICT_LOW_PART
5115 || GET_CODE (dest) == ZERO_EXTRACT)
5116 invalidate (XEXP (dest, 0), GET_MODE (dest));
5120 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5121 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5124 /* If setting CC0, record what it was set to, or a constant, if it
5125 is equivalent to a constant. If it is being set to a floating-point
5126 value, make a COMPARE with the appropriate constant of 0. If we
5127 don't do this, later code can interpret this as a test against
5128 const0_rtx, which can cause problems if we try to put it into an
5129 insn as a floating-point operand. */
5130 if (dest == cc0_rtx)
5132 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5133 this_insn_cc0_mode = mode;
5134 if (FLOAT_MODE_P (mode))
5135 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5141 /* Now enter all non-volatile source expressions in the hash table
5142 if they are not already present.
5143 Record their equivalence classes in src_elt.
5144 This way we can insert the corresponding destinations into
5145 the same classes even if the actual sources are no longer in them
5146 (having been invalidated). */
5148 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5149 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5151 struct table_elt *elt;
5152 struct table_elt *classp = sets[0].src_elt;
5153 rtx dest = SET_DEST (sets[0].rtl);
5154 enum machine_mode eqvmode = GET_MODE (dest);
5156 if (GET_CODE (dest) == STRICT_LOW_PART)
5158 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5161 if (insert_regs (src_eqv, classp, 0))
5163 rehash_using_reg (src_eqv);
5164 src_eqv_hash = HASH (src_eqv, eqvmode);
5166 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5167 elt->in_memory = src_eqv_in_memory;
5170 /* Check to see if src_eqv_elt is the same as a set source which
5171 does not yet have an elt, and if so set the elt of the set source
5173 for (i = 0; i < n_sets; i++)
5174 if (sets[i].rtl && sets[i].src_elt == 0
5175 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5176 sets[i].src_elt = src_eqv_elt;
5179 for (i = 0; i < n_sets; i++)
5180 if (sets[i].rtl && ! sets[i].src_volatile
5181 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5183 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5185 /* REG_EQUAL in setting a STRICT_LOW_PART
5186 gives an equivalent for the entire destination register,
5187 not just for the subreg being stored in now.
5188 This is a more interesting equivalence, so we arrange later
5189 to treat the entire reg as the destination. */
5190 sets[i].src_elt = src_eqv_elt;
5191 sets[i].src_hash = src_eqv_hash;
5195 /* Insert source and constant equivalent into hash table, if not
5197 struct table_elt *classp = src_eqv_elt;
5198 rtx src = sets[i].src;
5199 rtx dest = SET_DEST (sets[i].rtl);
5200 enum machine_mode mode
5201 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5203 /* It's possible that we have a source value known to be
5204 constant but don't have a REG_EQUAL note on the insn.
5205 Lack of a note will mean src_eqv_elt will be NULL. This
5206 can happen where we've generated a SUBREG to access a
5207 CONST_INT that is already in a register in a wider mode.
5208 Ensure that the source expression is put in the proper
5211 classp = sets[i].src_const_elt;
5213 if (sets[i].src_elt == 0)
5215 /* Don't put a hard register source into the table if this is
5216 the last insn of a libcall. In this case, we only need
5217 to put src_eqv_elt in src_elt. */
5218 if (! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5220 struct table_elt *elt;
5222 /* Note that these insert_regs calls cannot remove
5223 any of the src_elt's, because they would have failed to
5224 match if not still valid. */
5225 if (insert_regs (src, classp, 0))
5227 rehash_using_reg (src);
5228 sets[i].src_hash = HASH (src, mode);
5230 elt = insert (src, classp, sets[i].src_hash, mode);
5231 elt->in_memory = sets[i].src_in_memory;
5232 sets[i].src_elt = classp = elt;
5235 sets[i].src_elt = classp;
5237 if (sets[i].src_const && sets[i].src_const_elt == 0
5238 && src != sets[i].src_const
5239 && ! rtx_equal_p (sets[i].src_const, src))
5240 sets[i].src_elt = insert (sets[i].src_const, classp,
5241 sets[i].src_const_hash, mode);
5244 else if (sets[i].src_elt == 0)
5245 /* If we did not insert the source into the hash table (e.g., it was
5246 volatile), note the equivalence class for the REG_EQUAL value, if any,
5247 so that the destination goes into that class. */
5248 sets[i].src_elt = src_eqv_elt;
5250 /* Record destination addresses in the hash table. This allows us to
5251 check if they are invalidated by other sets. */
5252 for (i = 0; i < n_sets; i++)
5256 rtx x = sets[i].inner_dest;
5257 struct table_elt *elt;
5258 enum machine_mode mode;
5264 mode = GET_MODE (x);
5265 hash = HASH (x, mode);
5266 elt = lookup (x, hash, mode);
5269 if (insert_regs (x, NULL, 0))
5271 rtx dest = SET_DEST (sets[i].rtl);
5273 rehash_using_reg (x);
5274 hash = HASH (x, mode);
5275 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
5277 elt = insert (x, NULL, hash, mode);
5280 sets[i].dest_addr_elt = elt;
5283 sets[i].dest_addr_elt = NULL;
5287 invalidate_from_clobbers (x);
5289 /* Some registers are invalidated by subroutine calls. Memory is
5290 invalidated by non-constant calls. */
5294 if (! CONST_OR_PURE_CALL_P (insn))
5295 invalidate_memory ();
5296 invalidate_for_call ();
5299 /* Now invalidate everything set by this instruction.
5300 If a SUBREG or other funny destination is being set,
5301 sets[i].rtl is still nonzero, so here we invalidate the reg
5302 a part of which is being set. */
5304 for (i = 0; i < n_sets; i++)
5307 /* We can't use the inner dest, because the mode associated with
5308 a ZERO_EXTRACT is significant. */
5309 rtx dest = SET_DEST (sets[i].rtl);
5311 /* Needed for registers to remove the register from its
5312 previous quantity's chain.
5313 Needed for memory if this is a nonvarying address, unless
5314 we have just done an invalidate_memory that covers even those. */
5315 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5316 invalidate (dest, VOIDmode);
5317 else if (MEM_P (dest))
5318 invalidate (dest, VOIDmode);
5319 else if (GET_CODE (dest) == STRICT_LOW_PART
5320 || GET_CODE (dest) == ZERO_EXTRACT)
5321 invalidate (XEXP (dest, 0), GET_MODE (dest));
5324 /* A volatile ASM invalidates everything. */
5325 if (NONJUMP_INSN_P (insn)
5326 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5327 && MEM_VOLATILE_P (PATTERN (insn)))
5328 flush_hash_table ();
5330 /* Don't cse over a call to setjmp; on some machines (eg VAX)
5331 the regs restored by the longjmp come from a later time
5333 if (CALL_P (insn) && find_reg_note (insn, REG_SETJMP, NULL))
5335 flush_hash_table ();
5339 /* Make sure registers mentioned in destinations
5340 are safe for use in an expression to be inserted.
5341 This removes from the hash table
5342 any invalid entry that refers to one of these registers.
5344 We don't care about the return value from mention_regs because
5345 we are going to hash the SET_DEST values unconditionally. */
5347 for (i = 0; i < n_sets; i++)
5351 rtx x = SET_DEST (sets[i].rtl);
5357 /* We used to rely on all references to a register becoming
5358 inaccessible when a register changes to a new quantity,
5359 since that changes the hash code. However, that is not
5360 safe, since after HASH_SIZE new quantities we get a
5361 hash 'collision' of a register with its own invalid
5362 entries. And since SUBREGs have been changed not to
5363 change their hash code with the hash code of the register,
5364 it wouldn't work any longer at all. So we have to check
5365 for any invalid references lying around now.
5366 This code is similar to the REG case in mention_regs,
5367 but it knows that reg_tick has been incremented, and
5368 it leaves reg_in_table as -1 . */
5369 unsigned int regno = REGNO (x);
5370 unsigned int endregno = END_REGNO (x);
5373 for (i = regno; i < endregno; i++)
5375 if (REG_IN_TABLE (i) >= 0)
5377 remove_invalid_refs (i);
5378 REG_IN_TABLE (i) = -1;
5385 /* We may have just removed some of the src_elt's from the hash table.
5386 So replace each one with the current head of the same class.
5387 Also check if destination addresses have been removed. */
5389 for (i = 0; i < n_sets; i++)
5392 if (sets[i].dest_addr_elt
5393 && sets[i].dest_addr_elt->first_same_value == 0)
5395 /* The elt was removed, which means this destination is not
5396 valid after this instruction. */
5397 sets[i].rtl = NULL_RTX;
5399 else if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
5400 /* If elt was removed, find current head of same class,
5401 or 0 if nothing remains of that class. */
5403 struct table_elt *elt = sets[i].src_elt;
5405 while (elt && elt->prev_same_value)
5406 elt = elt->prev_same_value;
5408 while (elt && elt->first_same_value == 0)
5409 elt = elt->next_same_value;
5410 sets[i].src_elt = elt ? elt->first_same_value : 0;
5414 /* Now insert the destinations into their equivalence classes. */
5416 for (i = 0; i < n_sets; i++)
5419 rtx dest = SET_DEST (sets[i].rtl);
5420 struct table_elt *elt;
5422 /* Don't record value if we are not supposed to risk allocating
5423 floating-point values in registers that might be wider than
5425 if ((flag_float_store
5427 && FLOAT_MODE_P (GET_MODE (dest)))
5428 /* Don't record BLKmode values, because we don't know the
5429 size of it, and can't be sure that other BLKmode values
5430 have the same or smaller size. */
5431 || GET_MODE (dest) == BLKmode
5432 /* Don't record values of destinations set inside a libcall block
5433 since we might delete the libcall. Things should have been set
5434 up so we won't want to reuse such a value, but we play it safe
5437 /* If we didn't put a REG_EQUAL value or a source into the hash
5438 table, there is no point is recording DEST. */
5439 || sets[i].src_elt == 0
5440 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
5441 or SIGN_EXTEND, don't record DEST since it can cause
5442 some tracking to be wrong.
5444 ??? Think about this more later. */
5445 || (GET_CODE (dest) == SUBREG
5446 && (GET_MODE_SIZE (GET_MODE (dest))
5447 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5448 && (GET_CODE (sets[i].src) == SIGN_EXTEND
5449 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
5452 /* STRICT_LOW_PART isn't part of the value BEING set,
5453 and neither is the SUBREG inside it.
5454 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
5455 if (GET_CODE (dest) == STRICT_LOW_PART)
5456 dest = SUBREG_REG (XEXP (dest, 0));
5458 if (REG_P (dest) || GET_CODE (dest) == SUBREG)
5459 /* Registers must also be inserted into chains for quantities. */
5460 if (insert_regs (dest, sets[i].src_elt, 1))
5462 /* If `insert_regs' changes something, the hash code must be
5464 rehash_using_reg (dest);
5465 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
5468 elt = insert (dest, sets[i].src_elt,
5469 sets[i].dest_hash, GET_MODE (dest));
5471 elt->in_memory = (MEM_P (sets[i].inner_dest)
5472 && !MEM_READONLY_P (sets[i].inner_dest));
5474 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
5475 narrower than M2, and both M1 and M2 are the same number of words,
5476 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
5477 make that equivalence as well.
5479 However, BAR may have equivalences for which gen_lowpart
5480 will produce a simpler value than gen_lowpart applied to
5481 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
5482 BAR's equivalences. If we don't get a simplified form, make
5483 the SUBREG. It will not be used in an equivalence, but will
5484 cause two similar assignments to be detected.
5486 Note the loop below will find SUBREG_REG (DEST) since we have
5487 already entered SRC and DEST of the SET in the table. */
5489 if (GET_CODE (dest) == SUBREG
5490 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
5492 == (GET_MODE_SIZE (GET_MODE (dest)) - 1) / UNITS_PER_WORD)
5493 && (GET_MODE_SIZE (GET_MODE (dest))
5494 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5495 && sets[i].src_elt != 0)
5497 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
5498 struct table_elt *elt, *classp = 0;
5500 for (elt = sets[i].src_elt->first_same_value; elt;
5501 elt = elt->next_same_value)
5505 struct table_elt *src_elt;
5508 /* Ignore invalid entries. */
5509 if (!REG_P (elt->exp)
5510 && ! exp_equiv_p (elt->exp, elt->exp, 1, false))
5513 /* We may have already been playing subreg games. If the
5514 mode is already correct for the destination, use it. */
5515 if (GET_MODE (elt->exp) == new_mode)
5519 /* Calculate big endian correction for the SUBREG_BYTE.
5520 We have already checked that M1 (GET_MODE (dest))
5521 is not narrower than M2 (new_mode). */
5522 if (BYTES_BIG_ENDIAN)
5523 byte = (GET_MODE_SIZE (GET_MODE (dest))
5524 - GET_MODE_SIZE (new_mode));
5526 new_src = simplify_gen_subreg (new_mode, elt->exp,
5527 GET_MODE (dest), byte);
5530 /* The call to simplify_gen_subreg fails if the value
5531 is VOIDmode, yet we can't do any simplification, e.g.
5532 for EXPR_LISTs denoting function call results.
5533 It is invalid to construct a SUBREG with a VOIDmode
5534 SUBREG_REG, hence a zero new_src means we can't do
5535 this substitution. */
5539 src_hash = HASH (new_src, new_mode);
5540 src_elt = lookup (new_src, src_hash, new_mode);
5542 /* Put the new source in the hash table is if isn't
5546 if (insert_regs (new_src, classp, 0))
5548 rehash_using_reg (new_src);
5549 src_hash = HASH (new_src, new_mode);
5551 src_elt = insert (new_src, classp, src_hash, new_mode);
5552 src_elt->in_memory = elt->in_memory;
5554 else if (classp && classp != src_elt->first_same_value)
5555 /* Show that two things that we've seen before are
5556 actually the same. */
5557 merge_equiv_classes (src_elt, classp);
5559 classp = src_elt->first_same_value;
5560 /* Ignore invalid entries. */
5562 && !REG_P (classp->exp)
5563 && ! exp_equiv_p (classp->exp, classp->exp, 1, false))
5564 classp = classp->next_same_value;
5569 /* Special handling for (set REG0 REG1) where REG0 is the
5570 "cheapest", cheaper than REG1. After cse, REG1 will probably not
5571 be used in the sequel, so (if easily done) change this insn to
5572 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
5573 that computed their value. Then REG1 will become a dead store
5574 and won't cloud the situation for later optimizations.
5576 Do not make this change if REG1 is a hard register, because it will
5577 then be used in the sequel and we may be changing a two-operand insn
5578 into a three-operand insn.
5580 Also do not do this if we are operating on a copy of INSN.
5582 Also don't do this if INSN ends a libcall; this would cause an unrelated
5583 register to be set in the middle of a libcall, and we then get bad code
5584 if the libcall is deleted. */
5586 if (n_sets == 1 && sets[0].rtl && REG_P (SET_DEST (sets[0].rtl))
5587 && NEXT_INSN (PREV_INSN (insn)) == insn
5588 && REG_P (SET_SRC (sets[0].rtl))
5589 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
5590 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
5592 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
5593 struct qty_table_elem *src_ent = &qty_table[src_q];
5595 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
5596 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5598 /* Scan for the previous nonnote insn, but stop at a basic
5601 rtx bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
5604 prev = PREV_INSN (prev);
5606 while (prev != bb_head && NOTE_P (prev));
5608 /* Do not swap the registers around if the previous instruction
5609 attaches a REG_EQUIV note to REG1.
5611 ??? It's not entirely clear whether we can transfer a REG_EQUIV
5612 from the pseudo that originally shadowed an incoming argument
5613 to another register. Some uses of REG_EQUIV might rely on it
5614 being attached to REG1 rather than REG2.
5616 This section previously turned the REG_EQUIV into a REG_EQUAL
5617 note. We cannot do that because REG_EQUIV may provide an
5618 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
5619 if (NONJUMP_INSN_P (prev)
5620 && GET_CODE (PATTERN (prev)) == SET
5621 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
5622 && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
5624 rtx dest = SET_DEST (sets[0].rtl);
5625 rtx src = SET_SRC (sets[0].rtl);
5628 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
5629 validate_change (insn, &SET_DEST (sets[0].rtl), src, 1);
5630 validate_change (insn, &SET_SRC (sets[0].rtl), dest, 1);
5631 apply_change_group ();
5633 /* If INSN has a REG_EQUAL note, and this note mentions
5634 REG0, then we must delete it, because the value in
5635 REG0 has changed. If the note's value is REG1, we must
5636 also delete it because that is now this insn's dest. */
5637 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5639 && (reg_mentioned_p (dest, XEXP (note, 0))
5640 || rtx_equal_p (src, XEXP (note, 0))))
5641 remove_note (insn, note);
5649 /* Remove from the hash table all expressions that reference memory. */
5652 invalidate_memory (void)
5655 struct table_elt *p, *next;
5657 for (i = 0; i < HASH_SIZE; i++)
5658 for (p = table[i]; p; p = next)
5660 next = p->next_same_hash;
5662 remove_from_table (p, i);
5666 /* Perform invalidation on the basis of everything about an insn
5667 except for invalidating the actual places that are SET in it.
5668 This includes the places CLOBBERed, and anything that might
5669 alias with something that is SET or CLOBBERed.
5671 X is the pattern of the insn. */
5674 invalidate_from_clobbers (rtx x)
5676 if (GET_CODE (x) == CLOBBER)
5678 rtx ref = XEXP (x, 0);
5681 if (REG_P (ref) || GET_CODE (ref) == SUBREG
5683 invalidate (ref, VOIDmode);
5684 else if (GET_CODE (ref) == STRICT_LOW_PART
5685 || GET_CODE (ref) == ZERO_EXTRACT)
5686 invalidate (XEXP (ref, 0), GET_MODE (ref));
5689 else if (GET_CODE (x) == PARALLEL)
5692 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
5694 rtx y = XVECEXP (x, 0, i);
5695 if (GET_CODE (y) == CLOBBER)
5697 rtx ref = XEXP (y, 0);
5698 if (REG_P (ref) || GET_CODE (ref) == SUBREG
5700 invalidate (ref, VOIDmode);
5701 else if (GET_CODE (ref) == STRICT_LOW_PART
5702 || GET_CODE (ref) == ZERO_EXTRACT)
5703 invalidate (XEXP (ref, 0), GET_MODE (ref));
5709 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
5710 and replace any registers in them with either an equivalent constant
5711 or the canonical form of the register. If we are inside an address,
5712 only do this if the address remains valid.
5714 OBJECT is 0 except when within a MEM in which case it is the MEM.
5716 Return the replacement for X. */
5719 cse_process_notes (rtx x, rtx object)
5721 enum rtx_code code = GET_CODE (x);
5722 const char *fmt = GET_RTX_FORMAT (code);
5739 validate_change (x, &XEXP (x, 0),
5740 cse_process_notes (XEXP (x, 0), x), 0);
5745 if (REG_NOTE_KIND (x) == REG_EQUAL)
5746 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
5748 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
5755 rtx new = cse_process_notes (XEXP (x, 0), object);
5756 /* We don't substitute VOIDmode constants into these rtx,
5757 since they would impede folding. */
5758 if (GET_MODE (new) != VOIDmode)
5759 validate_change (object, &XEXP (x, 0), new, 0);
5764 i = REG_QTY (REGNO (x));
5766 /* Return a constant or a constant register. */
5767 if (REGNO_QTY_VALID_P (REGNO (x)))
5769 struct qty_table_elem *ent = &qty_table[i];
5771 if (ent->const_rtx != NULL_RTX
5772 && (CONSTANT_P (ent->const_rtx)
5773 || REG_P (ent->const_rtx)))
5775 rtx new = gen_lowpart (GET_MODE (x), ent->const_rtx);
5777 return copy_rtx (new);
5781 /* Otherwise, canonicalize this register. */
5782 return canon_reg (x, NULL_RTX);
5788 for (i = 0; i < GET_RTX_LENGTH (code); i++)
5790 validate_change (object, &XEXP (x, i),
5791 cse_process_notes (XEXP (x, i), object), 0);
5796 /* Find a path in the CFG, starting with FIRST_BB to perform CSE on.
5798 DATA is a pointer to a struct cse_basic_block_data, that is used to
5800 It is filled with a queue of basic blocks, starting with FIRST_BB
5801 and following a trace through the CFG.
5803 If all paths starting at FIRST_BB have been followed, or no new path
5804 starting at FIRST_BB can be constructed, this function returns FALSE.
5805 Otherwise, DATA->path is filled and the function returns TRUE indicating
5806 that a path to follow was found.
5808 If FOLLOW_JUMPS is false, the maximum path length is 1 and the only
5809 block in the path will be FIRST_BB. */
5812 cse_find_path (basic_block first_bb, struct cse_basic_block_data *data,
5819 SET_BIT (cse_visited_basic_blocks, first_bb->index);
5821 /* See if there is a previous path. */
5822 path_size = data->path_size;
5824 /* There is a previous path. Make sure it started with FIRST_BB. */
5826 gcc_assert (data->path[0].bb == first_bb);
5828 /* There was only one basic block in the last path. Clear the path and
5829 return, so that paths starting at another basic block can be tried. */
5836 /* If the path was empty from the beginning, construct a new path. */
5838 data->path[path_size++].bb = first_bb;
5841 /* Otherwise, path_size must be equal to or greater than 2, because
5842 a previous path exists that is at least two basic blocks long.
5844 Update the previous branch path, if any. If the last branch was
5845 previously along the branch edge, take the fallthrough edge now. */
5846 while (path_size >= 2)
5848 basic_block last_bb_in_path, previous_bb_in_path;
5852 last_bb_in_path = data->path[path_size].bb;
5853 previous_bb_in_path = data->path[path_size - 1].bb;
5855 /* If we previously followed a path along the branch edge, try
5856 the fallthru edge now. */
5857 if (EDGE_COUNT (previous_bb_in_path->succs) == 2
5858 && any_condjump_p (BB_END (previous_bb_in_path))
5859 && (e = find_edge (previous_bb_in_path, last_bb_in_path))
5860 && e == BRANCH_EDGE (previous_bb_in_path))
5862 bb = FALLTHRU_EDGE (previous_bb_in_path)->dest;
5863 if (bb != EXIT_BLOCK_PTR
5864 && single_pred_p (bb)
5865 /* We used to assert here that we would only see blocks
5866 that we have not visited yet. But we may end up
5867 visiting basic blocks twice if the CFG has changed
5868 in this run of cse_main, because when the CFG changes
5869 the topological sort of the CFG also changes. A basic
5870 blocks that previously had more than two predecessors
5871 may now have a single predecessor, and become part of
5872 a path that starts at another basic block.
5874 We still want to visit each basic block only once, so
5875 halt the path here if we have already visited BB. */
5876 && !TEST_BIT (cse_visited_basic_blocks, bb->index))
5878 SET_BIT (cse_visited_basic_blocks, bb->index);
5879 data->path[path_size++].bb = bb;
5884 data->path[path_size].bb = NULL;
5887 /* If only one block remains in the path, bail. */
5895 /* Extend the path if possible. */
5898 bb = data->path[path_size - 1].bb;
5899 while (bb && path_size < PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH))
5901 if (single_succ_p (bb))
5902 e = single_succ_edge (bb);
5903 else if (EDGE_COUNT (bb->succs) == 2
5904 && any_condjump_p (BB_END (bb)))
5906 /* First try to follow the branch. If that doesn't lead
5907 to a useful path, follow the fallthru edge. */
5908 e = BRANCH_EDGE (bb);
5909 if (!single_pred_p (e->dest))
5910 e = FALLTHRU_EDGE (bb);
5915 if (e && e->dest != EXIT_BLOCK_PTR
5916 && single_pred_p (e->dest)
5917 /* Avoid visiting basic blocks twice. The large comment
5918 above explains why this can happen. */
5919 && !TEST_BIT (cse_visited_basic_blocks, e->dest->index))
5921 basic_block bb2 = e->dest;
5922 SET_BIT (cse_visited_basic_blocks, bb2->index);
5923 data->path[path_size++].bb = bb2;
5932 data->path_size = path_size;
5933 return path_size != 0;
5936 /* Dump the path in DATA to file F. NSETS is the number of sets
5940 cse_dump_path (struct cse_basic_block_data *data, int nsets, FILE *f)
5944 fprintf (f, ";; Following path with %d sets: ", nsets);
5945 for (path_entry = 0; path_entry < data->path_size; path_entry++)
5946 fprintf (f, "%d ", (data->path[path_entry].bb)->index);
5947 fputc ('\n', dump_file);
5952 /* Return true if BB has exception handling successor edges. */
5955 have_eh_succ_edges (basic_block bb)
5960 FOR_EACH_EDGE (e, ei, bb->succs)
5961 if (e->flags & EDGE_EH)
5968 /* Scan to the end of the path described by DATA. Return an estimate of
5969 the total number of SETs, and the lowest and highest insn CUID, of all
5970 insns in the path. */
5973 cse_prescan_path (struct cse_basic_block_data *data)
5976 int low_cuid = -1, high_cuid = -1; /* FIXME low_cuid not computed correctly */
5977 int path_size = data->path_size;
5980 /* Scan to end of each basic block in the path. */
5981 for (path_entry = 0; path_entry < path_size; path_entry++)
5986 bb = data->path[path_entry].bb;
5988 FOR_BB_INSNS (bb, insn)
5993 /* A PARALLEL can have lots of SETs in it,
5994 especially if it is really an ASM_OPERANDS. */
5995 if (GET_CODE (PATTERN (insn)) == PARALLEL)
5996 nsets += XVECLEN (PATTERN (insn), 0);
6000 /* Ignore insns made by CSE in a previous traversal of this
6001 basic block. They cannot affect the boundaries of the
6003 FIXME: When we only visit each basic block at most once,
6004 this can go away. */
6005 if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) > high_cuid)
6006 high_cuid = INSN_CUID (insn);
6007 if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) < low_cuid)
6008 low_cuid = INSN_CUID (insn);
6012 data->low_cuid = low_cuid;
6013 data->high_cuid = high_cuid;
6014 data->nsets = nsets;
6017 /* Process a single extended basic block described by EBB_DATA. */
6020 cse_extended_basic_block (struct cse_basic_block_data *ebb_data)
6022 int path_size = ebb_data->path_size;
6026 /* Allocate the space needed by qty_table. */
6027 qty_table = XNEWVEC (struct qty_table_elem, max_qty);
6030 for (path_entry = 0; path_entry < path_size; path_entry++)
6034 rtx libcall_insn = NULL_RTX;
6035 int no_conflict = 0;
6037 bb = ebb_data->path[path_entry].bb;
6038 FOR_BB_INSNS (bb, insn)
6040 /* If we have processed 1,000 insns, flush the hash table to
6041 avoid extreme quadratic behavior. We must not include NOTEs
6042 in the count since there may be more of them when generating
6043 debugging information. If we clear the table at different
6044 times, code generated with -g -O might be different than code
6045 generated with -O but not -g.
6047 FIXME: This is a real kludge and needs to be done some other
6050 && num_insns++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS))
6052 flush_hash_table ();
6058 /* Process notes first so we have all notes in canonical forms
6059 when looking for duplicate operations. */
6060 if (REG_NOTES (insn))
6061 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn),
6064 /* Track when we are inside in LIBCALL block. Inside such
6065 a block we do not want to record destinations. The last
6066 insn of a LIBCALL block is not considered to be part of
6067 the block, since its destination is the result of the
6068 block and hence should be recorded. */
6069 if (REG_NOTES (insn) != 0)
6073 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
6074 libcall_insn = XEXP (p, 0);
6075 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
6077 /* Keep libcall_insn for the last SET insn of
6078 a no-conflict block to prevent changing the
6081 libcall_insn = NULL_RTX;
6085 else if (find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
6089 cse_insn (insn, libcall_insn);
6091 /* If we kept libcall_insn for a no-conflict bock,
6093 if (no_conflict == -1)
6095 libcall_insn = NULL_RTX;
6099 /* If we haven't already found an insn where we added a LABEL_REF,
6101 if (NONJUMP_INSN_P (insn) && ! recorded_label_ref
6102 && for_each_rtx (&PATTERN (insn), check_for_label_ref,
6104 recorded_label_ref = 1;
6107 /* If the previous insn set CC0 and this insn no longer
6108 references CC0, delete the previous insn. Here we use
6109 fact that nothing expects CC0 to be valid over an insn,
6110 which is true until the final pass. */
6114 prev_insn = PREV_INSN (insn);
6115 if (prev_insn && NONJUMP_INSN_P (prev_insn)
6116 && (tem = single_set (prev_insn)) != 0
6117 && SET_DEST (tem) == cc0_rtx
6118 && ! reg_mentioned_p (cc0_rtx, PATTERN (insn)))
6119 delete_insn (prev_insn);
6122 /* If this insn is not the last insn in the basic block,
6123 it will be PREV_INSN(insn) in the next iteration. If
6124 we recorded any CC0-related information for this insn,
6126 if (insn != BB_END (bb))
6128 prev_insn_cc0 = this_insn_cc0;
6129 prev_insn_cc0_mode = this_insn_cc0_mode;
6135 /* Make sure that libcalls don't span multiple basic blocks. */
6136 gcc_assert (libcall_insn == NULL_RTX);
6138 /* With non-call exceptions, we are not always able to update
6139 the CFG properly inside cse_insn. So clean up possibly
6140 redundant EH edges here. */
6141 if (flag_non_call_exceptions && have_eh_succ_edges (bb))
6142 purge_dead_edges (bb);
6144 /* If we changed a conditional jump, we may have terminated
6145 the path we are following. Check that by verifying that
6146 the edge we would take still exists. If the edge does
6147 not exist anymore, purge the remainder of the path.
6148 Note that this will cause us to return to the caller. */
6149 if (path_entry < path_size - 1)
6151 basic_block next_bb = ebb_data->path[path_entry + 1].bb;
6152 if (!find_edge (bb, next_bb))
6158 /* If we truncate the path, we must also reset the
6159 visited bit on the remaining blocks in the path,
6160 or we will never visit them at all. */
6161 RESET_BIT (cse_visited_basic_blocks,
6162 ebb_data->path[path_size].bb->index);
6163 ebb_data->path[path_size].bb = NULL;
6165 while (path_size - 1 != path_entry);
6166 ebb_data->path_size = path_size;
6170 /* If this is a conditional jump insn, record any known
6171 equivalences due to the condition being tested. */
6173 if (path_entry < path_size - 1
6175 && single_set (insn)
6176 && any_condjump_p (insn))
6178 basic_block next_bb = ebb_data->path[path_entry + 1].bb;
6179 bool taken = (next_bb == BRANCH_EDGE (bb)->dest);
6180 record_jump_equiv (insn, taken);
6184 /* Clear the CC0-tracking related insns, they can't provide
6185 useful information across basic block boundaries. */
6190 gcc_assert (next_qty <= max_qty);
6195 /* Perform cse on the instructions of a function.
6196 F is the first instruction.
6197 NREGS is one plus the highest pseudo-reg number used in the instruction.
6199 Returns 1 if jump_optimize should be redone due to simplifications
6200 in conditional jump instructions. */
6203 cse_main (rtx f ATTRIBUTE_UNUSED, int nregs)
6205 struct cse_basic_block_data ebb_data;
6207 int *rc_order = XNEWVEC (int, last_basic_block);
6210 init_cse_reg_info (nregs);
6212 ebb_data.path = XNEWVEC (struct branch_path,
6213 PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
6215 cse_jumps_altered = 0;
6216 recorded_label_ref = 0;
6217 constant_pool_entries_cost = 0;
6218 constant_pool_entries_regcost = 0;
6219 ebb_data.path_size = 0;
6221 rtl_hooks = cse_rtl_hooks;
6224 init_alias_analysis ();
6226 reg_eqv_table = XNEWVEC (struct reg_eqv_elem, nregs);
6228 /* Set up the table of already visited basic blocks. */
6229 cse_visited_basic_blocks = sbitmap_alloc (last_basic_block);
6230 sbitmap_zero (cse_visited_basic_blocks);
6232 /* Compute the mapping from uids to cuids.
6233 CUIDs are numbers assigned to insns, like uids, except that
6234 that cuids increase monotonically through the code. */
6235 max_uid = get_max_uid ();
6236 uid_cuid = XCNEWVEC (int, max_uid + 1);
6241 FOR_BB_INSNS (bb, insn)
6242 INSN_CUID (insn) = ++i;
6245 /* Loop over basic blocks in reverse completion order (RPO),
6246 excluding the ENTRY and EXIT blocks. */
6247 n_blocks = pre_and_rev_post_order_compute (NULL, rc_order, false);
6249 while (i < n_blocks)
6251 /* Find the first block in the RPO queue that we have not yet
6252 processed before. */
6255 bb = BASIC_BLOCK (rc_order[i++]);
6257 while (TEST_BIT (cse_visited_basic_blocks, bb->index)
6260 /* Find all paths starting with BB, and process them. */
6261 while (cse_find_path (bb, &ebb_data, flag_cse_follow_jumps))
6263 /* Pre-scan the path. */
6264 cse_prescan_path (&ebb_data);
6266 /* If this basic block has no sets, skip it. */
6267 if (ebb_data.nsets == 0)
6270 /* Get a reasonable estimate for the maximum number of qty's
6271 needed for this path. For this, we take the number of sets
6272 and multiply that by MAX_RECOG_OPERANDS. */
6273 max_qty = ebb_data.nsets * MAX_RECOG_OPERANDS;
6274 cse_basic_block_start = ebb_data.low_cuid;
6275 cse_basic_block_end = ebb_data.high_cuid;
6277 /* Dump the path we're about to process. */
6279 cse_dump_path (&ebb_data, ebb_data.nsets, dump_file);
6281 cse_extended_basic_block (&ebb_data);
6286 end_alias_analysis ();
6288 free (reg_eqv_table);
6289 free (ebb_data.path);
6290 sbitmap_free (cse_visited_basic_blocks);
6292 rtl_hooks = general_rtl_hooks;
6294 return cse_jumps_altered || recorded_label_ref;
6297 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
6298 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
6301 check_for_label_ref (rtx *rtl, void *data)
6303 rtx insn = (rtx) data;
6305 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
6306 we must rerun jump since it needs to place the note. If this is a
6307 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
6308 since no REG_LABEL will be added. */
6309 return (GET_CODE (*rtl) == LABEL_REF
6310 && ! LABEL_REF_NONLOCAL_P (*rtl)
6311 && LABEL_P (XEXP (*rtl, 0))
6312 && INSN_UID (XEXP (*rtl, 0)) != 0
6313 && ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)));
6316 /* Count the number of times registers are used (not set) in X.
6317 COUNTS is an array in which we accumulate the count, INCR is how much
6318 we count each register usage.
6320 Don't count a usage of DEST, which is the SET_DEST of a SET which
6321 contains X in its SET_SRC. This is because such a SET does not
6322 modify the liveness of DEST.
6323 DEST is set to pc_rtx for a trapping insn, which means that we must count
6324 uses of a SET_DEST regardless because the insn can't be deleted here. */
6327 count_reg_usage (rtx x, int *counts, rtx dest, int incr)
6337 switch (code = GET_CODE (x))
6341 counts[REGNO (x)] += incr;
6355 /* If we are clobbering a MEM, mark any registers inside the address
6357 if (MEM_P (XEXP (x, 0)))
6358 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
6362 /* Unless we are setting a REG, count everything in SET_DEST. */
6363 if (!REG_P (SET_DEST (x)))
6364 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
6365 count_reg_usage (SET_SRC (x), counts,
6366 dest ? dest : SET_DEST (x),
6373 /* We expect dest to be NULL_RTX here. If the insn may trap, mark
6374 this fact by setting DEST to pc_rtx. */
6375 if (flag_non_call_exceptions && may_trap_p (PATTERN (x)))
6377 if (code == CALL_INSN)
6378 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, dest, incr);
6379 count_reg_usage (PATTERN (x), counts, dest, incr);
6381 /* Things used in a REG_EQUAL note aren't dead since loop may try to
6384 note = find_reg_equal_equiv_note (x);
6387 rtx eqv = XEXP (note, 0);
6389 if (GET_CODE (eqv) == EXPR_LIST)
6390 /* This REG_EQUAL note describes the result of a function call.
6391 Process all the arguments. */
6394 count_reg_usage (XEXP (eqv, 0), counts, dest, incr);
6395 eqv = XEXP (eqv, 1);
6397 while (eqv && GET_CODE (eqv) == EXPR_LIST);
6399 count_reg_usage (eqv, counts, dest, incr);
6404 if (REG_NOTE_KIND (x) == REG_EQUAL
6405 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE)
6406 /* FUNCTION_USAGE expression lists may include (CLOBBER (mem /u)),
6407 involving registers in the address. */
6408 || GET_CODE (XEXP (x, 0)) == CLOBBER)
6409 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
6411 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
6415 /* If the asm is volatile, then this insn cannot be deleted,
6416 and so the inputs *must* be live. */
6417 if (MEM_VOLATILE_P (x))
6419 /* Iterate over just the inputs, not the constraints as well. */
6420 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
6421 count_reg_usage (ASM_OPERANDS_INPUT (x, i), counts, dest, incr);
6431 fmt = GET_RTX_FORMAT (code);
6432 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
6435 count_reg_usage (XEXP (x, i), counts, dest, incr);
6436 else if (fmt[i] == 'E')
6437 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
6438 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
6442 /* Return true if set is live. */
6444 set_live_p (rtx set, rtx insn ATTRIBUTE_UNUSED, /* Only used with HAVE_cc0. */
6451 if (set_noop_p (set))
6455 else if (GET_CODE (SET_DEST (set)) == CC0
6456 && !side_effects_p (SET_SRC (set))
6457 && ((tem = next_nonnote_insn (insn)) == 0
6459 || !reg_referenced_p (cc0_rtx, PATTERN (tem))))
6462 else if (!REG_P (SET_DEST (set))
6463 || REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
6464 || counts[REGNO (SET_DEST (set))] != 0
6465 || side_effects_p (SET_SRC (set)))
6470 /* Return true if insn is live. */
6473 insn_live_p (rtx insn, int *counts)
6476 if (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
6478 else if (GET_CODE (PATTERN (insn)) == SET)
6479 return set_live_p (PATTERN (insn), insn, counts);
6480 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
6482 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6484 rtx elt = XVECEXP (PATTERN (insn), 0, i);
6486 if (GET_CODE (elt) == SET)
6488 if (set_live_p (elt, insn, counts))
6491 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
6500 /* Return true if libcall is dead as a whole. */
6503 dead_libcall_p (rtx insn, int *counts)
6507 /* See if there's a REG_EQUAL note on this insn and try to
6508 replace the source with the REG_EQUAL expression.
6510 We assume that insns with REG_RETVALs can only be reg->reg
6511 copies at this point. */
6512 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6516 set = single_set (insn);
6520 new = simplify_rtx (XEXP (note, 0));
6522 new = XEXP (note, 0);
6524 /* While changing insn, we must update the counts accordingly. */
6525 count_reg_usage (insn, counts, NULL_RTX, -1);
6527 if (validate_change (insn, &SET_SRC (set), new, 0))
6529 count_reg_usage (insn, counts, NULL_RTX, 1);
6530 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
6531 remove_note (insn, note);
6535 if (CONSTANT_P (new))
6537 new = force_const_mem (GET_MODE (SET_DEST (set)), new);
6538 if (new && validate_change (insn, &SET_SRC (set), new, 0))
6540 count_reg_usage (insn, counts, NULL_RTX, 1);
6541 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
6542 remove_note (insn, note);
6547 count_reg_usage (insn, counts, NULL_RTX, 1);
6551 /* Scan all the insns and delete any that are dead; i.e., they store a register
6552 that is never used or they copy a register to itself.
6554 This is used to remove insns made obviously dead by cse, loop or other
6555 optimizations. It improves the heuristics in loop since it won't try to
6556 move dead invariants out of loops or make givs for dead quantities. The
6557 remaining passes of the compilation are also sped up. */
6560 delete_trivially_dead_insns (rtx insns, int nreg)
6564 int in_libcall = 0, dead_libcall = 0;
6567 timevar_push (TV_DELETE_TRIVIALLY_DEAD);
6568 /* First count the number of times each register is used. */
6569 counts = XCNEWVEC (int, nreg);
6570 for (insn = insns; insn; insn = NEXT_INSN (insn))
6572 count_reg_usage (insn, counts, NULL_RTX, 1);
6574 /* Go from the last insn to the first and delete insns that only set unused
6575 registers or copy a register to itself. As we delete an insn, remove
6576 usage counts for registers it uses.
6578 The first jump optimization pass may leave a real insn as the last
6579 insn in the function. We must not skip that insn or we may end
6580 up deleting code that is not really dead. */
6581 for (insn = get_last_insn (); insn; insn = prev)
6585 prev = PREV_INSN (insn);
6589 /* Don't delete any insns that are part of a libcall block unless
6590 we can delete the whole libcall block.
6592 Flow or loop might get confused if we did that. Remember
6593 that we are scanning backwards. */
6594 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
6598 dead_libcall = dead_libcall_p (insn, counts);
6600 else if (in_libcall)
6601 live_insn = ! dead_libcall;
6603 live_insn = insn_live_p (insn, counts);
6605 /* If this is a dead insn, delete it and show registers in it aren't
6610 count_reg_usage (insn, counts, NULL_RTX, -1);
6611 delete_insn_and_edges (insn);
6615 if (in_libcall && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
6622 if (dump_file && ndead)
6623 fprintf (dump_file, "Deleted %i trivially dead insns\n",
6627 timevar_pop (TV_DELETE_TRIVIALLY_DEAD);
6631 /* This function is called via for_each_rtx. The argument, NEWREG, is
6632 a condition code register with the desired mode. If we are looking
6633 at the same register in a different mode, replace it with
6637 cse_change_cc_mode (rtx *loc, void *data)
6639 struct change_cc_mode_args* args = (struct change_cc_mode_args*)data;
6643 && REGNO (*loc) == REGNO (args->newreg)
6644 && GET_MODE (*loc) != GET_MODE (args->newreg))
6646 validate_change (args->insn, loc, args->newreg, 1);
6653 /* Change the mode of any reference to the register REGNO (NEWREG) to
6654 GET_MODE (NEWREG) in INSN. */
6657 cse_change_cc_mode_insn (rtx insn, rtx newreg)
6659 struct change_cc_mode_args args;
6666 args.newreg = newreg;
6668 for_each_rtx (&PATTERN (insn), cse_change_cc_mode, &args);
6669 for_each_rtx (®_NOTES (insn), cse_change_cc_mode, &args);
6671 /* If the following assertion was triggered, there is most probably
6672 something wrong with the cc_modes_compatible back end function.
6673 CC modes only can be considered compatible if the insn - with the mode
6674 replaced by any of the compatible modes - can still be recognized. */
6675 success = apply_change_group ();
6676 gcc_assert (success);
6679 /* Change the mode of any reference to the register REGNO (NEWREG) to
6680 GET_MODE (NEWREG), starting at START. Stop before END. Stop at
6681 any instruction which modifies NEWREG. */
6684 cse_change_cc_mode_insns (rtx start, rtx end, rtx newreg)
6688 for (insn = start; insn != end; insn = NEXT_INSN (insn))
6690 if (! INSN_P (insn))
6693 if (reg_set_p (newreg, insn))
6696 cse_change_cc_mode_insn (insn, newreg);
6700 /* BB is a basic block which finishes with CC_REG as a condition code
6701 register which is set to CC_SRC. Look through the successors of BB
6702 to find blocks which have a single predecessor (i.e., this one),
6703 and look through those blocks for an assignment to CC_REG which is
6704 equivalent to CC_SRC. CAN_CHANGE_MODE indicates whether we are
6705 permitted to change the mode of CC_SRC to a compatible mode. This
6706 returns VOIDmode if no equivalent assignments were found.
6707 Otherwise it returns the mode which CC_SRC should wind up with.
6709 The main complexity in this function is handling the mode issues.
6710 We may have more than one duplicate which we can eliminate, and we
6711 try to find a mode which will work for multiple duplicates. */
6713 static enum machine_mode
6714 cse_cc_succs (basic_block bb, rtx cc_reg, rtx cc_src, bool can_change_mode)
6717 enum machine_mode mode;
6718 unsigned int insn_count;
6721 enum machine_mode modes[2];
6727 /* We expect to have two successors. Look at both before picking
6728 the final mode for the comparison. If we have more successors
6729 (i.e., some sort of table jump, although that seems unlikely),
6730 then we require all beyond the first two to use the same
6733 found_equiv = false;
6734 mode = GET_MODE (cc_src);
6736 FOR_EACH_EDGE (e, ei, bb->succs)
6741 if (e->flags & EDGE_COMPLEX)
6744 if (EDGE_COUNT (e->dest->preds) != 1
6745 || e->dest == EXIT_BLOCK_PTR)
6748 end = NEXT_INSN (BB_END (e->dest));
6749 for (insn = BB_HEAD (e->dest); insn != end; insn = NEXT_INSN (insn))
6753 if (! INSN_P (insn))
6756 /* If CC_SRC is modified, we have to stop looking for
6757 something which uses it. */
6758 if (modified_in_p (cc_src, insn))
6761 /* Check whether INSN sets CC_REG to CC_SRC. */
6762 set = single_set (insn);
6764 && REG_P (SET_DEST (set))
6765 && REGNO (SET_DEST (set)) == REGNO (cc_reg))
6768 enum machine_mode set_mode;
6769 enum machine_mode comp_mode;
6772 set_mode = GET_MODE (SET_SRC (set));
6773 comp_mode = set_mode;
6774 if (rtx_equal_p (cc_src, SET_SRC (set)))
6776 else if (GET_CODE (cc_src) == COMPARE
6777 && GET_CODE (SET_SRC (set)) == COMPARE
6779 && rtx_equal_p (XEXP (cc_src, 0),
6780 XEXP (SET_SRC (set), 0))
6781 && rtx_equal_p (XEXP (cc_src, 1),
6782 XEXP (SET_SRC (set), 1)))
6785 comp_mode = targetm.cc_modes_compatible (mode, set_mode);
6786 if (comp_mode != VOIDmode
6787 && (can_change_mode || comp_mode == mode))
6794 if (insn_count < ARRAY_SIZE (insns))
6796 insns[insn_count] = insn;
6797 modes[insn_count] = set_mode;
6798 last_insns[insn_count] = end;
6801 if (mode != comp_mode)
6803 gcc_assert (can_change_mode);
6806 /* The modified insn will be re-recognized later. */
6807 PUT_MODE (cc_src, mode);
6812 if (set_mode != mode)
6814 /* We found a matching expression in the
6815 wrong mode, but we don't have room to
6816 store it in the array. Punt. This case
6820 /* INSN sets CC_REG to a value equal to CC_SRC
6821 with the right mode. We can simply delete
6826 /* We found an instruction to delete. Keep looking,
6827 in the hopes of finding a three-way jump. */
6831 /* We found an instruction which sets the condition
6832 code, so don't look any farther. */
6836 /* If INSN sets CC_REG in some other way, don't look any
6838 if (reg_set_p (cc_reg, insn))
6842 /* If we fell off the bottom of the block, we can keep looking
6843 through successors. We pass CAN_CHANGE_MODE as false because
6844 we aren't prepared to handle compatibility between the
6845 further blocks and this block. */
6848 enum machine_mode submode;
6850 submode = cse_cc_succs (e->dest, cc_reg, cc_src, false);
6851 if (submode != VOIDmode)
6853 gcc_assert (submode == mode);
6855 can_change_mode = false;
6863 /* Now INSN_COUNT is the number of instructions we found which set
6864 CC_REG to a value equivalent to CC_SRC. The instructions are in
6865 INSNS. The modes used by those instructions are in MODES. */
6868 for (i = 0; i < insn_count; ++i)
6870 if (modes[i] != mode)
6872 /* We need to change the mode of CC_REG in INSNS[i] and
6873 subsequent instructions. */
6876 if (GET_MODE (cc_reg) == mode)
6879 newreg = gen_rtx_REG (mode, REGNO (cc_reg));
6881 cse_change_cc_mode_insns (NEXT_INSN (insns[i]), last_insns[i],
6885 delete_insn (insns[i]);
6891 /* If we have a fixed condition code register (or two), walk through
6892 the instructions and try to eliminate duplicate assignments. */
6895 cse_condition_code_reg (void)
6897 unsigned int cc_regno_1;
6898 unsigned int cc_regno_2;
6903 if (! targetm.fixed_condition_code_regs (&cc_regno_1, &cc_regno_2))
6906 cc_reg_1 = gen_rtx_REG (CCmode, cc_regno_1);
6907 if (cc_regno_2 != INVALID_REGNUM)
6908 cc_reg_2 = gen_rtx_REG (CCmode, cc_regno_2);
6910 cc_reg_2 = NULL_RTX;
6919 enum machine_mode mode;
6920 enum machine_mode orig_mode;
6922 /* Look for blocks which end with a conditional jump based on a
6923 condition code register. Then look for the instruction which
6924 sets the condition code register. Then look through the
6925 successor blocks for instructions which set the condition
6926 code register to the same value. There are other possible
6927 uses of the condition code register, but these are by far the
6928 most common and the ones which we are most likely to be able
6931 last_insn = BB_END (bb);
6932 if (!JUMP_P (last_insn))
6935 if (reg_referenced_p (cc_reg_1, PATTERN (last_insn)))
6937 else if (cc_reg_2 && reg_referenced_p (cc_reg_2, PATTERN (last_insn)))
6942 cc_src_insn = NULL_RTX;
6944 for (insn = PREV_INSN (last_insn);
6945 insn && insn != PREV_INSN (BB_HEAD (bb));
6946 insn = PREV_INSN (insn))
6950 if (! INSN_P (insn))
6952 set = single_set (insn);
6954 && REG_P (SET_DEST (set))
6955 && REGNO (SET_DEST (set)) == REGNO (cc_reg))
6958 cc_src = SET_SRC (set);
6961 else if (reg_set_p (cc_reg, insn))
6968 if (modified_between_p (cc_src, cc_src_insn, NEXT_INSN (last_insn)))
6971 /* Now CC_REG is a condition code register used for a
6972 conditional jump at the end of the block, and CC_SRC, in
6973 CC_SRC_INSN, is the value to which that condition code
6974 register is set, and CC_SRC is still meaningful at the end of
6977 orig_mode = GET_MODE (cc_src);
6978 mode = cse_cc_succs (bb, cc_reg, cc_src, true);
6979 if (mode != VOIDmode)
6981 gcc_assert (mode == GET_MODE (cc_src));
6982 if (mode != orig_mode)
6984 rtx newreg = gen_rtx_REG (mode, REGNO (cc_reg));
6986 cse_change_cc_mode_insn (cc_src_insn, newreg);
6988 /* Do the same in the following insns that use the
6989 current value of CC_REG within BB. */
6990 cse_change_cc_mode_insns (NEXT_INSN (cc_src_insn),
6991 NEXT_INSN (last_insn),
6999 /* Perform common subexpression elimination. Nonzero value from
7000 `cse_main' means that jumps were simplified and some code may now
7001 be unreachable, so do jump optimization again. */
7003 gate_handle_cse (void)
7005 return optimize > 0;
7009 rest_of_handle_cse (void)
7013 dump_flow_info (dump_file, dump_flags);
7015 reg_scan (get_insns (), max_reg_num ());
7017 tem = cse_main (get_insns (), max_reg_num ());
7019 /* If we are not running more CSE passes, then we are no longer
7020 expecting CSE to be run. But always rerun it in a cheap mode. */
7021 cse_not_expected = !flag_rerun_cse_after_loop && !flag_gcse;
7024 rebuild_jump_labels (get_insns ());
7026 if (tem || optimize > 1)
7027 cleanup_cfg (CLEANUP_EXPENSIVE);
7032 struct tree_opt_pass pass_cse =
7035 gate_handle_cse, /* gate */
7036 rest_of_handle_cse, /* execute */
7039 0, /* static_pass_number */
7041 0, /* properties_required */
7042 0, /* properties_provided */
7043 0, /* properties_destroyed */
7044 0, /* todo_flags_start */
7047 TODO_verify_flow, /* todo_flags_finish */
7053 gate_handle_cse2 (void)
7055 return optimize > 0 && flag_rerun_cse_after_loop;
7058 /* Run second CSE pass after loop optimizations. */
7060 rest_of_handle_cse2 (void)
7065 dump_flow_info (dump_file, dump_flags);
7067 tem = cse_main (get_insns (), max_reg_num ());
7069 /* Run a pass to eliminate duplicated assignments to condition code
7070 registers. We have to run this after bypass_jumps, because it
7071 makes it harder for that pass to determine whether a jump can be
7073 cse_condition_code_reg ();
7075 delete_trivially_dead_insns (get_insns (), max_reg_num ());
7079 timevar_push (TV_JUMP);
7080 rebuild_jump_labels (get_insns ());
7081 delete_dead_jumptables ();
7082 cleanup_cfg (CLEANUP_EXPENSIVE);
7083 timevar_pop (TV_JUMP);
7085 reg_scan (get_insns (), max_reg_num ());
7086 cse_not_expected = 1;
7091 struct tree_opt_pass pass_cse2 =
7094 gate_handle_cse2, /* gate */
7095 rest_of_handle_cse2, /* execute */
7098 0, /* static_pass_number */
7099 TV_CSE2, /* tv_id */
7100 0, /* properties_required */
7101 0, /* properties_provided */
7102 0, /* properties_destroyed */
7103 0, /* todo_flags_start */
7106 TODO_verify_flow, /* todo_flags_finish */