1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3 1999, 2000, 2001, 2002, 2003 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
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
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
23 /* stdio.h must precede rtl.h for FFS. */
25 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
35 #include "insn-config.h"
47 /* The basic idea of common subexpression elimination is to go
48 through the code, keeping a record of expressions that would
49 have the same value at the current scan point, and replacing
50 expressions encountered with the cheapest equivalent expression.
52 It is too complicated to keep track of the different possibilities
53 when control paths merge in this code; so, at each label, we forget all
54 that is known and start fresh. This can be described as processing each
55 extended basic block separately. We have a separate pass to perform
58 Note CSE can turn a conditional or computed jump into a nop or
59 an unconditional jump. When this occurs we arrange to run the jump
60 optimizer after CSE to delete the unreachable code.
62 We use two data structures to record the equivalent expressions:
63 a hash table for most expressions, and a vector of "quantity
64 numbers" to record equivalent (pseudo) registers.
66 The use of the special data structure for registers is desirable
67 because it is faster. It is possible because registers references
68 contain a fairly small number, the register number, taken from
69 a contiguously allocated series, and two register references are
70 identical if they have the same number. General expressions
71 do not have any such thing, so the only way to retrieve the
72 information recorded on an expression other than a register
73 is to keep it in a hash table.
75 Registers and "quantity numbers":
77 At the start of each basic block, all of the (hardware and pseudo)
78 registers used in the function are given distinct quantity
79 numbers to indicate their contents. During scan, when the code
80 copies one register into another, we copy the quantity number.
81 When a register is loaded in any other way, we allocate a new
82 quantity number to describe the value generated by this operation.
83 `reg_qty' records what quantity a register is currently thought
86 All real quantity numbers are greater than or equal to `max_reg'.
87 If register N has not been assigned a quantity, reg_qty[N] will equal N.
89 Quantity numbers below `max_reg' do not exist and none of the `qty_table'
90 entries should be referenced with an index below `max_reg'.
92 We also maintain a bidirectional chain of registers for each
93 quantity number. The `qty_table` members `first_reg' and `last_reg',
94 and `reg_eqv_table' members `next' and `prev' hold these chains.
96 The first register in a chain is the one whose lifespan is least local.
97 Among equals, it is the one that was seen first.
98 We replace any equivalent register with that one.
100 If two registers have the same quantity number, it must be true that
101 REG expressions with qty_table `mode' must be in the hash table for both
102 registers and must be in the same class.
104 The converse is not true. Since hard registers may be referenced in
105 any mode, two REG expressions might be equivalent in the hash table
106 but not have the same quantity number if the quantity number of one
107 of the registers is not the same mode as those expressions.
109 Constants and quantity numbers
111 When a quantity has a known constant value, that value is stored
112 in the appropriate qty_table `const_rtx'. This is in addition to
113 putting the constant in the hash table as is usual for non-regs.
115 Whether a reg or a constant is preferred is determined by the configuration
116 macro CONST_COSTS and will often depend on the constant value. In any
117 event, expressions containing constants can be simplified, by fold_rtx.
119 When a quantity has a known nearly constant value (such as an address
120 of a stack slot), that value is stored in the appropriate qty_table
123 Integer constants don't have a machine mode. However, cse
124 determines the intended machine mode from the destination
125 of the instruction that moves the constant. The machine mode
126 is recorded in the hash table along with the actual RTL
127 constant expression so that different modes are kept separate.
131 To record known equivalences among expressions in general
132 we use a hash table called `table'. It has a fixed number of buckets
133 that contain chains of `struct table_elt' elements for expressions.
134 These chains connect the elements whose expressions have the same
137 Other chains through the same elements connect the elements which
138 currently have equivalent values.
140 Register references in an expression are canonicalized before hashing
141 the expression. This is done using `reg_qty' and qty_table `first_reg'.
142 The hash code of a register reference is computed using the quantity
143 number, not the register number.
145 When the value of an expression changes, it is necessary to remove from the
146 hash table not just that expression but all expressions whose values
147 could be different as a result.
149 1. If the value changing is in memory, except in special cases
150 ANYTHING referring to memory could be changed. That is because
151 nobody knows where a pointer does not point.
152 The function `invalidate_memory' removes what is necessary.
154 The special cases are when the address is constant or is
155 a constant plus a fixed register such as the frame pointer
156 or a static chain pointer. When such addresses are stored in,
157 we can tell exactly which other such addresses must be invalidated
158 due to overlap. `invalidate' does this.
159 All expressions that refer to non-constant
160 memory addresses are also invalidated. `invalidate_memory' does this.
162 2. If the value changing is a register, all expressions
163 containing references to that register, and only those,
166 Because searching the entire hash table for expressions that contain
167 a register is very slow, we try to figure out when it isn't necessary.
168 Precisely, this is necessary only when expressions have been
169 entered in the hash table using this register, and then the value has
170 changed, and then another expression wants to be added to refer to
171 the register's new value. This sequence of circumstances is rare
172 within any one basic block.
174 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
175 reg_tick[i] is incremented whenever a value is stored in register i.
176 reg_in_table[i] holds -1 if no references to register i have been
177 entered in the table; otherwise, it contains the value reg_tick[i] had
178 when the references were entered. If we want to enter a reference
179 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
180 Until we want to enter a new entry, the mere fact that the two vectors
181 don't match makes the entries be ignored if anyone tries to match them.
183 Registers themselves are entered in the hash table as well as in
184 the equivalent-register chains. However, the vectors `reg_tick'
185 and `reg_in_table' do not apply to expressions which are simple
186 register references. These expressions are removed from the table
187 immediately when they become invalid, and this can be done even if
188 we do not immediately search for all the expressions that refer to
191 A CLOBBER rtx in an instruction invalidates its operand for further
192 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
193 invalidates everything that resides in memory.
197 Constant expressions that differ only by an additive integer
198 are called related. When a constant expression is put in
199 the table, the related expression with no constant term
200 is also entered. These are made to point at each other
201 so that it is possible to find out if there exists any
202 register equivalent to an expression related to a given expression. */
204 /* One plus largest register number used in this function. */
208 /* One plus largest instruction UID used in this function at time of
211 static int max_insn_uid;
213 /* Length of qty_table vector. We know in advance we will not need
214 a quantity number this big. */
218 /* Next quantity number to be allocated.
219 This is 1 + the largest number needed so far. */
223 /* Per-qty information tracking.
225 `first_reg' and `last_reg' track the head and tail of the
226 chain of registers which currently contain this quantity.
228 `mode' contains the machine mode of this quantity.
230 `const_rtx' holds the rtx of the constant value of this
231 quantity, if known. A summations of the frame/arg pointer
232 and a constant can also be entered here. When this holds
233 a known value, `const_insn' is the insn which stored the
236 `comparison_{code,const,qty}' are used to track when a
237 comparison between a quantity and some constant or register has
238 been passed. In such a case, we know the results of the comparison
239 in case we see it again. These members record a comparison that
240 is known to be true. `comparison_code' holds the rtx code of such
241 a comparison, else it is set to UNKNOWN and the other two
242 comparison members are undefined. `comparison_const' holds
243 the constant being compared against, or zero if the comparison
244 is not against a constant. `comparison_qty' holds the quantity
245 being compared against when the result is known. If the comparison
246 is not with a register, `comparison_qty' is -1. */
248 struct qty_table_elem
252 rtx comparison_const;
254 unsigned int first_reg, last_reg;
255 /* The sizes of these fields should match the sizes of the
256 code and mode fields of struct rtx_def (see rtl.h). */
257 ENUM_BITFIELD(rtx_code) comparison_code : 16;
258 ENUM_BITFIELD(machine_mode) mode : 8;
261 /* The table of all qtys, indexed by qty number. */
262 static struct qty_table_elem *qty_table;
265 /* For machines that have a CC0, we do not record its value in the hash
266 table since its use is guaranteed to be the insn immediately following
267 its definition and any other insn is presumed to invalidate it.
269 Instead, we store below the value last assigned to CC0. If it should
270 happen to be a constant, it is stored in preference to the actual
271 assigned value. In case it is a constant, we store the mode in which
272 the constant should be interpreted. */
274 static rtx prev_insn_cc0;
275 static enum machine_mode prev_insn_cc0_mode;
277 /* Previous actual insn. 0 if at first insn of basic block. */
279 static rtx prev_insn;
282 /* Insn being scanned. */
284 static rtx this_insn;
286 /* Index by register number, gives the number of the next (or
287 previous) register in the chain of registers sharing the same
290 Or -1 if this register is at the end of the chain.
292 If reg_qty[N] == N, reg_eqv_table[N].next is undefined. */
294 /* Per-register equivalence chain. */
300 /* The table of all register equivalence chains. */
301 static struct reg_eqv_elem *reg_eqv_table;
305 /* Next in hash chain. */
306 struct cse_reg_info *hash_next;
308 /* The next cse_reg_info structure in the free or used list. */
309 struct cse_reg_info *next;
314 /* The quantity number of the register's current contents. */
317 /* The number of times the register has been altered in the current
321 /* The REG_TICK value at which rtx's containing this register are
322 valid in the hash table. If this does not equal the current
323 reg_tick value, such expressions existing in the hash table are
327 /* The SUBREG that was set when REG_TICK was last incremented. Set
328 to -1 if the last store was to the whole register, not a subreg. */
329 unsigned int subreg_ticked;
332 /* A free list of cse_reg_info entries. */
333 static struct cse_reg_info *cse_reg_info_free_list;
335 /* A used list of cse_reg_info entries. */
336 static struct cse_reg_info *cse_reg_info_used_list;
337 static struct cse_reg_info *cse_reg_info_used_list_end;
339 /* A mapping from registers to cse_reg_info data structures. */
340 #define REGHASH_SHIFT 7
341 #define REGHASH_SIZE (1 << REGHASH_SHIFT)
342 #define REGHASH_MASK (REGHASH_SIZE - 1)
343 static struct cse_reg_info *reg_hash[REGHASH_SIZE];
345 #define REGHASH_FN(REGNO) \
346 (((REGNO) ^ ((REGNO) >> REGHASH_SHIFT)) & REGHASH_MASK)
348 /* The last lookup we did into the cse_reg_info_tree. This allows us
349 to cache repeated lookups. */
350 static unsigned int cached_regno;
351 static struct cse_reg_info *cached_cse_reg_info;
353 /* A HARD_REG_SET containing all the hard registers for which there is
354 currently a REG expression in the hash table. Note the difference
355 from the above variables, which indicate if the REG is mentioned in some
356 expression in the table. */
358 static HARD_REG_SET hard_regs_in_table;
360 /* CUID of insn that starts the basic block currently being cse-processed. */
362 static int cse_basic_block_start;
364 /* CUID of insn that ends the basic block currently being cse-processed. */
366 static int cse_basic_block_end;
368 /* Vector mapping INSN_UIDs to cuids.
369 The cuids are like uids but increase monotonically always.
370 We use them to see whether a reg is used outside a given basic block. */
372 static int *uid_cuid;
374 /* Highest UID in UID_CUID. */
377 /* Get the cuid of an insn. */
379 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
381 /* Nonzero if this pass has made changes, and therefore it's
382 worthwhile to run the garbage collector. */
384 static int cse_altered;
386 /* Nonzero if cse has altered conditional jump insns
387 in such a way that jump optimization should be redone. */
389 static int cse_jumps_altered;
391 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
392 REG_LABEL, we have to rerun jump after CSE to put in the note. */
393 static int recorded_label_ref;
395 /* canon_hash stores 1 in do_not_record
396 if it notices a reference to CC0, PC, or some other volatile
399 static int do_not_record;
401 #ifdef LOAD_EXTEND_OP
403 /* Scratch rtl used when looking for load-extended copy of a MEM. */
404 static rtx memory_extend_rtx;
407 /* canon_hash stores 1 in hash_arg_in_memory
408 if it notices a reference to memory within the expression being hashed. */
410 static int hash_arg_in_memory;
412 /* The hash table contains buckets which are chains of `struct table_elt's,
413 each recording one expression's information.
414 That expression is in the `exp' field.
416 The canon_exp field contains a canonical (from the point of view of
417 alias analysis) version of the `exp' field.
419 Those elements with the same hash code are chained in both directions
420 through the `next_same_hash' and `prev_same_hash' fields.
422 Each set of expressions with equivalent values
423 are on a two-way chain through the `next_same_value'
424 and `prev_same_value' fields, and all point with
425 the `first_same_value' field at the first element in
426 that chain. The chain is in order of increasing cost.
427 Each element's cost value is in its `cost' field.
429 The `in_memory' field is nonzero for elements that
430 involve any reference to memory. These elements are removed
431 whenever a write is done to an unidentified location in memory.
432 To be safe, we assume that a memory address is unidentified unless
433 the address is either a symbol constant or a constant plus
434 the frame pointer or argument pointer.
436 The `related_value' field is used to connect related expressions
437 (that differ by adding an integer).
438 The related expressions are chained in a circular fashion.
439 `related_value' is zero for expressions for which this
442 The `cost' field stores the cost of this element's expression.
443 The `regcost' field stores the value returned by approx_reg_cost for
444 this element's expression.
446 The `is_const' flag is set if the element is a constant (including
449 The `flag' field is used as a temporary during some search routines.
451 The `mode' field is usually the same as GET_MODE (`exp'), but
452 if `exp' is a CONST_INT and has no machine mode then the `mode'
453 field is the mode it was being used as. Each constant is
454 recorded separately for each mode it is used with. */
460 struct table_elt *next_same_hash;
461 struct table_elt *prev_same_hash;
462 struct table_elt *next_same_value;
463 struct table_elt *prev_same_value;
464 struct table_elt *first_same_value;
465 struct table_elt *related_value;
468 /* The size of this field should match the size
469 of the mode field of struct rtx_def (see rtl.h). */
470 ENUM_BITFIELD(machine_mode) mode : 8;
476 /* We don't want a lot of buckets, because we rarely have very many
477 things stored in the hash table, and a lot of buckets slows
478 down a lot of loops that happen frequently. */
480 #define HASH_SIZE (1 << HASH_SHIFT)
481 #define HASH_MASK (HASH_SIZE - 1)
483 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
484 register (hard registers may require `do_not_record' to be set). */
487 ((GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
488 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
489 : canon_hash (X, M)) & HASH_MASK)
491 /* Determine whether register number N is considered a fixed register for the
492 purpose of approximating register costs.
493 It is desirable to replace other regs with fixed regs, to reduce need for
495 A reg wins if it is either the frame pointer or designated as fixed. */
496 #define FIXED_REGNO_P(N) \
497 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
498 || fixed_regs[N] || global_regs[N])
500 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
501 hard registers and pointers into the frame are the cheapest with a cost
502 of 0. Next come pseudos with a cost of one and other hard registers with
503 a cost of 2. Aside from these special cases, call `rtx_cost'. */
505 #define CHEAP_REGNO(N) \
506 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
507 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
508 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
509 || ((N) < FIRST_PSEUDO_REGISTER \
510 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
512 #define COST(X) (GET_CODE (X) == REG ? 0 : notreg_cost (X, SET))
513 #define COST_IN(X,OUTER) (GET_CODE (X) == REG ? 0 : notreg_cost (X, OUTER))
515 /* Get the info associated with register N. */
517 #define GET_CSE_REG_INFO(N) \
518 (((N) == cached_regno && cached_cse_reg_info) \
519 ? cached_cse_reg_info : get_cse_reg_info ((N)))
521 /* Get the number of times this register has been updated in this
524 #define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
526 /* Get the point at which REG was recorded in the table. */
528 #define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
530 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
533 #define SUBREG_TICKED(N) ((GET_CSE_REG_INFO (N))->subreg_ticked)
535 /* Get the quantity number for REG. */
537 #define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
539 /* Determine if the quantity number for register X represents a valid index
540 into the qty_table. */
542 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (int) (N))
544 static struct table_elt *table[HASH_SIZE];
546 /* Chain of `struct table_elt's made so far for this function
547 but currently removed from the table. */
549 static struct table_elt *free_element_chain;
551 /* Number of `struct table_elt' structures made so far for this function. */
553 static int n_elements_made;
555 /* Maximum value `n_elements_made' has had so far in this compilation
556 for functions previously processed. */
558 static int max_elements_made;
560 /* Surviving equivalence class when two equivalence classes are merged
561 by recording the effects of a jump in the last insn. Zero if the
562 last insn was not a conditional jump. */
564 static struct table_elt *last_jump_equiv_class;
566 /* Set to the cost of a constant pool reference if one was found for a
567 symbolic constant. If this was found, it means we should try to
568 convert constants into constant pool entries if they don't fit in
571 static int constant_pool_entries_cost;
573 /* This data describes a block that will be processed by cse_basic_block. */
575 struct cse_basic_block_data
577 /* Lowest CUID value of insns in block. */
579 /* Highest CUID value of insns in block. */
581 /* Total number of SETs in block. */
583 /* Last insn in the block. */
585 /* Size of current branch path, if any. */
587 /* Current branch path, indicating which branches will be taken. */
590 /* The branch insn. */
592 /* Whether it should be taken or not. AROUND is the same as taken
593 except that it is used when the destination label is not preceded
595 enum taken {TAKEN, NOT_TAKEN, AROUND} status;
599 static bool fixed_base_plus_p (rtx x);
600 static int notreg_cost (rtx, enum rtx_code);
601 static int approx_reg_cost_1 (rtx *, void *);
602 static int approx_reg_cost (rtx);
603 static int preferrable (int, int, int, int);
604 static void new_basic_block (void);
605 static void make_new_qty (unsigned int, enum machine_mode);
606 static void make_regs_eqv (unsigned int, unsigned int);
607 static void delete_reg_equiv (unsigned int);
608 static int mention_regs (rtx);
609 static int insert_regs (rtx, struct table_elt *, int);
610 static void remove_from_table (struct table_elt *, unsigned);
611 static struct table_elt *lookup (rtx, unsigned, enum machine_mode);
612 static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);
613 static rtx lookup_as_function (rtx, enum rtx_code);
614 static struct table_elt *insert (rtx, struct table_elt *, unsigned,
616 static void merge_equiv_classes (struct table_elt *, struct table_elt *);
617 static void invalidate (rtx, enum machine_mode);
618 static int cse_rtx_varies_p (rtx, int);
619 static void remove_invalid_refs (unsigned int);
620 static void remove_invalid_subreg_refs (unsigned int, unsigned int,
622 static void rehash_using_reg (rtx);
623 static void invalidate_memory (void);
624 static void invalidate_for_call (void);
625 static rtx use_related_value (rtx, struct table_elt *);
626 static unsigned canon_hash (rtx, enum machine_mode);
627 static unsigned canon_hash_string (const char *);
628 static unsigned safe_hash (rtx, enum machine_mode);
629 static int exp_equiv_p (rtx, rtx, int, int);
630 static rtx canon_reg (rtx, rtx);
631 static void find_best_addr (rtx, rtx *, enum machine_mode);
632 static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
634 enum machine_mode *);
635 static rtx fold_rtx (rtx, rtx);
636 static rtx equiv_constant (rtx);
637 static void record_jump_equiv (rtx, int);
638 static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
640 static void cse_insn (rtx, rtx);
641 static int addr_affects_sp_p (rtx);
642 static void invalidate_from_clobbers (rtx);
643 static rtx cse_process_notes (rtx, rtx);
644 static void cse_around_loop (rtx);
645 static void invalidate_skipped_set (rtx, rtx, void *);
646 static void invalidate_skipped_block (rtx);
647 static void cse_check_loop_start (rtx, rtx, void *);
648 static void cse_set_around_loop (rtx, rtx, rtx);
649 static rtx cse_basic_block (rtx, rtx, struct branch_path *, int);
650 static void count_reg_usage (rtx, int *, rtx, int);
651 static int check_for_label_ref (rtx *, void *);
652 extern void dump_class (struct table_elt*);
653 static struct cse_reg_info * get_cse_reg_info (unsigned int);
654 static int check_dependence (rtx *, void *);
656 static void flush_hash_table (void);
657 static bool insn_live_p (rtx, int *);
658 static bool set_live_p (rtx, rtx, int *);
659 static bool dead_libcall_p (rtx, int *);
661 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
662 virtual regs here because the simplify_*_operation routines are called
663 by integrate.c, which is called before virtual register instantiation. */
666 fixed_base_plus_p (rtx x)
668 switch (GET_CODE (x))
671 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx)
673 if (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
675 if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
676 && REGNO (x) <= LAST_VIRTUAL_REGISTER)
681 if (GET_CODE (XEXP (x, 1)) != CONST_INT)
683 return fixed_base_plus_p (XEXP (x, 0));
693 /* Dump the expressions in the equivalence class indicated by CLASSP.
694 This function is used only for debugging. */
696 dump_class (struct table_elt *classp)
698 struct table_elt *elt;
700 fprintf (stderr, "Equivalence chain for ");
701 print_rtl (stderr, classp->exp);
702 fprintf (stderr, ": \n");
704 for (elt = classp->first_same_value; elt; elt = elt->next_same_value)
706 print_rtl (stderr, elt->exp);
707 fprintf (stderr, "\n");
711 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
714 approx_reg_cost_1 (rtx *xp, void *data)
719 if (x && GET_CODE (x) == REG)
721 unsigned int regno = REGNO (x);
723 if (! CHEAP_REGNO (regno))
725 if (regno < FIRST_PSEUDO_REGISTER)
727 if (SMALL_REGISTER_CLASSES)
739 /* Return an estimate of the cost of the registers used in an rtx.
740 This is mostly the number of different REG expressions in the rtx;
741 however for some exceptions like fixed registers we use a cost of
742 0. If any other hard register reference occurs, return MAX_COST. */
745 approx_reg_cost (rtx x)
749 if (for_each_rtx (&x, approx_reg_cost_1, (void *) &cost))
755 /* Return a negative value if an rtx A, whose costs are given by COST_A
756 and REGCOST_A, is more desirable than an rtx B.
757 Return a positive value if A is less desirable, or 0 if the two are
760 preferrable (int cost_a, int regcost_a, int cost_b, int regcost_b)
762 /* First, get rid of cases involving expressions that are entirely
764 if (cost_a != cost_b)
766 if (cost_a == MAX_COST)
768 if (cost_b == MAX_COST)
772 /* Avoid extending lifetimes of hardregs. */
773 if (regcost_a != regcost_b)
775 if (regcost_a == MAX_COST)
777 if (regcost_b == MAX_COST)
781 /* Normal operation costs take precedence. */
782 if (cost_a != cost_b)
783 return cost_a - cost_b;
784 /* Only if these are identical consider effects on register pressure. */
785 if (regcost_a != regcost_b)
786 return regcost_a - regcost_b;
790 /* Internal function, to compute cost when X is not a register; called
791 from COST macro to keep it simple. */
794 notreg_cost (rtx x, enum rtx_code outer)
796 return ((GET_CODE (x) == SUBREG
797 && GET_CODE (SUBREG_REG (x)) == REG
798 && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
799 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
800 && (GET_MODE_SIZE (GET_MODE (x))
801 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
802 && subreg_lowpart_p (x)
803 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
804 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
806 : rtx_cost (x, outer) * 2);
809 /* Return an estimate of the cost of computing rtx X.
810 One use is in cse, to decide which expression to keep in the hash table.
811 Another is in rtl generation, to pick the cheapest way to multiply.
812 Other uses like the latter are expected in the future. */
815 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
825 /* Compute the default costs of certain things.
826 Note that targetm.rtx_costs can override the defaults. */
832 total = COSTS_N_INSNS (5);
838 total = COSTS_N_INSNS (7);
841 /* Used in loop.c and combine.c as a marker. */
845 total = COSTS_N_INSNS (1);
854 /* If we can't tie these modes, make this expensive. The larger
855 the mode, the more expensive it is. */
856 if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
857 return COSTS_N_INSNS (2
858 + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
862 if ((*targetm.rtx_costs) (x, code, outer_code, &total))
867 /* Sum the costs of the sub-rtx's, plus cost of this operation,
868 which is already in total. */
870 fmt = GET_RTX_FORMAT (code);
871 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
873 total += rtx_cost (XEXP (x, i), code);
874 else if (fmt[i] == 'E')
875 for (j = 0; j < XVECLEN (x, i); j++)
876 total += rtx_cost (XVECEXP (x, i, j), code);
881 /* Return cost of address expression X.
882 Expect that X is properly formed address reference. */
885 address_cost (rtx x, enum machine_mode mode)
887 /* The address_cost target hook does not deal with ADDRESSOF nodes. But,
888 during CSE, such nodes are present. Using an ADDRESSOF node which
889 refers to the address of a REG is a good thing because we can then
890 turn (MEM (ADDRESSSOF (REG))) into just plain REG. */
892 if (GET_CODE (x) == ADDRESSOF && REG_P (XEXP ((x), 0)))
895 /* We may be asked for cost of various unusual addresses, such as operands
896 of push instruction. It is not worthwhile to complicate writing
897 of the target hook by such cases. */
899 if (!memory_address_p (mode, x))
902 return (*targetm.address_cost) (x);
905 /* If the target doesn't override, compute the cost as with arithmetic. */
908 default_address_cost (rtx x)
910 return rtx_cost (x, MEM);
913 static struct cse_reg_info *
914 get_cse_reg_info (unsigned int regno)
916 struct cse_reg_info **hash_head = ®_hash[REGHASH_FN (regno)];
917 struct cse_reg_info *p;
919 for (p = *hash_head; p != NULL; p = p->hash_next)
920 if (p->regno == regno)
925 /* Get a new cse_reg_info structure. */
926 if (cse_reg_info_free_list)
928 p = cse_reg_info_free_list;
929 cse_reg_info_free_list = p->next;
932 p = xmalloc (sizeof (struct cse_reg_info));
934 /* Insert into hash table. */
935 p->hash_next = *hash_head;
940 p->reg_in_table = -1;
941 p->subreg_ticked = -1;
944 p->next = cse_reg_info_used_list;
945 cse_reg_info_used_list = p;
946 if (!cse_reg_info_used_list_end)
947 cse_reg_info_used_list_end = p;
950 /* Cache this lookup; we tend to be looking up information about the
951 same register several times in a row. */
952 cached_regno = regno;
953 cached_cse_reg_info = p;
958 /* Clear the hash table and initialize each register with its own quantity,
959 for a new basic block. */
962 new_basic_block (void)
968 /* Clear out hash table state for this pass. */
970 memset (reg_hash, 0, sizeof reg_hash);
972 if (cse_reg_info_used_list)
974 cse_reg_info_used_list_end->next = cse_reg_info_free_list;
975 cse_reg_info_free_list = cse_reg_info_used_list;
976 cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
978 cached_cse_reg_info = 0;
980 CLEAR_HARD_REG_SET (hard_regs_in_table);
982 /* The per-quantity values used to be initialized here, but it is
983 much faster to initialize each as it is made in `make_new_qty'. */
985 for (i = 0; i < HASH_SIZE; i++)
987 struct table_elt *first;
992 struct table_elt *last = first;
996 while (last->next_same_hash != NULL)
997 last = last->next_same_hash;
999 /* Now relink this hash entire chain into
1000 the free element list. */
1002 last->next_same_hash = free_element_chain;
1003 free_element_chain = first;
1013 /* Say that register REG contains a quantity in mode MODE not in any
1014 register before and initialize that quantity. */
1017 make_new_qty (unsigned int reg, enum machine_mode mode)
1020 struct qty_table_elem *ent;
1021 struct reg_eqv_elem *eqv;
1023 if (next_qty >= max_qty)
1026 q = REG_QTY (reg) = next_qty++;
1027 ent = &qty_table[q];
1028 ent->first_reg = reg;
1029 ent->last_reg = reg;
1031 ent->const_rtx = ent->const_insn = NULL_RTX;
1032 ent->comparison_code = UNKNOWN;
1034 eqv = ®_eqv_table[reg];
1035 eqv->next = eqv->prev = -1;
1038 /* Make reg NEW equivalent to reg OLD.
1039 OLD is not changing; NEW is. */
1042 make_regs_eqv (unsigned int new, unsigned int old)
1044 unsigned int lastr, firstr;
1045 int q = REG_QTY (old);
1046 struct qty_table_elem *ent;
1048 ent = &qty_table[q];
1050 /* Nothing should become eqv until it has a "non-invalid" qty number. */
1051 if (! REGNO_QTY_VALID_P (old))
1055 firstr = ent->first_reg;
1056 lastr = ent->last_reg;
1058 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
1059 hard regs. Among pseudos, if NEW will live longer than any other reg
1060 of the same qty, and that is beyond the current basic block,
1061 make it the new canonical replacement for this qty. */
1062 if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
1063 /* Certain fixed registers might be of the class NO_REGS. This means
1064 that not only can they not be allocated by the compiler, but
1065 they cannot be used in substitutions or canonicalizations
1067 && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
1068 && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
1069 || (new >= FIRST_PSEUDO_REGISTER
1070 && (firstr < FIRST_PSEUDO_REGISTER
1071 || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
1072 || (uid_cuid[REGNO_FIRST_UID (new)]
1073 < cse_basic_block_start))
1074 && (uid_cuid[REGNO_LAST_UID (new)]
1075 > uid_cuid[REGNO_LAST_UID (firstr)]))))))
1077 reg_eqv_table[firstr].prev = new;
1078 reg_eqv_table[new].next = firstr;
1079 reg_eqv_table[new].prev = -1;
1080 ent->first_reg = new;
1084 /* If NEW is a hard reg (known to be non-fixed), insert at end.
1085 Otherwise, insert before any non-fixed hard regs that are at the
1086 end. Registers of class NO_REGS cannot be used as an
1087 equivalent for anything. */
1088 while (lastr < FIRST_PSEUDO_REGISTER && reg_eqv_table[lastr].prev >= 0
1089 && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
1090 && new >= FIRST_PSEUDO_REGISTER)
1091 lastr = reg_eqv_table[lastr].prev;
1092 reg_eqv_table[new].next = reg_eqv_table[lastr].next;
1093 if (reg_eqv_table[lastr].next >= 0)
1094 reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
1096 qty_table[q].last_reg = new;
1097 reg_eqv_table[lastr].next = new;
1098 reg_eqv_table[new].prev = lastr;
1102 /* Remove REG from its equivalence class. */
1105 delete_reg_equiv (unsigned int reg)
1107 struct qty_table_elem *ent;
1108 int q = REG_QTY (reg);
1111 /* If invalid, do nothing. */
1115 ent = &qty_table[q];
1117 p = reg_eqv_table[reg].prev;
1118 n = reg_eqv_table[reg].next;
1121 reg_eqv_table[n].prev = p;
1125 reg_eqv_table[p].next = n;
1129 REG_QTY (reg) = reg;
1132 /* Remove any invalid expressions from the hash table
1133 that refer to any of the registers contained in expression X.
1135 Make sure that newly inserted references to those registers
1136 as subexpressions will be considered valid.
1138 mention_regs is not called when a register itself
1139 is being stored in the table.
1141 Return 1 if we have done something that may have changed the hash code
1145 mention_regs (rtx x)
1155 code = GET_CODE (x);
1158 unsigned int regno = REGNO (x);
1159 unsigned int endregno
1160 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
1161 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
1164 for (i = regno; i < endregno; i++)
1166 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1167 remove_invalid_refs (i);
1169 REG_IN_TABLE (i) = REG_TICK (i);
1170 SUBREG_TICKED (i) = -1;
1176 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1177 pseudo if they don't use overlapping words. We handle only pseudos
1178 here for simplicity. */
1179 if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1180 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER)
1182 unsigned int i = REGNO (SUBREG_REG (x));
1184 if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
1186 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1187 the last store to this register really stored into this
1188 subreg, then remove the memory of this subreg.
1189 Otherwise, remove any memory of the entire register and
1190 all its subregs from the table. */
1191 if (REG_TICK (i) - REG_IN_TABLE (i) > 1
1192 || SUBREG_TICKED (i) != REGNO (SUBREG_REG (x)))
1193 remove_invalid_refs (i);
1195 remove_invalid_subreg_refs (i, SUBREG_BYTE (x), GET_MODE (x));
1198 REG_IN_TABLE (i) = REG_TICK (i);
1199 SUBREG_TICKED (i) = REGNO (SUBREG_REG (x));
1203 /* If X is a comparison or a COMPARE and either operand is a register
1204 that does not have a quantity, give it one. This is so that a later
1205 call to record_jump_equiv won't cause X to be assigned a different
1206 hash code and not found in the table after that call.
1208 It is not necessary to do this here, since rehash_using_reg can
1209 fix up the table later, but doing this here eliminates the need to
1210 call that expensive function in the most common case where the only
1211 use of the register is in the comparison. */
1213 if (code == COMPARE || GET_RTX_CLASS (code) == '<')
1215 if (GET_CODE (XEXP (x, 0)) == REG
1216 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
1217 if (insert_regs (XEXP (x, 0), NULL, 0))
1219 rehash_using_reg (XEXP (x, 0));
1223 if (GET_CODE (XEXP (x, 1)) == REG
1224 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
1225 if (insert_regs (XEXP (x, 1), NULL, 0))
1227 rehash_using_reg (XEXP (x, 1));
1232 fmt = GET_RTX_FORMAT (code);
1233 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1235 changed |= mention_regs (XEXP (x, i));
1236 else if (fmt[i] == 'E')
1237 for (j = 0; j < XVECLEN (x, i); j++)
1238 changed |= mention_regs (XVECEXP (x, i, j));
1243 /* Update the register quantities for inserting X into the hash table
1244 with a value equivalent to CLASSP.
1245 (If the class does not contain a REG, it is irrelevant.)
1246 If MODIFIED is nonzero, X is a destination; it is being modified.
1247 Note that delete_reg_equiv should be called on a register
1248 before insert_regs is done on that register with MODIFIED != 0.
1250 Nonzero value means that elements of reg_qty have changed
1251 so X's hash code may be different. */
1254 insert_regs (rtx x, struct table_elt *classp, int modified)
1256 if (GET_CODE (x) == REG)
1258 unsigned int regno = REGNO (x);
1261 /* If REGNO is in the equivalence table already but is of the
1262 wrong mode for that equivalence, don't do anything here. */
1264 qty_valid = REGNO_QTY_VALID_P (regno);
1267 struct qty_table_elem *ent = &qty_table[REG_QTY (regno)];
1269 if (ent->mode != GET_MODE (x))
1273 if (modified || ! qty_valid)
1276 for (classp = classp->first_same_value;
1278 classp = classp->next_same_value)
1279 if (GET_CODE (classp->exp) == REG
1280 && GET_MODE (classp->exp) == GET_MODE (x))
1282 make_regs_eqv (regno, REGNO (classp->exp));
1286 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1287 than REG_IN_TABLE to find out if there was only a single preceding
1288 invalidation - for the SUBREG - or another one, which would be
1289 for the full register. However, if we find here that REG_TICK
1290 indicates that the register is invalid, it means that it has
1291 been invalidated in a separate operation. The SUBREG might be used
1292 now (then this is a recursive call), or we might use the full REG
1293 now and a SUBREG of it later. So bump up REG_TICK so that
1294 mention_regs will do the right thing. */
1296 && REG_IN_TABLE (regno) >= 0
1297 && REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
1299 make_new_qty (regno, GET_MODE (x));
1306 /* If X is a SUBREG, we will likely be inserting the inner register in the
1307 table. If that register doesn't have an assigned quantity number at
1308 this point but does later, the insertion that we will be doing now will
1309 not be accessible because its hash code will have changed. So assign
1310 a quantity number now. */
1312 else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
1313 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
1315 insert_regs (SUBREG_REG (x), NULL, 0);
1320 return mention_regs (x);
1323 /* Look in or update the hash table. */
1325 /* Remove table element ELT from use in the table.
1326 HASH is its hash code, made using the HASH macro.
1327 It's an argument because often that is known in advance
1328 and we save much time not recomputing it. */
1331 remove_from_table (struct table_elt *elt, unsigned int hash)
1336 /* Mark this element as removed. See cse_insn. */
1337 elt->first_same_value = 0;
1339 /* Remove the table element from its equivalence class. */
1342 struct table_elt *prev = elt->prev_same_value;
1343 struct table_elt *next = elt->next_same_value;
1346 next->prev_same_value = prev;
1349 prev->next_same_value = next;
1352 struct table_elt *newfirst = next;
1355 next->first_same_value = newfirst;
1356 next = next->next_same_value;
1361 /* Remove the table element from its hash bucket. */
1364 struct table_elt *prev = elt->prev_same_hash;
1365 struct table_elt *next = elt->next_same_hash;
1368 next->prev_same_hash = prev;
1371 prev->next_same_hash = next;
1372 else if (table[hash] == elt)
1376 /* This entry is not in the proper hash bucket. This can happen
1377 when two classes were merged by `merge_equiv_classes'. Search
1378 for the hash bucket that it heads. This happens only very
1379 rarely, so the cost is acceptable. */
1380 for (hash = 0; hash < HASH_SIZE; hash++)
1381 if (table[hash] == elt)
1386 /* Remove the table element from its related-value circular chain. */
1388 if (elt->related_value != 0 && elt->related_value != elt)
1390 struct table_elt *p = elt->related_value;
1392 while (p->related_value != elt)
1393 p = p->related_value;
1394 p->related_value = elt->related_value;
1395 if (p->related_value == p)
1396 p->related_value = 0;
1399 /* Now add it to the free element chain. */
1400 elt->next_same_hash = free_element_chain;
1401 free_element_chain = elt;
1404 /* Look up X in the hash table and return its table element,
1405 or 0 if X is not in the table.
1407 MODE is the machine-mode of X, or if X is an integer constant
1408 with VOIDmode then MODE is the mode with which X will be used.
1410 Here we are satisfied to find an expression whose tree structure
1413 static struct table_elt *
1414 lookup (rtx x, unsigned int hash, enum machine_mode mode)
1416 struct table_elt *p;
1418 for (p = table[hash]; p; p = p->next_same_hash)
1419 if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
1420 || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
1426 /* Like `lookup' but don't care whether the table element uses invalid regs.
1427 Also ignore discrepancies in the machine mode of a register. */
1429 static struct table_elt *
1430 lookup_for_remove (rtx x, unsigned int hash, enum machine_mode mode)
1432 struct table_elt *p;
1434 if (GET_CODE (x) == REG)
1436 unsigned int regno = REGNO (x);
1438 /* Don't check the machine mode when comparing registers;
1439 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1440 for (p = table[hash]; p; p = p->next_same_hash)
1441 if (GET_CODE (p->exp) == REG
1442 && REGNO (p->exp) == regno)
1447 for (p = table[hash]; p; p = p->next_same_hash)
1448 if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
1455 /* Look for an expression equivalent to X and with code CODE.
1456 If one is found, return that expression. */
1459 lookup_as_function (rtx x, enum rtx_code code)
1462 = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, GET_MODE (x));
1464 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1465 long as we are narrowing. So if we looked in vain for a mode narrower
1466 than word_mode before, look for word_mode now. */
1467 if (p == 0 && code == CONST_INT
1468 && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (word_mode))
1471 PUT_MODE (x, word_mode);
1472 p = lookup (x, safe_hash (x, VOIDmode) & HASH_MASK, word_mode);
1478 for (p = p->first_same_value; p; p = p->next_same_value)
1479 if (GET_CODE (p->exp) == code
1480 /* Make sure this is a valid entry in the table. */
1481 && exp_equiv_p (p->exp, p->exp, 1, 0))
1487 /* Insert X in the hash table, assuming HASH is its hash code
1488 and CLASSP is an element of the class it should go in
1489 (or 0 if a new class should be made).
1490 It is inserted at the proper position to keep the class in
1491 the order cheapest first.
1493 MODE is the machine-mode of X, or if X is an integer constant
1494 with VOIDmode then MODE is the mode with which X will be used.
1496 For elements of equal cheapness, the most recent one
1497 goes in front, except that the first element in the list
1498 remains first unless a cheaper element is added. The order of
1499 pseudo-registers does not matter, as canon_reg will be called to
1500 find the cheapest when a register is retrieved from the table.
1502 The in_memory field in the hash table element is set to 0.
1503 The caller must set it nonzero if appropriate.
1505 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1506 and if insert_regs returns a nonzero value
1507 you must then recompute its hash code before calling here.
1509 If necessary, update table showing constant values of quantities. */
1511 #define CHEAPER(X, Y) \
1512 (preferrable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1514 static struct table_elt *
1515 insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
1517 struct table_elt *elt;
1519 /* If X is a register and we haven't made a quantity for it,
1520 something is wrong. */
1521 if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
1524 /* If X is a hard register, show it is being put in the table. */
1525 if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
1527 unsigned int regno = REGNO (x);
1528 unsigned int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1531 for (i = regno; i < endregno; i++)
1532 SET_HARD_REG_BIT (hard_regs_in_table, i);
1535 /* Put an element for X into the right hash bucket. */
1537 elt = free_element_chain;
1539 free_element_chain = elt->next_same_hash;
1543 elt = xmalloc (sizeof (struct table_elt));
1547 elt->canon_exp = NULL_RTX;
1548 elt->cost = COST (x);
1549 elt->regcost = approx_reg_cost (x);
1550 elt->next_same_value = 0;
1551 elt->prev_same_value = 0;
1552 elt->next_same_hash = table[hash];
1553 elt->prev_same_hash = 0;
1554 elt->related_value = 0;
1557 elt->is_const = (CONSTANT_P (x)
1558 /* GNU C++ takes advantage of this for `this'
1559 (and other const values). */
1560 || (GET_CODE (x) == REG
1561 && RTX_UNCHANGING_P (x)
1562 && REGNO (x) >= FIRST_PSEUDO_REGISTER)
1563 || fixed_base_plus_p (x));
1566 table[hash]->prev_same_hash = elt;
1569 /* Put it into the proper value-class. */
1572 classp = classp->first_same_value;
1573 if (CHEAPER (elt, classp))
1574 /* Insert at the head of the class. */
1576 struct table_elt *p;
1577 elt->next_same_value = classp;
1578 classp->prev_same_value = elt;
1579 elt->first_same_value = elt;
1581 for (p = classp; p; p = p->next_same_value)
1582 p->first_same_value = elt;
1586 /* Insert not at head of the class. */
1587 /* Put it after the last element cheaper than X. */
1588 struct table_elt *p, *next;
1590 for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
1593 /* Put it after P and before NEXT. */
1594 elt->next_same_value = next;
1596 next->prev_same_value = elt;
1598 elt->prev_same_value = p;
1599 p->next_same_value = elt;
1600 elt->first_same_value = classp;
1604 elt->first_same_value = elt;
1606 /* If this is a constant being set equivalent to a register or a register
1607 being set equivalent to a constant, note the constant equivalence.
1609 If this is a constant, it cannot be equivalent to a different constant,
1610 and a constant is the only thing that can be cheaper than a register. So
1611 we know the register is the head of the class (before the constant was
1614 If this is a register that is not already known equivalent to a
1615 constant, we must check the entire class.
1617 If this is a register that is already known equivalent to an insn,
1618 update the qtys `const_insn' to show that `this_insn' is the latest
1619 insn making that quantity equivalent to the constant. */
1621 if (elt->is_const && classp && GET_CODE (classp->exp) == REG
1622 && GET_CODE (x) != REG)
1624 int exp_q = REG_QTY (REGNO (classp->exp));
1625 struct qty_table_elem *exp_ent = &qty_table[exp_q];
1627 exp_ent->const_rtx = gen_lowpart_if_possible (exp_ent->mode, x);
1628 exp_ent->const_insn = this_insn;
1631 else if (GET_CODE (x) == REG
1633 && ! qty_table[REG_QTY (REGNO (x))].const_rtx
1636 struct table_elt *p;
1638 for (p = classp; p != 0; p = p->next_same_value)
1640 if (p->is_const && GET_CODE (p->exp) != REG)
1642 int x_q = REG_QTY (REGNO (x));
1643 struct qty_table_elem *x_ent = &qty_table[x_q];
1646 = gen_lowpart_if_possible (GET_MODE (x), p->exp);
1647 x_ent->const_insn = this_insn;
1653 else if (GET_CODE (x) == REG
1654 && qty_table[REG_QTY (REGNO (x))].const_rtx
1655 && GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
1656 qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
1658 /* If this is a constant with symbolic value,
1659 and it has a term with an explicit integer value,
1660 link it up with related expressions. */
1661 if (GET_CODE (x) == CONST)
1663 rtx subexp = get_related_value (x);
1665 struct table_elt *subelt, *subelt_prev;
1669 /* Get the integer-free subexpression in the hash table. */
1670 subhash = safe_hash (subexp, mode) & HASH_MASK;
1671 subelt = lookup (subexp, subhash, mode);
1673 subelt = insert (subexp, NULL, subhash, mode);
1674 /* Initialize SUBELT's circular chain if it has none. */
1675 if (subelt->related_value == 0)
1676 subelt->related_value = subelt;
1677 /* Find the element in the circular chain that precedes SUBELT. */
1678 subelt_prev = subelt;
1679 while (subelt_prev->related_value != subelt)
1680 subelt_prev = subelt_prev->related_value;
1681 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1682 This way the element that follows SUBELT is the oldest one. */
1683 elt->related_value = subelt_prev->related_value;
1684 subelt_prev->related_value = elt;
1691 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1692 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1693 the two classes equivalent.
1695 CLASS1 will be the surviving class; CLASS2 should not be used after this
1698 Any invalid entries in CLASS2 will not be copied. */
1701 merge_equiv_classes (struct table_elt *class1, struct table_elt *class2)
1703 struct table_elt *elt, *next, *new;
1705 /* Ensure we start with the head of the classes. */
1706 class1 = class1->first_same_value;
1707 class2 = class2->first_same_value;
1709 /* If they were already equal, forget it. */
1710 if (class1 == class2)
1713 for (elt = class2; elt; elt = next)
1717 enum machine_mode mode = elt->mode;
1719 next = elt->next_same_value;
1721 /* Remove old entry, make a new one in CLASS1's class.
1722 Don't do this for invalid entries as we cannot find their
1723 hash code (it also isn't necessary). */
1724 if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
1726 hash_arg_in_memory = 0;
1727 hash = HASH (exp, mode);
1729 if (GET_CODE (exp) == REG)
1730 delete_reg_equiv (REGNO (exp));
1732 remove_from_table (elt, hash);
1734 if (insert_regs (exp, class1, 0))
1736 rehash_using_reg (exp);
1737 hash = HASH (exp, mode);
1739 new = insert (exp, class1, hash, mode);
1740 new->in_memory = hash_arg_in_memory;
1745 /* Flush the entire hash table. */
1748 flush_hash_table (void)
1751 struct table_elt *p;
1753 for (i = 0; i < HASH_SIZE; i++)
1754 for (p = table[i]; p; p = table[i])
1756 /* Note that invalidate can remove elements
1757 after P in the current hash chain. */
1758 if (GET_CODE (p->exp) == REG)
1759 invalidate (p->exp, p->mode);
1761 remove_from_table (p, i);
1765 /* Function called for each rtx to check whether true dependence exist. */
1766 struct check_dependence_data
1768 enum machine_mode mode;
1773 check_dependence (rtx *x, void *data)
1775 struct check_dependence_data *d = (struct check_dependence_data *) data;
1776 if (*x && GET_CODE (*x) == MEM)
1777 return true_dependence (d->exp, d->mode, *x, cse_rtx_varies_p);
1782 /* Remove from the hash table, or mark as invalid, all expressions whose
1783 values could be altered by storing in X. X is a register, a subreg, or
1784 a memory reference with nonvarying address (because, when a memory
1785 reference with a varying address is stored in, all memory references are
1786 removed by invalidate_memory so specific invalidation is superfluous).
1787 FULL_MODE, if not VOIDmode, indicates that this much should be
1788 invalidated instead of just the amount indicated by the mode of X. This
1789 is only used for bitfield stores into memory.
1791 A nonvarying address may be just a register or just a symbol reference,
1792 or it may be either of those plus a numeric offset. */
1795 invalidate (rtx x, enum machine_mode full_mode)
1798 struct table_elt *p;
1800 switch (GET_CODE (x))
1804 /* If X is a register, dependencies on its contents are recorded
1805 through the qty number mechanism. Just change the qty number of
1806 the register, mark it as invalid for expressions that refer to it,
1807 and remove it itself. */
1808 unsigned int regno = REGNO (x);
1809 unsigned int hash = HASH (x, GET_MODE (x));
1811 /* Remove REGNO from any quantity list it might be on and indicate
1812 that its value might have changed. If it is a pseudo, remove its
1813 entry from the hash table.
1815 For a hard register, we do the first two actions above for any
1816 additional hard registers corresponding to X. Then, if any of these
1817 registers are in the table, we must remove any REG entries that
1818 overlap these registers. */
1820 delete_reg_equiv (regno);
1822 SUBREG_TICKED (regno) = -1;
1824 if (regno >= FIRST_PSEUDO_REGISTER)
1826 /* Because a register can be referenced in more than one mode,
1827 we might have to remove more than one table entry. */
1828 struct table_elt *elt;
1830 while ((elt = lookup_for_remove (x, hash, GET_MODE (x))))
1831 remove_from_table (elt, hash);
1835 HOST_WIDE_INT in_table
1836 = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
1837 unsigned int endregno
1838 = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
1839 unsigned int tregno, tendregno, rn;
1840 struct table_elt *p, *next;
1842 CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
1844 for (rn = regno + 1; rn < endregno; rn++)
1846 in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, rn);
1847 CLEAR_HARD_REG_BIT (hard_regs_in_table, rn);
1848 delete_reg_equiv (rn);
1850 SUBREG_TICKED (rn) = -1;
1854 for (hash = 0; hash < HASH_SIZE; hash++)
1855 for (p = table[hash]; p; p = next)
1857 next = p->next_same_hash;
1859 if (GET_CODE (p->exp) != REG
1860 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
1863 tregno = REGNO (p->exp);
1865 = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
1866 if (tendregno > regno && tregno < endregno)
1867 remove_from_table (p, hash);
1874 invalidate (SUBREG_REG (x), VOIDmode);
1878 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
1879 invalidate (XVECEXP (x, 0, i), VOIDmode);
1883 /* This is part of a disjoint return value; extract the location in
1884 question ignoring the offset. */
1885 invalidate (XEXP (x, 0), VOIDmode);
1889 /* Calculate the canonical version of X here so that
1890 true_dependence doesn't generate new RTL for X on each call. */
1893 /* Remove all hash table elements that refer to overlapping pieces of
1895 if (full_mode == VOIDmode)
1896 full_mode = GET_MODE (x);
1898 for (i = 0; i < HASH_SIZE; i++)
1900 struct table_elt *next;
1902 for (p = table[i]; p; p = next)
1904 next = p->next_same_hash;
1907 struct check_dependence_data d;
1909 /* Just canonicalize the expression once;
1910 otherwise each time we call invalidate
1911 true_dependence will canonicalize the
1912 expression again. */
1914 p->canon_exp = canon_rtx (p->exp);
1917 if (for_each_rtx (&p->canon_exp, check_dependence, &d))
1918 remove_from_table (p, i);
1929 /* Remove all expressions that refer to register REGNO,
1930 since they are already invalid, and we are about to
1931 mark that register valid again and don't want the old
1932 expressions to reappear as valid. */
1935 remove_invalid_refs (unsigned int regno)
1938 struct table_elt *p, *next;
1940 for (i = 0; i < HASH_SIZE; i++)
1941 for (p = table[i]; p; p = next)
1943 next = p->next_same_hash;
1944 if (GET_CODE (p->exp) != REG
1945 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1946 remove_from_table (p, i);
1950 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1953 remove_invalid_subreg_refs (unsigned int regno, unsigned int offset,
1954 enum machine_mode mode)
1957 struct table_elt *p, *next;
1958 unsigned int end = offset + (GET_MODE_SIZE (mode) - 1);
1960 for (i = 0; i < HASH_SIZE; i++)
1961 for (p = table[i]; p; p = next)
1964 next = p->next_same_hash;
1966 if (GET_CODE (exp) != REG
1967 && (GET_CODE (exp) != SUBREG
1968 || GET_CODE (SUBREG_REG (exp)) != REG
1969 || REGNO (SUBREG_REG (exp)) != regno
1970 || (((SUBREG_BYTE (exp)
1971 + (GET_MODE_SIZE (GET_MODE (exp)) - 1)) >= offset)
1972 && SUBREG_BYTE (exp) <= end))
1973 && refers_to_regno_p (regno, regno + 1, p->exp, (rtx *) 0))
1974 remove_from_table (p, i);
1978 /* Recompute the hash codes of any valid entries in the hash table that
1979 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1981 This is called when we make a jump equivalence. */
1984 rehash_using_reg (rtx x)
1987 struct table_elt *p, *next;
1990 if (GET_CODE (x) == SUBREG)
1993 /* If X is not a register or if the register is known not to be in any
1994 valid entries in the table, we have no work to do. */
1996 if (GET_CODE (x) != REG
1997 || REG_IN_TABLE (REGNO (x)) < 0
1998 || REG_IN_TABLE (REGNO (x)) != REG_TICK (REGNO (x)))
2001 /* Scan all hash chains looking for valid entries that mention X.
2002 If we find one and it is in the wrong hash chain, move it. We can skip
2003 objects that are registers, since they are handled specially. */
2005 for (i = 0; i < HASH_SIZE; i++)
2006 for (p = table[i]; p; p = next)
2008 next = p->next_same_hash;
2009 if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
2010 && exp_equiv_p (p->exp, p->exp, 1, 0)
2011 && i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
2013 if (p->next_same_hash)
2014 p->next_same_hash->prev_same_hash = p->prev_same_hash;
2016 if (p->prev_same_hash)
2017 p->prev_same_hash->next_same_hash = p->next_same_hash;
2019 table[i] = p->next_same_hash;
2021 p->next_same_hash = table[hash];
2022 p->prev_same_hash = 0;
2024 table[hash]->prev_same_hash = p;
2030 /* Remove from the hash table any expression that is a call-clobbered
2031 register. Also update their TICK values. */
2034 invalidate_for_call (void)
2036 unsigned int regno, endregno;
2039 struct table_elt *p, *next;
2042 /* Go through all the hard registers. For each that is clobbered in
2043 a CALL_INSN, remove the register from quantity chains and update
2044 reg_tick if defined. Also see if any of these registers is currently
2047 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2048 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
2050 delete_reg_equiv (regno);
2051 if (REG_TICK (regno) >= 0)
2054 SUBREG_TICKED (regno) = -1;
2057 in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
2060 /* In the case where we have no call-clobbered hard registers in the
2061 table, we are done. Otherwise, scan the table and remove any
2062 entry that overlaps a call-clobbered register. */
2065 for (hash = 0; hash < HASH_SIZE; hash++)
2066 for (p = table[hash]; p; p = next)
2068 next = p->next_same_hash;
2070 if (GET_CODE (p->exp) != REG
2071 || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
2074 regno = REGNO (p->exp);
2075 endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
2077 for (i = regno; i < endregno; i++)
2078 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
2080 remove_from_table (p, hash);
2086 /* Given an expression X of type CONST,
2087 and ELT which is its table entry (or 0 if it
2088 is not in the hash table),
2089 return an alternate expression for X as a register plus integer.
2090 If none can be found, return 0. */
2093 use_related_value (rtx x, struct table_elt *elt)
2095 struct table_elt *relt = 0;
2096 struct table_elt *p, *q;
2097 HOST_WIDE_INT offset;
2099 /* First, is there anything related known?
2100 If we have a table element, we can tell from that.
2101 Otherwise, must look it up. */
2103 if (elt != 0 && elt->related_value != 0)
2105 else if (elt == 0 && GET_CODE (x) == CONST)
2107 rtx subexp = get_related_value (x);
2109 relt = lookup (subexp,
2110 safe_hash (subexp, GET_MODE (subexp)) & HASH_MASK,
2117 /* Search all related table entries for one that has an
2118 equivalent register. */
2123 /* This loop is strange in that it is executed in two different cases.
2124 The first is when X is already in the table. Then it is searching
2125 the RELATED_VALUE list of X's class (RELT). The second case is when
2126 X is not in the table. Then RELT points to a class for the related
2129 Ensure that, whatever case we are in, that we ignore classes that have
2130 the same value as X. */
2132 if (rtx_equal_p (x, p->exp))
2135 for (q = p->first_same_value; q; q = q->next_same_value)
2136 if (GET_CODE (q->exp) == REG)
2142 p = p->related_value;
2144 /* We went all the way around, so there is nothing to be found.
2145 Alternatively, perhaps RELT was in the table for some other reason
2146 and it has no related values recorded. */
2147 if (p == relt || p == 0)
2154 offset = (get_integer_term (x) - get_integer_term (p->exp));
2155 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2156 return plus_constant (q->exp, offset);
2159 /* Hash a string. Just add its bytes up. */
2160 static inline unsigned
2161 canon_hash_string (const char *ps)
2164 const unsigned char *p = (const unsigned char *) ps;
2173 /* Hash an rtx. We are careful to make sure the value is never negative.
2174 Equivalent registers hash identically.
2175 MODE is used in hashing for CONST_INTs only;
2176 otherwise the mode of X is used.
2178 Store 1 in do_not_record if any subexpression is volatile.
2180 Store 1 in hash_arg_in_memory if X contains a MEM rtx
2181 which does not have the RTX_UNCHANGING_P bit set.
2183 Note that cse_insn knows that the hash code of a MEM expression
2184 is just (int) MEM plus the hash code of the address. */
2187 canon_hash (rtx x, enum machine_mode mode)
2194 /* repeat is used to turn tail-recursion into iteration. */
2199 code = GET_CODE (x);
2204 unsigned int regno = REGNO (x);
2207 /* On some machines, we can't record any non-fixed hard register,
2208 because extending its life will cause reload problems. We
2209 consider ap, fp, sp, gp to be fixed for this purpose.
2211 We also consider CCmode registers to be fixed for this purpose;
2212 failure to do so leads to failure to simplify 0<100 type of
2215 On all machines, we can't record any global registers.
2216 Nor should we record any register that is in a small
2217 class, as defined by CLASS_LIKELY_SPILLED_P. */
2219 if (regno >= FIRST_PSEUDO_REGISTER)
2221 else if (x == frame_pointer_rtx
2222 || x == hard_frame_pointer_rtx
2223 || x == arg_pointer_rtx
2224 || x == stack_pointer_rtx
2225 || x == pic_offset_table_rtx)
2227 else if (global_regs[regno])
2229 else if (fixed_regs[regno])
2231 else if (GET_MODE_CLASS (GET_MODE (x)) == MODE_CC)
2233 else if (SMALL_REGISTER_CLASSES)
2235 else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno)))
2246 hash += ((unsigned) REG << 7) + (unsigned) REG_QTY (regno);
2250 /* We handle SUBREG of a REG specially because the underlying
2251 reg changes its hash value with every value change; we don't
2252 want to have to forget unrelated subregs when one subreg changes. */
2255 if (GET_CODE (SUBREG_REG (x)) == REG)
2257 hash += (((unsigned) SUBREG << 7)
2258 + REGNO (SUBREG_REG (x))
2259 + (SUBREG_BYTE (x) / UNITS_PER_WORD));
2267 unsigned HOST_WIDE_INT tem = INTVAL (x);
2268 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
2273 /* This is like the general case, except that it only counts
2274 the integers representing the constant. */
2275 hash += (unsigned) code + (unsigned) GET_MODE (x);
2276 if (GET_MODE (x) != VOIDmode)
2277 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
2279 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2280 + (unsigned) CONST_DOUBLE_HIGH (x));
2288 units = CONST_VECTOR_NUNITS (x);
2290 for (i = 0; i < units; ++i)
2292 elt = CONST_VECTOR_ELT (x, i);
2293 hash += canon_hash (elt, GET_MODE (elt));
2299 /* Assume there is only one rtx object for any given label. */
2301 hash += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2305 hash += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2309 /* We don't record if marked volatile or if BLKmode since we don't
2310 know the size of the move. */
2311 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
2316 if (! RTX_UNCHANGING_P (x) || fixed_base_plus_p (XEXP (x, 0)))
2317 hash_arg_in_memory = 1;
2319 /* Now that we have already found this special case,
2320 might as well speed it up as much as possible. */
2321 hash += (unsigned) MEM;
2326 /* A USE that mentions non-volatile memory needs special
2327 handling since the MEM may be BLKmode which normally
2328 prevents an entry from being made. Pure calls are
2329 marked by a USE which mentions BLKmode memory. */
2330 if (GET_CODE (XEXP (x, 0)) == MEM
2331 && ! MEM_VOLATILE_P (XEXP (x, 0)))
2333 hash += (unsigned) USE;
2336 if (! RTX_UNCHANGING_P (x) || fixed_base_plus_p (XEXP (x, 0)))
2337 hash_arg_in_memory = 1;
2339 /* Now that we have already found this special case,
2340 might as well speed it up as much as possible. */
2341 hash += (unsigned) MEM;
2356 case UNSPEC_VOLATILE:
2361 if (MEM_VOLATILE_P (x))
2368 /* We don't want to take the filename and line into account. */
2369 hash += (unsigned) code + (unsigned) GET_MODE (x)
2370 + canon_hash_string (ASM_OPERANDS_TEMPLATE (x))
2371 + canon_hash_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
2372 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
2374 if (ASM_OPERANDS_INPUT_LENGTH (x))
2376 for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
2378 hash += (canon_hash (ASM_OPERANDS_INPUT (x, i),
2379 GET_MODE (ASM_OPERANDS_INPUT (x, i)))
2380 + canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT
2384 hash += canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
2385 x = ASM_OPERANDS_INPUT (x, 0);
2386 mode = GET_MODE (x);
2398 i = GET_RTX_LENGTH (code) - 1;
2399 hash += (unsigned) code + (unsigned) GET_MODE (x);
2400 fmt = GET_RTX_FORMAT (code);
2405 rtx tem = XEXP (x, i);
2407 /* If we are about to do the last recursive call
2408 needed at this level, change it into iteration.
2409 This function is called enough to be worth it. */
2415 hash += canon_hash (tem, 0);
2417 else if (fmt[i] == 'E')
2418 for (j = 0; j < XVECLEN (x, i); j++)
2419 hash += canon_hash (XVECEXP (x, i, j), 0);
2420 else if (fmt[i] == 's')
2421 hash += canon_hash_string (XSTR (x, i));
2422 else if (fmt[i] == 'i')
2424 unsigned tem = XINT (x, i);
2427 else if (fmt[i] == '0' || fmt[i] == 't')
2436 /* Like canon_hash but with no side effects. */
2439 safe_hash (rtx x, enum machine_mode mode)
2441 int save_do_not_record = do_not_record;
2442 int save_hash_arg_in_memory = hash_arg_in_memory;
2443 unsigned hash = canon_hash (x, mode);
2444 hash_arg_in_memory = save_hash_arg_in_memory;
2445 do_not_record = save_do_not_record;
2449 /* Return 1 iff X and Y would canonicalize into the same thing,
2450 without actually constructing the canonicalization of either one.
2451 If VALIDATE is nonzero,
2452 we assume X is an expression being processed from the rtl
2453 and Y was found in the hash table. We check register refs
2454 in Y for being marked as valid.
2456 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2457 that is known to be in the register. Ordinarily, we don't allow them
2458 to match, because letting them match would cause unpredictable results
2459 in all the places that search a hash table chain for an equivalent
2460 for a given value. A possible equivalent that has different structure
2461 has its hash code computed from different data. Whether the hash code
2462 is the same as that of the given value is pure luck. */
2465 exp_equiv_p (rtx x, rtx y, int validate, int equal_values)
2471 /* Note: it is incorrect to assume an expression is equivalent to itself
2472 if VALIDATE is nonzero. */
2473 if (x == y && !validate)
2475 if (x == 0 || y == 0)
2478 code = GET_CODE (x);
2479 if (code != GET_CODE (y))
2484 /* If X is a constant and Y is a register or vice versa, they may be
2485 equivalent. We only have to validate if Y is a register. */
2486 if (CONSTANT_P (x) && GET_CODE (y) == REG
2487 && REGNO_QTY_VALID_P (REGNO (y)))
2489 int y_q = REG_QTY (REGNO (y));
2490 struct qty_table_elem *y_ent = &qty_table[y_q];
2492 if (GET_MODE (y) == y_ent->mode
2493 && rtx_equal_p (x, y_ent->const_rtx)
2494 && (! validate || REG_IN_TABLE (REGNO (y)) == REG_TICK (REGNO (y))))
2498 if (CONSTANT_P (y) && code == REG
2499 && REGNO_QTY_VALID_P (REGNO (x)))
2501 int x_q = REG_QTY (REGNO (x));
2502 struct qty_table_elem *x_ent = &qty_table[x_q];
2504 if (GET_MODE (x) == x_ent->mode
2505 && rtx_equal_p (y, x_ent->const_rtx))
2512 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2513 if (GET_MODE (x) != GET_MODE (y))
2524 return XEXP (x, 0) == XEXP (y, 0);
2527 return XSTR (x, 0) == XSTR (y, 0);
2531 unsigned int regno = REGNO (y);
2532 unsigned int endregno
2533 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
2534 : HARD_REGNO_NREGS (regno, GET_MODE (y)));
2537 /* If the quantities are not the same, the expressions are not
2538 equivalent. If there are and we are not to validate, they
2539 are equivalent. Otherwise, ensure all regs are up-to-date. */
2541 if (REG_QTY (REGNO (x)) != REG_QTY (regno))
2547 for (i = regno; i < endregno; i++)
2548 if (REG_IN_TABLE (i) != REG_TICK (i))
2554 /* For commutative operations, check both orders. */
2562 return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
2563 && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
2564 validate, equal_values))
2565 || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
2566 validate, equal_values)
2567 && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
2568 validate, equal_values)));
2571 /* We don't use the generic code below because we want to
2572 disregard filename and line numbers. */
2574 /* A volatile asm isn't equivalent to any other. */
2575 if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2578 if (GET_MODE (x) != GET_MODE (y)
2579 || strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
2580 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
2581 ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
2582 || ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
2583 || ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
2586 if (ASM_OPERANDS_INPUT_LENGTH (x))
2588 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
2589 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x, i),
2590 ASM_OPERANDS_INPUT (y, i),
2591 validate, equal_values)
2592 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
2593 ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
2603 /* Compare the elements. If any pair of corresponding elements
2604 fail to match, return 0 for the whole things. */
2606 fmt = GET_RTX_FORMAT (code);
2607 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2612 if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
2617 if (XVECLEN (x, i) != XVECLEN (y, i))
2619 for (j = 0; j < XVECLEN (x, i); j++)
2620 if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2621 validate, equal_values))
2626 if (strcmp (XSTR (x, i), XSTR (y, i)))
2631 if (XINT (x, i) != XINT (y, i))
2636 if (XWINT (x, i) != XWINT (y, i))
2652 /* Return 1 if X has a value that can vary even between two
2653 executions of the program. 0 means X can be compared reliably
2654 against certain constants or near-constants. */
2657 cse_rtx_varies_p (rtx x, int from_alias)
2659 /* We need not check for X and the equivalence class being of the same
2660 mode because if X is equivalent to a constant in some mode, it
2661 doesn't vary in any mode. */
2663 if (GET_CODE (x) == REG
2664 && REGNO_QTY_VALID_P (REGNO (x)))
2666 int x_q = REG_QTY (REGNO (x));
2667 struct qty_table_elem *x_ent = &qty_table[x_q];
2669 if (GET_MODE (x) == x_ent->mode
2670 && x_ent->const_rtx != NULL_RTX)
2674 if (GET_CODE (x) == PLUS
2675 && GET_CODE (XEXP (x, 1)) == CONST_INT
2676 && GET_CODE (XEXP (x, 0)) == REG
2677 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
2679 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2680 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2682 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2683 && x0_ent->const_rtx != NULL_RTX)
2687 /* This can happen as the result of virtual register instantiation, if
2688 the initial constant is too large to be a valid address. This gives
2689 us a three instruction sequence, load large offset into a register,
2690 load fp minus a constant into a register, then a MEM which is the
2691 sum of the two `constant' registers. */
2692 if (GET_CODE (x) == PLUS
2693 && GET_CODE (XEXP (x, 0)) == REG
2694 && GET_CODE (XEXP (x, 1)) == REG
2695 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
2696 && REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
2698 int x0_q = REG_QTY (REGNO (XEXP (x, 0)));
2699 int x1_q = REG_QTY (REGNO (XEXP (x, 1)));
2700 struct qty_table_elem *x0_ent = &qty_table[x0_q];
2701 struct qty_table_elem *x1_ent = &qty_table[x1_q];
2703 if ((GET_MODE (XEXP (x, 0)) == x0_ent->mode)
2704 && x0_ent->const_rtx != NULL_RTX
2705 && (GET_MODE (XEXP (x, 1)) == x1_ent->mode)
2706 && x1_ent->const_rtx != NULL_RTX)
2710 return rtx_varies_p (x, from_alias);
2713 /* Canonicalize an expression:
2714 replace each register reference inside it
2715 with the "oldest" equivalent register.
2717 If INSN is nonzero and we are replacing a pseudo with a hard register
2718 or vice versa, validate_change is used to ensure that INSN remains valid
2719 after we make our substitution. The calls are made with IN_GROUP nonzero
2720 so apply_change_group must be called upon the outermost return from this
2721 function (unless INSN is zero). The result of apply_change_group can
2722 generally be discarded since the changes we are making are optional. */
2725 canon_reg (rtx x, rtx insn)
2734 code = GET_CODE (x);
2753 struct qty_table_elem *ent;
2755 /* Never replace a hard reg, because hard regs can appear
2756 in more than one machine mode, and we must preserve the mode
2757 of each occurrence. Also, some hard regs appear in
2758 MEMs that are shared and mustn't be altered. Don't try to
2759 replace any reg that maps to a reg of class NO_REGS. */
2760 if (REGNO (x) < FIRST_PSEUDO_REGISTER
2761 || ! REGNO_QTY_VALID_P (REGNO (x)))
2764 q = REG_QTY (REGNO (x));
2765 ent = &qty_table[q];
2766 first = ent->first_reg;
2767 return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
2768 : REGNO_REG_CLASS (first) == NO_REGS ? x
2769 : gen_rtx_REG (ent->mode, first));
2776 fmt = GET_RTX_FORMAT (code);
2777 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2783 rtx new = canon_reg (XEXP (x, i), insn);
2786 /* If replacing pseudo with hard reg or vice versa, ensure the
2787 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2788 if (insn != 0 && new != 0
2789 && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
2790 && (((REGNO (new) < FIRST_PSEUDO_REGISTER)
2791 != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER))
2792 || (insn_code = recog_memoized (insn)) < 0
2793 || insn_data[insn_code].n_dups > 0))
2794 validate_change (insn, &XEXP (x, i), new, 1);
2798 else if (fmt[i] == 'E')
2799 for (j = 0; j < XVECLEN (x, i); j++)
2800 XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
2806 /* LOC is a location within INSN that is an operand address (the contents of
2807 a MEM). Find the best equivalent address to use that is valid for this
2810 On most CISC machines, complicated address modes are costly, and rtx_cost
2811 is a good approximation for that cost. However, most RISC machines have
2812 only a few (usually only one) memory reference formats. If an address is
2813 valid at all, it is often just as cheap as any other address. Hence, for
2814 RISC machines, we use `address_cost' to compare the costs of various
2815 addresses. For two addresses of equal cost, choose the one with the
2816 highest `rtx_cost' value as that has the potential of eliminating the
2817 most insns. For equal costs, we choose the first in the equivalence
2818 class. Note that we ignore the fact that pseudo registers are cheaper than
2819 hard registers here because we would also prefer the pseudo registers. */
2822 find_best_addr (rtx insn, rtx *loc, enum machine_mode mode)
2824 struct table_elt *elt;
2826 struct table_elt *p;
2827 int found_better = 1;
2828 int save_do_not_record = do_not_record;
2829 int save_hash_arg_in_memory = hash_arg_in_memory;
2834 /* Do not try to replace constant addresses or addresses of local and
2835 argument slots. These MEM expressions are made only once and inserted
2836 in many instructions, as well as being used to control symbol table
2837 output. It is not safe to clobber them.
2839 There are some uncommon cases where the address is already in a register
2840 for some reason, but we cannot take advantage of that because we have
2841 no easy way to unshare the MEM. In addition, looking up all stack
2842 addresses is costly. */
2843 if ((GET_CODE (addr) == PLUS
2844 && GET_CODE (XEXP (addr, 0)) == REG
2845 && GET_CODE (XEXP (addr, 1)) == CONST_INT
2846 && (regno = REGNO (XEXP (addr, 0)),
2847 regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM
2848 || regno == ARG_POINTER_REGNUM))
2849 || (GET_CODE (addr) == REG
2850 && (regno = REGNO (addr), regno == FRAME_POINTER_REGNUM
2851 || regno == HARD_FRAME_POINTER_REGNUM
2852 || regno == ARG_POINTER_REGNUM))
2853 || GET_CODE (addr) == ADDRESSOF
2854 || CONSTANT_ADDRESS_P (addr))
2857 /* If this address is not simply a register, try to fold it. This will
2858 sometimes simplify the expression. Many simplifications
2859 will not be valid, but some, usually applying the associative rule, will
2860 be valid and produce better code. */
2861 if (GET_CODE (addr) != REG)
2863 rtx folded = fold_rtx (copy_rtx (addr), NULL_RTX);
2864 int addr_folded_cost = address_cost (folded, mode);
2865 int addr_cost = address_cost (addr, mode);
2867 if ((addr_folded_cost < addr_cost
2868 || (addr_folded_cost == addr_cost
2869 /* ??? The rtx_cost comparison is left over from an older
2870 version of this code. It is probably no longer helpful. */
2871 && (rtx_cost (folded, MEM) > rtx_cost (addr, MEM)
2872 || approx_reg_cost (folded) < approx_reg_cost (addr))))
2873 && validate_change (insn, loc, folded, 0))
2877 /* If this address is not in the hash table, we can't look for equivalences
2878 of the whole address. Also, ignore if volatile. */
2881 hash = HASH (addr, Pmode);
2882 addr_volatile = do_not_record;
2883 do_not_record = save_do_not_record;
2884 hash_arg_in_memory = save_hash_arg_in_memory;
2889 elt = lookup (addr, hash, Pmode);
2893 /* We need to find the best (under the criteria documented above) entry
2894 in the class that is valid. We use the `flag' field to indicate
2895 choices that were invalid and iterate until we can't find a better
2896 one that hasn't already been tried. */
2898 for (p = elt->first_same_value; p; p = p->next_same_value)
2901 while (found_better)
2903 int best_addr_cost = address_cost (*loc, mode);
2904 int best_rtx_cost = (elt->cost + 1) >> 1;
2906 struct table_elt *best_elt = elt;
2909 for (p = elt->first_same_value; p; p = p->next_same_value)
2912 if ((GET_CODE (p->exp) == REG
2913 || exp_equiv_p (p->exp, p->exp, 1, 0))
2914 && ((exp_cost = address_cost (p->exp, mode)) < best_addr_cost
2915 || (exp_cost == best_addr_cost
2916 && ((p->cost + 1) >> 1) > best_rtx_cost)))
2919 best_addr_cost = exp_cost;
2920 best_rtx_cost = (p->cost + 1) >> 1;
2927 if (validate_change (insn, loc,
2928 canon_reg (copy_rtx (best_elt->exp),
2937 /* If the address is a binary operation with the first operand a register
2938 and the second a constant, do the same as above, but looking for
2939 equivalences of the register. Then try to simplify before checking for
2940 the best address to use. This catches a few cases: First is when we
2941 have REG+const and the register is another REG+const. We can often merge
2942 the constants and eliminate one insn and one register. It may also be
2943 that a machine has a cheap REG+REG+const. Finally, this improves the
2944 code on the Alpha for unaligned byte stores. */
2946 if (flag_expensive_optimizations
2947 && (GET_RTX_CLASS (GET_CODE (*loc)) == '2'
2948 || GET_RTX_CLASS (GET_CODE (*loc)) == 'c')
2949 && GET_CODE (XEXP (*loc, 0)) == REG)
2951 rtx op1 = XEXP (*loc, 1);
2954 hash = HASH (XEXP (*loc, 0), Pmode);
2955 do_not_record = save_do_not_record;
2956 hash_arg_in_memory = save_hash_arg_in_memory;
2958 elt = lookup (XEXP (*loc, 0), hash, Pmode);
2962 /* We need to find the best (under the criteria documented above) entry
2963 in the class that is valid. We use the `flag' field to indicate
2964 choices that were invalid and iterate until we can't find a better
2965 one that hasn't already been tried. */
2967 for (p = elt->first_same_value; p; p = p->next_same_value)
2970 while (found_better)
2972 int best_addr_cost = address_cost (*loc, mode);
2973 int best_rtx_cost = (COST (*loc) + 1) >> 1;
2974 struct table_elt *best_elt = elt;
2975 rtx best_rtx = *loc;
2978 /* This is at worst case an O(n^2) algorithm, so limit our search
2979 to the first 32 elements on the list. This avoids trouble
2980 compiling code with very long basic blocks that can easily
2981 call simplify_gen_binary so many times that we run out of
2985 for (p = elt->first_same_value, count = 0;
2987 p = p->next_same_value, count++)
2989 && (GET_CODE (p->exp) == REG
2990 || exp_equiv_p (p->exp, p->exp, 1, 0)))
2992 rtx new = simplify_gen_binary (GET_CODE (*loc), Pmode,
2995 new_cost = address_cost (new, mode);
2997 if (new_cost < best_addr_cost
2998 || (new_cost == best_addr_cost
2999 && (COST (new) + 1) >> 1 > best_rtx_cost))
3002 best_addr_cost = new_cost;
3003 best_rtx_cost = (COST (new) + 1) >> 1;
3011 if (validate_change (insn, loc,
3012 canon_reg (copy_rtx (best_rtx),
3022 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
3023 operation (EQ, NE, GT, etc.), follow it back through the hash table and
3024 what values are being compared.
3026 *PARG1 and *PARG2 are updated to contain the rtx representing the values
3027 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
3028 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
3029 compared to produce cc0.
3031 The return value is the comparison operator and is either the code of
3032 A or the code corresponding to the inverse of the comparison. */
3034 static enum rtx_code
3035 find_comparison_args (enum rtx_code code, rtx *parg1, rtx *parg2,
3036 enum machine_mode *pmode1, enum machine_mode *pmode2)
3040 arg1 = *parg1, arg2 = *parg2;
3042 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
3044 while (arg2 == CONST0_RTX (GET_MODE (arg1)))
3046 /* Set nonzero when we find something of interest. */
3048 int reverse_code = 0;
3049 struct table_elt *p = 0;
3051 /* If arg1 is a COMPARE, extract the comparison arguments from it.
3052 On machines with CC0, this is the only case that can occur, since
3053 fold_rtx will return the COMPARE or item being compared with zero
3056 if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
3059 /* If ARG1 is a comparison operator and CODE is testing for
3060 STORE_FLAG_VALUE, get the inner arguments. */
3062 else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
3064 #ifdef FLOAT_STORE_FLAG_VALUE
3065 REAL_VALUE_TYPE fsfv;
3069 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3070 && code == LT && STORE_FLAG_VALUE == -1)
3071 #ifdef FLOAT_STORE_FLAG_VALUE
3072 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3073 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3074 REAL_VALUE_NEGATIVE (fsfv)))
3079 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_INT
3080 && code == GE && STORE_FLAG_VALUE == -1)
3081 #ifdef FLOAT_STORE_FLAG_VALUE
3082 || (GET_MODE_CLASS (GET_MODE (arg1)) == MODE_FLOAT
3083 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3084 REAL_VALUE_NEGATIVE (fsfv)))
3087 x = arg1, reverse_code = 1;
3090 /* ??? We could also check for
3092 (ne (and (eq (...) (const_int 1))) (const_int 0))
3094 and related forms, but let's wait until we see them occurring. */
3097 /* Look up ARG1 in the hash table and see if it has an equivalence
3098 that lets us see what is being compared. */
3099 p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) & HASH_MASK,
3103 p = p->first_same_value;
3105 /* If what we compare is already known to be constant, that is as
3107 We need to break the loop in this case, because otherwise we
3108 can have an infinite loop when looking at a reg that is known
3109 to be a constant which is the same as a comparison of a reg
3110 against zero which appears later in the insn stream, which in
3111 turn is constant and the same as the comparison of the first reg
3117 for (; p; p = p->next_same_value)
3119 enum machine_mode inner_mode = GET_MODE (p->exp);
3120 #ifdef FLOAT_STORE_FLAG_VALUE
3121 REAL_VALUE_TYPE fsfv;
3124 /* If the entry isn't valid, skip it. */
3125 if (! exp_equiv_p (p->exp, p->exp, 1, 0))
3128 if (GET_CODE (p->exp) == COMPARE
3129 /* Another possibility is that this machine has a compare insn
3130 that includes the comparison code. In that case, ARG1 would
3131 be equivalent to a comparison operation that would set ARG1 to
3132 either STORE_FLAG_VALUE or zero. If this is an NE operation,
3133 ORIG_CODE is the actual comparison being done; if it is an EQ,
3134 we must reverse ORIG_CODE. On machine with a negative value
3135 for STORE_FLAG_VALUE, also look at LT and GE operations. */
3138 && GET_MODE_CLASS (inner_mode) == MODE_INT
3139 && (GET_MODE_BITSIZE (inner_mode)
3140 <= HOST_BITS_PER_WIDE_INT)
3141 && (STORE_FLAG_VALUE
3142 & ((HOST_WIDE_INT) 1
3143 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3144 #ifdef FLOAT_STORE_FLAG_VALUE
3146 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3147 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3148 REAL_VALUE_NEGATIVE (fsfv)))
3151 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
3156 else if ((code == EQ
3158 && GET_MODE_CLASS (inner_mode) == MODE_INT
3159 && (GET_MODE_BITSIZE (inner_mode)
3160 <= HOST_BITS_PER_WIDE_INT)
3161 && (STORE_FLAG_VALUE
3162 & ((HOST_WIDE_INT) 1
3163 << (GET_MODE_BITSIZE (inner_mode) - 1))))
3164 #ifdef FLOAT_STORE_FLAG_VALUE
3166 && GET_MODE_CLASS (inner_mode) == MODE_FLOAT
3167 && (fsfv = FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1)),
3168 REAL_VALUE_NEGATIVE (fsfv)))
3171 && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
3178 /* If this non-trapping address, e.g. fp + constant, the
3179 equivalent is a better operand since it may let us predict
3180 the value of the comparison. */
3181 else if (!rtx_addr_can_trap_p (p->exp))
3188 /* If we didn't find a useful equivalence for ARG1, we are done.
3189 Otherwise, set up for the next iteration. */
3193 /* If we need to reverse the comparison, make sure that that is
3194 possible -- we can't necessarily infer the value of GE from LT
3195 with floating-point operands. */
3198 enum rtx_code reversed = reversed_comparison_code (x, NULL_RTX);
3199 if (reversed == UNKNOWN)
3204 else if (GET_RTX_CLASS (GET_CODE (x)) == '<')
3205 code = GET_CODE (x);
3206 arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
3209 /* Return our results. Return the modes from before fold_rtx
3210 because fold_rtx might produce const_int, and then it's too late. */
3211 *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
3212 *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
3217 /* If X is a nontrivial arithmetic operation on an argument
3218 for which a constant value can be determined, return
3219 the result of operating on that value, as a constant.
3220 Otherwise, return X, possibly with one or more operands
3221 modified by recursive calls to this function.
3223 If X is a register whose contents are known, we do NOT
3224 return those contents here. equiv_constant is called to
3227 INSN is the insn that we may be modifying. If it is 0, make a copy
3228 of X before modifying it. */
3231 fold_rtx (rtx x, rtx insn)
3234 enum machine_mode mode;
3241 /* Folded equivalents of first two operands of X. */
3245 /* Constant equivalents of first three operands of X;
3246 0 when no such equivalent is known. */
3251 /* The mode of the first operand of X. We need this for sign and zero
3253 enum machine_mode mode_arg0;
3258 mode = GET_MODE (x);
3259 code = GET_CODE (x);
3269 /* No use simplifying an EXPR_LIST
3270 since they are used only for lists of args
3271 in a function call's REG_EQUAL note. */
3273 /* Changing anything inside an ADDRESSOF is incorrect; we don't
3274 want to (e.g.,) make (addressof (const_int 0)) just because
3275 the location is known to be zero. */
3281 return prev_insn_cc0;
3285 /* If the next insn is a CODE_LABEL followed by a jump table,
3286 PC's value is a LABEL_REF pointing to that label. That
3287 lets us fold switch statements on the VAX. */
3290 if (insn && tablejump_p (insn, &next, NULL))
3291 return gen_rtx_LABEL_REF (Pmode, next);
3296 /* See if we previously assigned a constant value to this SUBREG. */
3297 if ((new = lookup_as_function (x, CONST_INT)) != 0
3298 || (new = lookup_as_function (x, CONST_DOUBLE)) != 0)
3301 /* If this is a paradoxical SUBREG, we have no idea what value the
3302 extra bits would have. However, if the operand is equivalent
3303 to a SUBREG whose operand is the same as our mode, and all the
3304 modes are within a word, we can just use the inner operand
3305 because these SUBREGs just say how to treat the register.
3307 Similarly if we find an integer constant. */
3309 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3311 enum machine_mode imode = GET_MODE (SUBREG_REG (x));
3312 struct table_elt *elt;
3314 if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
3315 && GET_MODE_SIZE (imode) <= UNITS_PER_WORD
3316 && (elt = lookup (SUBREG_REG (x), HASH (SUBREG_REG (x), imode),
3318 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
3320 if (CONSTANT_P (elt->exp)
3321 && GET_MODE (elt->exp) == VOIDmode)
3324 if (GET_CODE (elt->exp) == SUBREG
3325 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3326 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3327 return copy_rtx (SUBREG_REG (elt->exp));
3333 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
3334 We might be able to if the SUBREG is extracting a single word in an
3335 integral mode or extracting the low part. */
3337 folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
3338 const_arg0 = equiv_constant (folded_arg0);
3340 folded_arg0 = const_arg0;
3342 if (folded_arg0 != SUBREG_REG (x))
3344 new = simplify_subreg (mode, folded_arg0,
3345 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
3350 /* If this is a narrowing SUBREG and our operand is a REG, see if
3351 we can find an equivalence for REG that is an arithmetic operation
3352 in a wider mode where both operands are paradoxical SUBREGs
3353 from objects of our result mode. In that case, we couldn't report
3354 an equivalent value for that operation, since we don't know what the
3355 extra bits will be. But we can find an equivalence for this SUBREG
3356 by folding that operation is the narrow mode. This allows us to
3357 fold arithmetic in narrow modes when the machine only supports
3358 word-sized arithmetic.
3360 Also look for a case where we have a SUBREG whose operand is the
3361 same as our result. If both modes are smaller than a word, we
3362 are simply interpreting a register in different modes and we
3363 can use the inner value. */
3365 if (GET_CODE (folded_arg0) == REG
3366 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (folded_arg0))
3367 && subreg_lowpart_p (x))
3369 struct table_elt *elt;
3371 /* We can use HASH here since we know that canon_hash won't be
3373 elt = lookup (folded_arg0,
3374 HASH (folded_arg0, GET_MODE (folded_arg0)),
3375 GET_MODE (folded_arg0));
3378 elt = elt->first_same_value;
3380 for (; elt; elt = elt->next_same_value)
3382 enum rtx_code eltcode = GET_CODE (elt->exp);
3384 /* Just check for unary and binary operations. */
3385 if (GET_RTX_CLASS (GET_CODE (elt->exp)) == '1'
3386 && GET_CODE (elt->exp) != SIGN_EXTEND
3387 && GET_CODE (elt->exp) != ZERO_EXTEND
3388 && GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3389 && GET_MODE (SUBREG_REG (XEXP (elt->exp, 0))) == mode
3390 && (GET_MODE_CLASS (mode)
3391 == GET_MODE_CLASS (GET_MODE (XEXP (elt->exp, 0)))))
3393 rtx op0 = SUBREG_REG (XEXP (elt->exp, 0));
3395 if (GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3396 op0 = fold_rtx (op0, NULL_RTX);
3398 op0 = equiv_constant (op0);
3400 new = simplify_unary_operation (GET_CODE (elt->exp), mode,
3403 else if ((GET_RTX_CLASS (GET_CODE (elt->exp)) == '2'
3404 || GET_RTX_CLASS (GET_CODE (elt->exp)) == 'c')
3405 && eltcode != DIV && eltcode != MOD
3406 && eltcode != UDIV && eltcode != UMOD
3407 && eltcode != ASHIFTRT && eltcode != LSHIFTRT
3408 && eltcode != ROTATE && eltcode != ROTATERT
3409 && ((GET_CODE (XEXP (elt->exp, 0)) == SUBREG
3410 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 0)))
3412 || CONSTANT_P (XEXP (elt->exp, 0)))
3413 && ((GET_CODE (XEXP (elt->exp, 1)) == SUBREG
3414 && (GET_MODE (SUBREG_REG (XEXP (elt->exp, 1)))
3416 || CONSTANT_P (XEXP (elt->exp, 1))))
3418 rtx op0 = gen_lowpart_common (mode, XEXP (elt->exp, 0));
3419 rtx op1 = gen_lowpart_common (mode, XEXP (elt->exp, 1));
3421 if (op0 && GET_CODE (op0) != REG && ! CONSTANT_P (op0))
3422 op0 = fold_rtx (op0, NULL_RTX);
3425 op0 = equiv_constant (op0);
3427 if (op1 && GET_CODE (op1) != REG && ! CONSTANT_P (op1))
3428 op1 = fold_rtx (op1, NULL_RTX);
3431 op1 = equiv_constant (op1);
3433 /* If we are looking for the low SImode part of
3434 (ashift:DI c (const_int 32)), it doesn't work
3435 to compute that in SImode, because a 32-bit shift
3436 in SImode is unpredictable. We know the value is 0. */
3438 && GET_CODE (elt->exp) == ASHIFT
3439 && GET_CODE (op1) == CONST_INT
3440 && INTVAL (op1) >= GET_MODE_BITSIZE (mode))
3442 if (INTVAL (op1) < GET_MODE_BITSIZE (GET_MODE (elt->exp)))
3444 /* If the count fits in the inner mode's width,
3445 but exceeds the outer mode's width,
3446 the value will get truncated to 0
3450 /* If the count exceeds even the inner mode's width,
3451 don't fold this expression. */
3454 else if (op0 && op1)
3455 new = simplify_binary_operation (GET_CODE (elt->exp), mode,
3459 else if (GET_CODE (elt->exp) == SUBREG
3460 && GET_MODE (SUBREG_REG (elt->exp)) == mode
3461 && (GET_MODE_SIZE (GET_MODE (folded_arg0))
3463 && exp_equiv_p (elt->exp, elt->exp, 1, 0))
3464 new = copy_rtx (SUBREG_REG (elt->exp));
3475 /* If we have (NOT Y), see if Y is known to be (NOT Z).
3476 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
3477 new = lookup_as_function (XEXP (x, 0), code);
3479 return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
3483 /* If we are not actually processing an insn, don't try to find the
3484 best address. Not only don't we care, but we could modify the
3485 MEM in an invalid way since we have no insn to validate against. */
3487 find_best_addr (insn, &XEXP (x, 0), GET_MODE (x));
3490 /* Even if we don't fold in the insn itself,
3491 we can safely do so here, in hopes of getting a constant. */
3492 rtx addr = fold_rtx (XEXP (x, 0), NULL_RTX);
3494 HOST_WIDE_INT offset = 0;
3496 if (GET_CODE (addr) == REG
3497 && REGNO_QTY_VALID_P (REGNO (addr)))
3499 int addr_q = REG_QTY (REGNO (addr));
3500 struct qty_table_elem *addr_ent = &qty_table[addr_q];
3502 if (GET_MODE (addr) == addr_ent->mode
3503 && addr_ent->const_rtx != NULL_RTX)
3504 addr = addr_ent->const_rtx;
3507 /* If address is constant, split it into a base and integer offset. */
3508 if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
3510 else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
3511 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
3513 base = XEXP (XEXP (addr, 0), 0);
3514 offset = INTVAL (XEXP (XEXP (addr, 0), 1));
3516 else if (GET_CODE (addr) == LO_SUM
3517 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
3518 base = XEXP (addr, 1);
3519 else if (GET_CODE (addr) == ADDRESSOF)
3520 return change_address (x, VOIDmode, addr);
3522 /* If this is a constant pool reference, we can fold it into its
3523 constant to allow better value tracking. */
3524 if (base && GET_CODE (base) == SYMBOL_REF
3525 && CONSTANT_POOL_ADDRESS_P (base))
3527 rtx constant = get_pool_constant (base);
3528 enum machine_mode const_mode = get_pool_mode (base);
3531 if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
3532 constant_pool_entries_cost = COST (constant);
3534 /* If we are loading the full constant, we have an equivalence. */
3535 if (offset == 0 && mode == const_mode)
3538 /* If this actually isn't a constant (weird!), we can't do
3539 anything. Otherwise, handle the two most common cases:
3540 extracting a word from a multi-word constant, and extracting
3541 the low-order bits. Other cases don't seem common enough to
3543 if (! CONSTANT_P (constant))
3546 if (GET_MODE_CLASS (mode) == MODE_INT
3547 && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3548 && offset % UNITS_PER_WORD == 0
3549 && (new = operand_subword (constant,
3550 offset / UNITS_PER_WORD,
3551 0, const_mode)) != 0)
3554 if (((BYTES_BIG_ENDIAN
3555 && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
3556 || (! BYTES_BIG_ENDIAN && offset == 0))
3557 && (new = gen_lowpart_if_possible (mode, constant)) != 0)
3561 /* If this is a reference to a label at a known position in a jump
3562 table, we also know its value. */
3563 if (base && GET_CODE (base) == LABEL_REF)
3565 rtx label = XEXP (base, 0);
3566 rtx table_insn = NEXT_INSN (label);
3568 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3569 && GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
3571 rtx table = PATTERN (table_insn);
3574 && (offset / GET_MODE_SIZE (GET_MODE (table))
3575 < XVECLEN (table, 0)))
3576 return XVECEXP (table, 0,
3577 offset / GET_MODE_SIZE (GET_MODE (table)));
3579 if (table_insn && GET_CODE (table_insn) == JUMP_INSN
3580 && GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
3582 rtx table = PATTERN (table_insn);
3585 && (offset / GET_MODE_SIZE (GET_MODE (table))
3586 < XVECLEN (table, 1)))
3588 offset /= GET_MODE_SIZE (GET_MODE (table));
3589 new = gen_rtx_MINUS (Pmode, XVECEXP (table, 1, offset),
3592 if (GET_MODE (table) != Pmode)
3593 new = gen_rtx_TRUNCATE (GET_MODE (table), new);
3595 /* Indicate this is a constant. This isn't a
3596 valid form of CONST, but it will only be used
3597 to fold the next insns and then discarded, so
3600 Note this expression must be explicitly discarded,
3601 by cse_insn, else it may end up in a REG_EQUAL note
3602 and "escape" to cause problems elsewhere. */
3603 return gen_rtx_CONST (GET_MODE (new), new);
3611 #ifdef NO_FUNCTION_CSE
3613 if (CONSTANT_P (XEXP (XEXP (x, 0), 0)))
3619 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
3620 validate_change (insn, &ASM_OPERANDS_INPUT (x, i),
3621 fold_rtx (ASM_OPERANDS_INPUT (x, i), insn), 0);
3631 mode_arg0 = VOIDmode;
3633 /* Try folding our operands.
3634 Then see which ones have constant values known. */
3636 fmt = GET_RTX_FORMAT (code);
3637 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3640 rtx arg = XEXP (x, i);
3641 rtx folded_arg = arg, const_arg = 0;
3642 enum machine_mode mode_arg = GET_MODE (arg);
3643 rtx cheap_arg, expensive_arg;
3644 rtx replacements[2];
3646 int old_cost = COST_IN (XEXP (x, i), code);
3648 /* Most arguments are cheap, so handle them specially. */
3649 switch (GET_CODE (arg))
3652 /* This is the same as calling equiv_constant; it is duplicated
3654 if (REGNO_QTY_VALID_P (REGNO (arg)))
3656 int arg_q = REG_QTY (REGNO (arg));
3657 struct qty_table_elem *arg_ent = &qty_table[arg_q];
3659 if (arg_ent->const_rtx != NULL_RTX
3660 && GET_CODE (arg_ent->const_rtx) != REG
3661 && GET_CODE (arg_ent->const_rtx) != PLUS)
3663 = gen_lowpart_if_possible (GET_MODE (arg),
3664 arg_ent->const_rtx);
3679 folded_arg = prev_insn_cc0;
3680 mode_arg = prev_insn_cc0_mode;
3681 const_arg = equiv_constant (folded_arg);
3686 folded_arg = fold_rtx (arg, insn);
3687 const_arg = equiv_constant (folded_arg);
3690 /* For the first three operands, see if the operand
3691 is constant or equivalent to a constant. */
3695 folded_arg0 = folded_arg;
3696 const_arg0 = const_arg;
3697 mode_arg0 = mode_arg;
3700 folded_arg1 = folded_arg;
3701 const_arg1 = const_arg;
3704 const_arg2 = const_arg;
3708 /* Pick the least expensive of the folded argument and an
3709 equivalent constant argument. */
3710 if (const_arg == 0 || const_arg == folded_arg
3711 || COST_IN (const_arg, code) > COST_IN (folded_arg, code))
3712 cheap_arg = folded_arg, expensive_arg = const_arg;
3714 cheap_arg = const_arg, expensive_arg = folded_arg;
3716 /* Try to replace the operand with the cheapest of the two
3717 possibilities. If it doesn't work and this is either of the first
3718 two operands of a commutative operation, try swapping them.
3719 If THAT fails, try the more expensive, provided it is cheaper
3720 than what is already there. */
3722 if (cheap_arg == XEXP (x, i))
3725 if (insn == 0 && ! copied)
3731 /* Order the replacements from cheapest to most expensive. */
3732 replacements[0] = cheap_arg;
3733 replacements[1] = expensive_arg;
3735 for (j = 0; j < 2 && replacements[j]; j++)
3737 int new_cost = COST_IN (replacements[j], code);
3739 /* Stop if what existed before was cheaper. Prefer constants
3740 in the case of a tie. */
3741 if (new_cost > old_cost
3742 || (new_cost == old_cost && CONSTANT_P (XEXP (x, i))))
3745 if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
3748 if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c'
3749 || code == LTGT || code == UNEQ || code == ORDERED
3750 || code == UNORDERED)
3752 validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
3753 validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
3755 if (apply_change_group ())
3757 /* Swap them back to be invalid so that this loop can
3758 continue and flag them to be swapped back later. */
3761 tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
3773 /* Don't try to fold inside of a vector of expressions.
3774 Doing nothing is harmless. */
3778 /* If a commutative operation, place a constant integer as the second
3779 operand unless the first operand is also a constant integer. Otherwise,
3780 place any constant second unless the first operand is also a constant. */
3782 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c'
3783 || code == LTGT || code == UNEQ || code == ORDERED
3784 || code == UNORDERED)
3787 || swap_commutative_operands_p (const_arg0 ? const_arg0
3789 const_arg1 ? const_arg1
3792 rtx tem = XEXP (x, 0);
3794 if (insn == 0 && ! copied)
3800 validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
3801 validate_change (insn, &XEXP (x, 1), tem, 1);
3802 if (apply_change_group ())
3804 tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
3805 tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
3810 /* If X is an arithmetic operation, see if we can simplify it. */
3812 switch (GET_RTX_CLASS (code))
3818 /* We can't simplify extension ops unless we know the
3820 if ((code == ZERO_EXTEND || code == SIGN_EXTEND)
3821 && mode_arg0 == VOIDmode)
3824 /* If we had a CONST, strip it off and put it back later if we
3826 if (const_arg0 != 0 && GET_CODE (const_arg0) == CONST)
3827 is_const = 1, const_arg0 = XEXP (const_arg0, 0);
3829 new = simplify_unary_operation (code, mode,
3830 const_arg0 ? const_arg0 : folded_arg0,
3832 if (new != 0 && is_const)
3833 new = gen_rtx_CONST (mode, new);
3838 /* See what items are actually being compared and set FOLDED_ARG[01]
3839 to those values and CODE to the actual comparison code. If any are
3840 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3841 do anything if both operands are already known to be constant. */
3843 if (const_arg0 == 0 || const_arg1 == 0)
3845 struct table_elt *p0, *p1;
3846 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3847 enum machine_mode mode_arg1;
3849 #ifdef FLOAT_STORE_FLAG_VALUE
3850 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3852 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3853 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3854 false_rtx = CONST0_RTX (mode);
3858 code = find_comparison_args (code, &folded_arg0, &folded_arg1,
3859 &mode_arg0, &mode_arg1);
3860 const_arg0 = equiv_constant (folded_arg0);
3861 const_arg1 = equiv_constant (folded_arg1);
3863 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3864 what kinds of things are being compared, so we can't do
3865 anything with this comparison. */
3867 if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
3870 /* If we do not now have two constants being compared, see
3871 if we can nevertheless deduce some things about the
3873 if (const_arg0 == 0 || const_arg1 == 0)
3875 /* Some addresses are known to be nonzero. We don't know
3876 their sign, but equality comparisons are known. */
3877 if (const_arg1 == const0_rtx
3878 && nonzero_address_p (folded_arg0))
3882 else if (code == NE)
3886 /* See if the two operands are the same. */
3888 if (folded_arg0 == folded_arg1
3889 || (GET_CODE (folded_arg0) == REG
3890 && GET_CODE (folded_arg1) == REG
3891 && (REG_QTY (REGNO (folded_arg0))
3892 == REG_QTY (REGNO (folded_arg1))))
3893 || ((p0 = lookup (folded_arg0,
3894 (safe_hash (folded_arg0, mode_arg0)
3895 & HASH_MASK), mode_arg0))
3896 && (p1 = lookup (folded_arg1,
3897 (safe_hash (folded_arg1, mode_arg0)
3898 & HASH_MASK), mode_arg0))
3899 && p0->first_same_value == p1->first_same_value))
3901 /* Sadly two equal NaNs are not equivalent. */
3902 if (!HONOR_NANS (mode_arg0))
3903 return ((code == EQ || code == LE || code == GE
3904 || code == LEU || code == GEU || code == UNEQ
3905 || code == UNLE || code == UNGE
3907 ? true_rtx : false_rtx);
3908 /* Take care for the FP compares we can resolve. */
3909 if (code == UNEQ || code == UNLE || code == UNGE)
3911 if (code == LTGT || code == LT || code == GT)
3915 /* If FOLDED_ARG0 is a register, see if the comparison we are
3916 doing now is either the same as we did before or the reverse
3917 (we only check the reverse if not floating-point). */
3918 else if (GET_CODE (folded_arg0) == REG)
3920 int qty = REG_QTY (REGNO (folded_arg0));
3922 if (REGNO_QTY_VALID_P (REGNO (folded_arg0)))
3924 struct qty_table_elem *ent = &qty_table[qty];
3926 if ((comparison_dominates_p (ent->comparison_code, code)
3927 || (! FLOAT_MODE_P (mode_arg0)
3928 && comparison_dominates_p (ent->comparison_code,
3929 reverse_condition (code))))
3930 && (rtx_equal_p (ent->comparison_const, folded_arg1)
3932 && rtx_equal_p (ent->comparison_const,
3934 || (GET_CODE (folded_arg1) == REG
3935 && (REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty))))
3936 return (comparison_dominates_p (ent->comparison_code, code)
3937 ? true_rtx : false_rtx);
3943 /* If we are comparing against zero, see if the first operand is
3944 equivalent to an IOR with a constant. If so, we may be able to
3945 determine the result of this comparison. */
3947 if (const_arg1 == const0_rtx)
3949 rtx y = lookup_as_function (folded_arg0, IOR);
3953 && (inner_const = equiv_constant (XEXP (y, 1))) != 0
3954 && GET_CODE (inner_const) == CONST_INT
3955 && INTVAL (inner_const) != 0)
3957 int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
3958 int has_sign = (HOST_BITS_PER_WIDE_INT >= sign_bitnum
3959 && (INTVAL (inner_const)
3960 & ((HOST_WIDE_INT) 1 << sign_bitnum)));
3961 rtx true_rtx = const_true_rtx, false_rtx = const0_rtx;
3963 #ifdef FLOAT_STORE_FLAG_VALUE
3964 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
3966 true_rtx = (CONST_DOUBLE_FROM_REAL_VALUE
3967 (FLOAT_STORE_FLAG_VALUE (mode), mode));
3968 false_rtx = CONST0_RTX (mode);
3992 new = simplify_relational_operation (code,
3993 (mode_arg0 != VOIDmode
3995 : (GET_MODE (const_arg0
3999 ? GET_MODE (const_arg0
4002 : GET_MODE (const_arg1
4005 const_arg0 ? const_arg0 : folded_arg0,
4006 const_arg1 ? const_arg1 : folded_arg1);
4007 #ifdef FLOAT_STORE_FLAG_VALUE
4008 if (new != 0 && GET_MODE_CLASS (mode) == MODE_FLOAT)
4010 if (new == const0_rtx)
4011 new = CONST0_RTX (mode);
4013 new = (CONST_DOUBLE_FROM_REAL_VALUE
4014 (FLOAT_STORE_FLAG_VALUE (mode), mode));
4024 /* If the second operand is a LABEL_REF, see if the first is a MINUS
4025 with that LABEL_REF as its second operand. If so, the result is
4026 the first operand of that MINUS. This handles switches with an
4027 ADDR_DIFF_VEC table. */
4028 if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
4031 = GET_CODE (folded_arg0) == MINUS ? folded_arg0
4032 : lookup_as_function (folded_arg0, MINUS);
4034 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4035 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
4038 /* Now try for a CONST of a MINUS like the above. */
4039 if ((y = (GET_CODE (folded_arg0) == CONST ? folded_arg0
4040 : lookup_as_function (folded_arg0, CONST))) != 0
4041 && GET_CODE (XEXP (y, 0)) == MINUS
4042 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4043 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg1, 0))
4044 return XEXP (XEXP (y, 0), 0);
4047 /* Likewise if the operands are in the other order. */
4048 if (const_arg0 && GET_CODE (const_arg0) == LABEL_REF)
4051 = GET_CODE (folded_arg1) == MINUS ? folded_arg1
4052 : lookup_as_function (folded_arg1, MINUS);
4054 if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
4055 && XEXP (XEXP (y, 1), 0) == XEXP (const_arg0, 0))
4058 /* Now try for a CONST of a MINUS like the above. */
4059 if ((y = (GET_CODE (folded_arg1) == CONST ? folded_arg1
4060 : lookup_as_function (folded_arg1, CONST))) != 0
4061 && GET_CODE (XEXP (y, 0)) == MINUS
4062 && GET_CODE (XEXP (XEXP (y, 0), 1)) == LABEL_REF
4063 && XEXP (XEXP (XEXP (y, 0), 1), 0) == XEXP (const_arg0, 0))
4064 return XEXP (XEXP (y, 0), 0);
4067 /* If second operand is a register equivalent to a negative
4068 CONST_INT, see if we can find a register equivalent to the
4069 positive constant. Make a MINUS if so. Don't do this for
4070 a non-negative constant since we might then alternate between
4071 choosing positive and negative constants. Having the positive
4072 constant previously-used is the more common case. Be sure
4073 the resulting constant is non-negative; if const_arg1 were
4074 the smallest negative number this would overflow: depending
4075 on the mode, this would either just be the same value (and
4076 hence not save anything) or be incorrect. */
4077 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
4078 && INTVAL (const_arg1) < 0
4079 /* This used to test
4081 -INTVAL (const_arg1) >= 0
4083 But The Sun V5.0 compilers mis-compiled that test. So
4084 instead we test for the problematic value in a more direct
4085 manner and hope the Sun compilers get it correct. */
4086 && INTVAL (const_arg1) !=
4087 ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
4088 && GET_CODE (folded_arg1) == REG)
4090 rtx new_const = GEN_INT (-INTVAL (const_arg1));
4092 = lookup (new_const, safe_hash (new_const, mode) & HASH_MASK,
4096 for (p = p->first_same_value; p; p = p->next_same_value)
4097 if (GET_CODE (p->exp) == REG)
4098 return simplify_gen_binary (MINUS, mode, folded_arg0,
4099 canon_reg (p->exp, NULL_RTX));
4104 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
4105 If so, produce (PLUS Z C2-C). */
4106 if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT)
4108 rtx y = lookup_as_function (XEXP (x, 0), PLUS);
4109 if (y && GET_CODE (XEXP (y, 1)) == CONST_INT)
4110 return fold_rtx (plus_constant (copy_rtx (y),
4111 -INTVAL (const_arg1)),
4118 case SMIN: case SMAX: case UMIN: case UMAX:
4119 case IOR: case AND: case XOR:
4121 case ASHIFT: case LSHIFTRT: case ASHIFTRT:
4122 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
4123 is known to be of similar form, we may be able to replace the
4124 operation with a combined operation. This may eliminate the
4125 intermediate operation if every use is simplified in this way.
4126 Note that the similar optimization done by combine.c only works
4127 if the intermediate operation's result has only one reference. */
4129 if (GET_CODE (folded_arg0) == REG
4130 && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
4133 = (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
4134 rtx y = lookup_as_function (folded_arg0, code);
4136 enum rtx_code associate_code;
4140 || 0 == (inner_const
4141 = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
4142 || GET_CODE (inner_const) != CONST_INT
4143 /* If we have compiled a statement like
4144 "if (x == (x & mask1))", and now are looking at
4145 "x & mask2", we will have a case where the first operand
4146 of Y is the same as our first operand. Unless we detect
4147 this case, an infinite loop will result. */
4148 || XEXP (y, 0) == folded_arg0)
4151 /* Don't associate these operations if they are a PLUS with the
4152 same constant and it is a power of two. These might be doable
4153 with a pre- or post-increment. Similarly for two subtracts of
4154 identical powers of two with post decrement. */
4156 if (code == PLUS && const_arg1 == inner_const
4157 && ((HAVE_PRE_INCREMENT
4158 && exact_log2 (INTVAL (const_arg1)) >= 0)
4159 || (HAVE_POST_INCREMENT
4160 && exact_log2 (INTVAL (const_arg1)) >= 0)
4161 || (HAVE_PRE_DECREMENT
4162 && exact_log2 (- INTVAL (const_arg1)) >= 0)
4163 || (HAVE_POST_DECREMENT
4164 && exact_log2 (- INTVAL (const_arg1)) >= 0)))
4167 /* Compute the code used to compose the constants. For example,
4168 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
4170 associate_code = (is_shift || code == MINUS ? PLUS : code);
4172 new_const = simplify_binary_operation (associate_code, mode,
4173 const_arg1, inner_const);
4178 /* If we are associating shift operations, don't let this
4179 produce a shift of the size of the object or larger.
4180 This could occur when we follow a sign-extend by a right
4181 shift on a machine that does a sign-extend as a pair
4184 if (is_shift && GET_CODE (new_const) == CONST_INT
4185 && INTVAL (new_const) >= GET_MODE_BITSIZE (mode))
4187 /* As an exception, we can turn an ASHIFTRT of this
4188 form into a shift of the number of bits - 1. */
4189 if (code == ASHIFTRT)
4190 new_const = GEN_INT (GET_MODE_BITSIZE (mode) - 1);
4195 y = copy_rtx (XEXP (y, 0));
4197 /* If Y contains our first operand (the most common way this
4198 can happen is if Y is a MEM), we would do into an infinite
4199 loop if we tried to fold it. So don't in that case. */
4201 if (! reg_mentioned_p (folded_arg0, y))
4202 y = fold_rtx (y, insn);
4204 return simplify_gen_binary (code, mode, y, new_const);
4208 case DIV: case UDIV:
4209 /* ??? The associative optimization performed immediately above is
4210 also possible for DIV and UDIV using associate_code of MULT.
4211 However, we would need extra code to verify that the
4212 multiplication does not overflow, that is, there is no overflow
4213 in the calculation of new_const. */
4220 new = simplify_binary_operation (code, mode,
4221 const_arg0 ? const_arg0 : folded_arg0,
4222 const_arg1 ? const_arg1 : folded_arg1);
4226 /* (lo_sum (high X) X) is simply X. */
4227 if (code == LO_SUM && const_arg0 != 0
4228 && GET_CODE (const_arg0) == HIGH
4229 && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
4235 new = simplify_ternary_operation (code, mode, mode_arg0,
4236 const_arg0 ? const_arg0 : folded_arg0,
4237 const_arg1 ? const_arg1 : folded_arg1,
4238 const_arg2 ? const_arg2 : XEXP (x, 2));
4242 /* Eliminate CONSTANT_P_RTX if its constant. */
4243 if (code == CONSTANT_P_RTX)
4247 if (optimize == 0 || !flag_gcse)
4253 return new ? new : x;
4256 /* Return a constant value currently equivalent to X.
4257 Return 0 if we don't know one. */
4260 equiv_constant (rtx x)
4262 if (GET_CODE (x) == REG
4263 && REGNO_QTY_VALID_P (REGNO (x)))
4265 int x_q = REG_QTY (REGNO (x));
4266 struct qty_table_elem *x_ent = &qty_table[x_q];
4268 if (x_ent->const_rtx)
4269 x = gen_lowpart_if_possible (GET_MODE (x), x_ent->const_rtx);
4272 if (x == 0 || CONSTANT_P (x))
4275 /* If X is a MEM, try to fold it outside the context of any insn to see if
4276 it might be equivalent to a constant. That handles the case where it
4277 is a constant-pool reference. Then try to look it up in the hash table
4278 in case it is something whose value we have seen before. */
4280 if (GET_CODE (x) == MEM)
4282 struct table_elt *elt;
4284 x = fold_rtx (x, NULL_RTX);
4288 elt = lookup (x, safe_hash (x, GET_MODE (x)) & HASH_MASK, GET_MODE (x));
4292 for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
4293 if (elt->is_const && CONSTANT_P (elt->exp))
4300 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4301 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4302 least-significant part of X.
4303 MODE specifies how big a part of X to return.
4305 If the requested operation cannot be done, 0 is returned.
4307 This is similar to gen_lowpart in emit-rtl.c. */
4310 gen_lowpart_if_possible (enum machine_mode mode, rtx x)
4312 rtx result = gen_lowpart_common (mode, x);
4316 else if (GET_CODE (x) == MEM)
4318 /* This is the only other case we handle. */
4322 if (WORDS_BIG_ENDIAN)
4323 offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
4324 - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
4325 if (BYTES_BIG_ENDIAN)
4326 /* Adjust the address so that the address-after-the-data is
4328 offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode))
4329 - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
4331 new = adjust_address_nv (x, mode, offset);
4332 if (! memory_address_p (mode, XEXP (new, 0)))
4341 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4342 branch. It will be zero if not.
4344 In certain cases, this can cause us to add an equivalence. For example,
4345 if we are following the taken case of
4347 we can add the fact that `i' and '2' are now equivalent.
4349 In any case, we can record that this comparison was passed. If the same
4350 comparison is seen later, we will know its value. */
4353 record_jump_equiv (rtx insn, int taken)
4355 int cond_known_true;
4358 enum machine_mode mode, mode0, mode1;
4359 int reversed_nonequality = 0;
4362 /* Ensure this is the right kind of insn. */
4363 if (! any_condjump_p (insn))
4365 set = pc_set (insn);
4367 /* See if this jump condition is known true or false. */
4369 cond_known_true = (XEXP (SET_SRC (set), 2) == pc_rtx);
4371 cond_known_true = (XEXP (SET_SRC (set), 1) == pc_rtx);
4373 /* Get the type of comparison being done and the operands being compared.
4374 If we had to reverse a non-equality condition, record that fact so we
4375 know that it isn't valid for floating-point. */
4376 code = GET_CODE (XEXP (SET_SRC (set), 0));
4377 op0 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 0), insn);
4378 op1 = fold_rtx (XEXP (XEXP (SET_SRC (set), 0), 1), insn);
4380 code = find_comparison_args (code, &op0, &op1, &mode0, &mode1);
4381 if (! cond_known_true)
4383 code = reversed_comparison_code_parts (code, op0, op1, insn);
4385 /* Don't remember if we can't find the inverse. */
4386 if (code == UNKNOWN)
4390 /* The mode is the mode of the non-constant. */
4392 if (mode1 != VOIDmode)
4395 record_jump_cond (code, mode, op0, op1, reversed_nonequality);
4398 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
4399 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
4400 Make any useful entries we can with that information. Called from
4401 above function and called recursively. */
4404 record_jump_cond (enum rtx_code code, enum machine_mode mode, rtx op0,
4405 rtx op1, int reversed_nonequality)
4407 unsigned op0_hash, op1_hash;
4408 int op0_in_memory, op1_in_memory;
4409 struct table_elt *op0_elt, *op1_elt;
4411 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
4412 we know that they are also equal in the smaller mode (this is also
4413 true for all smaller modes whether or not there is a SUBREG, but
4414 is not worth testing for with no SUBREG). */
4416 /* Note that GET_MODE (op0) may not equal MODE. */
4417 if (code == EQ && GET_CODE (op0) == SUBREG
4418 && (GET_MODE_SIZE (GET_MODE (op0))
4419 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4421 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4422 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4424 record_jump_cond (code, mode, SUBREG_REG (op0),
4425 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4426 reversed_nonequality);
4429 if (code == EQ && GET_CODE (op1) == SUBREG
4430 && (GET_MODE_SIZE (GET_MODE (op1))
4431 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4433 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4434 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4436 record_jump_cond (code, mode, SUBREG_REG (op1),
4437 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4438 reversed_nonequality);
4441 /* Similarly, if this is an NE comparison, and either is a SUBREG
4442 making a smaller mode, we know the whole thing is also NE. */
4444 /* Note that GET_MODE (op0) may not equal MODE;
4445 if we test MODE instead, we can get an infinite recursion
4446 alternating between two modes each wider than MODE. */
4448 if (code == NE && GET_CODE (op0) == SUBREG
4449 && subreg_lowpart_p (op0)
4450 && (GET_MODE_SIZE (GET_MODE (op0))
4451 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
4453 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
4454 rtx tem = gen_lowpart_if_possible (inner_mode, op1);
4456 record_jump_cond (code, mode, SUBREG_REG (op0),
4457 tem ? tem : gen_rtx_SUBREG (inner_mode, op1, 0),
4458 reversed_nonequality);
4461 if (code == NE && GET_CODE (op1) == SUBREG
4462 && subreg_lowpart_p (op1)
4463 && (GET_MODE_SIZE (GET_MODE (op1))
4464 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1)))))
4466 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
4467 rtx tem = gen_lowpart_if_possible (inner_mode, op0);
4469 record_jump_cond (code, mode, SUBREG_REG (op1),
4470 tem ? tem : gen_rtx_SUBREG (inner_mode, op0, 0),
4471 reversed_nonequality);
4474 /* Hash both operands. */
4477 hash_arg_in_memory = 0;
4478 op0_hash = HASH (op0, mode);
4479 op0_in_memory = hash_arg_in_memory;
4485 hash_arg_in_memory = 0;
4486 op1_hash = HASH (op1, mode);
4487 op1_in_memory = hash_arg_in_memory;
4492 /* Look up both operands. */
4493 op0_elt = lookup (op0, op0_hash, mode);
4494 op1_elt = lookup (op1, op1_hash, mode);
4496 /* If both operands are already equivalent or if they are not in the
4497 table but are identical, do nothing. */
4498 if ((op0_elt != 0 && op1_elt != 0
4499 && op0_elt->first_same_value == op1_elt->first_same_value)
4500 || op0 == op1 || rtx_equal_p (op0, op1))
4503 /* If we aren't setting two things equal all we can do is save this
4504 comparison. Similarly if this is floating-point. In the latter
4505 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4506 If we record the equality, we might inadvertently delete code
4507 whose intent was to change -0 to +0. */
4509 if (code != EQ || FLOAT_MODE_P (GET_MODE (op0)))
4511 struct qty_table_elem *ent;
4514 /* If we reversed a floating-point comparison, if OP0 is not a
4515 register, or if OP1 is neither a register or constant, we can't
4518 if (GET_CODE (op1) != REG)
4519 op1 = equiv_constant (op1);
4521 if ((reversed_nonequality && FLOAT_MODE_P (mode))
4522 || GET_CODE (op0) != REG || op1 == 0)
4525 /* Put OP0 in the hash table if it isn't already. This gives it a
4526 new quantity number. */
4529 if (insert_regs (op0, NULL, 0))
4531 rehash_using_reg (op0);
4532 op0_hash = HASH (op0, mode);
4534 /* If OP0 is contained in OP1, this changes its hash code
4535 as well. Faster to rehash than to check, except
4536 for the simple case of a constant. */
4537 if (! CONSTANT_P (op1))
4538 op1_hash = HASH (op1,mode);
4541 op0_elt = insert (op0, NULL, op0_hash, mode);
4542 op0_elt->in_memory = op0_in_memory;
4545 qty = REG_QTY (REGNO (op0));
4546 ent = &qty_table[qty];
4548 ent->comparison_code = code;
4549 if (GET_CODE (op1) == REG)
4551 /* Look it up again--in case op0 and op1 are the same. */
4552 op1_elt = lookup (op1, op1_hash, mode);
4554 /* Put OP1 in the hash table so it gets a new quantity number. */
4557 if (insert_regs (op1, NULL, 0))
4559 rehash_using_reg (op1);
4560 op1_hash = HASH (op1, mode);
4563 op1_elt = insert (op1, NULL, op1_hash, mode);
4564 op1_elt->in_memory = op1_in_memory;
4567 ent->comparison_const = NULL_RTX;
4568 ent->comparison_qty = REG_QTY (REGNO (op1));
4572 ent->comparison_const = op1;
4573 ent->comparison_qty = -1;
4579 /* If either side is still missing an equivalence, make it now,
4580 then merge the equivalences. */
4584 if (insert_regs (op0, NULL, 0))
4586 rehash_using_reg (op0);
4587 op0_hash = HASH (op0, mode);
4590 op0_elt = insert (op0, NULL, op0_hash, mode);
4591 op0_elt->in_memory = op0_in_memory;
4596 if (insert_regs (op1, NULL, 0))
4598 rehash_using_reg (op1);
4599 op1_hash = HASH (op1, mode);
4602 op1_elt = insert (op1, NULL, op1_hash, mode);
4603 op1_elt->in_memory = op1_in_memory;
4606 merge_equiv_classes (op0_elt, op1_elt);
4607 last_jump_equiv_class = op0_elt;
4610 /* CSE processing for one instruction.
4611 First simplify sources and addresses of all assignments
4612 in the instruction, using previously-computed equivalents values.
4613 Then install the new sources and destinations in the table
4614 of available values.
4616 If LIBCALL_INSN is nonzero, don't record any equivalence made in
4617 the insn. It means that INSN is inside libcall block. In this
4618 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
4620 /* Data on one SET contained in the instruction. */
4624 /* The SET rtx itself. */
4626 /* The SET_SRC of the rtx (the original value, if it is changing). */
4628 /* The hash-table element for the SET_SRC of the SET. */
4629 struct table_elt *src_elt;
4630 /* Hash value for the SET_SRC. */
4632 /* Hash value for the SET_DEST. */
4634 /* The SET_DEST, with SUBREG, etc., stripped. */
4636 /* Nonzero if the SET_SRC is in memory. */
4638 /* Nonzero if the SET_SRC contains something
4639 whose value cannot be predicted and understood. */
4641 /* Original machine mode, in case it becomes a CONST_INT.
4642 The size of this field should match the size of the mode
4643 field of struct rtx_def (see rtl.h). */
4644 ENUM_BITFIELD(machine_mode) mode : 8;
4645 /* A constant equivalent for SET_SRC, if any. */
4647 /* Original SET_SRC value used for libcall notes. */
4649 /* Hash value of constant equivalent for SET_SRC. */
4650 unsigned src_const_hash;
4651 /* Table entry for constant equivalent for SET_SRC, if any. */
4652 struct table_elt *src_const_elt;
4656 cse_insn (rtx insn, rtx libcall_insn)
4658 rtx x = PATTERN (insn);
4664 /* Records what this insn does to set CC0. */
4665 rtx this_insn_cc0 = 0;
4666 enum machine_mode this_insn_cc0_mode = VOIDmode;
4670 struct table_elt *src_eqv_elt = 0;
4671 int src_eqv_volatile = 0;
4672 int src_eqv_in_memory = 0;
4673 unsigned src_eqv_hash = 0;
4675 struct set *sets = (struct set *) 0;
4679 /* Find all the SETs and CLOBBERs in this instruction.
4680 Record all the SETs in the array `set' and count them.
4681 Also determine whether there is a CLOBBER that invalidates
4682 all memory references, or all references at varying addresses. */
4684 if (GET_CODE (insn) == CALL_INSN)
4686 for (tem = CALL_INSN_FUNCTION_USAGE (insn); tem; tem = XEXP (tem, 1))
4688 if (GET_CODE (XEXP (tem, 0)) == CLOBBER)
4689 invalidate (SET_DEST (XEXP (tem, 0)), VOIDmode);
4690 XEXP (tem, 0) = canon_reg (XEXP (tem, 0), insn);
4694 if (GET_CODE (x) == SET)
4696 sets = alloca (sizeof (struct set));
4699 /* Ignore SETs that are unconditional jumps.
4700 They never need cse processing, so this does not hurt.
4701 The reason is not efficiency but rather
4702 so that we can test at the end for instructions
4703 that have been simplified to unconditional jumps
4704 and not be misled by unchanged instructions
4705 that were unconditional jumps to begin with. */
4706 if (SET_DEST (x) == pc_rtx
4707 && GET_CODE (SET_SRC (x)) == LABEL_REF)
4710 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4711 The hard function value register is used only once, to copy to
4712 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4713 Ensure we invalidate the destination register. On the 80386 no
4714 other code would invalidate it since it is a fixed_reg.
4715 We need not check the return of apply_change_group; see canon_reg. */
4717 else if (GET_CODE (SET_SRC (x)) == CALL)
4719 canon_reg (SET_SRC (x), insn);
4720 apply_change_group ();
4721 fold_rtx (SET_SRC (x), insn);
4722 invalidate (SET_DEST (x), VOIDmode);
4727 else if (GET_CODE (x) == PARALLEL)
4729 int lim = XVECLEN (x, 0);
4731 sets = alloca (lim * sizeof (struct set));
4733 /* Find all regs explicitly clobbered in this insn,
4734 and ensure they are not replaced with any other regs
4735 elsewhere in this insn.
4736 When a reg that is clobbered is also used for input,
4737 we should presume that that is for a reason,
4738 and we should not substitute some other register
4739 which is not supposed to be clobbered.
4740 Therefore, this loop cannot be merged into the one below
4741 because a CALL may precede a CLOBBER and refer to the
4742 value clobbered. We must not let a canonicalization do
4743 anything in that case. */
4744 for (i = 0; i < lim; i++)
4746 rtx y = XVECEXP (x, 0, i);
4747 if (GET_CODE (y) == CLOBBER)
4749 rtx clobbered = XEXP (y, 0);
4751 if (GET_CODE (clobbered) == REG
4752 || GET_CODE (clobbered) == SUBREG)
4753 invalidate (clobbered, VOIDmode);
4754 else if (GET_CODE (clobbered) == STRICT_LOW_PART
4755 || GET_CODE (clobbered) == ZERO_EXTRACT)
4756 invalidate (XEXP (clobbered, 0), GET_MODE (clobbered));
4760 for (i = 0; i < lim; i++)
4762 rtx y = XVECEXP (x, 0, i);
4763 if (GET_CODE (y) == SET)
4765 /* As above, we ignore unconditional jumps and call-insns and
4766 ignore the result of apply_change_group. */
4767 if (GET_CODE (SET_SRC (y)) == CALL)
4769 canon_reg (SET_SRC (y), insn);
4770 apply_change_group ();
4771 fold_rtx (SET_SRC (y), insn);
4772 invalidate (SET_DEST (y), VOIDmode);
4774 else if (SET_DEST (y) == pc_rtx
4775 && GET_CODE (SET_SRC (y)) == LABEL_REF)
4778 sets[n_sets++].rtl = y;
4780 else if (GET_CODE (y) == CLOBBER)
4782 /* If we clobber memory, canon the address.
4783 This does nothing when a register is clobbered
4784 because we have already invalidated the reg. */
4785 if (GET_CODE (XEXP (y, 0)) == MEM)
4786 canon_reg (XEXP (y, 0), NULL_RTX);
4788 else if (GET_CODE (y) == USE
4789 && ! (GET_CODE (XEXP (y, 0)) == REG
4790 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
4791 canon_reg (y, NULL_RTX);
4792 else if (GET_CODE (y) == CALL)
4794 /* The result of apply_change_group can be ignored; see
4796 canon_reg (y, insn);
4797 apply_change_group ();
4802 else if (GET_CODE (x) == CLOBBER)
4804 if (GET_CODE (XEXP (x, 0)) == MEM)
4805 canon_reg (XEXP (x, 0), NULL_RTX);
4808 /* Canonicalize a USE of a pseudo register or memory location. */
4809 else if (GET_CODE (x) == USE
4810 && ! (GET_CODE (XEXP (x, 0)) == REG
4811 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
4812 canon_reg (XEXP (x, 0), NULL_RTX);
4813 else if (GET_CODE (x) == CALL)
4815 /* The result of apply_change_group can be ignored; see canon_reg. */
4816 canon_reg (x, insn);
4817 apply_change_group ();
4821 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4822 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4823 is handled specially for this case, and if it isn't set, then there will
4824 be no equivalence for the destination. */
4825 if (n_sets == 1 && REG_NOTES (insn) != 0
4826 && (tem = find_reg_note (insn, REG_EQUAL, NULL_RTX)) != 0
4827 && (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
4828 || GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
4830 src_eqv = fold_rtx (canon_reg (XEXP (tem, 0), NULL_RTX), insn);
4831 XEXP (tem, 0) = src_eqv;
4834 /* Canonicalize sources and addresses of destinations.
4835 We do this in a separate pass to avoid problems when a MATCH_DUP is
4836 present in the insn pattern. In that case, we want to ensure that
4837 we don't break the duplicate nature of the pattern. So we will replace
4838 both operands at the same time. Otherwise, we would fail to find an
4839 equivalent substitution in the loop calling validate_change below.
4841 We used to suppress canonicalization of DEST if it appears in SRC,
4842 but we don't do this any more. */
4844 for (i = 0; i < n_sets; i++)
4846 rtx dest = SET_DEST (sets[i].rtl);
4847 rtx src = SET_SRC (sets[i].rtl);
4848 rtx new = canon_reg (src, insn);
4851 sets[i].orig_src = src;
4852 if ((GET_CODE (new) == REG && GET_CODE (src) == REG
4853 && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
4854 != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
4855 || (insn_code = recog_memoized (insn)) < 0
4856 || insn_data[insn_code].n_dups > 0)
4857 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
4859 SET_SRC (sets[i].rtl) = new;
4861 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4863 validate_change (insn, &XEXP (dest, 1),
4864 canon_reg (XEXP (dest, 1), insn), 1);
4865 validate_change (insn, &XEXP (dest, 2),
4866 canon_reg (XEXP (dest, 2), insn), 1);
4869 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
4870 || GET_CODE (dest) == ZERO_EXTRACT
4871 || GET_CODE (dest) == SIGN_EXTRACT)
4872 dest = XEXP (dest, 0);
4874 if (GET_CODE (dest) == MEM)
4875 canon_reg (dest, insn);
4878 /* Now that we have done all the replacements, we can apply the change
4879 group and see if they all work. Note that this will cause some
4880 canonicalizations that would have worked individually not to be applied
4881 because some other canonicalization didn't work, but this should not
4884 The result of apply_change_group can be ignored; see canon_reg. */
4886 apply_change_group ();
4888 /* Set sets[i].src_elt to the class each source belongs to.
4889 Detect assignments from or to volatile things
4890 and set set[i] to zero so they will be ignored
4891 in the rest of this function.
4893 Nothing in this loop changes the hash table or the register chains. */
4895 for (i = 0; i < n_sets; i++)
4899 struct table_elt *elt = 0, *p;
4900 enum machine_mode mode;
4903 rtx src_related = 0;
4904 struct table_elt *src_const_elt = 0;
4905 int src_cost = MAX_COST;
4906 int src_eqv_cost = MAX_COST;
4907 int src_folded_cost = MAX_COST;
4908 int src_related_cost = MAX_COST;
4909 int src_elt_cost = MAX_COST;
4910 int src_regcost = MAX_COST;
4911 int src_eqv_regcost = MAX_COST;
4912 int src_folded_regcost = MAX_COST;
4913 int src_related_regcost = MAX_COST;
4914 int src_elt_regcost = MAX_COST;
4915 /* Set nonzero if we need to call force_const_mem on with the
4916 contents of src_folded before using it. */
4917 int src_folded_force_flag = 0;
4919 dest = SET_DEST (sets[i].rtl);
4920 src = SET_SRC (sets[i].rtl);
4922 /* If SRC is a constant that has no machine mode,
4923 hash it with the destination's machine mode.
4924 This way we can keep different modes separate. */
4926 mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
4927 sets[i].mode = mode;
4931 enum machine_mode eqvmode = mode;
4932 if (GET_CODE (dest) == STRICT_LOW_PART)
4933 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
4935 hash_arg_in_memory = 0;
4936 src_eqv_hash = HASH (src_eqv, eqvmode);
4938 /* Find the equivalence class for the equivalent expression. */
4941 src_eqv_elt = lookup (src_eqv, src_eqv_hash, eqvmode);
4943 src_eqv_volatile = do_not_record;
4944 src_eqv_in_memory = hash_arg_in_memory;
4947 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4948 value of the INNER register, not the destination. So it is not
4949 a valid substitution for the source. But save it for later. */
4950 if (GET_CODE (dest) == STRICT_LOW_PART)
4953 src_eqv_here = src_eqv;
4955 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4956 simplified result, which may not necessarily be valid. */
4957 src_folded = fold_rtx (src, insn);
4960 /* ??? This caused bad code to be generated for the m68k port with -O2.
4961 Suppose src is (CONST_INT -1), and that after truncation src_folded
4962 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4963 At the end we will add src and src_const to the same equivalence
4964 class. We now have 3 and -1 on the same equivalence class. This
4965 causes later instructions to be mis-optimized. */
4966 /* If storing a constant in a bitfield, pre-truncate the constant
4967 so we will be able to record it later. */
4968 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
4969 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
4971 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
4973 if (GET_CODE (src) == CONST_INT
4974 && GET_CODE (width) == CONST_INT
4975 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
4976 && (INTVAL (src) & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
4978 = GEN_INT (INTVAL (src) & (((HOST_WIDE_INT) 1
4979 << INTVAL (width)) - 1));
4983 /* Compute SRC's hash code, and also notice if it
4984 should not be recorded at all. In that case,
4985 prevent any further processing of this assignment. */
4987 hash_arg_in_memory = 0;
4990 sets[i].src_hash = HASH (src, mode);
4991 sets[i].src_volatile = do_not_record;
4992 sets[i].src_in_memory = hash_arg_in_memory;
4994 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4995 a pseudo, do not record SRC. Using SRC as a replacement for
4996 anything else will be incorrect in that situation. Note that
4997 this usually occurs only for stack slots, in which case all the
4998 RTL would be referring to SRC, so we don't lose any optimization
4999 opportunities by not having SRC in the hash table. */
5001 if (GET_CODE (src) == MEM
5002 && find_reg_note (insn, REG_EQUIV, NULL_RTX) != 0
5003 && GET_CODE (dest) == REG
5004 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
5005 sets[i].src_volatile = 1;
5008 /* It is no longer clear why we used to do this, but it doesn't
5009 appear to still be needed. So let's try without it since this
5010 code hurts cse'ing widened ops. */
5011 /* If source is a perverse subreg (such as QI treated as an SI),
5012 treat it as volatile. It may do the work of an SI in one context
5013 where the extra bits are not being used, but cannot replace an SI
5015 if (GET_CODE (src) == SUBREG
5016 && (GET_MODE_SIZE (GET_MODE (src))
5017 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
5018 sets[i].src_volatile = 1;
5021 /* Locate all possible equivalent forms for SRC. Try to replace
5022 SRC in the insn with each cheaper equivalent.
5024 We have the following types of equivalents: SRC itself, a folded
5025 version, a value given in a REG_EQUAL note, or a value related
5028 Each of these equivalents may be part of an additional class
5029 of equivalents (if more than one is in the table, they must be in
5030 the same class; we check for this).
5032 If the source is volatile, we don't do any table lookups.
5034 We note any constant equivalent for possible later use in a
5037 if (!sets[i].src_volatile)
5038 elt = lookup (src, sets[i].src_hash, mode);
5040 sets[i].src_elt = elt;
5042 if (elt && src_eqv_here && src_eqv_elt)
5044 if (elt->first_same_value != src_eqv_elt->first_same_value)
5046 /* The REG_EQUAL is indicating that two formerly distinct
5047 classes are now equivalent. So merge them. */
5048 merge_equiv_classes (elt, src_eqv_elt);
5049 src_eqv_hash = HASH (src_eqv, elt->mode);
5050 src_eqv_elt = lookup (src_eqv, src_eqv_hash, elt->mode);
5056 else if (src_eqv_elt)
5059 /* Try to find a constant somewhere and record it in `src_const'.
5060 Record its table element, if any, in `src_const_elt'. Look in
5061 any known equivalences first. (If the constant is not in the
5062 table, also set `sets[i].src_const_hash'). */
5064 for (p = elt->first_same_value; p; p = p->next_same_value)
5068 src_const_elt = elt;
5073 && (CONSTANT_P (src_folded)
5074 /* Consider (minus (label_ref L1) (label_ref L2)) as
5075 "constant" here so we will record it. This allows us
5076 to fold switch statements when an ADDR_DIFF_VEC is used. */
5077 || (GET_CODE (src_folded) == MINUS
5078 && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
5079 && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
5080 src_const = src_folded, src_const_elt = elt;
5081 else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
5082 src_const = src_eqv_here, src_const_elt = src_eqv_elt;
5084 /* If we don't know if the constant is in the table, get its
5085 hash code and look it up. */
5086 if (src_const && src_const_elt == 0)
5088 sets[i].src_const_hash = HASH (src_const, mode);
5089 src_const_elt = lookup (src_const, sets[i].src_const_hash, mode);
5092 sets[i].src_const = src_const;
5093 sets[i].src_const_elt = src_const_elt;
5095 /* If the constant and our source are both in the table, mark them as
5096 equivalent. Otherwise, if a constant is in the table but the source
5097 isn't, set ELT to it. */
5098 if (src_const_elt && elt
5099 && src_const_elt->first_same_value != elt->first_same_value)
5100 merge_equiv_classes (elt, src_const_elt);
5101 else if (src_const_elt && elt == 0)
5102 elt = src_const_elt;
5104 /* See if there is a register linearly related to a constant
5105 equivalent of SRC. */
5107 && (GET_CODE (src_const) == CONST
5108 || (src_const_elt && src_const_elt->related_value != 0)))
5110 src_related = use_related_value (src_const, src_const_elt);
5113 struct table_elt *src_related_elt
5114 = lookup (src_related, HASH (src_related, mode), mode);
5115 if (src_related_elt && elt)
5117 if (elt->first_same_value
5118 != src_related_elt->first_same_value)
5119 /* This can occur when we previously saw a CONST
5120 involving a SYMBOL_REF and then see the SYMBOL_REF
5121 twice. Merge the involved classes. */
5122 merge_equiv_classes (elt, src_related_elt);
5125 src_related_elt = 0;
5127 else if (src_related_elt && elt == 0)
5128 elt = src_related_elt;
5132 /* See if we have a CONST_INT that is already in a register in a
5135 if (src_const && src_related == 0 && GET_CODE (src_const) == CONST_INT
5136 && GET_MODE_CLASS (mode) == MODE_INT
5137 && GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
5139 enum machine_mode wider_mode;
5141 for (wider_mode = GET_MODE_WIDER_MODE (mode);
5142 GET_MODE_BITSIZE (wider_mode) <= BITS_PER_WORD
5143 && src_related == 0;
5144 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
5146 struct table_elt *const_elt
5147 = lookup (src_const, HASH (src_const, wider_mode), wider_mode);
5152 for (const_elt = const_elt->first_same_value;
5153 const_elt; const_elt = const_elt->next_same_value)
5154 if (GET_CODE (const_elt->exp) == REG)
5156 src_related = gen_lowpart_if_possible (mode,
5163 /* Another possibility is that we have an AND with a constant in
5164 a mode narrower than a word. If so, it might have been generated
5165 as part of an "if" which would narrow the AND. If we already
5166 have done the AND in a wider mode, we can use a SUBREG of that
5169 if (flag_expensive_optimizations && ! src_related
5170 && GET_CODE (src) == AND && GET_CODE (XEXP (src, 1)) == CONST_INT
5171 && GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5173 enum machine_mode tmode;
5174 rtx new_and = gen_rtx_AND (VOIDmode, NULL_RTX, XEXP (src, 1));
5176 for (tmode = GET_MODE_WIDER_MODE (mode);
5177 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5178 tmode = GET_MODE_WIDER_MODE (tmode))
5180 rtx inner = gen_lowpart_if_possible (tmode, XEXP (src, 0));
5181 struct table_elt *larger_elt;
5185 PUT_MODE (new_and, tmode);
5186 XEXP (new_and, 0) = inner;
5187 larger_elt = lookup (new_and, HASH (new_and, tmode), tmode);
5188 if (larger_elt == 0)
5191 for (larger_elt = larger_elt->first_same_value;
5192 larger_elt; larger_elt = larger_elt->next_same_value)
5193 if (GET_CODE (larger_elt->exp) == REG)
5196 = gen_lowpart_if_possible (mode, larger_elt->exp);
5206 #ifdef LOAD_EXTEND_OP
5207 /* See if a MEM has already been loaded with a widening operation;
5208 if it has, we can use a subreg of that. Many CISC machines
5209 also have such operations, but this is only likely to be
5210 beneficial these machines. */
5212 if (flag_expensive_optimizations && src_related == 0
5213 && (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5214 && GET_MODE_CLASS (mode) == MODE_INT
5215 && GET_CODE (src) == MEM && ! do_not_record
5216 && LOAD_EXTEND_OP (mode) != NIL)
5218 enum machine_mode tmode;
5220 /* Set what we are trying to extend and the operation it might
5221 have been extended with. */
5222 PUT_CODE (memory_extend_rtx, LOAD_EXTEND_OP (mode));
5223 XEXP (memory_extend_rtx, 0) = src;
5225 for (tmode = GET_MODE_WIDER_MODE (mode);
5226 GET_MODE_SIZE (tmode) <= UNITS_PER_WORD;
5227 tmode = GET_MODE_WIDER_MODE (tmode))
5229 struct table_elt *larger_elt;
5231 PUT_MODE (memory_extend_rtx, tmode);
5232 larger_elt = lookup (memory_extend_rtx,
5233 HASH (memory_extend_rtx, tmode), tmode);
5234 if (larger_elt == 0)
5237 for (larger_elt = larger_elt->first_same_value;
5238 larger_elt; larger_elt = larger_elt->next_same_value)
5239 if (GET_CODE (larger_elt->exp) == REG)
5241 src_related = gen_lowpart_if_possible (mode,
5250 #endif /* LOAD_EXTEND_OP */
5252 if (src == src_folded)
5255 /* At this point, ELT, if nonzero, points to a class of expressions
5256 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5257 and SRC_RELATED, if nonzero, each contain additional equivalent
5258 expressions. Prune these latter expressions by deleting expressions
5259 already in the equivalence class.
5261 Check for an equivalent identical to the destination. If found,
5262 this is the preferred equivalent since it will likely lead to
5263 elimination of the insn. Indicate this by placing it in
5267 elt = elt->first_same_value;
5268 for (p = elt; p; p = p->next_same_value)
5270 enum rtx_code code = GET_CODE (p->exp);
5272 /* If the expression is not valid, ignore it. Then we do not
5273 have to check for validity below. In most cases, we can use
5274 `rtx_equal_p', since canonicalization has already been done. */
5275 if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
5278 /* Also skip paradoxical subregs, unless that's what we're
5281 && (GET_MODE_SIZE (GET_MODE (p->exp))
5282 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))
5284 && GET_CODE (src) == SUBREG
5285 && GET_MODE (src) == GET_MODE (p->exp)
5286 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5287 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p->exp))))))
5290 if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
5292 else if (src_folded && GET_CODE (src_folded) == code
5293 && rtx_equal_p (src_folded, p->exp))
5295 else if (src_eqv_here && GET_CODE (src_eqv_here) == code
5296 && rtx_equal_p (src_eqv_here, p->exp))
5298 else if (src_related && GET_CODE (src_related) == code
5299 && rtx_equal_p (src_related, p->exp))
5302 /* This is the same as the destination of the insns, we want
5303 to prefer it. Copy it to src_related. The code below will
5304 then give it a negative cost. */
5305 if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
5309 /* Find the cheapest valid equivalent, trying all the available
5310 possibilities. Prefer items not in the hash table to ones
5311 that are when they are equal cost. Note that we can never
5312 worsen an insn as the current contents will also succeed.
5313 If we find an equivalent identical to the destination, use it as best,
5314 since this insn will probably be eliminated in that case. */
5317 if (rtx_equal_p (src, dest))
5318 src_cost = src_regcost = -1;
5321 src_cost = COST (src);
5322 src_regcost = approx_reg_cost (src);
5328 if (rtx_equal_p (src_eqv_here, dest))
5329 src_eqv_cost = src_eqv_regcost = -1;
5332 src_eqv_cost = COST (src_eqv_here);
5333 src_eqv_regcost = approx_reg_cost (src_eqv_here);
5339 if (rtx_equal_p (src_folded, dest))
5340 src_folded_cost = src_folded_regcost = -1;
5343 src_folded_cost = COST (src_folded);
5344 src_folded_regcost = approx_reg_cost (src_folded);
5350 if (rtx_equal_p (src_related, dest))
5351 src_related_cost = src_related_regcost = -1;
5354 src_related_cost = COST (src_related);
5355 src_related_regcost = approx_reg_cost (src_related);
5359 /* If this was an indirect jump insn, a known label will really be
5360 cheaper even though it looks more expensive. */
5361 if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
5362 src_folded = src_const, src_folded_cost = src_folded_regcost = -1;
5364 /* Terminate loop when replacement made. This must terminate since
5365 the current contents will be tested and will always be valid. */
5370 /* Skip invalid entries. */
5371 while (elt && GET_CODE (elt->exp) != REG
5372 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
5373 elt = elt->next_same_value;
5375 /* A paradoxical subreg would be bad here: it'll be the right
5376 size, but later may be adjusted so that the upper bits aren't
5377 what we want. So reject it. */
5379 && GET_CODE (elt->exp) == SUBREG
5380 && (GET_MODE_SIZE (GET_MODE (elt->exp))
5381 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))
5382 /* It is okay, though, if the rtx we're trying to match
5383 will ignore any of the bits we can't predict. */
5385 && GET_CODE (src) == SUBREG
5386 && GET_MODE (src) == GET_MODE (elt->exp)
5387 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))
5388 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt->exp))))))
5390 elt = elt->next_same_value;
5396 src_elt_cost = elt->cost;
5397 src_elt_regcost = elt->regcost;
5400 /* Find cheapest and skip it for the next time. For items
5401 of equal cost, use this order:
5402 src_folded, src, src_eqv, src_related and hash table entry. */
5404 && preferrable (src_folded_cost, src_folded_regcost,
5405 src_cost, src_regcost) <= 0
5406 && preferrable (src_folded_cost, src_folded_regcost,
5407 src_eqv_cost, src_eqv_regcost) <= 0
5408 && preferrable (src_folded_cost, src_folded_regcost,
5409 src_related_cost, src_related_regcost) <= 0
5410 && preferrable (src_folded_cost, src_folded_regcost,
5411 src_elt_cost, src_elt_regcost) <= 0)
5413 trial = src_folded, src_folded_cost = MAX_COST;
5414 if (src_folded_force_flag)
5415 trial = force_const_mem (mode, trial);
5418 && preferrable (src_cost, src_regcost,
5419 src_eqv_cost, src_eqv_regcost) <= 0
5420 && preferrable (src_cost, src_regcost,
5421 src_related_cost, src_related_regcost) <= 0
5422 && preferrable (src_cost, src_regcost,
5423 src_elt_cost, src_elt_regcost) <= 0)
5424 trial = src, src_cost = MAX_COST;
5425 else if (src_eqv_here
5426 && preferrable (src_eqv_cost, src_eqv_regcost,
5427 src_related_cost, src_related_regcost) <= 0
5428 && preferrable (src_eqv_cost, src_eqv_regcost,
5429 src_elt_cost, src_elt_regcost) <= 0)
5430 trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
5431 else if (src_related
5432 && preferrable (src_related_cost, src_related_regcost,
5433 src_elt_cost, src_elt_regcost) <= 0)
5434 trial = copy_rtx (src_related), src_related_cost = MAX_COST;
5437 trial = copy_rtx (elt->exp);
5438 elt = elt->next_same_value;
5439 src_elt_cost = MAX_COST;
5442 /* We don't normally have an insn matching (set (pc) (pc)), so
5443 check for this separately here. We will delete such an
5446 For other cases such as a table jump or conditional jump
5447 where we know the ultimate target, go ahead and replace the
5448 operand. While that may not make a valid insn, we will
5449 reemit the jump below (and also insert any necessary
5451 if (n_sets == 1 && dest == pc_rtx
5453 || (GET_CODE (trial) == LABEL_REF
5454 && ! condjump_p (insn))))
5456 SET_SRC (sets[i].rtl) = trial;
5457 cse_jumps_altered = 1;
5461 /* Look for a substitution that makes a valid insn. */
5462 else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
5464 rtx new = canon_reg (SET_SRC (sets[i].rtl), insn);
5466 /* If we just made a substitution inside a libcall, then we
5467 need to make the same substitution in any notes attached
5468 to the RETVAL insn. */
5470 && (GET_CODE (sets[i].orig_src) == REG
5471 || GET_CODE (sets[i].orig_src) == SUBREG
5472 || GET_CODE (sets[i].orig_src) == MEM))
5473 simplify_replace_rtx (REG_NOTES (libcall_insn),
5474 sets[i].orig_src, copy_rtx (new));
5476 /* The result of apply_change_group can be ignored; see
5479 validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
5480 apply_change_group ();
5484 /* If we previously found constant pool entries for
5485 constants and this is a constant, try making a
5486 pool entry. Put it in src_folded unless we already have done
5487 this since that is where it likely came from. */
5489 else if (constant_pool_entries_cost
5490 && CONSTANT_P (trial)
5491 /* Reject cases that will abort in decode_rtx_const.
5492 On the alpha when simplifying a switch, we get
5493 (const (truncate (minus (label_ref) (label_ref)))). */
5494 && ! (GET_CODE (trial) == CONST
5495 && GET_CODE (XEXP (trial, 0)) == TRUNCATE)
5496 /* Likewise on IA-64, except without the truncate. */
5497 && ! (GET_CODE (trial) == CONST
5498 && GET_CODE (XEXP (trial, 0)) == MINUS
5499 && GET_CODE (XEXP (XEXP (trial, 0), 0)) == LABEL_REF
5500 && GET_CODE (XEXP (XEXP (trial, 0), 1)) == LABEL_REF)
5502 || (GET_CODE (src_folded) != MEM
5503 && ! src_folded_force_flag))
5504 && GET_MODE_CLASS (mode) != MODE_CC
5505 && mode != VOIDmode)
5507 src_folded_force_flag = 1;
5509 src_folded_cost = constant_pool_entries_cost;
5513 src = SET_SRC (sets[i].rtl);
5515 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5516 However, there is an important exception: If both are registers
5517 that are not the head of their equivalence class, replace SET_SRC
5518 with the head of the class. If we do not do this, we will have
5519 both registers live over a portion of the basic block. This way,
5520 their lifetimes will likely abut instead of overlapping. */
5521 if (GET_CODE (dest) == REG
5522 && REGNO_QTY_VALID_P (REGNO (dest)))
5524 int dest_q = REG_QTY (REGNO (dest));
5525 struct qty_table_elem *dest_ent = &qty_table[dest_q];
5527 if (dest_ent->mode == GET_MODE (dest)
5528 && dest_ent->first_reg != REGNO (dest)
5529 && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
5530 /* Don't do this if the original insn had a hard reg as
5531 SET_SRC or SET_DEST. */
5532 && (GET_CODE (sets[i].src) != REG
5533 || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER)
5534 && (GET_CODE (dest) != REG || REGNO (dest) >= FIRST_PSEUDO_REGISTER))
5535 /* We can't call canon_reg here because it won't do anything if
5536 SRC is a hard register. */
5538 int src_q = REG_QTY (REGNO (src));
5539 struct qty_table_elem *src_ent = &qty_table[src_q];
5540 int first = src_ent->first_reg;
5542 = (first >= FIRST_PSEUDO_REGISTER
5543 ? regno_reg_rtx[first] : gen_rtx_REG (GET_MODE (src), first));
5545 /* We must use validate-change even for this, because this
5546 might be a special no-op instruction, suitable only to
5548 if (validate_change (insn, &SET_SRC (sets[i].rtl), new_src, 0))
5551 /* If we had a constant that is cheaper than what we are now
5552 setting SRC to, use that constant. We ignored it when we
5553 thought we could make this into a no-op. */
5554 if (src_const && COST (src_const) < COST (src)
5555 && validate_change (insn, &SET_SRC (sets[i].rtl),
5562 /* If we made a change, recompute SRC values. */
5563 if (src != sets[i].src)
5567 hash_arg_in_memory = 0;
5569 sets[i].src_hash = HASH (src, mode);
5570 sets[i].src_volatile = do_not_record;
5571 sets[i].src_in_memory = hash_arg_in_memory;
5572 sets[i].src_elt = lookup (src, sets[i].src_hash, mode);
5575 /* If this is a single SET, we are setting a register, and we have an
5576 equivalent constant, we want to add a REG_NOTE. We don't want
5577 to write a REG_EQUAL note for a constant pseudo since verifying that
5578 that pseudo hasn't been eliminated is a pain. Such a note also
5579 won't help anything.
5581 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
5582 which can be created for a reference to a compile time computable
5583 entry in a jump table. */
5585 if (n_sets == 1 && src_const && GET_CODE (dest) == REG
5586 && GET_CODE (src_const) != REG
5587 && ! (GET_CODE (src_const) == CONST
5588 && GET_CODE (XEXP (src_const, 0)) == MINUS
5589 && GET_CODE (XEXP (XEXP (src_const, 0), 0)) == LABEL_REF
5590 && GET_CODE (XEXP (XEXP (src_const, 0), 1)) == LABEL_REF))
5592 /* We only want a REG_EQUAL note if src_const != src. */
5593 if (! rtx_equal_p (src, src_const))
5595 /* Make sure that the rtx is not shared. */
5596 src_const = copy_rtx (src_const);
5598 /* Record the actual constant value in a REG_EQUAL note,
5599 making a new one if one does not already exist. */
5600 set_unique_reg_note (insn, REG_EQUAL, src_const);
5604 /* Now deal with the destination. */
5607 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5608 to the MEM or REG within it. */
5609 while (GET_CODE (dest) == SIGN_EXTRACT
5610 || GET_CODE (dest) == ZERO_EXTRACT
5611 || GET_CODE (dest) == SUBREG
5612 || GET_CODE (dest) == STRICT_LOW_PART)
5613 dest = XEXP (dest, 0);
5615 sets[i].inner_dest = dest;
5617 if (GET_CODE (dest) == MEM)
5619 #ifdef PUSH_ROUNDING
5620 /* Stack pushes invalidate the stack pointer. */
5621 rtx addr = XEXP (dest, 0);
5622 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
5623 && XEXP (addr, 0) == stack_pointer_rtx)
5624 invalidate (stack_pointer_rtx, Pmode);
5626 dest = fold_rtx (dest, insn);
5629 /* Compute the hash code of the destination now,
5630 before the effects of this instruction are recorded,
5631 since the register values used in the address computation
5632 are those before this instruction. */
5633 sets[i].dest_hash = HASH (dest, mode);
5635 /* Don't enter a bit-field in the hash table
5636 because the value in it after the store
5637 may not equal what was stored, due to truncation. */
5639 if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
5640 || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
5642 rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
5644 if (src_const != 0 && GET_CODE (src_const) == CONST_INT
5645 && GET_CODE (width) == CONST_INT
5646 && INTVAL (width) < HOST_BITS_PER_WIDE_INT
5647 && ! (INTVAL (src_const)
5648 & ((HOST_WIDE_INT) (-1) << INTVAL (width))))
5649 /* Exception: if the value is constant,
5650 and it won't be truncated, record it. */
5654 /* This is chosen so that the destination will be invalidated
5655 but no new value will be recorded.
5656 We must invalidate because sometimes constant
5657 values can be recorded for bitfields. */
5658 sets[i].src_elt = 0;
5659 sets[i].src_volatile = 1;
5665 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5667 else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
5669 /* One less use of the label this insn used to jump to. */
5671 cse_jumps_altered = 1;
5672 /* No more processing for this set. */
5676 /* If this SET is now setting PC to a label, we know it used to
5677 be a conditional or computed branch. */
5678 else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
5680 /* Now emit a BARRIER after the unconditional jump. */
5681 if (NEXT_INSN (insn) == 0
5682 || GET_CODE (NEXT_INSN (insn)) != BARRIER)
5683 emit_barrier_after (insn);
5685 /* We reemit the jump in as many cases as possible just in
5686 case the form of an unconditional jump is significantly
5687 different than a computed jump or conditional jump.
5689 If this insn has multiple sets, then reemitting the
5690 jump is nontrivial. So instead we just force rerecognition
5691 and hope for the best. */
5694 rtx new = emit_jump_insn_after (gen_jump (XEXP (src, 0)), insn);
5696 JUMP_LABEL (new) = XEXP (src, 0);
5697 LABEL_NUSES (XEXP (src, 0))++;
5701 /* Now emit a BARRIER after the unconditional jump. */
5702 if (NEXT_INSN (insn) == 0
5703 || GET_CODE (NEXT_INSN (insn)) != BARRIER)
5704 emit_barrier_after (insn);
5707 INSN_CODE (insn) = -1;
5709 never_reached_warning (insn, NULL);
5711 /* Do not bother deleting any unreachable code,
5712 let jump/flow do that. */
5714 cse_jumps_altered = 1;
5718 /* If destination is volatile, invalidate it and then do no further
5719 processing for this assignment. */
5721 else if (do_not_record)
5723 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5724 invalidate (dest, VOIDmode);
5725 else if (GET_CODE (dest) == MEM)
5727 /* Outgoing arguments for a libcall don't
5728 affect any recorded expressions. */
5729 if (! libcall_insn || insn == libcall_insn)
5730 invalidate (dest, VOIDmode);
5732 else if (GET_CODE (dest) == STRICT_LOW_PART
5733 || GET_CODE (dest) == ZERO_EXTRACT)
5734 invalidate (XEXP (dest, 0), GET_MODE (dest));
5738 if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
5739 sets[i].dest_hash = HASH (SET_DEST (sets[i].rtl), mode);
5742 /* If setting CC0, record what it was set to, or a constant, if it
5743 is equivalent to a constant. If it is being set to a floating-point
5744 value, make a COMPARE with the appropriate constant of 0. If we
5745 don't do this, later code can interpret this as a test against
5746 const0_rtx, which can cause problems if we try to put it into an
5747 insn as a floating-point operand. */
5748 if (dest == cc0_rtx)
5750 this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
5751 this_insn_cc0_mode = mode;
5752 if (FLOAT_MODE_P (mode))
5753 this_insn_cc0 = gen_rtx_COMPARE (VOIDmode, this_insn_cc0,
5759 /* Now enter all non-volatile source expressions in the hash table
5760 if they are not already present.
5761 Record their equivalence classes in src_elt.
5762 This way we can insert the corresponding destinations into
5763 the same classes even if the actual sources are no longer in them
5764 (having been invalidated). */
5766 if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
5767 && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
5769 struct table_elt *elt;
5770 struct table_elt *classp = sets[0].src_elt;
5771 rtx dest = SET_DEST (sets[0].rtl);
5772 enum machine_mode eqvmode = GET_MODE (dest);
5774 if (GET_CODE (dest) == STRICT_LOW_PART)
5776 eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
5779 if (insert_regs (src_eqv, classp, 0))
5781 rehash_using_reg (src_eqv);
5782 src_eqv_hash = HASH (src_eqv, eqvmode);
5784 elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
5785 elt->in_memory = src_eqv_in_memory;
5788 /* Check to see if src_eqv_elt is the same as a set source which
5789 does not yet have an elt, and if so set the elt of the set source
5791 for (i = 0; i < n_sets; i++)
5792 if (sets[i].rtl && sets[i].src_elt == 0
5793 && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
5794 sets[i].src_elt = src_eqv_elt;
5797 for (i = 0; i < n_sets; i++)
5798 if (sets[i].rtl && ! sets[i].src_volatile
5799 && ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
5801 if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
5803 /* REG_EQUAL in setting a STRICT_LOW_PART
5804 gives an equivalent for the entire destination register,
5805 not just for the subreg being stored in now.
5806 This is a more interesting equivalence, so we arrange later
5807 to treat the entire reg as the destination. */
5808 sets[i].src_elt = src_eqv_elt;
5809 sets[i].src_hash = src_eqv_hash;
5813 /* Insert source and constant equivalent into hash table, if not
5815 struct table_elt *classp = src_eqv_elt;
5816 rtx src = sets[i].src;
5817 rtx dest = SET_DEST (sets[i].rtl);
5818 enum machine_mode mode
5819 = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
5821 if (sets[i].src_elt == 0)
5823 /* Don't put a hard register source into the table if this is
5824 the last insn of a libcall. In this case, we only need
5825 to put src_eqv_elt in src_elt. */
5826 if (! find_reg_note (insn, REG_RETVAL, NULL_RTX))
5828 struct table_elt *elt;
5830 /* Note that these insert_regs calls cannot remove
5831 any of the src_elt's, because they would have failed to
5832 match if not still valid. */
5833 if (insert_regs (src, classp, 0))
5835 rehash_using_reg (src);
5836 sets[i].src_hash = HASH (src, mode);
5838 elt = insert (src, classp, sets[i].src_hash, mode);
5839 elt->in_memory = sets[i].src_in_memory;
5840 sets[i].src_elt = classp = elt;
5843 sets[i].src_elt = classp;
5845 if (sets[i].src_const && sets[i].src_const_elt == 0
5846 && src != sets[i].src_const
5847 && ! rtx_equal_p (sets[i].src_const, src))
5848 sets[i].src_elt = insert (sets[i].src_const, classp,
5849 sets[i].src_const_hash, mode);
5852 else if (sets[i].src_elt == 0)
5853 /* If we did not insert the source into the hash table (e.g., it was
5854 volatile), note the equivalence class for the REG_EQUAL value, if any,
5855 so that the destination goes into that class. */
5856 sets[i].src_elt = src_eqv_elt;
5858 invalidate_from_clobbers (x);
5860 /* Some registers are invalidated by subroutine calls. Memory is
5861 invalidated by non-constant calls. */
5863 if (GET_CODE (insn) == CALL_INSN)
5865 if (! CONST_OR_PURE_CALL_P (insn))
5866 invalidate_memory ();
5867 invalidate_for_call ();
5870 /* Now invalidate everything set by this instruction.
5871 If a SUBREG or other funny destination is being set,
5872 sets[i].rtl is still nonzero, so here we invalidate the reg
5873 a part of which is being set. */
5875 for (i = 0; i < n_sets; i++)
5878 /* We can't use the inner dest, because the mode associated with
5879 a ZERO_EXTRACT is significant. */
5880 rtx dest = SET_DEST (sets[i].rtl);
5882 /* Needed for registers to remove the register from its
5883 previous quantity's chain.
5884 Needed for memory if this is a nonvarying address, unless
5885 we have just done an invalidate_memory that covers even those. */
5886 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
5887 invalidate (dest, VOIDmode);
5888 else if (GET_CODE (dest) == MEM)
5890 /* Outgoing arguments for a libcall don't
5891 affect any recorded expressions. */
5892 if (! libcall_insn || insn == libcall_insn)
5893 invalidate (dest, VOIDmode);
5895 else if (GET_CODE (dest) == STRICT_LOW_PART
5896 || GET_CODE (dest) == ZERO_EXTRACT)
5897 invalidate (XEXP (dest, 0), GET_MODE (dest));
5900 /* A volatile ASM invalidates everything. */
5901 if (GET_CODE (insn) == INSN
5902 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5903 && MEM_VOLATILE_P (PATTERN (insn)))
5904 flush_hash_table ();
5906 /* Make sure registers mentioned in destinations
5907 are safe for use in an expression to be inserted.
5908 This removes from the hash table
5909 any invalid entry that refers to one of these registers.
5911 We don't care about the return value from mention_regs because
5912 we are going to hash the SET_DEST values unconditionally. */
5914 for (i = 0; i < n_sets; i++)
5918 rtx x = SET_DEST (sets[i].rtl);
5920 if (GET_CODE (x) != REG)
5924 /* We used to rely on all references to a register becoming
5925 inaccessible when a register changes to a new quantity,
5926 since that changes the hash code. However, that is not
5927 safe, since after HASH_SIZE new quantities we get a
5928 hash 'collision' of a register with its own invalid
5929 entries. And since SUBREGs have been changed not to
5930 change their hash code with the hash code of the register,
5931 it wouldn't work any longer at all. So we have to check
5932 for any invalid references lying around now.
5933 This code is similar to the REG case in mention_regs,
5934 but it knows that reg_tick has been incremented, and
5935 it leaves reg_in_table as -1 . */
5936 unsigned int regno = REGNO (x);
5937 unsigned int endregno
5938 = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
5939 : HARD_REGNO_NREGS (regno, GET_MODE (x)));
5942 for (i = regno; i < endregno; i++)
5944 if (REG_IN_TABLE (i) >= 0)
5946 remove_invalid_refs (i);
5947 REG_IN_TABLE (i) = -1;
5954 /* We may have just removed some of the src_elt's from the hash table.
5955 So replace each one with the current head of the same class. */
5957 for (i = 0; i < n_sets; i++)
5960 if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
5961 /* If elt was removed, find current head of same class,
5962 or 0 if nothing remains of that class. */
5964 struct table_elt *elt = sets[i].src_elt;
5966 while (elt && elt->prev_same_value)
5967 elt = elt->prev_same_value;
5969 while (elt && elt->first_same_value == 0)
5970 elt = elt->next_same_value;
5971 sets[i].src_elt = elt ? elt->first_same_value : 0;
5975 /* Now insert the destinations into their equivalence classes. */
5977 for (i = 0; i < n_sets; i++)
5980 rtx dest = SET_DEST (sets[i].rtl);
5981 rtx inner_dest = sets[i].inner_dest;
5982 struct table_elt *elt;
5984 /* Don't record value if we are not supposed to risk allocating
5985 floating-point values in registers that might be wider than
5987 if ((flag_float_store
5988 && GET_CODE (dest) == MEM
5989 && FLOAT_MODE_P (GET_MODE (dest)))
5990 /* Don't record BLKmode values, because we don't know the
5991 size of it, and can't be sure that other BLKmode values
5992 have the same or smaller size. */
5993 || GET_MODE (dest) == BLKmode
5994 /* Don't record values of destinations set inside a libcall block
5995 since we might delete the libcall. Things should have been set
5996 up so we won't want to reuse such a value, but we play it safe
5999 /* If we didn't put a REG_EQUAL value or a source into the hash
6000 table, there is no point is recording DEST. */
6001 || sets[i].src_elt == 0
6002 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
6003 or SIGN_EXTEND, don't record DEST since it can cause
6004 some tracking to be wrong.
6006 ??? Think about this more later. */
6007 || (GET_CODE (dest) == SUBREG
6008 && (GET_MODE_SIZE (GET_MODE (dest))
6009 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6010 && (GET_CODE (sets[i].src) == SIGN_EXTEND
6011 || GET_CODE (sets[i].src) == ZERO_EXTEND)))
6014 /* STRICT_LOW_PART isn't part of the value BEING set,
6015 and neither is the SUBREG inside it.
6016 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6017 if (GET_CODE (dest) == STRICT_LOW_PART)
6018 dest = SUBREG_REG (XEXP (dest, 0));
6020 if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG)
6021 /* Registers must also be inserted into chains for quantities. */
6022 if (insert_regs (dest, sets[i].src_elt, 1))
6024 /* If `insert_regs' changes something, the hash code must be
6026 rehash_using_reg (dest);
6027 sets[i].dest_hash = HASH (dest, GET_MODE (dest));
6030 if (GET_CODE (inner_dest) == MEM
6031 && GET_CODE (XEXP (inner_dest, 0)) == ADDRESSOF)
6032 /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say
6033 that (MEM (ADDRESSOF (X))) is equivalent to Y.
6034 Consider the case in which the address of the MEM is
6035 passed to a function, which alters the MEM. Then, if we
6036 later use Y instead of the MEM we'll miss the update. */
6037 elt = insert (dest, 0, sets[i].dest_hash, GET_MODE (dest));
6039 elt = insert (dest, sets[i].src_elt,
6040 sets[i].dest_hash, GET_MODE (dest));
6042 elt->in_memory = (GET_CODE (sets[i].inner_dest) == MEM
6043 && (! RTX_UNCHANGING_P (sets[i].inner_dest)
6044 || fixed_base_plus_p (XEXP (sets[i].inner_dest,
6047 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6048 narrower than M2, and both M1 and M2 are the same number of words,
6049 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6050 make that equivalence as well.
6052 However, BAR may have equivalences for which gen_lowpart_if_possible
6053 will produce a simpler value than gen_lowpart_if_possible applied to
6054 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6055 BAR's equivalences. If we don't get a simplified form, make
6056 the SUBREG. It will not be used in an equivalence, but will
6057 cause two similar assignments to be detected.
6059 Note the loop below will find SUBREG_REG (DEST) since we have
6060 already entered SRC and DEST of the SET in the table. */
6062 if (GET_CODE (dest) == SUBREG
6063 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - 1)
6065 == (GET_MODE_SIZE (GET_MODE (dest)) - 1) / UNITS_PER_WORD)
6066 && (GET_MODE_SIZE (GET_MODE (dest))
6067 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
6068 && sets[i].src_elt != 0)
6070 enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
6071 struct table_elt *elt, *classp = 0;
6073 for (elt = sets[i].src_elt->first_same_value; elt;
6074 elt = elt->next_same_value)
6078 struct table_elt *src_elt;
6081 /* Ignore invalid entries. */
6082 if (GET_CODE (elt->exp) != REG
6083 && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
6086 /* We may have already been playing subreg games. If the
6087 mode is already correct for the destination, use it. */
6088 if (GET_MODE (elt->exp) == new_mode)
6092 /* Calculate big endian correction for the SUBREG_BYTE.
6093 We have already checked that M1 (GET_MODE (dest))
6094 is not narrower than M2 (new_mode). */
6095 if (BYTES_BIG_ENDIAN)
6096 byte = (GET_MODE_SIZE (GET_MODE (dest))
6097 - GET_MODE_SIZE (new_mode));
6099 new_src = simplify_gen_subreg (new_mode, elt->exp,
6100 GET_MODE (dest), byte);
6103 /* The call to simplify_gen_subreg fails if the value
6104 is VOIDmode, yet we can't do any simplification, e.g.
6105 for EXPR_LISTs denoting function call results.
6106 It is invalid to construct a SUBREG with a VOIDmode
6107 SUBREG_REG, hence a zero new_src means we can't do
6108 this substitution. */
6112 src_hash = HASH (new_src, new_mode);
6113 src_elt = lookup (new_src, src_hash, new_mode);
6115 /* Put the new source in the hash table is if isn't
6119 if (insert_regs (new_src, classp, 0))
6121 rehash_using_reg (new_src);
6122 src_hash = HASH (new_src, new_mode);
6124 src_elt = insert (new_src, classp, src_hash, new_mode);
6125 src_elt->in_memory = elt->in_memory;
6127 else if (classp && classp != src_elt->first_same_value)
6128 /* Show that two things that we've seen before are
6129 actually the same. */
6130 merge_equiv_classes (src_elt, classp);
6132 classp = src_elt->first_same_value;
6133 /* Ignore invalid entries. */
6135 && GET_CODE (classp->exp) != REG
6136 && ! exp_equiv_p (classp->exp, classp->exp, 1, 0))
6137 classp = classp->next_same_value;
6142 /* Special handling for (set REG0 REG1) where REG0 is the
6143 "cheapest", cheaper than REG1. After cse, REG1 will probably not
6144 be used in the sequel, so (if easily done) change this insn to
6145 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
6146 that computed their value. Then REG1 will become a dead store
6147 and won't cloud the situation for later optimizations.
6149 Do not make this change if REG1 is a hard register, because it will
6150 then be used in the sequel and we may be changing a two-operand insn
6151 into a three-operand insn.
6153 Also do not do this if we are operating on a copy of INSN.
6155 Also don't do this if INSN ends a libcall; this would cause an unrelated
6156 register to be set in the middle of a libcall, and we then get bad code
6157 if the libcall is deleted. */
6159 if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
6160 && NEXT_INSN (PREV_INSN (insn)) == insn
6161 && GET_CODE (SET_SRC (sets[0].rtl)) == REG
6162 && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
6163 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl))))
6165 int src_q = REG_QTY (REGNO (SET_SRC (sets[0].rtl)));
6166 struct qty_table_elem *src_ent = &qty_table[src_q];
6168 if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
6169 && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
6172 /* Scan for the previous nonnote insn, but stop at a basic
6176 prev = PREV_INSN (prev);
6178 while (prev && GET_CODE (prev) == NOTE
6179 && NOTE_LINE_NUMBER (prev) != NOTE_INSN_BASIC_BLOCK);
6181 /* Do not swap the registers around if the previous instruction
6182 attaches a REG_EQUIV note to REG1.
6184 ??? It's not entirely clear whether we can transfer a REG_EQUIV
6185 from the pseudo that originally shadowed an incoming argument
6186 to another register. Some uses of REG_EQUIV might rely on it
6187 being attached to REG1 rather than REG2.
6189 This section previously turned the REG_EQUIV into a REG_EQUAL
6190 note. We cannot do that because REG_EQUIV may provide an
6191 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
6193 if (prev != 0 && GET_CODE (prev) == INSN
6194 && GET_CODE (PATTERN (prev)) == SET
6195 && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
6196 && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
6198 rtx dest = SET_DEST (sets[0].rtl);
6199 rtx src = SET_SRC (sets[0].rtl);
6202 validate_change (prev, &SET_DEST (PATTERN (prev)), dest, 1);
6203 validate_change (insn, &SET_DEST (sets[0].rtl), src, 1);
6204 validate_change (insn, &SET_SRC (sets[0].rtl), dest, 1);
6205 apply_change_group ();
6207 /* If INSN has a REG_EQUAL note, and this note mentions
6208 REG0, then we must delete it, because the value in
6209 REG0 has changed. If the note's value is REG1, we must
6210 also delete it because that is now this insn's dest. */
6211 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
6213 && (reg_mentioned_p (dest, XEXP (note, 0))
6214 || rtx_equal_p (src, XEXP (note, 0))))
6215 remove_note (insn, note);
6220 /* If this is a conditional jump insn, record any known equivalences due to
6221 the condition being tested. */
6223 last_jump_equiv_class = 0;
6224 if (GET_CODE (insn) == JUMP_INSN
6225 && n_sets == 1 && GET_CODE (x) == SET
6226 && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
6227 record_jump_equiv (insn, 0);
6230 /* If the previous insn set CC0 and this insn no longer references CC0,
6231 delete the previous insn. Here we use the fact that nothing expects CC0
6232 to be valid over an insn, which is true until the final pass. */
6233 if (prev_insn && GET_CODE (prev_insn) == INSN
6234 && (tem = single_set (prev_insn)) != 0
6235 && SET_DEST (tem) == cc0_rtx
6236 && ! reg_mentioned_p (cc0_rtx, x))
6237 delete_insn (prev_insn);
6239 prev_insn_cc0 = this_insn_cc0;
6240 prev_insn_cc0_mode = this_insn_cc0_mode;
6245 /* Remove from the hash table all expressions that reference memory. */
6248 invalidate_memory (void)
6251 struct table_elt *p, *next;
6253 for (i = 0; i < HASH_SIZE; i++)
6254 for (p = table[i]; p; p = next)
6256 next = p->next_same_hash;
6258 remove_from_table (p, i);
6262 /* If ADDR is an address that implicitly affects the stack pointer, return
6263 1 and update the register tables to show the effect. Else, return 0. */
6266 addr_affects_sp_p (rtx addr)
6268 if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
6269 && GET_CODE (XEXP (addr, 0)) == REG
6270 && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
6272 if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
6274 REG_TICK (STACK_POINTER_REGNUM)++;
6275 /* Is it possible to use a subreg of SP? */
6276 SUBREG_TICKED (STACK_POINTER_REGNUM) = -1;
6279 /* This should be *very* rare. */
6280 if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
6281 invalidate (stack_pointer_rtx, VOIDmode);
6289 /* Perform invalidation on the basis of everything about an insn
6290 except for invalidating the actual places that are SET in it.
6291 This includes the places CLOBBERed, and anything that might
6292 alias with something that is SET or CLOBBERed.
6294 X is the pattern of the insn. */
6297 invalidate_from_clobbers (rtx x)
6299 if (GET_CODE (x) == CLOBBER)
6301 rtx ref = XEXP (x, 0);
6304 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6305 || GET_CODE (ref) == MEM)
6306 invalidate (ref, VOIDmode);
6307 else if (GET_CODE (ref) == STRICT_LOW_PART
6308 || GET_CODE (ref) == ZERO_EXTRACT)
6309 invalidate (XEXP (ref, 0), GET_MODE (ref));
6312 else if (GET_CODE (x) == PARALLEL)
6315 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
6317 rtx y = XVECEXP (x, 0, i);
6318 if (GET_CODE (y) == CLOBBER)
6320 rtx ref = XEXP (y, 0);
6321 if (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
6322 || GET_CODE (ref) == MEM)
6323 invalidate (ref, VOIDmode);
6324 else if (GET_CODE (ref) == STRICT_LOW_PART
6325 || GET_CODE (ref) == ZERO_EXTRACT)
6326 invalidate (XEXP (ref, 0), GET_MODE (ref));
6332 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6333 and replace any registers in them with either an equivalent constant
6334 or the canonical form of the register. If we are inside an address,
6335 only do this if the address remains valid.
6337 OBJECT is 0 except when within a MEM in which case it is the MEM.
6339 Return the replacement for X. */
6342 cse_process_notes (rtx x, rtx object)
6344 enum rtx_code code = GET_CODE (x);
6345 const char *fmt = GET_RTX_FORMAT (code);
6362 validate_change (x, &XEXP (x, 0),
6363 cse_process_notes (XEXP (x, 0), x), 0);
6368 if (REG_NOTE_KIND (x) == REG_EQUAL)
6369 XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
6371 XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
6378 rtx new = cse_process_notes (XEXP (x, 0), object);
6379 /* We don't substitute VOIDmode constants into these rtx,
6380 since they would impede folding. */
6381 if (GET_MODE (new) != VOIDmode)
6382 validate_change (object, &XEXP (x, 0), new, 0);
6387 i = REG_QTY (REGNO (x));
6389 /* Return a constant or a constant register. */
6390 if (REGNO_QTY_VALID_P (REGNO (x)))
6392 struct qty_table_elem *ent = &qty_table[i];
6394 if (ent->const_rtx != NULL_RTX
6395 && (CONSTANT_P (ent->const_rtx)
6396 || GET_CODE (ent->const_rtx) == REG))
6398 rtx new = gen_lowpart_if_possible (GET_MODE (x), ent->const_rtx);
6404 /* Otherwise, canonicalize this register. */
6405 return canon_reg (x, NULL_RTX);
6411 for (i = 0; i < GET_RTX_LENGTH (code); i++)
6413 validate_change (object, &XEXP (x, i),
6414 cse_process_notes (XEXP (x, i), object), 0);
6419 /* Find common subexpressions between the end test of a loop and the beginning
6420 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6422 Often we have a loop where an expression in the exit test is used
6423 in the body of the loop. For example "while (*p) *q++ = *p++;".
6424 Because of the way we duplicate the loop exit test in front of the loop,
6425 however, we don't detect that common subexpression. This will be caught
6426 when global cse is implemented, but this is a quite common case.
6428 This function handles the most common cases of these common expressions.
6429 It is called after we have processed the basic block ending with the
6430 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6431 jumps to a label used only once. */
6434 cse_around_loop (rtx loop_start)
6438 struct table_elt *p;
6440 /* If the jump at the end of the loop doesn't go to the start, we don't
6442 for (insn = PREV_INSN (loop_start);
6443 insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
6444 insn = PREV_INSN (insn))
6448 || GET_CODE (insn) != NOTE
6449 || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
6452 /* If the last insn of the loop (the end test) was an NE comparison,
6453 we will interpret it as an EQ comparison, since we fell through
6454 the loop. Any equivalences resulting from that comparison are
6455 therefore not valid and must be invalidated. */
6456 if (last_jump_equiv_class)
6457 for (p = last_jump_equiv_class->first_same_value; p;
6458 p = p->next_same_value)
6460 if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
6461 || (GET_CODE (p->exp) == SUBREG
6462 && GET_CODE (SUBREG_REG (p->exp)) == REG))
6463 invalidate (p->exp, VOIDmode);
6464 else if (GET_CODE (p->exp) == STRICT_LOW_PART
6465 || GET_CODE (p->exp) == ZERO_EXTRACT)
6466 invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
6469 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6470 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6472 The only thing we do with SET_DEST is invalidate entries, so we
6473 can safely process each SET in order. It is slightly less efficient
6474 to do so, but we only want to handle the most common cases.
6476 The gen_move_insn call in cse_set_around_loop may create new pseudos.
6477 These pseudos won't have valid entries in any of the tables indexed
6478 by register number, such as reg_qty. We avoid out-of-range array
6479 accesses by not processing any instructions created after cse started. */
6481 for (insn = NEXT_INSN (loop_start);
6482 GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
6483 && INSN_UID (insn) < max_insn_uid
6484 && ! (GET_CODE (insn) == NOTE
6485 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
6486 insn = NEXT_INSN (insn))
6489 && (GET_CODE (PATTERN (insn)) == SET
6490 || GET_CODE (PATTERN (insn)) == CLOBBER))
6491 cse_set_around_loop (PATTERN (insn), insn, loop_start);
6492 else if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == PARALLEL)
6493 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
6494 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
6495 || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
6496 cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
6501 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6502 since they are done elsewhere. This function is called via note_stores. */
6505 invalidate_skipped_set (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED)
6507 enum rtx_code code = GET_CODE (dest);
6510 && ! addr_affects_sp_p (dest) /* If this is not a stack push ... */
6511 /* There are times when an address can appear varying and be a PLUS
6512 during this scan when it would be a fixed address were we to know
6513 the proper equivalences. So invalidate all memory if there is
6514 a BLKmode or nonscalar memory reference or a reference to a
6515 variable address. */
6516 && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
6517 || cse_rtx_varies_p (XEXP (dest, 0), 0)))
6519 invalidate_memory ();
6523 if (GET_CODE (set) == CLOBBER
6528 if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
6529 invalidate (XEXP (dest, 0), GET_MODE (dest));
6530 else if (code == REG || code == SUBREG || code == MEM)
6531 invalidate (dest, VOIDmode);
6534 /* Invalidate all insns from START up to the end of the function or the
6535 next label. This called when we wish to CSE around a block that is
6536 conditionally executed. */
6539 invalidate_skipped_block (rtx start)
6543 for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
6544 insn = NEXT_INSN (insn))
6546 if (! INSN_P (insn))
6549 if (GET_CODE (insn) == CALL_INSN)
6551 if (! CONST_OR_PURE_CALL_P (insn))
6552 invalidate_memory ();
6553 invalidate_for_call ();
6556 invalidate_from_clobbers (PATTERN (insn));
6557 note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
6561 /* If modifying X will modify the value in *DATA (which is really an
6562 `rtx *'), indicate that fact by setting the pointed to value to
6566 cse_check_loop_start (rtx x, rtx set ATTRIBUTE_UNUSED, void *data)
6568 rtx *cse_check_loop_start_value = (rtx *) data;
6570 if (*cse_check_loop_start_value == NULL_RTX
6571 || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
6574 if ((GET_CODE (x) == MEM && GET_CODE (*cse_check_loop_start_value) == MEM)
6575 || reg_overlap_mentioned_p (x, *cse_check_loop_start_value))
6576 *cse_check_loop_start_value = NULL_RTX;
6579 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6580 a loop that starts with the label at LOOP_START.
6582 If X is a SET, we see if its SET_SRC is currently in our hash table.
6583 If so, we see if it has a value equal to some register used only in the
6584 loop exit code (as marked by jump.c).
6586 If those two conditions are true, we search backwards from the start of
6587 the loop to see if that same value was loaded into a register that still
6588 retains its value at the start of the loop.
6590 If so, we insert an insn after the load to copy the destination of that
6591 load into the equivalent register and (try to) replace our SET_SRC with that
6594 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6597 cse_set_around_loop (rtx x, rtx insn, rtx loop_start)
6599 struct table_elt *src_elt;
6601 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6602 are setting PC or CC0 or whose SET_SRC is already a register. */
6603 if (GET_CODE (x) == SET
6604 && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
6605 && GET_CODE (SET_SRC (x)) != REG)
6607 src_elt = lookup (SET_SRC (x),
6608 HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
6609 GET_MODE (SET_DEST (x)));
6612 for (src_elt = src_elt->first_same_value; src_elt;
6613 src_elt = src_elt->next_same_value)
6614 if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
6615 && COST (src_elt->exp) < COST (SET_SRC (x)))
6619 /* Look for an insn in front of LOOP_START that sets
6620 something in the desired mode to SET_SRC (x) before we hit
6621 a label or CALL_INSN. */
6623 for (p = prev_nonnote_insn (loop_start);
6624 p && GET_CODE (p) != CALL_INSN
6625 && GET_CODE (p) != CODE_LABEL;
6626 p = prev_nonnote_insn (p))
6627 if ((set = single_set (p)) != 0
6628 && GET_CODE (SET_DEST (set)) == REG
6629 && GET_MODE (SET_DEST (set)) == src_elt->mode
6630 && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
6632 /* We now have to ensure that nothing between P
6633 and LOOP_START modified anything referenced in
6634 SET_SRC (x). We know that nothing within the loop
6635 can modify it, or we would have invalidated it in
6638 rtx cse_check_loop_start_value = SET_SRC (x);
6639 for (q = p; q != loop_start; q = NEXT_INSN (q))
6641 note_stores (PATTERN (q),
6642 cse_check_loop_start,
6643 &cse_check_loop_start_value);
6645 /* If nothing was changed and we can replace our
6646 SET_SRC, add an insn after P to copy its destination
6647 to what we will be replacing SET_SRC with. */
6648 if (cse_check_loop_start_value
6650 && !can_throw_internal (insn)
6651 && validate_change (insn, &SET_SRC (x),
6654 /* If this creates new pseudos, this is unsafe,
6655 because the regno of new pseudo is unsuitable
6656 to index into reg_qty when cse_insn processes
6657 the new insn. Therefore, if a new pseudo was
6658 created, discard this optimization. */
6659 int nregs = max_reg_num ();
6661 = gen_move_insn (src_elt->exp, SET_DEST (set));
6662 if (nregs != max_reg_num ())
6664 if (! validate_change (insn, &SET_SRC (x),
6669 emit_insn_after (move, p);
6676 /* Deal with the destination of X affecting the stack pointer. */
6677 addr_affects_sp_p (SET_DEST (x));
6679 /* See comment on similar code in cse_insn for explanation of these
6681 if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
6682 || GET_CODE (SET_DEST (x)) == MEM)
6683 invalidate (SET_DEST (x), VOIDmode);
6684 else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
6685 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
6686 invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
6689 /* Find the end of INSN's basic block and return its range,
6690 the total number of SETs in all the insns of the block, the last insn of the
6691 block, and the branch path.
6693 The branch path indicates which branches should be followed. If a nonzero
6694 path size is specified, the block should be rescanned and a different set
6695 of branches will be taken. The branch path is only used if
6696 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is nonzero.
6698 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6699 used to describe the block. It is filled in with the information about
6700 the current block. The incoming structure's branch path, if any, is used
6701 to construct the output branch path. */
6704 cse_end_of_basic_block (rtx insn, struct cse_basic_block_data *data,
6705 int follow_jumps, int after_loop, int skip_blocks)
6709 int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
6710 rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
6711 int path_size = data->path_size;
6715 /* Update the previous branch path, if any. If the last branch was
6716 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6717 shorten the path by one and look at the previous branch. We know that
6718 at least one branch must have been taken if PATH_SIZE is nonzero. */
6719 while (path_size > 0)
6721 if (data->path[path_size - 1].status != NOT_TAKEN)
6723 data->path[path_size - 1].status = NOT_TAKEN;
6730 /* If the first instruction is marked with QImode, that means we've
6731 already processed this block. Our caller will look at DATA->LAST
6732 to figure out where to go next. We want to return the next block
6733 in the instruction stream, not some branched-to block somewhere
6734 else. We accomplish this by pretending our called forbid us to
6735 follow jumps, or skip blocks. */
6736 if (GET_MODE (insn) == QImode)
6737 follow_jumps = skip_blocks = 0;
6739 /* Scan to end of this basic block. */
6740 while (p && GET_CODE (p) != CODE_LABEL)
6742 /* Don't cse out the end of a loop. This makes a difference
6743 only for the unusual loops that always execute at least once;
6744 all other loops have labels there so we will stop in any case.
6745 Cse'ing out the end of the loop is dangerous because it
6746 might cause an invariant expression inside the loop
6747 to be reused after the end of the loop. This would make it
6748 hard to move the expression out of the loop in loop.c,
6749 especially if it is one of several equivalent expressions
6750 and loop.c would like to eliminate it.
6752 If we are running after loop.c has finished, we can ignore
6753 the NOTE_INSN_LOOP_END. */
6755 if (! after_loop && GET_CODE (p) == NOTE
6756 && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
6759 /* Don't cse over a call to setjmp; on some machines (eg VAX)
6760 the regs restored by the longjmp come from
6761 a later time than the setjmp. */
6762 if (PREV_INSN (p) && GET_CODE (PREV_INSN (p)) == CALL_INSN
6763 && find_reg_note (PREV_INSN (p), REG_SETJMP, NULL))
6766 /* A PARALLEL can have lots of SETs in it,
6767 especially if it is really an ASM_OPERANDS. */
6768 if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
6769 nsets += XVECLEN (PATTERN (p), 0);
6770 else if (GET_CODE (p) != NOTE)
6773 /* Ignore insns made by CSE; they cannot affect the boundaries of
6776 if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
6777 high_cuid = INSN_CUID (p);
6778 if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
6779 low_cuid = INSN_CUID (p);
6781 /* See if this insn is in our branch path. If it is and we are to
6783 if (path_entry < path_size && data->path[path_entry].branch == p)
6785 if (data->path[path_entry].status != NOT_TAKEN)
6788 /* Point to next entry in path, if any. */
6792 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
6793 was specified, we haven't reached our maximum path length, there are
6794 insns following the target of the jump, this is the only use of the
6795 jump label, and the target label is preceded by a BARRIER.
6797 Alternatively, we can follow the jump if it branches around a
6798 block of code and there are no other branches into the block.
6799 In this case invalidate_skipped_block will be called to invalidate any
6800 registers set in the block when following the jump. */
6802 else if ((follow_jumps || skip_blocks) && path_size < PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH) - 1
6803 && GET_CODE (p) == JUMP_INSN
6804 && GET_CODE (PATTERN (p)) == SET
6805 && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
6806 && JUMP_LABEL (p) != 0
6807 && LABEL_NUSES (JUMP_LABEL (p)) == 1
6808 && NEXT_INSN (JUMP_LABEL (p)) != 0)
6810 for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
6811 if ((GET_CODE (q) != NOTE
6812 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
6813 || (PREV_INSN (q) && GET_CODE (PREV_INSN (q)) == CALL_INSN
6814 && find_reg_note (PREV_INSN (q), REG_SETJMP, NULL)))
6815 && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
6818 /* If we ran into a BARRIER, this code is an extension of the
6819 basic block when the branch is taken. */
6820 if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
6822 /* Don't allow ourself to keep walking around an
6823 always-executed loop. */
6824 if (next_real_insn (q) == next)
6830 /* Similarly, don't put a branch in our path more than once. */
6831 for (i = 0; i < path_entry; i++)
6832 if (data->path[i].branch == p)
6835 if (i != path_entry)
6838 data->path[path_entry].branch = p;
6839 data->path[path_entry++].status = TAKEN;
6841 /* This branch now ends our path. It was possible that we
6842 didn't see this branch the last time around (when the
6843 insn in front of the target was a JUMP_INSN that was
6844 turned into a no-op). */
6845 path_size = path_entry;
6848 /* Mark block so we won't scan it again later. */
6849 PUT_MODE (NEXT_INSN (p), QImode);
6851 /* Detect a branch around a block of code. */
6852 else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
6856 if (next_real_insn (q) == next)
6862 for (i = 0; i < path_entry; i++)
6863 if (data->path[i].branch == p)
6866 if (i != path_entry)
6869 /* This is no_labels_between_p (p, q) with an added check for
6870 reaching the end of a function (in case Q precedes P). */
6871 for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
6872 if (GET_CODE (tmp) == CODE_LABEL)
6877 data->path[path_entry].branch = p;
6878 data->path[path_entry++].status = AROUND;
6880 path_size = path_entry;
6883 /* Mark block so we won't scan it again later. */
6884 PUT_MODE (NEXT_INSN (p), QImode);
6891 data->low_cuid = low_cuid;
6892 data->high_cuid = high_cuid;
6893 data->nsets = nsets;
6896 /* If all jumps in the path are not taken, set our path length to zero
6897 so a rescan won't be done. */
6898 for (i = path_size - 1; i >= 0; i--)
6899 if (data->path[i].status != NOT_TAKEN)
6903 data->path_size = 0;
6905 data->path_size = path_size;
6907 /* End the current branch path. */
6908 data->path[path_size].branch = 0;
6911 /* Perform cse on the instructions of a function.
6912 F is the first instruction.
6913 NREGS is one plus the highest pseudo-reg number used in the instruction.
6915 AFTER_LOOP is 1 if this is the cse call done after loop optimization
6916 (only if -frerun-cse-after-loop).
6918 Returns 1 if jump_optimize should be redone due to simplifications
6919 in conditional jump instructions. */
6922 cse_main (rtx f, int nregs, int after_loop, FILE *file)
6924 struct cse_basic_block_data val;
6928 val.path = xmalloc (sizeof (struct branch_path)
6929 * PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
6931 cse_jumps_altered = 0;
6932 recorded_label_ref = 0;
6933 constant_pool_entries_cost = 0;
6937 init_alias_analysis ();
6941 max_insn_uid = get_max_uid ();
6943 reg_eqv_table = xmalloc (nregs * sizeof (struct reg_eqv_elem));
6945 #ifdef LOAD_EXTEND_OP
6947 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
6948 and change the code and mode as appropriate. */
6949 memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX);
6952 /* Reset the counter indicating how many elements have been made
6954 n_elements_made = 0;
6956 /* Find the largest uid. */
6958 max_uid = get_max_uid ();
6959 uid_cuid = xcalloc (max_uid + 1, sizeof (int));
6961 /* Compute the mapping from uids to cuids.
6962 CUIDs are numbers assigned to insns, like uids,
6963 except that cuids increase monotonically through the code.
6964 Don't assign cuids to line-number NOTEs, so that the distance in cuids
6965 between two insns is not affected by -g. */
6967 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
6969 if (GET_CODE (insn) != NOTE
6970 || NOTE_LINE_NUMBER (insn) < 0)
6971 INSN_CUID (insn) = ++i;
6973 /* Give a line number note the same cuid as preceding insn. */
6974 INSN_CUID (insn) = i;
6977 ggc_push_context ();
6979 /* Loop over basic blocks.
6980 Compute the maximum number of qty's needed for each basic block
6981 (which is 2 for each SET). */
6986 cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
6987 flag_cse_skip_blocks);
6989 /* If this basic block was already processed or has no sets, skip it. */
6990 if (val.nsets == 0 || GET_MODE (insn) == QImode)
6992 PUT_MODE (insn, VOIDmode);
6993 insn = (val.last ? NEXT_INSN (val.last) : 0);
6998 cse_basic_block_start = val.low_cuid;
6999 cse_basic_block_end = val.high_cuid;
7000 max_qty = val.nsets * 2;
7003 fnotice (file, ";; Processing block from %d to %d, %d sets.\n",
7004 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
7007 /* Make MAX_QTY bigger to give us room to optimize
7008 past the end of this basic block, if that should prove useful. */
7014 /* If this basic block is being extended by following certain jumps,
7015 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7016 Otherwise, we start after this basic block. */
7017 if (val.path_size > 0)
7018 cse_basic_block (insn, val.last, val.path, 0);
7021 int old_cse_jumps_altered = cse_jumps_altered;
7024 /* When cse changes a conditional jump to an unconditional
7025 jump, we want to reprocess the block, since it will give
7026 us a new branch path to investigate. */
7027 cse_jumps_altered = 0;
7028 temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
7029 if (cse_jumps_altered == 0
7030 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7033 cse_jumps_altered |= old_cse_jumps_altered;
7046 if (max_elements_made < n_elements_made)
7047 max_elements_made = n_elements_made;
7050 end_alias_analysis ();
7052 free (reg_eqv_table);
7055 return cse_jumps_altered || recorded_label_ref;
7058 /* Process a single basic block. FROM and TO and the limits of the basic
7059 block. NEXT_BRANCH points to the branch path when following jumps or
7060 a null path when not following jumps.
7062 AROUND_LOOP is nonzero if we are to try to cse around to the start of a
7063 loop. This is true when we are being called for the last time on a
7064 block and this CSE pass is before loop.c. */
7067 cse_basic_block (rtx from, rtx to, struct branch_path *next_branch,
7072 rtx libcall_insn = NULL_RTX;
7075 /* This array is undefined before max_reg, so only allocate
7076 the space actually needed and adjust the start. */
7078 qty_table = xmalloc ((max_qty - max_reg) * sizeof (struct qty_table_elem));
7079 qty_table -= max_reg;
7083 /* TO might be a label. If so, protect it from being deleted. */
7084 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7087 for (insn = from; insn != to; insn = NEXT_INSN (insn))
7089 enum rtx_code code = GET_CODE (insn);
7091 /* If we have processed 1,000 insns, flush the hash table to
7092 avoid extreme quadratic behavior. We must not include NOTEs
7093 in the count since there may be more of them when generating
7094 debugging information. If we clear the table at different
7095 times, code generated with -g -O might be different than code
7096 generated with -O but not -g.
7098 ??? This is a real kludge and needs to be done some other way.
7100 if (code != NOTE && num_insns++ > 1000)
7102 flush_hash_table ();
7106 /* See if this is a branch that is part of the path. If so, and it is
7107 to be taken, do so. */
7108 if (next_branch->branch == insn)
7110 enum taken status = next_branch++->status;
7111 if (status != NOT_TAKEN)
7113 if (status == TAKEN)
7114 record_jump_equiv (insn, 1);
7116 invalidate_skipped_block (NEXT_INSN (insn));
7118 /* Set the last insn as the jump insn; it doesn't affect cc0.
7119 Then follow this branch. */
7124 insn = JUMP_LABEL (insn);
7129 if (GET_MODE (insn) == QImode)
7130 PUT_MODE (insn, VOIDmode);
7132 if (GET_RTX_CLASS (code) == 'i')
7136 /* Process notes first so we have all notes in canonical forms when
7137 looking for duplicate operations. */
7139 if (REG_NOTES (insn))
7140 REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
7142 /* Track when we are inside in LIBCALL block. Inside such a block,
7143 we do not want to record destinations. The last insn of a
7144 LIBCALL block is not considered to be part of the block, since
7145 its destination is the result of the block and hence should be
7148 if (REG_NOTES (insn) != 0)
7150 if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
7151 libcall_insn = XEXP (p, 0);
7152 else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7156 cse_insn (insn, libcall_insn);
7158 /* If we haven't already found an insn where we added a LABEL_REF,
7160 if (GET_CODE (insn) == INSN && ! recorded_label_ref
7161 && for_each_rtx (&PATTERN (insn), check_for_label_ref,
7163 recorded_label_ref = 1;
7166 /* If INSN is now an unconditional jump, skip to the end of our
7167 basic block by pretending that we just did the last insn in the
7168 basic block. If we are jumping to the end of our block, show
7169 that we can have one usage of TO. */
7171 if (any_uncondjump_p (insn))
7175 free (qty_table + max_reg);
7179 if (JUMP_LABEL (insn) == to)
7182 /* Maybe TO was deleted because the jump is unconditional.
7183 If so, there is nothing left in this basic block. */
7184 /* ??? Perhaps it would be smarter to set TO
7185 to whatever follows this insn,
7186 and pretend the basic block had always ended here. */
7187 if (INSN_DELETED_P (to))
7190 insn = PREV_INSN (to);
7193 /* See if it is ok to keep on going past the label
7194 which used to end our basic block. Remember that we incremented
7195 the count of that label, so we decrement it here. If we made
7196 a jump unconditional, TO_USAGE will be one; in that case, we don't
7197 want to count the use in that jump. */
7199 if (to != 0 && NEXT_INSN (insn) == to
7200 && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
7202 struct cse_basic_block_data val;
7205 insn = NEXT_INSN (to);
7207 /* If TO was the last insn in the function, we are done. */
7210 free (qty_table + max_reg);
7214 /* If TO was preceded by a BARRIER we are done with this block
7215 because it has no continuation. */
7216 prev = prev_nonnote_insn (to);
7217 if (prev && GET_CODE (prev) == BARRIER)
7219 free (qty_table + max_reg);
7223 /* Find the end of the following block. Note that we won't be
7224 following branches in this case. */
7227 val.path = xmalloc (sizeof (struct branch_path)
7228 * PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
7229 cse_end_of_basic_block (insn, &val, 0, 0, 0);
7232 /* If the tables we allocated have enough space left
7233 to handle all the SETs in the next basic block,
7234 continue through it. Otherwise, return,
7235 and that block will be scanned individually. */
7236 if (val.nsets * 2 + next_qty > max_qty)
7239 cse_basic_block_start = val.low_cuid;
7240 cse_basic_block_end = val.high_cuid;
7243 /* Prevent TO from being deleted if it is a label. */
7244 if (to != 0 && GET_CODE (to) == CODE_LABEL)
7247 /* Back up so we process the first insn in the extension. */
7248 insn = PREV_INSN (insn);
7252 if (next_qty > max_qty)
7255 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7256 the previous insn is the only insn that branches to the head of a loop,
7257 we can cse into the loop. Don't do this if we changed the jump
7258 structure of a loop unless we aren't going to be following jumps. */
7260 insn = prev_nonnote_insn (to);
7261 if ((cse_jumps_altered == 0
7262 || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
7263 && around_loop && to != 0
7264 && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
7265 && GET_CODE (insn) == JUMP_INSN
7266 && JUMP_LABEL (insn) != 0
7267 && LABEL_NUSES (JUMP_LABEL (insn)) == 1)
7268 cse_around_loop (JUMP_LABEL (insn));
7270 free (qty_table + max_reg);
7272 return to ? NEXT_INSN (to) : 0;
7275 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
7276 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
7279 check_for_label_ref (rtx *rtl, void *data)
7281 rtx insn = (rtx) data;
7283 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
7284 we must rerun jump since it needs to place the note. If this is a
7285 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
7286 since no REG_LABEL will be added. */
7287 return (GET_CODE (*rtl) == LABEL_REF
7288 && ! LABEL_REF_NONLOCAL_P (*rtl)
7289 && LABEL_P (XEXP (*rtl, 0))
7290 && INSN_UID (XEXP (*rtl, 0)) != 0
7291 && ! find_reg_note (insn, REG_LABEL, XEXP (*rtl, 0)));
7294 /* Count the number of times registers are used (not set) in X.
7295 COUNTS is an array in which we accumulate the count, INCR is how much
7296 we count each register usage.
7298 Don't count a usage of DEST, which is the SET_DEST of a SET which
7299 contains X in its SET_SRC. This is because such a SET does not
7300 modify the liveness of DEST. */
7303 count_reg_usage (rtx x, int *counts, rtx dest, int incr)
7313 switch (code = GET_CODE (x))
7317 counts[REGNO (x)] += incr;
7331 /* If we are clobbering a MEM, mark any registers inside the address
7333 if (GET_CODE (XEXP (x, 0)) == MEM)
7334 count_reg_usage (XEXP (XEXP (x, 0), 0), counts, NULL_RTX, incr);
7338 /* Unless we are setting a REG, count everything in SET_DEST. */
7339 if (GET_CODE (SET_DEST (x)) != REG)
7340 count_reg_usage (SET_DEST (x), counts, NULL_RTX, incr);
7341 count_reg_usage (SET_SRC (x), counts,
7347 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x), counts, NULL_RTX, incr);
7352 count_reg_usage (PATTERN (x), counts, NULL_RTX, incr);
7354 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7357 note = find_reg_equal_equiv_note (x);
7360 rtx eqv = XEXP (note, 0);
7362 if (GET_CODE (eqv) == EXPR_LIST)
7363 /* This REG_EQUAL note describes the result of a function call.
7364 Process all the arguments. */
7367 count_reg_usage (XEXP (eqv, 0), counts, NULL_RTX, incr);
7368 eqv = XEXP (eqv, 1);
7370 while (eqv && GET_CODE (eqv) == EXPR_LIST);
7372 count_reg_usage (eqv, counts, NULL_RTX, incr);
7377 if (REG_NOTE_KIND (x) == REG_EQUAL
7378 || (REG_NOTE_KIND (x) != REG_NONNEG && GET_CODE (XEXP (x,0)) == USE)
7379 /* FUNCTION_USAGE expression lists may include (CLOBBER (mem /u)),
7380 involving registers in the address. */
7381 || GET_CODE (XEXP (x, 0)) == CLOBBER)
7382 count_reg_usage (XEXP (x, 0), counts, NULL_RTX, incr);
7384 count_reg_usage (XEXP (x, 1), counts, NULL_RTX, incr);
7388 /* If the asm is volatile, then this insn cannot be deleted,
7389 and so the inputs *must* be live. */
7390 if (MEM_VOLATILE_P (x))
7392 /* Iterate over just the inputs, not the constraints as well. */
7393 for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
7394 count_reg_usage (ASM_OPERANDS_INPUT (x, i), counts, dest, incr);
7404 fmt = GET_RTX_FORMAT (code);
7405 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
7408 count_reg_usage (XEXP (x, i), counts, dest, incr);
7409 else if (fmt[i] == 'E')
7410 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
7411 count_reg_usage (XVECEXP (x, i, j), counts, dest, incr);
7415 /* Return true if set is live. */
7417 set_live_p (rtx set, rtx insn ATTRIBUTE_UNUSED, /* Only used with HAVE_cc0. */
7424 if (set_noop_p (set))
7428 else if (GET_CODE (SET_DEST (set)) == CC0
7429 && !side_effects_p (SET_SRC (set))
7430 && ((tem = next_nonnote_insn (insn)) == 0
7432 || !reg_referenced_p (cc0_rtx, PATTERN (tem))))
7435 else if (GET_CODE (SET_DEST (set)) != REG
7436 || REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
7437 || counts[REGNO (SET_DEST (set))] != 0
7438 || side_effects_p (SET_SRC (set))
7439 /* An ADDRESSOF expression can turn into a use of the
7440 internal arg pointer, so always consider the
7441 internal arg pointer live. If it is truly dead,
7442 flow will delete the initializing insn. */
7443 || (SET_DEST (set) == current_function_internal_arg_pointer))
7448 /* Return true if insn is live. */
7451 insn_live_p (rtx insn, int *counts)
7454 if (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
7456 else if (GET_CODE (PATTERN (insn)) == SET)
7457 return set_live_p (PATTERN (insn), insn, counts);
7458 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
7460 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
7462 rtx elt = XVECEXP (PATTERN (insn), 0, i);
7464 if (GET_CODE (elt) == SET)
7466 if (set_live_p (elt, insn, counts))
7469 else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
7478 /* Return true if libcall is dead as a whole. */
7481 dead_libcall_p (rtx insn, int *counts)
7485 /* See if there's a REG_EQUAL note on this insn and try to
7486 replace the source with the REG_EQUAL expression.
7488 We assume that insns with REG_RETVALs can only be reg->reg
7489 copies at this point. */
7490 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
7494 set = single_set (insn);
7498 new = simplify_rtx (XEXP (note, 0));
7500 new = XEXP (note, 0);
7502 /* While changing insn, we must update the counts accordingly. */
7503 count_reg_usage (insn, counts, NULL_RTX, -1);
7505 if (validate_change (insn, &SET_SRC (set), new, 0))
7507 count_reg_usage (insn, counts, NULL_RTX, 1);
7508 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
7509 remove_note (insn, note);
7513 if (CONSTANT_P (new))
7515 new = force_const_mem (GET_MODE (SET_DEST (set)), new);
7516 if (new && validate_change (insn, &SET_SRC (set), new, 0))
7518 count_reg_usage (insn, counts, NULL_RTX, 1);
7519 remove_note (insn, find_reg_note (insn, REG_RETVAL, NULL_RTX));
7520 remove_note (insn, note);
7525 count_reg_usage (insn, counts, NULL_RTX, 1);
7529 /* Scan all the insns and delete any that are dead; i.e., they store a register
7530 that is never used or they copy a register to itself.
7532 This is used to remove insns made obviously dead by cse, loop or other
7533 optimizations. It improves the heuristics in loop since it won't try to
7534 move dead invariants out of loops or make givs for dead quantities. The
7535 remaining passes of the compilation are also sped up. */
7538 delete_trivially_dead_insns (rtx insns, int nreg)
7542 int in_libcall = 0, dead_libcall = 0;
7543 int ndead = 0, nlastdead, niterations = 0;
7545 timevar_push (TV_DELETE_TRIVIALLY_DEAD);
7546 /* First count the number of times each register is used. */
7547 counts = xcalloc (nreg, sizeof (int));
7548 for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
7549 count_reg_usage (insn, counts, NULL_RTX, 1);
7555 /* Go from the last insn to the first and delete insns that only set unused
7556 registers or copy a register to itself. As we delete an insn, remove
7557 usage counts for registers it uses.
7559 The first jump optimization pass may leave a real insn as the last
7560 insn in the function. We must not skip that insn or we may end
7561 up deleting code that is not really dead. */
7562 insn = get_last_insn ();
7563 if (! INSN_P (insn))
7564 insn = prev_real_insn (insn);
7566 for (; insn; insn = prev)
7570 prev = prev_real_insn (insn);
7572 /* Don't delete any insns that are part of a libcall block unless
7573 we can delete the whole libcall block.
7575 Flow or loop might get confused if we did that. Remember
7576 that we are scanning backwards. */
7577 if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
7581 dead_libcall = dead_libcall_p (insn, counts);
7583 else if (in_libcall)
7584 live_insn = ! dead_libcall;
7586 live_insn = insn_live_p (insn, counts);
7588 /* If this is a dead insn, delete it and show registers in it aren't
7593 count_reg_usage (insn, counts, NULL_RTX, -1);
7594 delete_insn_and_edges (insn);
7598 if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
7605 while (ndead != nlastdead);
7607 if (rtl_dump_file && ndead)
7608 fprintf (rtl_dump_file, "Deleted %i trivially dead insns; %i iterations\n",
7609 ndead, niterations);
7612 timevar_pop (TV_DELETE_TRIVIALLY_DEAD);