1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 88, 89, 92-7, 1998, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 /* stdio.h must precede rtl.h for FFS. */
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
42 /* The basic idea of common subexpression elimination is to go
43 through the code, keeping a record of expressions that would
44 have the same value at the current scan point, and replacing
45 expressions encountered with the cheapest equivalent expression.
47 It is too complicated to keep track of the different possibilities
48 when control paths merge in this code; so, at each label, we forget all
49 that is known and start fresh. This can be described as processing each
50 extended basic block separately. We have a separate pass to perform
53 Note CSE can turn a conditional or computed jump into a nop or
54 an unconditional jump. When this occurs we arrange to run the jump
55 optimizer after CSE to delete the unreachable code.
57 We use two data structures to record the equivalent expressions:
58 a hash table for most expressions, and a vector of "quantity
59 numbers" to record equivalent (pseudo) registers.
61 The use of the special data structure for registers is desirable
62 because it is faster. It is possible because registers references
63 contain a fairly small number, the register number, taken from
64 a contiguously allocated series, and two register references are
65 identical if they have the same number. General expressions
66 do not have any such thing, so the only way to retrieve the
67 information recorded on an expression other than a register
68 is to keep it in a hash table.
70 Registers and "quantity numbers":
72 At the start of each basic block, all of the (hardware and pseudo)
73 registers used in the function are given distinct quantity
74 numbers to indicate their contents. During scan, when the code
75 copies one register into another, we copy the quantity number.
76 When a register is loaded in any other way, we allocate a new
77 quantity number to describe the value generated by this operation.
78 `reg_qty' records what quantity a register is currently thought
81 All real quantity numbers are greater than or equal to `max_reg'.
82 If register N has not been assigned a quantity, reg_qty[N] will equal N.
84 Quantity numbers below `max_reg' do not exist and none of the `qty_table'
85 entries should be referenced with an index below `max_reg'.
87 We also maintain a bidirectional chain of registers for each
88 quantity number. The `qty_table` members `first_reg' and `last_reg',
89 and `reg_eqv_table' members `next' and `prev' hold these chains.
91 The first register in a chain is the one whose lifespan is least local.
92 Among equals, it is the one that was seen first.
93 We replace any equivalent register with that one.
95 If two registers have the same quantity number, it must be true that
96 REG expressions with qty_table `mode' must be in the hash table for both
97 registers and must be in the same class.
99 The converse is not true. Since hard registers may be referenced in
100 any mode, two REG expressions might be equivalent in the hash table
101 but not have the same quantity number if the quantity number of one
102 of the registers is not the same mode as those expressions.
104 Constants and quantity numbers
106 When a quantity has a known constant value, that value is stored
107 in the appropriate qty_table `const_rtx'. This is in addition to
108 putting the constant in the hash table as is usual for non-regs.
110 Whether a reg or a constant is preferred is determined by the configuration
111 macro CONST_COSTS and will often depend on the constant value. In any
112 event, expressions containing constants can be simplified, by fold_rtx.
114 When a quantity has a known nearly constant value (such as an address
115 of a stack slot), that value is stored in the appropriate qty_table
118 Integer constants don't have a machine mode. However, cse
119 determines the intended machine mode from the destination
120 of the instruction that moves the constant. The machine mode
121 is recorded in the hash table along with the actual RTL
122 constant expression so that different modes are kept separate.
126 To record known equivalences among expressions in general
127 we use a hash table called `table'. It has a fixed number of buckets
128 that contain chains of `struct table_elt' elements for expressions.
129 These chains connect the elements whose expressions have the same
132 Other chains through the same elements connect the elements which
133 currently have equivalent values.
135 Register references in an expression are canonicalized before hashing
136 the expression. This is done using `reg_qty' and qty_table `first_reg'.
137 The hash code of a register reference is computed using the quantity
138 number, not the register number.
140 When the value of an expression changes, it is necessary to remove from the
141 hash table not just that expression but all expressions whose values
142 could be different as a result.
144 1. If the value changing is in memory, except in special cases
145 ANYTHING referring to memory could be changed. That is because
146 nobody knows where a pointer does not point.
147 The function `invalidate_memory' removes what is necessary.
149 The special cases are when the address is constant or is
150 a constant plus a fixed register such as the frame pointer
151 or a static chain pointer. When such addresses are stored in,
152 we can tell exactly which other such addresses must be invalidated
153 due to overlap. `invalidate' does this.
154 All expressions that refer to non-constant
155 memory addresses are also invalidated. `invalidate_memory' does this.
157 2. If the value changing is a register, all expressions
158 containing references to that register, and only those,
161 Because searching the entire hash table for expressions that contain
162 a register is very slow, we try to figure out when it isn't necessary.
163 Precisely, this is necessary only when expressions have been
164 entered in the hash table using this register, and then the value has
165 changed, and then another expression wants to be added to refer to
166 the register's new value. This sequence of circumstances is rare
167 within any one basic block.
169 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
170 reg_tick[i] is incremented whenever a value is stored in register i.
171 reg_in_table[i] holds -1 if no references to register i have been
172 entered in the table; otherwise, it contains the value reg_tick[i] had
173 when the references were entered. If we want to enter a reference
174 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
175 Until we want to enter a new entry, the mere fact that the two vectors
176 don't match makes the entries be ignored if anyone tries to match them.
178 Registers themselves are entered in the hash table as well as in
179 the equivalent-register chains. However, the vectors `reg_tick'
180 and `reg_in_table' do not apply to expressions which are simple
181 register references. These expressions are removed from the table
182 immediately when they become invalid, and this can be done even if
183 we do not immediately search for all the expressions that refer to
186 A CLOBBER rtx in an instruction invalidates its operand for further
187 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
188 invalidates everything that resides in memory.
192 Constant expressions that differ only by an additive integer
193 are called related. When a constant expression is put in
194 the table, the related expression with no constant term
195 is also entered. These are made to point at each other
196 so that it is possible to find out if there exists any
197 register equivalent to an expression related to a given expression. */
199 /* One plus largest register number used in this function. */
203 /* One plus largest instruction UID used in this function at time of
206 static int max_insn_uid;
208 /* Length of qty_table vector. We know in advance we will not need
209 a quantity number this big. */
213 /* Next quantity number to be allocated.
214 This is 1 + the largest number needed so far. */
218 /* Per-qty information tracking.
220 `first_reg' and `last_reg' track the head and tail of the
221 chain of registers which currently contain this quantity.
223 `mode' contains the machine mode of this quantity.
225 `const_rtx' holds the rtx of the constant value of this
226 quantity, if known. A summations of the frame/arg pointer
227 and a constant can also be entered here. When this holds
228 a known value, `const_insn' is the insn which stored the
231 `comparison_{code,const,qty}' are used to track when a
232 comparison between a quantity and some constant or register has
233 been passed. In such a case, we know the results of the comparison
234 in case we see it again. These members record a comparison that
235 is known to be true. `comparison_code' holds the rtx code of such
236 a comparison, else it is set to UNKNOWN and the other two
237 comparison members are undefined. `comparison_const' holds
238 the constant being compared against, or zero if the comparison
239 is not against a constant. `comparison_qty' holds the quantity
240 being compared against when the result is known. If the comparison
241 is not with a register, `comparison_qty' is -1. */
243 struct qty_table_elem
247 rtx comparison_const;
249 int first_reg, last_reg;
250 enum machine_mode mode;
251 enum rtx_code comparison_code;
254 /* The table of all qtys, indexed by qty number. */
255 static struct qty_table_elem *qty_table;
258 /* For machines that have a CC0, we do not record its value in the hash
259 table since its use is guaranteed to be the insn immediately following
260 its definition and any other insn is presumed to invalidate it.
262 Instead, we store below the value last assigned to CC0. If it should
263 happen to be a constant, it is stored in preference to the actual
264 assigned value. In case it is a constant, we store the mode in which
265 the constant should be interpreted. */
267 static rtx prev_insn_cc0;
268 static enum machine_mode prev_insn_cc0_mode;
271 /* Previous actual insn. 0 if at first insn of basic block. */
273 static rtx prev_insn;
275 /* Insn being scanned. */
277 static rtx this_insn;
279 /* Index by register number, gives the number of the next (or
280 previous) register in the chain of registers sharing the same
283 Or -1 if this register is at the end of the chain.
285 If reg_qty[N] == N, reg_eqv_table[N].next is undefined. */
287 /* Per-register equivalence chain. */
293 /* The table of all register equivalence chains. */
294 static struct reg_eqv_elem *reg_eqv_table;
298 /* The number of times the register has been altered in the current
302 /* The next cse_reg_info structure in the free or used list. */
303 struct cse_reg_info *next;
305 /* The REG_TICK value at which rtx's containing this register are
306 valid in the hash table. If this does not equal the current
307 reg_tick value, such expressions existing in the hash table are
311 /* The quantity number of the register's current contents. */
318 /* A free list of cse_reg_info entries. */
319 static struct cse_reg_info *cse_reg_info_free_list;
321 /* A used list of cse_reg_info entries. */
322 static struct cse_reg_info *cse_reg_info_used_list;
323 static struct cse_reg_info *cse_reg_info_used_list_end;
325 /* A mapping from registers to cse_reg_info data structures. */
326 static hash_table_t cse_reg_info_tree;
328 /* The last lookup we did into the cse_reg_info_tree. This allows us
329 to cache repeated lookups. */
330 static int cached_regno;
331 static struct cse_reg_info *cached_cse_reg_info;
333 /* A HARD_REG_SET containing all the hard registers for which there is
334 currently a REG expression in the hash table. Note the difference
335 from the above variables, which indicate if the REG is mentioned in some
336 expression in the table. */
338 static HARD_REG_SET hard_regs_in_table;
340 /* A HARD_REG_SET containing all the hard registers that are invalidated
343 static HARD_REG_SET regs_invalidated_by_call;
345 /* CUID of insn that starts the basic block currently being cse-processed. */
347 static int cse_basic_block_start;
349 /* CUID of insn that ends the basic block currently being cse-processed. */
351 static int cse_basic_block_end;
353 /* Vector mapping INSN_UIDs to cuids.
354 The cuids are like uids but increase monotonically always.
355 We use them to see whether a reg is used outside a given basic block. */
357 static int *uid_cuid;
359 /* Highest UID in UID_CUID. */
362 /* Get the cuid of an insn. */
364 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
366 /* Nonzero if cse has altered conditional jump insns
367 in such a way that jump optimization should be redone. */
369 static int cse_jumps_altered;
371 /* Nonzero if we put a LABEL_REF into the hash table. Since we may have put
372 it into an INSN without a REG_LABEL, we have to rerun jump after CSE
373 to put in the note. */
374 static int recorded_label_ref;
376 /* canon_hash stores 1 in do_not_record
377 if it notices a reference to CC0, PC, or some other volatile
380 static int do_not_record;
382 #ifdef LOAD_EXTEND_OP
384 /* Scratch rtl used when looking for load-extended copy of a MEM. */
385 static rtx memory_extend_rtx;
388 /* canon_hash stores 1 in hash_arg_in_memory
389 if it notices a reference to memory within the expression being hashed. */
391 static int hash_arg_in_memory;
393 /* The hash table contains buckets which are chains of `struct table_elt's,
394 each recording one expression's information.
395 That expression is in the `exp' field.
397 Those elements with the same hash code are chained in both directions
398 through the `next_same_hash' and `prev_same_hash' fields.
400 Each set of expressions with equivalent values
401 are on a two-way chain through the `next_same_value'
402 and `prev_same_value' fields, and all point with
403 the `first_same_value' field at the first element in
404 that chain. The chain is in order of increasing cost.
405 Each element's cost value is in its `cost' field.
407 The `in_memory' field is nonzero for elements that
408 involve any reference to memory. These elements are removed
409 whenever a write is done to an unidentified location in memory.
410 To be safe, we assume that a memory address is unidentified unless
411 the address is either a symbol constant or a constant plus
412 the frame pointer or argument pointer.
414 The `related_value' field is used to connect related expressions
415 (that differ by adding an integer).
416 The related expressions are chained in a circular fashion.
417 `related_value' is zero for expressions for which this
420 The `cost' field stores the cost of this element's expression.
422 The `is_const' flag is set if the element is a constant (including
425 The `flag' field is used as a temporary during some search routines.
427 The `mode' field is usually the same as GET_MODE (`exp'), but
428 if `exp' is a CONST_INT and has no machine mode then the `mode'
429 field is the mode it was being used as. Each constant is
430 recorded separately for each mode it is used with. */
436 struct table_elt *next_same_hash;
437 struct table_elt *prev_same_hash;
438 struct table_elt *next_same_value;
439 struct table_elt *prev_same_value;
440 struct table_elt *first_same_value;
441 struct table_elt *related_value;
443 enum machine_mode mode;
449 /* We don't want a lot of buckets, because we rarely have very many
450 things stored in the hash table, and a lot of buckets slows
451 down a lot of loops that happen frequently. */
454 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
455 register (hard registers may require `do_not_record' to be set). */
458 (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
459 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) % NBUCKETS \
460 : canon_hash (X, M) % NBUCKETS)
462 /* Determine whether register number N is considered a fixed register for CSE.
463 It is desirable to replace other regs with fixed regs, to reduce need for
465 A reg wins if it is either the frame pointer or designated as fixed,
466 but not if it is an overlapping register. */
467 #ifdef OVERLAPPING_REGNO_P
468 #define FIXED_REGNO_P(N) \
469 (((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
470 || fixed_regs[N] || global_regs[N]) \
471 && ! OVERLAPPING_REGNO_P ((N)))
473 #define FIXED_REGNO_P(N) \
474 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
475 || fixed_regs[N] || global_regs[N])
478 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
479 hard registers and pointers into the frame are the cheapest with a cost
480 of 0. Next come pseudos with a cost of one and other hard registers with
481 a cost of 2. Aside from these special cases, call `rtx_cost'. */
483 #define CHEAP_REGNO(N) \
484 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
485 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
486 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
487 || ((N) < FIRST_PSEUDO_REGISTER \
488 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
490 /* A register is cheap if it is a user variable assigned to the register
491 or if its register number always corresponds to a cheap register. */
493 #define CHEAP_REG(N) \
494 ((REG_USERVAR_P (N) && REGNO (N) < FIRST_PSEUDO_REGISTER) \
495 || CHEAP_REGNO (REGNO (N)))
498 (GET_CODE (X) == REG \
499 ? (CHEAP_REG (X) ? 0 \
500 : REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1 \
504 /* Get the info associated with register N. */
506 #define GET_CSE_REG_INFO(N) \
507 (((N) == cached_regno && cached_cse_reg_info) \
508 ? cached_cse_reg_info : get_cse_reg_info ((N)))
510 /* Get the number of times this register has been updated in this
513 #define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
515 /* Get the point at which REG was recorded in the table. */
517 #define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
519 /* Get the quantity number for REG. */
521 #define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
523 /* Determine if the quantity number for register X represents a valid index
524 into the qty_table. */
526 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (N))
529 /* The ADDRESS_COST macro does not deal with ADDRESSOF nodes. But,
530 during CSE, such nodes are present. Using an ADDRESSOF node which
531 refers to the address of a REG is a good thing because we can then
532 turn (MEM (ADDRESSSOF (REG))) into just plain REG. */
533 #define CSE_ADDRESS_COST(RTX) \
534 ((GET_CODE (RTX) == ADDRESSOF && REG_P (XEXP ((RTX), 0))) \
535 ? -1 : ADDRESS_COST(RTX))
538 static struct table_elt *table[NBUCKETS];
540 /* Chain of `struct table_elt's made so far for this function
541 but currently removed from the table. */
543 static struct table_elt *free_element_chain;
545 /* Number of `struct table_elt' structures made so far for this function. */
547 static int n_elements_made;
549 /* Maximum value `n_elements_made' has had so far in this compilation
550 for functions previously processed. */
552 static int max_elements_made;
554 /* Surviving equivalence class when two equivalence classes are merged
555 by recording the effects of a jump in the last insn. Zero if the
556 last insn was not a conditional jump. */
558 static struct table_elt *last_jump_equiv_class;
560 /* Set to the cost of a constant pool reference if one was found for a
561 symbolic constant. If this was found, it means we should try to
562 convert constants into constant pool entries if they don't fit in
565 static int constant_pool_entries_cost;
567 /* Define maximum length of a branch path. */
569 #define PATHLENGTH 10
571 /* This data describes a block that will be processed by cse_basic_block. */
573 struct cse_basic_block_data
575 /* Lowest CUID value of insns in block. */
577 /* Highest CUID value of insns in block. */
579 /* Total number of SETs in block. */
581 /* Last insn in the block. */
583 /* Size of current branch path, if any. */
585 /* Current branch path, indicating which branches will be taken. */
588 /* The branch insn. */
590 /* Whether it should be taken or not. AROUND is the same as taken
591 except that it is used when the destination label is not preceded
593 enum taken {TAKEN, NOT_TAKEN, AROUND} status;
597 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
598 virtual regs here because the simplify_*_operation routines are called
599 by integrate.c, which is called before virtual register instantiation.
601 ?!? FIXED_BASE_PLUS_P and NONZERO_BASE_PLUS_P need to move into
602 a header file so that their definitions can be shared with the
603 simplification routines in simplify-rtx.c. Until then, do not
604 change these macros without also changing the copy in simplify-rtx.c. */
606 #define FIXED_BASE_PLUS_P(X) \
607 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
608 || ((X) == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])\
609 || (X) == virtual_stack_vars_rtx \
610 || (X) == virtual_incoming_args_rtx \
611 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
612 && (XEXP (X, 0) == frame_pointer_rtx \
613 || XEXP (X, 0) == hard_frame_pointer_rtx \
614 || ((X) == arg_pointer_rtx \
615 && fixed_regs[ARG_POINTER_REGNUM]) \
616 || XEXP (X, 0) == virtual_stack_vars_rtx \
617 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
618 || GET_CODE (X) == ADDRESSOF)
620 /* Similar, but also allows reference to the stack pointer.
622 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
623 arg_pointer_rtx by itself is nonzero, because on at least one machine,
624 the i960, the arg pointer is zero when it is unused. */
626 #define NONZERO_BASE_PLUS_P(X) \
627 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
628 || (X) == virtual_stack_vars_rtx \
629 || (X) == virtual_incoming_args_rtx \
630 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
631 && (XEXP (X, 0) == frame_pointer_rtx \
632 || XEXP (X, 0) == hard_frame_pointer_rtx \
633 || ((X) == arg_pointer_rtx \
634 && fixed_regs[ARG_POINTER_REGNUM]) \
635 || XEXP (X, 0) == virtual_stack_vars_rtx \
636 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
637 || (X) == stack_pointer_rtx \
638 || (X) == virtual_stack_dynamic_rtx \
639 || (X) == virtual_outgoing_args_rtx \
640 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
641 && (XEXP (X, 0) == stack_pointer_rtx \
642 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
643 || XEXP (X, 0) == virtual_outgoing_args_rtx)) \
644 || GET_CODE (X) == ADDRESSOF)
646 static int notreg_cost PROTO((rtx));
647 static void new_basic_block PROTO((void));
648 static void make_new_qty PROTO((int, enum machine_mode));
649 static void make_regs_eqv PROTO((int, int));
650 static void delete_reg_equiv PROTO((int));
651 static int mention_regs PROTO((rtx));
652 static int insert_regs PROTO((rtx, struct table_elt *, int));
653 static void free_element PROTO((struct table_elt *));
654 static void remove_from_table PROTO((struct table_elt *, unsigned));
655 static struct table_elt *get_element PROTO((void));
656 static struct table_elt *lookup PROTO((rtx, unsigned, enum machine_mode)),
657 *lookup_for_remove PROTO((rtx, unsigned, enum machine_mode));
658 static rtx lookup_as_function PROTO((rtx, enum rtx_code));
659 static struct table_elt *insert PROTO((rtx, struct table_elt *, unsigned,
661 static void merge_equiv_classes PROTO((struct table_elt *,
662 struct table_elt *));
663 static void invalidate PROTO((rtx, enum machine_mode));
664 static int cse_rtx_varies_p PROTO((rtx));
665 static void remove_invalid_refs PROTO((int));
666 static void remove_invalid_subreg_refs PROTO((int, int, enum machine_mode));
667 static void rehash_using_reg PROTO((rtx));
668 static void invalidate_memory PROTO((void));
669 static void invalidate_for_call PROTO((void));
670 static rtx use_related_value PROTO((rtx, struct table_elt *));
671 static unsigned canon_hash PROTO((rtx, enum machine_mode));
672 static unsigned safe_hash PROTO((rtx, enum machine_mode));
673 static int exp_equiv_p PROTO((rtx, rtx, int, int));
674 static rtx canon_reg PROTO((rtx, rtx));
675 static void find_best_addr PROTO((rtx, rtx *));
676 static enum rtx_code find_comparison_args PROTO((enum rtx_code, rtx *, rtx *,
678 enum machine_mode *));
679 static rtx fold_rtx PROTO((rtx, rtx));
680 static rtx equiv_constant PROTO((rtx));
681 static void record_jump_equiv PROTO((rtx, int));
682 static void record_jump_cond PROTO((enum rtx_code, enum machine_mode,
684 static void cse_insn PROTO((rtx, rtx));
685 static int addr_affects_sp_p PROTO((rtx));
686 static void invalidate_from_clobbers PROTO((rtx));
687 static rtx cse_process_notes PROTO((rtx, rtx));
688 static void cse_around_loop PROTO((rtx));
689 static void invalidate_skipped_set PROTO((rtx, rtx, void *));
690 static void invalidate_skipped_block PROTO((rtx));
691 static void cse_check_loop_start PROTO((rtx, rtx, void *));
692 static void cse_set_around_loop PROTO((rtx, rtx, rtx));
693 static rtx cse_basic_block PROTO((rtx, rtx, struct branch_path *, int));
694 static void count_reg_usage PROTO((rtx, int *, rtx, int));
695 extern void dump_class PROTO((struct table_elt*));
696 static struct cse_reg_info* get_cse_reg_info PROTO((int));
697 static unsigned int hash_cse_reg_info PROTO((hash_table_entry_t));
698 static int cse_reg_info_equal_p PROTO((hash_table_entry_t,
699 hash_table_entry_t));
701 static void flush_hash_table PROTO((void));
703 /* Dump the expressions in the equivalence class indicated by CLASSP.
704 This function is used only for debugging. */
707 struct table_elt *classp;
709 struct table_elt *elt;
711 fprintf (stderr, "Equivalence chain for ");
712 print_rtl (stderr, classp->exp);
713 fprintf (stderr, ": \n");
715 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
717 print_rtl (stderr, elt->exp);
718 fprintf (stderr, "\n");
722 /* Return an estimate of the cost of computing rtx X.
723 One use is in cse, to decide which expression to keep in the hash table.
724 Another is in rtl generation, to pick the cheapest way to multiply.
725 Other uses like the latter are expected in the future. */
727 /* Internal function, to compute cost when X is not a register; called
728 from COST macro to keep it simple. */
734 return ((GET_CODE (x) == SUBREG
735 && GET_CODE (SUBREG_REG (x)) == REG
736 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
737 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
738 && (GET_MODE_SIZE (GET_MODE (x))
739 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
740 && subreg_lowpart_p (x)
741 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
742 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
743 ? (CHEAP_REG (SUBREG_REG (x)) ? 0
744 : (REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER ? 1
746 : rtx_cost (x, SET) * 2);
749 /* Return the right cost to give to an operation
750 to make the cost of the corresponding register-to-register instruction
751 N times that of a fast register-to-register instruction. */
753 #define COSTS_N_INSNS(N) ((N) * 4 - 2)
756 rtx_cost (x, outer_code)
758 enum rtx_code outer_code ATTRIBUTE_UNUSED;
761 register enum rtx_code code;
762 register const char *fmt;
768 /* Compute the default costs of certain things.
769 Note that RTX_COSTS can override the defaults. */
775 /* Count multiplication by 2**n as a shift,
776 because if we are considering it, we would output it as a shift. */
777 if (GET_CODE (XEXP (x, 1)) == CONST_INT
778 && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
781 total = COSTS_N_INSNS (5);
787 total = COSTS_N_INSNS (7);
790 /* Used in loop.c and combine.c as a marker. */
794 /* We don't want these to be used in substitutions because
795 we have no way of validating the resulting insn. So assign
796 anything containing an ASM_OPERANDS a very high cost. */
806 return ! CHEAP_REG (x);
809 /* If we can't tie these modes, make this expensive. The larger
810 the mode, the more expensive it is. */
811 if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
812 return COSTS_N_INSNS (2
813 + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
816 RTX_COSTS (x, code, outer_code);
819 CONST_COSTS (x, code, outer_code);
823 #ifdef DEFAULT_RTX_COSTS
824 DEFAULT_RTX_COSTS(x, code, outer_code);
829 /* Sum the costs of the sub-rtx's, plus cost of this operation,
830 which is already in total. */
832 fmt = GET_RTX_FORMAT (code);
833 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
835 total += rtx_cost (XEXP (x, i), code);
836 else if (fmt[i] == 'E')
837 for (j = 0; j < XVECLEN (x, i); j++)
838 total += rtx_cost (XVECEXP (x, i, j), code);
843 static struct cse_reg_info *
844 get_cse_reg_info (regno)
847 struct cse_reg_info *cri;
848 struct cse_reg_info **entry;
849 struct cse_reg_info temp;
851 /* See if we already have this entry. */
853 entry = (struct cse_reg_info **) find_hash_table_entry (cse_reg_info_tree,
860 /* Get a new cse_reg_info structure. */
861 if (cse_reg_info_free_list)
863 cri = cse_reg_info_free_list;
864 cse_reg_info_free_list = cri->next;
867 cri = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info));
871 cri->reg_in_table = -1;
872 cri->reg_qty = regno;
874 cri->next = cse_reg_info_used_list;
875 cse_reg_info_used_list = cri;
876 if (!cse_reg_info_used_list_end)
877 cse_reg_info_used_list_end = cri;
882 /* Cache this lookup; we tend to be looking up information about the
883 same register several times in a row. */
884 cached_regno = regno;
885 cached_cse_reg_info = cri;
891 hash_cse_reg_info (el_ptr)
892 hash_table_entry_t el_ptr;
894 return ((const struct cse_reg_info *) el_ptr)->regno;
898 cse_reg_info_equal_p (el_ptr1, el_ptr2)
899 hash_table_entry_t el_ptr1;
900 hash_table_entry_t el_ptr2;
902 return (((const struct cse_reg_info *) el_ptr1)->regno
903 == ((const struct cse_reg_info *) el_ptr2)->regno);
906 /* Clear the hash table and initialize each register with its own quantity,
907 for a new basic block. */
916 if (cse_reg_info_tree)
918 delete_hash_table (cse_reg_info_tree);
919 if (cse_reg_info_used_list)
921 cse_reg_info_used_list_end->next = cse_reg_info_free_list;
922 cse_reg_info_free_list = cse_reg_info_used_list;
923 cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
925 cached_cse_reg_info = 0;
928 cse_reg_info_tree = create_hash_table (0, hash_cse_reg_info,
929 cse_reg_info_equal_p);
931 CLEAR_HARD_REG_SET (hard_regs_in_table);
933 /* The per-quantity values used to be initialized here, but it is
934 much faster to initialize each as it is made in `make_new_qty'. */
936 for (i = 0; i < NBUCKETS; i++)
938 register struct table_elt *this, *next;
939 for (this = table[i]; this; this = next)
941 next = this->next_same_hash;
946 bzero ((char *) table, sizeof table);
955 /* Say that register REG contains a quantity in mode MODE not in any
956 register before and initialize that quantity. */
959 make_new_qty (reg, mode)
961 register enum machine_mode mode;
964 register struct qty_table_elem *ent;
965 register struct reg_eqv_elem *eqv;
967 if (next_qty >= max_qty)
970 q = REG_QTY (reg) = next_qty++;
972 ent->first_reg = reg;
975 ent->const_rtx = ent->const_insn = NULL_RTX;
976 ent->comparison_code = UNKNOWN;
978 eqv = ®_eqv_table[reg];
979 eqv->next = eqv->prev = -1;
982 /* Make reg NEW equivalent to reg OLD.
983 OLD is not changing; NEW is. */
986 make_regs_eqv (new, old)
987 register int new, old;
989 register int lastr, firstr;
990 register int q = REG_QTY (old);
991 register struct qty_table_elem *ent;
995 /* Nothing should become eqv until it has a "non-invalid" qty number. */
996 if (! REGNO_QTY_VALID_P (old))
1000 firstr = ent->first_reg;
1001 lastr = ent->last_reg;
1003 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
1004 hard regs. Among pseudos, if NEW will live longer than any other reg
1005 of the same qty, and that is beyond the current basic block,
1006 make it the new canonical replacement for this qty. */
1007 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
1008 /* Certain fixed registers might be of the class NO_REGS. This means
1009 that not only can they not be allocated by the compiler, but
1010 they cannot be used in substitutions or canonicalizations
1012 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
1013 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
1014 || (new >= FIRST_PSEUDO_REGISTER
1015 && (firstr < FIRST_PSEUDO_REGISTER
1016 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
1017 || (uid_cuid[REGNO_FIRST_UID (new)]
1018 < cse_basic_block_start))
1019 && (uid_cuid[REGNO_LAST_UID (new)]
1020 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
1022 reg_eqv_table[firstr].prev = new;
1023 reg_eqv_table[new].next = firstr;
1024 reg_eqv_table[new].prev = -1;
1025 ent->first_reg = new;
1029 /* If NEW is a hard reg (known to be non-fixed), insert at end.
1030 Otherwise, insert before any non-fixed hard regs that are at the
1031 end. Registers of class NO_REGS cannot be used as an
1032 equivalent for anything. */
1033 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
1034 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
1035 && new >= FIRST_PSEUDO_REGISTER)
1036 lastr = reg_eqv_table[lastr].prev;
1037 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
1038 if (reg_eqv_table[lastr].next >= 0)
1039 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
1041 qty_table[q].last_reg = new;
1042 reg_eqv_table[lastr].next = new;
1043 reg_eqv_table[new].prev = lastr;
1047 /* Remove REG from its equivalence class. */
1050 delete_reg_equiv (reg)
1053 register struct qty_table_elem *ent;
1054 register int q = REG_QTY (reg);
1057 /* If invalid, do nothing. */
1061 ent = &qty_table[q];
1063 p = reg_eqv_table[reg].prev;
1064 n = reg_eqv_table[reg].next;
1067 reg_eqv_table[n].prev = p;
1071 reg_eqv_table[p].next = n;
1075 REG_QTY (reg) = reg;
1078 /* Remove any invalid expressions from the hash table
1079 that refer to any of the registers contained in expression X.
1081 Make sure that newly inserted references to those registers
1082 as subexpressions will be considered valid.
1084 mention_regs is not called when a register itself
1085 is being stored in the table.
1087 Return 1 if we have done something that may have changed the hash code
1094 register enum rtx_code code;
1096 register const char *fmt;
1097 register int changed = 0;
1102 code = GET_CODE (x);
1105 register int regno = REGNO (x);
1106 register int endregno
1107 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1108 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
1111 for (i = regno; i < endregno; i++)
1113 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1114 remove_invalid_refs (i);
1116 REG_IN_TABLE (i) = REG_TICK (i);
1122 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1123 pseudo if they don't use overlapping words. We handle only pseudos
1124 here for simplicity. */
1125 if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1126 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1128 int i = REGNO (SUBREG_REG (x));
1130 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1132 /* If reg_tick has been incremented more than once since
1133 reg_in_table was last set, that means that the entire
1134 register has been set before, so discard anything memorized
1135 for the entrire register, including all SUBREG expressions. */
1136 if (REG_IN_TABLE (i) != REG_TICK (i) - 1)
1137 remove_invalid_refs (i);
1139 remove_invalid_subreg_refs (i, SUBREG_WORD (x), GET_MODE (x));
1142 REG_IN_TABLE (i) = REG_TICK (i);
1146 /* If X is a comparison or a COMPARE and either operand is a register
1147 that does not have a quantity, give it one. This is so that a later
1148 call to record_jump_equiv won't cause X to be assigned a different
1149 hash code and not found in the table after that call.
1151 It is not necessary to do this here, since rehash_using_reg can
1152 fix up the table later, but doing this here eliminates the need to
1153 call that expensive function in the most common case where the only
1154 use of the register is in the comparison. */
1156 if (code == COMPARE || GET_RTX_CLASS (code) == '<')
1158 if (GET_CODE (XEXP (x, 0)) == REG
1159 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1160 if (insert_regs (XEXP (x, 0), NULL_PTR, 0))
1162 rehash_using_reg (XEXP (x, 0));
1166 if (GET_CODE (XEXP (x, 1)) == REG
1167 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1168 if (insert_regs (XEXP (x, 1), NULL_PTR, 0))
1170 rehash_using_reg (XEXP (x, 1));
1175 fmt = GET_RTX_FORMAT (code);
1176 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1178 changed |= mention_regs (XEXP (x, i));
1179 else if (fmt[i] == 'E')
1180 for (j = 0; j < XVECLEN (x, i); j++)
1181 changed |= mention_regs (XVECEXP (x, i, j));
1186 /* Update the register quantities for inserting X into the hash table
1187 with a value equivalent to CLASSP.
1188 (If the class does not contain a REG, it is irrelevant.)
1189 If MODIFIED is nonzero, X is a destination; it is being modified.
1190 Note that delete_reg_equiv should be called on a register
1191 before insert_regs is done on that register with MODIFIED != 0.
1193 Nonzero value means that elements of reg_qty have changed
1194 so X's hash code may be different. */
1197 insert_regs (x, classp, modified)
1199 struct table_elt *classp;
1202 if (GET_CODE (x) == REG)
1204 register int regno = REGNO (x);
1205 register int qty_valid;
1207 /* If REGNO is in the equivalence table already but is of the
1208 wrong mode for that equivalence, don't do anything here. */
1210 qty_valid = REGNO_QTY_VALID_P (regno);
1213 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1215 if (ent->mode != GET_MODE (x))
1219 if (modified || ! qty_valid)
1222 for (classp = classp->first_same_value;
1224 classp = classp->next_same_value)
1225 if (GET_CODE (classp->exp) == REG
1226 && GET_MODE (classp->exp) == GET_MODE (x))
1228 make_regs_eqv (regno, REGNO (classp->exp));
1232 make_new_qty (regno, GET_MODE (x));
1239 /* If X is a SUBREG, we will likely be inserting the inner register in the
1240 table. If that register doesn't have an assigned quantity number at
1241 this point but does later, the insertion that we will be doing now will
1242 not be accessible because its hash code will have changed. So assign
1243 a quantity number now. */
1245 else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1246 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1248 int regno = REGNO (SUBREG_REG (x));
1250 insert_regs (SUBREG_REG (x), NULL_PTR, 0);
1251 /* Mention_regs checks if REG_TICK is exactly one larger than
1252 REG_IN_TABLE to find out if there was only a single preceding
1253 invalidation - for the SUBREG - or another one, which would be
1254 for the full register. Since we don't invalidate the SUBREG
1255 here first, we might have to bump up REG_TICK so that mention_regs
1256 will do the right thing. */
1257 if (REG_IN_TABLE (regno) >= 0
1258 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1264 return mention_regs (x);
1267 /* Look in or update the hash table. */
1269 /* Put the element ELT on the list of free elements. */
1273 struct table_elt *elt;
1275 elt->next_same_hash = free_element_chain;
1276 free_element_chain = elt;
1279 /* Return an element that is free for use. */
1281 static struct table_elt *
1284 struct table_elt *elt = free_element_chain;
1287 free_element_chain = elt->next_same_hash;
1291 return (struct table_elt *) oballoc (sizeof (struct table_elt));
1294 /* Remove table element ELT from use in the table.
1295 HASH is its hash code, made using the HASH macro.
1296 It's an argument because often that is known in advance
1297 and we save much time not recomputing it. */
1300 remove_from_table (elt, hash)
1301 register struct table_elt *elt;
1307 /* Mark this element as removed. See cse_insn. */
1308 elt->first_same_value = 0;
1310 /* Remove the table element from its equivalence class. */
1313 register struct table_elt *prev = elt->prev_same_value;
1314 register struct table_elt *next = elt->next_same_value;
1316 if (next) next->prev_same_value = prev;
1319 prev->next_same_value = next;
1322 register struct table_elt *newfirst = next;
1325 next->first_same_value = newfirst;
1326 next = next->next_same_value;
1331 /* Remove the table element from its hash bucket. */
1334 register struct table_elt *prev = elt->prev_same_hash;
1335 register struct table_elt *next = elt->next_same_hash;
1337 if (next) next->prev_same_hash = prev;
1340 prev->next_same_hash = next;
1341 else if (table[hash] == elt)
1345 /* This entry is not in the proper hash bucket. This can happen
1346 when two classes were merged by `merge_equiv_classes'. Search
1347 for the hash bucket that it heads. This happens only very
1348 rarely, so the cost is acceptable. */
1349 for (hash = 0; hash < NBUCKETS; hash++)
1350 if (table[hash] == elt)
1355 /* Remove the table element from its related-value circular chain. */
1357 if (elt->related_value != 0 && elt->related_value != elt)
1359 register struct table_elt *p = elt->related_value;
1360 while (p->related_value != elt)
1361 p = p->related_value;
1362 p->related_value = elt->related_value;
1363 if (p->related_value == p)
1364 p->related_value = 0;
1370 /* Look up X in the hash table and return its table element,
1371 or 0 if X is not in the table.
1373 MODE is the machine-mode of X, or if X is an integer constant
1374 with VOIDmode then MODE is the mode with which X will be used.
1376 Here we are satisfied to find an expression whose tree structure
1379 static struct table_elt *
1380 lookup (x, hash, mode)
1383 enum machine_mode mode;
1385 register struct table_elt *p;
1387 for (p = table[hash]; p; p = p->next_same_hash)
1388 if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
1389 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
1395 /* Like `lookup' but don't care whether the table element uses invalid regs.
1396 Also ignore discrepancies in the machine mode of a register. */
1398 static struct table_elt *
1399 lookup_for_remove (x, hash, mode)
1402 enum machine_mode mode;
1404 register struct table_elt *p;
1406 if (GET_CODE (x) == REG)
1408 int regno = REGNO (x);
1409 /* Don't check the machine mode when comparing registers;
1410 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1411 for (p = table[hash]; p; p = p->next_same_hash)
1412 if (GET_CODE (p->exp) == REG
1413 && REGNO (p->exp) == regno)
1418 for (p = table[hash]; p; p = p->next_same_hash)
1419 if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
1426 /* Look for an expression equivalent to X and with code CODE.
1427 If one is found, return that expression. */
1430 lookup_as_function (x, code)
1434 register struct table_elt *p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS,
1436 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1437 long as we are narrowing. So if we looked in vain for a mode narrower
1438 than word_mode before, look for word_mode now. */
1439 if (p == 0 && code == CONST_INT
1440 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1443 PUT_MODE (x, word_mode);
1444 p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS, word_mode);
1450 for (p = p->first_same_value; p; p = p->next_same_value)
1452 if (GET_CODE (p->exp) == code
1453 /* Make sure this is a valid entry in the table. */
1454 && exp_equiv_p (p->exp, p->exp, 1, 0))
1461 /* Insert X in the hash table, assuming HASH is its hash code
1462 and CLASSP is an element of the class it should go in
1463 (or 0 if a new class should be made).
1464 It is inserted at the proper position to keep the class in
1465 the order cheapest first.
1467 MODE is the machine-mode of X, or if X is an integer constant
1468 with VOIDmode then MODE is the mode with which X will be used.
1470 For elements of equal cheapness, the most recent one
1471 goes in front, except that the first element in the list
1472 remains first unless a cheaper element is added. The order of
1473 pseudo-registers does not matter, as canon_reg will be called to
1474 find the cheapest when a register is retrieved from the table.
1476 The in_memory field in the hash table element is set to 0.
1477 The caller must set it nonzero if appropriate.
1479 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1480 and if insert_regs returns a nonzero value
1481 you must then recompute its hash code before calling here.
1483 If necessary, update table showing constant values of quantities. */
1485 #define CHEAPER(X,Y) ((X)->cost < (Y)->cost)
1487 static struct table_elt *
1488 insert (x, classp, hash, mode)
1490 register struct table_elt *classp;
1492 enum machine_mode mode;
1494 register struct table_elt *elt;
1496 /* If X is a register and we haven't made a quantity for it,
1497 something is wrong. */
1498 if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
1501 /* If X is a hard register, show it is being put in the table. */
1502 if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
1504 int regno = REGNO (x);
1505 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1508 for (i = regno; i < endregno; i++)
1509 SET_HARD_REG_BIT (hard_regs_in_table, i);
1512 /* If X is a label, show we recorded it. */
1513 if (GET_CODE (x) == LABEL_REF
1514 || (GET_CODE (x) == CONST && GET_CODE (XEXP (x, 0)) == PLUS
1515 && GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))
1516 recorded_label_ref = 1;
1518 /* Put an element for X into the right hash bucket. */
1520 elt = get_element ();
1522 elt->cost = COST (x);
1523 elt->next_same_value = 0;
1524 elt->prev_same_value = 0;
1525 elt->next_same_hash = table[hash];
1526 elt->prev_same_hash = 0;
1527 elt->related_value = 0;
1530 elt->is_const = (CONSTANT_P (x)
1531 /* GNU C++ takes advantage of this for `this'
1532 (and other const values). */
1533 || (RTX_UNCHANGING_P (x)
1534 && GET_CODE (x) == REG
1535 && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1536 || FIXED_BASE_PLUS_P (x));
1539 table[hash]->prev_same_hash = elt;
1542 /* Put it into the proper value-class. */
1545 classp = classp->first_same_value;
1546 if (CHEAPER (elt, classp))
1547 /* Insert at the head of the class */
1549 register struct table_elt *p;
1550 elt->next_same_value = classp;
1551 classp->prev_same_value = elt;
1552 elt->first_same_value = elt;
1554 for (p = classp; p; p = p->next_same_value)
1555 p->first_same_value = elt;
1559 /* Insert not at head of the class. */
1560 /* Put it after the last element cheaper than X. */
1561 register struct table_elt *p, *next;
1562 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1564 /* Put it after P and before NEXT. */
1565 elt->next_same_value = next;
1567 next->prev_same_value = elt;
1568 elt->prev_same_value = p;
1569 p->next_same_value = elt;
1570 elt->first_same_value = classp;
1574 elt->first_same_value = elt;
1576 /* If this is a constant being set equivalent to a register or a register
1577 being set equivalent to a constant, note the constant equivalence.
1579 If this is a constant, it cannot be equivalent to a different constant,
1580 and a constant is the only thing that can be cheaper than a register. So
1581 we know the register is the head of the class (before the constant was
1584 If this is a register that is not already known equivalent to a
1585 constant, we must check the entire class.
1587 If this is a register that is already known equivalent to an insn,
1588 update the qtys `const_insn' to show that `this_insn' is the latest
1589 insn making that quantity equivalent to the constant. */
1591 if (elt->is_const && classp && GET_CODE (classp->exp) == REG
1592 && GET_CODE (x) != REG)
1594 int exp_q = REG_QTY (REGNO (classp->exp));
1595 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1597 exp_ent->const_rtx = gen_lowpart_if_possible (exp_ent->mode, x);
1598 exp_ent->const_insn = this_insn;
1601 else if (GET_CODE (x) == REG
1603 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1606 register struct table_elt *p;
1608 for (p = classp; p != 0; p = p->next_same_value)
1610 if (p->is_const && GET_CODE (p->exp) != REG)
1612 int x_q = REG_QTY (REGNO (x));
1613 struct qty_table_elem *x_ent = &qty_table[x_q];
1615 x_ent->const_rtx = gen_lowpart_if_possible (GET_MODE (x), p->exp);
1616 x_ent->const_insn = this_insn;
1622 else if (GET_CODE (x) == REG
1623 && qty_table[REG_QTY (REGNO (x))].const_rtx
1624 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1625 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1627 /* If this is a constant with symbolic value,
1628 and it has a term with an explicit integer value,
1629 link it up with related expressions. */
1630 if (GET_CODE (x) == CONST)
1632 rtx subexp = get_related_value (x);
1634 struct table_elt *subelt, *subelt_prev;
1638 /* Get the integer-free subexpression in the hash table. */
1639 subhash = safe_hash (subexp, mode) % NBUCKETS;
1640 subelt = lookup (subexp, subhash, mode);
1642 subelt = insert (subexp, NULL_PTR, subhash, mode);
1643 /* Initialize SUBELT's circular chain if it has none. */
1644 if (subelt->related_value == 0)
1645 subelt->related_value = subelt;
1646 /* Find the element in the circular chain that precedes SUBELT. */
1647 subelt_prev = subelt;
1648 while (subelt_prev->related_value != subelt)
1649 subelt_prev = subelt_prev->related_value;
1650 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1651 This way the element that follows SUBELT is the oldest one. */
1652 elt->related_value = subelt_prev->related_value;
1653 subelt_prev->related_value = elt;
1660 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1661 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1662 the two classes equivalent.
1664 CLASS1 will be the surviving class; CLASS2 should not be used after this
1667 Any invalid entries in CLASS2 will not be copied. */
1670 merge_equiv_classes (class1, class2)
1671 struct table_elt *class1, *class2;
1673 struct table_elt *elt, *next, *new;
1675 /* Ensure we start with the head of the classes. */
1676 class1 = class1->first_same_value;
1677 class2 = class2->first_same_value;
1679 /* If they were already equal, forget it. */
1680 if (class1 == class2)
1683 for (elt = class2; elt; elt = next)
1687 enum machine_mode mode = elt->mode;
1689 next = elt->next_same_value;
1691 /* Remove old entry, make a new one in CLASS1's class.
1692 Don't do this for invalid entries as we cannot find their
1693 hash code (it also isn't necessary). */
1694 if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
1696 hash_arg_in_memory = 0;
1697 hash = HASH (exp, mode);
1699 if (GET_CODE (exp) == REG)
1700 delete_reg_equiv (REGNO (exp));
1702 remove_from_table (elt, hash);
1704 if (insert_regs (exp, class1, 0))
1706 rehash_using_reg (exp);
1707 hash = HASH (exp, mode);
1709 new = insert (exp, class1, hash, mode);
1710 new->in_memory = hash_arg_in_memory;
1716 /* Flush the entire hash table. */
1722 struct table_elt *p;
1724 for (i = 0; i < NBUCKETS; i++)
1725 for (p = table[i]; p; p = table[i])
1727 /* Note that invalidate can remove elements
1728 after P in the current hash chain. */
1729 if (GET_CODE (p->exp) == REG)
1730 invalidate (p->exp, p->mode);
1732 remove_from_table (p, i);
1736 /* Remove from the hash table, or mark as invalid, all expressions whose
1737 values could be altered by storing in X. X is a register, a subreg, or
1738 a memory reference with nonvarying address (because, when a memory
1739 reference with a varying address is stored in, all memory references are
1740 removed by invalidate_memory so specific invalidation is superfluous).
1741 FULL_MODE, if not VOIDmode, indicates that this much should be
1742 invalidated instead of just the amount indicated by the mode of X. This
1743 is only used for bitfield stores into memory.
1745 A nonvarying address may be just a register or just a symbol reference,
1746 or it may be either of those plus a numeric offset. */
1749 invalidate (x, full_mode)
1751 enum machine_mode full_mode;
1754 register struct table_elt *p;
1756 switch (GET_CODE (x))
1760 /* If X is a register, dependencies on its contents are recorded
1761 through the qty number mechanism. Just change the qty number of
1762 the register, mark it as invalid for expressions that refer to it,
1763 and remove it itself. */
1764 register int regno = REGNO (x);
1765 register unsigned hash = HASH (x, GET_MODE (x));
1767 /* Remove REGNO from any quantity list it might be on and indicate
1768 that its value might have changed. If it is a pseudo, remove its
1769 entry from the hash table.
1771 For a hard register, we do the first two actions above for any
1772 additional hard registers corresponding to X. Then, if any of these
1773 registers are in the table, we must remove any REG entries that
1774 overlap these registers. */
1776 delete_reg_equiv (regno);
1779 if (regno >= FIRST_PSEUDO_REGISTER)
1781 /* Because a register can be referenced in more than one mode,
1782 we might have to remove more than one table entry. */
1783 struct table_elt *elt;
1785 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1786 remove_from_table (elt, hash);
1790 HOST_WIDE_INT in_table
1791 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1792 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1793 int tregno, tendregno;
1794 register struct table_elt *p, *next;
1796 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1798 for (i = regno + 1; i < endregno; i++)
1800 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
1801 CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
1802 delete_reg_equiv (i);
1807 for (hash = 0; hash < NBUCKETS; hash++)
1808 for (p = table[hash]; p; p = next)
1810 next = p->next_same_hash;
1812 if (GET_CODE (p->exp) != REG
1813 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1816 tregno = REGNO (p->exp);
1818 = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
1819 if (tendregno > regno && tregno < endregno)
1820 remove_from_table (p, hash);
1827 invalidate (SUBREG_REG (x), VOIDmode);
1831 for (i = XVECLEN (x, 0) - 1; i >= 0 ; --i)
1832 invalidate (XVECEXP (x, 0, i), VOIDmode);
1836 /* This is part of a disjoint return value; extract the location in
1837 question ignoring the offset. */
1838 invalidate (XEXP (x, 0), VOIDmode);
1842 /* Remove all hash table elements that refer to overlapping pieces of
1844 if (full_mode == VOIDmode)
1845 full_mode = GET_MODE (x);
1847 for (i = 0; i < NBUCKETS; i++)
1849 register struct table_elt *next;
1851 for (p = table[i]; p; p = next)
1853 next = p->next_same_hash;
1855 && (GET_CODE (p->exp) != MEM
1856 || true_dependence (x, full_mode, p->exp,
1858 remove_from_table (p, i);
1868 /* Remove all expressions that refer to register REGNO,
1869 since they are already invalid, and we are about to
1870 mark that register valid again and don't want the old
1871 expressions to reappear as valid. */
1874 remove_invalid_refs (regno)
1878 register struct table_elt *p, *next;
1880 for (i = 0; i < NBUCKETS; i++)
1881 for (p = table[i]; p; p = next)
1883 next = p->next_same_hash;
1884 if (GET_CODE (p->exp) != REG
1885 && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR))
1886 remove_from_table (p, i);
1890 /* Likewise for a subreg with subreg_reg WORD and mode MODE. */
1892 remove_invalid_subreg_refs (regno, word, mode)
1895 enum machine_mode mode;
1898 register struct table_elt *p, *next;
1899 int end = word + (GET_MODE_SIZE (mode) - 1) / UNITS_PER_WORD;
1901 for (i = 0; i < NBUCKETS; i++)
1902 for (p = table[i]; p; p = next)
1905 next = p->next_same_hash;
1908 if (GET_CODE (p->exp) != REG
1909 && (GET_CODE (exp) != SUBREG
1910 || GET_CODE (SUBREG_REG (exp)) != REG
1911 || REGNO (SUBREG_REG (exp)) != regno
1912 || (((SUBREG_WORD (exp)
1913 + (GET_MODE_SIZE (GET_MODE (exp)) - 1) / UNITS_PER_WORD)
1915 && SUBREG_WORD (exp) <= end))
1916 && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR))
1917 remove_from_table (p, i);
1921 /* Recompute the hash codes of any valid entries in the hash table that
1922 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1924 This is called when we make a jump equivalence. */
1927 rehash_using_reg (x)
1931 struct table_elt *p, *next;
1934 if (GET_CODE (x) == SUBREG)
1937 /* If X is not a register or if the register is known not to be in any
1938 valid entries in the table, we have no work to do. */
1940 if (GET_CODE (x) != REG
1941 || REG_IN_TABLE (REGNO (x)) < 0
1942 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
1945 /* Scan all hash chains looking for valid entries that mention X.
1946 If we find one and it is in the wrong hash chain, move it. We can skip
1947 objects that are registers, since they are handled specially. */
1949 for (i = 0; i < NBUCKETS; i++)
1950 for (p = table[i]; p; p = next)
1952 next = p->next_same_hash;
1953 if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
1954 && exp_equiv_p (p->exp, p->exp, 1, 0)
1955 && i != (hash = safe_hash (p->exp, p->mode) % NBUCKETS))
1957 if (p->next_same_hash)
1958 p->next_same_hash->prev_same_hash = p->prev_same_hash;
1960 if (p->prev_same_hash)
1961 p->prev_same_hash->next_same_hash = p->next_same_hash;
1963 table[i] = p->next_same_hash;
1965 p->next_same_hash = table[hash];
1966 p->prev_same_hash = 0;
1968 table[hash]->prev_same_hash = p;
1974 /* Remove from the hash table any expression that is a call-clobbered
1975 register. Also update their TICK values. */
1978 invalidate_for_call ()
1980 int regno, endregno;
1983 struct table_elt *p, *next;
1986 /* Go through all the hard registers. For each that is clobbered in
1987 a CALL_INSN, remove the register from quantity chains and update
1988 reg_tick if defined. Also see if any of these registers is currently
1991 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1992 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1994 delete_reg_equiv (regno);
1995 if (REG_TICK (regno) >= 0)
1998 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2001 /* In the case where we have no call-clobbered hard registers in the
2002 table, we are done. Otherwise, scan the table and remove any
2003 entry that overlaps a call-clobbered register. */
2006 for (hash = 0; hash < NBUCKETS; hash++)
2007 for (p = table[hash]; p; p = next)
2009 next = p->next_same_hash;
2011 if (GET_CODE (p->exp) != REG
2012 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2015 regno = REGNO (p->exp);
2016 endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
2018 for (i = regno; i < endregno; i++)
2019 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2021 remove_from_table (p, hash);
2027 /* Given an expression X of type CONST,
2028 and ELT which is its table entry (or 0 if it
2029 is not in the hash table),
2030 return an alternate expression for X as a register plus integer.
2031 If none can be found, return 0. */
2034 use_related_value (x, elt)
2036 struct table_elt *elt;
2038 register struct table_elt *relt = 0;
2039 register struct table_elt *p, *q;
2040 HOST_WIDE_INT offset;
2042 /* First, is there anything related known?
2043 If we have a table element, we can tell from that.
2044 Otherwise, must look it up. */
2046 if (elt != 0 && elt->related_value != 0)
2048 else if (elt == 0 && GET_CODE (x) == CONST)
2050 rtx subexp = get_related_value (x);
2052 relt = lookup (subexp,
2053 safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
2060 /* Search all related table entries for one that has an
2061 equivalent register. */
2066 /* This loop is strange in that it is executed in two different cases.
2067 The first is when X is already in the table. Then it is searching
2068 the RELATED_VALUE list of X's class (RELT). The second case is when
2069 X is not in the table. Then RELT points to a class for the related
2072 Ensure that, whatever case we are in, that we ignore classes that have
2073 the same value as X. */
2075 if (rtx_equal_p (x, p->exp))
2078 for (q = p->first_same_value; q; q = q->next_same_value)
2079 if (GET_CODE (q->exp) == REG)
2085 p = p->related_value;
2087 /* We went all the way around, so there is nothing to be found.
2088 Alternatively, perhaps RELT was in the table for some other reason
2089 and it has no related values recorded. */
2090 if (p == relt || p == 0)
2097 offset = (get_integer_term (x) - get_integer_term (p->exp));
2098 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2099 return plus_constant (q->exp, offset);
2102 /* Hash an rtx. We are careful to make sure the value is never negative.
2103 Equivalent registers hash identically.
2104 MODE is used in hashing for CONST_INTs only;
2105 otherwise the mode of X is used.
2107 Store 1 in do_not_record if any subexpression is volatile.
2109 Store 1 in hash_arg_in_memory if X contains a MEM rtx
2110 which does not have the RTX_UNCHANGING_P bit set.
2112 Note that cse_insn knows that the hash code of a MEM expression
2113 is just (int) MEM plus the hash code of the address. */
2116 canon_hash (x, mode)
2118 enum machine_mode mode;
2121 register unsigned hash = 0;
2122 register enum rtx_code code;
2123 register const char *fmt;
2125 /* repeat is used to turn tail-recursion into iteration. */
2130 code = GET_CODE (x);
2135 register int regno = REGNO (x);
2137 /* On some machines, we can't record any non-fixed hard register,
2138 because extending its life will cause reload problems. We
2139 consider ap, fp, and sp to be fixed for this purpose.
2141 We also consider CCmode registers to be fixed for this purpose;
2142 failure to do so leads to failure to simplify 0<100 type of
2145 On all machines, we can't record any global registers. */
2147 if (regno < FIRST_PSEUDO_REGISTER
2148 && (global_regs[regno]
2149 || (SMALL_REGISTER_CLASSES
2150 && ! fixed_regs[regno]
2151 && regno != FRAME_POINTER_REGNUM
2152 && regno != HARD_FRAME_POINTER_REGNUM
2153 && regno != ARG_POINTER_REGNUM
2154 && regno != STACK_POINTER_REGNUM
2155 && GET_MODE_CLASS (GET_MODE (x)) != MODE_CC)))
2160 hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno);
2164 /* We handle SUBREG of a REG specially because the underlying
2165 reg changes its hash value with every value change; we don't
2166 want to have to forget unrelated subregs when one subreg changes. */
2169 if (GET_CODE (SUBREG_REG (x)) == REG)
2171 hash += (((unsigned) SUBREG << 7)
2172 + REGNO (SUBREG_REG (x)) + SUBREG_WORD (x));
2180 unsigned HOST_WIDE_INT tem = INTVAL (x);
2181 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
2186 /* This is like the general case, except that it only counts
2187 the integers representing the constant. */
2188 hash += (unsigned) code + (unsigned) GET_MODE (x);
2189 if (GET_MODE (x) != VOIDmode)
2190 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2192 unsigned HOST_WIDE_INT tem = XWINT (x, i);
2196 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2197 + (unsigned) CONST_DOUBLE_HIGH (x));
2200 /* Assume there is only one rtx object for any given label. */
2203 += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2208 += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2212 /* We don't record if marked volatile or if BLKmode since we don't
2213 know the size of the move. */
2214 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2219 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
2221 hash_arg_in_memory = 1;
2223 /* Now that we have already found this special case,
2224 might as well speed it up as much as possible. */
2225 hash += (unsigned) MEM;
2236 case UNSPEC_VOLATILE:
2241 if (MEM_VOLATILE_P (x))
2252 i = GET_RTX_LENGTH (code) - 1;
2253 hash += (unsigned) code + (unsigned) GET_MODE (x);
2254 fmt = GET_RTX_FORMAT (code);
2259 rtx tem = XEXP (x, i);
2261 /* If we are about to do the last recursive call
2262 needed at this level, change it into iteration.
2263 This function is called enough to be worth it. */
2269 hash += canon_hash (tem, 0);
2271 else if (fmt[i] == 'E')
2272 for (j = 0; j < XVECLEN (x, i); j++)
2273 hash += canon_hash (XVECEXP (x, i, j), 0);
2274 else if (fmt[i] == 's')
2276 register unsigned char *p = (unsigned char *) XSTR (x, i);
2281 else if (fmt[i] == 'i')
2283 register unsigned tem = XINT (x, i);
2286 else if (fmt[i] == '0' || fmt[i] == 't')
2294 /* Like canon_hash but with no side effects. */
2299 enum machine_mode mode;
2301 int save_do_not_record = do_not_record;
2302 int save_hash_arg_in_memory = hash_arg_in_memory;
2303 unsigned hash = canon_hash (x, mode);
2304 hash_arg_in_memory = save_hash_arg_in_memory;
2305 do_not_record = save_do_not_record;
2309 /* Return 1 iff X and Y would canonicalize into the same thing,
2310 without actually constructing the canonicalization of either one.
2311 If VALIDATE is nonzero,
2312 we assume X is an expression being processed from the rtl
2313 and Y was found in the hash table. We check register refs
2314 in Y for being marked as valid.
2316 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2317 that is known to be in the register. Ordinarily, we don't allow them
2318 to match, because letting them match would cause unpredictable results
2319 in all the places that search a hash table chain for an equivalent
2320 for a given value. A possible equivalent that has different structure
2321 has its hash code computed from different data. Whether the hash code
2322 is the same as that of the given value is pure luck. */
2325 exp_equiv_p (x, y, validate, equal_values)
2331 register enum rtx_code code;
2332 register const char *fmt;
2334 /* Note: it is incorrect to assume an expression is equivalent to itself
2335 if VALIDATE is nonzero. */
2336 if (x == y && !validate)
2338 if (x == 0 || y == 0)
2341 code = GET_CODE (x);
2342 if (code != GET_CODE (y))
2347 /* If X is a constant and Y is a register or vice versa, they may be
2348 equivalent. We only have to validate if Y is a register. */
2349 if (CONSTANT_P (x) && GET_CODE (y) == REG
2350 && REGNO_QTY_VALID_P (REGNO (y)))
2352 int y_q = REG_QTY (REGNO (y));
2353 struct qty_table_elem *y_ent = &qty_table[y_q];
2355 if (GET_MODE (y) == y_ent->mode
2356 && rtx_equal_p (x, y_ent->const_rtx)
2357 && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y))))
2361 if (CONSTANT_P (y) && code == REG
2362 && REGNO_QTY_VALID_P (REGNO (x)))
2364 int x_q = REG_QTY (REGNO (x));
2365 struct qty_table_elem *x_ent = &qty_table[x_q];
2367 if (GET_MODE (x) == x_ent->mode
2368 && rtx_equal_p (y, x_ent->const_rtx))
2375 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2376 if (GET_MODE (x) != GET_MODE (y))
2386 return INTVAL (x) == INTVAL (y);
2389 return XEXP (x, 0) == XEXP (y, 0);
2392 return XSTR (x, 0) == XSTR (y, 0);
2396 int regno = REGNO (y);
2398 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2399 : HARD_REGNO_NREGS (regno, GET_MODE (y)));
2402 /* If the quantities are not the same, the expressions are not
2403 equivalent. If there are and we are not to validate, they
2404 are equivalent. Otherwise, ensure all regs are up-to-date. */
2406 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2412 for (i = regno; i < endregno; i++)
2413 if (REG_IN_TABLE (i) != REG_TICK (i))
2419 /* For commutative operations, check both orders. */
2427 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
2428 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2429 validate, equal_values))
2430 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2431 validate, equal_values)
2432 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2433 validate, equal_values)));
2439 /* Compare the elements. If any pair of corresponding elements
2440 fail to match, return 0 for the whole things. */
2442 fmt = GET_RTX_FORMAT (code);
2443 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2448 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
2453 if (XVECLEN (x, i) != XVECLEN (y, i))
2455 for (j = 0; j < XVECLEN (x, i); j++)
2456 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2457 validate, equal_values))
2462 if (strcmp (XSTR (x, i), XSTR (y, i)))
2467 if (XINT (x, i) != XINT (y, i))
2472 if (XWINT (x, i) != XWINT (y, i))
2488 /* Return 1 if X has a value that can vary even between two
2489 executions of the program. 0 means X can be compared reliably
2490 against certain constants or near-constants. */
2493 cse_rtx_varies_p (x)
2496 /* We need not check for X and the equivalence class being of the same
2497 mode because if X is equivalent to a constant in some mode, it
2498 doesn't vary in any mode. */
2500 if (GET_CODE (x) == REG
2501 && REGNO_QTY_VALID_P (REGNO (x)))
2503 int x_q = REG_QTY (REGNO (x));
2504 struct qty_table_elem *x_ent = &qty_table[x_q];
2506 if (GET_MODE (x) == x_ent->mode
2507 && x_ent->const_rtx != NULL_RTX)
2511 if (GET_CODE (x) == PLUS
2512 && GET_CODE (XEXP (x, 1)) == CONST_INT
2513 && GET_CODE (XEXP (x, 0)) == REG
2514 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2516 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2517 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2519 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2520 && x0_ent->const_rtx != NULL_RTX)
2524 /* This can happen as the result of virtual register instantiation, if
2525 the initial constant is too large to be a valid address. This gives
2526 us a three instruction sequence, load large offset into a register,
2527 load fp minus a constant into a register, then a MEM which is the
2528 sum of the two `constant' registers. */
2529 if (GET_CODE (x) == PLUS
2530 && GET_CODE (XEXP (x, 0)) == REG
2531 && GET_CODE (XEXP (x, 1)) == REG
2532 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2533 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2535 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2536 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2537 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2538 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2540 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2541 && x0_ent->const_rtx != NULL_RTX
2542 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2543 && x1_ent->const_rtx != NULL_RTX)
2547 return rtx_varies_p (x);
2550 /* Canonicalize an expression:
2551 replace each register reference inside it
2552 with the "oldest" equivalent register.
2554 If INSN is non-zero and we are replacing a pseudo with a hard register
2555 or vice versa, validate_change is used to ensure that INSN remains valid
2556 after we make our substitution. The calls are made with IN_GROUP non-zero
2557 so apply_change_group must be called upon the outermost return from this
2558 function (unless INSN is zero). The result of apply_change_group can
2559 generally be discarded since the changes we are making are optional. */
2567 register enum rtx_code code;
2568 register const char *fmt;
2573 code = GET_CODE (x);
2591 register struct qty_table_elem *ent;
2593 /* Never replace a hard reg, because hard regs can appear
2594 in more than one machine mode, and we must preserve the mode
2595 of each occurrence. Also, some hard regs appear in
2596 MEMs that are shared and mustn't be altered. Don't try to
2597 replace any reg that maps to a reg of class NO_REGS. */
2598 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2599 || ! REGNO_QTY_VALID_P (REGNO (x)))
2602 q = REG_QTY (REGNO(x));
2603 ent = &qty_table[q];
2604 first = ent->first_reg;
2605 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2606 : REGNO_REG_CLASS (first) == NO_REGS ? x
2607 : gen_rtx_REG (ent->mode, first));
2614 fmt = GET_RTX_FORMAT (code);
2615 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2621 rtx new = canon_reg (XEXP (x, i), insn);
2624 /* If replacing pseudo with hard reg or vice versa, ensure the
2625 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2626 if (insn != 0 && new != 0
2627 && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
2628 && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2629 != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER))
2630 || (insn_code = recog_memoized (insn)) < 0
2631 || insn_data[insn_code].n_dups > 0))
2632 validate_change (insn, &XEXP (x, i), new, 1);
2636 else if (fmt[i] == 'E')
2637 for (j = 0; j < XVECLEN (x, i); j++)
2638 XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
2644 /* LOC is a location within INSN that is an operand address (the contents of
2645 a MEM). Find the best equivalent address to use that is valid for this
2648 On most CISC machines, complicated address modes are costly, and rtx_cost
2649 is a good approximation for that cost. However, most RISC machines have
2650 only a few (usually only one) memory reference formats. If an address is
2651 valid at all, it is often just as cheap as any other address. Hence, for
2652 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2653 costs of various addresses. For two addresses of equal cost, choose the one
2654 with the highest `rtx_cost' value as that has the potential of eliminating
2655 the most insns. For equal costs, we choose the first in the equivalence
2656 class. Note that we ignore the fact that pseudo registers are cheaper
2657 than hard registers here because we would also prefer the pseudo registers.
2661 find_best_addr (insn, loc)
2665 struct table_elt *elt;
2668 struct table_elt *p;
2669 int found_better = 1;
2671 int save_do_not_record = do_not_record;
2672 int save_hash_arg_in_memory = hash_arg_in_memory;
2677 /* Do not try to replace constant addresses or addresses of local and
2678 argument slots. These MEM expressions are made only once and inserted
2679 in many instructions, as well as being used to control symbol table
2680 output. It is not safe to clobber them.
2682 There are some uncommon cases where the address is already in a register
2683 for some reason, but we cannot take advantage of that because we have
2684 no easy way to unshare the MEM. In addition, looking up all stack
2685 addresses is costly. */
2686 if ((GET_CODE (addr) == PLUS
2687 && GET_CODE (XEXP (addr, 0)) == REG
2688 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2689 && (regno = REGNO (XEXP (addr, 0)),
2690 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2691 || regno == ARG_POINTER_REGNUM))
2692 || (GET_CODE (addr) == REG
2693 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2694 || regno == HARD_FRAME_POINTER_REGNUM
2695 || regno == ARG_POINTER_REGNUM))
2696 || GET_CODE (addr) == ADDRESSOF
2697 || CONSTANT_ADDRESS_P (addr))
2700 /* If this address is not simply a register, try to fold it. This will
2701 sometimes simplify the expression. Many simplifications
2702 will not be valid, but some, usually applying the associative rule, will
2703 be valid and produce better code. */
2704 if (GET_CODE (addr) != REG)
2706 rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX);
2710 && (CSE_ADDRESS_COST (folded) < CSE_ADDRESS_COST (addr)
2711 || (CSE_ADDRESS_COST (folded) == CSE_ADDRESS_COST (addr)
2712 && rtx_cost (folded, MEM) > rtx_cost (addr, MEM)))
2714 && rtx_cost (folded, MEM) < rtx_cost (addr, MEM)
2716 && validate_change (insn, loc, folded, 0))
2720 /* If this address is not in the hash table, we can't look for equivalences
2721 of the whole address. Also, ignore if volatile. */
2724 hash = HASH (addr, Pmode);
2725 addr_volatile = do_not_record;
2726 do_not_record = save_do_not_record;
2727 hash_arg_in_memory = save_hash_arg_in_memory;
2732 elt = lookup (addr, hash, Pmode);
2734 #ifndef ADDRESS_COST
2737 int our_cost = elt->cost;
2739 /* Find the lowest cost below ours that works. */
2740 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
2741 if (elt->cost < our_cost
2742 && (GET_CODE (elt->exp) == REG
2743 || exp_equiv_p (elt->exp, elt->exp, 1, 0))
2744 && validate_change (insn, loc,
2745 canon_reg (copy_rtx (elt->exp), NULL_RTX), 0))
2752 /* We need to find the best (under the criteria documented above) entry
2753 in the class that is valid. We use the `flag' field to indicate
2754 choices that were invalid and iterate until we can't find a better
2755 one that hasn't already been tried. */
2757 for (p = elt->first_same_value; p; p = p->next_same_value)
2760 while (found_better)
2762 int best_addr_cost = CSE_ADDRESS_COST (*loc);
2763 int best_rtx_cost = (elt->cost + 1) >> 1;
2764 struct table_elt *best_elt = elt;
2767 for (p = elt->first_same_value; p; p = p->next_same_value)
2770 if ((GET_CODE (p->exp) == REG
2771 || exp_equiv_p (p->exp, p->exp, 1, 0))
2772 && (CSE_ADDRESS_COST (p->exp) < best_addr_cost
2773 || (CSE_ADDRESS_COST (p->exp) == best_addr_cost
2774 && (p->cost + 1) >> 1 > best_rtx_cost)))
2777 best_addr_cost = CSE_ADDRESS_COST (p->exp);
2778 best_rtx_cost = (p->cost + 1) >> 1;
2785 if (validate_change (insn, loc,
2786 canon_reg (copy_rtx (best_elt->exp),
2795 /* If the address is a binary operation with the first operand a register
2796 and the second a constant, do the same as above, but looking for
2797 equivalences of the register. Then try to simplify before checking for
2798 the best address to use. This catches a few cases: First is when we
2799 have REG+const and the register is another REG+const. We can often merge
2800 the constants and eliminate one insn and one register. It may also be
2801 that a machine has a cheap REG+REG+const. Finally, this improves the
2802 code on the Alpha for unaligned byte stores. */
2804 if (flag_expensive_optimizations
2805 && (GET_RTX_CLASS (GET_CODE (*loc)) == '2'
2806 || GET_RTX_CLASS (GET_CODE (*loc)) == 'c')
2807 && GET_CODE (XEXP (*loc, 0)) == REG
2808 && GET_CODE (XEXP (*loc, 1)) == CONST_INT)
2810 rtx c = XEXP (*loc, 1);
2813 hash = HASH (XEXP (*loc, 0), Pmode);
2814 do_not_record = save_do_not_record;
2815 hash_arg_in_memory = save_hash_arg_in_memory;
2817 elt = lookup (XEXP (*loc, 0), hash, Pmode);
2821 /* We need to find the best (under the criteria documented above) entry
2822 in the class that is valid. We use the `flag' field to indicate
2823 choices that were invalid and iterate until we can't find a better
2824 one that hasn't already been tried. */
2826 for (p = elt->first_same_value; p; p = p->next_same_value)
2829 while (found_better)
2831 int best_addr_cost = CSE_ADDRESS_COST (*loc);
2832 int best_rtx_cost = (COST (*loc) + 1) >> 1;
2833 struct table_elt *best_elt = elt;
2834 rtx best_rtx = *loc;
2837 /* This is at worst case an O(n^2) algorithm, so limit our search
2838 to the first 32 elements on the list. This avoids trouble
2839 compiling code with very long basic blocks that can easily
2840 call simplify_gen_binary so many times that we run out of
2844 for (p = elt->first_same_value, count = 0;
2846 p = p->next_same_value, count++)
2848 && (GET_CODE (p->exp) == REG
2849 || exp_equiv_p (p->exp, p->exp, 1, 0)))
2851 rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
2854 if ((CSE_ADDRESS_COST (new) < best_addr_cost
2855 || (CSE_ADDRESS_COST (new) == best_addr_cost
2856 && (COST (new) + 1) >> 1 > best_rtx_cost)))
2859 best_addr_cost = CSE_ADDRESS_COST (new);
2860 best_rtx_cost = (COST (new) + 1) >> 1;
2868 if (validate_change (insn, loc,
2869 canon_reg (copy_rtx (best_rtx),
2880 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2881 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2882 what values are being compared.
2884 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2885 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2886 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2887 compared to produce cc0.
2889 The return value is the comparison operator and is either the code of
2890 A or the code corresponding to the inverse of the comparison. */
2892 static enum rtx_code
2893 find_comparison_args (code, parg1, parg2, pmode1, pmode2)
2896 enum machine_mode *pmode1, *pmode2;
2900 arg1 = *parg1, arg2 = *parg2;
2902 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2904 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2906 /* Set non-zero when we find something of interest. */
2908 int reverse_code = 0;
2909 struct table_elt *p = 0;
2911 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2912 On machines with CC0, this is the only case that can occur, since
2913 fold_rtx will return the COMPARE or item being compared with zero
2916 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2919 /* If ARG1 is a comparison operator and CODE is testing for
2920 STORE_FLAG_VALUE, get the inner arguments. */
2922 else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
2925 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2926 && code == LT && STORE_FLAG_VALUE == -1)
2927 #ifdef FLOAT_STORE_FLAG_VALUE
2928 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
2929 && FLOAT_STORE_FLAG_VALUE < 0)
2934 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2935 && code == GE && STORE_FLAG_VALUE == -1)
2936 #ifdef FLOAT_STORE_FLAG_VALUE
2937 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
2938 && FLOAT_STORE_FLAG_VALUE < 0)
2941 x = arg1, reverse_code = 1;
2944 /* ??? We could also check for
2946 (ne (and (eq (...) (const_int 1))) (const_int 0))
2948 and related forms, but let's wait until we see them occurring. */
2951 /* Look up ARG1 in the hash table and see if it has an equivalence
2952 that lets us see what is being compared. */
2953 p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) % NBUCKETS,
2955 if (p) p = p->first_same_value;
2957 for (; p; p = p->next_same_value)
2959 enum machine_mode inner_mode = GET_MODE (p->exp);
2961 /* If the entry isn't valid, skip it. */
2962 if (! exp_equiv_p (p->exp, p->exp, 1, 0))
2965 if (GET_CODE (p->exp) == COMPARE
2966 /* Another possibility is that this machine has a compare insn
2967 that includes the comparison code. In that case, ARG1 would
2968 be equivalent to a comparison operation that would set ARG1 to
2969 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2970 ORIG_CODE is the actual comparison being done; if it is an EQ,
2971 we must reverse ORIG_CODE. On machine with a negative value
2972 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2975 && GET_MODE_CLASS (inner_mode) == MODE_INT
2976 && (GET_MODE_BITSIZE (inner_mode)
2977 <= HOST_BITS_PER_WIDE_INT)
2978 && (STORE_FLAG_VALUE
2979 & ((HOST_WIDE_INT) 1
2980 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2981 #ifdef FLOAT_STORE_FLAG_VALUE
2983 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
2984 && FLOAT_STORE_FLAG_VALUE < 0)
2987 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
2992 else if ((code == EQ
2994 && GET_MODE_CLASS (inner_mode) == MODE_INT
2995 && (GET_MODE_BITSIZE (inner_mode)
2996 <= HOST_BITS_PER_WIDE_INT)
2997 && (STORE_FLAG_VALUE
2998 & ((HOST_WIDE_INT) 1
2999 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3000 #ifdef FLOAT_STORE_FLAG_VALUE
3002 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3003 && FLOAT_STORE_FLAG_VALUE < 0)
3006 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
3013 /* If this is fp + constant, the equivalent is a better operand since
3014 it may let us predict the value of the comparison. */
3015 else if (NONZERO_BASE_PLUS_P (p->exp))
3022 /* If we didn't find a useful equivalence for ARG1, we are done.
3023 Otherwise, set up for the next iteration. */
3027 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3028 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
3029 code = GET_CODE (x);
3032 code = reverse_condition (code);
3035 /* Return our results. Return the modes from before fold_rtx
3036 because fold_rtx might produce const_int, and then it's too late. */
3037 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3038 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3043 /* If X is a nontrivial arithmetic operation on an argument
3044 for which a constant value can be determined, return
3045 the result of operating on that value, as a constant.
3046 Otherwise, return X, possibly with one or more operands
3047 modified by recursive calls to this function.
3049 If X is a register whose contents are known, we do NOT
3050 return those contents here. equiv_constant is called to
3053 INSN is the insn that we may be modifying. If it is 0, make a copy
3054 of X before modifying it. */
3061 register enum rtx_code code;
3062 register enum machine_mode mode;
3063 register const char *fmt;
3069 /* Folded equivalents of first two operands of X. */
3073 /* Constant equivalents of first three operands of X;
3074 0 when no such equivalent is known. */
3079 /* The mode of the first operand of X. We need this for sign and zero
3081 enum machine_mode mode_arg0;
3086 mode = GET_MODE (x);
3087 code = GET_CODE (x);
3096 /* No use simplifying an EXPR_LIST
3097 since they are used only for lists of args
3098 in a function call's REG_EQUAL note. */
3100 /* Changing anything inside an ADDRESSOF is incorrect; we don't
3101 want to (e.g.,) make (addressof (const_int 0)) just because
3102 the location is known to be zero. */
3108 return prev_insn_cc0;
3112 /* If the next insn is a CODE_LABEL followed by a jump table,
3113 PC's value is a LABEL_REF pointing to that label. That
3114 lets us fold switch statements on the Vax. */
3115 if (insn && GET_CODE (insn) == JUMP_INSN)
3117 rtx next = next_nonnote_insn (insn);
3119 if (next && GET_CODE (next) == CODE_LABEL
3120 && NEXT_INSN (next) != 0
3121 && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
3122 && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
3123 || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
3124 return gen_rtx_LABEL_REF (Pmode, next);
3129 /* See if we previously assigned a constant value to this SUBREG. */
3130 if ((new = lookup_as_function (x, CONST_INT)) != 0
3131 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3134 /* If this is a paradoxical SUBREG, we have no idea what value the
3135 extra bits would have. However, if the operand is equivalent
3136 to a SUBREG whose operand is the same as our mode, and all the
3137 modes are within a word, we can just use the inner operand
3138 because these SUBREGs just say how to treat the register.
3140 Similarly if we find an integer constant. */
3142 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3144 enum machine_mode imode = GET_MODE (SUBREG_REG (x));
3145 struct table_elt *elt;
3147 if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
3148 && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
3149 && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
3151 for (elt = elt->first_same_value;
3152 elt; elt = elt->next_same_value)
3154 if (CONSTANT_P (elt->exp)
3155 && GET_MODE (elt->exp) == VOIDmode)
3158 if (GET_CODE (elt->exp) == SUBREG
3159 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3160 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3161 return copy_rtx (SUBREG_REG (elt->exp));
3167 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
3168 We might be able to if the SUBREG is extracting a single word in an
3169 integral mode or extracting the low part. */
3171 folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
3172 const_arg0 = equiv_constant (folded_arg0);
3174 folded_arg0 = const_arg0;
3176 if (folded_arg0 != SUBREG_REG (x))
3180 if (GET_MODE_CLASS (mode) == MODE_INT
3181 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3182 && GET_MODE (SUBREG_REG (x)) != VOIDmode)
3183 new = operand_subword (folded_arg0, SUBREG_WORD (x), 0,
3184 GET_MODE (SUBREG_REG (x)));
3185 if (new == 0 && subreg_lowpart_p (x))
3186 new = gen_lowpart_if_possible (mode, folded_arg0);
3191 /* If this is a narrowing SUBREG and our operand is a REG, see if
3192 we can find an equivalence for REG that is an arithmetic operation
3193 in a wider mode where both operands are paradoxical SUBREGs
3194 from objects of our result mode. In that case, we couldn't report
3195 an equivalent value for that operation, since we don't know what the
3196 extra bits will be. But we can find an equivalence for this SUBREG
3197 by folding that operation is the narrow mode. This allows us to
3198 fold arithmetic in narrow modes when the machine only supports
3199 word-sized arithmetic.
3201 Also look for a case where we have a SUBREG whose operand is the
3202 same as our result. If both modes are smaller than a word, we
3203 are simply interpreting a register in different modes and we
3204 can use the inner value. */
3206 if (GET_CODE (folded_arg0) == REG
3207 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0))
3208 && subreg_lowpart_p (x))
3210 struct table_elt *elt;
3212 /* We can use HASH here since we know that canon_hash won't be
3214 elt = lookup (folded_arg0,
3215 HASH (folded_arg0, GET_MODE (folded_arg0)),
3216 GET_MODE (folded_arg0));
3219 elt = elt->first_same_value;
3221 for (; elt; elt = elt->next_same_value)
3223 enum rtx_code eltcode = GET_CODE (elt->exp);
3225 /* Just check for unary and binary operations. */
3226 if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1'
3227 && GET_CODE (elt->exp) != SIGN_EXTEND
3228 && GET_CODE (elt->exp) != ZERO_EXTEND
3229 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3230 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode)
3232 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
3234 if (GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3235 op0 = fold_rtx (op0, NULL_RTX);
3237 op0 = equiv_constant (op0);
3239 new = simplify_unary_operation (GET_CODE (elt->exp), mode,
3242 else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2'
3243 || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c')
3244 && eltcode != DIV && eltcode != MOD
3245 && eltcode != UDIV && eltcode != UMOD
3246 && eltcode != ASHIFTRT && eltcode != LSHIFTRT
3247 && eltcode != ROTATE && eltcode != ROTATERT
3248 && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3249 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
3251 || CONSTANT_P (XEXP (elt->exp, 0)))
3252 && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
3253 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
3255 || CONSTANT_P (XEXP (elt->exp, 1))))
3257 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
3258 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
3260 if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3261 op0 = fold_rtx (op0, NULL_RTX);
3264 op0 = equiv_constant (op0);
3266 if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1))
3267 op1 = fold_rtx (op1, NULL_RTX);
3270 op1 = equiv_constant (op1);
3272 /* If we are looking for the low SImode part of
3273 (ashift:DI c (const_int 32)), it doesn't work
3274 to compute that in SImode, because a 32-bit shift
3275 in SImode is unpredictable. We know the value is 0. */
3277 && GET_CODE (elt->exp) == ASHIFT
3278 && GET_CODE (op1) == CONST_INT
3279 && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
3281 if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
3283 /* If the count fits in the inner mode's width,
3284 but exceeds the outer mode's width,
3285 the value will get truncated to 0
3289 /* If the count exceeds even the inner mode's width,
3290 don't fold this expression. */
3293 else if (op0 && op1)
3294 new = simplify_binary_operation (GET_CODE (elt->exp), mode,
3298 else if (GET_CODE (elt->exp) == SUBREG
3299 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3300 && (GET_MODE_SIZE (GET_MODE (folded_arg0))
3302 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3303 new = copy_rtx (SUBREG_REG (elt->exp));
3314 /* If we have (NOT Y), see if Y is known to be (NOT Z).
3315 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
3316 new = lookup_as_function (XEXP (x, 0), code);
3318 return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
3322 /* If we are not actually processing an insn, don't try to find the
3323 best address. Not only don't we care, but we could modify the
3324 MEM in an invalid way since we have no insn to validate against. */
3326 find_best_addr (insn, &XEXP (x, 0));
3329 /* Even if we don't fold in the insn itself,
3330 we can safely do so here, in hopes of getting a constant. */
3331 rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
3333 HOST_WIDE_INT offset = 0;
3335 if (GET_CODE (addr) == REG
3336 && REGNO_QTY_VALID_P (REGNO (addr)))
3338 int addr_q = REG_QTY (REGNO (addr));
3339 struct qty_table_elem *addr_ent = &qty_table[addr_q];
3341 if (GET_MODE (addr) == addr_ent->mode
3342 && addr_ent->const_rtx != NULL_RTX)
3343 addr = addr_ent->const_rtx;
3346 /* If address is constant, split it into a base and integer offset. */
3347 if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
3349 else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
3350 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
3352 base = XEXP (XEXP (addr, 0), 0);
3353 offset = INTVAL (XEXP (XEXP (addr, 0), 1));
3355 else if (GET_CODE (addr) == LO_SUM
3356 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
3357 base = XEXP (addr, 1);
3358 else if (GET_CODE (addr) == ADDRESSOF)
3359 return change_address (x, VOIDmode, addr);
3361 /* If this is a constant pool reference, we can fold it into its
3362 constant to allow better value tracking. */
3363 if (base && GET_CODE (base) == SYMBOL_REF
3364 && CONSTANT_POOL_ADDRESS_P (base))
3366 rtx constant = get_pool_constant (base);
3367 enum machine_mode const_mode = get_pool_mode (base);
3370 if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
3371 constant_pool_entries_cost = COST (constant);
3373 /* If we are loading the full constant, we have an equivalence. */
3374 if (offset == 0 && mode == const_mode)
3377 /* If this actually isn't a constant (weird!), we can't do
3378 anything. Otherwise, handle the two most common cases:
3379 extracting a word from a multi-word constant, and extracting
3380 the low-order bits. Other cases don't seem common enough to
3382 if (! CONSTANT_P (constant))
3385 if (GET_MODE_CLASS (mode) == MODE_INT
3386 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3387 && offset % UNITS_PER_WORD == 0
3388 && (new = operand_subword (constant,
3389 offset / UNITS_PER_WORD,
3390 0, const_mode)) != 0)
3393 if (((BYTES_BIG_ENDIAN
3394 && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
3395 || (! BYTES_BIG_ENDIAN && offset == 0))
3396 && (new = gen_lowpart_if_possible (mode, constant)) != 0)
3400 /* If this is a reference to a label at a known position in a jump
3401 table, we also know its value. */
3402 if (base && GET_CODE (base) == LABEL_REF)
3404 rtx label = XEXP (base, 0);
3405 rtx table_insn = NEXT_INSN (label);
3407 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3408 && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
3410 rtx table = PATTERN (table_insn);
3413 && (offset / GET_MODE_SIZE (GET_MODE (table))
3414 < XVECLEN (table, 0)))
3415 return XVECEXP (table, 0,
3416 offset / GET_MODE_SIZE (GET_MODE (table)));
3418 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3419 && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
3421 rtx table = PATTERN (table_insn);
3424 && (offset / GET_MODE_SIZE (GET_MODE (table))
3425 < XVECLEN (table, 1)))
3427 offset /= GET_MODE_SIZE (GET_MODE (table));
3428 new = gen_rtx_MINUS (Pmode, XVECEXP (table, 1, offset),
3431 if (GET_MODE (table) != Pmode)
3432 new = gen_rtx_TRUNCATE (GET_MODE (table), new);
3434 /* Indicate this is a constant. This isn't a
3435 valid form of CONST, but it will only be used
3436 to fold the next insns and then discarded, so
3439 Note this expression must be explicitly discarded,
3440 by cse_insn, else it may end up in a REG_EQUAL note
3441 and "escape" to cause problems elsewhere. */
3442 return gen_rtx_CONST (GET_MODE (new), new);
3451 for (i = XVECLEN (x, 3) - 1; i >= 0; i--)
3452 validate_change (insn, &XVECEXP (x, 3, i),
3453 fold_rtx (XVECEXP (x, 3, i), insn), 0);
3463 mode_arg0 = VOIDmode;
3465 /* Try folding our operands.
3466 Then see which ones have constant values known. */
3468 fmt = GET_RTX_FORMAT (code);
3469 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3472 rtx arg = XEXP (x, i);
3473 rtx folded_arg = arg, const_arg = 0;
3474 enum machine_mode mode_arg = GET_MODE (arg);
3475 rtx cheap_arg, expensive_arg;
3476 rtx replacements[2];
3479 /* Most arguments are cheap, so handle them specially. */
3480 switch (GET_CODE (arg))
3483 /* This is the same as calling equiv_constant; it is duplicated
3485 if (REGNO_QTY_VALID_P (REGNO (arg)))
3487 int arg_q = REG_QTY (REGNO (arg));
3488 struct qty_table_elem *arg_ent = &qty_table[arg_q];
3490 if (arg_ent->const_rtx != NULL_RTX
3491 && GET_CODE (arg_ent->const_rtx) != REG
3492 && GET_CODE (arg_ent->const_rtx) != PLUS)
3494 = gen_lowpart_if_possible (GET_MODE (arg),
3495 arg_ent->const_rtx);
3509 folded_arg = prev_insn_cc0;
3510 mode_arg = prev_insn_cc0_mode;
3511 const_arg = equiv_constant (folded_arg);
3516 folded_arg = fold_rtx (arg, insn);
3517 const_arg = equiv_constant (folded_arg);
3520 /* For the first three operands, see if the operand
3521 is constant or equivalent to a constant. */
3525 folded_arg0 = folded_arg;
3526 const_arg0 = const_arg;
3527 mode_arg0 = mode_arg;
3530 folded_arg1 = folded_arg;
3531 const_arg1 = const_arg;
3534 const_arg2 = const_arg;
3538 /* Pick the least expensive of the folded argument and an
3539 equivalent constant argument. */
3540 if (const_arg == 0 || const_arg == folded_arg
3541 || COST (const_arg) > COST (folded_arg))
3542 cheap_arg = folded_arg, expensive_arg = const_arg;
3544 cheap_arg = const_arg, expensive_arg = folded_arg;
3546 /* Try to replace the operand with the cheapest of the two
3547 possibilities. If it doesn't work and this is either of the first
3548 two operands of a commutative operation, try swapping them.
3549 If THAT fails, try the more expensive, provided it is cheaper
3550 than what is already there. */
3552 if (cheap_arg == XEXP (x, i))
3555 if (insn == 0 && ! copied)
3561 replacements[0] = cheap_arg, replacements[1] = expensive_arg;
3563 j < 2 && replacements[j]
3564 && COST (replacements[j]) < COST (XEXP (x, i));
3567 if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
3570 if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c')
3572 validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
3573 validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
3575 if (apply_change_group ())
3577 /* Swap them back to be invalid so that this loop can
3578 continue and flag them to be swapped back later. */
3581 tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
3593 /* Don't try to fold inside of a vector of expressions.
3594 Doing nothing is harmless. */
3598 /* If a commutative operation, place a constant integer as the second
3599 operand unless the first operand is also a constant integer. Otherwise,
3600 place any constant second unless the first operand is also a constant. */
3602 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3604 if (must_swap || (const_arg0
3606 || (GET_CODE (const_arg0) == CONST_INT
3607 && GET_CODE (const_arg1) != CONST_INT))))
3609 register rtx tem = XEXP (x, 0);
3611 if (insn == 0 && ! copied)
3617 validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
3618 validate_change (insn, &XEXP (x, 1), tem, 1);
3619 if (apply_change_group ())
3621 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3622 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3627 /* If X is an arithmetic operation, see if we can simplify it. */
3629 switch (GET_RTX_CLASS (code))
3635 /* We can't simplify extension ops unless we know the
3637 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3638 && mode_arg0 == VOIDmode)
3641 /* If we had a CONST, strip it off and put it back later if we
3643 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3644 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3646 new = simplify_unary_operation (code, mode,
3647 const_arg0 ? const_arg0 : folded_arg0,
3649 if (new != 0 && is_const)
3650 new = gen_rtx_CONST (mode, new);
3655 /* See what items are actually being compared and set FOLDED_ARG[01]
3656 to those values and CODE to the actual comparison code. If any are
3657 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3658 do anything if both operands are already known to be constant. */
3660 if (const_arg0 == 0 || const_arg1 == 0)
3662 struct table_elt *p0, *p1;
3663 rtx true = const_true_rtx, false = const0_rtx;
3664 enum machine_mode mode_arg1;
3666 #ifdef FLOAT_STORE_FLAG_VALUE
3667 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3669 true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE,
3671 false = CONST0_RTX (mode);
3675 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3676 &mode_arg0, &mode_arg1);
3677 const_arg0 = equiv_constant (folded_arg0);
3678 const_arg1 = equiv_constant (folded_arg1);
3680 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3681 what kinds of things are being compared, so we can't do
3682 anything with this comparison. */
3684 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3687 /* If we do not now have two constants being compared, see
3688 if we can nevertheless deduce some things about the
3690 if (const_arg0 == 0 || const_arg1 == 0)
3692 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or
3693 non-explicit constant? These aren't zero, but we
3694 don't know their sign. */
3695 if (const_arg1 == const0_rtx
3696 && (NONZERO_BASE_PLUS_P (folded_arg0)
3697 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
3699 || GET_CODE (folded_arg0) == SYMBOL_REF
3701 || GET_CODE (folded_arg0) == LABEL_REF
3702 || GET_CODE (folded_arg0) == CONST))
3706 else if (code == NE)
3710 /* See if the two operands are the same. We don't do this
3711 for IEEE floating-point since we can't assume x == x
3712 since x might be a NaN. */
3714 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3715 || ! FLOAT_MODE_P (mode_arg0) || flag_fast_math)
3716 && (folded_arg0 == folded_arg1
3717 || (GET_CODE (folded_arg0) == REG
3718 && GET_CODE (folded_arg1) == REG
3719 && (REG_QTY (REGNO (folded_arg0))
3720 == REG_QTY (REGNO (folded_arg1))))
3721 || ((p0 = lookup (folded_arg0,
3722 (safe_hash (folded_arg0, mode_arg0)
3723 % NBUCKETS), mode_arg0))
3724 && (p1 = lookup (folded_arg1,
3725 (safe_hash (folded_arg1, mode_arg0)
3726 % NBUCKETS), mode_arg0))
3727 && p0->first_same_value == p1->first_same_value)))
3728 return ((code == EQ || code == LE || code == GE
3729 || code == LEU || code == GEU)
3732 /* If FOLDED_ARG0 is a register, see if the comparison we are
3733 doing now is either the same as we did before or the reverse
3734 (we only check the reverse if not floating-point). */
3735 else if (GET_CODE (folded_arg0) == REG)
3737 int qty = REG_QTY (REGNO (folded_arg0));
3739 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3741 struct qty_table_elem *ent = &qty_table[qty];
3743 if ((comparison_dominates_p (ent->comparison_code, code)
3744 || (comparison_dominates_p (ent->comparison_code,
3745 reverse_condition (code))
3746 && ! FLOAT_MODE_P (mode_arg0)))
3747 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3749 && rtx_equal_p (ent->comparison_const,
3751 || (GET_CODE (folded_arg1) == REG
3752 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3753 return (comparison_dominates_p (ent->comparison_code, code)
3760 /* If we are comparing against zero, see if the first operand is
3761 equivalent to an IOR with a constant. If so, we may be able to
3762 determine the result of this comparison. */
3764 if (const_arg1 == const0_rtx)
3766 rtx y = lookup_as_function (folded_arg0, IOR);
3770 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3771 && GET_CODE (inner_const) == CONST_INT
3772 && INTVAL (inner_const) != 0)
3774 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
3775 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
3776 && (INTVAL (inner_const)
3777 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
3778 rtx true = const_true_rtx, false = const0_rtx;
3780 #ifdef FLOAT_STORE_FLAG_VALUE
3781 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3783 true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE,
3785 false = CONST0_RTX (mode);
3809 new = simplify_relational_operation (code, mode_arg0,
3810 const_arg0 ? const_arg0 : folded_arg0,
3811 const_arg1 ? const_arg1 : folded_arg1);
3812 #ifdef FLOAT_STORE_FLAG_VALUE
3813 if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT)
3814 new = ((new == const0_rtx) ? CONST0_RTX (mode)
3815 : CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE, mode));
3824 /* If the second operand is a LABEL_REF, see if the first is a MINUS
3825 with that LABEL_REF as its second operand. If so, the result is
3826 the first operand of that MINUS. This handles switches with an
3827 ADDR_DIFF_VEC table. */
3828 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
3831 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
3832 : lookup_as_function (folded_arg0, MINUS);
3834 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3835 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
3838 /* Now try for a CONST of a MINUS like the above. */
3839 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
3840 : lookup_as_function (folded_arg0, CONST))) != 0
3841 && GET_CODE (XEXP (y, 0)) == MINUS
3842 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3843 && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg1, 0))
3844 return XEXP (XEXP (y, 0), 0);
3847 /* Likewise if the operands are in the other order. */
3848 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
3851 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
3852 : lookup_as_function (folded_arg1, MINUS);
3854 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
3855 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
3858 /* Now try for a CONST of a MINUS like the above. */
3859 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
3860 : lookup_as_function (folded_arg1, CONST))) != 0
3861 && GET_CODE (XEXP (y, 0)) == MINUS
3862 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
3863 && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg0, 0))
3864 return XEXP (XEXP (y, 0), 0);
3867 /* If second operand is a register equivalent to a negative
3868 CONST_INT, see if we can find a register equivalent to the
3869 positive constant. Make a MINUS if so. Don't do this for
3870 a non-negative constant since we might then alternate between
3871 chosing positive and negative constants. Having the positive
3872 constant previously-used is the more common case. Be sure
3873 the resulting constant is non-negative; if const_arg1 were
3874 the smallest negative number this would overflow: depending
3875 on the mode, this would either just be the same value (and
3876 hence not save anything) or be incorrect. */
3877 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
3878 && INTVAL (const_arg1) < 0
3879 /* This used to test
3881 - INTVAL (const_arg1) >= 0
3883 But The Sun V5.0 compilers mis-compiled that test. So
3884 instead we test for the problematic value in a more direct
3885 manner and hope the Sun compilers get it correct. */
3886 && INTVAL (const_arg1) !=
3887 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
3888 && GET_CODE (folded_arg1) == REG)
3890 rtx new_const = GEN_INT (- INTVAL (const_arg1));
3892 = lookup (new_const, safe_hash (new_const, mode) % NBUCKETS,
3896 for (p = p->first_same_value; p; p = p->next_same_value)
3897 if (GET_CODE (p->exp) == REG)
3898 return simplify_gen_binary (MINUS, mode, folded_arg0,
3899 canon_reg (p->exp, NULL_RTX));
3904 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3905 If so, produce (PLUS Z C2-C). */
3906 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
3908 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
3909 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
3910 return fold_rtx (plus_constant (copy_rtx (y),
3911 -INTVAL (const_arg1)),
3915 /* ... fall through ... */
3918 case SMIN: case SMAX: case UMIN: case UMAX:
3919 case IOR: case AND: case XOR:
3920 case MULT: case DIV: case UDIV:
3921 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
3922 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3923 is known to be of similar form, we may be able to replace the
3924 operation with a combined operation. This may eliminate the
3925 intermediate operation if every use is simplified in this way.
3926 Note that the similar optimization done by combine.c only works
3927 if the intermediate operation's result has only one reference. */
3929 if (GET_CODE (folded_arg0) == REG
3930 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
3933 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
3934 rtx y = lookup_as_function (folded_arg0, code);
3936 enum rtx_code associate_code;
3940 || 0 == (inner_const
3941 = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
3942 || GET_CODE (inner_const) != CONST_INT
3943 /* If we have compiled a statement like
3944 "if (x == (x & mask1))", and now are looking at
3945 "x & mask2", we will have a case where the first operand
3946 of Y is the same as our first operand. Unless we detect
3947 this case, an infinite loop will result. */
3948 || XEXP (y, 0) == folded_arg0)
3951 /* Don't associate these operations if they are a PLUS with the
3952 same constant and it is a power of two. These might be doable
3953 with a pre- or post-increment. Similarly for two subtracts of
3954 identical powers of two with post decrement. */
3956 if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
3957 && ((HAVE_PRE_INCREMENT
3958 && exact_log2 (INTVAL (const_arg1)) >= 0)
3959 || (HAVE_POST_INCREMENT
3960 && exact_log2 (INTVAL (const_arg1)) >= 0)
3961 || (HAVE_PRE_DECREMENT
3962 && exact_log2 (- INTVAL (const_arg1)) >= 0)
3963 || (HAVE_POST_DECREMENT
3964 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
3967 /* Compute the code used to compose the constants. For example,
3968 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
3971 = (code == MULT || code == DIV || code == UDIV ? MULT
3972 : is_shift || code == PLUS || code == MINUS ? PLUS : code);
3974 new_const = simplify_binary_operation (associate_code, mode,
3975 const_arg1, inner_const);
3980 /* If we are associating shift operations, don't let this
3981 produce a shift of the size of the object or larger.
3982 This could occur when we follow a sign-extend by a right
3983 shift on a machine that does a sign-extend as a pair
3986 if (is_shift && GET_CODE (new_const) == CONST_INT
3987 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
3989 /* As an exception, we can turn an ASHIFTRT of this
3990 form into a shift of the number of bits - 1. */
3991 if (code == ASHIFTRT)
3992 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
3997 y = copy_rtx (XEXP (y, 0));
3999 /* If Y contains our first operand (the most common way this
4000 can happen is if Y is a MEM), we would do into an infinite
4001 loop if we tried to fold it. So don't in that case. */
4003 if (! reg_mentioned_p (folded_arg0, y))
4004 y = fold_rtx (y, insn);
4006 return simplify_gen_binary (code, mode, y, new_const);
4014 new = simplify_binary_operation (code, mode,
4015 const_arg0 ? const_arg0 : folded_arg0,
4016 const_arg1 ? const_arg1 : folded_arg1);
4020 /* (lo_sum (high X) X) is simply X. */
4021 if (code == LO_SUM && const_arg0 != 0
4022 && GET_CODE (const_arg0) == HIGH
4023 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
4029 new = simplify_ternary_operation (code, mode, mode_arg0,
4030 const_arg0 ? const_arg0 : folded_arg0,
4031 const_arg1 ? const_arg1 : folded_arg1,
4032 const_arg2 ? const_arg2 : XEXP (x, 2));
4036 /* Always eliminate CONSTANT_P_RTX at this stage. */
4037 if (code == CONSTANT_P_RTX)
4038 return (const_arg0 ? const1_rtx : const0_rtx);
4042 return new ? new : x;
4045 /* Return a constant value currently equivalent to X.
4046 Return 0 if we don't know one. */
4052 if (GET_CODE (x) == REG
4053 && REGNO_QTY_VALID_P (REGNO (x)))
4055 int x_q = REG_QTY (REGNO (x));
4056 struct qty_table_elem *x_ent = &qty_table[x_q];
4058 if (x_ent->const_rtx)
4059 x = gen_lowpart_if_possible (GET_MODE (x), x_ent->const_rtx);
4062 if (x == 0 || CONSTANT_P (x))
4065 /* If X is a MEM, try to fold it outside the context of any insn to see if
4066 it might be equivalent to a constant. That handles the case where it
4067 is a constant-pool reference. Then try to look it up in the hash table
4068 in case it is something whose value we have seen before. */
4070 if (GET_CODE (x) == MEM)
4072 struct table_elt *elt;
4074 x = fold_rtx (x, NULL_RTX);
4078 elt = lookup (x, safe_hash (x, GET_MODE (x)) % NBUCKETS, GET_MODE (x));
4082 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
4083 if (elt->is_const && CONSTANT_P (elt->exp))
4090 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4091 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4092 least-significant part of X.
4093 MODE specifies how big a part of X to return.
4095 If the requested operation cannot be done, 0 is returned.
4097 This is similar to gen_lowpart in emit-rtl.c. */
4100 gen_lowpart_if_possible (mode, x)
4101 enum machine_mode mode;
4104 rtx result = gen_lowpart_common (mode, x);
4108 else if (GET_CODE (x) == MEM)
4110 /* This is the only other case we handle. */
4111 register int offset = 0;
4114 if (WORDS_BIG_ENDIAN)
4115 offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
4116 - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
4117 if (BYTES_BIG_ENDIAN)
4118 /* Adjust the address so that the address-after-the-data is
4120 offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode))
4121 - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
4122 new = gen_rtx_MEM (mode, plus_constant (XEXP (x, 0), offset));
4123 if (! memory_address_p (mode, XEXP (new, 0)))
4125 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
4126 MEM_COPY_ATTRIBUTES (new, x);
4133 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4134 branch. It will be zero if not.
4136 In certain cases, this can cause us to add an equivalence. For example,
4137 if we are following the taken case of
4139 we can add the fact that `i' and '2' are now equivalent.
4141 In any case, we can record that this comparison was passed. If the same
4142 comparison is seen later, we will know its value. */
4145 record_jump_equiv (insn, taken)
4149 int cond_known_true;
4151 enum machine_mode mode, mode0, mode1;
4152 int reversed_nonequality = 0;
4155 /* Ensure this is the right kind of insn. */
4156 if (! condjump_p (insn) || simplejump_p (insn))
4159 /* See if this jump condition is known true or false. */
4161 cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx);
4163 cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx);
4165 /* Get the type of comparison being done and the operands being compared.
4166 If we had to reverse a non-equality condition, record that fact so we
4167 know that it isn't valid for floating-point. */
4168 code = GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0));
4169 op0 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0), insn);
4170 op1 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 1), insn);
4172 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
4173 if (! cond_known_true)
4175 reversed_nonequality = (code != EQ && code != NE);
4176 code = reverse_condition (code);
4179 /* The mode is the mode of the non-constant. */
4181 if (mode1 != VOIDmode)
4184 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
4187 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
4188 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
4189 Make any useful entries we can with that information. Called from
4190 above function and called recursively. */
4193 record_jump_cond (code, mode, op0, op1, reversed_nonequality)
4195 enum machine_mode mode;
4197 int reversed_nonequality;
4199 unsigned op0_hash, op1_hash;
4200 int op0_in_memory, op1_in_memory;
4201 struct table_elt *op0_elt, *op1_elt;
4203 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
4204 we know that they are also equal in the smaller mode (this is also
4205 true for all smaller modes whether or not there is a SUBREG, but
4206 is not worth testing for with no SUBREG). */
4208 /* Note that GET_MODE (op0) may not equal MODE. */
4209 if (code == EQ && GET_CODE (op0) == SUBREG
4210 && (GET_MODE_SIZE (GET_MODE (op0))
4211 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4213 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4214 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4216 record_jump_cond (code, mode, SUBREG_REG (op0),
4217 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4218 reversed_nonequality);
4221 if (code == EQ && GET_CODE (op1) == SUBREG
4222 && (GET_MODE_SIZE (GET_MODE (op1))
4223 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4225 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4226 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4228 record_jump_cond (code, mode, SUBREG_REG (op1),
4229 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4230 reversed_nonequality);
4233 /* Similarly, if this is an NE comparison, and either is a SUBREG
4234 making a smaller mode, we know the whole thing is also NE. */
4236 /* Note that GET_MODE (op0) may not equal MODE;
4237 if we test MODE instead, we can get an infinite recursion
4238 alternating between two modes each wider than MODE. */
4240 if (code == NE && GET_CODE (op0) == SUBREG
4241 && subreg_lowpart_p (op0)
4242 && (GET_MODE_SIZE (GET_MODE (op0))
4243 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4245 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4246 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4248 record_jump_cond (code, mode, SUBREG_REG (op0),
4249 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4250 reversed_nonequality);
4253 if (code == NE && GET_CODE (op1) == SUBREG
4254 && subreg_lowpart_p (op1)
4255 && (GET_MODE_SIZE (GET_MODE (op1))
4256 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4258 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4259 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4261 record_jump_cond (code, mode, SUBREG_REG (op1),
4262 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4263 reversed_nonequality);
4266 /* Hash both operands. */
4269 hash_arg_in_memory = 0;
4270 op0_hash = HASH (op0, mode);
4271 op0_in_memory = hash_arg_in_memory;
4277 hash_arg_in_memory = 0;
4278 op1_hash = HASH (op1, mode);
4279 op1_in_memory = hash_arg_in_memory;
4284 /* Look up both operands. */
4285 op0_elt = lookup (op0, op0_hash, mode);
4286 op1_elt = lookup (op1, op1_hash, mode);
4288 /* If both operands are already equivalent or if they are not in the
4289 table but are identical, do nothing. */
4290 if ((op0_elt != 0 && op1_elt != 0
4291 && op0_elt->first_same_value == op1_elt->first_same_value)
4292 || op0 == op1 || rtx_equal_p (op0, op1))
4295 /* If we aren't setting two things equal all we can do is save this
4296 comparison. Similarly if this is floating-point. In the latter
4297 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4298 If we record the equality, we might inadvertently delete code
4299 whose intent was to change -0 to +0. */
4301 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
4303 struct qty_table_elem *ent;
4306 /* If we reversed a floating-point comparison, if OP0 is not a
4307 register, or if OP1 is neither a register or constant, we can't
4310 if (GET_CODE (op1) != REG)
4311 op1 = equiv_constant (op1);
4313 if ((reversed_nonequality && FLOAT_MODE_P (mode))
4314 || GET_CODE (op0) != REG || op1 == 0)
4317 /* Put OP0 in the hash table if it isn't already. This gives it a
4318 new quantity number. */
4321 if (insert_regs (op0, NULL_PTR, 0))
4323 rehash_using_reg (op0);
4324 op0_hash = HASH (op0, mode);
4326 /* If OP0 is contained in OP1, this changes its hash code
4327 as well. Faster to rehash than to check, except
4328 for the simple case of a constant. */
4329 if (! CONSTANT_P (op1))
4330 op1_hash = HASH (op1,mode);
4333 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
4334 op0_elt->in_memory = op0_in_memory;
4337 qty = REG_QTY (REGNO (op0));
4338 ent = &qty_table[qty];
4340 ent->comparison_code = code;
4341 if (GET_CODE (op1) == REG)
4343 /* Look it up again--in case op0 and op1 are the same. */
4344 op1_elt = lookup (op1, op1_hash, mode);
4346 /* Put OP1 in the hash table so it gets a new quantity number. */
4349 if (insert_regs (op1, NULL_PTR, 0))
4351 rehash_using_reg (op1);
4352 op1_hash = HASH (op1, mode);
4355 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
4356 op1_elt->in_memory = op1_in_memory;
4359 ent->comparison_const = NULL_RTX;
4360 ent->comparison_qty = REG_QTY (REGNO (op1));
4364 ent->comparison_const = op1;
4365 ent->comparison_qty = -1;
4371 /* If either side is still missing an equivalence, make it now,
4372 then merge the equivalences. */
4376 if (insert_regs (op0, NULL_PTR, 0))
4378 rehash_using_reg (op0);
4379 op0_hash = HASH (op0, mode);
4382 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
4383 op0_elt->in_memory = op0_in_memory;
4388 if (insert_regs (op1, NULL_PTR, 0))
4390 rehash_using_reg (op1);
4391 op1_hash = HASH (op1, mode);
4394 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
4395 op1_elt->in_memory = op1_in_memory;
4398 merge_equiv_classes (op0_elt, op1_elt);
4399 last_jump_equiv_class = op0_elt;
4402 /* CSE processing for one instruction.
4403 First simplify sources and addresses of all assignments
4404 in the instruction, using previously-computed equivalents values.
4405 Then install the new sources and destinations in the table
4406 of available values.
4408 If LIBCALL_INSN is nonzero, don't record any equivalence made in
4409 the insn. It means that INSN is inside libcall block. In this
4410 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
4412 /* Data on one SET contained in the instruction. */
4416 /* The SET rtx itself. */
4418 /* The SET_SRC of the rtx (the original value, if it is changing). */
4420 /* The hash-table element for the SET_SRC of the SET. */
4421 struct table_elt *src_elt;
4422 /* Hash value for the SET_SRC. */
4424 /* Hash value for the SET_DEST. */
4426 /* The SET_DEST, with SUBREG, etc., stripped. */
4428 /* Nonzero if the SET_SRC is in memory. */
4430 /* Nonzero if the SET_SRC contains something
4431 whose value cannot be predicted and understood. */
4433 /* Original machine mode, in case it becomes a CONST_INT. */
4434 enum machine_mode mode;
4435 /* A constant equivalent for SET_SRC, if any. */
4437 /* Hash value of constant equivalent for SET_SRC. */
4438 unsigned src_const_hash;
4439 /* Table entry for constant equivalent for SET_SRC, if any. */
4440 struct table_elt *src_const_elt;
4444 cse_insn (insn, libcall_insn)
4448 register rtx x = PATTERN (insn);
4451 register int n_sets = 0;
4454 /* Records what this insn does to set CC0. */
4455 rtx this_insn_cc0 = 0;
4456 enum machine_mode this_insn_cc0_mode = VOIDmode;
4460 struct table_elt *src_eqv_elt = 0;
4461 int src_eqv_volatile = 0;
4462 int src_eqv_in_memory = 0;
4463 unsigned src_eqv_hash = 0;
4465 struct set *sets = NULL_PTR;
4469 /* Find all the SETs and CLOBBERs in this instruction.
4470 Record all the SETs in the array `set' and count them.
4471 Also determine whether there is a CLOBBER that invalidates
4472 all memory references, or all references at varying addresses. */
4474 if (GET_CODE (insn) == CALL_INSN)
4476 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4477 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4478 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4481 if (GET_CODE (x) == SET)
4483 sets = (struct set *) alloca (sizeof (struct set));
4486 /* Ignore SETs that are unconditional jumps.
4487 They never need cse processing, so this does not hurt.
4488 The reason is not efficiency but rather
4489 so that we can test at the end for instructions
4490 that have been simplified to unconditional jumps
4491 and not be misled by unchanged instructions
4492 that were unconditional jumps to begin with. */
4493 if (SET_DEST (x) == pc_rtx
4494 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4497 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4498 The hard function value register is used only once, to copy to
4499 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4500 Ensure we invalidate the destination register. On the 80386 no
4501 other code would invalidate it since it is a fixed_reg.
4502 We need not check the return of apply_change_group; see canon_reg. */
4504 else if (GET_CODE (SET_SRC (x)) == CALL)
4506 canon_reg (SET_SRC (x), insn);
4507 apply_change_group ();
4508 fold_rtx (SET_SRC (x), insn);
4509 invalidate (SET_DEST (x), VOIDmode);
4514 else if (GET_CODE (x) == PARALLEL)
4516 register int lim = XVECLEN (x, 0);
4518 sets = (struct set *) alloca (lim * sizeof (struct set));
4520 /* Find all regs explicitly clobbered in this insn,
4521 and ensure they are not replaced with any other regs
4522 elsewhere in this insn.
4523 When a reg that is clobbered is also used for input,
4524 we should presume that that is for a reason,
4525 and we should not substitute some other register
4526 which is not supposed to be clobbered.
4527 Therefore, this loop cannot be merged into the one below
4528 because a CALL may precede a CLOBBER and refer to the
4529 value clobbered. We must not let a canonicalization do
4530 anything in that case. */
4531 for (i = 0; i < lim; i++)
4533 register rtx y = XVECEXP (x, 0, i);
4534 if (GET_CODE (y) == CLOBBER)
4536 rtx clobbered = XEXP (y, 0);
4538 if (GET_CODE (clobbered) == REG
4539 || GET_CODE (clobbered) == SUBREG)
4540 invalidate (clobbered, VOIDmode);
4541 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4542 || GET_CODE (clobbered) == ZERO_EXTRACT)
4543 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4547 for (i = 0; i < lim; i++)
4549 register rtx y = XVECEXP (x, 0, i);
4550 if (GET_CODE (y) == SET)
4552 /* As above, we ignore unconditional jumps and call-insns and
4553 ignore the result of apply_change_group. */
4554 if (GET_CODE (SET_SRC (y)) == CALL)
4556 canon_reg (SET_SRC (y), insn);
4557 apply_change_group ();
4558 fold_rtx (SET_SRC (y), insn);
4559 invalidate (SET_DEST (y), VOIDmode);
4561 else if (SET_DEST (y) == pc_rtx
4562 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4565 sets[n_sets++].rtl = y;
4567 else if (GET_CODE (y) == CLOBBER)
4569 /* If we clobber memory, canon the address.
4570 This does nothing when a register is clobbered
4571 because we have already invalidated the reg. */
4572 if (GET_CODE (XEXP (y, 0)) == MEM)
4573 canon_reg (XEXP (y, 0), NULL_RTX);
4575 else if (GET_CODE (y) == USE
4576 && ! (GET_CODE (XEXP (y, 0)) == REG
4577 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4578 canon_reg (y, NULL_RTX);
4579 else if (GET_CODE (y) == CALL)
4581 /* The result of apply_change_group can be ignored; see
4583 canon_reg (y, insn);
4584 apply_change_group ();
4589 else if (GET_CODE (x) == CLOBBER)
4591 if (GET_CODE (XEXP (x, 0)) == MEM)
4592 canon_reg (XEXP (x, 0), NULL_RTX);
4595 /* Canonicalize a USE of a pseudo register or memory location. */
4596 else if (GET_CODE (x) == USE
4597 && ! (GET_CODE (XEXP (x, 0)) == REG
4598 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4599 canon_reg (XEXP (x, 0), NULL_RTX);
4600 else if (GET_CODE (x) == CALL)
4602 /* The result of apply_change_group can be ignored; see canon_reg. */
4603 canon_reg (x, insn);
4604 apply_change_group ();
4608 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4609 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4610 is handled specially for this case, and if it isn't set, then there will
4611 be no equivalence for the destination. */
4612 if (n_sets == 1 && REG_NOTES (insn) != 0
4613 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4614 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4615 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4616 src_eqv = canon_reg (XEXP (tem, 0), NULL_RTX);
4618 /* Canonicalize sources and addresses of destinations.
4619 We do this in a separate pass to avoid problems when a MATCH_DUP is
4620 present in the insn pattern. In that case, we want to ensure that
4621 we don't break the duplicate nature of the pattern. So we will replace
4622 both operands at the same time. Otherwise, we would fail to find an
4623 equivalent substitution in the loop calling validate_change below.
4625 We used to suppress canonicalization of DEST if it appears in SRC,
4626 but we don't do this any more. */
4628 for (i = 0; i < n_sets; i++)
4630 rtx dest = SET_DEST (sets[i].rtl);
4631 rtx src = SET_SRC (sets[i].rtl);
4632 rtx new = canon_reg (src, insn);
4635 if ((GET_CODE (new) == REG && GET_CODE (src) == REG
4636 && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
4637 != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
4638 || (insn_code = recog_memoized (insn)) < 0
4639 || insn_data[insn_code].n_dups > 0)
4640 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4642 SET_SRC (sets[i].rtl) = new;
4644 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4646 validate_change (insn, &XEXP (dest, 1),
4647 canon_reg (XEXP (dest, 1), insn), 1);
4648 validate_change (insn, &XEXP (dest, 2),
4649 canon_reg (XEXP (dest, 2), insn), 1);
4652 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
4653 || GET_CODE (dest) == ZERO_EXTRACT
4654 || GET_CODE (dest) == SIGN_EXTRACT)
4655 dest = XEXP (dest, 0);
4657 if (GET_CODE (dest) == MEM)
4658 canon_reg (dest, insn);
4661 /* Now that we have done all the replacements, we can apply the change
4662 group and see if they all work. Note that this will cause some
4663 canonicalizations that would have worked individually not to be applied
4664 because some other canonicalization didn't work, but this should not
4667 The result of apply_change_group can be ignored; see canon_reg. */
4669 apply_change_group ();
4671 /* Set sets[i].src_elt to the class each source belongs to.
4672 Detect assignments from or to volatile things
4673 and set set[i] to zero so they will be ignored
4674 in the rest of this function.
4676 Nothing in this loop changes the hash table or the register chains. */
4678 for (i = 0; i < n_sets; i++)
4680 register rtx src, dest;
4681 register rtx src_folded;
4682 register struct table_elt *elt = 0, *p;
4683 enum machine_mode mode;
4686 rtx src_related = 0;
4687 struct table_elt *src_const_elt = 0;
4688 int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000;
4689 int src_related_cost = 10000, src_elt_cost = 10000;
4690 /* Set non-zero if we need to call force_const_mem on with the
4691 contents of src_folded before using it. */
4692 int src_folded_force_flag = 0;
4694 dest = SET_DEST (sets[i].rtl);
4695 src = SET_SRC (sets[i].rtl);
4697 /* If SRC is a constant that has no machine mode,
4698 hash it with the destination's machine mode.
4699 This way we can keep different modes separate. */
4701 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4702 sets[i].mode = mode;
4706 enum machine_mode eqvmode = mode;
4707 if (GET_CODE (dest) == STRICT_LOW_PART)
4708 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4710 hash_arg_in_memory = 0;
4711 src_eqv = fold_rtx (src_eqv, insn);
4712 src_eqv_hash = HASH (src_eqv, eqvmode);
4714 /* Find the equivalence class for the equivalent expression. */
4717 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4719 src_eqv_volatile = do_not_record;
4720 src_eqv_in_memory = hash_arg_in_memory;
4723 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4724 value of the INNER register, not the destination. So it is not
4725 a valid substitution for the source. But save it for later. */
4726 if (GET_CODE (dest) == STRICT_LOW_PART)
4729 src_eqv_here = src_eqv;
4731 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4732 simplified result, which may not necessarily be valid. */
4733 src_folded = fold_rtx (src, insn);
4736 /* ??? This caused bad code to be generated for the m68k port with -O2.
4737 Suppose src is (CONST_INT -1), and that after truncation src_folded
4738 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4739 At the end we will add src and src_const to the same equivalence
4740 class. We now have 3 and -1 on the same equivalence class. This
4741 causes later instructions to be mis-optimized. */
4742 /* If storing a constant in a bitfield, pre-truncate the constant
4743 so we will be able to record it later. */
4744 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
4745 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
4747 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
4749 if (GET_CODE (src) == CONST_INT
4750 && GET_CODE (width) == CONST_INT
4751 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
4752 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
4754 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
4755 << INTVAL (width)) - 1));
4759 /* Compute SRC's hash code, and also notice if it
4760 should not be recorded at all. In that case,
4761 prevent any further processing of this assignment. */
4763 hash_arg_in_memory = 0;
4766 sets[i].src_hash = HASH (src, mode);
4767 sets[i].src_volatile = do_not_record;
4768 sets[i].src_in_memory = hash_arg_in_memory;
4770 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4771 a pseudo that is set more than once, do not record SRC. Using
4772 SRC as a replacement for anything else will be incorrect in that
4773 situation. Note that this usually occurs only for stack slots,
4774 in which case all the RTL would be referring to SRC, so we don't
4775 lose any optimization opportunities by not having SRC in the
4778 if (GET_CODE (src) == MEM
4779 && find_reg_note (insn, REG_EQUIV, src) != 0
4780 && GET_CODE (dest) == REG
4781 && REGNO (dest) >= FIRST_PSEUDO_REGISTER
4782 && REG_N_SETS (REGNO (dest)) != 1)
4783 sets[i].src_volatile = 1;
4786 /* It is no longer clear why we used to do this, but it doesn't
4787 appear to still be needed. So let's try without it since this
4788 code hurts cse'ing widened ops. */
4789 /* If source is a perverse subreg (such as QI treated as an SI),
4790 treat it as volatile. It may do the work of an SI in one context
4791 where the extra bits are not being used, but cannot replace an SI
4793 if (GET_CODE (src) == SUBREG
4794 && (GET_MODE_SIZE (GET_MODE (src))
4795 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
4796 sets[i].src_volatile = 1;
4799 /* Locate all possible equivalent forms for SRC. Try to replace
4800 SRC in the insn with each cheaper equivalent.
4802 We have the following types of equivalents: SRC itself, a folded
4803 version, a value given in a REG_EQUAL note, or a value related
4806 Each of these equivalents may be part of an additional class
4807 of equivalents (if more than one is in the table, they must be in
4808 the same class; we check for this).
4810 If the source is volatile, we don't do any table lookups.
4812 We note any constant equivalent for possible later use in a
4815 if (!sets[i].src_volatile)
4816 elt = lookup (src, sets[i].src_hash, mode);
4818 sets[i].src_elt = elt;
4820 if (elt && src_eqv_here && src_eqv_elt)
4822 if (elt->first_same_value != src_eqv_elt->first_same_value)
4824 /* The REG_EQUAL is indicating that two formerly distinct
4825 classes are now equivalent. So merge them. */
4826 merge_equiv_classes (elt, src_eqv_elt);
4827 src_eqv_hash = HASH (src_eqv, elt->mode);
4828 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
4834 else if (src_eqv_elt)
4837 /* Try to find a constant somewhere and record it in `src_const'.
4838 Record its table element, if any, in `src_const_elt'. Look in
4839 any known equivalences first. (If the constant is not in the
4840 table, also set `sets[i].src_const_hash'). */
4842 for (p = elt->first_same_value; p; p = p->next_same_value)
4846 src_const_elt = elt;
4851 && (CONSTANT_P (src_folded)
4852 /* Consider (minus (label_ref L1) (label_ref L2)) as
4853 "constant" here so we will record it. This allows us
4854 to fold switch statements when an ADDR_DIFF_VEC is used. */
4855 || (GET_CODE (src_folded) == MINUS
4856 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
4857 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
4858 src_const = src_folded, src_const_elt = elt;
4859 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
4860 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
4862 /* If we don't know if the constant is in the table, get its
4863 hash code and look it up. */
4864 if (src_const && src_const_elt == 0)
4866 sets[i].src_const_hash = HASH (src_const, mode);
4867 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
4870 sets[i].src_const = src_const;
4871 sets[i].src_const_elt = src_const_elt;
4873 /* If the constant and our source are both in the table, mark them as
4874 equivalent. Otherwise, if a constant is in the table but the source
4875 isn't, set ELT to it. */
4876 if (src_const_elt && elt
4877 && src_const_elt->first_same_value != elt->first_same_value)
4878 merge_equiv_classes (elt, src_const_elt);
4879 else if (src_const_elt && elt == 0)
4880 elt = src_const_elt;
4882 /* See if there is a register linearly related to a constant
4883 equivalent of SRC. */
4885 && (GET_CODE (src_const) == CONST
4886 || (src_const_elt && src_const_elt->related_value != 0)))
4888 src_related = use_related_value (src_const, src_const_elt);
4891 struct table_elt *src_related_elt
4892 = lookup (src_related, HASH (src_related, mode), mode);
4893 if (src_related_elt && elt)
4895 if (elt->first_same_value
4896 != src_related_elt->first_same_value)
4897 /* This can occur when we previously saw a CONST
4898 involving a SYMBOL_REF and then see the SYMBOL_REF
4899 twice. Merge the involved classes. */
4900 merge_equiv_classes (elt, src_related_elt);
4903 src_related_elt = 0;
4905 else if (src_related_elt && elt == 0)
4906 elt = src_related_elt;
4910 /* See if we have a CONST_INT that is already in a register in a
4913 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
4914 && GET_MODE_CLASS (mode) == MODE_INT
4915 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
4917 enum machine_mode wider_mode;
4919 for (wider_mode = GET_MODE_WIDER_MODE (mode);
4920 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
4921 && src_related == 0;
4922 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
4924 struct table_elt *const_elt
4925 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
4930 for (const_elt = const_elt->first_same_value;
4931 const_elt; const_elt = const_elt->next_same_value)
4932 if (GET_CODE (const_elt->exp) == REG)
4934 src_related = gen_lowpart_if_possible (mode,
4941 /* Another possibility is that we have an AND with a constant in
4942 a mode narrower than a word. If so, it might have been generated
4943 as part of an "if" which would narrow the AND. If we already
4944 have done the AND in a wider mode, we can use a SUBREG of that
4947 if (flag_expensive_optimizations && ! src_related
4948 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
4949 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4951 enum machine_mode tmode;
4952 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
4954 for (tmode = GET_MODE_WIDER_MODE (mode);
4955 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
4956 tmode = GET_MODE_WIDER_MODE (tmode))
4958 rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0));
4959 struct table_elt *larger_elt;
4963 PUT_MODE (new_and, tmode);
4964 XEXP (new_and, 0) = inner;
4965 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
4966 if (larger_elt == 0)
4969 for (larger_elt = larger_elt->first_same_value;
4970 larger_elt; larger_elt = larger_elt->next_same_value)
4971 if (GET_CODE (larger_elt->exp) == REG)
4974 = gen_lowpart_if_possible (mode, larger_elt->exp);
4984 #ifdef LOAD_EXTEND_OP
4985 /* See if a MEM has already been loaded with a widening operation;
4986 if it has, we can use a subreg of that. Many CISC machines
4987 also have such operations, but this is only likely to be
4988 beneficial these machines. */
4990 if (flag_expensive_optimizations && src_related == 0
4991 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4992 && GET_MODE_CLASS (mode) == MODE_INT
4993 && GET_CODE (src) == MEM && ! do_not_record
4994 && LOAD_EXTEND_OP (mode) != NIL)
4996 enum machine_mode tmode;
4998 /* Set what we are trying to extend and the operation it might
4999 have been extended with. */
5000 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
5001 XEXP (memory_extend_rtx, 0) = src;
5003 for (tmode = GET_MODE_WIDER_MODE (mode);
5004 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5005 tmode = GET_MODE_WIDER_MODE (tmode))
5007 struct table_elt *larger_elt;
5009 PUT_MODE (memory_extend_rtx, tmode);
5010 larger_elt = lookup (memory_extend_rtx,
5011 HASH (memory_extend_rtx, tmode), tmode);
5012 if (larger_elt == 0)
5015 for (larger_elt = larger_elt->first_same_value;
5016 larger_elt; larger_elt = larger_elt->next_same_value)
5017 if (GET_CODE (larger_elt->exp) == REG)
5019 src_related = gen_lowpart_if_possible (mode,
5028 #endif /* LOAD_EXTEND_OP */
5030 if (src == src_folded)
5033 /* At this point, ELT, if non-zero, points to a class of expressions
5034 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5035 and SRC_RELATED, if non-zero, each contain additional equivalent
5036 expressions. Prune these latter expressions by deleting expressions
5037 already in the equivalence class.
5039 Check for an equivalent identical to the destination. If found,
5040 this is the preferred equivalent since it will likely lead to
5041 elimination of the insn. Indicate this by placing it in
5044 if (elt) elt = elt->first_same_value;
5045 for (p = elt; p; p = p->next_same_value)
5047 enum rtx_code code = GET_CODE (p->exp);
5049 /* If the expression is not valid, ignore it. Then we do not
5050 have to check for validity below. In most cases, we can use
5051 `rtx_equal_p', since canonicalization has already been done. */
5052 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
5055 /* Also skip paradoxical subregs, unless that's what we're
5058 && (GET_MODE_SIZE (GET_MODE (p->exp))
5059 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
5061 && GET_CODE (src) == SUBREG
5062 && GET_MODE (src) == GET_MODE (p->exp)
5063 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5064 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
5067 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
5069 else if (src_folded && GET_CODE (src_folded) == code
5070 && rtx_equal_p (src_folded, p->exp))
5072 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
5073 && rtx_equal_p (src_eqv_here, p->exp))
5075 else if (src_related && GET_CODE (src_related) == code
5076 && rtx_equal_p (src_related, p->exp))
5079 /* This is the same as the destination of the insns, we want
5080 to prefer it. Copy it to src_related. The code below will
5081 then give it a negative cost. */
5082 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
5087 /* Find the cheapest valid equivalent, trying all the available
5088 possibilities. Prefer items not in the hash table to ones
5089 that are when they are equal cost. Note that we can never
5090 worsen an insn as the current contents will also succeed.
5091 If we find an equivalent identical to the destination, use it as best,
5092 since this insn will probably be eliminated in that case. */
5095 if (rtx_equal_p (src, dest))
5098 src_cost = COST (src);
5103 if (rtx_equal_p (src_eqv_here, dest))
5106 src_eqv_cost = COST (src_eqv_here);
5111 if (rtx_equal_p (src_folded, dest))
5112 src_folded_cost = -1;
5114 src_folded_cost = COST (src_folded);
5119 if (rtx_equal_p (src_related, dest))
5120 src_related_cost = -1;
5122 src_related_cost = COST (src_related);
5125 /* If this was an indirect jump insn, a known label will really be
5126 cheaper even though it looks more expensive. */
5127 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
5128 src_folded = src_const, src_folded_cost = -1;
5130 /* Terminate loop when replacement made. This must terminate since
5131 the current contents will be tested and will always be valid. */
5136 /* Skip invalid entries. */
5137 while (elt && GET_CODE (elt->exp) != REG
5138 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
5139 elt = elt->next_same_value;
5141 /* A paradoxical subreg would be bad here: it'll be the right
5142 size, but later may be adjusted so that the upper bits aren't
5143 what we want. So reject it. */
5145 && GET_CODE (elt->exp) == SUBREG
5146 && (GET_MODE_SIZE (GET_MODE (elt->exp))
5147 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
5148 /* It is okay, though, if the rtx we're trying to match
5149 will ignore any of the bits we can't predict. */
5151 && GET_CODE (src) == SUBREG
5152 && GET_MODE (src) == GET_MODE (elt->exp)
5153 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5154 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
5156 elt = elt->next_same_value;
5160 if (elt) src_elt_cost = elt->cost;
5162 /* Find cheapest and skip it for the next time. For items
5163 of equal cost, use this order:
5164 src_folded, src, src_eqv, src_related and hash table entry. */
5165 if (src_folded_cost <= src_cost
5166 && src_folded_cost <= src_eqv_cost
5167 && src_folded_cost <= src_related_cost
5168 && src_folded_cost <= src_elt_cost)
5170 trial = src_folded, src_folded_cost = 10000;
5171 if (src_folded_force_flag)
5172 trial = force_const_mem (mode, trial);
5174 else if (src_cost <= src_eqv_cost
5175 && src_cost <= src_related_cost
5176 && src_cost <= src_elt_cost)
5177 trial = src, src_cost = 10000;
5178 else if (src_eqv_cost <= src_related_cost
5179 && src_eqv_cost <= src_elt_cost)
5180 trial = copy_rtx (src_eqv_here), src_eqv_cost = 10000;
5181 else if (src_related_cost <= src_elt_cost)
5182 trial = copy_rtx (src_related), src_related_cost = 10000;
5185 trial = copy_rtx (elt->exp);
5186 elt = elt->next_same_value;
5187 src_elt_cost = 10000;
5190 /* We don't normally have an insn matching (set (pc) (pc)), so
5191 check for this separately here. We will delete such an
5194 Tablejump insns contain a USE of the table, so simply replacing
5195 the operand with the constant won't match. This is simply an
5196 unconditional branch, however, and is therefore valid. Just
5197 insert the substitution here and we will delete and re-emit
5200 /* Keep track of the original SET_SRC so that we can fix notes
5201 on libcall instructions. */
5202 old_src = SET_SRC (sets[i].rtl);
5204 if (n_sets == 1 && dest == pc_rtx
5206 || (GET_CODE (trial) == LABEL_REF
5207 && ! condjump_p (insn))))
5209 /* If TRIAL is a label in front of a jump table, we are
5210 really falling through the switch (this is how casesi
5211 insns work), so we must branch around the table. */
5212 if (GET_CODE (trial) == CODE_LABEL
5213 && NEXT_INSN (trial) != 0
5214 && GET_CODE (NEXT_INSN (trial)) == JUMP_INSN
5215 && (GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_DIFF_VEC
5216 || GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_VEC))
5218 trial = gen_rtx_LABEL_REF (Pmode, get_label_after (trial));
5220 SET_SRC (sets[i].rtl) = trial;
5221 cse_jumps_altered = 1;
5225 /* Look for a substitution that makes a valid insn. */
5226 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
5228 /* If we just made a substitution inside a libcall, then we
5229 need to make the same substitution in any notes attached
5230 to the RETVAL insn. */
5232 && (GET_CODE (old_src) == REG
5233 || GET_CODE (old_src) == SUBREG
5234 || GET_CODE (old_src) == MEM))
5235 replace_rtx (REG_NOTES (libcall_insn), old_src,
5236 canon_reg (SET_SRC (sets[i].rtl), insn));
5238 /* The result of apply_change_group can be ignored; see
5241 validate_change (insn, &SET_SRC (sets[i].rtl),
5242 canon_reg (SET_SRC (sets[i].rtl), insn),
5244 apply_change_group ();
5248 /* If we previously found constant pool entries for
5249 constants and this is a constant, try making a
5250 pool entry. Put it in src_folded unless we already have done
5251 this since that is where it likely came from. */
5253 else if (constant_pool_entries_cost
5254 && CONSTANT_P (trial)
5255 && ! (GET_CODE (trial) == CONST
5256 && GET_CODE (XEXP (trial, 0)) == TRUNCATE)
5258 || (GET_CODE (src_folded) != MEM
5259 && ! src_folded_force_flag))
5260 && GET_MODE_CLASS (mode) != MODE_CC
5261 && mode != VOIDmode)
5263 src_folded_force_flag = 1;
5265 src_folded_cost = constant_pool_entries_cost;
5269 src = SET_SRC (sets[i].rtl);
5271 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5272 However, there is an important exception: If both are registers
5273 that are not the head of their equivalence class, replace SET_SRC
5274 with the head of the class. If we do not do this, we will have
5275 both registers live over a portion of the basic block. This way,
5276 their lifetimes will likely abut instead of overlapping. */
5277 if (GET_CODE (dest) == REG
5278 && REGNO_QTY_VALID_P (REGNO (dest)))
5280 int dest_q = REG_QTY (REGNO (dest));
5281 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5283 if (dest_ent->mode == GET_MODE (dest)
5284 && dest_ent->first_reg != REGNO (dest)
5285 && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
5286 /* Don't do this if the original insn had a hard reg as
5287 SET_SRC or SET_DEST. */
5288 && (GET_CODE (sets[i].src) != REG
5289 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
5290 && (GET_CODE (dest) != REG || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
5291 /* We can't call canon_reg here because it won't do anything if
5292 SRC is a hard register. */
5294 int src_q = REG_QTY (REGNO (src));
5295 struct qty_table_elem *src_ent = &qty_table[src_q];
5296 int first = src_ent->first_reg;
5298 = (first >= FIRST_PSEUDO_REGISTER
5299 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
5301 /* We must use validate-change even for this, because this
5302 might be a special no-op instruction, suitable only to
5304 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
5307 /* If we had a constant that is cheaper than what we are now
5308 setting SRC to, use that constant. We ignored it when we
5309 thought we could make this into a no-op. */
5310 if (src_const && COST (src_const) < COST (src)
5311 && validate_change (insn, &SET_SRC (sets[i].rtl), src_const,
5318 /* If we made a change, recompute SRC values. */
5319 if (src != sets[i].src)
5322 hash_arg_in_memory = 0;
5324 sets[i].src_hash = HASH (src, mode);
5325 sets[i].src_volatile = do_not_record;
5326 sets[i].src_in_memory = hash_arg_in_memory;
5327 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
5330 /* If this is a single SET, we are setting a register, and we have an
5331 equivalent constant, we want to add a REG_NOTE. We don't want
5332 to write a REG_EQUAL note for a constant pseudo since verifying that
5333 that pseudo hasn't been eliminated is a pain. Such a note also
5334 won't help anything.
5336 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
5337 which can be created for a reference to a compile time computable
5338 entry in a jump table. */
5340 if (n_sets == 1 && src_const && GET_CODE (dest) == REG
5341 && GET_CODE (src_const) != REG
5342 && ! (GET_CODE (src_const) == CONST
5343 && GET_CODE (XEXP (src_const, 0)) == MINUS
5344 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
5345 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
5347 tem = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5349 /* Make sure that the rtx is not shared with any other insn. */
5350 src_const = copy_rtx (src_const);
5352 /* Record the actual constant value in a REG_EQUAL note, making
5353 a new one if one does not already exist. */
5355 XEXP (tem, 0) = src_const;
5357 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_EQUAL,
5358 src_const, REG_NOTES (insn));
5360 /* If storing a constant value in a register that
5361 previously held the constant value 0,
5362 record this fact with a REG_WAS_0 note on this insn.
5364 Note that the *register* is required to have previously held 0,
5365 not just any register in the quantity and we must point to the
5366 insn that set that register to zero.
5368 Rather than track each register individually, we just see if
5369 the last set for this quantity was for this register. */
5371 if (REGNO_QTY_VALID_P (REGNO (dest)))
5373 int dest_q = REG_QTY (REGNO (dest));
5374 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5376 if (dest_ent->const_rtx == const0_rtx)
5378 /* See if we previously had a REG_WAS_0 note. */
5379 rtx note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
5380 rtx const_insn = dest_ent->const_insn;
5382 if ((tem = single_set (const_insn)) != 0
5383 && rtx_equal_p (SET_DEST (tem), dest))
5386 XEXP (note, 0) = const_insn;
5389 = gen_rtx_INSN_LIST (REG_WAS_0, const_insn,
5396 /* Now deal with the destination. */
5399 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5400 to the MEM or REG within it. */
5401 while (GET_CODE (dest) == SIGN_EXTRACT
5402 || GET_CODE (dest) == ZERO_EXTRACT
5403 || GET_CODE (dest) == SUBREG
5404 || GET_CODE (dest) == STRICT_LOW_PART)
5405 dest = XEXP (dest, 0);
5407 sets[i].inner_dest = dest;
5409 if (GET_CODE (dest) == MEM)
5411 #ifdef PUSH_ROUNDING
5412 /* Stack pushes invalidate the stack pointer. */
5413 rtx addr = XEXP (dest, 0);
5414 if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
5415 || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
5416 && XEXP (addr, 0) == stack_pointer_rtx)
5417 invalidate (stack_pointer_rtx, Pmode);
5419 dest = fold_rtx (dest, insn);
5422 /* Compute the hash code of the destination now,
5423 before the effects of this instruction are recorded,
5424 since the register values used in the address computation
5425 are those before this instruction. */
5426 sets[i].dest_hash = HASH (dest, mode);
5428 /* Don't enter a bit-field in the hash table
5429 because the value in it after the store
5430 may not equal what was stored, due to truncation. */
5432 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
5433 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
5435 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5437 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5438 && GET_CODE (width) == CONST_INT
5439 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5440 && ! (INTVAL (src_const)
5441 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5442 /* Exception: if the value is constant,
5443 and it won't be truncated, record it. */
5447 /* This is chosen so that the destination will be invalidated
5448 but no new value will be recorded.
5449 We must invalidate because sometimes constant
5450 values can be recorded for bitfields. */
5451 sets[i].src_elt = 0;
5452 sets[i].src_volatile = 1;
5458 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5460 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5462 /* One less use of the label this insn used to jump to. */
5463 if (JUMP_LABEL (insn) != 0)
5464 --LABEL_NUSES (JUMP_LABEL (insn));
5465 PUT_CODE (insn, NOTE);
5466 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5467 NOTE_SOURCE_FILE (insn) = 0;
5468 cse_jumps_altered = 1;
5469 /* No more processing for this set. */
5473 /* If this SET is now setting PC to a label, we know it used to
5474 be a conditional or computed branch. So we see if we can follow
5475 it. If it was a computed branch, delete it and re-emit. */
5476 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
5478 /* If this is not in the format for a simple branch and
5479 we are the only SET in it, re-emit it. */
5480 if (! simplejump_p (insn) && n_sets == 1)
5482 rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
5483 JUMP_LABEL (new) = XEXP (src, 0);
5484 LABEL_NUSES (XEXP (src, 0))++;
5488 /* Otherwise, force rerecognition, since it probably had
5489 a different pattern before.
5490 This shouldn't really be necessary, since whatever
5491 changed the source value above should have done this.
5492 Until the right place is found, might as well do this here. */
5493 INSN_CODE (insn) = -1;
5495 never_reached_warning (insn);
5497 /* Now emit a BARRIER after the unconditional jump. Do not bother
5498 deleting any unreachable code, let jump/flow do that. */
5499 if (NEXT_INSN (insn) != 0
5500 && GET_CODE (NEXT_INSN (insn)) != BARRIER)
5501 emit_barrier_after (insn);
5503 cse_jumps_altered = 1;
5507 /* If destination is volatile, invalidate it and then do no further
5508 processing for this assignment. */
5510 else if (do_not_record)
5512 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
5513 || GET_CODE (dest) == MEM)
5514 invalidate (dest, VOIDmode);
5515 else if (GET_CODE (dest) == STRICT_LOW_PART
5516 || GET_CODE (dest) == ZERO_EXTRACT)
5517 invalidate (XEXP (dest, 0), GET_MODE (dest));
5521 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5522 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5525 /* If setting CC0, record what it was set to, or a constant, if it
5526 is equivalent to a constant. If it is being set to a floating-point
5527 value, make a COMPARE with the appropriate constant of 0. If we
5528 don't do this, later code can interpret this as a test against
5529 const0_rtx, which can cause problems if we try to put it into an
5530 insn as a floating-point operand. */
5531 if (dest == cc0_rtx)
5533 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5534 this_insn_cc0_mode = mode;
5535 if (FLOAT_MODE_P (mode))
5536 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5542 /* Now enter all non-volatile source expressions in the hash table
5543 if they are not already present.
5544 Record their equivalence classes in src_elt.
5545 This way we can insert the corresponding destinations into
5546 the same classes even if the actual sources are no longer in them
5547 (having been invalidated). */
5549 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5550 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5552 register struct table_elt *elt;
5553 register struct table_elt *classp = sets[0].src_elt;
5554 rtx dest = SET_DEST (sets[0].rtl);
5555 enum machine_mode eqvmode = GET_MODE (dest);
5557 if (GET_CODE (dest) == STRICT_LOW_PART)
5559 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5562 if (insert_regs (src_eqv, classp, 0))
5564 rehash_using_reg (src_eqv);
5565 src_eqv_hash = HASH (src_eqv, eqvmode);
5567 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5568 elt->in_memory = src_eqv_in_memory;
5571 /* Check to see if src_eqv_elt is the same as a set source which
5572 does not yet have an elt, and if so set the elt of the set source
5574 for (i = 0; i < n_sets; i++)
5575 if (sets[i].rtl && sets[i].src_elt == 0
5576 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5577 sets[i].src_elt = src_eqv_elt;
5580 for (i = 0; i < n_sets; i++)
5581 if (sets[i].rtl && ! sets[i].src_volatile
5582 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5584 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5586 /* REG_EQUAL in setting a STRICT_LOW_PART
5587 gives an equivalent for the entire destination register,
5588 not just for the subreg being stored in now.
5589 This is a more interesting equivalence, so we arrange later
5590 to treat the entire reg as the destination. */
5591 sets[i].src_elt = src_eqv_elt;
5592 sets[i].src_hash = src_eqv_hash;
5596 /* Insert source and constant equivalent into hash table, if not
5598 register struct table_elt *classp = src_eqv_elt;
5599 register rtx src = sets[i].src;
5600 register rtx dest = SET_DEST (sets[i].rtl);
5601 enum machine_mode mode
5602 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5604 if (sets[i].src_elt == 0)
5606 /* Don't put a hard register source into the table if this is
5607 the last insn of a libcall. In this case, we only need
5608 to put src_eqv_elt in src_elt. */
5609 if (GET_CODE (src) != REG
5610 || REGNO (src) >= FIRST_PSEUDO_REGISTER
5611 || ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5613 register struct table_elt *elt;
5615 /* Note that these insert_regs calls cannot remove
5616 any of the src_elt's, because they would have failed to
5617 match if not still valid. */
5618 if (insert_regs (src, classp, 0))
5620 rehash_using_reg (src);
5621 sets[i].src_hash = HASH (src, mode);
5623 elt = insert (src, classp, sets[i].src_hash, mode);
5624 elt->in_memory = sets[i].src_in_memory;
5625 sets[i].src_elt = classp = elt;
5628 sets[i].src_elt = classp;
5630 if (sets[i].src_const && sets[i].src_const_elt == 0
5631 && src != sets[i].src_const
5632 && ! rtx_equal_p (sets[i].src_const, src))
5633 sets[i].src_elt = insert (sets[i].src_const, classp,
5634 sets[i].src_const_hash, mode);
5637 else if (sets[i].src_elt == 0)
5638 /* If we did not insert the source into the hash table (e.g., it was
5639 volatile), note the equivalence class for the REG_EQUAL value, if any,
5640 so that the destination goes into that class. */
5641 sets[i].src_elt = src_eqv_elt;
5643 invalidate_from_clobbers (x);
5645 /* Some registers are invalidated by subroutine calls. Memory is
5646 invalidated by non-constant calls. */
5648 if (GET_CODE (insn) == CALL_INSN)
5650 if (! CONST_CALL_P (insn))
5651 invalidate_memory ();
5652 invalidate_for_call ();
5655 /* Now invalidate everything set by this instruction.
5656 If a SUBREG or other funny destination is being set,
5657 sets[i].rtl is still nonzero, so here we invalidate the reg
5658 a part of which is being set. */
5660 for (i = 0; i < n_sets; i++)
5663 /* We can't use the inner dest, because the mode associated with
5664 a ZERO_EXTRACT is significant. */
5665 register rtx dest = SET_DEST (sets[i].rtl);
5667 /* Needed for registers to remove the register from its
5668 previous quantity's chain.
5669 Needed for memory if this is a nonvarying address, unless
5670 we have just done an invalidate_memory that covers even those. */
5671 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
5672 || GET_CODE (dest) == MEM)
5673 invalidate (dest, VOIDmode);
5674 else if (GET_CODE (dest) == STRICT_LOW_PART
5675 || GET_CODE (dest) == ZERO_EXTRACT)
5676 invalidate (XEXP (dest, 0), GET_MODE (dest));
5679 /* A volatile ASM invalidates everything. */
5680 if (GET_CODE (insn) == INSN
5681 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5682 && MEM_VOLATILE_P (PATTERN (insn)))
5683 flush_hash_table ();
5685 /* Make sure registers mentioned in destinations
5686 are safe for use in an expression to be inserted.
5687 This removes from the hash table
5688 any invalid entry that refers to one of these registers.
5690 We don't care about the return value from mention_regs because
5691 we are going to hash the SET_DEST values unconditionally. */
5693 for (i = 0; i < n_sets; i++)
5697 rtx x = SET_DEST (sets[i].rtl);
5699 if (GET_CODE (x) != REG)
5703 /* We used to rely on all references to a register becoming
5704 inaccessible when a register changes to a new quantity,
5705 since that changes the hash code. However, that is not
5706 safe, since after NBUCKETS new quantities we get a
5707 hash 'collision' of a register with its own invalid
5708 entries. And since SUBREGs have been changed not to
5709 change their hash code with the hash code of the register,
5710 it wouldn't work any longer at all. So we have to check
5711 for any invalid references lying around now.
5712 This code is similar to the REG case in mention_regs,
5713 but it knows that reg_tick has been incremented, and
5714 it leaves reg_in_table as -1 . */
5715 register int regno = REGNO (x);
5716 register int endregno
5717 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
5718 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
5721 for (i = regno; i < endregno; i++)
5723 if (REG_IN_TABLE (i) >= 0)
5725 remove_invalid_refs (i);
5726 REG_IN_TABLE (i) = -1;
5733 /* We may have just removed some of the src_elt's from the hash table.
5734 So replace each one with the current head of the same class. */
5736 for (i = 0; i < n_sets; i++)
5739 if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
5740 /* If elt was removed, find current head of same class,
5741 or 0 if nothing remains of that class. */
5743 register struct table_elt *elt = sets[i].src_elt;
5745 while (elt && elt->prev_same_value)
5746 elt = elt->prev_same_value;
5748 while (elt && elt->first_same_value == 0)
5749 elt = elt->next_same_value;
5750 sets[i].src_elt = elt ? elt->first_same_value : 0;
5754 /* Now insert the destinations into their equivalence classes. */
5756 for (i = 0; i < n_sets; i++)
5759 register rtx dest = SET_DEST (sets[i].rtl);
5760 rtx inner_dest = sets[i].inner_dest;
5761 register struct table_elt *elt;
5763 /* Don't record value if we are not supposed to risk allocating
5764 floating-point values in registers that might be wider than
5766 if ((flag_float_store
5767 && GET_CODE (dest) == MEM
5768 && FLOAT_MODE_P (GET_MODE (dest)))
5769 /* Don't record BLKmode values, because we don't know the
5770 size of it, and can't be sure that other BLKmode values
5771 have the same or smaller size. */
5772 || GET_MODE (dest) == BLKmode
5773 /* Don't record values of destinations set inside a libcall block
5774 since we might delete the libcall. Things should have been set
5775 up so we won't want to reuse such a value, but we play it safe
5778 /* If we didn't put a REG_EQUAL value or a source into the hash
5779 table, there is no point is recording DEST. */
5780 || sets[i].src_elt == 0
5781 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
5782 or SIGN_EXTEND, don't record DEST since it can cause
5783 some tracking to be wrong.
5785 ??? Think about this more later. */
5786 || (GET_CODE (dest) == SUBREG
5787 && (GET_MODE_SIZE (GET_MODE (dest))
5788 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5789 && (GET_CODE (sets[i].src) == SIGN_EXTEND
5790 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
5793 /* STRICT_LOW_PART isn't part of the value BEING set,
5794 and neither is the SUBREG inside it.
5795 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
5796 if (GET_CODE (dest) == STRICT_LOW_PART)
5797 dest = SUBREG_REG (XEXP (dest, 0));
5799 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5800 /* Registers must also be inserted into chains for quantities. */
5801 if (insert_regs (dest, sets[i].src_elt, 1))
5803 /* If `insert_regs' changes something, the hash code must be
5805 rehash_using_reg (dest);
5806 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
5809 if (GET_CODE (inner_dest) == MEM
5810 && GET_CODE (XEXP (inner_dest, 0)) == ADDRESSOF)
5811 /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say
5812 that (MEM (ADDRESSOF (X))) is equivalent to Y.
5813 Consider the case in which the address of the MEM is
5814 passed to a function, which alters the MEM. Then, if we
5815 later use Y instead of the MEM we'll miss the update. */
5816 elt = insert (dest, 0, sets[i].dest_hash, GET_MODE (dest));
5818 elt = insert (dest, sets[i].src_elt,
5819 sets[i].dest_hash, GET_MODE (dest));
5821 elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM
5822 && (! RTX_UNCHANGING_P (sets[i].inner_dest)
5823 || FIXED_BASE_PLUS_P (XEXP (sets[i].inner_dest,
5826 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
5827 narrower than M2, and both M1 and M2 are the same number of words,
5828 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
5829 make that equivalence as well.
5831 However, BAR may have equivalences for which gen_lowpart_if_possible
5832 will produce a simpler value than gen_lowpart_if_possible applied to
5833 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
5834 BAR's equivalences. If we don't get a simplified form, make
5835 the SUBREG. It will not be used in an equivalence, but will
5836 cause two similar assignments to be detected.
5838 Note the loop below will find SUBREG_REG (DEST) since we have
5839 already entered SRC and DEST of the SET in the table. */
5841 if (GET_CODE (dest) == SUBREG
5842 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
5844 == (GET_MODE_SIZE (GET_MODE (dest)) - 1)/ UNITS_PER_WORD)
5845 && (GET_MODE_SIZE (GET_MODE (dest))
5846 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
5847 && sets[i].src_elt != 0)
5849 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
5850 struct table_elt *elt, *classp = 0;
5852 for (elt = sets[i].src_elt->first_same_value; elt;
5853 elt = elt->next_same_value)
5857 struct table_elt *src_elt;
5859 /* Ignore invalid entries. */
5860 if (GET_CODE (elt->exp) != REG
5861 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
5864 new_src = gen_lowpart_if_possible (new_mode, elt->exp);
5866 new_src = gen_rtx_SUBREG (new_mode, elt->exp, 0);
5868 src_hash = HASH (new_src, new_mode);
5869 src_elt = lookup (new_src, src_hash, new_mode);
5871 /* Put the new source in the hash table is if isn't
5875 if (insert_regs (new_src, classp, 0))
5877 rehash_using_reg (new_src);
5878 src_hash = HASH (new_src, new_mode);
5880 src_elt = insert (new_src, classp, src_hash, new_mode);
5881 src_elt->in_memory = elt->in_memory;
5883 else if (classp && classp != src_elt->first_same_value)
5884 /* Show that two things that we've seen before are
5885 actually the same. */
5886 merge_equiv_classes (src_elt, classp);
5888 classp = src_elt->first_same_value;
5889 /* Ignore invalid entries. */
5891 && GET_CODE (classp->exp) != REG
5892 && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
5893 classp = classp->next_same_value;
5898 /* Special handling for (set REG0 REG1)
5899 where REG0 is the "cheapest", cheaper than REG1.
5900 After cse, REG1 will probably not be used in the sequel,
5901 so (if easily done) change this insn to (set REG1 REG0) and
5902 replace REG1 with REG0 in the previous insn that computed their value.
5903 Then REG1 will become a dead store and won't cloud the situation
5904 for later optimizations.
5906 Do not make this change if REG1 is a hard register, because it will
5907 then be used in the sequel and we may be changing a two-operand insn
5908 into a three-operand insn.
5910 Also do not do this if we are operating on a copy of INSN.
5912 Also don't do this if INSN ends a libcall; this would cause an unrelated
5913 register to be set in the middle of a libcall, and we then get bad code
5914 if the libcall is deleted. */
5916 if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
5917 && NEXT_INSN (PREV_INSN (insn)) == insn
5918 && GET_CODE (SET_SRC (sets[0].rtl)) == REG
5919 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
5920 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
5922 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
5923 struct qty_table_elem *src_ent = &qty_table[src_q];
5925 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
5926 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5928 rtx prev = PREV_INSN (insn);
5929 while (prev && GET_CODE (prev) == NOTE)
5930 prev = PREV_INSN (prev);
5932 if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
5933 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
5935 rtx dest = SET_DEST (sets[0].rtl);
5936 rtx note = find_reg_note (prev, REG_EQUIV, NULL_RTX);
5938 validate_change (prev, & SET_DEST (PATTERN (prev)), dest, 1);
5939 validate_change (insn, & SET_DEST (sets[0].rtl),
5940 SET_SRC (sets[0].rtl), 1);
5941 validate_change (insn, & SET_SRC (sets[0].rtl), dest, 1);
5942 apply_change_group ();
5944 /* If REG1 was equivalent to a constant, REG0 is not. */
5946 PUT_REG_NOTE_KIND (note, REG_EQUAL);
5948 /* If there was a REG_WAS_0 note on PREV, remove it. Move
5949 any REG_WAS_0 note on INSN to PREV. */
5950 note = find_reg_note (prev, REG_WAS_0, NULL_RTX);
5952 remove_note (prev, note);
5954 note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
5957 remove_note (insn, note);
5958 XEXP (note, 1) = REG_NOTES (prev);
5959 REG_NOTES (prev) = note;
5962 /* If INSN has a REG_EQUAL note, and this note mentions REG0,
5963 then we must delete it, because the value in REG0 has changed. */
5964 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5965 if (note && reg_mentioned_p (dest, XEXP (note, 0)))
5966 remove_note (insn, note);
5971 /* If this is a conditional jump insn, record any known equivalences due to
5972 the condition being tested. */
5974 last_jump_equiv_class = 0;
5975 if (GET_CODE (insn) == JUMP_INSN
5976 && n_sets == 1 && GET_CODE (x) == SET
5977 && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
5978 record_jump_equiv (insn, 0);
5981 /* If the previous insn set CC0 and this insn no longer references CC0,
5982 delete the previous insn. Here we use the fact that nothing expects CC0
5983 to be valid over an insn, which is true until the final pass. */
5984 if (prev_insn && GET_CODE (prev_insn) == INSN
5985 && (tem = single_set (prev_insn)) != 0
5986 && SET_DEST (tem) == cc0_rtx
5987 && ! reg_mentioned_p (cc0_rtx, x))
5989 PUT_CODE (prev_insn, NOTE);
5990 NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
5991 NOTE_SOURCE_FILE (prev_insn) = 0;
5994 prev_insn_cc0 = this_insn_cc0;
5995 prev_insn_cc0_mode = this_insn_cc0_mode;
6001 /* Remove from the hash table all expressions that reference memory. */
6004 invalidate_memory ()
6007 register struct table_elt *p, *next;
6009 for (i = 0; i < NBUCKETS; i++)
6010 for (p = table[i]; p; p = next)
6012 next = p->next_same_hash;
6014 remove_from_table (p, i);
6018 /* If ADDR is an address that implicitly affects the stack pointer, return
6019 1 and update the register tables to show the effect. Else, return 0. */
6022 addr_affects_sp_p (addr)
6025 if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
6026 || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
6027 && GET_CODE (XEXP (addr, 0)) == REG
6028 && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
6030 if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
6031 REG_TICK (STACK_POINTER_REGNUM)++;
6033 /* This should be *very* rare. */
6034 if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
6035 invalidate (stack_pointer_rtx, VOIDmode);
6043 /* Perform invalidation on the basis of everything about an insn
6044 except for invalidating the actual places that are SET in it.
6045 This includes the places CLOBBERed, and anything that might
6046 alias with something that is SET or CLOBBERed.
6048 X is the pattern of the insn. */
6051 invalidate_from_clobbers (x)
6054 if (GET_CODE (x) == CLOBBER)
6056 rtx ref = XEXP (x, 0);
6059 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6060 || GET_CODE (ref) == MEM)
6061 invalidate (ref, VOIDmode);
6062 else if (GET_CODE (ref) == STRICT_LOW_PART
6063 || GET_CODE (ref) == ZERO_EXTRACT)
6064 invalidate (XEXP (ref, 0), GET_MODE (ref));
6067 else if (GET_CODE (x) == PARALLEL)
6070 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
6072 register rtx y = XVECEXP (x, 0, i);
6073 if (GET_CODE (y) == CLOBBER)
6075 rtx ref = XEXP (y, 0);
6076 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6077 || GET_CODE (ref) == MEM)
6078 invalidate (ref, VOIDmode);
6079 else if (GET_CODE (ref) == STRICT_LOW_PART
6080 || GET_CODE (ref) == ZERO_EXTRACT)
6081 invalidate (XEXP (ref, 0), GET_MODE (ref));
6087 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6088 and replace any registers in them with either an equivalent constant
6089 or the canonical form of the register. If we are inside an address,
6090 only do this if the address remains valid.
6092 OBJECT is 0 except when within a MEM in which case it is the MEM.
6094 Return the replacement for X. */
6097 cse_process_notes (x, object)
6101 enum rtx_code code = GET_CODE (x);
6102 const char *fmt = GET_RTX_FORMAT (code);
6118 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), x);
6123 if (REG_NOTE_KIND (x) == REG_EQUAL)
6124 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
6126 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
6133 rtx new = cse_process_notes (XEXP (x, 0), object);
6134 /* We don't substitute VOIDmode constants into these rtx,
6135 since they would impede folding. */
6136 if (GET_MODE (new) != VOIDmode)
6137 validate_change (object, &XEXP (x, 0), new, 0);
6142 i = REG_QTY (REGNO (x));
6144 /* Return a constant or a constant register. */
6145 if (REGNO_QTY_VALID_P (REGNO (x)))
6147 struct qty_table_elem *ent = &qty_table[i];
6149 if (ent->const_rtx != NULL_RTX
6150 && (CONSTANT_P (ent->const_rtx)
6151 || GET_CODE (ent->const_rtx) == REG))
6153 rtx new = gen_lowpart_if_possible (GET_MODE (x), ent->const_rtx);
6159 /* Otherwise, canonicalize this register. */
6160 return canon_reg (x, NULL_RTX);
6166 for (i = 0; i < GET_RTX_LENGTH (code); i++)
6168 validate_change (object, &XEXP (x, i),
6169 cse_process_notes (XEXP (x, i), object), 0);
6174 /* Find common subexpressions between the end test of a loop and the beginning
6175 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6177 Often we have a loop where an expression in the exit test is used
6178 in the body of the loop. For example "while (*p) *q++ = *p++;".
6179 Because of the way we duplicate the loop exit test in front of the loop,
6180 however, we don't detect that common subexpression. This will be caught
6181 when global cse is implemented, but this is a quite common case.
6183 This function handles the most common cases of these common expressions.
6184 It is called after we have processed the basic block ending with the
6185 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6186 jumps to a label used only once. */
6189 cse_around_loop (loop_start)
6194 struct table_elt *p;
6196 /* If the jump at the end of the loop doesn't go to the start, we don't
6198 for (insn = PREV_INSN (loop_start);
6199 insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
6200 insn = PREV_INSN (insn))
6204 || GET_CODE (insn) != NOTE
6205 || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
6208 /* If the last insn of the loop (the end test) was an NE comparison,
6209 we will interpret it as an EQ comparison, since we fell through
6210 the loop. Any equivalences resulting from that comparison are
6211 therefore not valid and must be invalidated. */
6212 if (last_jump_equiv_class)
6213 for (p = last_jump_equiv_class->first_same_value; p;
6214 p = p->next_same_value)
6216 if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
6217 || (GET_CODE (p->exp) == SUBREG
6218 && GET_CODE (SUBREG_REG (p->exp)) == REG))
6219 invalidate (p->exp, VOIDmode);
6220 else if (GET_CODE (p->exp) == STRICT_LOW_PART
6221 || GET_CODE (p->exp) == ZERO_EXTRACT)
6222 invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
6225 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6226 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6228 The only thing we do with SET_DEST is invalidate entries, so we
6229 can safely process each SET in order. It is slightly less efficient
6230 to do so, but we only want to handle the most common cases.
6232 The gen_move_insn call in cse_set_around_loop may create new pseudos.
6233 These pseudos won't have valid entries in any of the tables indexed
6234 by register number, such as reg_qty. We avoid out-of-range array
6235 accesses by not processing any instructions created after cse started. */
6237 for (insn = NEXT_INSN (loop_start);
6238 GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
6239 && INSN_UID (insn) < max_insn_uid
6240 && ! (GET_CODE (insn) == NOTE
6241 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
6242 insn = NEXT_INSN (insn))
6244 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
6245 && (GET_CODE (PATTERN (insn)) == SET
6246 || GET_CODE (PATTERN (insn)) == CLOBBER))
6247 cse_set_around_loop (PATTERN (insn), insn, loop_start);
6248 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
6249 && GET_CODE (PATTERN (insn)) == PARALLEL)
6250 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6251 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
6252 || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
6253 cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
6258 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6259 since they are done elsewhere. This function is called via note_stores. */
6262 invalidate_skipped_set (dest, set, data)
6265 void *data ATTRIBUTE_UNUSED;
6267 enum rtx_code code = GET_CODE (dest);
6270 && ! addr_affects_sp_p (dest) /* If this is not a stack push ... */
6271 /* There are times when an address can appear varying and be a PLUS
6272 during this scan when it would be a fixed address were we to know
6273 the proper equivalences. So invalidate all memory if there is
6274 a BLKmode or nonscalar memory reference or a reference to a
6275 variable address. */
6276 && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
6277 || cse_rtx_varies_p (XEXP (dest, 0))))
6279 invalidate_memory ();
6283 if (GET_CODE (set) == CLOBBER
6290 if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
6291 invalidate (XEXP (dest, 0), GET_MODE (dest));
6292 else if (code == REG || code == SUBREG || code == MEM)
6293 invalidate (dest, VOIDmode);
6296 /* Invalidate all insns from START up to the end of the function or the
6297 next label. This called when we wish to CSE around a block that is
6298 conditionally executed. */
6301 invalidate_skipped_block (start)
6306 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
6307 insn = NEXT_INSN (insn))
6309 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6312 if (GET_CODE (insn) == CALL_INSN)
6314 if (! CONST_CALL_P (insn))
6315 invalidate_memory ();
6316 invalidate_for_call ();
6319 invalidate_from_clobbers (PATTERN (insn));
6320 note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
6324 /* If modifying X will modify the value in *DATA (which is really an
6325 `rtx *'), indicate that fact by setting the pointed to value to
6329 cse_check_loop_start (x, set, data)
6331 rtx set ATTRIBUTE_UNUSED;
6334 rtx *cse_check_loop_start_value = (rtx *) data;
6336 if (*cse_check_loop_start_value == NULL_RTX
6337 || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
6340 if ((GET_CODE (x) == MEM && GET_CODE (*cse_check_loop_start_value) == MEM)
6341 || reg_overlap_mentioned_p (x, *cse_check_loop_start_value))
6342 *cse_check_loop_start_value = NULL_RTX;
6345 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6346 a loop that starts with the label at LOOP_START.
6348 If X is a SET, we see if its SET_SRC is currently in our hash table.
6349 If so, we see if it has a value equal to some register used only in the
6350 loop exit code (as marked by jump.c).
6352 If those two conditions are true, we search backwards from the start of
6353 the loop to see if that same value was loaded into a register that still
6354 retains its value at the start of the loop.
6356 If so, we insert an insn after the load to copy the destination of that
6357 load into the equivalent register and (try to) replace our SET_SRC with that
6360 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6363 cse_set_around_loop (x, insn, loop_start)
6368 struct table_elt *src_elt;
6370 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6371 are setting PC or CC0 or whose SET_SRC is already a register. */
6372 if (GET_CODE (x) == SET
6373 && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
6374 && GET_CODE (SET_SRC (x)) != REG)
6376 src_elt = lookup (SET_SRC (x),
6377 HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
6378 GET_MODE (SET_DEST (x)));
6381 for (src_elt = src_elt->first_same_value; src_elt;
6382 src_elt = src_elt->next_same_value)
6383 if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
6384 && COST (src_elt->exp) < COST (SET_SRC (x)))
6388 /* Look for an insn in front of LOOP_START that sets
6389 something in the desired mode to SET_SRC (x) before we hit
6390 a label or CALL_INSN. */
6392 for (p = prev_nonnote_insn (loop_start);
6393 p && GET_CODE (p) != CALL_INSN
6394 && GET_CODE (p) != CODE_LABEL;
6395 p = prev_nonnote_insn (p))
6396 if ((set = single_set (p)) != 0
6397 && GET_CODE (SET_DEST (set)) == REG
6398 && GET_MODE (SET_DEST (set)) == src_elt->mode
6399 && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
6401 /* We now have to ensure that nothing between P
6402 and LOOP_START modified anything referenced in
6403 SET_SRC (x). We know that nothing within the loop
6404 can modify it, or we would have invalidated it in
6407 rtx cse_check_loop_start_value = SET_SRC (x);
6408 for (q = p; q != loop_start; q = NEXT_INSN (q))
6409 if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
6410 note_stores (PATTERN (q),
6411 cse_check_loop_start,
6412 &cse_check_loop_start_value);
6414 /* If nothing was changed and we can replace our
6415 SET_SRC, add an insn after P to copy its destination
6416 to what we will be replacing SET_SRC with. */
6417 if (cse_check_loop_start_value
6418 && validate_change (insn, &SET_SRC (x),
6421 /* If this creates new pseudos, this is unsafe,
6422 because the regno of new pseudo is unsuitable
6423 to index into reg_qty when cse_insn processes
6424 the new insn. Therefore, if a new pseudo was
6425 created, discard this optimization. */
6426 int nregs = max_reg_num ();
6428 = gen_move_insn (src_elt->exp, SET_DEST (set));
6429 if (nregs != max_reg_num ())
6431 if (! validate_change (insn, &SET_SRC (x),
6436 emit_insn_after (move, p);
6443 /* Deal with the destination of X affecting the stack pointer. */
6444 addr_affects_sp_p (SET_DEST (x));
6446 /* See comment on similar code in cse_insn for explanation of these
6448 if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
6449 || GET_CODE (SET_DEST (x)) == MEM)
6450 invalidate (SET_DEST (x), VOIDmode);
6451 else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
6452 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
6453 invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
6456 /* Find the end of INSN's basic block and return its range,
6457 the total number of SETs in all the insns of the block, the last insn of the
6458 block, and the branch path.
6460 The branch path indicates which branches should be followed. If a non-zero
6461 path size is specified, the block should be rescanned and a different set
6462 of branches will be taken. The branch path is only used if
6463 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
6465 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6466 used to describe the block. It is filled in with the information about
6467 the current block. The incoming structure's branch path, if any, is used
6468 to construct the output branch path. */
6471 cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks)
6473 struct cse_basic_block_data *data;
6480 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
6481 rtx next = GET_RTX_CLASS (GET_CODE (insn)) == 'i' ? insn : next_real_insn (insn);
6482 int path_size = data->path_size;
6486 /* Update the previous branch path, if any. If the last branch was
6487 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6488 shorten the path by one and look at the previous branch. We know that
6489 at least one branch must have been taken if PATH_SIZE is non-zero. */
6490 while (path_size > 0)
6492 if (data->path[path_size - 1].status != NOT_TAKEN)
6494 data->path[path_size - 1].status = NOT_TAKEN;
6501 /* If the first instruction is marked with QImode, that means we've
6502 already processed this block. Our caller will look at DATA->LAST
6503 to figure out where to go next. We want to return the next block
6504 in the instruction stream, not some branched-to block somewhere
6505 else. We accomplish this by pretending our called forbid us to
6506 follow jumps, or skip blocks. */
6507 if (GET_MODE (insn) == QImode)
6508 follow_jumps = skip_blocks = 0;
6510 /* Scan to end of this basic block. */
6511 while (p && GET_CODE (p) != CODE_LABEL)
6513 /* Don't cse out the end of a loop. This makes a difference
6514 only for the unusual loops that always execute at least once;
6515 all other loops have labels there so we will stop in any case.
6516 Cse'ing out the end of the loop is dangerous because it
6517 might cause an invariant expression inside the loop
6518 to be reused after the end of the loop. This would make it
6519 hard to move the expression out of the loop in loop.c,
6520 especially if it is one of several equivalent expressions
6521 and loop.c would like to eliminate it.
6523 If we are running after loop.c has finished, we can ignore
6524 the NOTE_INSN_LOOP_END. */
6526 if (! after_loop && GET_CODE (p) == NOTE
6527 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
6530 /* Don't cse over a call to setjmp; on some machines (eg vax)
6531 the regs restored by the longjmp come from
6532 a later time than the setjmp. */
6533 if (GET_CODE (p) == NOTE
6534 && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
6537 /* A PARALLEL can have lots of SETs in it,
6538 especially if it is really an ASM_OPERANDS. */
6539 if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
6540 && GET_CODE (PATTERN (p)) == PARALLEL)
6541 nsets += XVECLEN (PATTERN (p), 0);
6542 else if (GET_CODE (p) != NOTE)
6545 /* Ignore insns made by CSE; they cannot affect the boundaries of
6548 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
6549 high_cuid = INSN_CUID (p);
6550 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
6551 low_cuid = INSN_CUID (p);
6553 /* See if this insn is in our branch path. If it is and we are to
6555 if (path_entry < path_size && data->path[path_entry].branch == p)
6557 if (data->path[path_entry].status != NOT_TAKEN)
6560 /* Point to next entry in path, if any. */
6564 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
6565 was specified, we haven't reached our maximum path length, there are
6566 insns following the target of the jump, this is the only use of the
6567 jump label, and the target label is preceded by a BARRIER.
6569 Alternatively, we can follow the jump if it branches around a
6570 block of code and there are no other branches into the block.
6571 In this case invalidate_skipped_block will be called to invalidate any
6572 registers set in the block when following the jump. */
6574 else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1
6575 && GET_CODE (p) == JUMP_INSN
6576 && GET_CODE (PATTERN (p)) == SET
6577 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
6578 && JUMP_LABEL (p) != 0
6579 && LABEL_NUSES (JUMP_LABEL (p)) == 1
6580 && NEXT_INSN (JUMP_LABEL (p)) != 0)
6582 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
6583 if ((GET_CODE (q) != NOTE
6584 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
6585 || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP)
6586 && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
6589 /* If we ran into a BARRIER, this code is an extension of the
6590 basic block when the branch is taken. */
6591 if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
6593 /* Don't allow ourself to keep walking around an
6594 always-executed loop. */
6595 if (next_real_insn (q) == next)
6601 /* Similarly, don't put a branch in our path more than once. */
6602 for (i = 0; i < path_entry; i++)
6603 if (data->path[i].branch == p)
6606 if (i != path_entry)
6609 data->path[path_entry].branch = p;
6610 data->path[path_entry++].status = TAKEN;
6612 /* This branch now ends our path. It was possible that we
6613 didn't see this branch the last time around (when the
6614 insn in front of the target was a JUMP_INSN that was
6615 turned into a no-op). */
6616 path_size = path_entry;
6619 /* Mark block so we won't scan it again later. */
6620 PUT_MODE (NEXT_INSN (p), QImode);
6622 /* Detect a branch around a block of code. */
6623 else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
6627 if (next_real_insn (q) == next)
6633 for (i = 0; i < path_entry; i++)
6634 if (data->path[i].branch == p)
6637 if (i != path_entry)
6640 /* This is no_labels_between_p (p, q) with an added check for
6641 reaching the end of a function (in case Q precedes P). */
6642 for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
6643 if (GET_CODE (tmp) == CODE_LABEL)
6648 data->path[path_entry].branch = p;
6649 data->path[path_entry++].status = AROUND;
6651 path_size = path_entry;
6654 /* Mark block so we won't scan it again later. */
6655 PUT_MODE (NEXT_INSN (p), QImode);
6662 data->low_cuid = low_cuid;
6663 data->high_cuid = high_cuid;
6664 data->nsets = nsets;
6667 /* If all jumps in the path are not taken, set our path length to zero
6668 so a rescan won't be done. */
6669 for (i = path_size - 1; i >= 0; i--)
6670 if (data->path[i].status != NOT_TAKEN)
6674 data->path_size = 0;
6676 data->path_size = path_size;
6678 /* End the current branch path. */
6679 data->path[path_size].branch = 0;
6682 /* Perform cse on the instructions of a function.
6683 F is the first instruction.
6684 NREGS is one plus the highest pseudo-reg number used in the instruction.
6686 AFTER_LOOP is 1 if this is the cse call done after loop optimization
6687 (only if -frerun-cse-after-loop).
6689 Returns 1 if jump_optimize should be redone due to simplifications
6690 in conditional jump instructions. */
6693 cse_main (f, nregs, after_loop, file)
6699 struct cse_basic_block_data val;
6700 register rtx insn = f;
6703 cse_jumps_altered = 0;
6704 recorded_label_ref = 0;
6705 constant_pool_entries_cost = 0;
6709 init_alias_analysis ();
6713 max_insn_uid = get_max_uid ();
6715 reg_eqv_table = (struct reg_eqv_elem *)
6716 xmalloc(nregs * sizeof(struct reg_eqv_elem));
6718 #ifdef LOAD_EXTEND_OP
6720 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
6721 and change the code and mode as appropriate. */
6722 memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX);
6725 /* Discard all the free elements of the previous function
6726 since they are allocated in the temporarily obstack. */
6727 bzero ((char *) table, sizeof table);
6728 free_element_chain = 0;
6729 n_elements_made = 0;
6731 /* Find the largest uid. */
6733 max_uid = get_max_uid ();
6734 uid_cuid = (int *) xcalloc (max_uid + 1, sizeof (int));
6736 /* Compute the mapping from uids to cuids.
6737 CUIDs are numbers assigned to insns, like uids,
6738 except that cuids increase monotonically through the code.
6739 Don't assign cuids to line-number NOTEs, so that the distance in cuids
6740 between two insns is not affected by -g. */
6742 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
6744 if (GET_CODE (insn) != NOTE
6745 || NOTE_LINE_NUMBER (insn) < 0)
6746 INSN_CUID (insn) = ++i;
6748 /* Give a line number note the same cuid as preceding insn. */
6749 INSN_CUID (insn) = i;
6752 /* Initialize which registers are clobbered by calls. */
6754 CLEAR_HARD_REG_SET (regs_invalidated_by_call);
6756 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
6757 if ((call_used_regs[i]
6758 /* Used to check !fixed_regs[i] here, but that isn't safe;
6759 fixed regs are still call-clobbered, and sched can get
6760 confused if they can "live across calls".
6762 The frame pointer is always preserved across calls. The arg
6763 pointer is if it is fixed. The stack pointer usually is, unless
6764 RETURN_POPS_ARGS, in which case an explicit CLOBBER
6765 will be present. If we are generating PIC code, the PIC offset
6766 table register is preserved across calls. */
6768 && i != STACK_POINTER_REGNUM
6769 && i != FRAME_POINTER_REGNUM
6770 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
6771 && i != HARD_FRAME_POINTER_REGNUM
6773 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
6774 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
6776 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
6777 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
6781 SET_HARD_REG_BIT (regs_invalidated_by_call, i);
6784 ggc_push_context ();
6786 /* Loop over basic blocks.
6787 Compute the maximum number of qty's needed for each basic block
6788 (which is 2 for each SET). */
6792 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
6793 flag_cse_skip_blocks);
6795 /* If this basic block was already processed or has no sets, skip it. */
6796 if (val.nsets == 0 || GET_MODE (insn) == QImode)
6798 PUT_MODE (insn, VOIDmode);
6799 insn = (val.last ? NEXT_INSN (val.last) : 0);
6804 cse_basic_block_start = val.low_cuid;
6805 cse_basic_block_end = val.high_cuid;
6806 max_qty = val.nsets * 2;
6809 fnotice (file, ";; Processing block from %d to %d, %d sets.\n",
6810 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
6813 /* Make MAX_QTY bigger to give us room to optimize
6814 past the end of this basic block, if that should prove useful. */
6820 /* If this basic block is being extended by following certain jumps,
6821 (see `cse_end_of_basic_block'), we reprocess the code from the start.
6822 Otherwise, we start after this basic block. */
6823 if (val.path_size > 0)
6824 cse_basic_block (insn, val.last, val.path, 0);
6827 int old_cse_jumps_altered = cse_jumps_altered;
6830 /* When cse changes a conditional jump to an unconditional
6831 jump, we want to reprocess the block, since it will give
6832 us a new branch path to investigate. */
6833 cse_jumps_altered = 0;
6834 temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
6835 if (cse_jumps_altered == 0
6836 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
6839 cse_jumps_altered |= old_cse_jumps_altered;
6853 if (max_elements_made < n_elements_made)
6854 max_elements_made = n_elements_made;
6857 end_alias_analysis ();
6859 free (reg_eqv_table);
6861 return cse_jumps_altered || recorded_label_ref;
6864 /* Process a single basic block. FROM and TO and the limits of the basic
6865 block. NEXT_BRANCH points to the branch path when following jumps or
6866 a null path when not following jumps.
6868 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
6869 loop. This is true when we are being called for the last time on a
6870 block and this CSE pass is before loop.c. */
6873 cse_basic_block (from, to, next_branch, around_loop)
6874 register rtx from, to;
6875 struct branch_path *next_branch;
6880 rtx libcall_insn = NULL_RTX;
6883 /* This array is undefined before max_reg, so only allocate
6884 the space actually needed and adjust the start. */
6886 qty_table = (struct qty_table_elem *) xmalloc ((max_qty - max_reg)
6887 * sizeof(struct qty_table_elem));
6888 qty_table -= max_reg;
6892 /* TO might be a label. If so, protect it from being deleted. */
6893 if (to != 0 && GET_CODE (to) == CODE_LABEL)
6896 for (insn = from; insn != to; insn = NEXT_INSN (insn))
6898 register enum rtx_code code = GET_CODE (insn);
6900 /* If we have processed 1,000 insns, flush the hash table to
6901 avoid extreme quadratic behavior. We must not include NOTEs
6902 in the count since there may be more or them when generating
6903 debugging information. If we clear the table at different
6904 times, code generated with -g -O might be different than code
6905 generated with -O but not -g.
6907 ??? This is a real kludge and needs to be done some other way.
6909 if (code != NOTE && num_insns++ > 1000)
6911 flush_hash_table ();
6915 /* See if this is a branch that is part of the path. If so, and it is
6916 to be taken, do so. */
6917 if (next_branch->branch == insn)
6919 enum taken status = next_branch++->status;
6920 if (status != NOT_TAKEN)
6922 if (status == TAKEN)
6923 record_jump_equiv (insn, 1);
6925 invalidate_skipped_block (NEXT_INSN (insn));
6927 /* Set the last insn as the jump insn; it doesn't affect cc0.
6928 Then follow this branch. */
6933 insn = JUMP_LABEL (insn);
6938 if (GET_MODE (insn) == QImode)
6939 PUT_MODE (insn, VOIDmode);
6941 if (GET_RTX_CLASS (code) == 'i')
6945 /* Process notes first so we have all notes in canonical forms when
6946 looking for duplicate operations. */
6948 if (REG_NOTES (insn))
6949 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
6951 /* Track when we are inside in LIBCALL block. Inside such a block,
6952 we do not want to record destinations. The last insn of a
6953 LIBCALL block is not considered to be part of the block, since
6954 its destination is the result of the block and hence should be
6957 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
6958 libcall_insn = XEXP (p, 0);
6959 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
6960 libcall_insn = NULL_RTX;
6962 cse_insn (insn, libcall_insn);
6965 /* If INSN is now an unconditional jump, skip to the end of our
6966 basic block by pretending that we just did the last insn in the
6967 basic block. If we are jumping to the end of our block, show
6968 that we can have one usage of TO. */
6970 if (simplejump_p (insn))
6975 if (JUMP_LABEL (insn) == to)
6978 /* Maybe TO was deleted because the jump is unconditional.
6979 If so, there is nothing left in this basic block. */
6980 /* ??? Perhaps it would be smarter to set TO
6981 to whatever follows this insn,
6982 and pretend the basic block had always ended here. */
6983 if (INSN_DELETED_P (to))
6986 insn = PREV_INSN (to);
6989 /* See if it is ok to keep on going past the label
6990 which used to end our basic block. Remember that we incremented
6991 the count of that label, so we decrement it here. If we made
6992 a jump unconditional, TO_USAGE will be one; in that case, we don't
6993 want to count the use in that jump. */
6995 if (to != 0 && NEXT_INSN (insn) == to
6996 && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
6998 struct cse_basic_block_data val;
7001 insn = NEXT_INSN (to);
7003 /* If TO was the last insn in the function, we are done. */
7007 /* If TO was preceded by a BARRIER we are done with this block
7008 because it has no continuation. */
7009 prev = prev_nonnote_insn (to);
7010 if (prev && GET_CODE (prev) == BARRIER)
7013 /* Find the end of the following block. Note that we won't be
7014 following branches in this case. */
7017 cse_end_of_basic_block (insn, &val, 0, 0, 0);
7019 /* If the tables we allocated have enough space left
7020 to handle all the SETs in the next basic block,
7021 continue through it. Otherwise, return,
7022 and that block will be scanned individually. */
7023 if (val.nsets * 2 + next_qty > max_qty)
7026 cse_basic_block_start = val.low_cuid;
7027 cse_basic_block_end = val.high_cuid;
7030 /* Prevent TO from being deleted if it is a label. */
7031 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7034 /* Back up so we process the first insn in the extension. */
7035 insn = PREV_INSN (insn);
7039 if (next_qty > max_qty)
7042 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7043 the previous insn is the only insn that branches to the head of a loop,
7044 we can cse into the loop. Don't do this if we changed the jump
7045 structure of a loop unless we aren't going to be following jumps. */
7047 if ((cse_jumps_altered == 0
7048 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7049 && around_loop && to != 0
7050 && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
7051 && GET_CODE (PREV_INSN (to)) == JUMP_INSN
7052 && JUMP_LABEL (PREV_INSN (to)) != 0
7053 && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
7054 cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
7056 free (qty_table + max_reg);
7058 return to ? NEXT_INSN (to) : 0;
7061 /* Count the number of times registers are used (not set) in X.
7062 COUNTS is an array in which we accumulate the count, INCR is how much
7063 we count each register usage.
7065 Don't count a usage of DEST, which is the SET_DEST of a SET which
7066 contains X in its SET_SRC. This is because such a SET does not
7067 modify the liveness of DEST. */
7070 count_reg_usage (x, counts, dest, incr)
7083 switch (code = GET_CODE (x))
7087 counts[REGNO (x)] += incr;
7100 /* If we are clobbering a MEM, mark any registers inside the address
7102 if (GET_CODE (XEXP (x, 0)) == MEM)
7103 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
7107 /* Unless we are setting a REG, count everything in SET_DEST. */
7108 if (GET_CODE (SET_DEST (x)) != REG)
7109 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
7111 /* If SRC has side-effects, then we can't delete this insn, so the
7112 usage of SET_DEST inside SRC counts.
7114 ??? Strictly-speaking, we might be preserving this insn
7115 because some other SET has side-effects, but that's hard
7116 to do and can't happen now. */
7117 count_reg_usage (SET_SRC (x), counts,
7118 side_effects_p (SET_SRC (x)) ? NULL_RTX : SET_DEST (x),
7123 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr);
7125 /* ... falls through ... */
7128 count_reg_usage (PATTERN (x), counts, NULL_RTX, incr);
7130 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7133 count_reg_usage (REG_NOTES (x), counts, NULL_RTX, incr);
7138 if (REG_NOTE_KIND (x) == REG_EQUAL
7139 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE))
7140 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
7141 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
7148 fmt = GET_RTX_FORMAT (code);
7149 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
7152 count_reg_usage (XEXP (x, i), counts, dest, incr);
7153 else if (fmt[i] == 'E')
7154 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7155 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
7159 /* Scan all the insns and delete any that are dead; i.e., they store a register
7160 that is never used or they copy a register to itself.
7162 This is used to remove insns made obviously dead by cse, loop or other
7163 optimizations. It improves the heuristics in loop since it won't try to
7164 move dead invariants out of loops or make givs for dead quantities. The
7165 remaining passes of the compilation are also sped up. */
7168 delete_trivially_dead_insns (insns, nreg)
7178 int in_libcall = 0, dead_libcall = 0;
7180 /* First count the number of times each register is used. */
7181 counts = (int *) xcalloc (nreg, sizeof (int));
7182 for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
7183 count_reg_usage (insn, counts, NULL_RTX, 1);
7185 /* Go from the last insn to the first and delete insns that only set unused
7186 registers or copy a register to itself. As we delete an insn, remove
7187 usage counts for registers it uses.
7189 The first jump optimization pass may leave a real insn as the last
7190 insn in the function. We must not skip that insn or we may end
7191 up deleting code that is not really dead. */
7192 insn = get_last_insn ();
7193 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7194 insn = prev_real_insn (insn);
7196 for ( ; insn; insn = prev)
7201 prev = prev_real_insn (insn);
7203 /* Don't delete any insns that are part of a libcall block unless
7204 we can delete the whole libcall block.
7206 Flow or loop might get confused if we did that. Remember
7207 that we are scanning backwards. */
7208 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7214 /* See if there's a REG_EQUAL note on this insn and try to
7215 replace the source with the REG_EQUAL expression.
7217 We assume that insns with REG_RETVALs can only be reg->reg
7218 copies at this point. */
7219 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
7222 rtx set = single_set (insn);
7223 rtx new = simplify_rtx (XEXP (note, 0));
7226 new = XEXP (note, 0);
7228 if (set && validate_change (insn, &SET_SRC (set), new, 0))
7231 find_reg_note (insn, REG_RETVAL, NULL_RTX));
7236 else if (in_libcall)
7237 live_insn = ! dead_libcall;
7238 else if (GET_CODE (PATTERN (insn)) == SET)
7240 if ((GET_CODE (SET_DEST (PATTERN (insn))) == REG
7241 || GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG)
7242 && rtx_equal_p (SET_DEST (PATTERN (insn)),
7243 SET_SRC (PATTERN (insn))))
7247 else if (GET_CODE (SET_DEST (PATTERN (insn))) == CC0
7248 && ! side_effects_p (SET_SRC (PATTERN (insn)))
7249 && ((tem = next_nonnote_insn (insn)) == 0
7250 || GET_RTX_CLASS (GET_CODE (tem)) != 'i'
7251 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
7254 else if (GET_CODE (SET_DEST (PATTERN (insn))) != REG
7255 || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER
7256 || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0
7257 || side_effects_p (SET_SRC (PATTERN (insn)))
7258 /* An ADDRESSOF expression can turn into a use of the
7259 internal arg pointer, so always consider the
7260 internal arg pointer live. If it is truly dead,
7261 flow will delete the initializing insn. */
7262 || (SET_DEST (PATTERN (insn))
7263 == current_function_internal_arg_pointer))
7266 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
7267 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
7269 rtx elt = XVECEXP (PATTERN (insn), 0, i);
7271 if (GET_CODE (elt) == SET)
7273 if ((GET_CODE (SET_DEST (elt)) == REG
7274 || GET_CODE (SET_DEST (elt)) == SUBREG)
7275 && rtx_equal_p (SET_DEST (elt), SET_SRC (elt)))
7279 else if (GET_CODE (SET_DEST (elt)) == CC0
7280 && ! side_effects_p (SET_SRC (elt))
7281 && ((tem = next_nonnote_insn (insn)) == 0
7282 || GET_RTX_CLASS (GET_CODE (tem)) != 'i'
7283 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
7286 else if (GET_CODE (SET_DEST (elt)) != REG
7287 || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER
7288 || counts[REGNO (SET_DEST (elt))] != 0
7289 || side_effects_p (SET_SRC (elt))
7290 /* An ADDRESSOF expression can turn into a use of the
7291 internal arg pointer, so always consider the
7292 internal arg pointer live. If it is truly dead,
7293 flow will delete the initializing insn. */
7295 == current_function_internal_arg_pointer))
7298 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
7304 /* If this is a dead insn, delete it and show registers in it aren't
7309 count_reg_usage (insn, counts, NULL_RTX, -1);
7313 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))