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"
46 /* The basic idea of common subexpression elimination is to go
47 through the code, keeping a record of expressions that would
48 have the same value at the current scan point, and replacing
49 expressions encountered with the cheapest equivalent expression.
51 It is too complicated to keep track of the different possibilities
52 when control paths merge in this code; so, at each label, we forget all
53 that is known and start fresh. This can be described as processing each
54 extended basic block separately. We have a separate pass to perform
57 Note CSE can turn a conditional or computed jump into a nop or
58 an unconditional jump. When this occurs we arrange to run the jump
59 optimizer after CSE to delete the unreachable code.
61 We use two data structures to record the equivalent expressions:
62 a hash table for most expressions, and a vector of "quantity
63 numbers" to record equivalent (pseudo) registers.
65 The use of the special data structure for registers is desirable
66 because it is faster. It is possible because registers references
67 contain a fairly small number, the register number, taken from
68 a contiguously allocated series, and two register references are
69 identical if they have the same number. General expressions
70 do not have any such thing, so the only way to retrieve the
71 information recorded on an expression other than a register
72 is to keep it in a hash table.
74 Registers and "quantity numbers":
76 At the start of each basic block, all of the (hardware and pseudo)
77 registers used in the function are given distinct quantity
78 numbers to indicate their contents. During scan, when the code
79 copies one register into another, we copy the quantity number.
80 When a register is loaded in any other way, we allocate a new
81 quantity number to describe the value generated by this operation.
82 `reg_qty' records what quantity a register is currently thought
85 All real quantity numbers are greater than or equal to `max_reg'.
86 If register N has not been assigned a quantity, reg_qty[N] will equal N.
88 Quantity numbers below `max_reg' do not exist and none of the `qty_table'
89 entries should be referenced with an index below `max_reg'.
91 We also maintain a bidirectional chain of registers for each
92 quantity number. The `qty_table` members `first_reg' and `last_reg',
93 and `reg_eqv_table' members `next' and `prev' hold these chains.
95 The first register in a chain is the one whose lifespan is least local.
96 Among equals, it is the one that was seen first.
97 We replace any equivalent register with that one.
99 If two registers have the same quantity number, it must be true that
100 REG expressions with qty_table `mode' must be in the hash table for both
101 registers and must be in the same class.
103 The converse is not true. Since hard registers may be referenced in
104 any mode, two REG expressions might be equivalent in the hash table
105 but not have the same quantity number if the quantity number of one
106 of the registers is not the same mode as those expressions.
108 Constants and quantity numbers
110 When a quantity has a known constant value, that value is stored
111 in the appropriate qty_table `const_rtx'. This is in addition to
112 putting the constant in the hash table as is usual for non-regs.
114 Whether a reg or a constant is preferred is determined by the configuration
115 macro CONST_COSTS and will often depend on the constant value. In any
116 event, expressions containing constants can be simplified, by fold_rtx.
118 When a quantity has a known nearly constant value (such as an address
119 of a stack slot), that value is stored in the appropriate qty_table
122 Integer constants don't have a machine mode. However, cse
123 determines the intended machine mode from the destination
124 of the instruction that moves the constant. The machine mode
125 is recorded in the hash table along with the actual RTL
126 constant expression so that different modes are kept separate.
130 To record known equivalences among expressions in general
131 we use a hash table called `table'. It has a fixed number of buckets
132 that contain chains of `struct table_elt' elements for expressions.
133 These chains connect the elements whose expressions have the same
136 Other chains through the same elements connect the elements which
137 currently have equivalent values.
139 Register references in an expression are canonicalized before hashing
140 the expression. This is done using `reg_qty' and qty_table `first_reg'.
141 The hash code of a register reference is computed using the quantity
142 number, not the register number.
144 When the value of an expression changes, it is necessary to remove from the
145 hash table not just that expression but all expressions whose values
146 could be different as a result.
148 1. If the value changing is in memory, except in special cases
149 ANYTHING referring to memory could be changed. That is because
150 nobody knows where a pointer does not point.
151 The function `invalidate_memory' removes what is necessary.
153 The special cases are when the address is constant or is
154 a constant plus a fixed register such as the frame pointer
155 or a static chain pointer. When such addresses are stored in,
156 we can tell exactly which other such addresses must be invalidated
157 due to overlap. `invalidate' does this.
158 All expressions that refer to non-constant
159 memory addresses are also invalidated. `invalidate_memory' does this.
161 2. If the value changing is a register, all expressions
162 containing references to that register, and only those,
165 Because searching the entire hash table for expressions that contain
166 a register is very slow, we try to figure out when it isn't necessary.
167 Precisely, this is necessary only when expressions have been
168 entered in the hash table using this register, and then the value has
169 changed, and then another expression wants to be added to refer to
170 the register's new value. This sequence of circumstances is rare
171 within any one basic block.
173 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
174 reg_tick[i] is incremented whenever a value is stored in register i.
175 reg_in_table[i] holds -1 if no references to register i have been
176 entered in the table; otherwise, it contains the value reg_tick[i] had
177 when the references were entered. If we want to enter a reference
178 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
179 Until we want to enter a new entry, the mere fact that the two vectors
180 don't match makes the entries be ignored if anyone tries to match them.
182 Registers themselves are entered in the hash table as well as in
183 the equivalent-register chains. However, the vectors `reg_tick'
184 and `reg_in_table' do not apply to expressions which are simple
185 register references. These expressions are removed from the table
186 immediately when they become invalid, and this can be done even if
187 we do not immediately search for all the expressions that refer to
190 A CLOBBER rtx in an instruction invalidates its operand for further
191 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
192 invalidates everything that resides in memory.
196 Constant expressions that differ only by an additive integer
197 are called related. When a constant expression is put in
198 the table, the related expression with no constant term
199 is also entered. These are made to point at each other
200 so that it is possible to find out if there exists any
201 register equivalent to an expression related to a given expression. */
203 /* One plus largest register number used in this function. */
207 /* One plus largest instruction UID used in this function at time of
210 static int max_insn_uid
;
212 /* Length of qty_table vector. We know in advance we will not need
213 a quantity number this big. */
217 /* Next quantity number to be allocated.
218 This is 1 + the largest number needed so far. */
222 /* Per-qty information tracking.
224 `first_reg' and `last_reg' track the head and tail of the
225 chain of registers which currently contain this quantity.
227 `mode' contains the machine mode of this quantity.
229 `const_rtx' holds the rtx of the constant value of this
230 quantity, if known. A summations of the frame/arg pointer
231 and a constant can also be entered here. When this holds
232 a known value, `const_insn' is the insn which stored the
235 `comparison_{code,const,qty}' are used to track when a
236 comparison between a quantity and some constant or register has
237 been passed. In such a case, we know the results of the comparison
238 in case we see it again. These members record a comparison that
239 is known to be true. `comparison_code' holds the rtx code of such
240 a comparison, else it is set to UNKNOWN and the other two
241 comparison members are undefined. `comparison_const' holds
242 the constant being compared against, or zero if the comparison
243 is not against a constant. `comparison_qty' holds the quantity
244 being compared against when the result is known. If the comparison
245 is not with a register, `comparison_qty' is -1. */
247 struct qty_table_elem
251 rtx comparison_const
;
253 unsigned int first_reg
, last_reg
;
254 enum machine_mode mode
;
255 enum rtx_code comparison_code
;
258 /* The table of all qtys, indexed by qty number. */
259 static struct qty_table_elem
*qty_table
;
262 /* For machines that have a CC0, we do not record its value in the hash
263 table since its use is guaranteed to be the insn immediately following
264 its definition and any other insn is presumed to invalidate it.
266 Instead, we store below the value last assigned to CC0. If it should
267 happen to be a constant, it is stored in preference to the actual
268 assigned value. In case it is a constant, we store the mode in which
269 the constant should be interpreted. */
271 static rtx prev_insn_cc0
;
272 static enum machine_mode prev_insn_cc0_mode
;
274 /* Previous actual insn. 0 if at first insn of basic block. */
276 static rtx prev_insn
;
279 /* Insn being scanned. */
281 static rtx this_insn
;
283 /* Index by register number, gives the number of the next (or
284 previous) register in the chain of registers sharing the same
287 Or -1 if this register is at the end of the chain.
289 If reg_qty[N] == N, reg_eqv_table[N].next is undefined. */
291 /* Per-register equivalence chain. */
297 /* The table of all register equivalence chains. */
298 static struct reg_eqv_elem
*reg_eqv_table
;
302 /* Next in hash chain. */
303 struct cse_reg_info
*hash_next
;
305 /* The next cse_reg_info structure in the free or used list. */
306 struct cse_reg_info
*next
;
311 /* The quantity number of the register's current contents. */
314 /* The number of times the register has been altered in the current
318 /* The REG_TICK value at which rtx's containing this register are
319 valid in the hash table. If this does not equal the current
320 reg_tick value, such expressions existing in the hash table are
324 /* The SUBREG that was set when REG_TICK was last incremented. Set
325 to -1 if the last store was to the whole register, not a subreg. */
326 unsigned int subreg_ticked
;
329 /* A free list of cse_reg_info entries. */
330 static struct cse_reg_info
*cse_reg_info_free_list
;
332 /* A used list of cse_reg_info entries. */
333 static struct cse_reg_info
*cse_reg_info_used_list
;
334 static struct cse_reg_info
*cse_reg_info_used_list_end
;
336 /* A mapping from registers to cse_reg_info data structures. */
337 #define REGHASH_SHIFT 7
338 #define REGHASH_SIZE (1 << REGHASH_SHIFT)
339 #define REGHASH_MASK (REGHASH_SIZE - 1)
340 static struct cse_reg_info
*reg_hash
[REGHASH_SIZE
];
342 #define REGHASH_FN(REGNO) \
343 (((REGNO) ^ ((REGNO) >> REGHASH_SHIFT)) & REGHASH_MASK)
345 /* The last lookup we did into the cse_reg_info_tree. This allows us
346 to cache repeated lookups. */
347 static unsigned int cached_regno
;
348 static struct cse_reg_info
*cached_cse_reg_info
;
350 /* A HARD_REG_SET containing all the hard registers for which there is
351 currently a REG expression in the hash table. Note the difference
352 from the above variables, which indicate if the REG is mentioned in some
353 expression in the table. */
355 static HARD_REG_SET hard_regs_in_table
;
357 /* CUID of insn that starts the basic block currently being cse-processed. */
359 static int cse_basic_block_start
;
361 /* CUID of insn that ends the basic block currently being cse-processed. */
363 static int cse_basic_block_end
;
365 /* Vector mapping INSN_UIDs to cuids.
366 The cuids are like uids but increase monotonically always.
367 We use them to see whether a reg is used outside a given basic block. */
369 static int *uid_cuid
;
371 /* Highest UID in UID_CUID. */
374 /* Get the cuid of an insn. */
376 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
378 /* Nonzero if this pass has made changes, and therefore it's
379 worthwhile to run the garbage collector. */
381 static int cse_altered
;
383 /* Nonzero if cse has altered conditional jump insns
384 in such a way that jump optimization should be redone. */
386 static int cse_jumps_altered
;
388 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
389 REG_LABEL, we have to rerun jump after CSE to put in the note. */
390 static int recorded_label_ref
;
392 /* canon_hash stores 1 in do_not_record
393 if it notices a reference to CC0, PC, or some other volatile
396 static int do_not_record
;
398 #ifdef LOAD_EXTEND_OP
400 /* Scratch rtl used when looking for load-extended copy of a MEM. */
401 static rtx memory_extend_rtx
;
404 /* canon_hash stores 1 in hash_arg_in_memory
405 if it notices a reference to memory within the expression being hashed. */
407 static int hash_arg_in_memory
;
409 /* The hash table contains buckets which are chains of `struct table_elt's,
410 each recording one expression's information.
411 That expression is in the `exp' field.
413 The canon_exp field contains a canonical (from the point of view of
414 alias analysis) version of the `exp' field.
416 Those elements with the same hash code are chained in both directions
417 through the `next_same_hash' and `prev_same_hash' fields.
419 Each set of expressions with equivalent values
420 are on a two-way chain through the `next_same_value'
421 and `prev_same_value' fields, and all point with
422 the `first_same_value' field at the first element in
423 that chain. The chain is in order of increasing cost.
424 Each element's cost value is in its `cost' field.
426 The `in_memory' field is nonzero for elements that
427 involve any reference to memory. These elements are removed
428 whenever a write is done to an unidentified location in memory.
429 To be safe, we assume that a memory address is unidentified unless
430 the address is either a symbol constant or a constant plus
431 the frame pointer or argument pointer.
433 The `related_value' field is used to connect related expressions
434 (that differ by adding an integer).
435 The related expressions are chained in a circular fashion.
436 `related_value' is zero for expressions for which this
439 The `cost' field stores the cost of this element's expression.
440 The `regcost' field stores the value returned by approx_reg_cost for
441 this element's expression.
443 The `is_const' flag is set if the element is a constant (including
446 The `flag' field is used as a temporary during some search routines.
448 The `mode' field is usually the same as GET_MODE (`exp'), but
449 if `exp' is a CONST_INT and has no machine mode then the `mode'
450 field is the mode it was being used as. Each constant is
451 recorded separately for each mode it is used with. */
457 struct table_elt
*next_same_hash
;
458 struct table_elt
*prev_same_hash
;
459 struct table_elt
*next_same_value
;
460 struct table_elt
*prev_same_value
;
461 struct table_elt
*first_same_value
;
462 struct table_elt
*related_value
;
465 enum machine_mode mode
;
471 /* We don't want a lot of buckets, because we rarely have very many
472 things stored in the hash table, and a lot of buckets slows
473 down a lot of loops that happen frequently. */
475 #define HASH_SIZE (1 << HASH_SHIFT)
476 #define HASH_MASK (HASH_SIZE - 1)
478 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
479 register (hard registers may require `do_not_record' to be set). */
482 ((GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
483 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
484 : canon_hash (X, M)) & HASH_MASK)
486 /* Determine whether register number N is considered a fixed register for the
487 purpose of approximating register costs.
488 It is desirable to replace other regs with fixed regs, to reduce need for
490 A reg wins if it is either the frame pointer or designated as fixed. */
491 #define FIXED_REGNO_P(N) \
492 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
493 || fixed_regs[N] || global_regs[N])
495 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
496 hard registers and pointers into the frame are the cheapest with a cost
497 of 0. Next come pseudos with a cost of one and other hard registers with
498 a cost of 2. Aside from these special cases, call `rtx_cost'. */
500 #define CHEAP_REGNO(N) \
501 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
502 || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM \
503 || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) \
504 || ((N) < FIRST_PSEUDO_REGISTER \
505 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
507 #define COST(X) (GET_CODE (X) == REG ? 0 : notreg_cost (X, SET))
508 #define COST_IN(X,OUTER) (GET_CODE (X) == REG ? 0 : notreg_cost (X, OUTER))
510 /* Get the info associated with register N. */
512 #define GET_CSE_REG_INFO(N) \
513 (((N) == cached_regno && cached_cse_reg_info) \
514 ? cached_cse_reg_info : get_cse_reg_info ((N)))
516 /* Get the number of times this register has been updated in this
519 #define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
521 /* Get the point at which REG was recorded in the table. */
523 #define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
525 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
528 #define SUBREG_TICKED(N) ((GET_CSE_REG_INFO (N))->subreg_ticked)
530 /* Get the quantity number for REG. */
532 #define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
534 /* Determine if the quantity number for register X represents a valid index
535 into the qty_table. */
537 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (int) (N))
539 static struct table_elt
*table
[HASH_SIZE
];
541 /* Chain of `struct table_elt's made so far for this function
542 but currently removed from the table. */
544 static struct table_elt
*free_element_chain
;
546 /* Number of `struct table_elt' structures made so far for this function. */
548 static int n_elements_made
;
550 /* Maximum value `n_elements_made' has had so far in this compilation
551 for functions previously processed. */
553 static int max_elements_made
;
555 /* Surviving equivalence class when two equivalence classes are merged
556 by recording the effects of a jump in the last insn. Zero if the
557 last insn was not a conditional jump. */
559 static struct table_elt
*last_jump_equiv_class
;
561 /* Set to the cost of a constant pool reference if one was found for a
562 symbolic constant. If this was found, it means we should try to
563 convert constants into constant pool entries if they don't fit in
566 static int constant_pool_entries_cost
;
568 /* Define maximum length of a branch path. */
570 #define PATHLENGTH 10
572 /* This data describes a block that will be processed by cse_basic_block. */
574 struct cse_basic_block_data
576 /* Lowest CUID value of insns in block. */
578 /* Highest CUID value of insns in block. */
580 /* Total number of SETs in block. */
582 /* Last insn in the block. */
584 /* Size of current branch path, if any. */
586 /* Current branch path, indicating which branches will be taken. */
589 /* The branch insn. */
591 /* Whether it should be taken or not. AROUND is the same as taken
592 except that it is used when the destination label is not preceded
594 enum taken
{TAKEN
, NOT_TAKEN
, AROUND
} status
;
598 static bool fixed_base_plus_p
PARAMS ((rtx x
));
599 static int notreg_cost
PARAMS ((rtx
, enum rtx_code
));
600 static int approx_reg_cost_1
PARAMS ((rtx
*, void *));
601 static int approx_reg_cost
PARAMS ((rtx
));
602 static int preferrable
PARAMS ((int, int, int, int));
603 static void new_basic_block
PARAMS ((void));
604 static void make_new_qty
PARAMS ((unsigned int, enum machine_mode
));
605 static void make_regs_eqv
PARAMS ((unsigned int, unsigned int));
606 static void delete_reg_equiv
PARAMS ((unsigned int));
607 static int mention_regs
PARAMS ((rtx
));
608 static int insert_regs
PARAMS ((rtx
, struct table_elt
*, int));
609 static void remove_from_table
PARAMS ((struct table_elt
*, unsigned));
610 static struct table_elt
*lookup
PARAMS ((rtx
, unsigned, enum machine_mode
)),
611 *lookup_for_remove
PARAMS ((rtx
, unsigned, enum machine_mode
));
612 static rtx lookup_as_function
PARAMS ((rtx
, enum rtx_code
));
613 static struct table_elt
*insert
PARAMS ((rtx
, struct table_elt
*, unsigned,
615 static void merge_equiv_classes
PARAMS ((struct table_elt
*,
616 struct table_elt
*));
617 static void invalidate
PARAMS ((rtx
, enum machine_mode
));
618 static int cse_rtx_varies_p
PARAMS ((rtx
, int));
619 static void remove_invalid_refs
PARAMS ((unsigned int));
620 static void remove_invalid_subreg_refs
PARAMS ((unsigned int, unsigned int,
622 static void rehash_using_reg
PARAMS ((rtx
));
623 static void invalidate_memory
PARAMS ((void));
624 static void invalidate_for_call
PARAMS ((void));
625 static rtx use_related_value
PARAMS ((rtx
, struct table_elt
*));
626 static unsigned canon_hash
PARAMS ((rtx
, enum machine_mode
));
627 static unsigned canon_hash_string
PARAMS ((const char *));
628 static unsigned safe_hash
PARAMS ((rtx
, enum machine_mode
));
629 static int exp_equiv_p
PARAMS ((rtx
, rtx
, int, int));
630 static rtx canon_reg
PARAMS ((rtx
, rtx
));
631 static void find_best_addr
PARAMS ((rtx
, rtx
*, enum machine_mode
));
632 static enum rtx_code find_comparison_args
PARAMS ((enum rtx_code
, rtx
*, rtx
*,
634 enum machine_mode
*));
635 static rtx fold_rtx
PARAMS ((rtx
, rtx
));
636 static rtx equiv_constant
PARAMS ((rtx
));
637 static void record_jump_equiv
PARAMS ((rtx
, int));
638 static void record_jump_cond
PARAMS ((enum rtx_code
, enum machine_mode
,
640 static void cse_insn
PARAMS ((rtx
, rtx
));
641 static int addr_affects_sp_p
PARAMS ((rtx
));
642 static void invalidate_from_clobbers
PARAMS ((rtx
));
643 static rtx cse_process_notes
PARAMS ((rtx
, rtx
));
644 static void cse_around_loop
PARAMS ((rtx
));
645 static void invalidate_skipped_set
PARAMS ((rtx
, rtx
, void *));
646 static void invalidate_skipped_block
PARAMS ((rtx
));
647 static void cse_check_loop_start
PARAMS ((rtx
, rtx
, void *));
648 static void cse_set_around_loop
PARAMS ((rtx
, rtx
, rtx
));
649 static rtx cse_basic_block
PARAMS ((rtx
, rtx
, struct branch_path
*, int));
650 static void count_reg_usage
PARAMS ((rtx
, int *, rtx
, int));
651 static int check_for_label_ref
PARAMS ((rtx
*, void *));
652 extern void dump_class
PARAMS ((struct table_elt
*));
653 static struct cse_reg_info
* get_cse_reg_info
PARAMS ((unsigned int));
654 static int check_dependence
PARAMS ((rtx
*, void *));
656 static void flush_hash_table
PARAMS ((void));
657 static bool insn_live_p
PARAMS ((rtx
, int *));
658 static bool set_live_p
PARAMS ((rtx
, rtx
, int *));
659 static bool dead_libcall_p
PARAMS ((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 (x
)
669 switch (GET_CODE (x
))
672 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
)
674 if (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
676 if (REGNO (x
) >= FIRST_VIRTUAL_REGISTER
677 && REGNO (x
) <= LAST_VIRTUAL_REGISTER
)
682 if (GET_CODE (XEXP (x
, 1)) != CONST_INT
)
684 return fixed_base_plus_p (XEXP (x
, 0));
694 /* Dump the expressions in the equivalence class indicated by CLASSP.
695 This function is used only for debugging. */
698 struct table_elt
*classp
;
700 struct table_elt
*elt
;
702 fprintf (stderr
, "Equivalence chain for ");
703 print_rtl (stderr
, classp
->exp
);
704 fprintf (stderr
, ": \n");
706 for (elt
= classp
->first_same_value
; elt
; elt
= elt
->next_same_value
)
708 print_rtl (stderr
, elt
->exp
);
709 fprintf (stderr
, "\n");
713 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
716 approx_reg_cost_1 (xp
, data
)
723 if (x
&& GET_CODE (x
) == REG
)
725 unsigned int regno
= REGNO (x
);
727 if (! CHEAP_REGNO (regno
))
729 if (regno
< FIRST_PSEUDO_REGISTER
)
731 if (SMALL_REGISTER_CLASSES
)
743 /* Return an estimate of the cost of the registers used in an rtx.
744 This is mostly the number of different REG expressions in the rtx;
745 however for some exceptions like fixed registers we use a cost of
746 0. If any other hard register reference occurs, return MAX_COST. */
754 if (for_each_rtx (&x
, approx_reg_cost_1
, (void *) &cost
))
760 /* Return a negative value if an rtx A, whose costs are given by COST_A
761 and REGCOST_A, is more desirable than an rtx B.
762 Return a positive value if A is less desirable, or 0 if the two are
765 preferrable (cost_a
, regcost_a
, cost_b
, regcost_b
)
766 int cost_a
, regcost_a
, cost_b
, regcost_b
;
768 /* First, get rid of cases involving expressions that are entirely
770 if (cost_a
!= cost_b
)
772 if (cost_a
== MAX_COST
)
774 if (cost_b
== MAX_COST
)
778 /* Avoid extending lifetimes of hardregs. */
779 if (regcost_a
!= regcost_b
)
781 if (regcost_a
== MAX_COST
)
783 if (regcost_b
== MAX_COST
)
787 /* Normal operation costs take precedence. */
788 if (cost_a
!= cost_b
)
789 return cost_a
- cost_b
;
790 /* Only if these are identical consider effects on register pressure. */
791 if (regcost_a
!= regcost_b
)
792 return regcost_a
- regcost_b
;
796 /* Internal function, to compute cost when X is not a register; called
797 from COST macro to keep it simple. */
800 notreg_cost (x
, outer
)
804 return ((GET_CODE (x
) == SUBREG
805 && GET_CODE (SUBREG_REG (x
)) == REG
806 && GET_MODE_CLASS (GET_MODE (x
)) == MODE_INT
807 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x
))) == MODE_INT
808 && (GET_MODE_SIZE (GET_MODE (x
))
809 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
810 && subreg_lowpart_p (x
)
811 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x
)),
812 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
)))))
814 : rtx_cost (x
, outer
) * 2);
817 /* Return an estimate of the cost of computing rtx X.
818 One use is in cse, to decide which expression to keep in the hash table.
819 Another is in rtl generation, to pick the cheapest way to multiply.
820 Other uses like the latter are expected in the future. */
823 rtx_cost (x
, outer_code
)
825 enum rtx_code outer_code ATTRIBUTE_UNUSED
;
835 /* Compute the default costs of certain things.
836 Note that targetm.rtx_costs can override the defaults. */
842 total
= COSTS_N_INSNS (5);
848 total
= COSTS_N_INSNS (7);
851 /* Used in loop.c and combine.c as a marker. */
855 total
= COSTS_N_INSNS (1);
864 /* If we can't tie these modes, make this expensive. The larger
865 the mode, the more expensive it is. */
866 if (! MODES_TIEABLE_P (GET_MODE (x
), GET_MODE (SUBREG_REG (x
))))
867 return COSTS_N_INSNS (2
868 + GET_MODE_SIZE (GET_MODE (x
)) / UNITS_PER_WORD
);
872 if ((*targetm
.rtx_costs
) (x
, code
, outer_code
, &total
))
877 /* Sum the costs of the sub-rtx's, plus cost of this operation,
878 which is already in total. */
880 fmt
= GET_RTX_FORMAT (code
);
881 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
883 total
+= rtx_cost (XEXP (x
, i
), code
);
884 else if (fmt
[i
] == 'E')
885 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
886 total
+= rtx_cost (XVECEXP (x
, i
, j
), code
);
891 /* Return cost of address expression X.
892 Expect that X is properly formed address reference. */
895 address_cost (x
, mode
)
897 enum machine_mode mode
;
899 /* The ADDRESS_COST macro does not deal with ADDRESSOF nodes. But,
900 during CSE, such nodes are present. Using an ADDRESSOF node which
901 refers to the address of a REG is a good thing because we can then
902 turn (MEM (ADDRESSSOF (REG))) into just plain REG. */
904 if (GET_CODE (x
) == ADDRESSOF
&& REG_P (XEXP ((x
), 0)))
907 /* We may be asked for cost of various unusual addresses, such as operands
908 of push instruction. It is not worthwhile to complicate writing
909 of ADDRESS_COST macro by such cases. */
911 if (!memory_address_p (mode
, x
))
914 return ADDRESS_COST (x
);
916 return rtx_cost (x
, MEM
);
921 static struct cse_reg_info
*
922 get_cse_reg_info (regno
)
925 struct cse_reg_info
**hash_head
= ®_hash
[REGHASH_FN (regno
)];
926 struct cse_reg_info
*p
;
928 for (p
= *hash_head
; p
!= NULL
; p
= p
->hash_next
)
929 if (p
->regno
== regno
)
934 /* Get a new cse_reg_info structure. */
935 if (cse_reg_info_free_list
)
937 p
= cse_reg_info_free_list
;
938 cse_reg_info_free_list
= p
->next
;
941 p
= (struct cse_reg_info
*) xmalloc (sizeof (struct cse_reg_info
));
943 /* Insert into hash table. */
944 p
->hash_next
= *hash_head
;
949 p
->reg_in_table
= -1;
950 p
->subreg_ticked
= -1;
953 p
->next
= cse_reg_info_used_list
;
954 cse_reg_info_used_list
= p
;
955 if (!cse_reg_info_used_list_end
)
956 cse_reg_info_used_list_end
= p
;
959 /* Cache this lookup; we tend to be looking up information about the
960 same register several times in a row. */
961 cached_regno
= regno
;
962 cached_cse_reg_info
= p
;
967 /* Clear the hash table and initialize each register with its own quantity,
968 for a new basic block. */
977 /* Clear out hash table state for this pass. */
979 memset ((char *) reg_hash
, 0, sizeof reg_hash
);
981 if (cse_reg_info_used_list
)
983 cse_reg_info_used_list_end
->next
= cse_reg_info_free_list
;
984 cse_reg_info_free_list
= cse_reg_info_used_list
;
985 cse_reg_info_used_list
= cse_reg_info_used_list_end
= 0;
987 cached_cse_reg_info
= 0;
989 CLEAR_HARD_REG_SET (hard_regs_in_table
);
991 /* The per-quantity values used to be initialized here, but it is
992 much faster to initialize each as it is made in `make_new_qty'. */
994 for (i
= 0; i
< HASH_SIZE
; i
++)
996 struct table_elt
*first
;
1001 struct table_elt
*last
= first
;
1005 while (last
->next_same_hash
!= NULL
)
1006 last
= last
->next_same_hash
;
1008 /* Now relink this hash entire chain into
1009 the free element list. */
1011 last
->next_same_hash
= free_element_chain
;
1012 free_element_chain
= first
;
1022 /* Say that register REG contains a quantity in mode MODE not in any
1023 register before and initialize that quantity. */
1026 make_new_qty (reg
, mode
)
1028 enum machine_mode mode
;
1031 struct qty_table_elem
*ent
;
1032 struct reg_eqv_elem
*eqv
;
1034 if (next_qty
>= max_qty
)
1037 q
= REG_QTY (reg
) = next_qty
++;
1038 ent
= &qty_table
[q
];
1039 ent
->first_reg
= reg
;
1040 ent
->last_reg
= reg
;
1042 ent
->const_rtx
= ent
->const_insn
= NULL_RTX
;
1043 ent
->comparison_code
= UNKNOWN
;
1045 eqv
= ®_eqv_table
[reg
];
1046 eqv
->next
= eqv
->prev
= -1;
1049 /* Make reg NEW equivalent to reg OLD.
1050 OLD is not changing; NEW is. */
1053 make_regs_eqv (new, old
)
1054 unsigned int new, old
;
1056 unsigned int lastr
, firstr
;
1057 int q
= REG_QTY (old
);
1058 struct qty_table_elem
*ent
;
1060 ent
= &qty_table
[q
];
1062 /* Nothing should become eqv until it has a "non-invalid" qty number. */
1063 if (! REGNO_QTY_VALID_P (old
))
1067 firstr
= ent
->first_reg
;
1068 lastr
= ent
->last_reg
;
1070 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
1071 hard regs. Among pseudos, if NEW will live longer than any other reg
1072 of the same qty, and that is beyond the current basic block,
1073 make it the new canonical replacement for this qty. */
1074 if (! (firstr
< FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (firstr
))
1075 /* Certain fixed registers might be of the class NO_REGS. This means
1076 that not only can they not be allocated by the compiler, but
1077 they cannot be used in substitutions or canonicalizations
1079 && (new >= FIRST_PSEUDO_REGISTER
|| REGNO_REG_CLASS (new) != NO_REGS
)
1080 && ((new < FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (new))
1081 || (new >= FIRST_PSEUDO_REGISTER
1082 && (firstr
< FIRST_PSEUDO_REGISTER
1083 || ((uid_cuid
[REGNO_LAST_UID (new)] > cse_basic_block_end
1084 || (uid_cuid
[REGNO_FIRST_UID (new)]
1085 < cse_basic_block_start
))
1086 && (uid_cuid
[REGNO_LAST_UID (new)]
1087 > uid_cuid
[REGNO_LAST_UID (firstr
)]))))))
1089 reg_eqv_table
[firstr
].prev
= new;
1090 reg_eqv_table
[new].next
= firstr
;
1091 reg_eqv_table
[new].prev
= -1;
1092 ent
->first_reg
= new;
1096 /* If NEW is a hard reg (known to be non-fixed), insert at end.
1097 Otherwise, insert before any non-fixed hard regs that are at the
1098 end. Registers of class NO_REGS cannot be used as an
1099 equivalent for anything. */
1100 while (lastr
< FIRST_PSEUDO_REGISTER
&& reg_eqv_table
[lastr
].prev
>= 0
1101 && (REGNO_REG_CLASS (lastr
) == NO_REGS
|| ! FIXED_REGNO_P (lastr
))
1102 && new >= FIRST_PSEUDO_REGISTER
)
1103 lastr
= reg_eqv_table
[lastr
].prev
;
1104 reg_eqv_table
[new].next
= reg_eqv_table
[lastr
].next
;
1105 if (reg_eqv_table
[lastr
].next
>= 0)
1106 reg_eqv_table
[reg_eqv_table
[lastr
].next
].prev
= new;
1108 qty_table
[q
].last_reg
= new;
1109 reg_eqv_table
[lastr
].next
= new;
1110 reg_eqv_table
[new].prev
= lastr
;
1114 /* Remove REG from its equivalence class. */
1117 delete_reg_equiv (reg
)
1120 struct qty_table_elem
*ent
;
1121 int q
= REG_QTY (reg
);
1124 /* If invalid, do nothing. */
1128 ent
= &qty_table
[q
];
1130 p
= reg_eqv_table
[reg
].prev
;
1131 n
= reg_eqv_table
[reg
].next
;
1134 reg_eqv_table
[n
].prev
= p
;
1138 reg_eqv_table
[p
].next
= n
;
1142 REG_QTY (reg
) = reg
;
1145 /* Remove any invalid expressions from the hash table
1146 that refer to any of the registers contained in expression X.
1148 Make sure that newly inserted references to those registers
1149 as subexpressions will be considered valid.
1151 mention_regs is not called when a register itself
1152 is being stored in the table.
1154 Return 1 if we have done something that may have changed the hash code
1169 code
= GET_CODE (x
);
1172 unsigned int regno
= REGNO (x
);
1173 unsigned int endregno
1174 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
1175 : HARD_REGNO_NREGS (regno
, GET_MODE (x
)));
1178 for (i
= regno
; i
< endregno
; i
++)
1180 if (REG_IN_TABLE (i
) >= 0 && REG_IN_TABLE (i
) != REG_TICK (i
))
1181 remove_invalid_refs (i
);
1183 REG_IN_TABLE (i
) = REG_TICK (i
);
1184 SUBREG_TICKED (i
) = -1;
1190 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1191 pseudo if they don't use overlapping words. We handle only pseudos
1192 here for simplicity. */
1193 if (code
== SUBREG
&& GET_CODE (SUBREG_REG (x
)) == REG
1194 && REGNO (SUBREG_REG (x
)) >= FIRST_PSEUDO_REGISTER
)
1196 unsigned int i
= REGNO (SUBREG_REG (x
));
1198 if (REG_IN_TABLE (i
) >= 0 && REG_IN_TABLE (i
) != REG_TICK (i
))
1200 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1201 the last store to this register really stored into this
1202 subreg, then remove the memory of this subreg.
1203 Otherwise, remove any memory of the entire register and
1204 all its subregs from the table. */
1205 if (REG_TICK (i
) - REG_IN_TABLE (i
) > 1
1206 || SUBREG_TICKED (i
) != REGNO (SUBREG_REG (x
)))
1207 remove_invalid_refs (i
);
1209 remove_invalid_subreg_refs (i
, SUBREG_BYTE (x
), GET_MODE (x
));
1212 REG_IN_TABLE (i
) = REG_TICK (i
);
1213 SUBREG_TICKED (i
) = REGNO (SUBREG_REG (x
));
1217 /* If X is a comparison or a COMPARE and either operand is a register
1218 that does not have a quantity, give it one. This is so that a later
1219 call to record_jump_equiv won't cause X to be assigned a different
1220 hash code and not found in the table after that call.
1222 It is not necessary to do this here, since rehash_using_reg can
1223 fix up the table later, but doing this here eliminates the need to
1224 call that expensive function in the most common case where the only
1225 use of the register is in the comparison. */
1227 if (code
== COMPARE
|| GET_RTX_CLASS (code
) == '<')
1229 if (GET_CODE (XEXP (x
, 0)) == REG
1230 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0))))
1231 if (insert_regs (XEXP (x
, 0), NULL
, 0))
1233 rehash_using_reg (XEXP (x
, 0));
1237 if (GET_CODE (XEXP (x
, 1)) == REG
1238 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 1))))
1239 if (insert_regs (XEXP (x
, 1), NULL
, 0))
1241 rehash_using_reg (XEXP (x
, 1));
1246 fmt
= GET_RTX_FORMAT (code
);
1247 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1249 changed
|= mention_regs (XEXP (x
, i
));
1250 else if (fmt
[i
] == 'E')
1251 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1252 changed
|= mention_regs (XVECEXP (x
, i
, j
));
1257 /* Update the register quantities for inserting X into the hash table
1258 with a value equivalent to CLASSP.
1259 (If the class does not contain a REG, it is irrelevant.)
1260 If MODIFIED is nonzero, X is a destination; it is being modified.
1261 Note that delete_reg_equiv should be called on a register
1262 before insert_regs is done on that register with MODIFIED != 0.
1264 Nonzero value means that elements of reg_qty have changed
1265 so X's hash code may be different. */
1268 insert_regs (x
, classp
, modified
)
1270 struct table_elt
*classp
;
1273 if (GET_CODE (x
) == REG
)
1275 unsigned int regno
= REGNO (x
);
1278 /* If REGNO is in the equivalence table already but is of the
1279 wrong mode for that equivalence, don't do anything here. */
1281 qty_valid
= REGNO_QTY_VALID_P (regno
);
1284 struct qty_table_elem
*ent
= &qty_table
[REG_QTY (regno
)];
1286 if (ent
->mode
!= GET_MODE (x
))
1290 if (modified
|| ! qty_valid
)
1293 for (classp
= classp
->first_same_value
;
1295 classp
= classp
->next_same_value
)
1296 if (GET_CODE (classp
->exp
) == REG
1297 && GET_MODE (classp
->exp
) == GET_MODE (x
))
1299 make_regs_eqv (regno
, REGNO (classp
->exp
));
1303 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1304 than REG_IN_TABLE to find out if there was only a single preceding
1305 invalidation - for the SUBREG - or another one, which would be
1306 for the full register. However, if we find here that REG_TICK
1307 indicates that the register is invalid, it means that it has
1308 been invalidated in a separate operation. The SUBREG might be used
1309 now (then this is a recursive call), or we might use the full REG
1310 now and a SUBREG of it later. So bump up REG_TICK so that
1311 mention_regs will do the right thing. */
1313 && REG_IN_TABLE (regno
) >= 0
1314 && REG_TICK (regno
) == REG_IN_TABLE (regno
) + 1)
1316 make_new_qty (regno
, GET_MODE (x
));
1323 /* If X is a SUBREG, we will likely be inserting the inner register in the
1324 table. If that register doesn't have an assigned quantity number at
1325 this point but does later, the insertion that we will be doing now will
1326 not be accessible because its hash code will have changed. So assign
1327 a quantity number now. */
1329 else if (GET_CODE (x
) == SUBREG
&& GET_CODE (SUBREG_REG (x
)) == REG
1330 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x
))))
1332 insert_regs (SUBREG_REG (x
), NULL
, 0);
1337 return mention_regs (x
);
1340 /* Look in or update the hash table. */
1342 /* Remove table element ELT from use in the table.
1343 HASH is its hash code, made using the HASH macro.
1344 It's an argument because often that is known in advance
1345 and we save much time not recomputing it. */
1348 remove_from_table (elt
, hash
)
1349 struct table_elt
*elt
;
1355 /* Mark this element as removed. See cse_insn. */
1356 elt
->first_same_value
= 0;
1358 /* Remove the table element from its equivalence class. */
1361 struct table_elt
*prev
= elt
->prev_same_value
;
1362 struct table_elt
*next
= elt
->next_same_value
;
1365 next
->prev_same_value
= prev
;
1368 prev
->next_same_value
= next
;
1371 struct table_elt
*newfirst
= next
;
1374 next
->first_same_value
= newfirst
;
1375 next
= next
->next_same_value
;
1380 /* Remove the table element from its hash bucket. */
1383 struct table_elt
*prev
= elt
->prev_same_hash
;
1384 struct table_elt
*next
= elt
->next_same_hash
;
1387 next
->prev_same_hash
= prev
;
1390 prev
->next_same_hash
= next
;
1391 else if (table
[hash
] == elt
)
1395 /* This entry is not in the proper hash bucket. This can happen
1396 when two classes were merged by `merge_equiv_classes'. Search
1397 for the hash bucket that it heads. This happens only very
1398 rarely, so the cost is acceptable. */
1399 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
1400 if (table
[hash
] == elt
)
1405 /* Remove the table element from its related-value circular chain. */
1407 if (elt
->related_value
!= 0 && elt
->related_value
!= elt
)
1409 struct table_elt
*p
= elt
->related_value
;
1411 while (p
->related_value
!= elt
)
1412 p
= p
->related_value
;
1413 p
->related_value
= elt
->related_value
;
1414 if (p
->related_value
== p
)
1415 p
->related_value
= 0;
1418 /* Now add it to the free element chain. */
1419 elt
->next_same_hash
= free_element_chain
;
1420 free_element_chain
= elt
;
1423 /* Look up X in the hash table and return its table element,
1424 or 0 if X is not in the table.
1426 MODE is the machine-mode of X, or if X is an integer constant
1427 with VOIDmode then MODE is the mode with which X will be used.
1429 Here we are satisfied to find an expression whose tree structure
1432 static struct table_elt
*
1433 lookup (x
, hash
, mode
)
1436 enum machine_mode mode
;
1438 struct table_elt
*p
;
1440 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1441 if (mode
== p
->mode
&& ((x
== p
->exp
&& GET_CODE (x
) == REG
)
1442 || exp_equiv_p (x
, p
->exp
, GET_CODE (x
) != REG
, 0)))
1448 /* Like `lookup' but don't care whether the table element uses invalid regs.
1449 Also ignore discrepancies in the machine mode of a register. */
1451 static struct table_elt
*
1452 lookup_for_remove (x
, hash
, mode
)
1455 enum machine_mode mode
;
1457 struct table_elt
*p
;
1459 if (GET_CODE (x
) == REG
)
1461 unsigned int regno
= REGNO (x
);
1463 /* Don't check the machine mode when comparing registers;
1464 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1465 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1466 if (GET_CODE (p
->exp
) == REG
1467 && REGNO (p
->exp
) == regno
)
1472 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1473 if (mode
== p
->mode
&& (x
== p
->exp
|| exp_equiv_p (x
, p
->exp
, 0, 0)))
1480 /* Look for an expression equivalent to X and with code CODE.
1481 If one is found, return that expression. */
1484 lookup_as_function (x
, code
)
1489 = lookup (x
, safe_hash (x
, VOIDmode
) & HASH_MASK
, GET_MODE (x
));
1491 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1492 long as we are narrowing. So if we looked in vain for a mode narrower
1493 than word_mode before, look for word_mode now. */
1494 if (p
== 0 && code
== CONST_INT
1495 && GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (word_mode
))
1498 PUT_MODE (x
, word_mode
);
1499 p
= lookup (x
, safe_hash (x
, VOIDmode
) & HASH_MASK
, word_mode
);
1505 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
1506 if (GET_CODE (p
->exp
) == code
1507 /* Make sure this is a valid entry in the table. */
1508 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
1514 /* Insert X in the hash table, assuming HASH is its hash code
1515 and CLASSP is an element of the class it should go in
1516 (or 0 if a new class should be made).
1517 It is inserted at the proper position to keep the class in
1518 the order cheapest first.
1520 MODE is the machine-mode of X, or if X is an integer constant
1521 with VOIDmode then MODE is the mode with which X will be used.
1523 For elements of equal cheapness, the most recent one
1524 goes in front, except that the first element in the list
1525 remains first unless a cheaper element is added. The order of
1526 pseudo-registers does not matter, as canon_reg will be called to
1527 find the cheapest when a register is retrieved from the table.
1529 The in_memory field in the hash table element is set to 0.
1530 The caller must set it nonzero if appropriate.
1532 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1533 and if insert_regs returns a nonzero value
1534 you must then recompute its hash code before calling here.
1536 If necessary, update table showing constant values of quantities. */
1538 #define CHEAPER(X, Y) \
1539 (preferrable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1541 static struct table_elt
*
1542 insert (x
, classp
, hash
, mode
)
1544 struct table_elt
*classp
;
1546 enum machine_mode mode
;
1548 struct table_elt
*elt
;
1550 /* If X is a register and we haven't made a quantity for it,
1551 something is wrong. */
1552 if (GET_CODE (x
) == REG
&& ! REGNO_QTY_VALID_P (REGNO (x
)))
1555 /* If X is a hard register, show it is being put in the table. */
1556 if (GET_CODE (x
) == REG
&& REGNO (x
) < FIRST_PSEUDO_REGISTER
)
1558 unsigned int regno
= REGNO (x
);
1559 unsigned int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1562 for (i
= regno
; i
< endregno
; i
++)
1563 SET_HARD_REG_BIT (hard_regs_in_table
, i
);
1566 /* Put an element for X into the right hash bucket. */
1568 elt
= free_element_chain
;
1570 free_element_chain
= elt
->next_same_hash
;
1574 elt
= (struct table_elt
*) xmalloc (sizeof (struct table_elt
));
1578 elt
->canon_exp
= NULL_RTX
;
1579 elt
->cost
= COST (x
);
1580 elt
->regcost
= approx_reg_cost (x
);
1581 elt
->next_same_value
= 0;
1582 elt
->prev_same_value
= 0;
1583 elt
->next_same_hash
= table
[hash
];
1584 elt
->prev_same_hash
= 0;
1585 elt
->related_value
= 0;
1588 elt
->is_const
= (CONSTANT_P (x
)
1589 /* GNU C++ takes advantage of this for `this'
1590 (and other const values). */
1591 || (GET_CODE (x
) == REG
1592 && RTX_UNCHANGING_P (x
)
1593 && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1594 || fixed_base_plus_p (x
));
1597 table
[hash
]->prev_same_hash
= elt
;
1600 /* Put it into the proper value-class. */
1603 classp
= classp
->first_same_value
;
1604 if (CHEAPER (elt
, classp
))
1605 /* Insert at the head of the class */
1607 struct table_elt
*p
;
1608 elt
->next_same_value
= classp
;
1609 classp
->prev_same_value
= elt
;
1610 elt
->first_same_value
= elt
;
1612 for (p
= classp
; p
; p
= p
->next_same_value
)
1613 p
->first_same_value
= elt
;
1617 /* Insert not at head of the class. */
1618 /* Put it after the last element cheaper than X. */
1619 struct table_elt
*p
, *next
;
1621 for (p
= classp
; (next
= p
->next_same_value
) && CHEAPER (next
, elt
);
1624 /* Put it after P and before NEXT. */
1625 elt
->next_same_value
= next
;
1627 next
->prev_same_value
= elt
;
1629 elt
->prev_same_value
= p
;
1630 p
->next_same_value
= elt
;
1631 elt
->first_same_value
= classp
;
1635 elt
->first_same_value
= elt
;
1637 /* If this is a constant being set equivalent to a register or a register
1638 being set equivalent to a constant, note the constant equivalence.
1640 If this is a constant, it cannot be equivalent to a different constant,
1641 and a constant is the only thing that can be cheaper than a register. So
1642 we know the register is the head of the class (before the constant was
1645 If this is a register that is not already known equivalent to a
1646 constant, we must check the entire class.
1648 If this is a register that is already known equivalent to an insn,
1649 update the qtys `const_insn' to show that `this_insn' is the latest
1650 insn making that quantity equivalent to the constant. */
1652 if (elt
->is_const
&& classp
&& GET_CODE (classp
->exp
) == REG
1653 && GET_CODE (x
) != REG
)
1655 int exp_q
= REG_QTY (REGNO (classp
->exp
));
1656 struct qty_table_elem
*exp_ent
= &qty_table
[exp_q
];
1658 exp_ent
->const_rtx
= gen_lowpart_if_possible (exp_ent
->mode
, x
);
1659 exp_ent
->const_insn
= this_insn
;
1662 else if (GET_CODE (x
) == REG
1664 && ! qty_table
[REG_QTY (REGNO (x
))].const_rtx
1667 struct table_elt
*p
;
1669 for (p
= classp
; p
!= 0; p
= p
->next_same_value
)
1671 if (p
->is_const
&& GET_CODE (p
->exp
) != REG
)
1673 int x_q
= REG_QTY (REGNO (x
));
1674 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
1677 = gen_lowpart_if_possible (GET_MODE (x
), p
->exp
);
1678 x_ent
->const_insn
= this_insn
;
1684 else if (GET_CODE (x
) == REG
1685 && qty_table
[REG_QTY (REGNO (x
))].const_rtx
1686 && GET_MODE (x
) == qty_table
[REG_QTY (REGNO (x
))].mode
)
1687 qty_table
[REG_QTY (REGNO (x
))].const_insn
= this_insn
;
1689 /* If this is a constant with symbolic value,
1690 and it has a term with an explicit integer value,
1691 link it up with related expressions. */
1692 if (GET_CODE (x
) == CONST
)
1694 rtx subexp
= get_related_value (x
);
1696 struct table_elt
*subelt
, *subelt_prev
;
1700 /* Get the integer-free subexpression in the hash table. */
1701 subhash
= safe_hash (subexp
, mode
) & HASH_MASK
;
1702 subelt
= lookup (subexp
, subhash
, mode
);
1704 subelt
= insert (subexp
, NULL
, subhash
, mode
);
1705 /* Initialize SUBELT's circular chain if it has none. */
1706 if (subelt
->related_value
== 0)
1707 subelt
->related_value
= subelt
;
1708 /* Find the element in the circular chain that precedes SUBELT. */
1709 subelt_prev
= subelt
;
1710 while (subelt_prev
->related_value
!= subelt
)
1711 subelt_prev
= subelt_prev
->related_value
;
1712 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1713 This way the element that follows SUBELT is the oldest one. */
1714 elt
->related_value
= subelt_prev
->related_value
;
1715 subelt_prev
->related_value
= elt
;
1722 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1723 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1724 the two classes equivalent.
1726 CLASS1 will be the surviving class; CLASS2 should not be used after this
1729 Any invalid entries in CLASS2 will not be copied. */
1732 merge_equiv_classes (class1
, class2
)
1733 struct table_elt
*class1
, *class2
;
1735 struct table_elt
*elt
, *next
, *new;
1737 /* Ensure we start with the head of the classes. */
1738 class1
= class1
->first_same_value
;
1739 class2
= class2
->first_same_value
;
1741 /* If they were already equal, forget it. */
1742 if (class1
== class2
)
1745 for (elt
= class2
; elt
; elt
= next
)
1749 enum machine_mode mode
= elt
->mode
;
1751 next
= elt
->next_same_value
;
1753 /* Remove old entry, make a new one in CLASS1's class.
1754 Don't do this for invalid entries as we cannot find their
1755 hash code (it also isn't necessary). */
1756 if (GET_CODE (exp
) == REG
|| exp_equiv_p (exp
, exp
, 1, 0))
1758 hash_arg_in_memory
= 0;
1759 hash
= HASH (exp
, mode
);
1761 if (GET_CODE (exp
) == REG
)
1762 delete_reg_equiv (REGNO (exp
));
1764 remove_from_table (elt
, hash
);
1766 if (insert_regs (exp
, class1
, 0))
1768 rehash_using_reg (exp
);
1769 hash
= HASH (exp
, mode
);
1771 new = insert (exp
, class1
, hash
, mode
);
1772 new->in_memory
= hash_arg_in_memory
;
1777 /* Flush the entire hash table. */
1783 struct table_elt
*p
;
1785 for (i
= 0; i
< HASH_SIZE
; i
++)
1786 for (p
= table
[i
]; p
; p
= table
[i
])
1788 /* Note that invalidate can remove elements
1789 after P in the current hash chain. */
1790 if (GET_CODE (p
->exp
) == REG
)
1791 invalidate (p
->exp
, p
->mode
);
1793 remove_from_table (p
, i
);
1797 /* Function called for each rtx to check whether true dependence exist. */
1798 struct check_dependence_data
1800 enum machine_mode mode
;
1805 check_dependence (x
, data
)
1809 struct check_dependence_data
*d
= (struct check_dependence_data
*) data
;
1810 if (*x
&& GET_CODE (*x
) == MEM
)
1811 return true_dependence (d
->exp
, d
->mode
, *x
, cse_rtx_varies_p
);
1816 /* Remove from the hash table, or mark as invalid, all expressions whose
1817 values could be altered by storing in X. X is a register, a subreg, or
1818 a memory reference with nonvarying address (because, when a memory
1819 reference with a varying address is stored in, all memory references are
1820 removed by invalidate_memory so specific invalidation is superfluous).
1821 FULL_MODE, if not VOIDmode, indicates that this much should be
1822 invalidated instead of just the amount indicated by the mode of X. This
1823 is only used for bitfield stores into memory.
1825 A nonvarying address may be just a register or just a symbol reference,
1826 or it may be either of those plus a numeric offset. */
1829 invalidate (x
, full_mode
)
1831 enum machine_mode full_mode
;
1834 struct table_elt
*p
;
1836 switch (GET_CODE (x
))
1840 /* If X is a register, dependencies on its contents are recorded
1841 through the qty number mechanism. Just change the qty number of
1842 the register, mark it as invalid for expressions that refer to it,
1843 and remove it itself. */
1844 unsigned int regno
= REGNO (x
);
1845 unsigned int hash
= HASH (x
, GET_MODE (x
));
1847 /* Remove REGNO from any quantity list it might be on and indicate
1848 that its value might have changed. If it is a pseudo, remove its
1849 entry from the hash table.
1851 For a hard register, we do the first two actions above for any
1852 additional hard registers corresponding to X. Then, if any of these
1853 registers are in the table, we must remove any REG entries that
1854 overlap these registers. */
1856 delete_reg_equiv (regno
);
1858 SUBREG_TICKED (regno
) = -1;
1860 if (regno
>= FIRST_PSEUDO_REGISTER
)
1862 /* Because a register can be referenced in more than one mode,
1863 we might have to remove more than one table entry. */
1864 struct table_elt
*elt
;
1866 while ((elt
= lookup_for_remove (x
, hash
, GET_MODE (x
))))
1867 remove_from_table (elt
, hash
);
1871 HOST_WIDE_INT in_table
1872 = TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1873 unsigned int endregno
1874 = regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1875 unsigned int tregno
, tendregno
, rn
;
1876 struct table_elt
*p
, *next
;
1878 CLEAR_HARD_REG_BIT (hard_regs_in_table
, regno
);
1880 for (rn
= regno
+ 1; rn
< endregno
; rn
++)
1882 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, rn
);
1883 CLEAR_HARD_REG_BIT (hard_regs_in_table
, rn
);
1884 delete_reg_equiv (rn
);
1886 SUBREG_TICKED (rn
) = -1;
1890 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
1891 for (p
= table
[hash
]; p
; p
= next
)
1893 next
= p
->next_same_hash
;
1895 if (GET_CODE (p
->exp
) != REG
1896 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1899 tregno
= REGNO (p
->exp
);
1901 = tregno
+ HARD_REGNO_NREGS (tregno
, GET_MODE (p
->exp
));
1902 if (tendregno
> regno
&& tregno
< endregno
)
1903 remove_from_table (p
, hash
);
1910 invalidate (SUBREG_REG (x
), VOIDmode
);
1914 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; --i
)
1915 invalidate (XVECEXP (x
, 0, i
), VOIDmode
);
1919 /* This is part of a disjoint return value; extract the location in
1920 question ignoring the offset. */
1921 invalidate (XEXP (x
, 0), VOIDmode
);
1925 /* Calculate the canonical version of X here so that
1926 true_dependence doesn't generate new RTL for X on each call. */
1929 /* Remove all hash table elements that refer to overlapping pieces of
1931 if (full_mode
== VOIDmode
)
1932 full_mode
= GET_MODE (x
);
1934 for (i
= 0; i
< HASH_SIZE
; i
++)
1936 struct table_elt
*next
;
1938 for (p
= table
[i
]; p
; p
= next
)
1940 next
= p
->next_same_hash
;
1943 struct check_dependence_data d
;
1945 /* Just canonicalize the expression once;
1946 otherwise each time we call invalidate
1947 true_dependence will canonicalize the
1948 expression again. */
1950 p
->canon_exp
= canon_rtx (p
->exp
);
1953 if (for_each_rtx (&p
->canon_exp
, check_dependence
, &d
))
1954 remove_from_table (p
, i
);
1965 /* Remove all expressions that refer to register REGNO,
1966 since they are already invalid, and we are about to
1967 mark that register valid again and don't want the old
1968 expressions to reappear as valid. */
1971 remove_invalid_refs (regno
)
1975 struct table_elt
*p
, *next
;
1977 for (i
= 0; i
< HASH_SIZE
; i
++)
1978 for (p
= table
[i
]; p
; p
= next
)
1980 next
= p
->next_same_hash
;
1981 if (GET_CODE (p
->exp
) != REG
1982 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, (rtx
*) 0))
1983 remove_from_table (p
, i
);
1987 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1990 remove_invalid_subreg_refs (regno
, offset
, mode
)
1992 unsigned int offset
;
1993 enum machine_mode mode
;
1996 struct table_elt
*p
, *next
;
1997 unsigned int end
= offset
+ (GET_MODE_SIZE (mode
) - 1);
1999 for (i
= 0; i
< HASH_SIZE
; i
++)
2000 for (p
= table
[i
]; p
; p
= next
)
2003 next
= p
->next_same_hash
;
2005 if (GET_CODE (exp
) != REG
2006 && (GET_CODE (exp
) != SUBREG
2007 || GET_CODE (SUBREG_REG (exp
)) != REG
2008 || REGNO (SUBREG_REG (exp
)) != regno
2009 || (((SUBREG_BYTE (exp
)
2010 + (GET_MODE_SIZE (GET_MODE (exp
)) - 1)) >= offset
)
2011 && SUBREG_BYTE (exp
) <= end
))
2012 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, (rtx
*) 0))
2013 remove_from_table (p
, i
);
2017 /* Recompute the hash codes of any valid entries in the hash table that
2018 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
2020 This is called when we make a jump equivalence. */
2023 rehash_using_reg (x
)
2027 struct table_elt
*p
, *next
;
2030 if (GET_CODE (x
) == SUBREG
)
2033 /* If X is not a register or if the register is known not to be in any
2034 valid entries in the table, we have no work to do. */
2036 if (GET_CODE (x
) != REG
2037 || REG_IN_TABLE (REGNO (x
)) < 0
2038 || REG_IN_TABLE (REGNO (x
)) != REG_TICK (REGNO (x
)))
2041 /* Scan all hash chains looking for valid entries that mention X.
2042 If we find one and it is in the wrong hash chain, move it. We can skip
2043 objects that are registers, since they are handled specially. */
2045 for (i
= 0; i
< HASH_SIZE
; i
++)
2046 for (p
= table
[i
]; p
; p
= next
)
2048 next
= p
->next_same_hash
;
2049 if (GET_CODE (p
->exp
) != REG
&& reg_mentioned_p (x
, p
->exp
)
2050 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0)
2051 && i
!= (hash
= safe_hash (p
->exp
, p
->mode
) & HASH_MASK
))
2053 if (p
->next_same_hash
)
2054 p
->next_same_hash
->prev_same_hash
= p
->prev_same_hash
;
2056 if (p
->prev_same_hash
)
2057 p
->prev_same_hash
->next_same_hash
= p
->next_same_hash
;
2059 table
[i
] = p
->next_same_hash
;
2061 p
->next_same_hash
= table
[hash
];
2062 p
->prev_same_hash
= 0;
2064 table
[hash
]->prev_same_hash
= p
;
2070 /* Remove from the hash table any expression that is a call-clobbered
2071 register. Also update their TICK values. */
2074 invalidate_for_call ()
2076 unsigned int regno
, endregno
;
2079 struct table_elt
*p
, *next
;
2082 /* Go through all the hard registers. For each that is clobbered in
2083 a CALL_INSN, remove the register from quantity chains and update
2084 reg_tick if defined. Also see if any of these registers is currently
2087 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
2088 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
2090 delete_reg_equiv (regno
);
2091 if (REG_TICK (regno
) >= 0)
2094 SUBREG_TICKED (regno
) = -1;
2097 in_table
|= (TEST_HARD_REG_BIT (hard_regs_in_table
, regno
) != 0);
2100 /* In the case where we have no call-clobbered hard registers in the
2101 table, we are done. Otherwise, scan the table and remove any
2102 entry that overlaps a call-clobbered register. */
2105 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
2106 for (p
= table
[hash
]; p
; p
= next
)
2108 next
= p
->next_same_hash
;
2110 if (GET_CODE (p
->exp
) != REG
2111 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
2114 regno
= REGNO (p
->exp
);
2115 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (p
->exp
));
2117 for (i
= regno
; i
< endregno
; i
++)
2118 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
2120 remove_from_table (p
, hash
);
2126 /* Given an expression X of type CONST,
2127 and ELT which is its table entry (or 0 if it
2128 is not in the hash table),
2129 return an alternate expression for X as a register plus integer.
2130 If none can be found, return 0. */
2133 use_related_value (x
, elt
)
2135 struct table_elt
*elt
;
2137 struct table_elt
*relt
= 0;
2138 struct table_elt
*p
, *q
;
2139 HOST_WIDE_INT offset
;
2141 /* First, is there anything related known?
2142 If we have a table element, we can tell from that.
2143 Otherwise, must look it up. */
2145 if (elt
!= 0 && elt
->related_value
!= 0)
2147 else if (elt
== 0 && GET_CODE (x
) == CONST
)
2149 rtx subexp
= get_related_value (x
);
2151 relt
= lookup (subexp
,
2152 safe_hash (subexp
, GET_MODE (subexp
)) & HASH_MASK
,
2159 /* Search all related table entries for one that has an
2160 equivalent register. */
2165 /* This loop is strange in that it is executed in two different cases.
2166 The first is when X is already in the table. Then it is searching
2167 the RELATED_VALUE list of X's class (RELT). The second case is when
2168 X is not in the table. Then RELT points to a class for the related
2171 Ensure that, whatever case we are in, that we ignore classes that have
2172 the same value as X. */
2174 if (rtx_equal_p (x
, p
->exp
))
2177 for (q
= p
->first_same_value
; q
; q
= q
->next_same_value
)
2178 if (GET_CODE (q
->exp
) == REG
)
2184 p
= p
->related_value
;
2186 /* We went all the way around, so there is nothing to be found.
2187 Alternatively, perhaps RELT was in the table for some other reason
2188 and it has no related values recorded. */
2189 if (p
== relt
|| p
== 0)
2196 offset
= (get_integer_term (x
) - get_integer_term (p
->exp
));
2197 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2198 return plus_constant (q
->exp
, offset
);
2201 /* Hash a string. Just add its bytes up. */
2202 static inline unsigned
2203 canon_hash_string (ps
)
2207 const unsigned char *p
= (const unsigned char *) ps
;
2216 /* Hash an rtx. We are careful to make sure the value is never negative.
2217 Equivalent registers hash identically.
2218 MODE is used in hashing for CONST_INTs only;
2219 otherwise the mode of X is used.
2221 Store 1 in do_not_record if any subexpression is volatile.
2223 Store 1 in hash_arg_in_memory if X contains a MEM rtx
2224 which does not have the RTX_UNCHANGING_P bit set.
2226 Note that cse_insn knows that the hash code of a MEM expression
2227 is just (int) MEM plus the hash code of the address. */
2230 canon_hash (x
, mode
)
2232 enum machine_mode mode
;
2239 /* repeat is used to turn tail-recursion into iteration. */
2244 code
= GET_CODE (x
);
2249 unsigned int regno
= REGNO (x
);
2252 /* On some machines, we can't record any non-fixed hard register,
2253 because extending its life will cause reload problems. We
2254 consider ap, fp, sp, gp to be fixed for this purpose.
2256 We also consider CCmode registers to be fixed for this purpose;
2257 failure to do so leads to failure to simplify 0<100 type of
2260 On all machines, we can't record any global registers.
2261 Nor should we record any register that is in a small
2262 class, as defined by CLASS_LIKELY_SPILLED_P. */
2264 if (regno
>= FIRST_PSEUDO_REGISTER
)
2266 else if (x
== frame_pointer_rtx
2267 || x
== hard_frame_pointer_rtx
2268 || x
== arg_pointer_rtx
2269 || x
== stack_pointer_rtx
2270 || x
== pic_offset_table_rtx
)
2272 else if (global_regs
[regno
])
2274 else if (fixed_regs
[regno
])
2276 else if (GET_MODE_CLASS (GET_MODE (x
)) == MODE_CC
)
2278 else if (SMALL_REGISTER_CLASSES
)
2280 else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno
)))
2291 hash
+= ((unsigned) REG
<< 7) + (unsigned) REG_QTY (regno
);
2295 /* We handle SUBREG of a REG specially because the underlying
2296 reg changes its hash value with every value change; we don't
2297 want to have to forget unrelated subregs when one subreg changes. */
2300 if (GET_CODE (SUBREG_REG (x
)) == REG
)
2302 hash
+= (((unsigned) SUBREG
<< 7)
2303 + REGNO (SUBREG_REG (x
))
2304 + (SUBREG_BYTE (x
) / UNITS_PER_WORD
));
2312 unsigned HOST_WIDE_INT tem
= INTVAL (x
);
2313 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ tem
;
2318 /* This is like the general case, except that it only counts
2319 the integers representing the constant. */
2320 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
2321 if (GET_MODE (x
) != VOIDmode
)
2322 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
2324 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
2325 + (unsigned) CONST_DOUBLE_HIGH (x
));
2333 units
= CONST_VECTOR_NUNITS (x
);
2335 for (i
= 0; i
< units
; ++i
)
2337 elt
= CONST_VECTOR_ELT (x
, i
);
2338 hash
+= canon_hash (elt
, GET_MODE (elt
));
2344 /* Assume there is only one rtx object for any given label. */
2346 hash
+= ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
2350 hash
+= ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
2354 /* We don't record if marked volatile or if BLKmode since we don't
2355 know the size of the move. */
2356 if (MEM_VOLATILE_P (x
) || GET_MODE (x
) == BLKmode
)
2361 if (! RTX_UNCHANGING_P (x
) || fixed_base_plus_p (XEXP (x
, 0)))
2362 hash_arg_in_memory
= 1;
2364 /* Now that we have already found this special case,
2365 might as well speed it up as much as possible. */
2366 hash
+= (unsigned) MEM
;
2371 /* A USE that mentions non-volatile memory needs special
2372 handling since the MEM may be BLKmode which normally
2373 prevents an entry from being made. Pure calls are
2374 marked by a USE which mentions BLKmode memory. */
2375 if (GET_CODE (XEXP (x
, 0)) == MEM
2376 && ! MEM_VOLATILE_P (XEXP (x
, 0)))
2378 hash
+= (unsigned) USE
;
2381 if (! RTX_UNCHANGING_P (x
) || fixed_base_plus_p (XEXP (x
, 0)))
2382 hash_arg_in_memory
= 1;
2384 /* Now that we have already found this special case,
2385 might as well speed it up as much as possible. */
2386 hash
+= (unsigned) MEM
;
2401 case UNSPEC_VOLATILE
:
2406 if (MEM_VOLATILE_P (x
))
2413 /* We don't want to take the filename and line into account. */
2414 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
)
2415 + canon_hash_string (ASM_OPERANDS_TEMPLATE (x
))
2416 + canon_hash_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x
))
2417 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x
);
2419 if (ASM_OPERANDS_INPUT_LENGTH (x
))
2421 for (i
= 1; i
< ASM_OPERANDS_INPUT_LENGTH (x
); i
++)
2423 hash
+= (canon_hash (ASM_OPERANDS_INPUT (x
, i
),
2424 GET_MODE (ASM_OPERANDS_INPUT (x
, i
)))
2425 + canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT
2429 hash
+= canon_hash_string (ASM_OPERANDS_INPUT_CONSTRAINT (x
, 0));
2430 x
= ASM_OPERANDS_INPUT (x
, 0);
2431 mode
= GET_MODE (x
);
2443 i
= GET_RTX_LENGTH (code
) - 1;
2444 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
2445 fmt
= GET_RTX_FORMAT (code
);
2450 rtx tem
= XEXP (x
, i
);
2452 /* If we are about to do the last recursive call
2453 needed at this level, change it into iteration.
2454 This function is called enough to be worth it. */
2460 hash
+= canon_hash (tem
, 0);
2462 else if (fmt
[i
] == 'E')
2463 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2464 hash
+= canon_hash (XVECEXP (x
, i
, j
), 0);
2465 else if (fmt
[i
] == 's')
2466 hash
+= canon_hash_string (XSTR (x
, i
));
2467 else if (fmt
[i
] == 'i')
2469 unsigned tem
= XINT (x
, i
);
2472 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
2481 /* Like canon_hash but with no side effects. */
2486 enum machine_mode mode
;
2488 int save_do_not_record
= do_not_record
;
2489 int save_hash_arg_in_memory
= hash_arg_in_memory
;
2490 unsigned hash
= canon_hash (x
, mode
);
2491 hash_arg_in_memory
= save_hash_arg_in_memory
;
2492 do_not_record
= save_do_not_record
;
2496 /* Return 1 iff X and Y would canonicalize into the same thing,
2497 without actually constructing the canonicalization of either one.
2498 If VALIDATE is nonzero,
2499 we assume X is an expression being processed from the rtl
2500 and Y was found in the hash table. We check register refs
2501 in Y for being marked as valid.
2503 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
2504 that is known to be in the register. Ordinarily, we don't allow them
2505 to match, because letting them match would cause unpredictable results
2506 in all the places that search a hash table chain for an equivalent
2507 for a given value. A possible equivalent that has different structure
2508 has its hash code computed from different data. Whether the hash code
2509 is the same as that of the given value is pure luck. */
2512 exp_equiv_p (x
, y
, validate
, equal_values
)
2521 /* Note: it is incorrect to assume an expression is equivalent to itself
2522 if VALIDATE is nonzero. */
2523 if (x
== y
&& !validate
)
2525 if (x
== 0 || y
== 0)
2528 code
= GET_CODE (x
);
2529 if (code
!= GET_CODE (y
))
2534 /* If X is a constant and Y is a register or vice versa, they may be
2535 equivalent. We only have to validate if Y is a register. */
2536 if (CONSTANT_P (x
) && GET_CODE (y
) == REG
2537 && REGNO_QTY_VALID_P (REGNO (y
)))
2539 int y_q
= REG_QTY (REGNO (y
));
2540 struct qty_table_elem
*y_ent
= &qty_table
[y_q
];
2542 if (GET_MODE (y
) == y_ent
->mode
2543 && rtx_equal_p (x
, y_ent
->const_rtx
)
2544 && (! validate
|| REG_IN_TABLE (REGNO (y
)) == REG_TICK (REGNO (y
))))
2548 if (CONSTANT_P (y
) && code
== REG
2549 && REGNO_QTY_VALID_P (REGNO (x
)))
2551 int x_q
= REG_QTY (REGNO (x
));
2552 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
2554 if (GET_MODE (x
) == x_ent
->mode
2555 && rtx_equal_p (y
, x_ent
->const_rtx
))
2562 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2563 if (GET_MODE (x
) != GET_MODE (y
))
2574 return XEXP (x
, 0) == XEXP (y
, 0);
2577 return XSTR (x
, 0) == XSTR (y
, 0);
2581 unsigned int regno
= REGNO (y
);
2582 unsigned int endregno
2583 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
2584 : HARD_REGNO_NREGS (regno
, GET_MODE (y
)));
2587 /* If the quantities are not the same, the expressions are not
2588 equivalent. If there are and we are not to validate, they
2589 are equivalent. Otherwise, ensure all regs are up-to-date. */
2591 if (REG_QTY (REGNO (x
)) != REG_QTY (regno
))
2597 for (i
= regno
; i
< endregno
; i
++)
2598 if (REG_IN_TABLE (i
) != REG_TICK (i
))
2604 /* For commutative operations, check both orders. */
2612 return ((exp_equiv_p (XEXP (x
, 0), XEXP (y
, 0), validate
, equal_values
)
2613 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 1),
2614 validate
, equal_values
))
2615 || (exp_equiv_p (XEXP (x
, 0), XEXP (y
, 1),
2616 validate
, equal_values
)
2617 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 0),
2618 validate
, equal_values
)));
2621 /* We don't use the generic code below because we want to
2622 disregard filename and line numbers. */
2624 /* A volatile asm isn't equivalent to any other. */
2625 if (MEM_VOLATILE_P (x
) || MEM_VOLATILE_P (y
))
2628 if (GET_MODE (x
) != GET_MODE (y
)
2629 || strcmp (ASM_OPERANDS_TEMPLATE (x
), ASM_OPERANDS_TEMPLATE (y
))
2630 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x
),
2631 ASM_OPERANDS_OUTPUT_CONSTRAINT (y
))
2632 || ASM_OPERANDS_OUTPUT_IDX (x
) != ASM_OPERANDS_OUTPUT_IDX (y
)
2633 || ASM_OPERANDS_INPUT_LENGTH (x
) != ASM_OPERANDS_INPUT_LENGTH (y
))
2636 if (ASM_OPERANDS_INPUT_LENGTH (x
))
2638 for (i
= ASM_OPERANDS_INPUT_LENGTH (x
) - 1; i
>= 0; i
--)
2639 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x
, i
),
2640 ASM_OPERANDS_INPUT (y
, i
),
2641 validate
, equal_values
)
2642 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x
, i
),
2643 ASM_OPERANDS_INPUT_CONSTRAINT (y
, i
)))
2653 /* Compare the elements. If any pair of corresponding elements
2654 fail to match, return 0 for the whole things. */
2656 fmt
= GET_RTX_FORMAT (code
);
2657 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2662 if (! exp_equiv_p (XEXP (x
, i
), XEXP (y
, i
), validate
, equal_values
))
2667 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
2669 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2670 if (! exp_equiv_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
),
2671 validate
, equal_values
))
2676 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
2681 if (XINT (x
, i
) != XINT (y
, i
))
2686 if (XWINT (x
, i
) != XWINT (y
, i
))
2702 /* Return 1 if X has a value that can vary even between two
2703 executions of the program. 0 means X can be compared reliably
2704 against certain constants or near-constants. */
2707 cse_rtx_varies_p (x
, from_alias
)
2711 /* We need not check for X and the equivalence class being of the same
2712 mode because if X is equivalent to a constant in some mode, it
2713 doesn't vary in any mode. */
2715 if (GET_CODE (x
) == REG
2716 && REGNO_QTY_VALID_P (REGNO (x
)))
2718 int x_q
= REG_QTY (REGNO (x
));
2719 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
2721 if (GET_MODE (x
) == x_ent
->mode
2722 && x_ent
->const_rtx
!= NULL_RTX
)
2726 if (GET_CODE (x
) == PLUS
2727 && GET_CODE (XEXP (x
, 1)) == CONST_INT
2728 && GET_CODE (XEXP (x
, 0)) == REG
2729 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0))))
2731 int x0_q
= REG_QTY (REGNO (XEXP (x
, 0)));
2732 struct qty_table_elem
*x0_ent
= &qty_table
[x0_q
];
2734 if ((GET_MODE (XEXP (x
, 0)) == x0_ent
->mode
)
2735 && x0_ent
->const_rtx
!= NULL_RTX
)
2739 /* This can happen as the result of virtual register instantiation, if
2740 the initial constant is too large to be a valid address. This gives
2741 us a three instruction sequence, load large offset into a register,
2742 load fp minus a constant into a register, then a MEM which is the
2743 sum of the two `constant' registers. */
2744 if (GET_CODE (x
) == PLUS
2745 && GET_CODE (XEXP (x
, 0)) == REG
2746 && GET_CODE (XEXP (x
, 1)) == REG
2747 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0)))
2748 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 1))))
2750 int x0_q
= REG_QTY (REGNO (XEXP (x
, 0)));
2751 int x1_q
= REG_QTY (REGNO (XEXP (x
, 1)));
2752 struct qty_table_elem
*x0_ent
= &qty_table
[x0_q
];
2753 struct qty_table_elem
*x1_ent
= &qty_table
[x1_q
];
2755 if ((GET_MODE (XEXP (x
, 0)) == x0_ent
->mode
)
2756 && x0_ent
->const_rtx
!= NULL_RTX
2757 && (GET_MODE (XEXP (x
, 1)) == x1_ent
->mode
)
2758 && x1_ent
->const_rtx
!= NULL_RTX
)
2762 return rtx_varies_p (x
, from_alias
);
2765 /* Canonicalize an expression:
2766 replace each register reference inside it
2767 with the "oldest" equivalent register.
2769 If INSN is nonzero and we are replacing a pseudo with a hard register
2770 or vice versa, validate_change is used to ensure that INSN remains valid
2771 after we make our substitution. The calls are made with IN_GROUP nonzero
2772 so apply_change_group must be called upon the outermost return from this
2773 function (unless INSN is zero). The result of apply_change_group can
2774 generally be discarded since the changes we are making are optional. */
2788 code
= GET_CODE (x
);
2807 struct qty_table_elem
*ent
;
2809 /* Never replace a hard reg, because hard regs can appear
2810 in more than one machine mode, and we must preserve the mode
2811 of each occurrence. Also, some hard regs appear in
2812 MEMs that are shared and mustn't be altered. Don't try to
2813 replace any reg that maps to a reg of class NO_REGS. */
2814 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
2815 || ! REGNO_QTY_VALID_P (REGNO (x
)))
2818 q
= REG_QTY (REGNO (x
));
2819 ent
= &qty_table
[q
];
2820 first
= ent
->first_reg
;
2821 return (first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
2822 : REGNO_REG_CLASS (first
) == NO_REGS
? x
2823 : gen_rtx_REG (ent
->mode
, first
));
2830 fmt
= GET_RTX_FORMAT (code
);
2831 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2837 rtx
new = canon_reg (XEXP (x
, i
), insn
);
2840 /* If replacing pseudo with hard reg or vice versa, ensure the
2841 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2842 if (insn
!= 0 && new != 0
2843 && GET_CODE (new) == REG
&& GET_CODE (XEXP (x
, i
)) == REG
2844 && (((REGNO (new) < FIRST_PSEUDO_REGISTER
)
2845 != (REGNO (XEXP (x
, i
)) < FIRST_PSEUDO_REGISTER
))
2846 || (insn_code
= recog_memoized (insn
)) < 0
2847 || insn_data
[insn_code
].n_dups
> 0))
2848 validate_change (insn
, &XEXP (x
, i
), new, 1);
2852 else if (fmt
[i
] == 'E')
2853 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2854 XVECEXP (x
, i
, j
) = canon_reg (XVECEXP (x
, i
, j
), insn
);
2860 /* LOC is a location within INSN that is an operand address (the contents of
2861 a MEM). Find the best equivalent address to use that is valid for this
2864 On most CISC machines, complicated address modes are costly, and rtx_cost
2865 is a good approximation for that cost. However, most RISC machines have
2866 only a few (usually only one) memory reference formats. If an address is
2867 valid at all, it is often just as cheap as any other address. Hence, for
2868 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2869 costs of various addresses. For two addresses of equal cost, choose the one
2870 with the highest `rtx_cost' value as that has the potential of eliminating
2871 the most insns. For equal costs, we choose the first in the equivalence
2872 class. Note that we ignore the fact that pseudo registers are cheaper
2873 than hard registers here because we would also prefer the pseudo registers.
2877 find_best_addr (insn
, loc
, mode
)
2880 enum machine_mode mode
;
2882 struct table_elt
*elt
;
2885 struct table_elt
*p
;
2886 int found_better
= 1;
2888 int save_do_not_record
= do_not_record
;
2889 int save_hash_arg_in_memory
= hash_arg_in_memory
;
2894 /* Do not try to replace constant addresses or addresses of local and
2895 argument slots. These MEM expressions are made only once and inserted
2896 in many instructions, as well as being used to control symbol table
2897 output. It is not safe to clobber them.
2899 There are some uncommon cases where the address is already in a register
2900 for some reason, but we cannot take advantage of that because we have
2901 no easy way to unshare the MEM. In addition, looking up all stack
2902 addresses is costly. */
2903 if ((GET_CODE (addr
) == PLUS
2904 && GET_CODE (XEXP (addr
, 0)) == REG
2905 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
2906 && (regno
= REGNO (XEXP (addr
, 0)),
2907 regno
== FRAME_POINTER_REGNUM
|| regno
== HARD_FRAME_POINTER_REGNUM
2908 || regno
== ARG_POINTER_REGNUM
))
2909 || (GET_CODE (addr
) == REG
2910 && (regno
= REGNO (addr
), regno
== FRAME_POINTER_REGNUM
2911 || regno
== HARD_FRAME_POINTER_REGNUM
2912 || regno
== ARG_POINTER_REGNUM
))
2913 || GET_CODE (addr
) == ADDRESSOF
2914 || CONSTANT_ADDRESS_P (addr
))
2917 /* If this address is not simply a register, try to fold it. This will
2918 sometimes simplify the expression. Many simplifications
2919 will not be valid, but some, usually applying the associative rule, will
2920 be valid and produce better code. */
2921 if (GET_CODE (addr
) != REG
)
2923 rtx folded
= fold_rtx (copy_rtx (addr
), NULL_RTX
);
2924 int addr_folded_cost
= address_cost (folded
, mode
);
2925 int addr_cost
= address_cost (addr
, mode
);
2927 if ((addr_folded_cost
< addr_cost
2928 || (addr_folded_cost
== addr_cost
2929 /* ??? The rtx_cost comparison is left over from an older
2930 version of this code. It is probably no longer helpful. */
2931 && (rtx_cost (folded
, MEM
) > rtx_cost (addr
, MEM
)
2932 || approx_reg_cost (folded
) < approx_reg_cost (addr
))))
2933 && validate_change (insn
, loc
, folded
, 0))
2937 /* If this address is not in the hash table, we can't look for equivalences
2938 of the whole address. Also, ignore if volatile. */
2941 hash
= HASH (addr
, Pmode
);
2942 addr_volatile
= do_not_record
;
2943 do_not_record
= save_do_not_record
;
2944 hash_arg_in_memory
= save_hash_arg_in_memory
;
2949 elt
= lookup (addr
, hash
, Pmode
);
2951 #ifndef ADDRESS_COST
2954 int our_cost
= elt
->cost
;
2956 /* Find the lowest cost below ours that works. */
2957 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
2958 if (elt
->cost
< our_cost
2959 && (GET_CODE (elt
->exp
) == REG
2960 || exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
2961 && validate_change (insn
, loc
,
2962 canon_reg (copy_rtx (elt
->exp
), NULL_RTX
), 0))
2969 /* We need to find the best (under the criteria documented above) entry
2970 in the class that is valid. We use the `flag' field to indicate
2971 choices that were invalid and iterate until we can't find a better
2972 one that hasn't already been tried. */
2974 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2977 while (found_better
)
2979 int best_addr_cost
= address_cost (*loc
, mode
);
2980 int best_rtx_cost
= (elt
->cost
+ 1) >> 1;
2982 struct table_elt
*best_elt
= elt
;
2985 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2988 if ((GET_CODE (p
->exp
) == REG
2989 || exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
2990 && ((exp_cost
= address_cost (p
->exp
, mode
)) < best_addr_cost
2991 || (exp_cost
== best_addr_cost
2992 && ((p
->cost
+ 1) >> 1) > best_rtx_cost
)))
2995 best_addr_cost
= exp_cost
;
2996 best_rtx_cost
= (p
->cost
+ 1) >> 1;
3003 if (validate_change (insn
, loc
,
3004 canon_reg (copy_rtx (best_elt
->exp
),
3013 /* If the address is a binary operation with the first operand a register
3014 and the second a constant, do the same as above, but looking for
3015 equivalences of the register. Then try to simplify before checking for
3016 the best address to use. This catches a few cases: First is when we
3017 have REG+const and the register is another REG+const. We can often merge
3018 the constants and eliminate one insn and one register. It may also be
3019 that a machine has a cheap REG+REG+const. Finally, this improves the
3020 code on the Alpha for unaligned byte stores. */
3022 if (flag_expensive_optimizations
3023 && (GET_RTX_CLASS (GET_CODE (*loc
)) == '2'
3024 || GET_RTX_CLASS (GET_CODE (*loc
)) == 'c')
3025 && GET_CODE (XEXP (*loc
, 0)) == REG
3026 && GET_CODE (XEXP (*loc
, 1)) == CONST_INT
)
3028 rtx c
= XEXP (*loc
, 1);
3031 hash
= HASH (XEXP (*loc
, 0), Pmode
);
3032 do_not_record
= save_do_not_record
;
3033 hash_arg_in_memory
= save_hash_arg_in_memory
;
3035 elt
= lookup (XEXP (*loc
, 0), hash
, Pmode
);
3039 /* We need to find the best (under the criteria documented above) entry
3040 in the class that is valid. We use the `flag' field to indicate
3041 choices that were invalid and iterate until we can't find a better
3042 one that hasn't already been tried. */
3044 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
3047 while (found_better
)
3049 int best_addr_cost
= address_cost (*loc
, mode
);
3050 int best_rtx_cost
= (COST (*loc
) + 1) >> 1;
3051 struct table_elt
*best_elt
= elt
;
3052 rtx best_rtx
= *loc
;
3055 /* This is at worst case an O(n^2) algorithm, so limit our search
3056 to the first 32 elements on the list. This avoids trouble
3057 compiling code with very long basic blocks that can easily
3058 call simplify_gen_binary so many times that we run out of
3062 for (p
= elt
->first_same_value
, count
= 0;
3064 p
= p
->next_same_value
, count
++)
3066 && (GET_CODE (p
->exp
) == REG
3067 || exp_equiv_p (p
->exp
, p
->exp
, 1, 0)))
3069 rtx
new = simplify_gen_binary (GET_CODE (*loc
), Pmode
,
3072 new_cost
= address_cost (new, mode
);
3074 if (new_cost
< best_addr_cost
3075 || (new_cost
== best_addr_cost
3076 && (COST (new) + 1) >> 1 > best_rtx_cost
))
3079 best_addr_cost
= new_cost
;
3080 best_rtx_cost
= (COST (new) + 1) >> 1;
3088 if (validate_change (insn
, loc
,
3089 canon_reg (copy_rtx (best_rtx
),
3100 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
3101 operation (EQ, NE, GT, etc.), follow it back through the hash table and
3102 what values are being compared.
3104 *PARG1 and *PARG2 are updated to contain the rtx representing the values
3105 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
3106 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
3107 compared to produce cc0.
3109 The return value is the comparison operator and is either the code of
3110 A or the code corresponding to the inverse of the comparison. */
3112 static enum rtx_code
3113 find_comparison_args (code
, parg1
, parg2
, pmode1
, pmode2
)
3116 enum machine_mode
*pmode1
, *pmode2
;
3120 arg1
= *parg1
, arg2
= *parg2
;
3122 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
3124 while (arg2
== CONST0_RTX (GET_MODE (arg1
)))
3126 /* Set nonzero when we find something of interest. */
3128 int reverse_code
= 0;
3129 struct table_elt
*p
= 0;
3131 /* If arg1 is a COMPARE, extract the comparison arguments from it.
3132 On machines with CC0, this is the only case that can occur, since
3133 fold_rtx will return the COMPARE or item being compared with zero
3136 if (GET_CODE (arg1
) == COMPARE
&& arg2
== const0_rtx
)
3139 /* If ARG1 is a comparison operator and CODE is testing for
3140 STORE_FLAG_VALUE, get the inner arguments. */
3142 else if (GET_RTX_CLASS (GET_CODE (arg1
)) == '<')
3144 #ifdef FLOAT_STORE_FLAG_VALUE
3145 REAL_VALUE_TYPE fsfv
;
3149 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
3150 && code
== LT
&& STORE_FLAG_VALUE
== -1)
3151 #ifdef FLOAT_STORE_FLAG_VALUE
3152 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_FLOAT
3153 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
3154 REAL_VALUE_NEGATIVE (fsfv
)))
3159 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
3160 && code
== GE
&& STORE_FLAG_VALUE
== -1)
3161 #ifdef FLOAT_STORE_FLAG_VALUE
3162 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_FLOAT
3163 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
3164 REAL_VALUE_NEGATIVE (fsfv
)))
3167 x
= arg1
, reverse_code
= 1;
3170 /* ??? We could also check for
3172 (ne (and (eq (...) (const_int 1))) (const_int 0))
3174 and related forms, but let's wait until we see them occurring. */
3177 /* Look up ARG1 in the hash table and see if it has an equivalence
3178 that lets us see what is being compared. */
3179 p
= lookup (arg1
, safe_hash (arg1
, GET_MODE (arg1
)) & HASH_MASK
,
3183 p
= p
->first_same_value
;
3185 /* If what we compare is already known to be constant, that is as
3187 We need to break the loop in this case, because otherwise we
3188 can have an infinite loop when looking at a reg that is known
3189 to be a constant which is the same as a comparison of a reg
3190 against zero which appears later in the insn stream, which in
3191 turn is constant and the same as the comparison of the first reg
3197 for (; p
; p
= p
->next_same_value
)
3199 enum machine_mode inner_mode
= GET_MODE (p
->exp
);
3200 #ifdef FLOAT_STORE_FLAG_VALUE
3201 REAL_VALUE_TYPE fsfv
;
3204 /* If the entry isn't valid, skip it. */
3205 if (! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
3208 if (GET_CODE (p
->exp
) == COMPARE
3209 /* Another possibility is that this machine has a compare insn
3210 that includes the comparison code. In that case, ARG1 would
3211 be equivalent to a comparison operation that would set ARG1 to
3212 either STORE_FLAG_VALUE or zero. If this is an NE operation,
3213 ORIG_CODE is the actual comparison being done; if it is an EQ,
3214 we must reverse ORIG_CODE. On machine with a negative value
3215 for STORE_FLAG_VALUE, also look at LT and GE operations. */
3218 && GET_MODE_CLASS (inner_mode
) == MODE_INT
3219 && (GET_MODE_BITSIZE (inner_mode
)
3220 <= HOST_BITS_PER_WIDE_INT
)
3221 && (STORE_FLAG_VALUE
3222 & ((HOST_WIDE_INT
) 1
3223 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
3224 #ifdef FLOAT_STORE_FLAG_VALUE
3226 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
3227 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
3228 REAL_VALUE_NEGATIVE (fsfv
)))
3231 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<'))
3236 else if ((code
== EQ
3238 && GET_MODE_CLASS (inner_mode
) == MODE_INT
3239 && (GET_MODE_BITSIZE (inner_mode
)
3240 <= HOST_BITS_PER_WIDE_INT
)
3241 && (STORE_FLAG_VALUE
3242 & ((HOST_WIDE_INT
) 1
3243 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
3244 #ifdef FLOAT_STORE_FLAG_VALUE
3246 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
3247 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
3248 REAL_VALUE_NEGATIVE (fsfv
)))
3251 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<')
3258 /* If this non-trapping address, e.g. fp + constant, the
3259 equivalent is a better operand since it may let us predict
3260 the value of the comparison. */
3261 else if (!rtx_addr_can_trap_p (p
->exp
))
3268 /* If we didn't find a useful equivalence for ARG1, we are done.
3269 Otherwise, set up for the next iteration. */
3273 /* If we need to reverse the comparison, make sure that that is
3274 possible -- we can't necessarily infer the value of GE from LT
3275 with floating-point operands. */
3278 enum rtx_code reversed
= reversed_comparison_code (x
, NULL_RTX
);
3279 if (reversed
== UNKNOWN
)
3284 else if (GET_RTX_CLASS (GET_CODE (x
)) == '<')
3285 code
= GET_CODE (x
);
3286 arg1
= XEXP (x
, 0), arg2
= XEXP (x
, 1);
3289 /* Return our results. Return the modes from before fold_rtx
3290 because fold_rtx might produce const_int, and then it's too late. */
3291 *pmode1
= GET_MODE (arg1
), *pmode2
= GET_MODE (arg2
);
3292 *parg1
= fold_rtx (arg1
, 0), *parg2
= fold_rtx (arg2
, 0);
3297 /* If X is a nontrivial arithmetic operation on an argument
3298 for which a constant value can be determined, return
3299 the result of operating on that value, as a constant.
3300 Otherwise, return X, possibly with one or more operands
3301 modified by recursive calls to this function.
3303 If X is a register whose contents are known, we do NOT
3304 return those contents here. equiv_constant is called to
3307 INSN is the insn that we may be modifying. If it is 0, make a copy
3308 of X before modifying it. */
3316 enum machine_mode mode
;
3323 /* Folded equivalents of first two operands of X. */
3327 /* Constant equivalents of first three operands of X;
3328 0 when no such equivalent is known. */
3333 /* The mode of the first operand of X. We need this for sign and zero
3335 enum machine_mode mode_arg0
;
3340 mode
= GET_MODE (x
);
3341 code
= GET_CODE (x
);
3351 /* No use simplifying an EXPR_LIST
3352 since they are used only for lists of args
3353 in a function call's REG_EQUAL note. */
3355 /* Changing anything inside an ADDRESSOF is incorrect; we don't
3356 want to (e.g.,) make (addressof (const_int 0)) just because
3357 the location is known to be zero. */
3363 return prev_insn_cc0
;
3367 /* If the next insn is a CODE_LABEL followed by a jump table,
3368 PC's value is a LABEL_REF pointing to that label. That
3369 lets us fold switch statements on the VAX. */
3370 if (insn
&& GET_CODE (insn
) == JUMP_INSN
)
3372 rtx next
= next_nonnote_insn (insn
);
3374 if (next
&& GET_CODE (next
) == CODE_LABEL
3375 && NEXT_INSN (next
) != 0
3376 && GET_CODE (NEXT_INSN (next
)) == JUMP_INSN
3377 && (GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_VEC
3378 || GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_DIFF_VEC
))
3379 return gen_rtx_LABEL_REF (Pmode
, next
);
3384 /* See if we previously assigned a constant value to this SUBREG. */
3385 if ((new = lookup_as_function (x
, CONST_INT
)) != 0
3386 || (new = lookup_as_function (x
, CONST_DOUBLE
)) != 0)
3389 /* If this is a paradoxical SUBREG, we have no idea what value the
3390 extra bits would have. However, if the operand is equivalent
3391 to a SUBREG whose operand is the same as our mode, and all the
3392 modes are within a word, we can just use the inner operand
3393 because these SUBREGs just say how to treat the register.
3395 Similarly if we find an integer constant. */
3397 if (GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
3399 enum machine_mode imode
= GET_MODE (SUBREG_REG (x
));
3400 struct table_elt
*elt
;
3402 if (GET_MODE_SIZE (mode
) <= UNITS_PER_WORD
3403 && GET_MODE_SIZE (imode
) <= UNITS_PER_WORD
3404 && (elt
= lookup (SUBREG_REG (x
), HASH (SUBREG_REG (x
), imode
),
3406 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
3408 if (CONSTANT_P (elt
->exp
)
3409 && GET_MODE (elt
->exp
) == VOIDmode
)
3412 if (GET_CODE (elt
->exp
) == SUBREG
3413 && GET_MODE (SUBREG_REG (elt
->exp
)) == mode
3414 && exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
3415 return copy_rtx (SUBREG_REG (elt
->exp
));
3421 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
3422 We might be able to if the SUBREG is extracting a single word in an
3423 integral mode or extracting the low part. */
3425 folded_arg0
= fold_rtx (SUBREG_REG (x
), insn
);
3426 const_arg0
= equiv_constant (folded_arg0
);
3428 folded_arg0
= const_arg0
;
3430 if (folded_arg0
!= SUBREG_REG (x
))
3432 new = simplify_subreg (mode
, folded_arg0
,
3433 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
3438 /* If this is a narrowing SUBREG and our operand is a REG, see if
3439 we can find an equivalence for REG that is an arithmetic operation
3440 in a wider mode where both operands are paradoxical SUBREGs
3441 from objects of our result mode. In that case, we couldn't report
3442 an equivalent value for that operation, since we don't know what the
3443 extra bits will be. But we can find an equivalence for this SUBREG
3444 by folding that operation is the narrow mode. This allows us to
3445 fold arithmetic in narrow modes when the machine only supports
3446 word-sized arithmetic.
3448 Also look for a case where we have a SUBREG whose operand is the
3449 same as our result. If both modes are smaller than a word, we
3450 are simply interpreting a register in different modes and we
3451 can use the inner value. */
3453 if (GET_CODE (folded_arg0
) == REG
3454 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (folded_arg0
))
3455 && subreg_lowpart_p (x
))
3457 struct table_elt
*elt
;
3459 /* We can use HASH here since we know that canon_hash won't be
3461 elt
= lookup (folded_arg0
,
3462 HASH (folded_arg0
, GET_MODE (folded_arg0
)),
3463 GET_MODE (folded_arg0
));
3466 elt
= elt
->first_same_value
;
3468 for (; elt
; elt
= elt
->next_same_value
)
3470 enum rtx_code eltcode
= GET_CODE (elt
->exp
);
3472 /* Just check for unary and binary operations. */
3473 if (GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '1'
3474 && GET_CODE (elt
->exp
) != SIGN_EXTEND
3475 && GET_CODE (elt
->exp
) != ZERO_EXTEND
3476 && GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
3477 && GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0))) == mode
3478 && (GET_MODE_CLASS (mode
)
3479 == GET_MODE_CLASS (GET_MODE (XEXP (elt
->exp
, 0)))))
3481 rtx op0
= SUBREG_REG (XEXP (elt
->exp
, 0));
3483 if (GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
3484 op0
= fold_rtx (op0
, NULL_RTX
);
3486 op0
= equiv_constant (op0
);
3488 new = simplify_unary_operation (GET_CODE (elt
->exp
), mode
,
3491 else if ((GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '2'
3492 || GET_RTX_CLASS (GET_CODE (elt
->exp
)) == 'c')
3493 && eltcode
!= DIV
&& eltcode
!= MOD
3494 && eltcode
!= UDIV
&& eltcode
!= UMOD
3495 && eltcode
!= ASHIFTRT
&& eltcode
!= LSHIFTRT
3496 && eltcode
!= ROTATE
&& eltcode
!= ROTATERT
3497 && ((GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
3498 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0)))
3500 || CONSTANT_P (XEXP (elt
->exp
, 0)))
3501 && ((GET_CODE (XEXP (elt
->exp
, 1)) == SUBREG
3502 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 1)))
3504 || CONSTANT_P (XEXP (elt
->exp
, 1))))
3506 rtx op0
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 0));
3507 rtx op1
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 1));
3509 if (op0
&& GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
3510 op0
= fold_rtx (op0
, NULL_RTX
);
3513 op0
= equiv_constant (op0
);
3515 if (op1
&& GET_CODE (op1
) != REG
&& ! CONSTANT_P (op1
))
3516 op1
= fold_rtx (op1
, NULL_RTX
);
3519 op1
= equiv_constant (op1
);
3521 /* If we are looking for the low SImode part of
3522 (ashift:DI c (const_int 32)), it doesn't work
3523 to compute that in SImode, because a 32-bit shift
3524 in SImode is unpredictable. We know the value is 0. */
3526 && GET_CODE (elt
->exp
) == ASHIFT
3527 && GET_CODE (op1
) == CONST_INT
3528 && INTVAL (op1
) >= GET_MODE_BITSIZE (mode
))
3530 if (INTVAL (op1
) < GET_MODE_BITSIZE (GET_MODE (elt
->exp
)))
3532 /* If the count fits in the inner mode's width,
3533 but exceeds the outer mode's width,
3534 the value will get truncated to 0
3538 /* If the count exceeds even the inner mode's width,
3539 don't fold this expression. */
3542 else if (op0
&& op1
)
3543 new = simplify_binary_operation (GET_CODE (elt
->exp
), mode
,
3547 else if (GET_CODE (elt
->exp
) == SUBREG
3548 && GET_MODE (SUBREG_REG (elt
->exp
)) == mode
3549 && (GET_MODE_SIZE (GET_MODE (folded_arg0
))
3551 && exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
3552 new = copy_rtx (SUBREG_REG (elt
->exp
));
3563 /* If we have (NOT Y), see if Y is known to be (NOT Z).
3564 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
3565 new = lookup_as_function (XEXP (x
, 0), code
);
3567 return fold_rtx (copy_rtx (XEXP (new, 0)), insn
);
3571 /* If we are not actually processing an insn, don't try to find the
3572 best address. Not only don't we care, but we could modify the
3573 MEM in an invalid way since we have no insn to validate against. */
3575 find_best_addr (insn
, &XEXP (x
, 0), GET_MODE (x
));
3578 /* Even if we don't fold in the insn itself,
3579 we can safely do so here, in hopes of getting a constant. */
3580 rtx addr
= fold_rtx (XEXP (x
, 0), NULL_RTX
);
3582 HOST_WIDE_INT offset
= 0;
3584 if (GET_CODE (addr
) == REG
3585 && REGNO_QTY_VALID_P (REGNO (addr
)))
3587 int addr_q
= REG_QTY (REGNO (addr
));
3588 struct qty_table_elem
*addr_ent
= &qty_table
[addr_q
];
3590 if (GET_MODE (addr
) == addr_ent
->mode
3591 && addr_ent
->const_rtx
!= NULL_RTX
)
3592 addr
= addr_ent
->const_rtx
;
3595 /* If address is constant, split it into a base and integer offset. */
3596 if (GET_CODE (addr
) == SYMBOL_REF
|| GET_CODE (addr
) == LABEL_REF
)
3598 else if (GET_CODE (addr
) == CONST
&& GET_CODE (XEXP (addr
, 0)) == PLUS
3599 && GET_CODE (XEXP (XEXP (addr
, 0), 1)) == CONST_INT
)
3601 base
= XEXP (XEXP (addr
, 0), 0);
3602 offset
= INTVAL (XEXP (XEXP (addr
, 0), 1));
3604 else if (GET_CODE (addr
) == LO_SUM
3605 && GET_CODE (XEXP (addr
, 1)) == SYMBOL_REF
)
3606 base
= XEXP (addr
, 1);
3607 else if (GET_CODE (addr
) == ADDRESSOF
)
3608 return change_address (x
, VOIDmode
, addr
);
3610 /* If this is a constant pool reference, we can fold it into its
3611 constant to allow better value tracking. */
3612 if (base
&& GET_CODE (base
) == SYMBOL_REF
3613 && CONSTANT_POOL_ADDRESS_P (base
))
3615 rtx constant
= get_pool_constant (base
);
3616 enum machine_mode const_mode
= get_pool_mode (base
);
3619 if (CONSTANT_P (constant
) && GET_CODE (constant
) != CONST_INT
)
3620 constant_pool_entries_cost
= COST (constant
);
3622 /* If we are loading the full constant, we have an equivalence. */
3623 if (offset
== 0 && mode
== const_mode
)
3626 /* If this actually isn't a constant (weird!), we can't do
3627 anything. Otherwise, handle the two most common cases:
3628 extracting a word from a multi-word constant, and extracting
3629 the low-order bits. Other cases don't seem common enough to
3631 if (! CONSTANT_P (constant
))
3634 if (GET_MODE_CLASS (mode
) == MODE_INT
3635 && GET_MODE_SIZE (mode
) == UNITS_PER_WORD
3636 && offset
% UNITS_PER_WORD
== 0
3637 && (new = operand_subword (constant
,
3638 offset
/ UNITS_PER_WORD
,
3639 0, const_mode
)) != 0)
3642 if (((BYTES_BIG_ENDIAN
3643 && offset
== GET_MODE_SIZE (GET_MODE (constant
)) - 1)
3644 || (! BYTES_BIG_ENDIAN
&& offset
== 0))
3645 && (new = gen_lowpart_if_possible (mode
, constant
)) != 0)
3649 /* If this is a reference to a label at a known position in a jump
3650 table, we also know its value. */
3651 if (base
&& GET_CODE (base
) == LABEL_REF
)
3653 rtx label
= XEXP (base
, 0);
3654 rtx table_insn
= NEXT_INSN (label
);
3656 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
3657 && GET_CODE (PATTERN (table_insn
)) == ADDR_VEC
)
3659 rtx table
= PATTERN (table_insn
);
3662 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
3663 < XVECLEN (table
, 0)))
3664 return XVECEXP (table
, 0,
3665 offset
/ GET_MODE_SIZE (GET_MODE (table
)));
3667 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
3668 && GET_CODE (PATTERN (table_insn
)) == ADDR_DIFF_VEC
)
3670 rtx table
= PATTERN (table_insn
);
3673 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
3674 < XVECLEN (table
, 1)))
3676 offset
/= GET_MODE_SIZE (GET_MODE (table
));
3677 new = gen_rtx_MINUS (Pmode
, XVECEXP (table
, 1, offset
),
3680 if (GET_MODE (table
) != Pmode
)
3681 new = gen_rtx_TRUNCATE (GET_MODE (table
), new);
3683 /* Indicate this is a constant. This isn't a
3684 valid form of CONST, but it will only be used
3685 to fold the next insns and then discarded, so
3688 Note this expression must be explicitly discarded,
3689 by cse_insn, else it may end up in a REG_EQUAL note
3690 and "escape" to cause problems elsewhere. */
3691 return gen_rtx_CONST (GET_MODE (new), new);
3699 #ifdef NO_FUNCTION_CSE
3701 if (CONSTANT_P (XEXP (XEXP (x
, 0), 0)))
3707 for (i
= ASM_OPERANDS_INPUT_LENGTH (x
) - 1; i
>= 0; i
--)
3708 validate_change (insn
, &ASM_OPERANDS_INPUT (x
, i
),
3709 fold_rtx (ASM_OPERANDS_INPUT (x
, i
), insn
), 0);
3719 mode_arg0
= VOIDmode
;
3721 /* Try folding our operands.
3722 Then see which ones have constant values known. */
3724 fmt
= GET_RTX_FORMAT (code
);
3725 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3728 rtx arg
= XEXP (x
, i
);
3729 rtx folded_arg
= arg
, const_arg
= 0;
3730 enum machine_mode mode_arg
= GET_MODE (arg
);
3731 rtx cheap_arg
, expensive_arg
;
3732 rtx replacements
[2];
3734 int old_cost
= COST_IN (XEXP (x
, i
), code
);
3736 /* Most arguments are cheap, so handle them specially. */
3737 switch (GET_CODE (arg
))
3740 /* This is the same as calling equiv_constant; it is duplicated
3742 if (REGNO_QTY_VALID_P (REGNO (arg
)))
3744 int arg_q
= REG_QTY (REGNO (arg
));
3745 struct qty_table_elem
*arg_ent
= &qty_table
[arg_q
];
3747 if (arg_ent
->const_rtx
!= NULL_RTX
3748 && GET_CODE (arg_ent
->const_rtx
) != REG
3749 && GET_CODE (arg_ent
->const_rtx
) != PLUS
)
3751 = gen_lowpart_if_possible (GET_MODE (arg
),
3752 arg_ent
->const_rtx
);
3767 folded_arg
= prev_insn_cc0
;
3768 mode_arg
= prev_insn_cc0_mode
;
3769 const_arg
= equiv_constant (folded_arg
);
3774 folded_arg
= fold_rtx (arg
, insn
);
3775 const_arg
= equiv_constant (folded_arg
);
3778 /* For the first three operands, see if the operand
3779 is constant or equivalent to a constant. */
3783 folded_arg0
= folded_arg
;
3784 const_arg0
= const_arg
;
3785 mode_arg0
= mode_arg
;
3788 folded_arg1
= folded_arg
;
3789 const_arg1
= const_arg
;
3792 const_arg2
= const_arg
;
3796 /* Pick the least expensive of the folded argument and an
3797 equivalent constant argument. */
3798 if (const_arg
== 0 || const_arg
== folded_arg
3799 || COST_IN (const_arg
, code
) > COST_IN (folded_arg
, code
))
3800 cheap_arg
= folded_arg
, expensive_arg
= const_arg
;
3802 cheap_arg
= const_arg
, expensive_arg
= folded_arg
;
3804 /* Try to replace the operand with the cheapest of the two
3805 possibilities. If it doesn't work and this is either of the first
3806 two operands of a commutative operation, try swapping them.
3807 If THAT fails, try the more expensive, provided it is cheaper
3808 than what is already there. */
3810 if (cheap_arg
== XEXP (x
, i
))
3813 if (insn
== 0 && ! copied
)
3819 /* Order the replacements from cheapest to most expensive. */
3820 replacements
[0] = cheap_arg
;
3821 replacements
[1] = expensive_arg
;
3823 for (j
= 0; j
< 2 && replacements
[j
]; j
++)
3825 int new_cost
= COST_IN (replacements
[j
], code
);
3827 /* Stop if what existed before was cheaper. Prefer constants
3828 in the case of a tie. */
3829 if (new_cost
> old_cost
3830 || (new_cost
== old_cost
&& CONSTANT_P (XEXP (x
, i
))))
3833 if (validate_change (insn
, &XEXP (x
, i
), replacements
[j
], 0))
3836 if (code
== NE
|| code
== EQ
|| GET_RTX_CLASS (code
) == 'c'
3837 || code
== LTGT
|| code
== UNEQ
|| code
== ORDERED
3838 || code
== UNORDERED
)
3840 validate_change (insn
, &XEXP (x
, i
), XEXP (x
, 1 - i
), 1);
3841 validate_change (insn
, &XEXP (x
, 1 - i
), replacements
[j
], 1);
3843 if (apply_change_group ())
3845 /* Swap them back to be invalid so that this loop can
3846 continue and flag them to be swapped back later. */
3849 tem
= XEXP (x
, 0); XEXP (x
, 0) = XEXP (x
, 1);
3861 /* Don't try to fold inside of a vector of expressions.
3862 Doing nothing is harmless. */
3866 /* If a commutative operation, place a constant integer as the second
3867 operand unless the first operand is also a constant integer. Otherwise,
3868 place any constant second unless the first operand is also a constant. */
3870 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c'
3871 || code
== LTGT
|| code
== UNEQ
|| code
== ORDERED
3872 || code
== UNORDERED
)
3874 if (must_swap
|| (const_arg0
3876 || (GET_CODE (const_arg0
) == CONST_INT
3877 && GET_CODE (const_arg1
) != CONST_INT
))))
3879 rtx tem
= XEXP (x
, 0);
3881 if (insn
== 0 && ! copied
)
3887 validate_change (insn
, &XEXP (x
, 0), XEXP (x
, 1), 1);
3888 validate_change (insn
, &XEXP (x
, 1), tem
, 1);
3889 if (apply_change_group ())
3891 tem
= const_arg0
, const_arg0
= const_arg1
, const_arg1
= tem
;
3892 tem
= folded_arg0
, folded_arg0
= folded_arg1
, folded_arg1
= tem
;
3897 /* If X is an arithmetic operation, see if we can simplify it. */
3899 switch (GET_RTX_CLASS (code
))
3905 /* We can't simplify extension ops unless we know the
3907 if ((code
== ZERO_EXTEND
|| code
== SIGN_EXTEND
)
3908 && mode_arg0
== VOIDmode
)
3911 /* If we had a CONST, strip it off and put it back later if we
3913 if (const_arg0
!= 0 && GET_CODE (const_arg0
) == CONST
)
3914 is_const
= 1, const_arg0
= XEXP (const_arg0
, 0);
3916 new = simplify_unary_operation (code
, mode
,
3917 const_arg0
? const_arg0
: folded_arg0
,
3919 if (new != 0 && is_const
)
3920 new = gen_rtx_CONST (mode
, new);
3925 /* See what items are actually being compared and set FOLDED_ARG[01]
3926 to those values and CODE to the actual comparison code. If any are
3927 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3928 do anything if both operands are already known to be constant. */
3930 if (const_arg0
== 0 || const_arg1
== 0)
3932 struct table_elt
*p0
, *p1
;
3933 rtx true_rtx
= const_true_rtx
, false_rtx
= const0_rtx
;
3934 enum machine_mode mode_arg1
;
3936 #ifdef FLOAT_STORE_FLAG_VALUE
3937 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
3939 true_rtx
= (CONST_DOUBLE_FROM_REAL_VALUE
3940 (FLOAT_STORE_FLAG_VALUE (mode
), mode
));
3941 false_rtx
= CONST0_RTX (mode
);
3945 code
= find_comparison_args (code
, &folded_arg0
, &folded_arg1
,
3946 &mode_arg0
, &mode_arg1
);
3947 const_arg0
= equiv_constant (folded_arg0
);
3948 const_arg1
= equiv_constant (folded_arg1
);
3950 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3951 what kinds of things are being compared, so we can't do
3952 anything with this comparison. */
3954 if (mode_arg0
== VOIDmode
|| GET_MODE_CLASS (mode_arg0
) == MODE_CC
)
3957 /* If we do not now have two constants being compared, see
3958 if we can nevertheless deduce some things about the
3960 if (const_arg0
== 0 || const_arg1
== 0)
3962 /* Some addresses are known to be nonzero. We don't know
3963 their sign, but equality comparisons are known. */
3964 if (const_arg1
== const0_rtx
3965 && nonzero_address_p (folded_arg0
))
3969 else if (code
== NE
)
3973 /* See if the two operands are the same. */
3975 if (folded_arg0
== folded_arg1
3976 || (GET_CODE (folded_arg0
) == REG
3977 && GET_CODE (folded_arg1
) == REG
3978 && (REG_QTY (REGNO (folded_arg0
))
3979 == REG_QTY (REGNO (folded_arg1
))))
3980 || ((p0
= lookup (folded_arg0
,
3981 (safe_hash (folded_arg0
, mode_arg0
)
3982 & HASH_MASK
), mode_arg0
))
3983 && (p1
= lookup (folded_arg1
,
3984 (safe_hash (folded_arg1
, mode_arg0
)
3985 & HASH_MASK
), mode_arg0
))
3986 && p0
->first_same_value
== p1
->first_same_value
))
3988 /* Sadly two equal NaNs are not equivalent. */
3989 if (!HONOR_NANS (mode_arg0
))
3990 return ((code
== EQ
|| code
== LE
|| code
== GE
3991 || code
== LEU
|| code
== GEU
|| code
== UNEQ
3992 || code
== UNLE
|| code
== UNGE
3994 ? true_rtx
: false_rtx
);
3995 /* Take care for the FP compares we can resolve. */
3996 if (code
== UNEQ
|| code
== UNLE
|| code
== UNGE
)
3998 if (code
== LTGT
|| code
== LT
|| code
== GT
)
4002 /* If FOLDED_ARG0 is a register, see if the comparison we are
4003 doing now is either the same as we did before or the reverse
4004 (we only check the reverse if not floating-point). */
4005 else if (GET_CODE (folded_arg0
) == REG
)
4007 int qty
= REG_QTY (REGNO (folded_arg0
));
4009 if (REGNO_QTY_VALID_P (REGNO (folded_arg0
)))
4011 struct qty_table_elem
*ent
= &qty_table
[qty
];
4013 if ((comparison_dominates_p (ent
->comparison_code
, code
)
4014 || (! FLOAT_MODE_P (mode_arg0
)
4015 && comparison_dominates_p (ent
->comparison_code
,
4016 reverse_condition (code
))))
4017 && (rtx_equal_p (ent
->comparison_const
, folded_arg1
)
4019 && rtx_equal_p (ent
->comparison_const
,
4021 || (GET_CODE (folded_arg1
) == REG
4022 && (REG_QTY (REGNO (folded_arg1
)) == ent
->comparison_qty
))))
4023 return (comparison_dominates_p (ent
->comparison_code
, code
)
4024 ? true_rtx
: false_rtx
);
4030 /* If we are comparing against zero, see if the first operand is
4031 equivalent to an IOR with a constant. If so, we may be able to
4032 determine the result of this comparison. */
4034 if (const_arg1
== const0_rtx
)
4036 rtx y
= lookup_as_function (folded_arg0
, IOR
);
4040 && (inner_const
= equiv_constant (XEXP (y
, 1))) != 0
4041 && GET_CODE (inner_const
) == CONST_INT
4042 && INTVAL (inner_const
) != 0)
4044 int sign_bitnum
= GET_MODE_BITSIZE (mode_arg0
) - 1;
4045 int has_sign
= (HOST_BITS_PER_WIDE_INT
>= sign_bitnum
4046 && (INTVAL (inner_const
)
4047 & ((HOST_WIDE_INT
) 1 << sign_bitnum
)));
4048 rtx true_rtx
= const_true_rtx
, false_rtx
= const0_rtx
;
4050 #ifdef FLOAT_STORE_FLAG_VALUE
4051 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
4053 true_rtx
= (CONST_DOUBLE_FROM_REAL_VALUE
4054 (FLOAT_STORE_FLAG_VALUE (mode
), mode
));
4055 false_rtx
= CONST0_RTX (mode
);
4079 new = simplify_relational_operation (code
,
4080 (mode_arg0
!= VOIDmode
4082 : (GET_MODE (const_arg0
4086 ? GET_MODE (const_arg0
4089 : GET_MODE (const_arg1
4092 const_arg0
? const_arg0
: folded_arg0
,
4093 const_arg1
? const_arg1
: folded_arg1
);
4094 #ifdef FLOAT_STORE_FLAG_VALUE
4095 if (new != 0 && GET_MODE_CLASS (mode
) == MODE_FLOAT
)
4097 if (new == const0_rtx
)
4098 new = CONST0_RTX (mode
);
4100 new = (CONST_DOUBLE_FROM_REAL_VALUE
4101 (FLOAT_STORE_FLAG_VALUE (mode
), mode
));
4111 /* If the second operand is a LABEL_REF, see if the first is a MINUS
4112 with that LABEL_REF as its second operand. If so, the result is
4113 the first operand of that MINUS. This handles switches with an
4114 ADDR_DIFF_VEC table. */
4115 if (const_arg1
&& GET_CODE (const_arg1
) == LABEL_REF
)
4118 = GET_CODE (folded_arg0
) == MINUS
? folded_arg0
4119 : lookup_as_function (folded_arg0
, MINUS
);
4121 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
4122 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg1
, 0))
4125 /* Now try for a CONST of a MINUS like the above. */
4126 if ((y
= (GET_CODE (folded_arg0
) == CONST
? folded_arg0
4127 : lookup_as_function (folded_arg0
, CONST
))) != 0
4128 && GET_CODE (XEXP (y
, 0)) == MINUS
4129 && GET_CODE (XEXP (XEXP (y
, 0), 1)) == LABEL_REF
4130 && XEXP (XEXP (XEXP (y
, 0), 1), 0) == XEXP (const_arg1
, 0))
4131 return XEXP (XEXP (y
, 0), 0);
4134 /* Likewise if the operands are in the other order. */
4135 if (const_arg0
&& GET_CODE (const_arg0
) == LABEL_REF
)
4138 = GET_CODE (folded_arg1
) == MINUS
? folded_arg1
4139 : lookup_as_function (folded_arg1
, MINUS
);
4141 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
4142 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg0
, 0))
4145 /* Now try for a CONST of a MINUS like the above. */
4146 if ((y
= (GET_CODE (folded_arg1
) == CONST
? folded_arg1
4147 : lookup_as_function (folded_arg1
, CONST
))) != 0
4148 && GET_CODE (XEXP (y
, 0)) == MINUS
4149 && GET_CODE (XEXP (XEXP (y
, 0), 1)) == LABEL_REF
4150 && XEXP (XEXP (XEXP (y
, 0), 1), 0) == XEXP (const_arg0
, 0))
4151 return XEXP (XEXP (y
, 0), 0);
4154 /* If second operand is a register equivalent to a negative
4155 CONST_INT, see if we can find a register equivalent to the
4156 positive constant. Make a MINUS if so. Don't do this for
4157 a non-negative constant since we might then alternate between
4158 choosing positive and negative constants. Having the positive
4159 constant previously-used is the more common case. Be sure
4160 the resulting constant is non-negative; if const_arg1 were
4161 the smallest negative number this would overflow: depending
4162 on the mode, this would either just be the same value (and
4163 hence not save anything) or be incorrect. */
4164 if (const_arg1
!= 0 && GET_CODE (const_arg1
) == CONST_INT
4165 && INTVAL (const_arg1
) < 0
4166 /* This used to test
4168 -INTVAL (const_arg1) >= 0
4170 But The Sun V5.0 compilers mis-compiled that test. So
4171 instead we test for the problematic value in a more direct
4172 manner and hope the Sun compilers get it correct. */
4173 && INTVAL (const_arg1
) !=
4174 ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1))
4175 && GET_CODE (folded_arg1
) == REG
)
4177 rtx new_const
= GEN_INT (-INTVAL (const_arg1
));
4179 = lookup (new_const
, safe_hash (new_const
, mode
) & HASH_MASK
,
4183 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
4184 if (GET_CODE (p
->exp
) == REG
)
4185 return simplify_gen_binary (MINUS
, mode
, folded_arg0
,
4186 canon_reg (p
->exp
, NULL_RTX
));
4191 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
4192 If so, produce (PLUS Z C2-C). */
4193 if (const_arg1
!= 0 && GET_CODE (const_arg1
) == CONST_INT
)
4195 rtx y
= lookup_as_function (XEXP (x
, 0), PLUS
);
4196 if (y
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
4197 return fold_rtx (plus_constant (copy_rtx (y
),
4198 -INTVAL (const_arg1
)),
4205 case SMIN
: case SMAX
: case UMIN
: case UMAX
:
4206 case IOR
: case AND
: case XOR
:
4208 case ASHIFT
: case LSHIFTRT
: case ASHIFTRT
:
4209 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
4210 is known to be of similar form, we may be able to replace the
4211 operation with a combined operation. This may eliminate the
4212 intermediate operation if every use is simplified in this way.
4213 Note that the similar optimization done by combine.c only works
4214 if the intermediate operation's result has only one reference. */
4216 if (GET_CODE (folded_arg0
) == REG
4217 && const_arg1
&& GET_CODE (const_arg1
) == CONST_INT
)
4220 = (code
== ASHIFT
|| code
== ASHIFTRT
|| code
== LSHIFTRT
);
4221 rtx y
= lookup_as_function (folded_arg0
, code
);
4223 enum rtx_code associate_code
;
4227 || 0 == (inner_const
4228 = equiv_constant (fold_rtx (XEXP (y
, 1), 0)))
4229 || GET_CODE (inner_const
) != CONST_INT
4230 /* If we have compiled a statement like
4231 "if (x == (x & mask1))", and now are looking at
4232 "x & mask2", we will have a case where the first operand
4233 of Y is the same as our first operand. Unless we detect
4234 this case, an infinite loop will result. */
4235 || XEXP (y
, 0) == folded_arg0
)
4238 /* Don't associate these operations if they are a PLUS with the
4239 same constant and it is a power of two. These might be doable
4240 with a pre- or post-increment. Similarly for two subtracts of
4241 identical powers of two with post decrement. */
4243 if (code
== PLUS
&& INTVAL (const_arg1
) == INTVAL (inner_const
)
4244 && ((HAVE_PRE_INCREMENT
4245 && exact_log2 (INTVAL (const_arg1
)) >= 0)
4246 || (HAVE_POST_INCREMENT
4247 && exact_log2 (INTVAL (const_arg1
)) >= 0)
4248 || (HAVE_PRE_DECREMENT
4249 && exact_log2 (- INTVAL (const_arg1
)) >= 0)
4250 || (HAVE_POST_DECREMENT
4251 && exact_log2 (- INTVAL (const_arg1
)) >= 0)))
4254 /* Compute the code used to compose the constants. For example,
4255 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
4257 associate_code
= (is_shift
|| code
== MINUS
? PLUS
: code
);
4259 new_const
= simplify_binary_operation (associate_code
, mode
,
4260 const_arg1
, inner_const
);
4265 /* If we are associating shift operations, don't let this
4266 produce a shift of the size of the object or larger.
4267 This could occur when we follow a sign-extend by a right
4268 shift on a machine that does a sign-extend as a pair
4271 if (is_shift
&& GET_CODE (new_const
) == CONST_INT
4272 && INTVAL (new_const
) >= GET_MODE_BITSIZE (mode
))
4274 /* As an exception, we can turn an ASHIFTRT of this
4275 form into a shift of the number of bits - 1. */
4276 if (code
== ASHIFTRT
)
4277 new_const
= GEN_INT (GET_MODE_BITSIZE (mode
) - 1);
4282 y
= copy_rtx (XEXP (y
, 0));
4284 /* If Y contains our first operand (the most common way this
4285 can happen is if Y is a MEM), we would do into an infinite
4286 loop if we tried to fold it. So don't in that case. */
4288 if (! reg_mentioned_p (folded_arg0
, y
))
4289 y
= fold_rtx (y
, insn
);
4291 return simplify_gen_binary (code
, mode
, y
, new_const
);
4295 case DIV
: case UDIV
:
4296 /* ??? The associative optimization performed immediately above is
4297 also possible for DIV and UDIV using associate_code of MULT.
4298 However, we would need extra code to verify that the
4299 multiplication does not overflow, that is, there is no overflow
4300 in the calculation of new_const. */
4307 new = simplify_binary_operation (code
, mode
,
4308 const_arg0
? const_arg0
: folded_arg0
,
4309 const_arg1
? const_arg1
: folded_arg1
);
4313 /* (lo_sum (high X) X) is simply X. */
4314 if (code
== LO_SUM
&& const_arg0
!= 0
4315 && GET_CODE (const_arg0
) == HIGH
4316 && rtx_equal_p (XEXP (const_arg0
, 0), const_arg1
))
4322 new = simplify_ternary_operation (code
, mode
, mode_arg0
,
4323 const_arg0
? const_arg0
: folded_arg0
,
4324 const_arg1
? const_arg1
: folded_arg1
,
4325 const_arg2
? const_arg2
: XEXP (x
, 2));
4329 /* Eliminate CONSTANT_P_RTX if its constant. */
4330 if (code
== CONSTANT_P_RTX
)
4334 if (optimize
== 0 || !flag_gcse
)
4340 return new ? new : x
;
4343 /* Return a constant value currently equivalent to X.
4344 Return 0 if we don't know one. */
4350 if (GET_CODE (x
) == REG
4351 && REGNO_QTY_VALID_P (REGNO (x
)))
4353 int x_q
= REG_QTY (REGNO (x
));
4354 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
4356 if (x_ent
->const_rtx
)
4357 x
= gen_lowpart_if_possible (GET_MODE (x
), x_ent
->const_rtx
);
4360 if (x
== 0 || CONSTANT_P (x
))
4363 /* If X is a MEM, try to fold it outside the context of any insn to see if
4364 it might be equivalent to a constant. That handles the case where it
4365 is a constant-pool reference. Then try to look it up in the hash table
4366 in case it is something whose value we have seen before. */
4368 if (GET_CODE (x
) == MEM
)
4370 struct table_elt
*elt
;
4372 x
= fold_rtx (x
, NULL_RTX
);
4376 elt
= lookup (x
, safe_hash (x
, GET_MODE (x
)) & HASH_MASK
, GET_MODE (x
));
4380 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
4381 if (elt
->is_const
&& CONSTANT_P (elt
->exp
))
4388 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4389 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4390 least-significant part of X.
4391 MODE specifies how big a part of X to return.
4393 If the requested operation cannot be done, 0 is returned.
4395 This is similar to gen_lowpart in emit-rtl.c. */
4398 gen_lowpart_if_possible (mode
, x
)
4399 enum machine_mode mode
;
4402 rtx result
= gen_lowpart_common (mode
, x
);
4406 else if (GET_CODE (x
) == MEM
)
4408 /* This is the only other case we handle. */
4412 if (WORDS_BIG_ENDIAN
)
4413 offset
= (MAX (GET_MODE_SIZE (GET_MODE (x
)), UNITS_PER_WORD
)
4414 - MAX (GET_MODE_SIZE (mode
), UNITS_PER_WORD
));
4415 if (BYTES_BIG_ENDIAN
)
4416 /* Adjust the address so that the address-after-the-data is
4418 offset
-= (MIN (UNITS_PER_WORD
, GET_MODE_SIZE (mode
))
4419 - MIN (UNITS_PER_WORD
, GET_MODE_SIZE (GET_MODE (x
))));
4421 new = adjust_address_nv (x
, mode
, offset
);
4422 if (! memory_address_p (mode
, XEXP (new, 0)))
4431 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4432 branch. It will be zero if not.
4434 In certain cases, this can cause us to add an equivalence. For example,
4435 if we are following the taken case of
4437 we can add the fact that `i' and '2' are now equivalent.
4439 In any case, we can record that this comparison was passed. If the same
4440 comparison is seen later, we will know its value. */
4443 record_jump_equiv (insn
, taken
)
4447 int cond_known_true
;
4450 enum machine_mode mode
, mode0
, mode1
;
4451 int reversed_nonequality
= 0;
4454 /* Ensure this is the right kind of insn. */
4455 if (! any_condjump_p (insn
))
4457 set
= pc_set (insn
);
4459 /* See if this jump condition is known true or false. */
4461 cond_known_true
= (XEXP (SET_SRC (set
), 2) == pc_rtx
);
4463 cond_known_true
= (XEXP (SET_SRC (set
), 1) == pc_rtx
);
4465 /* Get the type of comparison being done and the operands being compared.
4466 If we had to reverse a non-equality condition, record that fact so we
4467 know that it isn't valid for floating-point. */
4468 code
= GET_CODE (XEXP (SET_SRC (set
), 0));
4469 op0
= fold_rtx (XEXP (XEXP (SET_SRC (set
), 0), 0), insn
);
4470 op1
= fold_rtx (XEXP (XEXP (SET_SRC (set
), 0), 1), insn
);
4472 code
= find_comparison_args (code
, &op0
, &op1
, &mode0
, &mode1
);
4473 if (! cond_known_true
)
4475 code
= reversed_comparison_code_parts (code
, op0
, op1
, insn
);
4477 /* Don't remember if we can't find the inverse. */
4478 if (code
== UNKNOWN
)
4482 /* The mode is the mode of the non-constant. */
4484 if (mode1
!= VOIDmode
)
4487 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
);
4490 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
4491 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
4492 Make any useful entries we can with that information. Called from
4493 above function and called recursively. */
4496 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
)
4498 enum machine_mode mode
;
4500 int reversed_nonequality
;
4502 unsigned op0_hash
, op1_hash
;
4503 int op0_in_memory
, op1_in_memory
;
4504 struct table_elt
*op0_elt
, *op1_elt
;
4506 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
4507 we know that they are also equal in the smaller mode (this is also
4508 true for all smaller modes whether or not there is a SUBREG, but
4509 is not worth testing for with no SUBREG). */
4511 /* Note that GET_MODE (op0) may not equal MODE. */
4512 if (code
== EQ
&& GET_CODE (op0
) == SUBREG
4513 && (GET_MODE_SIZE (GET_MODE (op0
))
4514 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
)))))
4516 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
4517 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
4519 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
4520 tem
? tem
: gen_rtx_SUBREG (inner_mode
, op1
, 0),
4521 reversed_nonequality
);
4524 if (code
== EQ
&& GET_CODE (op1
) == SUBREG
4525 && (GET_MODE_SIZE (GET_MODE (op1
))
4526 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
)))))
4528 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
4529 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
4531 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
4532 tem
? tem
: gen_rtx_SUBREG (inner_mode
, op0
, 0),
4533 reversed_nonequality
);
4536 /* Similarly, if this is an NE comparison, and either is a SUBREG
4537 making a smaller mode, we know the whole thing is also NE. */
4539 /* Note that GET_MODE (op0) may not equal MODE;
4540 if we test MODE instead, we can get an infinite recursion
4541 alternating between two modes each wider than MODE. */
4543 if (code
== NE
&& GET_CODE (op0
) == SUBREG
4544 && subreg_lowpart_p (op0
)
4545 && (GET_MODE_SIZE (GET_MODE (op0
))
4546 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
)))))
4548 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
4549 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
4551 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
4552 tem
? tem
: gen_rtx_SUBREG (inner_mode
, op1
, 0),
4553 reversed_nonequality
);
4556 if (code
== NE
&& GET_CODE (op1
) == SUBREG
4557 && subreg_lowpart_p (op1
)
4558 && (GET_MODE_SIZE (GET_MODE (op1
))
4559 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
)))))
4561 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
4562 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
4564 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
4565 tem
? tem
: gen_rtx_SUBREG (inner_mode
, op0
, 0),
4566 reversed_nonequality
);
4569 /* Hash both operands. */
4572 hash_arg_in_memory
= 0;
4573 op0_hash
= HASH (op0
, mode
);
4574 op0_in_memory
= hash_arg_in_memory
;
4580 hash_arg_in_memory
= 0;
4581 op1_hash
= HASH (op1
, mode
);
4582 op1_in_memory
= hash_arg_in_memory
;
4587 /* Look up both operands. */
4588 op0_elt
= lookup (op0
, op0_hash
, mode
);
4589 op1_elt
= lookup (op1
, op1_hash
, mode
);
4591 /* If both operands are already equivalent or if they are not in the
4592 table but are identical, do nothing. */
4593 if ((op0_elt
!= 0 && op1_elt
!= 0
4594 && op0_elt
->first_same_value
== op1_elt
->first_same_value
)
4595 || op0
== op1
|| rtx_equal_p (op0
, op1
))
4598 /* If we aren't setting two things equal all we can do is save this
4599 comparison. Similarly if this is floating-point. In the latter
4600 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
4601 If we record the equality, we might inadvertently delete code
4602 whose intent was to change -0 to +0. */
4604 if (code
!= EQ
|| FLOAT_MODE_P (GET_MODE (op0
)))
4606 struct qty_table_elem
*ent
;
4609 /* If we reversed a floating-point comparison, if OP0 is not a
4610 register, or if OP1 is neither a register or constant, we can't
4613 if (GET_CODE (op1
) != REG
)
4614 op1
= equiv_constant (op1
);
4616 if ((reversed_nonequality
&& FLOAT_MODE_P (mode
))
4617 || GET_CODE (op0
) != REG
|| op1
== 0)
4620 /* Put OP0 in the hash table if it isn't already. This gives it a
4621 new quantity number. */
4624 if (insert_regs (op0
, NULL
, 0))
4626 rehash_using_reg (op0
);
4627 op0_hash
= HASH (op0
, mode
);
4629 /* If OP0 is contained in OP1, this changes its hash code
4630 as well. Faster to rehash than to check, except
4631 for the simple case of a constant. */
4632 if (! CONSTANT_P (op1
))
4633 op1_hash
= HASH (op1
,mode
);
4636 op0_elt
= insert (op0
, NULL
, op0_hash
, mode
);
4637 op0_elt
->in_memory
= op0_in_memory
;
4640 qty
= REG_QTY (REGNO (op0
));
4641 ent
= &qty_table
[qty
];
4643 ent
->comparison_code
= code
;
4644 if (GET_CODE (op1
) == REG
)
4646 /* Look it up again--in case op0 and op1 are the same. */
4647 op1_elt
= lookup (op1
, op1_hash
, mode
);
4649 /* Put OP1 in the hash table so it gets a new quantity number. */
4652 if (insert_regs (op1
, NULL
, 0))
4654 rehash_using_reg (op1
);
4655 op1_hash
= HASH (op1
, mode
);
4658 op1_elt
= insert (op1
, NULL
, op1_hash
, mode
);
4659 op1_elt
->in_memory
= op1_in_memory
;
4662 ent
->comparison_const
= NULL_RTX
;
4663 ent
->comparison_qty
= REG_QTY (REGNO (op1
));
4667 ent
->comparison_const
= op1
;
4668 ent
->comparison_qty
= -1;
4674 /* If either side is still missing an equivalence, make it now,
4675 then merge the equivalences. */
4679 if (insert_regs (op0
, NULL
, 0))
4681 rehash_using_reg (op0
);
4682 op0_hash
= HASH (op0
, mode
);
4685 op0_elt
= insert (op0
, NULL
, op0_hash
, mode
);
4686 op0_elt
->in_memory
= op0_in_memory
;
4691 if (insert_regs (op1
, NULL
, 0))
4693 rehash_using_reg (op1
);
4694 op1_hash
= HASH (op1
, mode
);
4697 op1_elt
= insert (op1
, NULL
, op1_hash
, mode
);
4698 op1_elt
->in_memory
= op1_in_memory
;
4701 merge_equiv_classes (op0_elt
, op1_elt
);
4702 last_jump_equiv_class
= op0_elt
;
4705 /* CSE processing for one instruction.
4706 First simplify sources and addresses of all assignments
4707 in the instruction, using previously-computed equivalents values.
4708 Then install the new sources and destinations in the table
4709 of available values.
4711 If LIBCALL_INSN is nonzero, don't record any equivalence made in
4712 the insn. It means that INSN is inside libcall block. In this
4713 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
4715 /* Data on one SET contained in the instruction. */
4719 /* The SET rtx itself. */
4721 /* The SET_SRC of the rtx (the original value, if it is changing). */
4723 /* The hash-table element for the SET_SRC of the SET. */
4724 struct table_elt
*src_elt
;
4725 /* Hash value for the SET_SRC. */
4727 /* Hash value for the SET_DEST. */
4729 /* The SET_DEST, with SUBREG, etc., stripped. */
4731 /* Nonzero if the SET_SRC is in memory. */
4733 /* Nonzero if the SET_SRC contains something
4734 whose value cannot be predicted and understood. */
4736 /* Original machine mode, in case it becomes a CONST_INT. */
4737 enum machine_mode mode
;
4738 /* A constant equivalent for SET_SRC, if any. */
4740 /* Original SET_SRC value used for libcall notes. */
4742 /* Hash value of constant equivalent for SET_SRC. */
4743 unsigned src_const_hash
;
4744 /* Table entry for constant equivalent for SET_SRC, if any. */
4745 struct table_elt
*src_const_elt
;
4749 cse_insn (insn
, libcall_insn
)
4753 rtx x
= PATTERN (insn
);
4759 /* Records what this insn does to set CC0. */
4760 rtx this_insn_cc0
= 0;
4761 enum machine_mode this_insn_cc0_mode
= VOIDmode
;
4765 struct table_elt
*src_eqv_elt
= 0;
4766 int src_eqv_volatile
= 0;
4767 int src_eqv_in_memory
= 0;
4768 unsigned src_eqv_hash
= 0;
4770 struct set
*sets
= (struct set
*) 0;
4774 /* Find all the SETs and CLOBBERs in this instruction.
4775 Record all the SETs in the array `set' and count them.
4776 Also determine whether there is a CLOBBER that invalidates
4777 all memory references, or all references at varying addresses. */
4779 if (GET_CODE (insn
) == CALL_INSN
)
4781 for (tem
= CALL_INSN_FUNCTION_USAGE (insn
); tem
; tem
= XEXP (tem
, 1))
4783 if (GET_CODE (XEXP (tem
, 0)) == CLOBBER
)
4784 invalidate (SET_DEST (XEXP (tem
, 0)), VOIDmode
);
4785 XEXP (tem
, 0) = canon_reg (XEXP (tem
, 0), insn
);
4789 if (GET_CODE (x
) == SET
)
4791 sets
= (struct set
*) alloca (sizeof (struct set
));
4794 /* Ignore SETs that are unconditional jumps.
4795 They never need cse processing, so this does not hurt.
4796 The reason is not efficiency but rather
4797 so that we can test at the end for instructions
4798 that have been simplified to unconditional jumps
4799 and not be misled by unchanged instructions
4800 that were unconditional jumps to begin with. */
4801 if (SET_DEST (x
) == pc_rtx
4802 && GET_CODE (SET_SRC (x
)) == LABEL_REF
)
4805 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4806 The hard function value register is used only once, to copy to
4807 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4808 Ensure we invalidate the destination register. On the 80386 no
4809 other code would invalidate it since it is a fixed_reg.
4810 We need not check the return of apply_change_group; see canon_reg. */
4812 else if (GET_CODE (SET_SRC (x
)) == CALL
)
4814 canon_reg (SET_SRC (x
), insn
);
4815 apply_change_group ();
4816 fold_rtx (SET_SRC (x
), insn
);
4817 invalidate (SET_DEST (x
), VOIDmode
);
4822 else if (GET_CODE (x
) == PARALLEL
)
4824 int lim
= XVECLEN (x
, 0);
4826 sets
= (struct set
*) alloca (lim
* sizeof (struct set
));
4828 /* Find all regs explicitly clobbered in this insn,
4829 and ensure they are not replaced with any other regs
4830 elsewhere in this insn.
4831 When a reg that is clobbered is also used for input,
4832 we should presume that that is for a reason,
4833 and we should not substitute some other register
4834 which is not supposed to be clobbered.
4835 Therefore, this loop cannot be merged into the one below
4836 because a CALL may precede a CLOBBER and refer to the
4837 value clobbered. We must not let a canonicalization do
4838 anything in that case. */
4839 for (i
= 0; i
< lim
; i
++)
4841 rtx y
= XVECEXP (x
, 0, i
);
4842 if (GET_CODE (y
) == CLOBBER
)
4844 rtx clobbered
= XEXP (y
, 0);
4846 if (GET_CODE (clobbered
) == REG
4847 || GET_CODE (clobbered
) == SUBREG
)
4848 invalidate (clobbered
, VOIDmode
);
4849 else if (GET_CODE (clobbered
) == STRICT_LOW_PART
4850 || GET_CODE (clobbered
) == ZERO_EXTRACT
)
4851 invalidate (XEXP (clobbered
, 0), GET_MODE (clobbered
));
4855 for (i
= 0; i
< lim
; i
++)
4857 rtx y
= XVECEXP (x
, 0, i
);
4858 if (GET_CODE (y
) == SET
)
4860 /* As above, we ignore unconditional jumps and call-insns and
4861 ignore the result of apply_change_group. */
4862 if (GET_CODE (SET_SRC (y
)) == CALL
)
4864 canon_reg (SET_SRC (y
), insn
);
4865 apply_change_group ();
4866 fold_rtx (SET_SRC (y
), insn
);
4867 invalidate (SET_DEST (y
), VOIDmode
);
4869 else if (SET_DEST (y
) == pc_rtx
4870 && GET_CODE (SET_SRC (y
)) == LABEL_REF
)
4873 sets
[n_sets
++].rtl
= y
;
4875 else if (GET_CODE (y
) == CLOBBER
)
4877 /* If we clobber memory, canon the address.
4878 This does nothing when a register is clobbered
4879 because we have already invalidated the reg. */
4880 if (GET_CODE (XEXP (y
, 0)) == MEM
)
4881 canon_reg (XEXP (y
, 0), NULL_RTX
);
4883 else if (GET_CODE (y
) == USE
4884 && ! (GET_CODE (XEXP (y
, 0)) == REG
4885 && REGNO (XEXP (y
, 0)) < FIRST_PSEUDO_REGISTER
))
4886 canon_reg (y
, NULL_RTX
);
4887 else if (GET_CODE (y
) == CALL
)
4889 /* The result of apply_change_group can be ignored; see
4891 canon_reg (y
, insn
);
4892 apply_change_group ();
4897 else if (GET_CODE (x
) == CLOBBER
)
4899 if (GET_CODE (XEXP (x
, 0)) == MEM
)
4900 canon_reg (XEXP (x
, 0), NULL_RTX
);
4903 /* Canonicalize a USE of a pseudo register or memory location. */
4904 else if (GET_CODE (x
) == USE
4905 && ! (GET_CODE (XEXP (x
, 0)) == REG
4906 && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
))
4907 canon_reg (XEXP (x
, 0), NULL_RTX
);
4908 else if (GET_CODE (x
) == CALL
)
4910 /* The result of apply_change_group can be ignored; see canon_reg. */
4911 canon_reg (x
, insn
);
4912 apply_change_group ();
4916 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4917 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4918 is handled specially for this case, and if it isn't set, then there will
4919 be no equivalence for the destination. */
4920 if (n_sets
== 1 && REG_NOTES (insn
) != 0
4921 && (tem
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
)) != 0
4922 && (! rtx_equal_p (XEXP (tem
, 0), SET_SRC (sets
[0].rtl
))
4923 || GET_CODE (SET_DEST (sets
[0].rtl
)) == STRICT_LOW_PART
))
4925 src_eqv
= fold_rtx (canon_reg (XEXP (tem
, 0), NULL_RTX
), insn
);
4926 XEXP (tem
, 0) = src_eqv
;
4929 /* Canonicalize sources and addresses of destinations.
4930 We do this in a separate pass to avoid problems when a MATCH_DUP is
4931 present in the insn pattern. In that case, we want to ensure that
4932 we don't break the duplicate nature of the pattern. So we will replace
4933 both operands at the same time. Otherwise, we would fail to find an
4934 equivalent substitution in the loop calling validate_change below.
4936 We used to suppress canonicalization of DEST if it appears in SRC,
4937 but we don't do this any more. */
4939 for (i
= 0; i
< n_sets
; i
++)
4941 rtx dest
= SET_DEST (sets
[i
].rtl
);
4942 rtx src
= SET_SRC (sets
[i
].rtl
);
4943 rtx
new = canon_reg (src
, insn
);
4946 sets
[i
].orig_src
= src
;
4947 if ((GET_CODE (new) == REG
&& GET_CODE (src
) == REG
4948 && ((REGNO (new) < FIRST_PSEUDO_REGISTER
)
4949 != (REGNO (src
) < FIRST_PSEUDO_REGISTER
)))
4950 || (insn_code
= recog_memoized (insn
)) < 0
4951 || insn_data
[insn_code
].n_dups
> 0)
4952 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 1);
4954 SET_SRC (sets
[i
].rtl
) = new;
4956 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
4958 validate_change (insn
, &XEXP (dest
, 1),
4959 canon_reg (XEXP (dest
, 1), insn
), 1);
4960 validate_change (insn
, &XEXP (dest
, 2),
4961 canon_reg (XEXP (dest
, 2), insn
), 1);
4964 while (GET_CODE (dest
) == SUBREG
|| GET_CODE (dest
) == STRICT_LOW_PART
4965 || GET_CODE (dest
) == ZERO_EXTRACT
4966 || GET_CODE (dest
) == SIGN_EXTRACT
)
4967 dest
= XEXP (dest
, 0);
4969 if (GET_CODE (dest
) == MEM
)
4970 canon_reg (dest
, insn
);
4973 /* Now that we have done all the replacements, we can apply the change
4974 group and see if they all work. Note that this will cause some
4975 canonicalizations that would have worked individually not to be applied
4976 because some other canonicalization didn't work, but this should not
4979 The result of apply_change_group can be ignored; see canon_reg. */
4981 apply_change_group ();
4983 /* Set sets[i].src_elt to the class each source belongs to.
4984 Detect assignments from or to volatile things
4985 and set set[i] to zero so they will be ignored
4986 in the rest of this function.
4988 Nothing in this loop changes the hash table or the register chains. */
4990 for (i
= 0; i
< n_sets
; i
++)
4994 struct table_elt
*elt
= 0, *p
;
4995 enum machine_mode mode
;
4998 rtx src_related
= 0;
4999 struct table_elt
*src_const_elt
= 0;
5000 int src_cost
= MAX_COST
;
5001 int src_eqv_cost
= MAX_COST
;
5002 int src_folded_cost
= MAX_COST
;
5003 int src_related_cost
= MAX_COST
;
5004 int src_elt_cost
= MAX_COST
;
5005 int src_regcost
= MAX_COST
;
5006 int src_eqv_regcost
= MAX_COST
;
5007 int src_folded_regcost
= MAX_COST
;
5008 int src_related_regcost
= MAX_COST
;
5009 int src_elt_regcost
= MAX_COST
;
5010 /* Set nonzero if we need to call force_const_mem on with the
5011 contents of src_folded before using it. */
5012 int src_folded_force_flag
= 0;
5014 dest
= SET_DEST (sets
[i
].rtl
);
5015 src
= SET_SRC (sets
[i
].rtl
);
5017 /* If SRC is a constant that has no machine mode,
5018 hash it with the destination's machine mode.
5019 This way we can keep different modes separate. */
5021 mode
= GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
5022 sets
[i
].mode
= mode
;
5026 enum machine_mode eqvmode
= mode
;
5027 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5028 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
5030 hash_arg_in_memory
= 0;
5031 src_eqv_hash
= HASH (src_eqv
, eqvmode
);
5033 /* Find the equivalence class for the equivalent expression. */
5036 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash
, eqvmode
);
5038 src_eqv_volatile
= do_not_record
;
5039 src_eqv_in_memory
= hash_arg_in_memory
;
5042 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
5043 value of the INNER register, not the destination. So it is not
5044 a valid substitution for the source. But save it for later. */
5045 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5048 src_eqv_here
= src_eqv
;
5050 /* Simplify and foldable subexpressions in SRC. Then get the fully-
5051 simplified result, which may not necessarily be valid. */
5052 src_folded
= fold_rtx (src
, insn
);
5055 /* ??? This caused bad code to be generated for the m68k port with -O2.
5056 Suppose src is (CONST_INT -1), and that after truncation src_folded
5057 is (CONST_INT 3). Suppose src_folded is then used for src_const.
5058 At the end we will add src and src_const to the same equivalence
5059 class. We now have 3 and -1 on the same equivalence class. This
5060 causes later instructions to be mis-optimized. */
5061 /* If storing a constant in a bitfield, pre-truncate the constant
5062 so we will be able to record it later. */
5063 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
5064 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
5066 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
5068 if (GET_CODE (src
) == CONST_INT
5069 && GET_CODE (width
) == CONST_INT
5070 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
5071 && (INTVAL (src
) & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
5073 = GEN_INT (INTVAL (src
) & (((HOST_WIDE_INT
) 1
5074 << INTVAL (width
)) - 1));
5078 /* Compute SRC's hash code, and also notice if it
5079 should not be recorded at all. In that case,
5080 prevent any further processing of this assignment. */
5082 hash_arg_in_memory
= 0;
5085 sets
[i
].src_hash
= HASH (src
, mode
);
5086 sets
[i
].src_volatile
= do_not_record
;
5087 sets
[i
].src_in_memory
= hash_arg_in_memory
;
5089 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
5090 a pseudo, do not record SRC. Using SRC as a replacement for
5091 anything else will be incorrect in that situation. Note that
5092 this usually occurs only for stack slots, in which case all the
5093 RTL would be referring to SRC, so we don't lose any optimization
5094 opportunities by not having SRC in the hash table. */
5096 if (GET_CODE (src
) == MEM
5097 && find_reg_note (insn
, REG_EQUIV
, NULL_RTX
) != 0
5098 && GET_CODE (dest
) == REG
5099 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
5100 sets
[i
].src_volatile
= 1;
5103 /* It is no longer clear why we used to do this, but it doesn't
5104 appear to still be needed. So let's try without it since this
5105 code hurts cse'ing widened ops. */
5106 /* If source is a perverse subreg (such as QI treated as an SI),
5107 treat it as volatile. It may do the work of an SI in one context
5108 where the extra bits are not being used, but cannot replace an SI
5110 if (GET_CODE (src
) == SUBREG
5111 && (GET_MODE_SIZE (GET_MODE (src
))
5112 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))))
5113 sets
[i
].src_volatile
= 1;
5116 /* Locate all possible equivalent forms for SRC. Try to replace
5117 SRC in the insn with each cheaper equivalent.
5119 We have the following types of equivalents: SRC itself, a folded
5120 version, a value given in a REG_EQUAL note, or a value related
5123 Each of these equivalents may be part of an additional class
5124 of equivalents (if more than one is in the table, they must be in
5125 the same class; we check for this).
5127 If the source is volatile, we don't do any table lookups.
5129 We note any constant equivalent for possible later use in a
5132 if (!sets
[i
].src_volatile
)
5133 elt
= lookup (src
, sets
[i
].src_hash
, mode
);
5135 sets
[i
].src_elt
= elt
;
5137 if (elt
&& src_eqv_here
&& src_eqv_elt
)
5139 if (elt
->first_same_value
!= src_eqv_elt
->first_same_value
)
5141 /* The REG_EQUAL is indicating that two formerly distinct
5142 classes are now equivalent. So merge them. */
5143 merge_equiv_classes (elt
, src_eqv_elt
);
5144 src_eqv_hash
= HASH (src_eqv
, elt
->mode
);
5145 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash
, elt
->mode
);
5151 else if (src_eqv_elt
)
5154 /* Try to find a constant somewhere and record it in `src_const'.
5155 Record its table element, if any, in `src_const_elt'. Look in
5156 any known equivalences first. (If the constant is not in the
5157 table, also set `sets[i].src_const_hash'). */
5159 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
5163 src_const_elt
= elt
;
5168 && (CONSTANT_P (src_folded
)
5169 /* Consider (minus (label_ref L1) (label_ref L2)) as
5170 "constant" here so we will record it. This allows us
5171 to fold switch statements when an ADDR_DIFF_VEC is used. */
5172 || (GET_CODE (src_folded
) == MINUS
5173 && GET_CODE (XEXP (src_folded
, 0)) == LABEL_REF
5174 && GET_CODE (XEXP (src_folded
, 1)) == LABEL_REF
)))
5175 src_const
= src_folded
, src_const_elt
= elt
;
5176 else if (src_const
== 0 && src_eqv_here
&& CONSTANT_P (src_eqv_here
))
5177 src_const
= src_eqv_here
, src_const_elt
= src_eqv_elt
;
5179 /* If we don't know if the constant is in the table, get its
5180 hash code and look it up. */
5181 if (src_const
&& src_const_elt
== 0)
5183 sets
[i
].src_const_hash
= HASH (src_const
, mode
);
5184 src_const_elt
= lookup (src_const
, sets
[i
].src_const_hash
, mode
);
5187 sets
[i
].src_const
= src_const
;
5188 sets
[i
].src_const_elt
= src_const_elt
;
5190 /* If the constant and our source are both in the table, mark them as
5191 equivalent. Otherwise, if a constant is in the table but the source
5192 isn't, set ELT to it. */
5193 if (src_const_elt
&& elt
5194 && src_const_elt
->first_same_value
!= elt
->first_same_value
)
5195 merge_equiv_classes (elt
, src_const_elt
);
5196 else if (src_const_elt
&& elt
== 0)
5197 elt
= src_const_elt
;
5199 /* See if there is a register linearly related to a constant
5200 equivalent of SRC. */
5202 && (GET_CODE (src_const
) == CONST
5203 || (src_const_elt
&& src_const_elt
->related_value
!= 0)))
5205 src_related
= use_related_value (src_const
, src_const_elt
);
5208 struct table_elt
*src_related_elt
5209 = lookup (src_related
, HASH (src_related
, mode
), mode
);
5210 if (src_related_elt
&& elt
)
5212 if (elt
->first_same_value
5213 != src_related_elt
->first_same_value
)
5214 /* This can occur when we previously saw a CONST
5215 involving a SYMBOL_REF and then see the SYMBOL_REF
5216 twice. Merge the involved classes. */
5217 merge_equiv_classes (elt
, src_related_elt
);
5220 src_related_elt
= 0;
5222 else if (src_related_elt
&& elt
== 0)
5223 elt
= src_related_elt
;
5227 /* See if we have a CONST_INT that is already in a register in a
5230 if (src_const
&& src_related
== 0 && GET_CODE (src_const
) == CONST_INT
5231 && GET_MODE_CLASS (mode
) == MODE_INT
5232 && GET_MODE_BITSIZE (mode
) < BITS_PER_WORD
)
5234 enum machine_mode wider_mode
;
5236 for (wider_mode
= GET_MODE_WIDER_MODE (mode
);
5237 GET_MODE_BITSIZE (wider_mode
) <= BITS_PER_WORD
5238 && src_related
== 0;
5239 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
5241 struct table_elt
*const_elt
5242 = lookup (src_const
, HASH (src_const
, wider_mode
), wider_mode
);
5247 for (const_elt
= const_elt
->first_same_value
;
5248 const_elt
; const_elt
= const_elt
->next_same_value
)
5249 if (GET_CODE (const_elt
->exp
) == REG
)
5251 src_related
= gen_lowpart_if_possible (mode
,
5258 /* Another possibility is that we have an AND with a constant in
5259 a mode narrower than a word. If so, it might have been generated
5260 as part of an "if" which would narrow the AND. If we already
5261 have done the AND in a wider mode, we can use a SUBREG of that
5264 if (flag_expensive_optimizations
&& ! src_related
5265 && GET_CODE (src
) == AND
&& GET_CODE (XEXP (src
, 1)) == CONST_INT
5266 && GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
5268 enum machine_mode tmode
;
5269 rtx new_and
= gen_rtx_AND (VOIDmode
, NULL_RTX
, XEXP (src
, 1));
5271 for (tmode
= GET_MODE_WIDER_MODE (mode
);
5272 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
5273 tmode
= GET_MODE_WIDER_MODE (tmode
))
5275 rtx inner
= gen_lowpart_if_possible (tmode
, XEXP (src
, 0));
5276 struct table_elt
*larger_elt
;
5280 PUT_MODE (new_and
, tmode
);
5281 XEXP (new_and
, 0) = inner
;
5282 larger_elt
= lookup (new_and
, HASH (new_and
, tmode
), tmode
);
5283 if (larger_elt
== 0)
5286 for (larger_elt
= larger_elt
->first_same_value
;
5287 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
5288 if (GET_CODE (larger_elt
->exp
) == REG
)
5291 = gen_lowpart_if_possible (mode
, larger_elt
->exp
);
5301 #ifdef LOAD_EXTEND_OP
5302 /* See if a MEM has already been loaded with a widening operation;
5303 if it has, we can use a subreg of that. Many CISC machines
5304 also have such operations, but this is only likely to be
5305 beneficial these machines. */
5307 if (flag_expensive_optimizations
&& src_related
== 0
5308 && (GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
5309 && GET_MODE_CLASS (mode
) == MODE_INT
5310 && GET_CODE (src
) == MEM
&& ! do_not_record
5311 && LOAD_EXTEND_OP (mode
) != NIL
)
5313 enum machine_mode tmode
;
5315 /* Set what we are trying to extend and the operation it might
5316 have been extended with. */
5317 PUT_CODE (memory_extend_rtx
, LOAD_EXTEND_OP (mode
));
5318 XEXP (memory_extend_rtx
, 0) = src
;
5320 for (tmode
= GET_MODE_WIDER_MODE (mode
);
5321 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
5322 tmode
= GET_MODE_WIDER_MODE (tmode
))
5324 struct table_elt
*larger_elt
;
5326 PUT_MODE (memory_extend_rtx
, tmode
);
5327 larger_elt
= lookup (memory_extend_rtx
,
5328 HASH (memory_extend_rtx
, tmode
), tmode
);
5329 if (larger_elt
== 0)
5332 for (larger_elt
= larger_elt
->first_same_value
;
5333 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
5334 if (GET_CODE (larger_elt
->exp
) == REG
)
5336 src_related
= gen_lowpart_if_possible (mode
,
5345 #endif /* LOAD_EXTEND_OP */
5347 if (src
== src_folded
)
5350 /* At this point, ELT, if nonzero, points to a class of expressions
5351 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5352 and SRC_RELATED, if nonzero, each contain additional equivalent
5353 expressions. Prune these latter expressions by deleting expressions
5354 already in the equivalence class.
5356 Check for an equivalent identical to the destination. If found,
5357 this is the preferred equivalent since it will likely lead to
5358 elimination of the insn. Indicate this by placing it in
5362 elt
= elt
->first_same_value
;
5363 for (p
= elt
; p
; p
= p
->next_same_value
)
5365 enum rtx_code code
= GET_CODE (p
->exp
);
5367 /* If the expression is not valid, ignore it. Then we do not
5368 have to check for validity below. In most cases, we can use
5369 `rtx_equal_p', since canonicalization has already been done. */
5370 if (code
!= REG
&& ! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
5373 /* Also skip paradoxical subregs, unless that's what we're
5376 && (GET_MODE_SIZE (GET_MODE (p
->exp
))
5377 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p
->exp
))))
5379 && GET_CODE (src
) == SUBREG
5380 && GET_MODE (src
) == GET_MODE (p
->exp
)
5381 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))
5382 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p
->exp
))))))
5385 if (src
&& GET_CODE (src
) == code
&& rtx_equal_p (src
, p
->exp
))
5387 else if (src_folded
&& GET_CODE (src_folded
) == code
5388 && rtx_equal_p (src_folded
, p
->exp
))
5390 else if (src_eqv_here
&& GET_CODE (src_eqv_here
) == code
5391 && rtx_equal_p (src_eqv_here
, p
->exp
))
5393 else if (src_related
&& GET_CODE (src_related
) == code
5394 && rtx_equal_p (src_related
, p
->exp
))
5397 /* This is the same as the destination of the insns, we want
5398 to prefer it. Copy it to src_related. The code below will
5399 then give it a negative cost. */
5400 if (GET_CODE (dest
) == code
&& rtx_equal_p (p
->exp
, dest
))
5404 /* Find the cheapest valid equivalent, trying all the available
5405 possibilities. Prefer items not in the hash table to ones
5406 that are when they are equal cost. Note that we can never
5407 worsen an insn as the current contents will also succeed.
5408 If we find an equivalent identical to the destination, use it as best,
5409 since this insn will probably be eliminated in that case. */
5412 if (rtx_equal_p (src
, dest
))
5413 src_cost
= src_regcost
= -1;
5416 src_cost
= COST (src
);
5417 src_regcost
= approx_reg_cost (src
);
5423 if (rtx_equal_p (src_eqv_here
, dest
))
5424 src_eqv_cost
= src_eqv_regcost
= -1;
5427 src_eqv_cost
= COST (src_eqv_here
);
5428 src_eqv_regcost
= approx_reg_cost (src_eqv_here
);
5434 if (rtx_equal_p (src_folded
, dest
))
5435 src_folded_cost
= src_folded_regcost
= -1;
5438 src_folded_cost
= COST (src_folded
);
5439 src_folded_regcost
= approx_reg_cost (src_folded
);
5445 if (rtx_equal_p (src_related
, dest
))
5446 src_related_cost
= src_related_regcost
= -1;
5449 src_related_cost
= COST (src_related
);
5450 src_related_regcost
= approx_reg_cost (src_related
);
5454 /* If this was an indirect jump insn, a known label will really be
5455 cheaper even though it looks more expensive. */
5456 if (dest
== pc_rtx
&& src_const
&& GET_CODE (src_const
) == LABEL_REF
)
5457 src_folded
= src_const
, src_folded_cost
= src_folded_regcost
= -1;
5459 /* Terminate loop when replacement made. This must terminate since
5460 the current contents will be tested and will always be valid. */
5465 /* Skip invalid entries. */
5466 while (elt
&& GET_CODE (elt
->exp
) != REG
5467 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
5468 elt
= elt
->next_same_value
;
5470 /* A paradoxical subreg would be bad here: it'll be the right
5471 size, but later may be adjusted so that the upper bits aren't
5472 what we want. So reject it. */
5474 && GET_CODE (elt
->exp
) == SUBREG
5475 && (GET_MODE_SIZE (GET_MODE (elt
->exp
))
5476 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt
->exp
))))
5477 /* It is okay, though, if the rtx we're trying to match
5478 will ignore any of the bits we can't predict. */
5480 && GET_CODE (src
) == SUBREG
5481 && GET_MODE (src
) == GET_MODE (elt
->exp
)
5482 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))
5483 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt
->exp
))))))
5485 elt
= elt
->next_same_value
;
5491 src_elt_cost
= elt
->cost
;
5492 src_elt_regcost
= elt
->regcost
;
5495 /* Find cheapest and skip it for the next time. For items
5496 of equal cost, use this order:
5497 src_folded, src, src_eqv, src_related and hash table entry. */
5499 && preferrable (src_folded_cost
, src_folded_regcost
,
5500 src_cost
, src_regcost
) <= 0
5501 && preferrable (src_folded_cost
, src_folded_regcost
,
5502 src_eqv_cost
, src_eqv_regcost
) <= 0
5503 && preferrable (src_folded_cost
, src_folded_regcost
,
5504 src_related_cost
, src_related_regcost
) <= 0
5505 && preferrable (src_folded_cost
, src_folded_regcost
,
5506 src_elt_cost
, src_elt_regcost
) <= 0)
5508 trial
= src_folded
, src_folded_cost
= MAX_COST
;
5509 if (src_folded_force_flag
)
5510 trial
= force_const_mem (mode
, trial
);
5513 && preferrable (src_cost
, src_regcost
,
5514 src_eqv_cost
, src_eqv_regcost
) <= 0
5515 && preferrable (src_cost
, src_regcost
,
5516 src_related_cost
, src_related_regcost
) <= 0
5517 && preferrable (src_cost
, src_regcost
,
5518 src_elt_cost
, src_elt_regcost
) <= 0)
5519 trial
= src
, src_cost
= MAX_COST
;
5520 else if (src_eqv_here
5521 && preferrable (src_eqv_cost
, src_eqv_regcost
,
5522 src_related_cost
, src_related_regcost
) <= 0
5523 && preferrable (src_eqv_cost
, src_eqv_regcost
,
5524 src_elt_cost
, src_elt_regcost
) <= 0)
5525 trial
= copy_rtx (src_eqv_here
), src_eqv_cost
= MAX_COST
;
5526 else if (src_related
5527 && preferrable (src_related_cost
, src_related_regcost
,
5528 src_elt_cost
, src_elt_regcost
) <= 0)
5529 trial
= copy_rtx (src_related
), src_related_cost
= MAX_COST
;
5532 trial
= copy_rtx (elt
->exp
);
5533 elt
= elt
->next_same_value
;
5534 src_elt_cost
= MAX_COST
;
5537 /* We don't normally have an insn matching (set (pc) (pc)), so
5538 check for this separately here. We will delete such an
5541 For other cases such as a table jump or conditional jump
5542 where we know the ultimate target, go ahead and replace the
5543 operand. While that may not make a valid insn, we will
5544 reemit the jump below (and also insert any necessary
5546 if (n_sets
== 1 && dest
== pc_rtx
5548 || (GET_CODE (trial
) == LABEL_REF
5549 && ! condjump_p (insn
))))
5551 SET_SRC (sets
[i
].rtl
) = trial
;
5552 cse_jumps_altered
= 1;
5556 /* Look for a substitution that makes a valid insn. */
5557 else if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), trial
, 0))
5559 rtx
new = canon_reg (SET_SRC (sets
[i
].rtl
), insn
);
5561 /* If we just made a substitution inside a libcall, then we
5562 need to make the same substitution in any notes attached
5563 to the RETVAL insn. */
5565 && (GET_CODE (sets
[i
].orig_src
) == REG
5566 || GET_CODE (sets
[i
].orig_src
) == SUBREG
5567 || GET_CODE (sets
[i
].orig_src
) == MEM
))
5568 replace_rtx (REG_NOTES (libcall_insn
), sets
[i
].orig_src
,
5571 /* The result of apply_change_group can be ignored; see
5574 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 1);
5575 apply_change_group ();
5579 /* If we previously found constant pool entries for
5580 constants and this is a constant, try making a
5581 pool entry. Put it in src_folded unless we already have done
5582 this since that is where it likely came from. */
5584 else if (constant_pool_entries_cost
5585 && CONSTANT_P (trial
)
5586 /* Reject cases that will abort in decode_rtx_const.
5587 On the alpha when simplifying a switch, we get
5588 (const (truncate (minus (label_ref) (label_ref)))). */
5589 && ! (GET_CODE (trial
) == CONST
5590 && GET_CODE (XEXP (trial
, 0)) == TRUNCATE
)
5591 /* Likewise on IA-64, except without the truncate. */
5592 && ! (GET_CODE (trial
) == CONST
5593 && GET_CODE (XEXP (trial
, 0)) == MINUS
5594 && GET_CODE (XEXP (XEXP (trial
, 0), 0)) == LABEL_REF
5595 && GET_CODE (XEXP (XEXP (trial
, 0), 1)) == LABEL_REF
)
5597 || (GET_CODE (src_folded
) != MEM
5598 && ! src_folded_force_flag
))
5599 && GET_MODE_CLASS (mode
) != MODE_CC
5600 && mode
!= VOIDmode
)
5602 src_folded_force_flag
= 1;
5604 src_folded_cost
= constant_pool_entries_cost
;
5608 src
= SET_SRC (sets
[i
].rtl
);
5610 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5611 However, there is an important exception: If both are registers
5612 that are not the head of their equivalence class, replace SET_SRC
5613 with the head of the class. If we do not do this, we will have
5614 both registers live over a portion of the basic block. This way,
5615 their lifetimes will likely abut instead of overlapping. */
5616 if (GET_CODE (dest
) == REG
5617 && REGNO_QTY_VALID_P (REGNO (dest
)))
5619 int dest_q
= REG_QTY (REGNO (dest
));
5620 struct qty_table_elem
*dest_ent
= &qty_table
[dest_q
];
5622 if (dest_ent
->mode
== GET_MODE (dest
)
5623 && dest_ent
->first_reg
!= REGNO (dest
)
5624 && GET_CODE (src
) == REG
&& REGNO (src
) == REGNO (dest
)
5625 /* Don't do this if the original insn had a hard reg as
5626 SET_SRC or SET_DEST. */
5627 && (GET_CODE (sets
[i
].src
) != REG
5628 || REGNO (sets
[i
].src
) >= FIRST_PSEUDO_REGISTER
)
5629 && (GET_CODE (dest
) != REG
|| REGNO (dest
) >= FIRST_PSEUDO_REGISTER
))
5630 /* We can't call canon_reg here because it won't do anything if
5631 SRC is a hard register. */
5633 int src_q
= REG_QTY (REGNO (src
));
5634 struct qty_table_elem
*src_ent
= &qty_table
[src_q
];
5635 int first
= src_ent
->first_reg
;
5637 = (first
>= FIRST_PSEUDO_REGISTER
5638 ? regno_reg_rtx
[first
] : gen_rtx_REG (GET_MODE (src
), first
));
5640 /* We must use validate-change even for this, because this
5641 might be a special no-op instruction, suitable only to
5643 if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new_src
, 0))
5646 /* If we had a constant that is cheaper than what we are now
5647 setting SRC to, use that constant. We ignored it when we
5648 thought we could make this into a no-op. */
5649 if (src_const
&& COST (src_const
) < COST (src
)
5650 && validate_change (insn
, &SET_SRC (sets
[i
].rtl
),
5657 /* If we made a change, recompute SRC values. */
5658 if (src
!= sets
[i
].src
)
5662 hash_arg_in_memory
= 0;
5664 sets
[i
].src_hash
= HASH (src
, mode
);
5665 sets
[i
].src_volatile
= do_not_record
;
5666 sets
[i
].src_in_memory
= hash_arg_in_memory
;
5667 sets
[i
].src_elt
= lookup (src
, sets
[i
].src_hash
, mode
);
5670 /* If this is a single SET, we are setting a register, and we have an
5671 equivalent constant, we want to add a REG_NOTE. We don't want
5672 to write a REG_EQUAL note for a constant pseudo since verifying that
5673 that pseudo hasn't been eliminated is a pain. Such a note also
5674 won't help anything.
5676 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
5677 which can be created for a reference to a compile time computable
5678 entry in a jump table. */
5680 if (n_sets
== 1 && src_const
&& GET_CODE (dest
) == REG
5681 && GET_CODE (src_const
) != REG
5682 && ! (GET_CODE (src_const
) == CONST
5683 && GET_CODE (XEXP (src_const
, 0)) == MINUS
5684 && GET_CODE (XEXP (XEXP (src_const
, 0), 0)) == LABEL_REF
5685 && GET_CODE (XEXP (XEXP (src_const
, 0), 1)) == LABEL_REF
))
5687 /* Make sure that the rtx is not shared with any other insn. */
5688 src_const
= copy_rtx (src_const
);
5690 /* Record the actual constant value in a REG_EQUAL note, making
5691 a new one if one does not already exist. */
5692 set_unique_reg_note (insn
, REG_EQUAL
, src_const
);
5694 /* If storing a constant value in a register that
5695 previously held the constant value 0,
5696 record this fact with a REG_WAS_0 note on this insn.
5698 Note that the *register* is required to have previously held 0,
5699 not just any register in the quantity and we must point to the
5700 insn that set that register to zero.
5702 Rather than track each register individually, we just see if
5703 the last set for this quantity was for this register. */
5705 if (REGNO_QTY_VALID_P (REGNO (dest
)))
5707 int dest_q
= REG_QTY (REGNO (dest
));
5708 struct qty_table_elem
*dest_ent
= &qty_table
[dest_q
];
5710 if (dest_ent
->const_rtx
== const0_rtx
)
5712 /* See if we previously had a REG_WAS_0 note. */
5713 rtx note
= find_reg_note (insn
, REG_WAS_0
, NULL_RTX
);
5714 rtx const_insn
= dest_ent
->const_insn
;
5716 if ((tem
= single_set (const_insn
)) != 0
5717 && rtx_equal_p (SET_DEST (tem
), dest
))
5720 XEXP (note
, 0) = const_insn
;
5723 = gen_rtx_INSN_LIST (REG_WAS_0
, const_insn
,
5730 /* Now deal with the destination. */
5733 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5734 to the MEM or REG within it. */
5735 while (GET_CODE (dest
) == SIGN_EXTRACT
5736 || GET_CODE (dest
) == ZERO_EXTRACT
5737 || GET_CODE (dest
) == SUBREG
5738 || GET_CODE (dest
) == STRICT_LOW_PART
)
5739 dest
= XEXP (dest
, 0);
5741 sets
[i
].inner_dest
= dest
;
5743 if (GET_CODE (dest
) == MEM
)
5745 #ifdef PUSH_ROUNDING
5746 /* Stack pushes invalidate the stack pointer. */
5747 rtx addr
= XEXP (dest
, 0);
5748 if (GET_RTX_CLASS (GET_CODE (addr
)) == 'a'
5749 && XEXP (addr
, 0) == stack_pointer_rtx
)
5750 invalidate (stack_pointer_rtx
, Pmode
);
5752 dest
= fold_rtx (dest
, insn
);
5755 /* Compute the hash code of the destination now,
5756 before the effects of this instruction are recorded,
5757 since the register values used in the address computation
5758 are those before this instruction. */
5759 sets
[i
].dest_hash
= HASH (dest
, mode
);
5761 /* Don't enter a bit-field in the hash table
5762 because the value in it after the store
5763 may not equal what was stored, due to truncation. */
5765 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
5766 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
5768 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
5770 if (src_const
!= 0 && GET_CODE (src_const
) == CONST_INT
5771 && GET_CODE (width
) == CONST_INT
5772 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
5773 && ! (INTVAL (src_const
)
5774 & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
5775 /* Exception: if the value is constant,
5776 and it won't be truncated, record it. */
5780 /* This is chosen so that the destination will be invalidated
5781 but no new value will be recorded.
5782 We must invalidate because sometimes constant
5783 values can be recorded for bitfields. */
5784 sets
[i
].src_elt
= 0;
5785 sets
[i
].src_volatile
= 1;
5791 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5793 else if (n_sets
== 1 && dest
== pc_rtx
&& src
== pc_rtx
)
5795 /* One less use of the label this insn used to jump to. */
5797 cse_jumps_altered
= 1;
5798 /* No more processing for this set. */
5802 /* If this SET is now setting PC to a label, we know it used to
5803 be a conditional or computed branch. */
5804 else if (dest
== pc_rtx
&& GET_CODE (src
) == LABEL_REF
)
5806 /* Now emit a BARRIER after the unconditional jump. */
5807 if (NEXT_INSN (insn
) == 0
5808 || GET_CODE (NEXT_INSN (insn
)) != BARRIER
)
5809 emit_barrier_after (insn
);
5811 /* We reemit the jump in as many cases as possible just in
5812 case the form of an unconditional jump is significantly
5813 different than a computed jump or conditional jump.
5815 If this insn has multiple sets, then reemitting the
5816 jump is nontrivial. So instead we just force rerecognition
5817 and hope for the best. */
5820 rtx
new = emit_jump_insn_after (gen_jump (XEXP (src
, 0)), insn
);
5822 JUMP_LABEL (new) = XEXP (src
, 0);
5823 LABEL_NUSES (XEXP (src
, 0))++;
5827 /* Now emit a BARRIER after the unconditional jump. */
5828 if (NEXT_INSN (insn
) == 0
5829 || GET_CODE (NEXT_INSN (insn
)) != BARRIER
)
5830 emit_barrier_after (insn
);
5833 INSN_CODE (insn
) = -1;
5835 never_reached_warning (insn
, NULL
);
5837 /* Do not bother deleting any unreachable code,
5838 let jump/flow do that. */
5840 cse_jumps_altered
= 1;
5844 /* If destination is volatile, invalidate it and then do no further
5845 processing for this assignment. */
5847 else if (do_not_record
)
5849 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
)
5850 invalidate (dest
, VOIDmode
);
5851 else if (GET_CODE (dest
) == MEM
)
5853 /* Outgoing arguments for a libcall don't
5854 affect any recorded expressions. */
5855 if (! libcall_insn
|| insn
== libcall_insn
)
5856 invalidate (dest
, VOIDmode
);
5858 else if (GET_CODE (dest
) == STRICT_LOW_PART
5859 || GET_CODE (dest
) == ZERO_EXTRACT
)
5860 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
5864 if (sets
[i
].rtl
!= 0 && dest
!= SET_DEST (sets
[i
].rtl
))
5865 sets
[i
].dest_hash
= HASH (SET_DEST (sets
[i
].rtl
), mode
);
5868 /* If setting CC0, record what it was set to, or a constant, if it
5869 is equivalent to a constant. If it is being set to a floating-point
5870 value, make a COMPARE with the appropriate constant of 0. If we
5871 don't do this, later code can interpret this as a test against
5872 const0_rtx, which can cause problems if we try to put it into an
5873 insn as a floating-point operand. */
5874 if (dest
== cc0_rtx
)
5876 this_insn_cc0
= src_const
&& mode
!= VOIDmode
? src_const
: src
;
5877 this_insn_cc0_mode
= mode
;
5878 if (FLOAT_MODE_P (mode
))
5879 this_insn_cc0
= gen_rtx_COMPARE (VOIDmode
, this_insn_cc0
,
5885 /* Now enter all non-volatile source expressions in the hash table
5886 if they are not already present.
5887 Record their equivalence classes in src_elt.
5888 This way we can insert the corresponding destinations into
5889 the same classes even if the actual sources are no longer in them
5890 (having been invalidated). */
5892 if (src_eqv
&& src_eqv_elt
== 0 && sets
[0].rtl
!= 0 && ! src_eqv_volatile
5893 && ! rtx_equal_p (src_eqv
, SET_DEST (sets
[0].rtl
)))
5895 struct table_elt
*elt
;
5896 struct table_elt
*classp
= sets
[0].src_elt
;
5897 rtx dest
= SET_DEST (sets
[0].rtl
);
5898 enum machine_mode eqvmode
= GET_MODE (dest
);
5900 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5902 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
5905 if (insert_regs (src_eqv
, classp
, 0))
5907 rehash_using_reg (src_eqv
);
5908 src_eqv_hash
= HASH (src_eqv
, eqvmode
);
5910 elt
= insert (src_eqv
, classp
, src_eqv_hash
, eqvmode
);
5911 elt
->in_memory
= src_eqv_in_memory
;
5914 /* Check to see if src_eqv_elt is the same as a set source which
5915 does not yet have an elt, and if so set the elt of the set source
5917 for (i
= 0; i
< n_sets
; i
++)
5918 if (sets
[i
].rtl
&& sets
[i
].src_elt
== 0
5919 && rtx_equal_p (SET_SRC (sets
[i
].rtl
), src_eqv
))
5920 sets
[i
].src_elt
= src_eqv_elt
;
5923 for (i
= 0; i
< n_sets
; i
++)
5924 if (sets
[i
].rtl
&& ! sets
[i
].src_volatile
5925 && ! rtx_equal_p (SET_SRC (sets
[i
].rtl
), SET_DEST (sets
[i
].rtl
)))
5927 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == STRICT_LOW_PART
)
5929 /* REG_EQUAL in setting a STRICT_LOW_PART
5930 gives an equivalent for the entire destination register,
5931 not just for the subreg being stored in now.
5932 This is a more interesting equivalence, so we arrange later
5933 to treat the entire reg as the destination. */
5934 sets
[i
].src_elt
= src_eqv_elt
;
5935 sets
[i
].src_hash
= src_eqv_hash
;
5939 /* Insert source and constant equivalent into hash table, if not
5941 struct table_elt
*classp
= src_eqv_elt
;
5942 rtx src
= sets
[i
].src
;
5943 rtx dest
= SET_DEST (sets
[i
].rtl
);
5944 enum machine_mode mode
5945 = GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
5947 if (sets
[i
].src_elt
== 0)
5949 /* Don't put a hard register source into the table if this is
5950 the last insn of a libcall. In this case, we only need
5951 to put src_eqv_elt in src_elt. */
5952 if (! find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
5954 struct table_elt
*elt
;
5956 /* Note that these insert_regs calls cannot remove
5957 any of the src_elt's, because they would have failed to
5958 match if not still valid. */
5959 if (insert_regs (src
, classp
, 0))
5961 rehash_using_reg (src
);
5962 sets
[i
].src_hash
= HASH (src
, mode
);
5964 elt
= insert (src
, classp
, sets
[i
].src_hash
, mode
);
5965 elt
->in_memory
= sets
[i
].src_in_memory
;
5966 sets
[i
].src_elt
= classp
= elt
;
5969 sets
[i
].src_elt
= classp
;
5971 if (sets
[i
].src_const
&& sets
[i
].src_const_elt
== 0
5972 && src
!= sets
[i
].src_const
5973 && ! rtx_equal_p (sets
[i
].src_const
, src
))
5974 sets
[i
].src_elt
= insert (sets
[i
].src_const
, classp
,
5975 sets
[i
].src_const_hash
, mode
);
5978 else if (sets
[i
].src_elt
== 0)
5979 /* If we did not insert the source into the hash table (e.g., it was
5980 volatile), note the equivalence class for the REG_EQUAL value, if any,
5981 so that the destination goes into that class. */
5982 sets
[i
].src_elt
= src_eqv_elt
;
5984 invalidate_from_clobbers (x
);
5986 /* Some registers are invalidated by subroutine calls. Memory is
5987 invalidated by non-constant calls. */
5989 if (GET_CODE (insn
) == CALL_INSN
)
5991 if (! CONST_OR_PURE_CALL_P (insn
))
5992 invalidate_memory ();
5993 invalidate_for_call ();
5996 /* Now invalidate everything set by this instruction.
5997 If a SUBREG or other funny destination is being set,
5998 sets[i].rtl is still nonzero, so here we invalidate the reg
5999 a part of which is being set. */
6001 for (i
= 0; i
< n_sets
; i
++)
6004 /* We can't use the inner dest, because the mode associated with
6005 a ZERO_EXTRACT is significant. */
6006 rtx dest
= SET_DEST (sets
[i
].rtl
);
6008 /* Needed for registers to remove the register from its
6009 previous quantity's chain.
6010 Needed for memory if this is a nonvarying address, unless
6011 we have just done an invalidate_memory that covers even those. */
6012 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
)
6013 invalidate (dest
, VOIDmode
);
6014 else if (GET_CODE (dest
) == MEM
)
6016 /* Outgoing arguments for a libcall don't
6017 affect any recorded expressions. */
6018 if (! libcall_insn
|| insn
== libcall_insn
)
6019 invalidate (dest
, VOIDmode
);
6021 else if (GET_CODE (dest
) == STRICT_LOW_PART
6022 || GET_CODE (dest
) == ZERO_EXTRACT
)
6023 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
6026 /* A volatile ASM invalidates everything. */
6027 if (GET_CODE (insn
) == INSN
6028 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
6029 && MEM_VOLATILE_P (PATTERN (insn
)))
6030 flush_hash_table ();
6032 /* Make sure registers mentioned in destinations
6033 are safe for use in an expression to be inserted.
6034 This removes from the hash table
6035 any invalid entry that refers to one of these registers.
6037 We don't care about the return value from mention_regs because
6038 we are going to hash the SET_DEST values unconditionally. */
6040 for (i
= 0; i
< n_sets
; i
++)
6044 rtx x
= SET_DEST (sets
[i
].rtl
);
6046 if (GET_CODE (x
) != REG
)
6050 /* We used to rely on all references to a register becoming
6051 inaccessible when a register changes to a new quantity,
6052 since that changes the hash code. However, that is not
6053 safe, since after HASH_SIZE new quantities we get a
6054 hash 'collision' of a register with its own invalid
6055 entries. And since SUBREGs have been changed not to
6056 change their hash code with the hash code of the register,
6057 it wouldn't work any longer at all. So we have to check
6058 for any invalid references lying around now.
6059 This code is similar to the REG case in mention_regs,
6060 but it knows that reg_tick has been incremented, and
6061 it leaves reg_in_table as -1 . */
6062 unsigned int regno
= REGNO (x
);
6063 unsigned int endregno
6064 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
6065 : HARD_REGNO_NREGS (regno
, GET_MODE (x
)));
6068 for (i
= regno
; i
< endregno
; i
++)
6070 if (REG_IN_TABLE (i
) >= 0)
6072 remove_invalid_refs (i
);
6073 REG_IN_TABLE (i
) = -1;
6080 /* We may have just removed some of the src_elt's from the hash table.
6081 So replace each one with the current head of the same class. */
6083 for (i
= 0; i
< n_sets
; i
++)
6086 if (sets
[i
].src_elt
&& sets
[i
].src_elt
->first_same_value
== 0)
6087 /* If elt was removed, find current head of same class,
6088 or 0 if nothing remains of that class. */
6090 struct table_elt
*elt
= sets
[i
].src_elt
;
6092 while (elt
&& elt
->prev_same_value
)
6093 elt
= elt
->prev_same_value
;
6095 while (elt
&& elt
->first_same_value
== 0)
6096 elt
= elt
->next_same_value
;
6097 sets
[i
].src_elt
= elt
? elt
->first_same_value
: 0;
6101 /* Now insert the destinations into their equivalence classes. */
6103 for (i
= 0; i
< n_sets
; i
++)
6106 rtx dest
= SET_DEST (sets
[i
].rtl
);
6107 rtx inner_dest
= sets
[i
].inner_dest
;
6108 struct table_elt
*elt
;
6110 /* Don't record value if we are not supposed to risk allocating
6111 floating-point values in registers that might be wider than
6113 if ((flag_float_store
6114 && GET_CODE (dest
) == MEM
6115 && FLOAT_MODE_P (GET_MODE (dest
)))
6116 /* Don't record BLKmode values, because we don't know the
6117 size of it, and can't be sure that other BLKmode values
6118 have the same or smaller size. */
6119 || GET_MODE (dest
) == BLKmode
6120 /* Don't record values of destinations set inside a libcall block
6121 since we might delete the libcall. Things should have been set
6122 up so we won't want to reuse such a value, but we play it safe
6125 /* If we didn't put a REG_EQUAL value or a source into the hash
6126 table, there is no point is recording DEST. */
6127 || sets
[i
].src_elt
== 0
6128 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
6129 or SIGN_EXTEND, don't record DEST since it can cause
6130 some tracking to be wrong.
6132 ??? Think about this more later. */
6133 || (GET_CODE (dest
) == SUBREG
6134 && (GET_MODE_SIZE (GET_MODE (dest
))
6135 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
6136 && (GET_CODE (sets
[i
].src
) == SIGN_EXTEND
6137 || GET_CODE (sets
[i
].src
) == ZERO_EXTEND
)))
6140 /* STRICT_LOW_PART isn't part of the value BEING set,
6141 and neither is the SUBREG inside it.
6142 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6143 if (GET_CODE (dest
) == STRICT_LOW_PART
)
6144 dest
= SUBREG_REG (XEXP (dest
, 0));
6146 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
)
6147 /* Registers must also be inserted into chains for quantities. */
6148 if (insert_regs (dest
, sets
[i
].src_elt
, 1))
6150 /* If `insert_regs' changes something, the hash code must be
6152 rehash_using_reg (dest
);
6153 sets
[i
].dest_hash
= HASH (dest
, GET_MODE (dest
));
6156 if (GET_CODE (inner_dest
) == MEM
6157 && GET_CODE (XEXP (inner_dest
, 0)) == ADDRESSOF
)
6158 /* Given (SET (MEM (ADDRESSOF (X))) Y) we don't want to say
6159 that (MEM (ADDRESSOF (X))) is equivalent to Y.
6160 Consider the case in which the address of the MEM is
6161 passed to a function, which alters the MEM. Then, if we
6162 later use Y instead of the MEM we'll miss the update. */
6163 elt
= insert (dest
, 0, sets
[i
].dest_hash
, GET_MODE (dest
));
6165 elt
= insert (dest
, sets
[i
].src_elt
,
6166 sets
[i
].dest_hash
, GET_MODE (dest
));
6168 elt
->in_memory
= (GET_CODE (sets
[i
].inner_dest
) == MEM
6169 && (! RTX_UNCHANGING_P (sets
[i
].inner_dest
)
6170 || fixed_base_plus_p (XEXP (sets
[i
].inner_dest
,
6173 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6174 narrower than M2, and both M1 and M2 are the same number of words,
6175 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6176 make that equivalence as well.
6178 However, BAR may have equivalences for which gen_lowpart_if_possible
6179 will produce a simpler value than gen_lowpart_if_possible applied to
6180 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6181 BAR's equivalences. If we don't get a simplified form, make
6182 the SUBREG. It will not be used in an equivalence, but will
6183 cause two similar assignments to be detected.
6185 Note the loop below will find SUBREG_REG (DEST) since we have
6186 already entered SRC and DEST of the SET in the table. */
6188 if (GET_CODE (dest
) == SUBREG
6189 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))) - 1)
6191 == (GET_MODE_SIZE (GET_MODE (dest
)) - 1) / UNITS_PER_WORD
)
6192 && (GET_MODE_SIZE (GET_MODE (dest
))
6193 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
6194 && sets
[i
].src_elt
!= 0)
6196 enum machine_mode new_mode
= GET_MODE (SUBREG_REG (dest
));
6197 struct table_elt
*elt
, *classp
= 0;
6199 for (elt
= sets
[i
].src_elt
->first_same_value
; elt
;
6200 elt
= elt
->next_same_value
)
6204 struct table_elt
*src_elt
;
6207 /* Ignore invalid entries. */
6208 if (GET_CODE (elt
->exp
) != REG
6209 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
6212 /* We may have already been playing subreg games. If the
6213 mode is already correct for the destination, use it. */
6214 if (GET_MODE (elt
->exp
) == new_mode
)
6218 /* Calculate big endian correction for the SUBREG_BYTE.
6219 We have already checked that M1 (GET_MODE (dest))
6220 is not narrower than M2 (new_mode). */
6221 if (BYTES_BIG_ENDIAN
)
6222 byte
= (GET_MODE_SIZE (GET_MODE (dest
))
6223 - GET_MODE_SIZE (new_mode
));
6225 new_src
= simplify_gen_subreg (new_mode
, elt
->exp
,
6226 GET_MODE (dest
), byte
);
6229 /* The call to simplify_gen_subreg fails if the value
6230 is VOIDmode, yet we can't do any simplification, e.g.
6231 for EXPR_LISTs denoting function call results.
6232 It is invalid to construct a SUBREG with a VOIDmode
6233 SUBREG_REG, hence a zero new_src means we can't do
6234 this substitution. */
6238 src_hash
= HASH (new_src
, new_mode
);
6239 src_elt
= lookup (new_src
, src_hash
, new_mode
);
6241 /* Put the new source in the hash table is if isn't
6245 if (insert_regs (new_src
, classp
, 0))
6247 rehash_using_reg (new_src
);
6248 src_hash
= HASH (new_src
, new_mode
);
6250 src_elt
= insert (new_src
, classp
, src_hash
, new_mode
);
6251 src_elt
->in_memory
= elt
->in_memory
;
6253 else if (classp
&& classp
!= src_elt
->first_same_value
)
6254 /* Show that two things that we've seen before are
6255 actually the same. */
6256 merge_equiv_classes (src_elt
, classp
);
6258 classp
= src_elt
->first_same_value
;
6259 /* Ignore invalid entries. */
6261 && GET_CODE (classp
->exp
) != REG
6262 && ! exp_equiv_p (classp
->exp
, classp
->exp
, 1, 0))
6263 classp
= classp
->next_same_value
;
6268 /* Special handling for (set REG0 REG1) where REG0 is the
6269 "cheapest", cheaper than REG1. After cse, REG1 will probably not
6270 be used in the sequel, so (if easily done) change this insn to
6271 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
6272 that computed their value. Then REG1 will become a dead store
6273 and won't cloud the situation for later optimizations.
6275 Do not make this change if REG1 is a hard register, because it will
6276 then be used in the sequel and we may be changing a two-operand insn
6277 into a three-operand insn.
6279 Also do not do this if we are operating on a copy of INSN.
6281 Also don't do this if INSN ends a libcall; this would cause an unrelated
6282 register to be set in the middle of a libcall, and we then get bad code
6283 if the libcall is deleted. */
6285 if (n_sets
== 1 && sets
[0].rtl
&& GET_CODE (SET_DEST (sets
[0].rtl
)) == REG
6286 && NEXT_INSN (PREV_INSN (insn
)) == insn
6287 && GET_CODE (SET_SRC (sets
[0].rtl
)) == REG
6288 && REGNO (SET_SRC (sets
[0].rtl
)) >= FIRST_PSEUDO_REGISTER
6289 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets
[0].rtl
))))
6291 int src_q
= REG_QTY (REGNO (SET_SRC (sets
[0].rtl
)));
6292 struct qty_table_elem
*src_ent
= &qty_table
[src_q
];
6294 if ((src_ent
->first_reg
== REGNO (SET_DEST (sets
[0].rtl
)))
6295 && ! find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
6298 /* Scan for the previous nonnote insn, but stop at a basic
6302 prev
= PREV_INSN (prev
);
6304 while (prev
&& GET_CODE (prev
) == NOTE
6305 && NOTE_LINE_NUMBER (prev
) != NOTE_INSN_BASIC_BLOCK
);
6307 /* Do not swap the registers around if the previous instruction
6308 attaches a REG_EQUIV note to REG1.
6310 ??? It's not entirely clear whether we can transfer a REG_EQUIV
6311 from the pseudo that originally shadowed an incoming argument
6312 to another register. Some uses of REG_EQUIV might rely on it
6313 being attached to REG1 rather than REG2.
6315 This section previously turned the REG_EQUIV into a REG_EQUAL
6316 note. We cannot do that because REG_EQUIV may provide an
6317 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
6319 if (prev
!= 0 && GET_CODE (prev
) == INSN
6320 && GET_CODE (PATTERN (prev
)) == SET
6321 && SET_DEST (PATTERN (prev
)) == SET_SRC (sets
[0].rtl
)
6322 && ! find_reg_note (prev
, REG_EQUIV
, NULL_RTX
))
6324 rtx dest
= SET_DEST (sets
[0].rtl
);
6325 rtx src
= SET_SRC (sets
[0].rtl
);
6328 validate_change (prev
, &SET_DEST (PATTERN (prev
)), dest
, 1);
6329 validate_change (insn
, &SET_DEST (sets
[0].rtl
), src
, 1);
6330 validate_change (insn
, &SET_SRC (sets
[0].rtl
), dest
, 1);
6331 apply_change_group ();
6333 /* If there was a REG_WAS_0 note on PREV, remove it. Move
6334 any REG_WAS_0 note on INSN to PREV. */
6335 note
= find_reg_note (prev
, REG_WAS_0
, NULL_RTX
);
6337 remove_note (prev
, note
);
6339 note
= find_reg_note (insn
, REG_WAS_0
, NULL_RTX
);
6342 remove_note (insn
, note
);
6343 XEXP (note
, 1) = REG_NOTES (prev
);
6344 REG_NOTES (prev
) = note
;
6347 /* If INSN has a REG_EQUAL note, and this note mentions
6348 REG0, then we must delete it, because the value in
6349 REG0 has changed. If the note's value is REG1, we must
6350 also delete it because that is now this insn's dest. */
6351 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
6353 && (reg_mentioned_p (dest
, XEXP (note
, 0))
6354 || rtx_equal_p (src
, XEXP (note
, 0))))
6355 remove_note (insn
, note
);
6360 /* If this is a conditional jump insn, record any known equivalences due to
6361 the condition being tested. */
6363 last_jump_equiv_class
= 0;
6364 if (GET_CODE (insn
) == JUMP_INSN
6365 && n_sets
== 1 && GET_CODE (x
) == SET
6366 && GET_CODE (SET_SRC (x
)) == IF_THEN_ELSE
)
6367 record_jump_equiv (insn
, 0);
6370 /* If the previous insn set CC0 and this insn no longer references CC0,
6371 delete the previous insn. Here we use the fact that nothing expects CC0
6372 to be valid over an insn, which is true until the final pass. */
6373 if (prev_insn
&& GET_CODE (prev_insn
) == INSN
6374 && (tem
= single_set (prev_insn
)) != 0
6375 && SET_DEST (tem
) == cc0_rtx
6376 && ! reg_mentioned_p (cc0_rtx
, x
))
6377 delete_insn (prev_insn
);
6379 prev_insn_cc0
= this_insn_cc0
;
6380 prev_insn_cc0_mode
= this_insn_cc0_mode
;
6385 /* Remove from the hash table all expressions that reference memory. */
6388 invalidate_memory ()
6391 struct table_elt
*p
, *next
;
6393 for (i
= 0; i
< HASH_SIZE
; i
++)
6394 for (p
= table
[i
]; p
; p
= next
)
6396 next
= p
->next_same_hash
;
6398 remove_from_table (p
, i
);
6402 /* If ADDR is an address that implicitly affects the stack pointer, return
6403 1 and update the register tables to show the effect. Else, return 0. */
6406 addr_affects_sp_p (addr
)
6409 if (GET_RTX_CLASS (GET_CODE (addr
)) == 'a'
6410 && GET_CODE (XEXP (addr
, 0)) == REG
6411 && REGNO (XEXP (addr
, 0)) == STACK_POINTER_REGNUM
)
6413 if (REG_TICK (STACK_POINTER_REGNUM
) >= 0)
6415 REG_TICK (STACK_POINTER_REGNUM
)++;
6416 /* Is it possible to use a subreg of SP? */
6417 SUBREG_TICKED (STACK_POINTER_REGNUM
) = -1;
6420 /* This should be *very* rare. */
6421 if (TEST_HARD_REG_BIT (hard_regs_in_table
, STACK_POINTER_REGNUM
))
6422 invalidate (stack_pointer_rtx
, VOIDmode
);
6430 /* Perform invalidation on the basis of everything about an insn
6431 except for invalidating the actual places that are SET in it.
6432 This includes the places CLOBBERed, and anything that might
6433 alias with something that is SET or CLOBBERed.
6435 X is the pattern of the insn. */
6438 invalidate_from_clobbers (x
)
6441 if (GET_CODE (x
) == CLOBBER
)
6443 rtx ref
= XEXP (x
, 0);
6446 if (GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6447 || GET_CODE (ref
) == MEM
)
6448 invalidate (ref
, VOIDmode
);
6449 else if (GET_CODE (ref
) == STRICT_LOW_PART
6450 || GET_CODE (ref
) == ZERO_EXTRACT
)
6451 invalidate (XEXP (ref
, 0), GET_MODE (ref
));
6454 else if (GET_CODE (x
) == PARALLEL
)
6457 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
6459 rtx y
= XVECEXP (x
, 0, i
);
6460 if (GET_CODE (y
) == CLOBBER
)
6462 rtx ref
= XEXP (y
, 0);
6463 if (GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6464 || GET_CODE (ref
) == MEM
)
6465 invalidate (ref
, VOIDmode
);
6466 else if (GET_CODE (ref
) == STRICT_LOW_PART
6467 || GET_CODE (ref
) == ZERO_EXTRACT
)
6468 invalidate (XEXP (ref
, 0), GET_MODE (ref
));
6474 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6475 and replace any registers in them with either an equivalent constant
6476 or the canonical form of the register. If we are inside an address,
6477 only do this if the address remains valid.
6479 OBJECT is 0 except when within a MEM in which case it is the MEM.
6481 Return the replacement for X. */
6484 cse_process_notes (x
, object
)
6488 enum rtx_code code
= GET_CODE (x
);
6489 const char *fmt
= GET_RTX_FORMAT (code
);
6506 validate_change (x
, &XEXP (x
, 0),
6507 cse_process_notes (XEXP (x
, 0), x
), 0);
6512 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
6513 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), NULL_RTX
);
6515 XEXP (x
, 1) = cse_process_notes (XEXP (x
, 1), NULL_RTX
);
6522 rtx
new = cse_process_notes (XEXP (x
, 0), object
);
6523 /* We don't substitute VOIDmode constants into these rtx,
6524 since they would impede folding. */
6525 if (GET_MODE (new) != VOIDmode
)
6526 validate_change (object
, &XEXP (x
, 0), new, 0);
6531 i
= REG_QTY (REGNO (x
));
6533 /* Return a constant or a constant register. */
6534 if (REGNO_QTY_VALID_P (REGNO (x
)))
6536 struct qty_table_elem
*ent
= &qty_table
[i
];
6538 if (ent
->const_rtx
!= NULL_RTX
6539 && (CONSTANT_P (ent
->const_rtx
)
6540 || GET_CODE (ent
->const_rtx
) == REG
))
6542 rtx
new = gen_lowpart_if_possible (GET_MODE (x
), ent
->const_rtx
);
6548 /* Otherwise, canonicalize this register. */
6549 return canon_reg (x
, NULL_RTX
);
6555 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
6557 validate_change (object
, &XEXP (x
, i
),
6558 cse_process_notes (XEXP (x
, i
), object
), 0);
6563 /* Find common subexpressions between the end test of a loop and the beginning
6564 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6566 Often we have a loop where an expression in the exit test is used
6567 in the body of the loop. For example "while (*p) *q++ = *p++;".
6568 Because of the way we duplicate the loop exit test in front of the loop,
6569 however, we don't detect that common subexpression. This will be caught
6570 when global cse is implemented, but this is a quite common case.
6572 This function handles the most common cases of these common expressions.
6573 It is called after we have processed the basic block ending with the
6574 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6575 jumps to a label used only once. */
6578 cse_around_loop (loop_start
)
6583 struct table_elt
*p
;
6585 /* If the jump at the end of the loop doesn't go to the start, we don't
6587 for (insn
= PREV_INSN (loop_start
);
6588 insn
&& (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) >= 0);
6589 insn
= PREV_INSN (insn
))
6593 || GET_CODE (insn
) != NOTE
6594 || NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
)
6597 /* If the last insn of the loop (the end test) was an NE comparison,
6598 we will interpret it as an EQ comparison, since we fell through
6599 the loop. Any equivalences resulting from that comparison are
6600 therefore not valid and must be invalidated. */
6601 if (last_jump_equiv_class
)
6602 for (p
= last_jump_equiv_class
->first_same_value
; p
;
6603 p
= p
->next_same_value
)
6605 if (GET_CODE (p
->exp
) == MEM
|| GET_CODE (p
->exp
) == REG
6606 || (GET_CODE (p
->exp
) == SUBREG
6607 && GET_CODE (SUBREG_REG (p
->exp
)) == REG
))
6608 invalidate (p
->exp
, VOIDmode
);
6609 else if (GET_CODE (p
->exp
) == STRICT_LOW_PART
6610 || GET_CODE (p
->exp
) == ZERO_EXTRACT
)
6611 invalidate (XEXP (p
->exp
, 0), GET_MODE (p
->exp
));
6614 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6615 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6617 The only thing we do with SET_DEST is invalidate entries, so we
6618 can safely process each SET in order. It is slightly less efficient
6619 to do so, but we only want to handle the most common cases.
6621 The gen_move_insn call in cse_set_around_loop may create new pseudos.
6622 These pseudos won't have valid entries in any of the tables indexed
6623 by register number, such as reg_qty. We avoid out-of-range array
6624 accesses by not processing any instructions created after cse started. */
6626 for (insn
= NEXT_INSN (loop_start
);
6627 GET_CODE (insn
) != CALL_INSN
&& GET_CODE (insn
) != CODE_LABEL
6628 && INSN_UID (insn
) < max_insn_uid
6629 && ! (GET_CODE (insn
) == NOTE
6630 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
);
6631 insn
= NEXT_INSN (insn
))
6634 && (GET_CODE (PATTERN (insn
)) == SET
6635 || GET_CODE (PATTERN (insn
)) == CLOBBER
))
6636 cse_set_around_loop (PATTERN (insn
), insn
, loop_start
);
6637 else if (INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == PARALLEL
)
6638 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
6639 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == SET
6640 || GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == CLOBBER
)
6641 cse_set_around_loop (XVECEXP (PATTERN (insn
), 0, i
), insn
,
6646 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6647 since they are done elsewhere. This function is called via note_stores. */
6650 invalidate_skipped_set (dest
, set
, data
)
6653 void *data ATTRIBUTE_UNUSED
;
6655 enum rtx_code code
= GET_CODE (dest
);
6658 && ! addr_affects_sp_p (dest
) /* If this is not a stack push ... */
6659 /* There are times when an address can appear varying and be a PLUS
6660 during this scan when it would be a fixed address were we to know
6661 the proper equivalences. So invalidate all memory if there is
6662 a BLKmode or nonscalar memory reference or a reference to a
6663 variable address. */
6664 && (MEM_IN_STRUCT_P (dest
) || GET_MODE (dest
) == BLKmode
6665 || cse_rtx_varies_p (XEXP (dest
, 0), 0)))
6667 invalidate_memory ();
6671 if (GET_CODE (set
) == CLOBBER
6678 if (code
== STRICT_LOW_PART
|| code
== ZERO_EXTRACT
)
6679 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
6680 else if (code
== REG
|| code
== SUBREG
|| code
== MEM
)
6681 invalidate (dest
, VOIDmode
);
6684 /* Invalidate all insns from START up to the end of the function or the
6685 next label. This called when we wish to CSE around a block that is
6686 conditionally executed. */
6689 invalidate_skipped_block (start
)
6694 for (insn
= start
; insn
&& GET_CODE (insn
) != CODE_LABEL
;
6695 insn
= NEXT_INSN (insn
))
6697 if (! INSN_P (insn
))
6700 if (GET_CODE (insn
) == CALL_INSN
)
6702 if (! CONST_OR_PURE_CALL_P (insn
))
6703 invalidate_memory ();
6704 invalidate_for_call ();
6707 invalidate_from_clobbers (PATTERN (insn
));
6708 note_stores (PATTERN (insn
), invalidate_skipped_set
, NULL
);
6712 /* If modifying X will modify the value in *DATA (which is really an
6713 `rtx *'), indicate that fact by setting the pointed to value to
6717 cse_check_loop_start (x
, set
, data
)
6719 rtx set ATTRIBUTE_UNUSED
;
6722 rtx
*cse_check_loop_start_value
= (rtx
*) data
;
6724 if (*cse_check_loop_start_value
== NULL_RTX
6725 || GET_CODE (x
) == CC0
|| GET_CODE (x
) == PC
)
6728 if ((GET_CODE (x
) == MEM
&& GET_CODE (*cse_check_loop_start_value
) == MEM
)
6729 || reg_overlap_mentioned_p (x
, *cse_check_loop_start_value
))
6730 *cse_check_loop_start_value
= NULL_RTX
;
6733 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6734 a loop that starts with the label at LOOP_START.
6736 If X is a SET, we see if its SET_SRC is currently in our hash table.
6737 If so, we see if it has a value equal to some register used only in the
6738 loop exit code (as marked by jump.c).
6740 If those two conditions are true, we search backwards from the start of
6741 the loop to see if that same value was loaded into a register that still
6742 retains its value at the start of the loop.
6744 If so, we insert an insn after the load to copy the destination of that
6745 load into the equivalent register and (try to) replace our SET_SRC with that
6748 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6751 cse_set_around_loop (x
, insn
, loop_start
)
6756 struct table_elt
*src_elt
;
6758 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6759 are setting PC or CC0 or whose SET_SRC is already a register. */
6760 if (GET_CODE (x
) == SET
6761 && GET_CODE (SET_DEST (x
)) != PC
&& GET_CODE (SET_DEST (x
)) != CC0
6762 && GET_CODE (SET_SRC (x
)) != REG
)
6764 src_elt
= lookup (SET_SRC (x
),
6765 HASH (SET_SRC (x
), GET_MODE (SET_DEST (x
))),
6766 GET_MODE (SET_DEST (x
)));
6769 for (src_elt
= src_elt
->first_same_value
; src_elt
;
6770 src_elt
= src_elt
->next_same_value
)
6771 if (GET_CODE (src_elt
->exp
) == REG
&& REG_LOOP_TEST_P (src_elt
->exp
)
6772 && COST (src_elt
->exp
) < COST (SET_SRC (x
)))
6776 /* Look for an insn in front of LOOP_START that sets
6777 something in the desired mode to SET_SRC (x) before we hit
6778 a label or CALL_INSN. */
6780 for (p
= prev_nonnote_insn (loop_start
);
6781 p
&& GET_CODE (p
) != CALL_INSN
6782 && GET_CODE (p
) != CODE_LABEL
;
6783 p
= prev_nonnote_insn (p
))
6784 if ((set
= single_set (p
)) != 0
6785 && GET_CODE (SET_DEST (set
)) == REG
6786 && GET_MODE (SET_DEST (set
)) == src_elt
->mode
6787 && rtx_equal_p (SET_SRC (set
), SET_SRC (x
)))
6789 /* We now have to ensure that nothing between P
6790 and LOOP_START modified anything referenced in
6791 SET_SRC (x). We know that nothing within the loop
6792 can modify it, or we would have invalidated it in
6795 rtx cse_check_loop_start_value
= SET_SRC (x
);
6796 for (q
= p
; q
!= loop_start
; q
= NEXT_INSN (q
))
6798 note_stores (PATTERN (q
),
6799 cse_check_loop_start
,
6800 &cse_check_loop_start_value
);
6802 /* If nothing was changed and we can replace our
6803 SET_SRC, add an insn after P to copy its destination
6804 to what we will be replacing SET_SRC with. */
6805 if (cse_check_loop_start_value
6807 && !can_throw_internal (insn
)
6808 && validate_change (insn
, &SET_SRC (x
),
6811 /* If this creates new pseudos, this is unsafe,
6812 because the regno of new pseudo is unsuitable
6813 to index into reg_qty when cse_insn processes
6814 the new insn. Therefore, if a new pseudo was
6815 created, discard this optimization. */
6816 int nregs
= max_reg_num ();
6818 = gen_move_insn (src_elt
->exp
, SET_DEST (set
));
6819 if (nregs
!= max_reg_num ())
6821 if (! validate_change (insn
, &SET_SRC (x
),
6826 emit_insn_after (move
, p
);
6833 /* Deal with the destination of X affecting the stack pointer. */
6834 addr_affects_sp_p (SET_DEST (x
));
6836 /* See comment on similar code in cse_insn for explanation of these
6838 if (GET_CODE (SET_DEST (x
)) == REG
|| GET_CODE (SET_DEST (x
)) == SUBREG
6839 || GET_CODE (SET_DEST (x
)) == MEM
)
6840 invalidate (SET_DEST (x
), VOIDmode
);
6841 else if (GET_CODE (SET_DEST (x
)) == STRICT_LOW_PART
6842 || GET_CODE (SET_DEST (x
)) == ZERO_EXTRACT
)
6843 invalidate (XEXP (SET_DEST (x
), 0), GET_MODE (SET_DEST (x
)));
6846 /* Find the end of INSN's basic block and return its range,
6847 the total number of SETs in all the insns of the block, the last insn of the
6848 block, and the branch path.
6850 The branch path indicates which branches should be followed. If a nonzero
6851 path size is specified, the block should be rescanned and a different set
6852 of branches will be taken. The branch path is only used if
6853 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is nonzero.
6855 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6856 used to describe the block. It is filled in with the information about
6857 the current block. The incoming structure's branch path, if any, is used
6858 to construct the output branch path. */
6861 cse_end_of_basic_block (insn
, data
, follow_jumps
, after_loop
, skip_blocks
)
6863 struct cse_basic_block_data
*data
;
6870 int low_cuid
= INSN_CUID (insn
), high_cuid
= INSN_CUID (insn
);
6871 rtx next
= INSN_P (insn
) ? insn
: next_real_insn (insn
);
6872 int path_size
= data
->path_size
;
6876 /* Update the previous branch path, if any. If the last branch was
6877 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6878 shorten the path by one and look at the previous branch. We know that
6879 at least one branch must have been taken if PATH_SIZE is nonzero. */
6880 while (path_size
> 0)
6882 if (data
->path
[path_size
- 1].status
!= NOT_TAKEN
)
6884 data
->path
[path_size
- 1].status
= NOT_TAKEN
;
6891 /* If the first instruction is marked with QImode, that means we've
6892 already processed this block. Our caller will look at DATA->LAST
6893 to figure out where to go next. We want to return the next block
6894 in the instruction stream, not some branched-to block somewhere
6895 else. We accomplish this by pretending our called forbid us to
6896 follow jumps, or skip blocks. */
6897 if (GET_MODE (insn
) == QImode
)
6898 follow_jumps
= skip_blocks
= 0;
6900 /* Scan to end of this basic block. */
6901 while (p
&& GET_CODE (p
) != CODE_LABEL
)
6903 /* Don't cse out the end of a loop. This makes a difference
6904 only for the unusual loops that always execute at least once;
6905 all other loops have labels there so we will stop in any case.
6906 Cse'ing out the end of the loop is dangerous because it
6907 might cause an invariant expression inside the loop
6908 to be reused after the end of the loop. This would make it
6909 hard to move the expression out of the loop in loop.c,
6910 especially if it is one of several equivalent expressions
6911 and loop.c would like to eliminate it.
6913 If we are running after loop.c has finished, we can ignore
6914 the NOTE_INSN_LOOP_END. */
6916 if (! after_loop
&& GET_CODE (p
) == NOTE
6917 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
6920 /* Don't cse over a call to setjmp; on some machines (eg VAX)
6921 the regs restored by the longjmp come from
6922 a later time than the setjmp. */
6923 if (PREV_INSN (p
) && GET_CODE (PREV_INSN (p
)) == CALL_INSN
6924 && find_reg_note (PREV_INSN (p
), REG_SETJMP
, NULL
))
6927 /* A PARALLEL can have lots of SETs in it,
6928 especially if it is really an ASM_OPERANDS. */
6929 if (INSN_P (p
) && GET_CODE (PATTERN (p
)) == PARALLEL
)
6930 nsets
+= XVECLEN (PATTERN (p
), 0);
6931 else if (GET_CODE (p
) != NOTE
)
6934 /* Ignore insns made by CSE; they cannot affect the boundaries of
6937 if (INSN_UID (p
) <= max_uid
&& INSN_CUID (p
) > high_cuid
)
6938 high_cuid
= INSN_CUID (p
);
6939 if (INSN_UID (p
) <= max_uid
&& INSN_CUID (p
) < low_cuid
)
6940 low_cuid
= INSN_CUID (p
);
6942 /* See if this insn is in our branch path. If it is and we are to
6944 if (path_entry
< path_size
&& data
->path
[path_entry
].branch
== p
)
6946 if (data
->path
[path_entry
].status
!= NOT_TAKEN
)
6949 /* Point to next entry in path, if any. */
6953 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
6954 was specified, we haven't reached our maximum path length, there are
6955 insns following the target of the jump, this is the only use of the
6956 jump label, and the target label is preceded by a BARRIER.
6958 Alternatively, we can follow the jump if it branches around a
6959 block of code and there are no other branches into the block.
6960 In this case invalidate_skipped_block will be called to invalidate any
6961 registers set in the block when following the jump. */
6963 else if ((follow_jumps
|| skip_blocks
) && path_size
< PATHLENGTH
- 1
6964 && GET_CODE (p
) == JUMP_INSN
6965 && GET_CODE (PATTERN (p
)) == SET
6966 && GET_CODE (SET_SRC (PATTERN (p
))) == IF_THEN_ELSE
6967 && JUMP_LABEL (p
) != 0
6968 && LABEL_NUSES (JUMP_LABEL (p
)) == 1
6969 && NEXT_INSN (JUMP_LABEL (p
)) != 0)
6971 for (q
= PREV_INSN (JUMP_LABEL (p
)); q
; q
= PREV_INSN (q
))
6972 if ((GET_CODE (q
) != NOTE
6973 || NOTE_LINE_NUMBER (q
) == NOTE_INSN_LOOP_END
6974 || (PREV_INSN (q
) && GET_CODE (PREV_INSN (q
)) == CALL_INSN
6975 && find_reg_note (PREV_INSN (q
), REG_SETJMP
, NULL
)))
6976 && (GET_CODE (q
) != CODE_LABEL
|| LABEL_NUSES (q
) != 0))
6979 /* If we ran into a BARRIER, this code is an extension of the
6980 basic block when the branch is taken. */
6981 if (follow_jumps
&& q
!= 0 && GET_CODE (q
) == BARRIER
)
6983 /* Don't allow ourself to keep walking around an
6984 always-executed loop. */
6985 if (next_real_insn (q
) == next
)
6991 /* Similarly, don't put a branch in our path more than once. */
6992 for (i
= 0; i
< path_entry
; i
++)
6993 if (data
->path
[i
].branch
== p
)
6996 if (i
!= path_entry
)
6999 data
->path
[path_entry
].branch
= p
;
7000 data
->path
[path_entry
++].status
= TAKEN
;
7002 /* This branch now ends our path. It was possible that we
7003 didn't see this branch the last time around (when the
7004 insn in front of the target was a JUMP_INSN that was
7005 turned into a no-op). */
7006 path_size
= path_entry
;
7009 /* Mark block so we won't scan it again later. */
7010 PUT_MODE (NEXT_INSN (p
), QImode
);
7012 /* Detect a branch around a block of code. */
7013 else if (skip_blocks
&& q
!= 0 && GET_CODE (q
) != CODE_LABEL
)
7017 if (next_real_insn (q
) == next
)
7023 for (i
= 0; i
< path_entry
; i
++)
7024 if (data
->path
[i
].branch
== p
)
7027 if (i
!= path_entry
)
7030 /* This is no_labels_between_p (p, q) with an added check for
7031 reaching the end of a function (in case Q precedes P). */
7032 for (tmp
= NEXT_INSN (p
); tmp
&& tmp
!= q
; tmp
= NEXT_INSN (tmp
))
7033 if (GET_CODE (tmp
) == CODE_LABEL
)
7038 data
->path
[path_entry
].branch
= p
;
7039 data
->path
[path_entry
++].status
= AROUND
;
7041 path_size
= path_entry
;
7044 /* Mark block so we won't scan it again later. */
7045 PUT_MODE (NEXT_INSN (p
), QImode
);
7052 data
->low_cuid
= low_cuid
;
7053 data
->high_cuid
= high_cuid
;
7054 data
->nsets
= nsets
;
7057 /* If all jumps in the path are not taken, set our path length to zero
7058 so a rescan won't be done. */
7059 for (i
= path_size
- 1; i
>= 0; i
--)
7060 if (data
->path
[i
].status
!= NOT_TAKEN
)
7064 data
->path_size
= 0;
7066 data
->path_size
= path_size
;
7068 /* End the current branch path. */
7069 data
->path
[path_size
].branch
= 0;
7072 /* Perform cse on the instructions of a function.
7073 F is the first instruction.
7074 NREGS is one plus the highest pseudo-reg number used in the instruction.
7076 AFTER_LOOP is 1 if this is the cse call done after loop optimization
7077 (only if -frerun-cse-after-loop).
7079 Returns 1 if jump_optimize should be redone due to simplifications
7080 in conditional jump instructions. */
7083 cse_main (f
, nregs
, after_loop
, file
)
7089 struct cse_basic_block_data val
;
7093 cse_jumps_altered
= 0;
7094 recorded_label_ref
= 0;
7095 constant_pool_entries_cost
= 0;
7099 init_alias_analysis ();
7103 max_insn_uid
= get_max_uid ();
7105 reg_eqv_table
= (struct reg_eqv_elem
*)
7106 xmalloc (nregs
* sizeof (struct reg_eqv_elem
));
7108 #ifdef LOAD_EXTEND_OP
7110 /* Allocate scratch rtl here. cse_insn will fill in the memory reference
7111 and change the code and mode as appropriate. */
7112 memory_extend_rtx
= gen_rtx_ZERO_EXTEND (VOIDmode
, NULL_RTX
);
7115 /* Reset the counter indicating how many elements have been made
7117 n_elements_made
= 0;
7119 /* Find the largest uid. */
7121 max_uid
= get_max_uid ();
7122 uid_cuid
= (int *) xcalloc (max_uid
+ 1, sizeof (int));
7124 /* Compute the mapping from uids to cuids.
7125 CUIDs are numbers assigned to insns, like uids,
7126 except that cuids increase monotonically through the code.
7127 Don't assign cuids to line-number NOTEs, so that the distance in cuids
7128 between two insns is not affected by -g. */
7130 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
7132 if (GET_CODE (insn
) != NOTE
7133 || NOTE_LINE_NUMBER (insn
) < 0)
7134 INSN_CUID (insn
) = ++i
;
7136 /* Give a line number note the same cuid as preceding insn. */
7137 INSN_CUID (insn
) = i
;
7140 ggc_push_context ();
7142 /* Loop over basic blocks.
7143 Compute the maximum number of qty's needed for each basic block
7144 (which is 2 for each SET). */
7149 cse_end_of_basic_block (insn
, &val
, flag_cse_follow_jumps
, after_loop
,
7150 flag_cse_skip_blocks
);
7152 /* If this basic block was already processed or has no sets, skip it. */
7153 if (val
.nsets
== 0 || GET_MODE (insn
) == QImode
)
7155 PUT_MODE (insn
, VOIDmode
);
7156 insn
= (val
.last
? NEXT_INSN (val
.last
) : 0);
7161 cse_basic_block_start
= val
.low_cuid
;
7162 cse_basic_block_end
= val
.high_cuid
;
7163 max_qty
= val
.nsets
* 2;
7166 fnotice (file
, ";; Processing block from %d to %d, %d sets.\n",
7167 INSN_UID (insn
), val
.last
? INSN_UID (val
.last
) : 0,
7170 /* Make MAX_QTY bigger to give us room to optimize
7171 past the end of this basic block, if that should prove useful. */
7177 /* If this basic block is being extended by following certain jumps,
7178 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7179 Otherwise, we start after this basic block. */
7180 if (val
.path_size
> 0)
7181 cse_basic_block (insn
, val
.last
, val
.path
, 0);
7184 int old_cse_jumps_altered
= cse_jumps_altered
;
7187 /* When cse changes a conditional jump to an unconditional
7188 jump, we want to reprocess the block, since it will give
7189 us a new branch path to investigate. */
7190 cse_jumps_altered
= 0;
7191 temp
= cse_basic_block (insn
, val
.last
, val
.path
, ! after_loop
);
7192 if (cse_jumps_altered
== 0
7193 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7196 cse_jumps_altered
|= old_cse_jumps_altered
;
7209 if (max_elements_made
< n_elements_made
)
7210 max_elements_made
= n_elements_made
;
7213 end_alias_analysis ();
7215 free (reg_eqv_table
);
7217 return cse_jumps_altered
|| recorded_label_ref
;
7220 /* Process a single basic block. FROM and TO and the limits of the basic
7221 block. NEXT_BRANCH points to the branch path when following jumps or
7222 a null path when not following jumps.
7224 AROUND_LOOP is nonzero if we are to try to cse around to the start of a
7225 loop. This is true when we are being called for the last time on a
7226 block and this CSE pass is before loop.c. */
7229 cse_basic_block (from
, to
, next_branch
, around_loop
)
7231 struct branch_path
*next_branch
;
7236 rtx libcall_insn
= NULL_RTX
;
7239 /* This array is undefined before max_reg, so only allocate
7240 the space actually needed and adjust the start. */
7243 = (struct qty_table_elem
*) xmalloc ((max_qty
- max_reg
)
7244 * sizeof (struct qty_table_elem
));
7245 qty_table
-= max_reg
;
7249 /* TO might be a label. If so, protect it from being deleted. */
7250 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7253 for (insn
= from
; insn
!= to
; insn
= NEXT_INSN (insn
))
7255 enum rtx_code code
= GET_CODE (insn
);
7257 /* If we have processed 1,000 insns, flush the hash table to
7258 avoid extreme quadratic behavior. We must not include NOTEs
7259 in the count since there may be more of them when generating
7260 debugging information. If we clear the table at different
7261 times, code generated with -g -O might be different than code
7262 generated with -O but not -g.
7264 ??? This is a real kludge and needs to be done some other way.
7266 if (code
!= NOTE
&& num_insns
++ > 1000)
7268 flush_hash_table ();
7272 /* See if this is a branch that is part of the path. If so, and it is
7273 to be taken, do so. */
7274 if (next_branch
->branch
== insn
)
7276 enum taken status
= next_branch
++->status
;
7277 if (status
!= NOT_TAKEN
)
7279 if (status
== TAKEN
)
7280 record_jump_equiv (insn
, 1);
7282 invalidate_skipped_block (NEXT_INSN (insn
));
7284 /* Set the last insn as the jump insn; it doesn't affect cc0.
7285 Then follow this branch. */
7290 insn
= JUMP_LABEL (insn
);
7295 if (GET_MODE (insn
) == QImode
)
7296 PUT_MODE (insn
, VOIDmode
);
7298 if (GET_RTX_CLASS (code
) == 'i')
7302 /* Process notes first so we have all notes in canonical forms when
7303 looking for duplicate operations. */
7305 if (REG_NOTES (insn
))
7306 REG_NOTES (insn
) = cse_process_notes (REG_NOTES (insn
), NULL_RTX
);
7308 /* Track when we are inside in LIBCALL block. Inside such a block,
7309 we do not want to record destinations. The last insn of a
7310 LIBCALL block is not considered to be part of the block, since
7311 its destination is the result of the block and hence should be
7314 if (REG_NOTES (insn
) != 0)
7316 if ((p
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)))
7317 libcall_insn
= XEXP (p
, 0);
7318 else if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
7322 cse_insn (insn
, libcall_insn
);
7324 /* If we haven't already found an insn where we added a LABEL_REF,
7326 if (GET_CODE (insn
) == INSN
&& ! recorded_label_ref
7327 && for_each_rtx (&PATTERN (insn
), check_for_label_ref
,
7329 recorded_label_ref
= 1;
7332 /* If INSN is now an unconditional jump, skip to the end of our
7333 basic block by pretending that we just did the last insn in the
7334 basic block. If we are jumping to the end of our block, show
7335 that we can have one usage of TO. */
7337 if (any_uncondjump_p (insn
))
7341 free (qty_table
+ max_reg
);
7345 if (JUMP_LABEL (insn
) == to
)
7348 /* Maybe TO was deleted because the jump is unconditional.
7349 If so, there is nothing left in this basic block. */
7350 /* ??? Perhaps it would be smarter to set TO
7351 to whatever follows this insn,
7352 and pretend the basic block had always ended here. */
7353 if (INSN_DELETED_P (to
))
7356 insn
= PREV_INSN (to
);
7359 /* See if it is ok to keep on going past the label
7360 which used to end our basic block. Remember that we incremented
7361 the count of that label, so we decrement it here. If we made
7362 a jump unconditional, TO_USAGE will be one; in that case, we don't
7363 want to count the use in that jump. */
7365 if (to
!= 0 && NEXT_INSN (insn
) == to
7366 && GET_CODE (to
) == CODE_LABEL
&& --LABEL_NUSES (to
) == to_usage
)
7368 struct cse_basic_block_data val
;
7371 insn
= NEXT_INSN (to
);
7373 /* If TO was the last insn in the function, we are done. */
7376 free (qty_table
+ max_reg
);
7380 /* If TO was preceded by a BARRIER we are done with this block
7381 because it has no continuation. */
7382 prev
= prev_nonnote_insn (to
);
7383 if (prev
&& GET_CODE (prev
) == BARRIER
)
7385 free (qty_table
+ max_reg
);
7389 /* Find the end of the following block. Note that we won't be
7390 following branches in this case. */
7393 cse_end_of_basic_block (insn
, &val
, 0, 0, 0);
7395 /* If the tables we allocated have enough space left
7396 to handle all the SETs in the next basic block,
7397 continue through it. Otherwise, return,
7398 and that block will be scanned individually. */
7399 if (val
.nsets
* 2 + next_qty
> max_qty
)
7402 cse_basic_block_start
= val
.low_cuid
;
7403 cse_basic_block_end
= val
.high_cuid
;
7406 /* Prevent TO from being deleted if it is a label. */
7407 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7410 /* Back up so we process the first insn in the extension. */
7411 insn
= PREV_INSN (insn
);
7415 if (next_qty
> max_qty
)
7418 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7419 the previous insn is the only insn that branches to the head of a loop,
7420 we can cse into the loop. Don't do this if we changed the jump
7421 structure of a loop unless we aren't going to be following jumps. */
7423 insn
= prev_nonnote_insn (to
);
7424 if ((cse_jumps_altered
== 0
7425 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7426 && around_loop
&& to
!= 0
7427 && GET_CODE (to
) == NOTE
&& NOTE_LINE_NUMBER (to
) == NOTE_INSN_LOOP_END
7428 && GET_CODE (insn
) == JUMP_INSN
7429 && JUMP_LABEL (insn
) != 0
7430 && LABEL_NUSES (JUMP_LABEL (insn
)) == 1)
7431 cse_around_loop (JUMP_LABEL (insn
));
7433 free (qty_table
+ max_reg
);
7435 return to
? NEXT_INSN (to
) : 0;
7438 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
7439 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
7442 check_for_label_ref (rtl
, data
)
7446 rtx insn
= (rtx
) data
;
7448 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
7449 we must rerun jump since it needs to place the note. If this is a
7450 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
7451 since no REG_LABEL will be added. */
7452 return (GET_CODE (*rtl
) == LABEL_REF
7453 && ! LABEL_REF_NONLOCAL_P (*rtl
)
7454 && LABEL_P (XEXP (*rtl
, 0))
7455 && INSN_UID (XEXP (*rtl
, 0)) != 0
7456 && ! find_reg_note (insn
, REG_LABEL
, XEXP (*rtl
, 0)));
7459 /* Count the number of times registers are used (not set) in X.
7460 COUNTS is an array in which we accumulate the count, INCR is how much
7461 we count each register usage.
7463 Don't count a usage of DEST, which is the SET_DEST of a SET which
7464 contains X in its SET_SRC. This is because such a SET does not
7465 modify the liveness of DEST. */
7468 count_reg_usage (x
, counts
, dest
, incr
)
7481 switch (code
= GET_CODE (x
))
7485 counts
[REGNO (x
)] += incr
;
7499 /* If we are clobbering a MEM, mark any registers inside the address
7501 if (GET_CODE (XEXP (x
, 0)) == MEM
)
7502 count_reg_usage (XEXP (XEXP (x
, 0), 0), counts
, NULL_RTX
, incr
);
7506 /* Unless we are setting a REG, count everything in SET_DEST. */
7507 if (GET_CODE (SET_DEST (x
)) != REG
)
7508 count_reg_usage (SET_DEST (x
), counts
, NULL_RTX
, incr
);
7510 /* If SRC has side-effects, then we can't delete this insn, so the
7511 usage of SET_DEST inside SRC counts.
7513 ??? Strictly-speaking, we might be preserving this insn
7514 because some other SET has side-effects, but that's hard
7515 to do and can't happen now. */
7516 count_reg_usage (SET_SRC (x
), counts
,
7517 side_effects_p (SET_SRC (x
)) ? NULL_RTX
: SET_DEST (x
),
7522 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x
), counts
, NULL_RTX
, incr
);
7527 count_reg_usage (PATTERN (x
), counts
, NULL_RTX
, incr
);
7529 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7532 count_reg_usage (REG_NOTES (x
), counts
, NULL_RTX
, incr
);
7537 if (REG_NOTE_KIND (x
) == REG_EQUAL
7538 || (REG_NOTE_KIND (x
) != REG_NONNEG
&& GET_CODE (XEXP (x
,0)) == USE
))
7539 count_reg_usage (XEXP (x
, 0), counts
, NULL_RTX
, incr
);
7540 count_reg_usage (XEXP (x
, 1), counts
, NULL_RTX
, incr
);
7547 fmt
= GET_RTX_FORMAT (code
);
7548 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
7551 count_reg_usage (XEXP (x
, i
), counts
, dest
, incr
);
7552 else if (fmt
[i
] == 'E')
7553 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7554 count_reg_usage (XVECEXP (x
, i
, j
), counts
, dest
, incr
);
7558 /* Return true if set is live. */
7560 set_live_p (set
, insn
, counts
)
7562 rtx insn ATTRIBUTE_UNUSED
; /* Only used with HAVE_cc0. */
7569 if (set_noop_p (set
))
7573 else if (GET_CODE (SET_DEST (set
)) == CC0
7574 && !side_effects_p (SET_SRC (set
))
7575 && ((tem
= next_nonnote_insn (insn
)) == 0
7577 || !reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
7580 else if (GET_CODE (SET_DEST (set
)) != REG
7581 || REGNO (SET_DEST (set
)) < FIRST_PSEUDO_REGISTER
7582 || counts
[REGNO (SET_DEST (set
))] != 0
7583 || side_effects_p (SET_SRC (set
))
7584 /* An ADDRESSOF expression can turn into a use of the
7585 internal arg pointer, so always consider the
7586 internal arg pointer live. If it is truly dead,
7587 flow will delete the initializing insn. */
7588 || (SET_DEST (set
) == current_function_internal_arg_pointer
))
7593 /* Return true if insn is live. */
7596 insn_live_p (insn
, counts
)
7601 if (flag_non_call_exceptions
&& may_trap_p (PATTERN (insn
)))
7603 else if (GET_CODE (PATTERN (insn
)) == SET
)
7604 return set_live_p (PATTERN (insn
), insn
, counts
);
7605 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
7607 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
7609 rtx elt
= XVECEXP (PATTERN (insn
), 0, i
);
7611 if (GET_CODE (elt
) == SET
)
7613 if (set_live_p (elt
, insn
, counts
))
7616 else if (GET_CODE (elt
) != CLOBBER
&& GET_CODE (elt
) != USE
)
7625 /* Return true if libcall is dead as a whole. */
7628 dead_libcall_p (insn
, counts
)
7633 /* See if there's a REG_EQUAL note on this insn and try to
7634 replace the source with the REG_EQUAL expression.
7636 We assume that insns with REG_RETVALs can only be reg->reg
7637 copies at this point. */
7638 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
7641 rtx set
= single_set (insn
);
7642 rtx
new = simplify_rtx (XEXP (note
, 0));
7645 new = XEXP (note
, 0);
7647 /* While changing insn, we must update the counts accordingly. */
7648 count_reg_usage (insn
, counts
, NULL_RTX
, -1);
7650 if (set
&& validate_change (insn
, &SET_SRC (set
), new, 0))
7652 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
7653 remove_note (insn
, find_reg_note (insn
, REG_RETVAL
, NULL_RTX
));
7654 remove_note (insn
, note
);
7657 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
7662 /* Scan all the insns and delete any that are dead; i.e., they store a register
7663 that is never used or they copy a register to itself.
7665 This is used to remove insns made obviously dead by cse, loop or other
7666 optimizations. It improves the heuristics in loop since it won't try to
7667 move dead invariants out of loops or make givs for dead quantities. The
7668 remaining passes of the compilation are also sped up. */
7671 delete_trivially_dead_insns (insns
, nreg
)
7677 int in_libcall
= 0, dead_libcall
= 0;
7678 int ndead
= 0, nlastdead
, niterations
= 0;
7680 timevar_push (TV_DELETE_TRIVIALLY_DEAD
);
7681 /* First count the number of times each register is used. */
7682 counts
= (int *) xcalloc (nreg
, sizeof (int));
7683 for (insn
= next_real_insn (insns
); insn
; insn
= next_real_insn (insn
))
7684 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
7690 /* Go from the last insn to the first and delete insns that only set unused
7691 registers or copy a register to itself. As we delete an insn, remove
7692 usage counts for registers it uses.
7694 The first jump optimization pass may leave a real insn as the last
7695 insn in the function. We must not skip that insn or we may end
7696 up deleting code that is not really dead. */
7697 insn
= get_last_insn ();
7698 if (! INSN_P (insn
))
7699 insn
= prev_real_insn (insn
);
7701 for (; insn
; insn
= prev
)
7705 prev
= prev_real_insn (insn
);
7707 /* Don't delete any insns that are part of a libcall block unless
7708 we can delete the whole libcall block.
7710 Flow or loop might get confused if we did that. Remember
7711 that we are scanning backwards. */
7712 if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
7716 dead_libcall
= dead_libcall_p (insn
, counts
);
7718 else if (in_libcall
)
7719 live_insn
= ! dead_libcall
;
7721 live_insn
= insn_live_p (insn
, counts
);
7723 /* If this is a dead insn, delete it and show registers in it aren't
7728 count_reg_usage (insn
, counts
, NULL_RTX
, -1);
7729 delete_insn_and_edges (insn
);
7733 if (find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))
7740 while (ndead
!= nlastdead
);
7742 if (rtl_dump_file
&& ndead
)
7743 fprintf (rtl_dump_file
, "Deleted %i trivially dead insns; %i iterations\n",
7744 ndead
, niterations
);
7747 timevar_pop (TV_DELETE_TRIVIALLY_DEAD
);