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, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* stdio.h must precede rtl.h for FFS. */
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
31 #include "basic-block.h"
34 #include "insn-config.h"
45 #include "rtlhooks-def.h"
46 #include "tree-pass.h"
48 /* The basic idea of common subexpression elimination is to go
49 through the code, keeping a record of expressions that would
50 have the same value at the current scan point, and replacing
51 expressions encountered with the cheapest equivalent expression.
53 It is too complicated to keep track of the different possibilities
54 when control paths merge in this code; so, at each label, we forget all
55 that is known and start fresh. This can be described as processing each
56 extended basic block separately. We have a separate pass to perform
59 Note CSE can turn a conditional or computed jump into a nop or
60 an unconditional jump. When this occurs we arrange to run the jump
61 optimizer after CSE to delete the unreachable code.
63 We use two data structures to record the equivalent expressions:
64 a hash table for most expressions, and a vector of "quantity
65 numbers" to record equivalent (pseudo) registers.
67 The use of the special data structure for registers is desirable
68 because it is faster. It is possible because registers references
69 contain a fairly small number, the register number, taken from
70 a contiguously allocated series, and two register references are
71 identical if they have the same number. General expressions
72 do not have any such thing, so the only way to retrieve the
73 information recorded on an expression other than a register
74 is to keep it in a hash table.
76 Registers and "quantity numbers":
78 At the start of each basic block, all of the (hardware and pseudo)
79 registers used in the function are given distinct quantity
80 numbers to indicate their contents. During scan, when the code
81 copies one register into another, we copy the quantity number.
82 When a register is loaded in any other way, we allocate a new
83 quantity number to describe the value generated by this operation.
84 `REG_QTY (N)' records what quantity register N is currently thought
87 All real quantity numbers are greater than or equal to zero.
88 If register N has not been assigned a quantity, `REG_QTY (N)' will
89 equal -N - 1, which is always negative.
91 Quantity numbers below zero do not exist and none of the `qty_table'
92 entries should be referenced with a negative index.
94 We also maintain a bidirectional chain of registers for each
95 quantity number. The `qty_table` members `first_reg' and `last_reg',
96 and `reg_eqv_table' members `next' and `prev' hold these chains.
98 The first register in a chain is the one whose lifespan is least local.
99 Among equals, it is the one that was seen first.
100 We replace any equivalent register with that one.
102 If two registers have the same quantity number, it must be true that
103 REG expressions with qty_table `mode' must be in the hash table for both
104 registers and must be in the same class.
106 The converse is not true. Since hard registers may be referenced in
107 any mode, two REG expressions might be equivalent in the hash table
108 but not have the same quantity number if the quantity number of one
109 of the registers is not the same mode as those expressions.
111 Constants and quantity numbers
113 When a quantity has a known constant value, that value is stored
114 in the appropriate qty_table `const_rtx'. This is in addition to
115 putting the constant in the hash table as is usual for non-regs.
117 Whether a reg or a constant is preferred is determined by the configuration
118 macro CONST_COSTS and will often depend on the constant value. In any
119 event, expressions containing constants can be simplified, by fold_rtx.
121 When a quantity has a known nearly constant value (such as an address
122 of a stack slot), that value is stored in the appropriate qty_table
125 Integer constants don't have a machine mode. However, cse
126 determines the intended machine mode from the destination
127 of the instruction that moves the constant. The machine mode
128 is recorded in the hash table along with the actual RTL
129 constant expression so that different modes are kept separate.
133 To record known equivalences among expressions in general
134 we use a hash table called `table'. It has a fixed number of buckets
135 that contain chains of `struct table_elt' elements for expressions.
136 These chains connect the elements whose expressions have the same
139 Other chains through the same elements connect the elements which
140 currently have equivalent values.
142 Register references in an expression are canonicalized before hashing
143 the expression. This is done using `reg_qty' and qty_table `first_reg'.
144 The hash code of a register reference is computed using the quantity
145 number, not the register number.
147 When the value of an expression changes, it is necessary to remove from the
148 hash table not just that expression but all expressions whose values
149 could be different as a result.
151 1. If the value changing is in memory, except in special cases
152 ANYTHING referring to memory could be changed. That is because
153 nobody knows where a pointer does not point.
154 The function `invalidate_memory' removes what is necessary.
156 The special cases are when the address is constant or is
157 a constant plus a fixed register such as the frame pointer
158 or a static chain pointer. When such addresses are stored in,
159 we can tell exactly which other such addresses must be invalidated
160 due to overlap. `invalidate' does this.
161 All expressions that refer to non-constant
162 memory addresses are also invalidated. `invalidate_memory' does this.
164 2. If the value changing is a register, all expressions
165 containing references to that register, and only those,
168 Because searching the entire hash table for expressions that contain
169 a register is very slow, we try to figure out when it isn't necessary.
170 Precisely, this is necessary only when expressions have been
171 entered in the hash table using this register, and then the value has
172 changed, and then another expression wants to be added to refer to
173 the register's new value. This sequence of circumstances is rare
174 within any one basic block.
176 `REG_TICK' and `REG_IN_TABLE', accessors for members of
177 cse_reg_info, are used to detect this case. REG_TICK (i) is
178 incremented whenever a value is stored in register i.
179 REG_IN_TABLE (i) holds -1 if no references to register i have been
180 entered in the table; otherwise, it contains the value REG_TICK (i)
181 had when the references were entered. If we want to enter a
182 reference and REG_IN_TABLE (i) != REG_TICK (i), we must scan and
183 remove old references. Until we want to enter a new entry, the
184 mere fact that the two vectors don't match makes the entries be
185 ignored if anyone tries to match them.
187 Registers themselves are entered in the hash table as well as in
188 the equivalent-register chains. However, `REG_TICK' and
189 `REG_IN_TABLE' do not apply to expressions which are simple
190 register references. These expressions are removed from the table
191 immediately when they become invalid, and this can be done even if
192 we do not immediately search for all the expressions that refer to
195 A CLOBBER rtx in an instruction invalidates its operand for further
196 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
197 invalidates everything that resides in memory.
201 Constant expressions that differ only by an additive integer
202 are called related. When a constant expression is put in
203 the table, the related expression with no constant term
204 is also entered. These are made to point at each other
205 so that it is possible to find out if there exists any
206 register equivalent to an expression related to a given expression. */
208 /* Length of qty_table vector. We know in advance we will not need
209 a quantity number this big. */
213 /* Next quantity number to be allocated.
214 This is 1 + the largest number needed so far. */
218 /* Per-qty information tracking.
220 `first_reg' and `last_reg' track the head and tail of the
221 chain of registers which currently contain this quantity.
223 `mode' contains the machine mode of this quantity.
225 `const_rtx' holds the rtx of the constant value of this
226 quantity, if known. A summations of the frame/arg pointer
227 and a constant can also be entered here. When this holds
228 a known value, `const_insn' is the insn which stored the
231 `comparison_{code,const,qty}' are used to track when a
232 comparison between a quantity and some constant or register has
233 been passed. In such a case, we know the results of the comparison
234 in case we see it again. These members record a comparison that
235 is known to be true. `comparison_code' holds the rtx code of such
236 a comparison, else it is set to UNKNOWN and the other two
237 comparison members are undefined. `comparison_const' holds
238 the constant being compared against, or zero if the comparison
239 is not against a constant. `comparison_qty' holds the quantity
240 being compared against when the result is known. If the comparison
241 is not with a register, `comparison_qty' is -1. */
243 struct qty_table_elem
247 rtx comparison_const
;
249 unsigned int first_reg
, last_reg
;
250 /* The sizes of these fields should match the sizes of the
251 code and mode fields of struct rtx_def (see rtl.h). */
252 ENUM_BITFIELD(rtx_code
) comparison_code
: 16;
253 ENUM_BITFIELD(machine_mode
) mode
: 8;
256 /* The table of all qtys, indexed by qty number. */
257 static struct qty_table_elem
*qty_table
;
259 /* Structure used to pass arguments via for_each_rtx to function
260 cse_change_cc_mode. */
261 struct change_cc_mode_args
268 /* For machines that have a CC0, we do not record its value in the hash
269 table since its use is guaranteed to be the insn immediately following
270 its definition and any other insn is presumed to invalidate it.
272 Instead, we store below the value last assigned to CC0. If it should
273 happen to be a constant, it is stored in preference to the actual
274 assigned value. In case it is a constant, we store the mode in which
275 the constant should be interpreted. */
277 static rtx prev_insn_cc0
;
278 static enum machine_mode prev_insn_cc0_mode
;
280 /* Previous actual insn. 0 if at first insn of basic block. */
282 static rtx prev_insn
;
285 /* Insn being scanned. */
287 static rtx this_insn
;
289 /* Index by register number, gives the number of the next (or
290 previous) register in the chain of registers sharing the same
293 Or -1 if this register is at the end of the chain.
295 If REG_QTY (N) == -N - 1, reg_eqv_table[N].next is undefined. */
297 /* Per-register equivalence chain. */
303 /* The table of all register equivalence chains. */
304 static struct reg_eqv_elem
*reg_eqv_table
;
308 /* The timestamp at which this register is initialized. */
309 unsigned int timestamp
;
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 table of cse_reg_info indexed by register numbers. */
330 static struct cse_reg_info
*cse_reg_info_table
;
332 /* The size of the above table. */
333 static unsigned int cse_reg_info_table_size
;
335 /* The index of the first entry that has not been initialized. */
336 static unsigned int cse_reg_info_table_first_uninitialized
;
338 /* The timestamp at the beginning of the current run of
339 cse_basic_block. We increment this variable at the beginning of
340 the current run of cse_basic_block. The timestamp field of a
341 cse_reg_info entry matches the value of this variable if and only
342 if the entry has been initialized during the current run of
344 static unsigned int cse_reg_info_timestamp
;
346 /* A HARD_REG_SET containing all the hard registers for which there is
347 currently a REG expression in the hash table. Note the difference
348 from the above variables, which indicate if the REG is mentioned in some
349 expression in the table. */
351 static HARD_REG_SET hard_regs_in_table
;
353 /* CUID of insn that starts the basic block currently being cse-processed. */
355 static int cse_basic_block_start
;
357 /* CUID of insn that ends the basic block currently being cse-processed. */
359 static int cse_basic_block_end
;
361 /* Vector mapping INSN_UIDs to cuids.
362 The cuids are like uids but increase monotonically always.
363 We use them to see whether a reg is used outside a given basic block. */
365 static int *uid_cuid
;
367 /* Highest UID in UID_CUID. */
370 /* Get the cuid of an insn. */
372 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
374 /* Nonzero if this pass has made changes, and therefore it's
375 worthwhile to run the garbage collector. */
377 static int cse_altered
;
379 /* Nonzero if cse has altered conditional jump insns
380 in such a way that jump optimization should be redone. */
382 static int cse_jumps_altered
;
384 /* Nonzero if we put a LABEL_REF into the hash table for an INSN without a
385 REG_LABEL, we have to rerun jump after CSE to put in the note. */
386 static int recorded_label_ref
;
388 /* canon_hash stores 1 in do_not_record
389 if it notices a reference to CC0, PC, or some other volatile
392 static int do_not_record
;
394 /* canon_hash stores 1 in hash_arg_in_memory
395 if it notices a reference to memory within the expression being hashed. */
397 static int hash_arg_in_memory
;
399 /* The hash table contains buckets which are chains of `struct table_elt's,
400 each recording one expression's information.
401 That expression is in the `exp' field.
403 The canon_exp field contains a canonical (from the point of view of
404 alias analysis) version of the `exp' field.
406 Those elements with the same hash code are chained in both directions
407 through the `next_same_hash' and `prev_same_hash' fields.
409 Each set of expressions with equivalent values
410 are on a two-way chain through the `next_same_value'
411 and `prev_same_value' fields, and all point with
412 the `first_same_value' field at the first element in
413 that chain. The chain is in order of increasing cost.
414 Each element's cost value is in its `cost' field.
416 The `in_memory' field is nonzero for elements that
417 involve any reference to memory. These elements are removed
418 whenever a write is done to an unidentified location in memory.
419 To be safe, we assume that a memory address is unidentified unless
420 the address is either a symbol constant or a constant plus
421 the frame pointer or argument pointer.
423 The `related_value' field is used to connect related expressions
424 (that differ by adding an integer).
425 The related expressions are chained in a circular fashion.
426 `related_value' is zero for expressions for which this
429 The `cost' field stores the cost of this element's expression.
430 The `regcost' field stores the value returned by approx_reg_cost for
431 this element's expression.
433 The `is_const' flag is set if the element is a constant (including
436 The `flag' field is used as a temporary during some search routines.
438 The `mode' field is usually the same as GET_MODE (`exp'), but
439 if `exp' is a CONST_INT and has no machine mode then the `mode'
440 field is the mode it was being used as. Each constant is
441 recorded separately for each mode it is used with. */
447 struct table_elt
*next_same_hash
;
448 struct table_elt
*prev_same_hash
;
449 struct table_elt
*next_same_value
;
450 struct table_elt
*prev_same_value
;
451 struct table_elt
*first_same_value
;
452 struct table_elt
*related_value
;
455 /* The size of this field should match the size
456 of the mode field of struct rtx_def (see rtl.h). */
457 ENUM_BITFIELD(machine_mode
) mode
: 8;
463 /* We don't want a lot of buckets, because we rarely have very many
464 things stored in the hash table, and a lot of buckets slows
465 down a lot of loops that happen frequently. */
467 #define HASH_SIZE (1 << HASH_SHIFT)
468 #define HASH_MASK (HASH_SIZE - 1)
470 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
471 register (hard registers may require `do_not_record' to be set). */
474 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
475 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
476 : canon_hash (X, M)) & HASH_MASK)
478 /* Like HASH, but without side-effects. */
479 #define SAFE_HASH(X, M) \
480 ((REG_P (X) && REGNO (X) >= FIRST_PSEUDO_REGISTER \
481 ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \
482 : safe_hash (X, M)) & HASH_MASK)
484 /* Determine whether register number N is considered a fixed register for the
485 purpose of approximating register costs.
486 It is desirable to replace other regs with fixed regs, to reduce need for
488 A reg wins if it is either the frame pointer or designated as fixed. */
489 #define FIXED_REGNO_P(N) \
490 ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
491 || fixed_regs[N] || global_regs[N])
493 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
494 hard registers and pointers into the frame are the cheapest with a cost
495 of 0. Next come pseudos with a cost of one and other hard registers with
496 a cost of 2. Aside from these special cases, call `rtx_cost'. */
498 #define CHEAP_REGNO(N) \
499 (REGNO_PTR_FRAME_P(N) \
500 || (HARD_REGISTER_NUM_P (N) \
501 && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))
503 #define COST(X) (REG_P (X) ? 0 : notreg_cost (X, SET))
504 #define COST_IN(X,OUTER) (REG_P (X) ? 0 : notreg_cost (X, OUTER))
506 /* Get the number of times this register has been updated in this
509 #define REG_TICK(N) (get_cse_reg_info (N)->reg_tick)
511 /* Get the point at which REG was recorded in the table. */
513 #define REG_IN_TABLE(N) (get_cse_reg_info (N)->reg_in_table)
515 /* Get the SUBREG set at the last increment to REG_TICK (-1 if not a
518 #define SUBREG_TICKED(N) (get_cse_reg_info (N)->subreg_ticked)
520 /* Get the quantity number for REG. */
522 #define REG_QTY(N) (get_cse_reg_info (N)->reg_qty)
524 /* Determine if the quantity number for register X represents a valid index
525 into the qty_table. */
527 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
529 static struct table_elt
*table
[HASH_SIZE
];
531 /* Chain of `struct table_elt's made so far for this function
532 but currently removed from the table. */
534 static struct table_elt
*free_element_chain
;
536 /* Set to the cost of a constant pool reference if one was found for a
537 symbolic constant. If this was found, it means we should try to
538 convert constants into constant pool entries if they don't fit in
541 static int constant_pool_entries_cost
;
542 static int constant_pool_entries_regcost
;
544 /* This data describes a block that will be processed by cse_basic_block. */
546 struct cse_basic_block_data
548 /* Lowest CUID value of insns in block. */
550 /* Highest CUID value of insns in block. */
552 /* Total number of SETs in block. */
554 /* Last insn in the block. */
556 /* Size of current branch path, if any. */
558 /* Current branch path, indicating which branches will be taken. */
561 /* The branch insn. */
563 /* Whether it should be taken or not. AROUND is the same as taken
564 except that it is used when the destination label is not preceded
566 enum taken
{PATH_TAKEN
, PATH_NOT_TAKEN
, PATH_AROUND
} status
;
570 static bool fixed_base_plus_p (rtx x
);
571 static int notreg_cost (rtx
, enum rtx_code
);
572 static int approx_reg_cost_1 (rtx
*, void *);
573 static int approx_reg_cost (rtx
);
574 static int preferable (int, int, int, int);
575 static void new_basic_block (void);
576 static void make_new_qty (unsigned int, enum machine_mode
);
577 static void make_regs_eqv (unsigned int, unsigned int);
578 static void delete_reg_equiv (unsigned int);
579 static int mention_regs (rtx
);
580 static int insert_regs (rtx
, struct table_elt
*, int);
581 static void remove_from_table (struct table_elt
*, unsigned);
582 static struct table_elt
*lookup (rtx
, unsigned, enum machine_mode
);
583 static struct table_elt
*lookup_for_remove (rtx
, unsigned, enum machine_mode
);
584 static rtx
lookup_as_function (rtx
, enum rtx_code
);
585 static struct table_elt
*insert (rtx
, struct table_elt
*, unsigned,
587 static void merge_equiv_classes (struct table_elt
*, struct table_elt
*);
588 static void invalidate (rtx
, enum machine_mode
);
589 static int cse_rtx_varies_p (rtx
, int);
590 static void remove_invalid_refs (unsigned int);
591 static void remove_invalid_subreg_refs (unsigned int, unsigned int,
593 static void rehash_using_reg (rtx
);
594 static void invalidate_memory (void);
595 static void invalidate_for_call (void);
596 static rtx
use_related_value (rtx
, struct table_elt
*);
598 static inline unsigned canon_hash (rtx
, enum machine_mode
);
599 static inline unsigned safe_hash (rtx
, enum machine_mode
);
600 static unsigned hash_rtx_string (const char *);
602 static rtx
canon_reg (rtx
, rtx
);
603 static enum rtx_code
find_comparison_args (enum rtx_code
, rtx
*, rtx
*,
605 enum machine_mode
*);
606 static rtx
fold_rtx (rtx
, rtx
);
607 static rtx
equiv_constant (rtx
);
608 static void record_jump_equiv (rtx
, int);
609 static void record_jump_cond (enum rtx_code
, enum machine_mode
, rtx
, rtx
,
611 static void cse_insn (rtx
, rtx
);
612 static void cse_end_of_basic_block (rtx
, struct cse_basic_block_data
*,
614 static int addr_affects_sp_p (rtx
);
615 static void invalidate_from_clobbers (rtx
);
616 static rtx
cse_process_notes (rtx
, rtx
);
617 static void invalidate_skipped_set (rtx
, rtx
, void *);
618 static void invalidate_skipped_block (rtx
);
619 static rtx
cse_basic_block (rtx
, rtx
, struct branch_path
*);
620 static void count_reg_usage (rtx
, int *, rtx
, int);
621 static int check_for_label_ref (rtx
*, void *);
622 extern void dump_class (struct table_elt
*);
623 static void get_cse_reg_info_1 (unsigned int regno
);
624 static struct cse_reg_info
* get_cse_reg_info (unsigned int regno
);
625 static int check_dependence (rtx
*, void *);
627 static void flush_hash_table (void);
628 static bool insn_live_p (rtx
, int *);
629 static bool set_live_p (rtx
, rtx
, int *);
630 static bool dead_libcall_p (rtx
, int *);
631 static int cse_change_cc_mode (rtx
*, void *);
632 static void cse_change_cc_mode_insn (rtx
, rtx
);
633 static void cse_change_cc_mode_insns (rtx
, rtx
, rtx
);
634 static enum machine_mode
cse_cc_succs (basic_block
, rtx
, rtx
, bool);
637 #undef RTL_HOOKS_GEN_LOWPART
638 #define RTL_HOOKS_GEN_LOWPART gen_lowpart_if_possible
640 static const struct rtl_hooks cse_rtl_hooks
= RTL_HOOKS_INITIALIZER
;
642 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
643 virtual regs here because the simplify_*_operation routines are called
644 by integrate.c, which is called before virtual register instantiation. */
647 fixed_base_plus_p (rtx x
)
649 switch (GET_CODE (x
))
652 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
)
654 if (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
656 if (REGNO (x
) >= FIRST_VIRTUAL_REGISTER
657 && REGNO (x
) <= LAST_VIRTUAL_REGISTER
)
662 if (GET_CODE (XEXP (x
, 1)) != CONST_INT
)
664 return fixed_base_plus_p (XEXP (x
, 0));
671 /* Dump the expressions in the equivalence class indicated by CLASSP.
672 This function is used only for debugging. */
674 dump_class (struct table_elt
*classp
)
676 struct table_elt
*elt
;
678 fprintf (stderr
, "Equivalence chain for ");
679 print_rtl (stderr
, classp
->exp
);
680 fprintf (stderr
, ": \n");
682 for (elt
= classp
->first_same_value
; elt
; elt
= elt
->next_same_value
)
684 print_rtl (stderr
, elt
->exp
);
685 fprintf (stderr
, "\n");
689 /* Subroutine of approx_reg_cost; called through for_each_rtx. */
692 approx_reg_cost_1 (rtx
*xp
, void *data
)
699 unsigned int regno
= REGNO (x
);
701 if (! CHEAP_REGNO (regno
))
703 if (regno
< FIRST_PSEUDO_REGISTER
)
705 if (SMALL_REGISTER_CLASSES
)
717 /* Return an estimate of the cost of the registers used in an rtx.
718 This is mostly the number of different REG expressions in the rtx;
719 however for some exceptions like fixed registers we use a cost of
720 0. If any other hard register reference occurs, return MAX_COST. */
723 approx_reg_cost (rtx x
)
727 if (for_each_rtx (&x
, approx_reg_cost_1
, (void *) &cost
))
733 /* Return a negative value if an rtx A, whose costs are given by COST_A
734 and REGCOST_A, is more desirable than an rtx B.
735 Return a positive value if A is less desirable, or 0 if the two are
738 preferable (int cost_a
, int regcost_a
, int cost_b
, int regcost_b
)
740 /* First, get rid of cases involving expressions that are entirely
742 if (cost_a
!= cost_b
)
744 if (cost_a
== MAX_COST
)
746 if (cost_b
== MAX_COST
)
750 /* Avoid extending lifetimes of hardregs. */
751 if (regcost_a
!= regcost_b
)
753 if (regcost_a
== MAX_COST
)
755 if (regcost_b
== MAX_COST
)
759 /* Normal operation costs take precedence. */
760 if (cost_a
!= cost_b
)
761 return cost_a
- cost_b
;
762 /* Only if these are identical consider effects on register pressure. */
763 if (regcost_a
!= regcost_b
)
764 return regcost_a
- regcost_b
;
768 /* Internal function, to compute cost when X is not a register; called
769 from COST macro to keep it simple. */
772 notreg_cost (rtx x
, enum rtx_code outer
)
774 return ((GET_CODE (x
) == SUBREG
775 && REG_P (SUBREG_REG (x
))
776 && GET_MODE_CLASS (GET_MODE (x
)) == MODE_INT
777 && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x
))) == MODE_INT
778 && (GET_MODE_SIZE (GET_MODE (x
))
779 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
780 && subreg_lowpart_p (x
)
781 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x
)),
782 GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x
)))))
784 : rtx_cost (x
, outer
) * 2);
788 /* Initialize CSE_REG_INFO_TABLE. */
791 init_cse_reg_info (unsigned int nregs
)
793 /* Do we need to grow the table? */
794 if (nregs
> cse_reg_info_table_size
)
796 unsigned int new_size
;
798 if (cse_reg_info_table_size
< 2048)
800 /* Compute a new size that is a power of 2 and no smaller
801 than the large of NREGS and 64. */
802 new_size
= (cse_reg_info_table_size
803 ? cse_reg_info_table_size
: 64);
805 while (new_size
< nregs
)
810 /* If we need a big table, allocate just enough to hold
815 /* Reallocate the table with NEW_SIZE entries. */
816 if (cse_reg_info_table
)
817 free (cse_reg_info_table
);
818 cse_reg_info_table
= XNEWVEC (struct cse_reg_info
, new_size
);
819 cse_reg_info_table_size
= new_size
;
820 cse_reg_info_table_first_uninitialized
= 0;
823 /* Do we have all of the first NREGS entries initialized? */
824 if (cse_reg_info_table_first_uninitialized
< nregs
)
826 unsigned int old_timestamp
= cse_reg_info_timestamp
- 1;
829 /* Put the old timestamp on newly allocated entries so that they
830 will all be considered out of date. We do not touch those
831 entries beyond the first NREGS entries to be nice to the
833 for (i
= cse_reg_info_table_first_uninitialized
; i
< nregs
; i
++)
834 cse_reg_info_table
[i
].timestamp
= old_timestamp
;
836 cse_reg_info_table_first_uninitialized
= nregs
;
840 /* Given REGNO, initialize the cse_reg_info entry for REGNO. */
843 get_cse_reg_info_1 (unsigned int regno
)
845 /* Set TIMESTAMP field to CSE_REG_INFO_TIMESTAMP so that this
846 entry will be considered to have been initialized. */
847 cse_reg_info_table
[regno
].timestamp
= cse_reg_info_timestamp
;
849 /* Initialize the rest of the entry. */
850 cse_reg_info_table
[regno
].reg_tick
= 1;
851 cse_reg_info_table
[regno
].reg_in_table
= -1;
852 cse_reg_info_table
[regno
].subreg_ticked
= -1;
853 cse_reg_info_table
[regno
].reg_qty
= -regno
- 1;
856 /* Find a cse_reg_info entry for REGNO. */
858 static inline struct cse_reg_info
*
859 get_cse_reg_info (unsigned int regno
)
861 struct cse_reg_info
*p
= &cse_reg_info_table
[regno
];
863 /* If this entry has not been initialized, go ahead and initialize
865 if (p
->timestamp
!= cse_reg_info_timestamp
)
866 get_cse_reg_info_1 (regno
);
871 /* Clear the hash table and initialize each register with its own quantity,
872 for a new basic block. */
875 new_basic_block (void)
881 /* Invalidate cse_reg_info_table. */
882 cse_reg_info_timestamp
++;
884 /* Clear out hash table state for this pass. */
885 CLEAR_HARD_REG_SET (hard_regs_in_table
);
887 /* The per-quantity values used to be initialized here, but it is
888 much faster to initialize each as it is made in `make_new_qty'. */
890 for (i
= 0; i
< HASH_SIZE
; i
++)
892 struct table_elt
*first
;
897 struct table_elt
*last
= first
;
901 while (last
->next_same_hash
!= NULL
)
902 last
= last
->next_same_hash
;
904 /* Now relink this hash entire chain into
905 the free element list. */
907 last
->next_same_hash
= free_element_chain
;
908 free_element_chain
= first
;
918 /* Say that register REG contains a quantity in mode MODE not in any
919 register before and initialize that quantity. */
922 make_new_qty (unsigned int reg
, enum machine_mode mode
)
925 struct qty_table_elem
*ent
;
926 struct reg_eqv_elem
*eqv
;
928 gcc_assert (next_qty
< max_qty
);
930 q
= REG_QTY (reg
) = next_qty
++;
932 ent
->first_reg
= reg
;
935 ent
->const_rtx
= ent
->const_insn
= NULL_RTX
;
936 ent
->comparison_code
= UNKNOWN
;
938 eqv
= ®_eqv_table
[reg
];
939 eqv
->next
= eqv
->prev
= -1;
942 /* Make reg NEW equivalent to reg OLD.
943 OLD is not changing; NEW is. */
946 make_regs_eqv (unsigned int new, unsigned int old
)
948 unsigned int lastr
, firstr
;
949 int q
= REG_QTY (old
);
950 struct qty_table_elem
*ent
;
954 /* Nothing should become eqv until it has a "non-invalid" qty number. */
955 gcc_assert (REGNO_QTY_VALID_P (old
));
958 firstr
= ent
->first_reg
;
959 lastr
= ent
->last_reg
;
961 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
962 hard regs. Among pseudos, if NEW will live longer than any other reg
963 of the same qty, and that is beyond the current basic block,
964 make it the new canonical replacement for this qty. */
965 if (! (firstr
< FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (firstr
))
966 /* Certain fixed registers might be of the class NO_REGS. This means
967 that not only can they not be allocated by the compiler, but
968 they cannot be used in substitutions or canonicalizations
970 && (new >= FIRST_PSEUDO_REGISTER
|| REGNO_REG_CLASS (new) != NO_REGS
)
971 && ((new < FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (new))
972 || (new >= FIRST_PSEUDO_REGISTER
973 && (firstr
< FIRST_PSEUDO_REGISTER
974 || ((uid_cuid
[REGNO_LAST_UID (new)] > cse_basic_block_end
975 || (uid_cuid
[REGNO_FIRST_UID (new)]
976 < cse_basic_block_start
))
977 && (uid_cuid
[REGNO_LAST_UID (new)]
978 > uid_cuid
[REGNO_LAST_UID (firstr
)]))))))
980 reg_eqv_table
[firstr
].prev
= new;
981 reg_eqv_table
[new].next
= firstr
;
982 reg_eqv_table
[new].prev
= -1;
983 ent
->first_reg
= new;
987 /* If NEW is a hard reg (known to be non-fixed), insert at end.
988 Otherwise, insert before any non-fixed hard regs that are at the
989 end. Registers of class NO_REGS cannot be used as an
990 equivalent for anything. */
991 while (lastr
< FIRST_PSEUDO_REGISTER
&& reg_eqv_table
[lastr
].prev
>= 0
992 && (REGNO_REG_CLASS (lastr
) == NO_REGS
|| ! FIXED_REGNO_P (lastr
))
993 && new >= FIRST_PSEUDO_REGISTER
)
994 lastr
= reg_eqv_table
[lastr
].prev
;
995 reg_eqv_table
[new].next
= reg_eqv_table
[lastr
].next
;
996 if (reg_eqv_table
[lastr
].next
>= 0)
997 reg_eqv_table
[reg_eqv_table
[lastr
].next
].prev
= new;
999 qty_table
[q
].last_reg
= new;
1000 reg_eqv_table
[lastr
].next
= new;
1001 reg_eqv_table
[new].prev
= lastr
;
1005 /* Remove REG from its equivalence class. */
1008 delete_reg_equiv (unsigned int reg
)
1010 struct qty_table_elem
*ent
;
1011 int q
= REG_QTY (reg
);
1014 /* If invalid, do nothing. */
1015 if (! REGNO_QTY_VALID_P (reg
))
1018 ent
= &qty_table
[q
];
1020 p
= reg_eqv_table
[reg
].prev
;
1021 n
= reg_eqv_table
[reg
].next
;
1024 reg_eqv_table
[n
].prev
= p
;
1028 reg_eqv_table
[p
].next
= n
;
1032 REG_QTY (reg
) = -reg
- 1;
1035 /* Remove any invalid expressions from the hash table
1036 that refer to any of the registers contained in expression X.
1038 Make sure that newly inserted references to those registers
1039 as subexpressions will be considered valid.
1041 mention_regs is not called when a register itself
1042 is being stored in the table.
1044 Return 1 if we have done something that may have changed the hash code
1048 mention_regs (rtx x
)
1058 code
= GET_CODE (x
);
1061 unsigned int regno
= REGNO (x
);
1062 unsigned int endregno
1063 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
1064 : hard_regno_nregs
[regno
][GET_MODE (x
)]);
1067 for (i
= regno
; i
< endregno
; i
++)
1069 if (REG_IN_TABLE (i
) >= 0 && REG_IN_TABLE (i
) != REG_TICK (i
))
1070 remove_invalid_refs (i
);
1072 REG_IN_TABLE (i
) = REG_TICK (i
);
1073 SUBREG_TICKED (i
) = -1;
1079 /* If this is a SUBREG, we don't want to discard other SUBREGs of the same
1080 pseudo if they don't use overlapping words. We handle only pseudos
1081 here for simplicity. */
1082 if (code
== SUBREG
&& REG_P (SUBREG_REG (x
))
1083 && REGNO (SUBREG_REG (x
)) >= FIRST_PSEUDO_REGISTER
)
1085 unsigned int i
= REGNO (SUBREG_REG (x
));
1087 if (REG_IN_TABLE (i
) >= 0 && REG_IN_TABLE (i
) != REG_TICK (i
))
1089 /* If REG_IN_TABLE (i) differs from REG_TICK (i) by one, and
1090 the last store to this register really stored into this
1091 subreg, then remove the memory of this subreg.
1092 Otherwise, remove any memory of the entire register and
1093 all its subregs from the table. */
1094 if (REG_TICK (i
) - REG_IN_TABLE (i
) > 1
1095 || SUBREG_TICKED (i
) != REGNO (SUBREG_REG (x
)))
1096 remove_invalid_refs (i
);
1098 remove_invalid_subreg_refs (i
, SUBREG_BYTE (x
), GET_MODE (x
));
1101 REG_IN_TABLE (i
) = REG_TICK (i
);
1102 SUBREG_TICKED (i
) = REGNO (SUBREG_REG (x
));
1106 /* If X is a comparison or a COMPARE and either operand is a register
1107 that does not have a quantity, give it one. This is so that a later
1108 call to record_jump_equiv won't cause X to be assigned a different
1109 hash code and not found in the table after that call.
1111 It is not necessary to do this here, since rehash_using_reg can
1112 fix up the table later, but doing this here eliminates the need to
1113 call that expensive function in the most common case where the only
1114 use of the register is in the comparison. */
1116 if (code
== COMPARE
|| COMPARISON_P (x
))
1118 if (REG_P (XEXP (x
, 0))
1119 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0))))
1120 if (insert_regs (XEXP (x
, 0), NULL
, 0))
1122 rehash_using_reg (XEXP (x
, 0));
1126 if (REG_P (XEXP (x
, 1))
1127 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 1))))
1128 if (insert_regs (XEXP (x
, 1), NULL
, 0))
1130 rehash_using_reg (XEXP (x
, 1));
1135 fmt
= GET_RTX_FORMAT (code
);
1136 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1138 changed
|= mention_regs (XEXP (x
, i
));
1139 else if (fmt
[i
] == 'E')
1140 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1141 changed
|= mention_regs (XVECEXP (x
, i
, j
));
1146 /* Update the register quantities for inserting X into the hash table
1147 with a value equivalent to CLASSP.
1148 (If the class does not contain a REG, it is irrelevant.)
1149 If MODIFIED is nonzero, X is a destination; it is being modified.
1150 Note that delete_reg_equiv should be called on a register
1151 before insert_regs is done on that register with MODIFIED != 0.
1153 Nonzero value means that elements of reg_qty have changed
1154 so X's hash code may be different. */
1157 insert_regs (rtx x
, struct table_elt
*classp
, int modified
)
1161 unsigned int regno
= REGNO (x
);
1164 /* If REGNO is in the equivalence table already but is of the
1165 wrong mode for that equivalence, don't do anything here. */
1167 qty_valid
= REGNO_QTY_VALID_P (regno
);
1170 struct qty_table_elem
*ent
= &qty_table
[REG_QTY (regno
)];
1172 if (ent
->mode
!= GET_MODE (x
))
1176 if (modified
|| ! qty_valid
)
1179 for (classp
= classp
->first_same_value
;
1181 classp
= classp
->next_same_value
)
1182 if (REG_P (classp
->exp
)
1183 && GET_MODE (classp
->exp
) == GET_MODE (x
))
1185 unsigned c_regno
= REGNO (classp
->exp
);
1187 gcc_assert (REGNO_QTY_VALID_P (c_regno
));
1189 /* Suppose that 5 is hard reg and 100 and 101 are
1192 (set (reg:si 100) (reg:si 5))
1193 (set (reg:si 5) (reg:si 100))
1194 (set (reg:di 101) (reg:di 5))
1196 We would now set REG_QTY (101) = REG_QTY (5), but the
1197 entry for 5 is in SImode. When we use this later in
1198 copy propagation, we get the register in wrong mode. */
1199 if (qty_table
[REG_QTY (c_regno
)].mode
!= GET_MODE (x
))
1202 make_regs_eqv (regno
, c_regno
);
1206 /* Mention_regs for a SUBREG checks if REG_TICK is exactly one larger
1207 than REG_IN_TABLE to find out if there was only a single preceding
1208 invalidation - for the SUBREG - or another one, which would be
1209 for the full register. However, if we find here that REG_TICK
1210 indicates that the register is invalid, it means that it has
1211 been invalidated in a separate operation. The SUBREG might be used
1212 now (then this is a recursive call), or we might use the full REG
1213 now and a SUBREG of it later. So bump up REG_TICK so that
1214 mention_regs will do the right thing. */
1216 && REG_IN_TABLE (regno
) >= 0
1217 && REG_TICK (regno
) == REG_IN_TABLE (regno
) + 1)
1219 make_new_qty (regno
, GET_MODE (x
));
1226 /* If X is a SUBREG, we will likely be inserting the inner register in the
1227 table. If that register doesn't have an assigned quantity number at
1228 this point but does later, the insertion that we will be doing now will
1229 not be accessible because its hash code will have changed. So assign
1230 a quantity number now. */
1232 else if (GET_CODE (x
) == SUBREG
&& REG_P (SUBREG_REG (x
))
1233 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x
))))
1235 insert_regs (SUBREG_REG (x
), NULL
, 0);
1240 return mention_regs (x
);
1243 /* Look in or update the hash table. */
1245 /* Remove table element ELT from use in the table.
1246 HASH is its hash code, made using the HASH macro.
1247 It's an argument because often that is known in advance
1248 and we save much time not recomputing it. */
1251 remove_from_table (struct table_elt
*elt
, unsigned int hash
)
1256 /* Mark this element as removed. See cse_insn. */
1257 elt
->first_same_value
= 0;
1259 /* Remove the table element from its equivalence class. */
1262 struct table_elt
*prev
= elt
->prev_same_value
;
1263 struct table_elt
*next
= elt
->next_same_value
;
1266 next
->prev_same_value
= prev
;
1269 prev
->next_same_value
= next
;
1272 struct table_elt
*newfirst
= next
;
1275 next
->first_same_value
= newfirst
;
1276 next
= next
->next_same_value
;
1281 /* Remove the table element from its hash bucket. */
1284 struct table_elt
*prev
= elt
->prev_same_hash
;
1285 struct table_elt
*next
= elt
->next_same_hash
;
1288 next
->prev_same_hash
= prev
;
1291 prev
->next_same_hash
= next
;
1292 else if (table
[hash
] == elt
)
1296 /* This entry is not in the proper hash bucket. This can happen
1297 when two classes were merged by `merge_equiv_classes'. Search
1298 for the hash bucket that it heads. This happens only very
1299 rarely, so the cost is acceptable. */
1300 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
1301 if (table
[hash
] == elt
)
1306 /* Remove the table element from its related-value circular chain. */
1308 if (elt
->related_value
!= 0 && elt
->related_value
!= elt
)
1310 struct table_elt
*p
= elt
->related_value
;
1312 while (p
->related_value
!= elt
)
1313 p
= p
->related_value
;
1314 p
->related_value
= elt
->related_value
;
1315 if (p
->related_value
== p
)
1316 p
->related_value
= 0;
1319 /* Now add it to the free element chain. */
1320 elt
->next_same_hash
= free_element_chain
;
1321 free_element_chain
= elt
;
1324 /* Look up X in the hash table and return its table element,
1325 or 0 if X is not in the table.
1327 MODE is the machine-mode of X, or if X is an integer constant
1328 with VOIDmode then MODE is the mode with which X will be used.
1330 Here we are satisfied to find an expression whose tree structure
1333 static struct table_elt
*
1334 lookup (rtx x
, unsigned int hash
, enum machine_mode mode
)
1336 struct table_elt
*p
;
1338 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1339 if (mode
== p
->mode
&& ((x
== p
->exp
&& REG_P (x
))
1340 || exp_equiv_p (x
, p
->exp
, !REG_P (x
), false)))
1346 /* Like `lookup' but don't care whether the table element uses invalid regs.
1347 Also ignore discrepancies in the machine mode of a register. */
1349 static struct table_elt
*
1350 lookup_for_remove (rtx x
, unsigned int hash
, enum machine_mode mode
)
1352 struct table_elt
*p
;
1356 unsigned int regno
= REGNO (x
);
1358 /* Don't check the machine mode when comparing registers;
1359 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1360 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1362 && REGNO (p
->exp
) == regno
)
1367 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1369 && (x
== p
->exp
|| exp_equiv_p (x
, p
->exp
, 0, false)))
1376 /* Look for an expression equivalent to X and with code CODE.
1377 If one is found, return that expression. */
1380 lookup_as_function (rtx x
, enum rtx_code code
)
1383 = lookup (x
, SAFE_HASH (x
, VOIDmode
), GET_MODE (x
));
1385 /* If we are looking for a CONST_INT, the mode doesn't really matter, as
1386 long as we are narrowing. So if we looked in vain for a mode narrower
1387 than word_mode before, look for word_mode now. */
1388 if (p
== 0 && code
== CONST_INT
1389 && GET_MODE_SIZE (GET_MODE (x
)) < GET_MODE_SIZE (word_mode
))
1392 PUT_MODE (x
, word_mode
);
1393 p
= lookup (x
, SAFE_HASH (x
, VOIDmode
), word_mode
);
1399 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
1400 if (GET_CODE (p
->exp
) == code
1401 /* Make sure this is a valid entry in the table. */
1402 && exp_equiv_p (p
->exp
, p
->exp
, 1, false))
1408 /* Insert X in the hash table, assuming HASH is its hash code
1409 and CLASSP is an element of the class it should go in
1410 (or 0 if a new class should be made).
1411 It is inserted at the proper position to keep the class in
1412 the order cheapest first.
1414 MODE is the machine-mode of X, or if X is an integer constant
1415 with VOIDmode then MODE is the mode with which X will be used.
1417 For elements of equal cheapness, the most recent one
1418 goes in front, except that the first element in the list
1419 remains first unless a cheaper element is added. The order of
1420 pseudo-registers does not matter, as canon_reg will be called to
1421 find the cheapest when a register is retrieved from the table.
1423 The in_memory field in the hash table element is set to 0.
1424 The caller must set it nonzero if appropriate.
1426 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1427 and if insert_regs returns a nonzero value
1428 you must then recompute its hash code before calling here.
1430 If necessary, update table showing constant values of quantities. */
1432 #define CHEAPER(X, Y) \
1433 (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
1435 static struct table_elt
*
1436 insert (rtx x
, struct table_elt
*classp
, unsigned int hash
, enum machine_mode mode
)
1438 struct table_elt
*elt
;
1440 /* If X is a register and we haven't made a quantity for it,
1441 something is wrong. */
1442 gcc_assert (!REG_P (x
) || REGNO_QTY_VALID_P (REGNO (x
)));
1444 /* If X is a hard register, show it is being put in the table. */
1445 if (REG_P (x
) && REGNO (x
) < FIRST_PSEUDO_REGISTER
)
1447 unsigned int regno
= REGNO (x
);
1448 unsigned int endregno
= regno
+ hard_regno_nregs
[regno
][GET_MODE (x
)];
1451 for (i
= regno
; i
< endregno
; i
++)
1452 SET_HARD_REG_BIT (hard_regs_in_table
, i
);
1455 /* Put an element for X into the right hash bucket. */
1457 elt
= free_element_chain
;
1459 free_element_chain
= elt
->next_same_hash
;
1461 elt
= XNEW (struct table_elt
);
1464 elt
->canon_exp
= NULL_RTX
;
1465 elt
->cost
= COST (x
);
1466 elt
->regcost
= approx_reg_cost (x
);
1467 elt
->next_same_value
= 0;
1468 elt
->prev_same_value
= 0;
1469 elt
->next_same_hash
= table
[hash
];
1470 elt
->prev_same_hash
= 0;
1471 elt
->related_value
= 0;
1474 elt
->is_const
= (CONSTANT_P (x
) || fixed_base_plus_p (x
));
1477 table
[hash
]->prev_same_hash
= elt
;
1480 /* Put it into the proper value-class. */
1483 classp
= classp
->first_same_value
;
1484 if (CHEAPER (elt
, classp
))
1485 /* Insert at the head of the class. */
1487 struct table_elt
*p
;
1488 elt
->next_same_value
= classp
;
1489 classp
->prev_same_value
= elt
;
1490 elt
->first_same_value
= elt
;
1492 for (p
= classp
; p
; p
= p
->next_same_value
)
1493 p
->first_same_value
= elt
;
1497 /* Insert not at head of the class. */
1498 /* Put it after the last element cheaper than X. */
1499 struct table_elt
*p
, *next
;
1501 for (p
= classp
; (next
= p
->next_same_value
) && CHEAPER (next
, elt
);
1504 /* Put it after P and before NEXT. */
1505 elt
->next_same_value
= next
;
1507 next
->prev_same_value
= elt
;
1509 elt
->prev_same_value
= p
;
1510 p
->next_same_value
= elt
;
1511 elt
->first_same_value
= classp
;
1515 elt
->first_same_value
= elt
;
1517 /* If this is a constant being set equivalent to a register or a register
1518 being set equivalent to a constant, note the constant equivalence.
1520 If this is a constant, it cannot be equivalent to a different constant,
1521 and a constant is the only thing that can be cheaper than a register. So
1522 we know the register is the head of the class (before the constant was
1525 If this is a register that is not already known equivalent to a
1526 constant, we must check the entire class.
1528 If this is a register that is already known equivalent to an insn,
1529 update the qtys `const_insn' to show that `this_insn' is the latest
1530 insn making that quantity equivalent to the constant. */
1532 if (elt
->is_const
&& classp
&& REG_P (classp
->exp
)
1535 int exp_q
= REG_QTY (REGNO (classp
->exp
));
1536 struct qty_table_elem
*exp_ent
= &qty_table
[exp_q
];
1538 exp_ent
->const_rtx
= gen_lowpart (exp_ent
->mode
, x
);
1539 exp_ent
->const_insn
= this_insn
;
1544 && ! qty_table
[REG_QTY (REGNO (x
))].const_rtx
1547 struct table_elt
*p
;
1549 for (p
= classp
; p
!= 0; p
= p
->next_same_value
)
1551 if (p
->is_const
&& !REG_P (p
->exp
))
1553 int x_q
= REG_QTY (REGNO (x
));
1554 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
1557 = gen_lowpart (GET_MODE (x
), p
->exp
);
1558 x_ent
->const_insn
= this_insn
;
1565 && qty_table
[REG_QTY (REGNO (x
))].const_rtx
1566 && GET_MODE (x
) == qty_table
[REG_QTY (REGNO (x
))].mode
)
1567 qty_table
[REG_QTY (REGNO (x
))].const_insn
= this_insn
;
1569 /* If this is a constant with symbolic value,
1570 and it has a term with an explicit integer value,
1571 link it up with related expressions. */
1572 if (GET_CODE (x
) == CONST
)
1574 rtx subexp
= get_related_value (x
);
1576 struct table_elt
*subelt
, *subelt_prev
;
1580 /* Get the integer-free subexpression in the hash table. */
1581 subhash
= SAFE_HASH (subexp
, mode
);
1582 subelt
= lookup (subexp
, subhash
, mode
);
1584 subelt
= insert (subexp
, NULL
, subhash
, mode
);
1585 /* Initialize SUBELT's circular chain if it has none. */
1586 if (subelt
->related_value
== 0)
1587 subelt
->related_value
= subelt
;
1588 /* Find the element in the circular chain that precedes SUBELT. */
1589 subelt_prev
= subelt
;
1590 while (subelt_prev
->related_value
!= subelt
)
1591 subelt_prev
= subelt_prev
->related_value
;
1592 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1593 This way the element that follows SUBELT is the oldest one. */
1594 elt
->related_value
= subelt_prev
->related_value
;
1595 subelt_prev
->related_value
= elt
;
1602 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1603 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1604 the two classes equivalent.
1606 CLASS1 will be the surviving class; CLASS2 should not be used after this
1609 Any invalid entries in CLASS2 will not be copied. */
1612 merge_equiv_classes (struct table_elt
*class1
, struct table_elt
*class2
)
1614 struct table_elt
*elt
, *next
, *new;
1616 /* Ensure we start with the head of the classes. */
1617 class1
= class1
->first_same_value
;
1618 class2
= class2
->first_same_value
;
1620 /* If they were already equal, forget it. */
1621 if (class1
== class2
)
1624 for (elt
= class2
; elt
; elt
= next
)
1628 enum machine_mode mode
= elt
->mode
;
1630 next
= elt
->next_same_value
;
1632 /* Remove old entry, make a new one in CLASS1's class.
1633 Don't do this for invalid entries as we cannot find their
1634 hash code (it also isn't necessary). */
1635 if (REG_P (exp
) || exp_equiv_p (exp
, exp
, 1, false))
1637 bool need_rehash
= false;
1639 hash_arg_in_memory
= 0;
1640 hash
= HASH (exp
, mode
);
1644 need_rehash
= REGNO_QTY_VALID_P (REGNO (exp
));
1645 delete_reg_equiv (REGNO (exp
));
1648 remove_from_table (elt
, hash
);
1650 if (insert_regs (exp
, class1
, 0) || need_rehash
)
1652 rehash_using_reg (exp
);
1653 hash
= HASH (exp
, mode
);
1655 new = insert (exp
, class1
, hash
, mode
);
1656 new->in_memory
= hash_arg_in_memory
;
1661 /* Flush the entire hash table. */
1664 flush_hash_table (void)
1667 struct table_elt
*p
;
1669 for (i
= 0; i
< HASH_SIZE
; i
++)
1670 for (p
= table
[i
]; p
; p
= table
[i
])
1672 /* Note that invalidate can remove elements
1673 after P in the current hash chain. */
1675 invalidate (p
->exp
, VOIDmode
);
1677 remove_from_table (p
, i
);
1681 /* Function called for each rtx to check whether true dependence exist. */
1682 struct check_dependence_data
1684 enum machine_mode mode
;
1690 check_dependence (rtx
*x
, void *data
)
1692 struct check_dependence_data
*d
= (struct check_dependence_data
*) data
;
1693 if (*x
&& MEM_P (*x
))
1694 return canon_true_dependence (d
->exp
, d
->mode
, d
->addr
, *x
,
1700 /* Remove from the hash table, or mark as invalid, all expressions whose
1701 values could be altered by storing in X. X is a register, a subreg, or
1702 a memory reference with nonvarying address (because, when a memory
1703 reference with a varying address is stored in, all memory references are
1704 removed by invalidate_memory so specific invalidation is superfluous).
1705 FULL_MODE, if not VOIDmode, indicates that this much should be
1706 invalidated instead of just the amount indicated by the mode of X. This
1707 is only used for bitfield stores into memory.
1709 A nonvarying address may be just a register or just a symbol reference,
1710 or it may be either of those plus a numeric offset. */
1713 invalidate (rtx x
, enum machine_mode full_mode
)
1716 struct table_elt
*p
;
1719 switch (GET_CODE (x
))
1723 /* If X is a register, dependencies on its contents are recorded
1724 through the qty number mechanism. Just change the qty number of
1725 the register, mark it as invalid for expressions that refer to it,
1726 and remove it itself. */
1727 unsigned int regno
= REGNO (x
);
1728 unsigned int hash
= HASH (x
, GET_MODE (x
));
1730 /* Remove REGNO from any quantity list it might be on and indicate
1731 that its value might have changed. If it is a pseudo, remove its
1732 entry from the hash table.
1734 For a hard register, we do the first two actions above for any
1735 additional hard registers corresponding to X. Then, if any of these
1736 registers are in the table, we must remove any REG entries that
1737 overlap these registers. */
1739 delete_reg_equiv (regno
);
1741 SUBREG_TICKED (regno
) = -1;
1743 if (regno
>= FIRST_PSEUDO_REGISTER
)
1745 /* Because a register can be referenced in more than one mode,
1746 we might have to remove more than one table entry. */
1747 struct table_elt
*elt
;
1749 while ((elt
= lookup_for_remove (x
, hash
, GET_MODE (x
))))
1750 remove_from_table (elt
, hash
);
1754 HOST_WIDE_INT in_table
1755 = TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1756 unsigned int endregno
1757 = regno
+ hard_regno_nregs
[regno
][GET_MODE (x
)];
1758 unsigned int tregno
, tendregno
, rn
;
1759 struct table_elt
*p
, *next
;
1761 CLEAR_HARD_REG_BIT (hard_regs_in_table
, regno
);
1763 for (rn
= regno
+ 1; rn
< endregno
; rn
++)
1765 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, rn
);
1766 CLEAR_HARD_REG_BIT (hard_regs_in_table
, rn
);
1767 delete_reg_equiv (rn
);
1769 SUBREG_TICKED (rn
) = -1;
1773 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
1774 for (p
= table
[hash
]; p
; p
= next
)
1776 next
= p
->next_same_hash
;
1779 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1782 tregno
= REGNO (p
->exp
);
1784 = tregno
+ hard_regno_nregs
[tregno
][GET_MODE (p
->exp
)];
1785 if (tendregno
> regno
&& tregno
< endregno
)
1786 remove_from_table (p
, hash
);
1793 invalidate (SUBREG_REG (x
), VOIDmode
);
1797 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; --i
)
1798 invalidate (XVECEXP (x
, 0, i
), VOIDmode
);
1802 /* This is part of a disjoint return value; extract the location in
1803 question ignoring the offset. */
1804 invalidate (XEXP (x
, 0), VOIDmode
);
1808 addr
= canon_rtx (get_addr (XEXP (x
, 0)));
1809 /* Calculate the canonical version of X here so that
1810 true_dependence doesn't generate new RTL for X on each call. */
1813 /* Remove all hash table elements that refer to overlapping pieces of
1815 if (full_mode
== VOIDmode
)
1816 full_mode
= GET_MODE (x
);
1818 for (i
= 0; i
< HASH_SIZE
; i
++)
1820 struct table_elt
*next
;
1822 for (p
= table
[i
]; p
; p
= next
)
1824 next
= p
->next_same_hash
;
1827 struct check_dependence_data d
;
1829 /* Just canonicalize the expression once;
1830 otherwise each time we call invalidate
1831 true_dependence will canonicalize the
1832 expression again. */
1834 p
->canon_exp
= canon_rtx (p
->exp
);
1838 if (for_each_rtx (&p
->canon_exp
, check_dependence
, &d
))
1839 remove_from_table (p
, i
);
1850 /* Remove all expressions that refer to register REGNO,
1851 since they are already invalid, and we are about to
1852 mark that register valid again and don't want the old
1853 expressions to reappear as valid. */
1856 remove_invalid_refs (unsigned int regno
)
1859 struct table_elt
*p
, *next
;
1861 for (i
= 0; i
< HASH_SIZE
; i
++)
1862 for (p
= table
[i
]; p
; p
= next
)
1864 next
= p
->next_same_hash
;
1866 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, (rtx
*) 0))
1867 remove_from_table (p
, i
);
1871 /* Likewise for a subreg with subreg_reg REGNO, subreg_byte OFFSET,
1874 remove_invalid_subreg_refs (unsigned int regno
, unsigned int offset
,
1875 enum machine_mode mode
)
1878 struct table_elt
*p
, *next
;
1879 unsigned int end
= offset
+ (GET_MODE_SIZE (mode
) - 1);
1881 for (i
= 0; i
< HASH_SIZE
; i
++)
1882 for (p
= table
[i
]; p
; p
= next
)
1885 next
= p
->next_same_hash
;
1888 && (GET_CODE (exp
) != SUBREG
1889 || !REG_P (SUBREG_REG (exp
))
1890 || REGNO (SUBREG_REG (exp
)) != regno
1891 || (((SUBREG_BYTE (exp
)
1892 + (GET_MODE_SIZE (GET_MODE (exp
)) - 1)) >= offset
)
1893 && SUBREG_BYTE (exp
) <= end
))
1894 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, (rtx
*) 0))
1895 remove_from_table (p
, i
);
1899 /* Recompute the hash codes of any valid entries in the hash table that
1900 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1902 This is called when we make a jump equivalence. */
1905 rehash_using_reg (rtx x
)
1908 struct table_elt
*p
, *next
;
1911 if (GET_CODE (x
) == SUBREG
)
1914 /* If X is not a register or if the register is known not to be in any
1915 valid entries in the table, we have no work to do. */
1918 || REG_IN_TABLE (REGNO (x
)) < 0
1919 || REG_IN_TABLE (REGNO (x
)) != REG_TICK (REGNO (x
)))
1922 /* Scan all hash chains looking for valid entries that mention X.
1923 If we find one and it is in the wrong hash chain, move it. */
1925 for (i
= 0; i
< HASH_SIZE
; i
++)
1926 for (p
= table
[i
]; p
; p
= next
)
1928 next
= p
->next_same_hash
;
1929 if (reg_mentioned_p (x
, p
->exp
)
1930 && exp_equiv_p (p
->exp
, p
->exp
, 1, false)
1931 && i
!= (hash
= SAFE_HASH (p
->exp
, p
->mode
)))
1933 if (p
->next_same_hash
)
1934 p
->next_same_hash
->prev_same_hash
= p
->prev_same_hash
;
1936 if (p
->prev_same_hash
)
1937 p
->prev_same_hash
->next_same_hash
= p
->next_same_hash
;
1939 table
[i
] = p
->next_same_hash
;
1941 p
->next_same_hash
= table
[hash
];
1942 p
->prev_same_hash
= 0;
1944 table
[hash
]->prev_same_hash
= p
;
1950 /* Remove from the hash table any expression that is a call-clobbered
1951 register. Also update their TICK values. */
1954 invalidate_for_call (void)
1956 unsigned int regno
, endregno
;
1959 struct table_elt
*p
, *next
;
1962 /* Go through all the hard registers. For each that is clobbered in
1963 a CALL_INSN, remove the register from quantity chains and update
1964 reg_tick if defined. Also see if any of these registers is currently
1967 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1968 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
1970 delete_reg_equiv (regno
);
1971 if (REG_TICK (regno
) >= 0)
1974 SUBREG_TICKED (regno
) = -1;
1977 in_table
|= (TEST_HARD_REG_BIT (hard_regs_in_table
, regno
) != 0);
1980 /* In the case where we have no call-clobbered hard registers in the
1981 table, we are done. Otherwise, scan the table and remove any
1982 entry that overlaps a call-clobbered register. */
1985 for (hash
= 0; hash
< HASH_SIZE
; hash
++)
1986 for (p
= table
[hash
]; p
; p
= next
)
1988 next
= p
->next_same_hash
;
1991 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1994 regno
= REGNO (p
->exp
);
1995 endregno
= regno
+ hard_regno_nregs
[regno
][GET_MODE (p
->exp
)];
1997 for (i
= regno
; i
< endregno
; i
++)
1998 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
2000 remove_from_table (p
, hash
);
2006 /* Given an expression X of type CONST,
2007 and ELT which is its table entry (or 0 if it
2008 is not in the hash table),
2009 return an alternate expression for X as a register plus integer.
2010 If none can be found, return 0. */
2013 use_related_value (rtx x
, struct table_elt
*elt
)
2015 struct table_elt
*relt
= 0;
2016 struct table_elt
*p
, *q
;
2017 HOST_WIDE_INT offset
;
2019 /* First, is there anything related known?
2020 If we have a table element, we can tell from that.
2021 Otherwise, must look it up. */
2023 if (elt
!= 0 && elt
->related_value
!= 0)
2025 else if (elt
== 0 && GET_CODE (x
) == CONST
)
2027 rtx subexp
= get_related_value (x
);
2029 relt
= lookup (subexp
,
2030 SAFE_HASH (subexp
, GET_MODE (subexp
)),
2037 /* Search all related table entries for one that has an
2038 equivalent register. */
2043 /* This loop is strange in that it is executed in two different cases.
2044 The first is when X is already in the table. Then it is searching
2045 the RELATED_VALUE list of X's class (RELT). The second case is when
2046 X is not in the table. Then RELT points to a class for the related
2049 Ensure that, whatever case we are in, that we ignore classes that have
2050 the same value as X. */
2052 if (rtx_equal_p (x
, p
->exp
))
2055 for (q
= p
->first_same_value
; q
; q
= q
->next_same_value
)
2062 p
= p
->related_value
;
2064 /* We went all the way around, so there is nothing to be found.
2065 Alternatively, perhaps RELT was in the table for some other reason
2066 and it has no related values recorded. */
2067 if (p
== relt
|| p
== 0)
2074 offset
= (get_integer_term (x
) - get_integer_term (p
->exp
));
2075 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
2076 return plus_constant (q
->exp
, offset
);
2079 /* Hash a string. Just add its bytes up. */
2080 static inline unsigned
2081 hash_rtx_string (const char *ps
)
2084 const unsigned char *p
= (const unsigned char *) ps
;
2093 /* Hash an rtx. We are careful to make sure the value is never negative.
2094 Equivalent registers hash identically.
2095 MODE is used in hashing for CONST_INTs only;
2096 otherwise the mode of X is used.
2098 Store 1 in DO_NOT_RECORD_P if any subexpression is volatile.
2100 If HASH_ARG_IN_MEMORY_P is not NULL, store 1 in it if X contains
2101 a MEM rtx which does not have the RTX_UNCHANGING_P bit set.
2103 Note that cse_insn knows that the hash code of a MEM expression
2104 is just (int) MEM plus the hash code of the address. */
2107 hash_rtx (rtx x
, enum machine_mode mode
, int *do_not_record_p
,
2108 int *hash_arg_in_memory_p
, bool have_reg_qty
)
2115 /* Used to turn recursion into iteration. We can't rely on GCC's
2116 tail-recursion elimination since we need to keep accumulating values
2122 code
= GET_CODE (x
);
2127 unsigned int regno
= REGNO (x
);
2129 if (!reload_completed
)
2131 /* On some machines, we can't record any non-fixed hard register,
2132 because extending its life will cause reload problems. We
2133 consider ap, fp, sp, gp to be fixed for this purpose.
2135 We also consider CCmode registers to be fixed for this purpose;
2136 failure to do so leads to failure to simplify 0<100 type of
2139 On all machines, we can't record any global registers.
2140 Nor should we record any register that is in a small
2141 class, as defined by CLASS_LIKELY_SPILLED_P. */
2144 if (regno
>= FIRST_PSEUDO_REGISTER
)
2146 else if (x
== frame_pointer_rtx
2147 || x
== hard_frame_pointer_rtx
2148 || x
== arg_pointer_rtx
2149 || x
== stack_pointer_rtx
2150 || x
== pic_offset_table_rtx
)
2152 else if (global_regs
[regno
])
2154 else if (fixed_regs
[regno
])
2156 else if (GET_MODE_CLASS (GET_MODE (x
)) == MODE_CC
)
2158 else if (SMALL_REGISTER_CLASSES
)
2160 else if (CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (regno
)))
2167 *do_not_record_p
= 1;
2172 hash
+= ((unsigned int) REG
<< 7);
2173 hash
+= (have_reg_qty
? (unsigned) REG_QTY (regno
) : regno
);
2177 /* We handle SUBREG of a REG specially because the underlying
2178 reg changes its hash value with every value change; we don't
2179 want to have to forget unrelated subregs when one subreg changes. */
2182 if (REG_P (SUBREG_REG (x
)))
2184 hash
+= (((unsigned int) SUBREG
<< 7)
2185 + REGNO (SUBREG_REG (x
))
2186 + (SUBREG_BYTE (x
) / UNITS_PER_WORD
));
2193 hash
+= (((unsigned int) CONST_INT
<< 7) + (unsigned int) mode
2194 + (unsigned int) INTVAL (x
));
2198 /* This is like the general case, except that it only counts
2199 the integers representing the constant. */
2200 hash
+= (unsigned int) code
+ (unsigned int) GET_MODE (x
);
2201 if (GET_MODE (x
) != VOIDmode
)
2202 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
2204 hash
+= ((unsigned int) CONST_DOUBLE_LOW (x
)
2205 + (unsigned int) CONST_DOUBLE_HIGH (x
));
2213 units
= CONST_VECTOR_NUNITS (x
);
2215 for (i
= 0; i
< units
; ++i
)
2217 elt
= CONST_VECTOR_ELT (x
, i
);
2218 hash
+= hash_rtx (elt
, GET_MODE (elt
), do_not_record_p
,
2219 hash_arg_in_memory_p
, have_reg_qty
);
2225 /* Assume there is only one rtx object for any given label. */
2227 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
2228 differences and differences between each stage's debugging dumps. */
2229 hash
+= (((unsigned int) LABEL_REF
<< 7)
2230 + CODE_LABEL_NUMBER (XEXP (x
, 0)));
2235 /* Don't hash on the symbol's address to avoid bootstrap differences.
2236 Different hash values may cause expressions to be recorded in
2237 different orders and thus different registers to be used in the
2238 final assembler. This also avoids differences in the dump files
2239 between various stages. */
2241 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
2244 h
+= (h
<< 7) + *p
++; /* ??? revisit */
2246 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
2251 /* We don't record if marked volatile or if BLKmode since we don't
2252 know the size of the move. */
2253 if (MEM_VOLATILE_P (x
) || GET_MODE (x
) == BLKmode
)
2255 *do_not_record_p
= 1;
2258 if (hash_arg_in_memory_p
&& !MEM_READONLY_P (x
))
2259 *hash_arg_in_memory_p
= 1;
2261 /* Now that we have already found this special case,
2262 might as well speed it up as much as possible. */
2263 hash
+= (unsigned) MEM
;
2268 /* A USE that mentions non-volatile memory needs special
2269 handling since the MEM may be BLKmode which normally
2270 prevents an entry from being made. Pure calls are
2271 marked by a USE which mentions BLKmode memory.
2272 See calls.c:emit_call_1. */
2273 if (MEM_P (XEXP (x
, 0))
2274 && ! MEM_VOLATILE_P (XEXP (x
, 0)))
2276 hash
+= (unsigned) USE
;
2279 if (hash_arg_in_memory_p
&& !MEM_READONLY_P (x
))
2280 *hash_arg_in_memory_p
= 1;
2282 /* Now that we have already found this special case,
2283 might as well speed it up as much as possible. */
2284 hash
+= (unsigned) MEM
;
2299 case UNSPEC_VOLATILE
:
2300 *do_not_record_p
= 1;
2304 if (MEM_VOLATILE_P (x
))
2306 *do_not_record_p
= 1;
2311 /* We don't want to take the filename and line into account. */
2312 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
)
2313 + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x
))
2314 + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x
))
2315 + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x
);
2317 if (ASM_OPERANDS_INPUT_LENGTH (x
))
2319 for (i
= 1; i
< ASM_OPERANDS_INPUT_LENGTH (x
); i
++)
2321 hash
+= (hash_rtx (ASM_OPERANDS_INPUT (x
, i
),
2322 GET_MODE (ASM_OPERANDS_INPUT (x
, i
)),
2323 do_not_record_p
, hash_arg_in_memory_p
,
2326 (ASM_OPERANDS_INPUT_CONSTRAINT (x
, i
)));
2329 hash
+= hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x
, 0));
2330 x
= ASM_OPERANDS_INPUT (x
, 0);
2331 mode
= GET_MODE (x
);
2343 i
= GET_RTX_LENGTH (code
) - 1;
2344 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
2345 fmt
= GET_RTX_FORMAT (code
);
2351 /* If we are about to do the last recursive call
2352 needed at this level, change it into iteration.
2353 This function is called enough to be worth it. */
2360 hash
+= hash_rtx (XEXP (x
, i
), 0, do_not_record_p
,
2361 hash_arg_in_memory_p
, have_reg_qty
);
2365 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2366 hash
+= hash_rtx (XVECEXP (x
, i
, j
), 0, do_not_record_p
,
2367 hash_arg_in_memory_p
, have_reg_qty
);
2371 hash
+= hash_rtx_string (XSTR (x
, i
));
2375 hash
+= (unsigned int) XINT (x
, i
);
2390 /* Hash an rtx X for cse via hash_rtx.
2391 Stores 1 in do_not_record if any subexpression is volatile.
2392 Stores 1 in hash_arg_in_memory if X contains a mem rtx which
2393 does not have the RTX_UNCHANGING_P bit set. */
2395 static inline unsigned
2396 canon_hash (rtx x
, enum machine_mode mode
)
2398 return hash_rtx (x
, mode
, &do_not_record
, &hash_arg_in_memory
, true);
2401 /* Like canon_hash but with no side effects, i.e. do_not_record
2402 and hash_arg_in_memory are not changed. */
2404 static inline unsigned
2405 safe_hash (rtx x
, enum machine_mode mode
)
2407 int dummy_do_not_record
;
2408 return hash_rtx (x
, mode
, &dummy_do_not_record
, NULL
, true);
2411 /* Return 1 iff X and Y would canonicalize into the same thing,
2412 without actually constructing the canonicalization of either one.
2413 If VALIDATE is nonzero,
2414 we assume X is an expression being processed from the rtl
2415 and Y was found in the hash table. We check register refs
2416 in Y for being marked as valid.
2418 If FOR_GCSE is true, we compare X and Y for equivalence for GCSE. */
2421 exp_equiv_p (rtx x
, rtx y
, int validate
, bool for_gcse
)
2427 /* Note: it is incorrect to assume an expression is equivalent to itself
2428 if VALIDATE is nonzero. */
2429 if (x
== y
&& !validate
)
2432 if (x
== 0 || y
== 0)
2435 code
= GET_CODE (x
);
2436 if (code
!= GET_CODE (y
))
2439 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
2440 if (GET_MODE (x
) != GET_MODE (y
))
2452 return XEXP (x
, 0) == XEXP (y
, 0);
2455 return XSTR (x
, 0) == XSTR (y
, 0);
2459 return REGNO (x
) == REGNO (y
);
2462 unsigned int regno
= REGNO (y
);
2464 unsigned int endregno
2465 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
2466 : hard_regno_nregs
[regno
][GET_MODE (y
)]);
2468 /* If the quantities are not the same, the expressions are not
2469 equivalent. If there are and we are not to validate, they
2470 are equivalent. Otherwise, ensure all regs are up-to-date. */
2472 if (REG_QTY (REGNO (x
)) != REG_QTY (regno
))
2478 for (i
= regno
; i
< endregno
; i
++)
2479 if (REG_IN_TABLE (i
) != REG_TICK (i
))
2488 /* A volatile mem should not be considered equivalent to any
2490 if (MEM_VOLATILE_P (x
) || MEM_VOLATILE_P (y
))
2493 /* Can't merge two expressions in different alias sets, since we
2494 can decide that the expression is transparent in a block when
2495 it isn't, due to it being set with the different alias set.
2497 Also, can't merge two expressions with different MEM_ATTRS.
2498 They could e.g. be two different entities allocated into the
2499 same space on the stack (see e.g. PR25130). In that case, the
2500 MEM addresses can be the same, even though the two MEMs are
2501 absolutely not equivalent.
2503 But because really all MEM attributes should be the same for
2504 equivalent MEMs, we just use the invariant that MEMs that have
2505 the same attributes share the same mem_attrs data structure. */
2506 if (MEM_ATTRS (x
) != MEM_ATTRS (y
))
2511 /* For commutative operations, check both orders. */
2519 return ((exp_equiv_p (XEXP (x
, 0), XEXP (y
, 0),
2521 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 1),
2522 validate
, for_gcse
))
2523 || (exp_equiv_p (XEXP (x
, 0), XEXP (y
, 1),
2525 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 0),
2526 validate
, for_gcse
)));
2529 /* We don't use the generic code below because we want to
2530 disregard filename and line numbers. */
2532 /* A volatile asm isn't equivalent to any other. */
2533 if (MEM_VOLATILE_P (x
) || MEM_VOLATILE_P (y
))
2536 if (GET_MODE (x
) != GET_MODE (y
)
2537 || strcmp (ASM_OPERANDS_TEMPLATE (x
), ASM_OPERANDS_TEMPLATE (y
))
2538 || strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x
),
2539 ASM_OPERANDS_OUTPUT_CONSTRAINT (y
))
2540 || ASM_OPERANDS_OUTPUT_IDX (x
) != ASM_OPERANDS_OUTPUT_IDX (y
)
2541 || ASM_OPERANDS_INPUT_LENGTH (x
) != ASM_OPERANDS_INPUT_LENGTH (y
))
2544 if (ASM_OPERANDS_INPUT_LENGTH (x
))
2546 for (i
= ASM_OPERANDS_INPUT_LENGTH (x
) - 1; i
>= 0; i
--)
2547 if (! exp_equiv_p (ASM_OPERANDS_INPUT (x
, i
),
2548 ASM_OPERANDS_INPUT (y
, i
),
2550 || strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x
, i
),
2551 ASM_OPERANDS_INPUT_CONSTRAINT (y
, i
)))
2561 /* Compare the elements. If any pair of corresponding elements
2562 fail to match, return 0 for the whole thing. */
2564 fmt
= GET_RTX_FORMAT (code
);
2565 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2570 if (! exp_equiv_p (XEXP (x
, i
), XEXP (y
, i
),
2571 validate
, for_gcse
))
2576 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
2578 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2579 if (! exp_equiv_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
),
2580 validate
, for_gcse
))
2585 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
2590 if (XINT (x
, i
) != XINT (y
, i
))
2595 if (XWINT (x
, i
) != XWINT (y
, i
))
2611 /* Return 1 if X has a value that can vary even between two
2612 executions of the program. 0 means X can be compared reliably
2613 against certain constants or near-constants. */
2616 cse_rtx_varies_p (rtx x
, int from_alias
)
2618 /* We need not check for X and the equivalence class being of the same
2619 mode because if X is equivalent to a constant in some mode, it
2620 doesn't vary in any mode. */
2623 && REGNO_QTY_VALID_P (REGNO (x
)))
2625 int x_q
= REG_QTY (REGNO (x
));
2626 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
2628 if (GET_MODE (x
) == x_ent
->mode
2629 && x_ent
->const_rtx
!= NULL_RTX
)
2633 if (GET_CODE (x
) == PLUS
2634 && GET_CODE (XEXP (x
, 1)) == CONST_INT
2635 && REG_P (XEXP (x
, 0))
2636 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0))))
2638 int x0_q
= REG_QTY (REGNO (XEXP (x
, 0)));
2639 struct qty_table_elem
*x0_ent
= &qty_table
[x0_q
];
2641 if ((GET_MODE (XEXP (x
, 0)) == x0_ent
->mode
)
2642 && x0_ent
->const_rtx
!= NULL_RTX
)
2646 /* This can happen as the result of virtual register instantiation, if
2647 the initial constant is too large to be a valid address. This gives
2648 us a three instruction sequence, load large offset into a register,
2649 load fp minus a constant into a register, then a MEM which is the
2650 sum of the two `constant' registers. */
2651 if (GET_CODE (x
) == PLUS
2652 && REG_P (XEXP (x
, 0))
2653 && REG_P (XEXP (x
, 1))
2654 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0)))
2655 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 1))))
2657 int x0_q
= REG_QTY (REGNO (XEXP (x
, 0)));
2658 int x1_q
= REG_QTY (REGNO (XEXP (x
, 1)));
2659 struct qty_table_elem
*x0_ent
= &qty_table
[x0_q
];
2660 struct qty_table_elem
*x1_ent
= &qty_table
[x1_q
];
2662 if ((GET_MODE (XEXP (x
, 0)) == x0_ent
->mode
)
2663 && x0_ent
->const_rtx
!= NULL_RTX
2664 && (GET_MODE (XEXP (x
, 1)) == x1_ent
->mode
)
2665 && x1_ent
->const_rtx
!= NULL_RTX
)
2669 return rtx_varies_p (x
, from_alias
);
2672 /* Subroutine of canon_reg. Pass *XLOC through canon_reg, and validate
2673 the result if necessary. INSN is as for canon_reg. */
2676 validate_canon_reg (rtx
*xloc
, rtx insn
)
2678 rtx
new = canon_reg (*xloc
, insn
);
2680 /* If replacing pseudo with hard reg or vice versa, ensure the
2681 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2682 if (insn
!= 0 && new != 0)
2683 validate_change (insn
, xloc
, new, 1);
2688 /* Canonicalize an expression:
2689 replace each register reference inside it
2690 with the "oldest" equivalent register.
2692 If INSN is nonzero validate_change is used to ensure that INSN remains valid
2693 after we make our substitution. The calls are made with IN_GROUP nonzero
2694 so apply_change_group must be called upon the outermost return from this
2695 function (unless INSN is zero). The result of apply_change_group can
2696 generally be discarded since the changes we are making are optional. */
2699 canon_reg (rtx x
, rtx insn
)
2708 code
= GET_CODE (x
);
2727 struct qty_table_elem
*ent
;
2729 /* Never replace a hard reg, because hard regs can appear
2730 in more than one machine mode, and we must preserve the mode
2731 of each occurrence. Also, some hard regs appear in
2732 MEMs that are shared and mustn't be altered. Don't try to
2733 replace any reg that maps to a reg of class NO_REGS. */
2734 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
2735 || ! REGNO_QTY_VALID_P (REGNO (x
)))
2738 q
= REG_QTY (REGNO (x
));
2739 ent
= &qty_table
[q
];
2740 first
= ent
->first_reg
;
2741 return (first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
2742 : REGNO_REG_CLASS (first
) == NO_REGS
? x
2743 : gen_rtx_REG (ent
->mode
, first
));
2750 fmt
= GET_RTX_FORMAT (code
);
2751 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2756 validate_canon_reg (&XEXP (x
, i
), insn
);
2757 else if (fmt
[i
] == 'E')
2758 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2759 validate_canon_reg (&XVECEXP (x
, i
, j
), insn
);
2765 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2766 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2767 what values are being compared.
2769 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2770 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2771 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2772 compared to produce cc0.
2774 The return value is the comparison operator and is either the code of
2775 A or the code corresponding to the inverse of the comparison. */
2777 static enum rtx_code
2778 find_comparison_args (enum rtx_code code
, rtx
*parg1
, rtx
*parg2
,
2779 enum machine_mode
*pmode1
, enum machine_mode
*pmode2
)
2783 arg1
= *parg1
, arg2
= *parg2
;
2785 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2787 while (arg2
== CONST0_RTX (GET_MODE (arg1
)))
2789 /* Set nonzero when we find something of interest. */
2791 int reverse_code
= 0;
2792 struct table_elt
*p
= 0;
2794 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2795 On machines with CC0, this is the only case that can occur, since
2796 fold_rtx will return the COMPARE or item being compared with zero
2799 if (GET_CODE (arg1
) == COMPARE
&& arg2
== const0_rtx
)
2802 /* If ARG1 is a comparison operator and CODE is testing for
2803 STORE_FLAG_VALUE, get the inner arguments. */
2805 else if (COMPARISON_P (arg1
))
2807 #ifdef FLOAT_STORE_FLAG_VALUE
2808 REAL_VALUE_TYPE fsfv
;
2812 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
2813 && code
== LT
&& STORE_FLAG_VALUE
== -1)
2814 #ifdef FLOAT_STORE_FLAG_VALUE
2815 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1
))
2816 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
2817 REAL_VALUE_NEGATIVE (fsfv
)))
2822 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
2823 && code
== GE
&& STORE_FLAG_VALUE
== -1)
2824 #ifdef FLOAT_STORE_FLAG_VALUE
2825 || (SCALAR_FLOAT_MODE_P (GET_MODE (arg1
))
2826 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
2827 REAL_VALUE_NEGATIVE (fsfv
)))
2830 x
= arg1
, reverse_code
= 1;
2833 /* ??? We could also check for
2835 (ne (and (eq (...) (const_int 1))) (const_int 0))
2837 and related forms, but let's wait until we see them occurring. */
2840 /* Look up ARG1 in the hash table and see if it has an equivalence
2841 that lets us see what is being compared. */
2842 p
= lookup (arg1
, SAFE_HASH (arg1
, GET_MODE (arg1
)), GET_MODE (arg1
));
2845 p
= p
->first_same_value
;
2847 /* If what we compare is already known to be constant, that is as
2849 We need to break the loop in this case, because otherwise we
2850 can have an infinite loop when looking at a reg that is known
2851 to be a constant which is the same as a comparison of a reg
2852 against zero which appears later in the insn stream, which in
2853 turn is constant and the same as the comparison of the first reg
2859 for (; p
; p
= p
->next_same_value
)
2861 enum machine_mode inner_mode
= GET_MODE (p
->exp
);
2862 #ifdef FLOAT_STORE_FLAG_VALUE
2863 REAL_VALUE_TYPE fsfv
;
2866 /* If the entry isn't valid, skip it. */
2867 if (! exp_equiv_p (p
->exp
, p
->exp
, 1, false))
2870 if (GET_CODE (p
->exp
) == COMPARE
2871 /* Another possibility is that this machine has a compare insn
2872 that includes the comparison code. In that case, ARG1 would
2873 be equivalent to a comparison operation that would set ARG1 to
2874 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2875 ORIG_CODE is the actual comparison being done; if it is an EQ,
2876 we must reverse ORIG_CODE. On machine with a negative value
2877 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2880 && GET_MODE_CLASS (inner_mode
) == MODE_INT
2881 && (GET_MODE_BITSIZE (inner_mode
)
2882 <= HOST_BITS_PER_WIDE_INT
)
2883 && (STORE_FLAG_VALUE
2884 & ((HOST_WIDE_INT
) 1
2885 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
2886 #ifdef FLOAT_STORE_FLAG_VALUE
2888 && SCALAR_FLOAT_MODE_P (inner_mode
)
2889 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
2890 REAL_VALUE_NEGATIVE (fsfv
)))
2893 && COMPARISON_P (p
->exp
)))
2898 else if ((code
== EQ
2900 && GET_MODE_CLASS (inner_mode
) == MODE_INT
2901 && (GET_MODE_BITSIZE (inner_mode
)
2902 <= HOST_BITS_PER_WIDE_INT
)
2903 && (STORE_FLAG_VALUE
2904 & ((HOST_WIDE_INT
) 1
2905 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
2906 #ifdef FLOAT_STORE_FLAG_VALUE
2908 && SCALAR_FLOAT_MODE_P (inner_mode
)
2909 && (fsfv
= FLOAT_STORE_FLAG_VALUE (GET_MODE (arg1
)),
2910 REAL_VALUE_NEGATIVE (fsfv
)))
2913 && COMPARISON_P (p
->exp
))
2920 /* If this non-trapping address, e.g. fp + constant, the
2921 equivalent is a better operand since it may let us predict
2922 the value of the comparison. */
2923 else if (!rtx_addr_can_trap_p (p
->exp
))
2930 /* If we didn't find a useful equivalence for ARG1, we are done.
2931 Otherwise, set up for the next iteration. */
2935 /* If we need to reverse the comparison, make sure that that is
2936 possible -- we can't necessarily infer the value of GE from LT
2937 with floating-point operands. */
2940 enum rtx_code reversed
= reversed_comparison_code (x
, NULL_RTX
);
2941 if (reversed
== UNKNOWN
)
2946 else if (COMPARISON_P (x
))
2947 code
= GET_CODE (x
);
2948 arg1
= XEXP (x
, 0), arg2
= XEXP (x
, 1);
2951 /* Return our results. Return the modes from before fold_rtx
2952 because fold_rtx might produce const_int, and then it's too late. */
2953 *pmode1
= GET_MODE (arg1
), *pmode2
= GET_MODE (arg2
);
2954 *parg1
= fold_rtx (arg1
, 0), *parg2
= fold_rtx (arg2
, 0);
2959 /* If X is a nontrivial arithmetic operation on an argument for which
2960 a constant value can be determined, return the result of operating
2961 on that value, as a constant. Otherwise, return X, possibly with
2962 one or more operands changed to a forward-propagated constant.
2964 If X is a register whose contents are known, we do NOT return
2965 those contents here; equiv_constant is called to perform that task.
2966 For SUBREGs and MEMs, we do that both here and in equiv_constant.
2968 INSN is the insn that we may be modifying. If it is 0, make a copy
2969 of X before modifying it. */
2972 fold_rtx (rtx x
, rtx insn
)
2975 enum machine_mode mode
;
2981 /* Operands of X. */
2985 /* Constant equivalents of first three operands of X;
2986 0 when no such equivalent is known. */
2991 /* The mode of the first operand of X. We need this for sign and zero
2993 enum machine_mode mode_arg0
;
2998 /* Try to perform some initial simplifications on X. */
2999 code
= GET_CODE (x
);
3004 if ((new = equiv_constant (x
)) != NULL_RTX
)
3016 /* No use simplifying an EXPR_LIST
3017 since they are used only for lists of args
3018 in a function call's REG_EQUAL note. */
3024 return prev_insn_cc0
;
3030 for (i
= ASM_OPERANDS_INPUT_LENGTH (x
) - 1; i
>= 0; i
--)
3031 validate_change (insn
, &ASM_OPERANDS_INPUT (x
, i
),
3032 fold_rtx (ASM_OPERANDS_INPUT (x
, i
), insn
), 0);
3036 #ifdef NO_FUNCTION_CSE
3038 if (CONSTANT_P (XEXP (XEXP (x
, 0), 0)))
3043 /* Anything else goes through the loop below. */
3048 mode
= GET_MODE (x
);
3052 mode_arg0
= VOIDmode
;
3054 /* Try folding our operands.
3055 Then see which ones have constant values known. */
3057 fmt
= GET_RTX_FORMAT (code
);
3058 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3061 rtx folded_arg
= XEXP (x
, i
), const_arg
;
3062 enum machine_mode mode_arg
= GET_MODE (folded_arg
);
3064 if (CC0_P (folded_arg
))
3065 folded_arg
= prev_insn_cc0
, mode_arg
= prev_insn_cc0_mode
;
3067 const_arg
= equiv_constant (folded_arg
);
3069 /* For the first three operands, see if the operand
3070 is constant or equivalent to a constant. */
3074 folded_arg0
= folded_arg
;
3075 const_arg0
= const_arg
;
3076 mode_arg0
= mode_arg
;
3079 folded_arg1
= folded_arg
;
3080 const_arg1
= const_arg
;
3083 const_arg2
= const_arg
;
3087 /* Pick the least expensive of the argument and an equivalent constant
3090 && const_arg
!= folded_arg
3091 && COST_IN (const_arg
, code
) <= COST_IN (folded_arg
, code
)
3093 /* It's not safe to substitute the operand of a conversion
3094 operator with a constant, as the conversion's identity
3095 depends upon the mode of its operand. This optimization
3096 is handled by the call to simplify_unary_operation. */
3097 && (GET_RTX_CLASS (code
) != RTX_UNARY
3098 || GET_MODE (const_arg
) == mode_arg0
3099 || (code
!= ZERO_EXTEND
3100 && code
!= SIGN_EXTEND
3102 && code
!= FLOAT_TRUNCATE
3103 && code
!= FLOAT_EXTEND
3106 && code
!= UNSIGNED_FLOAT
3107 && code
!= UNSIGNED_FIX
)))
3108 folded_arg
= const_arg
;
3110 if (folded_arg
== XEXP (x
, i
))
3113 if (insn
== NULL_RTX
&& !changed
)
3116 validate_change (insn
, &XEXP (x
, i
), folded_arg
, 1);
3121 /* Canonicalize X if necessary, and keep const_argN and folded_argN
3122 consistent with the order in X. */
3123 if (canonicalize_change_group (insn
, x
))
3126 tem
= const_arg0
, const_arg0
= const_arg1
, const_arg1
= tem
;
3127 tem
= folded_arg0
, folded_arg0
= folded_arg1
, folded_arg1
= tem
;
3130 apply_change_group ();
3133 /* If X is an arithmetic operation, see if we can simplify it. */
3135 switch (GET_RTX_CLASS (code
))
3141 /* We can't simplify extension ops unless we know the
3143 if ((code
== ZERO_EXTEND
|| code
== SIGN_EXTEND
)
3144 && mode_arg0
== VOIDmode
)
3147 /* If we had a CONST, strip it off and put it back later if we
3149 if (const_arg0
!= 0 && GET_CODE (const_arg0
) == CONST
)
3150 is_const
= 1, const_arg0
= XEXP (const_arg0
, 0);
3152 new = simplify_unary_operation (code
, mode
,
3153 const_arg0
? const_arg0
: folded_arg0
,
3155 /* NEG of PLUS could be converted into MINUS, but that causes
3156 expressions of the form
3157 (CONST (MINUS (CONST_INT) (SYMBOL_REF)))
3158 which many ports mistakenly treat as LEGITIMATE_CONSTANT_P.
3159 FIXME: those ports should be fixed. */
3160 if (new != 0 && is_const
3161 && GET_CODE (new) == PLUS
3162 && (GET_CODE (XEXP (new, 0)) == SYMBOL_REF
3163 || GET_CODE (XEXP (new, 0)) == LABEL_REF
)
3164 && GET_CODE (XEXP (new, 1)) == CONST_INT
)
3165 new = gen_rtx_CONST (mode
, new);
3170 case RTX_COMM_COMPARE
:
3171 /* See what items are actually being compared and set FOLDED_ARG[01]
3172 to those values and CODE to the actual comparison code. If any are
3173 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
3174 do anything if both operands are already known to be constant. */
3176 /* ??? Vector mode comparisons are not supported yet. */
3177 if (VECTOR_MODE_P (mode
))
3180 if (const_arg0
== 0 || const_arg1
== 0)
3182 struct table_elt
*p0
, *p1
;
3183 rtx true_rtx
= const_true_rtx
, false_rtx
= const0_rtx
;
3184 enum machine_mode mode_arg1
;
3186 #ifdef FLOAT_STORE_FLAG_VALUE
3187 if (SCALAR_FLOAT_MODE_P (mode
))
3189 true_rtx
= (CONST_DOUBLE_FROM_REAL_VALUE
3190 (FLOAT_STORE_FLAG_VALUE (mode
), mode
));
3191 false_rtx
= CONST0_RTX (mode
);
3195 code
= find_comparison_args (code
, &folded_arg0
, &folded_arg1
,
3196 &mode_arg0
, &mode_arg1
);
3198 /* If the mode is VOIDmode or a MODE_CC mode, we don't know
3199 what kinds of things are being compared, so we can't do
3200 anything with this comparison. */
3202 if (mode_arg0
== VOIDmode
|| GET_MODE_CLASS (mode_arg0
) == MODE_CC
)
3205 const_arg0
= equiv_constant (folded_arg0
);
3206 const_arg1
= equiv_constant (folded_arg1
);
3208 /* If we do not now have two constants being compared, see
3209 if we can nevertheless deduce some things about the
3211 if (const_arg0
== 0 || const_arg1
== 0)
3213 if (const_arg1
!= NULL
)
3215 rtx cheapest_simplification
;
3218 struct table_elt
*p
;
3220 /* See if we can find an equivalent of folded_arg0
3221 that gets us a cheaper expression, possibly a
3222 constant through simplifications. */
3223 p
= lookup (folded_arg0
, SAFE_HASH (folded_arg0
, mode_arg0
),
3228 cheapest_simplification
= x
;
3229 cheapest_cost
= COST (x
);
3231 for (p
= p
->first_same_value
; p
!= NULL
; p
= p
->next_same_value
)
3235 /* If the entry isn't valid, skip it. */
3236 if (! exp_equiv_p (p
->exp
, p
->exp
, 1, false))
3239 /* Try to simplify using this equivalence. */
3241 = simplify_relational_operation (code
, mode
,
3246 if (simp_result
== NULL
)
3249 cost
= COST (simp_result
);
3250 if (cost
< cheapest_cost
)
3252 cheapest_cost
= cost
;
3253 cheapest_simplification
= simp_result
;
3257 /* If we have a cheaper expression now, use that
3258 and try folding it further, from the top. */
3259 if (cheapest_simplification
!= x
)
3260 return fold_rtx (cheapest_simplification
, insn
);
3264 /* Some addresses are known to be nonzero. We don't know
3265 their sign, but equality comparisons are known. */
3266 if (const_arg1
== const0_rtx
3267 && nonzero_address_p (folded_arg0
))
3271 else if (code
== NE
)
3275 /* See if the two operands are the same. */
3277 if (folded_arg0
== folded_arg1
3278 || (REG_P (folded_arg0
)
3279 && REG_P (folded_arg1
)
3280 && (REG_QTY (REGNO (folded_arg0
))
3281 == REG_QTY (REGNO (folded_arg1
))))
3282 || ((p0
= lookup (folded_arg0
,
3283 SAFE_HASH (folded_arg0
, mode_arg0
),
3285 && (p1
= lookup (folded_arg1
,
3286 SAFE_HASH (folded_arg1
, mode_arg0
),
3288 && p0
->first_same_value
== p1
->first_same_value
))
3290 /* Sadly two equal NaNs are not equivalent. */
3291 if (!HONOR_NANS (mode_arg0
))
3292 return ((code
== EQ
|| code
== LE
|| code
== GE
3293 || code
== LEU
|| code
== GEU
|| code
== UNEQ
3294 || code
== UNLE
|| code
== UNGE
3296 ? true_rtx
: false_rtx
);
3297 /* Take care for the FP compares we can resolve. */
3298 if (code
== UNEQ
|| code
== UNLE
|| code
== UNGE
)
3300 if (code
== LTGT
|| code
== LT
|| code
== GT
)
3304 /* If FOLDED_ARG0 is a register, see if the comparison we are
3305 doing now is either the same as we did before or the reverse
3306 (we only check the reverse if not floating-point). */
3307 else if (REG_P (folded_arg0
))
3309 int qty
= REG_QTY (REGNO (folded_arg0
));
3311 if (REGNO_QTY_VALID_P (REGNO (folded_arg0
)))
3313 struct qty_table_elem
*ent
= &qty_table
[qty
];
3315 if ((comparison_dominates_p (ent
->comparison_code
, code
)
3316 || (! FLOAT_MODE_P (mode_arg0
)
3317 && comparison_dominates_p (ent
->comparison_code
,
3318 reverse_condition (code
))))
3319 && (rtx_equal_p (ent
->comparison_const
, folded_arg1
)
3321 && rtx_equal_p (ent
->comparison_const
,
3323 || (REG_P (folded_arg1
)
3324 && (REG_QTY (REGNO (folded_arg1
)) == ent
->comparison_qty
))))
3325 return (comparison_dominates_p (ent
->comparison_code
, code
)
3326 ? true_rtx
: false_rtx
);
3332 /* If we are comparing against zero, see if the first operand is
3333 equivalent to an IOR with a constant. If so, we may be able to
3334 determine the result of this comparison. */
3336 if (const_arg1
== const0_rtx
)
3338 rtx y
= lookup_as_function (folded_arg0
, IOR
);
3342 && (inner_const
= equiv_constant (XEXP (y
, 1))) != 0
3343 && GET_CODE (inner_const
) == CONST_INT
3344 && INTVAL (inner_const
) != 0)
3346 int sign_bitnum
= GET_MODE_BITSIZE (mode_arg0
) - 1;
3347 int has_sign
= (HOST_BITS_PER_WIDE_INT
>= sign_bitnum
3348 && (INTVAL (inner_const
)
3349 & ((HOST_WIDE_INT
) 1 << sign_bitnum
)));
3350 rtx true_rtx
= const_true_rtx
, false_rtx
= const0_rtx
;
3352 #ifdef FLOAT_STORE_FLAG_VALUE
3353 if (SCALAR_FLOAT_MODE_P (mode
))
3355 true_rtx
= (CONST_DOUBLE_FROM_REAL_VALUE
3356 (FLOAT_STORE_FLAG_VALUE (mode
), mode
));
3357 false_rtx
= CONST0_RTX (mode
);
3382 rtx op0
= const_arg0
? const_arg0
: folded_arg0
;
3383 rtx op1
= const_arg1
? const_arg1
: folded_arg1
;
3384 new = simplify_relational_operation (code
, mode
, mode_arg0
, op0
, op1
);
3389 case RTX_COMM_ARITH
:
3393 /* If the second operand is a LABEL_REF, see if the first is a MINUS
3394 with that LABEL_REF as its second operand. If so, the result is
3395 the first operand of that MINUS. This handles switches with an
3396 ADDR_DIFF_VEC table. */
3397 if (const_arg1
&& GET_CODE (const_arg1
) == LABEL_REF
)
3400 = GET_CODE (folded_arg0
) == MINUS
? folded_arg0
3401 : lookup_as_function (folded_arg0
, MINUS
);
3403 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
3404 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg1
, 0))
3407 /* Now try for a CONST of a MINUS like the above. */
3408 if ((y
= (GET_CODE (folded_arg0
) == CONST
? folded_arg0
3409 : lookup_as_function (folded_arg0
, CONST
))) != 0
3410 && GET_CODE (XEXP (y
, 0)) == MINUS
3411 && GET_CODE (XEXP (XEXP (y
, 0), 1)) == LABEL_REF
3412 && XEXP (XEXP (XEXP (y
, 0), 1), 0) == XEXP (const_arg1
, 0))
3413 return XEXP (XEXP (y
, 0), 0);
3416 /* Likewise if the operands are in the other order. */
3417 if (const_arg0
&& GET_CODE (const_arg0
) == LABEL_REF
)
3420 = GET_CODE (folded_arg1
) == MINUS
? folded_arg1
3421 : lookup_as_function (folded_arg1
, MINUS
);
3423 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
3424 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg0
, 0))
3427 /* Now try for a CONST of a MINUS like the above. */
3428 if ((y
= (GET_CODE (folded_arg1
) == CONST
? folded_arg1
3429 : lookup_as_function (folded_arg1
, CONST
))) != 0
3430 && GET_CODE (XEXP (y
, 0)) == MINUS
3431 && GET_CODE (XEXP (XEXP (y
, 0), 1)) == LABEL_REF
3432 && XEXP (XEXP (XEXP (y
, 0), 1), 0) == XEXP (const_arg0
, 0))
3433 return XEXP (XEXP (y
, 0), 0);
3436 /* If second operand is a register equivalent to a negative
3437 CONST_INT, see if we can find a register equivalent to the
3438 positive constant. Make a MINUS if so. Don't do this for
3439 a non-negative constant since we might then alternate between
3440 choosing positive and negative constants. Having the positive
3441 constant previously-used is the more common case. Be sure
3442 the resulting constant is non-negative; if const_arg1 were
3443 the smallest negative number this would overflow: depending
3444 on the mode, this would either just be the same value (and
3445 hence not save anything) or be incorrect. */
3446 if (const_arg1
!= 0 && GET_CODE (const_arg1
) == CONST_INT
3447 && INTVAL (const_arg1
) < 0
3448 /* This used to test
3450 -INTVAL (const_arg1) >= 0
3452 But The Sun V5.0 compilers mis-compiled that test. So
3453 instead we test for the problematic value in a more direct
3454 manner and hope the Sun compilers get it correct. */
3455 && INTVAL (const_arg1
) !=
3456 ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1))
3457 && REG_P (folded_arg1
))
3459 rtx new_const
= GEN_INT (-INTVAL (const_arg1
));
3461 = lookup (new_const
, SAFE_HASH (new_const
, mode
), mode
);
3464 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
3466 return simplify_gen_binary (MINUS
, mode
, folded_arg0
,
3467 canon_reg (p
->exp
, NULL_RTX
));
3472 /* If we have (MINUS Y C), see if Y is known to be (PLUS Z C2).
3473 If so, produce (PLUS Z C2-C). */
3474 if (const_arg1
!= 0 && GET_CODE (const_arg1
) == CONST_INT
)
3476 rtx y
= lookup_as_function (XEXP (x
, 0), PLUS
);
3477 if (y
&& GET_CODE (XEXP (y
, 1)) == CONST_INT
)
3478 return fold_rtx (plus_constant (copy_rtx (y
),
3479 -INTVAL (const_arg1
)),
3486 case SMIN
: case SMAX
: case UMIN
: case UMAX
:
3487 case IOR
: case AND
: case XOR
:
3489 case ASHIFT
: case LSHIFTRT
: case ASHIFTRT
:
3490 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
3491 is known to be of similar form, we may be able to replace the
3492 operation with a combined operation. This may eliminate the
3493 intermediate operation if every use is simplified in this way.
3494 Note that the similar optimization done by combine.c only works
3495 if the intermediate operation's result has only one reference. */
3497 if (REG_P (folded_arg0
)
3498 && const_arg1
&& GET_CODE (const_arg1
) == CONST_INT
)
3501 = (code
== ASHIFT
|| code
== ASHIFTRT
|| code
== LSHIFTRT
);
3502 rtx y
, inner_const
, new_const
;
3503 enum rtx_code associate_code
;
3506 && (INTVAL (const_arg1
) >= GET_MODE_BITSIZE (mode
)
3507 || INTVAL (const_arg1
) < 0))
3509 if (SHIFT_COUNT_TRUNCATED
)
3510 const_arg1
= GEN_INT (INTVAL (const_arg1
)
3511 & (GET_MODE_BITSIZE (mode
) - 1));
3516 y
= lookup_as_function (folded_arg0
, code
);
3520 /* If we have compiled a statement like
3521 "if (x == (x & mask1))", and now are looking at
3522 "x & mask2", we will have a case where the first operand
3523 of Y is the same as our first operand. Unless we detect
3524 this case, an infinite loop will result. */
3525 if (XEXP (y
, 0) == folded_arg0
)
3528 inner_const
= equiv_constant (fold_rtx (XEXP (y
, 1), 0));
3529 if (!inner_const
|| GET_CODE (inner_const
) != CONST_INT
)
3532 /* Don't associate these operations if they are a PLUS with the
3533 same constant and it is a power of two. These might be doable
3534 with a pre- or post-increment. Similarly for two subtracts of
3535 identical powers of two with post decrement. */
3537 if (code
== PLUS
&& const_arg1
== inner_const
3538 && ((HAVE_PRE_INCREMENT
3539 && exact_log2 (INTVAL (const_arg1
)) >= 0)
3540 || (HAVE_POST_INCREMENT
3541 && exact_log2 (INTVAL (const_arg1
)) >= 0)
3542 || (HAVE_PRE_DECREMENT
3543 && exact_log2 (- INTVAL (const_arg1
)) >= 0)
3544 || (HAVE_POST_DECREMENT
3545 && exact_log2 (- INTVAL (const_arg1
)) >= 0)))
3549 && (INTVAL (inner_const
) >= GET_MODE_BITSIZE (mode
)
3550 || INTVAL (inner_const
) < 0))
3552 if (SHIFT_COUNT_TRUNCATED
)
3553 inner_const
= GEN_INT (INTVAL (inner_const
)
3554 & (GET_MODE_BITSIZE (mode
) - 1));
3559 /* Compute the code used to compose the constants. For example,
3560 A-C1-C2 is A-(C1 + C2), so if CODE == MINUS, we want PLUS. */
3562 associate_code
= (is_shift
|| code
== MINUS
? PLUS
: code
);
3564 new_const
= simplify_binary_operation (associate_code
, mode
,
3565 const_arg1
, inner_const
);
3570 /* If we are associating shift operations, don't let this
3571 produce a shift of the size of the object or larger.
3572 This could occur when we follow a sign-extend by a right
3573 shift on a machine that does a sign-extend as a pair
3577 && GET_CODE (new_const
) == CONST_INT
3578 && INTVAL (new_const
) >= GET_MODE_BITSIZE (mode
))
3580 /* As an exception, we can turn an ASHIFTRT of this
3581 form into a shift of the number of bits - 1. */
3582 if (code
== ASHIFTRT
)
3583 new_const
= GEN_INT (GET_MODE_BITSIZE (mode
) - 1);
3584 else if (!side_effects_p (XEXP (y
, 0)))
3585 return CONST0_RTX (mode
);
3590 y
= copy_rtx (XEXP (y
, 0));
3592 /* If Y contains our first operand (the most common way this
3593 can happen is if Y is a MEM), we would do into an infinite
3594 loop if we tried to fold it. So don't in that case. */
3596 if (! reg_mentioned_p (folded_arg0
, y
))
3597 y
= fold_rtx (y
, insn
);
3599 return simplify_gen_binary (code
, mode
, y
, new_const
);
3603 case DIV
: case UDIV
:
3604 /* ??? The associative optimization performed immediately above is
3605 also possible for DIV and UDIV using associate_code of MULT.
3606 However, we would need extra code to verify that the
3607 multiplication does not overflow, that is, there is no overflow
3608 in the calculation of new_const. */
3615 new = simplify_binary_operation (code
, mode
,
3616 const_arg0
? const_arg0
: folded_arg0
,
3617 const_arg1
? const_arg1
: folded_arg1
);
3621 /* (lo_sum (high X) X) is simply X. */
3622 if (code
== LO_SUM
&& const_arg0
!= 0
3623 && GET_CODE (const_arg0
) == HIGH
3624 && rtx_equal_p (XEXP (const_arg0
, 0), const_arg1
))
3629 case RTX_BITFIELD_OPS
:
3630 new = simplify_ternary_operation (code
, mode
, mode_arg0
,
3631 const_arg0
? const_arg0
: folded_arg0
,
3632 const_arg1
? const_arg1
: folded_arg1
,
3633 const_arg2
? const_arg2
: XEXP (x
, 2));
3640 return new ? new : x
;
3643 /* Return a constant value currently equivalent to X.
3644 Return 0 if we don't know one. */
3647 equiv_constant (rtx x
)
3650 && REGNO_QTY_VALID_P (REGNO (x
)))
3652 int x_q
= REG_QTY (REGNO (x
));
3653 struct qty_table_elem
*x_ent
= &qty_table
[x_q
];
3655 if (x_ent
->const_rtx
)
3656 x
= gen_lowpart (GET_MODE (x
), x_ent
->const_rtx
);
3659 if (x
== 0 || CONSTANT_P (x
))
3662 if (GET_CODE (x
) == SUBREG
)
3666 /* See if we previously assigned a constant value to this SUBREG. */
3667 if ((new = lookup_as_function (x
, CONST_INT
)) != 0
3668 || (new = lookup_as_function (x
, CONST_DOUBLE
)) != 0)
3671 if (REG_P (SUBREG_REG (x
))
3672 && (new = equiv_constant (SUBREG_REG (x
))) != 0)
3673 return simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
3674 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
3679 /* If X is a MEM, see if it is a constant-pool reference, or look it up in
3680 the hash table in case its value was seen before. */
3684 struct table_elt
*elt
;
3686 x
= avoid_constant_pool_reference (x
);
3690 elt
= lookup (x
, SAFE_HASH (x
, GET_MODE (x
)), GET_MODE (x
));
3694 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
3695 if (elt
->is_const
&& CONSTANT_P (elt
->exp
))
3702 /* Given INSN, a jump insn, PATH_TAKEN indicates if we are following the "taken"
3703 branch. It will be zero if not.
3705 In certain cases, this can cause us to add an equivalence. For example,
3706 if we are following the taken case of
3708 we can add the fact that `i' and '2' are now equivalent.
3710 In any case, we can record that this comparison was passed. If the same
3711 comparison is seen later, we will know its value. */
3714 record_jump_equiv (rtx insn
, int taken
)
3716 int cond_known_true
;
3719 enum machine_mode mode
, mode0
, mode1
;
3720 int reversed_nonequality
= 0;
3723 /* Ensure this is the right kind of insn. */
3724 if (! any_condjump_p (insn
))
3726 set
= pc_set (insn
);
3728 /* See if this jump condition is known true or false. */
3730 cond_known_true
= (XEXP (SET_SRC (set
), 2) == pc_rtx
);
3732 cond_known_true
= (XEXP (SET_SRC (set
), 1) == pc_rtx
);
3734 /* Get the type of comparison being done and the operands being compared.
3735 If we had to reverse a non-equality condition, record that fact so we
3736 know that it isn't valid for floating-point. */
3737 code
= GET_CODE (XEXP (SET_SRC (set
), 0));
3738 op0
= fold_rtx (XEXP (XEXP (SET_SRC (set
), 0), 0), insn
);
3739 op1
= fold_rtx (XEXP (XEXP (SET_SRC (set
), 0), 1), insn
);
3741 code
= find_comparison_args (code
, &op0
, &op1
, &mode0
, &mode1
);
3742 if (! cond_known_true
)
3744 code
= reversed_comparison_code_parts (code
, op0
, op1
, insn
);
3746 /* Don't remember if we can't find the inverse. */
3747 if (code
== UNKNOWN
)
3751 /* The mode is the mode of the non-constant. */
3753 if (mode1
!= VOIDmode
)
3756 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
);
3759 /* Yet another form of subreg creation. In this case, we want something in
3760 MODE, and we should assume OP has MODE iff it is naturally modeless. */
3763 record_jump_cond_subreg (enum machine_mode mode
, rtx op
)
3765 enum machine_mode op_mode
= GET_MODE (op
);
3766 if (op_mode
== mode
|| op_mode
== VOIDmode
)
3768 return lowpart_subreg (mode
, op
, op_mode
);
3771 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
3772 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
3773 Make any useful entries we can with that information. Called from
3774 above function and called recursively. */
3777 record_jump_cond (enum rtx_code code
, enum machine_mode mode
, rtx op0
,
3778 rtx op1
, int reversed_nonequality
)
3780 unsigned op0_hash
, op1_hash
;
3781 int op0_in_memory
, op1_in_memory
;
3782 struct table_elt
*op0_elt
, *op1_elt
;
3784 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
3785 we know that they are also equal in the smaller mode (this is also
3786 true for all smaller modes whether or not there is a SUBREG, but
3787 is not worth testing for with no SUBREG). */
3789 /* Note that GET_MODE (op0) may not equal MODE. */
3790 if (code
== EQ
&& GET_CODE (op0
) == SUBREG
3791 && (GET_MODE_SIZE (GET_MODE (op0
))
3792 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
)))))
3794 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
3795 rtx tem
= record_jump_cond_subreg (inner_mode
, op1
);
3797 record_jump_cond (code
, mode
, SUBREG_REG (op0
), tem
,
3798 reversed_nonequality
);
3801 if (code
== EQ
&& GET_CODE (op1
) == SUBREG
3802 && (GET_MODE_SIZE (GET_MODE (op1
))
3803 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
)))))
3805 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
3806 rtx tem
= record_jump_cond_subreg (inner_mode
, op0
);
3808 record_jump_cond (code
, mode
, SUBREG_REG (op1
), tem
,
3809 reversed_nonequality
);
3812 /* Similarly, if this is an NE comparison, and either is a SUBREG
3813 making a smaller mode, we know the whole thing is also NE. */
3815 /* Note that GET_MODE (op0) may not equal MODE;
3816 if we test MODE instead, we can get an infinite recursion
3817 alternating between two modes each wider than MODE. */
3819 if (code
== NE
&& GET_CODE (op0
) == SUBREG
3820 && subreg_lowpart_p (op0
)
3821 && (GET_MODE_SIZE (GET_MODE (op0
))
3822 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
)))))
3824 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
3825 rtx tem
= record_jump_cond_subreg (inner_mode
, op1
);
3827 record_jump_cond (code
, mode
, SUBREG_REG (op0
), tem
,
3828 reversed_nonequality
);
3831 if (code
== NE
&& GET_CODE (op1
) == SUBREG
3832 && subreg_lowpart_p (op1
)
3833 && (GET_MODE_SIZE (GET_MODE (op1
))
3834 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
)))))
3836 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
3837 rtx tem
= record_jump_cond_subreg (inner_mode
, op0
);
3839 record_jump_cond (code
, mode
, SUBREG_REG (op1
), tem
,
3840 reversed_nonequality
);
3843 /* Hash both operands. */
3846 hash_arg_in_memory
= 0;
3847 op0_hash
= HASH (op0
, mode
);
3848 op0_in_memory
= hash_arg_in_memory
;
3854 hash_arg_in_memory
= 0;
3855 op1_hash
= HASH (op1
, mode
);
3856 op1_in_memory
= hash_arg_in_memory
;
3861 /* Look up both operands. */
3862 op0_elt
= lookup (op0
, op0_hash
, mode
);
3863 op1_elt
= lookup (op1
, op1_hash
, mode
);
3865 /* If both operands are already equivalent or if they are not in the
3866 table but are identical, do nothing. */
3867 if ((op0_elt
!= 0 && op1_elt
!= 0
3868 && op0_elt
->first_same_value
== op1_elt
->first_same_value
)
3869 || op0
== op1
|| rtx_equal_p (op0
, op1
))
3872 /* If we aren't setting two things equal all we can do is save this
3873 comparison. Similarly if this is floating-point. In the latter
3874 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
3875 If we record the equality, we might inadvertently delete code
3876 whose intent was to change -0 to +0. */
3878 if (code
!= EQ
|| FLOAT_MODE_P (GET_MODE (op0
)))
3880 struct qty_table_elem
*ent
;
3883 /* If we reversed a floating-point comparison, if OP0 is not a
3884 register, or if OP1 is neither a register or constant, we can't
3888 op1
= equiv_constant (op1
);
3890 if ((reversed_nonequality
&& FLOAT_MODE_P (mode
))
3891 || !REG_P (op0
) || op1
== 0)
3894 /* Put OP0 in the hash table if it isn't already. This gives it a
3895 new quantity number. */
3898 if (insert_regs (op0
, NULL
, 0))
3900 rehash_using_reg (op0
);
3901 op0_hash
= HASH (op0
, mode
);
3903 /* If OP0 is contained in OP1, this changes its hash code
3904 as well. Faster to rehash than to check, except
3905 for the simple case of a constant. */
3906 if (! CONSTANT_P (op1
))
3907 op1_hash
= HASH (op1
,mode
);
3910 op0_elt
= insert (op0
, NULL
, op0_hash
, mode
);
3911 op0_elt
->in_memory
= op0_in_memory
;
3914 qty
= REG_QTY (REGNO (op0
));
3915 ent
= &qty_table
[qty
];
3917 ent
->comparison_code
= code
;
3920 /* Look it up again--in case op0 and op1 are the same. */
3921 op1_elt
= lookup (op1
, op1_hash
, mode
);
3923 /* Put OP1 in the hash table so it gets a new quantity number. */
3926 if (insert_regs (op1
, NULL
, 0))
3928 rehash_using_reg (op1
);
3929 op1_hash
= HASH (op1
, mode
);
3932 op1_elt
= insert (op1
, NULL
, op1_hash
, mode
);
3933 op1_elt
->in_memory
= op1_in_memory
;
3936 ent
->comparison_const
= NULL_RTX
;
3937 ent
->comparison_qty
= REG_QTY (REGNO (op1
));
3941 ent
->comparison_const
= op1
;
3942 ent
->comparison_qty
= -1;
3948 /* If either side is still missing an equivalence, make it now,
3949 then merge the equivalences. */
3953 if (insert_regs (op0
, NULL
, 0))
3955 rehash_using_reg (op0
);
3956 op0_hash
= HASH (op0
, mode
);
3959 op0_elt
= insert (op0
, NULL
, op0_hash
, mode
);
3960 op0_elt
->in_memory
= op0_in_memory
;
3965 if (insert_regs (op1
, NULL
, 0))
3967 rehash_using_reg (op1
);
3968 op1_hash
= HASH (op1
, mode
);
3971 op1_elt
= insert (op1
, NULL
, op1_hash
, mode
);
3972 op1_elt
->in_memory
= op1_in_memory
;
3975 merge_equiv_classes (op0_elt
, op1_elt
);
3978 /* CSE processing for one instruction.
3979 First simplify sources and addresses of all assignments
3980 in the instruction, using previously-computed equivalents values.
3981 Then install the new sources and destinations in the table
3982 of available values.
3984 If LIBCALL_INSN is nonzero, don't record any equivalence made in
3985 the insn. It means that INSN is inside libcall block. In this
3986 case LIBCALL_INSN is the corresponding insn with REG_LIBCALL. */
3988 /* Data on one SET contained in the instruction. */
3992 /* The SET rtx itself. */
3994 /* The SET_SRC of the rtx (the original value, if it is changing). */
3996 /* The hash-table element for the SET_SRC of the SET. */
3997 struct table_elt
*src_elt
;
3998 /* Hash value for the SET_SRC. */
4000 /* Hash value for the SET_DEST. */
4002 /* The SET_DEST, with SUBREG, etc., stripped. */
4004 /* Nonzero if the SET_SRC is in memory. */
4006 /* Nonzero if the SET_SRC contains something
4007 whose value cannot be predicted and understood. */
4009 /* Original machine mode, in case it becomes a CONST_INT.
4010 The size of this field should match the size of the mode
4011 field of struct rtx_def (see rtl.h). */
4012 ENUM_BITFIELD(machine_mode
) mode
: 8;
4013 /* A constant equivalent for SET_SRC, if any. */
4015 /* Original SET_SRC value used for libcall notes. */
4017 /* Hash value of constant equivalent for SET_SRC. */
4018 unsigned src_const_hash
;
4019 /* Table entry for constant equivalent for SET_SRC, if any. */
4020 struct table_elt
*src_const_elt
;
4021 /* Table entry for the destination address. */
4022 struct table_elt
*dest_addr_elt
;
4026 cse_insn (rtx insn
, rtx libcall_insn
)
4028 rtx x
= PATTERN (insn
);
4034 /* Records what this insn does to set CC0. */
4035 rtx this_insn_cc0
= 0;
4036 enum machine_mode this_insn_cc0_mode
= VOIDmode
;
4040 struct table_elt
*src_eqv_elt
= 0;
4041 int src_eqv_volatile
= 0;
4042 int src_eqv_in_memory
= 0;
4043 unsigned src_eqv_hash
= 0;
4045 struct set
*sets
= (struct set
*) 0;
4049 /* Find all the SETs and CLOBBERs in this instruction.
4050 Record all the SETs in the array `set' and count them.
4051 Also determine whether there is a CLOBBER that invalidates
4052 all memory references, or all references at varying addresses. */
4056 for (tem
= CALL_INSN_FUNCTION_USAGE (insn
); tem
; tem
= XEXP (tem
, 1))
4058 if (GET_CODE (XEXP (tem
, 0)) == CLOBBER
)
4059 invalidate (SET_DEST (XEXP (tem
, 0)), VOIDmode
);
4060 XEXP (tem
, 0) = canon_reg (XEXP (tem
, 0), insn
);
4064 if (GET_CODE (x
) == SET
)
4066 sets
= alloca (sizeof (struct set
));
4069 /* Ignore SETs that are unconditional jumps.
4070 They never need cse processing, so this does not hurt.
4071 The reason is not efficiency but rather
4072 so that we can test at the end for instructions
4073 that have been simplified to unconditional jumps
4074 and not be misled by unchanged instructions
4075 that were unconditional jumps to begin with. */
4076 if (SET_DEST (x
) == pc_rtx
4077 && GET_CODE (SET_SRC (x
)) == LABEL_REF
)
4080 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
4081 The hard function value register is used only once, to copy to
4082 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
4083 Ensure we invalidate the destination register. On the 80386 no
4084 other code would invalidate it since it is a fixed_reg.
4085 We need not check the return of apply_change_group; see canon_reg. */
4087 else if (GET_CODE (SET_SRC (x
)) == CALL
)
4089 canon_reg (SET_SRC (x
), insn
);
4090 apply_change_group ();
4091 fold_rtx (SET_SRC (x
), insn
);
4092 invalidate (SET_DEST (x
), VOIDmode
);
4097 else if (GET_CODE (x
) == PARALLEL
)
4099 int lim
= XVECLEN (x
, 0);
4101 sets
= alloca (lim
* sizeof (struct set
));
4103 /* Find all regs explicitly clobbered in this insn,
4104 and ensure they are not replaced with any other regs
4105 elsewhere in this insn.
4106 When a reg that is clobbered is also used for input,
4107 we should presume that that is for a reason,
4108 and we should not substitute some other register
4109 which is not supposed to be clobbered.
4110 Therefore, this loop cannot be merged into the one below
4111 because a CALL may precede a CLOBBER and refer to the
4112 value clobbered. We must not let a canonicalization do
4113 anything in that case. */
4114 for (i
= 0; i
< lim
; i
++)
4116 rtx y
= XVECEXP (x
, 0, i
);
4117 if (GET_CODE (y
) == CLOBBER
)
4119 rtx clobbered
= XEXP (y
, 0);
4121 if (REG_P (clobbered
)
4122 || GET_CODE (clobbered
) == SUBREG
)
4123 invalidate (clobbered
, VOIDmode
);
4124 else if (GET_CODE (clobbered
) == STRICT_LOW_PART
4125 || GET_CODE (clobbered
) == ZERO_EXTRACT
)
4126 invalidate (XEXP (clobbered
, 0), GET_MODE (clobbered
));
4130 for (i
= 0; i
< lim
; i
++)
4132 rtx y
= XVECEXP (x
, 0, i
);
4133 if (GET_CODE (y
) == SET
)
4135 /* As above, we ignore unconditional jumps and call-insns and
4136 ignore the result of apply_change_group. */
4137 if (GET_CODE (SET_SRC (y
)) == CALL
)
4139 canon_reg (SET_SRC (y
), insn
);
4140 apply_change_group ();
4141 fold_rtx (SET_SRC (y
), insn
);
4142 invalidate (SET_DEST (y
), VOIDmode
);
4144 else if (SET_DEST (y
) == pc_rtx
4145 && GET_CODE (SET_SRC (y
)) == LABEL_REF
)
4148 sets
[n_sets
++].rtl
= y
;
4150 else if (GET_CODE (y
) == CLOBBER
)
4152 /* If we clobber memory, canon the address.
4153 This does nothing when a register is clobbered
4154 because we have already invalidated the reg. */
4155 if (MEM_P (XEXP (y
, 0)))
4156 canon_reg (XEXP (y
, 0), NULL_RTX
);
4158 else if (GET_CODE (y
) == USE
4159 && ! (REG_P (XEXP (y
, 0))
4160 && REGNO (XEXP (y
, 0)) < FIRST_PSEUDO_REGISTER
))
4161 canon_reg (y
, NULL_RTX
);
4162 else if (GET_CODE (y
) == CALL
)
4164 /* The result of apply_change_group can be ignored; see
4166 canon_reg (y
, insn
);
4167 apply_change_group ();
4172 else if (GET_CODE (x
) == CLOBBER
)
4174 if (MEM_P (XEXP (x
, 0)))
4175 canon_reg (XEXP (x
, 0), NULL_RTX
);
4178 /* Canonicalize a USE of a pseudo register or memory location. */
4179 else if (GET_CODE (x
) == USE
4180 && ! (REG_P (XEXP (x
, 0))
4181 && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
))
4182 canon_reg (XEXP (x
, 0), NULL_RTX
);
4183 else if (GET_CODE (x
) == CALL
)
4185 /* The result of apply_change_group can be ignored; see canon_reg. */
4186 canon_reg (x
, insn
);
4187 apply_change_group ();
4191 /* Store the equivalent value in SRC_EQV, if different, or if the DEST
4192 is a STRICT_LOW_PART. The latter condition is necessary because SRC_EQV
4193 is handled specially for this case, and if it isn't set, then there will
4194 be no equivalence for the destination. */
4195 if (n_sets
== 1 && REG_NOTES (insn
) != 0
4196 && (tem
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
)) != 0
4197 && (! rtx_equal_p (XEXP (tem
, 0), SET_SRC (sets
[0].rtl
))
4198 || GET_CODE (SET_DEST (sets
[0].rtl
)) == STRICT_LOW_PART
))
4200 src_eqv
= fold_rtx (canon_reg (XEXP (tem
, 0), NULL_RTX
), insn
);
4201 XEXP (tem
, 0) = src_eqv
;
4204 /* Canonicalize sources and addresses of destinations.
4205 We do this in a separate pass to avoid problems when a MATCH_DUP is
4206 present in the insn pattern. In that case, we want to ensure that
4207 we don't break the duplicate nature of the pattern. So we will replace
4208 both operands at the same time. Otherwise, we would fail to find an
4209 equivalent substitution in the loop calling validate_change below.
4211 We used to suppress canonicalization of DEST if it appears in SRC,
4212 but we don't do this any more. */
4214 for (i
= 0; i
< n_sets
; i
++)
4216 rtx dest
= SET_DEST (sets
[i
].rtl
);
4217 rtx src
= SET_SRC (sets
[i
].rtl
);
4218 rtx
new = canon_reg (src
, insn
);
4220 sets
[i
].orig_src
= src
;
4221 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 1);
4223 if (GET_CODE (dest
) == ZERO_EXTRACT
)
4225 validate_change (insn
, &XEXP (dest
, 1),
4226 canon_reg (XEXP (dest
, 1), insn
), 1);
4227 validate_change (insn
, &XEXP (dest
, 2),
4228 canon_reg (XEXP (dest
, 2), insn
), 1);
4231 while (GET_CODE (dest
) == SUBREG
4232 || GET_CODE (dest
) == ZERO_EXTRACT
4233 || GET_CODE (dest
) == STRICT_LOW_PART
)
4234 dest
= XEXP (dest
, 0);
4237 canon_reg (dest
, insn
);
4240 /* Now that we have done all the replacements, we can apply the change
4241 group and see if they all work. Note that this will cause some
4242 canonicalizations that would have worked individually not to be applied
4243 because some other canonicalization didn't work, but this should not
4246 The result of apply_change_group can be ignored; see canon_reg. */
4248 apply_change_group ();
4250 /* Set sets[i].src_elt to the class each source belongs to.
4251 Detect assignments from or to volatile things
4252 and set set[i] to zero so they will be ignored
4253 in the rest of this function.
4255 Nothing in this loop changes the hash table or the register chains. */
4257 for (i
= 0; i
< n_sets
; i
++)
4261 struct table_elt
*elt
= 0, *p
;
4262 enum machine_mode mode
;
4265 rtx src_related
= 0;
4266 struct table_elt
*src_const_elt
= 0;
4267 int src_cost
= MAX_COST
;
4268 int src_eqv_cost
= MAX_COST
;
4269 int src_folded_cost
= MAX_COST
;
4270 int src_related_cost
= MAX_COST
;
4271 int src_elt_cost
= MAX_COST
;
4272 int src_regcost
= MAX_COST
;
4273 int src_eqv_regcost
= MAX_COST
;
4274 int src_folded_regcost
= MAX_COST
;
4275 int src_related_regcost
= MAX_COST
;
4276 int src_elt_regcost
= MAX_COST
;
4277 /* Set nonzero if we need to call force_const_mem on with the
4278 contents of src_folded before using it. */
4279 int src_folded_force_flag
= 0;
4281 dest
= SET_DEST (sets
[i
].rtl
);
4282 src
= SET_SRC (sets
[i
].rtl
);
4284 /* If SRC is a constant that has no machine mode,
4285 hash it with the destination's machine mode.
4286 This way we can keep different modes separate. */
4288 mode
= GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
4289 sets
[i
].mode
= mode
;
4293 enum machine_mode eqvmode
= mode
;
4294 if (GET_CODE (dest
) == STRICT_LOW_PART
)
4295 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
4297 hash_arg_in_memory
= 0;
4298 src_eqv_hash
= HASH (src_eqv
, eqvmode
);
4300 /* Find the equivalence class for the equivalent expression. */
4303 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash
, eqvmode
);
4305 src_eqv_volatile
= do_not_record
;
4306 src_eqv_in_memory
= hash_arg_in_memory
;
4309 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
4310 value of the INNER register, not the destination. So it is not
4311 a valid substitution for the source. But save it for later. */
4312 if (GET_CODE (dest
) == STRICT_LOW_PART
)
4315 src_eqv_here
= src_eqv
;
4317 /* Simplify and foldable subexpressions in SRC. Then get the fully-
4318 simplified result, which may not necessarily be valid. */
4319 src_folded
= fold_rtx (src
, insn
);
4322 /* ??? This caused bad code to be generated for the m68k port with -O2.
4323 Suppose src is (CONST_INT -1), and that after truncation src_folded
4324 is (CONST_INT 3). Suppose src_folded is then used for src_const.
4325 At the end we will add src and src_const to the same equivalence
4326 class. We now have 3 and -1 on the same equivalence class. This
4327 causes later instructions to be mis-optimized. */
4328 /* If storing a constant in a bitfield, pre-truncate the constant
4329 so we will be able to record it later. */
4330 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
)
4332 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
4334 if (GET_CODE (src
) == CONST_INT
4335 && GET_CODE (width
) == CONST_INT
4336 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
4337 && (INTVAL (src
) & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
4339 = GEN_INT (INTVAL (src
) & (((HOST_WIDE_INT
) 1
4340 << INTVAL (width
)) - 1));
4344 /* Compute SRC's hash code, and also notice if it
4345 should not be recorded at all. In that case,
4346 prevent any further processing of this assignment. */
4348 hash_arg_in_memory
= 0;
4351 sets
[i
].src_hash
= HASH (src
, mode
);
4352 sets
[i
].src_volatile
= do_not_record
;
4353 sets
[i
].src_in_memory
= hash_arg_in_memory
;
4355 /* If SRC is a MEM, there is a REG_EQUIV note for SRC, and DEST is
4356 a pseudo, do not record SRC. Using SRC as a replacement for
4357 anything else will be incorrect in that situation. Note that
4358 this usually occurs only for stack slots, in which case all the
4359 RTL would be referring to SRC, so we don't lose any optimization
4360 opportunities by not having SRC in the hash table. */
4363 && find_reg_note (insn
, REG_EQUIV
, NULL_RTX
) != 0
4365 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
4366 sets
[i
].src_volatile
= 1;
4369 /* It is no longer clear why we used to do this, but it doesn't
4370 appear to still be needed. So let's try without it since this
4371 code hurts cse'ing widened ops. */
4372 /* If source is a paradoxical subreg (such as QI treated as an SI),
4373 treat it as volatile. It may do the work of an SI in one context
4374 where the extra bits are not being used, but cannot replace an SI
4376 if (GET_CODE (src
) == SUBREG
4377 && (GET_MODE_SIZE (GET_MODE (src
))
4378 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))))
4379 sets
[i
].src_volatile
= 1;
4382 /* Locate all possible equivalent forms for SRC. Try to replace
4383 SRC in the insn with each cheaper equivalent.
4385 We have the following types of equivalents: SRC itself, a folded
4386 version, a value given in a REG_EQUAL note, or a value related
4389 Each of these equivalents may be part of an additional class
4390 of equivalents (if more than one is in the table, they must be in
4391 the same class; we check for this).
4393 If the source is volatile, we don't do any table lookups.
4395 We note any constant equivalent for possible later use in a
4398 if (!sets
[i
].src_volatile
)
4399 elt
= lookup (src
, sets
[i
].src_hash
, mode
);
4401 sets
[i
].src_elt
= elt
;
4403 if (elt
&& src_eqv_here
&& src_eqv_elt
)
4405 if (elt
->first_same_value
!= src_eqv_elt
->first_same_value
)
4407 /* The REG_EQUAL is indicating that two formerly distinct
4408 classes are now equivalent. So merge them. */
4409 merge_equiv_classes (elt
, src_eqv_elt
);
4410 src_eqv_hash
= HASH (src_eqv
, elt
->mode
);
4411 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash
, elt
->mode
);
4417 else if (src_eqv_elt
)
4420 /* Try to find a constant somewhere and record it in `src_const'.
4421 Record its table element, if any, in `src_const_elt'. Look in
4422 any known equivalences first. (If the constant is not in the
4423 table, also set `sets[i].src_const_hash'). */
4425 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
4429 src_const_elt
= elt
;
4434 && (CONSTANT_P (src_folded
)
4435 /* Consider (minus (label_ref L1) (label_ref L2)) as
4436 "constant" here so we will record it. This allows us
4437 to fold switch statements when an ADDR_DIFF_VEC is used. */
4438 || (GET_CODE (src_folded
) == MINUS
4439 && GET_CODE (XEXP (src_folded
, 0)) == LABEL_REF
4440 && GET_CODE (XEXP (src_folded
, 1)) == LABEL_REF
)))
4441 src_const
= src_folded
, src_const_elt
= elt
;
4442 else if (src_const
== 0 && src_eqv_here
&& CONSTANT_P (src_eqv_here
))
4443 src_const
= src_eqv_here
, src_const_elt
= src_eqv_elt
;
4445 /* If we don't know if the constant is in the table, get its
4446 hash code and look it up. */
4447 if (src_const
&& src_const_elt
== 0)
4449 sets
[i
].src_const_hash
= HASH (src_const
, mode
);
4450 src_const_elt
= lookup (src_const
, sets
[i
].src_const_hash
, mode
);
4453 sets
[i
].src_const
= src_const
;
4454 sets
[i
].src_const_elt
= src_const_elt
;
4456 /* If the constant and our source are both in the table, mark them as
4457 equivalent. Otherwise, if a constant is in the table but the source
4458 isn't, set ELT to it. */
4459 if (src_const_elt
&& elt
4460 && src_const_elt
->first_same_value
!= elt
->first_same_value
)
4461 merge_equiv_classes (elt
, src_const_elt
);
4462 else if (src_const_elt
&& elt
== 0)
4463 elt
= src_const_elt
;
4465 /* See if there is a register linearly related to a constant
4466 equivalent of SRC. */
4468 && (GET_CODE (src_const
) == CONST
4469 || (src_const_elt
&& src_const_elt
->related_value
!= 0)))
4471 src_related
= use_related_value (src_const
, src_const_elt
);
4474 struct table_elt
*src_related_elt
4475 = lookup (src_related
, HASH (src_related
, mode
), mode
);
4476 if (src_related_elt
&& elt
)
4478 if (elt
->first_same_value
4479 != src_related_elt
->first_same_value
)
4480 /* This can occur when we previously saw a CONST
4481 involving a SYMBOL_REF and then see the SYMBOL_REF
4482 twice. Merge the involved classes. */
4483 merge_equiv_classes (elt
, src_related_elt
);
4486 src_related_elt
= 0;
4488 else if (src_related_elt
&& elt
== 0)
4489 elt
= src_related_elt
;
4493 /* See if we have a CONST_INT that is already in a register in a
4496 if (src_const
&& src_related
== 0 && GET_CODE (src_const
) == CONST_INT
4497 && GET_MODE_CLASS (mode
) == MODE_INT
4498 && GET_MODE_BITSIZE (mode
) < BITS_PER_WORD
)
4500 enum machine_mode wider_mode
;
4502 for (wider_mode
= GET_MODE_WIDER_MODE (mode
);
4503 GET_MODE_BITSIZE (wider_mode
) <= BITS_PER_WORD
4504 && src_related
== 0;
4505 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
4507 struct table_elt
*const_elt
4508 = lookup (src_const
, HASH (src_const
, wider_mode
), wider_mode
);
4513 for (const_elt
= const_elt
->first_same_value
;
4514 const_elt
; const_elt
= const_elt
->next_same_value
)
4515 if (REG_P (const_elt
->exp
))
4517 src_related
= gen_lowpart (mode
,
4524 /* Another possibility is that we have an AND with a constant in
4525 a mode narrower than a word. If so, it might have been generated
4526 as part of an "if" which would narrow the AND. If we already
4527 have done the AND in a wider mode, we can use a SUBREG of that
4530 if (flag_expensive_optimizations
&& ! src_related
4531 && GET_CODE (src
) == AND
&& GET_CODE (XEXP (src
, 1)) == CONST_INT
4532 && GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
4534 enum machine_mode tmode
;
4535 rtx new_and
= gen_rtx_AND (VOIDmode
, NULL_RTX
, XEXP (src
, 1));
4537 for (tmode
= GET_MODE_WIDER_MODE (mode
);
4538 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
4539 tmode
= GET_MODE_WIDER_MODE (tmode
))
4541 rtx inner
= gen_lowpart (tmode
, XEXP (src
, 0));
4542 struct table_elt
*larger_elt
;
4546 PUT_MODE (new_and
, tmode
);
4547 XEXP (new_and
, 0) = inner
;
4548 larger_elt
= lookup (new_and
, HASH (new_and
, tmode
), tmode
);
4549 if (larger_elt
== 0)
4552 for (larger_elt
= larger_elt
->first_same_value
;
4553 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
4554 if (REG_P (larger_elt
->exp
))
4557 = gen_lowpart (mode
, larger_elt
->exp
);
4567 #ifdef LOAD_EXTEND_OP
4568 /* See if a MEM has already been loaded with a widening operation;
4569 if it has, we can use a subreg of that. Many CISC machines
4570 also have such operations, but this is only likely to be
4571 beneficial on these machines. */
4573 if (flag_expensive_optimizations
&& src_related
== 0
4574 && (GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
4575 && GET_MODE_CLASS (mode
) == MODE_INT
4576 && MEM_P (src
) && ! do_not_record
4577 && LOAD_EXTEND_OP (mode
) != UNKNOWN
)
4579 struct rtx_def memory_extend_buf
;
4580 rtx memory_extend_rtx
= &memory_extend_buf
;
4581 enum machine_mode tmode
;
4583 /* Set what we are trying to extend and the operation it might
4584 have been extended with. */
4585 memset (memory_extend_rtx
, 0, sizeof(*memory_extend_rtx
));
4586 PUT_CODE (memory_extend_rtx
, LOAD_EXTEND_OP (mode
));
4587 XEXP (memory_extend_rtx
, 0) = src
;
4589 for (tmode
= GET_MODE_WIDER_MODE (mode
);
4590 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
4591 tmode
= GET_MODE_WIDER_MODE (tmode
))
4593 struct table_elt
*larger_elt
;
4595 PUT_MODE (memory_extend_rtx
, tmode
);
4596 larger_elt
= lookup (memory_extend_rtx
,
4597 HASH (memory_extend_rtx
, tmode
), tmode
);
4598 if (larger_elt
== 0)
4601 for (larger_elt
= larger_elt
->first_same_value
;
4602 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
4603 if (REG_P (larger_elt
->exp
))
4605 src_related
= gen_lowpart (mode
,
4614 #endif /* LOAD_EXTEND_OP */
4616 if (src
== src_folded
)
4619 /* At this point, ELT, if nonzero, points to a class of expressions
4620 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
4621 and SRC_RELATED, if nonzero, each contain additional equivalent
4622 expressions. Prune these latter expressions by deleting expressions
4623 already in the equivalence class.
4625 Check for an equivalent identical to the destination. If found,
4626 this is the preferred equivalent since it will likely lead to
4627 elimination of the insn. Indicate this by placing it in
4631 elt
= elt
->first_same_value
;
4632 for (p
= elt
; p
; p
= p
->next_same_value
)
4634 enum rtx_code code
= GET_CODE (p
->exp
);
4636 /* If the expression is not valid, ignore it. Then we do not
4637 have to check for validity below. In most cases, we can use
4638 `rtx_equal_p', since canonicalization has already been done. */
4639 if (code
!= REG
&& ! exp_equiv_p (p
->exp
, p
->exp
, 1, false))
4642 /* Also skip paradoxical subregs, unless that's what we're
4645 && (GET_MODE_SIZE (GET_MODE (p
->exp
))
4646 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (p
->exp
))))
4648 && GET_CODE (src
) == SUBREG
4649 && GET_MODE (src
) == GET_MODE (p
->exp
)
4650 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))
4651 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (p
->exp
))))))
4654 if (src
&& GET_CODE (src
) == code
&& rtx_equal_p (src
, p
->exp
))
4656 else if (src_folded
&& GET_CODE (src_folded
) == code
4657 && rtx_equal_p (src_folded
, p
->exp
))
4659 else if (src_eqv_here
&& GET_CODE (src_eqv_here
) == code
4660 && rtx_equal_p (src_eqv_here
, p
->exp
))
4662 else if (src_related
&& GET_CODE (src_related
) == code
4663 && rtx_equal_p (src_related
, p
->exp
))
4666 /* This is the same as the destination of the insns, we want
4667 to prefer it. Copy it to src_related. The code below will
4668 then give it a negative cost. */
4669 if (GET_CODE (dest
) == code
&& rtx_equal_p (p
->exp
, dest
))
4673 /* Find the cheapest valid equivalent, trying all the available
4674 possibilities. Prefer items not in the hash table to ones
4675 that are when they are equal cost. Note that we can never
4676 worsen an insn as the current contents will also succeed.
4677 If we find an equivalent identical to the destination, use it as best,
4678 since this insn will probably be eliminated in that case. */
4681 if (rtx_equal_p (src
, dest
))
4682 src_cost
= src_regcost
= -1;
4685 src_cost
= COST (src
);
4686 src_regcost
= approx_reg_cost (src
);
4692 if (rtx_equal_p (src_eqv_here
, dest
))
4693 src_eqv_cost
= src_eqv_regcost
= -1;
4696 src_eqv_cost
= COST (src_eqv_here
);
4697 src_eqv_regcost
= approx_reg_cost (src_eqv_here
);
4703 if (rtx_equal_p (src_folded
, dest
))
4704 src_folded_cost
= src_folded_regcost
= -1;
4707 src_folded_cost
= COST (src_folded
);
4708 src_folded_regcost
= approx_reg_cost (src_folded
);
4714 if (rtx_equal_p (src_related
, dest
))
4715 src_related_cost
= src_related_regcost
= -1;
4718 src_related_cost
= COST (src_related
);
4719 src_related_regcost
= approx_reg_cost (src_related
);
4723 /* If this was an indirect jump insn, a known label will really be
4724 cheaper even though it looks more expensive. */
4725 if (dest
== pc_rtx
&& src_const
&& GET_CODE (src_const
) == LABEL_REF
)
4726 src_folded
= src_const
, src_folded_cost
= src_folded_regcost
= -1;
4728 /* Terminate loop when replacement made. This must terminate since
4729 the current contents will be tested and will always be valid. */
4734 /* Skip invalid entries. */
4735 while (elt
&& !REG_P (elt
->exp
)
4736 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, false))
4737 elt
= elt
->next_same_value
;
4739 /* A paradoxical subreg would be bad here: it'll be the right
4740 size, but later may be adjusted so that the upper bits aren't
4741 what we want. So reject it. */
4743 && GET_CODE (elt
->exp
) == SUBREG
4744 && (GET_MODE_SIZE (GET_MODE (elt
->exp
))
4745 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt
->exp
))))
4746 /* It is okay, though, if the rtx we're trying to match
4747 will ignore any of the bits we can't predict. */
4749 && GET_CODE (src
) == SUBREG
4750 && GET_MODE (src
) == GET_MODE (elt
->exp
)
4751 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))
4752 < GET_MODE_SIZE (GET_MODE (SUBREG_REG (elt
->exp
))))))
4754 elt
= elt
->next_same_value
;
4760 src_elt_cost
= elt
->cost
;
4761 src_elt_regcost
= elt
->regcost
;
4764 /* Find cheapest and skip it for the next time. For items
4765 of equal cost, use this order:
4766 src_folded, src, src_eqv, src_related and hash table entry. */
4768 && preferable (src_folded_cost
, src_folded_regcost
,
4769 src_cost
, src_regcost
) <= 0
4770 && preferable (src_folded_cost
, src_folded_regcost
,
4771 src_eqv_cost
, src_eqv_regcost
) <= 0
4772 && preferable (src_folded_cost
, src_folded_regcost
,
4773 src_related_cost
, src_related_regcost
) <= 0
4774 && preferable (src_folded_cost
, src_folded_regcost
,
4775 src_elt_cost
, src_elt_regcost
) <= 0)
4777 trial
= src_folded
, src_folded_cost
= MAX_COST
;
4778 if (src_folded_force_flag
)
4780 rtx forced
= force_const_mem (mode
, trial
);
4786 && preferable (src_cost
, src_regcost
,
4787 src_eqv_cost
, src_eqv_regcost
) <= 0
4788 && preferable (src_cost
, src_regcost
,
4789 src_related_cost
, src_related_regcost
) <= 0
4790 && preferable (src_cost
, src_regcost
,
4791 src_elt_cost
, src_elt_regcost
) <= 0)
4792 trial
= src
, src_cost
= MAX_COST
;
4793 else if (src_eqv_here
4794 && preferable (src_eqv_cost
, src_eqv_regcost
,
4795 src_related_cost
, src_related_regcost
) <= 0
4796 && preferable (src_eqv_cost
, src_eqv_regcost
,
4797 src_elt_cost
, src_elt_regcost
) <= 0)
4798 trial
= copy_rtx (src_eqv_here
), src_eqv_cost
= MAX_COST
;
4799 else if (src_related
4800 && preferable (src_related_cost
, src_related_regcost
,
4801 src_elt_cost
, src_elt_regcost
) <= 0)
4802 trial
= copy_rtx (src_related
), src_related_cost
= MAX_COST
;
4805 trial
= copy_rtx (elt
->exp
);
4806 elt
= elt
->next_same_value
;
4807 src_elt_cost
= MAX_COST
;
4810 /* We don't normally have an insn matching (set (pc) (pc)), so
4811 check for this separately here. We will delete such an
4814 For other cases such as a table jump or conditional jump
4815 where we know the ultimate target, go ahead and replace the
4816 operand. While that may not make a valid insn, we will
4817 reemit the jump below (and also insert any necessary
4819 if (n_sets
== 1 && dest
== pc_rtx
4821 || (GET_CODE (trial
) == LABEL_REF
4822 && ! condjump_p (insn
))))
4824 /* Don't substitute non-local labels, this confuses CFG. */
4825 if (GET_CODE (trial
) == LABEL_REF
4826 && LABEL_REF_NONLOCAL_P (trial
))
4829 SET_SRC (sets
[i
].rtl
) = trial
;
4830 cse_jumps_altered
= 1;
4834 /* Reject certain invalid forms of CONST that we create. */
4835 else if (CONSTANT_P (trial
)
4836 && GET_CODE (trial
) == CONST
4837 /* Reject cases that will cause decode_rtx_const to
4838 die. On the alpha when simplifying a switch, we
4839 get (const (truncate (minus (label_ref)
4841 && (GET_CODE (XEXP (trial
, 0)) == TRUNCATE
4842 /* Likewise on IA-64, except without the
4844 || (GET_CODE (XEXP (trial
, 0)) == MINUS
4845 && GET_CODE (XEXP (XEXP (trial
, 0), 0)) == LABEL_REF
4846 && GET_CODE (XEXP (XEXP (trial
, 0), 1)) == LABEL_REF
)))
4847 /* Do nothing for this case. */
4850 /* Look for a substitution that makes a valid insn. */
4851 else if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), trial
, 0))
4853 rtx
new = canon_reg (SET_SRC (sets
[i
].rtl
), insn
);
4855 /* If we just made a substitution inside a libcall, then we
4856 need to make the same substitution in any notes attached
4857 to the RETVAL insn. */
4859 && (REG_P (sets
[i
].orig_src
)
4860 || GET_CODE (sets
[i
].orig_src
) == SUBREG
4861 || MEM_P (sets
[i
].orig_src
)))
4863 rtx note
= find_reg_equal_equiv_note (libcall_insn
);
4865 XEXP (note
, 0) = simplify_replace_rtx (XEXP (note
, 0),
4870 /* The result of apply_change_group can be ignored; see
4873 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 1);
4874 apply_change_group ();
4878 /* If we previously found constant pool entries for
4879 constants and this is a constant, try making a
4880 pool entry. Put it in src_folded unless we already have done
4881 this since that is where it likely came from. */
4883 else if (constant_pool_entries_cost
4884 && CONSTANT_P (trial
)
4886 || (!MEM_P (src_folded
)
4887 && ! src_folded_force_flag
))
4888 && GET_MODE_CLASS (mode
) != MODE_CC
4889 && mode
!= VOIDmode
)
4891 src_folded_force_flag
= 1;
4893 src_folded_cost
= constant_pool_entries_cost
;
4894 src_folded_regcost
= constant_pool_entries_regcost
;
4898 src
= SET_SRC (sets
[i
].rtl
);
4900 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
4901 However, there is an important exception: If both are registers
4902 that are not the head of their equivalence class, replace SET_SRC
4903 with the head of the class. If we do not do this, we will have
4904 both registers live over a portion of the basic block. This way,
4905 their lifetimes will likely abut instead of overlapping. */
4907 && REGNO_QTY_VALID_P (REGNO (dest
)))
4909 int dest_q
= REG_QTY (REGNO (dest
));
4910 struct qty_table_elem
*dest_ent
= &qty_table
[dest_q
];
4912 if (dest_ent
->mode
== GET_MODE (dest
)
4913 && dest_ent
->first_reg
!= REGNO (dest
)
4914 && REG_P (src
) && REGNO (src
) == REGNO (dest
)
4915 /* Don't do this if the original insn had a hard reg as
4916 SET_SRC or SET_DEST. */
4917 && (!REG_P (sets
[i
].src
)
4918 || REGNO (sets
[i
].src
) >= FIRST_PSEUDO_REGISTER
)
4919 && (!REG_P (dest
) || REGNO (dest
) >= FIRST_PSEUDO_REGISTER
))
4920 /* We can't call canon_reg here because it won't do anything if
4921 SRC is a hard register. */
4923 int src_q
= REG_QTY (REGNO (src
));
4924 struct qty_table_elem
*src_ent
= &qty_table
[src_q
];
4925 int first
= src_ent
->first_reg
;
4927 = (first
>= FIRST_PSEUDO_REGISTER
4928 ? regno_reg_rtx
[first
] : gen_rtx_REG (GET_MODE (src
), first
));
4930 /* We must use validate-change even for this, because this
4931 might be a special no-op instruction, suitable only to
4933 if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new_src
, 0))
4936 /* If we had a constant that is cheaper than what we are now
4937 setting SRC to, use that constant. We ignored it when we
4938 thought we could make this into a no-op. */
4939 if (src_const
&& COST (src_const
) < COST (src
)
4940 && validate_change (insn
, &SET_SRC (sets
[i
].rtl
),
4947 /* If we made a change, recompute SRC values. */
4948 if (src
!= sets
[i
].src
)
4952 hash_arg_in_memory
= 0;
4954 sets
[i
].src_hash
= HASH (src
, mode
);
4955 sets
[i
].src_volatile
= do_not_record
;
4956 sets
[i
].src_in_memory
= hash_arg_in_memory
;
4957 sets
[i
].src_elt
= lookup (src
, sets
[i
].src_hash
, mode
);
4960 /* If this is a single SET, we are setting a register, and we have an
4961 equivalent constant, we want to add a REG_NOTE. We don't want
4962 to write a REG_EQUAL note for a constant pseudo since verifying that
4963 that pseudo hasn't been eliminated is a pain. Such a note also
4964 won't help anything.
4966 Avoid a REG_EQUAL note for (CONST (MINUS (LABEL_REF) (LABEL_REF)))
4967 which can be created for a reference to a compile time computable
4968 entry in a jump table. */
4970 if (n_sets
== 1 && src_const
&& REG_P (dest
)
4971 && !REG_P (src_const
)
4972 && ! (GET_CODE (src_const
) == CONST
4973 && GET_CODE (XEXP (src_const
, 0)) == MINUS
4974 && GET_CODE (XEXP (XEXP (src_const
, 0), 0)) == LABEL_REF
4975 && GET_CODE (XEXP (XEXP (src_const
, 0), 1)) == LABEL_REF
))
4977 /* We only want a REG_EQUAL note if src_const != src. */
4978 if (! rtx_equal_p (src
, src_const
))
4980 /* Make sure that the rtx is not shared. */
4981 src_const
= copy_rtx (src_const
);
4983 /* Record the actual constant value in a REG_EQUAL note,
4984 making a new one if one does not already exist. */
4985 set_unique_reg_note (insn
, REG_EQUAL
, src_const
);
4989 /* Now deal with the destination. */
4992 /* Look within any ZERO_EXTRACT to the MEM or REG within it. */
4993 while (GET_CODE (dest
) == SUBREG
4994 || GET_CODE (dest
) == ZERO_EXTRACT
4995 || GET_CODE (dest
) == STRICT_LOW_PART
)
4996 dest
= XEXP (dest
, 0);
4998 sets
[i
].inner_dest
= dest
;
5002 #ifdef PUSH_ROUNDING
5003 /* Stack pushes invalidate the stack pointer. */
5004 rtx addr
= XEXP (dest
, 0);
5005 if (GET_RTX_CLASS (GET_CODE (addr
)) == RTX_AUTOINC
5006 && XEXP (addr
, 0) == stack_pointer_rtx
)
5007 invalidate (stack_pointer_rtx
, VOIDmode
);
5009 dest
= fold_rtx (dest
, insn
);
5012 /* Compute the hash code of the destination now,
5013 before the effects of this instruction are recorded,
5014 since the register values used in the address computation
5015 are those before this instruction. */
5016 sets
[i
].dest_hash
= HASH (dest
, mode
);
5018 /* Don't enter a bit-field in the hash table
5019 because the value in it after the store
5020 may not equal what was stored, due to truncation. */
5022 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
)
5024 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
5026 if (src_const
!= 0 && GET_CODE (src_const
) == CONST_INT
5027 && GET_CODE (width
) == CONST_INT
5028 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
5029 && ! (INTVAL (src_const
)
5030 & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
5031 /* Exception: if the value is constant,
5032 and it won't be truncated, record it. */
5036 /* This is chosen so that the destination will be invalidated
5037 but no new value will be recorded.
5038 We must invalidate because sometimes constant
5039 values can be recorded for bitfields. */
5040 sets
[i
].src_elt
= 0;
5041 sets
[i
].src_volatile
= 1;
5047 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
5049 else if (n_sets
== 1 && dest
== pc_rtx
&& src
== pc_rtx
)
5051 /* One less use of the label this insn used to jump to. */
5053 cse_jumps_altered
= 1;
5054 /* No more processing for this set. */
5058 /* If this SET is now setting PC to a label, we know it used to
5059 be a conditional or computed branch. */
5060 else if (dest
== pc_rtx
&& GET_CODE (src
) == LABEL_REF
5061 && !LABEL_REF_NONLOCAL_P (src
))
5063 /* Now emit a BARRIER after the unconditional jump. */
5064 if (NEXT_INSN (insn
) == 0
5065 || !BARRIER_P (NEXT_INSN (insn
)))
5066 emit_barrier_after (insn
);
5068 /* We reemit the jump in as many cases as possible just in
5069 case the form of an unconditional jump is significantly
5070 different than a computed jump or conditional jump.
5072 If this insn has multiple sets, then reemitting the
5073 jump is nontrivial. So instead we just force rerecognition
5074 and hope for the best. */
5079 new = emit_jump_insn_after (gen_jump (XEXP (src
, 0)), insn
);
5080 JUMP_LABEL (new) = XEXP (src
, 0);
5081 LABEL_NUSES (XEXP (src
, 0))++;
5083 /* Make sure to copy over REG_NON_LOCAL_GOTO. */
5084 note
= find_reg_note (insn
, REG_NON_LOCAL_GOTO
, 0);
5087 XEXP (note
, 1) = NULL_RTX
;
5088 REG_NOTES (new) = note
;
5094 /* Now emit a BARRIER after the unconditional jump. */
5095 if (NEXT_INSN (insn
) == 0
5096 || !BARRIER_P (NEXT_INSN (insn
)))
5097 emit_barrier_after (insn
);
5100 INSN_CODE (insn
) = -1;
5102 /* Do not bother deleting any unreachable code,
5103 let jump/flow do that. */
5105 cse_jumps_altered
= 1;
5109 /* If destination is volatile, invalidate it and then do no further
5110 processing for this assignment. */
5112 else if (do_not_record
)
5114 if (REG_P (dest
) || GET_CODE (dest
) == SUBREG
)
5115 invalidate (dest
, VOIDmode
);
5116 else if (MEM_P (dest
))
5117 invalidate (dest
, VOIDmode
);
5118 else if (GET_CODE (dest
) == STRICT_LOW_PART
5119 || GET_CODE (dest
) == ZERO_EXTRACT
)
5120 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
5124 if (sets
[i
].rtl
!= 0 && dest
!= SET_DEST (sets
[i
].rtl
))
5125 sets
[i
].dest_hash
= HASH (SET_DEST (sets
[i
].rtl
), mode
);
5128 /* If setting CC0, record what it was set to, or a constant, if it
5129 is equivalent to a constant. If it is being set to a floating-point
5130 value, make a COMPARE with the appropriate constant of 0. If we
5131 don't do this, later code can interpret this as a test against
5132 const0_rtx, which can cause problems if we try to put it into an
5133 insn as a floating-point operand. */
5134 if (dest
== cc0_rtx
)
5136 this_insn_cc0
= src_const
&& mode
!= VOIDmode
? src_const
: src
;
5137 this_insn_cc0_mode
= mode
;
5138 if (FLOAT_MODE_P (mode
))
5139 this_insn_cc0
= gen_rtx_COMPARE (VOIDmode
, this_insn_cc0
,
5145 /* Now enter all non-volatile source expressions in the hash table
5146 if they are not already present.
5147 Record their equivalence classes in src_elt.
5148 This way we can insert the corresponding destinations into
5149 the same classes even if the actual sources are no longer in them
5150 (having been invalidated). */
5152 if (src_eqv
&& src_eqv_elt
== 0 && sets
[0].rtl
!= 0 && ! src_eqv_volatile
5153 && ! rtx_equal_p (src_eqv
, SET_DEST (sets
[0].rtl
)))
5155 struct table_elt
*elt
;
5156 struct table_elt
*classp
= sets
[0].src_elt
;
5157 rtx dest
= SET_DEST (sets
[0].rtl
);
5158 enum machine_mode eqvmode
= GET_MODE (dest
);
5160 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5162 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
5165 if (insert_regs (src_eqv
, classp
, 0))
5167 rehash_using_reg (src_eqv
);
5168 src_eqv_hash
= HASH (src_eqv
, eqvmode
);
5170 elt
= insert (src_eqv
, classp
, src_eqv_hash
, eqvmode
);
5171 elt
->in_memory
= src_eqv_in_memory
;
5174 /* Check to see if src_eqv_elt is the same as a set source which
5175 does not yet have an elt, and if so set the elt of the set source
5177 for (i
= 0; i
< n_sets
; i
++)
5178 if (sets
[i
].rtl
&& sets
[i
].src_elt
== 0
5179 && rtx_equal_p (SET_SRC (sets
[i
].rtl
), src_eqv
))
5180 sets
[i
].src_elt
= src_eqv_elt
;
5183 for (i
= 0; i
< n_sets
; i
++)
5184 if (sets
[i
].rtl
&& ! sets
[i
].src_volatile
5185 && ! rtx_equal_p (SET_SRC (sets
[i
].rtl
), SET_DEST (sets
[i
].rtl
)))
5187 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == STRICT_LOW_PART
)
5189 /* REG_EQUAL in setting a STRICT_LOW_PART
5190 gives an equivalent for the entire destination register,
5191 not just for the subreg being stored in now.
5192 This is a more interesting equivalence, so we arrange later
5193 to treat the entire reg as the destination. */
5194 sets
[i
].src_elt
= src_eqv_elt
;
5195 sets
[i
].src_hash
= src_eqv_hash
;
5199 /* Insert source and constant equivalent into hash table, if not
5201 struct table_elt
*classp
= src_eqv_elt
;
5202 rtx src
= sets
[i
].src
;
5203 rtx dest
= SET_DEST (sets
[i
].rtl
);
5204 enum machine_mode mode
5205 = GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
5207 /* It's possible that we have a source value known to be
5208 constant but don't have a REG_EQUAL note on the insn.
5209 Lack of a note will mean src_eqv_elt will be NULL. This
5210 can happen where we've generated a SUBREG to access a
5211 CONST_INT that is already in a register in a wider mode.
5212 Ensure that the source expression is put in the proper
5215 classp
= sets
[i
].src_const_elt
;
5217 if (sets
[i
].src_elt
== 0)
5219 /* Don't put a hard register source into the table if this is
5220 the last insn of a libcall. In this case, we only need
5221 to put src_eqv_elt in src_elt. */
5222 if (! find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
5224 struct table_elt
*elt
;
5226 /* Note that these insert_regs calls cannot remove
5227 any of the src_elt's, because they would have failed to
5228 match if not still valid. */
5229 if (insert_regs (src
, classp
, 0))
5231 rehash_using_reg (src
);
5232 sets
[i
].src_hash
= HASH (src
, mode
);
5234 elt
= insert (src
, classp
, sets
[i
].src_hash
, mode
);
5235 elt
->in_memory
= sets
[i
].src_in_memory
;
5236 sets
[i
].src_elt
= classp
= elt
;
5239 sets
[i
].src_elt
= classp
;
5241 if (sets
[i
].src_const
&& sets
[i
].src_const_elt
== 0
5242 && src
!= sets
[i
].src_const
5243 && ! rtx_equal_p (sets
[i
].src_const
, src
))
5244 sets
[i
].src_elt
= insert (sets
[i
].src_const
, classp
,
5245 sets
[i
].src_const_hash
, mode
);
5248 else if (sets
[i
].src_elt
== 0)
5249 /* If we did not insert the source into the hash table (e.g., it was
5250 volatile), note the equivalence class for the REG_EQUAL value, if any,
5251 so that the destination goes into that class. */
5252 sets
[i
].src_elt
= src_eqv_elt
;
5254 /* Record destination addresses in the hash table. This allows us to
5255 check if they are invalidated by other sets. */
5256 for (i
= 0; i
< n_sets
; i
++)
5260 rtx x
= sets
[i
].inner_dest
;
5261 struct table_elt
*elt
;
5262 enum machine_mode mode
;
5268 mode
= GET_MODE (x
);
5269 hash
= HASH (x
, mode
);
5270 elt
= lookup (x
, hash
, mode
);
5273 if (insert_regs (x
, NULL
, 0))
5275 rehash_using_reg (x
);
5276 hash
= HASH (x
, mode
);
5278 elt
= insert (x
, NULL
, hash
, mode
);
5281 sets
[i
].dest_addr_elt
= elt
;
5284 sets
[i
].dest_addr_elt
= NULL
;
5288 invalidate_from_clobbers (x
);
5290 /* Some registers are invalidated by subroutine calls. Memory is
5291 invalidated by non-constant calls. */
5295 if (! CONST_OR_PURE_CALL_P (insn
))
5296 invalidate_memory ();
5297 invalidate_for_call ();
5300 /* Now invalidate everything set by this instruction.
5301 If a SUBREG or other funny destination is being set,
5302 sets[i].rtl is still nonzero, so here we invalidate the reg
5303 a part of which is being set. */
5305 for (i
= 0; i
< n_sets
; i
++)
5308 /* We can't use the inner dest, because the mode associated with
5309 a ZERO_EXTRACT is significant. */
5310 rtx dest
= SET_DEST (sets
[i
].rtl
);
5312 /* Needed for registers to remove the register from its
5313 previous quantity's chain.
5314 Needed for memory if this is a nonvarying address, unless
5315 we have just done an invalidate_memory that covers even those. */
5316 if (REG_P (dest
) || GET_CODE (dest
) == SUBREG
)
5317 invalidate (dest
, VOIDmode
);
5318 else if (MEM_P (dest
))
5319 invalidate (dest
, VOIDmode
);
5320 else if (GET_CODE (dest
) == STRICT_LOW_PART
5321 || GET_CODE (dest
) == ZERO_EXTRACT
)
5322 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
5325 /* A volatile ASM invalidates everything. */
5326 if (NONJUMP_INSN_P (insn
)
5327 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
5328 && MEM_VOLATILE_P (PATTERN (insn
)))
5329 flush_hash_table ();
5331 /* Make sure registers mentioned in destinations
5332 are safe for use in an expression to be inserted.
5333 This removes from the hash table
5334 any invalid entry that refers to one of these registers.
5336 We don't care about the return value from mention_regs because
5337 we are going to hash the SET_DEST values unconditionally. */
5339 for (i
= 0; i
< n_sets
; i
++)
5343 rtx x
= SET_DEST (sets
[i
].rtl
);
5349 /* We used to rely on all references to a register becoming
5350 inaccessible when a register changes to a new quantity,
5351 since that changes the hash code. However, that is not
5352 safe, since after HASH_SIZE new quantities we get a
5353 hash 'collision' of a register with its own invalid
5354 entries. And since SUBREGs have been changed not to
5355 change their hash code with the hash code of the register,
5356 it wouldn't work any longer at all. So we have to check
5357 for any invalid references lying around now.
5358 This code is similar to the REG case in mention_regs,
5359 but it knows that reg_tick has been incremented, and
5360 it leaves reg_in_table as -1 . */
5361 unsigned int regno
= REGNO (x
);
5362 unsigned int endregno
5363 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
5364 : hard_regno_nregs
[regno
][GET_MODE (x
)]);
5367 for (i
= regno
; i
< endregno
; i
++)
5369 if (REG_IN_TABLE (i
) >= 0)
5371 remove_invalid_refs (i
);
5372 REG_IN_TABLE (i
) = -1;
5379 /* We may have just removed some of the src_elt's from the hash table.
5380 So replace each one with the current head of the same class.
5381 Also check if destination addresses have been removed. */
5383 for (i
= 0; i
< n_sets
; i
++)
5386 if (sets
[i
].dest_addr_elt
5387 && sets
[i
].dest_addr_elt
->first_same_value
== 0)
5389 /* The elt was removed, which means this destination is not
5390 valid after this instruction. */
5391 sets
[i
].rtl
= NULL_RTX
;
5393 else if (sets
[i
].src_elt
&& sets
[i
].src_elt
->first_same_value
== 0)
5394 /* If elt was removed, find current head of same class,
5395 or 0 if nothing remains of that class. */
5397 struct table_elt
*elt
= sets
[i
].src_elt
;
5399 while (elt
&& elt
->prev_same_value
)
5400 elt
= elt
->prev_same_value
;
5402 while (elt
&& elt
->first_same_value
== 0)
5403 elt
= elt
->next_same_value
;
5404 sets
[i
].src_elt
= elt
? elt
->first_same_value
: 0;
5408 /* Now insert the destinations into their equivalence classes. */
5410 for (i
= 0; i
< n_sets
; i
++)
5413 rtx dest
= SET_DEST (sets
[i
].rtl
);
5414 struct table_elt
*elt
;
5416 /* Don't record value if we are not supposed to risk allocating
5417 floating-point values in registers that might be wider than
5419 if ((flag_float_store
5421 && FLOAT_MODE_P (GET_MODE (dest
)))
5422 /* Don't record BLKmode values, because we don't know the
5423 size of it, and can't be sure that other BLKmode values
5424 have the same or smaller size. */
5425 || GET_MODE (dest
) == BLKmode
5426 /* Don't record values of destinations set inside a libcall block
5427 since we might delete the libcall. Things should have been set
5428 up so we won't want to reuse such a value, but we play it safe
5431 /* If we didn't put a REG_EQUAL value or a source into the hash
5432 table, there is no point is recording DEST. */
5433 || sets
[i
].src_elt
== 0
5434 /* If DEST is a paradoxical SUBREG and SRC is a ZERO_EXTEND
5435 or SIGN_EXTEND, don't record DEST since it can cause
5436 some tracking to be wrong.
5438 ??? Think about this more later. */
5439 || (GET_CODE (dest
) == SUBREG
5440 && (GET_MODE_SIZE (GET_MODE (dest
))
5441 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
5442 && (GET_CODE (sets
[i
].src
) == SIGN_EXTEND
5443 || GET_CODE (sets
[i
].src
) == ZERO_EXTEND
)))
5446 /* STRICT_LOW_PART isn't part of the value BEING set,
5447 and neither is the SUBREG inside it.
5448 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
5449 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5450 dest
= SUBREG_REG (XEXP (dest
, 0));
5452 if (REG_P (dest
) || GET_CODE (dest
) == SUBREG
)
5453 /* Registers must also be inserted into chains for quantities. */
5454 if (insert_regs (dest
, sets
[i
].src_elt
, 1))
5456 /* If `insert_regs' changes something, the hash code must be
5458 rehash_using_reg (dest
);
5459 sets
[i
].dest_hash
= HASH (dest
, GET_MODE (dest
));
5462 elt
= insert (dest
, sets
[i
].src_elt
,
5463 sets
[i
].dest_hash
, GET_MODE (dest
));
5465 elt
->in_memory
= (MEM_P (sets
[i
].inner_dest
)
5466 && !MEM_READONLY_P (sets
[i
].inner_dest
));
5468 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
5469 narrower than M2, and both M1 and M2 are the same number of words,
5470 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
5471 make that equivalence as well.
5473 However, BAR may have equivalences for which gen_lowpart
5474 will produce a simpler value than gen_lowpart applied to
5475 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
5476 BAR's equivalences. If we don't get a simplified form, make
5477 the SUBREG. It will not be used in an equivalence, but will
5478 cause two similar assignments to be detected.
5480 Note the loop below will find SUBREG_REG (DEST) since we have
5481 already entered SRC and DEST of the SET in the table. */
5483 if (GET_CODE (dest
) == SUBREG
5484 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))) - 1)
5486 == (GET_MODE_SIZE (GET_MODE (dest
)) - 1) / UNITS_PER_WORD
)
5487 && (GET_MODE_SIZE (GET_MODE (dest
))
5488 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
5489 && sets
[i
].src_elt
!= 0)
5491 enum machine_mode new_mode
= GET_MODE (SUBREG_REG (dest
));
5492 struct table_elt
*elt
, *classp
= 0;
5494 for (elt
= sets
[i
].src_elt
->first_same_value
; elt
;
5495 elt
= elt
->next_same_value
)
5499 struct table_elt
*src_elt
;
5502 /* Ignore invalid entries. */
5503 if (!REG_P (elt
->exp
)
5504 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, false))
5507 /* We may have already been playing subreg games. If the
5508 mode is already correct for the destination, use it. */
5509 if (GET_MODE (elt
->exp
) == new_mode
)
5513 /* Calculate big endian correction for the SUBREG_BYTE.
5514 We have already checked that M1 (GET_MODE (dest))
5515 is not narrower than M2 (new_mode). */
5516 if (BYTES_BIG_ENDIAN
)
5517 byte
= (GET_MODE_SIZE (GET_MODE (dest
))
5518 - GET_MODE_SIZE (new_mode
));
5520 new_src
= simplify_gen_subreg (new_mode
, elt
->exp
,
5521 GET_MODE (dest
), byte
);
5524 /* The call to simplify_gen_subreg fails if the value
5525 is VOIDmode, yet we can't do any simplification, e.g.
5526 for EXPR_LISTs denoting function call results.
5527 It is invalid to construct a SUBREG with a VOIDmode
5528 SUBREG_REG, hence a zero new_src means we can't do
5529 this substitution. */
5533 src_hash
= HASH (new_src
, new_mode
);
5534 src_elt
= lookup (new_src
, src_hash
, new_mode
);
5536 /* Put the new source in the hash table is if isn't
5540 if (insert_regs (new_src
, classp
, 0))
5542 rehash_using_reg (new_src
);
5543 src_hash
= HASH (new_src
, new_mode
);
5545 src_elt
= insert (new_src
, classp
, src_hash
, new_mode
);
5546 src_elt
->in_memory
= elt
->in_memory
;
5548 else if (classp
&& classp
!= src_elt
->first_same_value
)
5549 /* Show that two things that we've seen before are
5550 actually the same. */
5551 merge_equiv_classes (src_elt
, classp
);
5553 classp
= src_elt
->first_same_value
;
5554 /* Ignore invalid entries. */
5556 && !REG_P (classp
->exp
)
5557 && ! exp_equiv_p (classp
->exp
, classp
->exp
, 1, false))
5558 classp
= classp
->next_same_value
;
5563 /* Special handling for (set REG0 REG1) where REG0 is the
5564 "cheapest", cheaper than REG1. After cse, REG1 will probably not
5565 be used in the sequel, so (if easily done) change this insn to
5566 (set REG1 REG0) and replace REG1 with REG0 in the previous insn
5567 that computed their value. Then REG1 will become a dead store
5568 and won't cloud the situation for later optimizations.
5570 Do not make this change if REG1 is a hard register, because it will
5571 then be used in the sequel and we may be changing a two-operand insn
5572 into a three-operand insn.
5574 Also do not do this if we are operating on a copy of INSN.
5576 Also don't do this if INSN ends a libcall; this would cause an unrelated
5577 register to be set in the middle of a libcall, and we then get bad code
5578 if the libcall is deleted. */
5580 if (n_sets
== 1 && sets
[0].rtl
&& REG_P (SET_DEST (sets
[0].rtl
))
5581 && NEXT_INSN (PREV_INSN (insn
)) == insn
5582 && REG_P (SET_SRC (sets
[0].rtl
))
5583 && REGNO (SET_SRC (sets
[0].rtl
)) >= FIRST_PSEUDO_REGISTER
5584 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets
[0].rtl
))))
5586 int src_q
= REG_QTY (REGNO (SET_SRC (sets
[0].rtl
)));
5587 struct qty_table_elem
*src_ent
= &qty_table
[src_q
];
5589 if ((src_ent
->first_reg
== REGNO (SET_DEST (sets
[0].rtl
)))
5590 && ! find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
5593 /* Scan for the previous nonnote insn, but stop at a basic
5597 prev
= PREV_INSN (prev
);
5599 while (prev
&& NOTE_P (prev
)
5600 && NOTE_LINE_NUMBER (prev
) != NOTE_INSN_BASIC_BLOCK
);
5602 /* Do not swap the registers around if the previous instruction
5603 attaches a REG_EQUIV note to REG1.
5605 ??? It's not entirely clear whether we can transfer a REG_EQUIV
5606 from the pseudo that originally shadowed an incoming argument
5607 to another register. Some uses of REG_EQUIV might rely on it
5608 being attached to REG1 rather than REG2.
5610 This section previously turned the REG_EQUIV into a REG_EQUAL
5611 note. We cannot do that because REG_EQUIV may provide an
5612 uninitialized stack slot when REG_PARM_STACK_SPACE is used. */
5614 if (prev
!= 0 && NONJUMP_INSN_P (prev
)
5615 && GET_CODE (PATTERN (prev
)) == SET
5616 && SET_DEST (PATTERN (prev
)) == SET_SRC (sets
[0].rtl
)
5617 && ! find_reg_note (prev
, REG_EQUIV
, NULL_RTX
))
5619 rtx dest
= SET_DEST (sets
[0].rtl
);
5620 rtx src
= SET_SRC (sets
[0].rtl
);
5623 validate_change (prev
, &SET_DEST (PATTERN (prev
)), dest
, 1);
5624 validate_change (insn
, &SET_DEST (sets
[0].rtl
), src
, 1);
5625 validate_change (insn
, &SET_SRC (sets
[0].rtl
), dest
, 1);
5626 apply_change_group ();
5628 /* If INSN has a REG_EQUAL note, and this note mentions
5629 REG0, then we must delete it, because the value in
5630 REG0 has changed. If the note's value is REG1, we must
5631 also delete it because that is now this insn's dest. */
5632 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
5634 && (reg_mentioned_p (dest
, XEXP (note
, 0))
5635 || rtx_equal_p (src
, XEXP (note
, 0))))
5636 remove_note (insn
, note
);
5641 /* If this is a conditional jump insn, record any known equivalences due to
5642 the condition being tested. */
5645 && n_sets
== 1 && GET_CODE (x
) == SET
5646 && GET_CODE (SET_SRC (x
)) == IF_THEN_ELSE
)
5647 record_jump_equiv (insn
, 0);
5650 /* If the previous insn set CC0 and this insn no longer references CC0,
5651 delete the previous insn. Here we use the fact that nothing expects CC0
5652 to be valid over an insn, which is true until the final pass. */
5653 if (prev_insn
&& NONJUMP_INSN_P (prev_insn
)
5654 && (tem
= single_set (prev_insn
)) != 0
5655 && SET_DEST (tem
) == cc0_rtx
5656 && ! reg_mentioned_p (cc0_rtx
, x
))
5657 delete_insn (prev_insn
);
5659 prev_insn_cc0
= this_insn_cc0
;
5660 prev_insn_cc0_mode
= this_insn_cc0_mode
;
5665 /* Remove from the hash table all expressions that reference memory. */
5668 invalidate_memory (void)
5671 struct table_elt
*p
, *next
;
5673 for (i
= 0; i
< HASH_SIZE
; i
++)
5674 for (p
= table
[i
]; p
; p
= next
)
5676 next
= p
->next_same_hash
;
5678 remove_from_table (p
, i
);
5682 /* If ADDR is an address that implicitly affects the stack pointer, return
5683 1 and update the register tables to show the effect. Else, return 0. */
5686 addr_affects_sp_p (rtx addr
)
5688 if (GET_RTX_CLASS (GET_CODE (addr
)) == RTX_AUTOINC
5689 && REG_P (XEXP (addr
, 0))
5690 && REGNO (XEXP (addr
, 0)) == STACK_POINTER_REGNUM
)
5692 if (REG_TICK (STACK_POINTER_REGNUM
) >= 0)
5694 REG_TICK (STACK_POINTER_REGNUM
)++;
5695 /* Is it possible to use a subreg of SP? */
5696 SUBREG_TICKED (STACK_POINTER_REGNUM
) = -1;
5699 /* This should be *very* rare. */
5700 if (TEST_HARD_REG_BIT (hard_regs_in_table
, STACK_POINTER_REGNUM
))
5701 invalidate (stack_pointer_rtx
, VOIDmode
);
5709 /* Perform invalidation on the basis of everything about an insn
5710 except for invalidating the actual places that are SET in it.
5711 This includes the places CLOBBERed, and anything that might
5712 alias with something that is SET or CLOBBERed.
5714 X is the pattern of the insn. */
5717 invalidate_from_clobbers (rtx x
)
5719 if (GET_CODE (x
) == CLOBBER
)
5721 rtx ref
= XEXP (x
, 0);
5724 if (REG_P (ref
) || GET_CODE (ref
) == SUBREG
5726 invalidate (ref
, VOIDmode
);
5727 else if (GET_CODE (ref
) == STRICT_LOW_PART
5728 || GET_CODE (ref
) == ZERO_EXTRACT
)
5729 invalidate (XEXP (ref
, 0), GET_MODE (ref
));
5732 else if (GET_CODE (x
) == PARALLEL
)
5735 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
5737 rtx y
= XVECEXP (x
, 0, i
);
5738 if (GET_CODE (y
) == CLOBBER
)
5740 rtx ref
= XEXP (y
, 0);
5741 if (REG_P (ref
) || GET_CODE (ref
) == SUBREG
5743 invalidate (ref
, VOIDmode
);
5744 else if (GET_CODE (ref
) == STRICT_LOW_PART
5745 || GET_CODE (ref
) == ZERO_EXTRACT
)
5746 invalidate (XEXP (ref
, 0), GET_MODE (ref
));
5752 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
5753 and replace any registers in them with either an equivalent constant
5754 or the canonical form of the register. If we are inside an address,
5755 only do this if the address remains valid.
5757 OBJECT is 0 except when within a MEM in which case it is the MEM.
5759 Return the replacement for X. */
5762 cse_process_notes (rtx x
, rtx object
)
5764 enum rtx_code code
= GET_CODE (x
);
5765 const char *fmt
= GET_RTX_FORMAT (code
);
5782 validate_change (x
, &XEXP (x
, 0),
5783 cse_process_notes (XEXP (x
, 0), x
), 0);
5788 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
5789 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), NULL_RTX
);
5791 XEXP (x
, 1) = cse_process_notes (XEXP (x
, 1), NULL_RTX
);
5798 rtx
new = cse_process_notes (XEXP (x
, 0), object
);
5799 /* We don't substitute VOIDmode constants into these rtx,
5800 since they would impede folding. */
5801 if (GET_MODE (new) != VOIDmode
)
5802 validate_change (object
, &XEXP (x
, 0), new, 0);
5807 i
= REG_QTY (REGNO (x
));
5809 /* Return a constant or a constant register. */
5810 if (REGNO_QTY_VALID_P (REGNO (x
)))
5812 struct qty_table_elem
*ent
= &qty_table
[i
];
5814 if (ent
->const_rtx
!= NULL_RTX
5815 && (CONSTANT_P (ent
->const_rtx
)
5816 || REG_P (ent
->const_rtx
)))
5818 rtx
new = gen_lowpart (GET_MODE (x
), ent
->const_rtx
);
5820 return copy_rtx (new);
5824 /* Otherwise, canonicalize this register. */
5825 return canon_reg (x
, NULL_RTX
);
5831 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
5833 validate_change (object
, &XEXP (x
, i
),
5834 cse_process_notes (XEXP (x
, i
), object
), 0);
5839 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
5840 since they are done elsewhere. This function is called via note_stores. */
5843 invalidate_skipped_set (rtx dest
, rtx set
, void *data ATTRIBUTE_UNUSED
)
5845 enum rtx_code code
= GET_CODE (dest
);
5848 && ! addr_affects_sp_p (dest
) /* If this is not a stack push ... */
5849 /* There are times when an address can appear varying and be a PLUS
5850 during this scan when it would be a fixed address were we to know
5851 the proper equivalences. So invalidate all memory if there is
5852 a BLKmode or nonscalar memory reference or a reference to a
5853 variable address. */
5854 && (MEM_IN_STRUCT_P (dest
) || GET_MODE (dest
) == BLKmode
5855 || cse_rtx_varies_p (XEXP (dest
, 0), 0)))
5857 invalidate_memory ();
5861 if (GET_CODE (set
) == CLOBBER
5866 if (code
== STRICT_LOW_PART
|| code
== ZERO_EXTRACT
)
5867 invalidate (XEXP (dest
, 0), GET_MODE (dest
));
5868 else if (code
== REG
|| code
== SUBREG
|| code
== MEM
)
5869 invalidate (dest
, VOIDmode
);
5872 /* Invalidate all insns from START up to the end of the function or the
5873 next label. This called when we wish to CSE around a block that is
5874 conditionally executed. */
5877 invalidate_skipped_block (rtx start
)
5881 for (insn
= start
; insn
&& !LABEL_P (insn
);
5882 insn
= NEXT_INSN (insn
))
5884 if (! INSN_P (insn
))
5889 if (! CONST_OR_PURE_CALL_P (insn
))
5890 invalidate_memory ();
5891 invalidate_for_call ();
5894 invalidate_from_clobbers (PATTERN (insn
));
5895 note_stores (PATTERN (insn
), invalidate_skipped_set
, NULL
);
5899 /* Find the end of INSN's basic block and return its range,
5900 the total number of SETs in all the insns of the block, the last insn of the
5901 block, and the branch path.
5903 The branch path indicates which branches should be followed. If a nonzero
5904 path size is specified, the block should be rescanned and a different set
5905 of branches will be taken. The branch path is only used if
5906 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is nonzero.
5908 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
5909 used to describe the block. It is filled in with the information about
5910 the current block. The incoming structure's branch path, if any, is used
5911 to construct the output branch path. */
5914 cse_end_of_basic_block (rtx insn
, struct cse_basic_block_data
*data
,
5915 int follow_jumps
, int skip_blocks
)
5919 int low_cuid
= INSN_CUID (insn
), high_cuid
= INSN_CUID (insn
);
5920 rtx next
= INSN_P (insn
) ? insn
: next_real_insn (insn
);
5921 int path_size
= data
->path_size
;
5925 /* Update the previous branch path, if any. If the last branch was
5926 previously PATH_TAKEN, mark it PATH_NOT_TAKEN.
5927 If it was previously PATH_NOT_TAKEN,
5928 shorten the path by one and look at the previous branch. We know that
5929 at least one branch must have been taken if PATH_SIZE is nonzero. */
5930 while (path_size
> 0)
5932 if (data
->path
[path_size
- 1].status
!= PATH_NOT_TAKEN
)
5934 data
->path
[path_size
- 1].status
= PATH_NOT_TAKEN
;
5941 /* If the first instruction is marked with QImode, that means we've
5942 already processed this block. Our caller will look at DATA->LAST
5943 to figure out where to go next. We want to return the next block
5944 in the instruction stream, not some branched-to block somewhere
5945 else. We accomplish this by pretending our called forbid us to
5946 follow jumps, or skip blocks. */
5947 if (GET_MODE (insn
) == QImode
)
5948 follow_jumps
= skip_blocks
= 0;
5950 /* Scan to end of this basic block. */
5951 while (p
&& !LABEL_P (p
))
5953 /* Don't cse over a call to setjmp; on some machines (eg VAX)
5954 the regs restored by the longjmp come from
5955 a later time than the setjmp. */
5956 if (PREV_INSN (p
) && CALL_P (PREV_INSN (p
))
5957 && find_reg_note (PREV_INSN (p
), REG_SETJMP
, NULL
))
5960 /* A PARALLEL can have lots of SETs in it,
5961 especially if it is really an ASM_OPERANDS. */
5962 if (INSN_P (p
) && GET_CODE (PATTERN (p
)) == PARALLEL
)
5963 nsets
+= XVECLEN (PATTERN (p
), 0);
5964 else if (!NOTE_P (p
))
5967 /* Ignore insns made by CSE; they cannot affect the boundaries of
5970 if (INSN_UID (p
) <= max_uid
&& INSN_CUID (p
) > high_cuid
)
5971 high_cuid
= INSN_CUID (p
);
5972 if (INSN_UID (p
) <= max_uid
&& INSN_CUID (p
) < low_cuid
)
5973 low_cuid
= INSN_CUID (p
);
5975 /* See if this insn is in our branch path. If it is and we are to
5977 if (path_entry
< path_size
&& data
->path
[path_entry
].branch
== p
)
5979 if (data
->path
[path_entry
].status
!= PATH_NOT_TAKEN
)
5982 /* Point to next entry in path, if any. */
5986 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
5987 was specified, we haven't reached our maximum path length, there are
5988 insns following the target of the jump, this is the only use of the
5989 jump label, and the target label is preceded by a BARRIER.
5991 Alternatively, we can follow the jump if it branches around a
5992 block of code and there are no other branches into the block.
5993 In this case invalidate_skipped_block will be called to invalidate any
5994 registers set in the block when following the jump. */
5996 else if ((follow_jumps
|| skip_blocks
) && path_size
< PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH
) - 1
5998 && GET_CODE (PATTERN (p
)) == SET
5999 && GET_CODE (SET_SRC (PATTERN (p
))) == IF_THEN_ELSE
6000 && JUMP_LABEL (p
) != 0
6001 && LABEL_NUSES (JUMP_LABEL (p
)) == 1
6002 && NEXT_INSN (JUMP_LABEL (p
)) != 0)
6004 for (q
= PREV_INSN (JUMP_LABEL (p
)); q
; q
= PREV_INSN (q
))
6006 || (PREV_INSN (q
) && CALL_P (PREV_INSN (q
))
6007 && find_reg_note (PREV_INSN (q
), REG_SETJMP
, NULL
)))
6008 && (!LABEL_P (q
) || LABEL_NUSES (q
) != 0))
6011 /* If we ran into a BARRIER, this code is an extension of the
6012 basic block when the branch is taken. */
6013 if (follow_jumps
&& q
!= 0 && BARRIER_P (q
))
6015 /* Don't allow ourself to keep walking around an
6016 always-executed loop. */
6017 if (next_real_insn (q
) == next
)
6023 /* Similarly, don't put a branch in our path more than once. */
6024 for (i
= 0; i
< path_entry
; i
++)
6025 if (data
->path
[i
].branch
== p
)
6028 if (i
!= path_entry
)
6031 data
->path
[path_entry
].branch
= p
;
6032 data
->path
[path_entry
++].status
= PATH_TAKEN
;
6034 /* This branch now ends our path. It was possible that we
6035 didn't see this branch the last time around (when the
6036 insn in front of the target was a JUMP_INSN that was
6037 turned into a no-op). */
6038 path_size
= path_entry
;
6041 /* Mark block so we won't scan it again later. */
6042 PUT_MODE (NEXT_INSN (p
), QImode
);
6044 /* Detect a branch around a block of code. */
6045 else if (skip_blocks
&& q
!= 0 && !LABEL_P (q
))
6049 if (next_real_insn (q
) == next
)
6055 for (i
= 0; i
< path_entry
; i
++)
6056 if (data
->path
[i
].branch
== p
)
6059 if (i
!= path_entry
)
6062 /* This is no_labels_between_p (p, q) with an added check for
6063 reaching the end of a function (in case Q precedes P). */
6064 for (tmp
= NEXT_INSN (p
); tmp
&& tmp
!= q
; tmp
= NEXT_INSN (tmp
))
6070 data
->path
[path_entry
].branch
= p
;
6071 data
->path
[path_entry
++].status
= PATH_AROUND
;
6073 path_size
= path_entry
;
6076 /* Mark block so we won't scan it again later. */
6077 PUT_MODE (NEXT_INSN (p
), QImode
);
6084 data
->low_cuid
= low_cuid
;
6085 data
->high_cuid
= high_cuid
;
6086 data
->nsets
= nsets
;
6089 /* If all jumps in the path are not taken, set our path length to zero
6090 so a rescan won't be done. */
6091 for (i
= path_size
- 1; i
>= 0; i
--)
6092 if (data
->path
[i
].status
!= PATH_NOT_TAKEN
)
6096 data
->path_size
= 0;
6098 data
->path_size
= path_size
;
6100 /* End the current branch path. */
6101 data
->path
[path_size
].branch
= 0;
6104 /* Perform cse on the instructions of a function.
6105 F is the first instruction.
6106 NREGS is one plus the highest pseudo-reg number used in the instruction.
6108 Returns 1 if jump_optimize should be redone due to simplifications
6109 in conditional jump instructions. */
6112 cse_main (rtx f
, int nregs
)
6114 struct cse_basic_block_data val
;
6118 init_cse_reg_info (nregs
);
6120 val
.path
= XNEWVEC (struct branch_path
, PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH
));
6122 cse_jumps_altered
= 0;
6123 recorded_label_ref
= 0;
6124 constant_pool_entries_cost
= 0;
6125 constant_pool_entries_regcost
= 0;
6127 rtl_hooks
= cse_rtl_hooks
;
6130 init_alias_analysis ();
6132 reg_eqv_table
= XNEWVEC (struct reg_eqv_elem
, nregs
);
6134 /* Find the largest uid. */
6136 max_uid
= get_max_uid ();
6137 uid_cuid
= XCNEWVEC (int, max_uid
+ 1);
6139 /* Compute the mapping from uids to cuids.
6140 CUIDs are numbers assigned to insns, like uids,
6141 except that cuids increase monotonically through the code. */
6143 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
6144 INSN_CUID (insn
) = ++i
;
6146 /* Loop over basic blocks.
6147 Compute the maximum number of qty's needed for each basic block
6148 (which is 2 for each SET). */
6153 cse_end_of_basic_block (insn
, &val
, flag_cse_follow_jumps
,
6154 flag_cse_skip_blocks
);
6156 /* If this basic block was already processed or has no sets, skip it. */
6157 if (val
.nsets
== 0 || GET_MODE (insn
) == QImode
)
6159 PUT_MODE (insn
, VOIDmode
);
6160 insn
= (val
.last
? NEXT_INSN (val
.last
) : 0);
6165 cse_basic_block_start
= val
.low_cuid
;
6166 cse_basic_block_end
= val
.high_cuid
;
6167 max_qty
= val
.nsets
* 2;
6170 fprintf (dump_file
, ";; Processing block from %d to %d, %d sets.\n",
6171 INSN_UID (insn
), val
.last
? INSN_UID (val
.last
) : 0,
6174 /* Make MAX_QTY bigger to give us room to optimize
6175 past the end of this basic block, if that should prove useful. */
6179 /* If this basic block is being extended by following certain jumps,
6180 (see `cse_end_of_basic_block'), we reprocess the code from the start.
6181 Otherwise, we start after this basic block. */
6182 if (val
.path_size
> 0)
6183 cse_basic_block (insn
, val
.last
, val
.path
);
6186 int old_cse_jumps_altered
= cse_jumps_altered
;
6189 /* When cse changes a conditional jump to an unconditional
6190 jump, we want to reprocess the block, since it will give
6191 us a new branch path to investigate. */
6192 cse_jumps_altered
= 0;
6193 temp
= cse_basic_block (insn
, val
.last
, val
.path
);
6194 if (cse_jumps_altered
== 0
6195 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
6198 cse_jumps_altered
|= old_cse_jumps_altered
;
6210 end_alias_analysis ();
6212 free (reg_eqv_table
);
6214 rtl_hooks
= general_rtl_hooks
;
6216 return cse_jumps_altered
|| recorded_label_ref
;
6219 /* Process a single basic block. FROM and TO and the limits of the basic
6220 block. NEXT_BRANCH points to the branch path when following jumps or
6221 a null path when not following jumps. */
6224 cse_basic_block (rtx from
, rtx to
, struct branch_path
*next_branch
)
6228 rtx libcall_insn
= NULL_RTX
;
6230 int no_conflict
= 0;
6232 /* Allocate the space needed by qty_table. */
6233 qty_table
= XNEWVEC (struct qty_table_elem
, max_qty
);
6237 /* TO might be a label. If so, protect it from being deleted. */
6238 if (to
!= 0 && LABEL_P (to
))
6241 for (insn
= from
; insn
!= to
; insn
= NEXT_INSN (insn
))
6243 enum rtx_code code
= GET_CODE (insn
);
6245 /* If we have processed 1,000 insns, flush the hash table to
6246 avoid extreme quadratic behavior. We must not include NOTEs
6247 in the count since there may be more of them when generating
6248 debugging information. If we clear the table at different
6249 times, code generated with -g -O might be different than code
6250 generated with -O but not -g.
6252 ??? This is a real kludge and needs to be done some other way.
6254 if (code
!= NOTE
&& num_insns
++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS
))
6256 flush_hash_table ();
6260 /* See if this is a branch that is part of the path. If so, and it is
6261 to be taken, do so. */
6262 if (next_branch
->branch
== insn
)
6264 enum taken status
= next_branch
++->status
;
6265 if (status
!= PATH_NOT_TAKEN
)
6267 if (status
== PATH_TAKEN
)
6268 record_jump_equiv (insn
, 1);
6270 invalidate_skipped_block (NEXT_INSN (insn
));
6272 /* Set the last insn as the jump insn; it doesn't affect cc0.
6273 Then follow this branch. */
6278 insn
= JUMP_LABEL (insn
);
6283 if (GET_MODE (insn
) == QImode
)
6284 PUT_MODE (insn
, VOIDmode
);
6286 if (GET_RTX_CLASS (code
) == RTX_INSN
)
6290 /* Process notes first so we have all notes in canonical forms when
6291 looking for duplicate operations. */
6293 if (REG_NOTES (insn
))
6294 REG_NOTES (insn
) = cse_process_notes (REG_NOTES (insn
), NULL_RTX
);
6296 /* Track when we are inside in LIBCALL block. Inside such a block,
6297 we do not want to record destinations. The last insn of a
6298 LIBCALL block is not considered to be part of the block, since
6299 its destination is the result of the block and hence should be
6302 if (REG_NOTES (insn
) != 0)
6304 if ((p
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)))
6305 libcall_insn
= XEXP (p
, 0);
6306 else if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
6308 /* Keep libcall_insn for the last SET insn of a no-conflict
6309 block to prevent changing the destination. */
6315 else if (find_reg_note (insn
, REG_NO_CONFLICT
, NULL_RTX
))
6319 cse_insn (insn
, libcall_insn
);
6321 if (no_conflict
== -1)
6327 /* If we haven't already found an insn where we added a LABEL_REF,
6329 if (NONJUMP_INSN_P (insn
) && ! recorded_label_ref
6330 && for_each_rtx (&PATTERN (insn
), check_for_label_ref
,
6332 recorded_label_ref
= 1;
6335 /* If INSN is now an unconditional jump, skip to the end of our
6336 basic block by pretending that we just did the last insn in the
6337 basic block. If we are jumping to the end of our block, show
6338 that we can have one usage of TO. */
6340 if (any_uncondjump_p (insn
))
6348 if (JUMP_LABEL (insn
) == to
)
6351 /* Maybe TO was deleted because the jump is unconditional.
6352 If so, there is nothing left in this basic block. */
6353 /* ??? Perhaps it would be smarter to set TO
6354 to whatever follows this insn,
6355 and pretend the basic block had always ended here. */
6356 if (INSN_DELETED_P (to
))
6359 insn
= PREV_INSN (to
);
6362 /* See if it is ok to keep on going past the label
6363 which used to end our basic block. Remember that we incremented
6364 the count of that label, so we decrement it here. If we made
6365 a jump unconditional, TO_USAGE will be one; in that case, we don't
6366 want to count the use in that jump. */
6368 if (to
!= 0 && NEXT_INSN (insn
) == to
6369 && LABEL_P (to
) && --LABEL_NUSES (to
) == to_usage
)
6371 struct cse_basic_block_data val
;
6374 insn
= NEXT_INSN (to
);
6376 /* If TO was the last insn in the function, we are done. */
6383 /* If TO was preceded by a BARRIER we are done with this block
6384 because it has no continuation. */
6385 prev
= prev_nonnote_insn (to
);
6386 if (prev
&& BARRIER_P (prev
))
6392 /* Find the end of the following block. Note that we won't be
6393 following branches in this case. */
6396 val
.path
= XNEWVEC (struct branch_path
, PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH
));
6397 cse_end_of_basic_block (insn
, &val
, 0, 0);
6400 /* If the tables we allocated have enough space left
6401 to handle all the SETs in the next basic block,
6402 continue through it. Otherwise, return,
6403 and that block will be scanned individually. */
6404 if (val
.nsets
* 2 + next_qty
> max_qty
)
6407 cse_basic_block_start
= val
.low_cuid
;
6408 cse_basic_block_end
= val
.high_cuid
;
6411 /* Prevent TO from being deleted if it is a label. */
6412 if (to
!= 0 && LABEL_P (to
))
6415 /* Back up so we process the first insn in the extension. */
6416 insn
= PREV_INSN (insn
);
6420 gcc_assert (next_qty
<= max_qty
);
6424 return to
? NEXT_INSN (to
) : 0;
6427 /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
6428 there isn't a REG_LABEL note. Return one if so. DATA is the insn. */
6431 check_for_label_ref (rtx
*rtl
, void *data
)
6433 rtx insn
= (rtx
) data
;
6435 /* If this insn uses a LABEL_REF and there isn't a REG_LABEL note for it,
6436 we must rerun jump since it needs to place the note. If this is a
6437 LABEL_REF for a CODE_LABEL that isn't in the insn chain, don't do this
6438 since no REG_LABEL will be added. */
6439 return (GET_CODE (*rtl
) == LABEL_REF
6440 && ! LABEL_REF_NONLOCAL_P (*rtl
)
6441 && LABEL_P (XEXP (*rtl
, 0))
6442 && INSN_UID (XEXP (*rtl
, 0)) != 0
6443 && ! find_reg_note (insn
, REG_LABEL
, XEXP (*rtl
, 0)));
6446 /* Count the number of times registers are used (not set) in X.
6447 COUNTS is an array in which we accumulate the count, INCR is how much
6448 we count each register usage.
6450 Don't count a usage of DEST, which is the SET_DEST of a SET which
6451 contains X in its SET_SRC. This is because such a SET does not
6452 modify the liveness of DEST.
6453 DEST is set to pc_rtx for a trapping insn, which means that we must count
6454 uses of a SET_DEST regardless because the insn can't be deleted here. */
6457 count_reg_usage (rtx x
, int *counts
, rtx dest
, int incr
)
6467 switch (code
= GET_CODE (x
))
6471 counts
[REGNO (x
)] += incr
;
6485 /* If we are clobbering a MEM, mark any registers inside the address
6487 if (MEM_P (XEXP (x
, 0)))
6488 count_reg_usage (XEXP (XEXP (x
, 0), 0), counts
, NULL_RTX
, incr
);
6492 /* Unless we are setting a REG, count everything in SET_DEST. */
6493 if (!REG_P (SET_DEST (x
)))
6494 count_reg_usage (SET_DEST (x
), counts
, NULL_RTX
, incr
);
6495 count_reg_usage (SET_SRC (x
), counts
,
6496 dest
? dest
: SET_DEST (x
),
6503 /* We expect dest to be NULL_RTX here. If the insn may trap, mark
6504 this fact by setting DEST to pc_rtx. */
6505 if (flag_non_call_exceptions
&& may_trap_p (PATTERN (x
)))
6507 if (code
== CALL_INSN
)
6508 count_reg_usage (CALL_INSN_FUNCTION_USAGE (x
), counts
, dest
, incr
);
6509 count_reg_usage (PATTERN (x
), counts
, dest
, incr
);
6511 /* Things used in a REG_EQUAL note aren't dead since loop may try to
6514 note
= find_reg_equal_equiv_note (x
);
6517 rtx eqv
= XEXP (note
, 0);
6519 if (GET_CODE (eqv
) == EXPR_LIST
)
6520 /* This REG_EQUAL note describes the result of a function call.
6521 Process all the arguments. */
6524 count_reg_usage (XEXP (eqv
, 0), counts
, dest
, incr
);
6525 eqv
= XEXP (eqv
, 1);
6527 while (eqv
&& GET_CODE (eqv
) == EXPR_LIST
);
6529 count_reg_usage (eqv
, counts
, dest
, incr
);
6534 if (REG_NOTE_KIND (x
) == REG_EQUAL
6535 || (REG_NOTE_KIND (x
) != REG_NONNEG
&& GET_CODE (XEXP (x
,0)) == USE
)
6536 /* FUNCTION_USAGE expression lists may include (CLOBBER (mem /u)),
6537 involving registers in the address. */
6538 || GET_CODE (XEXP (x
, 0)) == CLOBBER
)
6539 count_reg_usage (XEXP (x
, 0), counts
, NULL_RTX
, incr
);
6541 count_reg_usage (XEXP (x
, 1), counts
, NULL_RTX
, incr
);
6545 /* If the asm is volatile, then this insn cannot be deleted,
6546 and so the inputs *must* be live. */
6547 if (MEM_VOLATILE_P (x
))
6549 /* Iterate over just the inputs, not the constraints as well. */
6550 for (i
= ASM_OPERANDS_INPUT_LENGTH (x
) - 1; i
>= 0; i
--)
6551 count_reg_usage (ASM_OPERANDS_INPUT (x
, i
), counts
, dest
, incr
);
6561 fmt
= GET_RTX_FORMAT (code
);
6562 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
6565 count_reg_usage (XEXP (x
, i
), counts
, dest
, incr
);
6566 else if (fmt
[i
] == 'E')
6567 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
6568 count_reg_usage (XVECEXP (x
, i
, j
), counts
, dest
, incr
);
6572 /* Return true if set is live. */
6574 set_live_p (rtx set
, rtx insn ATTRIBUTE_UNUSED
, /* Only used with HAVE_cc0. */
6581 if (set_noop_p (set
))
6585 else if (GET_CODE (SET_DEST (set
)) == CC0
6586 && !side_effects_p (SET_SRC (set
))
6587 && ((tem
= next_nonnote_insn (insn
)) == 0
6589 || !reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
6592 else if (!REG_P (SET_DEST (set
))
6593 || REGNO (SET_DEST (set
)) < FIRST_PSEUDO_REGISTER
6594 || counts
[REGNO (SET_DEST (set
))] != 0
6595 || side_effects_p (SET_SRC (set
)))
6600 /* Return true if insn is live. */
6603 insn_live_p (rtx insn
, int *counts
)
6606 if (flag_non_call_exceptions
&& may_trap_p (PATTERN (insn
)))
6608 else if (GET_CODE (PATTERN (insn
)) == SET
)
6609 return set_live_p (PATTERN (insn
), insn
, counts
);
6610 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
6612 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
6614 rtx elt
= XVECEXP (PATTERN (insn
), 0, i
);
6616 if (GET_CODE (elt
) == SET
)
6618 if (set_live_p (elt
, insn
, counts
))
6621 else if (GET_CODE (elt
) != CLOBBER
&& GET_CODE (elt
) != USE
)
6630 /* Return true if libcall is dead as a whole. */
6633 dead_libcall_p (rtx insn
, int *counts
)
6637 /* See if there's a REG_EQUAL note on this insn and try to
6638 replace the source with the REG_EQUAL expression.
6640 We assume that insns with REG_RETVALs can only be reg->reg
6641 copies at this point. */
6642 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
6646 set
= single_set (insn
);
6650 new = simplify_rtx (XEXP (note
, 0));
6652 new = XEXP (note
, 0);
6654 /* While changing insn, we must update the counts accordingly. */
6655 count_reg_usage (insn
, counts
, NULL_RTX
, -1);
6657 if (validate_change (insn
, &SET_SRC (set
), new, 0))
6659 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
6660 remove_note (insn
, find_reg_note (insn
, REG_RETVAL
, NULL_RTX
));
6661 remove_note (insn
, note
);
6665 if (CONSTANT_P (new))
6667 new = force_const_mem (GET_MODE (SET_DEST (set
)), new);
6668 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
6670 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
6671 remove_note (insn
, find_reg_note (insn
, REG_RETVAL
, NULL_RTX
));
6672 remove_note (insn
, note
);
6677 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
6681 /* Scan all the insns and delete any that are dead; i.e., they store a register
6682 that is never used or they copy a register to itself.
6684 This is used to remove insns made obviously dead by cse, loop or other
6685 optimizations. It improves the heuristics in loop since it won't try to
6686 move dead invariants out of loops or make givs for dead quantities. The
6687 remaining passes of the compilation are also sped up. */
6690 delete_trivially_dead_insns (rtx insns
, int nreg
)
6694 int in_libcall
= 0, dead_libcall
= 0;
6697 timevar_push (TV_DELETE_TRIVIALLY_DEAD
);
6698 /* First count the number of times each register is used. */
6699 counts
= XCNEWVEC (int, nreg
);
6700 for (insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
6702 count_reg_usage (insn
, counts
, NULL_RTX
, 1);
6704 /* Go from the last insn to the first and delete insns that only set unused
6705 registers or copy a register to itself. As we delete an insn, remove
6706 usage counts for registers it uses.
6708 The first jump optimization pass may leave a real insn as the last
6709 insn in the function. We must not skip that insn or we may end
6710 up deleting code that is not really dead. */
6711 for (insn
= get_last_insn (); insn
; insn
= prev
)
6715 prev
= PREV_INSN (insn
);
6719 /* Don't delete any insns that are part of a libcall block unless
6720 we can delete the whole libcall block.
6722 Flow or loop might get confused if we did that. Remember
6723 that we are scanning backwards. */
6724 if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
6728 dead_libcall
= dead_libcall_p (insn
, counts
);
6730 else if (in_libcall
)
6731 live_insn
= ! dead_libcall
;
6733 live_insn
= insn_live_p (insn
, counts
);
6735 /* If this is a dead insn, delete it and show registers in it aren't
6740 count_reg_usage (insn
, counts
, NULL_RTX
, -1);
6741 delete_insn_and_edges (insn
);
6745 if (in_libcall
&& find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))
6752 if (dump_file
&& ndead
)
6753 fprintf (dump_file
, "Deleted %i trivially dead insns\n",
6757 timevar_pop (TV_DELETE_TRIVIALLY_DEAD
);
6761 /* This function is called via for_each_rtx. The argument, NEWREG, is
6762 a condition code register with the desired mode. If we are looking
6763 at the same register in a different mode, replace it with
6767 cse_change_cc_mode (rtx
*loc
, void *data
)
6769 struct change_cc_mode_args
* args
= (struct change_cc_mode_args
*)data
;
6773 && REGNO (*loc
) == REGNO (args
->newreg
)
6774 && GET_MODE (*loc
) != GET_MODE (args
->newreg
))
6776 validate_change (args
->insn
, loc
, args
->newreg
, 1);
6783 /* Change the mode of any reference to the register REGNO (NEWREG) to
6784 GET_MODE (NEWREG) in INSN. */
6787 cse_change_cc_mode_insn (rtx insn
, rtx newreg
)
6789 struct change_cc_mode_args args
;
6796 args
.newreg
= newreg
;
6798 for_each_rtx (&PATTERN (insn
), cse_change_cc_mode
, &args
);
6799 for_each_rtx (®_NOTES (insn
), cse_change_cc_mode
, &args
);
6801 /* If the following assertion was triggered, there is most probably
6802 something wrong with the cc_modes_compatible back end function.
6803 CC modes only can be considered compatible if the insn - with the mode
6804 replaced by any of the compatible modes - can still be recognized. */
6805 success
= apply_change_group ();
6806 gcc_assert (success
);
6809 /* Change the mode of any reference to the register REGNO (NEWREG) to
6810 GET_MODE (NEWREG), starting at START. Stop before END. Stop at
6811 any instruction which modifies NEWREG. */
6814 cse_change_cc_mode_insns (rtx start
, rtx end
, rtx newreg
)
6818 for (insn
= start
; insn
!= end
; insn
= NEXT_INSN (insn
))
6820 if (! INSN_P (insn
))
6823 if (reg_set_p (newreg
, insn
))
6826 cse_change_cc_mode_insn (insn
, newreg
);
6830 /* BB is a basic block which finishes with CC_REG as a condition code
6831 register which is set to CC_SRC. Look through the successors of BB
6832 to find blocks which have a single predecessor (i.e., this one),
6833 and look through those blocks for an assignment to CC_REG which is
6834 equivalent to CC_SRC. CAN_CHANGE_MODE indicates whether we are
6835 permitted to change the mode of CC_SRC to a compatible mode. This
6836 returns VOIDmode if no equivalent assignments were found.
6837 Otherwise it returns the mode which CC_SRC should wind up with.
6839 The main complexity in this function is handling the mode issues.
6840 We may have more than one duplicate which we can eliminate, and we
6841 try to find a mode which will work for multiple duplicates. */
6843 static enum machine_mode
6844 cse_cc_succs (basic_block bb
, rtx cc_reg
, rtx cc_src
, bool can_change_mode
)
6847 enum machine_mode mode
;
6848 unsigned int insn_count
;
6851 enum machine_mode modes
[2];
6857 /* We expect to have two successors. Look at both before picking
6858 the final mode for the comparison. If we have more successors
6859 (i.e., some sort of table jump, although that seems unlikely),
6860 then we require all beyond the first two to use the same
6863 found_equiv
= false;
6864 mode
= GET_MODE (cc_src
);
6866 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6871 if (e
->flags
& EDGE_COMPLEX
)
6874 if (EDGE_COUNT (e
->dest
->preds
) != 1
6875 || e
->dest
== EXIT_BLOCK_PTR
)
6878 end
= NEXT_INSN (BB_END (e
->dest
));
6879 for (insn
= BB_HEAD (e
->dest
); insn
!= end
; insn
= NEXT_INSN (insn
))
6883 if (! INSN_P (insn
))
6886 /* If CC_SRC is modified, we have to stop looking for
6887 something which uses it. */
6888 if (modified_in_p (cc_src
, insn
))
6891 /* Check whether INSN sets CC_REG to CC_SRC. */
6892 set
= single_set (insn
);
6894 && REG_P (SET_DEST (set
))
6895 && REGNO (SET_DEST (set
)) == REGNO (cc_reg
))
6898 enum machine_mode set_mode
;
6899 enum machine_mode comp_mode
;
6902 set_mode
= GET_MODE (SET_SRC (set
));
6903 comp_mode
= set_mode
;
6904 if (rtx_equal_p (cc_src
, SET_SRC (set
)))
6906 else if (GET_CODE (cc_src
) == COMPARE
6907 && GET_CODE (SET_SRC (set
)) == COMPARE
6909 && rtx_equal_p (XEXP (cc_src
, 0),
6910 XEXP (SET_SRC (set
), 0))
6911 && rtx_equal_p (XEXP (cc_src
, 1),
6912 XEXP (SET_SRC (set
), 1)))
6915 comp_mode
= targetm
.cc_modes_compatible (mode
, set_mode
);
6916 if (comp_mode
!= VOIDmode
6917 && (can_change_mode
|| comp_mode
== mode
))
6924 if (insn_count
< ARRAY_SIZE (insns
))
6926 insns
[insn_count
] = insn
;
6927 modes
[insn_count
] = set_mode
;
6928 last_insns
[insn_count
] = end
;
6931 if (mode
!= comp_mode
)
6933 gcc_assert (can_change_mode
);
6936 /* The modified insn will be re-recognized later. */
6937 PUT_MODE (cc_src
, mode
);
6942 if (set_mode
!= mode
)
6944 /* We found a matching expression in the
6945 wrong mode, but we don't have room to
6946 store it in the array. Punt. This case
6950 /* INSN sets CC_REG to a value equal to CC_SRC
6951 with the right mode. We can simply delete
6956 /* We found an instruction to delete. Keep looking,
6957 in the hopes of finding a three-way jump. */
6961 /* We found an instruction which sets the condition
6962 code, so don't look any farther. */
6966 /* If INSN sets CC_REG in some other way, don't look any
6968 if (reg_set_p (cc_reg
, insn
))
6972 /* If we fell off the bottom of the block, we can keep looking
6973 through successors. We pass CAN_CHANGE_MODE as false because
6974 we aren't prepared to handle compatibility between the
6975 further blocks and this block. */
6978 enum machine_mode submode
;
6980 submode
= cse_cc_succs (e
->dest
, cc_reg
, cc_src
, false);
6981 if (submode
!= VOIDmode
)
6983 gcc_assert (submode
== mode
);
6985 can_change_mode
= false;
6993 /* Now INSN_COUNT is the number of instructions we found which set
6994 CC_REG to a value equivalent to CC_SRC. The instructions are in
6995 INSNS. The modes used by those instructions are in MODES. */
6998 for (i
= 0; i
< insn_count
; ++i
)
7000 if (modes
[i
] != mode
)
7002 /* We need to change the mode of CC_REG in INSNS[i] and
7003 subsequent instructions. */
7006 if (GET_MODE (cc_reg
) == mode
)
7009 newreg
= gen_rtx_REG (mode
, REGNO (cc_reg
));
7011 cse_change_cc_mode_insns (NEXT_INSN (insns
[i
]), last_insns
[i
],
7015 delete_insn (insns
[i
]);
7021 /* If we have a fixed condition code register (or two), walk through
7022 the instructions and try to eliminate duplicate assignments. */
7025 cse_condition_code_reg (void)
7027 unsigned int cc_regno_1
;
7028 unsigned int cc_regno_2
;
7033 if (! targetm
.fixed_condition_code_regs (&cc_regno_1
, &cc_regno_2
))
7036 cc_reg_1
= gen_rtx_REG (CCmode
, cc_regno_1
);
7037 if (cc_regno_2
!= INVALID_REGNUM
)
7038 cc_reg_2
= gen_rtx_REG (CCmode
, cc_regno_2
);
7040 cc_reg_2
= NULL_RTX
;
7049 enum machine_mode mode
;
7050 enum machine_mode orig_mode
;
7052 /* Look for blocks which end with a conditional jump based on a
7053 condition code register. Then look for the instruction which
7054 sets the condition code register. Then look through the
7055 successor blocks for instructions which set the condition
7056 code register to the same value. There are other possible
7057 uses of the condition code register, but these are by far the
7058 most common and the ones which we are most likely to be able
7061 last_insn
= BB_END (bb
);
7062 if (!JUMP_P (last_insn
))
7065 if (reg_referenced_p (cc_reg_1
, PATTERN (last_insn
)))
7067 else if (cc_reg_2
&& reg_referenced_p (cc_reg_2
, PATTERN (last_insn
)))
7072 cc_src_insn
= NULL_RTX
;
7074 for (insn
= PREV_INSN (last_insn
);
7075 insn
&& insn
!= PREV_INSN (BB_HEAD (bb
));
7076 insn
= PREV_INSN (insn
))
7080 if (! INSN_P (insn
))
7082 set
= single_set (insn
);
7084 && REG_P (SET_DEST (set
))
7085 && REGNO (SET_DEST (set
)) == REGNO (cc_reg
))
7088 cc_src
= SET_SRC (set
);
7091 else if (reg_set_p (cc_reg
, insn
))
7098 if (modified_between_p (cc_src
, cc_src_insn
, NEXT_INSN (last_insn
)))
7101 /* Now CC_REG is a condition code register used for a
7102 conditional jump at the end of the block, and CC_SRC, in
7103 CC_SRC_INSN, is the value to which that condition code
7104 register is set, and CC_SRC is still meaningful at the end of
7107 orig_mode
= GET_MODE (cc_src
);
7108 mode
= cse_cc_succs (bb
, cc_reg
, cc_src
, true);
7109 if (mode
!= VOIDmode
)
7111 gcc_assert (mode
== GET_MODE (cc_src
));
7112 if (mode
!= orig_mode
)
7114 rtx newreg
= gen_rtx_REG (mode
, REGNO (cc_reg
));
7116 cse_change_cc_mode_insn (cc_src_insn
, newreg
);
7118 /* Do the same in the following insns that use the
7119 current value of CC_REG within BB. */
7120 cse_change_cc_mode_insns (NEXT_INSN (cc_src_insn
),
7121 NEXT_INSN (last_insn
),
7129 /* Perform common subexpression elimination. Nonzero value from
7130 `cse_main' means that jumps were simplified and some code may now
7131 be unreachable, so do jump optimization again. */
7133 gate_handle_cse (void)
7135 return optimize
> 0;
7139 rest_of_handle_cse (void)
7144 dump_flow_info (dump_file
, dump_flags
);
7146 reg_scan (get_insns (), max_reg_num ());
7148 tem
= cse_main (get_insns (), max_reg_num ());
7150 rebuild_jump_labels (get_insns ());
7151 if (purge_all_dead_edges ())
7152 delete_unreachable_blocks ();
7154 delete_trivially_dead_insns (get_insns (), max_reg_num ());
7156 /* If we are not running more CSE passes, then we are no longer
7157 expecting CSE to be run. But always rerun it in a cheap mode. */
7158 cse_not_expected
= !flag_rerun_cse_after_loop
&& !flag_gcse
;
7161 delete_dead_jumptables ();
7163 if (tem
|| optimize
> 1)
7164 cleanup_cfg (CLEANUP_EXPENSIVE
);
7168 struct tree_opt_pass pass_cse
=
7171 gate_handle_cse
, /* gate */
7172 rest_of_handle_cse
, /* execute */
7175 0, /* static_pass_number */
7177 0, /* properties_required */
7178 0, /* properties_provided */
7179 0, /* properties_destroyed */
7180 0, /* todo_flags_start */
7182 TODO_ggc_collect
, /* todo_flags_finish */
7188 gate_handle_cse2 (void)
7190 return optimize
> 0 && flag_rerun_cse_after_loop
;
7193 /* Run second CSE pass after loop optimizations. */
7195 rest_of_handle_cse2 (void)
7200 dump_flow_info (dump_file
, dump_flags
);
7202 tem
= cse_main (get_insns (), max_reg_num ());
7204 /* Run a pass to eliminate duplicated assignments to condition code
7205 registers. We have to run this after bypass_jumps, because it
7206 makes it harder for that pass to determine whether a jump can be
7208 cse_condition_code_reg ();
7210 purge_all_dead_edges ();
7211 delete_trivially_dead_insns (get_insns (), max_reg_num ());
7215 timevar_push (TV_JUMP
);
7216 rebuild_jump_labels (get_insns ());
7217 delete_dead_jumptables ();
7218 cleanup_cfg (CLEANUP_EXPENSIVE
);
7219 timevar_pop (TV_JUMP
);
7221 reg_scan (get_insns (), max_reg_num ());
7222 cse_not_expected
= 1;
7227 struct tree_opt_pass pass_cse2
=
7230 gate_handle_cse2
, /* gate */
7231 rest_of_handle_cse2
, /* execute */
7234 0, /* static_pass_number */
7235 TV_CSE2
, /* tv_id */
7236 0, /* properties_required */
7237 0, /* properties_provided */
7238 0, /* properties_destroyed */
7239 0, /* todo_flags_start */
7241 TODO_ggc_collect
, /* todo_flags_finish */