2002-05-10 David S. Miller <davem@redhat.com>
[official-gcc.git] / gcc / cse.c
blobb13de96cc40af11bab38e8b7393685abd58b8c70
1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
22 #include "config.h"
23 /* stdio.h must precede rtl.h for FFS. */
24 #include "system.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "regs.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "flags.h"
32 #include "real.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "function.h"
36 #include "expr.h"
37 #include "toplev.h"
38 #include "output.h"
39 #include "ggc.h"
40 #include "timevar.h"
42 /* The basic idea of common subexpression elimination is to go
43 through the code, keeping a record of expressions that would
44 have the same value at the current scan point, and replacing
45 expressions encountered with the cheapest equivalent expression.
47 It is too complicated to keep track of the different possibilities
48 when control paths merge in this code; so, at each label, we forget all
49 that is known and start fresh. This can be described as processing each
50 extended basic block separately. We have a separate pass to perform
51 global CSE.
53 Note CSE can turn a conditional or computed jump into a nop or
54 an unconditional jump. When this occurs we arrange to run the jump
55 optimizer after CSE to delete the unreachable code.
57 We use two data structures to record the equivalent expressions:
58 a hash table for most expressions, and a vector of "quantity
59 numbers" to record equivalent (pseudo) registers.
61 The use of the special data structure for registers is desirable
62 because it is faster. It is possible because registers references
63 contain a fairly small number, the register number, taken from
64 a contiguously allocated series, and two register references are
65 identical if they have the same number. General expressions
66 do not have any such thing, so the only way to retrieve the
67 information recorded on an expression other than a register
68 is to keep it in a hash table.
70 Registers and "quantity numbers":
72 At the start of each basic block, all of the (hardware and pseudo)
73 registers used in the function are given distinct quantity
74 numbers to indicate their contents. During scan, when the code
75 copies one register into another, we copy the quantity number.
76 When a register is loaded in any other way, we allocate a new
77 quantity number to describe the value generated by this operation.
78 `reg_qty' records what quantity a register is currently thought
79 of as containing.
81 All real quantity numbers are greater than or equal to `max_reg'.
82 If register N has not been assigned a quantity, reg_qty[N] will equal N.
84 Quantity numbers below `max_reg' do not exist and none of the `qty_table'
85 entries should be referenced with an index below `max_reg'.
87 We also maintain a bidirectional chain of registers for each
88 quantity number. The `qty_table` members `first_reg' and `last_reg',
89 and `reg_eqv_table' members `next' and `prev' hold these chains.
91 The first register in a chain is the one whose lifespan is least local.
92 Among equals, it is the one that was seen first.
93 We replace any equivalent register with that one.
95 If two registers have the same quantity number, it must be true that
96 REG expressions with qty_table `mode' must be in the hash table for both
97 registers and must be in the same class.
99 The converse is not true. Since hard registers may be referenced in
100 any mode, two REG expressions might be equivalent in the hash table
101 but not have the same quantity number if the quantity number of one
102 of the registers is not the same mode as those expressions.
104 Constants and quantity numbers
106 When a quantity has a known constant value, that value is stored
107 in the appropriate qty_table `const_rtx'. This is in addition to
108 putting the constant in the hash table as is usual for non-regs.
110 Whether a reg or a constant is preferred is determined by the configuration
111 macro CONST_COSTS and will often depend on the constant value. In any
112 event, expressions containing constants can be simplified, by fold_rtx.
114 When a quantity has a known nearly constant value (such as an address
115 of a stack slot), that value is stored in the appropriate qty_table
116 `const_rtx'.
118 Integer constants don't have a machine mode. However, cse
119 determines the intended machine mode from the destination
120 of the instruction that moves the constant. The machine mode
121 is recorded in the hash table along with the actual RTL
122 constant expression so that different modes are kept separate.
124 Other expressions:
126 To record known equivalences among expressions in general
127 we use a hash table called `table'. It has a fixed number of buckets
128 that contain chains of `struct table_elt' elements for expressions.
129 These chains connect the elements whose expressions have the same
130 hash codes.
132 Other chains through the same elements connect the elements which
133 currently have equivalent values.
135 Register references in an expression are canonicalized before hashing
136 the expression. This is done using `reg_qty' and qty_table `first_reg'.
137 The hash code of a register reference is computed using the quantity
138 number, not the register number.
140 When the value of an expression changes, it is necessary to remove from the
141 hash table not just that expression but all expressions whose values
142 could be different as a result.
144 1. If the value changing is in memory, except in special cases
145 ANYTHING referring to memory could be changed. That is because
146 nobody knows where a pointer does not point.
147 The function `invalidate_memory' removes what is necessary.
149 The special cases are when the address is constant or is
150 a constant plus a fixed register such as the frame pointer
151 or a static chain pointer. When such addresses are stored in,
152 we can tell exactly which other such addresses must be invalidated
153 due to overlap. `invalidate' does this.
154 All expressions that refer to non-constant
155 memory addresses are also invalidated. `invalidate_memory' does this.
157 2. If the value changing is a register, all expressions
158 containing references to that register, and only those,
159 must be removed.
161 Because searching the entire hash table for expressions that contain
162 a register is very slow, we try to figure out when it isn't necessary.
163 Precisely, this is necessary only when expressions have been
164 entered in the hash table using this register, and then the value has
165 changed, and then another expression wants to be added to refer to
166 the register's new value. This sequence of circumstances is rare
167 within any one basic block.
169 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
170 reg_tick[i] is incremented whenever a value is stored in register i.
171 reg_in_table[i] holds -1 if no references to register i have been
172 entered in the table; otherwise, it contains the value reg_tick[i] had
173 when the references were entered. If we want to enter a reference
174 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
175 Until we want to enter a new entry, the mere fact that the two vectors
176 don't match makes the entries be ignored if anyone tries to match them.
178 Registers themselves are entered in the hash table as well as in
179 the equivalent-register chains. However, the vectors `reg_tick'
180 and `reg_in_table' do not apply to expressions which are simple
181 register references. These expressions are removed from the table
182 immediately when they become invalid, and this can be done even if
183 we do not immediately search for all the expressions that refer to
184 the register.
186 A CLOBBER rtx in an instruction invalidates its operand for further
187 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
188 invalidates everything that resides in memory.
190 Related expressions:
192 Constant expressions that differ only by an additive integer
193 are called related. When a constant expression is put in
194 the table, the related expression with no constant term
195 is also entered. These are made to point at each other
196 so that it is possible to find out if there exists any
197 register equivalent to an expression related to a given expression. */
199 /* One plus largest register number used in this function. */
201 static int max_reg;
203 /* One plus largest instruction UID used in this function at time of
204 cse_main call. */
206 static int max_insn_uid;
208 /* Length of qty_table vector. We know in advance we will not need
209 a quantity number this big. */
211 static int max_qty;
213 /* Next quantity number to be allocated.
214 This is 1 + the largest number needed so far. */
216 static int next_qty;
218 /* Per-qty information tracking.
220 `first_reg' and `last_reg' track the head and tail of the
221 chain of registers which currently contain this quantity.
223 `mode' contains the machine mode of this quantity.
225 `const_rtx' holds the rtx of the constant value of this
226 quantity, if known. A summations of the frame/arg pointer
227 and a constant can also be entered here. When this holds
228 a known value, `const_insn' is the insn which stored the
229 constant value.
231 `comparison_{code,const,qty}' are used to track when a
232 comparison between a quantity and some constant or register has
233 been passed. In such a case, we know the results of the comparison
234 in case we see it again. These members record a comparison that
235 is known to be true. `comparison_code' holds the rtx code of such
236 a comparison, else it is set to UNKNOWN and the other two
237 comparison members are undefined. `comparison_const' holds
238 the constant being compared against, or zero if the comparison
239 is not against a constant. `comparison_qty' holds the quantity
240 being compared against when the result is known. If the comparison
241 is not with a register, `comparison_qty' is -1. */
243 struct qty_table_elem
245 rtx const_rtx;
246 rtx const_insn;
247 rtx comparison_const;
248 int comparison_qty;
249 unsigned int first_reg, last_reg;
250 enum machine_mode mode;
251 enum rtx_code comparison_code;
254 /* The table of all qtys, indexed by qty number. */
255 static struct qty_table_elem *qty_table;
257 #ifdef HAVE_cc0
258 /* For machines that have a CC0, we do not record its value in the hash
259 table since its use is guaranteed to be the insn immediately following
260 its definition and any other insn is presumed to invalidate it.
262 Instead, we store below the value last assigned to CC0. If it should
263 happen to be a constant, it is stored in preference to the actual
264 assigned value. In case it is a constant, we store the mode in which
265 the constant should be interpreted. */
267 static rtx prev_insn_cc0;
268 static enum machine_mode prev_insn_cc0_mode;
269 #endif
271 /* Previous actual insn. 0 if at first insn of basic block. */
273 static rtx prev_insn;
275 /* Insn being scanned. */
277 static rtx this_insn;
279 /* Index by register number, gives the number of the next (or
280 previous) register in the chain of registers sharing the same
281 value.
283 Or -1 if this register is at the end of the chain.
285 If reg_qty[N] == N, reg_eqv_table[N].next is undefined. */
287 /* Per-register equivalence chain. */
288 struct reg_eqv_elem
290 int next, prev;
293 /* The table of all register equivalence chains. */
294 static struct reg_eqv_elem *reg_eqv_table;
296 struct cse_reg_info
298 /* Next in hash chain. */
299 struct cse_reg_info *hash_next;
301 /* The next cse_reg_info structure in the free or used list. */
302 struct cse_reg_info *next;
304 /* Search key */
305 unsigned int regno;
307 /* The quantity number of the register's current contents. */
308 int reg_qty;
310 /* The number of times the register has been altered in the current
311 basic block. */
312 int reg_tick;
314 /* The REG_TICK value at which rtx's containing this register are
315 valid in the hash table. If this does not equal the current
316 reg_tick value, such expressions existing in the hash table are
317 invalid. */
318 int reg_in_table;
321 /* A free list of cse_reg_info entries. */
322 static struct cse_reg_info *cse_reg_info_free_list;
324 /* A used list of cse_reg_info entries. */
325 static struct cse_reg_info *cse_reg_info_used_list;
326 static struct cse_reg_info *cse_reg_info_used_list_end;
328 /* A mapping from registers to cse_reg_info data structures. */
329 #define REGHASH_SHIFT 7
330 #define REGHASH_SIZE (1 << REGHASH_SHIFT)
331 #define REGHASH_MASK (REGHASH_SIZE - 1)
332 static struct cse_reg_info *reg_hash[REGHASH_SIZE];
334 #define REGHASH_FN(REGNO) \
335 (((REGNO) ^ ((REGNO) >> REGHASH_SHIFT)) & REGHASH_MASK)
337 /* The last lookup we did into the cse_reg_info_tree. This allows us
338 to cache repeated lookups. */
339 static unsigned int cached_regno;
340 static struct cse_reg_info *cached_cse_reg_info;
342 /* A HARD_REG_SET containing all the hard registers for which there is
343 currently a REG expression in the hash table. Note the difference
344 from the above variables, which indicate if the REG is mentioned in some
345 expression in the table. */
347 static HARD_REG_SET hard_regs_in_table;
349 /* CUID of insn that starts the basic block currently being cse-processed. */
351 static int cse_basic_block_start;
353 /* CUID of insn that ends the basic block currently being cse-processed. */
355 static int cse_basic_block_end;
357 /* Vector mapping INSN_UIDs to cuids.
358 The cuids are like uids but increase monotonically always.
359 We use them to see whether a reg is used outside a given basic block. */
361 static int *uid_cuid;
363 /* Highest UID in UID_CUID. */
364 static int max_uid;
366 /* Get the cuid of an insn. */
368 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
370 /* Nonzero if this pass has made changes, and therefore it's
371 worthwhile to run the garbage collector. */
373 static int cse_altered;
375 /* Nonzero if cse has altered conditional jump insns
376 in such a way that jump optimization should be redone. */
378 static int cse_jumps_altered;
380 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
381 REG_LABEL, we have to rerun jump after CSE to put in the note. */
382 static int recorded_label_ref;
384 /* canon_hash stores 1 in do_not_record
385 if it notices a reference to CC0, PC, or some other volatile
386 subexpression. */
388 static int do_not_record;
390 #ifdef LOAD_EXTEND_OP
392 /* Scratch rtl used when looking for load-extended copy of a MEM. */
393 static rtx memory_extend_rtx;
394 #endif
396 /* canon_hash stores 1 in hash_arg_in_memory
397 if it notices a reference to memory within the expression being hashed. */
399 static int hash_arg_in_memory;
401 /* The hash table contains buckets which are chains of `struct table_elt's,
402 each recording one expression's information.
403 That expression is in the `exp' field.
405 The canon_exp field contains a canonical (from the point of view of
406 alias analysis) version of the `exp' field.
408 Those elements with the same hash code are chained in both directions
409 through the `next_same_hash' and `prev_same_hash' fields.
411 Each set of expressions with equivalent values
412 are on a two-way chain through the `next_same_value'
413 and `prev_same_value' fields, and all point with
414 the `first_same_value' field at the first element in
415 that chain. The chain is in order of increasing cost.
416 Each element's cost value is in its `cost' field.
418 The `in_memory' field is nonzero for elements that
419 involve any reference to memory. These elements are removed
420 whenever a write is done to an unidentified location in memory.
421 To be safe, we assume that a memory address is unidentified unless
422 the address is either a symbol constant or a constant plus
423 the frame pointer or argument pointer.
425 The `related_value' field is used to connect related expressions
426 (that differ by adding an integer).
427 The related expressions are chained in a circular fashion.
428 `related_value' is zero for expressions for which this
429 chain is not useful.
431 The `cost' field stores the cost of this element's expression.
432 The `regcost' field stores the value returned by approx_reg_cost for
433 this element's expression.
435 The `is_const' flag is set if the element is a constant (including
436 a fixed address).
438 The `flag' field is used as a temporary during some search routines.
440 The `mode' field is usually the same as GET_MODE (`exp'), but
441 if `exp' is a CONST_INT and has no machine mode then the `mode'
442 field is the mode it was being used as. Each constant is
443 recorded separately for each mode it is used with. */
445 struct table_elt
447 rtx exp;
448 rtx canon_exp;
449 struct table_elt *next_same_hash;
450 struct table_elt *prev_same_hash;
451 struct table_elt *next_same_value;
452 struct table_elt *prev_same_value;
453 struct table_elt *first_same_value;
454 struct table_elt *related_value;
455 int cost;
456 int regcost;
457 enum machine_mode mode;
458 char in_memory;
459 char is_const;
460 char flag;
463 /* We don't want a lot of buckets, because we rarely have very many
464 things stored in the hash table, and a lot of buckets slows
465 down a lot of loops that happen frequently. */
466 #define HASH_SHIFT 5
467 #define HASH_SIZE (1 << HASH_SHIFT)
468 #define HASH_MASK (HASH_SIZE - 1)
470 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
471 register (hard registers may require `do_not_record' to be set). */
473 #define HASH(X, M) \
474 ((GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
475 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
476 : canon_hash (X, M)) & HASH_MASK)
478 /* Determine whether register number N is considered a fixed register for the
479 purpose of approximating register costs.
480 It is desirable to replace other regs with fixed regs, to reduce need for
481 non-fixed hard regs.
482 A reg wins if it is either the frame pointer or designated as fixed. */
483 #define FIXED_REGNO_P(N) \
484 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
485 || fixed_regs[N] || global_regs[N])
487 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
488 hard registers and pointers into the frame are the cheapest with a cost
489 of 0. Next come pseudos with a cost of one and other hard registers with
490 a cost of 2. Aside from these special cases, call `rtx_cost'. */
492 #define CHEAP_REGNO(N) \
493 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
494 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
495 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
496 || ((N) < FIRST_PSEUDO_REGISTER \
497 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
499 #define COST(X) (GET_CODE (X) == REG ? 0 : notreg_cost (X, SET))
500 #define COST_IN(X,OUTER) (GET_CODE (X) == REG ? 0 : notreg_cost (X, OUTER))
502 /* Get the info associated with register N. */
504 #define GET_CSE_REG_INFO(N) \
505 (((N) == cached_regno && cached_cse_reg_info) \
506 ? cached_cse_reg_info : get_cse_reg_info ((N)))
508 /* Get the number of times this register has been updated in this
509 basic block. */
511 #define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
513 /* Get the point at which REG was recorded in the table. */
515 #define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
517 /* Get the quantity number for REG. */
519 #define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
521 /* Determine if the quantity number for register X represents a valid index
522 into the qty_table. */
524 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (int) (N))
526 static struct table_elt *table[HASH_SIZE];
528 /* Chain of `struct table_elt's made so far for this function
529 but currently removed from the table. */
531 static struct table_elt *free_element_chain;
533 /* Number of `struct table_elt' structures made so far for this function. */
535 static int n_elements_made;
537 /* Maximum value `n_elements_made' has had so far in this compilation
538 for functions previously processed. */
540 static int max_elements_made;
542 /* Surviving equivalence class when two equivalence classes are merged
543 by recording the effects of a jump in the last insn. Zero if the
544 last insn was not a conditional jump. */
546 static struct table_elt *last_jump_equiv_class;
548 /* Set to the cost of a constant pool reference if one was found for a
549 symbolic constant. If this was found, it means we should try to
550 convert constants into constant pool entries if they don't fit in
551 the insn. */
553 static int constant_pool_entries_cost;
555 /* Define maximum length of a branch path. */
557 #define PATHLENGTH 10
559 /* This data describes a block that will be processed by cse_basic_block. */
561 struct cse_basic_block_data
563 /* Lowest CUID value of insns in block. */
564 int low_cuid;
565 /* Highest CUID value of insns in block. */
566 int high_cuid;
567 /* Total number of SETs in block. */
568 int nsets;
569 /* Last insn in the block. */
570 rtx last;
571 /* Size of current branch path, if any. */
572 int path_size;
573 /* Current branch path, indicating which branches will be taken. */
574 struct branch_path
576 /* The branch insn. */
577 rtx branch;
578 /* Whether it should be taken or not. AROUND is the same as taken
579 except that it is used when the destination label is not preceded
580 by a BARRIER. */
581 enum taken {TAKEN, NOT_TAKEN, AROUND} status;
582 } path[PATHLENGTH];
585 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
586 virtual regs here because the simplify_*_operation routines are called
587 by integrate.c, which is called before virtual register instantiation.
589 ?!? FIXED_BASE_PLUS_P and NONZERO_BASE_PLUS_P need to move into
590 a header file so that their definitions can be shared with the
591 simplification routines in simplify-rtx.c. Until then, do not
592 change these macros without also changing the copy in simplify-rtx.c. */
594 #define FIXED_BASE_PLUS_P(X) \
595 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
596 || ((X) == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])\
597 || (X) == virtual_stack_vars_rtx \
598 || (X) == virtual_incoming_args_rtx \
599 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
600 && (XEXP (X, 0) == frame_pointer_rtx \
601 || XEXP (X, 0) == hard_frame_pointer_rtx \
602 || ((X) == arg_pointer_rtx \
603 && fixed_regs[ARG_POINTER_REGNUM]) \
604 || XEXP (X, 0) == virtual_stack_vars_rtx \
605 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
606 || GET_CODE (X) == ADDRESSOF)
608 /* Similar, but also allows reference to the stack pointer.
610 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
611 arg_pointer_rtx by itself is nonzero, because on at least one machine,
612 the i960, the arg pointer is zero when it is unused. */
614 #define NONZERO_BASE_PLUS_P(X) \
615 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
616 || (X) == virtual_stack_vars_rtx \
617 || (X) == virtual_incoming_args_rtx \
618 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
619 && (XEXP (X, 0) == frame_pointer_rtx \
620 || XEXP (X, 0) == hard_frame_pointer_rtx \
621 || ((X) == arg_pointer_rtx \
622 && fixed_regs[ARG_POINTER_REGNUM]) \
623 || XEXP (X, 0) == virtual_stack_vars_rtx \
624 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
625 || (X) == stack_pointer_rtx \
626 || (X) == virtual_stack_dynamic_rtx \
627 || (X) == virtual_outgoing_args_rtx \
628 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
629 && (XEXP (X, 0) == stack_pointer_rtx \
630 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
631 || XEXP (X, 0) == virtual_outgoing_args_rtx)) \
632 || GET_CODE (X) == ADDRESSOF)
634 static int notreg_cost PARAMS ((rtx, enum rtx_code));
635 static int approx_reg_cost_1 PARAMS ((rtx *, void *));
636 static int approx_reg_cost PARAMS ((rtx));
637 static int preferrable PARAMS ((int, int, int, int));
638 static void new_basic_block PARAMS ((void));
639 static void make_new_qty PARAMS ((unsigned int, enum machine_mode));
640 static void make_regs_eqv PARAMS ((unsigned int, unsigned int));
641 static void delete_reg_equiv PARAMS ((unsigned int));
642 static int mention_regs PARAMS ((rtx));
643 static int insert_regs PARAMS ((rtx, struct table_elt *, int));
644 static void remove_from_table PARAMS ((struct table_elt *, unsigned));
645 static struct table_elt *lookup PARAMS ((rtx, unsigned, enum machine_mode)),
646 *lookup_for_remove PARAMS ((rtx, unsigned, enum machine_mode));
647 static rtx lookup_as_function PARAMS ((rtx, enum rtx_code));
648 static struct table_elt *insert PARAMS ((rtx, struct table_elt *, unsigned,
649 enum machine_mode));
650 static void merge_equiv_classes PARAMS ((struct table_elt *,
651 struct table_elt *));
652 static void invalidate PARAMS ((rtx, enum machine_mode));
653 static int cse_rtx_varies_p PARAMS ((rtx, int));
654 static void remove_invalid_refs PARAMS ((unsigned int));
655 static void remove_invalid_subreg_refs PARAMS ((unsigned int, unsigned int,
656 enum machine_mode));
657 static void rehash_using_reg PARAMS ((rtx));
658 static void invalidate_memory PARAMS ((void));
659 static void invalidate_for_call PARAMS ((void));
660 static rtx use_related_value PARAMS ((rtx, struct table_elt *));
661 static unsigned canon_hash PARAMS ((rtx, enum machine_mode));
662 static unsigned canon_hash_string PARAMS ((const char *));
663 static unsigned safe_hash PARAMS ((rtx, enum machine_mode));
664 static int exp_equiv_p PARAMS ((rtx, rtx, int, int));
665 static rtx canon_reg PARAMS ((rtx, rtx));
666 static void find_best_addr PARAMS ((rtx, rtx *, enum machine_mode));
667 static enum rtx_code find_comparison_args PARAMS ((enum rtx_code, rtx *, rtx *,
668 enum machine_mode *,
669 enum machine_mode *));
670 static rtx fold_rtx PARAMS ((rtx, rtx));
671 static rtx equiv_constant PARAMS ((rtx));
672 static void record_jump_equiv PARAMS ((rtx, int));
673 static void record_jump_cond PARAMS ((enum rtx_code, enum machine_mode,
674 rtx, rtx, int));
675 static void cse_insn PARAMS ((rtx, rtx));
676 static int addr_affects_sp_p PARAMS ((rtx));
677 static void invalidate_from_clobbers PARAMS ((rtx));
678 static rtx cse_process_notes PARAMS ((rtx, rtx));
679 static void cse_around_loop PARAMS ((rtx));
680 static void invalidate_skipped_set PARAMS ((rtx, rtx, void *));
681 static void invalidate_skipped_block PARAMS ((rtx));
682 static void cse_check_loop_start PARAMS ((rtx, rtx, void *));
683 static void cse_set_around_loop PARAMS ((rtx, rtx, rtx));
684 static rtx cse_basic_block PARAMS ((rtx, rtx, struct branch_path *, int));
685 static void count_reg_usage PARAMS ((rtx, int *, rtx, int));
686 static int check_for_label_ref PARAMS ((rtx *, void *));
687 extern void dump_class PARAMS ((struct table_elt*));
688 static struct cse_reg_info * get_cse_reg_info PARAMS ((unsigned int));
689 static int check_dependence PARAMS ((rtx *, void *));
691 static void flush_hash_table PARAMS ((void));
692 static bool insn_live_p PARAMS ((rtx, int *));
693 static bool set_live_p PARAMS ((rtx, rtx, int *));
694 static bool dead_libcall_p PARAMS ((rtx, int *));
696 /* Dump the expressions in the equivalence class indicated by CLASSP.
697 This function is used only for debugging. */
698 void
699 dump_class (classp)
700 struct table_elt *classp;
702 struct table_elt *elt;
704 fprintf (stderr, "Equivalence chain for ");
705 print_rtl (stderr, classp->exp);
706 fprintf (stderr, ": \n");
708 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
710 print_rtl (stderr, elt->exp);
711 fprintf (stderr, "\n");
715 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
717 static int
718 approx_reg_cost_1 (xp, data)
719 rtx *xp;
720 void *data;
722 rtx x = *xp;
723 regset set = (regset) data;
725 if (x && GET_CODE (x) == REG)
726 SET_REGNO_REG_SET (set, REGNO (x));
727 return 0;
730 /* Return an estimate of the cost of the registers used in an rtx.
731 This is mostly the number of different REG expressions in the rtx;
732 however for some exceptions like fixed registers we use a cost of
733 0. If any other hard register reference occurs, return MAX_COST. */
735 static int
736 approx_reg_cost (x)
737 rtx x;
739 regset_head set;
740 int i;
741 int cost = 0;
742 int hardregs = 0;
744 INIT_REG_SET (&set);
745 for_each_rtx (&x, approx_reg_cost_1, (void *) &set);
747 EXECUTE_IF_SET_IN_REG_SET
748 (&set, 0, i,
750 if (! CHEAP_REGNO (i))
752 if (i < FIRST_PSEUDO_REGISTER)
753 hardregs++;
755 cost += i < FIRST_PSEUDO_REGISTER ? 2 : 1;
759 CLEAR_REG_SET (&set);
760 return hardregs && SMALL_REGISTER_CLASSES ? MAX_COST : cost;
763 /* Return a negative value if an rtx A, whose costs are given by COST_A
764 and REGCOST_A, is more desirable than an rtx B.
765 Return a positive value if A is less desirable, or 0 if the two are
766 equally good. */
767 static int
768 preferrable (cost_a, regcost_a, cost_b, regcost_b)
769 int cost_a, regcost_a, cost_b, regcost_b;
771 /* First, get rid of a cases involving expressions that are entirely
772 unwanted. */
773 if (cost_a != cost_b)
775 if (cost_a == MAX_COST)
776 return 1;
777 if (cost_b == MAX_COST)
778 return -1;
781 /* Avoid extending lifetimes of hardregs. */
782 if (regcost_a != regcost_b)
784 if (regcost_a == MAX_COST)
785 return 1;
786 if (regcost_b == MAX_COST)
787 return -1;
790 /* Normal operation costs take precedence. */
791 if (cost_a != cost_b)
792 return cost_a - cost_b;
793 /* Only if these are identical consider effects on register pressure. */
794 if (regcost_a != regcost_b)
795 return regcost_a - regcost_b;
796 return 0;
799 /* Internal function, to compute cost when X is not a register; called
800 from COST macro to keep it simple. */
802 static int
803 notreg_cost (x, outer)
804 rtx x;
805 enum rtx_code outer;
807 return ((GET_CODE (x) == SUBREG
808 && GET_CODE (SUBREG_REG (x)) == REG
809 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
810 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
811 && (GET_MODE_SIZE (GET_MODE (x))
812 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
813 && subreg_lowpart_p (x)
814 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
815 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
817 : rtx_cost (x, outer) * 2);
820 /* Return an estimate of the cost of computing rtx X.
821 One use is in cse, to decide which expression to keep in the hash table.
822 Another is in rtl generation, to pick the cheapest way to multiply.
823 Other uses like the latter are expected in the future. */
826 rtx_cost (x, outer_code)
827 rtx x;
828 enum rtx_code outer_code ATTRIBUTE_UNUSED;
830 int i, j;
831 enum rtx_code code;
832 const char *fmt;
833 int total;
835 if (x == 0)
836 return 0;
838 /* Compute the default costs of certain things.
839 Note that RTX_COSTS can override the defaults. */
841 code = GET_CODE (x);
842 switch (code)
844 case MULT:
845 total = COSTS_N_INSNS (5);
846 break;
847 case DIV:
848 case UDIV:
849 case MOD:
850 case UMOD:
851 total = COSTS_N_INSNS (7);
852 break;
853 case USE:
854 /* Used in loop.c and combine.c as a marker. */
855 total = 0;
856 break;
857 default:
858 total = COSTS_N_INSNS (1);
861 switch (code)
863 case REG:
864 return 0;
866 case SUBREG:
867 /* If we can't tie these modes, make this expensive. The larger
868 the mode, the more expensive it is. */
869 if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
870 return COSTS_N_INSNS (2
871 + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
872 break;
874 #ifdef RTX_COSTS
875 RTX_COSTS (x, code, outer_code);
876 #endif
877 #ifdef CONST_COSTS
878 CONST_COSTS (x, code, outer_code);
879 #endif
881 default:
882 #ifdef DEFAULT_RTX_COSTS
883 DEFAULT_RTX_COSTS (x, code, outer_code);
884 #endif
885 break;
888 /* Sum the costs of the sub-rtx's, plus cost of this operation,
889 which is already in total. */
891 fmt = GET_RTX_FORMAT (code);
892 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
893 if (fmt[i] == 'e')
894 total += rtx_cost (XEXP (x, i), code);
895 else if (fmt[i] == 'E')
896 for (j = 0; j < XVECLEN (x, i); j++)
897 total += rtx_cost (XVECEXP (x, i, j), code);
899 return total;
902 /* Return cost of address expression X.
903 Expect that X is properly formed address reference. */
906 address_cost (x, mode)
907 rtx x;
908 enum machine_mode mode;
910 /* The ADDRESS_COST macro does not deal with ADDRESSOF nodes. But,
911 during CSE, such nodes are present. Using an ADDRESSOF node which
912 refers to the address of a REG is a good thing because we can then
913 turn (MEM (ADDRESSSOF (REG))) into just plain REG. */
915 if (GET_CODE (x) == ADDRESSOF && REG_P (XEXP ((x), 0)))
916 return -1;
918 /* We may be asked for cost of various unusual addresses, such as operands
919 of push instruction. It is not worthwhile to complicate writing
920 of ADDRESS_COST macro by such cases. */
922 if (!memory_address_p (mode, x))
923 return 1000;
924 #ifdef ADDRESS_COST
925 return ADDRESS_COST (x);
926 #else
927 return rtx_cost (x, MEM);
928 #endif
932 static struct cse_reg_info *
933 get_cse_reg_info (regno)
934 unsigned int regno;
936 struct cse_reg_info **hash_head = &reg_hash[REGHASH_FN (regno)];
937 struct cse_reg_info *p;
939 for (p = *hash_head; p != NULL; p = p->hash_next)
940 if (p->regno == regno)
941 break;
943 if (p == NULL)
945 /* Get a new cse_reg_info structure. */
946 if (cse_reg_info_free_list)
948 p = cse_reg_info_free_list;
949 cse_reg_info_free_list = p->next;
951 else
952 p = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info));
954 /* Insert into hash table. */
955 p->hash_next = *hash_head;
956 *hash_head = p;
958 /* Initialize it. */
959 p->reg_tick = 1;
960 p->reg_in_table = -1;
961 p->reg_qty = regno;
962 p->regno = regno;
963 p->next = cse_reg_info_used_list;
964 cse_reg_info_used_list = p;
965 if (!cse_reg_info_used_list_end)
966 cse_reg_info_used_list_end = p;
969 /* Cache this lookup; we tend to be looking up information about the
970 same register several times in a row. */
971 cached_regno = regno;
972 cached_cse_reg_info = p;
974 return p;
977 /* Clear the hash table and initialize each register with its own quantity,
978 for a new basic block. */
980 static void
981 new_basic_block ()
983 int i;
985 next_qty = max_reg;
987 /* Clear out hash table state for this pass. */
989 memset ((char *) reg_hash, 0, sizeof reg_hash);
991 if (cse_reg_info_used_list)
993 cse_reg_info_used_list_end->next = cse_reg_info_free_list;
994 cse_reg_info_free_list = cse_reg_info_used_list;
995 cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
997 cached_cse_reg_info = 0;
999 CLEAR_HARD_REG_SET (hard_regs_in_table);
1001 /* The per-quantity values used to be initialized here, but it is
1002 much faster to initialize each as it is made in `make_new_qty'. */
1004 for (i = 0; i < HASH_SIZE; i++)
1006 struct table_elt *first;
1008 first = table[i];
1009 if (first != NULL)
1011 struct table_elt *last = first;
1013 table[i] = NULL;
1015 while (last->next_same_hash != NULL)
1016 last = last->next_same_hash;
1018 /* Now relink this hash entire chain into
1019 the free element list. */
1021 last->next_same_hash = free_element_chain;
1022 free_element_chain = first;
1026 prev_insn = 0;
1028 #ifdef HAVE_cc0
1029 prev_insn_cc0 = 0;
1030 #endif
1033 /* Say that register REG contains a quantity in mode MODE not in any
1034 register before and initialize that quantity. */
1036 static void
1037 make_new_qty (reg, mode)
1038 unsigned int reg;
1039 enum machine_mode mode;
1041 int q;
1042 struct qty_table_elem *ent;
1043 struct reg_eqv_elem *eqv;
1045 if (next_qty >= max_qty)
1046 abort ();
1048 q = REG_QTY (reg) = next_qty++;
1049 ent = &qty_table[q];
1050 ent->first_reg = reg;
1051 ent->last_reg = reg;
1052 ent->mode = mode;
1053 ent->const_rtx = ent->const_insn = NULL_RTX;
1054 ent->comparison_code = UNKNOWN;
1056 eqv = &reg_eqv_table[reg];
1057 eqv->next = eqv->prev = -1;
1060 /* Make reg NEW equivalent to reg OLD.
1061 OLD is not changing; NEW is. */
1063 static void
1064 make_regs_eqv (new, old)
1065 unsigned int new, old;
1067 unsigned int lastr, firstr;
1068 int q = REG_QTY (old);
1069 struct qty_table_elem *ent;
1071 ent = &qty_table[q];
1073 /* Nothing should become eqv until it has a "non-invalid" qty number. */
1074 if (! REGNO_QTY_VALID_P (old))
1075 abort ();
1077 REG_QTY (new) = q;
1078 firstr = ent->first_reg;
1079 lastr = ent->last_reg;
1081 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
1082 hard regs. Among pseudos, if NEW will live longer than any other reg
1083 of the same qty, and that is beyond the current basic block,
1084 make it the new canonical replacement for this qty. */
1085 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
1086 /* Certain fixed registers might be of the class NO_REGS. This means
1087 that not only can they not be allocated by the compiler, but
1088 they cannot be used in substitutions or canonicalizations
1089 either. */
1090 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
1091 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
1092 || (new >= FIRST_PSEUDO_REGISTER
1093 && (firstr < FIRST_PSEUDO_REGISTER
1094 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
1095 || (uid_cuid[REGNO_FIRST_UID (new)]
1096 < cse_basic_block_start))
1097 && (uid_cuid[REGNO_LAST_UID (new)]
1098 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
1100 reg_eqv_table[firstr].prev = new;
1101 reg_eqv_table[new].next = firstr;
1102 reg_eqv_table[new].prev = -1;
1103 ent->first_reg = new;
1105 else
1107 /* If NEW is a hard reg (known to be non-fixed), insert at end.
1108 Otherwise, insert before any non-fixed hard regs that are at the
1109 end. Registers of class NO_REGS cannot be used as an
1110 equivalent for anything. */
1111 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
1112 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
1113 && new >= FIRST_PSEUDO_REGISTER)
1114 lastr = reg_eqv_table[lastr].prev;
1115 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
1116 if (reg_eqv_table[lastr].next >= 0)
1117 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
1118 else
1119 qty_table[q].last_reg = new;
1120 reg_eqv_table[lastr].next = new;
1121 reg_eqv_table[new].prev = lastr;
1125 /* Remove REG from its equivalence class. */
1127 static void
1128 delete_reg_equiv (reg)
1129 unsigned int reg;
1131 struct qty_table_elem *ent;
1132 int q = REG_QTY (reg);
1133 int p, n;
1135 /* If invalid, do nothing. */
1136 if (q == (int) reg)
1137 return;
1139 ent = &qty_table[q];
1141 p = reg_eqv_table[reg].prev;
1142 n = reg_eqv_table[reg].next;
1144 if (n != -1)
1145 reg_eqv_table[n].prev = p;
1146 else
1147 ent->last_reg = p;
1148 if (p != -1)
1149 reg_eqv_table[p].next = n;
1150 else
1151 ent->first_reg = n;
1153 REG_QTY (reg) = reg;
1156 /* Remove any invalid expressions from the hash table
1157 that refer to any of the registers contained in expression X.
1159 Make sure that newly inserted references to those registers
1160 as subexpressions will be considered valid.
1162 mention_regs is not called when a register itself
1163 is being stored in the table.
1165 Return 1 if we have done something that may have changed the hash code
1166 of X. */
1168 static int
1169 mention_regs (x)
1170 rtx x;
1172 enum rtx_code code;
1173 int i, j;
1174 const char *fmt;
1175 int changed = 0;
1177 if (x == 0)
1178 return 0;
1180 code = GET_CODE (x);
1181 if (code == REG)
1183 unsigned int regno = REGNO (x);
1184 unsigned int endregno
1185 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1186 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
1187 unsigned int i;
1189 for (i = regno; i < endregno; i++)
1191 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1192 remove_invalid_refs (i);
1194 REG_IN_TABLE (i) = REG_TICK (i);
1197 return 0;
1200 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1201 pseudo if they don't use overlapping words. We handle only pseudos
1202 here for simplicity. */
1203 if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1204 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1206 unsigned int i = REGNO (SUBREG_REG (x));
1208 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1210 /* If reg_tick has been incremented more than once since
1211 reg_in_table was last set, that means that the entire
1212 register has been set before, so discard anything memorized
1213 for the entire register, including all SUBREG expressions. */
1214 if (REG_IN_TABLE (i) != REG_TICK (i) - 1)
1215 remove_invalid_refs (i);
1216 else
1217 remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1220 REG_IN_TABLE (i) = REG_TICK (i);
1221 return 0;
1224 /* If X is a comparison or a COMPARE and either operand is a register
1225 that does not have a quantity, give it one. This is so that a later
1226 call to record_jump_equiv won't cause X to be assigned a different
1227 hash code and not found in the table after that call.
1229 It is not necessary to do this here, since rehash_using_reg can
1230 fix up the table later, but doing this here eliminates the need to
1231 call that expensive function in the most common case where the only
1232 use of the register is in the comparison. */
1234 if (code == COMPARE || GET_RTX_CLASS (code) == '<')
1236 if (GET_CODE (XEXP (x, 0)) == REG
1237 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1238 if (insert_regs (XEXP (x, 0), NULL, 0))
1240 rehash_using_reg (XEXP (x, 0));
1241 changed = 1;
1244 if (GET_CODE (XEXP (x, 1)) == REG
1245 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1246 if (insert_regs (XEXP (x, 1), NULL, 0))
1248 rehash_using_reg (XEXP (x, 1));
1249 changed = 1;
1253 fmt = GET_RTX_FORMAT (code);
1254 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1255 if (fmt[i] == 'e')
1256 changed |= mention_regs (XEXP (x, i));
1257 else if (fmt[i] == 'E')
1258 for (j = 0; j < XVECLEN (x, i); j++)
1259 changed |= mention_regs (XVECEXP (x, i, j));
1261 return changed;
1264 /* Update the register quantities for inserting X into the hash table
1265 with a value equivalent to CLASSP.
1266 (If the class does not contain a REG, it is irrelevant.)
1267 If MODIFIED is nonzero, X is a destination; it is being modified.
1268 Note that delete_reg_equiv should be called on a register
1269 before insert_regs is done on that register with MODIFIED != 0.
1271 Nonzero value means that elements of reg_qty have changed
1272 so X's hash code may be different. */
1274 static int
1275 insert_regs (x, classp, modified)
1276 rtx x;
1277 struct table_elt *classp;
1278 int modified;
1280 if (GET_CODE (x) == REG)
1282 unsigned int regno = REGNO (x);
1283 int qty_valid;
1285 /* If REGNO is in the equivalence table already but is of the
1286 wrong mode for that equivalence, don't do anything here. */
1288 qty_valid = REGNO_QTY_VALID_P (regno);
1289 if (qty_valid)
1291 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1293 if (ent->mode != GET_MODE (x))
1294 return 0;
1297 if (modified || ! qty_valid)
1299 if (classp)
1300 for (classp = classp->first_same_value;
1301 classp != 0;
1302 classp = classp->next_same_value)
1303 if (GET_CODE (classp->exp) == REG
1304 && GET_MODE (classp->exp) == GET_MODE (x))
1306 make_regs_eqv (regno, REGNO (classp->exp));
1307 return 1;
1310 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1311 than REG_IN_TABLE to find out if there was only a single preceding
1312 invalidation - for the SUBREG - or another one, which would be
1313 for the full register. However, if we find here that REG_TICK
1314 indicates that the register is invalid, it means that it has
1315 been invalidated in a separate operation. The SUBREG might be used
1316 now (then this is a recursive call), or we might use the full REG
1317 now and a SUBREG of it later. So bump up REG_TICK so that
1318 mention_regs will do the right thing. */
1319 if (! modified
1320 && REG_IN_TABLE (regno) >= 0
1321 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1322 REG_TICK (regno)++;
1323 make_new_qty (regno, GET_MODE (x));
1324 return 1;
1327 return 0;
1330 /* If X is a SUBREG, we will likely be inserting the inner register in the
1331 table. If that register doesn't have an assigned quantity number at
1332 this point but does later, the insertion that we will be doing now will
1333 not be accessible because its hash code will have changed. So assign
1334 a quantity number now. */
1336 else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1337 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1339 insert_regs (SUBREG_REG (x), NULL, 0);
1340 mention_regs (x);
1341 return 1;
1343 else
1344 return mention_regs (x);
1347 /* Look in or update the hash table. */
1349 /* Remove table element ELT from use in the table.
1350 HASH is its hash code, made using the HASH macro.
1351 It's an argument because often that is known in advance
1352 and we save much time not recomputing it. */
1354 static void
1355 remove_from_table (elt, hash)
1356 struct table_elt *elt;
1357 unsigned hash;
1359 if (elt == 0)
1360 return;
1362 /* Mark this element as removed. See cse_insn. */
1363 elt->first_same_value = 0;
1365 /* Remove the table element from its equivalence class. */
1368 struct table_elt *prev = elt->prev_same_value;
1369 struct table_elt *next = elt->next_same_value;
1371 if (next)
1372 next->prev_same_value = prev;
1374 if (prev)
1375 prev->next_same_value = next;
1376 else
1378 struct table_elt *newfirst = next;
1379 while (next)
1381 next->first_same_value = newfirst;
1382 next = next->next_same_value;
1387 /* Remove the table element from its hash bucket. */
1390 struct table_elt *prev = elt->prev_same_hash;
1391 struct table_elt *next = elt->next_same_hash;
1393 if (next)
1394 next->prev_same_hash = prev;
1396 if (prev)
1397 prev->next_same_hash = next;
1398 else if (table[hash] == elt)
1399 table[hash] = next;
1400 else
1402 /* This entry is not in the proper hash bucket. This can happen
1403 when two classes were merged by `merge_equiv_classes'. Search
1404 for the hash bucket that it heads. This happens only very
1405 rarely, so the cost is acceptable. */
1406 for (hash = 0; hash < HASH_SIZE; hash++)
1407 if (table[hash] == elt)
1408 table[hash] = next;
1412 /* Remove the table element from its related-value circular chain. */
1414 if (elt->related_value != 0 && elt->related_value != elt)
1416 struct table_elt *p = elt->related_value;
1418 while (p->related_value != elt)
1419 p = p->related_value;
1420 p->related_value = elt->related_value;
1421 if (p->related_value == p)
1422 p->related_value = 0;
1425 /* Now add it to the free element chain. */
1426 elt->next_same_hash = free_element_chain;
1427 free_element_chain = elt;
1430 /* Look up X in the hash table and return its table element,
1431 or 0 if X is not in the table.
1433 MODE is the machine-mode of X, or if X is an integer constant
1434 with VOIDmode then MODE is the mode with which X will be used.
1436 Here we are satisfied to find an expression whose tree structure
1437 looks like X. */
1439 static struct table_elt *
1440 lookup (x, hash, mode)
1441 rtx x;
1442 unsigned hash;
1443 enum machine_mode mode;
1445 struct table_elt *p;
1447 for (p = table[hash]; p; p = p->next_same_hash)
1448 if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
1449 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
1450 return p;
1452 return 0;
1455 /* Like `lookup' but don't care whether the table element uses invalid regs.
1456 Also ignore discrepancies in the machine mode of a register. */
1458 static struct table_elt *
1459 lookup_for_remove (x, hash, mode)
1460 rtx x;
1461 unsigned hash;
1462 enum machine_mode mode;
1464 struct table_elt *p;
1466 if (GET_CODE (x) == REG)
1468 unsigned int regno = REGNO (x);
1470 /* Don't check the machine mode when comparing registers;
1471 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1472 for (p = table[hash]; p; p = p->next_same_hash)
1473 if (GET_CODE (p->exp) == REG
1474 && REGNO (p->exp) == regno)
1475 return p;
1477 else
1479 for (p = table[hash]; p; p = p->next_same_hash)
1480 if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
1481 return p;
1484 return 0;
1487 /* Look for an expression equivalent to X and with code CODE.
1488 If one is found, return that expression. */
1490 static rtx
1491 lookup_as_function (x, code)
1492 rtx x;
1493 enum rtx_code code;
1495 struct table_elt *p
1496 = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, GET_MODE (x));
1498 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1499 long as we are narrowing. So if we looked in vain for a mode narrower
1500 than word_mode before, look for word_mode now. */
1501 if (p == 0 && code == CONST_INT
1502 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1504 x = copy_rtx (x);
1505 PUT_MODE (x, word_mode);
1506 p = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, word_mode);
1509 if (p == 0)
1510 return 0;
1512 for (p = p->first_same_value; p; p = p->next_same_value)
1513 if (GET_CODE (p->exp) == code
1514 /* Make sure this is a valid entry in the table. */
1515 && exp_equiv_p (p->exp, p->exp, 1, 0))
1516 return p->exp;
1518 return 0;
1521 /* Insert X in the hash table, assuming HASH is its hash code
1522 and CLASSP is an element of the class it should go in
1523 (or 0 if a new class should be made).
1524 It is inserted at the proper position to keep the class in
1525 the order cheapest first.
1527 MODE is the machine-mode of X, or if X is an integer constant
1528 with VOIDmode then MODE is the mode with which X will be used.
1530 For elements of equal cheapness, the most recent one
1531 goes in front, except that the first element in the list
1532 remains first unless a cheaper element is added. The order of
1533 pseudo-registers does not matter, as canon_reg will be called to
1534 find the cheapest when a register is retrieved from the table.
1536 The in_memory field in the hash table element is set to 0.
1537 The caller must set it nonzero if appropriate.
1539 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1540 and if insert_regs returns a nonzero value
1541 you must then recompute its hash code before calling here.
1543 If necessary, update table showing constant values of quantities. */
1545 #define CHEAPER(X, Y) \
1546 (preferrable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1548 static struct table_elt *
1549 insert (x, classp, hash, mode)
1550 rtx x;
1551 struct table_elt *classp;
1552 unsigned hash;
1553 enum machine_mode mode;
1555 struct table_elt *elt;
1557 /* If X is a register and we haven't made a quantity for it,
1558 something is wrong. */
1559 if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
1560 abort ();
1562 /* If X is a hard register, show it is being put in the table. */
1563 if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
1565 unsigned int regno = REGNO (x);
1566 unsigned int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1567 unsigned int i;
1569 for (i = regno; i < endregno; i++)
1570 SET_HARD_REG_BIT (hard_regs_in_table, i);
1573 /* Put an element for X into the right hash bucket. */
1575 elt = free_element_chain;
1576 if (elt)
1577 free_element_chain = elt->next_same_hash;
1578 else
1580 n_elements_made++;
1581 elt = (struct table_elt *) xmalloc (sizeof (struct table_elt));
1584 elt->exp = x;
1585 elt->canon_exp = NULL_RTX;
1586 elt->cost = COST (x);
1587 elt->regcost = approx_reg_cost (x);
1588 elt->next_same_value = 0;
1589 elt->prev_same_value = 0;
1590 elt->next_same_hash = table[hash];
1591 elt->prev_same_hash = 0;
1592 elt->related_value = 0;
1593 elt->in_memory = 0;
1594 elt->mode = mode;
1595 elt->is_const = (CONSTANT_P (x)
1596 /* GNU C++ takes advantage of this for `this'
1597 (and other const values). */
1598 || (GET_CODE (x) == REG
1599 && RTX_UNCHANGING_P (x)
1600 && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1601 || FIXED_BASE_PLUS_P (x));
1603 if (table[hash])
1604 table[hash]->prev_same_hash = elt;
1605 table[hash] = elt;
1607 /* Put it into the proper value-class. */
1608 if (classp)
1610 classp = classp->first_same_value;
1611 if (CHEAPER (elt, classp))
1612 /* Insert at the head of the class */
1614 struct table_elt *p;
1615 elt->next_same_value = classp;
1616 classp->prev_same_value = elt;
1617 elt->first_same_value = elt;
1619 for (p = classp; p; p = p->next_same_value)
1620 p->first_same_value = elt;
1622 else
1624 /* Insert not at head of the class. */
1625 /* Put it after the last element cheaper than X. */
1626 struct table_elt *p, *next;
1628 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1629 p = next);
1631 /* Put it after P and before NEXT. */
1632 elt->next_same_value = next;
1633 if (next)
1634 next->prev_same_value = elt;
1636 elt->prev_same_value = p;
1637 p->next_same_value = elt;
1638 elt->first_same_value = classp;
1641 else
1642 elt->first_same_value = elt;
1644 /* If this is a constant being set equivalent to a register or a register
1645 being set equivalent to a constant, note the constant equivalence.
1647 If this is a constant, it cannot be equivalent to a different constant,
1648 and a constant is the only thing that can be cheaper than a register. So
1649 we know the register is the head of the class (before the constant was
1650 inserted).
1652 If this is a register that is not already known equivalent to a
1653 constant, we must check the entire class.
1655 If this is a register that is already known equivalent to an insn,
1656 update the qtys `const_insn' to show that `this_insn' is the latest
1657 insn making that quantity equivalent to the constant. */
1659 if (elt->is_const && classp && GET_CODE (classp->exp) == REG
1660 && GET_CODE (x) != REG)
1662 int exp_q = REG_QTY (REGNO (classp->exp));
1663 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1665 exp_ent->const_rtx = gen_lowpart_if_possible (exp_ent->mode, x);
1666 exp_ent->const_insn = this_insn;
1669 else if (GET_CODE (x) == REG
1670 && classp
1671 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1672 && ! elt->is_const)
1674 struct table_elt *p;
1676 for (p = classp; p != 0; p = p->next_same_value)
1678 if (p->is_const && GET_CODE (p->exp) != REG)
1680 int x_q = REG_QTY (REGNO (x));
1681 struct qty_table_elem *x_ent = &qty_table[x_q];
1683 x_ent->const_rtx
1684 = gen_lowpart_if_possible (GET_MODE (x), p->exp);
1685 x_ent->const_insn = this_insn;
1686 break;
1691 else if (GET_CODE (x) == REG
1692 && qty_table[REG_QTY (REGNO (x))].const_rtx
1693 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1694 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1696 /* If this is a constant with symbolic value,
1697 and it has a term with an explicit integer value,
1698 link it up with related expressions. */
1699 if (GET_CODE (x) == CONST)
1701 rtx subexp = get_related_value (x);
1702 unsigned subhash;
1703 struct table_elt *subelt, *subelt_prev;
1705 if (subexp != 0)
1707 /* Get the integer-free subexpression in the hash table. */
1708 subhash = safe_hash (subexp, mode) & HASH_MASK;
1709 subelt = lookup (subexp, subhash, mode);
1710 if (subelt == 0)
1711 subelt = insert (subexp, NULL, subhash, mode);
1712 /* Initialize SUBELT's circular chain if it has none. */
1713 if (subelt->related_value == 0)
1714 subelt->related_value = subelt;
1715 /* Find the element in the circular chain that precedes SUBELT. */
1716 subelt_prev = subelt;
1717 while (subelt_prev->related_value != subelt)
1718 subelt_prev = subelt_prev->related_value;
1719 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1720 This way the element that follows SUBELT is the oldest one. */
1721 elt->related_value = subelt_prev->related_value;
1722 subelt_prev->related_value = elt;
1726 return elt;
1729 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1730 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1731 the two classes equivalent.
1733 CLASS1 will be the surviving class; CLASS2 should not be used after this
1734 call.
1736 Any invalid entries in CLASS2 will not be copied. */
1738 static void
1739 merge_equiv_classes (class1, class2)
1740 struct table_elt *class1, *class2;
1742 struct table_elt *elt, *next, *new;
1744 /* Ensure we start with the head of the classes. */
1745 class1 = class1->first_same_value;
1746 class2 = class2->first_same_value;
1748 /* If they were already equal, forget it. */
1749 if (class1 == class2)
1750 return;
1752 for (elt = class2; elt; elt = next)
1754 unsigned int hash;
1755 rtx exp = elt->exp;
1756 enum machine_mode mode = elt->mode;
1758 next = elt->next_same_value;
1760 /* Remove old entry, make a new one in CLASS1's class.
1761 Don't do this for invalid entries as we cannot find their
1762 hash code (it also isn't necessary). */
1763 if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
1765 hash_arg_in_memory = 0;
1766 hash = HASH (exp, mode);
1768 if (GET_CODE (exp) == REG)
1769 delete_reg_equiv (REGNO (exp));
1771 remove_from_table (elt, hash);
1773 if (insert_regs (exp, class1, 0))
1775 rehash_using_reg (exp);
1776 hash = HASH (exp, mode);
1778 new = insert (exp, class1, hash, mode);
1779 new->in_memory = hash_arg_in_memory;
1784 /* Flush the entire hash table. */
1786 static void
1787 flush_hash_table ()
1789 int i;
1790 struct table_elt *p;
1792 for (i = 0; i < HASH_SIZE; i++)
1793 for (p = table[i]; p; p = table[i])
1795 /* Note that invalidate can remove elements
1796 after P in the current hash chain. */
1797 if (GET_CODE (p->exp) == REG)
1798 invalidate (p->exp, p->mode);
1799 else
1800 remove_from_table (p, i);
1804 /* Function called for each rtx to check whether true dependence exist. */
1805 struct check_dependence_data
1807 enum machine_mode mode;
1808 rtx exp;
1811 static int
1812 check_dependence (x, data)
1813 rtx *x;
1814 void *data;
1816 struct check_dependence_data *d = (struct check_dependence_data *) data;
1817 if (*x && GET_CODE (*x) == MEM)
1818 return true_dependence (d->exp, d->mode, *x, cse_rtx_varies_p);
1819 else
1820 return 0;
1823 /* Remove from the hash table, or mark as invalid, all expressions whose
1824 values could be altered by storing in X. X is a register, a subreg, or
1825 a memory reference with nonvarying address (because, when a memory
1826 reference with a varying address is stored in, all memory references are
1827 removed by invalidate_memory so specific invalidation is superfluous).
1828 FULL_MODE, if not VOIDmode, indicates that this much should be
1829 invalidated instead of just the amount indicated by the mode of X. This
1830 is only used for bitfield stores into memory.
1832 A nonvarying address may be just a register or just a symbol reference,
1833 or it may be either of those plus a numeric offset. */
1835 static void
1836 invalidate (x, full_mode)
1837 rtx x;
1838 enum machine_mode full_mode;
1840 int i;
1841 struct table_elt *p;
1843 switch (GET_CODE (x))
1845 case REG:
1847 /* If X is a register, dependencies on its contents are recorded
1848 through the qty number mechanism. Just change the qty number of
1849 the register, mark it as invalid for expressions that refer to it,
1850 and remove it itself. */
1851 unsigned int regno = REGNO (x);
1852 unsigned int hash = HASH (x, GET_MODE (x));
1854 /* Remove REGNO from any quantity list it might be on and indicate
1855 that its value might have changed. If it is a pseudo, remove its
1856 entry from the hash table.
1858 For a hard register, we do the first two actions above for any
1859 additional hard registers corresponding to X. Then, if any of these
1860 registers are in the table, we must remove any REG entries that
1861 overlap these registers. */
1863 delete_reg_equiv (regno);
1864 REG_TICK (regno)++;
1866 if (regno >= FIRST_PSEUDO_REGISTER)
1868 /* Because a register can be referenced in more than one mode,
1869 we might have to remove more than one table entry. */
1870 struct table_elt *elt;
1872 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1873 remove_from_table (elt, hash);
1875 else
1877 HOST_WIDE_INT in_table
1878 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1879 unsigned int endregno
1880 = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1881 unsigned int tregno, tendregno, rn;
1882 struct table_elt *p, *next;
1884 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1886 for (rn = regno + 1; rn < endregno; rn++)
1888 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1889 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1890 delete_reg_equiv (rn);
1891 REG_TICK (rn)++;
1894 if (in_table)
1895 for (hash = 0; hash < HASH_SIZE; hash++)
1896 for (p = table[hash]; p; p = next)
1898 next = p->next_same_hash;
1900 if (GET_CODE (p->exp) != REG
1901 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1902 continue;
1904 tregno = REGNO (p->exp);
1905 tendregno
1906 = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
1907 if (tendregno > regno && tregno < endregno)
1908 remove_from_table (p, hash);
1912 return;
1914 case SUBREG:
1915 invalidate (SUBREG_REG (x), VOIDmode);
1916 return;
1918 case PARALLEL:
1919 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1920 invalidate (XVECEXP (x, 0, i), VOIDmode);
1921 return;
1923 case EXPR_LIST:
1924 /* This is part of a disjoint return value; extract the location in
1925 question ignoring the offset. */
1926 invalidate (XEXP (x, 0), VOIDmode);
1927 return;
1929 case MEM:
1930 /* Calculate the canonical version of X here so that
1931 true_dependence doesn't generate new RTL for X on each call. */
1932 x = canon_rtx (x);
1934 /* Remove all hash table elements that refer to overlapping pieces of
1935 memory. */
1936 if (full_mode == VOIDmode)
1937 full_mode = GET_MODE (x);
1939 for (i = 0; i < HASH_SIZE; i++)
1941 struct table_elt *next;
1943 for (p = table[i]; p; p = next)
1945 next = p->next_same_hash;
1946 if (p->in_memory)
1948 struct check_dependence_data d;
1950 /* Just canonicalize the expression once;
1951 otherwise each time we call invalidate
1952 true_dependence will canonicalize the
1953 expression again. */
1954 if (!p->canon_exp)
1955 p->canon_exp = canon_rtx (p->exp);
1956 d.exp = x;
1957 d.mode = full_mode;
1958 if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1959 remove_from_table (p, i);
1963 return;
1965 default:
1966 abort ();
1970 /* Remove all expressions that refer to register REGNO,
1971 since they are already invalid, and we are about to
1972 mark that register valid again and don't want the old
1973 expressions to reappear as valid. */
1975 static void
1976 remove_invalid_refs (regno)
1977 unsigned int regno;
1979 unsigned int i;
1980 struct table_elt *p, *next;
1982 for (i = 0; i < HASH_SIZE; i++)
1983 for (p = table[i]; p; p = next)
1985 next = p->next_same_hash;
1986 if (GET_CODE (p->exp) != REG
1987 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1988 remove_from_table (p, i);
1992 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1993 and mode MODE. */
1994 static void
1995 remove_invalid_subreg_refs (regno, offset, mode)
1996 unsigned int regno;
1997 unsigned int offset;
1998 enum machine_mode mode;
2000 unsigned int i;
2001 struct table_elt *p, *next;
2002 unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
2004 for (i = 0; i < HASH_SIZE; i++)
2005 for (p = table[i]; p; p = next)
2007 rtx exp = p->exp;
2008 next = p->next_same_hash;
2010 if (GET_CODE (exp) != REG
2011 && (GET_CODE (exp) != SUBREG
2012 || GET_CODE (SUBREG_REG (exp)) != REG
2013 || REGNO (SUBREG_REG (exp)) != regno
2014 || (((SUBREG_BYTE (exp)
2015 + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
2016 && SUBREG_BYTE (exp) <= end))
2017 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
2018 remove_from_table (p, i);
2022 /* Recompute the hash codes of any valid entries in the hash table that
2023 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
2025 This is called when we make a jump equivalence. */
2027 static void
2028 rehash_using_reg (x)
2029 rtx x;
2031 unsigned int i;
2032 struct table_elt *p, *next;
2033 unsigned hash;
2035 if (GET_CODE (x) == SUBREG)
2036 x = SUBREG_REG (x);
2038 /* If X is not a register or if the register is known not to be in any
2039 valid entries in the table, we have no work to do. */
2041 if (GET_CODE (x) != REG
2042 || REG_IN_TABLE (REGNO (x)) < 0
2043 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
2044 return;
2046 /* Scan all hash chains looking for valid entries that mention X.
2047 If we find one and it is in the wrong hash chain, move it. We can skip
2048 objects that are registers, since they are handled specially. */
2050 for (i = 0; i < HASH_SIZE; i++)
2051 for (p = table[i]; p; p = next)
2053 next = p->next_same_hash;
2054 if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
2055 && exp_equiv_p (p->exp, p->exp, 1, 0)
2056 && i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
2058 if (p->next_same_hash)
2059 p->next_same_hash->prev_same_hash = p->prev_same_hash;
2061 if (p->prev_same_hash)
2062 p->prev_same_hash->next_same_hash = p->next_same_hash;
2063 else
2064 table[i] = p->next_same_hash;
2066 p->next_same_hash = table[hash];
2067 p->prev_same_hash = 0;
2068 if (table[hash])
2069 table[hash]->prev_same_hash = p;
2070 table[hash] = p;
2075 /* Remove from the hash table any expression that is a call-clobbered
2076 register. Also update their TICK values. */
2078 static void
2079 invalidate_for_call ()
2081 unsigned int regno, endregno;
2082 unsigned int i;
2083 unsigned hash;
2084 struct table_elt *p, *next;
2085 int in_table = 0;
2087 /* Go through all the hard registers. For each that is clobbered in
2088 a CALL_INSN, remove the register from quantity chains and update
2089 reg_tick if defined. Also see if any of these registers is currently
2090 in the table. */
2092 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2093 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2095 delete_reg_equiv (regno);
2096 if (REG_TICK (regno) >= 0)
2097 REG_TICK (regno)++;
2099 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2102 /* In the case where we have no call-clobbered hard registers in the
2103 table, we are done. Otherwise, scan the table and remove any
2104 entry that overlaps a call-clobbered register. */
2106 if (in_table)
2107 for (hash = 0; hash < HASH_SIZE; hash++)
2108 for (p = table[hash]; p; p = next)
2110 next = p->next_same_hash;
2112 if (GET_CODE (p->exp) != REG
2113 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2114 continue;
2116 regno = REGNO (p->exp);
2117 endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
2119 for (i = regno; i < endregno; i++)
2120 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2122 remove_from_table (p, hash);
2123 break;
2128 /* Given an expression X of type CONST,
2129 and ELT which is its table entry (or 0 if it
2130 is not in the hash table),
2131 return an alternate expression for X as a register plus integer.
2132 If none can be found, return 0. */
2134 static rtx
2135 use_related_value (x, elt)
2136 rtx x;
2137 struct table_elt *elt;
2139 struct table_elt *relt = 0;
2140 struct table_elt *p, *q;
2141 HOST_WIDE_INT offset;
2143 /* First, is there anything related known?
2144 If we have a table element, we can tell from that.
2145 Otherwise, must look it up. */
2147 if (elt != 0 && elt->related_value != 0)
2148 relt = elt;
2149 else if (elt == 0 && GET_CODE (x) == CONST)
2151 rtx subexp = get_related_value (x);
2152 if (subexp != 0)
2153 relt = lookup (subexp,
2154 safe_hash (subexp, GET_MODE (subexp)) & HASH_MASK,
2155 GET_MODE (subexp));
2158 if (relt == 0)
2159 return 0;
2161 /* Search all related table entries for one that has an
2162 equivalent register. */
2164 p = relt;
2165 while (1)
2167 /* This loop is strange in that it is executed in two different cases.
2168 The first is when X is already in the table. Then it is searching
2169 the RELATED_VALUE list of X's class (RELT). The second case is when
2170 X is not in the table. Then RELT points to a class for the related
2171 value.
2173 Ensure that, whatever case we are in, that we ignore classes that have
2174 the same value as X. */
2176 if (rtx_equal_p (x, p->exp))
2177 q = 0;
2178 else
2179 for (q = p->first_same_value; q; q = q->next_same_value)
2180 if (GET_CODE (q->exp) == REG)
2181 break;
2183 if (q)
2184 break;
2186 p = p->related_value;
2188 /* We went all the way around, so there is nothing to be found.
2189 Alternatively, perhaps RELT was in the table for some other reason
2190 and it has no related values recorded. */
2191 if (p == relt || p == 0)
2192 break;
2195 if (q == 0)
2196 return 0;
2198 offset = (get_integer_term (x) - get_integer_term (p->exp));
2199 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2200 return plus_constant (q->exp, offset);
2203 /* Hash a string. Just add its bytes up. */
2204 static inline unsigned
2205 canon_hash_string (ps)
2206 const char *ps;
2208 unsigned hash = 0;
2209 const unsigned char *p = (const unsigned char *) ps;
2211 if (p)
2212 while (*p)
2213 hash += *p++;
2215 return hash;
2218 /* Hash an rtx. We are careful to make sure the value is never negative.
2219 Equivalent registers hash identically.
2220 MODE is used in hashing for CONST_INTs only;
2221 otherwise the mode of X is used.
2223 Store 1 in do_not_record if any subexpression is volatile.
2225 Store 1 in hash_arg_in_memory if X contains a MEM rtx
2226 which does not have the RTX_UNCHANGING_P bit set.
2228 Note that cse_insn knows that the hash code of a MEM expression
2229 is just (int) MEM plus the hash code of the address. */
2231 static unsigned
2232 canon_hash (x, mode)
2233 rtx x;
2234 enum machine_mode mode;
2236 int i, j;
2237 unsigned hash = 0;
2238 enum rtx_code code;
2239 const char *fmt;
2241 /* repeat is used to turn tail-recursion into iteration. */
2242 repeat:
2243 if (x == 0)
2244 return hash;
2246 code = GET_CODE (x);
2247 switch (code)
2249 case REG:
2251 unsigned int regno = REGNO (x);
2253 /* On some machines, we can't record any non-fixed hard register,
2254 because extending its life will cause reload problems. We
2255 consider ap, fp, and sp to be fixed for this purpose.
2257 We also consider CCmode registers to be fixed for this purpose;
2258 failure to do so leads to failure to simplify 0<100 type of
2259 conditionals.
2261 On all machines, we can't record any global registers.
2262 Nor should we record any register that is in a small
2263 class, as defined by CLASS_LIKELY_SPILLED_P. */
2265 if (regno < FIRST_PSEUDO_REGISTER
2266 && (global_regs[regno]
2267 || CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno))
2268 || (SMALL_REGISTER_CLASSES
2269 && ! fixed_regs[regno]
2270 && x != frame_pointer_rtx
2271 && x != hard_frame_pointer_rtx
2272 && x != arg_pointer_rtx
2273 && x != stack_pointer_rtx
2274 && GET_MODE_CLASS (GET_MODE (x)) != MODE_CC)))
2276 do_not_record = 1;
2277 return 0;
2280 hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno);
2281 return hash;
2284 /* We handle SUBREG of a REG specially because the underlying
2285 reg changes its hash value with every value change; we don't
2286 want to have to forget unrelated subregs when one subreg changes. */
2287 case SUBREG:
2289 if (GET_CODE (SUBREG_REG (x)) == REG)
2291 hash += (((unsigned) SUBREG << 7)
2292 + REGNO (SUBREG_REG (x))
2293 + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2294 return hash;
2296 break;
2299 case CONST_INT:
2301 unsigned HOST_WIDE_INT tem = INTVAL (x);
2302 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
2303 return hash;
2306 case CONST_DOUBLE:
2307 /* This is like the general case, except that it only counts
2308 the integers representing the constant. */
2309 hash += (unsigned) code + (unsigned) GET_MODE (x);
2310 if (GET_MODE (x) != VOIDmode)
2311 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2313 unsigned HOST_WIDE_INT tem = XWINT (x, i);
2314 hash += tem;
2316 else
2317 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2318 + (unsigned) CONST_DOUBLE_HIGH (x));
2319 return hash;
2321 case CONST_VECTOR:
2323 int units;
2324 rtx elt;
2326 units = CONST_VECTOR_NUNITS (x);
2328 for (i = 0; i < units; ++i)
2330 elt = CONST_VECTOR_ELT (x, i);
2331 hash += canon_hash (elt, GET_MODE (elt));
2334 return hash;
2337 /* Assume there is only one rtx object for any given label. */
2338 case LABEL_REF:
2339 hash += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2340 return hash;
2342 case SYMBOL_REF:
2343 hash += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2344 return hash;
2346 case MEM:
2347 /* We don't record if marked volatile or if BLKmode since we don't
2348 know the size of the move. */
2349 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2351 do_not_record = 1;
2352 return 0;
2354 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
2356 hash_arg_in_memory = 1;
2358 /* Now that we have already found this special case,
2359 might as well speed it up as much as possible. */
2360 hash += (unsigned) MEM;
2361 x = XEXP (x, 0);
2362 goto repeat;
2364 case USE:
2365 /* A USE that mentions non-volatile memory needs special
2366 handling since the MEM may be BLKmode which normally
2367 prevents an entry from being made. Pure calls are
2368 marked by a USE which mentions BLKmode memory. */
2369 if (GET_CODE (XEXP (x, 0)) == MEM
2370 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2372 hash += (unsigned) USE;
2373 x = XEXP (x, 0);
2375 if (! RTX_UNCHANGING_P (x) || FIXED_BASE_PLUS_P (XEXP (x, 0)))
2376 hash_arg_in_memory = 1;
2378 /* Now that we have already found this special case,
2379 might as well speed it up as much as possible. */
2380 hash += (unsigned) MEM;
2381 x = XEXP (x, 0);
2382 goto repeat;
2384 break;
2386 case PRE_DEC:
2387 case PRE_INC:
2388 case POST_DEC:
2389 case POST_INC:
2390 case PRE_MODIFY:
2391 case POST_MODIFY:
2392 case PC:
2393 case CC0:
2394 case CALL:
2395 case UNSPEC_VOLATILE:
2396 do_not_record = 1;
2397 return 0;
2399 case ASM_OPERANDS:
2400 if (MEM_VOLATILE_P (x))
2402 do_not_record = 1;
2403 return 0;
2405 else
2407 /* We don't want to take the filename and line into account. */
2408 hash += (unsigned) code + (unsigned) GET_MODE (x)
2409 + canon_hash_string (ASM_OPERANDS_TEMPLATE (x))
2410 + canon_hash_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2411 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2413 if (ASM_OPERANDS_INPUT_LENGTH (x))
2415 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2417 hash += (canon_hash (ASM_OPERANDS_INPUT (x, i),
2418 GET_MODE (ASM_OPERANDS_INPUT (x, i)))
2419 + canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT
2420 (x, i)));
2423 hash += canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2424 x = ASM_OPERANDS_INPUT (x, 0);
2425 mode = GET_MODE (x);
2426 goto repeat;
2429 return hash;
2431 break;
2433 default:
2434 break;
2437 i = GET_RTX_LENGTH (code) - 1;
2438 hash += (unsigned) code + (unsigned) GET_MODE (x);
2439 fmt = GET_RTX_FORMAT (code);
2440 for (; i >= 0; i--)
2442 if (fmt[i] == 'e')
2444 rtx tem = XEXP (x, i);
2446 /* If we are about to do the last recursive call
2447 needed at this level, change it into iteration.
2448 This function is called enough to be worth it. */
2449 if (i == 0)
2451 x = tem;
2452 goto repeat;
2454 hash += canon_hash (tem, 0);
2456 else if (fmt[i] == 'E')
2457 for (j = 0; j < XVECLEN (x, i); j++)
2458 hash += canon_hash (XVECEXP (x, i, j), 0);
2459 else if (fmt[i] == 's')
2460 hash += canon_hash_string (XSTR (x, i));
2461 else if (fmt[i] == 'i')
2463 unsigned tem = XINT (x, i);
2464 hash += tem;
2466 else if (fmt[i] == '0' || fmt[i] == 't')
2467 /* Unused. */
2469 else
2470 abort ();
2472 return hash;
2475 /* Like canon_hash but with no side effects. */
2477 static unsigned
2478 safe_hash (x, mode)
2479 rtx x;
2480 enum machine_mode mode;
2482 int save_do_not_record = do_not_record;
2483 int save_hash_arg_in_memory = hash_arg_in_memory;
2484 unsigned hash = canon_hash (x, mode);
2485 hash_arg_in_memory = save_hash_arg_in_memory;
2486 do_not_record = save_do_not_record;
2487 return hash;
2490 /* Return 1 iff X and Y would canonicalize into the same thing,
2491 without actually constructing the canonicalization of either one.
2492 If VALIDATE is nonzero,
2493 we assume X is an expression being processed from the rtl
2494 and Y was found in the hash table. We check register refs
2495 in Y for being marked as valid.
2497 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2498 that is known to be in the register. Ordinarily, we don't allow them
2499 to match, because letting them match would cause unpredictable results
2500 in all the places that search a hash table chain for an equivalent
2501 for a given value. A possible equivalent that has different structure
2502 has its hash code computed from different data. Whether the hash code
2503 is the same as that of the given value is pure luck. */
2505 static int
2506 exp_equiv_p (x, y, validate, equal_values)
2507 rtx x, y;
2508 int validate;
2509 int equal_values;
2511 int i, j;
2512 enum rtx_code code;
2513 const char *fmt;
2515 /* Note: it is incorrect to assume an expression is equivalent to itself
2516 if VALIDATE is nonzero. */
2517 if (x == y && !validate)
2518 return 1;
2519 if (x == 0 || y == 0)
2520 return x == y;
2522 code = GET_CODE (x);
2523 if (code != GET_CODE (y))
2525 if (!equal_values)
2526 return 0;
2528 /* If X is a constant and Y is a register or vice versa, they may be
2529 equivalent. We only have to validate if Y is a register. */
2530 if (CONSTANT_P (x) && GET_CODE (y) == REG
2531 && REGNO_QTY_VALID_P (REGNO (y)))
2533 int y_q = REG_QTY (REGNO (y));
2534 struct qty_table_elem *y_ent = &qty_table[y_q];
2536 if (GET_MODE (y) == y_ent->mode
2537 && rtx_equal_p (x, y_ent->const_rtx)
2538 && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y))))
2539 return 1;
2542 if (CONSTANT_P (y) && code == REG
2543 && REGNO_QTY_VALID_P (REGNO (x)))
2545 int x_q = REG_QTY (REGNO (x));
2546 struct qty_table_elem *x_ent = &qty_table[x_q];
2548 if (GET_MODE (x) == x_ent->mode
2549 && rtx_equal_p (y, x_ent->const_rtx))
2550 return 1;
2553 return 0;
2556 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2557 if (GET_MODE (x) != GET_MODE (y))
2558 return 0;
2560 switch (code)
2562 case PC:
2563 case CC0:
2564 case CONST_INT:
2565 return x == y;
2567 case LABEL_REF:
2568 return XEXP (x, 0) == XEXP (y, 0);
2570 case SYMBOL_REF:
2571 return XSTR (x, 0) == XSTR (y, 0);
2573 case REG:
2575 unsigned int regno = REGNO (y);
2576 unsigned int endregno
2577 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2578 : HARD_REGNO_NREGS (regno, GET_MODE (y)));
2579 unsigned int i;
2581 /* If the quantities are not the same, the expressions are not
2582 equivalent. If there are and we are not to validate, they
2583 are equivalent. Otherwise, ensure all regs are up-to-date. */
2585 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2586 return 0;
2588 if (! validate)
2589 return 1;
2591 for (i = regno; i < endregno; i++)
2592 if (REG_IN_TABLE (i) != REG_TICK (i))
2593 return 0;
2595 return 1;
2598 /* For commutative operations, check both orders. */
2599 case PLUS:
2600 case MULT:
2601 case AND:
2602 case IOR:
2603 case XOR:
2604 case NE:
2605 case EQ:
2606 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
2607 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2608 validate, equal_values))
2609 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2610 validate, equal_values)
2611 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2612 validate, equal_values)));
2614 case ASM_OPERANDS:
2615 /* We don't use the generic code below because we want to
2616 disregard filename and line numbers. */
2618 /* A volatile asm isn't equivalent to any other. */
2619 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2620 return 0;
2622 if (GET_MODE (x) != GET_MODE (y)
2623 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2624 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2625 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2626 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2627 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2628 return 0;
2630 if (ASM_OPERANDS_INPUT_LENGTH (x))
2632 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2633 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2634 ASM_OPERANDS_INPUT (y, i),
2635 validate, equal_values)
2636 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2637 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2638 return 0;
2641 return 1;
2643 default:
2644 break;
2647 /* Compare the elements. If any pair of corresponding elements
2648 fail to match, return 0 for the whole things. */
2650 fmt = GET_RTX_FORMAT (code);
2651 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2653 switch (fmt[i])
2655 case 'e':
2656 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
2657 return 0;
2658 break;
2660 case 'E':
2661 if (XVECLEN (x, i) != XVECLEN (y, i))
2662 return 0;
2663 for (j = 0; j < XVECLEN (x, i); j++)
2664 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2665 validate, equal_values))
2666 return 0;
2667 break;
2669 case 's':
2670 if (strcmp (XSTR (x, i), XSTR (y, i)))
2671 return 0;
2672 break;
2674 case 'i':
2675 if (XINT (x, i) != XINT (y, i))
2676 return 0;
2677 break;
2679 case 'w':
2680 if (XWINT (x, i) != XWINT (y, i))
2681 return 0;
2682 break;
2684 case '0':
2685 case 't':
2686 break;
2688 default:
2689 abort ();
2693 return 1;
2696 /* Return 1 if X has a value that can vary even between two
2697 executions of the program. 0 means X can be compared reliably
2698 against certain constants or near-constants. */
2700 static int
2701 cse_rtx_varies_p (x, from_alias)
2702 rtx x;
2703 int from_alias;
2705 /* We need not check for X and the equivalence class being of the same
2706 mode because if X is equivalent to a constant in some mode, it
2707 doesn't vary in any mode. */
2709 if (GET_CODE (x) == REG
2710 && REGNO_QTY_VALID_P (REGNO (x)))
2712 int x_q = REG_QTY (REGNO (x));
2713 struct qty_table_elem *x_ent = &qty_table[x_q];
2715 if (GET_MODE (x) == x_ent->mode
2716 && x_ent->const_rtx != NULL_RTX)
2717 return 0;
2720 if (GET_CODE (x) == PLUS
2721 && GET_CODE (XEXP (x, 1)) == CONST_INT
2722 && GET_CODE (XEXP (x, 0)) == REG
2723 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2725 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2726 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2728 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2729 && x0_ent->const_rtx != NULL_RTX)
2730 return 0;
2733 /* This can happen as the result of virtual register instantiation, if
2734 the initial constant is too large to be a valid address. This gives
2735 us a three instruction sequence, load large offset into a register,
2736 load fp minus a constant into a register, then a MEM which is the
2737 sum of the two `constant' registers. */
2738 if (GET_CODE (x) == PLUS
2739 && GET_CODE (XEXP (x, 0)) == REG
2740 && GET_CODE (XEXP (x, 1)) == REG
2741 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2742 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2744 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2745 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2746 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2747 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2749 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2750 && x0_ent->const_rtx != NULL_RTX
2751 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2752 && x1_ent->const_rtx != NULL_RTX)
2753 return 0;
2756 return rtx_varies_p (x, from_alias);
2759 /* Canonicalize an expression:
2760 replace each register reference inside it
2761 with the "oldest" equivalent register.
2763 If INSN is non-zero and we are replacing a pseudo with a hard register
2764 or vice versa, validate_change is used to ensure that INSN remains valid
2765 after we make our substitution. The calls are made with IN_GROUP non-zero
2766 so apply_change_group must be called upon the outermost return from this
2767 function (unless INSN is zero). The result of apply_change_group can
2768 generally be discarded since the changes we are making are optional. */
2770 static rtx
2771 canon_reg (x, insn)
2772 rtx x;
2773 rtx insn;
2775 int i;
2776 enum rtx_code code;
2777 const char *fmt;
2779 if (x == 0)
2780 return x;
2782 code = GET_CODE (x);
2783 switch (code)
2785 case PC:
2786 case CC0:
2787 case CONST:
2788 case CONST_INT:
2789 case CONST_DOUBLE:
2790 case CONST_VECTOR:
2791 case SYMBOL_REF:
2792 case LABEL_REF:
2793 case ADDR_VEC:
2794 case ADDR_DIFF_VEC:
2795 return x;
2797 case REG:
2799 int first;
2800 int q;
2801 struct qty_table_elem *ent;
2803 /* Never replace a hard reg, because hard regs can appear
2804 in more than one machine mode, and we must preserve the mode
2805 of each occurrence. Also, some hard regs appear in
2806 MEMs that are shared and mustn't be altered. Don't try to
2807 replace any reg that maps to a reg of class NO_REGS. */
2808 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2809 || ! REGNO_QTY_VALID_P (REGNO (x)))
2810 return x;
2812 q = REG_QTY (REGNO (x));
2813 ent = &qty_table[q];
2814 first = ent->first_reg;
2815 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2816 : REGNO_REG_CLASS (first) == NO_REGS ? x
2817 : gen_rtx_REG (ent->mode, first));
2820 default:
2821 break;
2824 fmt = GET_RTX_FORMAT (code);
2825 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2827 int j;
2829 if (fmt[i] == 'e')
2831 rtx new = canon_reg (XEXP (x, i), insn);
2832 int insn_code;
2834 /* If replacing pseudo with hard reg or vice versa, ensure the
2835 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2836 if (insn != 0 && new != 0
2837 && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
2838 && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2839 != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER))
2840 || (insn_code = recog_memoized (insn)) < 0
2841 || insn_data[insn_code].n_dups > 0))
2842 validate_change (insn, &XEXP (x, i), new, 1);
2843 else
2844 XEXP (x, i) = new;
2846 else if (fmt[i] == 'E')
2847 for (j = 0; j < XVECLEN (x, i); j++)
2848 XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
2851 return x;
2854 /* LOC is a location within INSN that is an operand address (the contents of
2855 a MEM). Find the best equivalent address to use that is valid for this
2856 insn.
2858 On most CISC machines, complicated address modes are costly, and rtx_cost
2859 is a good approximation for that cost. However, most RISC machines have
2860 only a few (usually only one) memory reference formats. If an address is
2861 valid at all, it is often just as cheap as any other address. Hence, for
2862 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2863 costs of various addresses. For two addresses of equal cost, choose the one
2864 with the highest `rtx_cost' value as that has the potential of eliminating
2865 the most insns. For equal costs, we choose the first in the equivalence
2866 class. Note that we ignore the fact that pseudo registers are cheaper
2867 than hard registers here because we would also prefer the pseudo registers.
2870 static void
2871 find_best_addr (insn, loc, mode)
2872 rtx insn;
2873 rtx *loc;
2874 enum machine_mode mode;
2876 struct table_elt *elt;
2877 rtx addr = *loc;
2878 #ifdef ADDRESS_COST
2879 struct table_elt *p;
2880 int found_better = 1;
2881 #endif
2882 int save_do_not_record = do_not_record;
2883 int save_hash_arg_in_memory = hash_arg_in_memory;
2884 int addr_volatile;
2885 int regno;
2886 unsigned hash;
2888 /* Do not try to replace constant addresses or addresses of local and
2889 argument slots. These MEM expressions are made only once and inserted
2890 in many instructions, as well as being used to control symbol table
2891 output. It is not safe to clobber them.
2893 There are some uncommon cases where the address is already in a register
2894 for some reason, but we cannot take advantage of that because we have
2895 no easy way to unshare the MEM. In addition, looking up all stack
2896 addresses is costly. */
2897 if ((GET_CODE (addr) == PLUS
2898 && GET_CODE (XEXP (addr, 0)) == REG
2899 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2900 && (regno = REGNO (XEXP (addr, 0)),
2901 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2902 || regno == ARG_POINTER_REGNUM))
2903 || (GET_CODE (addr) == REG
2904 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2905 || regno == HARD_FRAME_POINTER_REGNUM
2906 || regno == ARG_POINTER_REGNUM))
2907 || GET_CODE (addr) == ADDRESSOF
2908 || CONSTANT_ADDRESS_P (addr))
2909 return;
2911 /* If this address is not simply a register, try to fold it. This will
2912 sometimes simplify the expression. Many simplifications
2913 will not be valid, but some, usually applying the associative rule, will
2914 be valid and produce better code. */
2915 if (GET_CODE (addr) != REG)
2917 rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX);
2918 int addr_folded_cost = address_cost (folded, mode);
2919 int addr_cost = address_cost (addr, mode);
2921 if ((addr_folded_cost < addr_cost
2922 || (addr_folded_cost == addr_cost
2923 /* ??? The rtx_cost comparison is left over from an older
2924 version of this code. It is probably no longer helpful. */
2925 && (rtx_cost (folded, MEM) > rtx_cost (addr, MEM)
2926 || approx_reg_cost (folded) < approx_reg_cost (addr))))
2927 && validate_change (insn, loc, folded, 0))
2928 addr = folded;
2931 /* If this address is not in the hash table, we can't look for equivalences
2932 of the whole address. Also, ignore if volatile. */
2934 do_not_record = 0;
2935 hash = HASH (addr, Pmode);
2936 addr_volatile = do_not_record;
2937 do_not_record = save_do_not_record;
2938 hash_arg_in_memory = save_hash_arg_in_memory;
2940 if (addr_volatile)
2941 return;
2943 elt = lookup (addr, hash, Pmode);
2945 #ifndef ADDRESS_COST
2946 if (elt)
2948 int our_cost = elt->cost;
2950 /* Find the lowest cost below ours that works. */
2951 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
2952 if (elt->cost < our_cost
2953 && (GET_CODE (elt->exp) == REG
2954 || exp_equiv_p (elt->exp, elt->exp, 1, 0))
2955 && validate_change (insn, loc,
2956 canon_reg (copy_rtx (elt->exp), NULL_RTX), 0))
2957 return;
2959 #else
2961 if (elt)
2963 /* We need to find the best (under the criteria documented above) entry
2964 in the class that is valid. We use the `flag' field to indicate
2965 choices that were invalid and iterate until we can't find a better
2966 one that hasn't already been tried. */
2968 for (p = elt->first_same_value; p; p = p->next_same_value)
2969 p->flag = 0;
2971 while (found_better)
2973 int best_addr_cost = address_cost (*loc, mode);
2974 int best_rtx_cost = (elt->cost + 1) >> 1;
2975 int exp_cost;
2976 struct table_elt *best_elt = elt;
2978 found_better = 0;
2979 for (p = elt->first_same_value; p; p = p->next_same_value)
2980 if (! p->flag)
2982 if ((GET_CODE (p->exp) == REG
2983 || exp_equiv_p (p->exp, p->exp, 1, 0))
2984 && ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
2985 || (exp_cost == best_addr_cost
2986 && ((p->cost + 1) >> 1) > best_rtx_cost)))
2988 found_better = 1;
2989 best_addr_cost = exp_cost;
2990 best_rtx_cost = (p->cost + 1) >> 1;
2991 best_elt = p;
2995 if (found_better)
2997 if (validate_change (insn, loc,
2998 canon_reg (copy_rtx (best_elt->exp),
2999 NULL_RTX), 0))
3000 return;
3001 else
3002 best_elt->flag = 1;
3007 /* If the address is a binary operation with the first operand a register
3008 and the second a constant, do the same as above, but looking for
3009 equivalences of the register. Then try to simplify before checking for
3010 the best address to use. This catches a few cases: First is when we
3011 have REG+const and the register is another REG+const. We can often merge
3012 the constants and eliminate one insn and one register. It may also be
3013 that a machine has a cheap REG+REG+const. Finally, this improves the
3014 code on the Alpha for unaligned byte stores. */
3016 if (flag_expensive_optimizations
3017 && (GET_RTX_CLASS (GET_CODE (*loc)) == '2'
3018 || GET_RTX_CLASS (GET_CODE (*loc)) == 'c')
3019 && GET_CODE (XEXP (*loc, 0)) == REG
3020 && GET_CODE (XEXP (*loc, 1)) == CONST_INT)
3022 rtx c = XEXP (*loc, 1);
3024 do_not_record = 0;
3025 hash = HASH (XEXP (*loc, 0), Pmode);
3026 do_not_record = save_do_not_record;
3027 hash_arg_in_memory = save_hash_arg_in_memory;
3029 elt = lookup (XEXP (*loc, 0), hash, Pmode);
3030 if (elt == 0)
3031 return;
3033 /* We need to find the best (under the criteria documented above) entry
3034 in the class that is valid. We use the `flag' field to indicate
3035 choices that were invalid and iterate until we can't find a better
3036 one that hasn't already been tried. */
3038 for (p = elt->first_same_value; p; p = p->next_same_value)
3039 p->flag = 0;
3041 while (found_better)
3043 int best_addr_cost = address_cost (*loc, mode);
3044 int best_rtx_cost = (COST (*loc) + 1) >> 1;
3045 struct table_elt *best_elt = elt;
3046 rtx best_rtx = *loc;
3047 int count;
3049 /* This is at worst case an O(n^2) algorithm, so limit our search
3050 to the first 32 elements on the list. This avoids trouble
3051 compiling code with very long basic blocks that can easily
3052 call simplify_gen_binary so many times that we run out of
3053 memory. */
3055 found_better = 0;
3056 for (p = elt->first_same_value, count = 0;
3057 p && count < 32;
3058 p = p->next_same_value, count++)
3059 if (! p->flag
3060 && (GET_CODE (p->exp) == REG
3061 || exp_equiv_p (p->exp, p->exp, 1, 0)))
3063 rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
3064 p->exp, c);
3065 int new_cost;
3066 new_cost = address_cost (new, mode);
3068 if (new_cost < best_addr_cost
3069 || (new_cost == best_addr_cost
3070 && (COST (new) + 1) >> 1 > best_rtx_cost))
3072 found_better = 1;
3073 best_addr_cost = new_cost;
3074 best_rtx_cost = (COST (new) + 1) >> 1;
3075 best_elt = p;
3076 best_rtx = new;
3080 if (found_better)
3082 if (validate_change (insn, loc,
3083 canon_reg (copy_rtx (best_rtx),
3084 NULL_RTX), 0))
3085 return;
3086 else
3087 best_elt->flag = 1;
3091 #endif
3094 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
3095 operation (EQ, NE, GT, etc.), follow it back through the hash table and
3096 what values are being compared.
3098 *PARG1 and *PARG2 are updated to contain the rtx representing the values
3099 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
3100 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
3101 compared to produce cc0.
3103 The return value is the comparison operator and is either the code of
3104 A or the code corresponding to the inverse of the comparison. */
3106 static enum rtx_code
3107 find_comparison_args (code, parg1, parg2, pmode1, pmode2)
3108 enum rtx_code code;
3109 rtx *parg1, *parg2;
3110 enum machine_mode *pmode1, *pmode2;
3112 rtx arg1, arg2;
3114 arg1 = *parg1, arg2 = *parg2;
3116 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
3118 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
3120 /* Set non-zero when we find something of interest. */
3121 rtx x = 0;
3122 int reverse_code = 0;
3123 struct table_elt *p = 0;
3125 /* If arg1 is a COMPARE, extract the comparison arguments from it.
3126 On machines with CC0, this is the only case that can occur, since
3127 fold_rtx will return the COMPARE or item being compared with zero
3128 when given CC0. */
3130 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
3131 x = arg1;
3133 /* If ARG1 is a comparison operator and CODE is testing for
3134 STORE_FLAG_VALUE, get the inner arguments. */
3136 else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
3138 if (code == NE
3139 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3140 && code == LT && STORE_FLAG_VALUE == -1)
3141 #ifdef FLOAT_STORE_FLAG_VALUE
3142 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3143 && (REAL_VALUE_NEGATIVE
3144 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3145 #endif
3147 x = arg1;
3148 else if (code == EQ
3149 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3150 && code == GE && STORE_FLAG_VALUE == -1)
3151 #ifdef FLOAT_STORE_FLAG_VALUE
3152 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3153 && (REAL_VALUE_NEGATIVE
3154 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3155 #endif
3157 x = arg1, reverse_code = 1;
3160 /* ??? We could also check for
3162 (ne (and (eq (...) (const_int 1))) (const_int 0))
3164 and related forms, but let's wait until we see them occurring. */
3166 if (x == 0)
3167 /* Look up ARG1 in the hash table and see if it has an equivalence
3168 that lets us see what is being compared. */
3169 p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) & HASH_MASK,
3170 GET_MODE (arg1));
3171 if (p)
3173 p = p->first_same_value;
3175 /* If what we compare is already known to be constant, that is as
3176 good as it gets.
3177 We need to break the loop in this case, because otherwise we
3178 can have an infinite loop when looking at a reg that is known
3179 to be a constant which is the same as a comparison of a reg
3180 against zero which appears later in the insn stream, which in
3181 turn is constant and the same as the comparison of the first reg
3182 against zero... */
3183 if (p->is_const)
3184 break;
3187 for (; p; p = p->next_same_value)
3189 enum machine_mode inner_mode = GET_MODE (p->exp);
3191 /* If the entry isn't valid, skip it. */
3192 if (! exp_equiv_p (p->exp, p->exp, 1, 0))
3193 continue;
3195 if (GET_CODE (p->exp) == COMPARE
3196 /* Another possibility is that this machine has a compare insn
3197 that includes the comparison code. In that case, ARG1 would
3198 be equivalent to a comparison operation that would set ARG1 to
3199 either STORE_FLAG_VALUE or zero. If this is an NE operation,
3200 ORIG_CODE is the actual comparison being done; if it is an EQ,
3201 we must reverse ORIG_CODE. On machine with a negative value
3202 for STORE_FLAG_VALUE, also look at LT and GE operations. */
3203 || ((code == NE
3204 || (code == LT
3205 && GET_MODE_CLASS (inner_mode) == MODE_INT
3206 && (GET_MODE_BITSIZE (inner_mode)
3207 <= HOST_BITS_PER_WIDE_INT)
3208 && (STORE_FLAG_VALUE
3209 & ((HOST_WIDE_INT) 1
3210 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3211 #ifdef FLOAT_STORE_FLAG_VALUE
3212 || (code == LT
3213 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3214 && (REAL_VALUE_NEGATIVE
3215 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3216 #endif
3218 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
3220 x = p->exp;
3221 break;
3223 else if ((code == EQ
3224 || (code == GE
3225 && GET_MODE_CLASS (inner_mode) == MODE_INT
3226 && (GET_MODE_BITSIZE (inner_mode)
3227 <= HOST_BITS_PER_WIDE_INT)
3228 && (STORE_FLAG_VALUE
3229 & ((HOST_WIDE_INT) 1
3230 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3231 #ifdef FLOAT_STORE_FLAG_VALUE
3232 || (code == GE
3233 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3234 && (REAL_VALUE_NEGATIVE
3235 (FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)))))
3236 #endif
3238 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
3240 reverse_code = 1;
3241 x = p->exp;
3242 break;
3245 /* If this is fp + constant, the equivalent is a better operand since
3246 it may let us predict the value of the comparison. */
3247 else if (NONZERO_BASE_PLUS_P (p->exp))
3249 arg1 = p->exp;
3250 continue;
3254 /* If we didn't find a useful equivalence for ARG1, we are done.
3255 Otherwise, set up for the next iteration. */
3256 if (x == 0)
3257 break;
3259 /* If we need to reverse the comparison, make sure that that is
3260 possible -- we can't necessarily infer the value of GE from LT
3261 with floating-point operands. */
3262 if (reverse_code)
3264 enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
3265 if (reversed == UNKNOWN)
3266 break;
3267 else
3268 code = reversed;
3270 else if (GET_RTX_CLASS (GET_CODE (x)) == '<')
3271 code = GET_CODE (x);
3272 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3275 /* Return our results. Return the modes from before fold_rtx
3276 because fold_rtx might produce const_int, and then it's too late. */
3277 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3278 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3280 return code;
3283 /* If X is a nontrivial arithmetic operation on an argument
3284 for which a constant value can be determined, return
3285 the result of operating on that value, as a constant.
3286 Otherwise, return X, possibly with one or more operands
3287 modified by recursive calls to this function.
3289 If X is a register whose contents are known, we do NOT
3290 return those contents here. equiv_constant is called to
3291 perform that task.
3293 INSN is the insn that we may be modifying. If it is 0, make a copy
3294 of X before modifying it. */
3296 static rtx
3297 fold_rtx (x, insn)
3298 rtx x;
3299 rtx insn;
3301 enum rtx_code code;
3302 enum machine_mode mode;
3303 const char *fmt;
3304 int i;
3305 rtx new = 0;
3306 int copied = 0;
3307 int must_swap = 0;
3309 /* Folded equivalents of first two operands of X. */
3310 rtx folded_arg0;
3311 rtx folded_arg1;
3313 /* Constant equivalents of first three operands of X;
3314 0 when no such equivalent is known. */
3315 rtx const_arg0;
3316 rtx const_arg1;
3317 rtx const_arg2;
3319 /* The mode of the first operand of X. We need this for sign and zero
3320 extends. */
3321 enum machine_mode mode_arg0;
3323 if (x == 0)
3324 return x;
3326 mode = GET_MODE (x);
3327 code = GET_CODE (x);
3328 switch (code)
3330 case CONST:
3331 case CONST_INT:
3332 case CONST_DOUBLE:
3333 case CONST_VECTOR:
3334 case SYMBOL_REF:
3335 case LABEL_REF:
3336 case REG:
3337 /* No use simplifying an EXPR_LIST
3338 since they are used only for lists of args
3339 in a function call's REG_EQUAL note. */
3340 case EXPR_LIST:
3341 /* Changing anything inside an ADDRESSOF is incorrect; we don't
3342 want to (e.g.,) make (addressof (const_int 0)) just because
3343 the location is known to be zero. */
3344 case ADDRESSOF:
3345 return x;
3347 #ifdef HAVE_cc0
3348 case CC0:
3349 return prev_insn_cc0;
3350 #endif
3352 case PC:
3353 /* If the next insn is a CODE_LABEL followed by a jump table,
3354 PC's value is a LABEL_REF pointing to that label. That
3355 lets us fold switch statements on the VAX. */
3356 if (insn && GET_CODE (insn) == JUMP_INSN)
3358 rtx next = next_nonnote_insn (insn);
3360 if (next && GET_CODE (next) == CODE_LABEL
3361 && NEXT_INSN (next) != 0
3362 && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
3363 && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
3364 || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
3365 return gen_rtx_LABEL_REF (Pmode, next);
3367 break;
3369 case SUBREG:
3370 /* See if we previously assigned a constant value to this SUBREG. */
3371 if ((new = lookup_as_function (x, CONST_INT)) != 0
3372 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3373 return new;
3375 /* If this is a paradoxical SUBREG, we have no idea what value the
3376 extra bits would have. However, if the operand is equivalent
3377 to a SUBREG whose operand is the same as our mode, and all the
3378 modes are within a word, we can just use the inner operand
3379 because these SUBREGs just say how to treat the register.
3381 Similarly if we find an integer constant. */
3383 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3385 enum machine_mode imode = GET_MODE (SUBREG_REG (x));
3386 struct table_elt *elt;
3388 if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
3389 && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
3390 && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
3391 imode)) != 0)
3392 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3394 if (CONSTANT_P (elt->exp)
3395 && GET_MODE (elt->exp) == VOIDmode)
3396 return elt->exp;
3398 if (GET_CODE (elt->exp) == SUBREG
3399 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3400 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3401 return copy_rtx (SUBREG_REG (elt->exp));
3404 return x;
3407 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
3408 We might be able to if the SUBREG is extracting a single word in an
3409 integral mode or extracting the low part. */
3411 folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
3412 const_arg0 = equiv_constant (folded_arg0);
3413 if (const_arg0)
3414 folded_arg0 = const_arg0;
3416 if (folded_arg0 != SUBREG_REG (x))
3418 new = simplify_subreg (mode, folded_arg0,
3419 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3420 if (new)
3421 return new;
3424 /* If this is a narrowing SUBREG and our operand is a REG, see if
3425 we can find an equivalence for REG that is an arithmetic operation
3426 in a wider mode where both operands are paradoxical SUBREGs
3427 from objects of our result mode. In that case, we couldn't report
3428 an equivalent value for that operation, since we don't know what the
3429 extra bits will be. But we can find an equivalence for this SUBREG
3430 by folding that operation is the narrow mode. This allows us to
3431 fold arithmetic in narrow modes when the machine only supports
3432 word-sized arithmetic.
3434 Also look for a case where we have a SUBREG whose operand is the
3435 same as our result. If both modes are smaller than a word, we
3436 are simply interpreting a register in different modes and we
3437 can use the inner value. */
3439 if (GET_CODE (folded_arg0) == REG
3440 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0))
3441 && subreg_lowpart_p (x))
3443 struct table_elt *elt;
3445 /* We can use HASH here since we know that canon_hash won't be
3446 called. */
3447 elt = lookup (folded_arg0,
3448 HASH (folded_arg0, GET_MODE (folded_arg0)),
3449 GET_MODE (folded_arg0));
3451 if (elt)
3452 elt = elt->first_same_value;
3454 for (; elt; elt = elt->next_same_value)
3456 enum rtx_code eltcode = GET_CODE (elt->exp);
3458 /* Just check for unary and binary operations. */
3459 if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1'
3460 && GET_CODE (elt->exp) != SIGN_EXTEND
3461 && GET_CODE (elt->exp) != ZERO_EXTEND
3462 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3463 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode)
3465 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
3467 if (GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3468 op0 = fold_rtx (op0, NULL_RTX);
3470 op0 = equiv_constant (op0);
3471 if (op0)
3472 new = simplify_unary_operation (GET_CODE (elt->exp), mode,
3473 op0, mode);
3475 else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2'
3476 || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c')
3477 && eltcode != DIV && eltcode != MOD
3478 && eltcode != UDIV && eltcode != UMOD
3479 && eltcode != ASHIFTRT && eltcode != LSHIFTRT
3480 && eltcode != ROTATE && eltcode != ROTATERT
3481 && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3482 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
3483 == mode))
3484 || CONSTANT_P (XEXP (elt->exp, 0)))
3485 && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
3486 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
3487 == mode))
3488 || CONSTANT_P (XEXP (elt->exp, 1))))
3490 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
3491 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
3493 if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3494 op0 = fold_rtx (op0, NULL_RTX);
3496 if (op0)
3497 op0 = equiv_constant (op0);
3499 if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1))
3500 op1 = fold_rtx (op1, NULL_RTX);
3502 if (op1)
3503 op1 = equiv_constant (op1);
3505 /* If we are looking for the low SImode part of
3506 (ashift:DI c (const_int 32)), it doesn't work
3507 to compute that in SImode, because a 32-bit shift
3508 in SImode is unpredictable. We know the value is 0. */
3509 if (op0 && op1
3510 && GET_CODE (elt->exp) == ASHIFT
3511 && GET_CODE (op1) == CONST_INT
3512 && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
3514 if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
3516 /* If the count fits in the inner mode's width,
3517 but exceeds the outer mode's width,
3518 the value will get truncated to 0
3519 by the subreg. */
3520 new = const0_rtx;
3521 else
3522 /* If the count exceeds even the inner mode's width,
3523 don't fold this expression. */
3524 new = 0;
3526 else if (op0 && op1)
3527 new = simplify_binary_operation (GET_CODE (elt->exp), mode,
3528 op0, op1);
3531 else if (GET_CODE (elt->exp) == SUBREG
3532 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3533 && (GET_MODE_SIZE (GET_MODE (folded_arg0))
3534 <= UNITS_PER_WORD)
3535 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3536 new = copy_rtx (SUBREG_REG (elt->exp));
3538 if (new)
3539 return new;
3543 return x;
3545 case NOT:
3546 case NEG:
3547 /* If we have (NOT Y), see if Y is known to be (NOT Z).
3548 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
3549 new = lookup_as_function (XEXP (x, 0), code);
3550 if (new)
3551 return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
3552 break;
3554 case MEM:
3555 /* If we are not actually processing an insn, don't try to find the
3556 best address. Not only don't we care, but we could modify the
3557 MEM in an invalid way since we have no insn to validate against. */
3558 if (insn != 0)
3559 find_best_addr (insn, &XEXP (x, 0), GET_MODE (x));
3562 /* Even if we don't fold in the insn itself,
3563 we can safely do so here, in hopes of getting a constant. */
3564 rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
3565 rtx base = 0;
3566 HOST_WIDE_INT offset = 0;
3568 if (GET_CODE (addr) == REG
3569 && REGNO_QTY_VALID_P (REGNO (addr)))
3571 int addr_q = REG_QTY (REGNO (addr));
3572 struct qty_table_elem *addr_ent = &qty_table[addr_q];
3574 if (GET_MODE (addr) == addr_ent->mode
3575 && addr_ent->const_rtx != NULL_RTX)
3576 addr = addr_ent->const_rtx;
3579 /* If address is constant, split it into a base and integer offset. */
3580 if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
3581 base = addr;
3582 else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
3583 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
3585 base = XEXP (XEXP (addr, 0), 0);
3586 offset = INTVAL (XEXP (XEXP (addr, 0), 1));
3588 else if (GET_CODE (addr) == LO_SUM
3589 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
3590 base = XEXP (addr, 1);
3591 else if (GET_CODE (addr) == ADDRESSOF)
3592 return change_address (x, VOIDmode, addr);
3594 /* If this is a constant pool reference, we can fold it into its
3595 constant to allow better value tracking. */
3596 if (base && GET_CODE (base) == SYMBOL_REF
3597 && CONSTANT_POOL_ADDRESS_P (base))
3599 rtx constant = get_pool_constant (base);
3600 enum machine_mode const_mode = get_pool_mode (base);
3601 rtx new;
3603 if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
3604 constant_pool_entries_cost = COST (constant);
3606 /* If we are loading the full constant, we have an equivalence. */
3607 if (offset == 0 && mode == const_mode)
3608 return constant;
3610 /* If this actually isn't a constant (weird!), we can't do
3611 anything. Otherwise, handle the two most common cases:
3612 extracting a word from a multi-word constant, and extracting
3613 the low-order bits. Other cases don't seem common enough to
3614 worry about. */
3615 if (! CONSTANT_P (constant))
3616 return x;
3618 if (GET_MODE_CLASS (mode) == MODE_INT
3619 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3620 && offset % UNITS_PER_WORD == 0
3621 && (new = operand_subword (constant,
3622 offset / UNITS_PER_WORD,
3623 0, const_mode)) != 0)
3624 return new;
3626 if (((BYTES_BIG_ENDIAN
3627 && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
3628 || (! BYTES_BIG_ENDIAN && offset == 0))
3629 && (new = gen_lowpart_if_possible (mode, constant)) != 0)
3630 return new;
3633 /* If this is a reference to a label at a known position in a jump
3634 table, we also know its value. */
3635 if (base && GET_CODE (base) == LABEL_REF)
3637 rtx label = XEXP (base, 0);
3638 rtx table_insn = NEXT_INSN (label);
3640 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3641 && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
3643 rtx table = PATTERN (table_insn);
3645 if (offset >= 0
3646 && (offset / GET_MODE_SIZE (GET_MODE (table))
3647 < XVECLEN (table, 0)))
3648 return XVECEXP (table, 0,
3649 offset / GET_MODE_SIZE (GET_MODE (table)));
3651 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3652 && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
3654 rtx table = PATTERN (table_insn);
3656 if (offset >= 0
3657 && (offset / GET_MODE_SIZE (GET_MODE (table))
3658 < XVECLEN (table, 1)))
3660 offset /= GET_MODE_SIZE (GET_MODE (table));
3661 new = gen_rtx_MINUS (Pmode, XVECEXP (table, 1, offset),
3662 XEXP (table, 0));
3664 if (GET_MODE (table) != Pmode)
3665 new = gen_rtx_TRUNCATE (GET_MODE (table), new);
3667 /* Indicate this is a constant. This isn't a
3668 valid form of CONST, but it will only be used
3669 to fold the next insns and then discarded, so
3670 it should be safe.
3672 Note this expression must be explicitly discarded,
3673 by cse_insn, else it may end up in a REG_EQUAL note
3674 and "escape" to cause problems elsewhere. */
3675 return gen_rtx_CONST (GET_MODE (new), new);
3680 return x;
3683 #ifdef NO_FUNCTION_CSE
3684 case CALL:
3685 if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3686 return x;
3687 break;
3688 #endif
3690 case ASM_OPERANDS:
3691 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3692 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3693 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3694 break;
3696 default:
3697 break;
3700 const_arg0 = 0;
3701 const_arg1 = 0;
3702 const_arg2 = 0;
3703 mode_arg0 = VOIDmode;
3705 /* Try folding our operands.
3706 Then see which ones have constant values known. */
3708 fmt = GET_RTX_FORMAT (code);
3709 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3710 if (fmt[i] == 'e')
3712 rtx arg = XEXP (x, i);
3713 rtx folded_arg = arg, const_arg = 0;
3714 enum machine_mode mode_arg = GET_MODE (arg);
3715 rtx cheap_arg, expensive_arg;
3716 rtx replacements[2];
3717 int j;
3719 /* Most arguments are cheap, so handle them specially. */
3720 switch (GET_CODE (arg))
3722 case REG:
3723 /* This is the same as calling equiv_constant; it is duplicated
3724 here for speed. */
3725 if (REGNO_QTY_VALID_P (REGNO (arg)))
3727 int arg_q = REG_QTY (REGNO (arg));
3728 struct qty_table_elem *arg_ent = &qty_table[arg_q];
3730 if (arg_ent->const_rtx != NULL_RTX
3731 && GET_CODE (arg_ent->const_rtx) != REG
3732 && GET_CODE (arg_ent->const_rtx) != PLUS)
3733 const_arg
3734 = gen_lowpart_if_possible (GET_MODE (arg),
3735 arg_ent->const_rtx);
3737 break;
3739 case CONST:
3740 case CONST_INT:
3741 case SYMBOL_REF:
3742 case LABEL_REF:
3743 case CONST_DOUBLE:
3744 case CONST_VECTOR:
3745 const_arg = arg;
3746 break;
3748 #ifdef HAVE_cc0
3749 case CC0:
3750 folded_arg = prev_insn_cc0;
3751 mode_arg = prev_insn_cc0_mode;
3752 const_arg = equiv_constant (folded_arg);
3753 break;
3754 #endif
3756 default:
3757 folded_arg = fold_rtx (arg, insn);
3758 const_arg = equiv_constant (folded_arg);
3761 /* For the first three operands, see if the operand
3762 is constant or equivalent to a constant. */
3763 switch (i)
3765 case 0:
3766 folded_arg0 = folded_arg;
3767 const_arg0 = const_arg;
3768 mode_arg0 = mode_arg;
3769 break;
3770 case 1:
3771 folded_arg1 = folded_arg;
3772 const_arg1 = const_arg;
3773 break;
3774 case 2:
3775 const_arg2 = const_arg;
3776 break;
3779 /* Pick the least expensive of the folded argument and an
3780 equivalent constant argument. */
3781 if (const_arg == 0 || const_arg == folded_arg
3782 || COST_IN (const_arg, code) > COST_IN (folded_arg, code))
3783 cheap_arg = folded_arg, expensive_arg = const_arg;
3784 else
3785 cheap_arg = const_arg, expensive_arg = folded_arg;
3787 /* Try to replace the operand with the cheapest of the two
3788 possibilities. If it doesn't work and this is either of the first
3789 two operands of a commutative operation, try swapping them.
3790 If THAT fails, try the more expensive, provided it is cheaper
3791 than what is already there. */
3793 if (cheap_arg == XEXP (x, i))
3794 continue;
3796 if (insn == 0 && ! copied)
3798 x = copy_rtx (x);
3799 copied = 1;
3802 /* Order the replacements from cheapest to most expensive. */
3803 replacements[0] = cheap_arg;
3804 replacements[1] = expensive_arg;
3806 for (j = 0; j < 2 && replacements[j]; j++)
3808 int old_cost = COST_IN (XEXP (x, i), code);
3809 int new_cost = COST_IN (replacements[j], code);
3811 /* Stop if what existed before was cheaper. Prefer constants
3812 in the case of a tie. */
3813 if (new_cost > old_cost
3814 || (new_cost == old_cost && CONSTANT_P (XEXP (x, i))))
3815 break;
3817 if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
3818 break;
3820 if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c'
3821 || code == LTGT || code == UNEQ || code == ORDERED
3822 || code == UNORDERED)
3824 validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
3825 validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
3827 if (apply_change_group ())
3829 /* Swap them back to be invalid so that this loop can
3830 continue and flag them to be swapped back later. */
3831 rtx tem;
3833 tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
3834 XEXP (x, 1) = tem;
3835 must_swap = 1;
3836 break;
3842 else
3844 if (fmt[i] == 'E')
3845 /* Don't try to fold inside of a vector of expressions.
3846 Doing nothing is harmless. */
3850 /* If a commutative operation, place a constant integer as the second
3851 operand unless the first operand is also a constant integer. Otherwise,
3852 place any constant second unless the first operand is also a constant. */
3854 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c'
3855 || code == LTGT || code == UNEQ || code == ORDERED
3856 || code == UNORDERED)
3858 if (must_swap || (const_arg0
3859 && (const_arg1 == 0
3860 || (GET_CODE (const_arg0) == CONST_INT
3861 && GET_CODE (const_arg1) != CONST_INT))))
3863 rtx tem = XEXP (x, 0);
3865 if (insn == 0 && ! copied)
3867 x = copy_rtx (x);
3868 copied = 1;
3871 validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
3872 validate_change (insn, &XEXP (x, 1), tem, 1);
3873 if (apply_change_group ())
3875 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3876 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3881 /* If X is an arithmetic operation, see if we can simplify it. */
3883 switch (GET_RTX_CLASS (code))
3885 case '1':
3887 int is_const = 0;
3889 /* We can't simplify extension ops unless we know the
3890 original mode. */
3891 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3892 && mode_arg0 == VOIDmode)
3893 break;
3895 /* If we had a CONST, strip it off and put it back later if we
3896 fold. */
3897 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3898 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3900 new = simplify_unary_operation (code, mode,
3901 const_arg0 ? const_arg0 : folded_arg0,
3902 mode_arg0);
3903 if (new != 0 && is_const)
3904 new = gen_rtx_CONST (mode, new);
3906 break;
3908 case '<':
3909 /* See what items are actually being compared and set FOLDED_ARG[01]
3910 to those values and CODE to the actual comparison code. If any are
3911 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3912 do anything if both operands are already known to be constant. */
3914 if (const_arg0 == 0 || const_arg1 == 0)
3916 struct table_elt *p0, *p1;
3917 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3918 enum machine_mode mode_arg1;
3920 #ifdef FLOAT_STORE_FLAG_VALUE
3921 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3923 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3924 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3925 false_rtx = CONST0_RTX (mode);
3927 #endif
3929 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3930 &mode_arg0, &mode_arg1);
3931 const_arg0 = equiv_constant (folded_arg0);
3932 const_arg1 = equiv_constant (folded_arg1);
3934 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3935 what kinds of things are being compared, so we can't do
3936 anything with this comparison. */
3938 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3939 break;
3941 /* If we do not now have two constants being compared, see
3942 if we can nevertheless deduce some things about the
3943 comparison. */
3944 if (const_arg0 == 0 || const_arg1 == 0)
3946 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or
3947 non-explicit constant? These aren't zero, but we
3948 don't know their sign. */
3949 if (const_arg1 == const0_rtx
3950 && (NONZERO_BASE_PLUS_P (folded_arg0)
3951 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
3952 come out as 0. */
3953 || GET_CODE (folded_arg0) == SYMBOL_REF
3954 #endif
3955 || GET_CODE (folded_arg0) == LABEL_REF
3956 || GET_CODE (folded_arg0) == CONST))
3958 if (code == EQ)
3959 return false_rtx;
3960 else if (code == NE)
3961 return true_rtx;
3964 /* See if the two operands are the same. */
3966 if (folded_arg0 == folded_arg1
3967 || (GET_CODE (folded_arg0) == REG
3968 && GET_CODE (folded_arg1) == REG
3969 && (REG_QTY (REGNO (folded_arg0))
3970 == REG_QTY (REGNO (folded_arg1))))
3971 || ((p0 = lookup (folded_arg0,
3972 (safe_hash (folded_arg0, mode_arg0)
3973 & HASH_MASK), mode_arg0))
3974 && (p1 = lookup (folded_arg1,
3975 (safe_hash (folded_arg1, mode_arg0)
3976 & HASH_MASK), mode_arg0))
3977 && p0->first_same_value == p1->first_same_value))
3979 /* Sadly two equal NaNs are not equivalent. */
3980 if (!HONOR_NANS (mode_arg0))
3981 return ((code == EQ || code == LE || code == GE
3982 || code == LEU || code == GEU || code == UNEQ
3983 || code == UNLE || code == UNGE
3984 || code == ORDERED)
3985 ? true_rtx : false_rtx);
3986 /* Take care for the FP compares we can resolve. */
3987 if (code == UNEQ || code == UNLE || code == UNGE)
3988 return true_rtx;
3989 if (code == LTGT || code == LT || code == GT)
3990 return false_rtx;
3993 /* If FOLDED_ARG0 is a register, see if the comparison we are
3994 doing now is either the same as we did before or the reverse
3995 (we only check the reverse if not floating-point). */
3996 else if (GET_CODE (folded_arg0) == REG)
3998 int qty = REG_QTY (REGNO (folded_arg0));
4000 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
4002 struct qty_table_elem *ent = &qty_table[qty];
4004 if ((comparison_dominates_p (ent->comparison_code, code)
4005 || (! FLOAT_MODE_P (mode_arg0)
4006 && comparison_dominates_p (ent->comparison_code,
4007 reverse_condition (code))))
4008 && (rtx_equal_p (ent->comparison_const, folded_arg1)
4009 || (const_arg1
4010 && rtx_equal_p (ent->comparison_const,
4011 const_arg1))
4012 || (GET_CODE (folded_arg1) == REG
4013 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
4014 return (comparison_dominates_p (ent->comparison_code, code)
4015 ? true_rtx : false_rtx);
4021 /* If we are comparing against zero, see if the first operand is
4022 equivalent to an IOR with a constant. If so, we may be able to
4023 determine the result of this comparison. */
4025 if (const_arg1 == const0_rtx)
4027 rtx y = lookup_as_function (folded_arg0, IOR);
4028 rtx inner_const;
4030 if (y != 0
4031 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
4032 && GET_CODE (inner_const) == CONST_INT
4033 && INTVAL (inner_const) != 0)
4035 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
4036 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
4037 && (INTVAL (inner_const)
4038 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
4039 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
4041 #ifdef FLOAT_STORE_FLAG_VALUE
4042 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
4044 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
4045 (FLOAT_STORE_FLAG_VALUE (mode), mode));
4046 false_rtx = CONST0_RTX (mode);
4048 #endif
4050 switch (code)
4052 case EQ:
4053 return false_rtx;
4054 case NE:
4055 return true_rtx;
4056 case LT: case LE:
4057 if (has_sign)
4058 return true_rtx;
4059 break;
4060 case GT: case GE:
4061 if (has_sign)
4062 return false_rtx;
4063 break;
4064 default:
4065 break;
4070 new = simplify_relational_operation (code,
4071 (mode_arg0 != VOIDmode
4072 ? mode_arg0
4073 : (GET_MODE (const_arg0
4074 ? const_arg0
4075 : folded_arg0)
4076 != VOIDmode)
4077 ? GET_MODE (const_arg0
4078 ? const_arg0
4079 : folded_arg0)
4080 : GET_MODE (const_arg1
4081 ? const_arg1
4082 : folded_arg1)),
4083 const_arg0 ? const_arg0 : folded_arg0,
4084 const_arg1 ? const_arg1 : folded_arg1);
4085 #ifdef FLOAT_STORE_FLAG_VALUE
4086 if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT)
4088 if (new == const0_rtx)
4089 new = CONST0_RTX (mode);
4090 else
4091 new = (CONST_DOUBLE_FROM_REAL_VALUE
4092 (FLOAT_STORE_FLAG_VALUE (mode), mode));
4094 #endif
4095 break;
4097 case '2':
4098 case 'c':
4099 switch (code)
4101 case PLUS:
4102 /* If the second operand is a LABEL_REF, see if the first is a MINUS
4103 with that LABEL_REF as its second operand. If so, the result is
4104 the first operand of that MINUS. This handles switches with an
4105 ADDR_DIFF_VEC table. */
4106 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
4108 rtx y
4109 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
4110 : lookup_as_function (folded_arg0, MINUS);
4112 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4113 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
4114 return XEXP (y, 0);
4116 /* Now try for a CONST of a MINUS like the above. */
4117 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
4118 : lookup_as_function (folded_arg0, CONST))) != 0
4119 && GET_CODE (XEXP (y, 0)) == MINUS
4120 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4121 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
4122 return XEXP (XEXP (y, 0), 0);
4125 /* Likewise if the operands are in the other order. */
4126 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
4128 rtx y
4129 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
4130 : lookup_as_function (folded_arg1, MINUS);
4132 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4133 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
4134 return XEXP (y, 0);
4136 /* Now try for a CONST of a MINUS like the above. */
4137 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
4138 : lookup_as_function (folded_arg1, CONST))) != 0
4139 && GET_CODE (XEXP (y, 0)) == MINUS
4140 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4141 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
4142 return XEXP (XEXP (y, 0), 0);
4145 /* If second operand is a register equivalent to a negative
4146 CONST_INT, see if we can find a register equivalent to the
4147 positive constant. Make a MINUS if so. Don't do this for
4148 a non-negative constant since we might then alternate between
4149 choosing positive and negative constants. Having the positive
4150 constant previously-used is the more common case. Be sure
4151 the resulting constant is non-negative; if const_arg1 were
4152 the smallest negative number this would overflow: depending
4153 on the mode, this would either just be the same value (and
4154 hence not save anything) or be incorrect. */
4155 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
4156 && INTVAL (const_arg1) < 0
4157 /* This used to test
4159 -INTVAL (const_arg1) >= 0
4161 But The Sun V5.0 compilers mis-compiled that test. So
4162 instead we test for the problematic value in a more direct
4163 manner and hope the Sun compilers get it correct. */
4164 && INTVAL (const_arg1) !=
4165 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
4166 && GET_CODE (folded_arg1) == REG)
4168 rtx new_const = GEN_INT (-INTVAL (const_arg1));
4169 struct table_elt *p
4170 = lookup (new_const, safe_hash (new_const, mode) & HASH_MASK,
4171 mode);
4173 if (p)
4174 for (p = p->first_same_value; p; p = p->next_same_value)
4175 if (GET_CODE (p->exp) == REG)
4176 return simplify_gen_binary (MINUS, mode, folded_arg0,
4177 canon_reg (p->exp, NULL_RTX));
4179 goto from_plus;
4181 case MINUS:
4182 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
4183 If so, produce (PLUS Z C2-C). */
4184 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
4186 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
4187 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
4188 return fold_rtx (plus_constant (copy_rtx (y),
4189 -INTVAL (const_arg1)),
4190 NULL_RTX);
4193 /* Fall through. */
4195 from_plus:
4196 case SMIN: case SMAX: case UMIN: case UMAX:
4197 case IOR: case AND: case XOR:
4198 case MULT: case DIV: case UDIV:
4199 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
4200 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
4201 is known to be of similar form, we may be able to replace the
4202 operation with a combined operation. This may eliminate the
4203 intermediate operation if every use is simplified in this way.
4204 Note that the similar optimization done by combine.c only works
4205 if the intermediate operation's result has only one reference. */
4207 if (GET_CODE (folded_arg0) == REG
4208 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
4210 int is_shift
4211 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
4212 rtx y = lookup_as_function (folded_arg0, code);
4213 rtx inner_const;
4214 enum rtx_code associate_code;
4215 rtx new_const;
4217 if (y == 0
4218 || 0 == (inner_const
4219 = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
4220 || GET_CODE (inner_const) != CONST_INT
4221 /* If we have compiled a statement like
4222 "if (x == (x & mask1))", and now are looking at
4223 "x & mask2", we will have a case where the first operand
4224 of Y is the same as our first operand. Unless we detect
4225 this case, an infinite loop will result. */
4226 || XEXP (y, 0) == folded_arg0)
4227 break;
4229 /* Don't associate these operations if they are a PLUS with the
4230 same constant and it is a power of two. These might be doable
4231 with a pre- or post-increment. Similarly for two subtracts of
4232 identical powers of two with post decrement. */
4234 if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
4235 && ((HAVE_PRE_INCREMENT
4236 && exact_log2 (INTVAL (const_arg1)) >= 0)
4237 || (HAVE_POST_INCREMENT
4238 && exact_log2 (INTVAL (const_arg1)) >= 0)
4239 || (HAVE_PRE_DECREMENT
4240 && exact_log2 (- INTVAL (const_arg1)) >= 0)
4241 || (HAVE_POST_DECREMENT
4242 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
4243 break;
4245 /* Compute the code used to compose the constants. For example,
4246 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
4248 associate_code
4249 = (code == MULT || code == DIV || code == UDIV ? MULT
4250 : is_shift || code == PLUS || code == MINUS ? PLUS : code);
4252 new_const = simplify_binary_operation (associate_code, mode,
4253 const_arg1, inner_const);
4255 if (new_const == 0)
4256 break;
4258 /* If we are associating shift operations, don't let this
4259 produce a shift of the size of the object or larger.
4260 This could occur when we follow a sign-extend by a right
4261 shift on a machine that does a sign-extend as a pair
4262 of shifts. */
4264 if (is_shift && GET_CODE (new_const) == CONST_INT
4265 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
4267 /* As an exception, we can turn an ASHIFTRT of this
4268 form into a shift of the number of bits - 1. */
4269 if (code == ASHIFTRT)
4270 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
4271 else
4272 break;
4275 y = copy_rtx (XEXP (y, 0));
4277 /* If Y contains our first operand (the most common way this
4278 can happen is if Y is a MEM), we would do into an infinite
4279 loop if we tried to fold it. So don't in that case. */
4281 if (! reg_mentioned_p (folded_arg0, y))
4282 y = fold_rtx (y, insn);
4284 return simplify_gen_binary (code, mode, y, new_const);
4286 break;
4288 default:
4289 break;
4292 new = simplify_binary_operation (code, mode,
4293 const_arg0 ? const_arg0 : folded_arg0,
4294 const_arg1 ? const_arg1 : folded_arg1);
4295 break;
4297 case 'o':
4298 /* (lo_sum (high X) X) is simply X. */
4299 if (code == LO_SUM && const_arg0 != 0
4300 && GET_CODE (const_arg0) == HIGH
4301 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
4302 return const_arg1;
4303 break;
4305 case '3':
4306 case 'b':
4307 new = simplify_ternary_operation (code, mode, mode_arg0,
4308 const_arg0 ? const_arg0 : folded_arg0,
4309 const_arg1 ? const_arg1 : folded_arg1,
4310 const_arg2 ? const_arg2 : XEXP (x, 2));
4311 break;
4313 case 'x':
4314 /* Always eliminate CONSTANT_P_RTX at this stage. */
4315 if (code == CONSTANT_P_RTX)
4316 return (const_arg0 ? const1_rtx : const0_rtx);
4317 break;
4320 return new ? new : x;
4323 /* Return a constant value currently equivalent to X.
4324 Return 0 if we don't know one. */
4326 static rtx
4327 equiv_constant (x)
4328 rtx x;
4330 if (GET_CODE (x) == REG
4331 && REGNO_QTY_VALID_P (REGNO (x)))
4333 int x_q = REG_QTY (REGNO (x));
4334 struct qty_table_elem *x_ent = &qty_table[x_q];
4336 if (x_ent->const_rtx)
4337 x = gen_lowpart_if_possible (GET_MODE (x), x_ent->const_rtx);
4340 if (x == 0 || CONSTANT_P (x))
4341 return x;
4343 /* If X is a MEM, try to fold it outside the context of any insn to see if
4344 it might be equivalent to a constant. That handles the case where it
4345 is a constant-pool reference. Then try to look it up in the hash table
4346 in case it is something whose value we have seen before. */
4348 if (GET_CODE (x) == MEM)
4350 struct table_elt *elt;
4352 x = fold_rtx (x, NULL_RTX);
4353 if (CONSTANT_P (x))
4354 return x;
4356 elt = lookup (x, safe_hash (x, GET_MODE (x)) & HASH_MASK, GET_MODE (x));
4357 if (elt == 0)
4358 return 0;
4360 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
4361 if (elt->is_const && CONSTANT_P (elt->exp))
4362 return elt->exp;
4365 return 0;
4368 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4369 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4370 least-significant part of X.
4371 MODE specifies how big a part of X to return.
4373 If the requested operation cannot be done, 0 is returned.
4375 This is similar to gen_lowpart in emit-rtl.c. */
4378 gen_lowpart_if_possible (mode, x)
4379 enum machine_mode mode;
4380 rtx x;
4382 rtx result = gen_lowpart_common (mode, x);
4384 if (result)
4385 return result;
4386 else if (GET_CODE (x) == MEM)
4388 /* This is the only other case we handle. */
4389 int offset = 0;
4390 rtx new;
4392 if (WORDS_BIG_ENDIAN)
4393 offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
4394 - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
4395 if (BYTES_BIG_ENDIAN)
4396 /* Adjust the address so that the address-after-the-data is
4397 unchanged. */
4398 offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode))
4399 - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
4401 new = adjust_address_nv (x, mode, offset);
4402 if (! memory_address_p (mode, XEXP (new, 0)))
4403 return 0;
4405 return new;
4407 else
4408 return 0;
4411 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4412 branch. It will be zero if not.
4414 In certain cases, this can cause us to add an equivalence. For example,
4415 if we are following the taken case of
4416 if (i == 2)
4417 we can add the fact that `i' and '2' are now equivalent.
4419 In any case, we can record that this comparison was passed. If the same
4420 comparison is seen later, we will know its value. */
4422 static void
4423 record_jump_equiv (insn, taken)
4424 rtx insn;
4425 int taken;
4427 int cond_known_true;
4428 rtx op0, op1;
4429 rtx set;
4430 enum machine_mode mode, mode0, mode1;
4431 int reversed_nonequality = 0;
4432 enum rtx_code code;
4434 /* Ensure this is the right kind of insn. */
4435 if (! any_condjump_p (insn))
4436 return;
4437 set = pc_set (insn);
4439 /* See if this jump condition is known true or false. */
4440 if (taken)
4441 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
4442 else
4443 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
4445 /* Get the type of comparison being done and the operands being compared.
4446 If we had to reverse a non-equality condition, record that fact so we
4447 know that it isn't valid for floating-point. */
4448 code = GET_CODE (XEXP (SET_SRC (set), 0));
4449 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
4450 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
4452 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
4453 if (! cond_known_true)
4455 code = reversed_comparison_code_parts (code, op0, op1, insn);
4457 /* Don't remember if we can't find the inverse. */
4458 if (code == UNKNOWN)
4459 return;
4462 /* The mode is the mode of the non-constant. */
4463 mode = mode0;
4464 if (mode1 != VOIDmode)
4465 mode = mode1;
4467 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
4470 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
4471 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
4472 Make any useful entries we can with that information. Called from
4473 above function and called recursively. */
4475 static void
4476 record_jump_cond (code, mode, op0, op1, reversed_nonequality)
4477 enum rtx_code code;
4478 enum machine_mode mode;
4479 rtx op0, op1;
4480 int reversed_nonequality;
4482 unsigned op0_hash, op1_hash;
4483 int op0_in_memory, op1_in_memory;
4484 struct table_elt *op0_elt, *op1_elt;
4486 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
4487 we know that they are also equal in the smaller mode (this is also
4488 true for all smaller modes whether or not there is a SUBREG, but
4489 is not worth testing for with no SUBREG). */
4491 /* Note that GET_MODE (op0) may not equal MODE. */
4492 if (code == EQ && GET_CODE (op0) == SUBREG
4493 && (GET_MODE_SIZE (GET_MODE (op0))
4494 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4496 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4497 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4499 record_jump_cond (code, mode, SUBREG_REG (op0),
4500 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4501 reversed_nonequality);
4504 if (code == EQ && GET_CODE (op1) == SUBREG
4505 && (GET_MODE_SIZE (GET_MODE (op1))
4506 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4508 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4509 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4511 record_jump_cond (code, mode, SUBREG_REG (op1),
4512 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4513 reversed_nonequality);
4516 /* Similarly, if this is an NE comparison, and either is a SUBREG
4517 making a smaller mode, we know the whole thing is also NE. */
4519 /* Note that GET_MODE (op0) may not equal MODE;
4520 if we test MODE instead, we can get an infinite recursion
4521 alternating between two modes each wider than MODE. */
4523 if (code == NE && GET_CODE (op0) == SUBREG
4524 && subreg_lowpart_p (op0)
4525 && (GET_MODE_SIZE (GET_MODE (op0))
4526 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4528 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4529 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4531 record_jump_cond (code, mode, SUBREG_REG (op0),
4532 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4533 reversed_nonequality);
4536 if (code == NE && GET_CODE (op1) == SUBREG
4537 && subreg_lowpart_p (op1)
4538 && (GET_MODE_SIZE (GET_MODE (op1))
4539 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4541 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4542 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4544 record_jump_cond (code, mode, SUBREG_REG (op1),
4545 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4546 reversed_nonequality);
4549 /* Hash both operands. */
4551 do_not_record = 0;
4552 hash_arg_in_memory = 0;
4553 op0_hash = HASH (op0, mode);
4554 op0_in_memory = hash_arg_in_memory;
4556 if (do_not_record)
4557 return;
4559 do_not_record = 0;
4560 hash_arg_in_memory = 0;
4561 op1_hash = HASH (op1, mode);
4562 op1_in_memory = hash_arg_in_memory;
4564 if (do_not_record)
4565 return;
4567 /* Look up both operands. */
4568 op0_elt = lookup (op0, op0_hash, mode);
4569 op1_elt = lookup (op1, op1_hash, mode);
4571 /* If both operands are already equivalent or if they are not in the
4572 table but are identical, do nothing. */
4573 if ((op0_elt != 0 && op1_elt != 0
4574 && op0_elt->first_same_value == op1_elt->first_same_value)
4575 || op0 == op1 || rtx_equal_p (op0, op1))
4576 return;
4578 /* If we aren't setting two things equal all we can do is save this
4579 comparison. Similarly if this is floating-point. In the latter
4580 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4581 If we record the equality, we might inadvertently delete code
4582 whose intent was to change -0 to +0. */
4584 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
4586 struct qty_table_elem *ent;
4587 int qty;
4589 /* If we reversed a floating-point comparison, if OP0 is not a
4590 register, or if OP1 is neither a register or constant, we can't
4591 do anything. */
4593 if (GET_CODE (op1) != REG)
4594 op1 = equiv_constant (op1);
4596 if ((reversed_nonequality && FLOAT_MODE_P (mode))
4597 || GET_CODE (op0) != REG || op1 == 0)
4598 return;
4600 /* Put OP0 in the hash table if it isn't already. This gives it a
4601 new quantity number. */
4602 if (op0_elt == 0)
4604 if (insert_regs (op0, NULL, 0))
4606 rehash_using_reg (op0);
4607 op0_hash = HASH (op0, mode);
4609 /* If OP0 is contained in OP1, this changes its hash code
4610 as well. Faster to rehash than to check, except
4611 for the simple case of a constant. */
4612 if (! CONSTANT_P (op1))
4613 op1_hash = HASH (op1,mode);
4616 op0_elt = insert (op0, NULL, op0_hash, mode);
4617 op0_elt->in_memory = op0_in_memory;
4620 qty = REG_QTY (REGNO (op0));
4621 ent = &qty_table[qty];
4623 ent->comparison_code = code;
4624 if (GET_CODE (op1) == REG)
4626 /* Look it up again--in case op0 and op1 are the same. */
4627 op1_elt = lookup (op1, op1_hash, mode);
4629 /* Put OP1 in the hash table so it gets a new quantity number. */
4630 if (op1_elt == 0)
4632 if (insert_regs (op1, NULL, 0))
4634 rehash_using_reg (op1);
4635 op1_hash = HASH (op1, mode);
4638 op1_elt = insert (op1, NULL, op1_hash, mode);
4639 op1_elt->in_memory = op1_in_memory;
4642 ent->comparison_const = NULL_RTX;
4643 ent->comparison_qty = REG_QTY (REGNO (op1));
4645 else
4647 ent->comparison_const = op1;
4648 ent->comparison_qty = -1;
4651 return;
4654 /* If either side is still missing an equivalence, make it now,
4655 then merge the equivalences. */
4657 if (op0_elt == 0)
4659 if (insert_regs (op0, NULL, 0))
4661 rehash_using_reg (op0);
4662 op0_hash = HASH (op0, mode);
4665 op0_elt = insert (op0, NULL, op0_hash, mode);
4666 op0_elt->in_memory = op0_in_memory;
4669 if (op1_elt == 0)
4671 if (insert_regs (op1, NULL, 0))
4673 rehash_using_reg (op1);
4674 op1_hash = HASH (op1, mode);
4677 op1_elt = insert (op1, NULL, op1_hash, mode);
4678 op1_elt->in_memory = op1_in_memory;
4681 merge_equiv_classes (op0_elt, op1_elt);
4682 last_jump_equiv_class = op0_elt;
4685 /* CSE processing for one instruction.
4686 First simplify sources and addresses of all assignments
4687 in the instruction, using previously-computed equivalents values.
4688 Then install the new sources and destinations in the table
4689 of available values.
4691 If LIBCALL_INSN is nonzero, don't record any equivalence made in
4692 the insn. It means that INSN is inside libcall block. In this
4693 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
4695 /* Data on one SET contained in the instruction. */
4697 struct set
4699 /* The SET rtx itself. */
4700 rtx rtl;
4701 /* The SET_SRC of the rtx (the original value, if it is changing). */
4702 rtx src;
4703 /* The hash-table element for the SET_SRC of the SET. */
4704 struct table_elt *src_elt;
4705 /* Hash value for the SET_SRC. */
4706 unsigned src_hash;
4707 /* Hash value for the SET_DEST. */
4708 unsigned dest_hash;
4709 /* The SET_DEST, with SUBREG, etc., stripped. */
4710 rtx inner_dest;
4711 /* Nonzero if the SET_SRC is in memory. */
4712 char src_in_memory;
4713 /* Nonzero if the SET_SRC contains something
4714 whose value cannot be predicted and understood. */
4715 char src_volatile;
4716 /* Original machine mode, in case it becomes a CONST_INT. */
4717 enum machine_mode mode;
4718 /* A constant equivalent for SET_SRC, if any. */
4719 rtx src_const;
4720 /* Original SET_SRC value used for libcall notes. */
4721 rtx orig_src;
4722 /* Hash value of constant equivalent for SET_SRC. */
4723 unsigned src_const_hash;
4724 /* Table entry for constant equivalent for SET_SRC, if any. */
4725 struct table_elt *src_const_elt;
4728 static void
4729 cse_insn (insn, libcall_insn)
4730 rtx insn;
4731 rtx libcall_insn;
4733 rtx x = PATTERN (insn);
4734 int i;
4735 rtx tem;
4736 int n_sets = 0;
4738 #ifdef HAVE_cc0
4739 /* Records what this insn does to set CC0. */
4740 rtx this_insn_cc0 = 0;
4741 enum machine_mode this_insn_cc0_mode = VOIDmode;
4742 #endif
4744 rtx src_eqv = 0;
4745 struct table_elt *src_eqv_elt = 0;
4746 int src_eqv_volatile = 0;
4747 int src_eqv_in_memory = 0;
4748 unsigned src_eqv_hash = 0;
4750 struct set *sets = (struct set *) 0;
4752 this_insn = insn;
4754 /* Find all the SETs and CLOBBERs in this instruction.
4755 Record all the SETs in the array `set' and count them.
4756 Also determine whether there is a CLOBBER that invalidates
4757 all memory references, or all references at varying addresses. */
4759 if (GET_CODE (insn) == CALL_INSN)
4761 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4763 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4764 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4765 XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4769 if (GET_CODE (x) == SET)
4771 sets = (struct set *) alloca (sizeof (struct set));
4772 sets[0].rtl = x;
4774 /* Ignore SETs that are unconditional jumps.
4775 They never need cse processing, so this does not hurt.
4776 The reason is not efficiency but rather
4777 so that we can test at the end for instructions
4778 that have been simplified to unconditional jumps
4779 and not be misled by unchanged instructions
4780 that were unconditional jumps to begin with. */
4781 if (SET_DEST (x) == pc_rtx
4782 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4785 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4786 The hard function value register is used only once, to copy to
4787 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4788 Ensure we invalidate the destination register. On the 80386 no
4789 other code would invalidate it since it is a fixed_reg.
4790 We need not check the return of apply_change_group; see canon_reg. */
4792 else if (GET_CODE (SET_SRC (x)) == CALL)
4794 canon_reg (SET_SRC (x), insn);
4795 apply_change_group ();
4796 fold_rtx (SET_SRC (x), insn);
4797 invalidate (SET_DEST (x), VOIDmode);
4799 else
4800 n_sets = 1;
4802 else if (GET_CODE (x) == PARALLEL)
4804 int lim = XVECLEN (x, 0);
4806 sets = (struct set *) alloca (lim * sizeof (struct set));
4808 /* Find all regs explicitly clobbered in this insn,
4809 and ensure they are not replaced with any other regs
4810 elsewhere in this insn.
4811 When a reg that is clobbered is also used for input,
4812 we should presume that that is for a reason,
4813 and we should not substitute some other register
4814 which is not supposed to be clobbered.
4815 Therefore, this loop cannot be merged into the one below
4816 because a CALL may precede a CLOBBER and refer to the
4817 value clobbered. We must not let a canonicalization do
4818 anything in that case. */
4819 for (i = 0; i < lim; i++)
4821 rtx y = XVECEXP (x, 0, i);
4822 if (GET_CODE (y) == CLOBBER)
4824 rtx clobbered = XEXP (y, 0);
4826 if (GET_CODE (clobbered) == REG
4827 || GET_CODE (clobbered) == SUBREG)
4828 invalidate (clobbered, VOIDmode);
4829 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4830 || GET_CODE (clobbered) == ZERO_EXTRACT)
4831 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4835 for (i = 0; i < lim; i++)
4837 rtx y = XVECEXP (x, 0, i);
4838 if (GET_CODE (y) == SET)
4840 /* As above, we ignore unconditional jumps and call-insns and
4841 ignore the result of apply_change_group. */
4842 if (GET_CODE (SET_SRC (y)) == CALL)
4844 canon_reg (SET_SRC (y), insn);
4845 apply_change_group ();
4846 fold_rtx (SET_SRC (y), insn);
4847 invalidate (SET_DEST (y), VOIDmode);
4849 else if (SET_DEST (y) == pc_rtx
4850 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4852 else
4853 sets[n_sets++].rtl = y;
4855 else if (GET_CODE (y) == CLOBBER)
4857 /* If we clobber memory, canon the address.
4858 This does nothing when a register is clobbered
4859 because we have already invalidated the reg. */
4860 if (GET_CODE (XEXP (y, 0)) == MEM)
4861 canon_reg (XEXP (y, 0), NULL_RTX);
4863 else if (GET_CODE (y) == USE
4864 && ! (GET_CODE (XEXP (y, 0)) == REG
4865 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4866 canon_reg (y, NULL_RTX);
4867 else if (GET_CODE (y) == CALL)
4869 /* The result of apply_change_group can be ignored; see
4870 canon_reg. */
4871 canon_reg (y, insn);
4872 apply_change_group ();
4873 fold_rtx (y, insn);
4877 else if (GET_CODE (x) == CLOBBER)
4879 if (GET_CODE (XEXP (x, 0)) == MEM)
4880 canon_reg (XEXP (x, 0), NULL_RTX);
4883 /* Canonicalize a USE of a pseudo register or memory location. */
4884 else if (GET_CODE (x) == USE
4885 && ! (GET_CODE (XEXP (x, 0)) == REG
4886 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4887 canon_reg (XEXP (x, 0), NULL_RTX);
4888 else if (GET_CODE (x) == CALL)
4890 /* The result of apply_change_group can be ignored; see canon_reg. */
4891 canon_reg (x, insn);
4892 apply_change_group ();
4893 fold_rtx (x, insn);
4896 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4897 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4898 is handled specially for this case, and if it isn't set, then there will
4899 be no equivalence for the destination. */
4900 if (n_sets == 1 && REG_NOTES (insn) != 0
4901 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4902 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4903 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4904 src_eqv = canon_reg (XEXP (tem, 0), NULL_RTX);
4906 /* Canonicalize sources and addresses of destinations.
4907 We do this in a separate pass to avoid problems when a MATCH_DUP is
4908 present in the insn pattern. In that case, we want to ensure that
4909 we don't break the duplicate nature of the pattern. So we will replace
4910 both operands at the same time. Otherwise, we would fail to find an
4911 equivalent substitution in the loop calling validate_change below.
4913 We used to suppress canonicalization of DEST if it appears in SRC,
4914 but we don't do this any more. */
4916 for (i = 0; i < n_sets; i++)
4918 rtx dest = SET_DEST (sets[i].rtl);
4919 rtx src = SET_SRC (sets[i].rtl);
4920 rtx new = canon_reg (src, insn);
4921 int insn_code;
4923 sets[i].orig_src = src;
4924 if ((GET_CODE (new) == REG && GET_CODE (src) == REG
4925 && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
4926 != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
4927 || (insn_code = recog_memoized (insn)) < 0
4928 || insn_data[insn_code].n_dups > 0)
4929 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4930 else
4931 SET_SRC (sets[i].rtl) = new;
4933 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4935 validate_change (insn, &XEXP (dest, 1),
4936 canon_reg (XEXP (dest, 1), insn), 1);
4937 validate_change (insn, &XEXP (dest, 2),
4938 canon_reg (XEXP (dest, 2), insn), 1);
4941 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
4942 || GET_CODE (dest) == ZERO_EXTRACT
4943 || GET_CODE (dest) == SIGN_EXTRACT)
4944 dest = XEXP (dest, 0);
4946 if (GET_CODE (dest) == MEM)
4947 canon_reg (dest, insn);
4950 /* Now that we have done all the replacements, we can apply the change
4951 group and see if they all work. Note that this will cause some
4952 canonicalizations that would have worked individually not to be applied
4953 because some other canonicalization didn't work, but this should not
4954 occur often.
4956 The result of apply_change_group can be ignored; see canon_reg. */
4958 apply_change_group ();
4960 /* Set sets[i].src_elt to the class each source belongs to.
4961 Detect assignments from or to volatile things
4962 and set set[i] to zero so they will be ignored
4963 in the rest of this function.
4965 Nothing in this loop changes the hash table or the register chains. */
4967 for (i = 0; i < n_sets; i++)
4969 rtx src, dest;
4970 rtx src_folded;
4971 struct table_elt *elt = 0, *p;
4972 enum machine_mode mode;
4973 rtx src_eqv_here;
4974 rtx src_const = 0;
4975 rtx src_related = 0;
4976 struct table_elt *src_const_elt = 0;
4977 int src_cost = MAX_COST;
4978 int src_eqv_cost = MAX_COST;
4979 int src_folded_cost = MAX_COST;
4980 int src_related_cost = MAX_COST;
4981 int src_elt_cost = MAX_COST;
4982 int src_regcost = MAX_COST;
4983 int src_eqv_regcost = MAX_COST;
4984 int src_folded_regcost = MAX_COST;
4985 int src_related_regcost = MAX_COST;
4986 int src_elt_regcost = MAX_COST;
4987 /* Set non-zero if we need to call force_const_mem on with the
4988 contents of src_folded before using it. */
4989 int src_folded_force_flag = 0;
4991 dest = SET_DEST (sets[i].rtl);
4992 src = SET_SRC (sets[i].rtl);
4994 /* If SRC is a constant that has no machine mode,
4995 hash it with the destination's machine mode.
4996 This way we can keep different modes separate. */
4998 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4999 sets[i].mode = mode;
5001 if (src_eqv)
5003 enum machine_mode eqvmode = mode;
5004 if (GET_CODE (dest) == STRICT_LOW_PART)
5005 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5006 do_not_record = 0;
5007 hash_arg_in_memory = 0;
5008 src_eqv = fold_rtx (src_eqv, insn);
5009 src_eqv_hash = HASH (src_eqv, eqvmode);
5011 /* Find the equivalence class for the equivalent expression. */
5013 if (!do_not_record)
5014 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
5016 src_eqv_volatile = do_not_record;
5017 src_eqv_in_memory = hash_arg_in_memory;
5020 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
5021 value of the INNER register, not the destination. So it is not
5022 a valid substitution for the source. But save it for later. */
5023 if (GET_CODE (dest) == STRICT_LOW_PART)
5024 src_eqv_here = 0;
5025 else
5026 src_eqv_here = src_eqv;
5028 /* Simplify and foldable subexpressions in SRC. Then get the fully-
5029 simplified result, which may not necessarily be valid. */
5030 src_folded = fold_rtx (src, insn);
5032 #if 0
5033 /* ??? This caused bad code to be generated for the m68k port with -O2.
5034 Suppose src is (CONST_INT -1), and that after truncation src_folded
5035 is (CONST_INT 3). Suppose src_folded is then used for src_const.
5036 At the end we will add src and src_const to the same equivalence
5037 class. We now have 3 and -1 on the same equivalence class. This
5038 causes later instructions to be mis-optimized. */
5039 /* If storing a constant in a bitfield, pre-truncate the constant
5040 so we will be able to record it later. */
5041 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
5042 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
5044 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5046 if (GET_CODE (src) == CONST_INT
5047 && GET_CODE (width) == CONST_INT
5048 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5049 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5050 src_folded
5051 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
5052 << INTVAL (width)) - 1));
5054 #endif
5056 /* Compute SRC's hash code, and also notice if it
5057 should not be recorded at all. In that case,
5058 prevent any further processing of this assignment. */
5059 do_not_record = 0;
5060 hash_arg_in_memory = 0;
5062 sets[i].src = src;
5063 sets[i].src_hash = HASH (src, mode);
5064 sets[i].src_volatile = do_not_record;
5065 sets[i].src_in_memory = hash_arg_in_memory;
5067 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
5068 a pseudo, do not record SRC. Using SRC as a replacement for
5069 anything else will be incorrect in that situation. Note that
5070 this usually occurs only for stack slots, in which case all the
5071 RTL would be referring to SRC, so we don't lose any optimization
5072 opportunities by not having SRC in the hash table. */
5074 if (GET_CODE (src) == MEM
5075 && find_reg_note (insn, REG_EQUIV, NULL_RTX) != 0
5076 && GET_CODE (dest) == REG
5077 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
5078 sets[i].src_volatile = 1;
5080 #if 0
5081 /* It is no longer clear why we used to do this, but it doesn't
5082 appear to still be needed. So let's try without it since this
5083 code hurts cse'ing widened ops. */
5084 /* If source is a perverse subreg (such as QI treated as an SI),
5085 treat it as volatile. It may do the work of an SI in one context
5086 where the extra bits are not being used, but cannot replace an SI
5087 in general. */
5088 if (GET_CODE (src) == SUBREG
5089 && (GET_MODE_SIZE (GET_MODE (src))
5090 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
5091 sets[i].src_volatile = 1;
5092 #endif
5094 /* Locate all possible equivalent forms for SRC. Try to replace
5095 SRC in the insn with each cheaper equivalent.
5097 We have the following types of equivalents: SRC itself, a folded
5098 version, a value given in a REG_EQUAL note, or a value related
5099 to a constant.
5101 Each of these equivalents may be part of an additional class
5102 of equivalents (if more than one is in the table, they must be in
5103 the same class; we check for this).
5105 If the source is volatile, we don't do any table lookups.
5107 We note any constant equivalent for possible later use in a
5108 REG_NOTE. */
5110 if (!sets[i].src_volatile)
5111 elt = lookup (src, sets[i].src_hash, mode);
5113 sets[i].src_elt = elt;
5115 if (elt && src_eqv_here && src_eqv_elt)
5117 if (elt->first_same_value != src_eqv_elt->first_same_value)
5119 /* The REG_EQUAL is indicating that two formerly distinct
5120 classes are now equivalent. So merge them. */
5121 merge_equiv_classes (elt, src_eqv_elt);
5122 src_eqv_hash = HASH (src_eqv, elt->mode);
5123 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
5126 src_eqv_here = 0;
5129 else if (src_eqv_elt)
5130 elt = src_eqv_elt;
5132 /* Try to find a constant somewhere and record it in `src_const'.
5133 Record its table element, if any, in `src_const_elt'. Look in
5134 any known equivalences first. (If the constant is not in the
5135 table, also set `sets[i].src_const_hash'). */
5136 if (elt)
5137 for (p = elt->first_same_value; p; p = p->next_same_value)
5138 if (p->is_const)
5140 src_const = p->exp;
5141 src_const_elt = elt;
5142 break;
5145 if (src_const == 0
5146 && (CONSTANT_P (src_folded)
5147 /* Consider (minus (label_ref L1) (label_ref L2)) as
5148 "constant" here so we will record it. This allows us
5149 to fold switch statements when an ADDR_DIFF_VEC is used. */
5150 || (GET_CODE (src_folded) == MINUS
5151 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
5152 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
5153 src_const = src_folded, src_const_elt = elt;
5154 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
5155 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
5157 /* If we don't know if the constant is in the table, get its
5158 hash code and look it up. */
5159 if (src_const && src_const_elt == 0)
5161 sets[i].src_const_hash = HASH (src_const, mode);
5162 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
5165 sets[i].src_const = src_const;
5166 sets[i].src_const_elt = src_const_elt;
5168 /* If the constant and our source are both in the table, mark them as
5169 equivalent. Otherwise, if a constant is in the table but the source
5170 isn't, set ELT to it. */
5171 if (src_const_elt && elt
5172 && src_const_elt->first_same_value != elt->first_same_value)
5173 merge_equiv_classes (elt, src_const_elt);
5174 else if (src_const_elt && elt == 0)
5175 elt = src_const_elt;
5177 /* See if there is a register linearly related to a constant
5178 equivalent of SRC. */
5179 if (src_const
5180 && (GET_CODE (src_const) == CONST
5181 || (src_const_elt && src_const_elt->related_value != 0)))
5183 src_related = use_related_value (src_const, src_const_elt);
5184 if (src_related)
5186 struct table_elt *src_related_elt
5187 = lookup (src_related, HASH (src_related, mode), mode);
5188 if (src_related_elt && elt)
5190 if (elt->first_same_value
5191 != src_related_elt->first_same_value)
5192 /* This can occur when we previously saw a CONST
5193 involving a SYMBOL_REF and then see the SYMBOL_REF
5194 twice. Merge the involved classes. */
5195 merge_equiv_classes (elt, src_related_elt);
5197 src_related = 0;
5198 src_related_elt = 0;
5200 else if (src_related_elt && elt == 0)
5201 elt = src_related_elt;
5205 /* See if we have a CONST_INT that is already in a register in a
5206 wider mode. */
5208 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
5209 && GET_MODE_CLASS (mode) == MODE_INT
5210 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
5212 enum machine_mode wider_mode;
5214 for (wider_mode = GET_MODE_WIDER_MODE (mode);
5215 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
5216 && src_related == 0;
5217 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5219 struct table_elt *const_elt
5220 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
5222 if (const_elt == 0)
5223 continue;
5225 for (const_elt = const_elt->first_same_value;
5226 const_elt; const_elt = const_elt->next_same_value)
5227 if (GET_CODE (const_elt->exp) == REG)
5229 src_related = gen_lowpart_if_possible (mode,
5230 const_elt->exp);
5231 break;
5236 /* Another possibility is that we have an AND with a constant in
5237 a mode narrower than a word. If so, it might have been generated
5238 as part of an "if" which would narrow the AND. If we already
5239 have done the AND in a wider mode, we can use a SUBREG of that
5240 value. */
5242 if (flag_expensive_optimizations && ! src_related
5243 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
5244 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5246 enum machine_mode tmode;
5247 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
5249 for (tmode = GET_MODE_WIDER_MODE (mode);
5250 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5251 tmode = GET_MODE_WIDER_MODE (tmode))
5253 rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0));
5254 struct table_elt *larger_elt;
5256 if (inner)
5258 PUT_MODE (new_and, tmode);
5259 XEXP (new_and, 0) = inner;
5260 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
5261 if (larger_elt == 0)
5262 continue;
5264 for (larger_elt = larger_elt->first_same_value;
5265 larger_elt; larger_elt = larger_elt->next_same_value)
5266 if (GET_CODE (larger_elt->exp) == REG)
5268 src_related
5269 = gen_lowpart_if_possible (mode, larger_elt->exp);
5270 break;
5273 if (src_related)
5274 break;
5279 #ifdef LOAD_EXTEND_OP
5280 /* See if a MEM has already been loaded with a widening operation;
5281 if it has, we can use a subreg of that. Many CISC machines
5282 also have such operations, but this is only likely to be
5283 beneficial these machines. */
5285 if (flag_expensive_optimizations && src_related == 0
5286 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5287 && GET_MODE_CLASS (mode) == MODE_INT
5288 && GET_CODE (src) == MEM && ! do_not_record
5289 && LOAD_EXTEND_OP (mode) != NIL)
5291 enum machine_mode tmode;
5293 /* Set what we are trying to extend and the operation it might
5294 have been extended with. */
5295 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
5296 XEXP (memory_extend_rtx, 0) = src;
5298 for (tmode = GET_MODE_WIDER_MODE (mode);
5299 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5300 tmode = GET_MODE_WIDER_MODE (tmode))
5302 struct table_elt *larger_elt;
5304 PUT_MODE (memory_extend_rtx, tmode);
5305 larger_elt = lookup (memory_extend_rtx,
5306 HASH (memory_extend_rtx, tmode), tmode);
5307 if (larger_elt == 0)
5308 continue;
5310 for (larger_elt = larger_elt->first_same_value;
5311 larger_elt; larger_elt = larger_elt->next_same_value)
5312 if (GET_CODE (larger_elt->exp) == REG)
5314 src_related = gen_lowpart_if_possible (mode,
5315 larger_elt->exp);
5316 break;
5319 if (src_related)
5320 break;
5323 #endif /* LOAD_EXTEND_OP */
5325 if (src == src_folded)
5326 src_folded = 0;
5328 /* At this point, ELT, if non-zero, points to a class of expressions
5329 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5330 and SRC_RELATED, if non-zero, each contain additional equivalent
5331 expressions. Prune these latter expressions by deleting expressions
5332 already in the equivalence class.
5334 Check for an equivalent identical to the destination. If found,
5335 this is the preferred equivalent since it will likely lead to
5336 elimination of the insn. Indicate this by placing it in
5337 `src_related'. */
5339 if (elt)
5340 elt = elt->first_same_value;
5341 for (p = elt; p; p = p->next_same_value)
5343 enum rtx_code code = GET_CODE (p->exp);
5345 /* If the expression is not valid, ignore it. Then we do not
5346 have to check for validity below. In most cases, we can use
5347 `rtx_equal_p', since canonicalization has already been done. */
5348 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
5349 continue;
5351 /* Also skip paradoxical subregs, unless that's what we're
5352 looking for. */
5353 if (code == SUBREG
5354 && (GET_MODE_SIZE (GET_MODE (p->exp))
5355 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
5356 && ! (src != 0
5357 && GET_CODE (src) == SUBREG
5358 && GET_MODE (src) == GET_MODE (p->exp)
5359 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5360 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
5361 continue;
5363 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
5364 src = 0;
5365 else if (src_folded && GET_CODE (src_folded) == code
5366 && rtx_equal_p (src_folded, p->exp))
5367 src_folded = 0;
5368 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
5369 && rtx_equal_p (src_eqv_here, p->exp))
5370 src_eqv_here = 0;
5371 else if (src_related && GET_CODE (src_related) == code
5372 && rtx_equal_p (src_related, p->exp))
5373 src_related = 0;
5375 /* This is the same as the destination of the insns, we want
5376 to prefer it. Copy it to src_related. The code below will
5377 then give it a negative cost. */
5378 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
5379 src_related = dest;
5382 /* Find the cheapest valid equivalent, trying all the available
5383 possibilities. Prefer items not in the hash table to ones
5384 that are when they are equal cost. Note that we can never
5385 worsen an insn as the current contents will also succeed.
5386 If we find an equivalent identical to the destination, use it as best,
5387 since this insn will probably be eliminated in that case. */
5388 if (src)
5390 if (rtx_equal_p (src, dest))
5391 src_cost = src_regcost = -1;
5392 else
5394 src_cost = COST (src);
5395 src_regcost = approx_reg_cost (src);
5399 if (src_eqv_here)
5401 if (rtx_equal_p (src_eqv_here, dest))
5402 src_eqv_cost = src_eqv_regcost = -1;
5403 else
5405 src_eqv_cost = COST (src_eqv_here);
5406 src_eqv_regcost = approx_reg_cost (src_eqv_here);
5410 if (src_folded)
5412 if (rtx_equal_p (src_folded, dest))
5413 src_folded_cost = src_folded_regcost = -1;
5414 else
5416 src_folded_cost = COST (src_folded);
5417 src_folded_regcost = approx_reg_cost (src_folded);
5421 if (src_related)
5423 if (rtx_equal_p (src_related, dest))
5424 src_related_cost = src_related_regcost = -1;
5425 else
5427 src_related_cost = COST (src_related);
5428 src_related_regcost = approx_reg_cost (src_related);
5432 /* If this was an indirect jump insn, a known label will really be
5433 cheaper even though it looks more expensive. */
5434 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
5435 src_folded = src_const, src_folded_cost = src_folded_regcost = -1;
5437 /* Terminate loop when replacement made. This must terminate since
5438 the current contents will be tested and will always be valid. */
5439 while (1)
5441 rtx trial;
5443 /* Skip invalid entries. */
5444 while (elt && GET_CODE (elt->exp) != REG
5445 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
5446 elt = elt->next_same_value;
5448 /* A paradoxical subreg would be bad here: it'll be the right
5449 size, but later may be adjusted so that the upper bits aren't
5450 what we want. So reject it. */
5451 if (elt != 0
5452 && GET_CODE (elt->exp) == SUBREG
5453 && (GET_MODE_SIZE (GET_MODE (elt->exp))
5454 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
5455 /* It is okay, though, if the rtx we're trying to match
5456 will ignore any of the bits we can't predict. */
5457 && ! (src != 0
5458 && GET_CODE (src) == SUBREG
5459 && GET_MODE (src) == GET_MODE (elt->exp)
5460 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5461 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
5463 elt = elt->next_same_value;
5464 continue;
5467 if (elt)
5469 src_elt_cost = elt->cost;
5470 src_elt_regcost = elt->regcost;
5473 /* Find cheapest and skip it for the next time. For items
5474 of equal cost, use this order:
5475 src_folded, src, src_eqv, src_related and hash table entry. */
5476 if (src_folded
5477 && preferrable (src_folded_cost, src_folded_regcost,
5478 src_cost, src_regcost) <= 0
5479 && preferrable (src_folded_cost, src_folded_regcost,
5480 src_eqv_cost, src_eqv_regcost) <= 0
5481 && preferrable (src_folded_cost, src_folded_regcost,
5482 src_related_cost, src_related_regcost) <= 0
5483 && preferrable (src_folded_cost, src_folded_regcost,
5484 src_elt_cost, src_elt_regcost) <= 0)
5486 trial = src_folded, src_folded_cost = MAX_COST;
5487 if (src_folded_force_flag)
5488 trial = force_const_mem (mode, trial);
5490 else if (src
5491 && preferrable (src_cost, src_regcost,
5492 src_eqv_cost, src_eqv_regcost) <= 0
5493 && preferrable (src_cost, src_regcost,
5494 src_related_cost, src_related_regcost) <= 0
5495 && preferrable (src_cost, src_regcost,
5496 src_elt_cost, src_elt_regcost) <= 0)
5497 trial = src, src_cost = MAX_COST;
5498 else if (src_eqv_here
5499 && preferrable (src_eqv_cost, src_eqv_regcost,
5500 src_related_cost, src_related_regcost) <= 0
5501 && preferrable (src_eqv_cost, src_eqv_regcost,
5502 src_elt_cost, src_elt_regcost) <= 0)
5503 trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
5504 else if (src_related
5505 && preferrable (src_related_cost, src_related_regcost,
5506 src_elt_cost, src_elt_regcost) <= 0)
5507 trial = copy_rtx (src_related), src_related_cost = MAX_COST;
5508 else
5510 trial = copy_rtx (elt->exp);
5511 elt = elt->next_same_value;
5512 src_elt_cost = MAX_COST;
5515 /* We don't normally have an insn matching (set (pc) (pc)), so
5516 check for this separately here. We will delete such an
5517 insn below.
5519 For other cases such as a table jump or conditional jump
5520 where we know the ultimate target, go ahead and replace the
5521 operand. While that may not make a valid insn, we will
5522 reemit the jump below (and also insert any necessary
5523 barriers). */
5524 if (n_sets == 1 && dest == pc_rtx
5525 && (trial == pc_rtx
5526 || (GET_CODE (trial) == LABEL_REF
5527 && ! condjump_p (insn))))
5529 SET_SRC (sets[i].rtl) = trial;
5530 cse_jumps_altered = 1;
5531 break;
5534 /* Look for a substitution that makes a valid insn. */
5535 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
5537 /* If we just made a substitution inside a libcall, then we
5538 need to make the same substitution in any notes attached
5539 to the RETVAL insn. */
5540 if (libcall_insn
5541 && (GET_CODE (sets[i].orig_src) == REG
5542 || GET_CODE (sets[i].orig_src) == SUBREG
5543 || GET_CODE (sets[i].orig_src) == MEM))
5544 replace_rtx (REG_NOTES (libcall_insn), sets[i].orig_src,
5545 canon_reg (SET_SRC (sets[i].rtl), insn));
5547 /* The result of apply_change_group can be ignored; see
5548 canon_reg. */
5550 validate_change (insn, &SET_SRC (sets[i].rtl),
5551 canon_reg (SET_SRC (sets[i].rtl), insn),
5553 apply_change_group ();
5554 break;
5557 /* If we previously found constant pool entries for
5558 constants and this is a constant, try making a
5559 pool entry. Put it in src_folded unless we already have done
5560 this since that is where it likely came from. */
5562 else if (constant_pool_entries_cost
5563 && CONSTANT_P (trial)
5564 /* Reject cases that will abort in decode_rtx_const.
5565 On the alpha when simplifying a switch, we get
5566 (const (truncate (minus (label_ref) (label_ref)))). */
5567 && ! (GET_CODE (trial) == CONST
5568 && GET_CODE (XEXP (trial, 0)) == TRUNCATE)
5569 /* Likewise on IA-64, except without the truncate. */
5570 && ! (GET_CODE (trial) == CONST
5571 && GET_CODE (XEXP (trial, 0)) == MINUS
5572 && GET_CODE (XEXP (XEXP (trial, 0), 0)) == LABEL_REF
5573 && GET_CODE (XEXP (XEXP (trial, 0), 1)) == LABEL_REF)
5574 && (src_folded == 0
5575 || (GET_CODE (src_folded) != MEM
5576 && ! src_folded_force_flag))
5577 && GET_MODE_CLASS (mode) != MODE_CC
5578 && mode != VOIDmode)
5580 src_folded_force_flag = 1;
5581 src_folded = trial;
5582 src_folded_cost = constant_pool_entries_cost;
5586 src = SET_SRC (sets[i].rtl);
5588 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5589 However, there is an important exception: If both are registers
5590 that are not the head of their equivalence class, replace SET_SRC
5591 with the head of the class. If we do not do this, we will have
5592 both registers live over a portion of the basic block. This way,
5593 their lifetimes will likely abut instead of overlapping. */
5594 if (GET_CODE (dest) == REG
5595 && REGNO_QTY_VALID_P (REGNO (dest)))
5597 int dest_q = REG_QTY (REGNO (dest));
5598 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5600 if (dest_ent->mode == GET_MODE (dest)
5601 && dest_ent->first_reg != REGNO (dest)
5602 && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
5603 /* Don't do this if the original insn had a hard reg as
5604 SET_SRC or SET_DEST. */
5605 && (GET_CODE (sets[i].src) != REG
5606 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
5607 && (GET_CODE (dest) != REG || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
5608 /* We can't call canon_reg here because it won't do anything if
5609 SRC is a hard register. */
5611 int src_q = REG_QTY (REGNO (src));
5612 struct qty_table_elem *src_ent = &qty_table[src_q];
5613 int first = src_ent->first_reg;
5614 rtx new_src
5615 = (first >= FIRST_PSEUDO_REGISTER
5616 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
5618 /* We must use validate-change even for this, because this
5619 might be a special no-op instruction, suitable only to
5620 tag notes onto. */
5621 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
5623 src = new_src;
5624 /* If we had a constant that is cheaper than what we are now
5625 setting SRC to, use that constant. We ignored it when we
5626 thought we could make this into a no-op. */
5627 if (src_const && COST (src_const) < COST (src)
5628 && validate_change (insn, &SET_SRC (sets[i].rtl),
5629 src_const, 0))
5630 src = src_const;
5635 /* If we made a change, recompute SRC values. */
5636 if (src != sets[i].src)
5638 cse_altered = 1;
5639 do_not_record = 0;
5640 hash_arg_in_memory = 0;
5641 sets[i].src = src;
5642 sets[i].src_hash = HASH (src, mode);
5643 sets[i].src_volatile = do_not_record;
5644 sets[i].src_in_memory = hash_arg_in_memory;
5645 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
5648 /* If this is a single SET, we are setting a register, and we have an
5649 equivalent constant, we want to add a REG_NOTE. We don't want
5650 to write a REG_EQUAL note for a constant pseudo since verifying that
5651 that pseudo hasn't been eliminated is a pain. Such a note also
5652 won't help anything.
5654 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
5655 which can be created for a reference to a compile time computable
5656 entry in a jump table. */
5658 if (n_sets == 1 && src_const && GET_CODE (dest) == REG
5659 && GET_CODE (src_const) != REG
5660 && ! (GET_CODE (src_const) == CONST
5661 && GET_CODE (XEXP (src_const, 0)) == MINUS
5662 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
5663 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
5665 /* Make sure that the rtx is not shared with any other insn. */
5666 src_const = copy_rtx (src_const);
5668 /* Record the actual constant value in a REG_EQUAL note, making
5669 a new one if one does not already exist. */
5670 set_unique_reg_note (insn, REG_EQUAL, src_const);
5672 /* If storing a constant value in a register that
5673 previously held the constant value 0,
5674 record this fact with a REG_WAS_0 note on this insn.
5676 Note that the *register* is required to have previously held 0,
5677 not just any register in the quantity and we must point to the
5678 insn that set that register to zero.
5680 Rather than track each register individually, we just see if
5681 the last set for this quantity was for this register. */
5683 if (REGNO_QTY_VALID_P (REGNO (dest)))
5685 int dest_q = REG_QTY (REGNO (dest));
5686 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5688 if (dest_ent->const_rtx == const0_rtx)
5690 /* See if we previously had a REG_WAS_0 note. */
5691 rtx note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
5692 rtx const_insn = dest_ent->const_insn;
5694 if ((tem = single_set (const_insn)) != 0
5695 && rtx_equal_p (SET_DEST (tem), dest))
5697 if (note)
5698 XEXP (note, 0) = const_insn;
5699 else
5700 REG_NOTES (insn)
5701 = gen_rtx_INSN_LIST (REG_WAS_0, const_insn,
5702 REG_NOTES (insn));
5708 /* Now deal with the destination. */
5709 do_not_record = 0;
5711 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5712 to the MEM or REG within it. */
5713 while (GET_CODE (dest) == SIGN_EXTRACT
5714 || GET_CODE (dest) == ZERO_EXTRACT
5715 || GET_CODE (dest) == SUBREG
5716 || GET_CODE (dest) == STRICT_LOW_PART)
5717 dest = XEXP (dest, 0);
5719 sets[i].inner_dest = dest;
5721 if (GET_CODE (dest) == MEM)
5723 #ifdef PUSH_ROUNDING
5724 /* Stack pushes invalidate the stack pointer. */
5725 rtx addr = XEXP (dest, 0);
5726 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
5727 && XEXP (addr, 0) == stack_pointer_rtx)
5728 invalidate (stack_pointer_rtx, Pmode);
5729 #endif
5730 dest = fold_rtx (dest, insn);
5733 /* Compute the hash code of the destination now,
5734 before the effects of this instruction are recorded,
5735 since the register values used in the address computation
5736 are those before this instruction. */
5737 sets[i].dest_hash = HASH (dest, mode);
5739 /* Don't enter a bit-field in the hash table
5740 because the value in it after the store
5741 may not equal what was stored, due to truncation. */
5743 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
5744 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
5746 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5748 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5749 && GET_CODE (width) == CONST_INT
5750 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5751 && ! (INTVAL (src_const)
5752 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5753 /* Exception: if the value is constant,
5754 and it won't be truncated, record it. */
5756 else
5758 /* This is chosen so that the destination will be invalidated
5759 but no new value will be recorded.
5760 We must invalidate because sometimes constant
5761 values can be recorded for bitfields. */
5762 sets[i].src_elt = 0;
5763 sets[i].src_volatile = 1;
5764 src_eqv = 0;
5765 src_eqv_elt = 0;
5769 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5770 the insn. */
5771 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5773 /* One less use of the label this insn used to jump to. */
5774 delete_insn (insn);
5775 cse_jumps_altered = 1;
5776 /* No more processing for this set. */
5777 sets[i].rtl = 0;
5780 /* If this SET is now setting PC to a label, we know it used to
5781 be a conditional or computed branch. */
5782 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
5784 /* Now emit a BARRIER after the unconditional jump. */
5785 if (NEXT_INSN (insn) == 0
5786 || GET_CODE (NEXT_INSN (insn)) != BARRIER)
5787 emit_barrier_after (insn);
5789 /* We reemit the jump in as many cases as possible just in
5790 case the form of an unconditional jump is significantly
5791 different than a computed jump or conditional jump.
5793 If this insn has multiple sets, then reemitting the
5794 jump is nontrivial. So instead we just force rerecognition
5795 and hope for the best. */
5796 if (n_sets == 1)
5798 rtx new = emit_jump_insn_after (gen_jump (XEXP (src, 0)), insn);
5800 JUMP_LABEL (new) = XEXP (src, 0);
5801 LABEL_NUSES (XEXP (src, 0))++;
5802 delete_insn (insn);
5803 insn = new;
5805 /* Now emit a BARRIER after the unconditional jump. */
5806 if (NEXT_INSN (insn) == 0
5807 || GET_CODE (NEXT_INSN (insn)) != BARRIER)
5808 emit_barrier_after (insn);
5810 else
5811 INSN_CODE (insn) = -1;
5813 never_reached_warning (insn, NULL);
5815 /* Do not bother deleting any unreachable code,
5816 let jump/flow do that. */
5818 cse_jumps_altered = 1;
5819 sets[i].rtl = 0;
5822 /* If destination is volatile, invalidate it and then do no further
5823 processing for this assignment. */
5825 else if (do_not_record)
5827 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5828 invalidate (dest, VOIDmode);
5829 else if (GET_CODE (dest) == MEM)
5831 /* Outgoing arguments for a libcall don't
5832 affect any recorded expressions. */
5833 if (! libcall_insn || insn == libcall_insn)
5834 invalidate (dest, VOIDmode);
5836 else if (GET_CODE (dest) == STRICT_LOW_PART
5837 || GET_CODE (dest) == ZERO_EXTRACT)
5838 invalidate (XEXP (dest, 0), GET_MODE (dest));
5839 sets[i].rtl = 0;
5842 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5843 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5845 #ifdef HAVE_cc0
5846 /* If setting CC0, record what it was set to, or a constant, if it
5847 is equivalent to a constant. If it is being set to a floating-point
5848 value, make a COMPARE with the appropriate constant of 0. If we
5849 don't do this, later code can interpret this as a test against
5850 const0_rtx, which can cause problems if we try to put it into an
5851 insn as a floating-point operand. */
5852 if (dest == cc0_rtx)
5854 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5855 this_insn_cc0_mode = mode;
5856 if (FLOAT_MODE_P (mode))
5857 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5858 CONST0_RTX (mode));
5860 #endif
5863 /* Now enter all non-volatile source expressions in the hash table
5864 if they are not already present.
5865 Record their equivalence classes in src_elt.
5866 This way we can insert the corresponding destinations into
5867 the same classes even if the actual sources are no longer in them
5868 (having been invalidated). */
5870 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5871 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5873 struct table_elt *elt;
5874 struct table_elt *classp = sets[0].src_elt;
5875 rtx dest = SET_DEST (sets[0].rtl);
5876 enum machine_mode eqvmode = GET_MODE (dest);
5878 if (GET_CODE (dest) == STRICT_LOW_PART)
5880 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5881 classp = 0;
5883 if (insert_regs (src_eqv, classp, 0))
5885 rehash_using_reg (src_eqv);
5886 src_eqv_hash = HASH (src_eqv, eqvmode);
5888 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5889 elt->in_memory = src_eqv_in_memory;
5890 src_eqv_elt = elt;
5892 /* Check to see if src_eqv_elt is the same as a set source which
5893 does not yet have an elt, and if so set the elt of the set source
5894 to src_eqv_elt. */
5895 for (i = 0; i < n_sets; i++)
5896 if (sets[i].rtl && sets[i].src_elt == 0
5897 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5898 sets[i].src_elt = src_eqv_elt;
5901 for (i = 0; i < n_sets; i++)
5902 if (sets[i].rtl && ! sets[i].src_volatile
5903 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5905 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5907 /* REG_EQUAL in setting a STRICT_LOW_PART
5908 gives an equivalent for the entire destination register,
5909 not just for the subreg being stored in now.
5910 This is a more interesting equivalence, so we arrange later
5911 to treat the entire reg as the destination. */
5912 sets[i].src_elt = src_eqv_elt;
5913 sets[i].src_hash = src_eqv_hash;
5915 else
5917 /* Insert source and constant equivalent into hash table, if not
5918 already present. */
5919 struct table_elt *classp = src_eqv_elt;
5920 rtx src = sets[i].src;
5921 rtx dest = SET_DEST (sets[i].rtl);
5922 enum machine_mode mode
5923 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5925 if (sets[i].src_elt == 0)
5927 /* Don't put a hard register source into the table if this is
5928 the last insn of a libcall. In this case, we only need
5929 to put src_eqv_elt in src_elt. */
5930 if (! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5932 struct table_elt *elt;
5934 /* Note that these insert_regs calls cannot remove
5935 any of the src_elt's, because they would have failed to
5936 match if not still valid. */
5937 if (insert_regs (src, classp, 0))
5939 rehash_using_reg (src);
5940 sets[i].src_hash = HASH (src, mode);
5942 elt = insert (src, classp, sets[i].src_hash, mode);
5943 elt->in_memory = sets[i].src_in_memory;
5944 sets[i].src_elt = classp = elt;
5946 else
5947 sets[i].src_elt = classp;
5949 if (sets[i].src_const && sets[i].src_const_elt == 0
5950 && src != sets[i].src_const
5951 && ! rtx_equal_p (sets[i].src_const, src))
5952 sets[i].src_elt = insert (sets[i].src_const, classp,
5953 sets[i].src_const_hash, mode);
5956 else if (sets[i].src_elt == 0)
5957 /* If we did not insert the source into the hash table (e.g., it was
5958 volatile), note the equivalence class for the REG_EQUAL value, if any,
5959 so that the destination goes into that class. */
5960 sets[i].src_elt = src_eqv_elt;
5962 invalidate_from_clobbers (x);
5964 /* Some registers are invalidated by subroutine calls. Memory is
5965 invalidated by non-constant calls. */
5967 if (GET_CODE (insn) == CALL_INSN)
5969 if (! CONST_OR_PURE_CALL_P (insn))
5970 invalidate_memory ();
5971 invalidate_for_call ();
5974 /* Now invalidate everything set by this instruction.
5975 If a SUBREG or other funny destination is being set,
5976 sets[i].rtl is still nonzero, so here we invalidate the reg
5977 a part of which is being set. */
5979 for (i = 0; i < n_sets; i++)
5980 if (sets[i].rtl)
5982 /* We can't use the inner dest, because the mode associated with
5983 a ZERO_EXTRACT is significant. */
5984 rtx dest = SET_DEST (sets[i].rtl);
5986 /* Needed for registers to remove the register from its
5987 previous quantity's chain.
5988 Needed for memory if this is a nonvarying address, unless
5989 we have just done an invalidate_memory that covers even those. */
5990 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5991 invalidate (dest, VOIDmode);
5992 else if (GET_CODE (dest) == MEM)
5994 /* Outgoing arguments for a libcall don't
5995 affect any recorded expressions. */
5996 if (! libcall_insn || insn == libcall_insn)
5997 invalidate (dest, VOIDmode);
5999 else if (GET_CODE (dest) == STRICT_LOW_PART
6000 || GET_CODE (dest) == ZERO_EXTRACT)
6001 invalidate (XEXP (dest, 0), GET_MODE (dest));
6004 /* A volatile ASM invalidates everything. */
6005 if (GET_CODE (insn) == INSN
6006 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
6007 && MEM_VOLATILE_P (PATTERN (insn)))
6008 flush_hash_table ();
6010 /* Make sure registers mentioned in destinations
6011 are safe for use in an expression to be inserted.
6012 This removes from the hash table
6013 any invalid entry that refers to one of these registers.
6015 We don't care about the return value from mention_regs because
6016 we are going to hash the SET_DEST values unconditionally. */
6018 for (i = 0; i < n_sets; i++)
6020 if (sets[i].rtl)
6022 rtx x = SET_DEST (sets[i].rtl);
6024 if (GET_CODE (x) != REG)
6025 mention_regs (x);
6026 else
6028 /* We used to rely on all references to a register becoming
6029 inaccessible when a register changes to a new quantity,
6030 since that changes the hash code. However, that is not
6031 safe, since after HASH_SIZE new quantities we get a
6032 hash 'collision' of a register with its own invalid
6033 entries. And since SUBREGs have been changed not to
6034 change their hash code with the hash code of the register,
6035 it wouldn't work any longer at all. So we have to check
6036 for any invalid references lying around now.
6037 This code is similar to the REG case in mention_regs,
6038 but it knows that reg_tick has been incremented, and
6039 it leaves reg_in_table as -1 . */
6040 unsigned int regno = REGNO (x);
6041 unsigned int endregno
6042 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
6043 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
6044 unsigned int i;
6046 for (i = regno; i < endregno; i++)
6048 if (REG_IN_TABLE (i) >= 0)
6050 remove_invalid_refs (i);
6051 REG_IN_TABLE (i) = -1;
6058 /* We may have just removed some of the src_elt's from the hash table.
6059 So replace each one with the current head of the same class. */
6061 for (i = 0; i < n_sets; i++)
6062 if (sets[i].rtl)
6064 if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
6065 /* If elt was removed, find current head of same class,
6066 or 0 if nothing remains of that class. */
6068 struct table_elt *elt = sets[i].src_elt;
6070 while (elt && elt->prev_same_value)
6071 elt = elt->prev_same_value;
6073 while (elt && elt->first_same_value == 0)
6074 elt = elt->next_same_value;
6075 sets[i].src_elt = elt ? elt->first_same_value : 0;
6079 /* Now insert the destinations into their equivalence classes. */
6081 for (i = 0; i < n_sets; i++)
6082 if (sets[i].rtl)
6084 rtx dest = SET_DEST (sets[i].rtl);
6085 rtx inner_dest = sets[i].inner_dest;
6086 struct table_elt *elt;
6088 /* Don't record value if we are not supposed to risk allocating
6089 floating-point values in registers that might be wider than
6090 memory. */
6091 if ((flag_float_store
6092 && GET_CODE (dest) == MEM
6093 && FLOAT_MODE_P (GET_MODE (dest)))
6094 /* Don't record BLKmode values, because we don't know the
6095 size of it, and can't be sure that other BLKmode values
6096 have the same or smaller size. */
6097 || GET_MODE (dest) == BLKmode
6098 /* Don't record values of destinations set inside a libcall block
6099 since we might delete the libcall. Things should have been set
6100 up so we won't want to reuse such a value, but we play it safe
6101 here. */
6102 || libcall_insn
6103 /* If we didn't put a REG_EQUAL value or a source into the hash
6104 table, there is no point is recording DEST. */
6105 || sets[i].src_elt == 0
6106 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
6107 or SIGN_EXTEND, don't record DEST since it can cause
6108 some tracking to be wrong.
6110 ??? Think about this more later. */
6111 || (GET_CODE (dest) == SUBREG
6112 && (GET_MODE_SIZE (GET_MODE (dest))
6113 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6114 && (GET_CODE (sets[i].src) == SIGN_EXTEND
6115 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
6116 continue;
6118 /* STRICT_LOW_PART isn't part of the value BEING set,
6119 and neither is the SUBREG inside it.
6120 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6121 if (GET_CODE (dest) == STRICT_LOW_PART)
6122 dest = SUBREG_REG (XEXP (dest, 0));
6124 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
6125 /* Registers must also be inserted into chains for quantities. */
6126 if (insert_regs (dest, sets[i].src_elt, 1))
6128 /* If `insert_regs' changes something, the hash code must be
6129 recalculated. */
6130 rehash_using_reg (dest);
6131 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
6134 if (GET_CODE (inner_dest) == MEM
6135 && GET_CODE (XEXP (inner_dest, 0)) == ADDRESSOF)
6136 /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say
6137 that (MEM (ADDRESSOF (X))) is equivalent to Y.
6138 Consider the case in which the address of the MEM is
6139 passed to a function, which alters the MEM. Then, if we
6140 later use Y instead of the MEM we'll miss the update. */
6141 elt = insert (dest, 0, sets[i].dest_hash, GET_MODE (dest));
6142 else
6143 elt = insert (dest, sets[i].src_elt,
6144 sets[i].dest_hash, GET_MODE (dest));
6146 elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM
6147 && (! RTX_UNCHANGING_P (sets[i].inner_dest)
6148 || FIXED_BASE_PLUS_P (XEXP (sets[i].inner_dest,
6149 0))));
6151 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6152 narrower than M2, and both M1 and M2 are the same number of words,
6153 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6154 make that equivalence as well.
6156 However, BAR may have equivalences for which gen_lowpart_if_possible
6157 will produce a simpler value than gen_lowpart_if_possible applied to
6158 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6159 BAR's equivalences. If we don't get a simplified form, make
6160 the SUBREG. It will not be used in an equivalence, but will
6161 cause two similar assignments to be detected.
6163 Note the loop below will find SUBREG_REG (DEST) since we have
6164 already entered SRC and DEST of the SET in the table. */
6166 if (GET_CODE (dest) == SUBREG
6167 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
6168 / UNITS_PER_WORD)
6169 == (GET_MODE_SIZE (GET_MODE (dest)) - 1) / UNITS_PER_WORD)
6170 && (GET_MODE_SIZE (GET_MODE (dest))
6171 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6172 && sets[i].src_elt != 0)
6174 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
6175 struct table_elt *elt, *classp = 0;
6177 for (elt = sets[i].src_elt->first_same_value; elt;
6178 elt = elt->next_same_value)
6180 rtx new_src = 0;
6181 unsigned src_hash;
6182 struct table_elt *src_elt;
6184 /* Ignore invalid entries. */
6185 if (GET_CODE (elt->exp) != REG
6186 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
6187 continue;
6189 new_src = gen_lowpart_if_possible (new_mode, elt->exp);
6190 if (new_src == 0)
6191 new_src = gen_rtx_SUBREG (new_mode, elt->exp, 0);
6193 src_hash = HASH (new_src, new_mode);
6194 src_elt = lookup (new_src, src_hash, new_mode);
6196 /* Put the new source in the hash table is if isn't
6197 already. */
6198 if (src_elt == 0)
6200 if (insert_regs (new_src, classp, 0))
6202 rehash_using_reg (new_src);
6203 src_hash = HASH (new_src, new_mode);
6205 src_elt = insert (new_src, classp, src_hash, new_mode);
6206 src_elt->in_memory = elt->in_memory;
6208 else if (classp && classp != src_elt->first_same_value)
6209 /* Show that two things that we've seen before are
6210 actually the same. */
6211 merge_equiv_classes (src_elt, classp);
6213 classp = src_elt->first_same_value;
6214 /* Ignore invalid entries. */
6215 while (classp
6216 && GET_CODE (classp->exp) != REG
6217 && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
6218 classp = classp->next_same_value;
6223 /* Special handling for (set REG0 REG1) where REG0 is the
6224 "cheapest", cheaper than REG1. After cse, REG1 will probably not
6225 be used in the sequel, so (if easily done) change this insn to
6226 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
6227 that computed their value. Then REG1 will become a dead store
6228 and won't cloud the situation for later optimizations.
6230 Do not make this change if REG1 is a hard register, because it will
6231 then be used in the sequel and we may be changing a two-operand insn
6232 into a three-operand insn.
6234 Also do not do this if we are operating on a copy of INSN.
6236 Also don't do this if INSN ends a libcall; this would cause an unrelated
6237 register to be set in the middle of a libcall, and we then get bad code
6238 if the libcall is deleted. */
6240 if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
6241 && NEXT_INSN (PREV_INSN (insn)) == insn
6242 && GET_CODE (SET_SRC (sets[0].rtl)) == REG
6243 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
6244 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
6246 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
6247 struct qty_table_elem *src_ent = &qty_table[src_q];
6249 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
6250 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
6252 rtx prev = prev_nonnote_insn (insn);
6254 /* Do not swap the registers around if the previous instruction
6255 attaches a REG_EQUIV note to REG1.
6257 ??? It's not entirely clear whether we can transfer a REG_EQUIV
6258 from the pseudo that originally shadowed an incoming argument
6259 to another register. Some uses of REG_EQUIV might rely on it
6260 being attached to REG1 rather than REG2.
6262 This section previously turned the REG_EQUIV into a REG_EQUAL
6263 note. We cannot do that because REG_EQUIV may provide an
6264 uninitialised stack slot when REG_PARM_STACK_SPACE is used. */
6266 if (prev != 0 && GET_CODE (prev) == INSN
6267 && GET_CODE (PATTERN (prev)) == SET
6268 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
6269 && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
6271 rtx dest = SET_DEST (sets[0].rtl);
6272 rtx src = SET_SRC (sets[0].rtl);
6273 rtx note;
6275 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
6276 validate_change (insn, &SET_DEST (sets[0].rtl), src, 1);
6277 validate_change (insn, &SET_SRC (sets[0].rtl), dest, 1);
6278 apply_change_group ();
6280 /* If there was a REG_WAS_0 note on PREV, remove it. Move
6281 any REG_WAS_0 note on INSN to PREV. */
6282 note = find_reg_note (prev, REG_WAS_0, NULL_RTX);
6283 if (note)
6284 remove_note (prev, note);
6286 note = find_reg_note (insn, REG_WAS_0, NULL_RTX);
6287 if (note)
6289 remove_note (insn, note);
6290 XEXP (note, 1) = REG_NOTES (prev);
6291 REG_NOTES (prev) = note;
6294 /* If INSN has a REG_EQUAL note, and this note mentions
6295 REG0, then we must delete it, because the value in
6296 REG0 has changed. If the note's value is REG1, we must
6297 also delete it because that is now this insn's dest. */
6298 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6299 if (note != 0
6300 && (reg_mentioned_p (dest, XEXP (note, 0))
6301 || rtx_equal_p (src, XEXP (note, 0))))
6302 remove_note (insn, note);
6307 /* If this is a conditional jump insn, record any known equivalences due to
6308 the condition being tested. */
6310 last_jump_equiv_class = 0;
6311 if (GET_CODE (insn) == JUMP_INSN
6312 && n_sets == 1 && GET_CODE (x) == SET
6313 && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
6314 record_jump_equiv (insn, 0);
6316 #ifdef HAVE_cc0
6317 /* If the previous insn set CC0 and this insn no longer references CC0,
6318 delete the previous insn. Here we use the fact that nothing expects CC0
6319 to be valid over an insn, which is true until the final pass. */
6320 if (prev_insn && GET_CODE (prev_insn) == INSN
6321 && (tem = single_set (prev_insn)) != 0
6322 && SET_DEST (tem) == cc0_rtx
6323 && ! reg_mentioned_p (cc0_rtx, x))
6324 delete_insn (prev_insn);
6326 prev_insn_cc0 = this_insn_cc0;
6327 prev_insn_cc0_mode = this_insn_cc0_mode;
6328 #endif
6330 prev_insn = insn;
6333 /* Remove from the hash table all expressions that reference memory. */
6335 static void
6336 invalidate_memory ()
6338 int i;
6339 struct table_elt *p, *next;
6341 for (i = 0; i < HASH_SIZE; i++)
6342 for (p = table[i]; p; p = next)
6344 next = p->next_same_hash;
6345 if (p->in_memory)
6346 remove_from_table (p, i);
6350 /* If ADDR is an address that implicitly affects the stack pointer, return
6351 1 and update the register tables to show the effect. Else, return 0. */
6353 static int
6354 addr_affects_sp_p (addr)
6355 rtx addr;
6357 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
6358 && GET_CODE (XEXP (addr, 0)) == REG
6359 && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
6361 if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
6362 REG_TICK (STACK_POINTER_REGNUM)++;
6364 /* This should be *very* rare. */
6365 if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
6366 invalidate (stack_pointer_rtx, VOIDmode);
6368 return 1;
6371 return 0;
6374 /* Perform invalidation on the basis of everything about an insn
6375 except for invalidating the actual places that are SET in it.
6376 This includes the places CLOBBERed, and anything that might
6377 alias with something that is SET or CLOBBERed.
6379 X is the pattern of the insn. */
6381 static void
6382 invalidate_from_clobbers (x)
6383 rtx x;
6385 if (GET_CODE (x) == CLOBBER)
6387 rtx ref = XEXP (x, 0);
6388 if (ref)
6390 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6391 || GET_CODE (ref) == MEM)
6392 invalidate (ref, VOIDmode);
6393 else if (GET_CODE (ref) == STRICT_LOW_PART
6394 || GET_CODE (ref) == ZERO_EXTRACT)
6395 invalidate (XEXP (ref, 0), GET_MODE (ref));
6398 else if (GET_CODE (x) == PARALLEL)
6400 int i;
6401 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
6403 rtx y = XVECEXP (x, 0, i);
6404 if (GET_CODE (y) == CLOBBER)
6406 rtx ref = XEXP (y, 0);
6407 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6408 || GET_CODE (ref) == MEM)
6409 invalidate (ref, VOIDmode);
6410 else if (GET_CODE (ref) == STRICT_LOW_PART
6411 || GET_CODE (ref) == ZERO_EXTRACT)
6412 invalidate (XEXP (ref, 0), GET_MODE (ref));
6418 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6419 and replace any registers in them with either an equivalent constant
6420 or the canonical form of the register. If we are inside an address,
6421 only do this if the address remains valid.
6423 OBJECT is 0 except when within a MEM in which case it is the MEM.
6425 Return the replacement for X. */
6427 static rtx
6428 cse_process_notes (x, object)
6429 rtx x;
6430 rtx object;
6432 enum rtx_code code = GET_CODE (x);
6433 const char *fmt = GET_RTX_FORMAT (code);
6434 int i;
6436 switch (code)
6438 case CONST_INT:
6439 case CONST:
6440 case SYMBOL_REF:
6441 case LABEL_REF:
6442 case CONST_DOUBLE:
6443 case CONST_VECTOR:
6444 case PC:
6445 case CC0:
6446 case LO_SUM:
6447 return x;
6449 case MEM:
6450 validate_change (x, &XEXP (x, 0),
6451 cse_process_notes (XEXP (x, 0), x), 0);
6452 return x;
6454 case EXPR_LIST:
6455 case INSN_LIST:
6456 if (REG_NOTE_KIND (x) == REG_EQUAL)
6457 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
6458 if (XEXP (x, 1))
6459 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
6460 return x;
6462 case SIGN_EXTEND:
6463 case ZERO_EXTEND:
6464 case SUBREG:
6466 rtx new = cse_process_notes (XEXP (x, 0), object);
6467 /* We don't substitute VOIDmode constants into these rtx,
6468 since they would impede folding. */
6469 if (GET_MODE (new) != VOIDmode)
6470 validate_change (object, &XEXP (x, 0), new, 0);
6471 return x;
6474 case REG:
6475 i = REG_QTY (REGNO (x));
6477 /* Return a constant or a constant register. */
6478 if (REGNO_QTY_VALID_P (REGNO (x)))
6480 struct qty_table_elem *ent = &qty_table[i];
6482 if (ent->const_rtx != NULL_RTX
6483 && (CONSTANT_P (ent->const_rtx)
6484 || GET_CODE (ent->const_rtx) == REG))
6486 rtx new = gen_lowpart_if_possible (GET_MODE (x), ent->const_rtx);
6487 if (new)
6488 return new;
6492 /* Otherwise, canonicalize this register. */
6493 return canon_reg (x, NULL_RTX);
6495 default:
6496 break;
6499 for (i = 0; i < GET_RTX_LENGTH (code); i++)
6500 if (fmt[i] == 'e')
6501 validate_change (object, &XEXP (x, i),
6502 cse_process_notes (XEXP (x, i), object), 0);
6504 return x;
6507 /* Find common subexpressions between the end test of a loop and the beginning
6508 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6510 Often we have a loop where an expression in the exit test is used
6511 in the body of the loop. For example "while (*p) *q++ = *p++;".
6512 Because of the way we duplicate the loop exit test in front of the loop,
6513 however, we don't detect that common subexpression. This will be caught
6514 when global cse is implemented, but this is a quite common case.
6516 This function handles the most common cases of these common expressions.
6517 It is called after we have processed the basic block ending with the
6518 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6519 jumps to a label used only once. */
6521 static void
6522 cse_around_loop (loop_start)
6523 rtx loop_start;
6525 rtx insn;
6526 int i;
6527 struct table_elt *p;
6529 /* If the jump at the end of the loop doesn't go to the start, we don't
6530 do anything. */
6531 for (insn = PREV_INSN (loop_start);
6532 insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
6533 insn = PREV_INSN (insn))
6536 if (insn == 0
6537 || GET_CODE (insn) != NOTE
6538 || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
6539 return;
6541 /* If the last insn of the loop (the end test) was an NE comparison,
6542 we will interpret it as an EQ comparison, since we fell through
6543 the loop. Any equivalences resulting from that comparison are
6544 therefore not valid and must be invalidated. */
6545 if (last_jump_equiv_class)
6546 for (p = last_jump_equiv_class->first_same_value; p;
6547 p = p->next_same_value)
6549 if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
6550 || (GET_CODE (p->exp) == SUBREG
6551 && GET_CODE (SUBREG_REG (p->exp)) == REG))
6552 invalidate (p->exp, VOIDmode);
6553 else if (GET_CODE (p->exp) == STRICT_LOW_PART
6554 || GET_CODE (p->exp) == ZERO_EXTRACT)
6555 invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
6558 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6559 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6561 The only thing we do with SET_DEST is invalidate entries, so we
6562 can safely process each SET in order. It is slightly less efficient
6563 to do so, but we only want to handle the most common cases.
6565 The gen_move_insn call in cse_set_around_loop may create new pseudos.
6566 These pseudos won't have valid entries in any of the tables indexed
6567 by register number, such as reg_qty. We avoid out-of-range array
6568 accesses by not processing any instructions created after cse started. */
6570 for (insn = NEXT_INSN (loop_start);
6571 GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
6572 && INSN_UID (insn) < max_insn_uid
6573 && ! (GET_CODE (insn) == NOTE
6574 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
6575 insn = NEXT_INSN (insn))
6577 if (INSN_P (insn)
6578 && (GET_CODE (PATTERN (insn)) == SET
6579 || GET_CODE (PATTERN (insn)) == CLOBBER))
6580 cse_set_around_loop (PATTERN (insn), insn, loop_start);
6581 else if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == PARALLEL)
6582 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6583 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
6584 || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
6585 cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
6586 loop_start);
6590 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6591 since they are done elsewhere. This function is called via note_stores. */
6593 static void
6594 invalidate_skipped_set (dest, set, data)
6595 rtx set;
6596 rtx dest;
6597 void *data ATTRIBUTE_UNUSED;
6599 enum rtx_code code = GET_CODE (dest);
6601 if (code == MEM
6602 && ! addr_affects_sp_p (dest) /* If this is not a stack push ... */
6603 /* There are times when an address can appear varying and be a PLUS
6604 during this scan when it would be a fixed address were we to know
6605 the proper equivalences. So invalidate all memory if there is
6606 a BLKmode or nonscalar memory reference or a reference to a
6607 variable address. */
6608 && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
6609 || cse_rtx_varies_p (XEXP (dest, 0), 0)))
6611 invalidate_memory ();
6612 return;
6615 if (GET_CODE (set) == CLOBBER
6616 #ifdef HAVE_cc0
6617 || dest == cc0_rtx
6618 #endif
6619 || dest == pc_rtx)
6620 return;
6622 if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
6623 invalidate (XEXP (dest, 0), GET_MODE (dest));
6624 else if (code == REG || code == SUBREG || code == MEM)
6625 invalidate (dest, VOIDmode);
6628 /* Invalidate all insns from START up to the end of the function or the
6629 next label. This called when we wish to CSE around a block that is
6630 conditionally executed. */
6632 static void
6633 invalidate_skipped_block (start)
6634 rtx start;
6636 rtx insn;
6638 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
6639 insn = NEXT_INSN (insn))
6641 if (! INSN_P (insn))
6642 continue;
6644 if (GET_CODE (insn) == CALL_INSN)
6646 if (! CONST_OR_PURE_CALL_P (insn))
6647 invalidate_memory ();
6648 invalidate_for_call ();
6651 invalidate_from_clobbers (PATTERN (insn));
6652 note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
6656 /* If modifying X will modify the value in *DATA (which is really an
6657 `rtx *'), indicate that fact by setting the pointed to value to
6658 NULL_RTX. */
6660 static void
6661 cse_check_loop_start (x, set, data)
6662 rtx x;
6663 rtx set ATTRIBUTE_UNUSED;
6664 void *data;
6666 rtx *cse_check_loop_start_value = (rtx *) data;
6668 if (*cse_check_loop_start_value == NULL_RTX
6669 || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
6670 return;
6672 if ((GET_CODE (x) == MEM && GET_CODE (*cse_check_loop_start_value) == MEM)
6673 || reg_overlap_mentioned_p (x, *cse_check_loop_start_value))
6674 *cse_check_loop_start_value = NULL_RTX;
6677 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6678 a loop that starts with the label at LOOP_START.
6680 If X is a SET, we see if its SET_SRC is currently in our hash table.
6681 If so, we see if it has a value equal to some register used only in the
6682 loop exit code (as marked by jump.c).
6684 If those two conditions are true, we search backwards from the start of
6685 the loop to see if that same value was loaded into a register that still
6686 retains its value at the start of the loop.
6688 If so, we insert an insn after the load to copy the destination of that
6689 load into the equivalent register and (try to) replace our SET_SRC with that
6690 register.
6692 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6694 static void
6695 cse_set_around_loop (x, insn, loop_start)
6696 rtx x;
6697 rtx insn;
6698 rtx loop_start;
6700 struct table_elt *src_elt;
6702 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6703 are setting PC or CC0 or whose SET_SRC is already a register. */
6704 if (GET_CODE (x) == SET
6705 && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
6706 && GET_CODE (SET_SRC (x)) != REG)
6708 src_elt = lookup (SET_SRC (x),
6709 HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
6710 GET_MODE (SET_DEST (x)));
6712 if (src_elt)
6713 for (src_elt = src_elt->first_same_value; src_elt;
6714 src_elt = src_elt->next_same_value)
6715 if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
6716 && COST (src_elt->exp) < COST (SET_SRC (x)))
6718 rtx p, set;
6720 /* Look for an insn in front of LOOP_START that sets
6721 something in the desired mode to SET_SRC (x) before we hit
6722 a label or CALL_INSN. */
6724 for (p = prev_nonnote_insn (loop_start);
6725 p && GET_CODE (p) != CALL_INSN
6726 && GET_CODE (p) != CODE_LABEL;
6727 p = prev_nonnote_insn (p))
6728 if ((set = single_set (p)) != 0
6729 && GET_CODE (SET_DEST (set)) == REG
6730 && GET_MODE (SET_DEST (set)) == src_elt->mode
6731 && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
6733 /* We now have to ensure that nothing between P
6734 and LOOP_START modified anything referenced in
6735 SET_SRC (x). We know that nothing within the loop
6736 can modify it, or we would have invalidated it in
6737 the hash table. */
6738 rtx q;
6739 rtx cse_check_loop_start_value = SET_SRC (x);
6740 for (q = p; q != loop_start; q = NEXT_INSN (q))
6741 if (INSN_P (q))
6742 note_stores (PATTERN (q),
6743 cse_check_loop_start,
6744 &cse_check_loop_start_value);
6746 /* If nothing was changed and we can replace our
6747 SET_SRC, add an insn after P to copy its destination
6748 to what we will be replacing SET_SRC with. */
6749 if (cse_check_loop_start_value
6750 && validate_change (insn, &SET_SRC (x),
6751 src_elt->exp, 0))
6753 /* If this creates new pseudos, this is unsafe,
6754 because the regno of new pseudo is unsuitable
6755 to index into reg_qty when cse_insn processes
6756 the new insn. Therefore, if a new pseudo was
6757 created, discard this optimization. */
6758 int nregs = max_reg_num ();
6759 rtx move
6760 = gen_move_insn (src_elt->exp, SET_DEST (set));
6761 if (nregs != max_reg_num ())
6763 if (! validate_change (insn, &SET_SRC (x),
6764 SET_SRC (set), 0))
6765 abort ();
6767 else
6768 emit_insn_after (move, p);
6770 break;
6775 /* Deal with the destination of X affecting the stack pointer. */
6776 addr_affects_sp_p (SET_DEST (x));
6778 /* See comment on similar code in cse_insn for explanation of these
6779 tests. */
6780 if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
6781 || GET_CODE (SET_DEST (x)) == MEM)
6782 invalidate (SET_DEST (x), VOIDmode);
6783 else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
6784 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
6785 invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
6788 /* Find the end of INSN's basic block and return its range,
6789 the total number of SETs in all the insns of the block, the last insn of the
6790 block, and the branch path.
6792 The branch path indicates which branches should be followed. If a non-zero
6793 path size is specified, the block should be rescanned and a different set
6794 of branches will be taken. The branch path is only used if
6795 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
6797 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6798 used to describe the block. It is filled in with the information about
6799 the current block. The incoming structure's branch path, if any, is used
6800 to construct the output branch path. */
6802 void
6803 cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks)
6804 rtx insn;
6805 struct cse_basic_block_data *data;
6806 int follow_jumps;
6807 int after_loop;
6808 int skip_blocks;
6810 rtx p = insn, q;
6811 int nsets = 0;
6812 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
6813 rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
6814 int path_size = data->path_size;
6815 int path_entry = 0;
6816 int i;
6818 /* Update the previous branch path, if any. If the last branch was
6819 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6820 shorten the path by one and look at the previous branch. We know that
6821 at least one branch must have been taken if PATH_SIZE is non-zero. */
6822 while (path_size > 0)
6824 if (data->path[path_size - 1].status != NOT_TAKEN)
6826 data->path[path_size - 1].status = NOT_TAKEN;
6827 break;
6829 else
6830 path_size--;
6833 /* If the first instruction is marked with QImode, that means we've
6834 already processed this block. Our caller will look at DATA->LAST
6835 to figure out where to go next. We want to return the next block
6836 in the instruction stream, not some branched-to block somewhere
6837 else. We accomplish this by pretending our called forbid us to
6838 follow jumps, or skip blocks. */
6839 if (GET_MODE (insn) == QImode)
6840 follow_jumps = skip_blocks = 0;
6842 /* Scan to end of this basic block. */
6843 while (p && GET_CODE (p) != CODE_LABEL)
6845 /* Don't cse out the end of a loop. This makes a difference
6846 only for the unusual loops that always execute at least once;
6847 all other loops have labels there so we will stop in any case.
6848 Cse'ing out the end of the loop is dangerous because it
6849 might cause an invariant expression inside the loop
6850 to be reused after the end of the loop. This would make it
6851 hard to move the expression out of the loop in loop.c,
6852 especially if it is one of several equivalent expressions
6853 and loop.c would like to eliminate it.
6855 If we are running after loop.c has finished, we can ignore
6856 the NOTE_INSN_LOOP_END. */
6858 if (! after_loop && GET_CODE (p) == NOTE
6859 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
6860 break;
6862 /* Don't cse over a call to setjmp; on some machines (eg VAX)
6863 the regs restored by the longjmp come from
6864 a later time than the setjmp. */
6865 if (PREV_INSN (p) && GET_CODE (PREV_INSN (p)) == CALL_INSN
6866 && find_reg_note (PREV_INSN (p), REG_SETJMP, NULL))
6867 break;
6869 /* A PARALLEL can have lots of SETs in it,
6870 especially if it is really an ASM_OPERANDS. */
6871 if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
6872 nsets += XVECLEN (PATTERN (p), 0);
6873 else if (GET_CODE (p) != NOTE)
6874 nsets += 1;
6876 /* Ignore insns made by CSE; they cannot affect the boundaries of
6877 the basic block. */
6879 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
6880 high_cuid = INSN_CUID (p);
6881 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
6882 low_cuid = INSN_CUID (p);
6884 /* See if this insn is in our branch path. If it is and we are to
6885 take it, do so. */
6886 if (path_entry < path_size && data->path[path_entry].branch == p)
6888 if (data->path[path_entry].status != NOT_TAKEN)
6889 p = JUMP_LABEL (p);
6891 /* Point to next entry in path, if any. */
6892 path_entry++;
6895 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
6896 was specified, we haven't reached our maximum path length, there are
6897 insns following the target of the jump, this is the only use of the
6898 jump label, and the target label is preceded by a BARRIER.
6900 Alternatively, we can follow the jump if it branches around a
6901 block of code and there are no other branches into the block.
6902 In this case invalidate_skipped_block will be called to invalidate any
6903 registers set in the block when following the jump. */
6905 else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1
6906 && GET_CODE (p) == JUMP_INSN
6907 && GET_CODE (PATTERN (p)) == SET
6908 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
6909 && JUMP_LABEL (p) != 0
6910 && LABEL_NUSES (JUMP_LABEL (p)) == 1
6911 && NEXT_INSN (JUMP_LABEL (p)) != 0)
6913 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
6914 if ((GET_CODE (q) != NOTE
6915 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
6916 || (PREV_INSN (q) && GET_CODE (PREV_INSN (q)) == CALL_INSN
6917 && find_reg_note (PREV_INSN (q), REG_SETJMP, NULL)))
6918 && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
6919 break;
6921 /* If we ran into a BARRIER, this code is an extension of the
6922 basic block when the branch is taken. */
6923 if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
6925 /* Don't allow ourself to keep walking around an
6926 always-executed loop. */
6927 if (next_real_insn (q) == next)
6929 p = NEXT_INSN (p);
6930 continue;
6933 /* Similarly, don't put a branch in our path more than once. */
6934 for (i = 0; i < path_entry; i++)
6935 if (data->path[i].branch == p)
6936 break;
6938 if (i != path_entry)
6939 break;
6941 data->path[path_entry].branch = p;
6942 data->path[path_entry++].status = TAKEN;
6944 /* This branch now ends our path. It was possible that we
6945 didn't see this branch the last time around (when the
6946 insn in front of the target was a JUMP_INSN that was
6947 turned into a no-op). */
6948 path_size = path_entry;
6950 p = JUMP_LABEL (p);
6951 /* Mark block so we won't scan it again later. */
6952 PUT_MODE (NEXT_INSN (p), QImode);
6954 /* Detect a branch around a block of code. */
6955 else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
6957 rtx tmp;
6959 if (next_real_insn (q) == next)
6961 p = NEXT_INSN (p);
6962 continue;
6965 for (i = 0; i < path_entry; i++)
6966 if (data->path[i].branch == p)
6967 break;
6969 if (i != path_entry)
6970 break;
6972 /* This is no_labels_between_p (p, q) with an added check for
6973 reaching the end of a function (in case Q precedes P). */
6974 for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
6975 if (GET_CODE (tmp) == CODE_LABEL)
6976 break;
6978 if (tmp == q)
6980 data->path[path_entry].branch = p;
6981 data->path[path_entry++].status = AROUND;
6983 path_size = path_entry;
6985 p = JUMP_LABEL (p);
6986 /* Mark block so we won't scan it again later. */
6987 PUT_MODE (NEXT_INSN (p), QImode);
6991 p = NEXT_INSN (p);
6994 data->low_cuid = low_cuid;
6995 data->high_cuid = high_cuid;
6996 data->nsets = nsets;
6997 data->last = p;
6999 /* If all jumps in the path are not taken, set our path length to zero
7000 so a rescan won't be done. */
7001 for (i = path_size - 1; i >= 0; i--)
7002 if (data->path[i].status != NOT_TAKEN)
7003 break;
7005 if (i == -1)
7006 data->path_size = 0;
7007 else
7008 data->path_size = path_size;
7010 /* End the current branch path. */
7011 data->path[path_size].branch = 0;
7014 /* Perform cse on the instructions of a function.
7015 F is the first instruction.
7016 NREGS is one plus the highest pseudo-reg number used in the instruction.
7018 AFTER_LOOP is 1 if this is the cse call done after loop optimization
7019 (only if -frerun-cse-after-loop).
7021 Returns 1 if jump_optimize should be redone due to simplifications
7022 in conditional jump instructions. */
7025 cse_main (f, nregs, after_loop, file)
7026 rtx f;
7027 int nregs;
7028 int after_loop;
7029 FILE *file;
7031 struct cse_basic_block_data val;
7032 rtx insn = f;
7033 int i;
7035 cse_jumps_altered = 0;
7036 recorded_label_ref = 0;
7037 constant_pool_entries_cost = 0;
7038 val.path_size = 0;
7040 init_recog ();
7041 init_alias_analysis ();
7043 max_reg = nregs;
7045 max_insn_uid = get_max_uid ();
7047 reg_eqv_table = (struct reg_eqv_elem *)
7048 xmalloc (nregs * sizeof (struct reg_eqv_elem));
7050 #ifdef LOAD_EXTEND_OP
7052 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
7053 and change the code and mode as appropriate. */
7054 memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX);
7055 #endif
7057 /* Reset the counter indicating how many elements have been made
7058 thus far. */
7059 n_elements_made = 0;
7061 /* Find the largest uid. */
7063 max_uid = get_max_uid ();
7064 uid_cuid = (int *) xcalloc (max_uid + 1, sizeof (int));
7066 /* Compute the mapping from uids to cuids.
7067 CUIDs are numbers assigned to insns, like uids,
7068 except that cuids increase monotonically through the code.
7069 Don't assign cuids to line-number NOTEs, so that the distance in cuids
7070 between two insns is not affected by -g. */
7072 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
7074 if (GET_CODE (insn) != NOTE
7075 || NOTE_LINE_NUMBER (insn) < 0)
7076 INSN_CUID (insn) = ++i;
7077 else
7078 /* Give a line number note the same cuid as preceding insn. */
7079 INSN_CUID (insn) = i;
7082 ggc_push_context ();
7084 /* Loop over basic blocks.
7085 Compute the maximum number of qty's needed for each basic block
7086 (which is 2 for each SET). */
7087 insn = f;
7088 while (insn)
7090 cse_altered = 0;
7091 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
7092 flag_cse_skip_blocks);
7094 /* If this basic block was already processed or has no sets, skip it. */
7095 if (val.nsets == 0 || GET_MODE (insn) == QImode)
7097 PUT_MODE (insn, VOIDmode);
7098 insn = (val.last ? NEXT_INSN (val.last) : 0);
7099 val.path_size = 0;
7100 continue;
7103 cse_basic_block_start = val.low_cuid;
7104 cse_basic_block_end = val.high_cuid;
7105 max_qty = val.nsets * 2;
7107 if (file)
7108 fnotice (file, ";; Processing block from %d to %d, %d sets.\n",
7109 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
7110 val.nsets);
7112 /* Make MAX_QTY bigger to give us room to optimize
7113 past the end of this basic block, if that should prove useful. */
7114 if (max_qty < 500)
7115 max_qty = 500;
7117 max_qty += max_reg;
7119 /* If this basic block is being extended by following certain jumps,
7120 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7121 Otherwise, we start after this basic block. */
7122 if (val.path_size > 0)
7123 cse_basic_block (insn, val.last, val.path, 0);
7124 else
7126 int old_cse_jumps_altered = cse_jumps_altered;
7127 rtx temp;
7129 /* When cse changes a conditional jump to an unconditional
7130 jump, we want to reprocess the block, since it will give
7131 us a new branch path to investigate. */
7132 cse_jumps_altered = 0;
7133 temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
7134 if (cse_jumps_altered == 0
7135 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7136 insn = temp;
7138 cse_jumps_altered |= old_cse_jumps_altered;
7141 if (cse_altered)
7142 ggc_collect ();
7144 #ifdef USE_C_ALLOCA
7145 alloca (0);
7146 #endif
7149 ggc_pop_context ();
7151 if (max_elements_made < n_elements_made)
7152 max_elements_made = n_elements_made;
7154 /* Clean up. */
7155 end_alias_analysis ();
7156 free (uid_cuid);
7157 free (reg_eqv_table);
7159 return cse_jumps_altered || recorded_label_ref;
7162 /* Process a single basic block. FROM and TO and the limits of the basic
7163 block. NEXT_BRANCH points to the branch path when following jumps or
7164 a null path when not following jumps.
7166 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
7167 loop. This is true when we are being called for the last time on a
7168 block and this CSE pass is before loop.c. */
7170 static rtx
7171 cse_basic_block (from, to, next_branch, around_loop)
7172 rtx from, to;
7173 struct branch_path *next_branch;
7174 int around_loop;
7176 rtx insn;
7177 int to_usage = 0;
7178 rtx libcall_insn = NULL_RTX;
7179 int num_insns = 0;
7181 /* This array is undefined before max_reg, so only allocate
7182 the space actually needed and adjust the start. */
7184 qty_table
7185 = (struct qty_table_elem *) xmalloc ((max_qty - max_reg)
7186 * sizeof (struct qty_table_elem));
7187 qty_table -= max_reg;
7189 new_basic_block ();
7191 /* TO might be a label. If so, protect it from being deleted. */
7192 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7193 ++LABEL_NUSES (to);
7195 for (insn = from; insn != to; insn = NEXT_INSN (insn))
7197 enum rtx_code code = GET_CODE (insn);
7199 /* If we have processed 1,000 insns, flush the hash table to
7200 avoid extreme quadratic behavior. We must not include NOTEs
7201 in the count since there may be more of them when generating
7202 debugging information. If we clear the table at different
7203 times, code generated with -g -O might be different than code
7204 generated with -O but not -g.
7206 ??? This is a real kludge and needs to be done some other way.
7207 Perhaps for 2.9. */
7208 if (code != NOTE && num_insns++ > 1000)
7210 flush_hash_table ();
7211 num_insns = 0;
7214 /* See if this is a branch that is part of the path. If so, and it is
7215 to be taken, do so. */
7216 if (next_branch->branch == insn)
7218 enum taken status = next_branch++->status;
7219 if (status != NOT_TAKEN)
7221 if (status == TAKEN)
7222 record_jump_equiv (insn, 1);
7223 else
7224 invalidate_skipped_block (NEXT_INSN (insn));
7226 /* Set the last insn as the jump insn; it doesn't affect cc0.
7227 Then follow this branch. */
7228 #ifdef HAVE_cc0
7229 prev_insn_cc0 = 0;
7230 #endif
7231 prev_insn = insn;
7232 insn = JUMP_LABEL (insn);
7233 continue;
7237 if (GET_MODE (insn) == QImode)
7238 PUT_MODE (insn, VOIDmode);
7240 if (GET_RTX_CLASS (code) == 'i')
7242 rtx p;
7244 /* Process notes first so we have all notes in canonical forms when
7245 looking for duplicate operations. */
7247 if (REG_NOTES (insn))
7248 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
7250 /* Track when we are inside in LIBCALL block. Inside such a block,
7251 we do not want to record destinations. The last insn of a
7252 LIBCALL block is not considered to be part of the block, since
7253 its destination is the result of the block and hence should be
7254 recorded. */
7256 if (REG_NOTES (insn) != 0)
7258 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
7259 libcall_insn = XEXP (p, 0);
7260 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7261 libcall_insn = 0;
7264 cse_insn (insn, libcall_insn);
7266 /* If we haven't already found an insn where we added a LABEL_REF,
7267 check this one. */
7268 if (GET_CODE (insn) == INSN && ! recorded_label_ref
7269 && for_each_rtx (&PATTERN (insn), check_for_label_ref,
7270 (void *) insn))
7271 recorded_label_ref = 1;
7274 /* If INSN is now an unconditional jump, skip to the end of our
7275 basic block by pretending that we just did the last insn in the
7276 basic block. If we are jumping to the end of our block, show
7277 that we can have one usage of TO. */
7279 if (any_uncondjump_p (insn))
7281 if (to == 0)
7283 free (qty_table + max_reg);
7284 return 0;
7287 if (JUMP_LABEL (insn) == to)
7288 to_usage = 1;
7290 /* Maybe TO was deleted because the jump is unconditional.
7291 If so, there is nothing left in this basic block. */
7292 /* ??? Perhaps it would be smarter to set TO
7293 to whatever follows this insn,
7294 and pretend the basic block had always ended here. */
7295 if (INSN_DELETED_P (to))
7296 break;
7298 insn = PREV_INSN (to);
7301 /* See if it is ok to keep on going past the label
7302 which used to end our basic block. Remember that we incremented
7303 the count of that label, so we decrement it here. If we made
7304 a jump unconditional, TO_USAGE will be one; in that case, we don't
7305 want to count the use in that jump. */
7307 if (to != 0 && NEXT_INSN (insn) == to
7308 && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
7310 struct cse_basic_block_data val;
7311 rtx prev;
7313 insn = NEXT_INSN (to);
7315 /* If TO was the last insn in the function, we are done. */
7316 if (insn == 0)
7318 free (qty_table + max_reg);
7319 return 0;
7322 /* If TO was preceded by a BARRIER we are done with this block
7323 because it has no continuation. */
7324 prev = prev_nonnote_insn (to);
7325 if (prev && GET_CODE (prev) == BARRIER)
7327 free (qty_table + max_reg);
7328 return insn;
7331 /* Find the end of the following block. Note that we won't be
7332 following branches in this case. */
7333 to_usage = 0;
7334 val.path_size = 0;
7335 cse_end_of_basic_block (insn, &val, 0, 0, 0);
7337 /* If the tables we allocated have enough space left
7338 to handle all the SETs in the next basic block,
7339 continue through it. Otherwise, return,
7340 and that block will be scanned individually. */
7341 if (val.nsets * 2 + next_qty > max_qty)
7342 break;
7344 cse_basic_block_start = val.low_cuid;
7345 cse_basic_block_end = val.high_cuid;
7346 to = val.last;
7348 /* Prevent TO from being deleted if it is a label. */
7349 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7350 ++LABEL_NUSES (to);
7352 /* Back up so we process the first insn in the extension. */
7353 insn = PREV_INSN (insn);
7357 if (next_qty > max_qty)
7358 abort ();
7360 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7361 the previous insn is the only insn that branches to the head of a loop,
7362 we can cse into the loop. Don't do this if we changed the jump
7363 structure of a loop unless we aren't going to be following jumps. */
7365 insn = prev_nonnote_insn (to);
7366 if ((cse_jumps_altered == 0
7367 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7368 && around_loop && to != 0
7369 && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
7370 && GET_CODE (insn) == JUMP_INSN
7371 && JUMP_LABEL (insn) != 0
7372 && LABEL_NUSES (JUMP_LABEL (insn)) == 1)
7373 cse_around_loop (JUMP_LABEL (insn));
7375 free (qty_table + max_reg);
7377 return to ? NEXT_INSN (to) : 0;
7380 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
7381 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
7383 static int
7384 check_for_label_ref (rtl, data)
7385 rtx *rtl;
7386 void *data;
7388 rtx insn = (rtx) data;
7390 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
7391 we must rerun jump since it needs to place the note. If this is a
7392 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
7393 since no REG_LABEL will be added. */
7394 return (GET_CODE (*rtl) == LABEL_REF
7395 && ! LABEL_REF_NONLOCAL_P (*rtl)
7396 && LABEL_P (XEXP (*rtl, 0))
7397 && INSN_UID (XEXP (*rtl, 0)) != 0
7398 && ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)));
7401 /* Count the number of times registers are used (not set) in X.
7402 COUNTS is an array in which we accumulate the count, INCR is how much
7403 we count each register usage.
7405 Don't count a usage of DEST, which is the SET_DEST of a SET which
7406 contains X in its SET_SRC. This is because such a SET does not
7407 modify the liveness of DEST. */
7409 static void
7410 count_reg_usage (x, counts, dest, incr)
7411 rtx x;
7412 int *counts;
7413 rtx dest;
7414 int incr;
7416 enum rtx_code code;
7417 const char *fmt;
7418 int i, j;
7420 if (x == 0)
7421 return;
7423 switch (code = GET_CODE (x))
7425 case REG:
7426 if (x != dest)
7427 counts[REGNO (x)] += incr;
7428 return;
7430 case PC:
7431 case CC0:
7432 case CONST:
7433 case CONST_INT:
7434 case CONST_DOUBLE:
7435 case CONST_VECTOR:
7436 case SYMBOL_REF:
7437 case LABEL_REF:
7438 return;
7440 case CLOBBER:
7441 /* If we are clobbering a MEM, mark any registers inside the address
7442 as being used. */
7443 if (GET_CODE (XEXP (x, 0)) == MEM)
7444 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
7445 return;
7447 case SET:
7448 /* Unless we are setting a REG, count everything in SET_DEST. */
7449 if (GET_CODE (SET_DEST (x)) != REG)
7450 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
7452 /* If SRC has side-effects, then we can't delete this insn, so the
7453 usage of SET_DEST inside SRC counts.
7455 ??? Strictly-speaking, we might be preserving this insn
7456 because some other SET has side-effects, but that's hard
7457 to do and can't happen now. */
7458 count_reg_usage (SET_SRC (x), counts,
7459 side_effects_p (SET_SRC (x)) ? NULL_RTX : SET_DEST (x),
7460 incr);
7461 return;
7463 case CALL_INSN:
7464 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr);
7465 /* Fall through. */
7467 case INSN:
7468 case JUMP_INSN:
7469 count_reg_usage (PATTERN (x), counts, NULL_RTX, incr);
7471 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7472 use them. */
7474 count_reg_usage (REG_NOTES (x), counts, NULL_RTX, incr);
7475 return;
7477 case EXPR_LIST:
7478 case INSN_LIST:
7479 if (REG_NOTE_KIND (x) == REG_EQUAL
7480 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE))
7481 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
7482 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
7483 return;
7485 default:
7486 break;
7489 fmt = GET_RTX_FORMAT (code);
7490 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
7492 if (fmt[i] == 'e')
7493 count_reg_usage (XEXP (x, i), counts, dest, incr);
7494 else if (fmt[i] == 'E')
7495 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7496 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
7500 /* Return true if set is live. */
7501 static bool
7502 set_live_p (set, insn, counts)
7503 rtx set;
7504 rtx insn ATTRIBUTE_UNUSED; /* Only used with HAVE_cc0. */
7505 int *counts;
7507 #ifdef HAVE_cc0
7508 rtx tem;
7509 #endif
7511 if (set_noop_p (set))
7514 #ifdef HAVE_cc0
7515 else if (GET_CODE (SET_DEST (set)) == CC0
7516 && !side_effects_p (SET_SRC (set))
7517 && ((tem = next_nonnote_insn (insn)) == 0
7518 || !INSN_P (tem)
7519 || !reg_referenced_p (cc0_rtx, PATTERN (tem))))
7520 return false;
7521 #endif
7522 else if (GET_CODE (SET_DEST (set)) != REG
7523 || REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
7524 || counts[REGNO (SET_DEST (set))] != 0
7525 || side_effects_p (SET_SRC (set))
7526 /* An ADDRESSOF expression can turn into a use of the
7527 internal arg pointer, so always consider the
7528 internal arg pointer live. If it is truly dead,
7529 flow will delete the initializing insn. */
7530 || (SET_DEST (set) == current_function_internal_arg_pointer))
7531 return true;
7532 return false;
7535 /* Return true if insn is live. */
7537 static bool
7538 insn_live_p (insn, counts)
7539 rtx insn;
7540 int *counts;
7542 int i;
7543 if (GET_CODE (PATTERN (insn)) == SET)
7544 return set_live_p (PATTERN (insn), insn, counts);
7545 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
7547 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
7549 rtx elt = XVECEXP (PATTERN (insn), 0, i);
7551 if (GET_CODE (elt) == SET)
7553 if (set_live_p (elt, insn, counts))
7554 return true;
7556 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
7557 return true;
7559 return false;
7561 else
7562 return true;
7565 /* Return true if libcall is dead as a whole. */
7567 static bool
7568 dead_libcall_p (insn, counts)
7569 rtx insn;
7570 int *counts;
7572 rtx note;
7573 /* See if there's a REG_EQUAL note on this insn and try to
7574 replace the source with the REG_EQUAL expression.
7576 We assume that insns with REG_RETVALs can only be reg->reg
7577 copies at this point. */
7578 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
7579 if (note)
7581 rtx set = single_set (insn);
7582 rtx new = simplify_rtx (XEXP (note, 0));
7584 if (!new)
7585 new = XEXP (note, 0);
7587 /* While changing insn, we must update the counts accordingly. */
7588 count_reg_usage (insn, counts, NULL_RTX, -1);
7590 if (set && validate_change (insn, &SET_SRC (set), new, 0))
7592 count_reg_usage (insn, counts, NULL_RTX, 1);
7593 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
7594 remove_note (insn, note);
7595 return true;
7597 count_reg_usage (insn, counts, NULL_RTX, 1);
7599 return false;
7602 /* Scan all the insns and delete any that are dead; i.e., they store a register
7603 that is never used or they copy a register to itself.
7605 This is used to remove insns made obviously dead by cse, loop or other
7606 optimizations. It improves the heuristics in loop since it won't try to
7607 move dead invariants out of loops or make givs for dead quantities. The
7608 remaining passes of the compilation are also sped up. */
7611 delete_trivially_dead_insns (insns, nreg)
7612 rtx insns;
7613 int nreg;
7615 int *counts;
7616 rtx insn, prev;
7617 int in_libcall = 0, dead_libcall = 0;
7618 int ndead = 0, nlastdead, niterations = 0;
7620 timevar_push (TV_DELETE_TRIVIALLY_DEAD);
7621 /* First count the number of times each register is used. */
7622 counts = (int *) xcalloc (nreg, sizeof (int));
7623 for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
7624 count_reg_usage (insn, counts, NULL_RTX, 1);
7628 nlastdead = ndead;
7629 niterations++;
7630 /* Go from the last insn to the first and delete insns that only set unused
7631 registers or copy a register to itself. As we delete an insn, remove
7632 usage counts for registers it uses.
7634 The first jump optimization pass may leave a real insn as the last
7635 insn in the function. We must not skip that insn or we may end
7636 up deleting code that is not really dead. */
7637 insn = get_last_insn ();
7638 if (! INSN_P (insn))
7639 insn = prev_real_insn (insn);
7641 for (; insn; insn = prev)
7643 int live_insn = 0;
7645 prev = prev_real_insn (insn);
7647 /* Don't delete any insns that are part of a libcall block unless
7648 we can delete the whole libcall block.
7650 Flow or loop might get confused if we did that. Remember
7651 that we are scanning backwards. */
7652 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7654 in_libcall = 1;
7655 live_insn = 1;
7656 dead_libcall = dead_libcall_p (insn, counts);
7658 else if (in_libcall)
7659 live_insn = ! dead_libcall;
7660 else
7661 live_insn = insn_live_p (insn, counts);
7663 /* If this is a dead insn, delete it and show registers in it aren't
7664 being used. */
7666 if (! live_insn)
7668 count_reg_usage (insn, counts, NULL_RTX, -1);
7669 delete_insn_and_edges (insn);
7670 ndead++;
7673 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
7675 in_libcall = 0;
7676 dead_libcall = 0;
7680 while (ndead != nlastdead);
7682 if (rtl_dump_file && ndead)
7683 fprintf (rtl_dump_file, "Deleted %i trivially dead insns; %i iterations\n",
7684 ndead, niterations);
7685 /* Clean up. */
7686 free (counts);
7687 timevar_pop (TV_DELETE_TRIVIALLY_DEAD);
7688 return ndead;