1 /* Common subexpression elimination for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
24 #include "hard-reg-set.h"
27 #include "insn-config.h"
33 /* The basic idea of common subexpression elimination is to go
34 through the code, keeping a record of expressions that would
35 have the same value at the current scan point, and replacing
36 expressions encountered with the cheapest equivalent expression.
38 It is too complicated to keep track of the different possibilities
39 when control paths merge; so, at each label, we forget all that is
40 known and start fresh. This can be described as processing each
41 basic block separately. Note, however, that these are not quite
42 the same as the basic blocks found by a later pass and used for
43 data flow analysis and register packing. We do not need to start fresh
44 after a conditional jump instruction if there is no label there.
46 We use two data structures to record the equivalent expressions:
47 a hash table for most expressions, and several vectors together
48 with "quantity numbers" to record equivalent (pseudo) registers.
50 The use of the special data structure for registers is desirable
51 because it is faster. It is possible because registers references
52 contain a fairly small number, the register number, taken from
53 a contiguously allocated series, and two register references are
54 identical if they have the same number. General expressions
55 do not have any such thing, so the only way to retrieve the
56 information recorded on an expression other than a register
57 is to keep it in a hash table.
59 Registers and "quantity numbers":
61 At the start of each basic block, all of the (hardware and pseudo)
62 registers used in the function are given distinct quantity
63 numbers to indicate their contents. During scan, when the code
64 copies one register into another, we copy the quantity number.
65 When a register is loaded in any other way, we allocate a new
66 quantity number to describe the value generated by this operation.
67 `reg_qty' records what quantity a register is currently thought
70 All real quantity numbers are greater than or equal to `max_reg'.
71 If register N has not been assigned a quantity, reg_qty[N] will equal N.
73 Quantity numbers below `max_reg' do not exist and none of the `qty_...'
74 variables should be referenced with an index below `max_reg'.
76 We also maintain a bidirectional chain of registers for each
77 quantity number. `qty_first_reg', `qty_last_reg',
78 `reg_next_eqv' and `reg_prev_eqv' hold these chains.
80 The first register in a chain is the one whose lifespan is least local.
81 Among equals, it is the one that was seen first.
82 We replace any equivalent register with that one.
84 If two registers have the same quantity number, it must be true that
85 REG expressions with `qty_mode' must be in the hash table for both
86 registers and must be in the same class.
88 The converse is not true. Since hard registers may be referenced in
89 any mode, two REG expressions might be equivalent in the hash table
90 but not have the same quantity number if the quantity number of one
91 of the registers is not the same mode as those expressions.
93 Constants and quantity numbers
95 When a quantity has a known constant value, that value is stored
96 in the appropriate element of qty_const. This is in addition to
97 putting the constant in the hash table as is usual for non-regs.
99 Whether a reg or a constant is preferred is determined by the configuration
100 macro CONST_COSTS and will often depend on the constant value. In any
101 event, expressions containing constants can be simplified, by fold_rtx.
103 When a quantity has a known nearly constant value (such as an address
104 of a stack slot), that value is stored in the appropriate element
107 Integer constants don't have a machine mode. However, cse
108 determines the intended machine mode from the destination
109 of the instruction that moves the constant. The machine mode
110 is recorded in the hash table along with the actual RTL
111 constant expression so that different modes are kept separate.
115 To record known equivalences among expressions in general
116 we use a hash table called `table'. It has a fixed number of buckets
117 that contain chains of `struct table_elt' elements for expressions.
118 These chains connect the elements whose expressions have the same
121 Other chains through the same elements connect the elements which
122 currently have equivalent values.
124 Register references in an expression are canonicalized before hashing
125 the expression. This is done using `reg_qty' and `qty_first_reg'.
126 The hash code of a register reference is computed using the quantity
127 number, not the register number.
129 When the value of an expression changes, it is necessary to remove from the
130 hash table not just that expression but all expressions whose values
131 could be different as a result.
133 1. If the value changing is in memory, except in special cases
134 ANYTHING referring to memory could be changed. That is because
135 nobody knows where a pointer does not point.
136 The function `invalidate_memory' removes what is necessary.
138 The special cases are when the address is constant or is
139 a constant plus a fixed register such as the frame pointer
140 or a static chain pointer. When such addresses are stored in,
141 we can tell exactly which other such addresses must be invalidated
142 due to overlap. `invalidate' does this.
143 All expressions that refer to non-constant
144 memory addresses are also invalidated. `invalidate_memory' does this.
146 2. If the value changing is a register, all expressions
147 containing references to that register, and only those,
150 Because searching the entire hash table for expressions that contain
151 a register is very slow, we try to figure out when it isn't necessary.
152 Precisely, this is necessary only when expressions have been
153 entered in the hash table using this register, and then the value has
154 changed, and then another expression wants to be added to refer to
155 the register's new value. This sequence of circumstances is rare
156 within any one basic block.
158 The vectors `reg_tick' and `reg_in_table' are used to detect this case.
159 reg_tick[i] is incremented whenever a value is stored in register i.
160 reg_in_table[i] holds -1 if no references to register i have been
161 entered in the table; otherwise, it contains the value reg_tick[i] had
162 when the references were entered. If we want to enter a reference
163 and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
164 Until we want to enter a new entry, the mere fact that the two vectors
165 don't match makes the entries be ignored if anyone tries to match them.
167 Registers themselves are entered in the hash table as well as in
168 the equivalent-register chains. However, the vectors `reg_tick'
169 and `reg_in_table' do not apply to expressions which are simple
170 register references. These expressions are removed from the table
171 immediately when they become invalid, and this can be done even if
172 we do not immediately search for all the expressions that refer to
175 A CLOBBER rtx in an instruction invalidates its operand for further
176 reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
177 invalidates everything that resides in memory.
181 Constant expressions that differ only by an additive integer
182 are called related. When a constant expression is put in
183 the table, the related expression with no constant term
184 is also entered. These are made to point at each other
185 so that it is possible to find out if there exists any
186 register equivalent to an expression related to a given expression. */
188 /* One plus largest register number used in this function. */
192 /* Length of vectors indexed by quantity number.
193 We know in advance we will not need a quantity number this big. */
197 /* Next quantity number to be allocated.
198 This is 1 + the largest number needed so far. */
202 /* Indexed by quantity number, gives the first (or last) (pseudo) register
203 in the chain of registers that currently contain this quantity. */
205 static int *qty_first_reg
;
206 static int *qty_last_reg
;
208 /* Index by quantity number, gives the mode of the quantity. */
210 static enum machine_mode
*qty_mode
;
212 /* Indexed by quantity number, gives the rtx of the constant value of the
213 quantity, or zero if it does not have a known value.
214 A sum of the frame pointer (or arg pointer) plus a constant
215 can also be entered here. */
217 static rtx
*qty_const
;
219 /* Indexed by qty number, gives the insn that stored the constant value
220 recorded in `qty_const'. */
222 static rtx
*qty_const_insn
;
224 /* The next three variables are used to track when a comparison between a
225 quantity and some constant or register has been passed. In that case, we
226 know the results of the comparison in case we see it again. These variables
227 record a comparison that is known to be true. */
229 /* Indexed by qty number, gives the rtx code of a comparison with a known
230 result involving this quantity. If none, it is UNKNOWN. */
231 static enum rtx_code
*qty_comparison_code
;
233 /* Indexed by qty number, gives the constant being compared against in a
234 comparison of known result. If no such comparison, it is undefined.
235 If the comparison is not with a constant, it is zero. */
237 static rtx
*qty_comparison_const
;
239 /* Indexed by qty number, gives the quantity being compared against in a
240 comparison of known result. If no such comparison, if it undefined.
241 If the comparison is not with a register, it is -1. */
243 static int *qty_comparison_qty
;
246 /* For machines that have a CC0, we do not record its value in the hash
247 table since its use is guaranteed to be the insn immediately following
248 its definition and any other insn is presumed to invalidate it.
250 Instead, we store below the value last assigned to CC0. If it should
251 happen to be a constant, it is stored in preference to the actual
252 assigned value. In case it is a constant, we store the mode in which
253 the constant should be interpreted. */
255 static rtx prev_insn_cc0
;
256 static enum machine_mode prev_insn_cc0_mode
;
259 /* Previous actual insn. 0 if at first insn of basic block. */
261 static rtx prev_insn
;
263 /* Insn being scanned. */
265 static rtx this_insn
;
267 /* Index by (pseudo) register number, gives the quantity number
268 of the register's current contents. */
272 /* Index by (pseudo) register number, gives the number of the next (or
273 previous) (pseudo) register in the chain of registers sharing the same
276 Or -1 if this register is at the end of the chain.
278 If reg_qty[N] == N, reg_next_eqv[N] is undefined. */
280 static int *reg_next_eqv
;
281 static int *reg_prev_eqv
;
283 /* Index by (pseudo) register number, gives the number of times
284 that register has been altered in the current basic block. */
286 static int *reg_tick
;
288 /* Index by (pseudo) register number, gives the reg_tick value at which
289 rtx's containing this register are valid in the hash table.
290 If this does not equal the current reg_tick value, such expressions
291 existing in the hash table are invalid.
292 If this is -1, no expressions containing this register have been
293 entered in the table. */
295 static int *reg_in_table
;
297 /* A HARD_REG_SET containing all the hard registers for which there is
298 currently a REG expression in the hash table. Note the difference
299 from the above variables, which indicate if the REG is mentioned in some
300 expression in the table. */
302 static HARD_REG_SET hard_regs_in_table
;
304 /* A HARD_REG_SET containing all the hard registers that are invalidated
307 static HARD_REG_SET regs_invalidated_by_call
;
309 /* Two vectors of ints:
310 one containing max_reg -1's; the other max_reg + 500 (an approximation
311 for max_qty) elements where element i contains i.
312 These are used to initialize various other vectors fast. */
314 static int *all_minus_one
;
315 static int *consec_ints
;
317 /* CUID of insn that starts the basic block currently being cse-processed. */
319 static int cse_basic_block_start
;
321 /* CUID of insn that ends the basic block currently being cse-processed. */
323 static int cse_basic_block_end
;
325 /* Vector mapping INSN_UIDs to cuids.
326 The cuids are like uids but increase monotonically always.
327 We use them to see whether a reg is used outside a given basic block. */
329 static short *uid_cuid
;
331 /* Get the cuid of an insn. */
333 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
335 /* Nonzero if cse has altered conditional jump insns
336 in such a way that jump optimization should be redone. */
338 static int cse_jumps_altered
;
340 /* canon_hash stores 1 in do_not_record
341 if it notices a reference to CC0, PC, or some other volatile
344 static int do_not_record
;
346 /* canon_hash stores 1 in hash_arg_in_memory
347 if it notices a reference to memory within the expression being hashed. */
349 static int hash_arg_in_memory
;
351 /* canon_hash stores 1 in hash_arg_in_struct
352 if it notices a reference to memory that's part of a structure. */
354 static int hash_arg_in_struct
;
356 /* The hash table contains buckets which are chains of `struct table_elt's,
357 each recording one expression's information.
358 That expression is in the `exp' field.
360 Those elements with the same hash code are chained in both directions
361 through the `next_same_hash' and `prev_same_hash' fields.
363 Each set of expressions with equivalent values
364 are on a two-way chain through the `next_same_value'
365 and `prev_same_value' fields, and all point with
366 the `first_same_value' field at the first element in
367 that chain. The chain is in order of increasing cost.
368 Each element's cost value is in its `cost' field.
370 The `in_memory' field is nonzero for elements that
371 involve any reference to memory. These elements are removed
372 whenever a write is done to an unidentified location in memory.
373 To be safe, we assume that a memory address is unidentified unless
374 the address is either a symbol constant or a constant plus
375 the frame pointer or argument pointer.
377 The `in_struct' field is nonzero for elements that
378 involve any reference to memory inside a structure or array.
380 The `related_value' field is used to connect related expressions
381 (that differ by adding an integer).
382 The related expressions are chained in a circular fashion.
383 `related_value' is zero for expressions for which this
386 The `cost' field stores the cost of this element's expression.
388 The `is_const' flag is set if the element is a constant (including
391 The `flag' field is used as a temporary during some search routines.
393 The `mode' field is usually the same as GET_MODE (`exp'), but
394 if `exp' is a CONST_INT and has no machine mode then the `mode'
395 field is the mode it was being used as. Each constant is
396 recorded separately for each mode it is used with. */
402 struct table_elt
*next_same_hash
;
403 struct table_elt
*prev_same_hash
;
404 struct table_elt
*next_same_value
;
405 struct table_elt
*prev_same_value
;
406 struct table_elt
*first_same_value
;
407 struct table_elt
*related_value
;
409 enum machine_mode mode
;
418 /* We don't want a lot of buckets, because we rarely have very many
419 things stored in the hash table, and a lot of buckets slows
420 down a lot of loops that happen frequently. */
423 /* Compute hash code of X in mode M. Special-case case where X is a pseudo
424 register (hard registers may require `do_not_record' to be set). */
427 (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER \
428 ? ((((int) REG << 7) + reg_qty[REGNO (X)]) % NBUCKETS) \
429 : canon_hash (X, M) % NBUCKETS)
431 /* Determine whether register number N is considered a fixed register for CSE.
432 It is desirable to replace other regs with fixed regs, to reduce need for
434 A reg wins if it is either the frame pointer or designated as fixed,
435 but not if it is an overlapping register. */
436 #ifdef OVERLAPPING_REGNO_P
437 #define FIXED_REGNO_P(N) \
438 (((N) == FRAME_POINTER_REGNUM || fixed_regs[N]) \
439 && ! OVERLAPPING_REGNO_P ((N)))
441 #define FIXED_REGNO_P(N) \
442 ((N) == FRAME_POINTER_REGNUM || fixed_regs[N])
445 /* Compute cost of X, as stored in the `cost' field of a table_elt. Fixed
446 hard registers are the cheapest with a cost of 0. Next come pseudos
447 with a cost of one and other hard registers with a cost of 2. Aside
448 from these special cases, call `rtx_cost'. */
451 (GET_CODE (X) == REG \
452 ? (REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1 \
453 : (FIXED_REGNO_P (REGNO (X)) \
454 && REGNO_REG_CLASS (REGNO (X)) != NO_REGS) ? 0 \
456 : rtx_cost (X, SET) * 2)
458 /* Determine if the quantity number for register X represents a valid index
459 into the `qty_...' variables. */
461 #define REGNO_QTY_VALID_P(N) (reg_qty[N] != (N))
463 static struct table_elt
*table
[NBUCKETS
];
465 /* Chain of `struct table_elt's made so far for this function
466 but currently removed from the table. */
468 static struct table_elt
*free_element_chain
;
470 /* Number of `struct table_elt' structures made so far for this function. */
472 static int n_elements_made
;
474 /* Maximum value `n_elements_made' has had so far in this compilation
475 for functions previously processed. */
477 static int max_elements_made
;
479 /* Surviving equivalence class when two equivalence classes are merged
480 by recording the effects of a jump in the last insn. Zero if the
481 last insn was not a conditional jump. */
483 static struct table_elt
*last_jump_equiv_class
;
485 /* Set to the cost of a constant pool reference if one was found for a
486 symbolic constant. If this was found, it means we should try to
487 convert constants into constant pool entries if they don't fit in
490 static int constant_pool_entries_cost
;
492 /* Bits describing what kind of values in memory must be invalidated
493 for a particular instruction. If all three bits are zero,
494 no memory refs need to be invalidated. Each bit is more powerful
495 than the preceding ones, and if a bit is set then the preceding
498 Here is how the bits are set:
499 Pushing onto the stack invalidates only the stack pointer,
500 writing at a fixed address invalidates only variable addresses,
501 writing in a structure element at variable address
502 invalidates all but scalar variables,
503 and writing in anything else at variable address invalidates everything. */
507 int sp
: 1; /* Invalidate stack pointer. */
508 int var
: 1; /* Invalidate variable addresses. */
509 int nonscalar
: 1; /* Invalidate all but scalar variables. */
510 int all
: 1; /* Invalidate all memory refs. */
513 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
514 virtual regs here because the simplify_*_operation routines are called
515 by integrate.c, which is called before virtual register instantiation. */
517 #define FIXED_BASE_PLUS_P(X) \
518 ((X) == frame_pointer_rtx || (X) == arg_pointer_rtx \
519 || (X) == virtual_stack_vars_rtx \
520 || (X) == virtual_incoming_args_rtx \
521 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
522 && (XEXP (X, 0) == frame_pointer_rtx \
523 || XEXP (X, 0) == arg_pointer_rtx \
524 || XEXP (X, 0) == virtual_stack_vars_rtx \
525 || XEXP (X, 0) == virtual_incoming_args_rtx)))
527 /* Similar, but also allows reference to the stack pointer.
529 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
530 arg_pointer_rtx by itself is nonzero, because on at least one machine,
531 the i960, the arg pointer is zero when it is unused. */
533 #define NONZERO_BASE_PLUS_P(X) \
534 ((X) == frame_pointer_rtx \
535 || (X) == virtual_stack_vars_rtx \
536 || (X) == virtual_incoming_args_rtx \
537 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
538 && (XEXP (X, 0) == frame_pointer_rtx \
539 || XEXP (X, 0) == arg_pointer_rtx \
540 || XEXP (X, 0) == virtual_stack_vars_rtx \
541 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
542 || (X) == stack_pointer_rtx \
543 || (X) == virtual_stack_dynamic_rtx \
544 || (X) == virtual_outgoing_args_rtx \
545 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
546 && (XEXP (X, 0) == stack_pointer_rtx \
547 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
548 || XEXP (X, 0) == virtual_outgoing_args_rtx)))
550 static struct table_elt
*lookup ();
551 static void free_element ();
553 static int insert_regs ();
554 static void rehash_using_reg ();
555 static void remove_invalid_refs ();
556 static int exp_equiv_p ();
558 int refers_to_mem_p ();
559 static void invalidate_from_clobbers ();
560 static int safe_hash ();
561 static int canon_hash ();
562 static rtx
fold_rtx ();
563 static rtx
equiv_constant ();
564 static void record_jump_cond ();
565 static void note_mem_written ();
566 static int cse_rtx_addr_varies_p ();
567 static enum rtx_code
find_comparison_args ();
568 static void cse_insn ();
569 static void cse_set_around_loop ();
571 /* Return an estimate of the cost of computing rtx X.
572 One use is in cse, to decide which expression to keep in the hash table.
573 Another is in rtl generation, to pick the cheapest way to multiply.
574 Other uses like the latter are expected in the future. */
576 /* Return the right cost to give to an operation
577 to make the cost of the corresponding register-to-register instruction
578 N times that of a fast register-to-register instruction. */
580 #define COSTS_N_INSNS(N) ((N) * 4 - 2)
583 rtx_cost (x
, outer_code
)
585 enum rtx_code outer_code
;
588 register enum rtx_code code
;
595 /* Compute the default costs of certain things.
596 Note that RTX_COSTS can override the defaults. */
602 /* Count multiplication by 2**n as a shift,
603 because if we are considering it, we would output it as a shift. */
604 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
605 && exact_log2 (INTVAL (XEXP (x
, 1))) >= 0)
608 total
= COSTS_N_INSNS (5);
614 total
= COSTS_N_INSNS (7);
617 /* Used in loop.c and combine.c as a marker. */
621 /* We don't want these to be used in substitutions because
622 we have no way of validating the resulting insn. So assign
623 anything containing an ASM_OPERANDS a very high cost. */
635 /* If we can't tie these modes, make this expensive. The larger
636 the mode, the more expensive it is. */
637 if (! MODES_TIEABLE_P (GET_MODE (x
), GET_MODE (SUBREG_REG (x
))))
638 return COSTS_N_INSNS (2
639 + GET_MODE_SIZE (GET_MODE (x
)) / UNITS_PER_WORD
);
642 RTX_COSTS (x
, code
, outer_code
);
644 CONST_COSTS (x
, code
, outer_code
);
647 /* Sum the costs of the sub-rtx's, plus cost of this operation,
648 which is already in total. */
650 fmt
= GET_RTX_FORMAT (code
);
651 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
653 total
+= rtx_cost (XEXP (x
, i
), code
);
654 else if (fmt
[i
] == 'E')
655 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
656 total
+= rtx_cost (XVECEXP (x
, i
, j
), code
);
661 /* Clear the hash table and initialize each register with its own quantity,
662 for a new basic block. */
671 bzero (reg_tick
, max_reg
* sizeof (int));
673 bcopy (all_minus_one
, reg_in_table
, max_reg
* sizeof (int));
674 bcopy (consec_ints
, reg_qty
, max_reg
* sizeof (int));
675 CLEAR_HARD_REG_SET (hard_regs_in_table
);
677 /* The per-quantity values used to be initialized here, but it is
678 much faster to initialize each as it is made in `make_new_qty'. */
680 for (i
= 0; i
< NBUCKETS
; i
++)
682 register struct table_elt
*this, *next
;
683 for (this = table
[i
]; this; this = next
)
685 next
= this->next_same_hash
;
690 bzero (table
, sizeof table
);
699 /* Say that register REG contains a quantity not in any register before
700 and initialize that quantity. */
708 if (next_qty
>= max_qty
)
711 q
= reg_qty
[reg
] = next_qty
++;
712 qty_first_reg
[q
] = reg
;
713 qty_last_reg
[q
] = reg
;
714 qty_const
[q
] = qty_const_insn
[q
] = 0;
715 qty_comparison_code
[q
] = UNKNOWN
;
717 reg_next_eqv
[reg
] = reg_prev_eqv
[reg
] = -1;
720 /* Make reg NEW equivalent to reg OLD.
721 OLD is not changing; NEW is. */
724 make_regs_eqv (new, old
)
725 register int new, old
;
727 register int lastr
, firstr
;
728 register int q
= reg_qty
[old
];
730 /* Nothing should become eqv until it has a "non-invalid" qty number. */
731 if (! REGNO_QTY_VALID_P (old
))
735 firstr
= qty_first_reg
[q
];
736 lastr
= qty_last_reg
[q
];
738 /* Prefer fixed hard registers to anything. Prefer pseudo regs to other
739 hard regs. Among pseudos, if NEW will live longer than any other reg
740 of the same qty, and that is beyond the current basic block,
741 make it the new canonical replacement for this qty. */
742 if (! (firstr
< FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (firstr
))
743 /* Certain fixed registers might be of the class NO_REGS. This means
744 that not only can they not be allocated by the compiler, but
745 they cannot be used in substitutions or canonicalizations
747 && (new >= FIRST_PSEUDO_REGISTER
|| REGNO_REG_CLASS (new) != NO_REGS
)
748 && ((new < FIRST_PSEUDO_REGISTER
&& FIXED_REGNO_P (new))
749 || (new >= FIRST_PSEUDO_REGISTER
750 && (firstr
< FIRST_PSEUDO_REGISTER
751 || ((uid_cuid
[regno_last_uid
[new]] > cse_basic_block_end
752 || (uid_cuid
[regno_first_uid
[new]]
753 < cse_basic_block_start
))
754 && (uid_cuid
[regno_last_uid
[new]]
755 > uid_cuid
[regno_last_uid
[firstr
]]))))))
757 reg_prev_eqv
[firstr
] = new;
758 reg_next_eqv
[new] = firstr
;
759 reg_prev_eqv
[new] = -1;
760 qty_first_reg
[q
] = new;
764 /* If NEW is a hard reg (known to be non-fixed), insert at end.
765 Otherwise, insert before any non-fixed hard regs that are at the
766 end. Registers of class NO_REGS cannot be used as an
767 equivalent for anything. */
768 while (lastr
< FIRST_PSEUDO_REGISTER
&& reg_prev_eqv
[lastr
] >= 0
769 && (REGNO_REG_CLASS (lastr
) == NO_REGS
|| ! FIXED_REGNO_P (lastr
))
770 && new >= FIRST_PSEUDO_REGISTER
)
771 lastr
= reg_prev_eqv
[lastr
];
772 reg_next_eqv
[new] = reg_next_eqv
[lastr
];
773 if (reg_next_eqv
[lastr
] >= 0)
774 reg_prev_eqv
[reg_next_eqv
[lastr
]] = new;
776 qty_last_reg
[q
] = new;
777 reg_next_eqv
[lastr
] = new;
778 reg_prev_eqv
[new] = lastr
;
782 /* Remove REG from its equivalence class. */
785 delete_reg_equiv (reg
)
788 register int n
= reg_next_eqv
[reg
];
789 register int p
= reg_prev_eqv
[reg
];
790 register int q
= reg_qty
[reg
];
792 /* If invalid, do nothing. N and P above are undefined in that case. */
803 qty_first_reg
[q
] = n
;
808 /* Remove any invalid expressions from the hash table
809 that refer to any of the registers contained in expression X.
811 Make sure that newly inserted references to those registers
812 as subexpressions will be considered valid.
814 mention_regs is not called when a register itself
815 is being stored in the table.
817 Return 1 if we have done something that may have changed the hash code
824 register enum rtx_code code
;
827 register int changed
= 0;
835 register int regno
= REGNO (x
);
836 register int endregno
837 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
838 : HARD_REGNO_NREGS (regno
, GET_MODE (x
)));
841 for (i
= regno
; i
< endregno
; i
++)
843 if (reg_in_table
[i
] >= 0 && reg_in_table
[i
] != reg_tick
[i
])
844 remove_invalid_refs (i
);
846 reg_in_table
[i
] = reg_tick
[i
];
852 /* If X is a comparison or a COMPARE and either operand is a register
853 that does not have a quantity, give it one. This is so that a later
854 call to record_jump_equiv won't cause X to be assigned a different
855 hash code and not found in the table after that call.
857 It is not necessary to do this here, since rehash_using_reg can
858 fix up the table later, but doing this here eliminates the need to
859 call that expensive function in the most common case where the only
860 use of the register is in the comparison. */
862 if (code
== COMPARE
|| GET_RTX_CLASS (code
) == '<')
864 if (GET_CODE (XEXP (x
, 0)) == REG
865 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0))))
866 if (insert_regs (XEXP (x
, 0), 0, 0))
868 rehash_using_reg (XEXP (x
, 0));
872 if (GET_CODE (XEXP (x
, 1)) == REG
873 && ! REGNO_QTY_VALID_P (REGNO (XEXP (x
, 1))))
874 if (insert_regs (XEXP (x
, 1), 0, 0))
876 rehash_using_reg (XEXP (x
, 1));
881 fmt
= GET_RTX_FORMAT (code
);
882 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
884 changed
|= mention_regs (XEXP (x
, i
));
885 else if (fmt
[i
] == 'E')
886 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
887 changed
|= mention_regs (XVECEXP (x
, i
, j
));
892 /* Update the register quantities for inserting X into the hash table
893 with a value equivalent to CLASSP.
894 (If the class does not contain a REG, it is irrelevant.)
895 If MODIFIED is nonzero, X is a destination; it is being modified.
896 Note that delete_reg_equiv should be called on a register
897 before insert_regs is done on that register with MODIFIED != 0.
899 Nonzero value means that elements of reg_qty have changed
900 so X's hash code may be different. */
903 insert_regs (x
, classp
, modified
)
905 struct table_elt
*classp
;
908 if (GET_CODE (x
) == REG
)
910 register int regno
= REGNO (x
);
913 || ! (REGNO_QTY_VALID_P (regno
)
914 && qty_mode
[reg_qty
[regno
]] == GET_MODE (x
)))
917 for (classp
= classp
->first_same_value
;
919 classp
= classp
->next_same_value
)
920 if (GET_CODE (classp
->exp
) == REG
921 && GET_MODE (classp
->exp
) == GET_MODE (x
))
923 make_regs_eqv (regno
, REGNO (classp
->exp
));
927 make_new_qty (regno
);
928 qty_mode
[reg_qty
[regno
]] = GET_MODE (x
);
933 return mention_regs (x
);
936 /* Look in or update the hash table. */
938 /* Put the element ELT on the list of free elements. */
942 struct table_elt
*elt
;
944 elt
->next_same_hash
= free_element_chain
;
945 free_element_chain
= elt
;
948 /* Return an element that is free for use. */
950 static struct table_elt
*
953 struct table_elt
*elt
= free_element_chain
;
956 free_element_chain
= elt
->next_same_hash
;
960 return (struct table_elt
*) oballoc (sizeof (struct table_elt
));
963 /* Remove table element ELT from use in the table.
964 HASH is its hash code, made using the HASH macro.
965 It's an argument because often that is known in advance
966 and we save much time not recomputing it. */
969 remove_from_table (elt
, hash
)
970 register struct table_elt
*elt
;
976 /* Mark this element as removed. See cse_insn. */
977 elt
->first_same_value
= 0;
979 /* Remove the table element from its equivalence class. */
982 register struct table_elt
*prev
= elt
->prev_same_value
;
983 register struct table_elt
*next
= elt
->next_same_value
;
985 if (next
) next
->prev_same_value
= prev
;
988 prev
->next_same_value
= next
;
991 register struct table_elt
*newfirst
= next
;
994 next
->first_same_value
= newfirst
;
995 next
= next
->next_same_value
;
1000 /* Remove the table element from its hash bucket. */
1003 register struct table_elt
*prev
= elt
->prev_same_hash
;
1004 register struct table_elt
*next
= elt
->next_same_hash
;
1006 if (next
) next
->prev_same_hash
= prev
;
1009 prev
->next_same_hash
= next
;
1010 else if (table
[hash
] == elt
)
1014 /* This entry is not in the proper hash bucket. This can happen
1015 when two classes were merged by `merge_equiv_classes'. Search
1016 for the hash bucket that it heads. This happens only very
1017 rarely, so the cost is acceptable. */
1018 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1019 if (table
[hash
] == elt
)
1024 /* Remove the table element from its related-value circular chain. */
1026 if (elt
->related_value
!= 0 && elt
->related_value
!= elt
)
1028 register struct table_elt
*p
= elt
->related_value
;
1029 while (p
->related_value
!= elt
)
1030 p
= p
->related_value
;
1031 p
->related_value
= elt
->related_value
;
1032 if (p
->related_value
== p
)
1033 p
->related_value
= 0;
1039 /* Look up X in the hash table and return its table element,
1040 or 0 if X is not in the table.
1042 MODE is the machine-mode of X, or if X is an integer constant
1043 with VOIDmode then MODE is the mode with which X will be used.
1045 Here we are satisfied to find an expression whose tree structure
1048 static struct table_elt
*
1049 lookup (x
, hash
, mode
)
1052 enum machine_mode mode
;
1054 register struct table_elt
*p
;
1056 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1057 if (mode
== p
->mode
&& ((x
== p
->exp
&& GET_CODE (x
) == REG
)
1058 || exp_equiv_p (x
, p
->exp
, GET_CODE (x
) != REG
, 0)))
1064 /* Like `lookup' but don't care whether the table element uses invalid regs.
1065 Also ignore discrepancies in the machine mode of a register. */
1067 static struct table_elt
*
1068 lookup_for_remove (x
, hash
, mode
)
1071 enum machine_mode mode
;
1073 register struct table_elt
*p
;
1075 if (GET_CODE (x
) == REG
)
1077 int regno
= REGNO (x
);
1078 /* Don't check the machine mode when comparing registers;
1079 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1080 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1081 if (GET_CODE (p
->exp
) == REG
1082 && REGNO (p
->exp
) == regno
)
1087 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1088 if (mode
== p
->mode
&& (x
== p
->exp
|| exp_equiv_p (x
, p
->exp
, 0, 0)))
1095 /* Look for an expression equivalent to X and with code CODE.
1096 If one is found, return that expression. */
1099 lookup_as_function (x
, code
)
1103 register struct table_elt
*p
= lookup (x
, safe_hash (x
, VOIDmode
) % NBUCKETS
,
1108 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
1110 if (GET_CODE (p
->exp
) == code
1111 /* Make sure this is a valid entry in the table. */
1112 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
1119 /* Insert X in the hash table, assuming HASH is its hash code
1120 and CLASSP is an element of the class it should go in
1121 (or 0 if a new class should be made).
1122 It is inserted at the proper position to keep the class in
1123 the order cheapest first.
1125 MODE is the machine-mode of X, or if X is an integer constant
1126 with VOIDmode then MODE is the mode with which X will be used.
1128 For elements of equal cheapness, the most recent one
1129 goes in front, except that the first element in the list
1130 remains first unless a cheaper element is added. The order of
1131 pseudo-registers does not matter, as canon_reg will be called to
1132 find the cheapest when a register is retrieved from the table.
1134 The in_memory field in the hash table element is set to 0.
1135 The caller must set it nonzero if appropriate.
1137 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1138 and if insert_regs returns a nonzero value
1139 you must then recompute its hash code before calling here.
1141 If necessary, update table showing constant values of quantities. */
1143 #define CHEAPER(X,Y) ((X)->cost < (Y)->cost)
1145 static struct table_elt
*
1146 insert (x
, classp
, hash
, mode
)
1148 register struct table_elt
*classp
;
1150 enum machine_mode mode
;
1152 register struct table_elt
*elt
;
1154 /* If X is a register and we haven't made a quantity for it,
1155 something is wrong. */
1156 if (GET_CODE (x
) == REG
&& ! REGNO_QTY_VALID_P (REGNO (x
)))
1159 /* If X is a hard register, show it is being put in the table. */
1160 if (GET_CODE (x
) == REG
&& REGNO (x
) < FIRST_PSEUDO_REGISTER
)
1162 int regno
= REGNO (x
);
1163 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1166 for (i
= regno
; i
< endregno
; i
++)
1167 SET_HARD_REG_BIT (hard_regs_in_table
, i
);
1171 /* Put an element for X into the right hash bucket. */
1173 elt
= get_element ();
1175 elt
->cost
= COST (x
);
1176 elt
->next_same_value
= 0;
1177 elt
->prev_same_value
= 0;
1178 elt
->next_same_hash
= table
[hash
];
1179 elt
->prev_same_hash
= 0;
1180 elt
->related_value
= 0;
1183 elt
->is_const
= (CONSTANT_P (x
)
1184 /* GNU C++ takes advantage of this for `this'
1185 (and other const values). */
1186 || (RTX_UNCHANGING_P (x
)
1187 && GET_CODE (x
) == REG
1188 && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1189 || FIXED_BASE_PLUS_P (x
));
1192 table
[hash
]->prev_same_hash
= elt
;
1195 /* Put it into the proper value-class. */
1198 classp
= classp
->first_same_value
;
1199 if (CHEAPER (elt
, classp
))
1200 /* Insert at the head of the class */
1202 register struct table_elt
*p
;
1203 elt
->next_same_value
= classp
;
1204 classp
->prev_same_value
= elt
;
1205 elt
->first_same_value
= elt
;
1207 for (p
= classp
; p
; p
= p
->next_same_value
)
1208 p
->first_same_value
= elt
;
1212 /* Insert not at head of the class. */
1213 /* Put it after the last element cheaper than X. */
1214 register struct table_elt
*p
, *next
;
1215 for (p
= classp
; (next
= p
->next_same_value
) && CHEAPER (next
, elt
);
1217 /* Put it after P and before NEXT. */
1218 elt
->next_same_value
= next
;
1220 next
->prev_same_value
= elt
;
1221 elt
->prev_same_value
= p
;
1222 p
->next_same_value
= elt
;
1223 elt
->first_same_value
= classp
;
1227 elt
->first_same_value
= elt
;
1229 /* If this is a constant being set equivalent to a register or a register
1230 being set equivalent to a constant, note the constant equivalence.
1232 If this is a constant, it cannot be equivalent to a different constant,
1233 and a constant is the only thing that can be cheaper than a register. So
1234 we know the register is the head of the class (before the constant was
1237 If this is a register that is not already known equivalent to a
1238 constant, we must check the entire class.
1240 If this is a register that is already known equivalent to an insn,
1241 update `qty_const_insn' to show that `this_insn' is the latest
1242 insn making that quantity equivalent to the constant. */
1244 if (elt
->is_const
&& classp
&& GET_CODE (classp
->exp
) == REG
)
1246 qty_const
[reg_qty
[REGNO (classp
->exp
)]]
1247 = gen_lowpart_if_possible (qty_mode
[reg_qty
[REGNO (classp
->exp
)]], x
);
1248 qty_const_insn
[reg_qty
[REGNO (classp
->exp
)]] = this_insn
;
1251 else if (GET_CODE (x
) == REG
&& classp
&& ! qty_const
[reg_qty
[REGNO (x
)]])
1253 register struct table_elt
*p
;
1255 for (p
= classp
; p
!= 0; p
= p
->next_same_value
)
1259 qty_const
[reg_qty
[REGNO (x
)]]
1260 = gen_lowpart_if_possible (GET_MODE (x
), p
->exp
);
1261 qty_const_insn
[reg_qty
[REGNO (x
)]] = this_insn
;
1267 else if (GET_CODE (x
) == REG
&& qty_const
[reg_qty
[REGNO (x
)]]
1268 && GET_MODE (x
) == qty_mode
[reg_qty
[REGNO (x
)]])
1269 qty_const_insn
[reg_qty
[REGNO (x
)]] = this_insn
;
1271 /* If this is a constant with symbolic value,
1272 and it has a term with an explicit integer value,
1273 link it up with related expressions. */
1274 if (GET_CODE (x
) == CONST
)
1276 rtx subexp
= get_related_value (x
);
1278 struct table_elt
*subelt
, *subelt_prev
;
1282 /* Get the integer-free subexpression in the hash table. */
1283 subhash
= safe_hash (subexp
, mode
) % NBUCKETS
;
1284 subelt
= lookup (subexp
, subhash
, mode
);
1286 subelt
= insert (subexp
, 0, subhash
, mode
);
1287 /* Initialize SUBELT's circular chain if it has none. */
1288 if (subelt
->related_value
== 0)
1289 subelt
->related_value
= subelt
;
1290 /* Find the element in the circular chain that precedes SUBELT. */
1291 subelt_prev
= subelt
;
1292 while (subelt_prev
->related_value
!= subelt
)
1293 subelt_prev
= subelt_prev
->related_value
;
1294 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1295 This way the element that follows SUBELT is the oldest one. */
1296 elt
->related_value
= subelt_prev
->related_value
;
1297 subelt_prev
->related_value
= elt
;
1304 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1305 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1306 the two classes equivalent.
1308 CLASS1 will be the surviving class; CLASS2 should not be used after this
1311 Any invalid entries in CLASS2 will not be copied. */
1314 merge_equiv_classes (class1
, class2
)
1315 struct table_elt
*class1
, *class2
;
1317 struct table_elt
*elt
, *next
, *new;
1319 /* Ensure we start with the head of the classes. */
1320 class1
= class1
->first_same_value
;
1321 class2
= class2
->first_same_value
;
1323 /* If they were already equal, forget it. */
1324 if (class1
== class2
)
1327 for (elt
= class2
; elt
; elt
= next
)
1331 enum machine_mode mode
= elt
->mode
;
1333 next
= elt
->next_same_value
;
1335 /* Remove old entry, make a new one in CLASS1's class.
1336 Don't do this for invalid entries as we cannot find their
1337 hash code (it also isn't necessary). */
1338 if (GET_CODE (exp
) == REG
|| exp_equiv_p (exp
, exp
, 1, 0))
1340 hash_arg_in_memory
= 0;
1341 hash_arg_in_struct
= 0;
1342 hash
= HASH (exp
, mode
);
1344 if (GET_CODE (exp
) == REG
)
1345 delete_reg_equiv (REGNO (exp
));
1347 remove_from_table (elt
, hash
);
1349 if (insert_regs (exp
, class1
, 0))
1350 hash
= HASH (exp
, mode
);
1351 new = insert (exp
, class1
, hash
, mode
);
1352 new->in_memory
= hash_arg_in_memory
;
1353 new->in_struct
= hash_arg_in_struct
;
1358 /* Remove from the hash table, or mark as invalid,
1359 all expressions whose values could be altered by storing in X.
1360 X is a register, a subreg, or a memory reference with nonvarying address
1361 (because, when a memory reference with a varying address is stored in,
1362 all memory references are removed by invalidate_memory
1363 so specific invalidation is superfluous).
1365 A nonvarying address may be just a register or just
1366 a symbol reference, or it may be either of those plus
1367 a numeric offset. */
1374 register struct table_elt
*p
;
1376 register int start
, end
;
1378 /* If X is a register, dependencies on its contents
1379 are recorded through the qty number mechanism.
1380 Just change the qty number of the register,
1381 mark it as invalid for expressions that refer to it,
1382 and remove it itself. */
1384 if (GET_CODE (x
) == REG
)
1386 register int regno
= REGNO (x
);
1387 register int hash
= HASH (x
, GET_MODE (x
));
1389 /* Remove REGNO from any quantity list it might be on and indicate
1390 that it's value might have changed. If it is a pseudo, remove its
1391 entry from the hash table.
1393 For a hard register, we do the first two actions above for any
1394 additional hard registers corresponding to X. Then, if any of these
1395 registers are in the table, we must remove any REG entries that
1396 overlap these registers. */
1398 delete_reg_equiv (regno
);
1401 if (regno
>= FIRST_PSEUDO_REGISTER
)
1402 remove_from_table (lookup_for_remove (x
, hash
, GET_MODE (x
)), hash
);
1405 int in_table
= TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1406 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1407 int tregno
, tendregno
;
1408 register struct table_elt
*p
, *next
;
1410 CLEAR_HARD_REG_BIT (hard_regs_in_table
, regno
);
1412 for (i
= regno
+ 1; i
< endregno
; i
++)
1414 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, i
);
1415 CLEAR_HARD_REG_BIT (hard_regs_in_table
, i
);
1416 delete_reg_equiv (i
);
1421 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1422 for (p
= table
[hash
]; p
; p
= next
)
1424 next
= p
->next_same_hash
;
1426 if (GET_CODE (p
->exp
) != REG
1427 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1430 tregno
= REGNO (p
->exp
);
1432 = tregno
+ HARD_REGNO_NREGS (tregno
, GET_MODE (p
->exp
));
1433 if (tendregno
> regno
&& tregno
< endregno
)
1434 remove_from_table (p
, hash
);
1441 if (GET_CODE (x
) == SUBREG
)
1443 if (GET_CODE (SUBREG_REG (x
)) != REG
)
1445 invalidate (SUBREG_REG (x
));
1449 /* X is not a register; it must be a memory reference with
1450 a nonvarying address. Remove all hash table elements
1451 that refer to overlapping pieces of memory. */
1453 if (GET_CODE (x
) != MEM
)
1458 /* Registers with nonvarying addresses usually have constant equivalents;
1459 but the frame pointer register is also possible. */
1460 if (GET_CODE (base
) == REG
1461 && REGNO_QTY_VALID_P (REGNO (base
))
1462 && qty_mode
[reg_qty
[REGNO (base
)]] == GET_MODE (base
)
1463 && qty_const
[reg_qty
[REGNO (base
)]] != 0)
1464 base
= qty_const
[reg_qty
[REGNO (base
)]];
1465 else if (GET_CODE (base
) == PLUS
1466 && GET_CODE (XEXP (base
, 1)) == CONST_INT
1467 && GET_CODE (XEXP (base
, 0)) == REG
1468 && REGNO_QTY_VALID_P (REGNO (XEXP (base
, 0)))
1469 && (qty_mode
[reg_qty
[REGNO (XEXP (base
, 0))]]
1470 == GET_MODE (XEXP (base
, 0)))
1471 && qty_const
[reg_qty
[REGNO (XEXP (base
, 0))]])
1473 start
= INTVAL (XEXP (base
, 1));
1474 base
= qty_const
[reg_qty
[REGNO (XEXP (base
, 0))]];
1477 if (GET_CODE (base
) == CONST
)
1478 base
= XEXP (base
, 0);
1479 if (GET_CODE (base
) == PLUS
1480 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
1482 start
+= INTVAL (XEXP (base
, 1));
1483 base
= XEXP (base
, 0);
1486 end
= start
+ GET_MODE_SIZE (GET_MODE (x
));
1487 for (i
= 0; i
< NBUCKETS
; i
++)
1489 register struct table_elt
*next
;
1490 for (p
= table
[i
]; p
; p
= next
)
1492 next
= p
->next_same_hash
;
1493 if (refers_to_mem_p (p
->exp
, base
, start
, end
))
1494 remove_from_table (p
, i
);
1499 /* Remove all expressions that refer to register REGNO,
1500 since they are already invalid, and we are about to
1501 mark that register valid again and don't want the old
1502 expressions to reappear as valid. */
1505 remove_invalid_refs (regno
)
1509 register struct table_elt
*p
, *next
;
1511 for (i
= 0; i
< NBUCKETS
; i
++)
1512 for (p
= table
[i
]; p
; p
= next
)
1514 next
= p
->next_same_hash
;
1515 if (GET_CODE (p
->exp
) != REG
1516 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, 0))
1517 remove_from_table (p
, i
);
1521 /* Recompute the hash codes of any valid entries in the hash table that
1522 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1524 This is called when we make a jump equivalence. */
1527 rehash_using_reg (x
)
1531 struct table_elt
*p
, *next
;
1534 if (GET_CODE (x
) == SUBREG
)
1537 /* If X is not a register or if the register is known not to be in any
1538 valid entries in the table, we have no work to do. */
1540 if (GET_CODE (x
) != REG
1541 || reg_in_table
[REGNO (x
)] < 0
1542 || reg_in_table
[REGNO (x
)] != reg_tick
[REGNO (x
)])
1545 /* Scan all hash chains looking for valid entries that mention X.
1546 If we find one and it is in the wrong hash chain, move it. We can skip
1547 objects that are registers, since they are handled specially. */
1549 for (i
= 0; i
< NBUCKETS
; i
++)
1550 for (p
= table
[i
]; p
; p
= next
)
1552 next
= p
->next_same_hash
;
1553 if (GET_CODE (p
->exp
) != REG
&& reg_mentioned_p (x
, p
->exp
)
1554 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0)
1555 && i
!= (hash
= safe_hash (p
->exp
, p
->mode
) % NBUCKETS
))
1557 if (p
->next_same_hash
)
1558 p
->next_same_hash
->prev_same_hash
= p
->prev_same_hash
;
1560 if (p
->prev_same_hash
)
1561 p
->prev_same_hash
->next_same_hash
= p
->next_same_hash
;
1563 table
[i
] = p
->next_same_hash
;
1565 p
->next_same_hash
= table
[hash
];
1566 p
->prev_same_hash
= 0;
1568 table
[hash
]->prev_same_hash
= p
;
1574 /* Remove from the hash table all expressions that reference memory,
1575 or some of them as specified by *WRITES. */
1578 invalidate_memory (writes
)
1579 struct write_data
*writes
;
1582 register struct table_elt
*p
, *next
;
1583 int all
= writes
->all
;
1584 int nonscalar
= writes
->nonscalar
;
1586 for (i
= 0; i
< NBUCKETS
; i
++)
1587 for (p
= table
[i
]; p
; p
= next
)
1589 next
= p
->next_same_hash
;
1592 || (nonscalar
&& p
->in_struct
)
1593 || cse_rtx_addr_varies_p (p
->exp
)))
1594 remove_from_table (p
, i
);
1598 /* Remove from the hash table any expression that is a call-clobbered
1599 register. Also update their TICK values. */
1602 invalidate_for_call ()
1604 int regno
, endregno
;
1607 struct table_elt
*p
, *next
;
1610 /* Go through all the hard registers. For each that is clobbered in
1611 a CALL_INSN, remove the register from quantity chains and update
1612 reg_tick if defined. Also see if any of these registers is currently
1615 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1616 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
1618 delete_reg_equiv (regno
);
1619 if (reg_tick
[regno
] >= 0)
1622 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1625 /* In the case where we have no call-clobbered hard registers in the
1626 table, we are done. Otherwise, scan the table and remove any
1627 entry that overlaps a call-clobbered register. */
1630 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1631 for (p
= table
[hash
]; p
; p
= next
)
1633 next
= p
->next_same_hash
;
1635 if (GET_CODE (p
->exp
) != REG
1636 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1639 regno
= REGNO (p
->exp
);
1640 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (p
->exp
));
1642 for (i
= regno
; i
< endregno
; i
++)
1643 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1645 remove_from_table (p
, hash
);
1651 /* Given an expression X of type CONST,
1652 and ELT which is its table entry (or 0 if it
1653 is not in the hash table),
1654 return an alternate expression for X as a register plus integer.
1655 If none can be found, return 0. */
1658 use_related_value (x
, elt
)
1660 struct table_elt
*elt
;
1662 register struct table_elt
*relt
= 0;
1663 register struct table_elt
*p
, *q
;
1666 /* First, is there anything related known?
1667 If we have a table element, we can tell from that.
1668 Otherwise, must look it up. */
1670 if (elt
!= 0 && elt
->related_value
!= 0)
1672 else if (elt
== 0 && GET_CODE (x
) == CONST
)
1674 rtx subexp
= get_related_value (x
);
1676 relt
= lookup (subexp
,
1677 safe_hash (subexp
, GET_MODE (subexp
)) % NBUCKETS
,
1684 /* Search all related table entries for one that has an
1685 equivalent register. */
1690 /* This loop is strange in that it is executed in two different cases.
1691 The first is when X is already in the table. Then it is searching
1692 the RELATED_VALUE list of X's class (RELT). The second case is when
1693 X is not in the table. Then RELT points to a class for the related
1696 Ensure that, whatever case we are in, that we ignore classes that have
1697 the same value as X. */
1699 if (rtx_equal_p (x
, p
->exp
))
1702 for (q
= p
->first_same_value
; q
; q
= q
->next_same_value
)
1703 if (GET_CODE (q
->exp
) == REG
)
1709 p
= p
->related_value
;
1711 /* We went all the way around, so there is nothing to be found.
1712 Alternatively, perhaps RELT was in the table for some other reason
1713 and it has no related values recorded. */
1714 if (p
== relt
|| p
== 0)
1721 offset
= (get_integer_term (x
) - get_integer_term (p
->exp
));
1722 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
1723 return plus_constant (q
->exp
, offset
);
1726 /* Hash an rtx. We are careful to make sure the value is never negative.
1727 Equivalent registers hash identically.
1728 MODE is used in hashing for CONST_INTs only;
1729 otherwise the mode of X is used.
1731 Store 1 in do_not_record if any subexpression is volatile.
1733 Store 1 in hash_arg_in_memory if X contains a MEM rtx
1734 which does not have the RTX_UNCHANGING_P bit set.
1735 In this case, also store 1 in hash_arg_in_struct
1736 if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
1738 Note that cse_insn knows that the hash code of a MEM expression
1739 is just (int) MEM plus the hash code of the address. */
1742 canon_hash (x
, mode
)
1744 enum machine_mode mode
;
1747 register int hash
= 0;
1748 register enum rtx_code code
;
1751 /* repeat is used to turn tail-recursion into iteration. */
1756 code
= GET_CODE (x
);
1761 register int regno
= REGNO (x
);
1763 /* On some machines, we can't record any non-fixed hard register,
1764 because extending its life will cause reload problems. We
1765 consider ap, fp, and sp to be fixed for this purpose.
1766 On all machines, we can't record any global registers. */
1768 if (regno
< FIRST_PSEUDO_REGISTER
1769 && (global_regs
[regno
]
1770 #ifdef SMALL_REGISTER_CLASSES
1771 || (! fixed_regs
[regno
]
1772 && regno
!= FRAME_POINTER_REGNUM
1773 && regno
!= ARG_POINTER_REGNUM
1774 && regno
!= STACK_POINTER_REGNUM
)
1781 return hash
+ ((int) REG
<< 7) + reg_qty
[regno
];
1785 hash
+= ((int) mode
+ ((int) CONST_INT
<< 7)
1786 + INTVAL (x
) + (INTVAL (x
) >> HASHBITS
));
1787 return ((1 << HASHBITS
) - 1) & hash
;
1790 /* This is like the general case, except that it only counts
1791 the integers representing the constant. */
1792 hash
+= (int) code
+ (int) GET_MODE (x
);
1795 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
1797 int tem
= XINT (x
, i
);
1798 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1803 /* Assume there is only one rtx object for any given label. */
1805 /* Use `and' to ensure a positive number. */
1806 return (hash
+ ((int) LABEL_REF
<< 7)
1807 + ((int) XEXP (x
, 0) & ((1 << HASHBITS
) - 1)));
1810 return (hash
+ ((int) SYMBOL_REF
<< 7)
1811 + ((int) XEXP (x
, 0) & ((1 << HASHBITS
) - 1)));
1814 if (MEM_VOLATILE_P (x
))
1819 if (! RTX_UNCHANGING_P (x
))
1821 hash_arg_in_memory
= 1;
1822 if (MEM_IN_STRUCT_P (x
)) hash_arg_in_struct
= 1;
1824 /* Now that we have already found this special case,
1825 might as well speed it up as much as possible. */
1837 case UNSPEC_VOLATILE
:
1842 if (MEM_VOLATILE_P (x
))
1849 i
= GET_RTX_LENGTH (code
) - 1;
1850 hash
+= (int) code
+ (int) GET_MODE (x
);
1851 fmt
= GET_RTX_FORMAT (code
);
1856 rtx tem
= XEXP (x
, i
);
1859 /* If the operand is a REG that is equivalent to a constant, hash
1860 as if we were hashing the constant, since we will be comparing
1862 if (tem
!= 0 && GET_CODE (tem
) == REG
1863 && REGNO_QTY_VALID_P (REGNO (tem
))
1864 && qty_mode
[reg_qty
[REGNO (tem
)]] == GET_MODE (tem
)
1865 && (tem1
= qty_const
[reg_qty
[REGNO (tem
)]]) != 0
1866 && CONSTANT_P (tem1
))
1869 /* If we are about to do the last recursive call
1870 needed at this level, change it into iteration.
1871 This function is called enough to be worth it. */
1877 hash
+= canon_hash (tem
, 0);
1879 else if (fmt
[i
] == 'E')
1880 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1881 hash
+= canon_hash (XVECEXP (x
, i
, j
), 0);
1882 else if (fmt
[i
] == 's')
1884 register char *p
= XSTR (x
, i
);
1888 register int tem
= *p
++;
1889 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1892 else if (fmt
[i
] == 'i')
1894 register int tem
= XINT (x
, i
);
1895 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1903 /* Like canon_hash but with no side effects. */
1908 enum machine_mode mode
;
1910 int save_do_not_record
= do_not_record
;
1911 int save_hash_arg_in_memory
= hash_arg_in_memory
;
1912 int save_hash_arg_in_struct
= hash_arg_in_struct
;
1913 int hash
= canon_hash (x
, mode
);
1914 hash_arg_in_memory
= save_hash_arg_in_memory
;
1915 hash_arg_in_struct
= save_hash_arg_in_struct
;
1916 do_not_record
= save_do_not_record
;
1920 /* Return 1 iff X and Y would canonicalize into the same thing,
1921 without actually constructing the canonicalization of either one.
1922 If VALIDATE is nonzero,
1923 we assume X is an expression being processed from the rtl
1924 and Y was found in the hash table. We check register refs
1925 in Y for being marked as valid.
1927 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
1928 that is known to be in the register. Ordinarily, we don't allow them
1929 to match, because letting them match would cause unpredictable results
1930 in all the places that search a hash table chain for an equivalent
1931 for a given value. A possible equivalent that has different structure
1932 has its hash code computed from different data. Whether the hash code
1933 is the same as that of the the given value is pure luck. */
1936 exp_equiv_p (x
, y
, validate
, equal_values
)
1942 register enum rtx_code code
;
1945 /* Note: it is incorrect to assume an expression is equivalent to itself
1946 if VALIDATE is nonzero. */
1947 if (x
== y
&& !validate
)
1949 if (x
== 0 || y
== 0)
1952 code
= GET_CODE (x
);
1953 if (code
!= GET_CODE (y
))
1958 /* If X is a constant and Y is a register or vice versa, they may be
1959 equivalent. We only have to validate if Y is a register. */
1960 if (CONSTANT_P (x
) && GET_CODE (y
) == REG
1961 && REGNO_QTY_VALID_P (REGNO (y
))
1962 && GET_MODE (y
) == qty_mode
[reg_qty
[REGNO (y
)]]
1963 && rtx_equal_p (x
, qty_const
[reg_qty
[REGNO (y
)]])
1964 && (! validate
|| reg_in_table
[REGNO (y
)] == reg_tick
[REGNO (y
)]))
1967 if (CONSTANT_P (y
) && code
== REG
1968 && REGNO_QTY_VALID_P (REGNO (x
))
1969 && GET_MODE (x
) == qty_mode
[reg_qty
[REGNO (x
)]]
1970 && rtx_equal_p (y
, qty_const
[reg_qty
[REGNO (x
)]]))
1976 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1977 if (GET_MODE (x
) != GET_MODE (y
))
1987 return XINT (x
, 0) == XINT (y
, 0);
1991 return XEXP (x
, 0) == XEXP (y
, 0);
1995 int regno
= REGNO (y
);
1997 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
1998 : HARD_REGNO_NREGS (regno
, GET_MODE (y
)));
2001 /* If the quantities are not the same, the expressions are not
2002 equivalent. If there are and we are not to validate, they
2003 are equivalent. Otherwise, ensure all regs are up-to-date. */
2005 if (reg_qty
[REGNO (x
)] != reg_qty
[regno
])
2011 for (i
= regno
; i
< endregno
; i
++)
2012 if (reg_in_table
[i
] != reg_tick
[i
])
2018 /* For commutative operations, check both orders. */
2026 return ((exp_equiv_p (XEXP (x
, 0), XEXP (y
, 0), validate
, equal_values
)
2027 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 1),
2028 validate
, equal_values
))
2029 || (exp_equiv_p (XEXP (x
, 0), XEXP (y
, 1),
2030 validate
, equal_values
)
2031 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 0),
2032 validate
, equal_values
)));
2035 /* Compare the elements. If any pair of corresponding elements
2036 fail to match, return 0 for the whole things. */
2038 fmt
= GET_RTX_FORMAT (code
);
2039 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2043 if (! exp_equiv_p (XEXP (x
, i
), XEXP (y
, i
), validate
, equal_values
))
2046 else if (fmt
[i
] == 'E')
2049 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
2051 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2052 if (! exp_equiv_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
),
2053 validate
, equal_values
))
2056 else if (fmt
[i
] == 's')
2058 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
2061 else if (fmt
[i
] == 'i')
2063 if (XINT (x
, i
) != XINT (y
, i
))
2066 else if (fmt
[i
] != '0')
2072 /* Return 1 iff any subexpression of X matches Y.
2073 Here we do not require that X or Y be valid (for registers referred to)
2074 for being in the hash table. */
2081 register enum rtx_code code
;
2087 if (x
== 0 || y
== 0)
2090 code
= GET_CODE (x
);
2091 /* If X as a whole has the same code as Y, they may match.
2093 if (code
== GET_CODE (y
))
2095 if (exp_equiv_p (x
, y
, 0, 1))
2099 /* X does not match, so try its subexpressions. */
2101 fmt
= GET_RTX_FORMAT (code
);
2102 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2111 if (refers_to_p (XEXP (x
, i
), y
))
2114 else if (fmt
[i
] == 'E')
2117 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2118 if (refers_to_p (XVECEXP (x
, i
, j
), y
))
2125 /* Return 1 iff any subexpression of X refers to memory
2126 at an address of BASE plus some offset
2127 such that any of the bytes' offsets fall between START (inclusive)
2128 and END (exclusive).
2130 The value is undefined if X is a varying address.
2131 This function is not used in such cases.
2133 When used in the cse pass, `qty_const' is nonzero, and it is used
2134 to treat an address that is a register with a known constant value
2135 as if it were that constant value.
2136 In the loop pass, `qty_const' is zero, so this is not done. */
2139 refers_to_mem_p (x
, base
, start
, end
)
2144 register enum rtx_code code
;
2147 if (GET_CODE (base
) == CONST_INT
)
2149 start
+= INTVAL (base
);
2150 end
+= INTVAL (base
);
2158 code
= GET_CODE (x
);
2161 register rtx addr
= XEXP (x
, 0); /* Get the address. */
2165 if (GET_CODE (addr
) == REG
2166 /* qty_const is 0 when outside the cse pass;
2167 at such times, this info is not available. */
2169 && REGNO_QTY_VALID_P (REGNO (addr
))
2170 && GET_MODE (addr
) == qty_mode
[reg_qty
[REGNO (addr
)]]
2171 && qty_const
[reg_qty
[REGNO (addr
)]] != 0)
2172 addr
= qty_const
[reg_qty
[REGNO (addr
)]];
2173 else if (GET_CODE (addr
) == PLUS
2174 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
2175 && GET_CODE (XEXP (addr
, 0)) == REG
2177 && REGNO_QTY_VALID_P (REGNO (XEXP (addr
, 0)))
2178 && (GET_MODE (XEXP (addr
, 0))
2179 == qty_mode
[reg_qty
[REGNO (XEXP (addr
, 0))]])
2180 && qty_const
[reg_qty
[REGNO (XEXP (addr
, 0))]])
2182 i
= INTVAL (XEXP (addr
, 1));
2183 addr
= qty_const
[reg_qty
[REGNO (XEXP (addr
, 0))]];
2187 if (GET_CODE (addr
) == CONST
)
2188 addr
= XEXP (addr
, 0);
2190 /* If ADDR is BASE, or BASE plus an integer, put
2191 the integer in I. */
2192 if (GET_CODE (addr
) == PLUS
2193 && XEXP (addr
, 0) == base
2194 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
)
2195 i
+= INTVAL (XEXP (addr
, 1));
2196 else if (GET_CODE (addr
) == LO_SUM
)
2198 if (GET_CODE (base
) != LO_SUM
)
2200 /* The REG component of the LO_SUM is known by the
2201 const value in the XEXP part. */
2202 addr
= XEXP (addr
, 1);
2203 base
= XEXP (base
, 1);
2205 if (GET_CODE (base
) == CONST
)
2206 base
= XEXP (base
, 0);
2207 if (GET_CODE (base
) == PLUS
2208 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
2210 int tem
= INTVAL (XEXP (base
, 1));
2213 base
= XEXP (base
, 0);
2217 else if (GET_CODE (base
) == LO_SUM
)
2219 base
= XEXP (base
, 1);
2220 if (GET_CODE (base
) == CONST
)
2221 base
= XEXP (base
, 0);
2222 if (GET_CODE (base
) == PLUS
2223 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
2225 int tem
= INTVAL (XEXP (base
, 1));
2228 base
= XEXP (base
, 0);
2232 else if (GET_CODE (addr
) == CONST_INT
&& base
== const0_rtx
)
2234 else if (addr
!= base
)
2237 myend
= i
+ GET_MODE_SIZE (GET_MODE (x
));
2238 return myend
> start
&& i
< end
;
2241 /* X does not match, so try its subexpressions. */
2243 fmt
= GET_RTX_FORMAT (code
);
2244 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2253 if (refers_to_mem_p (XEXP (x
, i
), base
, start
, end
))
2256 else if (fmt
[i
] == 'E')
2259 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2260 if (refers_to_mem_p (XVECEXP (x
, i
, j
), base
, start
, end
))
2267 /* Nonzero if X refers to memory at a varying address;
2268 except that a register which has at the moment a known constant value
2269 isn't considered variable. */
2272 cse_rtx_addr_varies_p (x
)
2275 /* We need not check for X and the equivalence class being of the same
2276 mode because if X is equivalent to a constant in some mode, it
2277 doesn't vary in any mode. */
2279 if (GET_CODE (x
) == MEM
2280 && GET_CODE (XEXP (x
, 0)) == REG
2281 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0)))
2282 && GET_MODE (XEXP (x
, 0)) == qty_mode
[reg_qty
[REGNO (XEXP (x
, 0))]]
2283 && qty_const
[reg_qty
[REGNO (XEXP (x
, 0))]] != 0)
2286 if (GET_CODE (x
) == MEM
2287 && GET_CODE (XEXP (x
, 0)) == PLUS
2288 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
2289 && GET_CODE (XEXP (XEXP (x
, 0), 0)) == REG
2290 && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x
, 0), 0)))
2291 && (GET_MODE (XEXP (XEXP (x
, 0), 0))
2292 == qty_mode
[reg_qty
[REGNO (XEXP (XEXP (x
, 0), 0))]])
2293 && qty_const
[reg_qty
[REGNO (XEXP (XEXP (x
, 0), 0))]])
2296 return rtx_addr_varies_p (x
);
2299 /* Canonicalize an expression:
2300 replace each register reference inside it
2301 with the "oldest" equivalent register.
2303 If INSN is non-zero and we are replacing a pseudo with a hard register
2304 or vice versa, verify that INSN remains valid after we make our
2313 register enum rtx_code code
;
2319 code
= GET_CODE (x
);
2337 /* Never replace a hard reg, because hard regs can appear
2338 in more than one machine mode, and we must preserve the mode
2339 of each occurrence. Also, some hard regs appear in
2340 MEMs that are shared and mustn't be altered. Don't try to
2341 replace any reg that maps to a reg of class NO_REGS. */
2342 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
2343 || ! REGNO_QTY_VALID_P (REGNO (x
)))
2346 first
= qty_first_reg
[reg_qty
[REGNO (x
)]];
2347 return (first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
2348 : REGNO_REG_CLASS (first
) == NO_REGS
? x
2349 : gen_rtx (REG
, qty_mode
[reg_qty
[REGNO (x
)]], first
));
2353 fmt
= GET_RTX_FORMAT (code
);
2354 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2360 rtx
new = canon_reg (XEXP (x
, i
), insn
);
2362 /* If replacing pseudo with hard reg or vice versa, ensure the
2363 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2364 if (new && GET_CODE (new) == REG
&& GET_CODE (XEXP (x
, i
)) == REG
2365 && (((REGNO (new) < FIRST_PSEUDO_REGISTER
)
2366 != (REGNO (XEXP (x
, i
)) < FIRST_PSEUDO_REGISTER
))
2367 || (insn
!= 0 && insn_n_dups
[recog_memoized (insn
)] > 0)))
2368 validate_change (insn
, &XEXP (x
, i
), new, 0);
2372 else if (fmt
[i
] == 'E')
2373 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2374 XVECEXP (x
, i
, j
) = canon_reg (XVECEXP (x
, i
, j
), insn
);
2380 /* LOC is a location with INSN that is an operand address (the contents of
2381 a MEM). Find the best equivalent address to use that is valid for this
2384 On most CISC machines, complicated address modes are costly, and rtx_cost
2385 is a good approximation for that cost. However, most RISC machines have
2386 only a few (usually only one) memory reference formats. If an address is
2387 valid at all, it is often just as cheap as any other address. Hence, for
2388 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2389 costs of various addresses. For two addresses of equal cost, choose the one
2390 with the highest `rtx_cost' value as that has the potential of eliminating
2391 the most insns. For equal costs, we choose the first in the equivalence
2392 class. Note that we ignore the fact that pseudo registers are cheaper
2393 than hard registers here because we would also prefer the pseudo registers.
2397 find_best_addr (insn
, loc
)
2401 struct table_elt
*elt
, *p
;
2404 int found_better
= 1;
2405 int save_do_not_record
= do_not_record
;
2406 int save_hash_arg_in_memory
= hash_arg_in_memory
;
2407 int save_hash_arg_in_struct
= hash_arg_in_struct
;
2412 /* Do not try to replace constant addresses or addresses of local and
2413 argument slots. These MEM expressions are made only once and inserted
2414 in many instructions, as well as being used to control symbol table
2415 output. It is not safe to clobber them.
2417 There are some uncommon cases where the address is already in a register
2418 for some reason, but we cannot take advantage of that because we have
2419 no easy way to unshare the MEM. In addition, looking up all stack
2420 addresses is costly. */
2421 if ((GET_CODE (addr
) == PLUS
2422 && GET_CODE (XEXP (addr
, 0)) == REG
2423 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
2424 && (regno
= REGNO (XEXP (addr
, 0)),
2425 regno
== FRAME_POINTER_REGNUM
|| regno
== ARG_POINTER_REGNUM
))
2426 || (GET_CODE (addr
) == REG
2427 && (regno
= REGNO (addr
),
2428 regno
== FRAME_POINTER_REGNUM
|| regno
== ARG_POINTER_REGNUM
))
2429 || CONSTANT_ADDRESS_P (addr
))
2432 /* If this address is not simply a register, try to fold it. This will
2433 sometimes simplify the expression. Many simplifications
2434 will not be valid, but some, usually applying the associative rule, will
2435 be valid and produce better code. */
2436 if (GET_CODE (addr
) != REG
2437 && validate_change (insn
, loc
, fold_rtx (addr
, insn
), 0))
2440 /* If this address is not in the hash table, we can't do any better.
2441 Also, ignore if volatile. */
2443 hash_code
= HASH (addr
, Pmode
);
2444 addr_volatile
= do_not_record
;
2445 do_not_record
= save_do_not_record
;
2446 hash_arg_in_memory
= save_hash_arg_in_memory
;
2447 hash_arg_in_struct
= save_hash_arg_in_struct
;
2452 elt
= lookup (addr
, hash_code
, Pmode
);
2457 #ifndef ADDRESS_COST
2458 our_cost
= elt
->cost
;
2460 /* Find the lowest cost below ours that works. */
2461 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
2462 if (elt
->cost
< our_cost
2463 && (GET_CODE (elt
->exp
) == REG
|| exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
2464 && validate_change (insn
, loc
, canon_reg (copy_rtx (elt
->exp
), 0), 0))
2469 /* We need to find the best (under the criteria documented above) entry in
2470 the class that is valid. We use the `flag' field to indicate choices
2471 that were invalid and iterate until we can't find a better one that
2472 hasn't already been tried. */
2474 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2477 while (found_better
)
2479 int best_addr_cost
= ADDRESS_COST (*loc
);
2480 int best_rtx_cost
= (elt
->cost
+ 1) >> 1;
2481 struct table_elt
*best_elt
= elt
;
2484 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2486 && (GET_CODE (p
->exp
) == REG
|| exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
2487 && (ADDRESS_COST (p
->exp
) < best_addr_cost
2488 || (ADDRESS_COST (p
->exp
) == best_addr_cost
2489 && (p
->cost
+ 1) >> 1 > best_rtx_cost
)))
2492 best_addr_cost
= ADDRESS_COST (p
->exp
);
2493 best_rtx_cost
= (p
->cost
+ 1) >> 1;
2499 if (validate_change (insn
, loc
,
2500 canon_reg (copy_rtx (best_elt
->exp
), 0), 0))
2509 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2510 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2511 what values are being compared.
2513 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2514 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2515 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2516 compared to produce cc0.
2518 The return value is the comparison operator and is either the code of
2519 A or the code corresponding to the inverse of the comparison. */
2521 static enum rtx_code
2522 find_comparison_args (code
, parg1
, parg2
)
2528 arg1
= *parg1
, arg2
= *parg2
;
2530 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2532 while (arg2
== const0_rtx
)
2534 /* Set non-zero when we find something of interest. */
2536 int reverse_code
= 0;
2537 struct table_elt
*p
= 0;
2539 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2540 On machines with CC0, this is the only case that can occur, since
2541 fold_rtx will return the COMPARE or item being compared with zero
2544 if (GET_CODE (arg1
) == COMPARE
&& arg2
== const0_rtx
)
2547 /* If ARG1 is a comparison operator and CODE is testing for
2548 STORE_FLAG_VALUE, get the inner arguments. */
2550 else if (GET_RTX_CLASS (GET_CODE (arg1
)) == '<')
2552 if (code
== NE
|| (code
== LT
&& STORE_FLAG_VALUE
== -1))
2554 else if (code
== EQ
|| (code
== GE
&& STORE_FLAG_VALUE
== -1))
2555 x
= arg1
, reverse_code
= 1;
2558 /* ??? We could also check for
2560 (ne (and (eq (...) (const_int 1))) (const_int 0))
2562 and related forms, but let's wait until we see them occurring. */
2565 /* Look up ARG1 in the hash table and see if it has an equivalence
2566 that lets us see what is being compared. */
2567 p
= lookup (arg1
, safe_hash (arg1
, GET_MODE (arg1
)) % NBUCKETS
,
2569 if (p
) p
= p
->first_same_value
;
2571 for (; p
; p
= p
->next_same_value
)
2573 enum machine_mode inner_mode
= GET_MODE (p
->exp
);
2575 /* If the entry isn't valid, skip it. */
2576 if (! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
2579 if (GET_CODE (p
->exp
) == COMPARE
2580 /* Another possibility is that this machine has a compare insn
2581 that includes the comparison code. In that case, ARG1 would
2582 be equivalent to a comparison operation that would set ARG1 to
2583 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2584 ORIG_CODE is the actual comparison being done; if it is an EQ,
2585 we must reverse ORIG_CODE. On machine with a negative value
2586 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2589 && inner_mode
!= VOIDmode
2590 && GET_MODE_BITSIZE (inner_mode
) <= HOST_BITS_PER_INT
2591 && (STORE_FLAG_VALUE
2592 & (1 << (GET_MODE_BITSIZE (inner_mode
) - 1)))))
2593 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<'))
2598 else if ((code
== EQ
2600 && inner_mode
!= VOIDmode
2601 && GET_MODE_BITSIZE (inner_mode
) <= HOST_BITS_PER_INT
2602 && (STORE_FLAG_VALUE
2603 & (1 << (GET_MODE_BITSIZE (inner_mode
) - 1)))))
2604 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<')
2611 /* If this is fp + constant, the equivalent is a better operand since
2612 it may let us predict the value of the comparison. */
2613 else if (NONZERO_BASE_PLUS_P (p
->exp
))
2620 /* If we didn't find a useful equivalence for ARG1, we are done.
2621 Otherwise, set up for the next iteration. */
2625 arg1
= XEXP (x
, 0), arg2
= XEXP (x
, 1);
2626 if (GET_RTX_CLASS (GET_CODE (x
)) == '<')
2627 code
= GET_CODE (x
);
2630 code
= reverse_condition (code
);
2633 /* Return our results. */
2634 *parg1
= fold_rtx (arg1
, 0), *parg2
= fold_rtx (arg2
, 0);
2639 /* Try to simplify a unary operation CODE whose output mode is to be
2640 MODE with input operand OP whose mode was originally OP_MODE.
2641 Return zero if no simplification can be made. */
2644 simplify_unary_operation (code
, mode
, op
, op_mode
)
2646 enum machine_mode mode
;
2648 enum machine_mode op_mode
;
2650 register int width
= GET_MODE_BITSIZE (mode
);
2652 /* The order of these tests is critical so that, for example, we don't
2653 check the wrong mode (input vs. output) for a conversion operation,
2654 such as FIX. At some point, this should be simplified. */
2656 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
2657 if (code
== FLOAT
&& GET_CODE (op
) == CONST_INT
)
2661 #ifdef REAL_ARITHMETIC
2662 REAL_VALUE_FROM_INT (d
, INTVAL (op
), INTVAL (op
) < 0 ? ~0 : 0);
2664 d
= (double) INTVAL (op
);
2666 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2668 else if (code
== UNSIGNED_FLOAT
&& GET_CODE (op
) == CONST_INT
)
2672 #ifdef REAL_ARITHMETIC
2673 REAL_VALUE_FROM_INT (d
, INTVAL (op
), 0);
2675 d
= (double) (unsigned int) INTVAL (op
);
2677 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2680 else if (code
== FLOAT
&& GET_CODE (op
) == CONST_DOUBLE
2681 && GET_MODE (op
) == VOIDmode
)
2685 #ifdef REAL_ARITHMETIC
2686 REAL_VALUE_FROM_INT (d
, CONST_DOUBLE_LOW (op
), CONST_DOUBLE_HIGH (op
));
2688 if (CONST_DOUBLE_HIGH (op
) < 0)
2690 d
= (double) (~ CONST_DOUBLE_HIGH (op
));
2691 d
*= ((double) (1 << (HOST_BITS_PER_INT
/ 2))
2692 * (double) (1 << (HOST_BITS_PER_INT
/ 2)));
2693 d
+= (double) (unsigned) (~ CONST_DOUBLE_LOW (op
));
2698 d
= (double) CONST_DOUBLE_HIGH (op
);
2699 d
*= ((double) (1 << (HOST_BITS_PER_INT
/ 2))
2700 * (double) (1 << (HOST_BITS_PER_INT
/ 2)));
2701 d
+= (double) (unsigned) CONST_DOUBLE_LOW (op
);
2703 #endif /* REAL_ARITHMETIC */
2704 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2706 else if (code
== UNSIGNED_FLOAT
&& GET_CODE (op
) == CONST_DOUBLE
2707 && GET_MODE (op
) == VOIDmode
)
2711 #ifdef REAL_ARITHMETIC
2712 REAL_VALUE_FROM_UNSIGNED_INT (d
, CONST_DOUBLE_LOW (op
),
2713 CONST_DOUBLE_HIGH (op
));
2715 d
= (double) CONST_DOUBLE_HIGH (op
);
2716 d
*= ((double) (1 << (HOST_BITS_PER_INT
/ 2))
2717 * (double) (1 << (HOST_BITS_PER_INT
/ 2)));
2718 d
+= (double) (unsigned) CONST_DOUBLE_LOW (op
);
2719 #endif /* REAL_ARITHMETIC */
2720 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2724 else if (GET_CODE (op
) == CONST_INT
2725 && width
<= HOST_BITS_PER_INT
&& width
> 0)
2727 register int arg0
= INTVAL (op
);
2741 val
= (arg0
>= 0 ? arg0
: - arg0
);
2745 /* Don't use ffs here. Instead, get low order bit and then its
2746 number. If arg0 is zero, this will return 0, as desired. */
2747 arg0
&= GET_MODE_MASK (mode
);
2748 val
= exact_log2 (arg0
& (- arg0
)) + 1;
2756 if (op_mode
== VOIDmode
)
2758 if (GET_MODE_BITSIZE (op_mode
) == HOST_BITS_PER_INT
)
2760 else if (GET_MODE_BITSIZE (op_mode
) < HOST_BITS_PER_INT
)
2761 val
= arg0
& ~((-1) << GET_MODE_BITSIZE (op_mode
));
2767 if (op_mode
== VOIDmode
)
2769 if (GET_MODE_BITSIZE (op_mode
) == HOST_BITS_PER_INT
)
2771 else if (GET_MODE_BITSIZE (op_mode
) < HOST_BITS_PER_INT
)
2773 val
= arg0
& ~((-1) << GET_MODE_BITSIZE (op_mode
));
2774 if (val
& (1 << (GET_MODE_BITSIZE (op_mode
) - 1)))
2775 val
-= 1 << GET_MODE_BITSIZE (op_mode
);
2788 /* Clear the bits that don't belong in our mode,
2789 unless they and our sign bit are all one.
2790 So we get either a reasonable negative value or a reasonable
2791 unsigned value for this mode. */
2792 if (width
< HOST_BITS_PER_INT
2793 && ((val
& ((-1) << (width
- 1))) != ((-1) << (width
- 1))))
2794 val
&= (1 << width
) - 1;
2796 return gen_rtx (CONST_INT
, VOIDmode
, val
);
2799 /* We can do some operations on integer CONST_DOUBLEs. Also allow
2800 for a DImode operation on a CONST_INT. */
2801 else if (GET_MODE (op
) == VOIDmode
2802 && (GET_CODE (op
) == CONST_DOUBLE
|| GET_CODE (op
) == CONST_INT
))
2806 if (GET_CODE (op
) == CONST_DOUBLE
)
2807 l1
= CONST_DOUBLE_LOW (op
), h1
= CONST_DOUBLE_HIGH (op
);
2809 l1
= INTVAL (op
), h1
= l1
< 0 ? -1 : 0;
2819 neg_double (l1
, h1
, &lv
, &hv
);
2824 neg_double (l1
, h1
, &lv
, &hv
);
2832 lv
= HOST_BITS_PER_INT
+ exact_log2 (h1
& (-h1
)) + 1;
2834 lv
= exact_log2 (l1
& (-l1
)) + 1;
2838 if (GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_INT
)
2839 return gen_rtx (CONST_INT
, VOIDmode
, l1
& GET_MODE_MASK (mode
));
2851 return immed_double_const (lv
, hv
, mode
);
2854 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
2855 else if (GET_CODE (op
) == CONST_DOUBLE
2856 && GET_MODE_CLASS (mode
) == MODE_FLOAT
)
2862 if (setjmp (handler
))
2863 /* There used to be a warning here, but that is inadvisable.
2864 People may want to cause traps, and the natural way
2865 to do it should not get a warning. */
2868 set_float_handler (handler
);
2870 REAL_VALUE_FROM_CONST_DOUBLE (d
, op
);
2875 d
= REAL_VALUE_NEGATE (d
);
2879 if (REAL_VALUE_NEGATIVE (d
))
2880 d
= REAL_VALUE_NEGATE (d
);
2883 case FLOAT_TRUNCATE
:
2884 d
= (double) REAL_VALUE_TRUNCATE (mode
, d
);
2888 /* All this does is change the mode. */
2892 d
= (double) REAL_VALUE_FIX_TRUNCATE (d
);
2896 d
= (double) REAL_VALUE_UNSIGNED_FIX_TRUNCATE (d
);
2906 x
= immed_real_const_1 (d
, mode
);
2907 set_float_handler (0);
2910 else if (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE_CLASS (mode
) == MODE_INT
2911 && width
<= HOST_BITS_PER_INT
&& width
> 0)
2918 if (setjmp (handler
))
2921 set_float_handler (handler
);
2923 REAL_VALUE_FROM_CONST_DOUBLE (d
, op
);
2928 val
= REAL_VALUE_FIX (d
);
2932 val
= REAL_VALUE_UNSIGNED_FIX (d
);
2939 set_float_handler (0);
2941 /* Clear the bits that don't belong in our mode,
2942 unless they and our sign bit are all one.
2943 So we get either a reasonable negative value or a reasonable
2944 unsigned value for this mode. */
2945 if (width
< HOST_BITS_PER_INT
2946 && ((val
& ((-1) << (width
- 1))) != ((-1) << (width
- 1))))
2947 val
&= (1 << width
) - 1;
2949 return gen_rtx (CONST_INT
, VOIDmode
, val
);
2952 /* This was formerly used only for non-IEEE float.
2953 eggert@twinsun.com says it is safe for IEEE also. */
2956 /* There are some simplifications we can do even if the operands
2962 /* (not (not X)) == X, similarly for NEG. */
2963 if (GET_CODE (op
) == code
)
2964 return XEXP (op
, 0);
2968 /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
2969 becomes just the MINUS if its mode is MODE. This allows
2970 folding switch statements on machines using casesi (such as
2972 if (GET_CODE (op
) == TRUNCATE
2973 && GET_MODE (XEXP (op
, 0)) == mode
2974 && GET_CODE (XEXP (op
, 0)) == MINUS
2975 && GET_CODE (XEXP (XEXP (op
, 0), 0)) == LABEL_REF
2976 && GET_CODE (XEXP (XEXP (op
, 0), 1)) == LABEL_REF
)
2977 return XEXP (op
, 0);
2985 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
2986 and OP1. Return 0 if no simplification is possible.
2988 Don't use this for relational operations such as EQ or LT.
2989 Use simplify_relational_operation instead. */
2992 simplify_binary_operation (code
, mode
, op0
, op1
)
2994 enum machine_mode mode
;
2997 register int arg0
, arg1
, arg0s
, arg1s
;
2999 int width
= GET_MODE_BITSIZE (mode
);
3001 /* Relational operations don't work here. We must know the mode
3002 of the operands in order to do the comparison correctly.
3003 Assuming a full word can give incorrect results.
3004 Consider comparing 128 with -128 in QImode. */
3006 if (GET_RTX_CLASS (code
) == '<')
3009 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3010 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
3011 && GET_CODE (op0
) == CONST_DOUBLE
&& GET_CODE (op1
) == CONST_DOUBLE
3012 && mode
== GET_MODE (op0
) && mode
== GET_MODE (op1
))
3014 REAL_VALUE_TYPE f0
, f1
, value
;
3017 if (setjmp (handler
))
3020 set_float_handler (handler
);
3022 REAL_VALUE_FROM_CONST_DOUBLE (f0
, op0
);
3023 REAL_VALUE_FROM_CONST_DOUBLE (f1
, op1
);
3024 f0
= REAL_VALUE_TRUNCATE (mode
, f0
);
3025 f1
= REAL_VALUE_TRUNCATE (mode
, f1
);
3027 #ifdef REAL_ARITHMETIC
3028 REAL_ARITHMETIC (value
, code
, f0
, f1
);
3042 #ifndef REAL_INFINITY
3049 value
= MIN (f0
, f1
);
3052 value
= MAX (f0
, f1
);
3059 set_float_handler (0);
3060 value
= REAL_VALUE_TRUNCATE (mode
, value
);
3061 return immed_real_const_1 (value
, mode
);
3064 /* We can fold some multi-word operations. */
3065 else if (GET_MODE_CLASS (mode
) == MODE_INT
3066 && GET_CODE (op0
) == CONST_DOUBLE
3067 && (GET_CODE (op1
) == CONST_DOUBLE
|| GET_CODE (op1
) == CONST_INT
))
3069 int l1
, l2
, h1
, h2
, lv
, hv
;
3071 l1
= CONST_DOUBLE_LOW (op0
), h1
= CONST_DOUBLE_HIGH (op0
);
3073 if (GET_CODE (op1
) == CONST_DOUBLE
)
3074 l2
= CONST_DOUBLE_LOW (op1
), h2
= CONST_DOUBLE_HIGH (op1
);
3076 l2
= INTVAL (op1
), h2
= l2
< 0 ? -1 : 0;
3081 /* A - B == A + (-B). */
3082 neg_double (l2
, h2
, &lv
, &hv
);
3085 /* .. fall through ... */
3088 add_double (l1
, h1
, l2
, h2
, &lv
, &hv
);
3092 mul_double (l1
, h1
, l2
, h2
, &lv
, &hv
);
3095 case DIV
: case MOD
: case UDIV
: case UMOD
:
3096 /* We'd need to include tree.h to do this and it doesn't seem worth
3101 lv
= l1
& l2
, hv
= h1
& h2
;
3105 lv
= l1
| l2
, hv
= h1
| h2
;
3109 lv
= l1
^ l2
, hv
= h1
^ h2
;
3113 if (h1
< h2
|| (h1
== h2
&& (unsigned) l1
< (unsigned) l2
))
3120 if (h1
> h2
|| (h1
== h2
&& (unsigned) l1
> (unsigned) l2
))
3127 if ((unsigned) h1
< (unsigned) h2
3128 || (h1
== h2
&& (unsigned) l1
< (unsigned) l2
))
3135 if ((unsigned) h1
> (unsigned) h2
3136 || (h1
== h2
&& (unsigned) l1
> (unsigned) l2
))
3142 case LSHIFTRT
: case ASHIFTRT
:
3143 case ASHIFT
: case LSHIFT
:
3144 case ROTATE
: case ROTATERT
:
3145 #ifdef SHIFT_COUNT_TRUNCATED
3146 l2
&= (GET_MODE_BITSIZE (mode
) - 1), h2
= 0;
3149 if (h2
!= 0 || l2
< 0 || l2
>= GET_MODE_BITSIZE (mode
))
3152 if (code
== LSHIFTRT
|| code
== ASHIFTRT
)
3153 rshift_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
,
3155 else if (code
== ASHIFT
|| code
== LSHIFT
)
3156 lshift_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
,
3158 else if (code
== ROTATE
)
3159 lrotate_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
);
3160 else /* code == ROTATERT */
3161 rrotate_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
);
3168 return immed_double_const (lv
, hv
, mode
);
3170 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3172 if (GET_CODE (op0
) != CONST_INT
|| GET_CODE (op1
) != CONST_INT
3173 || width
> HOST_BITS_PER_INT
|| width
== 0)
3175 /* Even if we can't compute a constant result,
3176 there are some cases worth simplifying. */
3181 /* In IEEE floating point, x+0 is not the same as x. Similarly
3182 for the other optimizations below. */
3183 if (TARGET_FLOAT_FORMAT
== IEEE_FLOAT_FORMAT
3184 && GET_MODE_CLASS (mode
) != MODE_INT
)
3187 if (op1
== CONST0_RTX (mode
))
3190 /* Strip off any surrounding CONSTs. They don't matter in any of
3192 if (GET_CODE (op0
) == CONST
)
3193 op0
= XEXP (op0
, 0);
3194 if (GET_CODE (op1
) == CONST
)
3195 op1
= XEXP (op1
, 0);
3197 /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
3198 if (GET_CODE (op0
) == NEG
)
3200 rtx tem
= simplify_binary_operation (MINUS
, mode
,
3201 op1
, XEXP (op0
, 0));
3202 return tem
? tem
: gen_rtx (MINUS
, mode
, op1
, XEXP (op0
, 0));
3204 else if (GET_CODE (op1
) == NEG
)
3206 rtx tem
= simplify_binary_operation (MINUS
, mode
,
3207 op0
, XEXP (op1
, 0));
3208 return tem
? tem
: gen_rtx (MINUS
, mode
, op0
, XEXP (op1
, 0));
3211 /* Don't use the associative law for floating point.
3212 The inaccuracy makes it nonassociative,
3213 and subtle programs can break if operations are associated. */
3214 if (GET_MODE_CLASS (mode
) != MODE_INT
)
3217 /* (a - b) + b -> a, similarly a + (b - a) -> a */
3218 if (GET_CODE (op0
) == MINUS
3219 && rtx_equal_p (XEXP (op0
, 1), op1
) && ! side_effects_p (op1
))
3220 return XEXP (op0
, 0);
3222 if (GET_CODE (op1
) == MINUS
3223 && rtx_equal_p (XEXP (op1
, 1), op0
) && ! side_effects_p (op0
))
3224 return XEXP (op1
, 0);
3226 /* (c1 - a) + c2 becomes (c1 + c2) - a. */
3227 if (GET_CODE (op1
) == CONST_INT
&& GET_CODE (op0
) == MINUS
3228 && GET_CODE (XEXP (op0
, 0)) == CONST_INT
)
3230 rtx tem
= simplify_binary_operation (PLUS
, mode
, op1
,
3233 return tem
? gen_rtx (MINUS
, mode
, tem
, XEXP (op0
, 1)) : 0;
3236 /* Handle both-operands-constant cases. */
3237 if (CONSTANT_P (op0
) && CONSTANT_P (op1
)
3238 && GET_CODE (op0
) != CONST_DOUBLE
3239 && GET_CODE (op1
) != CONST_DOUBLE
3240 && GET_MODE_CLASS (mode
) == MODE_INT
)
3242 if (GET_CODE (op1
) == CONST_INT
)
3243 return plus_constant (op0
, INTVAL (op1
));
3244 else if (GET_CODE (op0
) == CONST_INT
)
3245 return plus_constant (op1
, INTVAL (op0
));
3247 return gen_rtx (CONST
, mode
,
3248 gen_rtx (PLUS
, mode
,
3249 GET_CODE (op0
) == CONST
3250 ? XEXP (op0
, 0) : op0
,
3251 GET_CODE (op1
) == CONST
3252 ? XEXP (op1
, 0) : op1
));
3254 else if (GET_CODE (op1
) == CONST_INT
3255 && GET_CODE (op0
) == PLUS
3256 && (CONSTANT_P (XEXP (op0
, 0))
3257 || CONSTANT_P (XEXP (op0
, 1))))
3258 /* constant + (variable + constant)
3259 can result if an index register is made constant.
3260 We simplify this by adding the constants.
3261 If we did not, it would become an invalid address. */
3262 return plus_constant (op0
, INTVAL (op1
));
3267 /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
3268 using cc0, in which case we want to leave it as a COMPARE
3269 so we can distinguish it from a register-register-copy.
3271 In IEEE floating point, x-0 is not the same as x. */
3273 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3274 || GET_MODE_CLASS (mode
) == MODE_INT
)
3275 && op1
== CONST0_RTX (mode
))
3278 /* Do nothing here. */
3283 /* None of these optimizations can be done for IEEE
3285 if (TARGET_FLOAT_FORMAT
== IEEE_FLOAT_FORMAT
3286 && GET_MODE_CLASS (mode
) != MODE_INT
)
3289 /* We can't assume x-x is 0 even with non-IEEE floating point. */
3290 if (rtx_equal_p (op0
, op1
)
3291 && ! side_effects_p (op0
)
3292 && GET_MODE_CLASS (mode
) != MODE_FLOAT
)
3295 /* Change subtraction from zero into negation. */
3296 if (op0
== CONST0_RTX (mode
))
3297 return gen_rtx (NEG
, mode
, op1
);
3299 /* Subtracting 0 has no effect. */
3300 if (op1
== CONST0_RTX (mode
))
3303 /* Strip off any surrounding CONSTs. They don't matter in any of
3305 if (GET_CODE (op0
) == CONST
)
3306 op0
= XEXP (op0
, 0);
3307 if (GET_CODE (op1
) == CONST
)
3308 op1
= XEXP (op1
, 0);
3310 /* (a - (-b)) -> (a + b). */
3311 if (GET_CODE (op1
) == NEG
)
3313 rtx tem
= simplify_binary_operation (PLUS
, mode
,
3314 op0
, XEXP (op1
, 0));
3315 return tem
? tem
: gen_rtx (PLUS
, mode
, op0
, XEXP (op1
, 0));
3318 /* Don't use the associative law for floating point.
3319 The inaccuracy makes it nonassociative,
3320 and subtle programs can break if operations are associated. */
3321 if (GET_MODE_CLASS (mode
) != MODE_INT
)
3324 /* (a + b) - a -> b, and (b - (a + b)) -> -a */
3325 if (GET_CODE (op0
) == PLUS
3326 && rtx_equal_p (XEXP (op0
, 0), op1
)
3327 && ! side_effects_p (op1
))
3328 return XEXP (op0
, 1);
3329 else if (GET_CODE (op0
) == PLUS
3330 && rtx_equal_p (XEXP (op0
, 1), op1
)
3331 && ! side_effects_p (op1
))
3332 return XEXP (op0
, 0);
3334 if (GET_CODE (op1
) == PLUS
3335 && rtx_equal_p (XEXP (op1
, 0), op0
)
3336 && ! side_effects_p (op0
))
3338 rtx tem
= simplify_unary_operation (NEG
, mode
, XEXP (op1
, 1),
3341 return tem
? tem
: gen_rtx (NEG
, mode
, XEXP (op1
, 1));
3343 else if (GET_CODE (op1
) == PLUS
3344 && rtx_equal_p (XEXP (op1
, 1), op0
)
3345 && ! side_effects_p (op0
))
3347 rtx tem
= simplify_unary_operation (NEG
, mode
, XEXP (op1
, 0),
3350 return tem
? tem
: gen_rtx (NEG
, mode
, XEXP (op1
, 0));
3353 /* a - (a - b) -> b */
3354 if (GET_CODE (op1
) == MINUS
&& rtx_equal_p (op0
, XEXP (op1
, 0))
3355 && ! side_effects_p (op0
))
3356 return XEXP (op1
, 1);
3358 /* (a +/- b) - (a +/- c) can be simplified. Do variants of
3359 this involving commutativity. The most common case is
3360 (a + C1) - (a + C2), but it's not hard to do all the cases. */
3361 if ((GET_CODE (op0
) == PLUS
|| GET_CODE (op0
) == MINUS
)
3362 && (GET_CODE (op1
) == PLUS
|| GET_CODE (op1
) == MINUS
))
3364 rtx lhs0
= XEXP (op0
, 0), lhs1
= XEXP (op0
, 1);
3365 rtx rhs0
= XEXP (op1
, 0), rhs1
= XEXP (op1
, 1);
3366 int lhs_neg
= GET_CODE (op0
) == MINUS
;
3367 int rhs_neg
= GET_CODE (op1
) == MINUS
;
3368 rtx lhs
= 0, rhs
= 0;
3370 /* Set LHS and RHS to the two different terms. */
3371 if (rtx_equal_p (lhs0
, rhs0
) && ! side_effects_p (lhs0
))
3372 lhs
= lhs1
, rhs
= rhs1
;
3373 else if (! rhs_neg
&& rtx_equal_p (lhs0
, rhs1
)
3374 && ! side_effects_p (lhs0
))
3375 lhs
= lhs1
, rhs
= rhs0
;
3376 else if (! lhs_neg
&& rtx_equal_p (lhs1
, rhs0
)
3377 && ! side_effects_p (lhs1
))
3378 lhs
= lhs0
, rhs
= rhs1
;
3379 else if (! lhs_neg
&& ! rhs_neg
&& rtx_equal_p (lhs1
, rhs1
)
3380 && ! side_effects_p (lhs1
))
3381 lhs
= lhs0
, rhs
= rhs0
;
3383 /* The RHS is the operand of a MINUS, so its negation
3384 status should be complemented. */
3385 rhs_neg
= ! rhs_neg
;
3387 /* If we found two values equal, form the sum or difference
3388 of the remaining two terms. */
3391 rtx tem
= simplify_binary_operation (lhs_neg
== rhs_neg
3394 lhs_neg
? rhs
: lhs
,
3395 lhs_neg
? lhs
: rhs
);
3397 tem
= gen_rtx (lhs_neg
== rhs_neg
3399 mode
, lhs_neg
? rhs
: lhs
,
3400 lhs_neg
? lhs
: rhs
);
3402 /* If both sides negated, negate result. */
3403 if (lhs_neg
&& rhs_neg
)
3406 = simplify_unary_operation (NEG
, mode
, tem
, mode
);
3408 tem1
= gen_rtx (NEG
, mode
, tem
);
3418 /* c1 - (a + c2) becomes (c1 - c2) - a. */
3419 if (GET_CODE (op0
) == CONST_INT
&& GET_CODE (op1
) == PLUS
3420 && GET_CODE (XEXP (op1
, 1)) == CONST_INT
)
3422 rtx tem
= simplify_binary_operation (MINUS
, mode
, op0
,
3425 return tem
? gen_rtx (MINUS
, mode
, tem
, XEXP (op1
, 0)) : 0;
3428 /* c1 - (c2 - a) becomes (c1 - c2) + a. */
3429 if (GET_CODE (op0
) == CONST_INT
&& GET_CODE (op1
) == MINUS
3430 && GET_CODE (XEXP (op1
, 0)) == CONST_INT
)
3432 rtx tem
= simplify_binary_operation (MINUS
, mode
, op0
,
3435 return (tem
&& GET_CODE (tem
) == CONST_INT
3436 ? plus_constant (XEXP (op1
, 1), INTVAL (tem
))
3440 /* Don't let a relocatable value get a negative coeff. */
3441 if (GET_CODE (op1
) == CONST_INT
)
3442 return plus_constant (op0
, - INTVAL (op1
));
3446 if (op1
== constm1_rtx
)
3448 rtx tem
= simplify_unary_operation (NEG
, mode
, op0
, mode
);
3450 return tem
? tem
: gen_rtx (NEG
, mode
, op0
);
3453 /* In IEEE floating point, x*0 is not always 0. */
3454 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3455 || GET_MODE_CLASS (mode
) == MODE_INT
)
3456 && op1
== CONST0_RTX (mode
)
3457 && ! side_effects_p (op0
))
3460 /* In IEEE floating point, x*1 is not equivalent to x for nans.
3461 However, ANSI says we can drop signals,
3462 so we can do this anyway. */
3463 if (op1
== CONST1_RTX (mode
))
3466 /* Convert multiply by constant power of two into shift. */
3467 if (GET_CODE (op1
) == CONST_INT
3468 && (val
= exact_log2 (INTVAL (op1
))) >= 0)
3469 return gen_rtx (ASHIFT
, mode
, op0
,
3470 gen_rtx (CONST_INT
, VOIDmode
, val
));
3472 if (GET_CODE (op1
) == CONST_DOUBLE
3473 && GET_MODE_CLASS (GET_MODE (op1
)) == MODE_FLOAT
)
3476 REAL_VALUE_FROM_CONST_DOUBLE (d
, op1
);
3478 /* x*2 is x+x and x*(-1) is -x */
3479 if (REAL_VALUES_EQUAL (d
, dconst2
)
3480 && GET_MODE (op0
) == mode
)
3481 return gen_rtx (PLUS
, mode
, op0
, copy_rtx (op0
));
3483 else if (REAL_VALUES_EQUAL (d
, dconstm1
)
3484 && GET_MODE (op0
) == mode
)
3485 return gen_rtx (NEG
, mode
, op0
);
3490 if (op1
== const0_rtx
)
3492 if (GET_CODE (op1
) == CONST_INT
3493 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3495 if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3497 /* A | (~A) -> -1 */
3498 if (((GET_CODE (op0
) == NOT
&& rtx_equal_p (XEXP (op0
, 0), op1
))
3499 || (GET_CODE (op1
) == NOT
&& rtx_equal_p (XEXP (op1
, 0), op0
)))
3500 && ! side_effects_p (op0
))
3505 if (op1
== const0_rtx
)
3507 if (GET_CODE (op1
) == CONST_INT
3508 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3509 return gen_rtx (NOT
, mode
, op0
);
3510 if (op0
== op1
&& ! side_effects_p (op0
))
3515 if (op1
== const0_rtx
&& ! side_effects_p (op0
))
3517 if (GET_CODE (op1
) == CONST_INT
3518 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3520 if (op0
== op1
&& ! side_effects_p (op0
))
3523 if (((GET_CODE (op0
) == NOT
&& rtx_equal_p (XEXP (op0
, 0), op1
))
3524 || (GET_CODE (op1
) == NOT
&& rtx_equal_p (XEXP (op1
, 0), op0
)))
3525 && ! side_effects_p (op0
))
3530 /* Convert divide by power of two into shift (divide by 1 handled
3532 if (GET_CODE (op1
) == CONST_INT
3533 && (arg1
= exact_log2 (INTVAL (op1
))) > 0)
3534 return gen_rtx (LSHIFTRT
, mode
, op0
,
3535 gen_rtx (CONST_INT
, VOIDmode
, arg1
));
3537 /* ... fall through ... */
3540 if (op1
== CONST1_RTX (mode
))
3542 else if (op0
== CONST0_RTX (mode
)
3543 && ! side_effects_p (op1
))
3545 #if 0 /* Turned off till an expert says this is a safe thing to do. */
3546 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3547 /* Change division by a constant into multiplication. */
3548 else if (GET_CODE (op1
) == CONST_DOUBLE
3549 && GET_MODE_CLASS (GET_MODE (op1
)) == MODE_FLOAT
3550 && op1
!= CONST0_RTX (mode
))
3553 REAL_VALUE_FROM_CONST_DOUBLE (d
, op1
);
3554 if (REAL_VALUES_EQUAL (d
, dconst0
))
3556 #if defined (REAL_ARITHMETIC)
3557 REAL_ARITHMETIC (d
, RDIV_EXPR
, dconst1
, d
);
3558 return gen_rtx (MULT
, mode
, op0
,
3559 CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
));
3561 return gen_rtx (MULT
, mode
, op0
,
3562 CONST_DOUBLE_FROM_REAL_VALUE (1./d
, mode
));
3570 /* Handle modulus by power of two (mod with 1 handled below). */
3571 if (GET_CODE (op1
) == CONST_INT
3572 && exact_log2 (INTVAL (op1
)) > 0)
3573 return gen_rtx (AND
, mode
, op0
,
3574 gen_rtx (CONST_INT
, VOIDmode
, INTVAL (op1
) - 1));
3576 /* ... fall through ... */
3579 if ((op0
== const0_rtx
|| op1
== const1_rtx
)
3580 && ! side_effects_p (op0
) && ! side_effects_p (op1
))
3586 /* Rotating ~0 always results in ~0. */
3587 if (GET_CODE (op0
) == CONST_INT
&& width
<= HOST_BITS_PER_INT
3588 && INTVAL (op0
) == GET_MODE_MASK (mode
)
3589 && ! side_effects_p (op1
))
3592 /* ... fall through ... */
3598 if (op1
== const0_rtx
)
3600 if (op0
== const0_rtx
&& ! side_effects_p (op1
))
3605 if (width
<= HOST_BITS_PER_INT
&& GET_CODE (op1
) == CONST_INT
3606 && INTVAL (op1
) == 1 << (width
-1)
3607 && ! side_effects_p (op0
))
3609 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3614 if (width
<= HOST_BITS_PER_INT
&& GET_CODE (op1
) == CONST_INT
3615 && INTVAL (op1
) == GET_MODE_MASK (mode
) >> 1
3616 && ! side_effects_p (op0
))
3618 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3623 if (op1
== const0_rtx
&& ! side_effects_p (op0
))
3625 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3630 if (op1
== constm1_rtx
&& ! side_effects_p (op0
))
3632 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3643 /* Get the integer argument values in two forms:
3644 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
3646 arg0
= INTVAL (op0
);
3647 arg1
= INTVAL (op1
);
3649 if (width
< HOST_BITS_PER_INT
)
3651 arg0
&= (1 << width
) - 1;
3652 arg1
&= (1 << width
) - 1;
3655 if (arg0s
& (1 << (width
- 1)))
3656 arg0s
|= ((-1) << width
);
3659 if (arg1s
& (1 << (width
- 1)))
3660 arg1s
|= ((-1) << width
);
3668 /* Compute the value of the arithmetic. */
3673 val
= arg0s
+ arg1s
;
3677 val
= arg0s
- arg1s
;
3681 val
= arg0s
* arg1s
;
3687 val
= arg0s
/ arg1s
;
3693 val
= arg0s
% arg1s
;
3699 val
= (unsigned) arg0
/ arg1
;
3705 val
= (unsigned) arg0
% arg1
;
3721 /* If shift count is undefined, don't fold it; let the machine do
3722 what it wants. But truncate it if the machine will do that. */
3726 #ifdef SHIFT_COUNT_TRUNCATED
3727 arg1
&= (BITS_PER_WORD
- 1);
3733 val
= ((unsigned) arg0
) >> arg1
;
3741 #ifdef SHIFT_COUNT_TRUNCATED
3742 arg1
&= (BITS_PER_WORD
- 1);
3748 val
= ((unsigned) arg0
) << arg1
;
3755 #ifdef SHIFT_COUNT_TRUNCATED
3756 arg1
&= (BITS_PER_WORD
- 1);
3762 val
= arg0s
>> arg1
;
3770 val
= ((((unsigned) arg0
) << (width
- arg1
))
3771 | (((unsigned) arg0
) >> arg1
));
3779 val
= ((((unsigned) arg0
) << arg1
)
3780 | (((unsigned) arg0
) >> (width
- arg1
)));
3784 /* Do nothing here. */
3788 val
= arg0s
<= arg1s
? arg0s
: arg1s
;
3792 val
= (unsigned int)arg0
<= (unsigned int)arg1
? arg0
: arg1
;
3796 val
= arg0s
> arg1s
? arg0s
: arg1s
;
3800 val
= (unsigned int)arg0
> (unsigned int)arg1
? arg0
: arg1
;
3807 /* Clear the bits that don't belong in our mode, unless they and our sign
3808 bit are all one. So we get either a reasonable negative value or a
3809 reasonable unsigned value for this mode. */
3810 if (width
< HOST_BITS_PER_INT
3811 && ((val
& ((-1) << (width
- 1))) != ((-1) << (width
- 1))))
3812 val
&= (1 << width
) - 1;
3814 return gen_rtx (CONST_INT
, VOIDmode
, val
);
3817 /* Like simplify_binary_operation except used for relational operators.
3818 MODE is the mode of the operands, not that of the result. */
3821 simplify_relational_operation (code
, mode
, op0
, op1
)
3823 enum machine_mode mode
;
3826 register int arg0
, arg1
, arg0s
, arg1s
;
3828 int width
= GET_MODE_BITSIZE (mode
);
3830 /* If op0 is a compare, extract the comparison arguments from it. */
3831 if (GET_CODE (op0
) == COMPARE
&& op1
== const0_rtx
)
3832 op1
= XEXP (op0
, 1), op0
= XEXP (op0
, 0);
3834 if (GET_CODE (op0
) != CONST_INT
|| GET_CODE (op1
) != CONST_INT
3835 || width
> HOST_BITS_PER_INT
|| width
== 0)
3837 /* Even if we can't compute a constant result,
3838 there are some cases worth simplifying. */
3840 /* For non-IEEE floating-point, if the two operands are equal, we know
3842 if (rtx_equal_p (op0
, op1
)
3843 && (TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3844 || GET_MODE_CLASS (GET_MODE (op0
)) != MODE_FLOAT
))
3845 return (code
== EQ
|| code
== GE
|| code
== LE
|| code
== LEU
3846 || code
== GEU
) ? const_true_rtx
: const0_rtx
;
3847 else if (GET_CODE (op0
) == CONST_DOUBLE
3848 && GET_CODE (op1
) == CONST_DOUBLE
3849 && GET_MODE_CLASS (GET_MODE (op0
)) == MODE_FLOAT
)
3851 REAL_VALUE_TYPE d0
, d1
;
3854 int op0lt
, op1lt
, equal
;
3856 if (setjmp (handler
))
3859 set_float_handler (handler
);
3860 REAL_VALUE_FROM_CONST_DOUBLE (d0
, op0
);
3861 REAL_VALUE_FROM_CONST_DOUBLE (d1
, op1
);
3862 equal
= REAL_VALUES_EQUAL (d0
, d1
);
3863 op0lt
= REAL_VALUES_LESS (d0
, d1
);
3864 op1lt
= REAL_VALUES_LESS (d1
, d0
);
3865 set_float_handler (0);
3870 return equal
? const_true_rtx
: const0_rtx
;
3872 return !equal
? const_true_rtx
: const0_rtx
;
3874 return equal
|| op0lt
? const_true_rtx
: const0_rtx
;
3876 return op0lt
? const_true_rtx
: const0_rtx
;
3878 return equal
|| op1lt
? const_true_rtx
: const0_rtx
;
3880 return op1lt
? const_true_rtx
: const0_rtx
;
3889 /* We can't make this assumption due to #pragma weak */
3890 if (CONSTANT_P (op0
) && op1
== const0_rtx
)
3893 if (NONZERO_BASE_PLUS_P (op0
) && op1
== const0_rtx
3894 /* On some machines, the ap reg can be 0 sometimes. */
3895 && op0
!= arg_pointer_rtx
)
3902 /* We can't make this assumption due to #pragma weak */
3903 if (CONSTANT_P (op0
) && op1
== const0_rtx
)
3904 return const_true_rtx
;
3906 if (NONZERO_BASE_PLUS_P (op0
) && op1
== const0_rtx
3907 /* On some machines, the ap reg can be 0 sometimes. */
3908 && op0
!= arg_pointer_rtx
)
3909 return const_true_rtx
;
3913 /* Unsigned values are never negative, but we must be sure we are
3914 actually comparing a value, not a CC operand. */
3915 if (op1
== const0_rtx
3916 && GET_MODE_CLASS (mode
) == MODE_INT
)
3917 return const_true_rtx
;
3921 if (op1
== const0_rtx
3922 && GET_MODE_CLASS (mode
) == MODE_INT
)
3927 /* Unsigned values are never greater than the largest
3929 if (GET_CODE (op1
) == CONST_INT
3930 && INTVAL (op1
) == GET_MODE_MASK (mode
)
3931 && GET_MODE_CLASS (mode
) == MODE_INT
)
3932 return const_true_rtx
;
3936 if (GET_CODE (op1
) == CONST_INT
3937 && INTVAL (op1
) == GET_MODE_MASK (mode
)
3938 && GET_MODE_CLASS (mode
) == MODE_INT
)
3946 /* Get the integer argument values in two forms:
3947 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
3949 arg0
= INTVAL (op0
);
3950 arg1
= INTVAL (op1
);
3952 if (width
< HOST_BITS_PER_INT
)
3954 arg0
&= (1 << width
) - 1;
3955 arg1
&= (1 << width
) - 1;
3958 if (arg0s
& (1 << (width
- 1)))
3959 arg0s
|= ((-1) << width
);
3962 if (arg1s
& (1 << (width
- 1)))
3963 arg1s
|= ((-1) << width
);
3971 /* Compute the value of the arithmetic. */
3976 val
= arg0
!= arg1
? STORE_FLAG_VALUE
: 0;
3980 val
= arg0
== arg1
? STORE_FLAG_VALUE
: 0;
3984 val
= arg0s
<= arg1s
? STORE_FLAG_VALUE
: 0;
3988 val
= arg0s
< arg1s
? STORE_FLAG_VALUE
: 0;
3992 val
= arg0s
>= arg1s
? STORE_FLAG_VALUE
: 0;
3996 val
= arg0s
> arg1s
? STORE_FLAG_VALUE
: 0;
4000 val
= ((unsigned) arg0
) <= ((unsigned) arg1
) ? STORE_FLAG_VALUE
: 0;
4004 val
= ((unsigned) arg0
) < ((unsigned) arg1
) ? STORE_FLAG_VALUE
: 0;
4008 val
= ((unsigned) arg0
) >= ((unsigned) arg1
) ? STORE_FLAG_VALUE
: 0;
4012 val
= ((unsigned) arg0
) > ((unsigned) arg1
) ? STORE_FLAG_VALUE
: 0;
4019 /* Clear the bits that don't belong in our mode, unless they and our sign
4020 bit are all one. So we get either a reasonable negative value or a
4021 reasonable unsigned value for this mode. */
4022 if (width
< HOST_BITS_PER_INT
4023 && ((val
& ((-1) << (width
- 1))) != ((-1) << (width
- 1))))
4024 val
&= (1 << width
) - 1;
4026 return gen_rtx (CONST_INT
, VOIDmode
, val
);
4029 /* Simplify CODE, an operation with result mode MODE and three operands,
4030 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
4031 a constant. Return 0 if no simplifications is possible. */
4034 simplify_ternary_operation (code
, mode
, op0_mode
, op0
, op1
, op2
)
4036 enum machine_mode mode
, op0_mode
;
4039 int width
= GET_MODE_BITSIZE (mode
);
4041 /* VOIDmode means "infinite" precision. */
4043 width
= HOST_BITS_PER_INT
;
4049 if (GET_CODE (op0
) == CONST_INT
4050 && GET_CODE (op1
) == CONST_INT
4051 && GET_CODE (op2
) == CONST_INT
4052 && INTVAL (op1
) + INTVAL (op2
) <= GET_MODE_BITSIZE (op0_mode
)
4053 && width
<= HOST_BITS_PER_INT
)
4055 /* Extracting a bit-field from a constant */
4056 int val
= INTVAL (op0
);
4059 val
>>= (GET_MODE_BITSIZE (op0_mode
) - INTVAL (op2
) - INTVAL (op1
));
4061 val
>>= INTVAL (op2
);
4063 if (HOST_BITS_PER_INT
!= INTVAL (op1
))
4065 /* First zero-extend. */
4066 val
&= (1 << INTVAL (op1
)) - 1;
4067 /* If desired, propagate sign bit. */
4068 if (code
== SIGN_EXTRACT
&& (val
& (1 << (INTVAL (op1
) - 1))))
4069 val
|= ~ ((1 << INTVAL (op1
)) - 1);
4072 /* Clear the bits that don't belong in our mode,
4073 unless they and our sign bit are all one.
4074 So we get either a reasonable negative value or a reasonable
4075 unsigned value for this mode. */
4076 if (width
< HOST_BITS_PER_INT
4077 && ((val
& ((-1) << (width
- 1))) != ((-1) << (width
- 1))))
4078 val
&= (1 << width
) - 1;
4080 return gen_rtx (CONST_INT
, VOIDmode
, val
);
4085 if (GET_CODE (op0
) == CONST_INT
)
4086 return op0
!= const0_rtx
? op1
: op2
;
4096 /* If X is a nontrivial arithmetic operation on an argument
4097 for which a constant value can be determined, return
4098 the result of operating on that value, as a constant.
4099 Otherwise, return X, possibly with one or more operands
4100 modified by recursive calls to this function.
4102 If X is a register whose contents are known, we do NOT
4103 return those contents. This is because an instruction that
4104 uses a register is usually faster than one that uses a constant.
4106 INSN is the insn that we may be modifying. If it is 0, make a copy
4107 of X before modifying it. */
4114 register enum rtx_code code
;
4115 register enum machine_mode mode
;
4117 register int i
, val
;
4122 /* Folded equivalents of first two operands of X. */
4126 /* Constant equivalents of first three operands of X;
4127 0 when no such equivalent is known. */
4132 /* The mode of the first operand of X. We need this for sign and zero
4134 enum machine_mode mode_arg0
;
4139 mode
= GET_MODE (x
);
4140 code
= GET_CODE (x
);
4149 /* No use simplifying an EXPR_LIST
4150 since they are used only for lists of args
4151 in a function call's REG_EQUAL note. */
4157 return prev_insn_cc0
;
4161 /* If the next insn is a CODE_LABEL followed by a jump table,
4162 PC's value is a LABEL_REF pointing to that label. That
4163 lets us fold switch statements on the Vax. */
4164 if (insn
&& GET_CODE (insn
) == JUMP_INSN
)
4166 rtx next
= next_nonnote_insn (insn
);
4168 if (next
&& GET_CODE (next
) == CODE_LABEL
4169 && NEXT_INSN (next
) != 0
4170 && GET_CODE (NEXT_INSN (next
)) == JUMP_INSN
4171 && (GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_VEC
4172 || GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_DIFF_VEC
))
4173 return gen_rtx (LABEL_REF
, Pmode
, next
);
4178 /* If this is a single word of a multi-word value, see if we previously
4179 assigned a value to that word. */
4180 if (GET_MODE_SIZE (mode
) <= UNITS_PER_WORD
4181 && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))) > UNITS_PER_WORD
4182 && (new = lookup_as_function (x
, CONST_INT
)) != 0)
4185 /* If this is a paradoxical SUBREG, we can't do anything with
4186 it because we have no idea what value the extra bits would have. */
4187 if (GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
4190 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
4191 We might be able to if the SUBREG is extracting a single word in an
4192 integral mode or extracting the low part. */
4194 folded_arg0
= fold_rtx (SUBREG_REG (x
), insn
);
4195 const_arg0
= equiv_constant (folded_arg0
);
4197 folded_arg0
= const_arg0
;
4199 if (folded_arg0
!= SUBREG_REG (x
))
4203 if (GET_MODE_CLASS (mode
) == MODE_INT
4204 && GET_MODE_SIZE (mode
) == UNITS_PER_WORD
4205 && GET_MODE (SUBREG_REG (x
)) != VOIDmode
)
4206 new = operand_subword (folded_arg0
, SUBREG_WORD (x
), 0,
4207 GET_MODE (SUBREG_REG (x
)));
4208 if (new == 0 && subreg_lowpart_p (x
))
4209 new = gen_lowpart_if_possible (mode
, folded_arg0
);
4214 /* If this is a narrowing SUBREG and our operand is a REG, see if
4215 we can find an equivalence for REG that is a arithmetic operation
4216 in a wider mode where both operands are paradoxical SUBREGs
4217 from objects of our result mode. In that case, we couldn't report
4218 an equivalent value for that operation, since we don't know what the
4219 extra bits will be. But we can find an equivalence for this SUBREG
4220 by folding that operation is the narrow mode. This allows us to
4221 fold arithmetic in narrow modes when the machine only supports
4222 word-sized arithmetic. */
4224 if (GET_CODE (folded_arg0
) == REG
4225 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (folded_arg0
)))
4227 struct table_elt
*elt
;
4229 /* We can use HASH here since we know that canon_hash won't be
4231 elt
= lookup (folded_arg0
,
4232 HASH (folded_arg0
, GET_MODE (folded_arg0
)),
4233 GET_MODE (folded_arg0
));
4236 elt
= elt
->first_same_value
;
4238 for (; elt
; elt
= elt
->next_same_value
)
4240 /* Just check for unary and binary operations. */
4241 if (GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '1'
4242 && GET_CODE (elt
->exp
) != SIGN_EXTEND
4243 && GET_CODE (elt
->exp
) != ZERO_EXTEND
4244 && GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
4245 && GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0))) == mode
)
4247 rtx op0
= SUBREG_REG (XEXP (elt
->exp
, 0));
4249 if (GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
4250 op0
= fold_rtx (op0
, 0);
4252 op0
= equiv_constant (op0
);
4254 new = simplify_unary_operation (GET_CODE (elt
->exp
), mode
,
4257 else if ((GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '2'
4258 || GET_RTX_CLASS (GET_CODE (elt
->exp
)) == 'c')
4259 && ((GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
4260 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0)))
4262 || CONSTANT_P (XEXP (elt
->exp
, 0)))
4263 && ((GET_CODE (XEXP (elt
->exp
, 1)) == SUBREG
4264 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 1)))
4266 || CONSTANT_P (XEXP (elt
->exp
, 1))))
4268 rtx op0
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 0));
4269 rtx op1
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 1));
4271 if (op0
&& GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
4272 op0
= fold_rtx (op0
, 0);
4275 op0
= equiv_constant (op0
);
4277 if (op1
&& GET_CODE (op1
) != REG
&& ! CONSTANT_P (op1
))
4278 op1
= fold_rtx (op1
, 0);
4281 op1
= equiv_constant (op1
);
4284 new = simplify_binary_operation (GET_CODE (elt
->exp
), mode
,
4297 /* If we have (NOT Y), see if Y is known to be (NOT Z).
4298 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
4299 new = lookup_as_function (XEXP (x
, 0), code
);
4301 return fold_rtx (copy_rtx (XEXP (new, 0)), insn
);
4305 /* If we are not actually processing an insn, don't try to find the
4306 best address. Not only don't we care, but we could modify the
4307 MEM in an invalid way since we have no insn to validate against. */
4309 find_best_addr (insn
, &XEXP (x
, 0));
4312 /* Even if we don't fold in the insn itself,
4313 we can safely do so here, in hopes of getting a constant. */
4314 rtx addr
= fold_rtx (XEXP (x
, 0), 0);
4318 if (GET_CODE (addr
) == REG
4319 && REGNO_QTY_VALID_P (REGNO (addr
))
4320 && GET_MODE (addr
) == qty_mode
[reg_qty
[REGNO (addr
)]]
4321 && qty_const
[reg_qty
[REGNO (addr
)]] != 0)
4322 addr
= qty_const
[reg_qty
[REGNO (addr
)]];
4324 /* If address is constant, split it into a base and integer offset. */
4325 if (GET_CODE (addr
) == SYMBOL_REF
|| GET_CODE (addr
) == LABEL_REF
)
4327 else if (GET_CODE (addr
) == CONST
&& GET_CODE (XEXP (addr
, 0)) == PLUS
4328 && GET_CODE (XEXP (XEXP (addr
, 0), 1)) == CONST_INT
)
4330 base
= XEXP (XEXP (addr
, 0), 0);
4331 offset
= INTVAL (XEXP (XEXP (addr
, 0), 1));
4333 else if (GET_CODE (addr
) == LO_SUM
4334 && GET_CODE (XEXP (addr
, 1)) == SYMBOL_REF
)
4335 base
= XEXP (addr
, 1);
4337 /* If this is a constant pool reference, we can fold it into its
4338 constant to allow better value tracking. */
4339 if (base
&& GET_CODE (base
) == SYMBOL_REF
4340 && CONSTANT_POOL_ADDRESS_P (base
))
4342 rtx constant
= get_pool_constant (base
);
4343 enum machine_mode const_mode
= get_pool_mode (base
);
4346 if (CONSTANT_P (constant
) && GET_CODE (constant
) != CONST_INT
)
4347 constant_pool_entries_cost
= COST (constant
);
4349 /* If we are loading the full constant, we have an equivalence. */
4350 if (offset
== 0 && mode
== const_mode
)
4353 /* If this actually isn't a constant (wierd!), we can't do
4354 anything. Otherwise, handle the two most common cases:
4355 extracting a word from a multi-word constant, and extracting
4356 the low-order bits. Other cases don't seem common enough to
4358 if (! CONSTANT_P (constant
))
4361 if (GET_MODE_CLASS (mode
) == MODE_INT
4362 && GET_MODE_SIZE (mode
) == UNITS_PER_WORD
4363 && offset
% UNITS_PER_WORD
== 0
4364 && (new = operand_subword (constant
,
4365 offset
/ UNITS_PER_WORD
,
4366 0, const_mode
)) != 0)
4369 if (((BYTES_BIG_ENDIAN
4370 && offset
== GET_MODE_SIZE (GET_MODE (constant
)) - 1)
4371 || (! BYTES_BIG_ENDIAN
&& offset
== 0))
4372 && (new = gen_lowpart_if_possible (mode
, constant
)) != 0)
4376 /* If this is a reference to a label at a known position in a jump
4377 table, we also know its value. */
4378 if (base
&& GET_CODE (base
) == LABEL_REF
)
4380 rtx label
= XEXP (base
, 0);
4381 rtx table_insn
= NEXT_INSN (label
);
4383 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
4384 && GET_CODE (PATTERN (table_insn
)) == ADDR_VEC
)
4386 rtx table
= PATTERN (table_insn
);
4389 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
4390 < XVECLEN (table
, 0)))
4391 return XVECEXP (table
, 0,
4392 offset
/ GET_MODE_SIZE (GET_MODE (table
)));
4394 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
4395 && GET_CODE (PATTERN (table_insn
)) == ADDR_DIFF_VEC
)
4397 rtx table
= PATTERN (table_insn
);
4400 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
4401 < XVECLEN (table
, 1)))
4403 offset
/= GET_MODE_SIZE (GET_MODE (table
));
4404 new = gen_rtx (MINUS
, Pmode
, XVECEXP (table
, 1, offset
),
4407 if (GET_MODE (table
) != Pmode
)
4408 new = gen_rtx (TRUNCATE
, GET_MODE (table
), new);
4422 mode_arg0
= VOIDmode
;
4424 /* Try folding our operands.
4425 Then see which ones have constant values known. */
4427 fmt
= GET_RTX_FORMAT (code
);
4428 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4431 rtx arg
= XEXP (x
, i
);
4432 rtx folded_arg
= arg
, const_arg
= 0;
4433 enum machine_mode mode_arg
= GET_MODE (arg
);
4434 rtx cheap_arg
, expensive_arg
;
4435 rtx replacements
[2];
4438 /* Most arguments are cheap, so handle them specially. */
4439 switch (GET_CODE (arg
))
4442 /* This is the same as calling equiv_constant; it is duplicated
4444 if (REGNO_QTY_VALID_P (REGNO (arg
))
4445 && qty_const
[reg_qty
[REGNO (arg
)]] != 0
4446 && GET_CODE (qty_const
[reg_qty
[REGNO (arg
)]]) != REG
4447 && GET_CODE (qty_const
[reg_qty
[REGNO (arg
)]]) != PLUS
)
4449 = gen_lowpart_if_possible (GET_MODE (arg
),
4450 qty_const
[reg_qty
[REGNO (arg
)]]);
4463 folded_arg
= prev_insn_cc0
;
4464 mode_arg
= prev_insn_cc0_mode
;
4465 const_arg
= equiv_constant (folded_arg
);
4470 folded_arg
= fold_rtx (arg
, insn
);
4471 const_arg
= equiv_constant (folded_arg
);
4474 /* For the first three operands, see if the operand
4475 is constant or equivalent to a constant. */
4479 folded_arg0
= folded_arg
;
4480 const_arg0
= const_arg
;
4481 mode_arg0
= mode_arg
;
4484 folded_arg1
= folded_arg
;
4485 const_arg1
= const_arg
;
4488 const_arg2
= const_arg
;
4492 /* Pick the least expensive of the folded argument and an
4493 equivalent constant argument. */
4494 if (const_arg
== 0 || const_arg
== folded_arg
4495 || COST (const_arg
) > COST (folded_arg
))
4496 cheap_arg
= folded_arg
, expensive_arg
= const_arg
;
4498 cheap_arg
= const_arg
, expensive_arg
= folded_arg
;
4500 /* Try to replace the operand with the cheapest of the two
4501 possibilities. If it doesn't work and this is either of the first
4502 two operands of a commutative operation, try swapping them.
4503 If THAT fails, try the more expensive, provided it is cheaper
4504 than what is already there. */
4506 if (cheap_arg
== XEXP (x
, i
))
4509 if (insn
== 0 && ! copied
)
4515 replacements
[0] = cheap_arg
, replacements
[1] = expensive_arg
;
4517 j
< 2 && replacements
[j
]
4518 && COST (replacements
[j
]) < COST (XEXP (x
, i
));
4521 if (validate_change (insn
, &XEXP (x
, i
), replacements
[j
], 0))
4524 if (code
== NE
|| code
== EQ
|| GET_RTX_CLASS (code
) == 'c')
4526 validate_change (insn
, &XEXP (x
, i
), XEXP (x
, 1 - i
), 1);
4527 validate_change (insn
, &XEXP (x
, 1 - i
), replacements
[j
], 1);
4529 if (apply_change_group ())
4531 /* Swap them back to be invalid so that this loop can
4532 continue and flag them to be swapped back later. */
4535 tem
= XEXP (x
, 0); XEXP (x
, 0) = XEXP (x
, 1);
4544 else if (fmt
[i
] == 'E')
4545 /* Don't try to fold inside of a vector of expressions.
4546 Doing nothing is harmless. */
4549 /* If a commutative operation, place a constant integer as the second
4550 operand unless the first operand is also a constant integer. Otherwise,
4551 place any constant second unless the first operand is also a constant. */
4553 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
4555 if (must_swap
|| (const_arg0
4557 || (GET_CODE (const_arg0
) == CONST_INT
4558 && GET_CODE (const_arg1
) != CONST_INT
))))
4560 register rtx tem
= XEXP (x
, 0);
4562 if (insn
== 0 && ! copied
)
4568 validate_change (insn
, &XEXP (x
, 0), XEXP (x
, 1), 1);
4569 validate_change (insn
, &XEXP (x
, 1), tem
, 1);
4570 if (apply_change_group ())
4572 tem
= const_arg0
, const_arg0
= const_arg1
, const_arg1
= tem
;
4573 tem
= folded_arg0
, folded_arg0
= folded_arg1
, folded_arg1
= tem
;
4578 /* If X is an arithmetic operation, see if we can simplify it. */
4580 switch (GET_RTX_CLASS (code
))
4583 new = simplify_unary_operation (code
, mode
,
4584 const_arg0
? const_arg0
: folded_arg0
,
4589 /* See what items are actually being compared and set FOLDED_ARG[01]
4590 to those values and CODE to the actual comparison code. If any are
4591 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
4592 do anything if both operands are already known to be constant. */
4594 if (const_arg0
== 0 || const_arg1
== 0)
4596 struct table_elt
*p0
, *p1
;
4598 code
= find_comparison_args (code
, &folded_arg0
, &folded_arg1
);
4599 const_arg0
= equiv_constant (folded_arg0
);
4600 const_arg1
= equiv_constant (folded_arg1
);
4602 /* Get a mode from the values actually being compared, or from the
4603 old value of MODE_ARG0 if both are constants. If the resulting
4604 mode is VOIDmode or a MODE_CC mode, we don't know what kinds
4605 of things are being compared, so we can't do anything with this
4608 if (GET_MODE (folded_arg0
) != VOIDmode
4609 && GET_MODE_CLASS (GET_MODE (folded_arg0
)) != MODE_CC
)
4610 mode_arg0
= GET_MODE (folded_arg0
);
4612 else if (GET_MODE (folded_arg1
) != VOIDmode
4613 && GET_MODE_CLASS (GET_MODE (folded_arg1
)) != MODE_CC
)
4614 mode_arg0
= GET_MODE (folded_arg1
);
4616 if (mode_arg0
== VOIDmode
|| GET_MODE_CLASS (mode_arg0
) == MODE_CC
)
4619 /* If we do not now have two constants being compared, see if we
4620 can nevertheless deduce some things about the comparison. */
4621 if (const_arg0
== 0 || const_arg1
== 0)
4623 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or non-explicit
4624 constant? These aren't zero, but we don't know their sign. */
4625 if (const_arg1
== const0_rtx
4626 && (NONZERO_BASE_PLUS_P (folded_arg0
)
4627 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
4629 || GET_CODE (folded_arg0
) == SYMBOL_REF
4631 || GET_CODE (folded_arg0
) == LABEL_REF
4632 || GET_CODE (folded_arg0
) == CONST
))
4636 else if (code
== NE
)
4637 return const_true_rtx
;
4640 /* See if the two operands are the same. We don't do this
4641 for IEEE floating-point since we can't assume x == x
4642 since x might be a NaN. */
4644 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
4645 || GET_MODE_CLASS (mode_arg0
) != MODE_FLOAT
)
4646 && (folded_arg0
== folded_arg1
4647 || (GET_CODE (folded_arg0
) == REG
4648 && GET_CODE (folded_arg1
) == REG
4649 && (reg_qty
[REGNO (folded_arg0
)]
4650 == reg_qty
[REGNO (folded_arg1
)]))
4651 || ((p0
= lookup (folded_arg0
,
4652 (safe_hash (folded_arg0
, mode_arg0
)
4653 % NBUCKETS
), mode_arg0
))
4654 && (p1
= lookup (folded_arg1
,
4655 (safe_hash (folded_arg1
, mode_arg0
)
4656 % NBUCKETS
), mode_arg0
))
4657 && p0
->first_same_value
== p1
->first_same_value
)))
4658 return ((code
== EQ
|| code
== LE
|| code
== GE
4659 || code
== LEU
|| code
== GEU
)
4660 ? const_true_rtx
: const0_rtx
);
4662 /* If FOLDED_ARG0 is a register, see if the comparison we are
4663 doing now is either the same as we did before or the reverse
4664 (we only check the reverse if not floating-point). */
4665 else if (GET_CODE (folded_arg0
) == REG
)
4667 int qty
= reg_qty
[REGNO (folded_arg0
)];
4669 if (REGNO_QTY_VALID_P (REGNO (folded_arg0
))
4670 && (comparison_dominates_p (qty_comparison_code
[qty
], code
)
4671 || (comparison_dominates_p (qty_comparison_code
[qty
],
4672 reverse_condition (code
))
4673 && GET_MODE_CLASS (mode_arg0
) == MODE_INT
))
4674 && (rtx_equal_p (qty_comparison_const
[qty
], folded_arg1
)
4676 && rtx_equal_p (qty_comparison_const
[qty
],
4678 || (GET_CODE (folded_arg1
) == REG
4679 && (reg_qty
[REGNO (folded_arg1
)]
4680 == qty_comparison_qty
[qty
]))))
4681 return (comparison_dominates_p (qty_comparison_code
[qty
],
4683 ? const_true_rtx
: const0_rtx
);
4688 /* If we are comparing against zero, see if the first operand is
4689 equivalent to an IOR with a constant. If so, we may be able to
4690 determine the result of this comparison. */
4692 if (const_arg1
== const0_rtx
)
4694 rtx y
= lookup_as_function (folded_arg0
, IOR
);
4698 && (inner_const
= equiv_constant (XEXP (y
, 1))) != 0
4699 && GET_CODE (inner_const
) == CONST_INT
4700 && INTVAL (inner_const
) != 0)
4702 int sign_bitnum
= GET_MODE_BITSIZE (mode_arg0
) - 1;
4703 int has_sign
= (HOST_BITS_PER_INT
>= sign_bitnum
4704 && (INTVAL (inner_const
) & (1 << sign_bitnum
)));
4711 return const_true_rtx
;
4714 return const_true_rtx
;
4724 new = simplify_relational_operation (code
, mode_arg0
,
4725 const_arg0
? const_arg0
: folded_arg0
,
4726 const_arg1
? const_arg1
: folded_arg1
);
4734 /* If the second operand is a LABEL_REF, see if the first is a MINUS
4735 with that LABEL_REF as its second operand. If so, the result is
4736 the first operand of that MINUS. This handles switches with an
4737 ADDR_DIFF_VEC table. */
4738 if (const_arg1
&& GET_CODE (const_arg1
) == LABEL_REF
)
4740 rtx y
= lookup_as_function (folded_arg0
, MINUS
);
4742 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
4743 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg1
, 0))
4747 /* ... fall through ... */
4750 case SMIN
: case SMAX
: case UMIN
: case UMAX
:
4751 case IOR
: case AND
: case XOR
:
4752 case MULT
: case DIV
: case UDIV
:
4753 case ASHIFT
: case LSHIFTRT
: case ASHIFTRT
:
4754 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
4755 is known to be of similar form, we may be able to replace the
4756 operation with a combined operation. This may eliminate the
4757 intermediate operation if every use is simplified in this way.
4758 Note that the similar optimization done by combine.c only works
4759 if the intermediate operation's result has only one reference. */
4761 if (GET_CODE (folded_arg0
) == REG
4762 && const_arg1
&& GET_CODE (const_arg1
) == CONST_INT
)
4765 = (code
== ASHIFT
|| code
== ASHIFTRT
|| code
== LSHIFTRT
);
4766 rtx y
= lookup_as_function (folded_arg0
, code
);
4768 enum rtx_code associate_code
;
4772 || 0 == (inner_const
4773 = equiv_constant (fold_rtx (XEXP (y
, 1), 0)))
4774 || GET_CODE (inner_const
) != CONST_INT
4775 /* If we have compiled a statement like
4776 "if (x == (x & mask1))", and now are looking at
4777 "x & mask2", we will have a case where the first operand
4778 of Y is the same as our first operand. Unless we detect
4779 this case, an infinite loop will result. */
4780 || XEXP (y
, 0) == folded_arg0
)
4783 /* Don't associate these operations if they are a PLUS with the
4784 same constant and it is a power of two. These might be doable
4785 with a pre- or post-increment. Similarly for two subtracts of
4786 identical powers of two with post decrement. */
4788 if (code
== PLUS
&& INTVAL (const_arg1
) == INTVAL (inner_const
)
4790 #if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT)
4791 || exact_log2 (INTVAL (const_arg1
)) >= 0
4793 #if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT)
4794 || exact_log2 (- INTVAL (const_arg1
)) >= 0
4799 /* Compute the code used to compose the constants. For example,
4800 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
4803 = (code
== MULT
|| code
== DIV
|| code
== UDIV
? MULT
4804 : is_shift
|| code
== PLUS
|| code
== MINUS
? PLUS
: code
);
4806 new_const
= simplify_binary_operation (associate_code
, mode
,
4807 const_arg1
, inner_const
);
4812 /* If we are associating shift operations, don't let this
4813 produce a shift of larger than the object. This could
4814 occur when we following a sign-extend by a right shift on
4815 a machine that does a sign-extend as a pair of shifts. */
4817 if (is_shift
&& GET_CODE (new_const
) == CONST_INT
4818 && INTVAL (new_const
) > GET_MODE_BITSIZE (mode
))
4821 y
= copy_rtx (XEXP (y
, 0));
4823 /* If Y contains our first operand (the most common way this
4824 can happen is if Y is a MEM), we would do into an infinite
4825 loop if we tried to fold it. So don't in that case. */
4827 if (! reg_mentioned_p (folded_arg0
, y
))
4828 y
= fold_rtx (y
, insn
);
4830 new = simplify_binary_operation (code
, mode
, y
, new_const
);
4834 return gen_rtx (code
, mode
, y
, new_const
);
4838 new = simplify_binary_operation (code
, mode
,
4839 const_arg0
? const_arg0
: folded_arg0
,
4840 const_arg1
? const_arg1
: folded_arg1
);
4844 /* (lo_sum (high X) X) is simply X. */
4845 if (code
== LO_SUM
&& const_arg0
!= 0
4846 && GET_CODE (const_arg0
) == HIGH
4847 && rtx_equal_p (XEXP (const_arg0
, 0), const_arg1
))
4853 new = simplify_ternary_operation (code
, mode
, mode_arg0
,
4854 const_arg0
? const_arg0
: folded_arg0
,
4855 const_arg1
? const_arg1
: folded_arg1
,
4856 const_arg2
? const_arg2
: XEXP (x
, 2));
4860 return new ? new : x
;
4863 /* Return a constant value currently equivalent to X.
4864 Return 0 if we don't know one. */
4870 if (GET_CODE (x
) == REG
4871 && REGNO_QTY_VALID_P (REGNO (x
))
4872 && qty_const
[reg_qty
[REGNO (x
)]])
4873 x
= gen_lowpart_if_possible (GET_MODE (x
), qty_const
[reg_qty
[REGNO (x
)]]);
4875 if (x
!= 0 && CONSTANT_P (x
))
4878 /* If X is a MEM, try to fold it outside the context of any insn to see if
4879 it might be equivalent to a constant. That handles the case where it
4880 is a constant-pool reference. Then try to look it up in the hash table
4881 in case it is something whose value we have seen before. */
4883 if (GET_CODE (x
) == MEM
)
4885 struct table_elt
*elt
;
4887 x
= fold_rtx (x
, 0);
4891 elt
= lookup (x
, safe_hash (x
, GET_MODE (x
)) % NBUCKETS
, GET_MODE (x
));
4895 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
4896 if (elt
->is_const
&& CONSTANT_P (elt
->exp
))
4903 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
4904 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
4905 least-significant part of X.
4906 MODE specifies how big a part of X to return.
4908 If the requested operation cannot be done, 0 is returned.
4910 This is similar to gen_lowpart in emit-rtl.c. */
4913 gen_lowpart_if_possible (mode
, x
)
4914 enum machine_mode mode
;
4917 rtx result
= gen_lowpart_common (mode
, x
);
4921 else if (GET_CODE (x
) == MEM
)
4923 /* This is the only other case we handle. */
4924 register int offset
= 0;
4927 #if WORDS_BIG_ENDIAN
4928 offset
= (MAX (GET_MODE_SIZE (GET_MODE (x
)), UNITS_PER_WORD
)
4929 - MAX (GET_MODE_SIZE (mode
), UNITS_PER_WORD
));
4931 #if BYTES_BIG_ENDIAN
4932 /* Adjust the address so that the address-after-the-data
4934 offset
-= (MIN (UNITS_PER_WORD
, GET_MODE_SIZE (mode
))
4935 - MIN (UNITS_PER_WORD
, GET_MODE_SIZE (GET_MODE (x
))));
4937 new = gen_rtx (MEM
, mode
, plus_constant (XEXP (x
, 0), offset
));
4938 if (! memory_address_p (mode
, XEXP (new, 0)))
4940 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x
);
4941 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x
);
4942 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x
);
4949 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
4950 branch. It will be zero if not.
4952 In certain cases, this can cause us to add an equivalence. For example,
4953 if we are following the taken case of
4955 we can add the fact that `i' and '2' are now equivalent.
4957 In any case, we can record that this comparison was passed. If the same
4958 comparison is seen later, we will know its value. */
4961 record_jump_equiv (insn
, taken
)
4965 int cond_known_true
;
4967 enum machine_mode mode
;
4968 int reversed_nonequality
= 0;
4971 /* Ensure this is the right kind of insn. */
4972 if (! condjump_p (insn
) || simplejump_p (insn
))
4975 /* See if this jump condition is known true or false. */
4977 cond_known_true
= (XEXP (SET_SRC (PATTERN (insn
)), 2) == pc_rtx
);
4979 cond_known_true
= (XEXP (SET_SRC (PATTERN (insn
)), 1) == pc_rtx
);
4981 /* Get the type of comparison being done and the operands being compared.
4982 If we had to reverse a non-equality condition, record that fact so we
4983 know that it isn't valid for floating-point. */
4984 code
= GET_CODE (XEXP (SET_SRC (PATTERN (insn
)), 0));
4985 op0
= fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn
)), 0), 0), insn
);
4986 op1
= fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn
)), 0), 1), insn
);
4988 code
= find_comparison_args (code
, &op0
, &op1
);
4989 if (! cond_known_true
)
4991 reversed_nonequality
= (code
!= EQ
&& code
!= NE
);
4992 code
= reverse_condition (code
);
4995 /* The mode is the mode of the non-constant. */
4996 mode
= GET_MODE (op0
);
4997 if (mode
== VOIDmode
) mode
= GET_MODE (op1
);
4999 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
);
5002 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
5003 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
5004 Make any useful entries we can with that information. Called from
5005 above function and called recursively. */
5008 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
)
5010 enum machine_mode mode
;
5012 int reversed_nonequality
;
5014 int op0_hash_code
, op1_hash_code
;
5015 int op0_in_memory
, op0_in_struct
, op1_in_memory
, op1_in_struct
;
5016 struct table_elt
*op0_elt
, *op1_elt
;
5018 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
5019 we know that they are also equal in the smaller mode (this is also
5020 true for all smaller modes whether or not there is a SUBREG, but
5021 is not worth testing for with no SUBREG. */
5023 if (code
== EQ
&& GET_CODE (op0
) == SUBREG
5024 && GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
))))
5026 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
5027 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
5029 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
5030 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op1
, 0),
5031 reversed_nonequality
);
5034 if (code
== EQ
&& GET_CODE (op1
) == SUBREG
5035 && GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
))))
5037 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
5038 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
5040 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
5041 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op0
, 0),
5042 reversed_nonequality
);
5045 /* Similarly, if this is an NE comparison, and either is a SUBREG
5046 making a smaller mode, we know the whole thing is also NE. */
5048 if (code
== NE
&& GET_CODE (op0
) == SUBREG
5049 && subreg_lowpart_p (op0
)
5050 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
))))
5052 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
5053 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
5055 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
5056 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op1
, 0),
5057 reversed_nonequality
);
5060 if (code
== NE
&& GET_CODE (op1
) == SUBREG
5061 && subreg_lowpart_p (op1
)
5062 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
))))
5064 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
5065 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
5067 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
5068 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op0
, 0),
5069 reversed_nonequality
);
5072 /* Hash both operands. */
5075 hash_arg_in_memory
= 0;
5076 hash_arg_in_struct
= 0;
5077 op0_hash_code
= HASH (op0
, mode
);
5078 op0_in_memory
= hash_arg_in_memory
;
5079 op0_in_struct
= hash_arg_in_struct
;
5085 hash_arg_in_memory
= 0;
5086 hash_arg_in_struct
= 0;
5087 op1_hash_code
= HASH (op1
, mode
);
5088 op1_in_memory
= hash_arg_in_memory
;
5089 op1_in_struct
= hash_arg_in_struct
;
5094 /* Look up both operands. */
5095 op0_elt
= lookup (op0
, op0_hash_code
, mode
);
5096 op1_elt
= lookup (op1
, op1_hash_code
, mode
);
5098 /* If we aren't setting two things equal all we can do is save this
5102 /* If we reversed a floating-point comparison, if OP0 is not a
5103 register, or if OP1 is neither a register or constant, we can't
5106 if (GET_CODE (op1
) != REG
)
5107 op1
= equiv_constant (op1
);
5109 if ((reversed_nonequality
&& GET_MODE_CLASS (mode
) != MODE_INT
)
5110 || GET_CODE (op0
) != REG
|| op1
== 0)
5113 /* Put OP0 in the hash table if it isn't already. This gives it a
5114 new quantity number. */
5117 if (insert_regs (op0
, 0, 0))
5119 rehash_using_reg (op0
);
5120 op0_hash_code
= HASH (op0
, mode
);
5123 op0_elt
= insert (op0
, 0, op0_hash_code
, mode
);
5124 op0_elt
->in_memory
= op0_in_memory
;
5125 op0_elt
->in_struct
= op0_in_struct
;
5128 qty_comparison_code
[reg_qty
[REGNO (op0
)]] = code
;
5129 if (GET_CODE (op1
) == REG
)
5131 /* Put OP1 in the hash table so it gets a new quantity number. */
5134 if (insert_regs (op1
, 0, 0))
5136 rehash_using_reg (op1
);
5137 op1_hash_code
= HASH (op1
, mode
);
5140 op1_elt
= insert (op1
, 0, op1_hash_code
, mode
);
5141 op1_elt
->in_memory
= op1_in_memory
;
5142 op1_elt
->in_struct
= op1_in_struct
;
5145 qty_comparison_qty
[reg_qty
[REGNO (op0
)]] = reg_qty
[REGNO (op1
)];
5146 qty_comparison_const
[reg_qty
[REGNO (op0
)]] = 0;
5150 qty_comparison_qty
[reg_qty
[REGNO (op0
)]] = -1;
5151 qty_comparison_const
[reg_qty
[REGNO (op0
)]] = op1
;
5157 /* If both are equivalent, merge the two classes. Save this class for
5158 `cse_set_around_loop'. */
5159 if (op0_elt
&& op1_elt
)
5161 merge_equiv_classes (op0_elt
, op1_elt
);
5162 last_jump_equiv_class
= op0_elt
;
5165 /* For whichever side doesn't have an equivalence, make one. */
5168 if (insert_regs (op0
, op1_elt
, 0))
5170 rehash_using_reg (op0
);
5171 op0_hash_code
= HASH (op0
, mode
);
5174 op0_elt
= insert (op0
, op1_elt
, op0_hash_code
, mode
);
5175 op0_elt
->in_memory
= op0_in_memory
;
5176 op0_elt
->in_struct
= op0_in_struct
;
5177 last_jump_equiv_class
= op0_elt
;
5182 if (insert_regs (op1
, op0_elt
, 0))
5184 rehash_using_reg (op1
);
5185 op1_hash_code
= HASH (op1
, mode
);
5188 op1_elt
= insert (op1
, op0_elt
, op1_hash_code
, mode
);
5189 op1_elt
->in_memory
= op1_in_memory
;
5190 op1_elt
->in_struct
= op1_in_struct
;
5191 last_jump_equiv_class
= op1_elt
;
5195 /* CSE processing for one instruction.
5196 First simplify sources and addresses of all assignments
5197 in the instruction, using previously-computed equivalents values.
5198 Then install the new sources and destinations in the table
5199 of available values.
5201 If IN_LIBCALL_BLOCK is nonzero, don't record any equivalence made in
5204 /* Data on one SET contained in the instruction. */
5208 /* The SET rtx itself. */
5210 /* The SET_SRC of the rtx (the original value, if it is changing). */
5212 /* The hash-table element for the SET_SRC of the SET. */
5213 struct table_elt
*src_elt
;
5214 /* Hash code for the SET_SRC. */
5216 /* Hash code for the SET_DEST. */
5218 /* The SET_DEST, with SUBREG, etc., stripped. */
5220 /* Place where the pointer to the INNER_DEST was found. */
5221 rtx
*inner_dest_loc
;
5222 /* Nonzero if the SET_SRC is in memory. */
5224 /* Nonzero if the SET_SRC is in a structure. */
5226 /* Nonzero if the SET_SRC contains something
5227 whose value cannot be predicted and understood. */
5229 /* Original machine mode, in case it becomes a CONST_INT. */
5230 enum machine_mode mode
;
5231 /* A constant equivalent for SET_SRC, if any. */
5233 /* Hash code of constant equivalent for SET_SRC. */
5234 int src_const_hash_code
;
5235 /* Table entry for constant equivalent for SET_SRC, if any. */
5236 struct table_elt
*src_const_elt
;
5240 cse_insn (insn
, in_libcall_block
)
5242 int in_libcall_block
;
5244 register rtx x
= PATTERN (insn
);
5247 register int n_sets
= 0;
5249 /* Records what this insn does to set CC0. */
5250 rtx this_insn_cc0
= 0;
5251 enum machine_mode this_insn_cc0_mode
;
5252 struct write_data writes_memory
;
5253 static struct write_data init
= {0, 0, 0, 0};
5256 struct table_elt
*src_eqv_elt
= 0;
5257 int src_eqv_volatile
;
5258 int src_eqv_in_memory
;
5259 int src_eqv_in_struct
;
5260 int src_eqv_hash_code
;
5265 writes_memory
= init
;
5267 /* Find all the SETs and CLOBBERs in this instruction.
5268 Record all the SETs in the array `set' and count them.
5269 Also determine whether there is a CLOBBER that invalidates
5270 all memory references, or all references at varying addresses. */
5272 if (GET_CODE (x
) == SET
)
5274 sets
= (struct set
*) alloca (sizeof (struct set
));
5277 /* Ignore SETs that are unconditional jumps.
5278 They never need cse processing, so this does not hurt.
5279 The reason is not efficiency but rather
5280 so that we can test at the end for instructions
5281 that have been simplified to unconditional jumps
5282 and not be misled by unchanged instructions
5283 that were unconditional jumps to begin with. */
5284 if (SET_DEST (x
) == pc_rtx
5285 && GET_CODE (SET_SRC (x
)) == LABEL_REF
)
5288 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
5289 The hard function value register is used only once, to copy to
5290 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
5291 Ensure we invalidate the destination register. On the 80386 no
5292 other code would invalidate it since it is a fixed_reg. */
5294 else if (GET_CODE (SET_SRC (x
)) == CALL
)
5296 canon_reg (SET_SRC (x
), insn
);
5297 fold_rtx (SET_SRC (x
), insn
);
5298 invalidate (SET_DEST (x
));
5303 else if (GET_CODE (x
) == PARALLEL
)
5305 register int lim
= XVECLEN (x
, 0);
5307 sets
= (struct set
*) alloca (lim
* sizeof (struct set
));
5309 /* Find all regs explicitly clobbered in this insn,
5310 and ensure they are not replaced with any other regs
5311 elsewhere in this insn.
5312 When a reg that is clobbered is also used for input,
5313 we should presume that that is for a reason,
5314 and we should not substitute some other register
5315 which is not supposed to be clobbered.
5316 Therefore, this loop cannot be merged into the one below
5317 because a CALL may precede a CLOBBER and refer to the
5318 value clobbered. We must not let a canonicalization do
5319 anything in that case. */
5320 for (i
= 0; i
< lim
; i
++)
5322 register rtx y
= XVECEXP (x
, 0, i
);
5323 if (GET_CODE (y
) == CLOBBER
5324 && (GET_CODE (XEXP (y
, 0)) == REG
5325 || GET_CODE (XEXP (y
, 0)) == SUBREG
))
5326 invalidate (XEXP (y
, 0));
5329 for (i
= 0; i
< lim
; i
++)
5331 register rtx y
= XVECEXP (x
, 0, i
);
5332 if (GET_CODE (y
) == SET
)
5334 /* As above, we ignore unconditional jumps and call-insns. */
5335 if (GET_CODE (SET_SRC (y
)) == CALL
)
5337 canon_reg (SET_SRC (y
), insn
);
5338 fold_rtx (SET_SRC (y
), insn
);
5339 invalidate (SET_DEST (y
));
5341 else if (SET_DEST (y
) == pc_rtx
5342 && GET_CODE (SET_SRC (y
)) == LABEL_REF
)
5345 sets
[n_sets
++].rtl
= y
;
5347 else if (GET_CODE (y
) == CLOBBER
)
5349 /* If we clobber memory, take note of that,
5350 and canon the address.
5351 This does nothing when a register is clobbered
5352 because we have already invalidated the reg. */
5353 if (GET_CODE (XEXP (y
, 0)) == MEM
)
5355 canon_reg (XEXP (y
, 0), 0);
5356 note_mem_written (XEXP (y
, 0), &writes_memory
);
5359 else if (GET_CODE (y
) == USE
5360 && ! (GET_CODE (XEXP (y
, 0)) == REG
5361 && REGNO (XEXP (y
, 0)) < FIRST_PSEUDO_REGISTER
))
5363 else if (GET_CODE (y
) == CALL
)
5365 canon_reg (y
, insn
);
5370 else if (GET_CODE (x
) == CLOBBER
)
5372 if (GET_CODE (XEXP (x
, 0)) == MEM
)
5374 canon_reg (XEXP (x
, 0), 0);
5375 note_mem_written (XEXP (x
, 0), &writes_memory
);
5379 /* Canonicalize a USE of a pseudo register or memory location. */
5380 else if (GET_CODE (x
) == USE
5381 && ! (GET_CODE (XEXP (x
, 0)) == REG
5382 && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
))
5383 canon_reg (XEXP (x
, 0), 0);
5384 else if (GET_CODE (x
) == CALL
)
5386 canon_reg (x
, insn
);
5390 if (n_sets
== 1 && REG_NOTES (insn
) != 0)
5392 /* Store the equivalent value in SRC_EQV, if different. */
5393 rtx tem
= find_reg_note (insn
, REG_EQUAL
, 0);
5395 if (tem
&& ! rtx_equal_p (XEXP (tem
, 0), SET_SRC (sets
[0].rtl
)))
5396 src_eqv
= canon_reg (XEXP (tem
, 0), 0);
5399 /* Canonicalize sources and addresses of destinations.
5400 We do this in a separate pass to avoid problems when a MATCH_DUP is
5401 present in the insn pattern. In that case, we want to ensure that
5402 we don't break the duplicate nature of the pattern. So we will replace
5403 both operands at the same time. Otherwise, we would fail to find an
5404 equivalent substitution in the loop calling validate_change below.
5405 (We also speed up that loop when a canonicalization was done since
5406 recog_memoized need not be called for just a canonicalization unless
5407 a pseudo register is being replaced by a hard reg of vice versa.)
5409 We used to suppress canonicalization of DEST if it appears in SRC,
5410 but we don't do this any more.
5412 ??? The way this code is written now, if we have a MATCH_DUP between
5413 two operands that are pseudos and we would want to canonicalize them
5414 to a hard register, we won't do that. The only time this would happen
5415 is if the hard reg was a fixed register, and this should be rare.
5417 ??? This won't work if there is a MATCH_DUP between an input and an
5418 output, but these never worked and must be declared invalid. */
5420 for (i
= 0; i
< n_sets
; i
++)
5422 rtx dest
= SET_DEST (sets
[i
].rtl
);
5423 rtx src
= SET_SRC (sets
[i
].rtl
);
5424 rtx
new = canon_reg (src
, insn
);
5426 if (GET_CODE (new) == REG
&& GET_CODE (src
) == REG
5427 && ((REGNO (new) < FIRST_PSEUDO_REGISTER
)
5428 != (REGNO (src
) < FIRST_PSEUDO_REGISTER
)))
5429 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 0);
5431 SET_SRC (sets
[i
].rtl
) = new;
5433 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
5435 validate_change (insn
, &XEXP (dest
, 1),
5436 canon_reg (XEXP (dest
, 1), insn
), 0);
5437 validate_change (insn
, &XEXP (dest
, 2),
5438 canon_reg (XEXP (dest
, 2), insn
), 0);
5441 while (GET_CODE (dest
) == SUBREG
|| GET_CODE (dest
) == STRICT_LOW_PART
5442 || GET_CODE (dest
) == ZERO_EXTRACT
5443 || GET_CODE (dest
) == SIGN_EXTRACT
)
5444 dest
= XEXP (dest
, 0);
5446 if (GET_CODE (dest
) == MEM
)
5447 canon_reg (dest
, insn
);
5450 /* Set sets[i].src_elt to the class each source belongs to.
5451 Detect assignments from or to volatile things
5452 and set set[i] to zero so they will be ignored
5453 in the rest of this function.
5455 Nothing in this loop changes the hash table or the register chains. */
5457 for (i
= 0; i
< n_sets
; i
++)
5459 register rtx src
, dest
;
5460 register rtx src_folded
;
5461 register struct table_elt
*elt
= 0, *p
;
5462 enum machine_mode mode
;
5465 rtx src_related
= 0;
5466 struct table_elt
*src_const_elt
= 0;
5467 int src_cost
= 10000, src_eqv_cost
= 10000, src_folded_cost
= 10000;
5468 int src_related_cost
= 10000, src_elt_cost
= 10000;
5469 /* Set non-zero if we need to call force_const_mem on with the
5470 contents of src_folded before using it. */
5471 int src_folded_force_flag
= 0;
5473 dest
= SET_DEST (sets
[i
].rtl
);
5474 src
= SET_SRC (sets
[i
].rtl
);
5476 /* If SRC is a constant that has no machine mode,
5477 hash it with the destination's machine mode.
5478 This way we can keep different modes separate. */
5480 mode
= GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
5481 sets
[i
].mode
= mode
;
5485 enum machine_mode eqvmode
= mode
;
5486 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5487 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
5489 hash_arg_in_memory
= 0;
5490 hash_arg_in_struct
= 0;
5491 src_eqv
= fold_rtx (src_eqv
, insn
);
5492 src_eqv_hash_code
= HASH (src_eqv
, eqvmode
);
5494 /* Find the equivalence class for the equivalent expression. */
5497 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash_code
, eqvmode
);
5499 src_eqv_volatile
= do_not_record
;
5500 src_eqv_in_memory
= hash_arg_in_memory
;
5501 src_eqv_in_struct
= hash_arg_in_struct
;
5504 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
5505 value of the INNER register, not the destination. So it is not
5506 a legal substitution for the source. But save it for later. */
5507 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5510 src_eqv_here
= src_eqv
;
5512 /* Simplify and foldable subexpressions in SRC. Then get the fully-
5513 simplified result, which may not necessarily be valid. */
5514 src_folded
= fold_rtx (src
, insn
);
5516 /* If storing a constant in a bitfield, pre-truncate the constant
5517 so we will be able to record it later. */
5518 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
5519 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
5521 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
5523 if (GET_CODE (src
) == CONST_INT
5524 && GET_CODE (width
) == CONST_INT
5525 && INTVAL (width
) < HOST_BITS_PER_INT
5526 && (INTVAL (src
) & ((-1) << INTVAL (width
))))
5527 src_folded
= gen_rtx (CONST_INT
, VOIDmode
,
5528 INTVAL (src
) & ((1 << INTVAL (width
)) - 1));
5531 /* Compute SRC's hash code, and also notice if it
5532 should not be recorded at all. In that case,
5533 prevent any further processing of this assignment. */
5535 hash_arg_in_memory
= 0;
5536 hash_arg_in_struct
= 0;
5539 sets
[i
].src_hash_code
= HASH (src
, mode
);
5540 sets
[i
].src_volatile
= do_not_record
;
5541 sets
[i
].src_in_memory
= hash_arg_in_memory
;
5542 sets
[i
].src_in_struct
= hash_arg_in_struct
;
5544 /* If source is a perverse subreg (such as QI treated as an SI),
5545 treat it as volatile. It may do the work of an SI in one context
5546 where the extra bits are not being used, but cannot replace an SI
5548 if (GET_CODE (src
) == SUBREG
5549 && (GET_MODE_SIZE (GET_MODE (src
))
5550 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))))
5551 sets
[i
].src_volatile
= 1;
5553 /* Locate all possible equivalent forms for SRC. Try to replace
5554 SRC in the insn with each cheaper equivalent.
5556 We have the following types of equivalents: SRC itself, a folded
5557 version, a value given in a REG_EQUAL note, or a value related
5560 Each of these equivalents may be part of an additional class
5561 of equivalents (if more than one is in the table, they must be in
5562 the same class; we check for this).
5564 If the source is volatile, we don't do any table lookups.
5566 We note any constant equivalent for possible later use in a
5569 if (!sets
[i
].src_volatile
)
5570 elt
= lookup (src
, sets
[i
].src_hash_code
, mode
);
5572 sets
[i
].src_elt
= elt
;
5574 if (elt
&& src_eqv_here
&& src_eqv_elt
)
5576 if (elt
->first_same_value
!= src_eqv_elt
->first_same_value
)
5578 /* The REG_EQUAL is indicating that two formerly distinct
5579 classes are now equivalent. So merge them. */
5580 merge_equiv_classes (elt
, src_eqv_elt
);
5581 src_eqv_hash_code
= HASH (src_eqv
, elt
->mode
);
5582 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash_code
, elt
->mode
);
5588 else if (src_eqv_elt
)
5591 /* Try to find a constant somewhere and record it in `src_const'.
5592 Record its table element, if any, in `src_const_elt'. Look in
5593 any known equivalences first. (If the constant is not in the
5594 table, also set `sets[i].src_const_hash_code'). */
5596 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
5600 src_const_elt
= elt
;
5605 && (CONSTANT_P (src_folded
)
5606 /* Consider (minus (label_ref L1) (label_ref L2)) as
5607 "constant" here so we will record it. This allows us
5608 to fold switch statements when an ADDR_DIFF_VEC is used. */
5609 || (GET_CODE (src_folded
) == MINUS
5610 && GET_CODE (XEXP (src_folded
, 0)) == LABEL_REF
5611 && GET_CODE (XEXP (src_folded
, 1)) == LABEL_REF
)))
5612 src_const
= src_folded
, src_const_elt
= elt
;
5613 else if (src_const
== 0 && src_eqv_here
&& CONSTANT_P (src_eqv_here
))
5614 src_const
= src_eqv_here
, src_const_elt
= src_eqv_elt
;
5616 /* If we don't know if the constant is in the table, get its
5617 hash code and look it up. */
5618 if (src_const
&& src_const_elt
== 0)
5620 sets
[i
].src_const_hash_code
= HASH (src_const
, mode
);
5621 src_const_elt
= lookup (src_const
, sets
[i
].src_const_hash_code
,
5625 sets
[i
].src_const
= src_const
;
5626 sets
[i
].src_const_elt
= src_const_elt
;
5628 /* If the constant and our source are both in the table, mark them as
5629 equivalent. Otherwise, if a constant is in the table but the source
5630 isn't, set ELT to it. */
5631 if (src_const_elt
&& elt
5632 && src_const_elt
->first_same_value
!= elt
->first_same_value
)
5633 merge_equiv_classes (elt
, src_const_elt
);
5634 else if (src_const_elt
&& elt
== 0)
5635 elt
= src_const_elt
;
5637 /* See if there is a register linearly related to a constant
5638 equivalent of SRC. */
5640 && (GET_CODE (src_const
) == CONST
5641 || (src_const_elt
&& src_const_elt
->related_value
!= 0)))
5643 src_related
= use_related_value (src_const
, src_const_elt
);
5646 struct table_elt
*src_related_elt
5647 = lookup (src_related
, HASH (src_related
, mode
), mode
);
5648 if (src_related_elt
&& elt
)
5650 if (elt
->first_same_value
5651 != src_related_elt
->first_same_value
)
5652 /* This can occur when we previously saw a CONST
5653 involving a SYMBOL_REF and then see the SYMBOL_REF
5654 twice. Merge the involved classes. */
5655 merge_equiv_classes (elt
, src_related_elt
);
5658 src_related_elt
= 0;
5660 else if (src_related_elt
&& elt
== 0)
5661 elt
= src_related_elt
;
5665 /* Another possibility is that we have an AND with a constant in
5666 a mode narrower than a word. If so, it might have been generated
5667 as part of an "if" which would narrow the AND. If we already
5668 have done the AND in a wider mode, we can use a SUBREG of that
5671 if (flag_expensive_optimizations
&& ! src_related
5672 && GET_CODE (src
) == AND
&& GET_CODE (XEXP (src
, 1)) == CONST_INT
5673 && GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
5675 enum machine_mode tmode
;
5676 rtx new_and
= gen_rtx (AND
, VOIDmode
, 0, XEXP (src
, 1));
5678 for (tmode
= GET_MODE_WIDER_MODE (mode
);
5679 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
5680 tmode
= GET_MODE_WIDER_MODE (tmode
))
5682 rtx inner
= gen_lowpart_if_possible (tmode
, XEXP (src
, 0));
5683 struct table_elt
*larger_elt
;
5687 PUT_MODE (new_and
, tmode
);
5688 XEXP (new_and
, 0) = inner
;
5689 larger_elt
= lookup (new_and
, HASH (new_and
, tmode
), tmode
);
5690 if (larger_elt
== 0)
5693 for (larger_elt
= larger_elt
->first_same_value
;
5694 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
5695 if (GET_CODE (larger_elt
->exp
) == REG
)
5698 = gen_lowpart_if_possible (mode
, larger_elt
->exp
);
5708 if (src
== src_folded
)
5711 /* At this point, ELT, if non-zero, points to a class of expressions
5712 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
5713 and SRC_RELATED, if non-zero, each contain additional equivalent
5714 expressions. Prune these latter expressions by deleting expressions
5715 already in the equivalence class.
5717 Check for an equivalent identical to the destination. If found,
5718 this is the preferred equivalent since it will likely lead to
5719 elimination of the insn. Indicate this by placing it in
5722 if (elt
) elt
= elt
->first_same_value
;
5723 for (p
= elt
; p
; p
= p
->next_same_value
)
5725 enum rtx_code code
= GET_CODE (p
->exp
);
5727 /* If the expression is not valid, ignore it. Then we do not
5728 have to check for validity below. In most cases, we can use
5729 `rtx_equal_p', since canonicalization has already been done. */
5730 if (code
!= REG
&& ! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
5733 if (src
&& GET_CODE (src
) == code
&& rtx_equal_p (src
, p
->exp
))
5735 else if (src_folded
&& GET_CODE (src_folded
) == code
5736 && rtx_equal_p (src_folded
, p
->exp
))
5738 else if (src_eqv_here
&& GET_CODE (src_eqv_here
) == code
5739 && rtx_equal_p (src_eqv_here
, p
->exp
))
5741 else if (src_related
&& GET_CODE (src_related
) == code
5742 && rtx_equal_p (src_related
, p
->exp
))
5745 /* This is the same as the destination of the insns, we want
5746 to prefer it. Copy it to src_related. The code below will
5747 then give it a negative cost. */
5748 if (GET_CODE (dest
) == code
&& rtx_equal_p (p
->exp
, dest
))
5753 /* Find the cheapest valid equivalent, trying all the available
5754 possibilities. Prefer items not in the hash table to ones
5755 that are when they are equal cost. Note that we can never
5756 worsen an insn as the current contents will also succeed.
5757 If we find an equivalent identical to the destination, use it as best,
5758 since this insn will probably be eliminated in that case. */
5761 if (rtx_equal_p (src
, dest
))
5764 src_cost
= COST (src
);
5769 if (rtx_equal_p (src_eqv_here
, dest
))
5772 src_eqv_cost
= COST (src_eqv_here
);
5777 if (rtx_equal_p (src_folded
, dest
))
5778 src_folded_cost
= -1;
5780 src_folded_cost
= COST (src_folded
);
5785 if (rtx_equal_p (src_related
, dest
))
5786 src_related_cost
= -1;
5788 src_related_cost
= COST (src_related
);
5791 /* If this was an indirect jump insn, a known label will really be
5792 cheaper even though it looks more expensive. */
5793 if (dest
== pc_rtx
&& src_const
&& GET_CODE (src_const
) == LABEL_REF
)
5794 src_folded
= src_const
, src_folded_cost
= -1;
5796 /* Terminate loop when replacement made. This must terminate since
5797 the current contents will be tested and will always be valid. */
5802 /* Skip invalid entries. */
5803 while (elt
&& GET_CODE (elt
->exp
) != REG
5804 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
5805 elt
= elt
->next_same_value
;
5807 if (elt
) src_elt_cost
= elt
->cost
;
5809 /* Find cheapest and skip it for the next time. For items
5810 of equal cost, use this order:
5811 src_folded, src, src_eqv, src_related and hash table entry. */
5812 if (src_folded_cost
<= src_cost
5813 && src_folded_cost
<= src_eqv_cost
5814 && src_folded_cost
<= src_related_cost
5815 && src_folded_cost
<= src_elt_cost
)
5817 trial
= src_folded
, src_folded_cost
= 10000;
5818 if (src_folded_force_flag
)
5819 trial
= force_const_mem (mode
, trial
);
5821 else if (src_cost
<= src_eqv_cost
5822 && src_cost
<= src_related_cost
5823 && src_cost
<= src_elt_cost
)
5824 trial
= src
, src_cost
= 10000;
5825 else if (src_eqv_cost
<= src_related_cost
5826 && src_eqv_cost
<= src_elt_cost
)
5827 trial
= src_eqv_here
, src_eqv_cost
= 10000;
5828 else if (src_related_cost
<= src_elt_cost
)
5829 trial
= src_related
, src_related_cost
= 10000;
5832 trial
= copy_rtx (elt
->exp
);
5833 elt
= elt
->next_same_value
;
5834 src_elt_cost
= 10000;
5837 /* We don't normally have an insn matching (set (pc) (pc)), so
5838 check for this separately here. We will delete such an
5841 Tablejump insns contain a USE of the table, so simply replacing
5842 the operand with the constant won't match. This is simply an
5843 unconditional branch, however, and is therefore valid. Just
5844 insert the substitution here and we will delete and re-emit
5847 if (n_sets
== 1 && dest
== pc_rtx
5849 || (GET_CODE (trial
) == LABEL_REF
5850 && ! condjump_p (insn
))))
5852 /* If TRIAL is a label in front of a jump table, we are
5853 really falling through the switch (this is how casesi
5854 insns work), so we must branch around the table. */
5855 if (GET_CODE (trial
) == CODE_LABEL
5856 && NEXT_INSN (trial
) != 0
5857 && GET_CODE (NEXT_INSN (trial
)) == JUMP_INSN
5858 && (GET_CODE (PATTERN (NEXT_INSN (trial
))) == ADDR_DIFF_VEC
5859 || GET_CODE (PATTERN (NEXT_INSN (trial
))) == ADDR_VEC
))
5861 trial
= gen_rtx (LABEL_REF
, Pmode
, get_label_after (trial
));
5863 SET_SRC (sets
[i
].rtl
) = trial
;
5867 /* Look for a substitution that makes a valid insn. */
5868 else if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), trial
, 0))
5870 SET_SRC (sets
[i
].rtl
) = canon_reg (SET_SRC (sets
[i
].rtl
), insn
);
5874 /* If we previously found constant pool entries for
5875 constants and this is a constant, try making a
5876 pool entry. Put it in src_folded unless we already have done
5877 this since that is where it likely came from. */
5879 else if (constant_pool_entries_cost
5880 && CONSTANT_P (trial
)
5881 && (src_folded
== 0 || GET_CODE (src_folded
) != MEM
)
5882 && GET_MODE_CLASS (mode
) != MODE_CC
)
5884 src_folded_force_flag
= 1;
5886 src_folded_cost
= constant_pool_entries_cost
;
5890 src
= SET_SRC (sets
[i
].rtl
);
5892 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
5893 However, there is an important exception: If both are registers
5894 that are not the head of their equivalence class, replace SET_SRC
5895 with the head of the class. If we do not do this, we will have
5896 both registers live over a portion of the basic block. This way,
5897 their lifetimes will likely abut instead of overlapping. */
5898 if (GET_CODE (dest
) == REG
5899 && REGNO_QTY_VALID_P (REGNO (dest
))
5900 && qty_mode
[reg_qty
[REGNO (dest
)]] == GET_MODE (dest
)
5901 && qty_first_reg
[reg_qty
[REGNO (dest
)]] != REGNO (dest
)
5902 && GET_CODE (src
) == REG
&& REGNO (src
) == REGNO (dest
)
5903 /* Don't do this if the original insn had a hard reg as
5905 && (GET_CODE (sets
[i
].src
) != REG
5906 || REGNO (sets
[i
].src
) >= FIRST_PSEUDO_REGISTER
))
5907 /* We can't call canon_reg here because it won't do anything if
5908 SRC is a hard register. */
5910 int first
= qty_first_reg
[reg_qty
[REGNO (src
)]];
5912 src
= SET_SRC (sets
[i
].rtl
)
5913 = first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
5914 : gen_rtx (REG
, GET_MODE (src
), first
);
5916 /* If we had a constant that is cheaper than what we are now
5917 setting SRC to, use that constant. We ignored it when we
5918 thought we could make this into a no-op. */
5919 if (src_const
&& COST (src_const
) < COST (src
)
5920 && validate_change (insn
, &SET_SRC (sets
[i
].rtl
), src_const
, 0))
5924 /* If we made a change, recompute SRC values. */
5925 if (src
!= sets
[i
].src
)
5928 hash_arg_in_memory
= 0;
5929 hash_arg_in_struct
= 0;
5931 sets
[i
].src_hash_code
= HASH (src
, mode
);
5932 sets
[i
].src_volatile
= do_not_record
;
5933 sets
[i
].src_in_memory
= hash_arg_in_memory
;
5934 sets
[i
].src_in_struct
= hash_arg_in_struct
;
5935 sets
[i
].src_elt
= lookup (src
, sets
[i
].src_hash_code
, mode
);
5938 /* If this is a single SET, we are setting a register, and we have an
5939 equivalent constant, we want to add a REG_NOTE. We don't want
5940 to write a REG_EQUAL note for a constant pseudo since verifying that
5941 that pseudo hasn't been eliminated is a pain. Such a note also
5942 won't help anything. */
5943 if (n_sets
== 1 && src_const
&& GET_CODE (dest
) == REG
5944 && GET_CODE (src_const
) != REG
)
5946 rtx tem
= find_reg_note (insn
, REG_EQUAL
, 0);
5948 /* Record the actual constant value in a REG_EQUAL note, making
5949 a new one if one does not already exist. */
5951 XEXP (tem
, 0) = src_const
;
5953 REG_NOTES (insn
) = gen_rtx (EXPR_LIST
, REG_EQUAL
,
5954 src_const
, REG_NOTES (insn
));
5956 /* If storing a constant value in a register that
5957 previously held the constant value 0,
5958 record this fact with a REG_WAS_0 note on this insn.
5960 Note that the *register* is required to have previously held 0,
5961 not just any register in the quantity and we must point to the
5962 insn that set that register to zero.
5964 Rather than track each register individually, we just see if
5965 the last set for this quantity was for this register. */
5967 if (REGNO_QTY_VALID_P (REGNO (dest
))
5968 && qty_const
[reg_qty
[REGNO (dest
)]] == const0_rtx
)
5970 /* See if we previously had a REG_WAS_0 note. */
5971 rtx note
= find_reg_note (insn
, REG_WAS_0
, 0);
5972 rtx const_insn
= qty_const_insn
[reg_qty
[REGNO (dest
)]];
5974 if ((tem
= single_set (const_insn
)) != 0
5975 && rtx_equal_p (SET_DEST (tem
), dest
))
5978 XEXP (note
, 0) = const_insn
;
5980 REG_NOTES (insn
) = gen_rtx (INSN_LIST
, REG_WAS_0
,
5981 const_insn
, REG_NOTES (insn
));
5986 /* Now deal with the destination. */
5988 sets
[i
].inner_dest_loc
= &SET_DEST (sets
[0].rtl
);
5990 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
5991 to the MEM or REG within it. */
5992 while (GET_CODE (dest
) == SIGN_EXTRACT
5993 || GET_CODE (dest
) == ZERO_EXTRACT
5994 || GET_CODE (dest
) == SUBREG
5995 || GET_CODE (dest
) == STRICT_LOW_PART
)
5997 sets
[i
].inner_dest_loc
= &XEXP (dest
, 0);
5998 dest
= XEXP (dest
, 0);
6001 sets
[i
].inner_dest
= dest
;
6003 if (GET_CODE (dest
) == MEM
)
6005 dest
= fold_rtx (dest
, insn
);
6007 /* Decide whether we invalidate everything in memory,
6008 or just things at non-fixed places.
6009 Writing a large aggregate must invalidate everything
6010 because we don't know how long it is. */
6011 note_mem_written (dest
, &writes_memory
);
6014 /* Compute the hash code of the destination now,
6015 before the effects of this instruction are recorded,
6016 since the register values used in the address computation
6017 are those before this instruction. */
6018 sets
[i
].dest_hash_code
= HASH (dest
, mode
);
6020 /* Don't enter a bit-field in the hash table
6021 because the value in it after the store
6022 may not equal what was stored, due to truncation. */
6024 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
6025 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
6027 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
6029 if (src_const
!= 0 && GET_CODE (src_const
) == CONST_INT
6030 && GET_CODE (width
) == CONST_INT
6031 && INTVAL (width
) < HOST_BITS_PER_INT
6032 && ! (INTVAL (src_const
) & ((-1) << INTVAL (width
))))
6033 /* Exception: if the value is constant,
6034 and it won't be truncated, record it. */
6038 /* This is chosen so that the destination will be invalidated
6039 but no new value will be recorded.
6040 We must invalidate because sometimes constant
6041 values can be recorded for bitfields. */
6042 sets
[i
].src_elt
= 0;
6043 sets
[i
].src_volatile
= 1;
6049 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
6051 else if (n_sets
== 1 && dest
== pc_rtx
&& src
== pc_rtx
)
6053 PUT_CODE (insn
, NOTE
);
6054 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
6055 NOTE_SOURCE_FILE (insn
) = 0;
6056 cse_jumps_altered
= 1;
6057 /* One less use of the label this insn used to jump to. */
6058 --LABEL_NUSES (JUMP_LABEL (insn
));
6059 /* No more processing for this set. */
6063 /* If this SET is now setting PC to a label, we know it used to
6064 be a conditional or computed branch. So we see if we can follow
6065 it. If it was a computed branch, delete it and re-emit. */
6066 else if (dest
== pc_rtx
&& GET_CODE (src
) == LABEL_REF
)
6070 /* If this is not in the format for a simple branch and
6071 we are the only SET in it, re-emit it. */
6072 if (! simplejump_p (insn
) && n_sets
== 1)
6074 rtx
new = emit_jump_insn_before (gen_jump (XEXP (src
, 0)), insn
);
6075 JUMP_LABEL (new) = XEXP (src
, 0);
6076 LABEL_NUSES (XEXP (src
, 0))++;
6081 /* Now that we've converted this jump to an unconditional jump,
6082 there is dead code after it. Delete the dead code until we
6083 reach a BARRIER, the end of the function, or a label. Do
6084 not delete NOTEs except for NOTE_INSN_DELETED since later
6085 phases assume these notes are retained. */
6089 while (NEXT_INSN (p
) != 0
6090 && GET_CODE (NEXT_INSN (p
)) != BARRIER
6091 && GET_CODE (NEXT_INSN (p
)) != CODE_LABEL
)
6093 if (GET_CODE (NEXT_INSN (p
)) != NOTE
6094 || NOTE_LINE_NUMBER (NEXT_INSN (p
)) == NOTE_INSN_DELETED
)
6095 delete_insn (NEXT_INSN (p
));
6100 /* If we don't have a BARRIER immediately after INSN, put one there.
6101 Much code assumes that there are no NOTEs between a JUMP_INSN and
6104 if (NEXT_INSN (insn
) == 0
6105 || GET_CODE (NEXT_INSN (insn
)) != BARRIER
)
6106 emit_barrier_after (insn
);
6108 /* We might have two BARRIERs separated by notes. Delete the second
6111 if (p
!= insn
&& NEXT_INSN (p
) != 0
6112 && GET_CODE (NEXT_INSN (p
)) == BARRIER
)
6113 delete_insn (NEXT_INSN (p
));
6115 cse_jumps_altered
= 1;
6119 /* If destination is volatile, invalidate it and then do no further
6120 processing for this assignment. */
6122 else if (do_not_record
)
6124 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
6125 || GET_CODE (dest
) == MEM
)
6130 if (sets
[i
].rtl
!= 0 && dest
!= SET_DEST (sets
[i
].rtl
))
6131 sets
[i
].dest_hash_code
= HASH (SET_DEST (sets
[i
].rtl
), mode
);
6134 /* If setting CC0, record what it was set to, or a constant, if it
6135 is equivalent to a constant. If it is being set to a floating-point
6136 value, make a COMPARE with the appropriate constant of 0. If we
6137 don't do this, later code can interpret this as a test against
6138 const0_rtx, which can cause problems if we try to put it into an
6139 insn as a floating-point operand. */
6140 if (dest
== cc0_rtx
)
6142 this_insn_cc0
= src_const
&& mode
!= VOIDmode
? src_const
: src
;
6143 this_insn_cc0_mode
= mode
;
6144 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
6145 this_insn_cc0
= gen_rtx (COMPARE
, VOIDmode
, this_insn_cc0
,
6151 /* Now enter all non-volatile source expressions in the hash table
6152 if they are not already present.
6153 Record their equivalence classes in src_elt.
6154 This way we can insert the corresponding destinations into
6155 the same classes even if the actual sources are no longer in them
6156 (having been invalidated). */
6158 if (src_eqv
&& src_eqv_elt
== 0 && sets
[0].rtl
!= 0 && ! src_eqv_volatile
6159 && ! rtx_equal_p (src_eqv
, SET_DEST (sets
[0].rtl
)))
6161 register struct table_elt
*elt
;
6162 register struct table_elt
*classp
= sets
[0].src_elt
;
6163 rtx dest
= SET_DEST (sets
[0].rtl
);
6164 enum machine_mode eqvmode
= GET_MODE (dest
);
6166 if (GET_CODE (dest
) == STRICT_LOW_PART
)
6168 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
6171 if (insert_regs (src_eqv
, classp
, 0))
6172 src_eqv_hash_code
= HASH (src_eqv
, eqvmode
);
6173 elt
= insert (src_eqv
, classp
, src_eqv_hash_code
, eqvmode
);
6174 elt
->in_memory
= src_eqv_in_memory
;
6175 elt
->in_struct
= src_eqv_in_struct
;
6179 for (i
= 0; i
< n_sets
; i
++)
6180 if (sets
[i
].rtl
&& ! sets
[i
].src_volatile
6181 && ! rtx_equal_p (SET_SRC (sets
[i
].rtl
), SET_DEST (sets
[i
].rtl
)))
6183 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == STRICT_LOW_PART
)
6185 /* REG_EQUAL in setting a STRICT_LOW_PART
6186 gives an equivalent for the entire destination register,
6187 not just for the subreg being stored in now.
6188 This is a more interesting equivalence, so we arrange later
6189 to treat the entire reg as the destination. */
6190 sets
[i
].src_elt
= src_eqv_elt
;
6191 sets
[i
].src_hash_code
= src_eqv_hash_code
;
6195 /* Insert source and constant equivalent into hash table, if not
6197 register struct table_elt
*classp
= src_eqv_elt
;
6198 register rtx src
= sets
[i
].src
;
6199 register rtx dest
= SET_DEST (sets
[i
].rtl
);
6200 enum machine_mode mode
6201 = GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
6203 if (sets
[i
].src_elt
== 0)
6205 register struct table_elt
*elt
;
6207 /* Note that these insert_regs calls cannot remove
6208 any of the src_elt's, because they would have failed to
6209 match if not still valid. */
6210 if (insert_regs (src
, classp
, 0))
6211 sets
[i
].src_hash_code
= HASH (src
, mode
);
6212 elt
= insert (src
, classp
, sets
[i
].src_hash_code
, mode
);
6213 elt
->in_memory
= sets
[i
].src_in_memory
;
6214 elt
->in_struct
= sets
[i
].src_in_struct
;
6215 sets
[i
].src_elt
= classp
= elt
;
6218 if (sets
[i
].src_const
&& sets
[i
].src_const_elt
== 0
6219 && src
!= sets
[i
].src_const
6220 && ! rtx_equal_p (sets
[i
].src_const
, src
))
6221 sets
[i
].src_elt
= insert (sets
[i
].src_const
, classp
,
6222 sets
[i
].src_const_hash_code
, mode
);
6225 else if (sets
[i
].src_elt
== 0)
6226 /* If we did not insert the source into the hash table (e.g., it was
6227 volatile), note the equivalence class for the REG_EQUAL value, if any,
6228 so that the destination goes into that class. */
6229 sets
[i
].src_elt
= src_eqv_elt
;
6231 invalidate_from_clobbers (&writes_memory
, x
);
6232 /* Memory, and some registers, are invalidate by subroutine calls. */
6233 if (GET_CODE (insn
) == CALL_INSN
)
6235 static struct write_data everything
= {0, 1, 1, 1};
6236 invalidate_memory (&everything
);
6237 invalidate_for_call ();
6240 /* Now invalidate everything set by this instruction.
6241 If a SUBREG or other funny destination is being set,
6242 sets[i].rtl is still nonzero, so here we invalidate the reg
6243 a part of which is being set. */
6245 for (i
= 0; i
< n_sets
; i
++)
6248 register rtx dest
= sets
[i
].inner_dest
;
6250 /* Needed for registers to remove the register from its
6251 previous quantity's chain.
6252 Needed for memory if this is a nonvarying address, unless
6253 we have just done an invalidate_memory that covers even those. */
6254 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
6255 || (! writes_memory
.all
&& ! cse_rtx_addr_varies_p (dest
)))
6259 /* Make sure registers mentioned in destinations
6260 are safe for use in an expression to be inserted.
6261 This removes from the hash table
6262 any invalid entry that refers to one of these registers.
6264 We don't care about the return value from mention_regs because
6265 we are going to hash the SET_DEST values unconditionally. */
6267 for (i
= 0; i
< n_sets
; i
++)
6268 if (sets
[i
].rtl
&& GET_CODE (SET_DEST (sets
[i
].rtl
)) != REG
)
6269 mention_regs (SET_DEST (sets
[i
].rtl
));
6271 /* We may have just removed some of the src_elt's from the hash table.
6272 So replace each one with the current head of the same class. */
6274 for (i
= 0; i
< n_sets
; i
++)
6277 if (sets
[i
].src_elt
&& sets
[i
].src_elt
->first_same_value
== 0)
6278 /* If elt was removed, find current head of same class,
6279 or 0 if nothing remains of that class. */
6281 register struct table_elt
*elt
= sets
[i
].src_elt
;
6283 while (elt
&& elt
->prev_same_value
)
6284 elt
= elt
->prev_same_value
;
6286 while (elt
&& elt
->first_same_value
== 0)
6287 elt
= elt
->next_same_value
;
6288 sets
[i
].src_elt
= elt
? elt
->first_same_value
: 0;
6292 /* Now insert the destinations into their equivalence classes. */
6294 for (i
= 0; i
< n_sets
; i
++)
6297 register rtx dest
= SET_DEST (sets
[i
].rtl
);
6298 register struct table_elt
*elt
;
6300 /* Don't record value if we are not supposed to risk allocating
6301 floating-point values in registers that might be wider than
6303 if ((flag_float_store
6304 && GET_CODE (dest
) == MEM
6305 && GET_MODE_CLASS (GET_MODE (dest
)) == MODE_FLOAT
)
6306 /* Don't record values of destinations set inside a libcall block
6307 since we might delete the libcall. Things should have been set
6308 up so we won't want to reuse such a value, but we play it safe
6311 /* If we didn't put a REG_EQUAL value or a source into the hash
6312 table, there is no point is recording DEST. */
6313 || sets
[i
].src_elt
== 0)
6316 /* STRICT_LOW_PART isn't part of the value BEING set,
6317 and neither is the SUBREG inside it.
6318 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6319 if (GET_CODE (dest
) == STRICT_LOW_PART
)
6320 dest
= SUBREG_REG (XEXP (dest
, 0));
6322 if (GET_CODE (dest
) == REG
)
6323 /* Registers must also be inserted into chains for quantities. */
6324 if (insert_regs (dest
, sets
[i
].src_elt
, 1))
6325 /* If `insert_regs' changes something, the hash code must be
6327 sets
[i
].dest_hash_code
= HASH (dest
, GET_MODE (dest
));
6329 elt
= insert (dest
, sets
[i
].src_elt
,
6330 sets
[i
].dest_hash_code
, GET_MODE (dest
));
6331 elt
->in_memory
= GET_CODE (sets
[i
].inner_dest
) == MEM
;
6334 /* This implicitly assumes a whole struct
6335 need not have MEM_IN_STRUCT_P.
6336 But a whole struct is *supposed* to have MEM_IN_STRUCT_P. */
6337 elt
->in_struct
= (MEM_IN_STRUCT_P (sets
[i
].inner_dest
)
6338 || sets
[i
].inner_dest
!= SET_DEST (sets
[i
].rtl
));
6341 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6342 narrower than M2, and both M1 and M2 are the same number of words,
6343 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6344 make that equivalence as well.
6346 However, BAR may have equivalences for which gen_lowpart_if_possible
6347 will produce a simpler value than gen_lowpart_if_possible applied to
6348 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6349 BAR's equivalences. If we don't get a simplified form, make
6350 the SUBREG. It will not be used in an equivalence, but will
6351 cause two similar assignments to be detected.
6353 Note the loop below will find SUBREG_REG (DEST) since we have
6354 already entered SRC and DEST of the SET in the table. */
6356 if (GET_CODE (dest
) == SUBREG
6357 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))) / UNITS_PER_WORD
6358 == GET_MODE_SIZE (GET_MODE (dest
)) / UNITS_PER_WORD
)
6359 && (GET_MODE_SIZE (GET_MODE (dest
))
6360 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
6361 && sets
[i
].src_elt
!= 0)
6363 enum machine_mode new_mode
= GET_MODE (SUBREG_REG (dest
));
6364 struct table_elt
*elt
, *classp
= 0;
6366 for (elt
= sets
[i
].src_elt
->first_same_value
; elt
;
6367 elt
= elt
->next_same_value
)
6371 struct table_elt
*src_elt
;
6373 /* Ignore invalid entries. */
6374 if (GET_CODE (elt
->exp
) != REG
6375 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
6378 new_src
= gen_lowpart_if_possible (new_mode
, elt
->exp
);
6380 new_src
= gen_rtx (SUBREG
, new_mode
, elt
->exp
, 0);
6382 src_hash
= HASH (new_src
, new_mode
);
6383 src_elt
= lookup (new_src
, src_hash
, new_mode
);
6385 /* Put the new source in the hash table is if isn't
6389 if (insert_regs (new_src
, classp
, 0))
6390 src_hash
= HASH (new_src
, new_mode
);
6391 src_elt
= insert (new_src
, classp
, src_hash
, new_mode
);
6392 src_elt
->in_memory
= elt
->in_memory
;
6393 src_elt
->in_struct
= elt
->in_struct
;
6395 else if (classp
&& classp
!= src_elt
->first_same_value
)
6396 /* Show that two things that we've seen before are
6397 actually the same. */
6398 merge_equiv_classes (src_elt
, classp
);
6400 classp
= src_elt
->first_same_value
;
6405 /* Special handling for (set REG0 REG1)
6406 where REG0 is the "cheapest", cheaper than REG1.
6407 After cse, REG1 will probably not be used in the sequel,
6408 so (if easily done) change this insn to (set REG1 REG0) and
6409 replace REG1 with REG0 in the previous insn that computed their value.
6410 Then REG1 will become a dead store and won't cloud the situation
6411 for later optimizations.
6413 Do not make this change if REG1 is a hard register, because it will
6414 then be used in the sequel and we may be changing a two-operand insn
6415 into a three-operand insn.
6417 Also do not do this if we are operating on a copy of INSN. */
6419 if (n_sets
== 1 && sets
[0].rtl
&& GET_CODE (SET_DEST (sets
[0].rtl
)) == REG
6420 && NEXT_INSN (PREV_INSN (insn
)) == insn
6421 && GET_CODE (SET_SRC (sets
[0].rtl
)) == REG
6422 && REGNO (SET_SRC (sets
[0].rtl
)) >= FIRST_PSEUDO_REGISTER
6423 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets
[0].rtl
)))
6424 && (qty_first_reg
[reg_qty
[REGNO (SET_SRC (sets
[0].rtl
))]]
6425 == REGNO (SET_DEST (sets
[0].rtl
))))
6427 rtx prev
= PREV_INSN (insn
);
6428 while (prev
&& GET_CODE (prev
) == NOTE
)
6429 prev
= PREV_INSN (prev
);
6431 if (prev
&& GET_CODE (prev
) == INSN
&& GET_CODE (PATTERN (prev
)) == SET
6432 && SET_DEST (PATTERN (prev
)) == SET_SRC (sets
[0].rtl
))
6434 rtx dest
= SET_DEST (sets
[0].rtl
);
6435 rtx note
= find_reg_note (prev
, REG_EQUIV
, 0);
6437 validate_change (prev
, & SET_DEST (PATTERN (prev
)), dest
, 1);
6438 validate_change (insn
, & SET_DEST (sets
[0].rtl
),
6439 SET_SRC (sets
[0].rtl
), 1);
6440 validate_change (insn
, & SET_SRC (sets
[0].rtl
), dest
, 1);
6441 apply_change_group ();
6443 /* If REG1 was equivalent to a constant, REG0 is not. */
6445 PUT_REG_NOTE_KIND (note
, REG_EQUAL
);
6447 /* If there was a REG_WAS_0 note on PREV, remove it. Move
6448 any REG_WAS_0 note on INSN to PREV. */
6449 note
= find_reg_note (prev
, REG_WAS_0
, 0);
6451 remove_note (prev
, note
);
6453 note
= find_reg_note (insn
, REG_WAS_0
, 0);
6456 remove_note (insn
, note
);
6457 XEXP (note
, 1) = REG_NOTES (prev
);
6458 REG_NOTES (prev
) = note
;
6463 /* If this is a conditional jump insn, record any known equivalences due to
6464 the condition being tested. */
6466 last_jump_equiv_class
= 0;
6467 if (GET_CODE (insn
) == JUMP_INSN
6468 && n_sets
== 1 && GET_CODE (x
) == SET
6469 && GET_CODE (SET_SRC (x
)) == IF_THEN_ELSE
)
6470 record_jump_equiv (insn
, 0);
6473 /* If the previous insn set CC0 and this insn no longer references CC0,
6474 delete the previous insn. Here we use the fact that nothing expects CC0
6475 to be valid over an insn, which is true until the final pass. */
6476 if (prev_insn
&& GET_CODE (prev_insn
) == INSN
6477 && (tem
= single_set (prev_insn
)) != 0
6478 && SET_DEST (tem
) == cc0_rtx
6479 && ! reg_mentioned_p (cc0_rtx
, x
))
6481 PUT_CODE (prev_insn
, NOTE
);
6482 NOTE_LINE_NUMBER (prev_insn
) = NOTE_INSN_DELETED
;
6483 NOTE_SOURCE_FILE (prev_insn
) = 0;
6486 prev_insn_cc0
= this_insn_cc0
;
6487 prev_insn_cc0_mode
= this_insn_cc0_mode
;
6493 /* Store 1 in *WRITES_PTR for those categories of memory ref
6494 that must be invalidated when the expression WRITTEN is stored in.
6495 If WRITTEN is null, say everything must be invalidated. */
6498 note_mem_written (written
, writes_ptr
)
6500 struct write_data
*writes_ptr
;
6502 static struct write_data everything
= {0, 1, 1, 1};
6505 *writes_ptr
= everything
;
6506 else if (GET_CODE (written
) == MEM
)
6508 /* Pushing or popping the stack invalidates just the stack pointer. */
6509 rtx addr
= XEXP (written
, 0);
6510 if ((GET_CODE (addr
) == PRE_DEC
|| GET_CODE (addr
) == PRE_INC
6511 || GET_CODE (addr
) == POST_DEC
|| GET_CODE (addr
) == POST_INC
)
6512 && GET_CODE (XEXP (addr
, 0)) == REG
6513 && REGNO (XEXP (addr
, 0)) == STACK_POINTER_REGNUM
)
6518 else if (GET_MODE (written
) == BLKmode
)
6519 *writes_ptr
= everything
;
6520 else if (cse_rtx_addr_varies_p (written
))
6522 /* A varying address that is a sum indicates an array element,
6523 and that's just as good as a structure element
6524 in implying that we need not invalidate scalar variables. */
6525 if (!(MEM_IN_STRUCT_P (written
)
6526 || GET_CODE (XEXP (written
, 0)) == PLUS
))
6527 writes_ptr
->all
= 1;
6528 writes_ptr
->nonscalar
= 1;
6530 writes_ptr
->var
= 1;
6534 /* Perform invalidation on the basis of everything about an insn
6535 except for invalidating the actual places that are SET in it.
6536 This includes the places CLOBBERed, and anything that might
6537 alias with something that is SET or CLOBBERed.
6539 W points to the writes_memory for this insn, a struct write_data
6540 saying which kinds of memory references must be invalidated.
6541 X is the pattern of the insn. */
6544 invalidate_from_clobbers (w
, x
)
6545 struct write_data
*w
;
6548 /* If W->var is not set, W specifies no action.
6549 If W->all is set, this step gets all memory refs
6550 so they can be ignored in the rest of this function. */
6552 invalidate_memory (w
);
6556 if (reg_tick
[STACK_POINTER_REGNUM
] >= 0)
6557 reg_tick
[STACK_POINTER_REGNUM
]++;
6559 /* This should be *very* rare. */
6560 if (TEST_HARD_REG_BIT (hard_regs_in_table
, STACK_POINTER_REGNUM
))
6561 invalidate (stack_pointer_rtx
);
6564 if (GET_CODE (x
) == CLOBBER
)
6566 rtx ref
= XEXP (x
, 0);
6568 && (GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6569 || (GET_CODE (ref
) == MEM
&& ! w
->all
)))
6572 else if (GET_CODE (x
) == PARALLEL
)
6575 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
6577 register rtx y
= XVECEXP (x
, 0, i
);
6578 if (GET_CODE (y
) == CLOBBER
)
6580 rtx ref
= XEXP (y
, 0);
6582 &&(GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6583 || (GET_CODE (ref
) == MEM
&& !w
->all
)))
6590 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6591 and replace any registers in them with either an equivalent constant
6592 or the canonical form of the register. If we are inside an address,
6593 only do this if the address remains valid.
6595 OBJECT is 0 except when within a MEM in which case it is the MEM.
6597 Return the replacement for X. */
6600 cse_process_notes (x
, object
)
6604 enum rtx_code code
= GET_CODE (x
);
6605 char *fmt
= GET_RTX_FORMAT (code
);
6622 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), x
);
6627 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
6628 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), 0);
6630 XEXP (x
, 1) = cse_process_notes (XEXP (x
, 1), 0);
6634 i
= reg_qty
[REGNO (x
)];
6636 /* Return a constant or a constant register. */
6637 if (REGNO_QTY_VALID_P (REGNO (x
))
6638 && qty_const
[i
] != 0
6639 && (CONSTANT_P (qty_const
[i
])
6640 || GET_CODE (qty_const
[i
]) == REG
))
6642 rtx
new = gen_lowpart_if_possible (GET_MODE (x
), qty_const
[i
]);
6647 /* Otherwise, canonicalize this register. */
6648 return canon_reg (x
, 0);
6651 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
6653 validate_change (object
, &XEXP (x
, i
),
6654 cse_process_notes (XEXP (x
, i
), object
), 0);
6659 /* Find common subexpressions between the end test of a loop and the beginning
6660 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6662 Often we have a loop where an expression in the exit test is used
6663 in the body of the loop. For example "while (*p) *q++ = *p++;".
6664 Because of the way we duplicate the loop exit test in front of the loop,
6665 however, we don't detect that common subexpression. This will be caught
6666 when global cse is implemented, but this is a quite common case.
6668 This function handles the most common cases of these common expressions.
6669 It is called after we have processed the basic block ending with the
6670 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
6671 jumps to a label used only once. */
6674 cse_around_loop (loop_start
)
6679 struct table_elt
*p
;
6681 /* If the jump at the end of the loop doesn't go to the start, we don't
6683 for (insn
= PREV_INSN (loop_start
);
6684 insn
&& (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) >= 0);
6685 insn
= PREV_INSN (insn
))
6689 || GET_CODE (insn
) != NOTE
6690 || NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
)
6693 /* If the last insn of the loop (the end test) was an NE comparison,
6694 we will interpret it as an EQ comparison, since we fell through
6695 the loop. Any equivalances resulting from that comparison are
6696 therefore not valid and must be invalidated. */
6697 if (last_jump_equiv_class
)
6698 for (p
= last_jump_equiv_class
->first_same_value
; p
;
6699 p
= p
->next_same_value
)
6700 if (GET_CODE (p
->exp
) == MEM
|| GET_CODE (p
->exp
) == REG
6701 || GET_CODE (p
->exp
) == SUBREG
)
6702 invalidate (p
->exp
);
6704 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
6705 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
6707 The only thing we do with SET_DEST is invalidate entries, so we
6708 can safely process each SET in order. It is slightly less efficient
6709 to do so, but we only want to handle the most common cases. */
6711 for (insn
= NEXT_INSN (loop_start
);
6712 GET_CODE (insn
) != CALL_INSN
&& GET_CODE (insn
) != CODE_LABEL
6713 && ! (GET_CODE (insn
) == NOTE
6714 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
);
6715 insn
= NEXT_INSN (insn
))
6717 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
6718 && (GET_CODE (PATTERN (insn
)) == SET
6719 || GET_CODE (PATTERN (insn
)) == CLOBBER
))
6720 cse_set_around_loop (PATTERN (insn
), insn
, loop_start
);
6721 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
6722 && GET_CODE (PATTERN (insn
)) == PARALLEL
)
6723 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
6724 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == SET
6725 || GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == CLOBBER
)
6726 cse_set_around_loop (XVECEXP (PATTERN (insn
), 0, i
), insn
,
6731 /* Variable used for communications between the next two routines. */
6733 static struct write_data skipped_writes_memory
;
6735 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
6736 since they are done elsewhere. This function is called via note_stores. */
6739 invalidate_skipped_set (dest
, set
)
6743 if (GET_CODE (set
) == CLOBBER
6750 if (GET_CODE (dest
) == MEM
)
6751 note_mem_written (dest
, &skipped_writes_memory
);
6753 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
6754 || (! skipped_writes_memory
.all
&& ! cse_rtx_addr_varies_p (dest
)))
6758 /* Invalidate all insns from START up to the end of the function or the
6759 next label. This called when we wish to CSE around a block that is
6760 conditionally executed. */
6763 invalidate_skipped_block (start
)
6768 static struct write_data init
= {0, 0, 0, 0};
6769 static struct write_data everything
= {0, 1, 1, 1};
6771 for (insn
= start
; insn
&& GET_CODE (insn
) != CODE_LABEL
;
6772 insn
= NEXT_INSN (insn
))
6774 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6777 skipped_writes_memory
= init
;
6779 if (GET_CODE (insn
) == CALL_INSN
)
6781 invalidate_for_call ();
6782 skipped_writes_memory
= everything
;
6785 note_stores (PATTERN (insn
), invalidate_skipped_set
);
6786 invalidate_from_clobbers (&skipped_writes_memory
, PATTERN (insn
));
6790 /* Used for communication between the following two routines; contains a
6791 value to be checked for modification. */
6793 static rtx cse_check_loop_start_value
;
6795 /* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE,
6796 indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0. */
6799 cse_check_loop_start (x
, set
)
6803 if (cse_check_loop_start_value
== 0
6804 || GET_CODE (x
) == CC0
|| GET_CODE (x
) == PC
)
6807 if ((GET_CODE (x
) == MEM
&& GET_CODE (cse_check_loop_start_value
) == MEM
)
6808 || reg_overlap_mentioned_p (x
, cse_check_loop_start_value
))
6809 cse_check_loop_start_value
= 0;
6812 /* X is a SET or CLOBBER contained in INSN that was found near the start of
6813 a loop that starts with the label at LOOP_START.
6815 If X is a SET, we see if its SET_SRC is currently in our hash table.
6816 If so, we see if it has a value equal to some register used only in the
6817 loop exit code (as marked by jump.c).
6819 If those two conditions are true, we search backwards from the start of
6820 the loop to see if that same value was loaded into a register that still
6821 retains its value at the start of the loop.
6823 If so, we insert an insn after the load to copy the destination of that
6824 load into the equivalent register and (try to) replace our SET_SRC with that
6827 In any event, we invalidate whatever this SET or CLOBBER modifies. */
6830 cse_set_around_loop (x
, insn
, loop_start
)
6836 struct table_elt
*src_elt
;
6837 static struct write_data init
= {0, 0, 0, 0};
6838 struct write_data writes_memory
;
6840 writes_memory
= init
;
6842 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
6843 are setting PC or CC0 or whose SET_SRC is already a register. */
6844 if (GET_CODE (x
) == SET
6845 && GET_CODE (SET_DEST (x
)) != PC
&& GET_CODE (SET_DEST (x
)) != CC0
6846 && GET_CODE (SET_SRC (x
)) != REG
)
6848 src_elt
= lookup (SET_SRC (x
),
6849 HASH (SET_SRC (x
), GET_MODE (SET_DEST (x
))),
6850 GET_MODE (SET_DEST (x
)));
6853 for (src_elt
= src_elt
->first_same_value
; src_elt
;
6854 src_elt
= src_elt
->next_same_value
)
6855 if (GET_CODE (src_elt
->exp
) == REG
&& REG_LOOP_TEST_P (src_elt
->exp
)
6856 && COST (src_elt
->exp
) < COST (SET_SRC (x
)))
6860 /* Look for an insn in front of LOOP_START that sets
6861 something in the desired mode to SET_SRC (x) before we hit
6862 a label or CALL_INSN. */
6864 for (p
= prev_nonnote_insn (loop_start
);
6865 p
&& GET_CODE (p
) != CALL_INSN
6866 && GET_CODE (p
) != CODE_LABEL
;
6867 p
= prev_nonnote_insn (p
))
6868 if ((set
= single_set (p
)) != 0
6869 && GET_CODE (SET_DEST (set
)) == REG
6870 && GET_MODE (SET_DEST (set
)) == src_elt
->mode
6871 && rtx_equal_p (SET_SRC (set
), SET_SRC (x
)))
6873 /* We now have to ensure that nothing between P
6874 and LOOP_START modified anything referenced in
6875 SET_SRC (x). We know that nothing within the loop
6876 can modify it, or we would have invalidated it in
6880 cse_check_loop_start_value
= SET_SRC (x
);
6881 for (q
= p
; q
!= loop_start
; q
= NEXT_INSN (q
))
6882 if (GET_RTX_CLASS (GET_CODE (q
)) == 'i')
6883 note_stores (PATTERN (q
), cse_check_loop_start
);
6885 /* If nothing was changed and we can replace our
6886 SET_SRC, add an insn after P to copy its destination
6887 to what we will be replacing SET_SRC with. */
6888 if (cse_check_loop_start_value
6889 && validate_change (insn
, &SET_SRC (x
),
6891 emit_insn_after (gen_move_insn (src_elt
->exp
,
6899 /* Now invalidate anything modified by X. */
6900 note_mem_written (SET_DEST (x
), &writes_memory
);
6902 if (writes_memory
.var
)
6903 invalidate_memory (&writes_memory
);
6905 /* See comment on similar code in cse_insn for explanation of these tests. */
6906 if (GET_CODE (SET_DEST (x
)) == REG
|| GET_CODE (SET_DEST (x
)) == SUBREG
6907 || (GET_CODE (SET_DEST (x
)) == MEM
&& ! writes_memory
.all
6908 && ! cse_rtx_addr_varies_p (SET_DEST (x
))))
6909 invalidate (SET_DEST (x
));
6912 /* Find the end of INSN's basic block and return its range,
6913 the total number of SETs in all the insns of the block, the last insn of the
6914 block, and the branch path.
6916 The branch path indicates which branches should be followed. If a non-zero
6917 path size is specified, the block should be rescanned and a different set
6918 of branches will be taken. The branch path is only used if
6919 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
6921 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
6922 used to describe the block. It is filled in with the information about
6923 the current block. The incoming structure's branch path, if any, is used
6924 to construct the output branch path. */
6926 /* Define maximum length of a branch path. */
6928 #define PATHLENGTH 20
6930 struct cse_basic_block_data
{
6931 /* Lowest CUID value of insns in block. */
6933 /* Highest CUID value of insns in block. */
6935 /* Total number of SETs in block. */
6937 /* Last insn in the block. */
6939 /* Size of current branch path, if any. */
6941 /* Current branch path, indicating which branches will be taken. */
6942 struct branch_path
{
6943 /* The branch insn. */
6945 /* Whether it should be taken or not. AROUND is the same as taken
6946 except that it is used when the destination label is not preceded
6948 enum taken
{TAKEN
, NOT_TAKEN
, AROUND
} status
;
6953 cse_end_of_basic_block (insn
, data
, follow_jumps
, after_loop
, skip_blocks
)
6955 struct cse_basic_block_data
*data
;
6962 int low_cuid
= INSN_CUID (insn
), high_cuid
= INSN_CUID (insn
);
6963 rtx next
= GET_RTX_CLASS (GET_CODE (insn
)) == 'i' ? insn
: next_real_insn (insn
);
6964 int path_size
= data
->path_size
;
6968 /* Update the previous branch path, if any. If the last branch was
6969 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
6970 shorten the path by one and look at the previous branch. We know that
6971 at least one branch must have been taken if PATH_SIZE is non-zero. */
6972 while (path_size
> 0)
6974 if (data
->path
[path_size
- 1].status
!= NOT_TAKEN
)
6976 data
->path
[path_size
- 1].status
= NOT_TAKEN
;
6983 /* Scan to end of this basic block. */
6984 while (p
&& GET_CODE (p
) != CODE_LABEL
)
6986 /* Don't cse out the end of a loop. This makes a difference
6987 only for the unusual loops that always execute at least once;
6988 all other loops have labels there so we will stop in any case.
6989 Cse'ing out the end of the loop is dangerous because it
6990 might cause an invariant expression inside the loop
6991 to be reused after the end of the loop. This would make it
6992 hard to move the expression out of the loop in loop.c,
6993 especially if it is one of several equivalent expressions
6994 and loop.c would like to eliminate it.
6996 If we are running after loop.c has finished, we can ignore
6997 the NOTE_INSN_LOOP_END. */
6999 if (! after_loop
&& GET_CODE (p
) == NOTE
7000 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
7003 /* Don't cse over a call to setjmp; on some machines (eg vax)
7004 the regs restored by the longjmp come from
7005 a later time than the setjmp. */
7006 if (GET_CODE (p
) == NOTE
7007 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_SETJMP
)
7010 /* A PARALLEL can have lots of SETs in it,
7011 especially if it is really an ASM_OPERANDS. */
7012 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i'
7013 && GET_CODE (PATTERN (p
)) == PARALLEL
)
7014 nsets
+= XVECLEN (PATTERN (p
), 0);
7015 else if (GET_CODE (p
) != NOTE
)
7018 if (INSN_CUID (p
) > high_cuid
)
7019 high_cuid
= INSN_CUID (p
);
7020 if (INSN_CUID (p
) < low_cuid
)
7021 low_cuid
= INSN_CUID(p
);
7023 /* See if this insn is in our branch path. If it is and we are to
7025 if (path_entry
< path_size
&& data
->path
[path_entry
].branch
== p
)
7027 if (data
->path
[path_entry
].status
!= NOT_TAKEN
)
7030 /* Point to next entry in path, if any. */
7034 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
7035 was specified, we haven't reached our maximum path length, there are
7036 insns following the target of the jump, this is the only use of the
7037 jump label, and the target label is preceded by a BARRIER.
7039 Alternatively, we can follow the jump if it branches around a
7040 block of code and there are no other branches into the block.
7041 In this case invalidate_skipped_block will be called to invalidate any
7042 registers set in the block when following the jump. */
7044 else if ((follow_jumps
|| skip_blocks
) && path_size
< PATHLENGTH
- 1
7045 && GET_CODE (p
) == JUMP_INSN
7046 && GET_CODE (PATTERN (p
)) == SET
7047 && GET_CODE (SET_SRC (PATTERN (p
))) == IF_THEN_ELSE
7048 && LABEL_NUSES (JUMP_LABEL (p
)) == 1
7049 && NEXT_INSN (JUMP_LABEL (p
)) != 0)
7051 for (q
= PREV_INSN (JUMP_LABEL (p
)); q
; q
= PREV_INSN (q
))
7052 if ((GET_CODE (q
) != NOTE
7053 || NOTE_LINE_NUMBER (q
) == NOTE_INSN_LOOP_END
7054 || NOTE_LINE_NUMBER (q
) == NOTE_INSN_SETJMP
)
7055 && (GET_CODE (q
) != CODE_LABEL
|| LABEL_NUSES (q
) != 0))
7058 /* If we ran into a BARRIER, this code is an extension of the
7059 basic block when the branch is taken. */
7060 if (follow_jumps
&& q
!= 0 && GET_CODE (q
) == BARRIER
)
7062 /* Don't allow ourself to keep walking around an
7063 always-executed loop. */
7064 if (next_real_insn (q
) == next
)
7070 /* Similarly, don't put a branch in our path more than once. */
7071 for (i
= 0; i
< path_entry
; i
++)
7072 if (data
->path
[i
].branch
== p
)
7075 if (i
!= path_entry
)
7078 data
->path
[path_entry
].branch
= p
;
7079 data
->path
[path_entry
++].status
= TAKEN
;
7081 /* This branch now ends our path. It was possible that we
7082 didn't see this branch the last time around (when the
7083 insn in front of the target was a JUMP_INSN that was
7084 turned into a no-op). */
7085 path_size
= path_entry
;
7088 /* Mark block so we won't scan it again later. */
7089 PUT_MODE (NEXT_INSN (p
), QImode
);
7091 /* Detect a branch around a block of code. */
7092 else if (skip_blocks
&& q
!= 0 && GET_CODE (q
) != CODE_LABEL
)
7096 if (next_real_insn (q
) == next
)
7102 for (i
= 0; i
< path_entry
; i
++)
7103 if (data
->path
[i
].branch
== p
)
7106 if (i
!= path_entry
)
7109 /* This is no_labels_between_p (p, q) with an added check for
7110 reaching the end of a function (in case Q precedes P). */
7111 for (tmp
= NEXT_INSN (p
); tmp
&& tmp
!= q
; tmp
= NEXT_INSN (tmp
))
7112 if (GET_CODE (tmp
) == CODE_LABEL
)
7117 data
->path
[path_entry
].branch
= p
;
7118 data
->path
[path_entry
++].status
= AROUND
;
7120 path_size
= path_entry
;
7123 /* Mark block so we won't scan it again later. */
7124 PUT_MODE (NEXT_INSN (p
), QImode
);
7131 data
->low_cuid
= low_cuid
;
7132 data
->high_cuid
= high_cuid
;
7133 data
->nsets
= nsets
;
7136 /* If all jumps in the path are not taken, set our path length to zero
7137 so a rescan won't be done. */
7138 for (i
= path_size
- 1; i
>= 0; i
--)
7139 if (data
->path
[i
].status
!= NOT_TAKEN
)
7143 data
->path_size
= 0;
7145 data
->path_size
= path_size
;
7147 /* End the current branch path. */
7148 data
->path
[path_size
].branch
= 0;
7151 static rtx
cse_basic_block ();
7153 /* Perform cse on the instructions of a function.
7154 F is the first instruction.
7155 NREGS is one plus the highest pseudo-reg number used in the instruction.
7157 AFTER_LOOP is 1 if this is the cse call done after loop optimization
7158 (only if -frerun-cse-after-loop).
7160 Returns 1 if jump_optimize should be redone due to simplifications
7161 in conditional jump instructions. */
7164 cse_main (f
, nregs
, after_loop
, file
)
7170 struct cse_basic_block_data val
;
7171 register rtx insn
= f
;
7174 cse_jumps_altered
= 0;
7175 constant_pool_entries_cost
= 0;
7182 all_minus_one
= (int *) alloca (nregs
* sizeof (int));
7183 consec_ints
= (int *) alloca (nregs
* sizeof (int));
7185 for (i
= 0; i
< nregs
; i
++)
7187 all_minus_one
[i
] = -1;
7191 reg_next_eqv
= (int *) alloca (nregs
* sizeof (int));
7192 reg_prev_eqv
= (int *) alloca (nregs
* sizeof (int));
7193 reg_qty
= (int *) alloca (nregs
* sizeof (int));
7194 reg_in_table
= (int *) alloca (nregs
* sizeof (int));
7195 reg_tick
= (int *) alloca (nregs
* sizeof (int));
7197 /* Discard all the free elements of the previous function
7198 since they are allocated in the temporarily obstack. */
7199 bzero (table
, sizeof table
);
7200 free_element_chain
= 0;
7201 n_elements_made
= 0;
7203 /* Find the largest uid. */
7206 uid_cuid
= (short *) alloca ((i
+ 1) * sizeof (short));
7207 bzero (uid_cuid
, (i
+ 1) * sizeof (short));
7209 /* Compute the mapping from uids to cuids.
7210 CUIDs are numbers assigned to insns, like uids,
7211 except that cuids increase monotonically through the code.
7212 Don't assign cuids to line-number NOTEs, so that the distance in cuids
7213 between two insns is not affected by -g. */
7215 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
7217 if (GET_CODE (insn
) != NOTE
7218 || NOTE_LINE_NUMBER (insn
) < 0)
7219 INSN_CUID (insn
) = ++i
;
7221 /* Give a line number note the same cuid as preceding insn. */
7222 INSN_CUID (insn
) = i
;
7225 /* Initialize which registers are clobbered by calls. */
7227 CLEAR_HARD_REG_SET (regs_invalidated_by_call
);
7229 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
7230 if ((call_used_regs
[i
]
7231 /* Used to check !fixed_regs[i] here, but that isn't safe;
7232 fixed regs are still call-clobbered, and sched can get
7233 confused if they can "live across calls".
7235 The frame pointer is always preserved across calls. The arg
7236 pointer is if it is fixed. The stack pointer usually is, unless
7237 RETURN_POPS_ARGS, in which case an explicit CLOBBER
7238 will be present. If we are generating PIC code, the PIC offset
7239 table register is preserved across calls. */
7241 && i
!= STACK_POINTER_REGNUM
7242 && i
!= FRAME_POINTER_REGNUM
7243 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
7244 && ! (i
== ARG_POINTER_REGNUM
&& fixed_regs
[i
])
7246 #ifdef PIC_OFFSET_TABLE_REGNUM
7247 && ! (i
== PIC_OFFSET_TABLE_REGNUM
&& flag_pic
)
7251 SET_HARD_REG_BIT (regs_invalidated_by_call
, i
);
7253 /* Loop over basic blocks.
7254 Compute the maximum number of qty's needed for each basic block
7255 (which is 2 for each SET). */
7259 cse_end_of_basic_block (insn
, &val
, flag_cse_follow_jumps
, after_loop
,
7260 flag_cse_skip_blocks
);
7262 /* If this basic block was already processed or has no sets, skip it. */
7263 if (val
.nsets
== 0 || GET_MODE (insn
) == QImode
)
7265 PUT_MODE (insn
, VOIDmode
);
7266 insn
= (val
.last
? NEXT_INSN (val
.last
) : 0);
7271 cse_basic_block_start
= val
.low_cuid
;
7272 cse_basic_block_end
= val
.high_cuid
;
7273 max_qty
= val
.nsets
* 2;
7276 fprintf (file
, ";; Processing block from %d to %d, %d sets.\n",
7277 INSN_UID (insn
), val
.last
? INSN_UID (val
.last
) : 0,
7280 /* Make MAX_QTY bigger to give us room to optimize
7281 past the end of this basic block, if that should prove useful. */
7287 /* If this basic block is being extended by following certain jumps,
7288 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7289 Otherwise, we start after this basic block. */
7290 if (val
.path_size
> 0)
7291 cse_basic_block (insn
, val
.last
, val
.path
, 0);
7294 int old_cse_jumps_altered
= cse_jumps_altered
;
7297 /* When cse changes a conditional jump to an unconditional
7298 jump, we want to reprocess the block, since it will give
7299 us a new branch path to investigate. */
7300 cse_jumps_altered
= 0;
7301 temp
= cse_basic_block (insn
, val
.last
, val
.path
, ! after_loop
);
7302 if (cse_jumps_altered
== 0
7303 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7306 cse_jumps_altered
|= old_cse_jumps_altered
;
7314 /* Tell refers_to_mem_p that qty_const info is not available. */
7317 if (max_elements_made
< n_elements_made
)
7318 max_elements_made
= n_elements_made
;
7320 return cse_jumps_altered
;
7323 /* Process a single basic block. FROM and TO and the limits of the basic
7324 block. NEXT_BRANCH points to the branch path when following jumps or
7325 a null path when not following jumps.
7327 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
7328 loop. This is true when we are being called for the last time on a
7329 block and this CSE pass is before loop.c. */
7332 cse_basic_block (from
, to
, next_branch
, around_loop
)
7333 register rtx from
, to
;
7334 struct branch_path
*next_branch
;
7339 int in_libcall_block
= 0;
7341 /* Each of these arrays is undefined before max_reg, so only allocate
7342 the space actually needed and adjust the start below. */
7344 qty_first_reg
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7345 qty_last_reg
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7346 qty_mode
= (enum machine_mode
*) alloca ((max_qty
- max_reg
) * sizeof (enum machine_mode
));
7347 qty_const
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7348 qty_const_insn
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7350 = (enum rtx_code
*) alloca ((max_qty
- max_reg
) * sizeof (enum rtx_code
));
7351 qty_comparison_qty
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7352 qty_comparison_const
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7354 qty_first_reg
-= max_reg
;
7355 qty_last_reg
-= max_reg
;
7356 qty_mode
-= max_reg
;
7357 qty_const
-= max_reg
;
7358 qty_const_insn
-= max_reg
;
7359 qty_comparison_code
-= max_reg
;
7360 qty_comparison_qty
-= max_reg
;
7361 qty_comparison_const
-= max_reg
;
7365 /* TO might be a label. If so, protect it from being deleted. */
7366 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7369 for (insn
= from
; insn
!= to
; insn
= NEXT_INSN (insn
))
7371 register enum rtx_code code
;
7373 /* See if this is a branch that is part of the path. If so, and it is
7374 to be taken, do so. */
7375 if (next_branch
->branch
== insn
)
7377 enum taken status
= next_branch
++->status
;
7378 if (status
!= NOT_TAKEN
)
7380 if (status
== TAKEN
)
7381 record_jump_equiv (insn
, 1);
7383 invalidate_skipped_block (NEXT_INSN (insn
));
7385 /* Set the last insn as the jump insn; it doesn't affect cc0.
7386 Then follow this branch. */
7391 insn
= JUMP_LABEL (insn
);
7396 code
= GET_CODE (insn
);
7397 if (GET_MODE (insn
) == QImode
)
7398 PUT_MODE (insn
, VOIDmode
);
7400 if (GET_RTX_CLASS (code
) == 'i')
7402 /* Process notes first so we have all notes in canonical forms when
7403 looking for duplicate operations. */
7405 if (REG_NOTES (insn
))
7406 REG_NOTES (insn
) = cse_process_notes (REG_NOTES (insn
), 0);
7408 /* Track when we are inside in LIBCALL block. Inside such a block,
7409 we do not want to record destinations. The last insn of a
7410 LIBCALL block is not considered to be part of the block, since
7411 its destination is the result of the block and hence should be
7414 if (find_reg_note (insn
, REG_LIBCALL
, 0))
7415 in_libcall_block
= 1;
7416 else if (find_reg_note (insn
, REG_RETVAL
, 0))
7417 in_libcall_block
= 0;
7419 cse_insn (insn
, in_libcall_block
);
7422 /* If INSN is now an unconditional jump, skip to the end of our
7423 basic block by pretending that we just did the last insn in the
7424 basic block. If we are jumping to the end of our block, show
7425 that we can have one usage of TO. */
7427 if (simplejump_p (insn
))
7432 if (JUMP_LABEL (insn
) == to
)
7435 insn
= PREV_INSN (to
);
7438 /* See if it is ok to keep on going past the label
7439 which used to end our basic block. Remember that we incremented
7440 the count of that label, so we decrement it here. If we made
7441 a jump unconditional, TO_USAGE will be one; in that case, we don't
7442 want to count the use in that jump. */
7444 if (to
!= 0 && NEXT_INSN (insn
) == to
7445 && GET_CODE (to
) == CODE_LABEL
&& --LABEL_NUSES (to
) == to_usage
)
7447 struct cse_basic_block_data val
;
7449 insn
= NEXT_INSN (to
);
7451 if (LABEL_NUSES (to
) == 0)
7454 /* Find the end of the following block. Note that we won't be
7455 following branches in this case. If TO was the last insn
7456 in the function, we are done. Similarly, if we deleted the
7457 insn after TO, it must have been because it was preceded by
7458 a BARRIER. In that case, we are done with this block because it
7459 has no continuation. */
7461 if (insn
== 0 || INSN_DELETED_P (insn
))
7466 cse_end_of_basic_block (insn
, &val
, 0, 0, 0);
7468 /* If the tables we allocated have enough space left
7469 to handle all the SETs in the next basic block,
7470 continue through it. Otherwise, return,
7471 and that block will be scanned individually. */
7472 if (val
.nsets
* 2 + next_qty
> max_qty
)
7475 cse_basic_block_start
= val
.low_cuid
;
7476 cse_basic_block_end
= val
.high_cuid
;
7479 /* Prevent TO from being deleted if it is a label. */
7480 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7483 /* Back up so we process the first insn in the extension. */
7484 insn
= PREV_INSN (insn
);
7488 if (next_qty
> max_qty
)
7491 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7492 the previous insn is the only insn that branches to the head of a loop,
7493 we can cse into the loop. Don't do this if we changed the jump
7494 structure of a loop unless we aren't going to be following jumps. */
7496 if ((cse_jumps_altered
== 0
7497 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7498 && around_loop
&& to
!= 0
7499 && GET_CODE (to
) == NOTE
&& NOTE_LINE_NUMBER (to
) == NOTE_INSN_LOOP_END
7500 && GET_CODE (PREV_INSN (to
)) == JUMP_INSN
7501 && JUMP_LABEL (PREV_INSN (to
)) != 0
7502 && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to
))) == 1)
7503 cse_around_loop (JUMP_LABEL (PREV_INSN (to
)));
7505 return to
? NEXT_INSN (to
) : 0;
7508 /* Count the number of times registers are used (not set) in X.
7509 COUNTS is an array in which we accumulate the count, INCR is how much
7510 we count each register usage. */
7513 count_reg_usage (x
, counts
, incr
)
7518 enum rtx_code code
= GET_CODE (x
);
7525 counts
[REGNO (x
)] += incr
;
7539 /* Unless we are setting a REG, count everything in SET_DEST. */
7540 if (GET_CODE (SET_DEST (x
)) != REG
)
7541 count_reg_usage (SET_DEST (x
), counts
, incr
);
7542 count_reg_usage (SET_SRC (x
), counts
, incr
);
7548 count_reg_usage (PATTERN (x
), counts
, incr
);
7550 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7554 count_reg_usage (REG_NOTES (x
), counts
, incr
);
7559 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
7560 count_reg_usage (XEXP (x
, 0), counts
, incr
);
7562 count_reg_usage (XEXP (x
, 1), counts
, incr
);
7566 fmt
= GET_RTX_FORMAT (code
);
7567 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
7570 count_reg_usage (XEXP (x
, i
), counts
, incr
);
7571 else if (fmt
[i
] == 'E')
7572 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7573 count_reg_usage (XVECEXP (x
, i
, j
), counts
, incr
);
7577 /* Scan all the insns and delete any that are dead; i.e., they store a register
7578 that is never used or they copy a register to itself.
7580 This is used to remove insns made obviously dead by cse. It improves the
7581 heuristics in loop since it won't try to move dead invariants out of loops
7582 or make givs for dead quantities. The remaining passes of the compilation
7583 are also sped up. */
7586 delete_dead_from_cse (insns
, nreg
)
7590 int *counts
= (int *) alloca (nreg
* sizeof (int));
7595 /* First count the number of times each register is used. */
7596 bzero (counts
, sizeof (int) * nreg
);
7597 for (insn
= next_real_insn (insns
); insn
; insn
= next_real_insn (insn
))
7598 count_reg_usage (insn
, counts
, 1);
7600 /* Go from the last insn to the first and delete insns that only set unused
7601 registers or copy a register to itself. As we delete an insn, remove
7602 usage counts for registers it uses. */
7603 for (insn
= prev_real_insn (get_last_insn ());
7604 insn
; insn
= prev_real_insn (insn
))
7608 if (GET_CODE (PATTERN (insn
)) == SET
)
7610 if (GET_CODE (SET_DEST (PATTERN (insn
))) == REG
7611 && SET_DEST (PATTERN (insn
)) == SET_SRC (PATTERN (insn
)))
7615 else if (GET_CODE (SET_DEST (PATTERN (insn
))) == CC0
7616 && ! side_effects_p (SET_SRC (PATTERN (insn
)))
7617 && ((tem
= next_nonnote_insn (insn
)) == 0
7618 || GET_RTX_CLASS (GET_CODE (tem
)) != 'i'
7619 || ! reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
7622 else if (GET_CODE (SET_DEST (PATTERN (insn
))) != REG
7623 || REGNO (SET_DEST (PATTERN (insn
))) < FIRST_PSEUDO_REGISTER
7624 || counts
[REGNO (SET_DEST (PATTERN (insn
)))] != 0
7625 || side_effects_p (SET_SRC (PATTERN (insn
))))
7628 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
7629 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
7631 rtx elt
= XVECEXP (PATTERN (insn
), 0, i
);
7633 if (GET_CODE (elt
) == SET
)
7635 if (GET_CODE (SET_DEST (elt
)) == REG
7636 && SET_DEST (elt
) == SET_SRC (elt
))
7640 else if (GET_CODE (SET_DEST (elt
)) == CC0
7641 && ! side_effects_p (SET_SRC (elt
))
7642 && ((tem
= next_nonnote_insn (insn
)) == 0
7643 || GET_RTX_CLASS (GET_CODE (tem
)) != 'i'
7644 || ! reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
7647 else if (GET_CODE (SET_DEST (elt
)) != REG
7648 || REGNO (SET_DEST (elt
)) < FIRST_PSEUDO_REGISTER
7649 || counts
[REGNO (SET_DEST (elt
))] != 0
7650 || side_effects_p (SET_SRC (elt
)))
7653 else if (GET_CODE (elt
) != CLOBBER
&& GET_CODE (elt
) != USE
)
7659 /* If this is a dead insn, delete it and show registers in it aren't
7660 being used. If this is the last insn of a libcall sequence, don't
7661 delete it even if it is dead because we don't know how to do so
7664 if (! live_insn
&& ! find_reg_note (insn
, REG_RETVAL
, 0))
7666 count_reg_usage (insn
, counts
, -1);
7667 PUT_CODE (insn
, NOTE
);
7668 NOTE_SOURCE_FILE (insn
) = 0;
7669 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;