1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 /* stdio.h must precede rtl.h for FFS. */
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
34 #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 unsigned 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 /* Next in hash chain. */
299 struct cse_reg_info *hash_next;
301 /* The next cse_reg_info structure in the free or used list. */
302 struct cse_reg_info *next;
307 /* The quantity number of the register's current contents. */
310 /* The number of times the register has been altered in the current
314 /* The REG_TICK value at which rtx's containing this register are
315 valid in the hash table. If this does not equal the current
316 reg_tick value, such expressions existing in the hash table are
321 /* A free list of cse_reg_info entries. */
322 static struct cse_reg_info *cse_reg_info_free_list;
324 /* A used list of cse_reg_info entries. */
325 static struct cse_reg_info *cse_reg_info_used_list;
326 static struct cse_reg_info *cse_reg_info_used_list_end;
328 /* A mapping from registers to cse_reg_info data structures. */
329 #define REGHASH_SHIFT 7
330 #define REGHASH_SIZE (1 << REGHASH_SHIFT)
331 #define REGHASH_MASK (REGHASH_SIZE - 1)
332 static struct cse_reg_info *reg_hash[REGHASH_SIZE];
334 #define REGHASH_FN(REGNO) \
335 (((REGNO) ^ ((REGNO) >> REGHASH_SHIFT)) & REGHASH_MASK)
337 /* The last lookup we did into the cse_reg_info_tree. This allows us
338 to cache repeated lookups. */
339 static unsigned int cached_regno;
340 static struct cse_reg_info *cached_cse_reg_info;
342 /* A HARD_REG_SET containing all the hard registers for which there is
343 currently a REG expression in the hash table. Note the difference
344 from the above variables, which indicate if the REG is mentioned in some
345 expression in the table. */
347 static HARD_REG_SET hard_regs_in_table;
349 /* A HARD_REG_SET containing all the hard registers that are invalidated
352 static HARD_REG_SET regs_invalidated_by_call;
354 /* CUID of insn that starts the basic block currently being cse-processed. */
356 static int cse_basic_block_start;
358 /* CUID of insn that ends the basic block currently being cse-processed. */
360 static int cse_basic_block_end;
362 /* Vector mapping INSN_UIDs to cuids.
363 The cuids are like uids but increase monotonically always.
364 We use them to see whether a reg is used outside a given basic block. */
366 static int *uid_cuid;
368 /* Highest UID in UID_CUID. */
371 /* Get the cuid of an insn. */
373 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
375 /* Nonzero if this pass has made changes, and therefore it's
376 worthwhile to run the garbage collector. */
378 static int cse_altered;
380 /* Nonzero if cse has altered conditional jump insns
381 in such a way that jump optimization should be redone. */
383 static int cse_jumps_altered;
385 /* Nonzero if we put a LABEL_REF into the hash table. Since we may have put
386 it into an INSN without a REG_LABEL, we have to rerun jump after CSE
387 to put in the note. */
388 static int recorded_label_ref;
390 /* canon_hash stores 1 in do_not_record
391 if it notices a reference to CC0, PC, or some other volatile
394 static int do_not_record;
396 #ifdef LOAD_EXTEND_OP
398 /* Scratch rtl used when looking for load-extended copy of a MEM. */
399 static rtx memory_extend_rtx;
402 /* canon_hash stores 1 in hash_arg_in_memory
403 if it notices a reference to memory within the expression being hashed. */
405 static int hash_arg_in_memory;
407 /* The hash table contains buckets which are chains of `struct table_elt's,
408 each recording one expression's information.
409 That expression is in the `exp' field.
411 The canon_exp field contains a canonical (from the point of view of
412 alias analysis) version of the `exp' field.
414 Those elements with the same hash code are chained in both directions
415 through the `next_same_hash' and `prev_same_hash' fields.
417 Each set of expressions with equivalent values
418 are on a two-way chain through the `next_same_value'
419 and `prev_same_value' fields, and all point with
420 the `first_same_value' field at the first element in
421 that chain. The chain is in order of increasing cost.
422 Each element's cost value is in its `cost' field.
424 The `in_memory' field is nonzero for elements that
425 involve any reference to memory. These elements are removed
426 whenever a write is done to an unidentified location in memory.
427 To be safe, we assume that a memory address is unidentified unless
428 the address is either a symbol constant or a constant plus
429 the frame pointer or argument pointer.
431 The `related_value' field is used to connect related expressions
432 (that differ by adding an integer).
433 The related expressions are chained in a circular fashion.
434 `related_value' is zero for expressions for which this
437 The `cost' field stores the cost of this element's expression.
438 The `regcost' field stores the value returned by approx_reg_cost for
439 this element's expression.
441 The `is_const' flag is set if the element is a constant (including
444 The `flag' field is used as a temporary during some search routines.
446 The `mode' field is usually the same as GET_MODE (`exp'), but
447 if `exp' is a CONST_INT and has no machine mode then the `mode'
448 field is the mode it was being used as. Each constant is
449 recorded separately for each mode it is used with. */
455 struct table_elt *next_same_hash;
456 struct table_elt *prev_same_hash;
457 struct table_elt *next_same_value;
458 struct table_elt *prev_same_value;
459 struct table_elt *first_same_value;
460 struct table_elt *related_value;
463 enum machine_mode mode;
469 /* We don't want a lot of buckets, because we rarely have very many
470 things stored in the hash table, and a lot of buckets slows
471 down a lot of loops that happen frequently. */
473 #define HASH_SIZE (1 << HASH_SHIFT)
474 #define HASH_MASK (HASH_SIZE - 1)
476 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
477 register (hard registers may require `do_not_record' to be set). */
480 ((GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
481 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
482 : canon_hash (X, M)) & HASH_MASK)
484 /* Determine whether register number N is considered a fixed register for the
485 purpose of approximating register costs.
486 It is desirable to replace other regs with fixed regs, to reduce need for
488 A reg wins if it is either the frame pointer or designated as fixed. */
489 #define FIXED_REGNO_P(N) \
490 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
491 || fixed_regs[N] || global_regs[N])
493 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
494 hard registers and pointers into the frame are the cheapest with a cost
495 of 0. Next come pseudos with a cost of one and other hard registers with
496 a cost of 2. Aside from these special cases, call `rtx_cost'. */
498 #define CHEAP_REGNO(N) \
499 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
500 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
501 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
502 || ((N) < FIRST_PSEUDO_REGISTER \
503 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
505 #define COST(X) (GET_CODE (X) == REG ? 0 : notreg_cost (X, SET))
506 #define COST_IN(X,OUTER) (GET_CODE (X) == REG ? 0 : notreg_cost (X, OUTER))
508 /* Get the info associated with register N. */
510 #define GET_CSE_REG_INFO(N) \
511 (((N) == cached_regno && cached_cse_reg_info) \
512 ? cached_cse_reg_info : get_cse_reg_info ((N)))
514 /* Get the number of times this register has been updated in this
517 #define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
519 /* Get the point at which REG was recorded in the table. */
521 #define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
523 /* Get the quantity number for REG. */
525 #define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
527 /* Determine if the quantity number for register X represents a valid index
528 into the qty_table. */
530 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (int) (N))
532 static struct table_elt *table[HASH_SIZE];
534 /* Chain of `struct table_elt's made so far for this function
535 but currently removed from the table. */
537 static struct table_elt *free_element_chain;
539 /* Number of `struct table_elt' structures made so far for this function. */
541 static int n_elements_made;
543 /* Maximum value `n_elements_made' has had so far in this compilation
544 for functions previously processed. */
546 static int max_elements_made;
548 /* Surviving equivalence class when two equivalence classes are merged
549 by recording the effects of a jump in the last insn. Zero if the
550 last insn was not a conditional jump. */
552 static struct table_elt *last_jump_equiv_class;
554 /* Set to the cost of a constant pool reference if one was found for a
555 symbolic constant. If this was found, it means we should try to
556 convert constants into constant pool entries if they don't fit in
559 static int constant_pool_entries_cost;
561 /* Define maximum length of a branch path. */
563 #define PATHLENGTH 10
565 /* This data describes a block that will be processed by cse_basic_block. */
567 struct cse_basic_block_data
569 /* Lowest CUID value of insns in block. */
571 /* Highest CUID value of insns in block. */
573 /* Total number of SETs in block. */
575 /* Last insn in the block. */
577 /* Size of current branch path, if any. */
579 /* Current branch path, indicating which branches will be taken. */
582 /* The branch insn. */
584 /* Whether it should be taken or not. AROUND is the same as taken
585 except that it is used when the destination label is not preceded
587 enum taken {TAKEN, NOT_TAKEN, AROUND} status;
591 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
592 virtual regs here because the simplify_*_operation routines are called
593 by integrate.c, which is called before virtual register instantiation.
595 ?!? FIXED_BASE_PLUS_P and NONZERO_BASE_PLUS_P need to move into
596 a header file so that their definitions can be shared with the
597 simplification routines in simplify-rtx.c. Until then, do not
598 change these macros without also changing the copy in simplify-rtx.c. */
600 #define FIXED_BASE_PLUS_P(X) \
601 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
602 || ((X) == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])\
603 || (X) == virtual_stack_vars_rtx \
604 || (X) == virtual_incoming_args_rtx \
605 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
606 && (XEXP (X, 0) == frame_pointer_rtx \
607 || XEXP (X, 0) == hard_frame_pointer_rtx \
608 || ((X) == arg_pointer_rtx \
609 && fixed_regs[ARG_POINTER_REGNUM]) \
610 || XEXP (X, 0) == virtual_stack_vars_rtx \
611 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
612 || GET_CODE (X) == ADDRESSOF)
614 /* Similar, but also allows reference to the stack pointer.
616 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
617 arg_pointer_rtx by itself is nonzero, because on at least one machine,
618 the i960, the arg pointer is zero when it is unused. */
620 #define NONZERO_BASE_PLUS_P(X) \
621 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
622 || (X) == virtual_stack_vars_rtx \
623 || (X) == virtual_incoming_args_rtx \
624 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
625 && (XEXP (X, 0) == frame_pointer_rtx \
626 || XEXP (X, 0) == hard_frame_pointer_rtx \
627 || ((X) == arg_pointer_rtx \
628 && fixed_regs[ARG_POINTER_REGNUM]) \
629 || XEXP (X, 0) == virtual_stack_vars_rtx \
630 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
631 || (X) == stack_pointer_rtx \
632 || (X) == virtual_stack_dynamic_rtx \
633 || (X) == virtual_outgoing_args_rtx \
634 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
635 && (XEXP (X, 0) == stack_pointer_rtx \
636 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
637 || XEXP (X, 0) == virtual_outgoing_args_rtx)) \
638 || GET_CODE (X) == ADDRESSOF)
640 static int notreg_cost PARAMS ((rtx, enum rtx_code));
641 static int approx_reg_cost_1 PARAMS ((rtx *, void *));
642 static int approx_reg_cost PARAMS ((rtx));
643 static int preferrable PARAMS ((int, int, int, int));
644 static void new_basic_block PARAMS ((void));
645 static void make_new_qty PARAMS ((unsigned int, enum machine_mode));
646 static void make_regs_eqv PARAMS ((unsigned int, unsigned int));
647 static void delete_reg_equiv PARAMS ((unsigned int));
648 static int mention_regs PARAMS ((rtx));
649 static int insert_regs PARAMS ((rtx, struct table_elt *, int));
650 static void remove_from_table PARAMS ((struct table_elt *, unsigned));
651 static struct table_elt *lookup PARAMS ((rtx, unsigned, enum machine_mode)),
652 *lookup_for_remove PARAMS ((rtx, unsigned, enum machine_mode));
653 static rtx lookup_as_function PARAMS ((rtx, enum rtx_code));
654 static struct table_elt *insert PARAMS ((rtx, struct table_elt *, unsigned,
656 static void merge_equiv_classes PARAMS ((struct table_elt *,
657 struct table_elt *));
658 static void invalidate PARAMS ((rtx, enum machine_mode));
659 static int cse_rtx_varies_p PARAMS ((rtx));
660 static void remove_invalid_refs PARAMS ((unsigned int));
661 static void remove_invalid_subreg_refs PARAMS ((unsigned int, unsigned int,
663 static void rehash_using_reg PARAMS ((rtx));
664 static void invalidate_memory PARAMS ((void));
665 static void invalidate_for_call PARAMS ((void));
666 static rtx use_related_value PARAMS ((rtx, struct table_elt *));
667 static unsigned canon_hash PARAMS ((rtx, enum machine_mode));
668 static unsigned canon_hash_string PARAMS ((const char *));
669 static unsigned safe_hash PARAMS ((rtx, enum machine_mode));
670 static int exp_equiv_p PARAMS ((rtx, rtx, int, int));
671 static rtx canon_reg PARAMS ((rtx, rtx));
672 static void find_best_addr PARAMS ((rtx, rtx *, enum machine_mode));
673 static enum rtx_code find_comparison_args PARAMS ((enum rtx_code, rtx *, rtx *,
675 enum machine_mode *));
676 static rtx fold_rtx PARAMS ((rtx, rtx));
677 static rtx equiv_constant PARAMS ((rtx));
678 static void record_jump_equiv PARAMS ((rtx, int));
679 static void record_jump_cond PARAMS ((enum rtx_code, enum machine_mode,
681 static void cse_insn PARAMS ((rtx, rtx));
682 static int addr_affects_sp_p PARAMS ((rtx));
683 static void invalidate_from_clobbers PARAMS ((rtx));
684 static rtx cse_process_notes PARAMS ((rtx, rtx));
685 static void cse_around_loop PARAMS ((rtx));
686 static void invalidate_skipped_set PARAMS ((rtx, rtx, void *));
687 static void invalidate_skipped_block PARAMS ((rtx));
688 static void cse_check_loop_start PARAMS ((rtx, rtx, void *));
689 static void cse_set_around_loop PARAMS ((rtx, rtx, rtx));
690 static rtx cse_basic_block PARAMS ((rtx, rtx, struct branch_path *, int));
691 static void count_reg_usage PARAMS ((rtx, int *, rtx, int));
692 extern void dump_class PARAMS ((struct table_elt*));
693 static struct cse_reg_info * get_cse_reg_info PARAMS ((unsigned int));
694 static int check_dependence PARAMS ((rtx *, void *));
696 static void flush_hash_table PARAMS ((void));
698 /* Dump the expressions in the equivalence class indicated by CLASSP.
699 This function is used only for debugging. */
702 struct table_elt *classp;
704 struct table_elt *elt;
706 fprintf (stderr, "Equivalence chain for ");
707 print_rtl (stderr, classp->exp);
708 fprintf (stderr, ": \n");
710 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
712 print_rtl (stderr, elt->exp);
713 fprintf (stderr, "\n");
717 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
719 approx_reg_cost_1 (xp, data)
724 regset set = (regset) data;
726 if (x && GET_CODE (x) == REG)
727 SET_REGNO_REG_SET (set, REGNO (x));
731 /* Return an estimate of the cost of the registers used in an rtx.
732 This is mostly the number of different REG expressions in the rtx;
733 however for some excecptions like fixed registers we use a cost of
734 0. If any other hard register reference occurs, return MAX_COST. */
746 for_each_rtx (&x, approx_reg_cost_1, (void *)&set);
748 EXECUTE_IF_SET_IN_REG_SET
751 if (! CHEAP_REGNO (i))
753 if (i < FIRST_PSEUDO_REGISTER)
756 cost += i < FIRST_PSEUDO_REGISTER ? 2 : 1;
760 CLEAR_REG_SET (&set);
761 return hardregs && SMALL_REGISTER_CLASSES ? MAX_COST : cost;
764 /* Return a negative value if an rtx A, whose costs are given by COST_A
765 and REGCOST_A, is more desirable than an rtx B.
766 Return a positive value if A is less desirable, or 0 if the two are
769 preferrable (cost_a, regcost_a, cost_b, regcost_b)
770 int cost_a, regcost_a, cost_b, regcost_b;
772 /* First, get rid of a cases involving expressions that are entirely
774 if (cost_a != cost_b)
776 if (cost_a == MAX_COST)
778 if (cost_b == MAX_COST)
782 /* Avoid extending lifetimes of hardregs. */
783 if (regcost_a != regcost_b)
785 if (regcost_a == MAX_COST)
787 if (regcost_b == MAX_COST)
791 /* Normal operation costs take precedence. */
792 if (cost_a != cost_b)
793 return cost_a - cost_b;
794 /* Only if these are identical consider effects on register pressure. */
795 if (regcost_a != regcost_b)
796 return regcost_a - regcost_b;
800 /* Internal function, to compute cost when X is not a register; called
801 from COST macro to keep it simple. */
804 notreg_cost (x, outer)
808 return ((GET_CODE (x) == SUBREG
809 && GET_CODE (SUBREG_REG (x)) == REG
810 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
811 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
812 && (GET_MODE_SIZE (GET_MODE (x))
813 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
814 && subreg_lowpart_p (x)
815 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
816 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
818 : rtx_cost (x, outer) * 2);
821 /* Return an estimate of the cost of computing rtx X.
822 One use is in cse, to decide which expression to keep in the hash table.
823 Another is in rtl generation, to pick the cheapest way to multiply.
824 Other uses like the latter are expected in the future. */
827 rtx_cost (x, outer_code)
829 enum rtx_code outer_code ATTRIBUTE_UNUSED;
832 register enum rtx_code code;
833 register const char *fmt;
839 /* Compute the default costs of certain things.
840 Note that RTX_COSTS can override the defaults. */
846 /* Count multiplication by 2**n as a shift,
847 because if we are considering it, we would output it as a shift. */
848 if (GET_CODE (XEXP (x, 1)) == CONST_INT
849 && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
852 total = COSTS_N_INSNS (5);
858 total = COSTS_N_INSNS (7);
861 /* Used in loop.c and combine.c as a marker. */
865 total = COSTS_N_INSNS (1);
874 /* If we can't tie these modes, make this expensive. The larger
875 the mode, the more expensive it is. */
876 if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
877 return COSTS_N_INSNS (2
878 + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
882 RTX_COSTS (x, code, outer_code);
885 CONST_COSTS (x, code, outer_code);
889 #ifdef DEFAULT_RTX_COSTS
890 DEFAULT_RTX_COSTS (x, code, outer_code);
895 /* Sum the costs of the sub-rtx's, plus cost of this operation,
896 which is already in total. */
898 fmt = GET_RTX_FORMAT (code);
899 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
901 total += rtx_cost (XEXP (x, i), code);
902 else if (fmt[i] == 'E')
903 for (j = 0; j < XVECLEN (x, i); j++)
904 total += rtx_cost (XVECEXP (x, i, j), code);
909 /* Return cost of address expression X.
910 Expect that X is propertly formed address reference. */
913 address_cost (x, mode)
915 enum machine_mode mode;
917 /* The ADDRESS_COST macro does not deal with ADDRESSOF nodes. But,
918 during CSE, such nodes are present. Using an ADDRESSOF node which
919 refers to the address of a REG is a good thing because we can then
920 turn (MEM (ADDRESSSOF (REG))) into just plain REG. */
922 if (GET_CODE (x) == ADDRESSOF && REG_P (XEXP ((x), 0)))
925 /* We may be asked for cost of various unusual addresses, such as operands
926 of push instruction. It is not worthwhile to complicate writing
927 of ADDRESS_COST macro by such cases. */
929 if (!memory_address_p (mode, x))
932 return ADDRESS_COST (x);
934 return rtx_cost (x, MEM);
939 static struct cse_reg_info *
940 get_cse_reg_info (regno)
943 struct cse_reg_info **hash_head = ®_hash[REGHASH_FN (regno)];
944 struct cse_reg_info *p;
946 for (p = *hash_head; p != NULL; p = p->hash_next)
947 if (p->regno == regno)
952 /* Get a new cse_reg_info structure. */
953 if (cse_reg_info_free_list)
955 p = cse_reg_info_free_list;
956 cse_reg_info_free_list = p->next;
959 p = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info));
961 /* Insert into hash table. */
962 p->hash_next = *hash_head;
967 p->reg_in_table = -1;
970 p->next = cse_reg_info_used_list;
971 cse_reg_info_used_list = p;
972 if (!cse_reg_info_used_list_end)
973 cse_reg_info_used_list_end = p;
976 /* Cache this lookup; we tend to be looking up information about the
977 same register several times in a row. */
978 cached_regno = regno;
979 cached_cse_reg_info = p;
984 /* Clear the hash table and initialize each register with its own quantity,
985 for a new basic block. */
994 /* Clear out hash table state for this pass. */
996 bzero ((char *) reg_hash, sizeof reg_hash);
998 if (cse_reg_info_used_list)
1000 cse_reg_info_used_list_end->next = cse_reg_info_free_list;
1001 cse_reg_info_free_list = cse_reg_info_used_list;
1002 cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
1004 cached_cse_reg_info = 0;
1006 CLEAR_HARD_REG_SET (hard_regs_in_table);
1008 /* The per-quantity values used to be initialized here, but it is
1009 much faster to initialize each as it is made in `make_new_qty'. */
1011 for (i = 0; i < HASH_SIZE; i++)
1013 struct table_elt *first;
1018 struct table_elt *last = first;
1022 while (last->next_same_hash != NULL)
1023 last = last->next_same_hash;
1025 /* Now relink this hash entire chain into
1026 the free element list. */
1028 last->next_same_hash = free_element_chain;
1029 free_element_chain = first;
1040 /* Say that register REG contains a quantity in mode MODE not in any
1041 register before and initialize that quantity. */
1044 make_new_qty (reg, mode)
1046 enum machine_mode mode;
1049 register struct qty_table_elem *ent;
1050 register struct reg_eqv_elem *eqv;
1052 if (next_qty >= max_qty)
1055 q = REG_QTY (reg) = next_qty++;
1056 ent = &qty_table[q];
1057 ent->first_reg = reg;
1058 ent->last_reg = reg;
1060 ent->const_rtx = ent->const_insn = NULL_RTX;
1061 ent->comparison_code = UNKNOWN;
1063 eqv = ®_eqv_table[reg];
1064 eqv->next = eqv->prev = -1;
1067 /* Make reg NEW equivalent to reg OLD.
1068 OLD is not changing; NEW is. */
1071 make_regs_eqv (new, old)
1072 unsigned int new, old;
1074 unsigned int lastr, firstr;
1075 int q = REG_QTY (old);
1076 struct qty_table_elem *ent;
1078 ent = &qty_table[q];
1080 /* Nothing should become eqv until it has a "non-invalid" qty number. */
1081 if (! REGNO_QTY_VALID_P (old))
1085 firstr = ent->first_reg;
1086 lastr = ent->last_reg;
1088 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
1089 hard regs. Among pseudos, if NEW will live longer than any other reg
1090 of the same qty, and that is beyond the current basic block,
1091 make it the new canonical replacement for this qty. */
1092 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
1093 /* Certain fixed registers might be of the class NO_REGS. This means
1094 that not only can they not be allocated by the compiler, but
1095 they cannot be used in substitutions or canonicalizations
1097 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
1098 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
1099 || (new >= FIRST_PSEUDO_REGISTER
1100 && (firstr < FIRST_PSEUDO_REGISTER
1101 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
1102 || (uid_cuid[REGNO_FIRST_UID (new)]
1103 < cse_basic_block_start))
1104 && (uid_cuid[REGNO_LAST_UID (new)]
1105 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
1107 reg_eqv_table[firstr].prev = new;
1108 reg_eqv_table[new].next = firstr;
1109 reg_eqv_table[new].prev = -1;
1110 ent->first_reg = new;
1114 /* If NEW is a hard reg (known to be non-fixed), insert at end.
1115 Otherwise, insert before any non-fixed hard regs that are at the
1116 end. Registers of class NO_REGS cannot be used as an
1117 equivalent for anything. */
1118 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
1119 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
1120 && new >= FIRST_PSEUDO_REGISTER)
1121 lastr = reg_eqv_table[lastr].prev;
1122 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
1123 if (reg_eqv_table[lastr].next >= 0)
1124 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
1126 qty_table[q].last_reg = new;
1127 reg_eqv_table[lastr].next = new;
1128 reg_eqv_table[new].prev = lastr;
1132 /* Remove REG from its equivalence class. */
1135 delete_reg_equiv (reg)
1138 register struct qty_table_elem *ent;
1139 register int q = REG_QTY (reg);
1142 /* If invalid, do nothing. */
1146 ent = &qty_table[q];
1148 p = reg_eqv_table[reg].prev;
1149 n = reg_eqv_table[reg].next;
1152 reg_eqv_table[n].prev = p;
1156 reg_eqv_table[p].next = n;
1160 REG_QTY (reg) = reg;
1163 /* Remove any invalid expressions from the hash table
1164 that refer to any of the registers contained in expression X.
1166 Make sure that newly inserted references to those registers
1167 as subexpressions will be considered valid.
1169 mention_regs is not called when a register itself
1170 is being stored in the table.
1172 Return 1 if we have done something that may have changed the hash code
1179 register enum rtx_code code;
1181 register const char *fmt;
1182 register int changed = 0;
1187 code = GET_CODE (x);
1190 unsigned int regno = REGNO (x);
1191 unsigned int endregno
1192 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1193 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
1196 for (i = regno; i < endregno; i++)
1198 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1199 remove_invalid_refs (i);
1201 REG_IN_TABLE (i) = REG_TICK (i);
1207 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1208 pseudo if they don't use overlapping words. We handle only pseudos
1209 here for simplicity. */
1210 if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1211 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1213 unsigned int i = REGNO (SUBREG_REG (x));
1215 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1217 /* If reg_tick has been incremented more than once since
1218 reg_in_table was last set, that means that the entire
1219 register has been set before, so discard anything memorized
1220 for the entrire register, including all SUBREG expressions. */
1221 if (REG_IN_TABLE (i) != REG_TICK (i) - 1)
1222 remove_invalid_refs (i);
1224 remove_invalid_subreg_refs (i, SUBREG_WORD (x), GET_MODE (x));
1227 REG_IN_TABLE (i) = REG_TICK (i);
1231 /* If X is a comparison or a COMPARE and either operand is a register
1232 that does not have a quantity, give it one. This is so that a later
1233 call to record_jump_equiv won't cause X to be assigned a different
1234 hash code and not found in the table after that call.
1236 It is not necessary to do this here, since rehash_using_reg can
1237 fix up the table later, but doing this here eliminates the need to
1238 call that expensive function in the most common case where the only
1239 use of the register is in the comparison. */
1241 if (code == COMPARE || GET_RTX_CLASS (code) == '<')
1243 if (GET_CODE (XEXP (x, 0)) == REG
1244 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1245 if (insert_regs (XEXP (x, 0), NULL_PTR, 0))
1247 rehash_using_reg (XEXP (x, 0));
1251 if (GET_CODE (XEXP (x, 1)) == REG
1252 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1253 if (insert_regs (XEXP (x, 1), NULL_PTR, 0))
1255 rehash_using_reg (XEXP (x, 1));
1260 fmt = GET_RTX_FORMAT (code);
1261 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1263 changed |= mention_regs (XEXP (x, i));
1264 else if (fmt[i] == 'E')
1265 for (j = 0; j < XVECLEN (x, i); j++)
1266 changed |= mention_regs (XVECEXP (x, i, j));
1271 /* Update the register quantities for inserting X into the hash table
1272 with a value equivalent to CLASSP.
1273 (If the class does not contain a REG, it is irrelevant.)
1274 If MODIFIED is nonzero, X is a destination; it is being modified.
1275 Note that delete_reg_equiv should be called on a register
1276 before insert_regs is done on that register with MODIFIED != 0.
1278 Nonzero value means that elements of reg_qty have changed
1279 so X's hash code may be different. */
1282 insert_regs (x, classp, modified)
1284 struct table_elt *classp;
1287 if (GET_CODE (x) == REG)
1289 unsigned int regno = REGNO (x);
1292 /* If REGNO is in the equivalence table already but is of the
1293 wrong mode for that equivalence, don't do anything here. */
1295 qty_valid = REGNO_QTY_VALID_P (regno);
1298 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1300 if (ent->mode != GET_MODE (x))
1304 if (modified || ! qty_valid)
1307 for (classp = classp->first_same_value;
1309 classp = classp->next_same_value)
1310 if (GET_CODE (classp->exp) == REG
1311 && GET_MODE (classp->exp) == GET_MODE (x))
1313 make_regs_eqv (regno, REGNO (classp->exp));
1317 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1318 than REG_IN_TABLE to find out if there was only a single preceding
1319 invalidation - for the SUBREG - or another one, which would be
1320 for the full register. However, if we find here that REG_TICK
1321 indicates that the register is invalid, it means that it has
1322 been invalidated in a separate operation. The SUBREG might be used
1323 now (then this is a recursive call), or we might use the full REG
1324 now and a SUBREG of it later. So bump up REG_TICK so that
1325 mention_regs will do the right thing. */
1327 && REG_IN_TABLE (regno) >= 0
1328 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1330 make_new_qty (regno, GET_MODE (x));
1337 /* If X is a SUBREG, we will likely be inserting the inner register in the
1338 table. If that register doesn't have an assigned quantity number at
1339 this point but does later, the insertion that we will be doing now will
1340 not be accessible because its hash code will have changed. So assign
1341 a quantity number now. */
1343 else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1344 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1346 insert_regs (SUBREG_REG (x), NULL_PTR, 0);
1351 return mention_regs (x);
1354 /* Look in or update the hash table. */
1356 /* Remove table element ELT from use in the table.
1357 HASH is its hash code, made using the HASH macro.
1358 It's an argument because often that is known in advance
1359 and we save much time not recomputing it. */
1362 remove_from_table (elt, hash)
1363 register struct table_elt *elt;
1369 /* Mark this element as removed. See cse_insn. */
1370 elt->first_same_value = 0;
1372 /* Remove the table element from its equivalence class. */
1375 register struct table_elt *prev = elt->prev_same_value;
1376 register struct table_elt *next = elt->next_same_value;
1379 next->prev_same_value = prev;
1382 prev->next_same_value = next;
1385 register struct table_elt *newfirst = next;
1388 next->first_same_value = newfirst;
1389 next = next->next_same_value;
1394 /* Remove the table element from its hash bucket. */
1397 register struct table_elt *prev = elt->prev_same_hash;
1398 register struct table_elt *next = elt->next_same_hash;
1401 next->prev_same_hash = prev;
1404 prev->next_same_hash = next;
1405 else if (table[hash] == elt)
1409 /* This entry is not in the proper hash bucket. This can happen
1410 when two classes were merged by `merge_equiv_classes'. Search
1411 for the hash bucket that it heads. This happens only very
1412 rarely, so the cost is acceptable. */
1413 for (hash = 0; hash < HASH_SIZE; hash++)
1414 if (table[hash] == elt)
1419 /* Remove the table element from its related-value circular chain. */
1421 if (elt->related_value != 0 && elt->related_value != elt)
1423 register struct table_elt *p = elt->related_value;
1425 while (p->related_value != elt)
1426 p = p->related_value;
1427 p->related_value = elt->related_value;
1428 if (p->related_value == p)
1429 p->related_value = 0;
1432 /* Now add it to the free element chain. */
1433 elt->next_same_hash = free_element_chain;
1434 free_element_chain = elt;
1437 /* Look up X in the hash table and return its table element,
1438 or 0 if X is not in the table.
1440 MODE is the machine-mode of X, or if X is an integer constant
1441 with VOIDmode then MODE is the mode with which X will be used.
1443 Here we are satisfied to find an expression whose tree structure
1446 static struct table_elt *
1447 lookup (x, hash, mode)
1450 enum machine_mode mode;
1452 register struct table_elt *p;
1454 for (p = table[hash]; p; p = p->next_same_hash)
1455 if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
1456 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
1462 /* Like `lookup' but don't care whether the table element uses invalid regs.
1463 Also ignore discrepancies in the machine mode of a register. */
1465 static struct table_elt *
1466 lookup_for_remove (x, hash, mode)
1469 enum machine_mode mode;
1471 register struct table_elt *p;
1473 if (GET_CODE (x) == REG)
1475 unsigned int regno = REGNO (x);
1477 /* Don't check the machine mode when comparing registers;
1478 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1479 for (p = table[hash]; p; p = p->next_same_hash)
1480 if (GET_CODE (p->exp) == REG
1481 && REGNO (p->exp) == regno)
1486 for (p = table[hash]; p; p = p->next_same_hash)
1487 if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
1494 /* Look for an expression equivalent to X and with code CODE.
1495 If one is found, return that expression. */
1498 lookup_as_function (x, code)
1502 register struct table_elt *p
1503 = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, GET_MODE (x));
1505 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1506 long as we are narrowing. So if we looked in vain for a mode narrower
1507 than word_mode before, look for word_mode now. */
1508 if (p == 0 && code == CONST_INT
1509 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1512 PUT_MODE (x, word_mode);
1513 p = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, word_mode);
1519 for (p = p->first_same_value; p; p = p->next_same_value)
1520 if (GET_CODE (p->exp) == code
1521 /* Make sure this is a valid entry in the table. */
1522 && exp_equiv_p (p->exp, p->exp, 1, 0))
1528 /* Insert X in the hash table, assuming HASH is its hash code
1529 and CLASSP is an element of the class it should go in
1530 (or 0 if a new class should be made).
1531 It is inserted at the proper position to keep the class in
1532 the order cheapest first.
1534 MODE is the machine-mode of X, or if X is an integer constant
1535 with VOIDmode then MODE is the mode with which X will be used.
1537 For elements of equal cheapness, the most recent one
1538 goes in front, except that the first element in the list
1539 remains first unless a cheaper element is added. The order of
1540 pseudo-registers does not matter, as canon_reg will be called to
1541 find the cheapest when a register is retrieved from the table.
1543 The in_memory field in the hash table element is set to 0.
1544 The caller must set it nonzero if appropriate.
1546 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1547 and if insert_regs returns a nonzero value
1548 you must then recompute its hash code before calling here.
1550 If necessary, update table showing constant values of quantities. */
1552 #define CHEAPER(X, Y) \
1553 (preferrable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1555 static struct table_elt *
1556 insert (x, classp, hash, mode)
1558 register struct table_elt *classp;
1560 enum machine_mode mode;
1562 register struct table_elt *elt;
1564 /* If X is a register and we haven't made a quantity for it,
1565 something is wrong. */
1566 if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
1569 /* If X is a hard register, show it is being put in the table. */
1570 if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
1572 unsigned int regno = REGNO (x);
1573 unsigned int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1576 for (i = regno; i < endregno; i++)
1577 SET_HARD_REG_BIT (hard_regs_in_table, i);
1580 /* If X is a label, show we recorded it. */
1581 if (GET_CODE (x) == LABEL_REF
1582 || (GET_CODE (x) == CONST && GET_CODE (XEXP (x, 0)) == PLUS
1583 && GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))
1584 recorded_label_ref = 1;
1586 /* Put an element for X into the right hash bucket. */
1588 elt = free_element_chain;
1590 free_element_chain = elt->next_same_hash;
1594 elt = (struct table_elt *) oballoc (sizeof (struct table_elt));
1598 elt->canon_exp = NULL_RTX;
1599 elt->cost = COST (x);
1600 elt->regcost = approx_reg_cost (x);
1601 elt->next_same_value = 0;
1602 elt->prev_same_value = 0;
1603 elt->next_same_hash = table[hash];
1604 elt->prev_same_hash = 0;
1605 elt->related_value = 0;
1608 elt->is_const = (CONSTANT_P (x)
1609 /* GNU C++ takes advantage of this for `this'
1610 (and other const values). */
1611 || (RTX_UNCHANGING_P (x)
1612 && GET_CODE (x) == REG
1613 && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1614 || FIXED_BASE_PLUS_P (x));
1617 table[hash]->prev_same_hash = elt;
1620 /* Put it into the proper value-class. */
1623 classp = classp->first_same_value;
1624 if (CHEAPER (elt, classp))
1625 /* Insert at the head of the class */
1627 register struct table_elt *p;
1628 elt->next_same_value = classp;
1629 classp->prev_same_value = elt;
1630 elt->first_same_value = elt;
1632 for (p = classp; p; p = p->next_same_value)
1633 p->first_same_value = elt;
1637 /* Insert not at head of the class. */
1638 /* Put it after the last element cheaper than X. */
1639 register struct table_elt *p, *next;
1641 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1644 /* Put it after P and before NEXT. */
1645 elt->next_same_value = next;
1647 next->prev_same_value = elt;
1649 elt->prev_same_value = p;
1650 p->next_same_value = elt;
1651 elt->first_same_value = classp;
1655 elt->first_same_value = elt;
1657 /* If this is a constant being set equivalent to a register or a register
1658 being set equivalent to a constant, note the constant equivalence.
1660 If this is a constant, it cannot be equivalent to a different constant,
1661 and a constant is the only thing that can be cheaper than a register. So
1662 we know the register is the head of the class (before the constant was
1665 If this is a register that is not already known equivalent to a
1666 constant, we must check the entire class.
1668 If this is a register that is already known equivalent to an insn,
1669 update the qtys `const_insn' to show that `this_insn' is the latest
1670 insn making that quantity equivalent to the constant. */
1672 if (elt->is_const && classp && GET_CODE (classp->exp) == REG
1673 && GET_CODE (x) != REG)
1675 int exp_q = REG_QTY (REGNO (classp->exp));
1676 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1678 exp_ent->const_rtx = gen_lowpart_if_possible (exp_ent->mode, x);
1679 exp_ent->const_insn = this_insn;
1682 else if (GET_CODE (x) == REG
1684 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1687 register struct table_elt *p;
1689 for (p = classp; p != 0; p = p->next_same_value)
1691 if (p->is_const && GET_CODE (p->exp) != REG)
1693 int x_q = REG_QTY (REGNO (x));
1694 struct qty_table_elem *x_ent = &qty_table[x_q];
1697 = gen_lowpart_if_possible (GET_MODE (x), p->exp);
1698 x_ent->const_insn = this_insn;
1704 else if (GET_CODE (x) == REG
1705 && qty_table[REG_QTY (REGNO (x))].const_rtx
1706 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1707 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1709 /* If this is a constant with symbolic value,
1710 and it has a term with an explicit integer value,
1711 link it up with related expressions. */
1712 if (GET_CODE (x) == CONST)
1714 rtx subexp = get_related_value (x);
1716 struct table_elt *subelt, *subelt_prev;
1720 /* Get the integer-free subexpression in the hash table. */
1721 subhash = safe_hash (subexp, mode) & HASH_MASK;
1722 subelt = lookup (subexp, subhash, mode);
1724 subelt = insert (subexp, NULL_PTR, subhash, mode);
1725 /* Initialize SUBELT's circular chain if it has none. */
1726 if (subelt->related_value == 0)
1727 subelt->related_value = subelt;
1728 /* Find the element in the circular chain that precedes SUBELT. */
1729 subelt_prev = subelt;
1730 while (subelt_prev->related_value != subelt)
1731 subelt_prev = subelt_prev->related_value;
1732 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1733 This way the element that follows SUBELT is the oldest one. */
1734 elt->related_value = subelt_prev->related_value;
1735 subelt_prev->related_value = elt;
1742 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1743 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1744 the two classes equivalent.
1746 CLASS1 will be the surviving class; CLASS2 should not be used after this
1749 Any invalid entries in CLASS2 will not be copied. */
1752 merge_equiv_classes (class1, class2)
1753 struct table_elt *class1, *class2;
1755 struct table_elt *elt, *next, *new;
1757 /* Ensure we start with the head of the classes. */
1758 class1 = class1->first_same_value;
1759 class2 = class2->first_same_value;
1761 /* If they were already equal, forget it. */
1762 if (class1 == class2)
1765 for (elt = class2; elt; elt = next)
1769 enum machine_mode mode = elt->mode;
1771 next = elt->next_same_value;
1773 /* Remove old entry, make a new one in CLASS1's class.
1774 Don't do this for invalid entries as we cannot find their
1775 hash code (it also isn't necessary). */
1776 if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
1778 hash_arg_in_memory = 0;
1779 hash = HASH (exp, mode);
1781 if (GET_CODE (exp) == REG)
1782 delete_reg_equiv (REGNO (exp));
1784 remove_from_table (elt, hash);
1786 if (insert_regs (exp, class1, 0))
1788 rehash_using_reg (exp);
1789 hash = HASH (exp, mode);
1791 new = insert (exp, class1, hash, mode);
1792 new->in_memory = hash_arg_in_memory;
1797 /* Flush the entire hash table. */
1803 struct table_elt *p;
1805 for (i = 0; i < HASH_SIZE; i++)
1806 for (p = table[i]; p; p = table[i])
1808 /* Note that invalidate can remove elements
1809 after P in the current hash chain. */
1810 if (GET_CODE (p->exp) == REG)
1811 invalidate (p->exp, p->mode);
1813 remove_from_table (p, i);
1817 /* Function called for each rtx to check whether true dependence exist. */
1818 struct check_dependence_data
1820 enum machine_mode mode;
1824 check_dependence (x, data)
1828 struct check_dependence_data *d = (struct check_dependence_data *) data;
1829 if (*x && GET_CODE (*x) == MEM)
1830 return true_dependence (d->exp, d->mode, *x, cse_rtx_varies_p);
1835 /* Remove from the hash table, or mark as invalid, all expressions whose
1836 values could be altered by storing in X. X is a register, a subreg, or
1837 a memory reference with nonvarying address (because, when a memory
1838 reference with a varying address is stored in, all memory references are
1839 removed by invalidate_memory so specific invalidation is superfluous).
1840 FULL_MODE, if not VOIDmode, indicates that this much should be
1841 invalidated instead of just the amount indicated by the mode of X. This
1842 is only used for bitfield stores into memory.
1844 A nonvarying address may be just a register or just a symbol reference,
1845 or it may be either of those plus a numeric offset. */
1848 invalidate (x, full_mode)
1850 enum machine_mode full_mode;
1853 register struct table_elt *p;
1855 switch (GET_CODE (x))
1859 /* If X is a register, dependencies on its contents are recorded
1860 through the qty number mechanism. Just change the qty number of
1861 the register, mark it as invalid for expressions that refer to it,
1862 and remove it itself. */
1863 unsigned int regno = REGNO (x);
1864 unsigned int hash = HASH (x, GET_MODE (x));
1866 /* Remove REGNO from any quantity list it might be on and indicate
1867 that its value might have changed. If it is a pseudo, remove its
1868 entry from the hash table.
1870 For a hard register, we do the first two actions above for any
1871 additional hard registers corresponding to X. Then, if any of these
1872 registers are in the table, we must remove any REG entries that
1873 overlap these registers. */
1875 delete_reg_equiv (regno);
1878 if (regno >= FIRST_PSEUDO_REGISTER)
1880 /* Because a register can be referenced in more than one mode,
1881 we might have to remove more than one table entry. */
1882 struct table_elt *elt;
1884 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1885 remove_from_table (elt, hash);
1889 HOST_WIDE_INT in_table
1890 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1891 unsigned int endregno
1892 = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1893 unsigned int tregno, tendregno, rn;
1894 register struct table_elt *p, *next;
1896 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1898 for (rn = regno + 1; rn < endregno; rn++)
1900 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1901 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1902 delete_reg_equiv (rn);
1907 for (hash = 0; hash < HASH_SIZE; hash++)
1908 for (p = table[hash]; p; p = next)
1910 next = p->next_same_hash;
1912 if (GET_CODE (p->exp) != REG
1913 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1916 tregno = REGNO (p->exp);
1918 = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
1919 if (tendregno > regno && tregno < endregno)
1920 remove_from_table (p, hash);
1927 invalidate (SUBREG_REG (x), VOIDmode);
1931 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1932 invalidate (XVECEXP (x, 0, i), VOIDmode);
1936 /* This is part of a disjoint return value; extract the location in
1937 question ignoring the offset. */
1938 invalidate (XEXP (x, 0), VOIDmode);
1942 /* Calculate the canonical version of X here so that
1943 true_dependence doesn't generate new RTL for X on each call. */
1946 /* Remove all hash table elements that refer to overlapping pieces of
1948 if (full_mode == VOIDmode)
1949 full_mode = GET_MODE (x);
1951 for (i = 0; i < HASH_SIZE; i++)
1953 register struct table_elt *next;
1955 for (p = table[i]; p; p = next)
1957 next = p->next_same_hash;
1960 struct check_dependence_data d;
1962 /* Just canonicalize the expression once;
1963 otherwise each time we call invalidate
1964 true_dependence will canonicalize the
1965 expression again. */
1967 p->canon_exp = canon_rtx (p->exp);
1970 if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1971 remove_from_table (p, i);
1982 /* Remove all expressions that refer to register REGNO,
1983 since they are already invalid, and we are about to
1984 mark that register valid again and don't want the old
1985 expressions to reappear as valid. */
1988 remove_invalid_refs (regno)
1992 struct table_elt *p, *next;
1994 for (i = 0; i < HASH_SIZE; i++)
1995 for (p = table[i]; p; p = next)
1997 next = p->next_same_hash;
1998 if (GET_CODE (p->exp) != REG
1999 && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR))
2000 remove_from_table (p, i);
2004 /* Likewise for a subreg with subreg_reg WORD and mode MODE. */
2006 remove_invalid_subreg_refs (regno, word, mode)
2009 enum machine_mode mode;
2012 struct table_elt *p, *next;
2013 unsigned int end = word + (GET_MODE_SIZE (mode) - 1) / UNITS_PER_WORD;
2015 for (i = 0; i < HASH_SIZE; i++)
2016 for (p = table[i]; p; p = next)
2019 next = p->next_same_hash;
2022 if (GET_CODE (p->exp) != REG
2023 && (GET_CODE (exp) != SUBREG
2024 || GET_CODE (SUBREG_REG (exp)) != REG
2025 || REGNO (SUBREG_REG (exp)) != regno
2026 || (((SUBREG_WORD (exp)
2027 + (GET_MODE_SIZE (GET_MODE (exp)) - 1) / UNITS_PER_WORD)
2029 && SUBREG_WORD (exp) <= end))
2030 && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR))
2031 remove_from_table (p, i);
2035 /* Recompute the hash codes of any valid entries in the hash table that
2036 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
2038 This is called when we make a jump equivalence. */
2041 rehash_using_reg (x)
2045 struct table_elt *p, *next;
2048 if (GET_CODE (x) == SUBREG)
2051 /* If X is not a register or if the register is known not to be in any
2052 valid entries in the table, we have no work to do. */
2054 if (GET_CODE (x) != REG
2055 || REG_IN_TABLE (REGNO (x)) < 0
2056 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
2059 /* Scan all hash chains looking for valid entries that mention X.
2060 If we find one and it is in the wrong hash chain, move it. We can skip
2061 objects that are registers, since they are handled specially. */
2063 for (i = 0; i < HASH_SIZE; i++)
2064 for (p = table[i]; p; p = next)
2066 next = p->next_same_hash;
2067 if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
2068 && exp_equiv_p (p->exp, p->exp, 1, 0)
2069 && i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
2071 if (p->next_same_hash)
2072 p->next_same_hash->prev_same_hash = p->prev_same_hash;
2074 if (p->prev_same_hash)
2075 p->prev_same_hash->next_same_hash = p->next_same_hash;
2077 table[i] = p->next_same_hash;
2079 p->next_same_hash = table[hash];
2080 p->prev_same_hash = 0;
2082 table[hash]->prev_same_hash = p;
2088 /* Remove from the hash table any expression that is a call-clobbered
2089 register. Also update their TICK values. */
2092 invalidate_for_call ()
2094 unsigned int regno, endregno;
2097 struct table_elt *p, *next;
2100 /* Go through all the hard registers. For each that is clobbered in
2101 a CALL_INSN, remove the register from quantity chains and update
2102 reg_tick if defined. Also see if any of these registers is currently
2105 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2106 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2108 delete_reg_equiv (regno);
2109 if (REG_TICK (regno) >= 0)
2112 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2115 /* In the case where we have no call-clobbered hard registers in the
2116 table, we are done. Otherwise, scan the table and remove any
2117 entry that overlaps a call-clobbered register. */
2120 for (hash = 0; hash < HASH_SIZE; hash++)
2121 for (p = table[hash]; p; p = next)
2123 next = p->next_same_hash;
2125 if (GET_CODE (p->exp) != REG
2126 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2129 regno = REGNO (p->exp);
2130 endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
2132 for (i = regno; i < endregno; i++)
2133 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2135 remove_from_table (p, hash);
2141 /* Given an expression X of type CONST,
2142 and ELT which is its table entry (or 0 if it
2143 is not in the hash table),
2144 return an alternate expression for X as a register plus integer.
2145 If none can be found, return 0. */
2148 use_related_value (x, elt)
2150 struct table_elt *elt;
2152 register struct table_elt *relt = 0;
2153 register struct table_elt *p, *q;
2154 HOST_WIDE_INT offset;
2156 /* First, is there anything related known?
2157 If we have a table element, we can tell from that.
2158 Otherwise, must look it up. */
2160 if (elt != 0 && elt->related_value != 0)
2162 else if (elt == 0 && GET_CODE (x) == CONST)
2164 rtx subexp = get_related_value (x);
2166 relt = lookup (subexp,
2167 safe_hash (subexp, GET_MODE (subexp)) & HASH_MASK,
2174 /* Search all related table entries for one that has an
2175 equivalent register. */
2180 /* This loop is strange in that it is executed in two different cases.
2181 The first is when X is already in the table. Then it is searching
2182 the RELATED_VALUE list of X's class (RELT). The second case is when
2183 X is not in the table. Then RELT points to a class for the related
2186 Ensure that, whatever case we are in, that we ignore classes that have
2187 the same value as X. */
2189 if (rtx_equal_p (x, p->exp))
2192 for (q = p->first_same_value; q; q = q->next_same_value)
2193 if (GET_CODE (q->exp) == REG)
2199 p = p->related_value;
2201 /* We went all the way around, so there is nothing to be found.
2202 Alternatively, perhaps RELT was in the table for some other reason
2203 and it has no related values recorded. */
2204 if (p == relt || p == 0)
2211 offset = (get_integer_term (x) - get_integer_term (p->exp));
2212 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2213 return plus_constant (q->exp, offset);
2216 /* Hash a string. Just add its bytes up. */
2217 static inline unsigned
2218 canon_hash_string (ps)
2222 const unsigned char *p = (const unsigned char *)ps;
2231 /* Hash an rtx. We are careful to make sure the value is never negative.
2232 Equivalent registers hash identically.
2233 MODE is used in hashing for CONST_INTs only;
2234 otherwise the mode of X is used.
2236 Store 1 in do_not_record if any subexpression is volatile.
2238 Store 1 in hash_arg_in_memory if X contains a MEM rtx
2239 which does not have the RTX_UNCHANGING_P bit set.
2241 Note that cse_insn knows that the hash code of a MEM expression
2242 is just (int) MEM plus the hash code of the address. */
2245 canon_hash (x, mode)
2247 enum machine_mode mode;
2250 register unsigned hash = 0;
2251 register enum rtx_code code;
2252 register const char *fmt;
2254 /* repeat is used to turn tail-recursion into iteration. */
2259 code = GET_CODE (x);
2264 unsigned int regno = REGNO (x);
2266 /* On some machines, we can't record any non-fixed hard register,
2267 because extending its life will cause reload problems. We
2268 consider ap, fp, and sp to be fixed for this purpose.
2270 We also consider CCmode registers to be fixed for this purpose;
2271 failure to do so leads to failure to simplify 0<100 type of
2274 On all machines, we can't record any global registers. */
2276 if (regno < FIRST_PSEUDO_REGISTER
2277 && (global_regs[regno]
2278 || (SMALL_REGISTER_CLASSES
2279 && ! fixed_regs[regno]
2280 && regno != FRAME_POINTER_REGNUM
2281 && regno != HARD_FRAME_POINTER_REGNUM
2282 && regno != ARG_POINTER_REGNUM
2283 && regno != STACK_POINTER_REGNUM
2284 && GET_MODE_CLASS (GET_MODE (x)) != MODE_CC)))
2290 hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno);
2294 /* We handle SUBREG of a REG specially because the underlying
2295 reg changes its hash value with every value change; we don't
2296 want to have to forget unrelated subregs when one subreg changes. */
2299 if (GET_CODE (SUBREG_REG (x)) == REG)
2301 hash += (((unsigned) SUBREG << 7)
2302 + REGNO (SUBREG_REG (x)) + SUBREG_WORD (x));
2310 unsigned HOST_WIDE_INT tem = INTVAL (x);
2311 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
2316 /* This is like the general case, except that it only counts
2317 the integers representing the constant. */
2318 hash += (unsigned) code + (unsigned) GET_MODE (x);
2319 if (GET_MODE (x) != VOIDmode)
2320 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2322 unsigned HOST_WIDE_INT tem = XWINT (x, i);
2326 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2327 + (unsigned) CONST_DOUBLE_HIGH (x));
2330 /* Assume there is only one rtx object for any given label. */
2332 hash += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2336 hash += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2340 /* We don't record if marked volatile or if BLKmode since we don't
2341 know the size of the move. */
2342 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2347 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
2349 hash_arg_in_memory = 1;
2351 /* Now that we have already found this special case,
2352 might as well speed it up as much as possible. */
2353 hash += (unsigned) MEM;
2358 /* A USE that mentions non-volatile memory needs special
2359 handling since the MEM may be BLKmode which normally
2360 prevents an entry from being made. Pure calls are
2361 marked by a USE which mentions BLKmode memory. */
2362 if (GET_CODE (XEXP (x, 0)) == MEM
2363 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2365 hash += (unsigned)USE;
2368 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
2369 hash_arg_in_memory = 1;
2371 /* Now that we have already found this special case,
2372 might as well speed it up as much as possible. */
2373 hash += (unsigned) MEM;
2388 case UNSPEC_VOLATILE:
2393 if (MEM_VOLATILE_P (x))
2400 /* We don't want to take the filename and line into account. */
2401 hash += (unsigned) code + (unsigned) GET_MODE (x)
2402 + canon_hash_string (ASM_OPERANDS_TEMPLATE (x))
2403 + canon_hash_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2404 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2406 if (ASM_OPERANDS_INPUT_LENGTH (x))
2408 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2410 hash += (canon_hash (ASM_OPERANDS_INPUT (x, i),
2411 GET_MODE (ASM_OPERANDS_INPUT (x, i)))
2412 + canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT
2416 hash += canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2417 x = ASM_OPERANDS_INPUT (x, 0);
2418 mode = GET_MODE (x);
2430 i = GET_RTX_LENGTH (code) - 1;
2431 hash += (unsigned) code + (unsigned) GET_MODE (x);
2432 fmt = GET_RTX_FORMAT (code);
2437 rtx tem = XEXP (x, i);
2439 /* If we are about to do the last recursive call
2440 needed at this level, change it into iteration.
2441 This function is called enough to be worth it. */
2447 hash += canon_hash (tem, 0);
2449 else if (fmt[i] == 'E')
2450 for (j = 0; j < XVECLEN (x, i); j++)
2451 hash += canon_hash (XVECEXP (x, i, j), 0);
2452 else if (fmt[i] == 's')
2453 hash += canon_hash_string (XSTR (x, i));
2454 else if (fmt[i] == 'i')
2456 register unsigned tem = XINT (x, i);
2459 else if (fmt[i] == '0' || fmt[i] == 't')
2468 /* Like canon_hash but with no side effects. */
2473 enum machine_mode mode;
2475 int save_do_not_record = do_not_record;
2476 int save_hash_arg_in_memory = hash_arg_in_memory;
2477 unsigned hash = canon_hash (x, mode);
2478 hash_arg_in_memory = save_hash_arg_in_memory;
2479 do_not_record = save_do_not_record;
2483 /* Return 1 iff X and Y would canonicalize into the same thing,
2484 without actually constructing the canonicalization of either one.
2485 If VALIDATE is nonzero,
2486 we assume X is an expression being processed from the rtl
2487 and Y was found in the hash table. We check register refs
2488 in Y for being marked as valid.
2490 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2491 that is known to be in the register. Ordinarily, we don't allow them
2492 to match, because letting them match would cause unpredictable results
2493 in all the places that search a hash table chain for an equivalent
2494 for a given value. A possible equivalent that has different structure
2495 has its hash code computed from different data. Whether the hash code
2496 is the same as that of the given value is pure luck. */
2499 exp_equiv_p (x, y, validate, equal_values)
2505 register enum rtx_code code;
2506 register const char *fmt;
2508 /* Note: it is incorrect to assume an expression is equivalent to itself
2509 if VALIDATE is nonzero. */
2510 if (x == y && !validate)
2512 if (x == 0 || y == 0)
2515 code = GET_CODE (x);
2516 if (code != GET_CODE (y))
2521 /* If X is a constant and Y is a register or vice versa, they may be
2522 equivalent. We only have to validate if Y is a register. */
2523 if (CONSTANT_P (x) && GET_CODE (y) == REG
2524 && REGNO_QTY_VALID_P (REGNO (y)))
2526 int y_q = REG_QTY (REGNO (y));
2527 struct qty_table_elem *y_ent = &qty_table[y_q];
2529 if (GET_MODE (y) == y_ent->mode
2530 && rtx_equal_p (x, y_ent->const_rtx)
2531 && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y))))
2535 if (CONSTANT_P (y) && code == REG
2536 && REGNO_QTY_VALID_P (REGNO (x)))
2538 int x_q = REG_QTY (REGNO (x));
2539 struct qty_table_elem *x_ent = &qty_table[x_q];
2541 if (GET_MODE (x) == x_ent->mode
2542 && rtx_equal_p (y, x_ent->const_rtx))
2549 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2550 if (GET_MODE (x) != GET_MODE (y))
2561 return XEXP (x, 0) == XEXP (y, 0);
2564 return XSTR (x, 0) == XSTR (y, 0);
2568 unsigned int regno = REGNO (y);
2569 unsigned int endregno
2570 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2571 : HARD_REGNO_NREGS (regno, GET_MODE (y)));
2574 /* If the quantities are not the same, the expressions are not
2575 equivalent. If there are and we are not to validate, they
2576 are equivalent. Otherwise, ensure all regs are up-to-date. */
2578 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2584 for (i = regno; i < endregno; i++)
2585 if (REG_IN_TABLE (i) != REG_TICK (i))
2591 /* For commutative operations, check both orders. */
2599 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
2600 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2601 validate, equal_values))
2602 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2603 validate, equal_values)
2604 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2605 validate, equal_values)));
2608 /* We don't use the generic code below because we want to
2609 disregard filename and line numbers. */
2611 /* A volatile asm isn't equivalent to any other. */
2612 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2615 if (GET_MODE (x) != GET_MODE (y)
2616 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2617 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2618 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2619 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2620 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2623 if (ASM_OPERANDS_INPUT_LENGTH (x))
2625 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2626 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2627 ASM_OPERANDS_INPUT (y, i),
2628 validate, equal_values)
2629 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2630 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2640 /* Compare the elements. If any pair of corresponding elements
2641 fail to match, return 0 for the whole things. */
2643 fmt = GET_RTX_FORMAT (code);
2644 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2649 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
2654 if (XVECLEN (x, i) != XVECLEN (y, i))
2656 for (j = 0; j < XVECLEN (x, i); j++)
2657 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2658 validate, equal_values))
2663 if (strcmp (XSTR (x, i), XSTR (y, i)))
2668 if (XINT (x, i) != XINT (y, i))
2673 if (XWINT (x, i) != XWINT (y, i))
2689 /* Return 1 if X has a value that can vary even between two
2690 executions of the program. 0 means X can be compared reliably
2691 against certain constants or near-constants. */
2694 cse_rtx_varies_p (x)
2697 /* We need not check for X and the equivalence class being of the same
2698 mode because if X is equivalent to a constant in some mode, it
2699 doesn't vary in any mode. */
2701 if (GET_CODE (x) == REG
2702 && REGNO_QTY_VALID_P (REGNO (x)))
2704 int x_q = REG_QTY (REGNO (x));
2705 struct qty_table_elem *x_ent = &qty_table[x_q];
2707 if (GET_MODE (x) == x_ent->mode
2708 && x_ent->const_rtx != NULL_RTX)
2712 if (GET_CODE (x) == PLUS
2713 && GET_CODE (XEXP (x, 1)) == CONST_INT
2714 && GET_CODE (XEXP (x, 0)) == REG
2715 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2717 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2718 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2720 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2721 && x0_ent->const_rtx != NULL_RTX)
2725 /* This can happen as the result of virtual register instantiation, if
2726 the initial constant is too large to be a valid address. This gives
2727 us a three instruction sequence, load large offset into a register,
2728 load fp minus a constant into a register, then a MEM which is the
2729 sum of the two `constant' registers. */
2730 if (GET_CODE (x) == PLUS
2731 && GET_CODE (XEXP (x, 0)) == REG
2732 && GET_CODE (XEXP (x, 1)) == REG
2733 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2734 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2736 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2737 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2738 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2739 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2741 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2742 && x0_ent->const_rtx != NULL_RTX
2743 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2744 && x1_ent->const_rtx != NULL_RTX)
2748 return rtx_varies_p (x);
2751 /* Canonicalize an expression:
2752 replace each register reference inside it
2753 with the "oldest" equivalent register.
2755 If INSN is non-zero and we are replacing a pseudo with a hard register
2756 or vice versa, validate_change is used to ensure that INSN remains valid
2757 after we make our substitution. The calls are made with IN_GROUP non-zero
2758 so apply_change_group must be called upon the outermost return from this
2759 function (unless INSN is zero). The result of apply_change_group can
2760 generally be discarded since the changes we are making are optional. */
2768 register enum rtx_code code;
2769 register const char *fmt;
2774 code = GET_CODE (x);
2792 register struct qty_table_elem *ent;
2794 /* Never replace a hard reg, because hard regs can appear
2795 in more than one machine mode, and we must preserve the mode
2796 of each occurrence. Also, some hard regs appear in
2797 MEMs that are shared and mustn't be altered. Don't try to
2798 replace any reg that maps to a reg of class NO_REGS. */
2799 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2800 || ! REGNO_QTY_VALID_P (REGNO (x)))
2803 q = REG_QTY (REGNO (x));
2804 ent = &qty_table[q];
2805 first = ent->first_reg;
2806 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2807 : REGNO_REG_CLASS (first) == NO_REGS ? x
2808 : gen_rtx_REG (ent->mode, first));
2815 fmt = GET_RTX_FORMAT (code);
2816 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2822 rtx new = canon_reg (XEXP (x, i), insn);
2825 /* If replacing pseudo with hard reg or vice versa, ensure the
2826 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2827 if (insn != 0 && new != 0
2828 && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
2829 && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2830 != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER))
2831 || (insn_code = recog_memoized (insn)) < 0
2832 || insn_data[insn_code].n_dups > 0))
2833 validate_change (insn, &XEXP (x, i), new, 1);
2837 else if (fmt[i] == 'E')
2838 for (j = 0; j < XVECLEN (x, i); j++)
2839 XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
2845 /* LOC is a location within INSN that is an operand address (the contents of
2846 a MEM). Find the best equivalent address to use that is valid for this
2849 On most CISC machines, complicated address modes are costly, and rtx_cost
2850 is a good approximation for that cost. However, most RISC machines have
2851 only a few (usually only one) memory reference formats. If an address is
2852 valid at all, it is often just as cheap as any other address. Hence, for
2853 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2854 costs of various addresses. For two addresses of equal cost, choose the one
2855 with the highest `rtx_cost' value as that has the potential of eliminating
2856 the most insns. For equal costs, we choose the first in the equivalence
2857 class. Note that we ignore the fact that pseudo registers are cheaper
2858 than hard registers here because we would also prefer the pseudo registers.
2862 find_best_addr (insn, loc, mode)
2865 enum machine_mode mode;
2867 struct table_elt *elt;
2870 struct table_elt *p;
2871 int found_better = 1;
2873 int save_do_not_record = do_not_record;
2874 int save_hash_arg_in_memory = hash_arg_in_memory;
2879 /* Do not try to replace constant addresses or addresses of local and
2880 argument slots. These MEM expressions are made only once and inserted
2881 in many instructions, as well as being used to control symbol table
2882 output. It is not safe to clobber them.
2884 There are some uncommon cases where the address is already in a register
2885 for some reason, but we cannot take advantage of that because we have
2886 no easy way to unshare the MEM. In addition, looking up all stack
2887 addresses is costly. */
2888 if ((GET_CODE (addr) == PLUS
2889 && GET_CODE (XEXP (addr, 0)) == REG
2890 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2891 && (regno = REGNO (XEXP (addr, 0)),
2892 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2893 || regno == ARG_POINTER_REGNUM))
2894 || (GET_CODE (addr) == REG
2895 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2896 || regno == HARD_FRAME_POINTER_REGNUM
2897 || regno == ARG_POINTER_REGNUM))
2898 || GET_CODE (addr) == ADDRESSOF
2899 || CONSTANT_ADDRESS_P (addr))
2902 /* If this address is not simply a register, try to fold it. This will
2903 sometimes simplify the expression. Many simplifications
2904 will not be valid, but some, usually applying the associative rule, will
2905 be valid and produce better code. */
2906 if (GET_CODE (addr) != REG)
2908 rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX);
2909 int addr_folded_cost = address_cost (folded, mode);
2910 int addr_cost = address_cost (addr, mode);
2912 if ((addr_folded_cost < addr_cost
2913 || (addr_folded_cost == addr_cost
2914 /* ??? The rtx_cost comparison is left over from an older
2915 version of this code. It is probably no longer helpful. */
2916 && (rtx_cost (folded, MEM) > rtx_cost (addr, MEM)
2917 || approx_reg_cost (folded) < approx_reg_cost (addr))))
2918 && validate_change (insn, loc, folded, 0))
2922 /* If this address is not in the hash table, we can't look for equivalences
2923 of the whole address. Also, ignore if volatile. */
2926 hash = HASH (addr, Pmode);
2927 addr_volatile = do_not_record;
2928 do_not_record = save_do_not_record;
2929 hash_arg_in_memory = save_hash_arg_in_memory;
2934 elt = lookup (addr, hash, Pmode);
2936 #ifndef ADDRESS_COST
2939 int our_cost = elt->cost;
2941 /* Find the lowest cost below ours that works. */
2942 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
2943 if (elt->cost < our_cost
2944 && (GET_CODE (elt->exp) == REG
2945 || exp_equiv_p (elt->exp, elt->exp, 1, 0))
2946 && validate_change (insn, loc,
2947 canon_reg (copy_rtx (elt->exp), NULL_RTX), 0))
2954 /* We need to find the best (under the criteria documented above) entry
2955 in the class that is valid. We use the `flag' field to indicate
2956 choices that were invalid and iterate until we can't find a better
2957 one that hasn't already been tried. */
2959 for (p = elt->first_same_value; p; p = p->next_same_value)
2962 while (found_better)
2964 int best_addr_cost = address_cost (*loc, mode);
2965 int best_rtx_cost = (elt->cost + 1) >> 1;
2967 struct table_elt *best_elt = elt;
2970 for (p = elt->first_same_value; p; p = p->next_same_value)
2973 if ((GET_CODE (p->exp) == REG
2974 || exp_equiv_p (p->exp, p->exp, 1, 0))
2975 && ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
2976 || (exp_cost == best_addr_cost
2977 && (p->cost + 1) >> 1 < best_rtx_cost)))
2980 best_addr_cost = exp_cost;
2981 best_rtx_cost = (p->cost + 1) >> 1;
2988 if (validate_change (insn, loc,
2989 canon_reg (copy_rtx (best_elt->exp),
2998 /* If the address is a binary operation with the first operand a register
2999 and the second a constant, do the same as above, but looking for
3000 equivalences of the register. Then try to simplify before checking for
3001 the best address to use. This catches a few cases: First is when we
3002 have REG+const and the register is another REG+const. We can often merge
3003 the constants and eliminate one insn and one register. It may also be
3004 that a machine has a cheap REG+REG+const. Finally, this improves the
3005 code on the Alpha for unaligned byte stores. */
3007 if (flag_expensive_optimizations
3008 && (GET_RTX_CLASS (GET_CODE (*loc)) == '2'
3009 || GET_RTX_CLASS (GET_CODE (*loc)) == 'c')
3010 && GET_CODE (XEXP (*loc, 0)) == REG
3011 && GET_CODE (XEXP (*loc, 1)) == CONST_INT)
3013 rtx c = XEXP (*loc, 1);
3016 hash = HASH (XEXP (*loc, 0), Pmode);
3017 do_not_record = save_do_not_record;
3018 hash_arg_in_memory = save_hash_arg_in_memory;
3020 elt = lookup (XEXP (*loc, 0), hash, Pmode);
3024 /* We need to find the best (under the criteria documented above) entry
3025 in the class that is valid. We use the `flag' field to indicate
3026 choices that were invalid and iterate until we can't find a better
3027 one that hasn't already been tried. */
3029 for (p = elt->first_same_value; p; p = p->next_same_value)
3032 while (found_better)
3034 int best_addr_cost = address_cost (*loc, mode);
3035 int best_rtx_cost = (COST (*loc) + 1) >> 1;
3036 struct table_elt *best_elt = elt;
3037 rtx best_rtx = *loc;
3040 /* This is at worst case an O(n^2) algorithm, so limit our search
3041 to the first 32 elements on the list. This avoids trouble
3042 compiling code with very long basic blocks that can easily
3043 call simplify_gen_binary so many times that we run out of
3047 for (p = elt->first_same_value, count = 0;
3049 p = p->next_same_value, count++)
3051 && (GET_CODE (p->exp) == REG
3052 || exp_equiv_p (p->exp, p->exp, 1, 0)))
3054 rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
3057 new_cost = address_cost (new, mode);
3059 if (new_cost < best_addr_cost
3060 || (new_cost == best_addr_cost
3061 && (COST (new) + 1) >> 1 > best_rtx_cost))
3064 best_addr_cost = new_cost;
3065 best_rtx_cost = (COST (new) + 1) >> 1;
3073 if (validate_change (insn, loc,
3074 canon_reg (copy_rtx (best_rtx),
3085 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
3086 operation (EQ, NE, GT, etc.), follow it back through the hash table and
3087 what values are being compared.
3089 *PARG1 and *PARG2 are updated to contain the rtx representing the values
3090 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
3091 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
3092 compared to produce cc0.
3094 The return value is the comparison operator and is either the code of
3095 A or the code corresponding to the inverse of the comparison. */
3097 static enum rtx_code
3098 find_comparison_args (code, parg1, parg2, pmode1, pmode2)
3101 enum machine_mode *pmode1, *pmode2;
3105 arg1 = *parg1, arg2 = *parg2;
3107 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
3109 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
3111 /* Set non-zero when we find something of interest. */
3113 int reverse_code = 0;
3114 struct table_elt *p = 0;
3116 /* If arg1 is a COMPARE, extract the comparison arguments from it.
3117 On machines with CC0, this is the only case that can occur, since
3118 fold_rtx will return the COMPARE or item being compared with zero
3121 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
3124 /* If ARG1 is a comparison operator and CODE is testing for
3125 STORE_FLAG_VALUE, get the inner arguments. */
3127 else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
3130 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3131 && code == LT && STORE_FLAG_VALUE == -1)
3132 #ifdef FLOAT_STORE_FLAG_VALUE
3133 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3134 && (REAL_VALUE_NEGATIVE
3135 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3140 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3141 && code == GE && STORE_FLAG_VALUE == -1)
3142 #ifdef FLOAT_STORE_FLAG_VALUE
3143 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3144 && (REAL_VALUE_NEGATIVE
3145 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3148 x = arg1, reverse_code = 1;
3151 /* ??? We could also check for
3153 (ne (and (eq (...) (const_int 1))) (const_int 0))
3155 and related forms, but let's wait until we see them occurring. */
3158 /* Look up ARG1 in the hash table and see if it has an equivalence
3159 that lets us see what is being compared. */
3160 p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) & HASH_MASK,
3163 p = p->first_same_value;
3165 for (; p; p = p->next_same_value)
3167 enum machine_mode inner_mode = GET_MODE (p->exp);
3169 /* If the entry isn't valid, skip it. */
3170 if (! exp_equiv_p (p->exp, p->exp, 1, 0))
3173 if (GET_CODE (p->exp) == COMPARE
3174 /* Another possibility is that this machine has a compare insn
3175 that includes the comparison code. In that case, ARG1 would
3176 be equivalent to a comparison operation that would set ARG1 to
3177 either STORE_FLAG_VALUE or zero. If this is an NE operation,
3178 ORIG_CODE is the actual comparison being done; if it is an EQ,
3179 we must reverse ORIG_CODE. On machine with a negative value
3180 for STORE_FLAG_VALUE, also look at LT and GE operations. */
3183 && GET_MODE_CLASS (inner_mode) == MODE_INT
3184 && (GET_MODE_BITSIZE (inner_mode)
3185 <= HOST_BITS_PER_WIDE_INT)
3186 && (STORE_FLAG_VALUE
3187 & ((HOST_WIDE_INT) 1
3188 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3189 #ifdef FLOAT_STORE_FLAG_VALUE
3191 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3192 && (REAL_VALUE_NEGATIVE
3193 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3196 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
3201 else if ((code == EQ
3203 && GET_MODE_CLASS (inner_mode) == MODE_INT
3204 && (GET_MODE_BITSIZE (inner_mode)
3205 <= HOST_BITS_PER_WIDE_INT)
3206 && (STORE_FLAG_VALUE
3207 & ((HOST_WIDE_INT) 1
3208 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3209 #ifdef FLOAT_STORE_FLAG_VALUE
3211 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3212 && (REAL_VALUE_NEGATIVE
3213 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3216 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
3223 /* If this is fp + constant, the equivalent is a better operand since
3224 it may let us predict the value of the comparison. */
3225 else if (NONZERO_BASE_PLUS_P (p->exp))
3232 /* If we didn't find a useful equivalence for ARG1, we are done.
3233 Otherwise, set up for the next iteration. */
3237 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3238 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
3239 code = GET_CODE (x);
3242 code = reverse_condition (code);
3245 /* Return our results. Return the modes from before fold_rtx
3246 because fold_rtx might produce const_int, and then it's too late. */
3247 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3248 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3253 /* If X is a nontrivial arithmetic operation on an argument
3254 for which a constant value can be determined, return
3255 the result of operating on that value, as a constant.
3256 Otherwise, return X, possibly with one or more operands
3257 modified by recursive calls to this function.
3259 If X is a register whose contents are known, we do NOT
3260 return those contents here. equiv_constant is called to
3263 INSN is the insn that we may be modifying. If it is 0, make a copy
3264 of X before modifying it. */
3271 register enum rtx_code code;
3272 register enum machine_mode mode;
3273 register const char *fmt;
3279 /* Folded equivalents of first two operands of X. */
3283 /* Constant equivalents of first three operands of X;
3284 0 when no such equivalent is known. */
3289 /* The mode of the first operand of X. We need this for sign and zero
3291 enum machine_mode mode_arg0;
3296 mode = GET_MODE (x);
3297 code = GET_CODE (x);
3306 /* No use simplifying an EXPR_LIST
3307 since they are used only for lists of args
3308 in a function call's REG_EQUAL note. */
3310 /* Changing anything inside an ADDRESSOF is incorrect; we don't
3311 want to (e.g.,) make (addressof (const_int 0)) just because
3312 the location is known to be zero. */
3318 return prev_insn_cc0;
3322 /* If the next insn is a CODE_LABEL followed by a jump table,
3323 PC's value is a LABEL_REF pointing to that label. That
3324 lets us fold switch statements on the Vax. */
3325 if (insn && GET_CODE (insn) == JUMP_INSN)
3327 rtx next = next_nonnote_insn (insn);
3329 if (next && GET_CODE (next) == CODE_LABEL
3330 && NEXT_INSN (next) != 0
3331 && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
3332 && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
3333 || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
3334 return gen_rtx_LABEL_REF (Pmode, next);
3339 /* See if we previously assigned a constant value to this SUBREG. */
3340 if ((new = lookup_as_function (x, CONST_INT)) != 0
3341 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3344 /* If this is a paradoxical SUBREG, we have no idea what value the
3345 extra bits would have. However, if the operand is equivalent
3346 to a SUBREG whose operand is the same as our mode, and all the
3347 modes are within a word, we can just use the inner operand
3348 because these SUBREGs just say how to treat the register.
3350 Similarly if we find an integer constant. */
3352 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3354 enum machine_mode imode = GET_MODE (SUBREG_REG (x));
3355 struct table_elt *elt;
3357 if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
3358 && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
3359 && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
3361 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3363 if (CONSTANT_P (elt->exp)
3364 && GET_MODE (elt->exp) == VOIDmode)
3367 if (GET_CODE (elt->exp) == SUBREG
3368 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3369 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3370 return copy_rtx (SUBREG_REG (elt->exp));
3376 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
3377 We might be able to if the SUBREG is extracting a single word in an
3378 integral mode or extracting the low part. */
3380 folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
3381 const_arg0 = equiv_constant (folded_arg0);
3383 folded_arg0 = const_arg0;
3385 if (folded_arg0 != SUBREG_REG (x))
3389 if (GET_MODE_CLASS (mode) == MODE_INT
3390 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3391 && GET_MODE (SUBREG_REG (x)) != VOIDmode)
3392 new = operand_subword (folded_arg0, SUBREG_WORD (x), 0,
3393 GET_MODE (SUBREG_REG (x)));
3394 if (new == 0 && subreg_lowpart_p (x))
3395 new = gen_lowpart_if_possible (mode, folded_arg0);
3400 /* If this is a narrowing SUBREG and our operand is a REG, see if
3401 we can find an equivalence for REG that is an arithmetic operation
3402 in a wider mode where both operands are paradoxical SUBREGs
3403 from objects of our result mode. In that case, we couldn't report
3404 an equivalent value for that operation, since we don't know what the
3405 extra bits will be. But we can find an equivalence for this SUBREG
3406 by folding that operation is the narrow mode. This allows us to
3407 fold arithmetic in narrow modes when the machine only supports
3408 word-sized arithmetic.
3410 Also look for a case where we have a SUBREG whose operand is the
3411 same as our result. If both modes are smaller than a word, we
3412 are simply interpreting a register in different modes and we
3413 can use the inner value. */
3415 if (GET_CODE (folded_arg0) == REG
3416 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0))
3417 && subreg_lowpart_p (x))
3419 struct table_elt *elt;
3421 /* We can use HASH here since we know that canon_hash won't be
3423 elt = lookup (folded_arg0,
3424 HASH (folded_arg0, GET_MODE (folded_arg0)),
3425 GET_MODE (folded_arg0));
3428 elt = elt->first_same_value;
3430 for (; elt; elt = elt->next_same_value)
3432 enum rtx_code eltcode = GET_CODE (elt->exp);
3434 /* Just check for unary and binary operations. */
3435 if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1'
3436 && GET_CODE (elt->exp) != SIGN_EXTEND
3437 && GET_CODE (elt->exp) != ZERO_EXTEND
3438 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3439 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode)
3441 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
3443 if (GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3444 op0 = fold_rtx (op0, NULL_RTX);
3446 op0 = equiv_constant (op0);
3448 new = simplify_unary_operation (GET_CODE (elt->exp), mode,
3451 else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2'
3452 || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c')
3453 && eltcode != DIV && eltcode != MOD
3454 && eltcode != UDIV && eltcode != UMOD
3455 && eltcode != ASHIFTRT && eltcode != LSHIFTRT
3456 && eltcode != ROTATE && eltcode != ROTATERT
3457 && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3458 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
3460 || CONSTANT_P (XEXP (elt->exp, 0)))
3461 && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
3462 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
3464 || CONSTANT_P (XEXP (elt->exp, 1))))
3466 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
3467 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
3469 if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3470 op0 = fold_rtx (op0, NULL_RTX);
3473 op0 = equiv_constant (op0);
3475 if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1))
3476 op1 = fold_rtx (op1, NULL_RTX);
3479 op1 = equiv_constant (op1);
3481 /* If we are looking for the low SImode part of
3482 (ashift:DI c (const_int 32)), it doesn't work
3483 to compute that in SImode, because a 32-bit shift
3484 in SImode is unpredictable. We know the value is 0. */
3486 && GET_CODE (elt->exp) == ASHIFT
3487 && GET_CODE (op1) == CONST_INT
3488 && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
3490 if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
3492 /* If the count fits in the inner mode's width,
3493 but exceeds the outer mode's width,
3494 the value will get truncated to 0
3498 /* If the count exceeds even the inner mode's width,
3499 don't fold this expression. */
3502 else if (op0 && op1)
3503 new = simplify_binary_operation (GET_CODE (elt->exp), mode,
3507 else if (GET_CODE (elt->exp) == SUBREG
3508 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3509 && (GET_MODE_SIZE (GET_MODE (folded_arg0))
3511 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3512 new = copy_rtx (SUBREG_REG (elt->exp));
3523 /* If we have (NOT Y), see if Y is known to be (NOT Z).
3524 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
3525 new = lookup_as_function (XEXP (x, 0), code);
3527 return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
3531 /* If we are not actually processing an insn, don't try to find the
3532 best address. Not only don't we care, but we could modify the
3533 MEM in an invalid way since we have no insn to validate against. */
3535 find_best_addr (insn, &XEXP (x, 0), GET_MODE (x));
3538 /* Even if we don't fold in the insn itself,
3539 we can safely do so here, in hopes of getting a constant. */
3540 rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
3542 HOST_WIDE_INT offset = 0;
3544 if (GET_CODE (addr) == REG
3545 && REGNO_QTY_VALID_P (REGNO (addr)))
3547 int addr_q = REG_QTY (REGNO (addr));
3548 struct qty_table_elem *addr_ent = &qty_table[addr_q];
3550 if (GET_MODE (addr) == addr_ent->mode
3551 && addr_ent->const_rtx != NULL_RTX)
3552 addr = addr_ent->const_rtx;
3555 /* If address is constant, split it into a base and integer offset. */
3556 if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
3558 else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
3559 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
3561 base = XEXP (XEXP (addr, 0), 0);
3562 offset = INTVAL (XEXP (XEXP (addr, 0), 1));
3564 else if (GET_CODE (addr) == LO_SUM
3565 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
3566 base = XEXP (addr, 1);
3567 else if (GET_CODE (addr) == ADDRESSOF)
3568 return change_address (x, VOIDmode, addr);
3570 /* If this is a constant pool reference, we can fold it into its
3571 constant to allow better value tracking. */
3572 if (base && GET_CODE (base) == SYMBOL_REF
3573 && CONSTANT_POOL_ADDRESS_P (base))
3575 rtx constant = get_pool_constant (base);
3576 enum machine_mode const_mode = get_pool_mode (base);
3579 if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
3580 constant_pool_entries_cost = COST (constant);
3582 /* If we are loading the full constant, we have an equivalence. */
3583 if (offset == 0 && mode == const_mode)
3586 /* If this actually isn't a constant (weird!), we can't do
3587 anything. Otherwise, handle the two most common cases:
3588 extracting a word from a multi-word constant, and extracting
3589 the low-order bits. Other cases don't seem common enough to
3591 if (! CONSTANT_P (constant))
3594 if (GET_MODE_CLASS (mode) == MODE_INT
3595 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3596 && offset % UNITS_PER_WORD == 0
3597 && (new = operand_subword (constant,
3598 offset / UNITS_PER_WORD,
3599 0, const_mode)) != 0)
3602 if (((BYTES_BIG_ENDIAN
3603 && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
3604 || (! BYTES_BIG_ENDIAN && offset == 0))
3605 && (new = gen_lowpart_if_possible (mode, constant)) != 0)
3609 /* If this is a reference to a label at a known position in a jump
3610 table, we also know its value. */
3611 if (base && GET_CODE (base) == LABEL_REF)
3613 rtx label = XEXP (base, 0);
3614 rtx table_insn = NEXT_INSN (label);
3616 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3617 && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
3619 rtx table = PATTERN (table_insn);
3622 && (offset / GET_MODE_SIZE (GET_MODE (table))
3623 < XVECLEN (table, 0)))
3624 return XVECEXP (table, 0,
3625 offset / GET_MODE_SIZE (GET_MODE (table)));
3627 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3628 && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
3630 rtx table = PATTERN (table_insn);
3633 && (offset / GET_MODE_SIZE (GET_MODE (table))
3634 < XVECLEN (table, 1)))
3636 offset /= GET_MODE_SIZE (GET_MODE (table));
3637 new = gen_rtx_MINUS (Pmode, XVECEXP (table, 1, offset),
3640 if (GET_MODE (table) != Pmode)
3641 new = gen_rtx_TRUNCATE (GET_MODE (table), new);
3643 /* Indicate this is a constant. This isn't a
3644 valid form of CONST, but it will only be used
3645 to fold the next insns and then discarded, so
3648 Note this expression must be explicitly discarded,
3649 by cse_insn, else it may end up in a REG_EQUAL note
3650 and "escape" to cause problems elsewhere. */
3651 return gen_rtx_CONST (GET_MODE (new), new);
3659 #ifdef NO_FUNCTION_CSE
3661 if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3667 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3668 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3669 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3679 mode_arg0 = VOIDmode;
3681 /* Try folding our operands.
3682 Then see which ones have constant values known. */
3684 fmt = GET_RTX_FORMAT (code);
3685 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3688 rtx arg = XEXP (x, i);
3689 rtx folded_arg = arg, const_arg = 0;
3690 enum machine_mode mode_arg = GET_MODE (arg);
3691 rtx cheap_arg, expensive_arg;
3692 rtx replacements[2];
3695 /* Most arguments are cheap, so handle them specially. */
3696 switch (GET_CODE (arg))
3699 /* This is the same as calling equiv_constant; it is duplicated
3701 if (REGNO_QTY_VALID_P (REGNO (arg)))
3703 int arg_q = REG_QTY (REGNO (arg));
3704 struct qty_table_elem *arg_ent = &qty_table[arg_q];
3706 if (arg_ent->const_rtx != NULL_RTX
3707 && GET_CODE (arg_ent->const_rtx) != REG
3708 && GET_CODE (arg_ent->const_rtx) != PLUS)
3710 = gen_lowpart_if_possible (GET_MODE (arg),
3711 arg_ent->const_rtx);
3725 folded_arg = prev_insn_cc0;
3726 mode_arg = prev_insn_cc0_mode;
3727 const_arg = equiv_constant (folded_arg);
3732 folded_arg = fold_rtx (arg, insn);
3733 const_arg = equiv_constant (folded_arg);
3736 /* For the first three operands, see if the operand
3737 is constant or equivalent to a constant. */
3741 folded_arg0 = folded_arg;
3742 const_arg0 = const_arg;
3743 mode_arg0 = mode_arg;
3746 folded_arg1 = folded_arg;
3747 const_arg1 = const_arg;
3750 const_arg2 = const_arg;
3754 /* Pick the least expensive of the folded argument and an
3755 equivalent constant argument. */
3756 if (const_arg == 0 || const_arg == folded_arg
3757 || COST_IN (const_arg, code) > COST_IN (folded_arg, code))
3758 cheap_arg = folded_arg, expensive_arg = const_arg;
3760 cheap_arg = const_arg, expensive_arg = folded_arg;
3762 /* Try to replace the operand with the cheapest of the two
3763 possibilities. If it doesn't work and this is either of the first
3764 two operands of a commutative operation, try swapping them.
3765 If THAT fails, try the more expensive, provided it is cheaper
3766 than what is already there. */
3768 if (cheap_arg == XEXP (x, i))
3771 if (insn == 0 && ! copied)
3777 /* Order the replacements from cheapest to most expensive. */
3778 replacements[0] = cheap_arg;
3779 replacements[1] = expensive_arg;
3781 for (j = 0; j < 2 && replacements[j]; j++)
3783 int old_cost = COST_IN (XEXP (x, i), code);
3784 int new_cost = COST_IN (replacements[j], code);
3786 /* Stop if what existed before was cheaper. Prefer constants
3787 in the case of a tie. */
3788 if (new_cost > old_cost
3789 || (new_cost == old_cost && CONSTANT_P (XEXP (x, i))))
3792 if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
3795 if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c')
3797 validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
3798 validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
3800 if (apply_change_group ())
3802 /* Swap them back to be invalid so that this loop can
3803 continue and flag them to be swapped back later. */
3806 tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
3818 /* Don't try to fold inside of a vector of expressions.
3819 Doing nothing is harmless. */
3823 /* If a commutative operation, place a constant integer as the second
3824 operand unless the first operand is also a constant integer. Otherwise,
3825 place any constant second unless the first operand is also a constant. */
3827 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3829 if (must_swap || (const_arg0
3831 || (GET_CODE (const_arg0) == CONST_INT
3832 && GET_CODE (const_arg1) != CONST_INT))))
3834 register rtx tem = XEXP (x, 0);
3836 if (insn == 0 && ! copied)
3842 validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
3843 validate_change (insn, &XEXP (x, 1), tem, 1);
3844 if (apply_change_group ())
3846 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3847 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3852 /* If X is an arithmetic operation, see if we can simplify it. */
3854 switch (GET_RTX_CLASS (code))
3860 /* We can't simplify extension ops unless we know the
3862 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3863 && mode_arg0 == VOIDmode)
3866 /* If we had a CONST, strip it off and put it back later if we
3868 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3869 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3871 new = simplify_unary_operation (code, mode,
3872 const_arg0 ? const_arg0 : folded_arg0,
3874 if (new != 0 && is_const)
3875 new = gen_rtx_CONST (mode, new);
3880 /* See what items are actually being compared and set FOLDED_ARG[01]
3881 to those values and CODE to the actual comparison code. If any are
3882 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3883 do anything if both operands are already known to be constant. */
3885 if (const_arg0 == 0 || const_arg1 == 0)
3887 struct table_elt *p0, *p1;
3888 rtx true = const_true_rtx, false = const0_rtx;
3889 enum machine_mode mode_arg1;
3891 #ifdef FLOAT_STORE_FLAG_VALUE
3892 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3894 true = (CONST_DOUBLE_FROM_REAL_VALUE
3895 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3896 false = CONST0_RTX (mode);
3900 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3901 &mode_arg0, &mode_arg1);
3902 const_arg0 = equiv_constant (folded_arg0);
3903 const_arg1 = equiv_constant (folded_arg1);
3905 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3906 what kinds of things are being compared, so we can't do
3907 anything with this comparison. */
3909 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3912 /* If we do not now have two constants being compared, see
3913 if we can nevertheless deduce some things about the
3915 if (const_arg0 == 0 || const_arg1 == 0)
3917 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or
3918 non-explicit constant? These aren't zero, but we
3919 don't know their sign. */
3920 if (const_arg1 == const0_rtx
3921 && (NONZERO_BASE_PLUS_P (folded_arg0)
3922 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
3924 || GET_CODE (folded_arg0) == SYMBOL_REF
3926 || GET_CODE (folded_arg0) == LABEL_REF
3927 || GET_CODE (folded_arg0) == CONST))
3931 else if (code == NE)
3935 /* See if the two operands are the same. We don't do this
3936 for IEEE floating-point since we can't assume x == x
3937 since x might be a NaN. */
3939 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3940 || ! FLOAT_MODE_P (mode_arg0) || flag_fast_math)
3941 && (folded_arg0 == folded_arg1
3942 || (GET_CODE (folded_arg0) == REG
3943 && GET_CODE (folded_arg1) == REG
3944 && (REG_QTY (REGNO (folded_arg0))
3945 == REG_QTY (REGNO (folded_arg1))))
3946 || ((p0 = lookup (folded_arg0,
3947 (safe_hash (folded_arg0, mode_arg0)
3948 & HASH_MASK), mode_arg0))
3949 && (p1 = lookup (folded_arg1,
3950 (safe_hash (folded_arg1, mode_arg0)
3951 & HASH_MASK), mode_arg0))
3952 && p0->first_same_value == p1->first_same_value)))
3953 return ((code == EQ || code == LE || code == GE
3954 || code == LEU || code == GEU)
3957 /* If FOLDED_ARG0 is a register, see if the comparison we are
3958 doing now is either the same as we did before or the reverse
3959 (we only check the reverse if not floating-point). */
3960 else if (GET_CODE (folded_arg0) == REG)
3962 int qty = REG_QTY (REGNO (folded_arg0));
3964 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3966 struct qty_table_elem *ent = &qty_table[qty];
3968 if ((comparison_dominates_p (ent->comparison_code, code)
3969 || (! FLOAT_MODE_P (mode_arg0)
3970 && comparison_dominates_p (ent->comparison_code,
3971 reverse_condition (code))))
3972 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3974 && rtx_equal_p (ent->comparison_const,
3976 || (GET_CODE (folded_arg1) == REG
3977 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3978 return (comparison_dominates_p (ent->comparison_code, code)
3985 /* If we are comparing against zero, see if the first operand is
3986 equivalent to an IOR with a constant. If so, we may be able to
3987 determine the result of this comparison. */
3989 if (const_arg1 == const0_rtx)
3991 rtx y = lookup_as_function (folded_arg0, IOR);
3995 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3996 && GET_CODE (inner_const) == CONST_INT
3997 && INTVAL (inner_const) != 0)
3999 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
4000 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
4001 && (INTVAL (inner_const)
4002 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
4003 rtx true = const_true_rtx, false = const0_rtx;
4005 #ifdef FLOAT_STORE_FLAG_VALUE
4006 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
4008 true = (CONST_DOUBLE_FROM_REAL_VALUE
4009 (FLOAT_STORE_FLAG_VALUE (mode), mode));
4010 false = CONST0_RTX (mode);
4034 new = simplify_relational_operation (code,
4035 (mode_arg0 != VOIDmode
4037 : (GET_MODE (const_arg0
4041 ? GET_MODE (const_arg0
4044 : GET_MODE (const_arg1
4047 const_arg0 ? const_arg0 : folded_arg0,
4048 const_arg1 ? const_arg1 : folded_arg1);
4049 #ifdef FLOAT_STORE_FLAG_VALUE
4050 if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT)
4052 if (new == const0_rtx)
4053 new = CONST0_RTX (mode);
4055 new = (CONST_DOUBLE_FROM_REAL_VALUE
4056 (FLOAT_STORE_FLAG_VALUE (mode), mode));
4066 /* If the second operand is a LABEL_REF, see if the first is a MINUS
4067 with that LABEL_REF as its second operand. If so, the result is
4068 the first operand of that MINUS. This handles switches with an
4069 ADDR_DIFF_VEC table. */
4070 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
4073 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
4074 : lookup_as_function (folded_arg0, MINUS);
4076 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4077 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
4080 /* Now try for a CONST of a MINUS like the above. */
4081 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
4082 : lookup_as_function (folded_arg0, CONST))) != 0
4083 && GET_CODE (XEXP (y, 0)) == MINUS
4084 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4085 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
4086 return XEXP (XEXP (y, 0), 0);
4089 /* Likewise if the operands are in the other order. */
4090 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
4093 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
4094 : lookup_as_function (folded_arg1, MINUS);
4096 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4097 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
4100 /* Now try for a CONST of a MINUS like the above. */
4101 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
4102 : lookup_as_function (folded_arg1, CONST))) != 0
4103 && GET_CODE (XEXP (y, 0)) == MINUS
4104 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4105 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
4106 return XEXP (XEXP (y, 0), 0);
4109 /* If second operand is a register equivalent to a negative
4110 CONST_INT, see if we can find a register equivalent to the
4111 positive constant. Make a MINUS if so. Don't do this for
4112 a non-negative constant since we might then alternate between
4113 chosing positive and negative constants. Having the positive
4114 constant previously-used is the more common case. Be sure
4115 the resulting constant is non-negative; if const_arg1 were
4116 the smallest negative number this would overflow: depending
4117 on the mode, this would either just be the same value (and
4118 hence not save anything) or be incorrect. */
4119 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
4120 && INTVAL (const_arg1) < 0
4121 /* This used to test
4123 -INTVAL (const_arg1) >= 0
4125 But The Sun V5.0 compilers mis-compiled that test. So
4126 instead we test for the problematic value in a more direct
4127 manner and hope the Sun compilers get it correct. */
4128 && INTVAL (const_arg1) !=
4129 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
4130 && GET_CODE (folded_arg1) == REG)
4132 rtx new_const = GEN_INT (-INTVAL (const_arg1));
4134 = lookup (new_const, safe_hash (new_const, mode) & HASH_MASK,
4138 for (p = p->first_same_value; p; p = p->next_same_value)
4139 if (GET_CODE (p->exp) == REG)
4140 return simplify_gen_binary (MINUS, mode, folded_arg0,
4141 canon_reg (p->exp, NULL_RTX));
4146 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
4147 If so, produce (PLUS Z C2-C). */
4148 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
4150 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
4151 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
4152 return fold_rtx (plus_constant (copy_rtx (y),
4153 -INTVAL (const_arg1)),
4160 case SMIN: case SMAX: case UMIN: case UMAX:
4161 case IOR: case AND: case XOR:
4162 case MULT: case DIV: case UDIV:
4163 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
4164 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
4165 is known to be of similar form, we may be able to replace the
4166 operation with a combined operation. This may eliminate the
4167 intermediate operation if every use is simplified in this way.
4168 Note that the similar optimization done by combine.c only works
4169 if the intermediate operation's result has only one reference. */
4171 if (GET_CODE (folded_arg0) == REG
4172 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
4175 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
4176 rtx y = lookup_as_function (folded_arg0, code);
4178 enum rtx_code associate_code;
4182 || 0 == (inner_const
4183 = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
4184 || GET_CODE (inner_const) != CONST_INT
4185 /* If we have compiled a statement like
4186 "if (x == (x & mask1))", and now are looking at
4187 "x & mask2", we will have a case where the first operand
4188 of Y is the same as our first operand. Unless we detect
4189 this case, an infinite loop will result. */
4190 || XEXP (y, 0) == folded_arg0)
4193 /* Don't associate these operations if they are a PLUS with the
4194 same constant and it is a power of two. These might be doable
4195 with a pre- or post-increment. Similarly for two subtracts of
4196 identical powers of two with post decrement. */
4198 if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
4199 && ((HAVE_PRE_INCREMENT
4200 && exact_log2 (INTVAL (const_arg1)) >= 0)
4201 || (HAVE_POST_INCREMENT
4202 && exact_log2 (INTVAL (const_arg1)) >= 0)
4203 || (HAVE_PRE_DECREMENT
4204 && exact_log2 (- INTVAL (const_arg1)) >= 0)
4205 || (HAVE_POST_DECREMENT
4206 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
4209 /* Compute the code used to compose the constants. For example,
4210 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
4213 = (code == MULT || code == DIV || code == UDIV ? MULT
4214 : is_shift || code == PLUS || code == MINUS ? PLUS : code);
4216 new_const = simplify_binary_operation (associate_code, mode,
4217 const_arg1, inner_const);
4222 /* If we are associating shift operations, don't let this
4223 produce a shift of the size of the object or larger.
4224 This could occur when we follow a sign-extend by a right
4225 shift on a machine that does a sign-extend as a pair
4228 if (is_shift && GET_CODE (new_const) == CONST_INT
4229 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
4231 /* As an exception, we can turn an ASHIFTRT of this
4232 form into a shift of the number of bits - 1. */
4233 if (code == ASHIFTRT)
4234 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
4239 y = copy_rtx (XEXP (y, 0));
4241 /* If Y contains our first operand (the most common way this
4242 can happen is if Y is a MEM), we would do into an infinite
4243 loop if we tried to fold it. So don't in that case. */
4245 if (! reg_mentioned_p (folded_arg0, y))
4246 y = fold_rtx (y, insn);
4248 return simplify_gen_binary (code, mode, y, new_const);
4256 new = simplify_binary_operation (code, mode,
4257 const_arg0 ? const_arg0 : folded_arg0,
4258 const_arg1 ? const_arg1 : folded_arg1);
4262 /* (lo_sum (high X) X) is simply X. */
4263 if (code == LO_SUM && const_arg0 != 0
4264 && GET_CODE (const_arg0) == HIGH
4265 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
4271 new = simplify_ternary_operation (code, mode, mode_arg0,
4272 const_arg0 ? const_arg0 : folded_arg0,
4273 const_arg1 ? const_arg1 : folded_arg1,
4274 const_arg2 ? const_arg2 : XEXP (x, 2));
4278 /* Always eliminate CONSTANT_P_RTX at this stage. */
4279 if (code == CONSTANT_P_RTX)
4280 return (const_arg0 ? const1_rtx : const0_rtx);
4284 return new ? new : x;
4287 /* Return a constant value currently equivalent to X.
4288 Return 0 if we don't know one. */
4294 if (GET_CODE (x) == REG
4295 && REGNO_QTY_VALID_P (REGNO (x)))
4297 int x_q = REG_QTY (REGNO (x));
4298 struct qty_table_elem *x_ent = &qty_table[x_q];
4300 if (x_ent->const_rtx)
4301 x = gen_lowpart_if_possible (GET_MODE (x), x_ent->const_rtx);
4304 if (x == 0 || CONSTANT_P (x))
4307 /* If X is a MEM, try to fold it outside the context of any insn to see if
4308 it might be equivalent to a constant. That handles the case where it
4309 is a constant-pool reference. Then try to look it up in the hash table
4310 in case it is something whose value we have seen before. */
4312 if (GET_CODE (x) == MEM)
4314 struct table_elt *elt;
4316 x = fold_rtx (x, NULL_RTX);
4320 elt = lookup (x, safe_hash (x, GET_MODE (x)) & HASH_MASK, GET_MODE (x));
4324 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
4325 if (elt->is_const && CONSTANT_P (elt->exp))
4332 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4333 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4334 least-significant part of X.
4335 MODE specifies how big a part of X to return.
4337 If the requested operation cannot be done, 0 is returned.
4339 This is similar to gen_lowpart in emit-rtl.c. */
4342 gen_lowpart_if_possible (mode, x)
4343 enum machine_mode mode;
4346 rtx result = gen_lowpart_common (mode, x);
4350 else if (GET_CODE (x) == MEM)
4352 /* This is the only other case we handle. */
4353 register int offset = 0;
4356 if (WORDS_BIG_ENDIAN)
4357 offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
4358 - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
4359 if (BYTES_BIG_ENDIAN)
4360 /* Adjust the address so that the address-after-the-data is
4362 offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode))
4363 - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
4364 new = gen_rtx_MEM (mode, plus_constant (XEXP (x, 0), offset));
4365 if (! memory_address_p (mode, XEXP (new, 0)))
4367 MEM_COPY_ATTRIBUTES (new, x);
4374 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4375 branch. It will be zero if not.
4377 In certain cases, this can cause us to add an equivalence. For example,
4378 if we are following the taken case of
4380 we can add the fact that `i' and '2' are now equivalent.
4382 In any case, we can record that this comparison was passed. If the same
4383 comparison is seen later, we will know its value. */
4386 record_jump_equiv (insn, taken)
4390 int cond_known_true;
4393 enum machine_mode mode, mode0, mode1;
4394 int reversed_nonequality = 0;
4397 /* Ensure this is the right kind of insn. */
4398 if (! any_condjump_p (insn))
4400 set = pc_set (insn);
4402 /* See if this jump condition is known true or false. */
4404 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
4406 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
4408 /* Get the type of comparison being done and the operands being compared.
4409 If we had to reverse a non-equality condition, record that fact so we
4410 know that it isn't valid for floating-point. */
4411 code = GET_CODE (XEXP (SET_SRC (set), 0));
4412 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
4413 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
4415 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
4416 if (! cond_known_true)
4418 reversed_nonequality = (code != EQ && code != NE);
4419 code = reverse_condition (code);
4421 /* Don't remember if we can't find the inverse. */
4422 if (code == UNKNOWN)
4426 /* The mode is the mode of the non-constant. */
4428 if (mode1 != VOIDmode)
4431 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
4434 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
4435 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
4436 Make any useful entries we can with that information. Called from
4437 above function and called recursively. */
4440 record_jump_cond (code, mode, op0, op1, reversed_nonequality)
4442 enum machine_mode mode;
4444 int reversed_nonequality;
4446 unsigned op0_hash, op1_hash;
4447 int op0_in_memory, op1_in_memory;
4448 struct table_elt *op0_elt, *op1_elt;
4450 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
4451 we know that they are also equal in the smaller mode (this is also
4452 true for all smaller modes whether or not there is a SUBREG, but
4453 is not worth testing for with no SUBREG). */
4455 /* Note that GET_MODE (op0) may not equal MODE. */
4456 if (code == EQ && GET_CODE (op0) == SUBREG
4457 && (GET_MODE_SIZE (GET_MODE (op0))
4458 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4460 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4461 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4463 record_jump_cond (code, mode, SUBREG_REG (op0),
4464 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4465 reversed_nonequality);
4468 if (code == EQ && GET_CODE (op1) == SUBREG
4469 && (GET_MODE_SIZE (GET_MODE (op1))
4470 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4472 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4473 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4475 record_jump_cond (code, mode, SUBREG_REG (op1),
4476 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4477 reversed_nonequality);
4480 /* Similarly, if this is an NE comparison, and either is a SUBREG
4481 making a smaller mode, we know the whole thing is also NE. */
4483 /* Note that GET_MODE (op0) may not equal MODE;
4484 if we test MODE instead, we can get an infinite recursion
4485 alternating between two modes each wider than MODE. */
4487 if (code == NE && GET_CODE (op0) == SUBREG
4488 && subreg_lowpart_p (op0)
4489 && (GET_MODE_SIZE (GET_MODE (op0))
4490 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4492 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4493 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4495 record_jump_cond (code, mode, SUBREG_REG (op0),
4496 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4497 reversed_nonequality);
4500 if (code == NE && GET_CODE (op1) == SUBREG
4501 && subreg_lowpart_p (op1)
4502 && (GET_MODE_SIZE (GET_MODE (op1))
4503 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4505 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4506 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4508 record_jump_cond (code, mode, SUBREG_REG (op1),
4509 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4510 reversed_nonequality);
4513 /* Hash both operands. */
4516 hash_arg_in_memory = 0;
4517 op0_hash = HASH (op0, mode);
4518 op0_in_memory = hash_arg_in_memory;
4524 hash_arg_in_memory = 0;
4525 op1_hash = HASH (op1, mode);
4526 op1_in_memory = hash_arg_in_memory;
4531 /* Look up both operands. */
4532 op0_elt = lookup (op0, op0_hash, mode);
4533 op1_elt = lookup (op1, op1_hash, mode);
4535 /* If both operands are already equivalent or if they are not in the
4536 table but are identical, do nothing. */
4537 if ((op0_elt != 0 && op1_elt != 0
4538 && op0_elt->first_same_value == op1_elt->first_same_value)
4539 || op0 == op1 || rtx_equal_p (op0, op1))
4542 /* If we aren't setting two things equal all we can do is save this
4543 comparison. Similarly if this is floating-point. In the latter
4544 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4545 If we record the equality, we might inadvertently delete code
4546 whose intent was to change -0 to +0. */
4548 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
4550 struct qty_table_elem *ent;
4553 /* If we reversed a floating-point comparison, if OP0 is not a
4554 register, or if OP1 is neither a register or constant, we can't
4557 if (GET_CODE (op1) != REG)
4558 op1 = equiv_constant (op1);
4560 if ((reversed_nonequality && FLOAT_MODE_P (mode))
4561 || GET_CODE (op0) != REG || op1 == 0)
4564 /* Put OP0 in the hash table if it isn't already. This gives it a
4565 new quantity number. */
4568 if (insert_regs (op0, NULL_PTR, 0))
4570 rehash_using_reg (op0);
4571 op0_hash = HASH (op0, mode);
4573 /* If OP0 is contained in OP1, this changes its hash code
4574 as well. Faster to rehash than to check, except
4575 for the simple case of a constant. */
4576 if (! CONSTANT_P (op1))
4577 op1_hash = HASH (op1,mode);
4580 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
4581 op0_elt->in_memory = op0_in_memory;
4584 qty = REG_QTY (REGNO (op0));
4585 ent = &qty_table[qty];
4587 ent->comparison_code = code;
4588 if (GET_CODE (op1) == REG)
4590 /* Look it up again--in case op0 and op1 are the same. */
4591 op1_elt = lookup (op1, op1_hash, mode);
4593 /* Put OP1 in the hash table so it gets a new quantity number. */
4596 if (insert_regs (op1, NULL_PTR, 0))
4598 rehash_using_reg (op1);
4599 op1_hash = HASH (op1, mode);
4602 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
4603 op1_elt->in_memory = op1_in_memory;
4606 ent->comparison_const = NULL_RTX;
4607 ent->comparison_qty = REG_QTY (REGNO (op1));
4611 ent->comparison_const = op1;
4612 ent->comparison_qty = -1;
4618 /* If either side is still missing an equivalence, make it now,
4619 then merge the equivalences. */
4623 if (insert_regs (op0, NULL_PTR, 0))
4625 rehash_using_reg (op0);
4626 op0_hash = HASH (op0, mode);
4629 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
4630 op0_elt->in_memory = op0_in_memory;
4635 if (insert_regs (op1, NULL_PTR, 0))
4637 rehash_using_reg (op1);
4638 op1_hash = HASH (op1, mode);
4641 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
4642 op1_elt->in_memory = op1_in_memory;
4645 merge_equiv_classes (op0_elt, op1_elt);
4646 last_jump_equiv_class = op0_elt;
4649 /* CSE processing for one instruction.
4650 First simplify sources and addresses of all assignments
4651 in the instruction, using previously-computed equivalents values.
4652 Then install the new sources and destinations in the table
4653 of available values.
4655 If LIBCALL_INSN is nonzero, don't record any equivalence made in
4656 the insn. It means that INSN is inside libcall block. In this
4657 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
4659 /* Data on one SET contained in the instruction. */
4663 /* The SET rtx itself. */
4665 /* The SET_SRC of the rtx (the original value, if it is changing). */
4667 /* The hash-table element for the SET_SRC of the SET. */
4668 struct table_elt *src_elt;
4669 /* Hash value for the SET_SRC. */
4671 /* Hash value for the SET_DEST. */
4673 /* The SET_DEST, with SUBREG, etc., stripped. */
4675 /* Nonzero if the SET_SRC is in memory. */
4677 /* Nonzero if the SET_SRC contains something
4678 whose value cannot be predicted and understood. */
4680 /* Original machine mode, in case it becomes a CONST_INT. */
4681 enum machine_mode mode;
4682 /* A constant equivalent for SET_SRC, if any. */
4684 /* Original SET_SRC value used for libcall notes. */
4686 /* Hash value of constant equivalent for SET_SRC. */
4687 unsigned src_const_hash;
4688 /* Table entry for constant equivalent for SET_SRC, if any. */
4689 struct table_elt *src_const_elt;
4693 cse_insn (insn, libcall_insn)
4697 register rtx x = PATTERN (insn);
4700 register int n_sets = 0;
4703 /* Records what this insn does to set CC0. */
4704 rtx this_insn_cc0 = 0;
4705 enum machine_mode this_insn_cc0_mode = VOIDmode;
4709 struct table_elt *src_eqv_elt = 0;
4710 int src_eqv_volatile = 0;
4711 int src_eqv_in_memory = 0;
4712 unsigned src_eqv_hash = 0;
4714 struct set *sets = (struct set *) NULL_PTR;
4718 /* Find all the SETs and CLOBBERs in this instruction.
4719 Record all the SETs in the array `set' and count them.
4720 Also determine whether there is a CLOBBER that invalidates
4721 all memory references, or all references at varying addresses. */
4723 if (GET_CODE (insn) == CALL_INSN)
4725 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4726 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4727 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4730 if (GET_CODE (x) == SET)
4732 sets = (struct set *) alloca (sizeof (struct set));
4735 /* Ignore SETs that are unconditional jumps.
4736 They never need cse processing, so this does not hurt.
4737 The reason is not efficiency but rather
4738 so that we can test at the end for instructions
4739 that have been simplified to unconditional jumps
4740 and not be misled by unchanged instructions
4741 that were unconditional jumps to begin with. */
4742 if (SET_DEST (x) == pc_rtx
4743 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4746 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4747 The hard function value register is used only once, to copy to
4748 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4749 Ensure we invalidate the destination register. On the 80386 no
4750 other code would invalidate it since it is a fixed_reg.
4751 We need not check the return of apply_change_group; see canon_reg. */
4753 else if (GET_CODE (SET_SRC (x)) == CALL)
4755 canon_reg (SET_SRC (x), insn);
4756 apply_change_group ();
4757 fold_rtx (SET_SRC (x), insn);
4758 invalidate (SET_DEST (x), VOIDmode);
4763 else if (GET_CODE (x) == PARALLEL)
4765 register int lim = XVECLEN (x, 0);
4767 sets = (struct set *) alloca (lim * sizeof (struct set));
4769 /* Find all regs explicitly clobbered in this insn,
4770 and ensure they are not replaced with any other regs
4771 elsewhere in this insn.
4772 When a reg that is clobbered is also used for input,
4773 we should presume that that is for a reason,
4774 and we should not substitute some other register
4775 which is not supposed to be clobbered.
4776 Therefore, this loop cannot be merged into the one below
4777 because a CALL may precede a CLOBBER and refer to the
4778 value clobbered. We must not let a canonicalization do
4779 anything in that case. */
4780 for (i = 0; i < lim; i++)
4782 register rtx y = XVECEXP (x, 0, i);
4783 if (GET_CODE (y) == CLOBBER)
4785 rtx clobbered = XEXP (y, 0);
4787 if (GET_CODE (clobbered) == REG
4788 || GET_CODE (clobbered) == SUBREG)
4789 invalidate (clobbered, VOIDmode);
4790 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4791 || GET_CODE (clobbered) == ZERO_EXTRACT)
4792 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4796 for (i = 0; i < lim; i++)
4798 register rtx y = XVECEXP (x, 0, i);
4799 if (GET_CODE (y) == SET)
4801 /* As above, we ignore unconditional jumps and call-insns and
4802 ignore the result of apply_change_group. */
4803 if (GET_CODE (SET_SRC (y)) == CALL)
4805 canon_reg (SET_SRC (y), insn);
4806 apply_change_group ();
4807 fold_rtx (SET_SRC (y), insn);
4808 invalidate (SET_DEST (y), VOIDmode);
4810 else if (SET_DEST (y) == pc_rtx
4811 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4814 sets[n_sets++].rtl = y;
4816 else if (GET_CODE (y) == CLOBBER)
4818 /* If we clobber memory, canon the address.
4819 This does nothing when a register is clobbered
4820 because we have already invalidated the reg. */
4821 if (GET_CODE (XEXP (y, 0)) == MEM)
4822 canon_reg (XEXP (y, 0), NULL_RTX);
4824 else if (GET_CODE (y) == USE
4825 && ! (GET_CODE (XEXP (y, 0)) == REG
4826 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4827 canon_reg (y, NULL_RTX);
4828 else if (GET_CODE (y) == CALL)
4830 /* The result of apply_change_group can be ignored; see
4832 canon_reg (y, insn);
4833 apply_change_group ();
4838 else if (GET_CODE (x) == CLOBBER)
4840 if (GET_CODE (XEXP (x, 0)) == MEM)
4841 canon_reg (XEXP (x, 0), NULL_RTX);
4844 /* Canonicalize a USE of a pseudo register or memory location. */
4845 else if (GET_CODE (x) == USE
4846 && ! (GET_CODE (XEXP (x, 0)) == REG
4847 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4848 canon_reg (XEXP (x, 0), NULL_RTX);
4849 else if (GET_CODE (x) == CALL)
4851 /* The result of apply_change_group can be ignored; see canon_reg. */
4852 canon_reg (x, insn);
4853 apply_change_group ();
4857 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4858 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4859 is handled specially for this case, and if it isn't set, then there will
4860 be no equivalence for the destination. */
4861 if (n_sets == 1 && REG_NOTES (insn) != 0
4862 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4863 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4864 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4865 src_eqv = canon_reg (XEXP (tem, 0), NULL_RTX);
4867 /* Canonicalize sources and addresses of destinations.
4868 We do this in a separate pass to avoid problems when a MATCH_DUP is
4869 present in the insn pattern. In that case, we want to ensure that
4870 we don't break the duplicate nature of the pattern. So we will replace
4871 both operands at the same time. Otherwise, we would fail to find an
4872 equivalent substitution in the loop calling validate_change below.
4874 We used to suppress canonicalization of DEST if it appears in SRC,
4875 but we don't do this any more. */
4877 for (i = 0; i < n_sets; i++)
4879 rtx dest = SET_DEST (sets[i].rtl);
4880 rtx src = SET_SRC (sets[i].rtl);
4881 rtx new = canon_reg (src, insn);
4884 sets[i].orig_src = src;
4885 if ((GET_CODE (new) == REG && GET_CODE (src) == REG
4886 && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
4887 != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
4888 || (insn_code = recog_memoized (insn)) < 0
4889 || insn_data[insn_code].n_dups > 0)
4890 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4892 SET_SRC (sets[i].rtl) = new;
4894 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4896 validate_change (insn, &XEXP (dest, 1),
4897 canon_reg (XEXP (dest, 1), insn), 1);
4898 validate_change (insn, &XEXP (dest, 2),
4899 canon_reg (XEXP (dest, 2), insn), 1);
4902 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
4903 || GET_CODE (dest) == ZERO_EXTRACT
4904 || GET_CODE (dest) == SIGN_EXTRACT)
4905 dest = XEXP (dest, 0);
4907 if (GET_CODE (dest) == MEM)
4908 canon_reg (dest, insn);
4911 /* Now that we have done all the replacements, we can apply the change
4912 group and see if they all work. Note that this will cause some
4913 canonicalizations that would have worked individually not to be applied
4914 because some other canonicalization didn't work, but this should not
4917 The result of apply_change_group can be ignored; see canon_reg. */
4919 apply_change_group ();
4921 /* Set sets[i].src_elt to the class each source belongs to.
4922 Detect assignments from or to volatile things
4923 and set set[i] to zero so they will be ignored
4924 in the rest of this function.
4926 Nothing in this loop changes the hash table or the register chains. */
4928 for (i = 0; i < n_sets; i++)
4930 register rtx src, dest;
4931 register rtx src_folded;
4932 register struct table_elt *elt = 0, *p;
4933 enum machine_mode mode;
4936 rtx src_related = 0;
4937 struct table_elt *src_const_elt = 0;
4938 int src_cost = MAX_COST, src_eqv_cost = MAX_COST, src_folded_cost = MAX_COST;
4939 int src_related_cost = MAX_COST, src_elt_cost = MAX_COST;
4940 int src_regcost, src_eqv_regcost, src_folded_regcost;
4941 int src_related_regcost, src_elt_regcost;
4942 /* Set non-zero if we need to call force_const_mem on with the
4943 contents of src_folded before using it. */
4944 int src_folded_force_flag = 0;
4946 dest = SET_DEST (sets[i].rtl);
4947 src = SET_SRC (sets[i].rtl);
4949 /* If SRC is a constant that has no machine mode,
4950 hash it with the destination's machine mode.
4951 This way we can keep different modes separate. */
4953 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4954 sets[i].mode = mode;
4958 enum machine_mode eqvmode = mode;
4959 if (GET_CODE (dest) == STRICT_LOW_PART)
4960 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4962 hash_arg_in_memory = 0;
4963 src_eqv = fold_rtx (src_eqv, insn);
4964 src_eqv_hash = HASH (src_eqv, eqvmode);
4966 /* Find the equivalence class for the equivalent expression. */
4969 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4971 src_eqv_volatile = do_not_record;
4972 src_eqv_in_memory = hash_arg_in_memory;
4975 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4976 value of the INNER register, not the destination. So it is not
4977 a valid substitution for the source. But save it for later. */
4978 if (GET_CODE (dest) == STRICT_LOW_PART)
4981 src_eqv_here = src_eqv;
4983 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4984 simplified result, which may not necessarily be valid. */
4985 src_folded = fold_rtx (src, insn);
4988 /* ??? This caused bad code to be generated for the m68k port with -O2.
4989 Suppose src is (CONST_INT -1), and that after truncation src_folded
4990 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4991 At the end we will add src and src_const to the same equivalence
4992 class. We now have 3 and -1 on the same equivalence class. This
4993 causes later instructions to be mis-optimized. */
4994 /* If storing a constant in a bitfield, pre-truncate the constant
4995 so we will be able to record it later. */
4996 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
4997 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
4999 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5001 if (GET_CODE (src) == CONST_INT
5002 && GET_CODE (width) == CONST_INT
5003 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5004 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5006 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
5007 << INTVAL (width)) - 1));
5011 /* Compute SRC's hash code, and also notice if it
5012 should not be recorded at all. In that case,
5013 prevent any further processing of this assignment. */
5015 hash_arg_in_memory = 0;
5018 sets[i].src_hash = HASH (src, mode);
5019 sets[i].src_volatile = do_not_record;
5020 sets[i].src_in_memory = hash_arg_in_memory;
5022 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
5023 a pseudo that is set more than once, do not record SRC. Using
5024 SRC as a replacement for anything else will be incorrect in that
5025 situation. Note that this usually occurs only for stack slots,
5026 in which case all the RTL would be referring to SRC, so we don't
5027 lose any optimization opportunities by not having SRC in the
5030 if (GET_CODE (src) == MEM
5031 && find_reg_note (insn, REG_EQUIV, src) != 0
5032 && GET_CODE (dest) == REG
5033 && REGNO (dest) >= FIRST_PSEUDO_REGISTER
5034 && REG_N_SETS (REGNO (dest)) != 1)
5035 sets[i].src_volatile = 1;
5038 /* It is no longer clear why we used to do this, but it doesn't
5039 appear to still be needed. So let's try without it since this
5040 code hurts cse'ing widened ops. */
5041 /* If source is a perverse subreg (such as QI treated as an SI),
5042 treat it as volatile. It may do the work of an SI in one context
5043 where the extra bits are not being used, but cannot replace an SI
5045 if (GET_CODE (src) == SUBREG
5046 && (GET_MODE_SIZE (GET_MODE (src))
5047 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
5048 sets[i].src_volatile = 1;
5051 /* Locate all possible equivalent forms for SRC. Try to replace
5052 SRC in the insn with each cheaper equivalent.
5054 We have the following types of equivalents: SRC itself, a folded
5055 version, a value given in a REG_EQUAL note, or a value related
5058 Each of these equivalents may be part of an additional class
5059 of equivalents (if more than one is in the table, they must be in
5060 the same class; we check for this).
5062 If the source is volatile, we don't do any table lookups.
5064 We note any constant equivalent for possible later use in a
5067 if (!sets[i].src_volatile)
5068 elt = lookup (src, sets[i].src_hash, mode);
5070 sets[i].src_elt = elt;
5072 if (elt && src_eqv_here && src_eqv_elt)
5074 if (elt->first_same_value != src_eqv_elt->first_same_value)
5076 /* The REG_EQUAL is indicating that two formerly distinct
5077 classes are now equivalent. So merge them. */
5078 merge_equiv_classes (elt, src_eqv_elt);
5079 src_eqv_hash = HASH (src_eqv, elt->mode);
5080 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
5086 else if (src_eqv_elt)
5089 /* Try to find a constant somewhere and record it in `src_const'.
5090 Record its table element, if any, in `src_const_elt'. Look in
5091 any known equivalences first. (If the constant is not in the
5092 table, also set `sets[i].src_const_hash'). */
5094 for (p = elt->first_same_value; p; p = p->next_same_value)
5098 src_const_elt = elt;
5103 && (CONSTANT_P (src_folded)
5104 /* Consider (minus (label_ref L1) (label_ref L2)) as
5105 "constant" here so we will record it. This allows us
5106 to fold switch statements when an ADDR_DIFF_VEC is used. */
5107 || (GET_CODE (src_folded) == MINUS
5108 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
5109 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
5110 src_const = src_folded, src_const_elt = elt;
5111 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
5112 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
5114 /* If we don't know if the constant is in the table, get its
5115 hash code and look it up. */
5116 if (src_const && src_const_elt == 0)
5118 sets[i].src_const_hash = HASH (src_const, mode);
5119 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
5122 sets[i].src_const = src_const;
5123 sets[i].src_const_elt = src_const_elt;
5125 /* If the constant and our source are both in the table, mark them as
5126 equivalent. Otherwise, if a constant is in the table but the source
5127 isn't, set ELT to it. */
5128 if (src_const_elt && elt
5129 && src_const_elt->first_same_value != elt->first_same_value)
5130 merge_equiv_classes (elt, src_const_elt);
5131 else if (src_const_elt && elt == 0)
5132 elt = src_const_elt;
5134 /* See if there is a register linearly related to a constant
5135 equivalent of SRC. */
5137 && (GET_CODE (src_const) == CONST
5138 || (src_const_elt && src_const_elt->related_value != 0)))
5140 src_related = use_related_value (src_const, src_const_elt);
5143 struct table_elt *src_related_elt
5144 = lookup (src_related, HASH (src_related, mode), mode);
5145 if (src_related_elt && elt)
5147 if (elt->first_same_value
5148 != src_related_elt->first_same_value)
5149 /* This can occur when we previously saw a CONST
5150 involving a SYMBOL_REF and then see the SYMBOL_REF
5151 twice. Merge the involved classes. */
5152 merge_equiv_classes (elt, src_related_elt);
5155 src_related_elt = 0;
5157 else if (src_related_elt && elt == 0)
5158 elt = src_related_elt;
5162 /* See if we have a CONST_INT that is already in a register in a
5165 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
5166 && GET_MODE_CLASS (mode) == MODE_INT
5167 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
5169 enum machine_mode wider_mode;
5171 for (wider_mode = GET_MODE_WIDER_MODE (mode);
5172 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
5173 && src_related == 0;
5174 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5176 struct table_elt *const_elt
5177 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
5182 for (const_elt = const_elt->first_same_value;
5183 const_elt; const_elt = const_elt->next_same_value)
5184 if (GET_CODE (const_elt->exp) == REG)
5186 src_related = gen_lowpart_if_possible (mode,
5193 /* Another possibility is that we have an AND with a constant in
5194 a mode narrower than a word. If so, it might have been generated
5195 as part of an "if" which would narrow the AND. If we already
5196 have done the AND in a wider mode, we can use a SUBREG of that
5199 if (flag_expensive_optimizations && ! src_related
5200 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
5201 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5203 enum machine_mode tmode;
5204 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
5206 for (tmode = GET_MODE_WIDER_MODE (mode);
5207 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5208 tmode = GET_MODE_WIDER_MODE (tmode))
5210 rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0));
5211 struct table_elt *larger_elt;
5215 PUT_MODE (new_and, tmode);
5216 XEXP (new_and, 0) = inner;
5217 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
5218 if (larger_elt == 0)
5221 for (larger_elt = larger_elt->first_same_value;
5222 larger_elt; larger_elt = larger_elt->next_same_value)
5223 if (GET_CODE (larger_elt->exp) == REG)
5226 = gen_lowpart_if_possible (mode, larger_elt->exp);
5236 #ifdef LOAD_EXTEND_OP
5237 /* See if a MEM has already been loaded with a widening operation;
5238 if it has, we can use a subreg of that. Many CISC machines
5239 also have such operations, but this is only likely to be
5240 beneficial these machines. */
5242 if (flag_expensive_optimizations && src_related == 0
5243 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5244 && GET_MODE_CLASS (mode) == MODE_INT
5245 && GET_CODE (src) == MEM && ! do_not_record
5246 && LOAD_EXTEND_OP (mode) != NIL)
5248 enum machine_mode tmode;
5250 /* Set what we are trying to extend and the operation it might
5251 have been extended with. */
5252 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
5253 XEXP (memory_extend_rtx, 0) = src;
5255 for (tmode = GET_MODE_WIDER_MODE (mode);
5256 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5257 tmode = GET_MODE_WIDER_MODE (tmode))
5259 struct table_elt *larger_elt;
5261 PUT_MODE (memory_extend_rtx, tmode);
5262 larger_elt = lookup (memory_extend_rtx,
5263 HASH (memory_extend_rtx, tmode), tmode);
5264 if (larger_elt == 0)
5267 for (larger_elt = larger_elt->first_same_value;
5268 larger_elt; larger_elt = larger_elt->next_same_value)
5269 if (GET_CODE (larger_elt->exp) == REG)
5271 src_related = gen_lowpart_if_possible (mode,
5280 #endif /* LOAD_EXTEND_OP */
5282 if (src == src_folded)
5285 /* At this point, ELT, if non-zero, points to a class of expressions
5286 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5287 and SRC_RELATED, if non-zero, each contain additional equivalent
5288 expressions. Prune these latter expressions by deleting expressions
5289 already in the equivalence class.
5291 Check for an equivalent identical to the destination. If found,
5292 this is the preferred equivalent since it will likely lead to
5293 elimination of the insn. Indicate this by placing it in
5297 elt = elt->first_same_value;
5298 for (p = elt; p; p = p->next_same_value)
5300 enum rtx_code code = GET_CODE (p->exp);
5302 /* If the expression is not valid, ignore it. Then we do not
5303 have to check for validity below. In most cases, we can use
5304 `rtx_equal_p', since canonicalization has already been done. */
5305 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
5308 /* Also skip paradoxical subregs, unless that's what we're
5311 && (GET_MODE_SIZE (GET_MODE (p->exp))
5312 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
5314 && GET_CODE (src) == SUBREG
5315 && GET_MODE (src) == GET_MODE (p->exp)
5316 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5317 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
5320 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
5322 else if (src_folded && GET_CODE (src_folded) == code
5323 && rtx_equal_p (src_folded, p->exp))
5325 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
5326 && rtx_equal_p (src_eqv_here, p->exp))
5328 else if (src_related && GET_CODE (src_related) == code
5329 && rtx_equal_p (src_related, p->exp))
5332 /* This is the same as the destination of the insns, we want
5333 to prefer it. Copy it to src_related. The code below will
5334 then give it a negative cost. */
5335 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
5339 /* Find the cheapest valid equivalent, trying all the available
5340 possibilities. Prefer items not in the hash table to ones
5341 that are when they are equal cost. Note that we can never
5342 worsen an insn as the current contents will also succeed.
5343 If we find an equivalent identical to the destination, use it as best,
5344 since this insn will probably be eliminated in that case. */
5347 if (rtx_equal_p (src, dest))
5348 src_cost = src_regcost = -1;
5351 src_cost = COST (src);
5352 src_regcost = approx_reg_cost (src);
5358 if (rtx_equal_p (src_eqv_here, dest))
5359 src_eqv_cost = src_eqv_regcost = -1;
5362 src_eqv_cost = COST (src_eqv_here);
5363 src_eqv_regcost = approx_reg_cost (src_eqv_here);
5369 if (rtx_equal_p (src_folded, dest))
5370 src_folded_cost = src_folded_regcost = -1;
5373 src_folded_cost = COST (src_folded);
5374 src_folded_regcost = approx_reg_cost (src_folded);
5380 if (rtx_equal_p (src_related, dest))
5381 src_related_cost = src_related_regcost = -1;
5384 src_related_cost = COST (src_related);
5385 src_related_regcost = approx_reg_cost (src_related);
5389 /* If this was an indirect jump insn, a known label will really be
5390 cheaper even though it looks more expensive. */
5391 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
5392 src_folded = src_const, src_folded_cost = src_folded_regcost -1;
5394 /* Terminate loop when replacement made. This must terminate since
5395 the current contents will be tested and will always be valid. */
5400 /* Skip invalid entries. */
5401 while (elt && GET_CODE (elt->exp) != REG
5402 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
5403 elt = elt->next_same_value;
5405 /* A paradoxical subreg would be bad here: it'll be the right
5406 size, but later may be adjusted so that the upper bits aren't
5407 what we want. So reject it. */
5409 && GET_CODE (elt->exp) == SUBREG
5410 && (GET_MODE_SIZE (GET_MODE (elt->exp))
5411 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
5412 /* It is okay, though, if the rtx we're trying to match
5413 will ignore any of the bits we can't predict. */
5415 && GET_CODE (src) == SUBREG
5416 && GET_MODE (src) == GET_MODE (elt->exp)
5417 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5418 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
5420 elt = elt->next_same_value;
5426 src_elt_cost = elt->cost;
5427 src_elt_regcost = elt->regcost;
5430 /* Find cheapest and skip it for the next time. For items
5431 of equal cost, use this order:
5432 src_folded, src, src_eqv, src_related and hash table entry. */
5433 if (preferrable (src_folded_cost, src_folded_regcost,
5434 src_cost, src_regcost) <= 0
5435 && preferrable (src_folded_cost, src_folded_regcost,
5436 src_eqv_cost, src_eqv_regcost) <= 0
5437 && preferrable (src_folded_cost, src_folded_regcost,
5438 src_related_cost, src_related_regcost) <= 0
5439 && preferrable (src_folded_cost, src_folded_regcost,
5440 src_elt_cost, src_elt_regcost) <= 0)
5442 trial = src_folded, src_folded_cost = MAX_COST;
5443 if (src_folded_force_flag)
5444 trial = force_const_mem (mode, trial);
5446 else if (preferrable (src_cost, src_regcost,
5447 src_eqv_cost, src_eqv_regcost) <= 0
5448 && preferrable (src_cost, src_regcost,
5449 src_related_cost, src_related_regcost) <= 0
5450 && preferrable (src_cost, src_regcost,
5451 src_elt_cost, src_elt_regcost) <= 0)
5452 trial = src, src_cost = MAX_COST;
5453 else if (preferrable (src_eqv_cost, src_eqv_regcost,
5454 src_related_cost, src_related_regcost) <= 0
5455 && preferrable (src_eqv_cost, src_eqv_regcost,
5456 src_elt_cost, src_elt_regcost) <= 0)
5457 trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
5458 else if (preferrable (src_related_cost, src_related_regcost,
5459 src_elt_cost, src_elt_regcost) <= 0)
5460 trial = copy_rtx (src_related), src_related_cost = MAX_COST;
5463 trial = copy_rtx (elt->exp);
5464 elt = elt->next_same_value;
5465 src_elt_cost = MAX_COST;
5468 /* We don't normally have an insn matching (set (pc) (pc)), so
5469 check for this separately here. We will delete such an
5472 Tablejump insns contain a USE of the table, so simply replacing
5473 the operand with the constant won't match. This is simply an
5474 unconditional branch, however, and is therefore valid. Just
5475 insert the substitution here and we will delete and re-emit
5478 if (n_sets == 1 && dest == pc_rtx
5480 || (GET_CODE (trial) == LABEL_REF
5481 && ! condjump_p (insn))))
5483 if (trial == pc_rtx)
5485 SET_SRC (sets[i].rtl) = trial;
5486 cse_jumps_altered = 1;
5490 PATTERN (insn) = gen_jump (XEXP (trial, 0));
5491 INSN_CODE (insn) = -1;
5493 if (NEXT_INSN (insn) != 0
5494 && GET_CODE (NEXT_INSN (insn)) != BARRIER)
5495 emit_barrier_after (insn);
5497 cse_jumps_altered = 1;
5501 /* Look for a substitution that makes a valid insn. */
5502 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
5504 /* If we just made a substitution inside a libcall, then we
5505 need to make the same substitution in any notes attached
5506 to the RETVAL insn. */
5508 && (GET_CODE (sets[i].orig_src) == REG
5509 || GET_CODE (sets[i].orig_src) == SUBREG
5510 || GET_CODE (sets[i].orig_src) == MEM))
5511 replace_rtx (REG_NOTES (libcall_insn), sets[i].orig_src,
5512 canon_reg (SET_SRC (sets[i].rtl), insn));
5514 /* The result of apply_change_group can be ignored; see
5517 validate_change (insn, &SET_SRC (sets[i].rtl),
5518 canon_reg (SET_SRC (sets[i].rtl), insn),
5520 apply_change_group ();
5524 /* If we previously found constant pool entries for
5525 constants and this is a constant, try making a
5526 pool entry. Put it in src_folded unless we already have done
5527 this since that is where it likely came from. */
5529 else if (constant_pool_entries_cost
5530 && CONSTANT_P (trial)
5531 /* Reject cases that will abort in decode_rtx_const.
5532 On the alpha when simplifying a switch, we get
5533 (const (truncate (minus (label_ref) (label_ref)))). */
5534 && ! (GET_CODE (trial) == CONST
5535 && GET_CODE (XEXP (trial, 0)) == TRUNCATE)
5536 /* Likewise on IA-64, except without the truncate. */
5537 && ! (GET_CODE (trial) == CONST
5538 && GET_CODE (XEXP (trial, 0)) == MINUS
5539 && GET_CODE (XEXP (XEXP (trial, 0), 0)) == LABEL_REF
5540 && GET_CODE (XEXP (XEXP (trial, 0), 1)) == LABEL_REF)
5542 || (GET_CODE (src_folded) != MEM
5543 && ! src_folded_force_flag))
5544 && GET_MODE_CLASS (mode) != MODE_CC
5545 && mode != VOIDmode)
5547 src_folded_force_flag = 1;
5549 src_folded_cost = constant_pool_entries_cost;
5553 src = SET_SRC (sets[i].rtl);
5555 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5556 However, there is an important exception: If both are registers
5557 that are not the head of their equivalence class, replace SET_SRC
5558 with the head of the class. If we do not do this, we will have
5559 both registers live over a portion of the basic block. This way,
5560 their lifetimes will likely abut instead of overlapping. */
5561 if (GET_CODE (dest) == REG
5562 && REGNO_QTY_VALID_P (REGNO (dest)))
5564 int dest_q = REG_QTY (REGNO (dest));
5565 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5567 if (dest_ent->mode == GET_MODE (dest)
5568 && dest_ent->first_reg != REGNO (dest)
5569 && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
5570 /* Don't do this if the original insn had a hard reg as
5571 SET_SRC or SET_DEST. */
5572 && (GET_CODE (sets[i].src) != REG
5573 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
5574 && (GET_CODE (dest) != REG || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
5575 /* We can't call canon_reg here because it won't do anything if
5576 SRC is a hard register. */
5578 int src_q = REG_QTY (REGNO (src));
5579 struct qty_table_elem *src_ent = &qty_table[src_q];
5580 int first = src_ent->first_reg;
5582 = (first >= FIRST_PSEUDO_REGISTER
5583 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
5585 /* We must use validate-change even for this, because this
5586 might be a special no-op instruction, suitable only to
5588 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
5591 /* If we had a constant that is cheaper than what we are now
5592 setting SRC to, use that constant. We ignored it when we
5593 thought we could make this into a no-op. */
5594 if (src_const && COST (src_const) < COST (src)
5595 && validate_change (insn, &SET_SRC (sets[i].rtl),
5602 /* If we made a change, recompute SRC values. */
5603 if (src != sets[i].src)
5607 hash_arg_in_memory = 0;
5609 sets[i].src_hash = HASH (src, mode);
5610 sets[i].src_volatile = do_not_record;
5611 sets[i].src_in_memory = hash_arg_in_memory;
5612 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
5615 /* If this is a single SET, we are setting a register, and we have an
5616 equivalent constant, we want to add a REG_NOTE. We don't want
5617 to write a REG_EQUAL note for a constant pseudo since verifying that
5618 that pseudo hasn't been eliminated is a pain. Such a note also
5619 won't help anything.
5621 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
5622 which can be created for a reference to a compile time computable
5623 entry in a jump table. */
5625 if (n_sets == 1 && src_const && GET_CODE (dest) == REG
5626 && GET_CODE (src_const) != REG
5627 && ! (GET_CODE (src_const) == CONST
5628 && GET_CODE (XEXP (src_const, 0)) == MINUS
5629 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
5630 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
5632 tem = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5634 /* Make sure that the rtx is not shared with any other insn. */
5635 src_const = copy_rtx (src_const);
5637 /* Record the actual constant value in a REG_EQUAL note, making
5638 a new one if one does not already exist. */
5640 XEXP (tem, 0) = src_const;
5642 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_EQUAL,
5643 src_const, REG_NOTES (insn));
5645 /* If storing a constant value in a register that
5646 previously held the constant value 0,
5647 record this fact with a REG_WAS_0 note on this insn.
5649 Note that the *register* is required to have previously held 0,
5650 not just any register in the quantity and we must point to the
5651 insn that set that register to zero.
5653 Rather than track each register individually, we just see if
5654 the last set for this quantity was for this register. */
5656 if (REGNO_QTY_VALID_P (REGNO (dest)))
5658 int dest_q = REG_QTY (REGNO (dest));
5659 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5661 if (dest_ent->const_rtx == const0_rtx)
5663 /* See if we previously had a REG_WAS_0 note. */
5664 rtx note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
5665 rtx const_insn = dest_ent->const_insn;
5667 if ((tem = single_set (const_insn)) != 0
5668 && rtx_equal_p (SET_DEST (tem), dest))
5671 XEXP (note, 0) = const_insn;
5674 = gen_rtx_INSN_LIST (REG_WAS_0, const_insn,
5681 /* Now deal with the destination. */
5684 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5685 to the MEM or REG within it. */
5686 while (GET_CODE (dest) == SIGN_EXTRACT
5687 || GET_CODE (dest) == ZERO_EXTRACT
5688 || GET_CODE (dest) == SUBREG
5689 || GET_CODE (dest) == STRICT_LOW_PART)
5690 dest = XEXP (dest, 0);
5692 sets[i].inner_dest = dest;
5694 if (GET_CODE (dest) == MEM)
5696 #ifdef PUSH_ROUNDING
5697 /* Stack pushes invalidate the stack pointer. */
5698 rtx addr = XEXP (dest, 0);
5699 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
5700 && XEXP (addr, 0) == stack_pointer_rtx)
5701 invalidate (stack_pointer_rtx, Pmode);
5703 dest = fold_rtx (dest, insn);
5706 /* Compute the hash code of the destination now,
5707 before the effects of this instruction are recorded,
5708 since the register values used in the address computation
5709 are those before this instruction. */
5710 sets[i].dest_hash = HASH (dest, mode);
5712 /* Don't enter a bit-field in the hash table
5713 because the value in it after the store
5714 may not equal what was stored, due to truncation. */
5716 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
5717 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
5719 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5721 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5722 && GET_CODE (width) == CONST_INT
5723 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5724 && ! (INTVAL (src_const)
5725 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5726 /* Exception: if the value is constant,
5727 and it won't be truncated, record it. */
5731 /* This is chosen so that the destination will be invalidated
5732 but no new value will be recorded.
5733 We must invalidate because sometimes constant
5734 values can be recorded for bitfields. */
5735 sets[i].src_elt = 0;
5736 sets[i].src_volatile = 1;
5742 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5744 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5746 /* One less use of the label this insn used to jump to. */
5747 if (JUMP_LABEL (insn) != 0)
5748 --LABEL_NUSES (JUMP_LABEL (insn));
5749 PUT_CODE (insn, NOTE);
5750 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5751 NOTE_SOURCE_FILE (insn) = 0;
5752 cse_jumps_altered = 1;
5753 /* No more processing for this set. */
5757 /* If this SET is now setting PC to a label, we know it used to
5758 be a conditional or computed branch. So we see if we can follow
5759 it. If it was a computed branch, delete it and re-emit. */
5760 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
5762 /* If this is not in the format for a simple branch and
5763 we are the only SET in it, re-emit it. */
5764 if (! simplejump_p (insn) && n_sets == 1)
5766 rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
5767 JUMP_LABEL (new) = XEXP (src, 0);
5768 LABEL_NUSES (XEXP (src, 0))++;
5772 /* Otherwise, force rerecognition, since it probably had
5773 a different pattern before.
5774 This shouldn't really be necessary, since whatever
5775 changed the source value above should have done this.
5776 Until the right place is found, might as well do this here. */
5777 INSN_CODE (insn) = -1;
5779 never_reached_warning (insn);
5781 /* Now emit a BARRIER after the unconditional jump. Do not bother
5782 deleting any unreachable code, let jump/flow do that. */
5783 if (NEXT_INSN (insn) != 0
5784 && GET_CODE (NEXT_INSN (insn)) != BARRIER)
5785 emit_barrier_after (insn);
5787 cse_jumps_altered = 1;
5791 /* If destination is volatile, invalidate it and then do no further
5792 processing for this assignment. */
5794 else if (do_not_record)
5796 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5797 invalidate (dest, VOIDmode);
5798 else if (GET_CODE (dest) == MEM)
5800 /* Outgoing arguments for a libcall don't
5801 affect any recorded expressions. */
5802 if (! libcall_insn || insn == libcall_insn)
5803 invalidate (dest, VOIDmode);
5805 else if (GET_CODE (dest) == STRICT_LOW_PART
5806 || GET_CODE (dest) == ZERO_EXTRACT)
5807 invalidate (XEXP (dest, 0), GET_MODE (dest));
5811 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5812 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5815 /* If setting CC0, record what it was set to, or a constant, if it
5816 is equivalent to a constant. If it is being set to a floating-point
5817 value, make a COMPARE with the appropriate constant of 0. If we
5818 don't do this, later code can interpret this as a test against
5819 const0_rtx, which can cause problems if we try to put it into an
5820 insn as a floating-point operand. */
5821 if (dest == cc0_rtx)
5823 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5824 this_insn_cc0_mode = mode;
5825 if (FLOAT_MODE_P (mode))
5826 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5832 /* Now enter all non-volatile source expressions in the hash table
5833 if they are not already present.
5834 Record their equivalence classes in src_elt.
5835 This way we can insert the corresponding destinations into
5836 the same classes even if the actual sources are no longer in them
5837 (having been invalidated). */
5839 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5840 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5842 register struct table_elt *elt;
5843 register struct table_elt *classp = sets[0].src_elt;
5844 rtx dest = SET_DEST (sets[0].rtl);
5845 enum machine_mode eqvmode = GET_MODE (dest);
5847 if (GET_CODE (dest) == STRICT_LOW_PART)
5849 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5852 if (insert_regs (src_eqv, classp, 0))
5854 rehash_using_reg (src_eqv);
5855 src_eqv_hash = HASH (src_eqv, eqvmode);
5857 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5858 elt->in_memory = src_eqv_in_memory;
5861 /* Check to see if src_eqv_elt is the same as a set source which
5862 does not yet have an elt, and if so set the elt of the set source
5864 for (i = 0; i < n_sets; i++)
5865 if (sets[i].rtl && sets[i].src_elt == 0
5866 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5867 sets[i].src_elt = src_eqv_elt;
5870 for (i = 0; i < n_sets; i++)
5871 if (sets[i].rtl && ! sets[i].src_volatile
5872 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5874 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5876 /* REG_EQUAL in setting a STRICT_LOW_PART
5877 gives an equivalent for the entire destination register,
5878 not just for the subreg being stored in now.
5879 This is a more interesting equivalence, so we arrange later
5880 to treat the entire reg as the destination. */
5881 sets[i].src_elt = src_eqv_elt;
5882 sets[i].src_hash = src_eqv_hash;
5886 /* Insert source and constant equivalent into hash table, if not
5888 register struct table_elt *classp = src_eqv_elt;
5889 register rtx src = sets[i].src;
5890 register rtx dest = SET_DEST (sets[i].rtl);
5891 enum machine_mode mode
5892 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5894 if (sets[i].src_elt == 0)
5896 /* Don't put a hard register source into the table if this is
5897 the last insn of a libcall. In this case, we only need
5898 to put src_eqv_elt in src_elt. */
5899 if (GET_CODE (src) != REG
5900 || REGNO (src) >= FIRST_PSEUDO_REGISTER
5901 || ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5903 register struct table_elt *elt;
5905 /* Note that these insert_regs calls cannot remove
5906 any of the src_elt's, because they would have failed to
5907 match if not still valid. */
5908 if (insert_regs (src, classp, 0))
5910 rehash_using_reg (src);
5911 sets[i].src_hash = HASH (src, mode);
5913 elt = insert (src, classp, sets[i].src_hash, mode);
5914 elt->in_memory = sets[i].src_in_memory;
5915 sets[i].src_elt = classp = elt;
5918 sets[i].src_elt = classp;
5920 if (sets[i].src_const && sets[i].src_const_elt == 0
5921 && src != sets[i].src_const
5922 && ! rtx_equal_p (sets[i].src_const, src))
5923 sets[i].src_elt = insert (sets[i].src_const, classp,
5924 sets[i].src_const_hash, mode);
5927 else if (sets[i].src_elt == 0)
5928 /* If we did not insert the source into the hash table (e.g., it was
5929 volatile), note the equivalence class for the REG_EQUAL value, if any,
5930 so that the destination goes into that class. */
5931 sets[i].src_elt = src_eqv_elt;
5933 invalidate_from_clobbers (x);
5935 /* Some registers are invalidated by subroutine calls. Memory is
5936 invalidated by non-constant calls. */
5938 if (GET_CODE (insn) == CALL_INSN)
5940 if (! CONST_CALL_P (insn))
5941 invalidate_memory ();
5942 invalidate_for_call ();
5945 /* Now invalidate everything set by this instruction.
5946 If a SUBREG or other funny destination is being set,
5947 sets[i].rtl is still nonzero, so here we invalidate the reg
5948 a part of which is being set. */
5950 for (i = 0; i < n_sets; i++)
5953 /* We can't use the inner dest, because the mode associated with
5954 a ZERO_EXTRACT is significant. */
5955 register rtx dest = SET_DEST (sets[i].rtl);
5957 /* Needed for registers to remove the register from its
5958 previous quantity's chain.
5959 Needed for memory if this is a nonvarying address, unless
5960 we have just done an invalidate_memory that covers even those. */
5961 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5962 invalidate (dest, VOIDmode);
5963 else if (GET_CODE (dest) == MEM)
5965 /* Outgoing arguments for a libcall don't
5966 affect any recorded expressions. */
5967 if (! libcall_insn || insn == libcall_insn)
5968 invalidate (dest, VOIDmode);
5970 else if (GET_CODE (dest) == STRICT_LOW_PART
5971 || GET_CODE (dest) == ZERO_EXTRACT)
5972 invalidate (XEXP (dest, 0), GET_MODE (dest));
5975 /* A volatile ASM invalidates everything. */
5976 if (GET_CODE (insn) == INSN
5977 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5978 && MEM_VOLATILE_P (PATTERN (insn)))
5979 flush_hash_table ();
5981 /* Make sure registers mentioned in destinations
5982 are safe for use in an expression to be inserted.
5983 This removes from the hash table
5984 any invalid entry that refers to one of these registers.
5986 We don't care about the return value from mention_regs because
5987 we are going to hash the SET_DEST values unconditionally. */
5989 for (i = 0; i < n_sets; i++)
5993 rtx x = SET_DEST (sets[i].rtl);
5995 if (GET_CODE (x) != REG)
5999 /* We used to rely on all references to a register becoming
6000 inaccessible when a register changes to a new quantity,
6001 since that changes the hash code. However, that is not
6002 safe, since after HASH_SIZE new quantities we get a
6003 hash 'collision' of a register with its own invalid
6004 entries. And since SUBREGs have been changed not to
6005 change their hash code with the hash code of the register,
6006 it wouldn't work any longer at all. So we have to check
6007 for any invalid references lying around now.
6008 This code is similar to the REG case in mention_regs,
6009 but it knows that reg_tick has been incremented, and
6010 it leaves reg_in_table as -1 . */
6011 unsigned int regno = REGNO (x);
6012 unsigned int endregno
6013 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
6014 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
6017 for (i = regno; i < endregno; i++)
6019 if (REG_IN_TABLE (i) >= 0)
6021 remove_invalid_refs (i);
6022 REG_IN_TABLE (i) = -1;
6029 /* We may have just removed some of the src_elt's from the hash table.
6030 So replace each one with the current head of the same class. */
6032 for (i = 0; i < n_sets; i++)
6035 if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
6036 /* If elt was removed, find current head of same class,
6037 or 0 if nothing remains of that class. */
6039 register struct table_elt *elt = sets[i].src_elt;
6041 while (elt && elt->prev_same_value)
6042 elt = elt->prev_same_value;
6044 while (elt && elt->first_same_value == 0)
6045 elt = elt->next_same_value;
6046 sets[i].src_elt = elt ? elt->first_same_value : 0;
6050 /* Now insert the destinations into their equivalence classes. */
6052 for (i = 0; i < n_sets; i++)
6055 register rtx dest = SET_DEST (sets[i].rtl);
6056 rtx inner_dest = sets[i].inner_dest;
6057 register struct table_elt *elt;
6059 /* Don't record value if we are not supposed to risk allocating
6060 floating-point values in registers that might be wider than
6062 if ((flag_float_store
6063 && GET_CODE (dest) == MEM
6064 && FLOAT_MODE_P (GET_MODE (dest)))
6065 /* Don't record BLKmode values, because we don't know the
6066 size of it, and can't be sure that other BLKmode values
6067 have the same or smaller size. */
6068 || GET_MODE (dest) == BLKmode
6069 /* Don't record values of destinations set inside a libcall block
6070 since we might delete the libcall. Things should have been set
6071 up so we won't want to reuse such a value, but we play it safe
6074 /* If we didn't put a REG_EQUAL value or a source into the hash
6075 table, there is no point is recording DEST. */
6076 || sets[i].src_elt == 0
6077 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
6078 or SIGN_EXTEND, don't record DEST since it can cause
6079 some tracking to be wrong.
6081 ??? Think about this more later. */
6082 || (GET_CODE (dest) == SUBREG
6083 && (GET_MODE_SIZE (GET_MODE (dest))
6084 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6085 && (GET_CODE (sets[i].src) == SIGN_EXTEND
6086 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
6089 /* STRICT_LOW_PART isn't part of the value BEING set,
6090 and neither is the SUBREG inside it.
6091 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6092 if (GET_CODE (dest) == STRICT_LOW_PART)
6093 dest = SUBREG_REG (XEXP (dest, 0));
6095 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
6096 /* Registers must also be inserted into chains for quantities. */
6097 if (insert_regs (dest, sets[i].src_elt, 1))
6099 /* If `insert_regs' changes something, the hash code must be
6101 rehash_using_reg (dest);
6102 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
6105 if (GET_CODE (inner_dest) == MEM
6106 && GET_CODE (XEXP (inner_dest, 0)) == ADDRESSOF)
6107 /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say
6108 that (MEM (ADDRESSOF (X))) is equivalent to Y.
6109 Consider the case in which the address of the MEM is
6110 passed to a function, which alters the MEM. Then, if we
6111 later use Y instead of the MEM we'll miss the update. */
6112 elt = insert (dest, 0, sets[i].dest_hash, GET_MODE (dest));
6114 elt = insert (dest, sets[i].src_elt,
6115 sets[i].dest_hash, GET_MODE (dest));
6117 elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM
6118 && (! RTX_UNCHANGING_P (sets[i].inner_dest)
6119 || FIXED_BASE_PLUS_P (XEXP (sets[i].inner_dest,
6122 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6123 narrower than M2, and both M1 and M2 are the same number of words,
6124 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6125 make that equivalence as well.
6127 However, BAR may have equivalences for which gen_lowpart_if_possible
6128 will produce a simpler value than gen_lowpart_if_possible applied to
6129 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6130 BAR's equivalences. If we don't get a simplified form, make
6131 the SUBREG. It will not be used in an equivalence, but will
6132 cause two similar assignments to be detected.
6134 Note the loop below will find SUBREG_REG (DEST) since we have
6135 already entered SRC and DEST of the SET in the table. */
6137 if (GET_CODE (dest) == SUBREG
6138 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
6140 == (GET_MODE_SIZE (GET_MODE (dest)) - 1) / UNITS_PER_WORD)
6141 && (GET_MODE_SIZE (GET_MODE (dest))
6142 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6143 && sets[i].src_elt != 0)
6145 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
6146 struct table_elt *elt, *classp = 0;
6148 for (elt = sets[i].src_elt->first_same_value; elt;
6149 elt = elt->next_same_value)
6153 struct table_elt *src_elt;
6155 /* Ignore invalid entries. */
6156 if (GET_CODE (elt->exp) != REG
6157 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
6160 new_src = gen_lowpart_if_possible (new_mode, elt->exp);
6162 new_src = gen_rtx_SUBREG (new_mode, elt->exp, 0);
6164 src_hash = HASH (new_src, new_mode);
6165 src_elt = lookup (new_src, src_hash, new_mode);
6167 /* Put the new source in the hash table is if isn't
6171 if (insert_regs (new_src, classp, 0))
6173 rehash_using_reg (new_src);
6174 src_hash = HASH (new_src, new_mode);
6176 src_elt = insert (new_src, classp, src_hash, new_mode);
6177 src_elt->in_memory = elt->in_memory;
6179 else if (classp && classp != src_elt->first_same_value)
6180 /* Show that two things that we've seen before are
6181 actually the same. */
6182 merge_equiv_classes (src_elt, classp);
6184 classp = src_elt->first_same_value;
6185 /* Ignore invalid entries. */
6187 && GET_CODE (classp->exp) != REG
6188 && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
6189 classp = classp->next_same_value;
6194 /* Special handling for (set REG0 REG1) where REG0 is the
6195 "cheapest", cheaper than REG1. After cse, REG1 will probably not
6196 be used in the sequel, so (if easily done) change this insn to
6197 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
6198 that computed their value. Then REG1 will become a dead store
6199 and won't cloud the situation for later optimizations.
6201 Do not make this change if REG1 is a hard register, because it will
6202 then be used in the sequel and we may be changing a two-operand insn
6203 into a three-operand insn.
6205 Also do not do this if we are operating on a copy of INSN.
6207 Also don't do this if INSN ends a libcall; this would cause an unrelated
6208 register to be set in the middle of a libcall, and we then get bad code
6209 if the libcall is deleted. */
6211 if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
6212 && NEXT_INSN (PREV_INSN (insn)) == insn
6213 && GET_CODE (SET_SRC (sets[0].rtl)) == REG
6214 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
6215 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
6217 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
6218 struct qty_table_elem *src_ent = &qty_table[src_q];
6220 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
6221 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
6223 rtx prev = prev_nonnote_insn (insn);
6225 if (prev != 0 && GET_CODE (prev) == INSN
6226 && GET_CODE (PATTERN (prev)) == SET
6227 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
6229 rtx dest = SET_DEST (sets[0].rtl);
6230 rtx src = SET_SRC (sets[0].rtl);
6231 rtx note = find_reg_note (prev, REG_EQUIV, NULL_RTX);
6233 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
6234 validate_change (insn, &SET_DEST (sets[0].rtl), src, 1);
6235 validate_change (insn, &SET_SRC (sets[0].rtl), dest, 1);
6236 apply_change_group ();
6238 /* If REG1 was equivalent to a constant, REG0 is not. */
6240 PUT_REG_NOTE_KIND (note, REG_EQUAL);
6242 /* If there was a REG_WAS_0 note on PREV, remove it. Move
6243 any REG_WAS_0 note on INSN to PREV. */
6244 note = find_reg_note (prev, REG_WAS_0, NULL_RTX);
6246 remove_note (prev, note);
6248 note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
6251 remove_note (insn, note);
6252 XEXP (note, 1) = REG_NOTES (prev);
6253 REG_NOTES (prev) = note;
6256 /* If INSN has a REG_EQUAL note, and this note mentions
6257 REG0, then we must delete it, because the value in
6258 REG0 has changed. If the note's value is REG1, we must
6259 also delete it because that is now this insn's dest. */
6260 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6262 && (reg_mentioned_p (dest, XEXP (note, 0))
6263 || rtx_equal_p (src, XEXP (note, 0))))
6264 remove_note (insn, note);
6269 /* If this is a conditional jump insn, record any known equivalences due to
6270 the condition being tested. */
6272 last_jump_equiv_class = 0;
6273 if (GET_CODE (insn) == JUMP_INSN
6274 && n_sets == 1 && GET_CODE (x) == SET
6275 && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
6276 record_jump_equiv (insn, 0);
6279 /* If the previous insn set CC0 and this insn no longer references CC0,
6280 delete the previous insn. Here we use the fact that nothing expects CC0
6281 to be valid over an insn, which is true until the final pass. */
6282 if (prev_insn && GET_CODE (prev_insn) == INSN
6283 && (tem = single_set (prev_insn)) != 0
6284 && SET_DEST (tem) == cc0_rtx
6285 && ! reg_mentioned_p (cc0_rtx, x))
6287 PUT_CODE (prev_insn, NOTE);
6288 NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
6289 NOTE_SOURCE_FILE (prev_insn) = 0;
6292 prev_insn_cc0 = this_insn_cc0;
6293 prev_insn_cc0_mode = this_insn_cc0_mode;
6299 /* Remove from the hash table all expressions that reference memory. */
6302 invalidate_memory ()
6305 register struct table_elt *p, *next;
6307 for (i = 0; i < HASH_SIZE; i++)
6308 for (p = table[i]; p; p = next)
6310 next = p->next_same_hash;
6312 remove_from_table (p, i);
6316 /* If ADDR is an address that implicitly affects the stack pointer, return
6317 1 and update the register tables to show the effect. Else, return 0. */
6320 addr_affects_sp_p (addr)
6323 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
6324 && GET_CODE (XEXP (addr, 0)) == REG
6325 && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
6327 if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
6328 REG_TICK (STACK_POINTER_REGNUM)++;
6330 /* This should be *very* rare. */
6331 if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
6332 invalidate (stack_pointer_rtx, VOIDmode);
6340 /* Perform invalidation on the basis of everything about an insn
6341 except for invalidating the actual places that are SET in it.
6342 This includes the places CLOBBERed, and anything that might
6343 alias with something that is SET or CLOBBERed.
6345 X is the pattern of the insn. */
6348 invalidate_from_clobbers (x)
6351 if (GET_CODE (x) == CLOBBER)
6353 rtx ref = XEXP (x, 0);
6356 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6357 || GET_CODE (ref) == MEM)
6358 invalidate (ref, VOIDmode);
6359 else if (GET_CODE (ref) == STRICT_LOW_PART
6360 || GET_CODE (ref) == ZERO_EXTRACT)
6361 invalidate (XEXP (ref, 0), GET_MODE (ref));
6364 else if (GET_CODE (x) == PARALLEL)
6367 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
6369 register rtx y = XVECEXP (x, 0, i);
6370 if (GET_CODE (y) == CLOBBER)
6372 rtx ref = XEXP (y, 0);
6373 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6374 || GET_CODE (ref) == MEM)
6375 invalidate (ref, VOIDmode);
6376 else if (GET_CODE (ref) == STRICT_LOW_PART
6377 || GET_CODE (ref) == ZERO_EXTRACT)
6378 invalidate (XEXP (ref, 0), GET_MODE (ref));
6384 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6385 and replace any registers in them with either an equivalent constant
6386 or the canonical form of the register. If we are inside an address,
6387 only do this if the address remains valid.
6389 OBJECT is 0 except when within a MEM in which case it is the MEM.
6391 Return the replacement for X. */
6394 cse_process_notes (x, object)
6398 enum rtx_code code = GET_CODE (x);
6399 const char *fmt = GET_RTX_FORMAT (code);
6415 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), x);
6420 if (REG_NOTE_KIND (x) == REG_EQUAL)
6421 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
6423 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
6430 rtx new = cse_process_notes (XEXP (x, 0), object);
6431 /* We don't substitute VOIDmode constants into these rtx,
6432 since they would impede folding. */
6433 if (GET_MODE (new) != VOIDmode)
6434 validate_change (object, &XEXP (x, 0), new, 0);
6439 i = REG_QTY (REGNO (x));
6441 /* Return a constant or a constant register. */
6442 if (REGNO_QTY_VALID_P (REGNO (x)))
6444 struct qty_table_elem *ent = &qty_table[i];
6446 if (ent->const_rtx != NULL_RTX
6447 && (CONSTANT_P (ent->const_rtx)
6448 || GET_CODE (ent->const_rtx) == REG))
6450 rtx new = gen_lowpart_if_possible (GET_MODE (x), ent->const_rtx);
6456 /* Otherwise, canonicalize this register. */
6457 return canon_reg (x, NULL_RTX);
6463 for (i = 0; i < GET_RTX_LENGTH (code); i++)
6465 validate_change (object, &XEXP (x, i),
6466 cse_process_notes (XEXP (x, i), object), 0);
6471 /* Find common subexpressions between the end test of a loop and the beginning
6472 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6474 Often we have a loop where an expression in the exit test is used
6475 in the body of the loop. For example "while (*p) *q++ = *p++;".
6476 Because of the way we duplicate the loop exit test in front of the loop,
6477 however, we don't detect that common subexpression. This will be caught
6478 when global cse is implemented, but this is a quite common case.
6480 This function handles the most common cases of these common expressions.
6481 It is called after we have processed the basic block ending with the
6482 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6483 jumps to a label used only once. */
6486 cse_around_loop (loop_start)
6491 struct table_elt *p;
6493 /* If the jump at the end of the loop doesn't go to the start, we don't
6495 for (insn = PREV_INSN (loop_start);
6496 insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
6497 insn = PREV_INSN (insn))
6501 || GET_CODE (insn) != NOTE
6502 || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
6505 /* If the last insn of the loop (the end test) was an NE comparison,
6506 we will interpret it as an EQ comparison, since we fell through
6507 the loop. Any equivalences resulting from that comparison are
6508 therefore not valid and must be invalidated. */
6509 if (last_jump_equiv_class)
6510 for (p = last_jump_equiv_class->first_same_value; p;
6511 p = p->next_same_value)
6513 if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
6514 || (GET_CODE (p->exp) == SUBREG
6515 && GET_CODE (SUBREG_REG (p->exp)) == REG))
6516 invalidate (p->exp, VOIDmode);
6517 else if (GET_CODE (p->exp) == STRICT_LOW_PART
6518 || GET_CODE (p->exp) == ZERO_EXTRACT)
6519 invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
6522 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6523 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6525 The only thing we do with SET_DEST is invalidate entries, so we
6526 can safely process each SET in order. It is slightly less efficient
6527 to do so, but we only want to handle the most common cases.
6529 The gen_move_insn call in cse_set_around_loop may create new pseudos.
6530 These pseudos won't have valid entries in any of the tables indexed
6531 by register number, such as reg_qty. We avoid out-of-range array
6532 accesses by not processing any instructions created after cse started. */
6534 for (insn = NEXT_INSN (loop_start);
6535 GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
6536 && INSN_UID (insn) < max_insn_uid
6537 && ! (GET_CODE (insn) == NOTE
6538 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
6539 insn = NEXT_INSN (insn))
6542 && (GET_CODE (PATTERN (insn)) == SET
6543 || GET_CODE (PATTERN (insn)) == CLOBBER))
6544 cse_set_around_loop (PATTERN (insn), insn, loop_start);
6545 else if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == PARALLEL)
6546 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6547 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
6548 || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
6549 cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
6554 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6555 since they are done elsewhere. This function is called via note_stores. */
6558 invalidate_skipped_set (dest, set, data)
6561 void *data ATTRIBUTE_UNUSED;
6563 enum rtx_code code = GET_CODE (dest);
6566 && ! addr_affects_sp_p (dest) /* If this is not a stack push ... */
6567 /* There are times when an address can appear varying and be a PLUS
6568 during this scan when it would be a fixed address were we to know
6569 the proper equivalences. So invalidate all memory if there is
6570 a BLKmode or nonscalar memory reference or a reference to a
6571 variable address. */
6572 && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
6573 || cse_rtx_varies_p (XEXP (dest, 0))))
6575 invalidate_memory ();
6579 if (GET_CODE (set) == CLOBBER
6586 if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
6587 invalidate (XEXP (dest, 0), GET_MODE (dest));
6588 else if (code == REG || code == SUBREG || code == MEM)
6589 invalidate (dest, VOIDmode);
6592 /* Invalidate all insns from START up to the end of the function or the
6593 next label. This called when we wish to CSE around a block that is
6594 conditionally executed. */
6597 invalidate_skipped_block (start)
6602 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
6603 insn = NEXT_INSN (insn))
6605 if (! INSN_P (insn))
6608 if (GET_CODE (insn) == CALL_INSN)
6610 if (! CONST_CALL_P (insn))
6611 invalidate_memory ();
6612 invalidate_for_call ();
6615 invalidate_from_clobbers (PATTERN (insn));
6616 note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
6620 /* If modifying X will modify the value in *DATA (which is really an
6621 `rtx *'), indicate that fact by setting the pointed to value to
6625 cse_check_loop_start (x, set, data)
6627 rtx set ATTRIBUTE_UNUSED;
6630 rtx *cse_check_loop_start_value = (rtx *) data;
6632 if (*cse_check_loop_start_value == NULL_RTX
6633 || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
6636 if ((GET_CODE (x) == MEM && GET_CODE (*cse_check_loop_start_value) == MEM)
6637 || reg_overlap_mentioned_p (x, *cse_check_loop_start_value))
6638 *cse_check_loop_start_value = NULL_RTX;
6641 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6642 a loop that starts with the label at LOOP_START.
6644 If X is a SET, we see if its SET_SRC is currently in our hash table.
6645 If so, we see if it has a value equal to some register used only in the
6646 loop exit code (as marked by jump.c).
6648 If those two conditions are true, we search backwards from the start of
6649 the loop to see if that same value was loaded into a register that still
6650 retains its value at the start of the loop.
6652 If so, we insert an insn after the load to copy the destination of that
6653 load into the equivalent register and (try to) replace our SET_SRC with that
6656 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6659 cse_set_around_loop (x, insn, loop_start)
6664 struct table_elt *src_elt;
6666 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6667 are setting PC or CC0 or whose SET_SRC is already a register. */
6668 if (GET_CODE (x) == SET
6669 && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
6670 && GET_CODE (SET_SRC (x)) != REG)
6672 src_elt = lookup (SET_SRC (x),
6673 HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
6674 GET_MODE (SET_DEST (x)));
6677 for (src_elt = src_elt->first_same_value; src_elt;
6678 src_elt = src_elt->next_same_value)
6679 if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
6680 && COST (src_elt->exp) < COST (SET_SRC (x)))
6684 /* Look for an insn in front of LOOP_START that sets
6685 something in the desired mode to SET_SRC (x) before we hit
6686 a label or CALL_INSN. */
6688 for (p = prev_nonnote_insn (loop_start);
6689 p && GET_CODE (p) != CALL_INSN
6690 && GET_CODE (p) != CODE_LABEL;
6691 p = prev_nonnote_insn (p))
6692 if ((set = single_set (p)) != 0
6693 && GET_CODE (SET_DEST (set)) == REG
6694 && GET_MODE (SET_DEST (set)) == src_elt->mode
6695 && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
6697 /* We now have to ensure that nothing between P
6698 and LOOP_START modified anything referenced in
6699 SET_SRC (x). We know that nothing within the loop
6700 can modify it, or we would have invalidated it in
6703 rtx cse_check_loop_start_value = SET_SRC (x);
6704 for (q = p; q != loop_start; q = NEXT_INSN (q))
6706 note_stores (PATTERN (q),
6707 cse_check_loop_start,
6708 &cse_check_loop_start_value);
6710 /* If nothing was changed and we can replace our
6711 SET_SRC, add an insn after P to copy its destination
6712 to what we will be replacing SET_SRC with. */
6713 if (cse_check_loop_start_value
6714 && validate_change (insn, &SET_SRC (x),
6717 /* If this creates new pseudos, this is unsafe,
6718 because the regno of new pseudo is unsuitable
6719 to index into reg_qty when cse_insn processes
6720 the new insn. Therefore, if a new pseudo was
6721 created, discard this optimization. */
6722 int nregs = max_reg_num ();
6724 = gen_move_insn (src_elt->exp, SET_DEST (set));
6725 if (nregs != max_reg_num ())
6727 if (! validate_change (insn, &SET_SRC (x),
6732 emit_insn_after (move, p);
6739 /* Deal with the destination of X affecting the stack pointer. */
6740 addr_affects_sp_p (SET_DEST (x));
6742 /* See comment on similar code in cse_insn for explanation of these
6744 if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
6745 || GET_CODE (SET_DEST (x)) == MEM)
6746 invalidate (SET_DEST (x), VOIDmode);
6747 else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
6748 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
6749 invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
6752 /* Find the end of INSN's basic block and return its range,
6753 the total number of SETs in all the insns of the block, the last insn of the
6754 block, and the branch path.
6756 The branch path indicates which branches should be followed. If a non-zero
6757 path size is specified, the block should be rescanned and a different set
6758 of branches will be taken. The branch path is only used if
6759 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
6761 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6762 used to describe the block. It is filled in with the information about
6763 the current block. The incoming structure's branch path, if any, is used
6764 to construct the output branch path. */
6767 cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks)
6769 struct cse_basic_block_data *data;
6776 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
6777 rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
6778 int path_size = data->path_size;
6782 /* Update the previous branch path, if any. If the last branch was
6783 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6784 shorten the path by one and look at the previous branch. We know that
6785 at least one branch must have been taken if PATH_SIZE is non-zero. */
6786 while (path_size > 0)
6788 if (data->path[path_size - 1].status != NOT_TAKEN)
6790 data->path[path_size - 1].status = NOT_TAKEN;
6797 /* If the first instruction is marked with QImode, that means we've
6798 already processed this block. Our caller will look at DATA->LAST
6799 to figure out where to go next. We want to return the next block
6800 in the instruction stream, not some branched-to block somewhere
6801 else. We accomplish this by pretending our called forbid us to
6802 follow jumps, or skip blocks. */
6803 if (GET_MODE (insn) == QImode)
6804 follow_jumps = skip_blocks = 0;
6806 /* Scan to end of this basic block. */
6807 while (p && GET_CODE (p) != CODE_LABEL)
6809 /* Don't cse out the end of a loop. This makes a difference
6810 only for the unusual loops that always execute at least once;
6811 all other loops have labels there so we will stop in any case.
6812 Cse'ing out the end of the loop is dangerous because it
6813 might cause an invariant expression inside the loop
6814 to be reused after the end of the loop. This would make it
6815 hard to move the expression out of the loop in loop.c,
6816 especially if it is one of several equivalent expressions
6817 and loop.c would like to eliminate it.
6819 If we are running after loop.c has finished, we can ignore
6820 the NOTE_INSN_LOOP_END. */
6822 if (! after_loop && GET_CODE (p) == NOTE
6823 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
6826 /* Don't cse over a call to setjmp; on some machines (eg vax)
6827 the regs restored by the longjmp come from
6828 a later time than the setjmp. */
6829 if (GET_CODE (p) == NOTE
6830 && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
6833 /* A PARALLEL can have lots of SETs in it,
6834 especially if it is really an ASM_OPERANDS. */
6835 if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
6836 nsets += XVECLEN (PATTERN (p), 0);
6837 else if (GET_CODE (p) != NOTE)
6840 /* Ignore insns made by CSE; they cannot affect the boundaries of
6843 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
6844 high_cuid = INSN_CUID (p);
6845 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
6846 low_cuid = INSN_CUID (p);
6848 /* See if this insn is in our branch path. If it is and we are to
6850 if (path_entry < path_size && data->path[path_entry].branch == p)
6852 if (data->path[path_entry].status != NOT_TAKEN)
6855 /* Point to next entry in path, if any. */
6859 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
6860 was specified, we haven't reached our maximum path length, there are
6861 insns following the target of the jump, this is the only use of the
6862 jump label, and the target label is preceded by a BARRIER.
6864 Alternatively, we can follow the jump if it branches around a
6865 block of code and there are no other branches into the block.
6866 In this case invalidate_skipped_block will be called to invalidate any
6867 registers set in the block when following the jump. */
6869 else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1
6870 && GET_CODE (p) == JUMP_INSN
6871 && GET_CODE (PATTERN (p)) == SET
6872 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
6873 && JUMP_LABEL (p) != 0
6874 && LABEL_NUSES (JUMP_LABEL (p)) == 1
6875 && NEXT_INSN (JUMP_LABEL (p)) != 0)
6877 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
6878 if ((GET_CODE (q) != NOTE
6879 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
6880 || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP)
6881 && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
6884 /* If we ran into a BARRIER, this code is an extension of the
6885 basic block when the branch is taken. */
6886 if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
6888 /* Don't allow ourself to keep walking around an
6889 always-executed loop. */
6890 if (next_real_insn (q) == next)
6896 /* Similarly, don't put a branch in our path more than once. */
6897 for (i = 0; i < path_entry; i++)
6898 if (data->path[i].branch == p)
6901 if (i != path_entry)
6904 data->path[path_entry].branch = p;
6905 data->path[path_entry++].status = TAKEN;
6907 /* This branch now ends our path. It was possible that we
6908 didn't see this branch the last time around (when the
6909 insn in front of the target was a JUMP_INSN that was
6910 turned into a no-op). */
6911 path_size = path_entry;
6914 /* Mark block so we won't scan it again later. */
6915 PUT_MODE (NEXT_INSN (p), QImode);
6917 /* Detect a branch around a block of code. */
6918 else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
6922 if (next_real_insn (q) == next)
6928 for (i = 0; i < path_entry; i++)
6929 if (data->path[i].branch == p)
6932 if (i != path_entry)
6935 /* This is no_labels_between_p (p, q) with an added check for
6936 reaching the end of a function (in case Q precedes P). */
6937 for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
6938 if (GET_CODE (tmp) == CODE_LABEL)
6943 data->path[path_entry].branch = p;
6944 data->path[path_entry++].status = AROUND;
6946 path_size = path_entry;
6949 /* Mark block so we won't scan it again later. */
6950 PUT_MODE (NEXT_INSN (p), QImode);
6957 data->low_cuid = low_cuid;
6958 data->high_cuid = high_cuid;
6959 data->nsets = nsets;
6962 /* If all jumps in the path are not taken, set our path length to zero
6963 so a rescan won't be done. */
6964 for (i = path_size - 1; i >= 0; i--)
6965 if (data->path[i].status != NOT_TAKEN)
6969 data->path_size = 0;
6971 data->path_size = path_size;
6973 /* End the current branch path. */
6974 data->path[path_size].branch = 0;
6977 /* Perform cse on the instructions of a function.
6978 F is the first instruction.
6979 NREGS is one plus the highest pseudo-reg number used in the instruction.
6981 AFTER_LOOP is 1 if this is the cse call done after loop optimization
6982 (only if -frerun-cse-after-loop).
6984 Returns 1 if jump_optimize should be redone due to simplifications
6985 in conditional jump instructions. */
6988 cse_main (f, nregs, after_loop, file)
6994 struct cse_basic_block_data val;
6995 register rtx insn = f;
6998 cse_jumps_altered = 0;
6999 recorded_label_ref = 0;
7000 constant_pool_entries_cost = 0;
7004 init_alias_analysis ();
7008 max_insn_uid = get_max_uid ();
7010 reg_eqv_table = (struct reg_eqv_elem *)
7011 xmalloc (nregs * sizeof (struct reg_eqv_elem));
7013 #ifdef LOAD_EXTEND_OP
7015 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
7016 and change the code and mode as appropriate. */
7017 memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX);
7020 /* Discard all the free elements of the previous function
7021 since they are allocated in the temporarily obstack. */
7022 bzero ((char *) table, sizeof table);
7023 free_element_chain = 0;
7024 n_elements_made = 0;
7026 /* Find the largest uid. */
7028 max_uid = get_max_uid ();
7029 uid_cuid = (int *) xcalloc (max_uid + 1, sizeof (int));
7031 /* Compute the mapping from uids to cuids.
7032 CUIDs are numbers assigned to insns, like uids,
7033 except that cuids increase monotonically through the code.
7034 Don't assign cuids to line-number NOTEs, so that the distance in cuids
7035 between two insns is not affected by -g. */
7037 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
7039 if (GET_CODE (insn) != NOTE
7040 || NOTE_LINE_NUMBER (insn) < 0)
7041 INSN_CUID (insn) = ++i;
7043 /* Give a line number note the same cuid as preceding insn. */
7044 INSN_CUID (insn) = i;
7047 /* Initialize which registers are clobbered by calls. */
7049 CLEAR_HARD_REG_SET (regs_invalidated_by_call);
7051 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
7052 if ((call_used_regs[i]
7053 /* Used to check !fixed_regs[i] here, but that isn't safe;
7054 fixed regs are still call-clobbered, and sched can get
7055 confused if they can "live across calls".
7057 The frame pointer is always preserved across calls. The arg
7058 pointer is if it is fixed. The stack pointer usually is, unless
7059 RETURN_POPS_ARGS, in which case an explicit CLOBBER
7060 will be present. If we are generating PIC code, the PIC offset
7061 table register is preserved across calls. */
7063 && i != STACK_POINTER_REGNUM
7064 && i != FRAME_POINTER_REGNUM
7065 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
7066 && i != HARD_FRAME_POINTER_REGNUM
7068 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
7069 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
7071 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
7072 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
7076 SET_HARD_REG_BIT (regs_invalidated_by_call, i);
7079 ggc_push_context ();
7081 /* Loop over basic blocks.
7082 Compute the maximum number of qty's needed for each basic block
7083 (which is 2 for each SET). */
7088 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
7089 flag_cse_skip_blocks);
7091 /* If this basic block was already processed or has no sets, skip it. */
7092 if (val.nsets == 0 || GET_MODE (insn) == QImode)
7094 PUT_MODE (insn, VOIDmode);
7095 insn = (val.last ? NEXT_INSN (val.last) : 0);
7100 cse_basic_block_start = val.low_cuid;
7101 cse_basic_block_end = val.high_cuid;
7102 max_qty = val.nsets * 2;
7105 fnotice (file, ";; Processing block from %d to %d, %d sets.\n",
7106 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
7109 /* Make MAX_QTY bigger to give us room to optimize
7110 past the end of this basic block, if that should prove useful. */
7116 /* If this basic block is being extended by following certain jumps,
7117 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7118 Otherwise, we start after this basic block. */
7119 if (val.path_size > 0)
7120 cse_basic_block (insn, val.last, val.path, 0);
7123 int old_cse_jumps_altered = cse_jumps_altered;
7126 /* When cse changes a conditional jump to an unconditional
7127 jump, we want to reprocess the block, since it will give
7128 us a new branch path to investigate. */
7129 cse_jumps_altered = 0;
7130 temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
7131 if (cse_jumps_altered == 0
7132 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7135 cse_jumps_altered |= old_cse_jumps_altered;
7138 if (ggc_p && cse_altered)
7149 if (max_elements_made < n_elements_made)
7150 max_elements_made = n_elements_made;
7153 end_alias_analysis ();
7155 free (reg_eqv_table);
7157 return cse_jumps_altered || recorded_label_ref;
7160 /* Process a single basic block. FROM and TO and the limits of the basic
7161 block. NEXT_BRANCH points to the branch path when following jumps or
7162 a null path when not following jumps.
7164 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
7165 loop. This is true when we are being called for the last time on a
7166 block and this CSE pass is before loop.c. */
7169 cse_basic_block (from, to, next_branch, around_loop)
7170 register rtx from, to;
7171 struct branch_path *next_branch;
7176 rtx libcall_insn = NULL_RTX;
7179 /* This array is undefined before max_reg, so only allocate
7180 the space actually needed and adjust the start. */
7183 = (struct qty_table_elem *) xmalloc ((max_qty - max_reg)
7184 * sizeof (struct qty_table_elem));
7185 qty_table -= max_reg;
7189 /* TO might be a label. If so, protect it from being deleted. */
7190 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7193 for (insn = from; insn != to; insn = NEXT_INSN (insn))
7195 register enum rtx_code code = GET_CODE (insn);
7197 /* If we have processed 1,000 insns, flush the hash table to
7198 avoid extreme quadratic behavior. We must not include NOTEs
7199 in the count since there may be more of them when generating
7200 debugging information. If we clear the table at different
7201 times, code generated with -g -O might be different than code
7202 generated with -O but not -g.
7204 ??? This is a real kludge and needs to be done some other way.
7206 if (code != NOTE && num_insns++ > 1000)
7208 flush_hash_table ();
7212 /* See if this is a branch that is part of the path. If so, and it is
7213 to be taken, do so. */
7214 if (next_branch->branch == insn)
7216 enum taken status = next_branch++->status;
7217 if (status != NOT_TAKEN)
7219 if (status == TAKEN)
7220 record_jump_equiv (insn, 1);
7222 invalidate_skipped_block (NEXT_INSN (insn));
7224 /* Set the last insn as the jump insn; it doesn't affect cc0.
7225 Then follow this branch. */
7230 insn = JUMP_LABEL (insn);
7235 if (GET_MODE (insn) == QImode)
7236 PUT_MODE (insn, VOIDmode);
7238 if (GET_RTX_CLASS (code) == 'i')
7242 /* Process notes first so we have all notes in canonical forms when
7243 looking for duplicate operations. */
7245 if (REG_NOTES (insn))
7246 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
7248 /* Track when we are inside in LIBCALL block. Inside such a block,
7249 we do not want to record destinations. The last insn of a
7250 LIBCALL block is not considered to be part of the block, since
7251 its destination is the result of the block and hence should be
7254 if (REG_NOTES (insn) != 0)
7256 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
7257 libcall_insn = XEXP (p, 0);
7258 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7262 cse_insn (insn, libcall_insn);
7265 /* If INSN is now an unconditional jump, skip to the end of our
7266 basic block by pretending that we just did the last insn in the
7267 basic block. If we are jumping to the end of our block, show
7268 that we can have one usage of TO. */
7270 if (any_uncondjump_p (insn))
7274 free (qty_table + max_reg);
7278 if (JUMP_LABEL (insn) == to)
7281 /* Maybe TO was deleted because the jump is unconditional.
7282 If so, there is nothing left in this basic block. */
7283 /* ??? Perhaps it would be smarter to set TO
7284 to whatever follows this insn,
7285 and pretend the basic block had always ended here. */
7286 if (INSN_DELETED_P (to))
7289 insn = PREV_INSN (to);
7292 /* See if it is ok to keep on going past the label
7293 which used to end our basic block. Remember that we incremented
7294 the count of that label, so we decrement it here. If we made
7295 a jump unconditional, TO_USAGE will be one; in that case, we don't
7296 want to count the use in that jump. */
7298 if (to != 0 && NEXT_INSN (insn) == to
7299 && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
7301 struct cse_basic_block_data val;
7304 insn = NEXT_INSN (to);
7306 /* If TO was the last insn in the function, we are done. */
7309 free (qty_table + max_reg);
7313 /* If TO was preceded by a BARRIER we are done with this block
7314 because it has no continuation. */
7315 prev = prev_nonnote_insn (to);
7316 if (prev && GET_CODE (prev) == BARRIER)
7318 free (qty_table + max_reg);
7322 /* Find the end of the following block. Note that we won't be
7323 following branches in this case. */
7326 cse_end_of_basic_block (insn, &val, 0, 0, 0);
7328 /* If the tables we allocated have enough space left
7329 to handle all the SETs in the next basic block,
7330 continue through it. Otherwise, return,
7331 and that block will be scanned individually. */
7332 if (val.nsets * 2 + next_qty > max_qty)
7335 cse_basic_block_start = val.low_cuid;
7336 cse_basic_block_end = val.high_cuid;
7339 /* Prevent TO from being deleted if it is a label. */
7340 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7343 /* Back up so we process the first insn in the extension. */
7344 insn = PREV_INSN (insn);
7348 if (next_qty > max_qty)
7351 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7352 the previous insn is the only insn that branches to the head of a loop,
7353 we can cse into the loop. Don't do this if we changed the jump
7354 structure of a loop unless we aren't going to be following jumps. */
7356 if ((cse_jumps_altered == 0
7357 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7358 && around_loop && to != 0
7359 && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
7360 && GET_CODE (PREV_INSN (to)) == JUMP_INSN
7361 && JUMP_LABEL (PREV_INSN (to)) != 0
7362 && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
7363 cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
7365 free (qty_table + max_reg);
7367 return to ? NEXT_INSN (to) : 0;
7370 /* Count the number of times registers are used (not set) in X.
7371 COUNTS is an array in which we accumulate the count, INCR is how much
7372 we count each register usage.
7374 Don't count a usage of DEST, which is the SET_DEST of a SET which
7375 contains X in its SET_SRC. This is because such a SET does not
7376 modify the liveness of DEST. */
7379 count_reg_usage (x, counts, dest, incr)
7392 switch (code = GET_CODE (x))
7396 counts[REGNO (x)] += incr;
7409 /* If we are clobbering a MEM, mark any registers inside the address
7411 if (GET_CODE (XEXP (x, 0)) == MEM)
7412 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
7416 /* Unless we are setting a REG, count everything in SET_DEST. */
7417 if (GET_CODE (SET_DEST (x)) != REG)
7418 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
7420 /* If SRC has side-effects, then we can't delete this insn, so the
7421 usage of SET_DEST inside SRC counts.
7423 ??? Strictly-speaking, we might be preserving this insn
7424 because some other SET has side-effects, but that's hard
7425 to do and can't happen now. */
7426 count_reg_usage (SET_SRC (x), counts,
7427 side_effects_p (SET_SRC (x)) ? NULL_RTX : SET_DEST (x),
7432 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr);
7437 count_reg_usage (PATTERN (x), counts, NULL_RTX, incr);
7439 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7442 count_reg_usage (REG_NOTES (x), counts, NULL_RTX, incr);
7447 if (REG_NOTE_KIND (x) == REG_EQUAL
7448 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE))
7449 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
7450 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
7457 fmt = GET_RTX_FORMAT (code);
7458 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
7461 count_reg_usage (XEXP (x, i), counts, dest, incr);
7462 else if (fmt[i] == 'E')
7463 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7464 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
7468 /* Scan all the insns and delete any that are dead; i.e., they store a register
7469 that is never used or they copy a register to itself.
7471 This is used to remove insns made obviously dead by cse, loop or other
7472 optimizations. It improves the heuristics in loop since it won't try to
7473 move dead invariants out of loops or make givs for dead quantities. The
7474 remaining passes of the compilation are also sped up. */
7477 delete_trivially_dead_insns (insns, nreg)
7487 int in_libcall = 0, dead_libcall = 0;
7489 /* First count the number of times each register is used. */
7490 counts = (int *) xcalloc (nreg, sizeof (int));
7491 for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
7492 count_reg_usage (insn, counts, NULL_RTX, 1);
7494 /* Go from the last insn to the first and delete insns that only set unused
7495 registers or copy a register to itself. As we delete an insn, remove
7496 usage counts for registers it uses.
7498 The first jump optimization pass may leave a real insn as the last
7499 insn in the function. We must not skip that insn or we may end
7500 up deleting code that is not really dead. */
7501 insn = get_last_insn ();
7502 if (! INSN_P (insn))
7503 insn = prev_real_insn (insn);
7505 for (; insn; insn = prev)
7510 prev = prev_real_insn (insn);
7512 /* Don't delete any insns that are part of a libcall block unless
7513 we can delete the whole libcall block.
7515 Flow or loop might get confused if we did that. Remember
7516 that we are scanning backwards. */
7517 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7523 /* See if there's a REG_EQUAL note on this insn and try to
7524 replace the source with the REG_EQUAL expression.
7526 We assume that insns with REG_RETVALs can only be reg->reg
7527 copies at this point. */
7528 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
7531 rtx set = single_set (insn);
7532 rtx new = simplify_rtx (XEXP (note, 0));
7535 new = XEXP (note, 0);
7537 if (set && validate_change (insn, &SET_SRC (set), new, 0))
7540 find_reg_note (insn, REG_RETVAL, NULL_RTX));
7545 else if (in_libcall)
7546 live_insn = ! dead_libcall;
7547 else if (GET_CODE (PATTERN (insn)) == SET)
7549 if ((GET_CODE (SET_DEST (PATTERN (insn))) == REG
7550 || GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG)
7551 && rtx_equal_p (SET_DEST (PATTERN (insn)),
7552 SET_SRC (PATTERN (insn))))
7554 else if (GET_CODE (SET_DEST (PATTERN (insn))) == STRICT_LOW_PART
7555 && rtx_equal_p (XEXP (SET_DEST (PATTERN (insn)), 0),
7556 SET_SRC (PATTERN (insn))))
7560 else if (GET_CODE (SET_DEST (PATTERN (insn))) == CC0
7561 && ! side_effects_p (SET_SRC (PATTERN (insn)))
7562 && ((tem = next_nonnote_insn (insn)) == 0
7564 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
7567 else if (GET_CODE (SET_DEST (PATTERN (insn))) != REG
7568 || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER
7569 || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0
7570 || side_effects_p (SET_SRC (PATTERN (insn)))
7571 /* An ADDRESSOF expression can turn into a use of the
7572 internal arg pointer, so always consider the
7573 internal arg pointer live. If it is truly dead,
7574 flow will delete the initializing insn. */
7575 || (SET_DEST (PATTERN (insn))
7576 == current_function_internal_arg_pointer))
7579 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
7580 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
7582 rtx elt = XVECEXP (PATTERN (insn), 0, i);
7584 if (GET_CODE (elt) == SET)
7586 if ((GET_CODE (SET_DEST (elt)) == REG
7587 || GET_CODE (SET_DEST (elt)) == SUBREG)
7588 && rtx_equal_p (SET_DEST (elt), SET_SRC (elt)))
7592 else if (GET_CODE (SET_DEST (elt)) == CC0
7593 && ! side_effects_p (SET_SRC (elt))
7594 && ((tem = next_nonnote_insn (insn)) == 0
7596 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
7599 else if (GET_CODE (SET_DEST (elt)) != REG
7600 || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER
7601 || counts[REGNO (SET_DEST (elt))] != 0
7602 || side_effects_p (SET_SRC (elt))
7603 /* An ADDRESSOF expression can turn into a use of the
7604 internal arg pointer, so always consider the
7605 internal arg pointer live. If it is truly dead,
7606 flow will delete the initializing insn. */
7608 == current_function_internal_arg_pointer))
7611 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
7617 /* If this is a dead insn, delete it and show registers in it aren't
7622 count_reg_usage (insn, counts, NULL_RTX, -1);
7626 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))