1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 88, 89, 92-6, 1997 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 /* Must precede rtl.h for FFS. */
28 #include "hard-reg-set.h"
31 #include "insn-config.h"
37 /* The basic idea of common subexpression elimination is to go
38 through the code, keeping a record of expressions that would
39 have the same value at the current scan point, and replacing
40 expressions encountered with the cheapest equivalent expression.
42 It is too complicated to keep track of the different possibilities
43 when control paths merge; so, at each label, we forget all that is
44 known and start fresh. This can be described as processing each
45 basic block separately. Note, however, that these are not quite
46 the same as the basic blocks found by a later pass and used for
47 data flow analysis and register packing. We do not need to start fresh
48 after a conditional jump instruction if there is no label there.
50 We use two data structures to record the equivalent expressions:
51 a hash table for most expressions, and several vectors together
52 with "quantity numbers" to record equivalent (pseudo) registers.
54 The use of the special data structure for registers is desirable
55 because it is faster. It is possible because registers references
56 contain a fairly small number, the register number, taken from
57 a contiguously allocated series, and two register references are
58 identical if they have the same number. General expressions
59 do not have any such thing, so the only way to retrieve the
60 information recorded on an expression other than a register
61 is to keep it in a hash table.
63 Registers and "quantity numbers":
65 At the start of each basic block, all of the (hardware and pseudo)
66 registers used in the function are given distinct quantity
67 numbers to indicate their contents. During scan, when the code
68 copies one register into another, we copy the quantity number.
69 When a register is loaded in any other way, we allocate a new
70 quantity number to describe the value generated by this operation.
71 `reg_qty' records what quantity a register is currently thought
74 All real quantity numbers are greater than or equal to `max_reg'.
75 If register N has not been assigned a quantity, reg_qty[N] will equal N.
77 Quantity numbers below `max_reg' do not exist and none of the `qty_...'
78 variables should be referenced with an index below `max_reg'.
80 We also maintain a bidirectional chain of registers for each
81 quantity number. `qty_first_reg', `qty_last_reg',
82 `reg_next_eqv' and `reg_prev_eqv' hold these chains.
84 The first register in a chain is the one whose lifespan is least local.
85 Among equals, it is the one that was seen first.
86 We replace any equivalent register with that one.
88 If two registers have the same quantity number, it must be true that
89 REG expressions with `qty_mode' must be in the hash table for both
90 registers and must be in the same class.
92 The converse is not true. Since hard registers may be referenced in
93 any mode, two REG expressions might be equivalent in the hash table
94 but not have the same quantity number if the quantity number of one
95 of the registers is not the same mode as those expressions.
97 Constants and quantity numbers
99 When a quantity has a known constant value, that value is stored
100 in the appropriate element of qty_const. This is in addition to
101 putting the constant in the hash table as is usual for non-regs.
103 Whether a reg or a constant is preferred is determined by the configuration
104 macro CONST_COSTS and will often depend on the constant value. In any
105 event, expressions containing constants can be simplified, by fold_rtx.
107 When a quantity has a known nearly constant value (such as an address
108 of a stack slot), that value is stored in the appropriate element
111 Integer constants don't have a machine mode. However, cse
112 determines the intended machine mode from the destination
113 of the instruction that moves the constant. The machine mode
114 is recorded in the hash table along with the actual RTL
115 constant expression so that different modes are kept separate.
119 To record known equivalences among expressions in general
120 we use a hash table called `table'. It has a fixed number of buckets
121 that contain chains of `struct table_elt' elements for expressions.
122 These chains connect the elements whose expressions have the same
125 Other chains through the same elements connect the elements which
126 currently have equivalent values.
128 Register references in an expression are canonicalized before hashing
129 the expression. This is done using `reg_qty' and `qty_first_reg'.
130 The hash code of a register reference is computed using the quantity
131 number, not the register number.
133 When the value of an expression changes, it is necessary to remove from the
134 hash table not just that expression but all expressions whose values
135 could be different as a result.
137 1. If the value changing is in memory, except in special cases
138 ANYTHING referring to memory could be changed. That is because
139 nobody knows where a pointer does not point.
140 The function `invalidate_memory' removes what is necessary.
142 The special cases are when the address is constant or is
143 a constant plus a fixed register such as the frame pointer
144 or a static chain pointer. When such addresses are stored in,
145 we can tell exactly which other such addresses must be invalidated
146 due to overlap. `invalidate' does this.
147 All expressions that refer to non-constant
148 memory addresses are also invalidated. `invalidate_memory' does this.
150 2. If the value changing is a register, all expressions
151 containing references to that register, and only those,
154 Because searching the entire hash table for expressions that contain
155 a register is very slow, we try to figure out when it isn't necessary.
156 Precisely, this is necessary only when expressions have been
157 entered in the hash table using this register, and then the value has
158 changed, and then another expression wants to be added to refer to
159 the register's new value. This sequence of circumstances is rare
160 within any one basic block.
162 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
163 reg_tick[i] is incremented whenever a value is stored in register i.
164 reg_in_table[i] holds -1 if no references to register i have been
165 entered in the table; otherwise, it contains the value reg_tick[i] had
166 when the references were entered. If we want to enter a reference
167 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
168 Until we want to enter a new entry, the mere fact that the two vectors
169 don't match makes the entries be ignored if anyone tries to match them.
171 Registers themselves are entered in the hash table as well as in
172 the equivalent-register chains. However, the vectors `reg_tick'
173 and `reg_in_table' do not apply to expressions which are simple
174 register references. These expressions are removed from the table
175 immediately when they become invalid, and this can be done even if
176 we do not immediately search for all the expressions that refer to
179 A CLOBBER rtx in an instruction invalidates its operand for further
180 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
181 invalidates everything that resides in memory.
185 Constant expressions that differ only by an additive integer
186 are called related. When a constant expression is put in
187 the table, the related expression with no constant term
188 is also entered. These are made to point at each other
189 so that it is possible to find out if there exists any
190 register equivalent to an expression related to a given expression. */
192 /* One plus largest register number used in this function. */
196 /* Length of vectors indexed by quantity number.
197 We know in advance we will not need a quantity number this big. */
201 /* Next quantity number to be allocated.
202 This is 1 + the largest number needed so far. */
206 /* Indexed by quantity number, gives the first (or last) register
207 in the chain of registers that currently contain this quantity. */
209 static int *qty_first_reg;
210 static int *qty_last_reg;
212 /* Index by quantity number, gives the mode of the quantity. */
214 static enum machine_mode *qty_mode;
216 /* Indexed by quantity number, gives the rtx of the constant value of the
217 quantity, or zero if it does not have a known value.
218 A sum of the frame pointer (or arg pointer) plus a constant
219 can also be entered here. */
221 static rtx *qty_const;
223 /* Indexed by qty number, gives the insn that stored the constant value
224 recorded in `qty_const'. */
226 static rtx *qty_const_insn;
228 /* The next three variables are used to track when a comparison between a
229 quantity and some constant or register has been passed. In that case, we
230 know the results of the comparison in case we see it again. These variables
231 record a comparison that is known to be true. */
233 /* Indexed by qty number, gives the rtx code of a comparison with a known
234 result involving this quantity. If none, it is UNKNOWN. */
235 static enum rtx_code *qty_comparison_code;
237 /* Indexed by qty number, gives the constant being compared against in a
238 comparison of known result. If no such comparison, it is undefined.
239 If the comparison is not with a constant, it is zero. */
241 static rtx *qty_comparison_const;
243 /* Indexed by qty number, gives the quantity being compared against in a
244 comparison of known result. If no such comparison, if it undefined.
245 If the comparison is not with a register, it is -1. */
247 static int *qty_comparison_qty;
250 /* For machines that have a CC0, we do not record its value in the hash
251 table since its use is guaranteed to be the insn immediately following
252 its definition and any other insn is presumed to invalidate it.
254 Instead, we store below the value last assigned to CC0. If it should
255 happen to be a constant, it is stored in preference to the actual
256 assigned value. In case it is a constant, we store the mode in which
257 the constant should be interpreted. */
259 static rtx prev_insn_cc0;
260 static enum machine_mode prev_insn_cc0_mode;
263 /* Previous actual insn. 0 if at first insn of basic block. */
265 static rtx prev_insn;
267 /* Insn being scanned. */
269 static rtx this_insn;
271 /* Index by register number, gives the quantity number
272 of the register's current contents. */
276 /* Index by register number, gives the number of the next (or
277 previous) register in the chain of registers sharing the same
280 Or -1 if this register is at the end of the chain.
282 If reg_qty[N] == N, reg_next_eqv[N] is undefined. */
284 static int *reg_next_eqv;
285 static int *reg_prev_eqv;
287 /* Index by register number, gives the number of times
288 that register has been altered in the current basic block. */
290 static int *reg_tick;
292 /* Index by register number, gives the reg_tick value at which
293 rtx's containing this register are valid in the hash table.
294 If this does not equal the current reg_tick value, such expressions
295 existing in the hash table are invalid.
296 If this is -1, no expressions containing this register have been
297 entered in the table. */
299 static int *reg_in_table;
301 /* A HARD_REG_SET containing all the hard registers for which there is
302 currently a REG expression in the hash table. Note the difference
303 from the above variables, which indicate if the REG is mentioned in some
304 expression in the table. */
306 static HARD_REG_SET hard_regs_in_table;
308 /* A HARD_REG_SET containing all the hard registers that are invalidated
311 static HARD_REG_SET regs_invalidated_by_call;
313 /* Two vectors of ints:
314 one containing max_reg -1's; the other max_reg + 500 (an approximation
315 for max_qty) elements where element i contains i.
316 These are used to initialize various other vectors fast. */
318 static int *all_minus_one;
319 static int *consec_ints;
321 /* CUID of insn that starts the basic block currently being cse-processed. */
323 static int cse_basic_block_start;
325 /* CUID of insn that ends the basic block currently being cse-processed. */
327 static int cse_basic_block_end;
329 /* Vector mapping INSN_UIDs to cuids.
330 The cuids are like uids but increase monotonically always.
331 We use them to see whether a reg is used outside a given basic block. */
333 static int *uid_cuid;
335 /* Highest UID in UID_CUID. */
338 /* Get the cuid of an insn. */
340 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
342 /* Nonzero if cse has altered conditional jump insns
343 in such a way that jump optimization should be redone. */
345 static int cse_jumps_altered;
347 /* Nonzero if we put a LABEL_REF into the hash table. Since we may have put
348 it into an INSN without a REG_LABEL, we have to rerun jump after CSE
349 to put in the note. */
350 static int recorded_label_ref;
352 /* canon_hash stores 1 in do_not_record
353 if it notices a reference to CC0, PC, or some other volatile
356 static int do_not_record;
358 #ifdef LOAD_EXTEND_OP
360 /* Scratch rtl used when looking for load-extended copy of a MEM. */
361 static rtx memory_extend_rtx;
364 /* canon_hash stores 1 in hash_arg_in_memory
365 if it notices a reference to memory within the expression being hashed. */
367 static int hash_arg_in_memory;
369 /* canon_hash stores 1 in hash_arg_in_struct
370 if it notices a reference to memory that's part of a structure. */
372 static int hash_arg_in_struct;
374 /* The hash table contains buckets which are chains of `struct table_elt's,
375 each recording one expression's information.
376 That expression is in the `exp' field.
378 Those elements with the same hash code are chained in both directions
379 through the `next_same_hash' and `prev_same_hash' fields.
381 Each set of expressions with equivalent values
382 are on a two-way chain through the `next_same_value'
383 and `prev_same_value' fields, and all point with
384 the `first_same_value' field at the first element in
385 that chain. The chain is in order of increasing cost.
386 Each element's cost value is in its `cost' field.
388 The `in_memory' field is nonzero for elements that
389 involve any reference to memory. These elements are removed
390 whenever a write is done to an unidentified location in memory.
391 To be safe, we assume that a memory address is unidentified unless
392 the address is either a symbol constant or a constant plus
393 the frame pointer or argument pointer.
395 The `in_struct' field is nonzero for elements that
396 involve any reference to memory inside a structure or array.
398 The `related_value' field is used to connect related expressions
399 (that differ by adding an integer).
400 The related expressions are chained in a circular fashion.
401 `related_value' is zero for expressions for which this
404 The `cost' field stores the cost of this element's expression.
406 The `is_const' flag is set if the element is a constant (including
409 The `flag' field is used as a temporary during some search routines.
411 The `mode' field is usually the same as GET_MODE (`exp'), but
412 if `exp' is a CONST_INT and has no machine mode then the `mode'
413 field is the mode it was being used as. Each constant is
414 recorded separately for each mode it is used with. */
420 struct table_elt *next_same_hash;
421 struct table_elt *prev_same_hash;
422 struct table_elt *next_same_value;
423 struct table_elt *prev_same_value;
424 struct table_elt *first_same_value;
425 struct table_elt *related_value;
427 enum machine_mode mode;
434 /* We don't want a lot of buckets, because we rarely have very many
435 things stored in the hash table, and a lot of buckets slows
436 down a lot of loops that happen frequently. */
439 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
440 register (hard registers may require `do_not_record' to be set). */
443 (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
444 ? (((unsigned) REG << 7) + (unsigned) reg_qty[REGNO (X)]) % NBUCKETS \
445 : canon_hash (X, M) % NBUCKETS)
447 /* Determine whether register number N is considered a fixed register for CSE.
448 It is desirable to replace other regs with fixed regs, to reduce need for
450 A reg wins if it is either the frame pointer or designated as fixed,
451 but not if it is an overlapping register. */
452 #ifdef OVERLAPPING_REGNO_P
453 #define FIXED_REGNO_P(N) \
454 (((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
455 || fixed_regs[N] || global_regs[N]) \
456 && ! OVERLAPPING_REGNO_P ((N)))
458 #define FIXED_REGNO_P(N) \
459 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
460 || fixed_regs[N] || global_regs[N])
463 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
464 hard registers and pointers into the frame are the cheapest with a cost
465 of 0. Next come pseudos with a cost of one and other hard registers with
466 a cost of 2. Aside from these special cases, call `rtx_cost'. */
468 #define CHEAP_REGNO(N) \
469 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
470 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
471 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
472 || ((N) < FIRST_PSEUDO_REGISTER \
473 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
475 /* A register is cheap if it is a user variable assigned to the register
476 or if its register number always corresponds to a cheap register. */
478 #define CHEAP_REG(N) \
479 ((REG_USERVAR_P (N) && REGNO (N) < FIRST_PSEUDO_REGISTER) \
480 || CHEAP_REGNO (REGNO (N)))
483 (GET_CODE (X) == REG \
484 ? (CHEAP_REG (X) ? 0 \
485 : REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1 \
489 /* Determine if the quantity number for register X represents a valid index
490 into the `qty_...' variables. */
492 #define REGNO_QTY_VALID_P(N) (reg_qty[N] != (N))
494 static struct table_elt *table[NBUCKETS];
496 /* Chain of `struct table_elt's made so far for this function
497 but currently removed from the table. */
499 static struct table_elt *free_element_chain;
501 /* Number of `struct table_elt' structures made so far for this function. */
503 static int n_elements_made;
505 /* Maximum value `n_elements_made' has had so far in this compilation
506 for functions previously processed. */
508 static int max_elements_made;
510 /* Surviving equivalence class when two equivalence classes are merged
511 by recording the effects of a jump in the last insn. Zero if the
512 last insn was not a conditional jump. */
514 static struct table_elt *last_jump_equiv_class;
516 /* Set to the cost of a constant pool reference if one was found for a
517 symbolic constant. If this was found, it means we should try to
518 convert constants into constant pool entries if they don't fit in
521 static int constant_pool_entries_cost;
523 /* Define maximum length of a branch path. */
525 #define PATHLENGTH 10
527 /* This data describes a block that will be processed by cse_basic_block. */
529 struct cse_basic_block_data {
530 /* Lowest CUID value of insns in block. */
532 /* Highest CUID value of insns in block. */
534 /* Total number of SETs in block. */
536 /* Last insn in the block. */
538 /* Size of current branch path, if any. */
540 /* Current branch path, indicating which branches will be taken. */
542 /* The branch insn. */
544 /* Whether it should be taken or not. AROUND is the same as taken
545 except that it is used when the destination label is not preceded
547 enum taken {TAKEN, NOT_TAKEN, AROUND} status;
551 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
552 virtual regs here because the simplify_*_operation routines are called
553 by integrate.c, which is called before virtual register instantiation. */
555 #define FIXED_BASE_PLUS_P(X) \
556 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
557 || (X) == arg_pointer_rtx \
558 || (X) == virtual_stack_vars_rtx \
559 || (X) == virtual_incoming_args_rtx \
560 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
561 && (XEXP (X, 0) == frame_pointer_rtx \
562 || XEXP (X, 0) == hard_frame_pointer_rtx \
563 || XEXP (X, 0) == arg_pointer_rtx \
564 || XEXP (X, 0) == virtual_stack_vars_rtx \
565 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
566 || GET_CODE (X) == ADDRESSOF)
568 /* Similar, but also allows reference to the stack pointer.
570 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
571 arg_pointer_rtx by itself is nonzero, because on at least one machine,
572 the i960, the arg pointer is zero when it is unused. */
574 #define NONZERO_BASE_PLUS_P(X) \
575 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
576 || (X) == virtual_stack_vars_rtx \
577 || (X) == virtual_incoming_args_rtx \
578 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
579 && (XEXP (X, 0) == frame_pointer_rtx \
580 || XEXP (X, 0) == hard_frame_pointer_rtx \
581 || XEXP (X, 0) == arg_pointer_rtx \
582 || XEXP (X, 0) == virtual_stack_vars_rtx \
583 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
584 || (X) == stack_pointer_rtx \
585 || (X) == virtual_stack_dynamic_rtx \
586 || (X) == virtual_outgoing_args_rtx \
587 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
588 && (XEXP (X, 0) == stack_pointer_rtx \
589 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
590 || XEXP (X, 0) == virtual_outgoing_args_rtx)) \
591 || GET_CODE (X) == ADDRESSOF)
593 static int notreg_cost PROTO((rtx));
594 static void new_basic_block PROTO((void));
595 static void make_new_qty PROTO((int));
596 static void make_regs_eqv PROTO((int, int));
597 static void delete_reg_equiv PROTO((int));
598 static int mention_regs PROTO((rtx));
599 static int insert_regs PROTO((rtx, struct table_elt *, int));
600 static void free_element PROTO((struct table_elt *));
601 static void remove_from_table PROTO((struct table_elt *, unsigned));
602 static struct table_elt *get_element PROTO((void));
603 static struct table_elt *lookup PROTO((rtx, unsigned, enum machine_mode)),
604 *lookup_for_remove PROTO((rtx, unsigned, enum machine_mode));
605 static rtx lookup_as_function PROTO((rtx, enum rtx_code));
606 static struct table_elt *insert PROTO((rtx, struct table_elt *, unsigned,
608 static void merge_equiv_classes PROTO((struct table_elt *,
609 struct table_elt *));
610 static void invalidate PROTO((rtx, enum machine_mode));
611 static int cse_rtx_varies_p PROTO((rtx));
612 static void remove_invalid_refs PROTO((int));
613 static void rehash_using_reg PROTO((rtx));
614 static void invalidate_memory PROTO((void));
615 static void invalidate_for_call PROTO((void));
616 static rtx use_related_value PROTO((rtx, struct table_elt *));
617 static unsigned canon_hash PROTO((rtx, enum machine_mode));
618 static unsigned safe_hash PROTO((rtx, enum machine_mode));
619 static int exp_equiv_p PROTO((rtx, rtx, int, int));
620 static void set_nonvarying_address_components PROTO((rtx, int, rtx *,
623 static int refers_to_p PROTO((rtx, rtx));
624 static rtx canon_reg PROTO((rtx, rtx));
625 static void find_best_addr PROTO((rtx, rtx *));
626 static enum rtx_code find_comparison_args PROTO((enum rtx_code, rtx *, rtx *,
628 enum machine_mode *));
629 static rtx cse_gen_binary PROTO((enum rtx_code, enum machine_mode,
631 static rtx simplify_plus_minus PROTO((enum rtx_code, enum machine_mode,
633 static rtx fold_rtx PROTO((rtx, rtx));
634 static rtx equiv_constant PROTO((rtx));
635 static void record_jump_equiv PROTO((rtx, int));
636 static void record_jump_cond PROTO((enum rtx_code, enum machine_mode,
638 static void cse_insn PROTO((rtx, int));
639 static int note_mem_written PROTO((rtx));
640 static void invalidate_from_clobbers PROTO((rtx));
641 static rtx cse_process_notes PROTO((rtx, rtx));
642 static void cse_around_loop PROTO((rtx));
643 static void invalidate_skipped_set PROTO((rtx, rtx));
644 static void invalidate_skipped_block PROTO((rtx));
645 static void cse_check_loop_start PROTO((rtx, rtx));
646 static void cse_set_around_loop PROTO((rtx, rtx, rtx));
647 static rtx cse_basic_block PROTO((rtx, rtx, struct branch_path *, int));
648 static void count_reg_usage PROTO((rtx, int *, rtx, int));
650 extern int rtx_equal_function_value_matters;
652 /* Return an estimate of the cost of computing rtx X.
653 One use is in cse, to decide which expression to keep in the hash table.
654 Another is in rtl generation, to pick the cheapest way to multiply.
655 Other uses like the latter are expected in the future. */
657 /* Internal function, to compute cost when X is not a register; called
658 from COST macro to keep it simple. */
664 return ((GET_CODE (x) == SUBREG
665 && GET_CODE (SUBREG_REG (x)) == REG
666 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
667 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
668 && (GET_MODE_SIZE (GET_MODE (x))
669 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
670 && subreg_lowpart_p (x)
671 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
672 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
673 ? (CHEAP_REG (SUBREG_REG (x)) ? 0
674 : (REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER ? 1
676 : rtx_cost (x, SET) * 2);
679 /* Return the right cost to give to an operation
680 to make the cost of the corresponding register-to-register instruction
681 N times that of a fast register-to-register instruction. */
683 #define COSTS_N_INSNS(N) ((N) * 4 - 2)
686 rtx_cost (x, outer_code)
688 enum rtx_code outer_code;
691 register enum rtx_code code;
698 /* Compute the default costs of certain things.
699 Note that RTX_COSTS can override the defaults. */
705 /* Count multiplication by 2**n as a shift,
706 because if we are considering it, we would output it as a shift. */
707 if (GET_CODE (XEXP (x, 1)) == CONST_INT
708 && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
711 total = COSTS_N_INSNS (5);
717 total = COSTS_N_INSNS (7);
720 /* Used in loop.c and combine.c as a marker. */
724 /* We don't want these to be used in substitutions because
725 we have no way of validating the resulting insn. So assign
726 anything containing an ASM_OPERANDS a very high cost. */
736 return ! CHEAP_REG (x);
739 /* If we can't tie these modes, make this expensive. The larger
740 the mode, the more expensive it is. */
741 if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
742 return COSTS_N_INSNS (2
743 + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
746 RTX_COSTS (x, code, outer_code);
748 CONST_COSTS (x, code, outer_code);
751 /* Sum the costs of the sub-rtx's, plus cost of this operation,
752 which is already in total. */
754 fmt = GET_RTX_FORMAT (code);
755 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
757 total += rtx_cost (XEXP (x, i), code);
758 else if (fmt[i] == 'E')
759 for (j = 0; j < XVECLEN (x, i); j++)
760 total += rtx_cost (XVECEXP (x, i, j), code);
765 /* Clear the hash table and initialize each register with its own quantity,
766 for a new basic block. */
775 bzero ((char *) reg_tick, max_reg * sizeof (int));
777 bcopy ((char *) all_minus_one, (char *) reg_in_table,
778 max_reg * sizeof (int));
779 bcopy ((char *) consec_ints, (char *) reg_qty, max_reg * sizeof (int));
780 CLEAR_HARD_REG_SET (hard_regs_in_table);
782 /* The per-quantity values used to be initialized here, but it is
783 much faster to initialize each as it is made in `make_new_qty'. */
785 for (i = 0; i < NBUCKETS; i++)
787 register struct table_elt *this, *next;
788 for (this = table[i]; this; this = next)
790 next = this->next_same_hash;
795 bzero ((char *) table, sizeof table);
804 /* Say that register REG contains a quantity not in any register before
805 and initialize that quantity. */
813 if (next_qty >= max_qty)
816 q = reg_qty[reg] = next_qty++;
817 qty_first_reg[q] = reg;
818 qty_last_reg[q] = reg;
819 qty_const[q] = qty_const_insn[q] = 0;
820 qty_comparison_code[q] = UNKNOWN;
822 reg_next_eqv[reg] = reg_prev_eqv[reg] = -1;
825 /* Make reg NEW equivalent to reg OLD.
826 OLD is not changing; NEW is. */
829 make_regs_eqv (new, old)
830 register int new, old;
832 register int lastr, firstr;
833 register int q = reg_qty[old];
835 /* Nothing should become eqv until it has a "non-invalid" qty number. */
836 if (! REGNO_QTY_VALID_P (old))
840 firstr = qty_first_reg[q];
841 lastr = qty_last_reg[q];
843 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
844 hard regs. Among pseudos, if NEW will live longer than any other reg
845 of the same qty, and that is beyond the current basic block,
846 make it the new canonical replacement for this qty. */
847 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
848 /* Certain fixed registers might be of the class NO_REGS. This means
849 that not only can they not be allocated by the compiler, but
850 they cannot be used in substitutions or canonicalizations
852 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
853 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
854 || (new >= FIRST_PSEUDO_REGISTER
855 && (firstr < FIRST_PSEUDO_REGISTER
856 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
857 || (uid_cuid[REGNO_FIRST_UID (new)]
858 < cse_basic_block_start))
859 && (uid_cuid[REGNO_LAST_UID (new)]
860 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
862 reg_prev_eqv[firstr] = new;
863 reg_next_eqv[new] = firstr;
864 reg_prev_eqv[new] = -1;
865 qty_first_reg[q] = new;
869 /* If NEW is a hard reg (known to be non-fixed), insert at end.
870 Otherwise, insert before any non-fixed hard regs that are at the
871 end. Registers of class NO_REGS cannot be used as an
872 equivalent for anything. */
873 while (lastr < FIRST_PSEUDO_REGISTER && reg_prev_eqv[lastr] >= 0
874 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
875 && new >= FIRST_PSEUDO_REGISTER)
876 lastr = reg_prev_eqv[lastr];
877 reg_next_eqv[new] = reg_next_eqv[lastr];
878 if (reg_next_eqv[lastr] >= 0)
879 reg_prev_eqv[reg_next_eqv[lastr]] = new;
881 qty_last_reg[q] = new;
882 reg_next_eqv[lastr] = new;
883 reg_prev_eqv[new] = lastr;
887 /* Remove REG from its equivalence class. */
890 delete_reg_equiv (reg)
893 register int q = reg_qty[reg];
896 /* If invalid, do nothing. */
900 p = reg_prev_eqv[reg];
901 n = reg_next_eqv[reg];
910 qty_first_reg[q] = n;
915 /* Remove any invalid expressions from the hash table
916 that refer to any of the registers contained in expression X.
918 Make sure that newly inserted references to those registers
919 as subexpressions will be considered valid.
921 mention_regs is not called when a register itself
922 is being stored in the table.
924 Return 1 if we have done something that may have changed the hash code
931 register enum rtx_code code;
934 register int changed = 0;
942 register int regno = REGNO (x);
943 register int endregno
944 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
945 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
948 for (i = regno; i < endregno; i++)
950 if (reg_in_table[i] >= 0 && reg_in_table[i] != reg_tick[i])
951 remove_invalid_refs (i);
953 reg_in_table[i] = reg_tick[i];
959 /* If X is a comparison or a COMPARE and either operand is a register
960 that does not have a quantity, give it one. This is so that a later
961 call to record_jump_equiv won't cause X to be assigned a different
962 hash code and not found in the table after that call.
964 It is not necessary to do this here, since rehash_using_reg can
965 fix up the table later, but doing this here eliminates the need to
966 call that expensive function in the most common case where the only
967 use of the register is in the comparison. */
969 if (code == COMPARE || GET_RTX_CLASS (code) == '<')
971 if (GET_CODE (XEXP (x, 0)) == REG
972 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
973 if (insert_regs (XEXP (x, 0), NULL_PTR, 0))
975 rehash_using_reg (XEXP (x, 0));
979 if (GET_CODE (XEXP (x, 1)) == REG
980 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
981 if (insert_regs (XEXP (x, 1), NULL_PTR, 0))
983 rehash_using_reg (XEXP (x, 1));
988 fmt = GET_RTX_FORMAT (code);
989 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
991 changed |= mention_regs (XEXP (x, i));
992 else if (fmt[i] == 'E')
993 for (j = 0; j < XVECLEN (x, i); j++)
994 changed |= mention_regs (XVECEXP (x, i, j));
999 /* Update the register quantities for inserting X into the hash table
1000 with a value equivalent to CLASSP.
1001 (If the class does not contain a REG, it is irrelevant.)
1002 If MODIFIED is nonzero, X is a destination; it is being modified.
1003 Note that delete_reg_equiv should be called on a register
1004 before insert_regs is done on that register with MODIFIED != 0.
1006 Nonzero value means that elements of reg_qty have changed
1007 so X's hash code may be different. */
1010 insert_regs (x, classp, modified)
1012 struct table_elt *classp;
1015 if (GET_CODE (x) == REG)
1017 register int regno = REGNO (x);
1019 /* If REGNO is in the equivalence table already but is of the
1020 wrong mode for that equivalence, don't do anything here. */
1022 if (REGNO_QTY_VALID_P (regno)
1023 && qty_mode[reg_qty[regno]] != GET_MODE (x))
1026 if (modified || ! REGNO_QTY_VALID_P (regno))
1029 for (classp = classp->first_same_value;
1031 classp = classp->next_same_value)
1032 if (GET_CODE (classp->exp) == REG
1033 && GET_MODE (classp->exp) == GET_MODE (x))
1035 make_regs_eqv (regno, REGNO (classp->exp));
1039 make_new_qty (regno);
1040 qty_mode[reg_qty[regno]] = GET_MODE (x);
1047 /* If X is a SUBREG, we will likely be inserting the inner register in the
1048 table. If that register doesn't have an assigned quantity number at
1049 this point but does later, the insertion that we will be doing now will
1050 not be accessible because its hash code will have changed. So assign
1051 a quantity number now. */
1053 else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1054 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1056 insert_regs (SUBREG_REG (x), NULL_PTR, 0);
1057 mention_regs (SUBREG_REG (x));
1061 return mention_regs (x);
1064 /* Look in or update the hash table. */
1066 /* Put the element ELT on the list of free elements. */
1070 struct table_elt *elt;
1072 elt->next_same_hash = free_element_chain;
1073 free_element_chain = elt;
1076 /* Return an element that is free for use. */
1078 static struct table_elt *
1081 struct table_elt *elt = free_element_chain;
1084 free_element_chain = elt->next_same_hash;
1088 return (struct table_elt *) oballoc (sizeof (struct table_elt));
1091 /* Remove table element ELT from use in the table.
1092 HASH is its hash code, made using the HASH macro.
1093 It's an argument because often that is known in advance
1094 and we save much time not recomputing it. */
1097 remove_from_table (elt, hash)
1098 register struct table_elt *elt;
1104 /* Mark this element as removed. See cse_insn. */
1105 elt->first_same_value = 0;
1107 /* Remove the table element from its equivalence class. */
1110 register struct table_elt *prev = elt->prev_same_value;
1111 register struct table_elt *next = elt->next_same_value;
1113 if (next) next->prev_same_value = prev;
1116 prev->next_same_value = next;
1119 register struct table_elt *newfirst = next;
1122 next->first_same_value = newfirst;
1123 next = next->next_same_value;
1128 /* Remove the table element from its hash bucket. */
1131 register struct table_elt *prev = elt->prev_same_hash;
1132 register struct table_elt *next = elt->next_same_hash;
1134 if (next) next->prev_same_hash = prev;
1137 prev->next_same_hash = next;
1138 else if (table[hash] == elt)
1142 /* This entry is not in the proper hash bucket. This can happen
1143 when two classes were merged by `merge_equiv_classes'. Search
1144 for the hash bucket that it heads. This happens only very
1145 rarely, so the cost is acceptable. */
1146 for (hash = 0; hash < NBUCKETS; hash++)
1147 if (table[hash] == elt)
1152 /* Remove the table element from its related-value circular chain. */
1154 if (elt->related_value != 0 && elt->related_value != elt)
1156 register struct table_elt *p = elt->related_value;
1157 while (p->related_value != elt)
1158 p = p->related_value;
1159 p->related_value = elt->related_value;
1160 if (p->related_value == p)
1161 p->related_value = 0;
1167 /* Look up X in the hash table and return its table element,
1168 or 0 if X is not in the table.
1170 MODE is the machine-mode of X, or if X is an integer constant
1171 with VOIDmode then MODE is the mode with which X will be used.
1173 Here we are satisfied to find an expression whose tree structure
1176 static struct table_elt *
1177 lookup (x, hash, mode)
1180 enum machine_mode mode;
1182 register struct table_elt *p;
1184 for (p = table[hash]; p; p = p->next_same_hash)
1185 if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
1186 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
1192 /* Like `lookup' but don't care whether the table element uses invalid regs.
1193 Also ignore discrepancies in the machine mode of a register. */
1195 static struct table_elt *
1196 lookup_for_remove (x, hash, mode)
1199 enum machine_mode mode;
1201 register struct table_elt *p;
1203 if (GET_CODE (x) == REG)
1205 int regno = REGNO (x);
1206 /* Don't check the machine mode when comparing registers;
1207 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1208 for (p = table[hash]; p; p = p->next_same_hash)
1209 if (GET_CODE (p->exp) == REG
1210 && REGNO (p->exp) == regno)
1215 for (p = table[hash]; p; p = p->next_same_hash)
1216 if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
1223 /* Look for an expression equivalent to X and with code CODE.
1224 If one is found, return that expression. */
1227 lookup_as_function (x, code)
1231 register struct table_elt *p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS,
1236 for (p = p->first_same_value; p; p = p->next_same_value)
1238 if (GET_CODE (p->exp) == code
1239 /* Make sure this is a valid entry in the table. */
1240 && exp_equiv_p (p->exp, p->exp, 1, 0))
1247 /* Insert X in the hash table, assuming HASH is its hash code
1248 and CLASSP is an element of the class it should go in
1249 (or 0 if a new class should be made).
1250 It is inserted at the proper position to keep the class in
1251 the order cheapest first.
1253 MODE is the machine-mode of X, or if X is an integer constant
1254 with VOIDmode then MODE is the mode with which X will be used.
1256 For elements of equal cheapness, the most recent one
1257 goes in front, except that the first element in the list
1258 remains first unless a cheaper element is added. The order of
1259 pseudo-registers does not matter, as canon_reg will be called to
1260 find the cheapest when a register is retrieved from the table.
1262 The in_memory field in the hash table element is set to 0.
1263 The caller must set it nonzero if appropriate.
1265 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1266 and if insert_regs returns a nonzero value
1267 you must then recompute its hash code before calling here.
1269 If necessary, update table showing constant values of quantities. */
1271 #define CHEAPER(X,Y) ((X)->cost < (Y)->cost)
1273 static struct table_elt *
1274 insert (x, classp, hash, mode)
1276 register struct table_elt *classp;
1278 enum machine_mode mode;
1280 register struct table_elt *elt;
1282 /* If X is a register and we haven't made a quantity for it,
1283 something is wrong. */
1284 if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
1287 /* If X is a hard register, show it is being put in the table. */
1288 if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
1290 int regno = REGNO (x);
1291 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1294 for (i = regno; i < endregno; i++)
1295 SET_HARD_REG_BIT (hard_regs_in_table, i);
1298 /* If X is a label, show we recorded it. */
1299 if (GET_CODE (x) == LABEL_REF
1300 || (GET_CODE (x) == CONST && GET_CODE (XEXP (x, 0)) == PLUS
1301 && GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))
1302 recorded_label_ref = 1;
1304 /* Put an element for X into the right hash bucket. */
1306 elt = get_element ();
1308 elt->cost = COST (x);
1309 elt->next_same_value = 0;
1310 elt->prev_same_value = 0;
1311 elt->next_same_hash = table[hash];
1312 elt->prev_same_hash = 0;
1313 elt->related_value = 0;
1316 elt->is_const = (CONSTANT_P (x)
1317 /* GNU C++ takes advantage of this for `this'
1318 (and other const values). */
1319 || (RTX_UNCHANGING_P (x)
1320 && GET_CODE (x) == REG
1321 && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1322 || FIXED_BASE_PLUS_P (x));
1325 table[hash]->prev_same_hash = elt;
1328 /* Put it into the proper value-class. */
1331 classp = classp->first_same_value;
1332 if (CHEAPER (elt, classp))
1333 /* Insert at the head of the class */
1335 register struct table_elt *p;
1336 elt->next_same_value = classp;
1337 classp->prev_same_value = elt;
1338 elt->first_same_value = elt;
1340 for (p = classp; p; p = p->next_same_value)
1341 p->first_same_value = elt;
1345 /* Insert not at head of the class. */
1346 /* Put it after the last element cheaper than X. */
1347 register struct table_elt *p, *next;
1348 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1350 /* Put it after P and before NEXT. */
1351 elt->next_same_value = next;
1353 next->prev_same_value = elt;
1354 elt->prev_same_value = p;
1355 p->next_same_value = elt;
1356 elt->first_same_value = classp;
1360 elt->first_same_value = elt;
1362 /* If this is a constant being set equivalent to a register or a register
1363 being set equivalent to a constant, note the constant equivalence.
1365 If this is a constant, it cannot be equivalent to a different constant,
1366 and a constant is the only thing that can be cheaper than a register. So
1367 we know the register is the head of the class (before the constant was
1370 If this is a register that is not already known equivalent to a
1371 constant, we must check the entire class.
1373 If this is a register that is already known equivalent to an insn,
1374 update `qty_const_insn' to show that `this_insn' is the latest
1375 insn making that quantity equivalent to the constant. */
1377 if (elt->is_const && classp && GET_CODE (classp->exp) == REG
1378 && GET_CODE (x) != REG)
1380 qty_const[reg_qty[REGNO (classp->exp)]]
1381 = gen_lowpart_if_possible (qty_mode[reg_qty[REGNO (classp->exp)]], x);
1382 qty_const_insn[reg_qty[REGNO (classp->exp)]] = this_insn;
1385 else if (GET_CODE (x) == REG && classp && ! qty_const[reg_qty[REGNO (x)]]
1388 register struct table_elt *p;
1390 for (p = classp; p != 0; p = p->next_same_value)
1392 if (p->is_const && GET_CODE (p->exp) != REG)
1394 qty_const[reg_qty[REGNO (x)]]
1395 = gen_lowpart_if_possible (GET_MODE (x), p->exp);
1396 qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
1402 else if (GET_CODE (x) == REG && qty_const[reg_qty[REGNO (x)]]
1403 && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]])
1404 qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
1406 /* If this is a constant with symbolic value,
1407 and it has a term with an explicit integer value,
1408 link it up with related expressions. */
1409 if (GET_CODE (x) == CONST)
1411 rtx subexp = get_related_value (x);
1413 struct table_elt *subelt, *subelt_prev;
1417 /* Get the integer-free subexpression in the hash table. */
1418 subhash = safe_hash (subexp, mode) % NBUCKETS;
1419 subelt = lookup (subexp, subhash, mode);
1421 subelt = insert (subexp, NULL_PTR, subhash, mode);
1422 /* Initialize SUBELT's circular chain if it has none. */
1423 if (subelt->related_value == 0)
1424 subelt->related_value = subelt;
1425 /* Find the element in the circular chain that precedes SUBELT. */
1426 subelt_prev = subelt;
1427 while (subelt_prev->related_value != subelt)
1428 subelt_prev = subelt_prev->related_value;
1429 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1430 This way the element that follows SUBELT is the oldest one. */
1431 elt->related_value = subelt_prev->related_value;
1432 subelt_prev->related_value = elt;
1439 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1440 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1441 the two classes equivalent.
1443 CLASS1 will be the surviving class; CLASS2 should not be used after this
1446 Any invalid entries in CLASS2 will not be copied. */
1449 merge_equiv_classes (class1, class2)
1450 struct table_elt *class1, *class2;
1452 struct table_elt *elt, *next, *new;
1454 /* Ensure we start with the head of the classes. */
1455 class1 = class1->first_same_value;
1456 class2 = class2->first_same_value;
1458 /* If they were already equal, forget it. */
1459 if (class1 == class2)
1462 for (elt = class2; elt; elt = next)
1466 enum machine_mode mode = elt->mode;
1468 next = elt->next_same_value;
1470 /* Remove old entry, make a new one in CLASS1's class.
1471 Don't do this for invalid entries as we cannot find their
1472 hash code (it also isn't necessary). */
1473 if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
1475 hash_arg_in_memory = 0;
1476 hash_arg_in_struct = 0;
1477 hash = HASH (exp, mode);
1479 if (GET_CODE (exp) == REG)
1480 delete_reg_equiv (REGNO (exp));
1482 remove_from_table (elt, hash);
1484 if (insert_regs (exp, class1, 0))
1486 rehash_using_reg (exp);
1487 hash = HASH (exp, mode);
1489 new = insert (exp, class1, hash, mode);
1490 new->in_memory = hash_arg_in_memory;
1491 new->in_struct = hash_arg_in_struct;
1496 /* Remove from the hash table, or mark as invalid,
1497 all expressions whose values could be altered by storing in X.
1498 X is a register, a subreg, or a memory reference with nonvarying address
1499 (because, when a memory reference with a varying address is stored in,
1500 all memory references are removed by invalidate_memory
1501 so specific invalidation is superfluous).
1502 FULL_MODE, if not VOIDmode, indicates that this much should be invalidated
1503 instead of just the amount indicated by the mode of X. This is only used
1504 for bitfield stores into memory.
1506 A nonvarying address may be just a register or just
1507 a symbol reference, or it may be either of those plus
1508 a numeric offset. */
1511 invalidate (x, full_mode)
1513 enum machine_mode full_mode;
1516 register struct table_elt *p;
1518 /* If X is a register, dependencies on its contents
1519 are recorded through the qty number mechanism.
1520 Just change the qty number of the register,
1521 mark it as invalid for expressions that refer to it,
1522 and remove it itself. */
1524 if (GET_CODE (x) == REG)
1526 register int regno = REGNO (x);
1527 register unsigned hash = HASH (x, GET_MODE (x));
1529 /* Remove REGNO from any quantity list it might be on and indicate
1530 that it's value might have changed. If it is a pseudo, remove its
1531 entry from the hash table.
1533 For a hard register, we do the first two actions above for any
1534 additional hard registers corresponding to X. Then, if any of these
1535 registers are in the table, we must remove any REG entries that
1536 overlap these registers. */
1538 delete_reg_equiv (regno);
1541 if (regno >= FIRST_PSEUDO_REGISTER)
1543 /* Because a register can be referenced in more than one mode,
1544 we might have to remove more than one table entry. */
1546 struct table_elt *elt;
1548 while (elt = lookup_for_remove (x, hash, GET_MODE (x)))
1549 remove_from_table (elt, hash);
1553 HOST_WIDE_INT in_table
1554 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1555 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1556 int tregno, tendregno;
1557 register struct table_elt *p, *next;
1559 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1561 for (i = regno + 1; i < endregno; i++)
1563 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
1564 CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
1565 delete_reg_equiv (i);
1570 for (hash = 0; hash < NBUCKETS; hash++)
1571 for (p = table[hash]; p; p = next)
1573 next = p->next_same_hash;
1575 if (GET_CODE (p->exp) != REG
1576 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1579 tregno = REGNO (p->exp);
1581 = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
1582 if (tendregno > regno && tregno < endregno)
1583 remove_from_table (p, hash);
1590 if (GET_CODE (x) == SUBREG)
1592 if (GET_CODE (SUBREG_REG (x)) != REG)
1594 invalidate (SUBREG_REG (x), VOIDmode);
1598 /* X is not a register; it must be a memory reference with
1599 a nonvarying address. Remove all hash table elements
1600 that refer to overlapping pieces of memory. */
1602 if (GET_CODE (x) != MEM)
1605 if (full_mode == VOIDmode)
1606 full_mode = GET_MODE (x);
1608 for (i = 0; i < NBUCKETS; i++)
1610 register struct table_elt *next;
1611 for (p = table[i]; p; p = next)
1613 next = p->next_same_hash;
1614 /* Invalidate ASM_OPERANDS which reference memory (this is easier
1615 than checking all the aliases). */
1617 && (GET_CODE (p->exp) != MEM
1618 || true_dependence (x, full_mode, p->exp, cse_rtx_varies_p)))
1619 remove_from_table (p, i);
1624 /* Remove all expressions that refer to register REGNO,
1625 since they are already invalid, and we are about to
1626 mark that register valid again and don't want the old
1627 expressions to reappear as valid. */
1630 remove_invalid_refs (regno)
1634 register struct table_elt *p, *next;
1636 for (i = 0; i < NBUCKETS; i++)
1637 for (p = table[i]; p; p = next)
1639 next = p->next_same_hash;
1640 if (GET_CODE (p->exp) != REG
1641 && refers_to_regno_p (regno, regno + 1, p->exp, NULL_PTR))
1642 remove_from_table (p, i);
1646 /* Recompute the hash codes of any valid entries in the hash table that
1647 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1649 This is called when we make a jump equivalence. */
1652 rehash_using_reg (x)
1656 struct table_elt *p, *next;
1659 if (GET_CODE (x) == SUBREG)
1662 /* If X is not a register or if the register is known not to be in any
1663 valid entries in the table, we have no work to do. */
1665 if (GET_CODE (x) != REG
1666 || reg_in_table[REGNO (x)] < 0
1667 || reg_in_table[REGNO (x)] != reg_tick[REGNO (x)])
1670 /* Scan all hash chains looking for valid entries that mention X.
1671 If we find one and it is in the wrong hash chain, move it. We can skip
1672 objects that are registers, since they are handled specially. */
1674 for (i = 0; i < NBUCKETS; i++)
1675 for (p = table[i]; p; p = next)
1677 next = p->next_same_hash;
1678 if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
1679 && exp_equiv_p (p->exp, p->exp, 1, 0)
1680 && i != (hash = safe_hash (p->exp, p->mode) % NBUCKETS))
1682 if (p->next_same_hash)
1683 p->next_same_hash->prev_same_hash = p->prev_same_hash;
1685 if (p->prev_same_hash)
1686 p->prev_same_hash->next_same_hash = p->next_same_hash;
1688 table[i] = p->next_same_hash;
1690 p->next_same_hash = table[hash];
1691 p->prev_same_hash = 0;
1693 table[hash]->prev_same_hash = p;
1699 /* Remove from the hash table any expression that is a call-clobbered
1700 register. Also update their TICK values. */
1703 invalidate_for_call ()
1705 int regno, endregno;
1708 struct table_elt *p, *next;
1711 /* Go through all the hard registers. For each that is clobbered in
1712 a CALL_INSN, remove the register from quantity chains and update
1713 reg_tick if defined. Also see if any of these registers is currently
1716 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1717 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1719 delete_reg_equiv (regno);
1720 if (reg_tick[regno] >= 0)
1723 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
1726 /* In the case where we have no call-clobbered hard registers in the
1727 table, we are done. Otherwise, scan the table and remove any
1728 entry that overlaps a call-clobbered register. */
1731 for (hash = 0; hash < NBUCKETS; hash++)
1732 for (p = table[hash]; p; p = next)
1734 next = p->next_same_hash;
1738 remove_from_table (p, hash);
1742 if (GET_CODE (p->exp) != REG
1743 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1746 regno = REGNO (p->exp);
1747 endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
1749 for (i = regno; i < endregno; i++)
1750 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1752 remove_from_table (p, hash);
1758 /* Given an expression X of type CONST,
1759 and ELT which is its table entry (or 0 if it
1760 is not in the hash table),
1761 return an alternate expression for X as a register plus integer.
1762 If none can be found, return 0. */
1765 use_related_value (x, elt)
1767 struct table_elt *elt;
1769 register struct table_elt *relt = 0;
1770 register struct table_elt *p, *q;
1771 HOST_WIDE_INT offset;
1773 /* First, is there anything related known?
1774 If we have a table element, we can tell from that.
1775 Otherwise, must look it up. */
1777 if (elt != 0 && elt->related_value != 0)
1779 else if (elt == 0 && GET_CODE (x) == CONST)
1781 rtx subexp = get_related_value (x);
1783 relt = lookup (subexp,
1784 safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
1791 /* Search all related table entries for one that has an
1792 equivalent register. */
1797 /* This loop is strange in that it is executed in two different cases.
1798 The first is when X is already in the table. Then it is searching
1799 the RELATED_VALUE list of X's class (RELT). The second case is when
1800 X is not in the table. Then RELT points to a class for the related
1803 Ensure that, whatever case we are in, that we ignore classes that have
1804 the same value as X. */
1806 if (rtx_equal_p (x, p->exp))
1809 for (q = p->first_same_value; q; q = q->next_same_value)
1810 if (GET_CODE (q->exp) == REG)
1816 p = p->related_value;
1818 /* We went all the way around, so there is nothing to be found.
1819 Alternatively, perhaps RELT was in the table for some other reason
1820 and it has no related values recorded. */
1821 if (p == relt || p == 0)
1828 offset = (get_integer_term (x) - get_integer_term (p->exp));
1829 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
1830 return plus_constant (q->exp, offset);
1833 /* Hash an rtx. We are careful to make sure the value is never negative.
1834 Equivalent registers hash identically.
1835 MODE is used in hashing for CONST_INTs only;
1836 otherwise the mode of X is used.
1838 Store 1 in do_not_record if any subexpression is volatile.
1840 Store 1 in hash_arg_in_memory if X contains a MEM rtx
1841 which does not have the RTX_UNCHANGING_P bit set.
1842 In this case, also store 1 in hash_arg_in_struct
1843 if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
1845 Note that cse_insn knows that the hash code of a MEM expression
1846 is just (int) MEM plus the hash code of the address. */
1849 canon_hash (x, mode)
1851 enum machine_mode mode;
1854 register unsigned hash = 0;
1855 register enum rtx_code code;
1858 /* repeat is used to turn tail-recursion into iteration. */
1863 code = GET_CODE (x);
1868 register int regno = REGNO (x);
1870 /* On some machines, we can't record any non-fixed hard register,
1871 because extending its life will cause reload problems. We
1872 consider ap, fp, and sp to be fixed for this purpose.
1873 On all machines, we can't record any global registers. */
1875 if (regno < FIRST_PSEUDO_REGISTER
1876 && (global_regs[regno]
1877 || (SMALL_REGISTER_CLASSES
1878 && ! fixed_regs[regno]
1879 && regno != FRAME_POINTER_REGNUM
1880 && regno != HARD_FRAME_POINTER_REGNUM
1881 && regno != ARG_POINTER_REGNUM
1882 && regno != STACK_POINTER_REGNUM)))
1887 hash += ((unsigned) REG << 7) + (unsigned) reg_qty[regno];
1893 unsigned HOST_WIDE_INT tem = INTVAL (x);
1894 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
1899 /* This is like the general case, except that it only counts
1900 the integers representing the constant. */
1901 hash += (unsigned) code + (unsigned) GET_MODE (x);
1902 if (GET_MODE (x) != VOIDmode)
1903 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
1905 unsigned tem = XINT (x, i);
1909 hash += ((unsigned) CONST_DOUBLE_LOW (x)
1910 + (unsigned) CONST_DOUBLE_HIGH (x));
1913 /* Assume there is only one rtx object for any given label. */
1916 += ((unsigned) LABEL_REF << 7) + (unsigned HOST_WIDE_INT) XEXP (x, 0);
1921 += ((unsigned) SYMBOL_REF << 7) + (unsigned HOST_WIDE_INT) XSTR (x, 0);
1925 if (MEM_VOLATILE_P (x))
1930 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
1932 hash_arg_in_memory = 1;
1933 if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1;
1935 /* Now that we have already found this special case,
1936 might as well speed it up as much as possible. */
1937 hash += (unsigned) MEM;
1948 case UNSPEC_VOLATILE:
1953 if (MEM_VOLATILE_P (x))
1964 i = GET_RTX_LENGTH (code) - 1;
1965 hash += (unsigned) code + (unsigned) GET_MODE (x);
1966 fmt = GET_RTX_FORMAT (code);
1971 rtx tem = XEXP (x, i);
1973 /* If we are about to do the last recursive call
1974 needed at this level, change it into iteration.
1975 This function is called enough to be worth it. */
1981 hash += canon_hash (tem, 0);
1983 else if (fmt[i] == 'E')
1984 for (j = 0; j < XVECLEN (x, i); j++)
1985 hash += canon_hash (XVECEXP (x, i, j), 0);
1986 else if (fmt[i] == 's')
1988 register unsigned char *p = (unsigned char *) XSTR (x, i);
1993 else if (fmt[i] == 'i')
1995 register unsigned tem = XINT (x, i);
1998 else if (fmt[i] == '0')
2006 /* Like canon_hash but with no side effects. */
2011 enum machine_mode mode;
2013 int save_do_not_record = do_not_record;
2014 int save_hash_arg_in_memory = hash_arg_in_memory;
2015 int save_hash_arg_in_struct = hash_arg_in_struct;
2016 unsigned hash = canon_hash (x, mode);
2017 hash_arg_in_memory = save_hash_arg_in_memory;
2018 hash_arg_in_struct = save_hash_arg_in_struct;
2019 do_not_record = save_do_not_record;
2023 /* Return 1 iff X and Y would canonicalize into the same thing,
2024 without actually constructing the canonicalization of either one.
2025 If VALIDATE is nonzero,
2026 we assume X is an expression being processed from the rtl
2027 and Y was found in the hash table. We check register refs
2028 in Y for being marked as valid.
2030 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2031 that is known to be in the register. Ordinarily, we don't allow them
2032 to match, because letting them match would cause unpredictable results
2033 in all the places that search a hash table chain for an equivalent
2034 for a given value. A possible equivalent that has different structure
2035 has its hash code computed from different data. Whether the hash code
2036 is the same as that of the the given value is pure luck. */
2039 exp_equiv_p (x, y, validate, equal_values)
2045 register enum rtx_code code;
2048 /* Note: it is incorrect to assume an expression is equivalent to itself
2049 if VALIDATE is nonzero. */
2050 if (x == y && !validate)
2052 if (x == 0 || y == 0)
2055 code = GET_CODE (x);
2056 if (code != GET_CODE (y))
2061 /* If X is a constant and Y is a register or vice versa, they may be
2062 equivalent. We only have to validate if Y is a register. */
2063 if (CONSTANT_P (x) && GET_CODE (y) == REG
2064 && REGNO_QTY_VALID_P (REGNO (y))
2065 && GET_MODE (y) == qty_mode[reg_qty[REGNO (y)]]
2066 && rtx_equal_p (x, qty_const[reg_qty[REGNO (y)]])
2067 && (! validate || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]))
2070 if (CONSTANT_P (y) && code == REG
2071 && REGNO_QTY_VALID_P (REGNO (x))
2072 && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]]
2073 && rtx_equal_p (y, qty_const[reg_qty[REGNO (x)]]))
2079 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2080 if (GET_MODE (x) != GET_MODE (y))
2090 return INTVAL (x) == INTVAL (y);
2093 return XEXP (x, 0) == XEXP (y, 0);
2096 return XSTR (x, 0) == XSTR (y, 0);
2100 int regno = REGNO (y);
2102 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2103 : HARD_REGNO_NREGS (regno, GET_MODE (y)));
2106 /* If the quantities are not the same, the expressions are not
2107 equivalent. If there are and we are not to validate, they
2108 are equivalent. Otherwise, ensure all regs are up-to-date. */
2110 if (reg_qty[REGNO (x)] != reg_qty[regno])
2116 for (i = regno; i < endregno; i++)
2117 if (reg_in_table[i] != reg_tick[i])
2123 /* For commutative operations, check both orders. */
2131 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
2132 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2133 validate, equal_values))
2134 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2135 validate, equal_values)
2136 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2137 validate, equal_values)));
2143 /* Compare the elements. If any pair of corresponding elements
2144 fail to match, return 0 for the whole things. */
2146 fmt = GET_RTX_FORMAT (code);
2147 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2152 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
2157 if (XVECLEN (x, i) != XVECLEN (y, i))
2159 for (j = 0; j < XVECLEN (x, i); j++)
2160 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2161 validate, equal_values))
2166 if (strcmp (XSTR (x, i), XSTR (y, i)))
2171 if (XINT (x, i) != XINT (y, i))
2176 if (XWINT (x, i) != XWINT (y, i))
2191 /* Return 1 iff any subexpression of X matches Y.
2192 Here we do not require that X or Y be valid (for registers referred to)
2193 for being in the hash table. */
2200 register enum rtx_code code;
2206 if (x == 0 || y == 0)
2209 code = GET_CODE (x);
2210 /* If X as a whole has the same code as Y, they may match.
2212 if (code == GET_CODE (y))
2214 if (exp_equiv_p (x, y, 0, 1))
2218 /* X does not match, so try its subexpressions. */
2220 fmt = GET_RTX_FORMAT (code);
2221 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2230 if (refers_to_p (XEXP (x, i), y))
2233 else if (fmt[i] == 'E')
2236 for (j = 0; j < XVECLEN (x, i); j++)
2237 if (refers_to_p (XVECEXP (x, i, j), y))
2244 /* Given ADDR and SIZE (a memory address, and the size of the memory reference),
2245 set PBASE, PSTART, and PEND which correspond to the base of the address,
2246 the starting offset, and ending offset respectively.
2248 ADDR is known to be a nonvarying address. */
2250 /* ??? Despite what the comments say, this function is in fact frequently
2251 passed varying addresses. This does not appear to cause any problems. */
2254 set_nonvarying_address_components (addr, size, pbase, pstart, pend)
2258 HOST_WIDE_INT *pstart, *pend;
2261 HOST_WIDE_INT start, end;
2267 /* Registers with nonvarying addresses usually have constant equivalents;
2268 but the frame pointer register is also possible. */
2269 if (GET_CODE (base) == REG
2271 && REGNO_QTY_VALID_P (REGNO (base))
2272 && qty_mode[reg_qty[REGNO (base)]] == GET_MODE (base)
2273 && qty_const[reg_qty[REGNO (base)]] != 0)
2274 base = qty_const[reg_qty[REGNO (base)]];
2275 else if (GET_CODE (base) == PLUS
2276 && GET_CODE (XEXP (base, 1)) == CONST_INT
2277 && GET_CODE (XEXP (base, 0)) == REG
2279 && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0)))
2280 && (qty_mode[reg_qty[REGNO (XEXP (base, 0))]]
2281 == GET_MODE (XEXP (base, 0)))
2282 && qty_const[reg_qty[REGNO (XEXP (base, 0))]])
2284 start = INTVAL (XEXP (base, 1));
2285 base = qty_const[reg_qty[REGNO (XEXP (base, 0))]];
2287 /* This can happen as the result of virtual register instantiation,
2288 if the initial offset is too large to be a valid address. */
2289 else if (GET_CODE (base) == PLUS
2290 && GET_CODE (XEXP (base, 0)) == REG
2291 && GET_CODE (XEXP (base, 1)) == REG
2293 && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0)))
2294 && (qty_mode[reg_qty[REGNO (XEXP (base, 0))]]
2295 == GET_MODE (XEXP (base, 0)))
2296 && qty_const[reg_qty[REGNO (XEXP (base, 0))]]
2297 && REGNO_QTY_VALID_P (REGNO (XEXP (base, 1)))
2298 && (qty_mode[reg_qty[REGNO (XEXP (base, 1))]]
2299 == GET_MODE (XEXP (base, 1)))
2300 && qty_const[reg_qty[REGNO (XEXP (base, 1))]])
2302 rtx tem = qty_const[reg_qty[REGNO (XEXP (base, 1))]];
2303 base = qty_const[reg_qty[REGNO (XEXP (base, 0))]];
2305 /* One of the two values must be a constant. */
2306 if (GET_CODE (base) != CONST_INT)
2308 if (GET_CODE (tem) != CONST_INT)
2310 start = INTVAL (tem);
2314 start = INTVAL (base);
2319 /* Handle everything that we can find inside an address that has been
2320 viewed as constant. */
2324 /* If no part of this switch does a "continue", the code outside
2325 will exit this loop. */
2327 switch (GET_CODE (base))
2330 /* By definition, operand1 of a LO_SUM is the associated constant
2331 address. Use the associated constant address as the base
2333 base = XEXP (base, 1);
2337 /* Strip off CONST. */
2338 base = XEXP (base, 0);
2342 if (GET_CODE (XEXP (base, 1)) == CONST_INT)
2344 start += INTVAL (XEXP (base, 1));
2345 base = XEXP (base, 0);
2351 /* Handle the case of an AND which is the negative of a power of
2352 two. This is used to represent unaligned memory operations. */
2353 if (GET_CODE (XEXP (base, 1)) == CONST_INT
2354 && exact_log2 (- INTVAL (XEXP (base, 1))) > 0)
2356 set_nonvarying_address_components (XEXP (base, 0), size,
2357 pbase, pstart, pend);
2359 /* Assume the worst misalignment. START is affected, but not
2360 END, so compensate but adjusting SIZE. Don't lose any
2361 constant we already had. */
2363 size = *pend - *pstart - INTVAL (XEXP (base, 1)) - 1;
2364 start += *pstart + INTVAL (XEXP (base, 1)) + 1;
2377 if (GET_CODE (base) == CONST_INT)
2379 start += INTVAL (base);
2385 /* Set the return values. */
2391 /* Return 1 if X has a value that can vary even between two
2392 executions of the program. 0 means X can be compared reliably
2393 against certain constants or near-constants. */
2396 cse_rtx_varies_p (x)
2399 /* We need not check for X and the equivalence class being of the same
2400 mode because if X is equivalent to a constant in some mode, it
2401 doesn't vary in any mode. */
2403 if (GET_CODE (x) == REG
2404 && REGNO_QTY_VALID_P (REGNO (x))
2405 && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]]
2406 && qty_const[reg_qty[REGNO (x)]] != 0)
2409 if (GET_CODE (x) == PLUS
2410 && GET_CODE (XEXP (x, 1)) == CONST_INT
2411 && GET_CODE (XEXP (x, 0)) == REG
2412 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2413 && (GET_MODE (XEXP (x, 0))
2414 == qty_mode[reg_qty[REGNO (XEXP (x, 0))]])
2415 && qty_const[reg_qty[REGNO (XEXP (x, 0))]])
2418 /* This can happen as the result of virtual register instantiation, if
2419 the initial constant is too large to be a valid address. This gives
2420 us a three instruction sequence, load large offset into a register,
2421 load fp minus a constant into a register, then a MEM which is the
2422 sum of the two `constant' registers. */
2423 if (GET_CODE (x) == PLUS
2424 && GET_CODE (XEXP (x, 0)) == REG
2425 && GET_CODE (XEXP (x, 1)) == REG
2426 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2427 && (GET_MODE (XEXP (x, 0))
2428 == qty_mode[reg_qty[REGNO (XEXP (x, 0))]])
2429 && qty_const[reg_qty[REGNO (XEXP (x, 0))]]
2430 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1)))
2431 && (GET_MODE (XEXP (x, 1))
2432 == qty_mode[reg_qty[REGNO (XEXP (x, 1))]])
2433 && qty_const[reg_qty[REGNO (XEXP (x, 1))]])
2436 return rtx_varies_p (x);
2439 /* Canonicalize an expression:
2440 replace each register reference inside it
2441 with the "oldest" equivalent register.
2443 If INSN is non-zero and we are replacing a pseudo with a hard register
2444 or vice versa, validate_change is used to ensure that INSN remains valid
2445 after we make our substitution. The calls are made with IN_GROUP non-zero
2446 so apply_change_group must be called upon the outermost return from this
2447 function (unless INSN is zero). The result of apply_change_group can
2448 generally be discarded since the changes we are making are optional. */
2456 register enum rtx_code code;
2462 code = GET_CODE (x);
2480 /* Never replace a hard reg, because hard regs can appear
2481 in more than one machine mode, and we must preserve the mode
2482 of each occurrence. Also, some hard regs appear in
2483 MEMs that are shared and mustn't be altered. Don't try to
2484 replace any reg that maps to a reg of class NO_REGS. */
2485 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2486 || ! REGNO_QTY_VALID_P (REGNO (x)))
2489 first = qty_first_reg[reg_qty[REGNO (x)]];
2490 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2491 : REGNO_REG_CLASS (first) == NO_REGS ? x
2492 : gen_rtx (REG, qty_mode[reg_qty[REGNO (x)]], first));
2499 fmt = GET_RTX_FORMAT (code);
2500 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2506 rtx new = canon_reg (XEXP (x, i), insn);
2509 /* If replacing pseudo with hard reg or vice versa, ensure the
2510 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2511 if (insn != 0 && new != 0
2512 && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
2513 && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2514 != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER))
2515 || (insn_code = recog_memoized (insn)) < 0
2516 || insn_n_dups[insn_code] > 0))
2517 validate_change (insn, &XEXP (x, i), new, 1);
2521 else if (fmt[i] == 'E')
2522 for (j = 0; j < XVECLEN (x, i); j++)
2523 XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
2529 /* LOC is a location within INSN that is an operand address (the contents of
2530 a MEM). Find the best equivalent address to use that is valid for this
2533 On most CISC machines, complicated address modes are costly, and rtx_cost
2534 is a good approximation for that cost. However, most RISC machines have
2535 only a few (usually only one) memory reference formats. If an address is
2536 valid at all, it is often just as cheap as any other address. Hence, for
2537 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2538 costs of various addresses. For two addresses of equal cost, choose the one
2539 with the highest `rtx_cost' value as that has the potential of eliminating
2540 the most insns. For equal costs, we choose the first in the equivalence
2541 class. Note that we ignore the fact that pseudo registers are cheaper
2542 than hard registers here because we would also prefer the pseudo registers.
2546 find_best_addr (insn, loc)
2550 struct table_elt *elt, *p;
2553 int found_better = 1;
2554 int save_do_not_record = do_not_record;
2555 int save_hash_arg_in_memory = hash_arg_in_memory;
2556 int save_hash_arg_in_struct = hash_arg_in_struct;
2561 /* Do not try to replace constant addresses or addresses of local and
2562 argument slots. These MEM expressions are made only once and inserted
2563 in many instructions, as well as being used to control symbol table
2564 output. It is not safe to clobber them.
2566 There are some uncommon cases where the address is already in a register
2567 for some reason, but we cannot take advantage of that because we have
2568 no easy way to unshare the MEM. In addition, looking up all stack
2569 addresses is costly. */
2570 if ((GET_CODE (addr) == PLUS
2571 && GET_CODE (XEXP (addr, 0)) == REG
2572 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2573 && (regno = REGNO (XEXP (addr, 0)),
2574 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2575 || regno == ARG_POINTER_REGNUM))
2576 || (GET_CODE (addr) == REG
2577 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2578 || regno == HARD_FRAME_POINTER_REGNUM
2579 || regno == ARG_POINTER_REGNUM))
2580 || GET_CODE (addr) == ADDRESSOF
2581 || CONSTANT_ADDRESS_P (addr))
2584 /* If this address is not simply a register, try to fold it. This will
2585 sometimes simplify the expression. Many simplifications
2586 will not be valid, but some, usually applying the associative rule, will
2587 be valid and produce better code. */
2588 if (GET_CODE (addr) != REG)
2590 rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX);
2594 && (ADDRESS_COST (folded) < ADDRESS_COST (addr)
2595 || (ADDRESS_COST (folded) == ADDRESS_COST (addr)
2596 && rtx_cost (folded, MEM) > rtx_cost (addr, MEM)))
2598 && rtx_cost (folded, MEM) < rtx_cost (addr, MEM)
2600 && validate_change (insn, loc, folded, 0))
2604 /* If this address is not in the hash table, we can't look for equivalences
2605 of the whole address. Also, ignore if volatile. */
2608 hash = HASH (addr, Pmode);
2609 addr_volatile = do_not_record;
2610 do_not_record = save_do_not_record;
2611 hash_arg_in_memory = save_hash_arg_in_memory;
2612 hash_arg_in_struct = save_hash_arg_in_struct;
2617 elt = lookup (addr, hash, Pmode);
2619 #ifndef ADDRESS_COST
2622 our_cost = elt->cost;
2624 /* Find the lowest cost below ours that works. */
2625 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
2626 if (elt->cost < our_cost
2627 && (GET_CODE (elt->exp) == REG
2628 || exp_equiv_p (elt->exp, elt->exp, 1, 0))
2629 && validate_change (insn, loc,
2630 canon_reg (copy_rtx (elt->exp), NULL_RTX), 0))
2637 /* We need to find the best (under the criteria documented above) entry
2638 in the class that is valid. We use the `flag' field to indicate
2639 choices that were invalid and iterate until we can't find a better
2640 one that hasn't already been tried. */
2642 for (p = elt->first_same_value; p; p = p->next_same_value)
2645 while (found_better)
2647 int best_addr_cost = ADDRESS_COST (*loc);
2648 int best_rtx_cost = (elt->cost + 1) >> 1;
2649 struct table_elt *best_elt = elt;
2652 for (p = elt->first_same_value; p; p = p->next_same_value)
2654 && (GET_CODE (p->exp) == REG
2655 || exp_equiv_p (p->exp, p->exp, 1, 0))
2656 && (ADDRESS_COST (p->exp) < best_addr_cost
2657 || (ADDRESS_COST (p->exp) == best_addr_cost
2658 && (p->cost + 1) >> 1 > best_rtx_cost)))
2661 best_addr_cost = ADDRESS_COST (p->exp);
2662 best_rtx_cost = (p->cost + 1) >> 1;
2668 if (validate_change (insn, loc,
2669 canon_reg (copy_rtx (best_elt->exp),
2678 /* If the address is a binary operation with the first operand a register
2679 and the second a constant, do the same as above, but looking for
2680 equivalences of the register. Then try to simplify before checking for
2681 the best address to use. This catches a few cases: First is when we
2682 have REG+const and the register is another REG+const. We can often merge
2683 the constants and eliminate one insn and one register. It may also be
2684 that a machine has a cheap REG+REG+const. Finally, this improves the
2685 code on the Alpha for unaligned byte stores. */
2687 if (flag_expensive_optimizations
2688 && (GET_RTX_CLASS (GET_CODE (*loc)) == '2'
2689 || GET_RTX_CLASS (GET_CODE (*loc)) == 'c')
2690 && GET_CODE (XEXP (*loc, 0)) == REG
2691 && GET_CODE (XEXP (*loc, 1)) == CONST_INT)
2693 rtx c = XEXP (*loc, 1);
2696 hash = HASH (XEXP (*loc, 0), Pmode);
2697 do_not_record = save_do_not_record;
2698 hash_arg_in_memory = save_hash_arg_in_memory;
2699 hash_arg_in_struct = save_hash_arg_in_struct;
2701 elt = lookup (XEXP (*loc, 0), hash, Pmode);
2705 /* We need to find the best (under the criteria documented above) entry
2706 in the class that is valid. We use the `flag' field to indicate
2707 choices that were invalid and iterate until we can't find a better
2708 one that hasn't already been tried. */
2710 for (p = elt->first_same_value; p; p = p->next_same_value)
2713 while (found_better)
2715 int best_addr_cost = ADDRESS_COST (*loc);
2716 int best_rtx_cost = (COST (*loc) + 1) >> 1;
2717 struct table_elt *best_elt = elt;
2718 rtx best_rtx = *loc;
2721 /* This is at worst case an O(n^2) algorithm, so limit our search
2722 to the first 32 elements on the list. This avoids trouble
2723 compiling code with very long basic blocks that can easily
2724 call cse_gen_binary so many times that we run out of memory. */
2727 for (p = elt->first_same_value, count = 0;
2729 p = p->next_same_value, count++)
2731 && (GET_CODE (p->exp) == REG
2732 || exp_equiv_p (p->exp, p->exp, 1, 0)))
2734 rtx new = cse_gen_binary (GET_CODE (*loc), Pmode, p->exp, c);
2736 if ((ADDRESS_COST (new) < best_addr_cost
2737 || (ADDRESS_COST (new) == best_addr_cost
2738 && (COST (new) + 1) >> 1 > best_rtx_cost)))
2741 best_addr_cost = ADDRESS_COST (new);
2742 best_rtx_cost = (COST (new) + 1) >> 1;
2750 if (validate_change (insn, loc,
2751 canon_reg (copy_rtx (best_rtx),
2762 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2763 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2764 what values are being compared.
2766 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2767 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2768 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2769 compared to produce cc0.
2771 The return value is the comparison operator and is either the code of
2772 A or the code corresponding to the inverse of the comparison. */
2774 static enum rtx_code
2775 find_comparison_args (code, parg1, parg2, pmode1, pmode2)
2778 enum machine_mode *pmode1, *pmode2;
2782 arg1 = *parg1, arg2 = *parg2;
2784 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2786 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
2788 /* Set non-zero when we find something of interest. */
2790 int reverse_code = 0;
2791 struct table_elt *p = 0;
2793 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2794 On machines with CC0, this is the only case that can occur, since
2795 fold_rtx will return the COMPARE or item being compared with zero
2798 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
2801 /* If ARG1 is a comparison operator and CODE is testing for
2802 STORE_FLAG_VALUE, get the inner arguments. */
2804 else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
2807 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2808 && code == LT && STORE_FLAG_VALUE == -1)
2809 #ifdef FLOAT_STORE_FLAG_VALUE
2810 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
2811 && FLOAT_STORE_FLAG_VALUE < 0)
2816 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
2817 && code == GE && STORE_FLAG_VALUE == -1)
2818 #ifdef FLOAT_STORE_FLAG_VALUE
2819 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
2820 && FLOAT_STORE_FLAG_VALUE < 0)
2823 x = arg1, reverse_code = 1;
2826 /* ??? We could also check for
2828 (ne (and (eq (...) (const_int 1))) (const_int 0))
2830 and related forms, but let's wait until we see them occurring. */
2833 /* Look up ARG1 in the hash table and see if it has an equivalence
2834 that lets us see what is being compared. */
2835 p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) % NBUCKETS,
2837 if (p) p = p->first_same_value;
2839 for (; p; p = p->next_same_value)
2841 enum machine_mode inner_mode = GET_MODE (p->exp);
2843 /* If the entry isn't valid, skip it. */
2844 if (! exp_equiv_p (p->exp, p->exp, 1, 0))
2847 if (GET_CODE (p->exp) == COMPARE
2848 /* Another possibility is that this machine has a compare insn
2849 that includes the comparison code. In that case, ARG1 would
2850 be equivalent to a comparison operation that would set ARG1 to
2851 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2852 ORIG_CODE is the actual comparison being done; if it is an EQ,
2853 we must reverse ORIG_CODE. On machine with a negative value
2854 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2857 && GET_MODE_CLASS (inner_mode) == MODE_INT
2858 && (GET_MODE_BITSIZE (inner_mode)
2859 <= HOST_BITS_PER_WIDE_INT)
2860 && (STORE_FLAG_VALUE
2861 & ((HOST_WIDE_INT) 1
2862 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2863 #ifdef FLOAT_STORE_FLAG_VALUE
2865 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
2866 && FLOAT_STORE_FLAG_VALUE < 0)
2869 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
2874 else if ((code == EQ
2876 && GET_MODE_CLASS (inner_mode) == MODE_INT
2877 && (GET_MODE_BITSIZE (inner_mode)
2878 <= HOST_BITS_PER_WIDE_INT)
2879 && (STORE_FLAG_VALUE
2880 & ((HOST_WIDE_INT) 1
2881 << (GET_MODE_BITSIZE (inner_mode) - 1))))
2882 #ifdef FLOAT_STORE_FLAG_VALUE
2884 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
2885 && FLOAT_STORE_FLAG_VALUE < 0)
2888 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
2895 /* If this is fp + constant, the equivalent is a better operand since
2896 it may let us predict the value of the comparison. */
2897 else if (NONZERO_BASE_PLUS_P (p->exp))
2904 /* If we didn't find a useful equivalence for ARG1, we are done.
2905 Otherwise, set up for the next iteration. */
2909 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
2910 if (GET_RTX_CLASS (GET_CODE (x)) == '<')
2911 code = GET_CODE (x);
2914 code = reverse_condition (code);
2917 /* Return our results. Return the modes from before fold_rtx
2918 because fold_rtx might produce const_int, and then it's too late. */
2919 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
2920 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
2925 /* Try to simplify a unary operation CODE whose output mode is to be
2926 MODE with input operand OP whose mode was originally OP_MODE.
2927 Return zero if no simplification can be made. */
2930 simplify_unary_operation (code, mode, op, op_mode)
2932 enum machine_mode mode;
2934 enum machine_mode op_mode;
2936 register int width = GET_MODE_BITSIZE (mode);
2938 /* The order of these tests is critical so that, for example, we don't
2939 check the wrong mode (input vs. output) for a conversion operation,
2940 such as FIX. At some point, this should be simplified. */
2942 #if !defined(REAL_IS_NOT_DOUBLE) || defined(REAL_ARITHMETIC)
2944 if (code == FLOAT && GET_MODE (op) == VOIDmode
2945 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
2947 HOST_WIDE_INT hv, lv;
2950 if (GET_CODE (op) == CONST_INT)
2951 lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0;
2953 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
2955 #ifdef REAL_ARITHMETIC
2956 REAL_VALUE_FROM_INT (d, lv, hv, mode);
2960 d = (double) (~ hv);
2961 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
2962 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
2963 d += (double) (unsigned HOST_WIDE_INT) (~ lv);
2969 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
2970 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
2971 d += (double) (unsigned HOST_WIDE_INT) lv;
2973 #endif /* REAL_ARITHMETIC */
2974 d = real_value_truncate (mode, d);
2975 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
2977 else if (code == UNSIGNED_FLOAT && GET_MODE (op) == VOIDmode
2978 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
2980 HOST_WIDE_INT hv, lv;
2983 if (GET_CODE (op) == CONST_INT)
2984 lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0;
2986 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
2988 if (op_mode == VOIDmode)
2990 /* We don't know how to interpret negative-looking numbers in
2991 this case, so don't try to fold those. */
2995 else if (GET_MODE_BITSIZE (op_mode) >= HOST_BITS_PER_WIDE_INT * 2)
2998 hv = 0, lv &= GET_MODE_MASK (op_mode);
3000 #ifdef REAL_ARITHMETIC
3001 REAL_VALUE_FROM_UNSIGNED_INT (d, lv, hv, mode);
3004 d = (double) (unsigned HOST_WIDE_INT) hv;
3005 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
3006 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
3007 d += (double) (unsigned HOST_WIDE_INT) lv;
3008 #endif /* REAL_ARITHMETIC */
3009 d = real_value_truncate (mode, d);
3010 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
3014 if (GET_CODE (op) == CONST_INT
3015 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
3017 register HOST_WIDE_INT arg0 = INTVAL (op);
3018 register HOST_WIDE_INT val;
3031 val = (arg0 >= 0 ? arg0 : - arg0);
3035 /* Don't use ffs here. Instead, get low order bit and then its
3036 number. If arg0 is zero, this will return 0, as desired. */
3037 arg0 &= GET_MODE_MASK (mode);
3038 val = exact_log2 (arg0 & (- arg0)) + 1;
3046 if (op_mode == VOIDmode)
3048 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
3050 /* If we were really extending the mode,
3051 we would have to distinguish between zero-extension
3052 and sign-extension. */
3053 if (width != GET_MODE_BITSIZE (op_mode))
3057 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
3058 val = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
3064 if (op_mode == VOIDmode)
3066 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
3068 /* If we were really extending the mode,
3069 we would have to distinguish between zero-extension
3070 and sign-extension. */
3071 if (width != GET_MODE_BITSIZE (op_mode))
3075 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
3078 = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
3080 & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (op_mode) - 1)))
3081 val -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
3094 /* Clear the bits that don't belong in our mode,
3095 unless they and our sign bit are all one.
3096 So we get either a reasonable negative value or a reasonable
3097 unsigned value for this mode. */
3098 if (width < HOST_BITS_PER_WIDE_INT
3099 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
3100 != ((HOST_WIDE_INT) (-1) << (width - 1))))
3101 val &= ((HOST_WIDE_INT) 1 << width) - 1;
3103 return GEN_INT (val);
3106 /* We can do some operations on integer CONST_DOUBLEs. Also allow
3107 for a DImode operation on a CONST_INT. */
3108 else if (GET_MODE (op) == VOIDmode && width <= HOST_BITS_PER_INT * 2
3109 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
3111 HOST_WIDE_INT l1, h1, lv, hv;
3113 if (GET_CODE (op) == CONST_DOUBLE)
3114 l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op);
3116 l1 = INTVAL (op), h1 = l1 < 0 ? -1 : 0;
3126 neg_double (l1, h1, &lv, &hv);
3131 neg_double (l1, h1, &lv, &hv);
3139 lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & (-h1)) + 1;
3141 lv = exact_log2 (l1 & (-l1)) + 1;
3145 /* This is just a change-of-mode, so do nothing. */
3150 if (op_mode == VOIDmode
3151 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
3155 lv = l1 & GET_MODE_MASK (op_mode);
3159 if (op_mode == VOIDmode
3160 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
3164 lv = l1 & GET_MODE_MASK (op_mode);
3165 if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT
3166 && (lv & ((HOST_WIDE_INT) 1
3167 << (GET_MODE_BITSIZE (op_mode) - 1))) != 0)
3168 lv -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
3170 hv = (lv < 0) ? ~ (HOST_WIDE_INT) 0 : 0;
3181 return immed_double_const (lv, hv, mode);
3184 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3185 else if (GET_CODE (op) == CONST_DOUBLE
3186 && GET_MODE_CLASS (mode) == MODE_FLOAT)
3192 if (setjmp (handler))
3193 /* There used to be a warning here, but that is inadvisable.
3194 People may want to cause traps, and the natural way
3195 to do it should not get a warning. */
3198 set_float_handler (handler);
3200 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
3205 d = REAL_VALUE_NEGATE (d);
3209 if (REAL_VALUE_NEGATIVE (d))
3210 d = REAL_VALUE_NEGATE (d);
3213 case FLOAT_TRUNCATE:
3214 d = real_value_truncate (mode, d);
3218 /* All this does is change the mode. */
3222 d = REAL_VALUE_RNDZINT (d);
3226 d = REAL_VALUE_UNSIGNED_RNDZINT (d);
3236 x = CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
3237 set_float_handler (NULL_PTR);
3241 else if (GET_CODE (op) == CONST_DOUBLE
3242 && GET_MODE_CLASS (GET_MODE (op)) == MODE_FLOAT
3243 && GET_MODE_CLASS (mode) == MODE_INT
3244 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
3250 if (setjmp (handler))
3253 set_float_handler (handler);
3255 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
3260 val = REAL_VALUE_FIX (d);
3264 val = REAL_VALUE_UNSIGNED_FIX (d);
3271 set_float_handler (NULL_PTR);
3273 /* Clear the bits that don't belong in our mode,
3274 unless they and our sign bit are all one.
3275 So we get either a reasonable negative value or a reasonable
3276 unsigned value for this mode. */
3277 if (width < HOST_BITS_PER_WIDE_INT
3278 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
3279 != ((HOST_WIDE_INT) (-1) << (width - 1))))
3280 val &= ((HOST_WIDE_INT) 1 << width) - 1;
3282 /* If this would be an entire word for the target, but is not for
3283 the host, then sign-extend on the host so that the number will look
3284 the same way on the host that it would on the target.
3286 For example, when building a 64 bit alpha hosted 32 bit sparc
3287 targeted compiler, then we want the 32 bit unsigned value -1 to be
3288 represented as a 64 bit value -1, and not as 0x00000000ffffffff.
3289 The later confuses the sparc backend. */
3291 if (BITS_PER_WORD < HOST_BITS_PER_WIDE_INT && BITS_PER_WORD == width
3292 && (val & ((HOST_WIDE_INT) 1 << (width - 1))))
3293 val |= ((HOST_WIDE_INT) (-1) << width);
3295 return GEN_INT (val);
3298 /* This was formerly used only for non-IEEE float.
3299 eggert@twinsun.com says it is safe for IEEE also. */
3302 /* There are some simplifications we can do even if the operands
3308 /* (not (not X)) == X, similarly for NEG. */
3309 if (GET_CODE (op) == code)
3310 return XEXP (op, 0);
3314 /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
3315 becomes just the MINUS if its mode is MODE. This allows
3316 folding switch statements on machines using casesi (such as
3318 if (GET_CODE (op) == TRUNCATE
3319 && GET_MODE (XEXP (op, 0)) == mode
3320 && GET_CODE (XEXP (op, 0)) == MINUS
3321 && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
3322 && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
3323 return XEXP (op, 0);
3325 #ifdef POINTERS_EXTEND_UNSIGNED
3326 if (! POINTERS_EXTEND_UNSIGNED
3327 && mode == Pmode && GET_MODE (op) == ptr_mode
3329 return convert_memory_address (Pmode, op);
3333 #ifdef POINTERS_EXTEND_UNSIGNED
3335 if (POINTERS_EXTEND_UNSIGNED
3336 && mode == Pmode && GET_MODE (op) == ptr_mode
3338 return convert_memory_address (Pmode, op);
3350 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
3351 and OP1. Return 0 if no simplification is possible.
3353 Don't use this for relational operations such as EQ or LT.
3354 Use simplify_relational_operation instead. */
3357 simplify_binary_operation (code, mode, op0, op1)
3359 enum machine_mode mode;
3362 register HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
3364 int width = GET_MODE_BITSIZE (mode);
3367 /* Relational operations don't work here. We must know the mode
3368 of the operands in order to do the comparison correctly.
3369 Assuming a full word can give incorrect results.
3370 Consider comparing 128 with -128 in QImode. */
3372 if (GET_RTX_CLASS (code) == '<')
3375 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3376 if (GET_MODE_CLASS (mode) == MODE_FLOAT
3377 && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
3378 && mode == GET_MODE (op0) && mode == GET_MODE (op1))
3380 REAL_VALUE_TYPE f0, f1, value;
3383 if (setjmp (handler))
3386 set_float_handler (handler);
3388 REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
3389 REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
3390 f0 = real_value_truncate (mode, f0);
3391 f1 = real_value_truncate (mode, f1);
3393 #ifdef REAL_ARITHMETIC
3394 #ifndef REAL_INFINITY
3395 if (code == DIV && REAL_VALUES_EQUAL (f1, dconst0))
3398 REAL_ARITHMETIC (value, rtx_to_tree_code (code), f0, f1);
3412 #ifndef REAL_INFINITY
3419 value = MIN (f0, f1);
3422 value = MAX (f0, f1);
3429 value = real_value_truncate (mode, value);
3430 set_float_handler (NULL_PTR);
3431 return CONST_DOUBLE_FROM_REAL_VALUE (value, mode);
3433 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3435 /* We can fold some multi-word operations. */
3436 if (GET_MODE_CLASS (mode) == MODE_INT
3437 && width == HOST_BITS_PER_WIDE_INT * 2
3438 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
3439 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
3441 HOST_WIDE_INT l1, l2, h1, h2, lv, hv;
3443 if (GET_CODE (op0) == CONST_DOUBLE)
3444 l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0);
3446 l1 = INTVAL (op0), h1 = l1 < 0 ? -1 : 0;
3448 if (GET_CODE (op1) == CONST_DOUBLE)
3449 l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1);
3451 l2 = INTVAL (op1), h2 = l2 < 0 ? -1 : 0;
3456 /* A - B == A + (-B). */
3457 neg_double (l2, h2, &lv, &hv);
3460 /* .. fall through ... */
3463 add_double (l1, h1, l2, h2, &lv, &hv);
3467 mul_double (l1, h1, l2, h2, &lv, &hv);
3470 case DIV: case MOD: case UDIV: case UMOD:
3471 /* We'd need to include tree.h to do this and it doesn't seem worth
3476 lv = l1 & l2, hv = h1 & h2;
3480 lv = l1 | l2, hv = h1 | h2;
3484 lv = l1 ^ l2, hv = h1 ^ h2;
3490 && ((unsigned HOST_WIDE_INT) l1
3491 < (unsigned HOST_WIDE_INT) l2)))
3500 && ((unsigned HOST_WIDE_INT) l1
3501 > (unsigned HOST_WIDE_INT) l2)))
3508 if ((unsigned HOST_WIDE_INT) h1 < (unsigned HOST_WIDE_INT) h2
3510 && ((unsigned HOST_WIDE_INT) l1
3511 < (unsigned HOST_WIDE_INT) l2)))
3518 if ((unsigned HOST_WIDE_INT) h1 > (unsigned HOST_WIDE_INT) h2
3520 && ((unsigned HOST_WIDE_INT) l1
3521 > (unsigned HOST_WIDE_INT) l2)))
3527 case LSHIFTRT: case ASHIFTRT:
3529 case ROTATE: case ROTATERT:
3530 #ifdef SHIFT_COUNT_TRUNCATED
3531 if (SHIFT_COUNT_TRUNCATED)
3532 l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0;
3535 if (h2 != 0 || l2 < 0 || l2 >= GET_MODE_BITSIZE (mode))
3538 if (code == LSHIFTRT || code == ASHIFTRT)
3539 rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
3541 else if (code == ASHIFT)
3542 lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, 1);
3543 else if (code == ROTATE)
3544 lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
3545 else /* code == ROTATERT */
3546 rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
3553 return immed_double_const (lv, hv, mode);
3556 if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
3557 || width > HOST_BITS_PER_WIDE_INT || width == 0)
3559 /* Even if we can't compute a constant result,
3560 there are some cases worth simplifying. */
3565 /* In IEEE floating point, x+0 is not the same as x. Similarly
3566 for the other optimizations below. */
3567 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
3568 && FLOAT_MODE_P (mode) && ! flag_fast_math)
3571 if (op1 == CONST0_RTX (mode))
3574 /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
3575 if (GET_CODE (op0) == NEG)
3576 return cse_gen_binary (MINUS, mode, op1, XEXP (op0, 0));
3577 else if (GET_CODE (op1) == NEG)
3578 return cse_gen_binary (MINUS, mode, op0, XEXP (op1, 0));
3580 /* Handle both-operands-constant cases. We can only add
3581 CONST_INTs to constants since the sum of relocatable symbols
3582 can't be handled by most assemblers. Don't add CONST_INT
3583 to CONST_INT since overflow won't be computed properly if wider
3584 than HOST_BITS_PER_WIDE_INT. */
3586 if (CONSTANT_P (op0) && GET_MODE (op0) != VOIDmode
3587 && GET_CODE (op1) == CONST_INT)
3588 return plus_constant (op0, INTVAL (op1));
3589 else if (CONSTANT_P (op1) && GET_MODE (op1) != VOIDmode
3590 && GET_CODE (op0) == CONST_INT)
3591 return plus_constant (op1, INTVAL (op0));
3593 /* See if this is something like X * C - X or vice versa or
3594 if the multiplication is written as a shift. If so, we can
3595 distribute and make a new multiply, shift, or maybe just
3596 have X (if C is 2 in the example above). But don't make
3597 real multiply if we didn't have one before. */
3599 if (! FLOAT_MODE_P (mode))
3601 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
3602 rtx lhs = op0, rhs = op1;
3605 if (GET_CODE (lhs) == NEG)
3606 coeff0 = -1, lhs = XEXP (lhs, 0);
3607 else if (GET_CODE (lhs) == MULT
3608 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
3610 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
3613 else if (GET_CODE (lhs) == ASHIFT
3614 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
3615 && INTVAL (XEXP (lhs, 1)) >= 0
3616 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
3618 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
3619 lhs = XEXP (lhs, 0);
3622 if (GET_CODE (rhs) == NEG)
3623 coeff1 = -1, rhs = XEXP (rhs, 0);
3624 else if (GET_CODE (rhs) == MULT
3625 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
3627 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
3630 else if (GET_CODE (rhs) == ASHIFT
3631 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
3632 && INTVAL (XEXP (rhs, 1)) >= 0
3633 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
3635 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
3636 rhs = XEXP (rhs, 0);
3639 if (rtx_equal_p (lhs, rhs))
3641 tem = cse_gen_binary (MULT, mode, lhs,
3642 GEN_INT (coeff0 + coeff1));
3643 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
3647 /* If one of the operands is a PLUS or a MINUS, see if we can
3648 simplify this by the associative law.
3649 Don't use the associative law for floating point.
3650 The inaccuracy makes it nonassociative,
3651 and subtle programs can break if operations are associated. */
3653 if (INTEGRAL_MODE_P (mode)
3654 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
3655 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
3656 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
3662 /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
3663 using cc0, in which case we want to leave it as a COMPARE
3664 so we can distinguish it from a register-register-copy.
3666 In IEEE floating point, x-0 is not the same as x. */
3668 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3669 || ! FLOAT_MODE_P (mode) || flag_fast_math)
3670 && op1 == CONST0_RTX (mode))
3673 /* Do nothing here. */
3678 /* None of these optimizations can be done for IEEE
3680 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
3681 && FLOAT_MODE_P (mode) && ! flag_fast_math)
3684 /* We can't assume x-x is 0 even with non-IEEE floating point,
3685 but since it is zero except in very strange circumstances, we
3686 will treat it as zero with -ffast-math. */
3687 if (rtx_equal_p (op0, op1)
3688 && ! side_effects_p (op0)
3689 && (! FLOAT_MODE_P (mode) || flag_fast_math))
3690 return CONST0_RTX (mode);
3692 /* Change subtraction from zero into negation. */
3693 if (op0 == CONST0_RTX (mode))
3694 return gen_rtx (NEG, mode, op1);
3696 /* (-1 - a) is ~a. */
3697 if (op0 == constm1_rtx)
3698 return gen_rtx (NOT, mode, op1);
3700 /* Subtracting 0 has no effect. */
3701 if (op1 == CONST0_RTX (mode))
3704 /* See if this is something like X * C - X or vice versa or
3705 if the multiplication is written as a shift. If so, we can
3706 distribute and make a new multiply, shift, or maybe just
3707 have X (if C is 2 in the example above). But don't make
3708 real multiply if we didn't have one before. */
3710 if (! FLOAT_MODE_P (mode))
3712 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
3713 rtx lhs = op0, rhs = op1;
3716 if (GET_CODE (lhs) == NEG)
3717 coeff0 = -1, lhs = XEXP (lhs, 0);
3718 else if (GET_CODE (lhs) == MULT
3719 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
3721 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
3724 else if (GET_CODE (lhs) == ASHIFT
3725 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
3726 && INTVAL (XEXP (lhs, 1)) >= 0
3727 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
3729 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
3730 lhs = XEXP (lhs, 0);
3733 if (GET_CODE (rhs) == NEG)
3734 coeff1 = - 1, rhs = XEXP (rhs, 0);
3735 else if (GET_CODE (rhs) == MULT
3736 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
3738 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
3741 else if (GET_CODE (rhs) == ASHIFT
3742 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
3743 && INTVAL (XEXP (rhs, 1)) >= 0
3744 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
3746 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
3747 rhs = XEXP (rhs, 0);
3750 if (rtx_equal_p (lhs, rhs))
3752 tem = cse_gen_binary (MULT, mode, lhs,
3753 GEN_INT (coeff0 - coeff1));
3754 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
3758 /* (a - (-b)) -> (a + b). */
3759 if (GET_CODE (op1) == NEG)
3760 return cse_gen_binary (PLUS, mode, op0, XEXP (op1, 0));
3762 /* If one of the operands is a PLUS or a MINUS, see if we can
3763 simplify this by the associative law.
3764 Don't use the associative law for floating point.
3765 The inaccuracy makes it nonassociative,
3766 and subtle programs can break if operations are associated. */
3768 if (INTEGRAL_MODE_P (mode)
3769 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
3770 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
3771 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
3774 /* Don't let a relocatable value get a negative coeff. */
3775 if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode)
3776 return plus_constant (op0, - INTVAL (op1));
3778 /* (x - (x & y)) -> (x & ~y) */
3779 if (GET_CODE (op1) == AND)
3781 if (rtx_equal_p (op0, XEXP (op1, 0)))
3782 return cse_gen_binary (AND, mode, op0, gen_rtx (NOT, mode, XEXP (op1, 1)));
3783 if (rtx_equal_p (op0, XEXP (op1, 1)))
3784 return cse_gen_binary (AND, mode, op0, gen_rtx (NOT, mode, XEXP (op1, 0)));
3789 if (op1 == constm1_rtx)
3791 tem = simplify_unary_operation (NEG, mode, op0, mode);
3793 return tem ? tem : gen_rtx (NEG, mode, op0);
3796 /* In IEEE floating point, x*0 is not always 0. */
3797 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3798 || ! FLOAT_MODE_P (mode) || flag_fast_math)
3799 && op1 == CONST0_RTX (mode)
3800 && ! side_effects_p (op0))
3803 /* In IEEE floating point, x*1 is not equivalent to x for nans.
3804 However, ANSI says we can drop signals,
3805 so we can do this anyway. */
3806 if (op1 == CONST1_RTX (mode))
3809 /* Convert multiply by constant power of two into shift unless
3810 we are still generating RTL. This test is a kludge. */
3811 if (GET_CODE (op1) == CONST_INT
3812 && (val = exact_log2 (INTVAL (op1))) >= 0
3813 /* If the mode is larger than the host word size, and the
3814 uppermost bit is set, then this isn't a power of two due
3815 to implicit sign extension. */
3816 && (width <= HOST_BITS_PER_WIDE_INT
3817 || val != HOST_BITS_PER_WIDE_INT - 1)
3818 && ! rtx_equal_function_value_matters)
3819 return gen_rtx (ASHIFT, mode, op0, GEN_INT (val));
3821 if (GET_CODE (op1) == CONST_DOUBLE
3822 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
3826 int op1is2, op1ism1;
3828 if (setjmp (handler))
3831 set_float_handler (handler);
3832 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
3833 op1is2 = REAL_VALUES_EQUAL (d, dconst2);
3834 op1ism1 = REAL_VALUES_EQUAL (d, dconstm1);
3835 set_float_handler (NULL_PTR);
3837 /* x*2 is x+x and x*(-1) is -x */
3838 if (op1is2 && GET_MODE (op0) == mode)
3839 return gen_rtx (PLUS, mode, op0, copy_rtx (op0));
3841 else if (op1ism1 && GET_MODE (op0) == mode)
3842 return gen_rtx (NEG, mode, op0);
3847 if (op1 == const0_rtx)
3849 if (GET_CODE (op1) == CONST_INT
3850 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
3852 if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
3854 /* A | (~A) -> -1 */
3855 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
3856 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
3857 && ! side_effects_p (op0)
3858 && GET_MODE_CLASS (mode) != MODE_CC)
3863 if (op1 == const0_rtx)
3865 if (GET_CODE (op1) == CONST_INT
3866 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
3867 return gen_rtx (NOT, mode, op0);
3868 if (op0 == op1 && ! side_effects_p (op0)
3869 && GET_MODE_CLASS (mode) != MODE_CC)
3874 if (op1 == const0_rtx && ! side_effects_p (op0))
3876 if (GET_CODE (op1) == CONST_INT
3877 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
3879 if (op0 == op1 && ! side_effects_p (op0)
3880 && GET_MODE_CLASS (mode) != MODE_CC)
3883 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
3884 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
3885 && ! side_effects_p (op0)
3886 && GET_MODE_CLASS (mode) != MODE_CC)
3891 /* Convert divide by power of two into shift (divide by 1 handled
3893 if (GET_CODE (op1) == CONST_INT
3894 && (arg1 = exact_log2 (INTVAL (op1))) > 0)
3895 return gen_rtx (LSHIFTRT, mode, op0, GEN_INT (arg1));
3897 /* ... fall through ... */
3900 if (op1 == CONST1_RTX (mode))
3903 /* In IEEE floating point, 0/x is not always 0. */
3904 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3905 || ! FLOAT_MODE_P (mode) || flag_fast_math)
3906 && op0 == CONST0_RTX (mode)
3907 && ! side_effects_p (op1))
3910 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3911 /* Change division by a constant into multiplication. Only do
3912 this with -ffast-math until an expert says it is safe in
3914 else if (GET_CODE (op1) == CONST_DOUBLE
3915 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
3916 && op1 != CONST0_RTX (mode)
3920 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
3922 if (! REAL_VALUES_EQUAL (d, dconst0))
3924 #if defined (REAL_ARITHMETIC)
3925 REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d);
3926 return gen_rtx (MULT, mode, op0,
3927 CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
3929 return gen_rtx (MULT, mode, op0,
3930 CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
3938 /* Handle modulus by power of two (mod with 1 handled below). */
3939 if (GET_CODE (op1) == CONST_INT
3940 && exact_log2 (INTVAL (op1)) > 0)
3941 return gen_rtx (AND, mode, op0, GEN_INT (INTVAL (op1) - 1));
3943 /* ... fall through ... */
3946 if ((op0 == const0_rtx || op1 == const1_rtx)
3947 && ! side_effects_p (op0) && ! side_effects_p (op1))
3953 /* Rotating ~0 always results in ~0. */
3954 if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT
3955 && INTVAL (op0) == GET_MODE_MASK (mode)
3956 && ! side_effects_p (op1))
3959 /* ... fall through ... */
3964 if (op1 == const0_rtx)
3966 if (op0 == const0_rtx && ! side_effects_p (op1))
3971 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
3972 && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1)
3973 && ! side_effects_p (op0))
3975 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
3980 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
3982 == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1)
3983 && ! side_effects_p (op0))
3985 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
3990 if (op1 == const0_rtx && ! side_effects_p (op0))
3992 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
3997 if (op1 == constm1_rtx && ! side_effects_p (op0))
3999 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
4010 /* Get the integer argument values in two forms:
4011 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
4013 arg0 = INTVAL (op0);
4014 arg1 = INTVAL (op1);
4016 if (width < HOST_BITS_PER_WIDE_INT)
4018 arg0 &= ((HOST_WIDE_INT) 1 << width) - 1;
4019 arg1 &= ((HOST_WIDE_INT) 1 << width) - 1;
4022 if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1)))
4023 arg0s |= ((HOST_WIDE_INT) (-1) << width);
4026 if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1)))
4027 arg1s |= ((HOST_WIDE_INT) (-1) << width);
4035 /* Compute the value of the arithmetic. */
4040 val = arg0s + arg1s;
4044 val = arg0s - arg1s;
4048 val = arg0s * arg1s;
4054 val = arg0s / arg1s;
4060 val = arg0s % arg1s;
4066 val = (unsigned HOST_WIDE_INT) arg0 / arg1;
4072 val = (unsigned HOST_WIDE_INT) arg0 % arg1;
4088 /* If shift count is undefined, don't fold it; let the machine do
4089 what it wants. But truncate it if the machine will do that. */
4093 #ifdef SHIFT_COUNT_TRUNCATED
4094 if (SHIFT_COUNT_TRUNCATED)
4098 val = ((unsigned HOST_WIDE_INT) arg0) >> arg1;
4105 #ifdef SHIFT_COUNT_TRUNCATED
4106 if (SHIFT_COUNT_TRUNCATED)
4110 val = ((unsigned HOST_WIDE_INT) arg0) << arg1;
4117 #ifdef SHIFT_COUNT_TRUNCATED
4118 if (SHIFT_COUNT_TRUNCATED)
4122 val = arg0s >> arg1;
4124 /* Bootstrap compiler may not have sign extended the right shift.
4125 Manually extend the sign to insure bootstrap cc matches gcc. */
4126 if (arg0s < 0 && arg1 > 0)
4127 val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1);
4136 val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1))
4137 | (((unsigned HOST_WIDE_INT) arg0) >> arg1));
4145 val = ((((unsigned HOST_WIDE_INT) arg0) << arg1)
4146 | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1)));
4150 /* Do nothing here. */
4154 val = arg0s <= arg1s ? arg0s : arg1s;
4158 val = ((unsigned HOST_WIDE_INT) arg0
4159 <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
4163 val = arg0s > arg1s ? arg0s : arg1s;
4167 val = ((unsigned HOST_WIDE_INT) arg0
4168 > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
4175 /* Clear the bits that don't belong in our mode, unless they and our sign
4176 bit are all one. So we get either a reasonable negative value or a
4177 reasonable unsigned value for this mode. */
4178 if (width < HOST_BITS_PER_WIDE_INT
4179 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
4180 != ((HOST_WIDE_INT) (-1) << (width - 1))))
4181 val &= ((HOST_WIDE_INT) 1 << width) - 1;
4183 /* If this would be an entire word for the target, but is not for
4184 the host, then sign-extend on the host so that the number will look
4185 the same way on the host that it would on the target.
4187 For example, when building a 64 bit alpha hosted 32 bit sparc
4188 targeted compiler, then we want the 32 bit unsigned value -1 to be
4189 represented as a 64 bit value -1, and not as 0x00000000ffffffff.
4190 The later confuses the sparc backend. */
4192 if (BITS_PER_WORD < HOST_BITS_PER_WIDE_INT && BITS_PER_WORD == width
4193 && (val & ((HOST_WIDE_INT) 1 << (width - 1))))
4194 val |= ((HOST_WIDE_INT) (-1) << width);
4196 return GEN_INT (val);
4199 /* Simplify a PLUS or MINUS, at least one of whose operands may be another
4202 Rather than test for specific case, we do this by a brute-force method
4203 and do all possible simplifications until no more changes occur. Then
4204 we rebuild the operation. */
4207 simplify_plus_minus (code, mode, op0, op1)
4209 enum machine_mode mode;
4215 int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
4216 int first = 1, negate = 0, changed;
4219 bzero ((char *) ops, sizeof ops);
4221 /* Set up the two operands and then expand them until nothing has been
4222 changed. If we run out of room in our array, give up; this should
4223 almost never happen. */
4225 ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
4232 for (i = 0; i < n_ops; i++)
4233 switch (GET_CODE (ops[i]))
4240 ops[n_ops] = XEXP (ops[i], 1);
4241 negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
4242 ops[i] = XEXP (ops[i], 0);
4248 ops[i] = XEXP (ops[i], 0);
4249 negs[i] = ! negs[i];
4254 ops[i] = XEXP (ops[i], 0);
4260 /* ~a -> (-a - 1) */
4263 ops[n_ops] = constm1_rtx;
4264 negs[n_ops++] = negs[i];
4265 ops[i] = XEXP (ops[i], 0);
4266 negs[i] = ! negs[i];
4273 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
4281 /* If we only have two operands, we can't do anything. */
4285 /* Now simplify each pair of operands until nothing changes. The first
4286 time through just simplify constants against each other. */
4293 for (i = 0; i < n_ops - 1; i++)
4294 for (j = i + 1; j < n_ops; j++)
4295 if (ops[i] != 0 && ops[j] != 0
4296 && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
4298 rtx lhs = ops[i], rhs = ops[j];
4299 enum rtx_code ncode = PLUS;
4301 if (negs[i] && ! negs[j])
4302 lhs = ops[j], rhs = ops[i], ncode = MINUS;
4303 else if (! negs[i] && negs[j])
4306 tem = simplify_binary_operation (ncode, mode, lhs, rhs);
4309 ops[i] = tem, ops[j] = 0;
4310 negs[i] = negs[i] && negs[j];
4311 if (GET_CODE (tem) == NEG)
4312 ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
4314 if (GET_CODE (ops[i]) == CONST_INT && negs[i])
4315 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
4323 /* Pack all the operands to the lower-numbered entries and give up if
4324 we didn't reduce the number of operands we had. Make sure we
4325 count a CONST as two operands. If we have the same number of
4326 operands, but have made more CONSTs than we had, this is also
4327 an improvement, so accept it. */
4329 for (i = 0, j = 0; j < n_ops; j++)
4332 ops[i] = ops[j], negs[i++] = negs[j];
4333 if (GET_CODE (ops[j]) == CONST)
4337 if (i + n_consts > input_ops
4338 || (i + n_consts == input_ops && n_consts <= input_consts))
4343 /* If we have a CONST_INT, put it last. */
4344 for (i = 0; i < n_ops - 1; i++)
4345 if (GET_CODE (ops[i]) == CONST_INT)
4347 tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
4348 j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
4351 /* Put a non-negated operand first. If there aren't any, make all
4352 operands positive and negate the whole thing later. */
4353 for (i = 0; i < n_ops && negs[i]; i++)
4358 for (i = 0; i < n_ops; i++)
4364 tem = ops[0], ops[0] = ops[i], ops[i] = tem;
4365 j = negs[0], negs[0] = negs[i], negs[i] = j;
4368 /* Now make the result by performing the requested operations. */
4370 for (i = 1; i < n_ops; i++)
4371 result = cse_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
4373 return negate ? gen_rtx (NEG, mode, result) : result;
4376 /* Make a binary operation by properly ordering the operands and
4377 seeing if the expression folds. */
4380 cse_gen_binary (code, mode, op0, op1)
4382 enum machine_mode mode;
4387 /* Put complex operands first and constants second if commutative. */
4388 if (GET_RTX_CLASS (code) == 'c'
4389 && ((CONSTANT_P (op0) && GET_CODE (op1) != CONST_INT)
4390 || (GET_RTX_CLASS (GET_CODE (op0)) == 'o'
4391 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')
4392 || (GET_CODE (op0) == SUBREG
4393 && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op0))) == 'o'
4394 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')))
4395 tem = op0, op0 = op1, op1 = tem;
4397 /* If this simplifies, do it. */
4398 tem = simplify_binary_operation (code, mode, op0, op1);
4403 /* Handle addition and subtraction of CONST_INT specially. Otherwise,
4404 just form the operation. */
4406 if (code == PLUS && GET_CODE (op1) == CONST_INT
4407 && GET_MODE (op0) != VOIDmode)
4408 return plus_constant (op0, INTVAL (op1));
4409 else if (code == MINUS && GET_CODE (op1) == CONST_INT
4410 && GET_MODE (op0) != VOIDmode)
4411 return plus_constant (op0, - INTVAL (op1));
4413 return gen_rtx (code, mode, op0, op1);
4416 /* Like simplify_binary_operation except used for relational operators.
4417 MODE is the mode of the operands, not that of the result. If MODE
4418 is VOIDmode, both operands must also be VOIDmode and we compare the
4419 operands in "infinite precision".
4421 If no simplification is possible, this function returns zero. Otherwise,
4422 it returns either const_true_rtx or const0_rtx. */
4425 simplify_relational_operation (code, mode, op0, op1)
4427 enum machine_mode mode;
4430 int equal, op0lt, op0ltu, op1lt, op1ltu;
4433 /* If op0 is a compare, extract the comparison arguments from it. */
4434 if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
4435 op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
4437 /* We can't simplify MODE_CC values since we don't know what the
4438 actual comparison is. */
4439 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC
4446 /* For integer comparisons of A and B maybe we can simplify A - B and can
4447 then simplify a comparison of that with zero. If A and B are both either
4448 a register or a CONST_INT, this can't help; testing for these cases will
4449 prevent infinite recursion here and speed things up.
4451 If CODE is an unsigned comparison, then we can never do this optimization,
4452 because it gives an incorrect result if the subtraction wraps around zero.
4453 ANSI C defines unsigned operations such that they never overflow, and
4454 thus such cases can not be ignored. */
4456 if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx
4457 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT)
4458 && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT))
4459 && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1))
4460 && code != GTU && code != GEU && code != LTU && code != LEU)
4461 return simplify_relational_operation (signed_condition (code),
4462 mode, tem, const0_rtx);
4464 /* For non-IEEE floating-point, if the two operands are equal, we know the
4466 if (rtx_equal_p (op0, op1)
4467 && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
4468 || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math))
4469 equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0;
4471 /* If the operands are floating-point constants, see if we can fold
4473 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
4474 else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
4475 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
4477 REAL_VALUE_TYPE d0, d1;
4480 if (setjmp (handler))
4483 set_float_handler (handler);
4484 REAL_VALUE_FROM_CONST_DOUBLE (d0, op0);
4485 REAL_VALUE_FROM_CONST_DOUBLE (d1, op1);
4486 equal = REAL_VALUES_EQUAL (d0, d1);
4487 op0lt = op0ltu = REAL_VALUES_LESS (d0, d1);
4488 op1lt = op1ltu = REAL_VALUES_LESS (d1, d0);
4489 set_float_handler (NULL_PTR);
4491 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
4493 /* Otherwise, see if the operands are both integers. */
4494 else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode)
4495 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
4496 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
4498 int width = GET_MODE_BITSIZE (mode);
4499 HOST_WIDE_INT l0s, h0s, l1s, h1s;
4500 unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u;
4502 /* Get the two words comprising each integer constant. */
4503 if (GET_CODE (op0) == CONST_DOUBLE)
4505 l0u = l0s = CONST_DOUBLE_LOW (op0);
4506 h0u = h0s = CONST_DOUBLE_HIGH (op0);
4510 l0u = l0s = INTVAL (op0);
4511 h0u = h0s = l0s < 0 ? -1 : 0;
4514 if (GET_CODE (op1) == CONST_DOUBLE)
4516 l1u = l1s = CONST_DOUBLE_LOW (op1);
4517 h1u = h1s = CONST_DOUBLE_HIGH (op1);
4521 l1u = l1s = INTVAL (op1);
4522 h1u = h1s = l1s < 0 ? -1 : 0;
4525 /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT,
4526 we have to sign or zero-extend the values. */
4527 if (width != 0 && width <= HOST_BITS_PER_WIDE_INT)
4528 h0u = h1u = 0, h0s = l0s < 0 ? -1 : 0, h1s = l1s < 0 ? -1 : 0;
4530 if (width != 0 && width < HOST_BITS_PER_WIDE_INT)
4532 l0u &= ((HOST_WIDE_INT) 1 << width) - 1;
4533 l1u &= ((HOST_WIDE_INT) 1 << width) - 1;
4535 if (l0s & ((HOST_WIDE_INT) 1 << (width - 1)))
4536 l0s |= ((HOST_WIDE_INT) (-1) << width);
4538 if (l1s & ((HOST_WIDE_INT) 1 << (width - 1)))
4539 l1s |= ((HOST_WIDE_INT) (-1) << width);
4542 equal = (h0u == h1u && l0u == l1u);
4543 op0lt = (h0s < h1s || (h0s == h1s && l0s < l1s));
4544 op1lt = (h1s < h0s || (h1s == h0s && l1s < l0s));
4545 op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u));
4546 op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u));
4549 /* Otherwise, there are some code-specific tests we can make. */
4555 /* References to the frame plus a constant or labels cannot
4556 be zero, but a SYMBOL_REF can due to #pragma weak. */
4557 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
4558 || GET_CODE (op0) == LABEL_REF)
4559 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4560 /* On some machines, the ap reg can be 0 sometimes. */
4561 && op0 != arg_pointer_rtx
4568 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
4569 || GET_CODE (op0) == LABEL_REF)
4570 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4571 && op0 != arg_pointer_rtx
4574 return const_true_rtx;
4578 /* Unsigned values are never negative. */
4579 if (op1 == const0_rtx)
4580 return const_true_rtx;
4584 if (op1 == const0_rtx)
4589 /* Unsigned values are never greater than the largest
4591 if (GET_CODE (op1) == CONST_INT
4592 && INTVAL (op1) == GET_MODE_MASK (mode)
4593 && INTEGRAL_MODE_P (mode))
4594 return const_true_rtx;
4598 if (GET_CODE (op1) == CONST_INT
4599 && INTVAL (op1) == GET_MODE_MASK (mode)
4600 && INTEGRAL_MODE_P (mode))
4611 /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set
4616 return equal ? const_true_rtx : const0_rtx;
4618 return ! equal ? const_true_rtx : const0_rtx;
4620 return op0lt ? const_true_rtx : const0_rtx;
4622 return op1lt ? const_true_rtx : const0_rtx;
4624 return op0ltu ? const_true_rtx : const0_rtx;
4626 return op1ltu ? const_true_rtx : const0_rtx;
4628 return equal || op0lt ? const_true_rtx : const0_rtx;
4630 return equal || op1lt ? const_true_rtx : const0_rtx;
4632 return equal || op0ltu ? const_true_rtx : const0_rtx;
4634 return equal || op1ltu ? const_true_rtx : const0_rtx;
4640 /* Simplify CODE, an operation with result mode MODE and three operands,
4641 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
4642 a constant. Return 0 if no simplifications is possible. */
4645 simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
4647 enum machine_mode mode, op0_mode;
4650 int width = GET_MODE_BITSIZE (mode);
4652 /* VOIDmode means "infinite" precision. */
4654 width = HOST_BITS_PER_WIDE_INT;
4660 if (GET_CODE (op0) == CONST_INT
4661 && GET_CODE (op1) == CONST_INT
4662 && GET_CODE (op2) == CONST_INT
4663 && INTVAL (op1) + INTVAL (op2) <= GET_MODE_BITSIZE (op0_mode)
4664 && width <= HOST_BITS_PER_WIDE_INT)
4666 /* Extracting a bit-field from a constant */
4667 HOST_WIDE_INT val = INTVAL (op0);
4669 if (BITS_BIG_ENDIAN)
4670 val >>= (GET_MODE_BITSIZE (op0_mode)
4671 - INTVAL (op2) - INTVAL (op1));
4673 val >>= INTVAL (op2);
4675 if (HOST_BITS_PER_WIDE_INT != INTVAL (op1))
4677 /* First zero-extend. */
4678 val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1;
4679 /* If desired, propagate sign bit. */
4680 if (code == SIGN_EXTRACT
4681 && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1))))
4682 val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1);
4685 /* Clear the bits that don't belong in our mode,
4686 unless they and our sign bit are all one.
4687 So we get either a reasonable negative value or a reasonable
4688 unsigned value for this mode. */
4689 if (width < HOST_BITS_PER_WIDE_INT
4690 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
4691 != ((HOST_WIDE_INT) (-1) << (width - 1))))
4692 val &= ((HOST_WIDE_INT) 1 << width) - 1;
4694 return GEN_INT (val);
4699 if (GET_CODE (op0) == CONST_INT)
4700 return op0 != const0_rtx ? op1 : op2;
4702 /* Convert a == b ? b : a to "a". */
4703 if (GET_CODE (op0) == NE && ! side_effects_p (op0)
4704 && rtx_equal_p (XEXP (op0, 0), op1)
4705 && rtx_equal_p (XEXP (op0, 1), op2))
4707 else if (GET_CODE (op0) == EQ && ! side_effects_p (op0)
4708 && rtx_equal_p (XEXP (op0, 1), op1)
4709 && rtx_equal_p (XEXP (op0, 0), op2))
4720 /* If X is a nontrivial arithmetic operation on an argument
4721 for which a constant value can be determined, return
4722 the result of operating on that value, as a constant.
4723 Otherwise, return X, possibly with one or more operands
4724 modified by recursive calls to this function.
4726 If X is a register whose contents are known, we do NOT
4727 return those contents here. equiv_constant is called to
4730 INSN is the insn that we may be modifying. If it is 0, make a copy
4731 of X before modifying it. */
4738 register enum rtx_code code;
4739 register enum machine_mode mode;
4746 /* Folded equivalents of first two operands of X. */
4750 /* Constant equivalents of first three operands of X;
4751 0 when no such equivalent is known. */
4756 /* The mode of the first operand of X. We need this for sign and zero
4758 enum machine_mode mode_arg0;
4763 mode = GET_MODE (x);
4764 code = GET_CODE (x);
4773 /* No use simplifying an EXPR_LIST
4774 since they are used only for lists of args
4775 in a function call's REG_EQUAL note. */
4777 /* Changing anything inside an ADDRESSOF is incorrect; we don't
4778 want to (e.g.,) make (addressof (const_int 0)) just because
4779 the location is known to be zero. */
4785 return prev_insn_cc0;
4789 /* If the next insn is a CODE_LABEL followed by a jump table,
4790 PC's value is a LABEL_REF pointing to that label. That
4791 lets us fold switch statements on the Vax. */
4792 if (insn && GET_CODE (insn) == JUMP_INSN)
4794 rtx next = next_nonnote_insn (insn);
4796 if (next && GET_CODE (next) == CODE_LABEL
4797 && NEXT_INSN (next) != 0
4798 && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
4799 && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
4800 || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
4801 return gen_rtx (LABEL_REF, Pmode, next);
4806 /* See if we previously assigned a constant value to this SUBREG. */
4807 if ((new = lookup_as_function (x, CONST_INT)) != 0
4808 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
4811 /* If this is a paradoxical SUBREG, we have no idea what value the
4812 extra bits would have. However, if the operand is equivalent
4813 to a SUBREG whose operand is the same as our mode, and all the
4814 modes are within a word, we can just use the inner operand
4815 because these SUBREGs just say how to treat the register.
4817 Similarly if we find an integer constant. */
4819 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4821 enum machine_mode imode = GET_MODE (SUBREG_REG (x));
4822 struct table_elt *elt;
4824 if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
4825 && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
4826 && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
4828 for (elt = elt->first_same_value;
4829 elt; elt = elt->next_same_value)
4831 if (CONSTANT_P (elt->exp)
4832 && GET_MODE (elt->exp) == VOIDmode)
4835 if (GET_CODE (elt->exp) == SUBREG
4836 && GET_MODE (SUBREG_REG (elt->exp)) == mode
4837 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
4838 return copy_rtx (SUBREG_REG (elt->exp));
4844 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
4845 We might be able to if the SUBREG is extracting a single word in an
4846 integral mode or extracting the low part. */
4848 folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
4849 const_arg0 = equiv_constant (folded_arg0);
4851 folded_arg0 = const_arg0;
4853 if (folded_arg0 != SUBREG_REG (x))
4857 if (GET_MODE_CLASS (mode) == MODE_INT
4858 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
4859 && GET_MODE (SUBREG_REG (x)) != VOIDmode)
4860 new = operand_subword (folded_arg0, SUBREG_WORD (x), 0,
4861 GET_MODE (SUBREG_REG (x)));
4862 if (new == 0 && subreg_lowpart_p (x))
4863 new = gen_lowpart_if_possible (mode, folded_arg0);
4868 /* If this is a narrowing SUBREG and our operand is a REG, see if
4869 we can find an equivalence for REG that is an arithmetic operation
4870 in a wider mode where both operands are paradoxical SUBREGs
4871 from objects of our result mode. In that case, we couldn't report
4872 an equivalent value for that operation, since we don't know what the
4873 extra bits will be. But we can find an equivalence for this SUBREG
4874 by folding that operation is the narrow mode. This allows us to
4875 fold arithmetic in narrow modes when the machine only supports
4876 word-sized arithmetic.
4878 Also look for a case where we have a SUBREG whose operand is the
4879 same as our result. If both modes are smaller than a word, we
4880 are simply interpreting a register in different modes and we
4881 can use the inner value. */
4883 if (GET_CODE (folded_arg0) == REG
4884 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0))
4885 && subreg_lowpart_p (x))
4887 struct table_elt *elt;
4889 /* We can use HASH here since we know that canon_hash won't be
4891 elt = lookup (folded_arg0,
4892 HASH (folded_arg0, GET_MODE (folded_arg0)),
4893 GET_MODE (folded_arg0));
4896 elt = elt->first_same_value;
4898 for (; elt; elt = elt->next_same_value)
4900 enum rtx_code eltcode = GET_CODE (elt->exp);
4902 /* Just check for unary and binary operations. */
4903 if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1'
4904 && GET_CODE (elt->exp) != SIGN_EXTEND
4905 && GET_CODE (elt->exp) != ZERO_EXTEND
4906 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
4907 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode)
4909 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
4911 if (GET_CODE (op0) != REG && ! CONSTANT_P (op0))
4912 op0 = fold_rtx (op0, NULL_RTX);
4914 op0 = equiv_constant (op0);
4916 new = simplify_unary_operation (GET_CODE (elt->exp), mode,
4919 else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2'
4920 || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c')
4921 && eltcode != DIV && eltcode != MOD
4922 && eltcode != UDIV && eltcode != UMOD
4923 && eltcode != ASHIFTRT && eltcode != LSHIFTRT
4924 && eltcode != ROTATE && eltcode != ROTATERT
4925 && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
4926 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
4928 || CONSTANT_P (XEXP (elt->exp, 0)))
4929 && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
4930 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
4932 || CONSTANT_P (XEXP (elt->exp, 1))))
4934 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
4935 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
4937 if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0))
4938 op0 = fold_rtx (op0, NULL_RTX);
4941 op0 = equiv_constant (op0);
4943 if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1))
4944 op1 = fold_rtx (op1, NULL_RTX);
4947 op1 = equiv_constant (op1);
4949 /* If we are looking for the low SImode part of
4950 (ashift:DI c (const_int 32)), it doesn't work
4951 to compute that in SImode, because a 32-bit shift
4952 in SImode is unpredictable. We know the value is 0. */
4954 && GET_CODE (elt->exp) == ASHIFT
4955 && GET_CODE (op1) == CONST_INT
4956 && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
4958 if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
4960 /* If the count fits in the inner mode's width,
4961 but exceeds the outer mode's width,
4962 the value will get truncated to 0
4966 /* If the count exceeds even the inner mode's width,
4967 don't fold this expression. */
4970 else if (op0 && op1)
4971 new = simplify_binary_operation (GET_CODE (elt->exp), mode,
4975 else if (GET_CODE (elt->exp) == SUBREG
4976 && GET_MODE (SUBREG_REG (elt->exp)) == mode
4977 && (GET_MODE_SIZE (GET_MODE (folded_arg0))
4979 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
4980 new = copy_rtx (SUBREG_REG (elt->exp));
4991 /* If we have (NOT Y), see if Y is known to be (NOT Z).
4992 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
4993 new = lookup_as_function (XEXP (x, 0), code);
4995 return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
4999 /* If we are not actually processing an insn, don't try to find the
5000 best address. Not only don't we care, but we could modify the
5001 MEM in an invalid way since we have no insn to validate against. */
5003 find_best_addr (insn, &XEXP (x, 0));
5006 /* Even if we don't fold in the insn itself,
5007 we can safely do so here, in hopes of getting a constant. */
5008 rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
5010 HOST_WIDE_INT offset = 0;
5012 if (GET_CODE (addr) == REG
5013 && REGNO_QTY_VALID_P (REGNO (addr))
5014 && GET_MODE (addr) == qty_mode[reg_qty[REGNO (addr)]]
5015 && qty_const[reg_qty[REGNO (addr)]] != 0)
5016 addr = qty_const[reg_qty[REGNO (addr)]];
5018 /* If address is constant, split it into a base and integer offset. */
5019 if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
5021 else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
5022 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
5024 base = XEXP (XEXP (addr, 0), 0);
5025 offset = INTVAL (XEXP (XEXP (addr, 0), 1));
5027 else if (GET_CODE (addr) == LO_SUM
5028 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
5029 base = XEXP (addr, 1);
5030 else if (GET_CODE (addr) == ADDRESSOF)
5031 return change_address (x, VOIDmode, addr);
5033 /* If this is a constant pool reference, we can fold it into its
5034 constant to allow better value tracking. */
5035 if (base && GET_CODE (base) == SYMBOL_REF
5036 && CONSTANT_POOL_ADDRESS_P (base))
5038 rtx constant = get_pool_constant (base);
5039 enum machine_mode const_mode = get_pool_mode (base);
5042 if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
5043 constant_pool_entries_cost = COST (constant);
5045 /* If we are loading the full constant, we have an equivalence. */
5046 if (offset == 0 && mode == const_mode)
5049 /* If this actually isn't a constant (weird!), we can't do
5050 anything. Otherwise, handle the two most common cases:
5051 extracting a word from a multi-word constant, and extracting
5052 the low-order bits. Other cases don't seem common enough to
5054 if (! CONSTANT_P (constant))
5057 if (GET_MODE_CLASS (mode) == MODE_INT
5058 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
5059 && offset % UNITS_PER_WORD == 0
5060 && (new = operand_subword (constant,
5061 offset / UNITS_PER_WORD,
5062 0, const_mode)) != 0)
5065 if (((BYTES_BIG_ENDIAN
5066 && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
5067 || (! BYTES_BIG_ENDIAN && offset == 0))
5068 && (new = gen_lowpart_if_possible (mode, constant)) != 0)
5072 /* If this is a reference to a label at a known position in a jump
5073 table, we also know its value. */
5074 if (base && GET_CODE (base) == LABEL_REF)
5076 rtx label = XEXP (base, 0);
5077 rtx table_insn = NEXT_INSN (label);
5079 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
5080 && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
5082 rtx table = PATTERN (table_insn);
5085 && (offset / GET_MODE_SIZE (GET_MODE (table))
5086 < XVECLEN (table, 0)))
5087 return XVECEXP (table, 0,
5088 offset / GET_MODE_SIZE (GET_MODE (table)));
5090 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
5091 && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
5093 rtx table = PATTERN (table_insn);
5096 && (offset / GET_MODE_SIZE (GET_MODE (table))
5097 < XVECLEN (table, 1)))
5099 offset /= GET_MODE_SIZE (GET_MODE (table));
5100 new = gen_rtx (MINUS, Pmode, XVECEXP (table, 1, offset),
5103 if (GET_MODE (table) != Pmode)
5104 new = gen_rtx (TRUNCATE, GET_MODE (table), new);
5106 /* Indicate this is a constant. This isn't a
5107 valid form of CONST, but it will only be used
5108 to fold the next insns and then discarded, so
5109 it should be safe. */
5110 return gen_rtx (CONST, GET_MODE (new), new);
5119 for (i = XVECLEN (x, 3) - 1; i >= 0; i--)
5120 validate_change (insn, &XVECEXP (x, 3, i),
5121 fold_rtx (XVECEXP (x, 3, i), insn), 0);
5131 mode_arg0 = VOIDmode;
5133 /* Try folding our operands.
5134 Then see which ones have constant values known. */
5136 fmt = GET_RTX_FORMAT (code);
5137 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5140 rtx arg = XEXP (x, i);
5141 rtx folded_arg = arg, const_arg = 0;
5142 enum machine_mode mode_arg = GET_MODE (arg);
5143 rtx cheap_arg, expensive_arg;
5144 rtx replacements[2];
5147 /* Most arguments are cheap, so handle them specially. */
5148 switch (GET_CODE (arg))
5151 /* This is the same as calling equiv_constant; it is duplicated
5153 if (REGNO_QTY_VALID_P (REGNO (arg))
5154 && qty_const[reg_qty[REGNO (arg)]] != 0
5155 && GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != REG
5156 && GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != PLUS)
5158 = gen_lowpart_if_possible (GET_MODE (arg),
5159 qty_const[reg_qty[REGNO (arg)]]);
5172 folded_arg = prev_insn_cc0;
5173 mode_arg = prev_insn_cc0_mode;
5174 const_arg = equiv_constant (folded_arg);
5179 folded_arg = fold_rtx (arg, insn);
5180 const_arg = equiv_constant (folded_arg);
5183 /* For the first three operands, see if the operand
5184 is constant or equivalent to a constant. */
5188 folded_arg0 = folded_arg;
5189 const_arg0 = const_arg;
5190 mode_arg0 = mode_arg;
5193 folded_arg1 = folded_arg;
5194 const_arg1 = const_arg;
5197 const_arg2 = const_arg;
5201 /* Pick the least expensive of the folded argument and an
5202 equivalent constant argument. */
5203 if (const_arg == 0 || const_arg == folded_arg
5204 || COST (const_arg) > COST (folded_arg))
5205 cheap_arg = folded_arg, expensive_arg = const_arg;
5207 cheap_arg = const_arg, expensive_arg = folded_arg;
5209 /* Try to replace the operand with the cheapest of the two
5210 possibilities. If it doesn't work and this is either of the first
5211 two operands of a commutative operation, try swapping them.
5212 If THAT fails, try the more expensive, provided it is cheaper
5213 than what is already there. */
5215 if (cheap_arg == XEXP (x, i))
5218 if (insn == 0 && ! copied)
5224 replacements[0] = cheap_arg, replacements[1] = expensive_arg;
5226 j < 2 && replacements[j]
5227 && COST (replacements[j]) < COST (XEXP (x, i));
5230 if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
5233 if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c')
5235 validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
5236 validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
5238 if (apply_change_group ())
5240 /* Swap them back to be invalid so that this loop can
5241 continue and flag them to be swapped back later. */
5244 tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
5253 else if (fmt[i] == 'E')
5254 /* Don't try to fold inside of a vector of expressions.
5255 Doing nothing is harmless. */
5258 /* If a commutative operation, place a constant integer as the second
5259 operand unless the first operand is also a constant integer. Otherwise,
5260 place any constant second unless the first operand is also a constant. */
5262 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
5264 if (must_swap || (const_arg0
5266 || (GET_CODE (const_arg0) == CONST_INT
5267 && GET_CODE (const_arg1) != CONST_INT))))
5269 register rtx tem = XEXP (x, 0);
5271 if (insn == 0 && ! copied)
5277 validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
5278 validate_change (insn, &XEXP (x, 1), tem, 1);
5279 if (apply_change_group ())
5281 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
5282 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
5287 /* If X is an arithmetic operation, see if we can simplify it. */
5289 switch (GET_RTX_CLASS (code))
5295 /* We can't simplify extension ops unless we know the
5297 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
5298 && mode_arg0 == VOIDmode)
5301 /* If we had a CONST, strip it off and put it back later if we
5303 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
5304 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
5306 new = simplify_unary_operation (code, mode,
5307 const_arg0 ? const_arg0 : folded_arg0,
5309 if (new != 0 && is_const)
5310 new = gen_rtx (CONST, mode, new);
5315 /* See what items are actually being compared and set FOLDED_ARG[01]
5316 to those values and CODE to the actual comparison code. If any are
5317 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
5318 do anything if both operands are already known to be constant. */
5320 if (const_arg0 == 0 || const_arg1 == 0)
5322 struct table_elt *p0, *p1;
5323 rtx true = const_true_rtx, false = const0_rtx;
5324 enum machine_mode mode_arg1;
5326 #ifdef FLOAT_STORE_FLAG_VALUE
5327 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5329 true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE,
5331 false = CONST0_RTX (mode);
5335 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
5336 &mode_arg0, &mode_arg1);
5337 const_arg0 = equiv_constant (folded_arg0);
5338 const_arg1 = equiv_constant (folded_arg1);
5340 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
5341 what kinds of things are being compared, so we can't do
5342 anything with this comparison. */
5344 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
5347 /* If we do not now have two constants being compared, see
5348 if we can nevertheless deduce some things about the
5350 if (const_arg0 == 0 || const_arg1 == 0)
5352 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or
5353 non-explicit constant? These aren't zero, but we
5354 don't know their sign. */
5355 if (const_arg1 == const0_rtx
5356 && (NONZERO_BASE_PLUS_P (folded_arg0)
5357 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
5359 || GET_CODE (folded_arg0) == SYMBOL_REF
5361 || GET_CODE (folded_arg0) == LABEL_REF
5362 || GET_CODE (folded_arg0) == CONST))
5366 else if (code == NE)
5370 /* See if the two operands are the same. We don't do this
5371 for IEEE floating-point since we can't assume x == x
5372 since x might be a NaN. */
5374 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
5375 || ! FLOAT_MODE_P (mode_arg0) || flag_fast_math)
5376 && (folded_arg0 == folded_arg1
5377 || (GET_CODE (folded_arg0) == REG
5378 && GET_CODE (folded_arg1) == REG
5379 && (reg_qty[REGNO (folded_arg0)]
5380 == reg_qty[REGNO (folded_arg1)]))
5381 || ((p0 = lookup (folded_arg0,
5382 (safe_hash (folded_arg0, mode_arg0)
5383 % NBUCKETS), mode_arg0))
5384 && (p1 = lookup (folded_arg1,
5385 (safe_hash (folded_arg1, mode_arg0)
5386 % NBUCKETS), mode_arg0))
5387 && p0->first_same_value == p1->first_same_value)))
5388 return ((code == EQ || code == LE || code == GE
5389 || code == LEU || code == GEU)
5392 /* If FOLDED_ARG0 is a register, see if the comparison we are
5393 doing now is either the same as we did before or the reverse
5394 (we only check the reverse if not floating-point). */
5395 else if (GET_CODE (folded_arg0) == REG)
5397 int qty = reg_qty[REGNO (folded_arg0)];
5399 if (REGNO_QTY_VALID_P (REGNO (folded_arg0))
5400 && (comparison_dominates_p (qty_comparison_code[qty], code)
5401 || (comparison_dominates_p (qty_comparison_code[qty],
5402 reverse_condition (code))
5403 && ! FLOAT_MODE_P (mode_arg0)))
5404 && (rtx_equal_p (qty_comparison_const[qty], folded_arg1)
5406 && rtx_equal_p (qty_comparison_const[qty],
5408 || (GET_CODE (folded_arg1) == REG
5409 && (reg_qty[REGNO (folded_arg1)]
5410 == qty_comparison_qty[qty]))))
5411 return (comparison_dominates_p (qty_comparison_code[qty],
5418 /* If we are comparing against zero, see if the first operand is
5419 equivalent to an IOR with a constant. If so, we may be able to
5420 determine the result of this comparison. */
5422 if (const_arg1 == const0_rtx)
5424 rtx y = lookup_as_function (folded_arg0, IOR);
5428 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
5429 && GET_CODE (inner_const) == CONST_INT
5430 && INTVAL (inner_const) != 0)
5432 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
5433 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
5434 && (INTVAL (inner_const)
5435 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
5436 rtx true = const_true_rtx, false = const0_rtx;
5438 #ifdef FLOAT_STORE_FLAG_VALUE
5439 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5441 true = CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE,
5443 false = CONST0_RTX (mode);
5467 new = simplify_relational_operation (code, mode_arg0,
5468 const_arg0 ? const_arg0 : folded_arg0,
5469 const_arg1 ? const_arg1 : folded_arg1);
5470 #ifdef FLOAT_STORE_FLAG_VALUE
5471 if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT)
5472 new = ((new == const0_rtx) ? CONST0_RTX (mode)
5473 : CONST_DOUBLE_FROM_REAL_VALUE (FLOAT_STORE_FLAG_VALUE, mode));
5482 /* If the second operand is a LABEL_REF, see if the first is a MINUS
5483 with that LABEL_REF as its second operand. If so, the result is
5484 the first operand of that MINUS. This handles switches with an
5485 ADDR_DIFF_VEC table. */
5486 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
5489 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
5490 : lookup_as_function (folded_arg0, MINUS);
5492 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
5493 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
5496 /* Now try for a CONST of a MINUS like the above. */
5497 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
5498 : lookup_as_function (folded_arg0, CONST))) != 0
5499 && GET_CODE (XEXP (y, 0)) == MINUS
5500 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
5501 && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg1, 0))
5502 return XEXP (XEXP (y, 0), 0);
5505 /* Likewise if the operands are in the other order. */
5506 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
5509 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
5510 : lookup_as_function (folded_arg1, MINUS);
5512 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
5513 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
5516 /* Now try for a CONST of a MINUS like the above. */
5517 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
5518 : lookup_as_function (folded_arg1, CONST))) != 0
5519 && GET_CODE (XEXP (y, 0)) == MINUS
5520 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
5521 && XEXP (XEXP (XEXP (y, 0),1), 0) == XEXP (const_arg0, 0))
5522 return XEXP (XEXP (y, 0), 0);
5525 /* If second operand is a register equivalent to a negative
5526 CONST_INT, see if we can find a register equivalent to the
5527 positive constant. Make a MINUS if so. Don't do this for
5528 a non-negative constant since we might then alternate between
5529 chosing positive and negative constants. Having the positive
5530 constant previously-used is the more common case. Be sure
5531 the resulting constant is non-negative; if const_arg1 were
5532 the smallest negative number this would overflow: depending
5533 on the mode, this would either just be the same value (and
5534 hence not save anything) or be incorrect. */
5535 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
5536 && INTVAL (const_arg1) < 0
5537 && - INTVAL (const_arg1) >= 0
5538 && GET_CODE (folded_arg1) == REG)
5540 rtx new_const = GEN_INT (- INTVAL (const_arg1));
5542 = lookup (new_const, safe_hash (new_const, mode) % NBUCKETS,
5546 for (p = p->first_same_value; p; p = p->next_same_value)
5547 if (GET_CODE (p->exp) == REG)
5548 return cse_gen_binary (MINUS, mode, folded_arg0,
5549 canon_reg (p->exp, NULL_RTX));
5554 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
5555 If so, produce (PLUS Z C2-C). */
5556 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
5558 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
5559 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
5560 return fold_rtx (plus_constant (copy_rtx (y),
5561 -INTVAL (const_arg1)),
5565 /* ... fall through ... */
5568 case SMIN: case SMAX: case UMIN: case UMAX:
5569 case IOR: case AND: case XOR:
5570 case MULT: case DIV: case UDIV:
5571 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
5572 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
5573 is known to be of similar form, we may be able to replace the
5574 operation with a combined operation. This may eliminate the
5575 intermediate operation if every use is simplified in this way.
5576 Note that the similar optimization done by combine.c only works
5577 if the intermediate operation's result has only one reference. */
5579 if (GET_CODE (folded_arg0) == REG
5580 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
5583 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
5584 rtx y = lookup_as_function (folded_arg0, code);
5586 enum rtx_code associate_code;
5590 || 0 == (inner_const
5591 = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
5592 || GET_CODE (inner_const) != CONST_INT
5593 /* If we have compiled a statement like
5594 "if (x == (x & mask1))", and now are looking at
5595 "x & mask2", we will have a case where the first operand
5596 of Y is the same as our first operand. Unless we detect
5597 this case, an infinite loop will result. */
5598 || XEXP (y, 0) == folded_arg0)
5601 /* Don't associate these operations if they are a PLUS with the
5602 same constant and it is a power of two. These might be doable
5603 with a pre- or post-increment. Similarly for two subtracts of
5604 identical powers of two with post decrement. */
5606 if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
5608 #if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT)
5609 || exact_log2 (INTVAL (const_arg1)) >= 0
5611 #if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT)
5612 || exact_log2 (- INTVAL (const_arg1)) >= 0
5617 /* Compute the code used to compose the constants. For example,
5618 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
5621 = (code == MULT || code == DIV || code == UDIV ? MULT
5622 : is_shift || code == PLUS || code == MINUS ? PLUS : code);
5624 new_const = simplify_binary_operation (associate_code, mode,
5625 const_arg1, inner_const);
5630 /* If we are associating shift operations, don't let this
5631 produce a shift of the size of the object or larger.
5632 This could occur when we follow a sign-extend by a right
5633 shift on a machine that does a sign-extend as a pair
5636 if (is_shift && GET_CODE (new_const) == CONST_INT
5637 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
5639 /* As an exception, we can turn an ASHIFTRT of this
5640 form into a shift of the number of bits - 1. */
5641 if (code == ASHIFTRT)
5642 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
5647 y = copy_rtx (XEXP (y, 0));
5649 /* If Y contains our first operand (the most common way this
5650 can happen is if Y is a MEM), we would do into an infinite
5651 loop if we tried to fold it. So don't in that case. */
5653 if (! reg_mentioned_p (folded_arg0, y))
5654 y = fold_rtx (y, insn);
5656 return cse_gen_binary (code, mode, y, new_const);
5664 new = simplify_binary_operation (code, mode,
5665 const_arg0 ? const_arg0 : folded_arg0,
5666 const_arg1 ? const_arg1 : folded_arg1);
5670 /* (lo_sum (high X) X) is simply X. */
5671 if (code == LO_SUM && const_arg0 != 0
5672 && GET_CODE (const_arg0) == HIGH
5673 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
5679 new = simplify_ternary_operation (code, mode, mode_arg0,
5680 const_arg0 ? const_arg0 : folded_arg0,
5681 const_arg1 ? const_arg1 : folded_arg1,
5682 const_arg2 ? const_arg2 : XEXP (x, 2));
5686 return new ? new : x;
5689 /* Return a constant value currently equivalent to X.
5690 Return 0 if we don't know one. */
5696 if (GET_CODE (x) == REG
5697 && REGNO_QTY_VALID_P (REGNO (x))
5698 && qty_const[reg_qty[REGNO (x)]])
5699 x = gen_lowpart_if_possible (GET_MODE (x), qty_const[reg_qty[REGNO (x)]]);
5701 if (x != 0 && CONSTANT_P (x))
5704 /* If X is a MEM, try to fold it outside the context of any insn to see if
5705 it might be equivalent to a constant. That handles the case where it
5706 is a constant-pool reference. Then try to look it up in the hash table
5707 in case it is something whose value we have seen before. */
5709 if (GET_CODE (x) == MEM)
5711 struct table_elt *elt;
5713 x = fold_rtx (x, NULL_RTX);
5717 elt = lookup (x, safe_hash (x, GET_MODE (x)) % NBUCKETS, GET_MODE (x));
5721 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
5722 if (elt->is_const && CONSTANT_P (elt->exp))
5729 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
5730 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
5731 least-significant part of X.
5732 MODE specifies how big a part of X to return.
5734 If the requested operation cannot be done, 0 is returned.
5736 This is similar to gen_lowpart in emit-rtl.c. */
5739 gen_lowpart_if_possible (mode, x)
5740 enum machine_mode mode;
5743 rtx result = gen_lowpart_common (mode, x);
5747 else if (GET_CODE (x) == MEM)
5749 /* This is the only other case we handle. */
5750 register int offset = 0;
5753 if (WORDS_BIG_ENDIAN)
5754 offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
5755 - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
5756 if (BYTES_BIG_ENDIAN)
5757 /* Adjust the address so that the address-after-the-data is
5759 offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode))
5760 - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
5761 new = gen_rtx (MEM, mode, plus_constant (XEXP (x, 0), offset));
5762 if (! memory_address_p (mode, XEXP (new, 0)))
5764 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
5765 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
5766 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
5773 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
5774 branch. It will be zero if not.
5776 In certain cases, this can cause us to add an equivalence. For example,
5777 if we are following the taken case of
5779 we can add the fact that `i' and '2' are now equivalent.
5781 In any case, we can record that this comparison was passed. If the same
5782 comparison is seen later, we will know its value. */
5785 record_jump_equiv (insn, taken)
5789 int cond_known_true;
5791 enum machine_mode mode, mode0, mode1;
5792 int reversed_nonequality = 0;
5795 /* Ensure this is the right kind of insn. */
5796 if (! condjump_p (insn) || simplejump_p (insn))
5799 /* See if this jump condition is known true or false. */
5801 cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx);
5803 cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx);
5805 /* Get the type of comparison being done and the operands being compared.
5806 If we had to reverse a non-equality condition, record that fact so we
5807 know that it isn't valid for floating-point. */
5808 code = GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0));
5809 op0 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0), insn);
5810 op1 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 1), insn);
5812 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
5813 if (! cond_known_true)
5815 reversed_nonequality = (code != EQ && code != NE);
5816 code = reverse_condition (code);
5819 /* The mode is the mode of the non-constant. */
5821 if (mode1 != VOIDmode)
5824 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
5827 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
5828 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
5829 Make any useful entries we can with that information. Called from
5830 above function and called recursively. */
5833 record_jump_cond (code, mode, op0, op1, reversed_nonequality)
5835 enum machine_mode mode;
5837 int reversed_nonequality;
5839 unsigned op0_hash, op1_hash;
5840 int op0_in_memory, op0_in_struct, op1_in_memory, op1_in_struct;
5841 struct table_elt *op0_elt, *op1_elt;
5843 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
5844 we know that they are also equal in the smaller mode (this is also
5845 true for all smaller modes whether or not there is a SUBREG, but
5846 is not worth testing for with no SUBREG. */
5848 /* Note that GET_MODE (op0) may not equal MODE. */
5849 if (code == EQ && GET_CODE (op0) == SUBREG
5850 && (GET_MODE_SIZE (GET_MODE (op0))
5851 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
5853 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
5854 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
5856 record_jump_cond (code, mode, SUBREG_REG (op0),
5857 tem ? tem : gen_rtx (SUBREG, inner_mode, op1, 0),
5858 reversed_nonequality);
5861 if (code == EQ && GET_CODE (op1) == SUBREG
5862 && (GET_MODE_SIZE (GET_MODE (op1))
5863 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
5865 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
5866 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
5868 record_jump_cond (code, mode, SUBREG_REG (op1),
5869 tem ? tem : gen_rtx (SUBREG, inner_mode, op0, 0),
5870 reversed_nonequality);
5873 /* Similarly, if this is an NE comparison, and either is a SUBREG
5874 making a smaller mode, we know the whole thing is also NE. */
5876 /* Note that GET_MODE (op0) may not equal MODE;
5877 if we test MODE instead, we can get an infinite recursion
5878 alternating between two modes each wider than MODE. */
5880 if (code == NE && GET_CODE (op0) == SUBREG
5881 && subreg_lowpart_p (op0)
5882 && (GET_MODE_SIZE (GET_MODE (op0))
5883 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
5885 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
5886 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
5888 record_jump_cond (code, mode, SUBREG_REG (op0),
5889 tem ? tem : gen_rtx (SUBREG, inner_mode, op1, 0),
5890 reversed_nonequality);
5893 if (code == NE && GET_CODE (op1) == SUBREG
5894 && subreg_lowpart_p (op1)
5895 && (GET_MODE_SIZE (GET_MODE (op1))
5896 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
5898 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
5899 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
5901 record_jump_cond (code, mode, SUBREG_REG (op1),
5902 tem ? tem : gen_rtx (SUBREG, inner_mode, op0, 0),
5903 reversed_nonequality);
5906 /* Hash both operands. */
5909 hash_arg_in_memory = 0;
5910 hash_arg_in_struct = 0;
5911 op0_hash = HASH (op0, mode);
5912 op0_in_memory = hash_arg_in_memory;
5913 op0_in_struct = hash_arg_in_struct;
5919 hash_arg_in_memory = 0;
5920 hash_arg_in_struct = 0;
5921 op1_hash = HASH (op1, mode);
5922 op1_in_memory = hash_arg_in_memory;
5923 op1_in_struct = hash_arg_in_struct;
5928 /* Look up both operands. */
5929 op0_elt = lookup (op0, op0_hash, mode);
5930 op1_elt = lookup (op1, op1_hash, mode);
5932 /* If both operands are already equivalent or if they are not in the
5933 table but are identical, do nothing. */
5934 if ((op0_elt != 0 && op1_elt != 0
5935 && op0_elt->first_same_value == op1_elt->first_same_value)
5936 || op0 == op1 || rtx_equal_p (op0, op1))
5939 /* If we aren't setting two things equal all we can do is save this
5940 comparison. Similarly if this is floating-point. In the latter
5941 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
5942 If we record the equality, we might inadvertently delete code
5943 whose intent was to change -0 to +0. */
5945 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
5947 /* If we reversed a floating-point comparison, if OP0 is not a
5948 register, or if OP1 is neither a register or constant, we can't
5951 if (GET_CODE (op1) != REG)
5952 op1 = equiv_constant (op1);
5954 if ((reversed_nonequality && FLOAT_MODE_P (mode))
5955 || GET_CODE (op0) != REG || op1 == 0)
5958 /* Put OP0 in the hash table if it isn't already. This gives it a
5959 new quantity number. */
5962 if (insert_regs (op0, NULL_PTR, 0))
5964 rehash_using_reg (op0);
5965 op0_hash = HASH (op0, mode);
5967 /* If OP0 is contained in OP1, this changes its hash code
5968 as well. Faster to rehash than to check, except
5969 for the simple case of a constant. */
5970 if (! CONSTANT_P (op1))
5971 op1_hash = HASH (op1,mode);
5974 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
5975 op0_elt->in_memory = op0_in_memory;
5976 op0_elt->in_struct = op0_in_struct;
5979 qty_comparison_code[reg_qty[REGNO (op0)]] = code;
5980 if (GET_CODE (op1) == REG)
5982 /* Look it up again--in case op0 and op1 are the same. */
5983 op1_elt = lookup (op1, op1_hash, mode);
5985 /* Put OP1 in the hash table so it gets a new quantity number. */
5988 if (insert_regs (op1, NULL_PTR, 0))
5990 rehash_using_reg (op1);
5991 op1_hash = HASH (op1, mode);
5994 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
5995 op1_elt->in_memory = op1_in_memory;
5996 op1_elt->in_struct = op1_in_struct;
5999 qty_comparison_qty[reg_qty[REGNO (op0)]] = reg_qty[REGNO (op1)];
6000 qty_comparison_const[reg_qty[REGNO (op0)]] = 0;
6004 qty_comparison_qty[reg_qty[REGNO (op0)]] = -1;
6005 qty_comparison_const[reg_qty[REGNO (op0)]] = op1;
6011 /* If either side is still missing an equivalence, make it now,
6012 then merge the equivalences. */
6016 if (insert_regs (op0, NULL_PTR, 0))
6018 rehash_using_reg (op0);
6019 op0_hash = HASH (op0, mode);
6022 op0_elt = insert (op0, NULL_PTR, op0_hash, mode);
6023 op0_elt->in_memory = op0_in_memory;
6024 op0_elt->in_struct = op0_in_struct;
6029 if (insert_regs (op1, NULL_PTR, 0))
6031 rehash_using_reg (op1);
6032 op1_hash = HASH (op1, mode);
6035 op1_elt = insert (op1, NULL_PTR, op1_hash, mode);
6036 op1_elt->in_memory = op1_in_memory;
6037 op1_elt->in_struct = op1_in_struct;
6040 merge_equiv_classes (op0_elt, op1_elt);
6041 last_jump_equiv_class = op0_elt;
6044 /* CSE processing for one instruction.
6045 First simplify sources and addresses of all assignments
6046 in the instruction, using previously-computed equivalents values.
6047 Then install the new sources and destinations in the table
6048 of available values.
6050 If IN_LIBCALL_BLOCK is nonzero, don't record any equivalence made in
6053 /* Data on one SET contained in the instruction. */
6057 /* The SET rtx itself. */
6059 /* The SET_SRC of the rtx (the original value, if it is changing). */
6061 /* The hash-table element for the SET_SRC of the SET. */
6062 struct table_elt *src_elt;
6063 /* Hash value for the SET_SRC. */
6065 /* Hash value for the SET_DEST. */
6067 /* The SET_DEST, with SUBREG, etc., stripped. */
6069 /* Place where the pointer to the INNER_DEST was found. */
6070 rtx *inner_dest_loc;
6071 /* Nonzero if the SET_SRC is in memory. */
6073 /* Nonzero if the SET_SRC is in a structure. */
6075 /* Nonzero if the SET_SRC contains something
6076 whose value cannot be predicted and understood. */
6078 /* Original machine mode, in case it becomes a CONST_INT. */
6079 enum machine_mode mode;
6080 /* A constant equivalent for SET_SRC, if any. */
6082 /* Hash value of constant equivalent for SET_SRC. */
6083 unsigned src_const_hash;
6084 /* Table entry for constant equivalent for SET_SRC, if any. */
6085 struct table_elt *src_const_elt;
6089 cse_insn (insn, in_libcall_block)
6091 int in_libcall_block;
6093 register rtx x = PATTERN (insn);
6096 register int n_sets = 0;
6098 /* Records what this insn does to set CC0. */
6099 rtx this_insn_cc0 = 0;
6100 enum machine_mode this_insn_cc0_mode = VOIDmode;
6103 struct table_elt *src_eqv_elt = 0;
6104 int src_eqv_volatile;
6105 int src_eqv_in_memory;
6106 int src_eqv_in_struct;
6107 unsigned src_eqv_hash;
6113 /* Find all the SETs and CLOBBERs in this instruction.
6114 Record all the SETs in the array `set' and count them.
6115 Also determine whether there is a CLOBBER that invalidates
6116 all memory references, or all references at varying addresses. */
6118 if (GET_CODE (insn) == CALL_INSN)
6120 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
6121 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
6122 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
6125 if (GET_CODE (x) == SET)
6127 sets = (struct set *) alloca (sizeof (struct set));
6130 /* Ignore SETs that are unconditional jumps.
6131 They never need cse processing, so this does not hurt.
6132 The reason is not efficiency but rather
6133 so that we can test at the end for instructions
6134 that have been simplified to unconditional jumps
6135 and not be misled by unchanged instructions
6136 that were unconditional jumps to begin with. */
6137 if (SET_DEST (x) == pc_rtx
6138 && GET_CODE (SET_SRC (x)) == LABEL_REF)
6141 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
6142 The hard function value register is used only once, to copy to
6143 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
6144 Ensure we invalidate the destination register. On the 80386 no
6145 other code would invalidate it since it is a fixed_reg.
6146 We need not check the return of apply_change_group; see canon_reg. */
6148 else if (GET_CODE (SET_SRC (x)) == CALL)
6150 canon_reg (SET_SRC (x), insn);
6151 apply_change_group ();
6152 fold_rtx (SET_SRC (x), insn);
6153 invalidate (SET_DEST (x), VOIDmode);
6158 else if (GET_CODE (x) == PARALLEL)
6160 register int lim = XVECLEN (x, 0);
6162 sets = (struct set *) alloca (lim * sizeof (struct set));
6164 /* Find all regs explicitly clobbered in this insn,
6165 and ensure they are not replaced with any other regs
6166 elsewhere in this insn.
6167 When a reg that is clobbered is also used for input,
6168 we should presume that that is for a reason,
6169 and we should not substitute some other register
6170 which is not supposed to be clobbered.
6171 Therefore, this loop cannot be merged into the one below
6172 because a CALL may precede a CLOBBER and refer to the
6173 value clobbered. We must not let a canonicalization do
6174 anything in that case. */
6175 for (i = 0; i < lim; i++)
6177 register rtx y = XVECEXP (x, 0, i);
6178 if (GET_CODE (y) == CLOBBER)
6180 rtx clobbered = XEXP (y, 0);
6182 if (GET_CODE (clobbered) == REG
6183 || GET_CODE (clobbered) == SUBREG)
6184 invalidate (clobbered, VOIDmode);
6185 else if (GET_CODE (clobbered) == STRICT_LOW_PART
6186 || GET_CODE (clobbered) == ZERO_EXTRACT)
6187 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
6191 for (i = 0; i < lim; i++)
6193 register rtx y = XVECEXP (x, 0, i);
6194 if (GET_CODE (y) == SET)
6196 /* As above, we ignore unconditional jumps and call-insns and
6197 ignore the result of apply_change_group. */
6198 if (GET_CODE (SET_SRC (y)) == CALL)
6200 canon_reg (SET_SRC (y), insn);
6201 apply_change_group ();
6202 fold_rtx (SET_SRC (y), insn);
6203 invalidate (SET_DEST (y), VOIDmode);
6205 else if (SET_DEST (y) == pc_rtx
6206 && GET_CODE (SET_SRC (y)) == LABEL_REF)
6209 sets[n_sets++].rtl = y;
6211 else if (GET_CODE (y) == CLOBBER)
6213 /* If we clobber memory, canon the address.
6214 This does nothing when a register is clobbered
6215 because we have already invalidated the reg. */
6216 if (GET_CODE (XEXP (y, 0)) == MEM)
6217 canon_reg (XEXP (y, 0), NULL_RTX);
6219 else if (GET_CODE (y) == USE
6220 && ! (GET_CODE (XEXP (y, 0)) == REG
6221 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
6222 canon_reg (y, NULL_RTX);
6223 else if (GET_CODE (y) == CALL)
6225 /* The result of apply_change_group can be ignored; see
6227 canon_reg (y, insn);
6228 apply_change_group ();
6233 else if (GET_CODE (x) == CLOBBER)
6235 if (GET_CODE (XEXP (x, 0)) == MEM)
6236 canon_reg (XEXP (x, 0), NULL_RTX);
6239 /* Canonicalize a USE of a pseudo register or memory location. */
6240 else if (GET_CODE (x) == USE
6241 && ! (GET_CODE (XEXP (x, 0)) == REG
6242 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
6243 canon_reg (XEXP (x, 0), NULL_RTX);
6244 else if (GET_CODE (x) == CALL)
6246 /* The result of apply_change_group can be ignored; see canon_reg. */
6247 canon_reg (x, insn);
6248 apply_change_group ();
6252 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
6253 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
6254 is handled specially for this case, and if it isn't set, then there will
6255 be no equivalence for the destination. */
6256 if (n_sets == 1 && REG_NOTES (insn) != 0
6257 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
6258 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
6259 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
6260 src_eqv = canon_reg (XEXP (tem, 0), NULL_RTX);
6262 /* Canonicalize sources and addresses of destinations.
6263 We do this in a separate pass to avoid problems when a MATCH_DUP is
6264 present in the insn pattern. In that case, we want to ensure that
6265 we don't break the duplicate nature of the pattern. So we will replace
6266 both operands at the same time. Otherwise, we would fail to find an
6267 equivalent substitution in the loop calling validate_change below.
6269 We used to suppress canonicalization of DEST if it appears in SRC,
6270 but we don't do this any more. */
6272 for (i = 0; i < n_sets; i++)
6274 rtx dest = SET_DEST (sets[i].rtl);
6275 rtx src = SET_SRC (sets[i].rtl);
6276 rtx new = canon_reg (src, insn);
6279 if ((GET_CODE (new) == REG && GET_CODE (src) == REG
6280 && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
6281 != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
6282 || (insn_code = recog_memoized (insn)) < 0
6283 || insn_n_dups[insn_code] > 0)
6284 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
6286 SET_SRC (sets[i].rtl) = new;
6288 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
6290 validate_change (insn, &XEXP (dest, 1),
6291 canon_reg (XEXP (dest, 1), insn), 1);
6292 validate_change (insn, &XEXP (dest, 2),
6293 canon_reg (XEXP (dest, 2), insn), 1);
6296 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
6297 || GET_CODE (dest) == ZERO_EXTRACT
6298 || GET_CODE (dest) == SIGN_EXTRACT)
6299 dest = XEXP (dest, 0);
6301 if (GET_CODE (dest) == MEM)
6302 canon_reg (dest, insn);
6305 /* Now that we have done all the replacements, we can apply the change
6306 group and see if they all work. Note that this will cause some
6307 canonicalizations that would have worked individually not to be applied
6308 because some other canonicalization didn't work, but this should not
6311 The result of apply_change_group can be ignored; see canon_reg. */
6313 apply_change_group ();
6315 /* Set sets[i].src_elt to the class each source belongs to.
6316 Detect assignments from or to volatile things
6317 and set set[i] to zero so they will be ignored
6318 in the rest of this function.
6320 Nothing in this loop changes the hash table or the register chains. */
6322 for (i = 0; i < n_sets; i++)
6324 register rtx src, dest;
6325 register rtx src_folded;
6326 register struct table_elt *elt = 0, *p;
6327 enum machine_mode mode;
6330 rtx src_related = 0;
6331 struct table_elt *src_const_elt = 0;
6332 int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000;
6333 int src_related_cost = 10000, src_elt_cost = 10000;
6334 /* Set non-zero if we need to call force_const_mem on with the
6335 contents of src_folded before using it. */
6336 int src_folded_force_flag = 0;
6338 dest = SET_DEST (sets[i].rtl);
6339 src = SET_SRC (sets[i].rtl);
6341 /* If SRC is a constant that has no machine mode,
6342 hash it with the destination's machine mode.
6343 This way we can keep different modes separate. */
6345 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
6346 sets[i].mode = mode;
6350 enum machine_mode eqvmode = mode;
6351 if (GET_CODE (dest) == STRICT_LOW_PART)
6352 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
6354 hash_arg_in_memory = 0;
6355 hash_arg_in_struct = 0;
6356 src_eqv = fold_rtx (src_eqv, insn);
6357 src_eqv_hash = HASH (src_eqv, eqvmode);
6359 /* Find the equivalence class for the equivalent expression. */
6362 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
6364 src_eqv_volatile = do_not_record;
6365 src_eqv_in_memory = hash_arg_in_memory;
6366 src_eqv_in_struct = hash_arg_in_struct;
6369 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
6370 value of the INNER register, not the destination. So it is not
6371 a valid substitution for the source. But save it for later. */
6372 if (GET_CODE (dest) == STRICT_LOW_PART)
6375 src_eqv_here = src_eqv;
6377 /* Simplify and foldable subexpressions in SRC. Then get the fully-
6378 simplified result, which may not necessarily be valid. */
6379 src_folded = fold_rtx (src, insn);
6382 /* ??? This caused bad code to be generated for the m68k port with -O2.
6383 Suppose src is (CONST_INT -1), and that after truncation src_folded
6384 is (CONST_INT 3). Suppose src_folded is then used for src_const.
6385 At the end we will add src and src_const to the same equivalence
6386 class. We now have 3 and -1 on the same equivalence class. This
6387 causes later instructions to be mis-optimized. */
6388 /* If storing a constant in a bitfield, pre-truncate the constant
6389 so we will be able to record it later. */
6390 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
6391 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
6393 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
6395 if (GET_CODE (src) == CONST_INT
6396 && GET_CODE (width) == CONST_INT
6397 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
6398 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
6400 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
6401 << INTVAL (width)) - 1));
6405 /* Compute SRC's hash code, and also notice if it
6406 should not be recorded at all. In that case,
6407 prevent any further processing of this assignment. */
6409 hash_arg_in_memory = 0;
6410 hash_arg_in_struct = 0;
6413 sets[i].src_hash = HASH (src, mode);
6414 sets[i].src_volatile = do_not_record;
6415 sets[i].src_in_memory = hash_arg_in_memory;
6416 sets[i].src_in_struct = hash_arg_in_struct;
6418 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
6419 a pseudo that is set more than once, do not record SRC. Using
6420 SRC as a replacement for anything else will be incorrect in that
6421 situation. Note that this usually occurs only for stack slots,
6422 in which case all the RTL would be referring to SRC, so we don't
6423 lose any optimization opportunities by not having SRC in the
6426 if (GET_CODE (src) == MEM
6427 && find_reg_note (insn, REG_EQUIV, src) != 0
6428 && GET_CODE (dest) == REG
6429 && REGNO (dest) >= FIRST_PSEUDO_REGISTER
6430 && REG_N_SETS (REGNO (dest)) != 1)
6431 sets[i].src_volatile = 1;
6434 /* It is no longer clear why we used to do this, but it doesn't
6435 appear to still be needed. So let's try without it since this
6436 code hurts cse'ing widened ops. */
6437 /* If source is a perverse subreg (such as QI treated as an SI),
6438 treat it as volatile. It may do the work of an SI in one context
6439 where the extra bits are not being used, but cannot replace an SI
6441 if (GET_CODE (src) == SUBREG
6442 && (GET_MODE_SIZE (GET_MODE (src))
6443 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
6444 sets[i].src_volatile = 1;
6447 /* Locate all possible equivalent forms for SRC. Try to replace
6448 SRC in the insn with each cheaper equivalent.
6450 We have the following types of equivalents: SRC itself, a folded
6451 version, a value given in a REG_EQUAL note, or a value related
6454 Each of these equivalents may be part of an additional class
6455 of equivalents (if more than one is in the table, they must be in
6456 the same class; we check for this).
6458 If the source is volatile, we don't do any table lookups.
6460 We note any constant equivalent for possible later use in a
6463 if (!sets[i].src_volatile)
6464 elt = lookup (src, sets[i].src_hash, mode);
6466 sets[i].src_elt = elt;
6468 if (elt && src_eqv_here && src_eqv_elt)
6470 if (elt->first_same_value != src_eqv_elt->first_same_value)
6472 /* The REG_EQUAL is indicating that two formerly distinct
6473 classes are now equivalent. So merge them. */
6474 merge_equiv_classes (elt, src_eqv_elt);
6475 src_eqv_hash = HASH (src_eqv, elt->mode);
6476 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
6482 else if (src_eqv_elt)
6485 /* Try to find a constant somewhere and record it in `src_const'.
6486 Record its table element, if any, in `src_const_elt'. Look in
6487 any known equivalences first. (If the constant is not in the
6488 table, also set `sets[i].src_const_hash'). */
6490 for (p = elt->first_same_value; p; p = p->next_same_value)
6494 src_const_elt = elt;
6499 && (CONSTANT_P (src_folded)
6500 /* Consider (minus (label_ref L1) (label_ref L2)) as
6501 "constant" here so we will record it. This allows us
6502 to fold switch statements when an ADDR_DIFF_VEC is used. */
6503 || (GET_CODE (src_folded) == MINUS
6504 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
6505 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
6506 src_const = src_folded, src_const_elt = elt;
6507 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
6508 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
6510 /* If we don't know if the constant is in the table, get its
6511 hash code and look it up. */
6512 if (src_const && src_const_elt == 0)
6514 sets[i].src_const_hash = HASH (src_const, mode);
6515 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
6518 sets[i].src_const = src_const;
6519 sets[i].src_const_elt = src_const_elt;
6521 /* If the constant and our source are both in the table, mark them as
6522 equivalent. Otherwise, if a constant is in the table but the source
6523 isn't, set ELT to it. */
6524 if (src_const_elt && elt
6525 && src_const_elt->first_same_value != elt->first_same_value)
6526 merge_equiv_classes (elt, src_const_elt);
6527 else if (src_const_elt && elt == 0)
6528 elt = src_const_elt;
6530 /* See if there is a register linearly related to a constant
6531 equivalent of SRC. */
6533 && (GET_CODE (src_const) == CONST
6534 || (src_const_elt && src_const_elt->related_value != 0)))
6536 src_related = use_related_value (src_const, src_const_elt);
6539 struct table_elt *src_related_elt
6540 = lookup (src_related, HASH (src_related, mode), mode);
6541 if (src_related_elt && elt)
6543 if (elt->first_same_value
6544 != src_related_elt->first_same_value)
6545 /* This can occur when we previously saw a CONST
6546 involving a SYMBOL_REF and then see the SYMBOL_REF
6547 twice. Merge the involved classes. */
6548 merge_equiv_classes (elt, src_related_elt);
6551 src_related_elt = 0;
6553 else if (src_related_elt && elt == 0)
6554 elt = src_related_elt;
6558 /* See if we have a CONST_INT that is already in a register in a
6561 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
6562 && GET_MODE_CLASS (mode) == MODE_INT
6563 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
6565 enum machine_mode wider_mode;
6567 for (wider_mode = GET_MODE_WIDER_MODE (mode);
6568 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
6569 && src_related == 0;
6570 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
6572 struct table_elt *const_elt
6573 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
6578 for (const_elt = const_elt->first_same_value;
6579 const_elt; const_elt = const_elt->next_same_value)
6580 if (GET_CODE (const_elt->exp) == REG)
6582 src_related = gen_lowpart_if_possible (mode,
6589 /* Another possibility is that we have an AND with a constant in
6590 a mode narrower than a word. If so, it might have been generated
6591 as part of an "if" which would narrow the AND. If we already
6592 have done the AND in a wider mode, we can use a SUBREG of that
6595 if (flag_expensive_optimizations && ! src_related
6596 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
6597 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
6599 enum machine_mode tmode;
6600 rtx new_and = gen_rtx (AND, VOIDmode, NULL_RTX, XEXP (src, 1));
6602 for (tmode = GET_MODE_WIDER_MODE (mode);
6603 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
6604 tmode = GET_MODE_WIDER_MODE (tmode))
6606 rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0));
6607 struct table_elt *larger_elt;
6611 PUT_MODE (new_and, tmode);
6612 XEXP (new_and, 0) = inner;
6613 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
6614 if (larger_elt == 0)
6617 for (larger_elt = larger_elt->first_same_value;
6618 larger_elt; larger_elt = larger_elt->next_same_value)
6619 if (GET_CODE (larger_elt->exp) == REG)
6622 = gen_lowpart_if_possible (mode, larger_elt->exp);
6632 #ifdef LOAD_EXTEND_OP
6633 /* See if a MEM has already been loaded with a widening operation;
6634 if it has, we can use a subreg of that. Many CISC machines
6635 also have such operations, but this is only likely to be
6636 beneficial these machines. */
6638 if (flag_expensive_optimizations && src_related == 0
6639 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
6640 && GET_MODE_CLASS (mode) == MODE_INT
6641 && GET_CODE (src) == MEM && ! do_not_record
6642 && LOAD_EXTEND_OP (mode) != NIL)
6644 enum machine_mode tmode;
6646 /* Set what we are trying to extend and the operation it might
6647 have been extended with. */
6648 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
6649 XEXP (memory_extend_rtx, 0) = src;
6651 for (tmode = GET_MODE_WIDER_MODE (mode);
6652 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
6653 tmode = GET_MODE_WIDER_MODE (tmode))
6655 struct table_elt *larger_elt;
6657 PUT_MODE (memory_extend_rtx, tmode);
6658 larger_elt = lookup (memory_extend_rtx,
6659 HASH (memory_extend_rtx, tmode), tmode);
6660 if (larger_elt == 0)
6663 for (larger_elt = larger_elt->first_same_value;
6664 larger_elt; larger_elt = larger_elt->next_same_value)
6665 if (GET_CODE (larger_elt->exp) == REG)
6667 src_related = gen_lowpart_if_possible (mode,
6676 #endif /* LOAD_EXTEND_OP */
6678 if (src == src_folded)
6681 /* At this point, ELT, if non-zero, points to a class of expressions
6682 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
6683 and SRC_RELATED, if non-zero, each contain additional equivalent
6684 expressions. Prune these latter expressions by deleting expressions
6685 already in the equivalence class.
6687 Check for an equivalent identical to the destination. If found,
6688 this is the preferred equivalent since it will likely lead to
6689 elimination of the insn. Indicate this by placing it in
6692 if (elt) elt = elt->first_same_value;
6693 for (p = elt; p; p = p->next_same_value)
6695 enum rtx_code code = GET_CODE (p->exp);
6697 /* If the expression is not valid, ignore it. Then we do not
6698 have to check for validity below. In most cases, we can use
6699 `rtx_equal_p', since canonicalization has already been done. */
6700 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
6703 /* Also skip paradoxical subregs, unless that's what we're
6706 && (GET_MODE_SIZE (GET_MODE (p->exp))
6707 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
6709 && GET_CODE (src) == SUBREG
6710 && GET_MODE (src) == GET_MODE (p->exp)
6711 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
6712 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
6715 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
6717 else if (src_folded && GET_CODE (src_folded) == code
6718 && rtx_equal_p (src_folded, p->exp))
6720 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
6721 && rtx_equal_p (src_eqv_here, p->exp))
6723 else if (src_related && GET_CODE (src_related) == code
6724 && rtx_equal_p (src_related, p->exp))
6727 /* This is the same as the destination of the insns, we want
6728 to prefer it. Copy it to src_related. The code below will
6729 then give it a negative cost. */
6730 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
6735 /* Find the cheapest valid equivalent, trying all the available
6736 possibilities. Prefer items not in the hash table to ones
6737 that are when they are equal cost. Note that we can never
6738 worsen an insn as the current contents will also succeed.
6739 If we find an equivalent identical to the destination, use it as best,
6740 since this insn will probably be eliminated in that case. */
6743 if (rtx_equal_p (src, dest))
6746 src_cost = COST (src);
6751 if (rtx_equal_p (src_eqv_here, dest))
6754 src_eqv_cost = COST (src_eqv_here);
6759 if (rtx_equal_p (src_folded, dest))
6760 src_folded_cost = -1;
6762 src_folded_cost = COST (src_folded);
6767 if (rtx_equal_p (src_related, dest))
6768 src_related_cost = -1;
6770 src_related_cost = COST (src_related);
6773 /* If this was an indirect jump insn, a known label will really be
6774 cheaper even though it looks more expensive. */
6775 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
6776 src_folded = src_const, src_folded_cost = -1;
6778 /* Terminate loop when replacement made. This must terminate since
6779 the current contents will be tested and will always be valid. */
6784 /* Skip invalid entries. */
6785 while (elt && GET_CODE (elt->exp) != REG
6786 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
6787 elt = elt->next_same_value;
6789 /* A paradoxical subreg would be bad here: it'll be the right
6790 size, but later may be adjusted so that the upper bits aren't
6791 what we want. So reject it. */
6793 && GET_CODE (elt->exp) == SUBREG
6794 && (GET_MODE_SIZE (GET_MODE (elt->exp))
6795 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
6796 /* It is okay, though, if the rtx we're trying to match
6797 will ignore any of the bits we can't predict. */
6799 && GET_CODE (src) == SUBREG
6800 && GET_MODE (src) == GET_MODE (elt->exp)
6801 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
6802 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
6804 elt = elt->next_same_value;
6808 if (elt) src_elt_cost = elt->cost;
6810 /* Find cheapest and skip it for the next time. For items
6811 of equal cost, use this order:
6812 src_folded, src, src_eqv, src_related and hash table entry. */
6813 if (src_folded_cost <= src_cost
6814 && src_folded_cost <= src_eqv_cost
6815 && src_folded_cost <= src_related_cost
6816 && src_folded_cost <= src_elt_cost)
6818 trial = src_folded, src_folded_cost = 10000;
6819 if (src_folded_force_flag)
6820 trial = force_const_mem (mode, trial);
6822 else if (src_cost <= src_eqv_cost
6823 && src_cost <= src_related_cost
6824 && src_cost <= src_elt_cost)
6825 trial = src, src_cost = 10000;
6826 else if (src_eqv_cost <= src_related_cost
6827 && src_eqv_cost <= src_elt_cost)
6828 trial = copy_rtx (src_eqv_here), src_eqv_cost = 10000;
6829 else if (src_related_cost <= src_elt_cost)
6830 trial = copy_rtx (src_related), src_related_cost = 10000;
6833 trial = copy_rtx (elt->exp);
6834 elt = elt->next_same_value;
6835 src_elt_cost = 10000;
6838 /* We don't normally have an insn matching (set (pc) (pc)), so
6839 check for this separately here. We will delete such an
6842 Tablejump insns contain a USE of the table, so simply replacing
6843 the operand with the constant won't match. This is simply an
6844 unconditional branch, however, and is therefore valid. Just
6845 insert the substitution here and we will delete and re-emit
6848 if (n_sets == 1 && dest == pc_rtx
6850 || (GET_CODE (trial) == LABEL_REF
6851 && ! condjump_p (insn))))
6853 /* If TRIAL is a label in front of a jump table, we are
6854 really falling through the switch (this is how casesi
6855 insns work), so we must branch around the table. */
6856 if (GET_CODE (trial) == CODE_LABEL
6857 && NEXT_INSN (trial) != 0
6858 && GET_CODE (NEXT_INSN (trial)) == JUMP_INSN
6859 && (GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_DIFF_VEC
6860 || GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_VEC))
6862 trial = gen_rtx (LABEL_REF, Pmode, get_label_after (trial));
6864 SET_SRC (sets[i].rtl) = trial;
6865 cse_jumps_altered = 1;
6869 /* Look for a substitution that makes a valid insn. */
6870 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
6872 /* The result of apply_change_group can be ignored; see
6875 validate_change (insn, &SET_SRC (sets[i].rtl),
6876 canon_reg (SET_SRC (sets[i].rtl), insn),
6878 apply_change_group ();
6882 /* If we previously found constant pool entries for
6883 constants and this is a constant, try making a
6884 pool entry. Put it in src_folded unless we already have done
6885 this since that is where it likely came from. */
6887 else if (constant_pool_entries_cost
6888 && CONSTANT_P (trial)
6889 && ! (GET_CODE (trial) == CONST
6890 && GET_CODE (XEXP (trial, 0)) == TRUNCATE)
6892 || (GET_CODE (src_folded) != MEM
6893 && ! src_folded_force_flag))
6894 && GET_MODE_CLASS (mode) != MODE_CC
6895 && mode != VOIDmode)
6897 src_folded_force_flag = 1;
6899 src_folded_cost = constant_pool_entries_cost;
6903 src = SET_SRC (sets[i].rtl);
6905 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
6906 However, there is an important exception: If both are registers
6907 that are not the head of their equivalence class, replace SET_SRC
6908 with the head of the class. If we do not do this, we will have
6909 both registers live over a portion of the basic block. This way,
6910 their lifetimes will likely abut instead of overlapping. */
6911 if (GET_CODE (dest) == REG
6912 && REGNO_QTY_VALID_P (REGNO (dest))
6913 && qty_mode[reg_qty[REGNO (dest)]] == GET_MODE (dest)
6914 && qty_first_reg[reg_qty[REGNO (dest)]] != REGNO (dest)
6915 && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
6916 /* Don't do this if the original insn had a hard reg as
6918 && (GET_CODE (sets[i].src) != REG
6919 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER))
6920 /* We can't call canon_reg here because it won't do anything if
6921 SRC is a hard register. */
6923 int first = qty_first_reg[reg_qty[REGNO (src)]];
6925 src = SET_SRC (sets[i].rtl)
6926 = first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
6927 : gen_rtx (REG, GET_MODE (src), first);
6929 /* If we had a constant that is cheaper than what we are now
6930 setting SRC to, use that constant. We ignored it when we
6931 thought we could make this into a no-op. */
6932 if (src_const && COST (src_const) < COST (src)
6933 && validate_change (insn, &SET_SRC (sets[i].rtl), src_const, 0))
6937 /* If we made a change, recompute SRC values. */
6938 if (src != sets[i].src)
6941 hash_arg_in_memory = 0;
6942 hash_arg_in_struct = 0;
6944 sets[i].src_hash = HASH (src, mode);
6945 sets[i].src_volatile = do_not_record;
6946 sets[i].src_in_memory = hash_arg_in_memory;
6947 sets[i].src_in_struct = hash_arg_in_struct;
6948 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
6951 /* If this is a single SET, we are setting a register, and we have an
6952 equivalent constant, we want to add a REG_NOTE. We don't want
6953 to write a REG_EQUAL note for a constant pseudo since verifying that
6954 that pseudo hasn't been eliminated is a pain. Such a note also
6955 won't help anything. */
6956 if (n_sets == 1 && src_const && GET_CODE (dest) == REG
6957 && GET_CODE (src_const) != REG)
6959 tem = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6961 /* Record the actual constant value in a REG_EQUAL note, making
6962 a new one if one does not already exist. */
6964 XEXP (tem, 0) = src_const;
6966 REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUAL,
6967 src_const, REG_NOTES (insn));
6969 /* If storing a constant value in a register that
6970 previously held the constant value 0,
6971 record this fact with a REG_WAS_0 note on this insn.
6973 Note that the *register* is required to have previously held 0,
6974 not just any register in the quantity and we must point to the
6975 insn that set that register to zero.
6977 Rather than track each register individually, we just see if
6978 the last set for this quantity was for this register. */
6980 if (REGNO_QTY_VALID_P (REGNO (dest))
6981 && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
6983 /* See if we previously had a REG_WAS_0 note. */
6984 rtx note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
6985 rtx const_insn = qty_const_insn[reg_qty[REGNO (dest)]];
6987 if ((tem = single_set (const_insn)) != 0
6988 && rtx_equal_p (SET_DEST (tem), dest))
6991 XEXP (note, 0) = const_insn;
6993 REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0,
6994 const_insn, REG_NOTES (insn));
6999 /* Now deal with the destination. */
7001 sets[i].inner_dest_loc = &SET_DEST (sets[0].rtl);
7003 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
7004 to the MEM or REG within it. */
7005 while (GET_CODE (dest) == SIGN_EXTRACT
7006 || GET_CODE (dest) == ZERO_EXTRACT
7007 || GET_CODE (dest) == SUBREG
7008 || GET_CODE (dest) == STRICT_LOW_PART)
7010 sets[i].inner_dest_loc = &XEXP (dest, 0);
7011 dest = XEXP (dest, 0);
7014 sets[i].inner_dest = dest;
7016 if (GET_CODE (dest) == MEM)
7018 #ifdef PUSH_ROUNDING
7019 /* Stack pushes invalidate the stack pointer. */
7020 rtx addr = XEXP (dest, 0);
7021 if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
7022 || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
7023 && XEXP (addr, 0) == stack_pointer_rtx)
7024 invalidate (stack_pointer_rtx, Pmode);
7026 dest = fold_rtx (dest, insn);
7029 /* Compute the hash code of the destination now,
7030 before the effects of this instruction are recorded,
7031 since the register values used in the address computation
7032 are those before this instruction. */
7033 sets[i].dest_hash = HASH (dest, mode);
7035 /* Don't enter a bit-field in the hash table
7036 because the value in it after the store
7037 may not equal what was stored, due to truncation. */
7039 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
7040 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
7042 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
7044 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
7045 && GET_CODE (width) == CONST_INT
7046 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
7047 && ! (INTVAL (src_const)
7048 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
7049 /* Exception: if the value is constant,
7050 and it won't be truncated, record it. */
7054 /* This is chosen so that the destination will be invalidated
7055 but no new value will be recorded.
7056 We must invalidate because sometimes constant
7057 values can be recorded for bitfields. */
7058 sets[i].src_elt = 0;
7059 sets[i].src_volatile = 1;
7065 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
7067 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
7069 PUT_CODE (insn, NOTE);
7070 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
7071 NOTE_SOURCE_FILE (insn) = 0;
7072 cse_jumps_altered = 1;
7073 /* One less use of the label this insn used to jump to. */
7074 if (JUMP_LABEL (insn) != 0)
7075 --LABEL_NUSES (JUMP_LABEL (insn));
7076 /* No more processing for this set. */
7080 /* If this SET is now setting PC to a label, we know it used to
7081 be a conditional or computed branch. So we see if we can follow
7082 it. If it was a computed branch, delete it and re-emit. */
7083 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
7087 /* If this is not in the format for a simple branch and
7088 we are the only SET in it, re-emit it. */
7089 if (! simplejump_p (insn) && n_sets == 1)
7091 rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
7092 JUMP_LABEL (new) = XEXP (src, 0);
7093 LABEL_NUSES (XEXP (src, 0))++;
7098 /* Otherwise, force rerecognition, since it probably had
7099 a different pattern before.
7100 This shouldn't really be necessary, since whatever
7101 changed the source value above should have done this.
7102 Until the right place is found, might as well do this here. */
7103 INSN_CODE (insn) = -1;
7105 /* Now that we've converted this jump to an unconditional jump,
7106 there is dead code after it. Delete the dead code until we
7107 reach a BARRIER, the end of the function, or a label. Do
7108 not delete NOTEs except for NOTE_INSN_DELETED since later
7109 phases assume these notes are retained. */
7113 while (NEXT_INSN (p) != 0
7114 && GET_CODE (NEXT_INSN (p)) != BARRIER
7115 && GET_CODE (NEXT_INSN (p)) != CODE_LABEL)
7117 if (GET_CODE (NEXT_INSN (p)) != NOTE
7118 || NOTE_LINE_NUMBER (NEXT_INSN (p)) == NOTE_INSN_DELETED)
7119 delete_insn (NEXT_INSN (p));
7124 /* If we don't have a BARRIER immediately after INSN, put one there.
7125 Much code assumes that there are no NOTEs between a JUMP_INSN and
7128 if (NEXT_INSN (insn) == 0
7129 || GET_CODE (NEXT_INSN (insn)) != BARRIER)
7130 emit_barrier_before (NEXT_INSN (insn));
7132 /* We might have two BARRIERs separated by notes. Delete the second
7135 if (p != insn && NEXT_INSN (p) != 0
7136 && GET_CODE (NEXT_INSN (p)) == BARRIER)
7137 delete_insn (NEXT_INSN (p));
7139 cse_jumps_altered = 1;
7143 /* If destination is volatile, invalidate it and then do no further
7144 processing for this assignment. */
7146 else if (do_not_record)
7148 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
7149 || GET_CODE (dest) == MEM)
7150 invalidate (dest, VOIDmode);
7151 else if (GET_CODE (dest) == STRICT_LOW_PART
7152 || GET_CODE (dest) == ZERO_EXTRACT)
7153 invalidate (XEXP (dest, 0), GET_MODE (dest));
7157 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
7158 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
7161 /* If setting CC0, record what it was set to, or a constant, if it
7162 is equivalent to a constant. If it is being set to a floating-point
7163 value, make a COMPARE with the appropriate constant of 0. If we
7164 don't do this, later code can interpret this as a test against
7165 const0_rtx, which can cause problems if we try to put it into an
7166 insn as a floating-point operand. */
7167 if (dest == cc0_rtx)
7169 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
7170 this_insn_cc0_mode = mode;
7171 if (FLOAT_MODE_P (mode))
7172 this_insn_cc0 = gen_rtx (COMPARE, VOIDmode, this_insn_cc0,
7178 /* Now enter all non-volatile source expressions in the hash table
7179 if they are not already present.
7180 Record their equivalence classes in src_elt.
7181 This way we can insert the corresponding destinations into
7182 the same classes even if the actual sources are no longer in them
7183 (having been invalidated). */
7185 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
7186 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
7188 register struct table_elt *elt;
7189 register struct table_elt *classp = sets[0].src_elt;
7190 rtx dest = SET_DEST (sets[0].rtl);
7191 enum machine_mode eqvmode = GET_MODE (dest);
7193 if (GET_CODE (dest) == STRICT_LOW_PART)
7195 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
7198 if (insert_regs (src_eqv, classp, 0))
7200 rehash_using_reg (src_eqv);
7201 src_eqv_hash = HASH (src_eqv, eqvmode);
7203 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
7204 elt->in_memory = src_eqv_in_memory;
7205 elt->in_struct = src_eqv_in_struct;
7208 /* Check to see if src_eqv_elt is the same as a set source which
7209 does not yet have an elt, and if so set the elt of the set source
7211 for (i = 0; i < n_sets; i++)
7212 if (sets[i].rtl && sets[i].src_elt == 0
7213 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
7214 sets[i].src_elt = src_eqv_elt;
7217 for (i = 0; i < n_sets; i++)
7218 if (sets[i].rtl && ! sets[i].src_volatile
7219 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
7221 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
7223 /* REG_EQUAL in setting a STRICT_LOW_PART
7224 gives an equivalent for the entire destination register,
7225 not just for the subreg being stored in now.
7226 This is a more interesting equivalence, so we arrange later
7227 to treat the entire reg as the destination. */
7228 sets[i].src_elt = src_eqv_elt;
7229 sets[i].src_hash = src_eqv_hash;
7233 /* Insert source and constant equivalent into hash table, if not
7235 register struct table_elt *classp = src_eqv_elt;
7236 register rtx src = sets[i].src;
7237 register rtx dest = SET_DEST (sets[i].rtl);
7238 enum machine_mode mode
7239 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
7241 if (sets[i].src_elt == 0)
7243 register struct table_elt *elt;
7245 /* Note that these insert_regs calls cannot remove
7246 any of the src_elt's, because they would have failed to
7247 match if not still valid. */
7248 if (insert_regs (src, classp, 0))
7250 rehash_using_reg (src);
7251 sets[i].src_hash = HASH (src, mode);
7253 elt = insert (src, classp, sets[i].src_hash, mode);
7254 elt->in_memory = sets[i].src_in_memory;
7255 elt->in_struct = sets[i].src_in_struct;
7256 sets[i].src_elt = classp = elt;
7259 if (sets[i].src_const && sets[i].src_const_elt == 0
7260 && src != sets[i].src_const
7261 && ! rtx_equal_p (sets[i].src_const, src))
7262 sets[i].src_elt = insert (sets[i].src_const, classp,
7263 sets[i].src_const_hash, mode);
7266 else if (sets[i].src_elt == 0)
7267 /* If we did not insert the source into the hash table (e.g., it was
7268 volatile), note the equivalence class for the REG_EQUAL value, if any,
7269 so that the destination goes into that class. */
7270 sets[i].src_elt = src_eqv_elt;
7272 invalidate_from_clobbers (x);
7274 /* Some registers are invalidated by subroutine calls. Memory is
7275 invalidated by non-constant calls. */
7277 if (GET_CODE (insn) == CALL_INSN)
7279 if (! CONST_CALL_P (insn))
7280 invalidate_memory ();
7281 invalidate_for_call ();
7284 /* Now invalidate everything set by this instruction.
7285 If a SUBREG or other funny destination is being set,
7286 sets[i].rtl is still nonzero, so here we invalidate the reg
7287 a part of which is being set. */
7289 for (i = 0; i < n_sets; i++)
7292 /* We can't use the inner dest, because the mode associated with
7293 a ZERO_EXTRACT is significant. */
7294 register rtx dest = SET_DEST (sets[i].rtl);
7296 /* Needed for registers to remove the register from its
7297 previous quantity's chain.
7298 Needed for memory if this is a nonvarying address, unless
7299 we have just done an invalidate_memory that covers even those. */
7300 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
7301 || GET_CODE (dest) == MEM)
7302 invalidate (dest, VOIDmode);
7303 else if (GET_CODE (dest) == STRICT_LOW_PART
7304 || GET_CODE (dest) == ZERO_EXTRACT)
7305 invalidate (XEXP (dest, 0), GET_MODE (dest));
7308 /* Make sure registers mentioned in destinations
7309 are safe for use in an expression to be inserted.
7310 This removes from the hash table
7311 any invalid entry that refers to one of these registers.
7313 We don't care about the return value from mention_regs because
7314 we are going to hash the SET_DEST values unconditionally. */
7316 for (i = 0; i < n_sets; i++)
7317 if (sets[i].rtl && GET_CODE (SET_DEST (sets[i].rtl)) != REG)
7318 mention_regs (SET_DEST (sets[i].rtl));
7320 /* We may have just removed some of the src_elt's from the hash table.
7321 So replace each one with the current head of the same class. */
7323 for (i = 0; i < n_sets; i++)
7326 if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
7327 /* If elt was removed, find current head of same class,
7328 or 0 if nothing remains of that class. */
7330 register struct table_elt *elt = sets[i].src_elt;
7332 while (elt && elt->prev_same_value)
7333 elt = elt->prev_same_value;
7335 while (elt && elt->first_same_value == 0)
7336 elt = elt->next_same_value;
7337 sets[i].src_elt = elt ? elt->first_same_value : 0;
7341 /* Now insert the destinations into their equivalence classes. */
7343 for (i = 0; i < n_sets; i++)
7346 register rtx dest = SET_DEST (sets[i].rtl);
7347 register struct table_elt *elt;
7349 /* Don't record value if we are not supposed to risk allocating
7350 floating-point values in registers that might be wider than
7352 if ((flag_float_store
7353 && GET_CODE (dest) == MEM
7354 && FLOAT_MODE_P (GET_MODE (dest)))
7355 /* Don't record BLKmode values, because we don't know the
7356 size of it, and can't be sure that other BLKmode values
7357 have the same or smaller size. */
7358 || GET_MODE (dest) == BLKmode
7359 /* Don't record values of destinations set inside a libcall block
7360 since we might delete the libcall. Things should have been set
7361 up so we won't want to reuse such a value, but we play it safe
7364 /* If we didn't put a REG_EQUAL value or a source into the hash
7365 table, there is no point is recording DEST. */
7366 || sets[i].src_elt == 0
7367 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
7368 or SIGN_EXTEND, don't record DEST since it can cause
7369 some tracking to be wrong.
7371 ??? Think about this more later. */
7372 || (GET_CODE (dest) == SUBREG
7373 && (GET_MODE_SIZE (GET_MODE (dest))
7374 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
7375 && (GET_CODE (sets[i].src) == SIGN_EXTEND
7376 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
7379 /* STRICT_LOW_PART isn't part of the value BEING set,
7380 and neither is the SUBREG inside it.
7381 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
7382 if (GET_CODE (dest) == STRICT_LOW_PART)
7383 dest = SUBREG_REG (XEXP (dest, 0));
7385 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
7386 /* Registers must also be inserted into chains for quantities. */
7387 if (insert_regs (dest, sets[i].src_elt, 1))
7389 /* If `insert_regs' changes something, the hash code must be
7391 rehash_using_reg (dest);
7392 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
7395 elt = insert (dest, sets[i].src_elt,
7396 sets[i].dest_hash, GET_MODE (dest));
7397 elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM
7398 && (! RTX_UNCHANGING_P (sets[i].inner_dest)
7399 || FIXED_BASE_PLUS_P (XEXP (sets[i].inner_dest,
7404 /* This implicitly assumes a whole struct
7405 need not have MEM_IN_STRUCT_P.
7406 But a whole struct is *supposed* to have MEM_IN_STRUCT_P. */
7407 elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest)
7408 || sets[i].inner_dest != SET_DEST (sets[i].rtl));
7411 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
7412 narrower than M2, and both M1 and M2 are the same number of words,
7413 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
7414 make that equivalence as well.
7416 However, BAR may have equivalences for which gen_lowpart_if_possible
7417 will produce a simpler value than gen_lowpart_if_possible applied to
7418 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
7419 BAR's equivalences. If we don't get a simplified form, make
7420 the SUBREG. It will not be used in an equivalence, but will
7421 cause two similar assignments to be detected.
7423 Note the loop below will find SUBREG_REG (DEST) since we have
7424 already entered SRC and DEST of the SET in the table. */
7426 if (GET_CODE (dest) == SUBREG
7427 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
7429 == (GET_MODE_SIZE (GET_MODE (dest)) - 1)/ UNITS_PER_WORD)
7430 && (GET_MODE_SIZE (GET_MODE (dest))
7431 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
7432 && sets[i].src_elt != 0)
7434 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
7435 struct table_elt *elt, *classp = 0;
7437 for (elt = sets[i].src_elt->first_same_value; elt;
7438 elt = elt->next_same_value)
7442 struct table_elt *src_elt;
7444 /* Ignore invalid entries. */
7445 if (GET_CODE (elt->exp) != REG
7446 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
7449 new_src = gen_lowpart_if_possible (new_mode, elt->exp);
7451 new_src = gen_rtx (SUBREG, new_mode, elt->exp, 0);
7453 src_hash = HASH (new_src, new_mode);
7454 src_elt = lookup (new_src, src_hash, new_mode);
7456 /* Put the new source in the hash table is if isn't
7460 if (insert_regs (new_src, classp, 0))
7462 rehash_using_reg (new_src);
7463 src_hash = HASH (new_src, new_mode);
7465 src_elt = insert (new_src, classp, src_hash, new_mode);
7466 src_elt->in_memory = elt->in_memory;
7467 src_elt->in_struct = elt->in_struct;
7469 else if (classp && classp != src_elt->first_same_value)
7470 /* Show that two things that we've seen before are
7471 actually the same. */
7472 merge_equiv_classes (src_elt, classp);
7474 classp = src_elt->first_same_value;
7475 /* Ignore invalid entries. */
7477 && GET_CODE (classp->exp) != REG
7478 && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
7479 classp = classp->next_same_value;
7484 /* Special handling for (set REG0 REG1)
7485 where REG0 is the "cheapest", cheaper than REG1.
7486 After cse, REG1 will probably not be used in the sequel,
7487 so (if easily done) change this insn to (set REG1 REG0) and
7488 replace REG1 with REG0 in the previous insn that computed their value.
7489 Then REG1 will become a dead store and won't cloud the situation
7490 for later optimizations.
7492 Do not make this change if REG1 is a hard register, because it will
7493 then be used in the sequel and we may be changing a two-operand insn
7494 into a three-operand insn.
7496 Also do not do this if we are operating on a copy of INSN. */
7498 if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
7499 && NEXT_INSN (PREV_INSN (insn)) == insn
7500 && GET_CODE (SET_SRC (sets[0].rtl)) == REG
7501 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
7502 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl)))
7503 && (qty_first_reg[reg_qty[REGNO (SET_SRC (sets[0].rtl))]]
7504 == REGNO (SET_DEST (sets[0].rtl))))
7506 rtx prev = PREV_INSN (insn);
7507 while (prev && GET_CODE (prev) == NOTE)
7508 prev = PREV_INSN (prev);
7510 if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
7511 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
7513 rtx dest = SET_DEST (sets[0].rtl);
7514 rtx note = find_reg_note (prev, REG_EQUIV, NULL_RTX);
7516 validate_change (prev, & SET_DEST (PATTERN (prev)), dest, 1);
7517 validate_change (insn, & SET_DEST (sets[0].rtl),
7518 SET_SRC (sets[0].rtl), 1);
7519 validate_change (insn, & SET_SRC (sets[0].rtl), dest, 1);
7520 apply_change_group ();
7522 /* If REG1 was equivalent to a constant, REG0 is not. */
7524 PUT_REG_NOTE_KIND (note, REG_EQUAL);
7526 /* If there was a REG_WAS_0 note on PREV, remove it. Move
7527 any REG_WAS_0 note on INSN to PREV. */
7528 note = find_reg_note (prev, REG_WAS_0, NULL_RTX);
7530 remove_note (prev, note);
7532 note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
7535 remove_note (insn, note);
7536 XEXP (note, 1) = REG_NOTES (prev);
7537 REG_NOTES (prev) = note;
7540 /* If INSN has a REG_EQUAL note, and this note mentions REG0,
7541 then we must delete it, because the value in REG0 has changed. */
7542 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
7543 if (note && reg_mentioned_p (dest, XEXP (note, 0)))
7544 remove_note (insn, note);
7548 /* If this is a conditional jump insn, record any known equivalences due to
7549 the condition being tested. */
7551 last_jump_equiv_class = 0;
7552 if (GET_CODE (insn) == JUMP_INSN
7553 && n_sets == 1 && GET_CODE (x) == SET
7554 && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
7555 record_jump_equiv (insn, 0);
7558 /* If the previous insn set CC0 and this insn no longer references CC0,
7559 delete the previous insn. Here we use the fact that nothing expects CC0
7560 to be valid over an insn, which is true until the final pass. */
7561 if (prev_insn && GET_CODE (prev_insn) == INSN
7562 && (tem = single_set (prev_insn)) != 0
7563 && SET_DEST (tem) == cc0_rtx
7564 && ! reg_mentioned_p (cc0_rtx, x))
7566 PUT_CODE (prev_insn, NOTE);
7567 NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
7568 NOTE_SOURCE_FILE (prev_insn) = 0;
7571 prev_insn_cc0 = this_insn_cc0;
7572 prev_insn_cc0_mode = this_insn_cc0_mode;
7578 /* Remove from the ahsh table all expressions that reference memory. */
7580 invalidate_memory ()
7583 register struct table_elt *p, *next;
7585 for (i = 0; i < NBUCKETS; i++)
7586 for (p = table[i]; p; p = next)
7588 next = p->next_same_hash;
7590 remove_from_table (p, i);
7594 /* XXX ??? The name of this function bears little resemblance to
7595 what this function actually does. FIXME. */
7597 note_mem_written (addr)
7600 /* Pushing or popping the stack invalidates just the stack pointer. */
7601 if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
7602 || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
7603 && GET_CODE (XEXP (addr, 0)) == REG
7604 && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
7606 if (reg_tick[STACK_POINTER_REGNUM] >= 0)
7607 reg_tick[STACK_POINTER_REGNUM]++;
7609 /* This should be *very* rare. */
7610 if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
7611 invalidate (stack_pointer_rtx, VOIDmode);
7617 /* Perform invalidation on the basis of everything about an insn
7618 except for invalidating the actual places that are SET in it.
7619 This includes the places CLOBBERed, and anything that might
7620 alias with something that is SET or CLOBBERed.
7622 X is the pattern of the insn. */
7625 invalidate_from_clobbers (x)
7628 if (GET_CODE (x) == CLOBBER)
7630 rtx ref = XEXP (x, 0);
7633 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
7634 || GET_CODE (ref) == MEM)
7635 invalidate (ref, VOIDmode);
7636 else if (GET_CODE (ref) == STRICT_LOW_PART
7637 || GET_CODE (ref) == ZERO_EXTRACT)
7638 invalidate (XEXP (ref, 0), GET_MODE (ref));
7641 else if (GET_CODE (x) == PARALLEL)
7644 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
7646 register rtx y = XVECEXP (x, 0, i);
7647 if (GET_CODE (y) == CLOBBER)
7649 rtx ref = XEXP (y, 0);
7650 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
7651 || GET_CODE (ref) == MEM)
7652 invalidate (ref, VOIDmode);
7653 else if (GET_CODE (ref) == STRICT_LOW_PART
7654 || GET_CODE (ref) == ZERO_EXTRACT)
7655 invalidate (XEXP (ref, 0), GET_MODE (ref));
7661 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
7662 and replace any registers in them with either an equivalent constant
7663 or the canonical form of the register. If we are inside an address,
7664 only do this if the address remains valid.
7666 OBJECT is 0 except when within a MEM in which case it is the MEM.
7668 Return the replacement for X. */
7671 cse_process_notes (x, object)
7675 enum rtx_code code = GET_CODE (x);
7676 char *fmt = GET_RTX_FORMAT (code);
7692 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), x);
7697 if (REG_NOTE_KIND (x) == REG_EQUAL)
7698 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
7700 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
7707 rtx new = cse_process_notes (XEXP (x, 0), object);
7708 /* We don't substitute VOIDmode constants into these rtx,
7709 since they would impede folding. */
7710 if (GET_MODE (new) != VOIDmode)
7711 validate_change (object, &XEXP (x, 0), new, 0);
7716 i = reg_qty[REGNO (x)];
7718 /* Return a constant or a constant register. */
7719 if (REGNO_QTY_VALID_P (REGNO (x))
7720 && qty_const[i] != 0
7721 && (CONSTANT_P (qty_const[i])
7722 || GET_CODE (qty_const[i]) == REG))
7724 rtx new = gen_lowpart_if_possible (GET_MODE (x), qty_const[i]);
7729 /* Otherwise, canonicalize this register. */
7730 return canon_reg (x, NULL_RTX);
7736 for (i = 0; i < GET_RTX_LENGTH (code); i++)
7738 validate_change (object, &XEXP (x, i),
7739 cse_process_notes (XEXP (x, i), object), 0);
7744 /* Find common subexpressions between the end test of a loop and the beginning
7745 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
7747 Often we have a loop where an expression in the exit test is used
7748 in the body of the loop. For example "while (*p) *q++ = *p++;".
7749 Because of the way we duplicate the loop exit test in front of the loop,
7750 however, we don't detect that common subexpression. This will be caught
7751 when global cse is implemented, but this is a quite common case.
7753 This function handles the most common cases of these common expressions.
7754 It is called after we have processed the basic block ending with the
7755 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
7756 jumps to a label used only once. */
7759 cse_around_loop (loop_start)
7764 struct table_elt *p;
7766 /* If the jump at the end of the loop doesn't go to the start, we don't
7768 for (insn = PREV_INSN (loop_start);
7769 insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
7770 insn = PREV_INSN (insn))
7774 || GET_CODE (insn) != NOTE
7775 || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
7778 /* If the last insn of the loop (the end test) was an NE comparison,
7779 we will interpret it as an EQ comparison, since we fell through
7780 the loop. Any equivalences resulting from that comparison are
7781 therefore not valid and must be invalidated. */
7782 if (last_jump_equiv_class)
7783 for (p = last_jump_equiv_class->first_same_value; p;
7784 p = p->next_same_value)
7785 if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
7786 || (GET_CODE (p->exp) == SUBREG
7787 && GET_CODE (SUBREG_REG (p->exp)) == REG))
7788 invalidate (p->exp, VOIDmode);
7789 else if (GET_CODE (p->exp) == STRICT_LOW_PART
7790 || GET_CODE (p->exp) == ZERO_EXTRACT)
7791 invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
7793 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
7794 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
7796 The only thing we do with SET_DEST is invalidate entries, so we
7797 can safely process each SET in order. It is slightly less efficient
7798 to do so, but we only want to handle the most common cases. */
7800 for (insn = NEXT_INSN (loop_start);
7801 GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
7802 && ! (GET_CODE (insn) == NOTE
7803 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
7804 insn = NEXT_INSN (insn))
7806 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7807 && (GET_CODE (PATTERN (insn)) == SET
7808 || GET_CODE (PATTERN (insn)) == CLOBBER))
7809 cse_set_around_loop (PATTERN (insn), insn, loop_start);
7810 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
7811 && GET_CODE (PATTERN (insn)) == PARALLEL)
7812 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
7813 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
7814 || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
7815 cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
7820 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
7821 since they are done elsewhere. This function is called via note_stores. */
7824 invalidate_skipped_set (dest, set)
7828 enum rtx_code code = GET_CODE (dest);
7831 && ! note_mem_written (dest) /* If this is not a stack push ... */
7832 /* There are times when an address can appear varying and be a PLUS
7833 during this scan when it would be a fixed address were we to know
7834 the proper equivalences. So invalidate all memory if there is
7835 a BLKmode or nonscalar memory reference or a reference to a
7836 variable address. */
7837 && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
7838 || cse_rtx_varies_p (XEXP (dest, 0))))
7840 invalidate_memory ();
7844 if (GET_CODE (set) == CLOBBER
7851 if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
7852 invalidate (XEXP (dest, 0), GET_MODE (dest));
7853 else if (code == REG || code == SUBREG || code == MEM)
7854 invalidate (dest, VOIDmode);
7857 /* Invalidate all insns from START up to the end of the function or the
7858 next label. This called when we wish to CSE around a block that is
7859 conditionally executed. */
7862 invalidate_skipped_block (start)
7867 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
7868 insn = NEXT_INSN (insn))
7870 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
7873 if (GET_CODE (insn) == CALL_INSN)
7875 if (! CONST_CALL_P (insn))
7876 invalidate_memory ();
7877 invalidate_for_call ();
7880 note_stores (PATTERN (insn), invalidate_skipped_set);
7884 /* Used for communication between the following two routines; contains a
7885 value to be checked for modification. */
7887 static rtx cse_check_loop_start_value;
7889 /* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE,
7890 indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0. */
7893 cse_check_loop_start (x, set)
7897 if (cse_check_loop_start_value == 0
7898 || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
7901 if ((GET_CODE (x) == MEM && GET_CODE (cse_check_loop_start_value) == MEM)
7902 || reg_overlap_mentioned_p (x, cse_check_loop_start_value))
7903 cse_check_loop_start_value = 0;
7906 /* X is a SET or CLOBBER contained in INSN that was found near the start of
7907 a loop that starts with the label at LOOP_START.
7909 If X is a SET, we see if its SET_SRC is currently in our hash table.
7910 If so, we see if it has a value equal to some register used only in the
7911 loop exit code (as marked by jump.c).
7913 If those two conditions are true, we search backwards from the start of
7914 the loop to see if that same value was loaded into a register that still
7915 retains its value at the start of the loop.
7917 If so, we insert an insn after the load to copy the destination of that
7918 load into the equivalent register and (try to) replace our SET_SRC with that
7921 In any event, we invalidate whatever this SET or CLOBBER modifies. */
7924 cse_set_around_loop (x, insn, loop_start)
7929 struct table_elt *src_elt;
7931 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
7932 are setting PC or CC0 or whose SET_SRC is already a register. */
7933 if (GET_CODE (x) == SET
7934 && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
7935 && GET_CODE (SET_SRC (x)) != REG)
7937 src_elt = lookup (SET_SRC (x),
7938 HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
7939 GET_MODE (SET_DEST (x)));
7942 for (src_elt = src_elt->first_same_value; src_elt;
7943 src_elt = src_elt->next_same_value)
7944 if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
7945 && COST (src_elt->exp) < COST (SET_SRC (x)))
7949 /* Look for an insn in front of LOOP_START that sets
7950 something in the desired mode to SET_SRC (x) before we hit
7951 a label or CALL_INSN. */
7953 for (p = prev_nonnote_insn (loop_start);
7954 p && GET_CODE (p) != CALL_INSN
7955 && GET_CODE (p) != CODE_LABEL;
7956 p = prev_nonnote_insn (p))
7957 if ((set = single_set (p)) != 0
7958 && GET_CODE (SET_DEST (set)) == REG
7959 && GET_MODE (SET_DEST (set)) == src_elt->mode
7960 && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
7962 /* We now have to ensure that nothing between P
7963 and LOOP_START modified anything referenced in
7964 SET_SRC (x). We know that nothing within the loop
7965 can modify it, or we would have invalidated it in
7969 cse_check_loop_start_value = SET_SRC (x);
7970 for (q = p; q != loop_start; q = NEXT_INSN (q))
7971 if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
7972 note_stores (PATTERN (q), cse_check_loop_start);
7974 /* If nothing was changed and we can replace our
7975 SET_SRC, add an insn after P to copy its destination
7976 to what we will be replacing SET_SRC with. */
7977 if (cse_check_loop_start_value
7978 && validate_change (insn, &SET_SRC (x),
7980 emit_insn_after (gen_move_insn (src_elt->exp,
7988 /* Now invalidate anything modified by X. */
7989 note_mem_written (SET_DEST (x));
7991 /* See comment on similar code in cse_insn for explanation of these tests. */
7992 if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
7993 || GET_CODE (SET_DEST (x)) == MEM)
7994 invalidate (SET_DEST (x), VOIDmode);
7995 else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
7996 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
7997 invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
8000 /* Find the end of INSN's basic block and return its range,
8001 the total number of SETs in all the insns of the block, the last insn of the
8002 block, and the branch path.
8004 The branch path indicates which branches should be followed. If a non-zero
8005 path size is specified, the block should be rescanned and a different set
8006 of branches will be taken. The branch path is only used if
8007 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
8009 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
8010 used to describe the block. It is filled in with the information about
8011 the current block. The incoming structure's branch path, if any, is used
8012 to construct the output branch path. */
8015 cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks)
8017 struct cse_basic_block_data *data;
8024 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
8025 rtx next = GET_RTX_CLASS (GET_CODE (insn)) == 'i' ? insn : next_real_insn (insn);
8026 int path_size = data->path_size;
8030 /* Update the previous branch path, if any. If the last branch was
8031 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
8032 shorten the path by one and look at the previous branch. We know that
8033 at least one branch must have been taken if PATH_SIZE is non-zero. */
8034 while (path_size > 0)
8036 if (data->path[path_size - 1].status != NOT_TAKEN)
8038 data->path[path_size - 1].status = NOT_TAKEN;
8045 /* Scan to end of this basic block. */
8046 while (p && GET_CODE (p) != CODE_LABEL)
8048 /* Don't cse out the end of a loop. This makes a difference
8049 only for the unusual loops that always execute at least once;
8050 all other loops have labels there so we will stop in any case.
8051 Cse'ing out the end of the loop is dangerous because it
8052 might cause an invariant expression inside the loop
8053 to be reused after the end of the loop. This would make it
8054 hard to move the expression out of the loop in loop.c,
8055 especially if it is one of several equivalent expressions
8056 and loop.c would like to eliminate it.
8058 If we are running after loop.c has finished, we can ignore
8059 the NOTE_INSN_LOOP_END. */
8061 if (! after_loop && GET_CODE (p) == NOTE
8062 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
8065 /* Don't cse over a call to setjmp; on some machines (eg vax)
8066 the regs restored by the longjmp come from
8067 a later time than the setjmp. */
8068 if (GET_CODE (p) == NOTE
8069 && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
8072 /* A PARALLEL can have lots of SETs in it,
8073 especially if it is really an ASM_OPERANDS. */
8074 if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
8075 && GET_CODE (PATTERN (p)) == PARALLEL)
8076 nsets += XVECLEN (PATTERN (p), 0);
8077 else if (GET_CODE (p) != NOTE)
8080 /* Ignore insns made by CSE; they cannot affect the boundaries of
8083 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
8084 high_cuid = INSN_CUID (p);
8085 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
8086 low_cuid = INSN_CUID (p);
8088 /* See if this insn is in our branch path. If it is and we are to
8090 if (path_entry < path_size && data->path[path_entry].branch == p)
8092 if (data->path[path_entry].status != NOT_TAKEN)
8095 /* Point to next entry in path, if any. */
8099 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
8100 was specified, we haven't reached our maximum path length, there are
8101 insns following the target of the jump, this is the only use of the
8102 jump label, and the target label is preceded by a BARRIER.
8104 Alternatively, we can follow the jump if it branches around a
8105 block of code and there are no other branches into the block.
8106 In this case invalidate_skipped_block will be called to invalidate any
8107 registers set in the block when following the jump. */
8109 else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1
8110 && GET_CODE (p) == JUMP_INSN
8111 && GET_CODE (PATTERN (p)) == SET
8112 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
8113 && JUMP_LABEL (p) != 0
8114 && LABEL_NUSES (JUMP_LABEL (p)) == 1
8115 && NEXT_INSN (JUMP_LABEL (p)) != 0)
8117 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
8118 if ((GET_CODE (q) != NOTE
8119 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
8120 || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP)
8121 && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
8124 /* If we ran into a BARRIER, this code is an extension of the
8125 basic block when the branch is taken. */
8126 if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
8128 /* Don't allow ourself to keep walking around an
8129 always-executed loop. */
8130 if (next_real_insn (q) == next)
8136 /* Similarly, don't put a branch in our path more than once. */
8137 for (i = 0; i < path_entry; i++)
8138 if (data->path[i].branch == p)
8141 if (i != path_entry)
8144 data->path[path_entry].branch = p;
8145 data->path[path_entry++].status = TAKEN;
8147 /* This branch now ends our path. It was possible that we
8148 didn't see this branch the last time around (when the
8149 insn in front of the target was a JUMP_INSN that was
8150 turned into a no-op). */
8151 path_size = path_entry;
8154 /* Mark block so we won't scan it again later. */
8155 PUT_MODE (NEXT_INSN (p), QImode);
8157 /* Detect a branch around a block of code. */
8158 else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
8162 if (next_real_insn (q) == next)
8168 for (i = 0; i < path_entry; i++)
8169 if (data->path[i].branch == p)
8172 if (i != path_entry)
8175 /* This is no_labels_between_p (p, q) with an added check for
8176 reaching the end of a function (in case Q precedes P). */
8177 for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
8178 if (GET_CODE (tmp) == CODE_LABEL)
8183 data->path[path_entry].branch = p;
8184 data->path[path_entry++].status = AROUND;
8186 path_size = path_entry;
8189 /* Mark block so we won't scan it again later. */
8190 PUT_MODE (NEXT_INSN (p), QImode);
8197 data->low_cuid = low_cuid;
8198 data->high_cuid = high_cuid;
8199 data->nsets = nsets;
8202 /* If all jumps in the path are not taken, set our path length to zero
8203 so a rescan won't be done. */
8204 for (i = path_size - 1; i >= 0; i--)
8205 if (data->path[i].status != NOT_TAKEN)
8209 data->path_size = 0;
8211 data->path_size = path_size;
8213 /* End the current branch path. */
8214 data->path[path_size].branch = 0;
8217 /* Perform cse on the instructions of a function.
8218 F is the first instruction.
8219 NREGS is one plus the highest pseudo-reg number used in the instruction.
8221 AFTER_LOOP is 1 if this is the cse call done after loop optimization
8222 (only if -frerun-cse-after-loop).
8224 Returns 1 if jump_optimize should be redone due to simplifications
8225 in conditional jump instructions. */
8228 cse_main (f, nregs, after_loop, file)
8234 struct cse_basic_block_data val;
8235 register rtx insn = f;
8238 cse_jumps_altered = 0;
8239 recorded_label_ref = 0;
8240 constant_pool_entries_cost = 0;
8244 init_alias_analysis ();
8248 all_minus_one = (int *) alloca (nregs * sizeof (int));
8249 consec_ints = (int *) alloca (nregs * sizeof (int));
8251 for (i = 0; i < nregs; i++)
8253 all_minus_one[i] = -1;
8257 reg_next_eqv = (int *) alloca (nregs * sizeof (int));
8258 reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
8259 reg_qty = (int *) alloca (nregs * sizeof (int));
8260 reg_in_table = (int *) alloca (nregs * sizeof (int));
8261 reg_tick = (int *) alloca (nregs * sizeof (int));
8263 #ifdef LOAD_EXTEND_OP
8265 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
8266 and change the code and mode as appropriate. */
8267 memory_extend_rtx = gen_rtx (ZERO_EXTEND, VOIDmode, NULL_RTX);
8270 /* Discard all the free elements of the previous function
8271 since they are allocated in the temporarily obstack. */
8272 bzero ((char *) table, sizeof table);
8273 free_element_chain = 0;
8274 n_elements_made = 0;
8276 /* Find the largest uid. */
8278 max_uid = get_max_uid ();
8279 uid_cuid = (int *) alloca ((max_uid + 1) * sizeof (int));
8280 bzero ((char *) uid_cuid, (max_uid + 1) * sizeof (int));
8282 /* Compute the mapping from uids to cuids.
8283 CUIDs are numbers assigned to insns, like uids,
8284 except that cuids increase monotonically through the code.
8285 Don't assign cuids to line-number NOTEs, so that the distance in cuids
8286 between two insns is not affected by -g. */
8288 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
8290 if (GET_CODE (insn) != NOTE
8291 || NOTE_LINE_NUMBER (insn) < 0)
8292 INSN_CUID (insn) = ++i;
8294 /* Give a line number note the same cuid as preceding insn. */
8295 INSN_CUID (insn) = i;
8298 /* Initialize which registers are clobbered by calls. */
8300 CLEAR_HARD_REG_SET (regs_invalidated_by_call);
8302 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
8303 if ((call_used_regs[i]
8304 /* Used to check !fixed_regs[i] here, but that isn't safe;
8305 fixed regs are still call-clobbered, and sched can get
8306 confused if they can "live across calls".
8308 The frame pointer is always preserved across calls. The arg
8309 pointer is if it is fixed. The stack pointer usually is, unless
8310 RETURN_POPS_ARGS, in which case an explicit CLOBBER
8311 will be present. If we are generating PIC code, the PIC offset
8312 table register is preserved across calls. */
8314 && i != STACK_POINTER_REGNUM
8315 && i != FRAME_POINTER_REGNUM
8316 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
8317 && i != HARD_FRAME_POINTER_REGNUM
8319 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
8320 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
8322 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
8323 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
8327 SET_HARD_REG_BIT (regs_invalidated_by_call, i);
8329 /* Loop over basic blocks.
8330 Compute the maximum number of qty's needed for each basic block
8331 (which is 2 for each SET). */
8335 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
8336 flag_cse_skip_blocks);
8338 /* If this basic block was already processed or has no sets, skip it. */
8339 if (val.nsets == 0 || GET_MODE (insn) == QImode)
8341 PUT_MODE (insn, VOIDmode);
8342 insn = (val.last ? NEXT_INSN (val.last) : 0);
8347 cse_basic_block_start = val.low_cuid;
8348 cse_basic_block_end = val.high_cuid;
8349 max_qty = val.nsets * 2;
8352 fprintf (file, ";; Processing block from %d to %d, %d sets.\n",
8353 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
8356 /* Make MAX_QTY bigger to give us room to optimize
8357 past the end of this basic block, if that should prove useful. */
8363 /* If this basic block is being extended by following certain jumps,
8364 (see `cse_end_of_basic_block'), we reprocess the code from the start.
8365 Otherwise, we start after this basic block. */
8366 if (val.path_size > 0)
8367 cse_basic_block (insn, val.last, val.path, 0);
8370 int old_cse_jumps_altered = cse_jumps_altered;
8373 /* When cse changes a conditional jump to an unconditional
8374 jump, we want to reprocess the block, since it will give
8375 us a new branch path to investigate. */
8376 cse_jumps_altered = 0;
8377 temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
8378 if (cse_jumps_altered == 0
8379 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
8382 cse_jumps_altered |= old_cse_jumps_altered;
8390 /* Tell refers_to_mem_p that qty_const info is not available. */
8393 if (max_elements_made < n_elements_made)
8394 max_elements_made = n_elements_made;
8396 return cse_jumps_altered || recorded_label_ref;
8399 /* Process a single basic block. FROM and TO and the limits of the basic
8400 block. NEXT_BRANCH points to the branch path when following jumps or
8401 a null path when not following jumps.
8403 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
8404 loop. This is true when we are being called for the last time on a
8405 block and this CSE pass is before loop.c. */
8408 cse_basic_block (from, to, next_branch, around_loop)
8409 register rtx from, to;
8410 struct branch_path *next_branch;
8415 int in_libcall_block = 0;
8418 /* Each of these arrays is undefined before max_reg, so only allocate
8419 the space actually needed and adjust the start below. */
8421 qty_first_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
8422 qty_last_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
8423 qty_mode= (enum machine_mode *) alloca ((max_qty - max_reg) * sizeof (enum machine_mode));
8424 qty_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
8425 qty_const_insn = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
8427 = (enum rtx_code *) alloca ((max_qty - max_reg) * sizeof (enum rtx_code));
8428 qty_comparison_qty = (int *) alloca ((max_qty - max_reg) * sizeof (int));
8429 qty_comparison_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
8431 qty_first_reg -= max_reg;
8432 qty_last_reg -= max_reg;
8433 qty_mode -= max_reg;
8434 qty_const -= max_reg;
8435 qty_const_insn -= max_reg;
8436 qty_comparison_code -= max_reg;
8437 qty_comparison_qty -= max_reg;
8438 qty_comparison_const -= max_reg;
8442 /* TO might be a label. If so, protect it from being deleted. */
8443 if (to != 0 && GET_CODE (to) == CODE_LABEL)
8446 for (insn = from; insn != to; insn = NEXT_INSN (insn))
8448 register enum rtx_code code;
8450 struct table_elt *p, *next;
8452 /* If we have processed 1,000 insns, flush the hash table to avoid
8453 extreme quadratic behavior.
8455 ??? This is a real kludge and needs to be done some other way.
8457 if (num_insns++ > 1000)
8459 for (i = 0; i < NBUCKETS; i++)
8460 for (p = table[i]; p; p = next)
8462 next = p->next_same_hash;
8464 if (GET_CODE (p->exp) == REG)
8465 invalidate (p->exp, p->mode);
8467 remove_from_table (p, i);
8473 /* See if this is a branch that is part of the path. If so, and it is
8474 to be taken, do so. */
8475 if (next_branch->branch == insn)
8477 enum taken status = next_branch++->status;
8478 if (status != NOT_TAKEN)
8480 if (status == TAKEN)
8481 record_jump_equiv (insn, 1);
8483 invalidate_skipped_block (NEXT_INSN (insn));
8485 /* Set the last insn as the jump insn; it doesn't affect cc0.
8486 Then follow this branch. */
8491 insn = JUMP_LABEL (insn);
8496 code = GET_CODE (insn);
8497 if (GET_MODE (insn) == QImode)
8498 PUT_MODE (insn, VOIDmode);
8500 if (GET_RTX_CLASS (code) == 'i')
8502 /* Process notes first so we have all notes in canonical forms when
8503 looking for duplicate operations. */
8505 if (REG_NOTES (insn))
8506 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
8508 /* Track when we are inside in LIBCALL block. Inside such a block,
8509 we do not want to record destinations. The last insn of a
8510 LIBCALL block is not considered to be part of the block, since
8511 its destination is the result of the block and hence should be
8514 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
8515 in_libcall_block = 1;
8516 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
8517 in_libcall_block = 0;
8519 cse_insn (insn, in_libcall_block);
8522 /* If INSN is now an unconditional jump, skip to the end of our
8523 basic block by pretending that we just did the last insn in the
8524 basic block. If we are jumping to the end of our block, show
8525 that we can have one usage of TO. */
8527 if (simplejump_p (insn))
8532 if (JUMP_LABEL (insn) == to)
8535 /* Maybe TO was deleted because the jump is unconditional.
8536 If so, there is nothing left in this basic block. */
8537 /* ??? Perhaps it would be smarter to set TO
8538 to whatever follows this insn,
8539 and pretend the basic block had always ended here. */
8540 if (INSN_DELETED_P (to))
8543 insn = PREV_INSN (to);
8546 /* See if it is ok to keep on going past the label
8547 which used to end our basic block. Remember that we incremented
8548 the count of that label, so we decrement it here. If we made
8549 a jump unconditional, TO_USAGE will be one; in that case, we don't
8550 want to count the use in that jump. */
8552 if (to != 0 && NEXT_INSN (insn) == to
8553 && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
8555 struct cse_basic_block_data val;
8558 insn = NEXT_INSN (to);
8560 if (LABEL_NUSES (to) == 0)
8561 insn = delete_insn (to);
8563 /* If TO was the last insn in the function, we are done. */
8567 /* If TO was preceded by a BARRIER we are done with this block
8568 because it has no continuation. */
8569 prev = prev_nonnote_insn (to);
8570 if (prev && GET_CODE (prev) == BARRIER)
8573 /* Find the end of the following block. Note that we won't be
8574 following branches in this case. */
8577 cse_end_of_basic_block (insn, &val, 0, 0, 0);
8579 /* If the tables we allocated have enough space left
8580 to handle all the SETs in the next basic block,
8581 continue through it. Otherwise, return,
8582 and that block will be scanned individually. */
8583 if (val.nsets * 2 + next_qty > max_qty)
8586 cse_basic_block_start = val.low_cuid;
8587 cse_basic_block_end = val.high_cuid;
8590 /* Prevent TO from being deleted if it is a label. */
8591 if (to != 0 && GET_CODE (to) == CODE_LABEL)
8594 /* Back up so we process the first insn in the extension. */
8595 insn = PREV_INSN (insn);
8599 if (next_qty > max_qty)
8602 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
8603 the previous insn is the only insn that branches to the head of a loop,
8604 we can cse into the loop. Don't do this if we changed the jump
8605 structure of a loop unless we aren't going to be following jumps. */
8607 if ((cse_jumps_altered == 0
8608 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
8609 && around_loop && to != 0
8610 && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
8611 && GET_CODE (PREV_INSN (to)) == JUMP_INSN
8612 && JUMP_LABEL (PREV_INSN (to)) != 0
8613 && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
8614 cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
8616 return to ? NEXT_INSN (to) : 0;
8619 /* Count the number of times registers are used (not set) in X.
8620 COUNTS is an array in which we accumulate the count, INCR is how much
8621 we count each register usage.
8623 Don't count a usage of DEST, which is the SET_DEST of a SET which
8624 contains X in its SET_SRC. This is because such a SET does not
8625 modify the liveness of DEST. */
8628 count_reg_usage (x, counts, dest, incr)
8641 switch (code = GET_CODE (x))
8645 counts[REGNO (x)] += incr;
8659 /* Unless we are setting a REG, count everything in SET_DEST. */
8660 if (GET_CODE (SET_DEST (x)) != REG)
8661 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
8663 /* If SRC has side-effects, then we can't delete this insn, so the
8664 usage of SET_DEST inside SRC counts.
8666 ??? Strictly-speaking, we might be preserving this insn
8667 because some other SET has side-effects, but that's hard
8668 to do and can't happen now. */
8669 count_reg_usage (SET_SRC (x), counts,
8670 side_effects_p (SET_SRC (x)) ? NULL_RTX : SET_DEST (x),
8675 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr);
8677 /* ... falls through ... */
8680 count_reg_usage (PATTERN (x), counts, NULL_RTX, incr);
8682 /* Things used in a REG_EQUAL note aren't dead since loop may try to
8685 count_reg_usage (REG_NOTES (x), counts, NULL_RTX, incr);
8690 if (REG_NOTE_KIND (x) == REG_EQUAL
8691 || GET_CODE (XEXP (x,0)) == USE)
8692 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
8693 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
8700 fmt = GET_RTX_FORMAT (code);
8701 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
8704 count_reg_usage (XEXP (x, i), counts, dest, incr);
8705 else if (fmt[i] == 'E')
8706 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
8707 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
8711 /* Scan all the insns and delete any that are dead; i.e., they store a register
8712 that is never used or they copy a register to itself.
8714 This is used to remove insns made obviously dead by cse. It improves the
8715 heuristics in loop since it won't try to move dead invariants out of loops
8716 or make givs for dead quantities. The remaining passes of the compilation
8717 are also sped up. */
8720 delete_dead_from_cse (insns, nreg)
8724 int *counts = (int *) alloca (nreg * sizeof (int));
8730 /* First count the number of times each register is used. */
8731 bzero ((char *) counts, sizeof (int) * nreg);
8732 for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
8733 count_reg_usage (insn, counts, NULL_RTX, 1);
8735 /* Go from the last insn to the first and delete insns that only set unused
8736 registers or copy a register to itself. As we delete an insn, remove
8737 usage counts for registers it uses. */
8738 for (insn = prev_real_insn (get_last_insn ()); insn; insn = prev)
8742 prev = prev_real_insn (insn);
8744 /* Don't delete any insns that are part of a libcall block.
8745 Flow or loop might get confused if we did that. Remember
8746 that we are scanning backwards. */
8747 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
8752 else if (GET_CODE (PATTERN (insn)) == SET)
8754 if (GET_CODE (SET_DEST (PATTERN (insn))) == REG
8755 && SET_DEST (PATTERN (insn)) == SET_SRC (PATTERN (insn)))
8759 else if (GET_CODE (SET_DEST (PATTERN (insn))) == CC0
8760 && ! side_effects_p (SET_SRC (PATTERN (insn)))
8761 && ((tem = next_nonnote_insn (insn)) == 0
8762 || GET_RTX_CLASS (GET_CODE (tem)) != 'i'
8763 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
8766 else if (GET_CODE (SET_DEST (PATTERN (insn))) != REG
8767 || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER
8768 || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0
8769 || side_effects_p (SET_SRC (PATTERN (insn))))
8772 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
8773 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
8775 rtx elt = XVECEXP (PATTERN (insn), 0, i);
8777 if (GET_CODE (elt) == SET)
8779 if (GET_CODE (SET_DEST (elt)) == REG
8780 && SET_DEST (elt) == SET_SRC (elt))
8784 else if (GET_CODE (SET_DEST (elt)) == CC0
8785 && ! side_effects_p (SET_SRC (elt))
8786 && ((tem = next_nonnote_insn (insn)) == 0
8787 || GET_RTX_CLASS (GET_CODE (tem)) != 'i'
8788 || ! reg_referenced_p (cc0_rtx, PATTERN (tem))))
8791 else if (GET_CODE (SET_DEST (elt)) != REG
8792 || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER
8793 || counts[REGNO (SET_DEST (elt))] != 0
8794 || side_effects_p (SET_SRC (elt)))
8797 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
8803 /* If this is a dead insn, delete it and show registers in it aren't
8808 count_reg_usage (insn, counts, NULL_RTX, -1);
8812 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))