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 int *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), NULL_PTR
, 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), NULL_PTR
, 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 /* If X is a SUBREG, we will likely be inserting the inner register in the
934 table. If that register doesn't have an assigned quantity number at
935 this point but does later, the insertion that we will be doing now will
936 not be accessible because its hash code will have changed. So assign
937 a quantity number now. */
939 else if (GET_CODE (x
) == SUBREG
&& GET_CODE (SUBREG_REG (x
)) == REG
940 && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x
))))
942 insert_regs (SUBREG_REG (x
), NULL_PTR
, 0);
943 mention_regs (SUBREG_REG (x
));
947 return mention_regs (x
);
950 /* Look in or update the hash table. */
952 /* Put the element ELT on the list of free elements. */
956 struct table_elt
*elt
;
958 elt
->next_same_hash
= free_element_chain
;
959 free_element_chain
= elt
;
962 /* Return an element that is free for use. */
964 static struct table_elt
*
967 struct table_elt
*elt
= free_element_chain
;
970 free_element_chain
= elt
->next_same_hash
;
974 return (struct table_elt
*) oballoc (sizeof (struct table_elt
));
977 /* Remove table element ELT from use in the table.
978 HASH is its hash code, made using the HASH macro.
979 It's an argument because often that is known in advance
980 and we save much time not recomputing it. */
983 remove_from_table (elt
, hash
)
984 register struct table_elt
*elt
;
990 /* Mark this element as removed. See cse_insn. */
991 elt
->first_same_value
= 0;
993 /* Remove the table element from its equivalence class. */
996 register struct table_elt
*prev
= elt
->prev_same_value
;
997 register struct table_elt
*next
= elt
->next_same_value
;
999 if (next
) next
->prev_same_value
= prev
;
1002 prev
->next_same_value
= next
;
1005 register struct table_elt
*newfirst
= next
;
1008 next
->first_same_value
= newfirst
;
1009 next
= next
->next_same_value
;
1014 /* Remove the table element from its hash bucket. */
1017 register struct table_elt
*prev
= elt
->prev_same_hash
;
1018 register struct table_elt
*next
= elt
->next_same_hash
;
1020 if (next
) next
->prev_same_hash
= prev
;
1023 prev
->next_same_hash
= next
;
1024 else if (table
[hash
] == elt
)
1028 /* This entry is not in the proper hash bucket. This can happen
1029 when two classes were merged by `merge_equiv_classes'. Search
1030 for the hash bucket that it heads. This happens only very
1031 rarely, so the cost is acceptable. */
1032 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1033 if (table
[hash
] == elt
)
1038 /* Remove the table element from its related-value circular chain. */
1040 if (elt
->related_value
!= 0 && elt
->related_value
!= elt
)
1042 register struct table_elt
*p
= elt
->related_value
;
1043 while (p
->related_value
!= elt
)
1044 p
= p
->related_value
;
1045 p
->related_value
= elt
->related_value
;
1046 if (p
->related_value
== p
)
1047 p
->related_value
= 0;
1053 /* Look up X in the hash table and return its table element,
1054 or 0 if X is not in the table.
1056 MODE is the machine-mode of X, or if X is an integer constant
1057 with VOIDmode then MODE is the mode with which X will be used.
1059 Here we are satisfied to find an expression whose tree structure
1062 static struct table_elt
*
1063 lookup (x
, hash
, mode
)
1066 enum machine_mode mode
;
1068 register struct table_elt
*p
;
1070 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1071 if (mode
== p
->mode
&& ((x
== p
->exp
&& GET_CODE (x
) == REG
)
1072 || exp_equiv_p (x
, p
->exp
, GET_CODE (x
) != REG
, 0)))
1078 /* Like `lookup' but don't care whether the table element uses invalid regs.
1079 Also ignore discrepancies in the machine mode of a register. */
1081 static struct table_elt
*
1082 lookup_for_remove (x
, hash
, mode
)
1085 enum machine_mode mode
;
1087 register struct table_elt
*p
;
1089 if (GET_CODE (x
) == REG
)
1091 int regno
= REGNO (x
);
1092 /* Don't check the machine mode when comparing registers;
1093 invalidating (REG:SI 0) also invalidates (REG:DF 0). */
1094 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1095 if (GET_CODE (p
->exp
) == REG
1096 && REGNO (p
->exp
) == regno
)
1101 for (p
= table
[hash
]; p
; p
= p
->next_same_hash
)
1102 if (mode
== p
->mode
&& (x
== p
->exp
|| exp_equiv_p (x
, p
->exp
, 0, 0)))
1109 /* Look for an expression equivalent to X and with code CODE.
1110 If one is found, return that expression. */
1113 lookup_as_function (x
, code
)
1117 register struct table_elt
*p
= lookup (x
, safe_hash (x
, VOIDmode
) % NBUCKETS
,
1122 for (p
= p
->first_same_value
; p
; p
= p
->next_same_value
)
1124 if (GET_CODE (p
->exp
) == code
1125 /* Make sure this is a valid entry in the table. */
1126 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
1133 /* Insert X in the hash table, assuming HASH is its hash code
1134 and CLASSP is an element of the class it should go in
1135 (or 0 if a new class should be made).
1136 It is inserted at the proper position to keep the class in
1137 the order cheapest first.
1139 MODE is the machine-mode of X, or if X is an integer constant
1140 with VOIDmode then MODE is the mode with which X will be used.
1142 For elements of equal cheapness, the most recent one
1143 goes in front, except that the first element in the list
1144 remains first unless a cheaper element is added. The order of
1145 pseudo-registers does not matter, as canon_reg will be called to
1146 find the cheapest when a register is retrieved from the table.
1148 The in_memory field in the hash table element is set to 0.
1149 The caller must set it nonzero if appropriate.
1151 You should call insert_regs (X, CLASSP, MODIFY) before calling here,
1152 and if insert_regs returns a nonzero value
1153 you must then recompute its hash code before calling here.
1155 If necessary, update table showing constant values of quantities. */
1157 #define CHEAPER(X,Y) ((X)->cost < (Y)->cost)
1159 static struct table_elt
*
1160 insert (x
, classp
, hash
, mode
)
1162 register struct table_elt
*classp
;
1164 enum machine_mode mode
;
1166 register struct table_elt
*elt
;
1168 /* If X is a register and we haven't made a quantity for it,
1169 something is wrong. */
1170 if (GET_CODE (x
) == REG
&& ! REGNO_QTY_VALID_P (REGNO (x
)))
1173 /* If X is a hard register, show it is being put in the table. */
1174 if (GET_CODE (x
) == REG
&& REGNO (x
) < FIRST_PSEUDO_REGISTER
)
1176 int regno
= REGNO (x
);
1177 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1180 for (i
= regno
; i
< endregno
; i
++)
1181 SET_HARD_REG_BIT (hard_regs_in_table
, i
);
1185 /* Put an element for X into the right hash bucket. */
1187 elt
= get_element ();
1189 elt
->cost
= COST (x
);
1190 elt
->next_same_value
= 0;
1191 elt
->prev_same_value
= 0;
1192 elt
->next_same_hash
= table
[hash
];
1193 elt
->prev_same_hash
= 0;
1194 elt
->related_value
= 0;
1197 elt
->is_const
= (CONSTANT_P (x
)
1198 /* GNU C++ takes advantage of this for `this'
1199 (and other const values). */
1200 || (RTX_UNCHANGING_P (x
)
1201 && GET_CODE (x
) == REG
1202 && REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1203 || FIXED_BASE_PLUS_P (x
));
1206 table
[hash
]->prev_same_hash
= elt
;
1209 /* Put it into the proper value-class. */
1212 classp
= classp
->first_same_value
;
1213 if (CHEAPER (elt
, classp
))
1214 /* Insert at the head of the class */
1216 register struct table_elt
*p
;
1217 elt
->next_same_value
= classp
;
1218 classp
->prev_same_value
= elt
;
1219 elt
->first_same_value
= elt
;
1221 for (p
= classp
; p
; p
= p
->next_same_value
)
1222 p
->first_same_value
= elt
;
1226 /* Insert not at head of the class. */
1227 /* Put it after the last element cheaper than X. */
1228 register struct table_elt
*p
, *next
;
1229 for (p
= classp
; (next
= p
->next_same_value
) && CHEAPER (next
, elt
);
1231 /* Put it after P and before NEXT. */
1232 elt
->next_same_value
= next
;
1234 next
->prev_same_value
= elt
;
1235 elt
->prev_same_value
= p
;
1236 p
->next_same_value
= elt
;
1237 elt
->first_same_value
= classp
;
1241 elt
->first_same_value
= elt
;
1243 /* If this is a constant being set equivalent to a register or a register
1244 being set equivalent to a constant, note the constant equivalence.
1246 If this is a constant, it cannot be equivalent to a different constant,
1247 and a constant is the only thing that can be cheaper than a register. So
1248 we know the register is the head of the class (before the constant was
1251 If this is a register that is not already known equivalent to a
1252 constant, we must check the entire class.
1254 If this is a register that is already known equivalent to an insn,
1255 update `qty_const_insn' to show that `this_insn' is the latest
1256 insn making that quantity equivalent to the constant. */
1258 if (elt
->is_const
&& classp
&& GET_CODE (classp
->exp
) == REG
)
1260 qty_const
[reg_qty
[REGNO (classp
->exp
)]]
1261 = gen_lowpart_if_possible (qty_mode
[reg_qty
[REGNO (classp
->exp
)]], x
);
1262 qty_const_insn
[reg_qty
[REGNO (classp
->exp
)]] = this_insn
;
1265 else if (GET_CODE (x
) == REG
&& classp
&& ! qty_const
[reg_qty
[REGNO (x
)]])
1267 register struct table_elt
*p
;
1269 for (p
= classp
; p
!= 0; p
= p
->next_same_value
)
1273 qty_const
[reg_qty
[REGNO (x
)]]
1274 = gen_lowpart_if_possible (GET_MODE (x
), p
->exp
);
1275 qty_const_insn
[reg_qty
[REGNO (x
)]] = this_insn
;
1281 else if (GET_CODE (x
) == REG
&& qty_const
[reg_qty
[REGNO (x
)]]
1282 && GET_MODE (x
) == qty_mode
[reg_qty
[REGNO (x
)]])
1283 qty_const_insn
[reg_qty
[REGNO (x
)]] = this_insn
;
1285 /* If this is a constant with symbolic value,
1286 and it has a term with an explicit integer value,
1287 link it up with related expressions. */
1288 if (GET_CODE (x
) == CONST
)
1290 rtx subexp
= get_related_value (x
);
1292 struct table_elt
*subelt
, *subelt_prev
;
1296 /* Get the integer-free subexpression in the hash table. */
1297 subhash
= safe_hash (subexp
, mode
) % NBUCKETS
;
1298 subelt
= lookup (subexp
, subhash
, mode
);
1300 subelt
= insert (subexp
, NULL_PTR
, subhash
, mode
);
1301 /* Initialize SUBELT's circular chain if it has none. */
1302 if (subelt
->related_value
== 0)
1303 subelt
->related_value
= subelt
;
1304 /* Find the element in the circular chain that precedes SUBELT. */
1305 subelt_prev
= subelt
;
1306 while (subelt_prev
->related_value
!= subelt
)
1307 subelt_prev
= subelt_prev
->related_value
;
1308 /* Put new ELT into SUBELT's circular chain just before SUBELT.
1309 This way the element that follows SUBELT is the oldest one. */
1310 elt
->related_value
= subelt_prev
->related_value
;
1311 subelt_prev
->related_value
= elt
;
1318 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
1319 CLASS2 into CLASS1. This is done when we have reached an insn which makes
1320 the two classes equivalent.
1322 CLASS1 will be the surviving class; CLASS2 should not be used after this
1325 Any invalid entries in CLASS2 will not be copied. */
1328 merge_equiv_classes (class1
, class2
)
1329 struct table_elt
*class1
, *class2
;
1331 struct table_elt
*elt
, *next
, *new;
1333 /* Ensure we start with the head of the classes. */
1334 class1
= class1
->first_same_value
;
1335 class2
= class2
->first_same_value
;
1337 /* If they were already equal, forget it. */
1338 if (class1
== class2
)
1341 for (elt
= class2
; elt
; elt
= next
)
1345 enum machine_mode mode
= elt
->mode
;
1347 next
= elt
->next_same_value
;
1349 /* Remove old entry, make a new one in CLASS1's class.
1350 Don't do this for invalid entries as we cannot find their
1351 hash code (it also isn't necessary). */
1352 if (GET_CODE (exp
) == REG
|| exp_equiv_p (exp
, exp
, 1, 0))
1354 hash_arg_in_memory
= 0;
1355 hash_arg_in_struct
= 0;
1356 hash
= HASH (exp
, mode
);
1358 if (GET_CODE (exp
) == REG
)
1359 delete_reg_equiv (REGNO (exp
));
1361 remove_from_table (elt
, hash
);
1363 if (insert_regs (exp
, class1
, 0))
1364 hash
= HASH (exp
, mode
);
1365 new = insert (exp
, class1
, hash
, mode
);
1366 new->in_memory
= hash_arg_in_memory
;
1367 new->in_struct
= hash_arg_in_struct
;
1372 /* Remove from the hash table, or mark as invalid,
1373 all expressions whose values could be altered by storing in X.
1374 X is a register, a subreg, or a memory reference with nonvarying address
1375 (because, when a memory reference with a varying address is stored in,
1376 all memory references are removed by invalidate_memory
1377 so specific invalidation is superfluous).
1379 A nonvarying address may be just a register or just
1380 a symbol reference, or it may be either of those plus
1381 a numeric offset. */
1388 register struct table_elt
*p
;
1390 register HOST_WIDE_INT start
, end
;
1392 /* If X is a register, dependencies on its contents
1393 are recorded through the qty number mechanism.
1394 Just change the qty number of the register,
1395 mark it as invalid for expressions that refer to it,
1396 and remove it itself. */
1398 if (GET_CODE (x
) == REG
)
1400 register int regno
= REGNO (x
);
1401 register int hash
= HASH (x
, GET_MODE (x
));
1403 /* Remove REGNO from any quantity list it might be on and indicate
1404 that it's value might have changed. If it is a pseudo, remove its
1405 entry from the hash table.
1407 For a hard register, we do the first two actions above for any
1408 additional hard registers corresponding to X. Then, if any of these
1409 registers are in the table, we must remove any REG entries that
1410 overlap these registers. */
1412 delete_reg_equiv (regno
);
1415 if (regno
>= FIRST_PSEUDO_REGISTER
)
1416 remove_from_table (lookup_for_remove (x
, hash
, GET_MODE (x
)), hash
);
1419 int in_table
= TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1420 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1421 int tregno
, tendregno
;
1422 register struct table_elt
*p
, *next
;
1424 CLEAR_HARD_REG_BIT (hard_regs_in_table
, regno
);
1426 for (i
= regno
+ 1; i
< endregno
; i
++)
1428 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, i
);
1429 CLEAR_HARD_REG_BIT (hard_regs_in_table
, i
);
1430 delete_reg_equiv (i
);
1435 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1436 for (p
= table
[hash
]; p
; p
= next
)
1438 next
= p
->next_same_hash
;
1440 if (GET_CODE (p
->exp
) != REG
1441 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1444 tregno
= REGNO (p
->exp
);
1446 = tregno
+ HARD_REGNO_NREGS (tregno
, GET_MODE (p
->exp
));
1447 if (tendregno
> regno
&& tregno
< endregno
)
1448 remove_from_table (p
, hash
);
1455 if (GET_CODE (x
) == SUBREG
)
1457 if (GET_CODE (SUBREG_REG (x
)) != REG
)
1459 invalidate (SUBREG_REG (x
));
1463 /* X is not a register; it must be a memory reference with
1464 a nonvarying address. Remove all hash table elements
1465 that refer to overlapping pieces of memory. */
1467 if (GET_CODE (x
) != MEM
)
1472 /* Registers with nonvarying addresses usually have constant equivalents;
1473 but the frame pointer register is also possible. */
1474 if (GET_CODE (base
) == REG
1475 && REGNO_QTY_VALID_P (REGNO (base
))
1476 && qty_mode
[reg_qty
[REGNO (base
)]] == GET_MODE (base
)
1477 && qty_const
[reg_qty
[REGNO (base
)]] != 0)
1478 base
= qty_const
[reg_qty
[REGNO (base
)]];
1479 else if (GET_CODE (base
) == PLUS
1480 && GET_CODE (XEXP (base
, 1)) == CONST_INT
1481 && GET_CODE (XEXP (base
, 0)) == REG
1482 && REGNO_QTY_VALID_P (REGNO (XEXP (base
, 0)))
1483 && (qty_mode
[reg_qty
[REGNO (XEXP (base
, 0))]]
1484 == GET_MODE (XEXP (base
, 0)))
1485 && qty_const
[reg_qty
[REGNO (XEXP (base
, 0))]])
1487 start
= INTVAL (XEXP (base
, 1));
1488 base
= qty_const
[reg_qty
[REGNO (XEXP (base
, 0))]];
1491 if (GET_CODE (base
) == CONST
)
1492 base
= XEXP (base
, 0);
1493 if (GET_CODE (base
) == PLUS
1494 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
1496 start
+= INTVAL (XEXP (base
, 1));
1497 base
= XEXP (base
, 0);
1500 end
= start
+ GET_MODE_SIZE (GET_MODE (x
));
1501 for (i
= 0; i
< NBUCKETS
; i
++)
1503 register struct table_elt
*next
;
1504 for (p
= table
[i
]; p
; p
= next
)
1506 next
= p
->next_same_hash
;
1507 if (refers_to_mem_p (p
->exp
, base
, start
, end
))
1508 remove_from_table (p
, i
);
1513 /* Remove all expressions that refer to register REGNO,
1514 since they are already invalid, and we are about to
1515 mark that register valid again and don't want the old
1516 expressions to reappear as valid. */
1519 remove_invalid_refs (regno
)
1523 register struct table_elt
*p
, *next
;
1525 for (i
= 0; i
< NBUCKETS
; i
++)
1526 for (p
= table
[i
]; p
; p
= next
)
1528 next
= p
->next_same_hash
;
1529 if (GET_CODE (p
->exp
) != REG
1530 && refers_to_regno_p (regno
, regno
+ 1, p
->exp
, NULL_PTR
))
1531 remove_from_table (p
, i
);
1535 /* Recompute the hash codes of any valid entries in the hash table that
1536 reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
1538 This is called when we make a jump equivalence. */
1541 rehash_using_reg (x
)
1545 struct table_elt
*p
, *next
;
1548 if (GET_CODE (x
) == SUBREG
)
1551 /* If X is not a register or if the register is known not to be in any
1552 valid entries in the table, we have no work to do. */
1554 if (GET_CODE (x
) != REG
1555 || reg_in_table
[REGNO (x
)] < 0
1556 || reg_in_table
[REGNO (x
)] != reg_tick
[REGNO (x
)])
1559 /* Scan all hash chains looking for valid entries that mention X.
1560 If we find one and it is in the wrong hash chain, move it. We can skip
1561 objects that are registers, since they are handled specially. */
1563 for (i
= 0; i
< NBUCKETS
; i
++)
1564 for (p
= table
[i
]; p
; p
= next
)
1566 next
= p
->next_same_hash
;
1567 if (GET_CODE (p
->exp
) != REG
&& reg_mentioned_p (x
, p
->exp
)
1568 && exp_equiv_p (p
->exp
, p
->exp
, 1, 0)
1569 && i
!= (hash
= safe_hash (p
->exp
, p
->mode
) % NBUCKETS
))
1571 if (p
->next_same_hash
)
1572 p
->next_same_hash
->prev_same_hash
= p
->prev_same_hash
;
1574 if (p
->prev_same_hash
)
1575 p
->prev_same_hash
->next_same_hash
= p
->next_same_hash
;
1577 table
[i
] = p
->next_same_hash
;
1579 p
->next_same_hash
= table
[hash
];
1580 p
->prev_same_hash
= 0;
1582 table
[hash
]->prev_same_hash
= p
;
1588 /* Remove from the hash table all expressions that reference memory,
1589 or some of them as specified by *WRITES. */
1592 invalidate_memory (writes
)
1593 struct write_data
*writes
;
1596 register struct table_elt
*p
, *next
;
1597 int all
= writes
->all
;
1598 int nonscalar
= writes
->nonscalar
;
1600 for (i
= 0; i
< NBUCKETS
; i
++)
1601 for (p
= table
[i
]; p
; p
= next
)
1603 next
= p
->next_same_hash
;
1606 || (nonscalar
&& p
->in_struct
)
1607 || cse_rtx_addr_varies_p (p
->exp
)))
1608 remove_from_table (p
, i
);
1612 /* Remove from the hash table any expression that is a call-clobbered
1613 register. Also update their TICK values. */
1616 invalidate_for_call ()
1618 int regno
, endregno
;
1621 struct table_elt
*p
, *next
;
1624 /* Go through all the hard registers. For each that is clobbered in
1625 a CALL_INSN, remove the register from quantity chains and update
1626 reg_tick if defined. Also see if any of these registers is currently
1629 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1630 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
1632 delete_reg_equiv (regno
);
1633 if (reg_tick
[regno
] >= 0)
1636 in_table
|= TEST_HARD_REG_BIT (hard_regs_in_table
, regno
);
1639 /* In the case where we have no call-clobbered hard registers in the
1640 table, we are done. Otherwise, scan the table and remove any
1641 entry that overlaps a call-clobbered register. */
1644 for (hash
= 0; hash
< NBUCKETS
; hash
++)
1645 for (p
= table
[hash
]; p
; p
= next
)
1647 next
= p
->next_same_hash
;
1649 if (GET_CODE (p
->exp
) != REG
1650 || REGNO (p
->exp
) >= FIRST_PSEUDO_REGISTER
)
1653 regno
= REGNO (p
->exp
);
1654 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (p
->exp
));
1656 for (i
= regno
; i
< endregno
; i
++)
1657 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1659 remove_from_table (p
, hash
);
1665 /* Given an expression X of type CONST,
1666 and ELT which is its table entry (or 0 if it
1667 is not in the hash table),
1668 return an alternate expression for X as a register plus integer.
1669 If none can be found, return 0. */
1672 use_related_value (x
, elt
)
1674 struct table_elt
*elt
;
1676 register struct table_elt
*relt
= 0;
1677 register struct table_elt
*p
, *q
;
1678 HOST_WIDE_INT offset
;
1680 /* First, is there anything related known?
1681 If we have a table element, we can tell from that.
1682 Otherwise, must look it up. */
1684 if (elt
!= 0 && elt
->related_value
!= 0)
1686 else if (elt
== 0 && GET_CODE (x
) == CONST
)
1688 rtx subexp
= get_related_value (x
);
1690 relt
= lookup (subexp
,
1691 safe_hash (subexp
, GET_MODE (subexp
)) % NBUCKETS
,
1698 /* Search all related table entries for one that has an
1699 equivalent register. */
1704 /* This loop is strange in that it is executed in two different cases.
1705 The first is when X is already in the table. Then it is searching
1706 the RELATED_VALUE list of X's class (RELT). The second case is when
1707 X is not in the table. Then RELT points to a class for the related
1710 Ensure that, whatever case we are in, that we ignore classes that have
1711 the same value as X. */
1713 if (rtx_equal_p (x
, p
->exp
))
1716 for (q
= p
->first_same_value
; q
; q
= q
->next_same_value
)
1717 if (GET_CODE (q
->exp
) == REG
)
1723 p
= p
->related_value
;
1725 /* We went all the way around, so there is nothing to be found.
1726 Alternatively, perhaps RELT was in the table for some other reason
1727 and it has no related values recorded. */
1728 if (p
== relt
|| p
== 0)
1735 offset
= (get_integer_term (x
) - get_integer_term (p
->exp
));
1736 /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity. */
1737 return plus_constant (q
->exp
, offset
);
1740 /* Hash an rtx. We are careful to make sure the value is never negative.
1741 Equivalent registers hash identically.
1742 MODE is used in hashing for CONST_INTs only;
1743 otherwise the mode of X is used.
1745 Store 1 in do_not_record if any subexpression is volatile.
1747 Store 1 in hash_arg_in_memory if X contains a MEM rtx
1748 which does not have the RTX_UNCHANGING_P bit set.
1749 In this case, also store 1 in hash_arg_in_struct
1750 if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
1752 Note that cse_insn knows that the hash code of a MEM expression
1753 is just (int) MEM plus the hash code of the address. */
1756 canon_hash (x
, mode
)
1758 enum machine_mode mode
;
1761 register int hash
= 0;
1762 register enum rtx_code code
;
1765 /* repeat is used to turn tail-recursion into iteration. */
1770 code
= GET_CODE (x
);
1775 register int regno
= REGNO (x
);
1777 /* On some machines, we can't record any non-fixed hard register,
1778 because extending its life will cause reload problems. We
1779 consider ap, fp, and sp to be fixed for this purpose.
1780 On all machines, we can't record any global registers. */
1782 if (regno
< FIRST_PSEUDO_REGISTER
1783 && (global_regs
[regno
]
1784 #ifdef SMALL_REGISTER_CLASSES
1785 || (! fixed_regs
[regno
]
1786 && regno
!= FRAME_POINTER_REGNUM
1787 && regno
!= ARG_POINTER_REGNUM
1788 && regno
!= STACK_POINTER_REGNUM
)
1795 return hash
+ ((int) REG
<< 7) + reg_qty
[regno
];
1799 hash
+= ((int) mode
+ ((int) CONST_INT
<< 7)
1800 + INTVAL (x
) + (INTVAL (x
) >> HASHBITS
));
1801 return ((1 << HASHBITS
) - 1) & hash
;
1804 /* This is like the general case, except that it only counts
1805 the integers representing the constant. */
1806 hash
+= (int) code
+ (int) GET_MODE (x
);
1809 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
1811 int tem
= XINT (x
, i
);
1812 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1817 /* Assume there is only one rtx object for any given label. */
1819 /* Use `and' to ensure a positive number. */
1820 return (hash
+ ((HOST_WIDE_INT
) LABEL_REF
<< 7)
1821 + ((HOST_WIDE_INT
) XEXP (x
, 0) & ((1 << HASHBITS
) - 1)));
1824 return (hash
+ ((HOST_WIDE_INT
) SYMBOL_REF
<< 7)
1825 + ((HOST_WIDE_INT
) XEXP (x
, 0) & ((1 << HASHBITS
) - 1)));
1828 if (MEM_VOLATILE_P (x
))
1833 if (! RTX_UNCHANGING_P (x
))
1835 hash_arg_in_memory
= 1;
1836 if (MEM_IN_STRUCT_P (x
)) hash_arg_in_struct
= 1;
1838 /* Now that we have already found this special case,
1839 might as well speed it up as much as possible. */
1851 case UNSPEC_VOLATILE
:
1856 if (MEM_VOLATILE_P (x
))
1863 i
= GET_RTX_LENGTH (code
) - 1;
1864 hash
+= (int) code
+ (int) GET_MODE (x
);
1865 fmt
= GET_RTX_FORMAT (code
);
1870 rtx tem
= XEXP (x
, i
);
1873 /* If the operand is a REG that is equivalent to a constant, hash
1874 as if we were hashing the constant, since we will be comparing
1876 if (tem
!= 0 && GET_CODE (tem
) == REG
1877 && REGNO_QTY_VALID_P (REGNO (tem
))
1878 && qty_mode
[reg_qty
[REGNO (tem
)]] == GET_MODE (tem
)
1879 && (tem1
= qty_const
[reg_qty
[REGNO (tem
)]]) != 0
1880 && CONSTANT_P (tem1
))
1883 /* If we are about to do the last recursive call
1884 needed at this level, change it into iteration.
1885 This function is called enough to be worth it. */
1891 hash
+= canon_hash (tem
, 0);
1893 else if (fmt
[i
] == 'E')
1894 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1895 hash
+= canon_hash (XVECEXP (x
, i
, j
), 0);
1896 else if (fmt
[i
] == 's')
1898 register char *p
= XSTR (x
, i
);
1902 register int tem
= *p
++;
1903 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1906 else if (fmt
[i
] == 'i')
1908 register int tem
= XINT (x
, i
);
1909 hash
+= ((1 << HASHBITS
) - 1) & (tem
+ (tem
>> HASHBITS
));
1917 /* Like canon_hash but with no side effects. */
1922 enum machine_mode mode
;
1924 int save_do_not_record
= do_not_record
;
1925 int save_hash_arg_in_memory
= hash_arg_in_memory
;
1926 int save_hash_arg_in_struct
= hash_arg_in_struct
;
1927 int hash
= canon_hash (x
, mode
);
1928 hash_arg_in_memory
= save_hash_arg_in_memory
;
1929 hash_arg_in_struct
= save_hash_arg_in_struct
;
1930 do_not_record
= save_do_not_record
;
1934 /* Return 1 iff X and Y would canonicalize into the same thing,
1935 without actually constructing the canonicalization of either one.
1936 If VALIDATE is nonzero,
1937 we assume X is an expression being processed from the rtl
1938 and Y was found in the hash table. We check register refs
1939 in Y for being marked as valid.
1941 If EQUAL_VALUES is nonzero, we allow a register to match a constant value
1942 that is known to be in the register. Ordinarily, we don't allow them
1943 to match, because letting them match would cause unpredictable results
1944 in all the places that search a hash table chain for an equivalent
1945 for a given value. A possible equivalent that has different structure
1946 has its hash code computed from different data. Whether the hash code
1947 is the same as that of the the given value is pure luck. */
1950 exp_equiv_p (x
, y
, validate
, equal_values
)
1956 register enum rtx_code code
;
1959 /* Note: it is incorrect to assume an expression is equivalent to itself
1960 if VALIDATE is nonzero. */
1961 if (x
== y
&& !validate
)
1963 if (x
== 0 || y
== 0)
1966 code
= GET_CODE (x
);
1967 if (code
!= GET_CODE (y
))
1972 /* If X is a constant and Y is a register or vice versa, they may be
1973 equivalent. We only have to validate if Y is a register. */
1974 if (CONSTANT_P (x
) && GET_CODE (y
) == REG
1975 && REGNO_QTY_VALID_P (REGNO (y
))
1976 && GET_MODE (y
) == qty_mode
[reg_qty
[REGNO (y
)]]
1977 && rtx_equal_p (x
, qty_const
[reg_qty
[REGNO (y
)]])
1978 && (! validate
|| reg_in_table
[REGNO (y
)] == reg_tick
[REGNO (y
)]))
1981 if (CONSTANT_P (y
) && code
== REG
1982 && REGNO_QTY_VALID_P (REGNO (x
))
1983 && GET_MODE (x
) == qty_mode
[reg_qty
[REGNO (x
)]]
1984 && rtx_equal_p (y
, qty_const
[reg_qty
[REGNO (x
)]]))
1990 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1991 if (GET_MODE (x
) != GET_MODE (y
))
2001 return INTVAL (x
) == INTVAL (y
);
2005 return XEXP (x
, 0) == XEXP (y
, 0);
2009 int regno
= REGNO (y
);
2011 = regno
+ (regno
>= FIRST_PSEUDO_REGISTER
? 1
2012 : HARD_REGNO_NREGS (regno
, GET_MODE (y
)));
2015 /* If the quantities are not the same, the expressions are not
2016 equivalent. If there are and we are not to validate, they
2017 are equivalent. Otherwise, ensure all regs are up-to-date. */
2019 if (reg_qty
[REGNO (x
)] != reg_qty
[regno
])
2025 for (i
= regno
; i
< endregno
; i
++)
2026 if (reg_in_table
[i
] != reg_tick
[i
])
2032 /* For commutative operations, check both orders. */
2040 return ((exp_equiv_p (XEXP (x
, 0), XEXP (y
, 0), validate
, equal_values
)
2041 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 1),
2042 validate
, equal_values
))
2043 || (exp_equiv_p (XEXP (x
, 0), XEXP (y
, 1),
2044 validate
, equal_values
)
2045 && exp_equiv_p (XEXP (x
, 1), XEXP (y
, 0),
2046 validate
, equal_values
)));
2049 /* Compare the elements. If any pair of corresponding elements
2050 fail to match, return 0 for the whole things. */
2052 fmt
= GET_RTX_FORMAT (code
);
2053 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2058 if (! exp_equiv_p (XEXP (x
, i
), XEXP (y
, i
), validate
, equal_values
))
2063 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
2065 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2066 if (! exp_equiv_p (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
),
2067 validate
, equal_values
))
2072 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
2077 if (XINT (x
, i
) != XINT (y
, i
))
2082 if (XWINT (x
, i
) != XWINT (y
, i
))
2097 /* Return 1 iff any subexpression of X matches Y.
2098 Here we do not require that X or Y be valid (for registers referred to)
2099 for being in the hash table. */
2106 register enum rtx_code code
;
2112 if (x
== 0 || y
== 0)
2115 code
= GET_CODE (x
);
2116 /* If X as a whole has the same code as Y, they may match.
2118 if (code
== GET_CODE (y
))
2120 if (exp_equiv_p (x
, y
, 0, 1))
2124 /* X does not match, so try its subexpressions. */
2126 fmt
= GET_RTX_FORMAT (code
);
2127 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2136 if (refers_to_p (XEXP (x
, i
), y
))
2139 else if (fmt
[i
] == 'E')
2142 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2143 if (refers_to_p (XVECEXP (x
, i
, j
), y
))
2150 /* Return 1 iff any subexpression of X refers to memory
2151 at an address of BASE plus some offset
2152 such that any of the bytes' offsets fall between START (inclusive)
2153 and END (exclusive).
2155 The value is undefined if X is a varying address.
2156 This function is not used in such cases.
2158 When used in the cse pass, `qty_const' is nonzero, and it is used
2159 to treat an address that is a register with a known constant value
2160 as if it were that constant value.
2161 In the loop pass, `qty_const' is zero, so this is not done. */
2164 refers_to_mem_p (x
, base
, start
, end
)
2166 HOST_WIDE_INT start
, end
;
2168 register HOST_WIDE_INT i
;
2169 register enum rtx_code code
;
2172 if (GET_CODE (base
) == CONST_INT
)
2174 start
+= INTVAL (base
);
2175 end
+= INTVAL (base
);
2183 code
= GET_CODE (x
);
2186 register rtx addr
= XEXP (x
, 0); /* Get the address. */
2190 if (GET_CODE (addr
) == REG
2191 /* qty_const is 0 when outside the cse pass;
2192 at such times, this info is not available. */
2194 && REGNO_QTY_VALID_P (REGNO (addr
))
2195 && GET_MODE (addr
) == qty_mode
[reg_qty
[REGNO (addr
)]]
2196 && qty_const
[reg_qty
[REGNO (addr
)]] != 0)
2197 addr
= qty_const
[reg_qty
[REGNO (addr
)]];
2198 else if (GET_CODE (addr
) == PLUS
2199 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
2200 && GET_CODE (XEXP (addr
, 0)) == REG
2202 && REGNO_QTY_VALID_P (REGNO (XEXP (addr
, 0)))
2203 && (GET_MODE (XEXP (addr
, 0))
2204 == qty_mode
[reg_qty
[REGNO (XEXP (addr
, 0))]])
2205 && qty_const
[reg_qty
[REGNO (XEXP (addr
, 0))]])
2207 i
= INTVAL (XEXP (addr
, 1));
2208 addr
= qty_const
[reg_qty
[REGNO (XEXP (addr
, 0))]];
2212 if (GET_CODE (addr
) == CONST
)
2213 addr
= XEXP (addr
, 0);
2215 /* If ADDR is BASE, or BASE plus an integer, put
2216 the integer in I. */
2217 if (GET_CODE (addr
) == PLUS
2218 && XEXP (addr
, 0) == base
2219 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
)
2220 i
+= INTVAL (XEXP (addr
, 1));
2221 else if (GET_CODE (addr
) == LO_SUM
)
2223 if (GET_CODE (base
) != LO_SUM
)
2225 /* The REG component of the LO_SUM is known by the
2226 const value in the XEXP part. */
2227 addr
= XEXP (addr
, 1);
2228 base
= XEXP (base
, 1);
2230 if (GET_CODE (base
) == CONST
)
2231 base
= XEXP (base
, 0);
2232 if (GET_CODE (base
) == PLUS
2233 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
2235 HOST_WIDE_INT tem
= INTVAL (XEXP (base
, 1));
2238 base
= XEXP (base
, 0);
2242 else if (GET_CODE (base
) == LO_SUM
)
2244 base
= XEXP (base
, 1);
2245 if (GET_CODE (base
) == CONST
)
2246 base
= XEXP (base
, 0);
2247 if (GET_CODE (base
) == PLUS
2248 && GET_CODE (XEXP (base
, 1)) == CONST_INT
)
2250 HOST_WIDE_INT tem
= INTVAL (XEXP (base
, 1));
2253 base
= XEXP (base
, 0);
2257 else if (GET_CODE (addr
) == CONST_INT
&& base
== const0_rtx
)
2259 else if (addr
!= base
)
2262 myend
= i
+ GET_MODE_SIZE (GET_MODE (x
));
2263 return myend
> start
&& i
< end
;
2266 /* X does not match, so try its subexpressions. */
2268 fmt
= GET_RTX_FORMAT (code
);
2269 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2278 if (refers_to_mem_p (XEXP (x
, i
), base
, start
, end
))
2281 else if (fmt
[i
] == 'E')
2284 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2285 if (refers_to_mem_p (XVECEXP (x
, i
, j
), base
, start
, end
))
2292 /* Nonzero if X refers to memory at a varying address;
2293 except that a register which has at the moment a known constant value
2294 isn't considered variable. */
2297 cse_rtx_addr_varies_p (x
)
2300 /* We need not check for X and the equivalence class being of the same
2301 mode because if X is equivalent to a constant in some mode, it
2302 doesn't vary in any mode. */
2304 if (GET_CODE (x
) == MEM
2305 && GET_CODE (XEXP (x
, 0)) == REG
2306 && REGNO_QTY_VALID_P (REGNO (XEXP (x
, 0)))
2307 && GET_MODE (XEXP (x
, 0)) == qty_mode
[reg_qty
[REGNO (XEXP (x
, 0))]]
2308 && qty_const
[reg_qty
[REGNO (XEXP (x
, 0))]] != 0)
2311 if (GET_CODE (x
) == MEM
2312 && GET_CODE (XEXP (x
, 0)) == PLUS
2313 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
2314 && GET_CODE (XEXP (XEXP (x
, 0), 0)) == REG
2315 && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x
, 0), 0)))
2316 && (GET_MODE (XEXP (XEXP (x
, 0), 0))
2317 == qty_mode
[reg_qty
[REGNO (XEXP (XEXP (x
, 0), 0))]])
2318 && qty_const
[reg_qty
[REGNO (XEXP (XEXP (x
, 0), 0))]])
2321 return rtx_addr_varies_p (x
);
2324 /* Canonicalize an expression:
2325 replace each register reference inside it
2326 with the "oldest" equivalent register.
2328 If INSN is non-zero and we are replacing a pseudo with a hard register
2329 or vice versa, verify that INSN remains valid after we make our
2338 register enum rtx_code code
;
2344 code
= GET_CODE (x
);
2362 /* Never replace a hard reg, because hard regs can appear
2363 in more than one machine mode, and we must preserve the mode
2364 of each occurrence. Also, some hard regs appear in
2365 MEMs that are shared and mustn't be altered. Don't try to
2366 replace any reg that maps to a reg of class NO_REGS. */
2367 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
2368 || ! REGNO_QTY_VALID_P (REGNO (x
)))
2371 first
= qty_first_reg
[reg_qty
[REGNO (x
)]];
2372 return (first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
2373 : REGNO_REG_CLASS (first
) == NO_REGS
? x
2374 : gen_rtx (REG
, qty_mode
[reg_qty
[REGNO (x
)]], first
));
2378 fmt
= GET_RTX_FORMAT (code
);
2379 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2385 rtx
new = canon_reg (XEXP (x
, i
), insn
);
2387 /* If replacing pseudo with hard reg or vice versa, ensure the
2388 insn remains valid. Likewise if the insn has MATCH_DUPs. */
2389 if (new && GET_CODE (new) == REG
&& GET_CODE (XEXP (x
, i
)) == REG
2390 && (((REGNO (new) < FIRST_PSEUDO_REGISTER
)
2391 != (REGNO (XEXP (x
, i
)) < FIRST_PSEUDO_REGISTER
))
2392 || (insn
!= 0 && insn_n_dups
[recog_memoized (insn
)] > 0)))
2393 validate_change (insn
, &XEXP (x
, i
), new, 1);
2397 else if (fmt
[i
] == 'E')
2398 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2399 XVECEXP (x
, i
, j
) = canon_reg (XVECEXP (x
, i
, j
), insn
);
2405 /* LOC is a location with INSN that is an operand address (the contents of
2406 a MEM). Find the best equivalent address to use that is valid for this
2409 On most CISC machines, complicated address modes are costly, and rtx_cost
2410 is a good approximation for that cost. However, most RISC machines have
2411 only a few (usually only one) memory reference formats. If an address is
2412 valid at all, it is often just as cheap as any other address. Hence, for
2413 RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
2414 costs of various addresses. For two addresses of equal cost, choose the one
2415 with the highest `rtx_cost' value as that has the potential of eliminating
2416 the most insns. For equal costs, we choose the first in the equivalence
2417 class. Note that we ignore the fact that pseudo registers are cheaper
2418 than hard registers here because we would also prefer the pseudo registers.
2422 find_best_addr (insn
, loc
)
2426 struct table_elt
*elt
, *p
;
2429 int found_better
= 1;
2430 int save_do_not_record
= do_not_record
;
2431 int save_hash_arg_in_memory
= hash_arg_in_memory
;
2432 int save_hash_arg_in_struct
= hash_arg_in_struct
;
2437 /* Do not try to replace constant addresses or addresses of local and
2438 argument slots. These MEM expressions are made only once and inserted
2439 in many instructions, as well as being used to control symbol table
2440 output. It is not safe to clobber them.
2442 There are some uncommon cases where the address is already in a register
2443 for some reason, but we cannot take advantage of that because we have
2444 no easy way to unshare the MEM. In addition, looking up all stack
2445 addresses is costly. */
2446 if ((GET_CODE (addr
) == PLUS
2447 && GET_CODE (XEXP (addr
, 0)) == REG
2448 && GET_CODE (XEXP (addr
, 1)) == CONST_INT
2449 && (regno
= REGNO (XEXP (addr
, 0)),
2450 regno
== FRAME_POINTER_REGNUM
|| regno
== ARG_POINTER_REGNUM
))
2451 || (GET_CODE (addr
) == REG
2452 && (regno
= REGNO (addr
),
2453 regno
== FRAME_POINTER_REGNUM
|| regno
== ARG_POINTER_REGNUM
))
2454 || CONSTANT_ADDRESS_P (addr
))
2457 /* If this address is not simply a register, try to fold it. This will
2458 sometimes simplify the expression. Many simplifications
2459 will not be valid, but some, usually applying the associative rule, will
2460 be valid and produce better code. */
2461 if (GET_CODE (addr
) != REG
2462 && validate_change (insn
, loc
, fold_rtx (addr
, insn
), 0))
2465 /* If this address is not in the hash table, we can't look for equivalences
2466 of the whole address. Also, ignore if volatile. */
2469 hash_code
= HASH (addr
, Pmode
);
2470 addr_volatile
= do_not_record
;
2471 do_not_record
= save_do_not_record
;
2472 hash_arg_in_memory
= save_hash_arg_in_memory
;
2473 hash_arg_in_struct
= save_hash_arg_in_struct
;
2478 elt
= lookup (addr
, hash_code
, Pmode
);
2480 #ifndef ADDRESS_COST
2483 our_cost
= elt
->cost
;
2485 /* Find the lowest cost below ours that works. */
2486 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
2487 if (elt
->cost
< our_cost
2488 && (GET_CODE (elt
->exp
) == REG
2489 || exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
2490 && validate_change (insn
, loc
,
2491 canon_reg (copy_rtx (elt
->exp
), NULL_RTX
), 0))
2498 /* We need to find the best (under the criteria documented above) entry
2499 in the class that is valid. We use the `flag' field to indicate
2500 choices that were invalid and iterate until we can't find a better
2501 one that hasn't already been tried. */
2503 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2506 while (found_better
)
2508 int best_addr_cost
= ADDRESS_COST (*loc
);
2509 int best_rtx_cost
= (elt
->cost
+ 1) >> 1;
2510 struct table_elt
*best_elt
= elt
;
2513 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2515 && (GET_CODE (p
->exp
) == REG
2516 || exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
2517 && (ADDRESS_COST (p
->exp
) < best_addr_cost
2518 || (ADDRESS_COST (p
->exp
) == best_addr_cost
2519 && (p
->cost
+ 1) >> 1 > best_rtx_cost
)))
2522 best_addr_cost
= ADDRESS_COST (p
->exp
);
2523 best_rtx_cost
= (p
->cost
+ 1) >> 1;
2529 if (validate_change (insn
, loc
,
2530 canon_reg (copy_rtx (best_elt
->exp
),
2539 /* If the address is a binary operation with the first operand a register
2540 and the second a constant, do the same as above, but looking for
2541 equivalences of the register. Then try to simplify before checking for
2542 the best address to use. This catches a few cases: First is when we
2543 have REG+const and the register is another REG+const. We can often merge
2544 the constants and eliminate one insn and one register. It may also be
2545 that a machine has a cheap REG+REG+const. Finally, this improves the
2546 code on the Alpha for unaligned byte stores. */
2548 if (flag_expensive_optimizations
2549 && (GET_RTX_CLASS (GET_CODE (*loc
)) == '2'
2550 || GET_RTX_CLASS (GET_CODE (*loc
)) == 'c')
2551 && GET_CODE (XEXP (*loc
, 0)) == REG
2552 && GET_CODE (XEXP (*loc
, 1)) == CONST_INT
)
2554 rtx c
= XEXP (*loc
, 1);
2557 hash_code
= HASH (XEXP (*loc
, 0), Pmode
);
2558 do_not_record
= save_do_not_record
;
2559 hash_arg_in_memory
= save_hash_arg_in_memory
;
2560 hash_arg_in_struct
= save_hash_arg_in_struct
;
2562 elt
= lookup (XEXP (*loc
, 0), hash_code
, Pmode
);
2566 /* We need to find the best (under the criteria documented above) entry
2567 in the class that is valid. We use the `flag' field to indicate
2568 choices that were invalid and iterate until we can't find a better
2569 one that hasn't already been tried. */
2571 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2574 while (found_better
)
2576 int best_addr_cost
= ADDRESS_COST (*loc
);
2577 int best_rtx_cost
= (COST (*loc
) + 1) >> 1;
2578 struct table_elt
*best_elt
= elt
;
2579 rtx best_rtx
= *loc
;
2582 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
2584 && (GET_CODE (p
->exp
) == REG
2585 || exp_equiv_p (p
->exp
, p
->exp
, 1, 0)))
2587 rtx
new = simplify_binary_operation (GET_CODE (*loc
), Pmode
,
2591 new = gen_rtx (GET_CODE (*loc
), Pmode
, p
->exp
, c
);
2593 if ((ADDRESS_COST (new) < best_addr_cost
2594 || (ADDRESS_COST (new) == best_addr_cost
2595 && (COST (new) + 1) >> 1 > best_rtx_cost
)))
2598 best_addr_cost
= ADDRESS_COST (new);
2599 best_rtx_cost
= (COST (new) + 1) >> 1;
2607 if (validate_change (insn
, loc
,
2608 canon_reg (copy_rtx (best_rtx
),
2619 /* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
2620 operation (EQ, NE, GT, etc.), follow it back through the hash table and
2621 what values are being compared.
2623 *PARG1 and *PARG2 are updated to contain the rtx representing the values
2624 actually being compared. For example, if *PARG1 was (cc0) and *PARG2
2625 was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
2626 compared to produce cc0.
2628 The return value is the comparison operator and is either the code of
2629 A or the code corresponding to the inverse of the comparison. */
2631 static enum rtx_code
2632 find_comparison_args (code
, parg1
, parg2
)
2638 arg1
= *parg1
, arg2
= *parg2
;
2640 /* If ARG2 is const0_rtx, see what ARG1 is equivalent to. */
2642 while (arg2
== CONST0_RTX (GET_MODE (arg1
)))
2644 /* Set non-zero when we find something of interest. */
2646 int reverse_code
= 0;
2647 struct table_elt
*p
= 0;
2649 /* If arg1 is a COMPARE, extract the comparison arguments from it.
2650 On machines with CC0, this is the only case that can occur, since
2651 fold_rtx will return the COMPARE or item being compared with zero
2654 if (GET_CODE (arg1
) == COMPARE
&& arg2
== const0_rtx
)
2657 /* If ARG1 is a comparison operator and CODE is testing for
2658 STORE_FLAG_VALUE, get the inner arguments. */
2660 else if (GET_RTX_CLASS (GET_CODE (arg1
)) == '<')
2663 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
2664 && code
== LT
&& STORE_FLAG_VALUE
== -1)
2665 #ifdef FLOAT_STORE_FLAG_VALUE
2666 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_FLOAT
2667 && FLOAT_STORE_FLAG_VALUE
< 0)
2672 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_INT
2673 && code
== GE
&& STORE_FLAG_VALUE
== -1)
2674 #ifdef FLOAT_STORE_FLAG_VALUE
2675 || (GET_MODE_CLASS (GET_MODE (arg1
)) == MODE_FLOAT
2676 && FLOAT_STORE_FLAG_VALUE
< 0)
2679 x
= arg1
, reverse_code
= 1;
2682 /* ??? We could also check for
2684 (ne (and (eq (...) (const_int 1))) (const_int 0))
2686 and related forms, but let's wait until we see them occurring. */
2689 /* Look up ARG1 in the hash table and see if it has an equivalence
2690 that lets us see what is being compared. */
2691 p
= lookup (arg1
, safe_hash (arg1
, GET_MODE (arg1
)) % NBUCKETS
,
2693 if (p
) p
= p
->first_same_value
;
2695 for (; p
; p
= p
->next_same_value
)
2697 enum machine_mode inner_mode
= GET_MODE (p
->exp
);
2699 /* If the entry isn't valid, skip it. */
2700 if (! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
2703 if (GET_CODE (p
->exp
) == COMPARE
2704 /* Another possibility is that this machine has a compare insn
2705 that includes the comparison code. In that case, ARG1 would
2706 be equivalent to a comparison operation that would set ARG1 to
2707 either STORE_FLAG_VALUE or zero. If this is an NE operation,
2708 ORIG_CODE is the actual comparison being done; if it is an EQ,
2709 we must reverse ORIG_CODE. On machine with a negative value
2710 for STORE_FLAG_VALUE, also look at LT and GE operations. */
2713 && GET_MODE_CLASS (inner_mode
) == MODE_INT
2714 && (GET_MODE_BITSIZE (inner_mode
)
2715 <= HOST_BITS_PER_WIDE_INT
)
2716 && (STORE_FLAG_VALUE
2717 & ((HOST_WIDE_INT
) 1
2718 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
2719 #ifdef FLOAT_STORE_FLAG_VALUE
2721 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
2722 && FLOAT_STORE_FLAG_VALUE
< 0)
2725 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<'))
2730 else if ((code
== EQ
2732 && GET_MODE_CLASS (inner_mode
) == MODE_INT
2733 && (GET_MODE_BITSIZE (inner_mode
)
2734 <= HOST_BITS_PER_WIDE_INT
)
2735 && (STORE_FLAG_VALUE
2736 & ((HOST_WIDE_INT
) 1
2737 << (GET_MODE_BITSIZE (inner_mode
) - 1))))
2738 #ifdef FLOAT_STORE_FLAG_VALUE
2740 && GET_MODE_CLASS (inner_mode
) == MODE_FLOAT
2741 && FLOAT_STORE_FLAG_VALUE
< 0)
2744 && GET_RTX_CLASS (GET_CODE (p
->exp
)) == '<')
2751 /* If this is fp + constant, the equivalent is a better operand since
2752 it may let us predict the value of the comparison. */
2753 else if (NONZERO_BASE_PLUS_P (p
->exp
))
2760 /* If we didn't find a useful equivalence for ARG1, we are done.
2761 Otherwise, set up for the next iteration. */
2765 arg1
= XEXP (x
, 0), arg2
= XEXP (x
, 1);
2766 if (GET_RTX_CLASS (GET_CODE (x
)) == '<')
2767 code
= GET_CODE (x
);
2770 code
= reverse_condition (code
);
2773 /* Return our results. */
2774 *parg1
= fold_rtx (arg1
, 0), *parg2
= fold_rtx (arg2
, 0);
2779 /* Try to simplify a unary operation CODE whose output mode is to be
2780 MODE with input operand OP whose mode was originally OP_MODE.
2781 Return zero if no simplification can be made. */
2784 simplify_unary_operation (code
, mode
, op
, op_mode
)
2786 enum machine_mode mode
;
2788 enum machine_mode op_mode
;
2790 register int width
= GET_MODE_BITSIZE (mode
);
2792 /* The order of these tests is critical so that, for example, we don't
2793 check the wrong mode (input vs. output) for a conversion operation,
2794 such as FIX. At some point, this should be simplified. */
2796 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
2797 if (code
== FLOAT
&& GET_CODE (op
) == CONST_INT
)
2801 #ifdef REAL_ARITHMETIC
2802 REAL_VALUE_FROM_INT (d
, INTVAL (op
), INTVAL (op
) < 0 ? ~0 : 0);
2804 d
= (double) INTVAL (op
);
2806 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2808 else if (code
== UNSIGNED_FLOAT
&& GET_CODE (op
) == CONST_INT
)
2812 #ifdef REAL_ARITHMETIC
2813 REAL_VALUE_FROM_INT (d
, INTVAL (op
), 0);
2815 d
= (double) (unsigned int) INTVAL (op
);
2817 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2820 else if (code
== FLOAT
&& GET_CODE (op
) == CONST_DOUBLE
2821 && GET_MODE (op
) == VOIDmode
)
2825 #ifdef REAL_ARITHMETIC
2826 REAL_VALUE_FROM_INT (d
, CONST_DOUBLE_LOW (op
), CONST_DOUBLE_HIGH (op
));
2828 if (CONST_DOUBLE_HIGH (op
) < 0)
2830 d
= (double) (~ CONST_DOUBLE_HIGH (op
));
2831 d
*= ((double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2))
2832 * (double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2)));
2833 d
+= (double) (unsigned HOST_WIDE_INT
) (~ CONST_DOUBLE_LOW (op
));
2838 d
= (double) CONST_DOUBLE_HIGH (op
);
2839 d
*= ((double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2))
2840 * (double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2)));
2841 d
+= (double) (unsigned HOST_WIDE_INT
) CONST_DOUBLE_LOW (op
);
2843 #endif /* REAL_ARITHMETIC */
2844 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2846 else if (code
== UNSIGNED_FLOAT
&& GET_CODE (op
) == CONST_DOUBLE
2847 && GET_MODE (op
) == VOIDmode
)
2851 #ifdef REAL_ARITHMETIC
2852 REAL_VALUE_FROM_UNSIGNED_INT (d
, CONST_DOUBLE_LOW (op
),
2853 CONST_DOUBLE_HIGH (op
));
2855 d
= (double) CONST_DOUBLE_HIGH (op
);
2856 d
*= ((double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2))
2857 * (double) ((HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
/ 2)));
2858 d
+= (double) (unsigned HOST_WIDE_INT
) CONST_DOUBLE_LOW (op
);
2859 #endif /* REAL_ARITHMETIC */
2860 return CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
);
2864 if (GET_CODE (op
) == CONST_INT
2865 && width
<= HOST_BITS_PER_WIDE_INT
&& width
> 0)
2867 register HOST_WIDE_INT arg0
= INTVAL (op
);
2868 register HOST_WIDE_INT val
;
2881 val
= (arg0
>= 0 ? arg0
: - arg0
);
2885 /* Don't use ffs here. Instead, get low order bit and then its
2886 number. If arg0 is zero, this will return 0, as desired. */
2887 arg0
&= GET_MODE_MASK (mode
);
2888 val
= exact_log2 (arg0
& (- arg0
)) + 1;
2896 if (op_mode
== VOIDmode
)
2898 if (GET_MODE_BITSIZE (op_mode
) == HOST_BITS_PER_WIDE_INT
)
2900 /* If we were really extending the mode,
2901 we would have to distinguish between zero-extension
2902 and sign-extension. */
2903 if (width
!= GET_MODE_BITSIZE (op_mode
))
2907 else if (GET_MODE_BITSIZE (op_mode
) < HOST_BITS_PER_WIDE_INT
)
2908 val
= arg0
& ~((HOST_WIDE_INT
) (-1) << GET_MODE_BITSIZE (op_mode
));
2914 if (op_mode
== VOIDmode
)
2916 if (GET_MODE_BITSIZE (op_mode
) == HOST_BITS_PER_WIDE_INT
)
2918 /* If we were really extending the mode,
2919 we would have to distinguish between zero-extension
2920 and sign-extension. */
2921 if (width
!= GET_MODE_BITSIZE (op_mode
))
2925 else if (GET_MODE_BITSIZE (op_mode
) < HOST_BITS_PER_INT
)
2928 = arg0
& ~((HOST_WIDE_INT
) (-1) << GET_MODE_BITSIZE (op_mode
));
2930 & ((HOST_WIDE_INT
) 1 << (GET_MODE_BITSIZE (op_mode
) - 1)))
2931 val
-= (HOST_WIDE_INT
) 1 << GET_MODE_BITSIZE (op_mode
);
2944 /* Clear the bits that don't belong in our mode,
2945 unless they and our sign bit are all one.
2946 So we get either a reasonable negative value or a reasonable
2947 unsigned value for this mode. */
2948 if (width
< HOST_BITS_PER_WIDE_INT
2949 && ((val
& ((HOST_WIDE_INT
) (-1) << (width
- 1)))
2950 != ((HOST_WIDE_INT
) (-1) << (width
- 1))))
2951 val
&= (1 << width
) - 1;
2953 return GEN_INT (val
);
2956 /* We can do some operations on integer CONST_DOUBLEs. Also allow
2957 for a DImode operation on a CONST_INT. */
2958 else if (GET_MODE (op
) == VOIDmode
2959 && (GET_CODE (op
) == CONST_DOUBLE
|| GET_CODE (op
) == CONST_INT
))
2961 HOST_WIDE_INT l1
, h1
, lv
, hv
;
2963 if (GET_CODE (op
) == CONST_DOUBLE
)
2964 l1
= CONST_DOUBLE_LOW (op
), h1
= CONST_DOUBLE_HIGH (op
);
2966 l1
= INTVAL (op
), h1
= l1
< 0 ? -1 : 0;
2976 neg_double (l1
, h1
, &lv
, &hv
);
2981 neg_double (l1
, h1
, &lv
, &hv
);
2989 lv
= HOST_BITS_PER_WIDE_INT
+ exact_log2 (h1
& (-h1
)) + 1;
2991 lv
= exact_log2 (l1
& (-l1
)) + 1;
2995 if (GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
2996 return GEN_INT (l1
& GET_MODE_MASK (mode
));
3002 if (op_mode
== VOIDmode
3003 || GET_MODE_BITSIZE (op_mode
) > HOST_BITS_PER_WIDE_INT
)
3007 lv
= l1
& GET_MODE_MASK (op_mode
);
3011 if (op_mode
== VOIDmode
3012 || GET_MODE_BITSIZE (op_mode
) > HOST_BITS_PER_WIDE_INT
)
3016 lv
= l1
& GET_MODE_MASK (op_mode
);
3017 if (GET_MODE_BITSIZE (op_mode
) < HOST_BITS_PER_WIDE_INT
3018 && (lv
& ((HOST_WIDE_INT
) 1
3019 << (GET_MODE_BITSIZE (op_mode
) - 1))) != 0)
3020 lv
-= (HOST_WIDE_INT
) 1 << GET_MODE_BITSIZE (op_mode
);
3022 hv
= (lv
< 0) ? ~ (HOST_WIDE_INT
) 0 : 0;
3033 return immed_double_const (lv
, hv
, mode
);
3036 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3037 else if (GET_CODE (op
) == CONST_DOUBLE
3038 && GET_MODE_CLASS (mode
) == MODE_FLOAT
)
3044 if (setjmp (handler
))
3045 /* There used to be a warning here, but that is inadvisable.
3046 People may want to cause traps, and the natural way
3047 to do it should not get a warning. */
3050 set_float_handler (handler
);
3052 REAL_VALUE_FROM_CONST_DOUBLE (d
, op
);
3057 d
= REAL_VALUE_NEGATE (d
);
3061 if (REAL_VALUE_NEGATIVE (d
))
3062 d
= REAL_VALUE_NEGATE (d
);
3065 case FLOAT_TRUNCATE
:
3066 d
= (double) real_value_truncate (mode
, d
);
3070 /* All this does is change the mode. */
3074 d
= (double) REAL_VALUE_FIX_TRUNCATE (d
);
3078 d
= (double) REAL_VALUE_UNSIGNED_FIX_TRUNCATE (d
);
3088 x
= immed_real_const_1 (d
, mode
);
3089 set_float_handler (NULL_PTR
);
3092 else if (GET_CODE (op
) == CONST_DOUBLE
&& GET_MODE_CLASS (mode
) == MODE_INT
3093 && width
<= HOST_BITS_PER_WIDE_INT
&& width
> 0)
3100 if (setjmp (handler
))
3103 set_float_handler (handler
);
3105 REAL_VALUE_FROM_CONST_DOUBLE (d
, op
);
3110 val
= REAL_VALUE_FIX (d
);
3114 val
= REAL_VALUE_UNSIGNED_FIX (d
);
3121 set_float_handler (NULL_PTR
);
3123 /* Clear the bits that don't belong in our mode,
3124 unless they and our sign bit are all one.
3125 So we get either a reasonable negative value or a reasonable
3126 unsigned value for this mode. */
3127 if (width
< HOST_BITS_PER_WIDE_INT
3128 && ((val
& ((HOST_WIDE_INT
) (-1) << (width
- 1)))
3129 != ((HOST_WIDE_INT
) (-1) << (width
- 1))))
3130 val
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
3132 return GEN_INT (val
);
3135 /* This was formerly used only for non-IEEE float.
3136 eggert@twinsun.com says it is safe for IEEE also. */
3139 /* There are some simplifications we can do even if the operands
3145 /* (not (not X)) == X, similarly for NEG. */
3146 if (GET_CODE (op
) == code
)
3147 return XEXP (op
, 0);
3151 /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
3152 becomes just the MINUS if its mode is MODE. This allows
3153 folding switch statements on machines using casesi (such as
3155 if (GET_CODE (op
) == TRUNCATE
3156 && GET_MODE (XEXP (op
, 0)) == mode
3157 && GET_CODE (XEXP (op
, 0)) == MINUS
3158 && GET_CODE (XEXP (XEXP (op
, 0), 0)) == LABEL_REF
3159 && GET_CODE (XEXP (XEXP (op
, 0), 1)) == LABEL_REF
)
3160 return XEXP (op
, 0);
3168 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
3169 and OP1. Return 0 if no simplification is possible.
3171 Don't use this for relational operations such as EQ or LT.
3172 Use simplify_relational_operation instead. */
3175 simplify_binary_operation (code
, mode
, op0
, op1
)
3177 enum machine_mode mode
;
3180 register HOST_WIDE_INT arg0
, arg1
, arg0s
, arg1s
;
3182 int width
= GET_MODE_BITSIZE (mode
);
3184 /* Relational operations don't work here. We must know the mode
3185 of the operands in order to do the comparison correctly.
3186 Assuming a full word can give incorrect results.
3187 Consider comparing 128 with -128 in QImode. */
3189 if (GET_RTX_CLASS (code
) == '<')
3192 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3193 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
3194 && GET_CODE (op0
) == CONST_DOUBLE
&& GET_CODE (op1
) == CONST_DOUBLE
3195 && mode
== GET_MODE (op0
) && mode
== GET_MODE (op1
))
3197 REAL_VALUE_TYPE f0
, f1
, value
;
3200 if (setjmp (handler
))
3203 set_float_handler (handler
);
3205 REAL_VALUE_FROM_CONST_DOUBLE (f0
, op0
);
3206 REAL_VALUE_FROM_CONST_DOUBLE (f1
, op1
);
3207 f0
= real_value_truncate (mode
, f0
);
3208 f1
= real_value_truncate (mode
, f1
);
3210 #ifdef REAL_ARITHMETIC
3211 REAL_ARITHMETIC (value
, code
, f0
, f1
);
3225 #ifndef REAL_INFINITY
3232 value
= MIN (f0
, f1
);
3235 value
= MAX (f0
, f1
);
3242 set_float_handler (NULL_PTR
);
3243 value
= real_value_truncate (mode
, value
);
3244 return immed_real_const_1 (value
, mode
);
3247 /* We can fold some multi-word operations. */
3248 else if (GET_MODE_CLASS (mode
) == MODE_INT
3249 && GET_CODE (op0
) == CONST_DOUBLE
3250 && (GET_CODE (op1
) == CONST_DOUBLE
|| GET_CODE (op1
) == CONST_INT
))
3252 HOST_WIDE_INT l1
, l2
, h1
, h2
, lv
, hv
;
3254 l1
= CONST_DOUBLE_LOW (op0
), h1
= CONST_DOUBLE_HIGH (op0
);
3256 if (GET_CODE (op1
) == CONST_DOUBLE
)
3257 l2
= CONST_DOUBLE_LOW (op1
), h2
= CONST_DOUBLE_HIGH (op1
);
3259 l2
= INTVAL (op1
), h2
= l2
< 0 ? -1 : 0;
3264 /* A - B == A + (-B). */
3265 neg_double (l2
, h2
, &lv
, &hv
);
3268 /* .. fall through ... */
3271 add_double (l1
, h1
, l2
, h2
, &lv
, &hv
);
3275 mul_double (l1
, h1
, l2
, h2
, &lv
, &hv
);
3278 case DIV
: case MOD
: case UDIV
: case UMOD
:
3279 /* We'd need to include tree.h to do this and it doesn't seem worth
3284 lv
= l1
& l2
, hv
= h1
& h2
;
3288 lv
= l1
| l2
, hv
= h1
| h2
;
3292 lv
= l1
^ l2
, hv
= h1
^ h2
;
3298 && ((unsigned HOST_WIDE_INT
) l1
3299 < (unsigned HOST_WIDE_INT
) l2
)))
3308 && ((unsigned HOST_WIDE_INT
) l1
3309 > (unsigned HOST_WIDE_INT
) l2
)))
3316 if ((unsigned HOST_WIDE_INT
) h1
< (unsigned HOST_WIDE_INT
) h2
3318 && ((unsigned HOST_WIDE_INT
) l1
3319 < (unsigned HOST_WIDE_INT
) l2
)))
3326 if ((unsigned HOST_WIDE_INT
) h1
> (unsigned HOST_WIDE_INT
) h2
3328 && ((unsigned HOST_WIDE_INT
) l1
3329 > (unsigned HOST_WIDE_INT
) l2
)))
3335 case LSHIFTRT
: case ASHIFTRT
:
3336 case ASHIFT
: case LSHIFT
:
3337 case ROTATE
: case ROTATERT
:
3338 #ifdef SHIFT_COUNT_TRUNCATED
3339 l2
&= (GET_MODE_BITSIZE (mode
) - 1), h2
= 0;
3342 if (h2
!= 0 || l2
< 0 || l2
>= GET_MODE_BITSIZE (mode
))
3345 if (code
== LSHIFTRT
|| code
== ASHIFTRT
)
3346 rshift_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
,
3348 else if (code
== ASHIFT
|| code
== LSHIFT
)
3349 lshift_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
,
3351 else if (code
== ROTATE
)
3352 lrotate_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
);
3353 else /* code == ROTATERT */
3354 rrotate_double (l1
, h1
, l2
, GET_MODE_BITSIZE (mode
), &lv
, &hv
);
3361 return immed_double_const (lv
, hv
, mode
);
3363 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
3365 if (GET_CODE (op0
) != CONST_INT
|| GET_CODE (op1
) != CONST_INT
3366 || width
> HOST_BITS_PER_WIDE_INT
|| width
== 0)
3368 /* Even if we can't compute a constant result,
3369 there are some cases worth simplifying. */
3374 /* In IEEE floating point, x+0 is not the same as x. Similarly
3375 for the other optimizations below. */
3376 if (TARGET_FLOAT_FORMAT
== IEEE_FLOAT_FORMAT
3377 && GET_MODE_CLASS (mode
) != MODE_INT
)
3380 if (op1
== CONST0_RTX (mode
))
3383 /* Strip off any surrounding CONSTs. They don't matter in any of
3385 if (GET_CODE (op0
) == CONST
)
3386 op0
= XEXP (op0
, 0);
3387 if (GET_CODE (op1
) == CONST
)
3388 op1
= XEXP (op1
, 0);
3390 /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
3391 if (GET_CODE (op0
) == NEG
)
3393 rtx tem
= simplify_binary_operation (MINUS
, mode
,
3394 op1
, XEXP (op0
, 0));
3395 return tem
? tem
: gen_rtx (MINUS
, mode
, op1
, XEXP (op0
, 0));
3397 else if (GET_CODE (op1
) == NEG
)
3399 rtx tem
= simplify_binary_operation (MINUS
, mode
,
3400 op0
, XEXP (op1
, 0));
3401 return tem
? tem
: gen_rtx (MINUS
, mode
, op0
, XEXP (op1
, 0));
3404 /* Don't use the associative law for floating point.
3405 The inaccuracy makes it nonassociative,
3406 and subtle programs can break if operations are associated. */
3407 if (GET_MODE_CLASS (mode
) != MODE_INT
)
3410 /* (a - b) + b -> a, similarly a + (b - a) -> a */
3411 if (GET_CODE (op0
) == MINUS
3412 && rtx_equal_p (XEXP (op0
, 1), op1
) && ! side_effects_p (op1
))
3413 return XEXP (op0
, 0);
3415 if (GET_CODE (op1
) == MINUS
3416 && rtx_equal_p (XEXP (op1
, 1), op0
) && ! side_effects_p (op0
))
3417 return XEXP (op1
, 0);
3419 /* (c1 - a) + c2 becomes (c1 + c2) - a. */
3420 if (GET_CODE (op1
) == CONST_INT
&& GET_CODE (op0
) == MINUS
3421 && GET_CODE (XEXP (op0
, 0)) == CONST_INT
)
3423 rtx tem
= simplify_binary_operation (PLUS
, mode
, op1
,
3426 return tem
? gen_rtx (MINUS
, mode
, tem
, XEXP (op0
, 1)) : 0;
3429 /* Handle both-operands-constant cases. */
3430 if (CONSTANT_P (op0
) && CONSTANT_P (op1
)
3431 && GET_CODE (op0
) != CONST_DOUBLE
3432 && GET_CODE (op1
) != CONST_DOUBLE
3433 && GET_MODE_CLASS (mode
) == MODE_INT
)
3435 if (GET_CODE (op1
) == CONST_INT
)
3436 return plus_constant (op0
, INTVAL (op1
));
3437 else if (GET_CODE (op0
) == CONST_INT
)
3438 return plus_constant (op1
, INTVAL (op0
));
3441 #if 0 /* No good, because this can produce the sum of two relocatable
3442 symbols, in an assembler instruction. Most UNIX assemblers can't
3445 return gen_rtx (CONST
, mode
,
3446 gen_rtx (PLUS
, mode
,
3447 GET_CODE (op0
) == CONST
3448 ? XEXP (op0
, 0) : op0
,
3449 GET_CODE (op1
) == CONST
3450 ? XEXP (op1
, 0) : op1
));
3453 else if (GET_CODE (op1
) == CONST_INT
3454 && GET_CODE (op0
) == PLUS
3455 && (CONSTANT_P (XEXP (op0
, 0))
3456 || CONSTANT_P (XEXP (op0
, 1))))
3457 /* constant + (variable + constant)
3458 can result if an index register is made constant.
3459 We simplify this by adding the constants.
3460 If we did not, it would become an invalid address. */
3461 return plus_constant (op0
, INTVAL (op1
));
3466 /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
3467 using cc0, in which case we want to leave it as a COMPARE
3468 so we can distinguish it from a register-register-copy.
3470 In IEEE floating point, x-0 is not the same as x. */
3472 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3473 || GET_MODE_CLASS (mode
) == MODE_INT
)
3474 && op1
== CONST0_RTX (mode
))
3477 /* Do nothing here. */
3482 /* None of these optimizations can be done for IEEE
3484 if (TARGET_FLOAT_FORMAT
== IEEE_FLOAT_FORMAT
3485 && GET_MODE_CLASS (mode
) != MODE_INT
)
3488 /* We can't assume x-x is 0 even with non-IEEE floating point. */
3489 if (rtx_equal_p (op0
, op1
)
3490 && ! side_effects_p (op0
)
3491 && GET_MODE_CLASS (mode
) != MODE_FLOAT
)
3494 /* Change subtraction from zero into negation. */
3495 if (op0
== CONST0_RTX (mode
))
3496 return gen_rtx (NEG
, mode
, op1
);
3498 /* Subtracting 0 has no effect. */
3499 if (op1
== CONST0_RTX (mode
))
3502 /* Strip off any surrounding CONSTs. They don't matter in any of
3504 if (GET_CODE (op0
) == CONST
)
3505 op0
= XEXP (op0
, 0);
3506 if (GET_CODE (op1
) == CONST
)
3507 op1
= XEXP (op1
, 0);
3509 /* (a - (-b)) -> (a + b). */
3510 if (GET_CODE (op1
) == NEG
)
3512 rtx tem
= simplify_binary_operation (PLUS
, mode
,
3513 op0
, XEXP (op1
, 0));
3514 return tem
? tem
: gen_rtx (PLUS
, mode
, op0
, XEXP (op1
, 0));
3517 /* Don't use the associative law for floating point.
3518 The inaccuracy makes it nonassociative,
3519 and subtle programs can break if operations are associated. */
3520 if (GET_MODE_CLASS (mode
) != MODE_INT
)
3523 /* (a + b) - a -> b, and (b - (a + b)) -> -a */
3524 if (GET_CODE (op0
) == PLUS
3525 && rtx_equal_p (XEXP (op0
, 0), op1
)
3526 && ! side_effects_p (op1
))
3527 return XEXP (op0
, 1);
3528 else if (GET_CODE (op0
) == PLUS
3529 && rtx_equal_p (XEXP (op0
, 1), op1
)
3530 && ! side_effects_p (op1
))
3531 return XEXP (op0
, 0);
3533 if (GET_CODE (op1
) == PLUS
3534 && rtx_equal_p (XEXP (op1
, 0), op0
)
3535 && ! side_effects_p (op0
))
3537 rtx tem
= simplify_unary_operation (NEG
, mode
, XEXP (op1
, 1),
3540 return tem
? tem
: gen_rtx (NEG
, mode
, XEXP (op1
, 1));
3542 else if (GET_CODE (op1
) == PLUS
3543 && rtx_equal_p (XEXP (op1
, 1), op0
)
3544 && ! side_effects_p (op0
))
3546 rtx tem
= simplify_unary_operation (NEG
, mode
, XEXP (op1
, 0),
3549 return tem
? tem
: gen_rtx (NEG
, mode
, XEXP (op1
, 0));
3552 /* a - (a - b) -> b */
3553 if (GET_CODE (op1
) == MINUS
&& rtx_equal_p (op0
, XEXP (op1
, 0))
3554 && ! side_effects_p (op0
))
3555 return XEXP (op1
, 1);
3557 /* (a +/- b) - (a +/- c) can be simplified. Do variants of
3558 this involving commutativity. The most common case is
3559 (a + C1) - (a + C2), but it's not hard to do all the cases. */
3560 if ((GET_CODE (op0
) == PLUS
|| GET_CODE (op0
) == MINUS
)
3561 && (GET_CODE (op1
) == PLUS
|| GET_CODE (op1
) == MINUS
))
3563 rtx lhs0
= XEXP (op0
, 0), lhs1
= XEXP (op0
, 1);
3564 rtx rhs0
= XEXP (op1
, 0), rhs1
= XEXP (op1
, 1);
3565 int lhs_neg
= GET_CODE (op0
) == MINUS
;
3566 int rhs_neg
= GET_CODE (op1
) == MINUS
;
3567 rtx lhs
= 0, rhs
= 0;
3569 /* Set LHS and RHS to the two different terms. */
3570 if (rtx_equal_p (lhs0
, rhs0
) && ! side_effects_p (lhs0
))
3571 lhs
= lhs1
, rhs
= rhs1
;
3572 else if (! rhs_neg
&& rtx_equal_p (lhs0
, rhs1
)
3573 && ! side_effects_p (lhs0
))
3574 lhs
= lhs1
, rhs
= rhs0
;
3575 else if (! lhs_neg
&& rtx_equal_p (lhs1
, rhs0
)
3576 && ! side_effects_p (lhs1
))
3577 lhs
= lhs0
, rhs
= rhs1
;
3578 else if (! lhs_neg
&& ! rhs_neg
&& rtx_equal_p (lhs1
, rhs1
)
3579 && ! side_effects_p (lhs1
))
3580 lhs
= lhs0
, rhs
= rhs0
;
3582 /* The RHS is the operand of a MINUS, so its negation
3583 status should be complemented. */
3584 rhs_neg
= ! rhs_neg
;
3586 /* If we found two values equal, form the sum or difference
3587 of the remaining two terms. */
3590 rtx tem
= simplify_binary_operation (lhs_neg
== rhs_neg
3593 lhs_neg
? rhs
: lhs
,
3594 lhs_neg
? lhs
: rhs
);
3596 tem
= gen_rtx (lhs_neg
== rhs_neg
3598 mode
, lhs_neg
? rhs
: lhs
,
3599 lhs_neg
? lhs
: rhs
);
3601 /* If both sides negated, negate result. */
3602 if (lhs_neg
&& rhs_neg
)
3605 = simplify_unary_operation (NEG
, mode
, tem
, mode
);
3607 tem1
= gen_rtx (NEG
, mode
, tem
);
3617 /* c1 - (a + c2) becomes (c1 - c2) - a. */
3618 if (GET_CODE (op0
) == CONST_INT
&& GET_CODE (op1
) == PLUS
3619 && GET_CODE (XEXP (op1
, 1)) == CONST_INT
)
3621 rtx tem
= simplify_binary_operation (MINUS
, mode
, op0
,
3624 return tem
? gen_rtx (MINUS
, mode
, tem
, XEXP (op1
, 0)) : 0;
3627 /* c1 - (c2 - a) becomes (c1 - c2) + a. */
3628 if (GET_CODE (op0
) == CONST_INT
&& GET_CODE (op1
) == MINUS
3629 && GET_CODE (XEXP (op1
, 0)) == CONST_INT
)
3631 rtx tem
= simplify_binary_operation (MINUS
, mode
, op0
,
3634 return (tem
&& GET_CODE (tem
) == CONST_INT
3635 ? plus_constant (XEXP (op1
, 1), INTVAL (tem
))
3639 /* Don't let a relocatable value get a negative coeff. */
3640 if (GET_CODE (op1
) == CONST_INT
)
3641 return plus_constant (op0
, - INTVAL (op1
));
3645 if (op1
== constm1_rtx
)
3647 rtx tem
= simplify_unary_operation (NEG
, mode
, op0
, mode
);
3649 return tem
? tem
: gen_rtx (NEG
, mode
, op0
);
3652 /* In IEEE floating point, x*0 is not always 0. */
3653 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3654 || GET_MODE_CLASS (mode
) == MODE_INT
)
3655 && op1
== CONST0_RTX (mode
)
3656 && ! side_effects_p (op0
))
3659 /* In IEEE floating point, x*1 is not equivalent to x for nans.
3660 However, ANSI says we can drop signals,
3661 so we can do this anyway. */
3662 if (op1
== CONST1_RTX (mode
))
3665 /* Convert multiply by constant power of two into shift. */
3666 if (GET_CODE (op1
) == CONST_INT
3667 && (val
= exact_log2 (INTVAL (op1
))) >= 0)
3668 return gen_rtx (ASHIFT
, mode
, op0
, GEN_INT (val
));
3670 if (GET_CODE (op1
) == CONST_DOUBLE
3671 && GET_MODE_CLASS (GET_MODE (op1
)) == MODE_FLOAT
)
3674 REAL_VALUE_FROM_CONST_DOUBLE (d
, op1
);
3676 /* x*2 is x+x and x*(-1) is -x */
3677 if (REAL_VALUES_EQUAL (d
, dconst2
)
3678 && GET_MODE (op0
) == mode
)
3679 return gen_rtx (PLUS
, mode
, op0
, copy_rtx (op0
));
3681 else if (REAL_VALUES_EQUAL (d
, dconstm1
)
3682 && GET_MODE (op0
) == mode
)
3683 return gen_rtx (NEG
, mode
, op0
);
3688 if (op1
== const0_rtx
)
3690 if (GET_CODE (op1
) == CONST_INT
3691 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3693 if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3695 /* A | (~A) -> -1 */
3696 if (((GET_CODE (op0
) == NOT
&& rtx_equal_p (XEXP (op0
, 0), op1
))
3697 || (GET_CODE (op1
) == NOT
&& rtx_equal_p (XEXP (op1
, 0), op0
)))
3698 && ! side_effects_p (op0
))
3703 if (op1
== const0_rtx
)
3705 if (GET_CODE (op1
) == CONST_INT
3706 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3707 return gen_rtx (NOT
, mode
, op0
);
3708 if (op0
== op1
&& ! side_effects_p (op0
))
3713 if (op1
== const0_rtx
&& ! side_effects_p (op0
))
3715 if (GET_CODE (op1
) == CONST_INT
3716 && (INTVAL (op1
) & GET_MODE_MASK (mode
)) == GET_MODE_MASK (mode
))
3718 if (op0
== op1
&& ! side_effects_p (op0
))
3721 if (((GET_CODE (op0
) == NOT
&& rtx_equal_p (XEXP (op0
, 0), op1
))
3722 || (GET_CODE (op1
) == NOT
&& rtx_equal_p (XEXP (op1
, 0), op0
)))
3723 && ! side_effects_p (op0
))
3728 /* Convert divide by power of two into shift (divide by 1 handled
3730 if (GET_CODE (op1
) == CONST_INT
3731 && (arg1
= exact_log2 (INTVAL (op1
))) > 0)
3732 return gen_rtx (LSHIFTRT
, mode
, op0
, GEN_INT (arg1
));
3734 /* ... fall through ... */
3737 if (op1
== CONST1_RTX (mode
))
3740 /* In IEEE floating point, 0/x is not always 0. */
3741 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
3742 || GET_MODE_CLASS (mode
) == MODE_INT
)
3743 && op0
== CONST0_RTX (mode
)
3744 && ! side_effects_p (op1
))
3747 #if 0 /* Turned off till an expert says this is a safe thing to do. */
3748 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
3749 /* Change division by a constant into multiplication. */
3750 else if (GET_CODE (op1
) == CONST_DOUBLE
3751 && GET_MODE_CLASS (GET_MODE (op1
)) == MODE_FLOAT
3752 && op1
!= CONST0_RTX (mode
))
3755 REAL_VALUE_FROM_CONST_DOUBLE (d
, op1
);
3756 if (REAL_VALUES_EQUAL (d
, dconst0
))
3758 #if defined (REAL_ARITHMETIC)
3759 REAL_ARITHMETIC (d
, RDIV_EXPR
, dconst1
, d
);
3760 return gen_rtx (MULT
, mode
, op0
,
3761 CONST_DOUBLE_FROM_REAL_VALUE (d
, mode
));
3763 return gen_rtx (MULT
, mode
, op0
,
3764 CONST_DOUBLE_FROM_REAL_VALUE (1./d
, mode
));
3772 /* Handle modulus by power of two (mod with 1 handled below). */
3773 if (GET_CODE (op1
) == CONST_INT
3774 && exact_log2 (INTVAL (op1
)) > 0)
3775 return gen_rtx (AND
, mode
, op0
, GEN_INT (INTVAL (op1
) - 1));
3777 /* ... fall through ... */
3780 if ((op0
== const0_rtx
|| op1
== const1_rtx
)
3781 && ! side_effects_p (op0
) && ! side_effects_p (op1
))
3787 /* Rotating ~0 always results in ~0. */
3788 if (GET_CODE (op0
) == CONST_INT
&& width
<= HOST_BITS_PER_WIDE_INT
3789 && INTVAL (op0
) == GET_MODE_MASK (mode
)
3790 && ! side_effects_p (op1
))
3793 /* ... fall through ... */
3799 if (op1
== const0_rtx
)
3801 if (op0
== const0_rtx
&& ! side_effects_p (op1
))
3806 if (width
<= HOST_BITS_PER_WIDE_INT
&& GET_CODE (op1
) == CONST_INT
3807 && INTVAL (op1
) == (HOST_WIDE_INT
) 1 << (width
-1)
3808 && ! side_effects_p (op0
))
3810 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3815 if (width
<= HOST_BITS_PER_WIDE_INT
&& GET_CODE (op1
) == CONST_INT
3816 && INTVAL (op1
) == GET_MODE_MASK (mode
) >> 1
3817 && ! side_effects_p (op0
))
3819 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3824 if (op1
== const0_rtx
&& ! side_effects_p (op0
))
3826 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3831 if (op1
== constm1_rtx
&& ! side_effects_p (op0
))
3833 else if (rtx_equal_p (op0
, op1
) && ! side_effects_p (op0
))
3844 /* Get the integer argument values in two forms:
3845 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
3847 arg0
= INTVAL (op0
);
3848 arg1
= INTVAL (op1
);
3850 if (width
< HOST_BITS_PER_WIDE_INT
)
3852 arg0
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
3853 arg1
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
3856 if (arg0s
& ((HOST_WIDE_INT
) 1 << (width
- 1)))
3857 arg0s
|= ((HOST_WIDE_INT
) (-1) << width
);
3860 if (arg1s
& ((HOST_WIDE_INT
) 1 << (width
- 1)))
3861 arg1s
|= ((HOST_WIDE_INT
) (-1) << width
);
3869 /* Compute the value of the arithmetic. */
3874 val
= arg0s
+ arg1s
;
3878 val
= arg0s
- arg1s
;
3882 val
= arg0s
* arg1s
;
3888 val
= arg0s
/ arg1s
;
3894 val
= arg0s
% arg1s
;
3900 val
= (unsigned HOST_WIDE_INT
) arg0
/ arg1
;
3906 val
= (unsigned HOST_WIDE_INT
) arg0
% arg1
;
3922 /* If shift count is undefined, don't fold it; let the machine do
3923 what it wants. But truncate it if the machine will do that. */
3927 #ifdef SHIFT_COUNT_TRUNCATED
3928 arg1
&= (BITS_PER_WORD
- 1);
3934 val
= ((unsigned HOST_WIDE_INT
) arg0
) >> arg1
;
3942 #ifdef SHIFT_COUNT_TRUNCATED
3943 arg1
&= (BITS_PER_WORD
- 1);
3949 val
= ((unsigned HOST_WIDE_INT
) arg0
) << arg1
;
3956 #ifdef SHIFT_COUNT_TRUNCATED
3957 arg1
&= (BITS_PER_WORD
- 1);
3963 val
= arg0s
>> arg1
;
3971 val
= ((((unsigned HOST_WIDE_INT
) arg0
) << (width
- arg1
))
3972 | (((unsigned HOST_WIDE_INT
) arg0
) >> arg1
));
3980 val
= ((((unsigned HOST_WIDE_INT
) arg0
) << arg1
)
3981 | (((unsigned HOST_WIDE_INT
) arg0
) >> (width
- arg1
)));
3985 /* Do nothing here. */
3989 val
= arg0s
<= arg1s
? arg0s
: arg1s
;
3993 val
= ((unsigned HOST_WIDE_INT
) arg0
3994 <= (unsigned HOST_WIDE_INT
) arg1
? arg0
: arg1
);
3998 val
= arg0s
> arg1s
? arg0s
: arg1s
;
4002 val
= ((unsigned HOST_WIDE_INT
) arg0
4003 > (unsigned HOST_WIDE_INT
) arg1
? arg0
: arg1
);
4010 /* Clear the bits that don't belong in our mode, unless they and our sign
4011 bit are all one. So we get either a reasonable negative value or a
4012 reasonable unsigned value for this mode. */
4013 if (width
< HOST_BITS_PER_WIDE_INT
4014 && ((val
& ((HOST_WIDE_INT
) (-1) << (width
- 1)))
4015 != ((HOST_WIDE_INT
) (-1) << (width
- 1))))
4016 val
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
4018 return GEN_INT (val
);
4021 /* Like simplify_binary_operation except used for relational operators.
4022 MODE is the mode of the operands, not that of the result. */
4025 simplify_relational_operation (code
, mode
, op0
, op1
)
4027 enum machine_mode mode
;
4030 register HOST_WIDE_INT arg0
, arg1
, arg0s
, arg1s
;
4032 int width
= GET_MODE_BITSIZE (mode
);
4034 /* If op0 is a compare, extract the comparison arguments from it. */
4035 if (GET_CODE (op0
) == COMPARE
&& op1
== const0_rtx
)
4036 op1
= XEXP (op0
, 1), op0
= XEXP (op0
, 0);
4038 if (GET_CODE (op0
) != CONST_INT
|| GET_CODE (op1
) != CONST_INT
4039 || width
> HOST_BITS_PER_WIDE_INT
|| width
== 0)
4041 /* Even if we can't compute a constant result,
4042 there are some cases worth simplifying. */
4044 /* For non-IEEE floating-point, if the two operands are equal, we know
4046 if (rtx_equal_p (op0
, op1
)
4047 && (TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
4048 || GET_MODE_CLASS (GET_MODE (op0
)) != MODE_FLOAT
))
4049 return (code
== EQ
|| code
== GE
|| code
== LE
|| code
== LEU
4050 || code
== GEU
) ? const_true_rtx
: const0_rtx
;
4051 else if (GET_CODE (op0
) == CONST_DOUBLE
4052 && GET_CODE (op1
) == CONST_DOUBLE
4053 && GET_MODE_CLASS (GET_MODE (op0
)) == MODE_FLOAT
)
4055 REAL_VALUE_TYPE d0
, d1
;
4057 int op0lt
, op1lt
, equal
;
4059 if (setjmp (handler
))
4062 set_float_handler (handler
);
4063 REAL_VALUE_FROM_CONST_DOUBLE (d0
, op0
);
4064 REAL_VALUE_FROM_CONST_DOUBLE (d1
, op1
);
4065 equal
= REAL_VALUES_EQUAL (d0
, d1
);
4066 op0lt
= REAL_VALUES_LESS (d0
, d1
);
4067 op1lt
= REAL_VALUES_LESS (d1
, d0
);
4068 set_float_handler (NULL_PTR
);
4073 return equal
? const_true_rtx
: const0_rtx
;
4075 return !equal
? const_true_rtx
: const0_rtx
;
4077 return equal
|| op0lt
? const_true_rtx
: const0_rtx
;
4079 return op0lt
? const_true_rtx
: const0_rtx
;
4081 return equal
|| op1lt
? const_true_rtx
: const0_rtx
;
4083 return op1lt
? const_true_rtx
: const0_rtx
;
4092 /* We can't make this assumption due to #pragma weak */
4093 if (CONSTANT_P (op0
) && op1
== const0_rtx
)
4096 if (NONZERO_BASE_PLUS_P (op0
) && op1
== const0_rtx
4097 /* On some machines, the ap reg can be 0 sometimes. */
4098 && op0
!= arg_pointer_rtx
)
4105 /* We can't make this assumption due to #pragma weak */
4106 if (CONSTANT_P (op0
) && op1
== const0_rtx
)
4107 return const_true_rtx
;
4109 if (NONZERO_BASE_PLUS_P (op0
) && op1
== const0_rtx
4110 /* On some machines, the ap reg can be 0 sometimes. */
4111 && op0
!= arg_pointer_rtx
)
4112 return const_true_rtx
;
4116 /* Unsigned values are never negative, but we must be sure we are
4117 actually comparing a value, not a CC operand. */
4118 if (op1
== const0_rtx
4119 && GET_MODE_CLASS (mode
) == MODE_INT
)
4120 return const_true_rtx
;
4124 if (op1
== const0_rtx
4125 && GET_MODE_CLASS (mode
) == MODE_INT
)
4130 /* Unsigned values are never greater than the largest
4132 if (GET_CODE (op1
) == CONST_INT
4133 && INTVAL (op1
) == GET_MODE_MASK (mode
)
4134 && GET_MODE_CLASS (mode
) == MODE_INT
)
4135 return const_true_rtx
;
4139 if (GET_CODE (op1
) == CONST_INT
4140 && INTVAL (op1
) == GET_MODE_MASK (mode
)
4141 && GET_MODE_CLASS (mode
) == MODE_INT
)
4149 /* Get the integer argument values in two forms:
4150 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
4152 arg0
= INTVAL (op0
);
4153 arg1
= INTVAL (op1
);
4155 if (width
< HOST_BITS_PER_WIDE_INT
)
4157 arg0
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
4158 arg1
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
4161 if (arg0s
& ((HOST_WIDE_INT
) 1 << (width
- 1)))
4162 arg0s
|= ((HOST_WIDE_INT
) (-1) << width
);
4165 if (arg1s
& ((HOST_WIDE_INT
) 1 << (width
- 1)))
4166 arg1s
|= ((HOST_WIDE_INT
) (-1) << width
);
4174 /* Compute the value of the arithmetic. */
4179 val
= arg0
!= arg1
? STORE_FLAG_VALUE
: 0;
4183 val
= arg0
== arg1
? STORE_FLAG_VALUE
: 0;
4187 val
= arg0s
<= arg1s
? STORE_FLAG_VALUE
: 0;
4191 val
= arg0s
< arg1s
? STORE_FLAG_VALUE
: 0;
4195 val
= arg0s
>= arg1s
? STORE_FLAG_VALUE
: 0;
4199 val
= arg0s
> arg1s
? STORE_FLAG_VALUE
: 0;
4203 val
= (((unsigned HOST_WIDE_INT
) arg0
)
4204 <= ((unsigned HOST_WIDE_INT
) arg1
) ? STORE_FLAG_VALUE
: 0);
4208 val
= (((unsigned HOST_WIDE_INT
) arg0
)
4209 < ((unsigned HOST_WIDE_INT
) arg1
) ? STORE_FLAG_VALUE
: 0);
4213 val
= (((unsigned HOST_WIDE_INT
) arg0
)
4214 >= ((unsigned HOST_WIDE_INT
) arg1
) ? STORE_FLAG_VALUE
: 0);
4218 val
= (((unsigned HOST_WIDE_INT
) arg0
)
4219 > ((unsigned HOST_WIDE_INT
) arg1
) ? STORE_FLAG_VALUE
: 0);
4226 /* Clear the bits that don't belong in our mode, unless they and our sign
4227 bit are all one. So we get either a reasonable negative value or a
4228 reasonable unsigned value for this mode. */
4229 if (width
< HOST_BITS_PER_WIDE_INT
4230 && ((val
& ((HOST_WIDE_INT
) (-1) << (width
- 1)))
4231 != ((HOST_WIDE_INT
) (-1) << (width
- 1))))
4232 val
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
4234 return GEN_INT (val
);
4237 /* Simplify CODE, an operation with result mode MODE and three operands,
4238 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
4239 a constant. Return 0 if no simplifications is possible. */
4242 simplify_ternary_operation (code
, mode
, op0_mode
, op0
, op1
, op2
)
4244 enum machine_mode mode
, op0_mode
;
4247 int width
= GET_MODE_BITSIZE (mode
);
4249 /* VOIDmode means "infinite" precision. */
4251 width
= HOST_BITS_PER_WIDE_INT
;
4257 if (GET_CODE (op0
) == CONST_INT
4258 && GET_CODE (op1
) == CONST_INT
4259 && GET_CODE (op2
) == CONST_INT
4260 && INTVAL (op1
) + INTVAL (op2
) <= GET_MODE_BITSIZE (op0_mode
)
4261 && width
<= HOST_BITS_PER_WIDE_INT
)
4263 /* Extracting a bit-field from a constant */
4264 HOST_WIDE_INT val
= INTVAL (op0
);
4267 val
>>= (GET_MODE_BITSIZE (op0_mode
) - INTVAL (op2
) - INTVAL (op1
));
4269 val
>>= INTVAL (op2
);
4271 if (HOST_BITS_PER_WIDE_INT
!= INTVAL (op1
))
4273 /* First zero-extend. */
4274 val
&= ((HOST_WIDE_INT
) 1 << INTVAL (op1
)) - 1;
4275 /* If desired, propagate sign bit. */
4276 if (code
== SIGN_EXTRACT
4277 && (val
& ((HOST_WIDE_INT
) 1 << (INTVAL (op1
) - 1))))
4278 val
|= ~ (((HOST_WIDE_INT
) 1 << INTVAL (op1
)) - 1);
4281 /* Clear the bits that don't belong in our mode,
4282 unless they and our sign bit are all one.
4283 So we get either a reasonable negative value or a reasonable
4284 unsigned value for this mode. */
4285 if (width
< HOST_BITS_PER_WIDE_INT
4286 && ((val
& ((HOST_WIDE_INT
) (-1) << (width
- 1)))
4287 != ((HOST_WIDE_INT
) (-1) << (width
- 1))))
4288 val
&= ((HOST_WIDE_INT
) 1 << width
) - 1;
4290 return GEN_INT (val
);
4295 if (GET_CODE (op0
) == CONST_INT
)
4296 return op0
!= const0_rtx
? op1
: op2
;
4306 /* If X is a nontrivial arithmetic operation on an argument
4307 for which a constant value can be determined, return
4308 the result of operating on that value, as a constant.
4309 Otherwise, return X, possibly with one or more operands
4310 modified by recursive calls to this function.
4312 If X is a register whose contents are known, we do NOT
4313 return those contents. This is because an instruction that
4314 uses a register is usually faster than one that uses a constant.
4316 INSN is the insn that we may be modifying. If it is 0, make a copy
4317 of X before modifying it. */
4324 register enum rtx_code code
;
4325 register enum machine_mode mode
;
4332 /* Folded equivalents of first two operands of X. */
4336 /* Constant equivalents of first three operands of X;
4337 0 when no such equivalent is known. */
4342 /* The mode of the first operand of X. We need this for sign and zero
4344 enum machine_mode mode_arg0
;
4349 mode
= GET_MODE (x
);
4350 code
= GET_CODE (x
);
4359 /* No use simplifying an EXPR_LIST
4360 since they are used only for lists of args
4361 in a function call's REG_EQUAL note. */
4367 return prev_insn_cc0
;
4371 /* If the next insn is a CODE_LABEL followed by a jump table,
4372 PC's value is a LABEL_REF pointing to that label. That
4373 lets us fold switch statements on the Vax. */
4374 if (insn
&& GET_CODE (insn
) == JUMP_INSN
)
4376 rtx next
= next_nonnote_insn (insn
);
4378 if (next
&& GET_CODE (next
) == CODE_LABEL
4379 && NEXT_INSN (next
) != 0
4380 && GET_CODE (NEXT_INSN (next
)) == JUMP_INSN
4381 && (GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_VEC
4382 || GET_CODE (PATTERN (NEXT_INSN (next
))) == ADDR_DIFF_VEC
))
4383 return gen_rtx (LABEL_REF
, Pmode
, next
);
4388 /* See if we previously assigned a constant value to this SUBREG. */
4389 if ((new = lookup_as_function (x
, CONST_INT
)) != 0
4390 || (new = lookup_as_function (x
, CONST_DOUBLE
)) != 0)
4393 /* If this is a paradoxical SUBREG, we have no idea what value the
4394 extra bits would have. However, if the operand is equivalent
4395 to a SUBREG whose operand is the same as our mode, and all the
4396 modes are within a word, we can just use the inner operand
4397 because these SUBREGs just say how to treat the register. */
4399 if (GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))))
4401 enum machine_mode imode
= GET_MODE (SUBREG_REG (x
));
4402 struct table_elt
*elt
;
4404 if (GET_MODE_SIZE (mode
) <= UNITS_PER_WORD
4405 && GET_MODE_SIZE (imode
) <= UNITS_PER_WORD
4406 && (elt
= lookup (SUBREG_REG (x
), HASH (SUBREG_REG (x
), imode
),
4409 for (elt
= elt
->first_same_value
;
4410 elt
; elt
= elt
->next_same_value
)
4411 if (GET_CODE (elt
->exp
) == SUBREG
4412 && GET_MODE (SUBREG_REG (elt
->exp
)) == mode
4413 && exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
4414 return copy_rtx (SUBREG_REG (elt
->exp
));
4420 /* Fold SUBREG_REG. If it changed, see if we can simplify the SUBREG.
4421 We might be able to if the SUBREG is extracting a single word in an
4422 integral mode or extracting the low part. */
4424 folded_arg0
= fold_rtx (SUBREG_REG (x
), insn
);
4425 const_arg0
= equiv_constant (folded_arg0
);
4427 folded_arg0
= const_arg0
;
4429 if (folded_arg0
!= SUBREG_REG (x
))
4433 if (GET_MODE_CLASS (mode
) == MODE_INT
4434 && GET_MODE_SIZE (mode
) == UNITS_PER_WORD
4435 && GET_MODE (SUBREG_REG (x
)) != VOIDmode
)
4436 new = operand_subword (folded_arg0
, SUBREG_WORD (x
), 0,
4437 GET_MODE (SUBREG_REG (x
)));
4438 if (new == 0 && subreg_lowpart_p (x
))
4439 new = gen_lowpart_if_possible (mode
, folded_arg0
);
4444 /* If this is a narrowing SUBREG and our operand is a REG, see if
4445 we can find an equivalence for REG that is an arithmetic operation
4446 in a wider mode where both operands are paradoxical SUBREGs
4447 from objects of our result mode. In that case, we couldn't report
4448 an equivalent value for that operation, since we don't know what the
4449 extra bits will be. But we can find an equivalence for this SUBREG
4450 by folding that operation is the narrow mode. This allows us to
4451 fold arithmetic in narrow modes when the machine only supports
4452 word-sized arithmetic.
4454 Also look for a case where we have a SUBREG whose operand is the
4455 same as our result. If both modes are smaller than a word, we
4456 are simply interpreting a register in different modes and we
4457 can use the inner value. */
4459 if (GET_CODE (folded_arg0
) == REG
4460 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (folded_arg0
)))
4462 struct table_elt
*elt
;
4464 /* We can use HASH here since we know that canon_hash won't be
4466 elt
= lookup (folded_arg0
,
4467 HASH (folded_arg0
, GET_MODE (folded_arg0
)),
4468 GET_MODE (folded_arg0
));
4471 elt
= elt
->first_same_value
;
4473 for (; elt
; elt
= elt
->next_same_value
)
4475 /* Just check for unary and binary operations. */
4476 if (GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '1'
4477 && GET_CODE (elt
->exp
) != SIGN_EXTEND
4478 && GET_CODE (elt
->exp
) != ZERO_EXTEND
4479 && GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
4480 && GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0))) == mode
)
4482 rtx op0
= SUBREG_REG (XEXP (elt
->exp
, 0));
4484 if (GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
4485 op0
= fold_rtx (op0
, NULL_RTX
);
4487 op0
= equiv_constant (op0
);
4489 new = simplify_unary_operation (GET_CODE (elt
->exp
), mode
,
4492 else if ((GET_RTX_CLASS (GET_CODE (elt
->exp
)) == '2'
4493 || GET_RTX_CLASS (GET_CODE (elt
->exp
)) == 'c')
4494 && ((GET_CODE (XEXP (elt
->exp
, 0)) == SUBREG
4495 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 0)))
4497 || CONSTANT_P (XEXP (elt
->exp
, 0)))
4498 && ((GET_CODE (XEXP (elt
->exp
, 1)) == SUBREG
4499 && (GET_MODE (SUBREG_REG (XEXP (elt
->exp
, 1)))
4501 || CONSTANT_P (XEXP (elt
->exp
, 1))))
4503 rtx op0
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 0));
4504 rtx op1
= gen_lowpart_common (mode
, XEXP (elt
->exp
, 1));
4506 if (op0
&& GET_CODE (op0
) != REG
&& ! CONSTANT_P (op0
))
4507 op0
= fold_rtx (op0
, NULL_RTX
);
4510 op0
= equiv_constant (op0
);
4512 if (op1
&& GET_CODE (op1
) != REG
&& ! CONSTANT_P (op1
))
4513 op1
= fold_rtx (op1
, NULL_RTX
);
4516 op1
= equiv_constant (op1
);
4519 new = simplify_binary_operation (GET_CODE (elt
->exp
), mode
,
4523 else if (GET_CODE (elt
->exp
) == SUBREG
4524 && GET_MODE (SUBREG_REG (elt
->exp
)) == mode
4525 && (GET_MODE_SIZE (GET_MODE (folded_arg0
))
4527 && exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
4528 new = copy_rtx (SUBREG_REG (elt
->exp
));
4539 /* If we have (NOT Y), see if Y is known to be (NOT Z).
4540 If so, (NOT Y) simplifies to Z. Similarly for NEG. */
4541 new = lookup_as_function (XEXP (x
, 0), code
);
4543 return fold_rtx (copy_rtx (XEXP (new, 0)), insn
);
4547 /* If we are not actually processing an insn, don't try to find the
4548 best address. Not only don't we care, but we could modify the
4549 MEM in an invalid way since we have no insn to validate against. */
4551 find_best_addr (insn
, &XEXP (x
, 0));
4554 /* Even if we don't fold in the insn itself,
4555 we can safely do so here, in hopes of getting a constant. */
4556 rtx addr
= fold_rtx (XEXP (x
, 0), NULL_RTX
);
4558 HOST_WIDE_INT offset
= 0;
4560 if (GET_CODE (addr
) == REG
4561 && REGNO_QTY_VALID_P (REGNO (addr
))
4562 && GET_MODE (addr
) == qty_mode
[reg_qty
[REGNO (addr
)]]
4563 && qty_const
[reg_qty
[REGNO (addr
)]] != 0)
4564 addr
= qty_const
[reg_qty
[REGNO (addr
)]];
4566 /* If address is constant, split it into a base and integer offset. */
4567 if (GET_CODE (addr
) == SYMBOL_REF
|| GET_CODE (addr
) == LABEL_REF
)
4569 else if (GET_CODE (addr
) == CONST
&& GET_CODE (XEXP (addr
, 0)) == PLUS
4570 && GET_CODE (XEXP (XEXP (addr
, 0), 1)) == CONST_INT
)
4572 base
= XEXP (XEXP (addr
, 0), 0);
4573 offset
= INTVAL (XEXP (XEXP (addr
, 0), 1));
4575 else if (GET_CODE (addr
) == LO_SUM
4576 && GET_CODE (XEXP (addr
, 1)) == SYMBOL_REF
)
4577 base
= XEXP (addr
, 1);
4579 /* If this is a constant pool reference, we can fold it into its
4580 constant to allow better value tracking. */
4581 if (base
&& GET_CODE (base
) == SYMBOL_REF
4582 && CONSTANT_POOL_ADDRESS_P (base
))
4584 rtx constant
= get_pool_constant (base
);
4585 enum machine_mode const_mode
= get_pool_mode (base
);
4588 if (CONSTANT_P (constant
) && GET_CODE (constant
) != CONST_INT
)
4589 constant_pool_entries_cost
= COST (constant
);
4591 /* If we are loading the full constant, we have an equivalence. */
4592 if (offset
== 0 && mode
== const_mode
)
4595 /* If this actually isn't a constant (wierd!), we can't do
4596 anything. Otherwise, handle the two most common cases:
4597 extracting a word from a multi-word constant, and extracting
4598 the low-order bits. Other cases don't seem common enough to
4600 if (! CONSTANT_P (constant
))
4603 if (GET_MODE_CLASS (mode
) == MODE_INT
4604 && GET_MODE_SIZE (mode
) == UNITS_PER_WORD
4605 && offset
% UNITS_PER_WORD
== 0
4606 && (new = operand_subword (constant
,
4607 offset
/ UNITS_PER_WORD
,
4608 0, const_mode
)) != 0)
4611 if (((BYTES_BIG_ENDIAN
4612 && offset
== GET_MODE_SIZE (GET_MODE (constant
)) - 1)
4613 || (! BYTES_BIG_ENDIAN
&& offset
== 0))
4614 && (new = gen_lowpart_if_possible (mode
, constant
)) != 0)
4618 /* If this is a reference to a label at a known position in a jump
4619 table, we also know its value. */
4620 if (base
&& GET_CODE (base
) == LABEL_REF
)
4622 rtx label
= XEXP (base
, 0);
4623 rtx table_insn
= NEXT_INSN (label
);
4625 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
4626 && GET_CODE (PATTERN (table_insn
)) == ADDR_VEC
)
4628 rtx table
= PATTERN (table_insn
);
4631 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
4632 < XVECLEN (table
, 0)))
4633 return XVECEXP (table
, 0,
4634 offset
/ GET_MODE_SIZE (GET_MODE (table
)));
4636 if (table_insn
&& GET_CODE (table_insn
) == JUMP_INSN
4637 && GET_CODE (PATTERN (table_insn
)) == ADDR_DIFF_VEC
)
4639 rtx table
= PATTERN (table_insn
);
4642 && (offset
/ GET_MODE_SIZE (GET_MODE (table
))
4643 < XVECLEN (table
, 1)))
4645 offset
/= GET_MODE_SIZE (GET_MODE (table
));
4646 new = gen_rtx (MINUS
, Pmode
, XVECEXP (table
, 1, offset
),
4649 if (GET_MODE (table
) != Pmode
)
4650 new = gen_rtx (TRUNCATE
, GET_MODE (table
), new);
4664 mode_arg0
= VOIDmode
;
4666 /* Try folding our operands.
4667 Then see which ones have constant values known. */
4669 fmt
= GET_RTX_FORMAT (code
);
4670 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4673 rtx arg
= XEXP (x
, i
);
4674 rtx folded_arg
= arg
, const_arg
= 0;
4675 enum machine_mode mode_arg
= GET_MODE (arg
);
4676 rtx cheap_arg
, expensive_arg
;
4677 rtx replacements
[2];
4680 /* Most arguments are cheap, so handle them specially. */
4681 switch (GET_CODE (arg
))
4684 /* This is the same as calling equiv_constant; it is duplicated
4686 if (REGNO_QTY_VALID_P (REGNO (arg
))
4687 && qty_const
[reg_qty
[REGNO (arg
)]] != 0
4688 && GET_CODE (qty_const
[reg_qty
[REGNO (arg
)]]) != REG
4689 && GET_CODE (qty_const
[reg_qty
[REGNO (arg
)]]) != PLUS
)
4691 = gen_lowpart_if_possible (GET_MODE (arg
),
4692 qty_const
[reg_qty
[REGNO (arg
)]]);
4705 folded_arg
= prev_insn_cc0
;
4706 mode_arg
= prev_insn_cc0_mode
;
4707 const_arg
= equiv_constant (folded_arg
);
4712 folded_arg
= fold_rtx (arg
, insn
);
4713 const_arg
= equiv_constant (folded_arg
);
4716 /* For the first three operands, see if the operand
4717 is constant or equivalent to a constant. */
4721 folded_arg0
= folded_arg
;
4722 const_arg0
= const_arg
;
4723 mode_arg0
= mode_arg
;
4726 folded_arg1
= folded_arg
;
4727 const_arg1
= const_arg
;
4730 const_arg2
= const_arg
;
4734 /* Pick the least expensive of the folded argument and an
4735 equivalent constant argument. */
4736 if (const_arg
== 0 || const_arg
== folded_arg
4737 || COST (const_arg
) > COST (folded_arg
))
4738 cheap_arg
= folded_arg
, expensive_arg
= const_arg
;
4740 cheap_arg
= const_arg
, expensive_arg
= folded_arg
;
4742 /* Try to replace the operand with the cheapest of the two
4743 possibilities. If it doesn't work and this is either of the first
4744 two operands of a commutative operation, try swapping them.
4745 If THAT fails, try the more expensive, provided it is cheaper
4746 than what is already there. */
4748 if (cheap_arg
== XEXP (x
, i
))
4751 if (insn
== 0 && ! copied
)
4757 replacements
[0] = cheap_arg
, replacements
[1] = expensive_arg
;
4759 j
< 2 && replacements
[j
]
4760 && COST (replacements
[j
]) < COST (XEXP (x
, i
));
4763 if (validate_change (insn
, &XEXP (x
, i
), replacements
[j
], 0))
4766 if (code
== NE
|| code
== EQ
|| GET_RTX_CLASS (code
) == 'c')
4768 validate_change (insn
, &XEXP (x
, i
), XEXP (x
, 1 - i
), 1);
4769 validate_change (insn
, &XEXP (x
, 1 - i
), replacements
[j
], 1);
4771 if (apply_change_group ())
4773 /* Swap them back to be invalid so that this loop can
4774 continue and flag them to be swapped back later. */
4777 tem
= XEXP (x
, 0); XEXP (x
, 0) = XEXP (x
, 1);
4786 else if (fmt
[i
] == 'E')
4787 /* Don't try to fold inside of a vector of expressions.
4788 Doing nothing is harmless. */
4791 /* If a commutative operation, place a constant integer as the second
4792 operand unless the first operand is also a constant integer. Otherwise,
4793 place any constant second unless the first operand is also a constant. */
4795 if (code
== EQ
|| code
== NE
|| GET_RTX_CLASS (code
) == 'c')
4797 if (must_swap
|| (const_arg0
4799 || (GET_CODE (const_arg0
) == CONST_INT
4800 && GET_CODE (const_arg1
) != CONST_INT
))))
4802 register rtx tem
= XEXP (x
, 0);
4804 if (insn
== 0 && ! copied
)
4810 validate_change (insn
, &XEXP (x
, 0), XEXP (x
, 1), 1);
4811 validate_change (insn
, &XEXP (x
, 1), tem
, 1);
4812 if (apply_change_group ())
4814 tem
= const_arg0
, const_arg0
= const_arg1
, const_arg1
= tem
;
4815 tem
= folded_arg0
, folded_arg0
= folded_arg1
, folded_arg1
= tem
;
4820 /* If X is an arithmetic operation, see if we can simplify it. */
4822 switch (GET_RTX_CLASS (code
))
4825 /* We can't simplify extension ops unless we know the original mode. */
4826 if ((code
== ZERO_EXTEND
|| code
== SIGN_EXTEND
)
4827 && mode_arg0
== VOIDmode
)
4829 new = simplify_unary_operation (code
, mode
,
4830 const_arg0
? const_arg0
: folded_arg0
,
4835 /* See what items are actually being compared and set FOLDED_ARG[01]
4836 to those values and CODE to the actual comparison code. If any are
4837 constant, set CONST_ARG0 and CONST_ARG1 appropriately. We needn't
4838 do anything if both operands are already known to be constant. */
4840 if (const_arg0
== 0 || const_arg1
== 0)
4842 struct table_elt
*p0
, *p1
;
4843 rtx
true = const_true_rtx
, false = const0_rtx
;
4845 #ifdef FLOAT_STORE_FLAG_VALUE
4846 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
4848 true = immed_real_const_1 (FLOAT_STORE_FLAG_VALUE
, mode
);
4849 false = CONST0_RTX (mode
);
4853 code
= find_comparison_args (code
, &folded_arg0
, &folded_arg1
);
4854 const_arg0
= equiv_constant (folded_arg0
);
4855 const_arg1
= equiv_constant (folded_arg1
);
4857 /* Get a mode from the values actually being compared, or from the
4858 old value of MODE_ARG0 if both are constants. If the resulting
4859 mode is VOIDmode or a MODE_CC mode, we don't know what kinds
4860 of things are being compared, so we can't do anything with this
4863 if (GET_MODE (folded_arg0
) != VOIDmode
4864 && GET_MODE_CLASS (GET_MODE (folded_arg0
)) != MODE_CC
)
4865 mode_arg0
= GET_MODE (folded_arg0
);
4867 else if (GET_MODE (folded_arg1
) != VOIDmode
4868 && GET_MODE_CLASS (GET_MODE (folded_arg1
)) != MODE_CC
)
4869 mode_arg0
= GET_MODE (folded_arg1
);
4871 if (mode_arg0
== VOIDmode
|| GET_MODE_CLASS (mode_arg0
) == MODE_CC
)
4874 /* If we do not now have two constants being compared, see if we
4875 can nevertheless deduce some things about the comparison. */
4876 if (const_arg0
== 0 || const_arg1
== 0)
4878 /* Is FOLDED_ARG0 frame-pointer plus a constant? Or non-explicit
4879 constant? These aren't zero, but we don't know their sign. */
4880 if (const_arg1
== const0_rtx
4881 && (NONZERO_BASE_PLUS_P (folded_arg0
)
4882 #if 0 /* Sad to say, on sysvr4, #pragma weak can make a symbol address
4884 || GET_CODE (folded_arg0
) == SYMBOL_REF
4886 || GET_CODE (folded_arg0
) == LABEL_REF
4887 || GET_CODE (folded_arg0
) == CONST
))
4891 else if (code
== NE
)
4895 /* See if the two operands are the same. We don't do this
4896 for IEEE floating-point since we can't assume x == x
4897 since x might be a NaN. */
4899 if ((TARGET_FLOAT_FORMAT
!= IEEE_FLOAT_FORMAT
4900 || GET_MODE_CLASS (mode_arg0
) != MODE_FLOAT
)
4901 && (folded_arg0
== folded_arg1
4902 || (GET_CODE (folded_arg0
) == REG
4903 && GET_CODE (folded_arg1
) == REG
4904 && (reg_qty
[REGNO (folded_arg0
)]
4905 == reg_qty
[REGNO (folded_arg1
)]))
4906 || ((p0
= lookup (folded_arg0
,
4907 (safe_hash (folded_arg0
, mode_arg0
)
4908 % NBUCKETS
), mode_arg0
))
4909 && (p1
= lookup (folded_arg1
,
4910 (safe_hash (folded_arg1
, mode_arg0
)
4911 % NBUCKETS
), mode_arg0
))
4912 && p0
->first_same_value
== p1
->first_same_value
)))
4913 return ((code
== EQ
|| code
== LE
|| code
== GE
4914 || code
== LEU
|| code
== GEU
)
4917 /* If FOLDED_ARG0 is a register, see if the comparison we are
4918 doing now is either the same as we did before or the reverse
4919 (we only check the reverse if not floating-point). */
4920 else if (GET_CODE (folded_arg0
) == REG
)
4922 int qty
= reg_qty
[REGNO (folded_arg0
)];
4924 if (REGNO_QTY_VALID_P (REGNO (folded_arg0
))
4925 && (comparison_dominates_p (qty_comparison_code
[qty
], code
)
4926 || (comparison_dominates_p (qty_comparison_code
[qty
],
4927 reverse_condition (code
))
4928 && GET_MODE_CLASS (mode_arg0
) == MODE_INT
))
4929 && (rtx_equal_p (qty_comparison_const
[qty
], folded_arg1
)
4931 && rtx_equal_p (qty_comparison_const
[qty
],
4933 || (GET_CODE (folded_arg1
) == REG
4934 && (reg_qty
[REGNO (folded_arg1
)]
4935 == qty_comparison_qty
[qty
]))))
4936 return (comparison_dominates_p (qty_comparison_code
[qty
],
4943 /* If we are comparing against zero, see if the first operand is
4944 equivalent to an IOR with a constant. If so, we may be able to
4945 determine the result of this comparison. */
4947 if (const_arg1
== const0_rtx
)
4949 rtx y
= lookup_as_function (folded_arg0
, IOR
);
4953 && (inner_const
= equiv_constant (XEXP (y
, 1))) != 0
4954 && GET_CODE (inner_const
) == CONST_INT
4955 && INTVAL (inner_const
) != 0)
4957 int sign_bitnum
= GET_MODE_BITSIZE (mode_arg0
) - 1;
4958 int has_sign
= (HOST_BITS_PER_WIDE_INT
>= sign_bitnum
4959 && (INTVAL (inner_const
)
4960 & ((HOST_WIDE_INT
) 1 << sign_bitnum
)));
4961 rtx
true = const_true_rtx
, false = const0_rtx
;
4963 #ifdef FLOAT_STORE_FLAG_VALUE
4964 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
4966 true = immed_real_const_1 (FLOAT_STORE_FLAG_VALUE
, mode
);
4967 false = CONST0_RTX (mode
);
4989 new = simplify_relational_operation (code
, mode_arg0
,
4990 const_arg0
? const_arg0
: folded_arg0
,
4991 const_arg1
? const_arg1
: folded_arg1
);
4992 #ifdef FLOAT_STORE_FLAG_VALUE
4993 if (new != 0 && GET_MODE_CLASS (mode
) == MODE_FLOAT
)
4994 new = ((new == const0_rtx
) ? CONST0_RTX (mode
)
4995 : immed_real_const_1 (FLOAT_STORE_FLAG_VALUE
, mode
));
5004 /* If the second operand is a LABEL_REF, see if the first is a MINUS
5005 with that LABEL_REF as its second operand. If so, the result is
5006 the first operand of that MINUS. This handles switches with an
5007 ADDR_DIFF_VEC table. */
5008 if (const_arg1
&& GET_CODE (const_arg1
) == LABEL_REF
)
5010 rtx y
= lookup_as_function (folded_arg0
, MINUS
);
5012 if (y
!= 0 && GET_CODE (XEXP (y
, 1)) == LABEL_REF
5013 && XEXP (XEXP (y
, 1), 0) == XEXP (const_arg1
, 0))
5017 /* ... fall through ... */
5020 case SMIN
: case SMAX
: case UMIN
: case UMAX
:
5021 case IOR
: case AND
: case XOR
:
5022 case MULT
: case DIV
: case UDIV
:
5023 case ASHIFT
: case LSHIFTRT
: case ASHIFTRT
:
5024 /* If we have (<op> <reg> <const_int>) for an associative OP and REG
5025 is known to be of similar form, we may be able to replace the
5026 operation with a combined operation. This may eliminate the
5027 intermediate operation if every use is simplified in this way.
5028 Note that the similar optimization done by combine.c only works
5029 if the intermediate operation's result has only one reference. */
5031 if (GET_CODE (folded_arg0
) == REG
5032 && const_arg1
&& GET_CODE (const_arg1
) == CONST_INT
)
5035 = (code
== ASHIFT
|| code
== ASHIFTRT
|| code
== LSHIFTRT
);
5036 rtx y
= lookup_as_function (folded_arg0
, code
);
5038 enum rtx_code associate_code
;
5042 || 0 == (inner_const
5043 = equiv_constant (fold_rtx (XEXP (y
, 1), 0)))
5044 || GET_CODE (inner_const
) != CONST_INT
5045 /* If we have compiled a statement like
5046 "if (x == (x & mask1))", and now are looking at
5047 "x & mask2", we will have a case where the first operand
5048 of Y is the same as our first operand. Unless we detect
5049 this case, an infinite loop will result. */
5050 || XEXP (y
, 0) == folded_arg0
)
5053 /* Don't associate these operations if they are a PLUS with the
5054 same constant and it is a power of two. These might be doable
5055 with a pre- or post-increment. Similarly for two subtracts of
5056 identical powers of two with post decrement. */
5058 if (code
== PLUS
&& INTVAL (const_arg1
) == INTVAL (inner_const
)
5060 #if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT)
5061 || exact_log2 (INTVAL (const_arg1
)) >= 0
5063 #if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT)
5064 || exact_log2 (- INTVAL (const_arg1
)) >= 0
5069 /* Compute the code used to compose the constants. For example,
5070 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT. */
5073 = (code
== MULT
|| code
== DIV
|| code
== UDIV
? MULT
5074 : is_shift
|| code
== PLUS
|| code
== MINUS
? PLUS
: code
);
5076 new_const
= simplify_binary_operation (associate_code
, mode
,
5077 const_arg1
, inner_const
);
5082 /* If we are associating shift operations, don't let this
5083 produce a shift of larger than the object. This could
5084 occur when we following a sign-extend by a right shift on
5085 a machine that does a sign-extend as a pair of shifts. */
5087 if (is_shift
&& GET_CODE (new_const
) == CONST_INT
5088 && INTVAL (new_const
) > GET_MODE_BITSIZE (mode
))
5091 y
= copy_rtx (XEXP (y
, 0));
5093 /* If Y contains our first operand (the most common way this
5094 can happen is if Y is a MEM), we would do into an infinite
5095 loop if we tried to fold it. So don't in that case. */
5097 if (! reg_mentioned_p (folded_arg0
, y
))
5098 y
= fold_rtx (y
, insn
);
5100 new = simplify_binary_operation (code
, mode
, y
, new_const
);
5104 return gen_rtx (code
, mode
, y
, new_const
);
5108 new = simplify_binary_operation (code
, mode
,
5109 const_arg0
? const_arg0
: folded_arg0
,
5110 const_arg1
? const_arg1
: folded_arg1
);
5114 /* (lo_sum (high X) X) is simply X. */
5115 if (code
== LO_SUM
&& const_arg0
!= 0
5116 && GET_CODE (const_arg0
) == HIGH
5117 && rtx_equal_p (XEXP (const_arg0
, 0), const_arg1
))
5123 new = simplify_ternary_operation (code
, mode
, mode_arg0
,
5124 const_arg0
? const_arg0
: folded_arg0
,
5125 const_arg1
? const_arg1
: folded_arg1
,
5126 const_arg2
? const_arg2
: XEXP (x
, 2));
5130 return new ? new : x
;
5133 /* Return a constant value currently equivalent to X.
5134 Return 0 if we don't know one. */
5140 if (GET_CODE (x
) == REG
5141 && REGNO_QTY_VALID_P (REGNO (x
))
5142 && qty_const
[reg_qty
[REGNO (x
)]])
5143 x
= gen_lowpart_if_possible (GET_MODE (x
), qty_const
[reg_qty
[REGNO (x
)]]);
5145 if (x
!= 0 && CONSTANT_P (x
))
5148 /* If X is a MEM, try to fold it outside the context of any insn to see if
5149 it might be equivalent to a constant. That handles the case where it
5150 is a constant-pool reference. Then try to look it up in the hash table
5151 in case it is something whose value we have seen before. */
5153 if (GET_CODE (x
) == MEM
)
5155 struct table_elt
*elt
;
5157 x
= fold_rtx (x
, NULL_RTX
);
5161 elt
= lookup (x
, safe_hash (x
, GET_MODE (x
)) % NBUCKETS
, GET_MODE (x
));
5165 for (elt
= elt
->first_same_value
; elt
; elt
= elt
->next_same_value
)
5166 if (elt
->is_const
&& CONSTANT_P (elt
->exp
))
5173 /* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
5174 number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
5175 least-significant part of X.
5176 MODE specifies how big a part of X to return.
5178 If the requested operation cannot be done, 0 is returned.
5180 This is similar to gen_lowpart in emit-rtl.c. */
5183 gen_lowpart_if_possible (mode
, x
)
5184 enum machine_mode mode
;
5187 rtx result
= gen_lowpart_common (mode
, x
);
5191 else if (GET_CODE (x
) == MEM
)
5193 /* This is the only other case we handle. */
5194 register int offset
= 0;
5197 #if WORDS_BIG_ENDIAN
5198 offset
= (MAX (GET_MODE_SIZE (GET_MODE (x
)), UNITS_PER_WORD
)
5199 - MAX (GET_MODE_SIZE (mode
), UNITS_PER_WORD
));
5201 #if BYTES_BIG_ENDIAN
5202 /* Adjust the address so that the address-after-the-data
5204 offset
-= (MIN (UNITS_PER_WORD
, GET_MODE_SIZE (mode
))
5205 - MIN (UNITS_PER_WORD
, GET_MODE_SIZE (GET_MODE (x
))));
5207 new = gen_rtx (MEM
, mode
, plus_constant (XEXP (x
, 0), offset
));
5208 if (! memory_address_p (mode
, XEXP (new, 0)))
5210 MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x
);
5211 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x
);
5212 MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x
);
5219 /* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
5220 branch. It will be zero if not.
5222 In certain cases, this can cause us to add an equivalence. For example,
5223 if we are following the taken case of
5225 we can add the fact that `i' and '2' are now equivalent.
5227 In any case, we can record that this comparison was passed. If the same
5228 comparison is seen later, we will know its value. */
5231 record_jump_equiv (insn
, taken
)
5235 int cond_known_true
;
5237 enum machine_mode mode
;
5238 int reversed_nonequality
= 0;
5241 /* Ensure this is the right kind of insn. */
5242 if (! condjump_p (insn
) || simplejump_p (insn
))
5245 /* See if this jump condition is known true or false. */
5247 cond_known_true
= (XEXP (SET_SRC (PATTERN (insn
)), 2) == pc_rtx
);
5249 cond_known_true
= (XEXP (SET_SRC (PATTERN (insn
)), 1) == pc_rtx
);
5251 /* Get the type of comparison being done and the operands being compared.
5252 If we had to reverse a non-equality condition, record that fact so we
5253 know that it isn't valid for floating-point. */
5254 code
= GET_CODE (XEXP (SET_SRC (PATTERN (insn
)), 0));
5255 op0
= fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn
)), 0), 0), insn
);
5256 op1
= fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn
)), 0), 1), insn
);
5258 code
= find_comparison_args (code
, &op0
, &op1
);
5259 if (! cond_known_true
)
5261 reversed_nonequality
= (code
!= EQ
&& code
!= NE
);
5262 code
= reverse_condition (code
);
5265 /* The mode is the mode of the non-constant. */
5266 mode
= GET_MODE (op0
);
5267 if (mode
== VOIDmode
) mode
= GET_MODE (op1
);
5269 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
);
5272 /* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
5273 REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
5274 Make any useful entries we can with that information. Called from
5275 above function and called recursively. */
5278 record_jump_cond (code
, mode
, op0
, op1
, reversed_nonequality
)
5280 enum machine_mode mode
;
5282 int reversed_nonequality
;
5284 int op0_hash_code
, op1_hash_code
;
5285 int op0_in_memory
, op0_in_struct
, op1_in_memory
, op1_in_struct
;
5286 struct table_elt
*op0_elt
, *op1_elt
;
5288 /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
5289 we know that they are also equal in the smaller mode (this is also
5290 true for all smaller modes whether or not there is a SUBREG, but
5291 is not worth testing for with no SUBREG. */
5293 if (code
== EQ
&& GET_CODE (op0
) == SUBREG
5294 && GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
))))
5296 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
5297 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
5299 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
5300 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op1
, 0),
5301 reversed_nonequality
);
5304 if (code
== EQ
&& GET_CODE (op1
) == SUBREG
5305 && GET_MODE_SIZE (mode
) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
))))
5307 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
5308 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
5310 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
5311 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op0
, 0),
5312 reversed_nonequality
);
5315 /* Similarly, if this is an NE comparison, and either is a SUBREG
5316 making a smaller mode, we know the whole thing is also NE. */
5318 if (code
== NE
&& GET_CODE (op0
) == SUBREG
5319 && subreg_lowpart_p (op0
)
5320 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0
))))
5322 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op0
));
5323 rtx tem
= gen_lowpart_if_possible (inner_mode
, op1
);
5325 record_jump_cond (code
, mode
, SUBREG_REG (op0
),
5326 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op1
, 0),
5327 reversed_nonequality
);
5330 if (code
== NE
&& GET_CODE (op1
) == SUBREG
5331 && subreg_lowpart_p (op1
)
5332 && GET_MODE_SIZE (mode
) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1
))))
5334 enum machine_mode inner_mode
= GET_MODE (SUBREG_REG (op1
));
5335 rtx tem
= gen_lowpart_if_possible (inner_mode
, op0
);
5337 record_jump_cond (code
, mode
, SUBREG_REG (op1
),
5338 tem
? tem
: gen_rtx (SUBREG
, inner_mode
, op0
, 0),
5339 reversed_nonequality
);
5342 /* Hash both operands. */
5345 hash_arg_in_memory
= 0;
5346 hash_arg_in_struct
= 0;
5347 op0_hash_code
= HASH (op0
, mode
);
5348 op0_in_memory
= hash_arg_in_memory
;
5349 op0_in_struct
= hash_arg_in_struct
;
5355 hash_arg_in_memory
= 0;
5356 hash_arg_in_struct
= 0;
5357 op1_hash_code
= HASH (op1
, mode
);
5358 op1_in_memory
= hash_arg_in_memory
;
5359 op1_in_struct
= hash_arg_in_struct
;
5364 /* Look up both operands. */
5365 op0_elt
= lookup (op0
, op0_hash_code
, mode
);
5366 op1_elt
= lookup (op1
, op1_hash_code
, mode
);
5368 /* If we aren't setting two things equal all we can do is save this
5369 comparison. Similarly if this is floating-point. In the latter
5370 case, OP1 might be zero and both -0.0 and 0.0 are equal to it.
5371 If we record the equality, we might inadvertently delete code
5372 whose intent was to change -0 to +0. */
5374 if (code
!= EQ
|| GET_MODE_CLASS (GET_MODE (op0
)) == MODE_FLOAT
)
5376 /* If we reversed a floating-point comparison, if OP0 is not a
5377 register, or if OP1 is neither a register or constant, we can't
5380 if (GET_CODE (op1
) != REG
)
5381 op1
= equiv_constant (op1
);
5383 if ((reversed_nonequality
&& GET_MODE_CLASS (mode
) != MODE_INT
)
5384 || GET_CODE (op0
) != REG
|| op1
== 0)
5387 /* Put OP0 in the hash table if it isn't already. This gives it a
5388 new quantity number. */
5391 if (insert_regs (op0
, NULL_PTR
, 0))
5393 rehash_using_reg (op0
);
5394 op0_hash_code
= HASH (op0
, mode
);
5397 op0_elt
= insert (op0
, NULL_PTR
, op0_hash_code
, mode
);
5398 op0_elt
->in_memory
= op0_in_memory
;
5399 op0_elt
->in_struct
= op0_in_struct
;
5402 qty_comparison_code
[reg_qty
[REGNO (op0
)]] = code
;
5403 if (GET_CODE (op1
) == REG
)
5405 /* Put OP1 in the hash table so it gets a new quantity number. */
5408 if (insert_regs (op1
, NULL_PTR
, 0))
5410 rehash_using_reg (op1
);
5411 op1_hash_code
= HASH (op1
, mode
);
5414 op1_elt
= insert (op1
, NULL_PTR
, op1_hash_code
, mode
);
5415 op1_elt
->in_memory
= op1_in_memory
;
5416 op1_elt
->in_struct
= op1_in_struct
;
5419 qty_comparison_qty
[reg_qty
[REGNO (op0
)]] = reg_qty
[REGNO (op1
)];
5420 qty_comparison_const
[reg_qty
[REGNO (op0
)]] = 0;
5424 qty_comparison_qty
[reg_qty
[REGNO (op0
)]] = -1;
5425 qty_comparison_const
[reg_qty
[REGNO (op0
)]] = op1
;
5431 /* If both are equivalent, merge the two classes. Save this class for
5432 `cse_set_around_loop'. */
5433 if (op0_elt
&& op1_elt
)
5435 merge_equiv_classes (op0_elt
, op1_elt
);
5436 last_jump_equiv_class
= op0_elt
;
5439 /* For whichever side doesn't have an equivalence, make one. */
5442 if (insert_regs (op0
, op1_elt
, 0))
5444 rehash_using_reg (op0
);
5445 op0_hash_code
= HASH (op0
, mode
);
5448 op0_elt
= insert (op0
, op1_elt
, op0_hash_code
, mode
);
5449 op0_elt
->in_memory
= op0_in_memory
;
5450 op0_elt
->in_struct
= op0_in_struct
;
5451 last_jump_equiv_class
= op0_elt
;
5456 if (insert_regs (op1
, op0_elt
, 0))
5458 rehash_using_reg (op1
);
5459 op1_hash_code
= HASH (op1
, mode
);
5462 op1_elt
= insert (op1
, op0_elt
, op1_hash_code
, mode
);
5463 op1_elt
->in_memory
= op1_in_memory
;
5464 op1_elt
->in_struct
= op1_in_struct
;
5465 last_jump_equiv_class
= op1_elt
;
5469 /* CSE processing for one instruction.
5470 First simplify sources and addresses of all assignments
5471 in the instruction, using previously-computed equivalents values.
5472 Then install the new sources and destinations in the table
5473 of available values.
5475 If IN_LIBCALL_BLOCK is nonzero, don't record any equivalence made in
5478 /* Data on one SET contained in the instruction. */
5482 /* The SET rtx itself. */
5484 /* The SET_SRC of the rtx (the original value, if it is changing). */
5486 /* The hash-table element for the SET_SRC of the SET. */
5487 struct table_elt
*src_elt
;
5488 /* Hash code for the SET_SRC. */
5490 /* Hash code for the SET_DEST. */
5492 /* The SET_DEST, with SUBREG, etc., stripped. */
5494 /* Place where the pointer to the INNER_DEST was found. */
5495 rtx
*inner_dest_loc
;
5496 /* Nonzero if the SET_SRC is in memory. */
5498 /* Nonzero if the SET_SRC is in a structure. */
5500 /* Nonzero if the SET_SRC contains something
5501 whose value cannot be predicted and understood. */
5503 /* Original machine mode, in case it becomes a CONST_INT. */
5504 enum machine_mode mode
;
5505 /* A constant equivalent for SET_SRC, if any. */
5507 /* Hash code of constant equivalent for SET_SRC. */
5508 int src_const_hash_code
;
5509 /* Table entry for constant equivalent for SET_SRC, if any. */
5510 struct table_elt
*src_const_elt
;
5514 cse_insn (insn
, in_libcall_block
)
5516 int in_libcall_block
;
5518 register rtx x
= PATTERN (insn
);
5521 register int n_sets
= 0;
5523 /* Records what this insn does to set CC0. */
5524 rtx this_insn_cc0
= 0;
5525 enum machine_mode this_insn_cc0_mode
;
5526 struct write_data writes_memory
;
5527 static struct write_data init
= {0, 0, 0, 0};
5530 struct table_elt
*src_eqv_elt
= 0;
5531 int src_eqv_volatile
;
5532 int src_eqv_in_memory
;
5533 int src_eqv_in_struct
;
5534 int src_eqv_hash_code
;
5539 writes_memory
= init
;
5541 /* Find all the SETs and CLOBBERs in this instruction.
5542 Record all the SETs in the array `set' and count them.
5543 Also determine whether there is a CLOBBER that invalidates
5544 all memory references, or all references at varying addresses. */
5546 if (GET_CODE (x
) == SET
)
5548 sets
= (struct set
*) alloca (sizeof (struct set
));
5551 /* Ignore SETs that are unconditional jumps.
5552 They never need cse processing, so this does not hurt.
5553 The reason is not efficiency but rather
5554 so that we can test at the end for instructions
5555 that have been simplified to unconditional jumps
5556 and not be misled by unchanged instructions
5557 that were unconditional jumps to begin with. */
5558 if (SET_DEST (x
) == pc_rtx
5559 && GET_CODE (SET_SRC (x
)) == LABEL_REF
)
5562 /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
5563 The hard function value register is used only once, to copy to
5564 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
5565 Ensure we invalidate the destination register. On the 80386 no
5566 other code would invalidate it since it is a fixed_reg. */
5568 else if (GET_CODE (SET_SRC (x
)) == CALL
)
5570 canon_reg (SET_SRC (x
), insn
);
5571 apply_change_group ();
5572 fold_rtx (SET_SRC (x
), insn
);
5573 invalidate (SET_DEST (x
));
5578 else if (GET_CODE (x
) == PARALLEL
)
5580 register int lim
= XVECLEN (x
, 0);
5582 sets
= (struct set
*) alloca (lim
* sizeof (struct set
));
5584 /* Find all regs explicitly clobbered in this insn,
5585 and ensure they are not replaced with any other regs
5586 elsewhere in this insn.
5587 When a reg that is clobbered is also used for input,
5588 we should presume that that is for a reason,
5589 and we should not substitute some other register
5590 which is not supposed to be clobbered.
5591 Therefore, this loop cannot be merged into the one below
5592 because a CALL may precede a CLOBBER and refer to the
5593 value clobbered. We must not let a canonicalization do
5594 anything in that case. */
5595 for (i
= 0; i
< lim
; i
++)
5597 register rtx y
= XVECEXP (x
, 0, i
);
5598 if (GET_CODE (y
) == CLOBBER
5599 && (GET_CODE (XEXP (y
, 0)) == REG
5600 || GET_CODE (XEXP (y
, 0)) == SUBREG
))
5601 invalidate (XEXP (y
, 0));
5604 for (i
= 0; i
< lim
; i
++)
5606 register rtx y
= XVECEXP (x
, 0, i
);
5607 if (GET_CODE (y
) == SET
)
5609 /* As above, we ignore unconditional jumps and call-insns. */
5610 if (GET_CODE (SET_SRC (y
)) == CALL
)
5612 canon_reg (SET_SRC (y
), insn
);
5613 apply_change_group ();
5614 fold_rtx (SET_SRC (y
), insn
);
5615 invalidate (SET_DEST (y
));
5617 else if (SET_DEST (y
) == pc_rtx
5618 && GET_CODE (SET_SRC (y
)) == LABEL_REF
)
5621 sets
[n_sets
++].rtl
= y
;
5623 else if (GET_CODE (y
) == CLOBBER
)
5625 /* If we clobber memory, take note of that,
5626 and canon the address.
5627 This does nothing when a register is clobbered
5628 because we have already invalidated the reg. */
5629 if (GET_CODE (XEXP (y
, 0)) == MEM
)
5631 canon_reg (XEXP (y
, 0), NULL_RTX
);
5632 note_mem_written (XEXP (y
, 0), &writes_memory
);
5635 else if (GET_CODE (y
) == USE
5636 && ! (GET_CODE (XEXP (y
, 0)) == REG
5637 && REGNO (XEXP (y
, 0)) < FIRST_PSEUDO_REGISTER
))
5638 canon_reg (y
, NULL_RTX
);
5639 else if (GET_CODE (y
) == CALL
)
5641 canon_reg (y
, insn
);
5642 apply_change_group ();
5647 else if (GET_CODE (x
) == CLOBBER
)
5649 if (GET_CODE (XEXP (x
, 0)) == MEM
)
5651 canon_reg (XEXP (x
, 0), NULL_RTX
);
5652 note_mem_written (XEXP (x
, 0), &writes_memory
);
5656 /* Canonicalize a USE of a pseudo register or memory location. */
5657 else if (GET_CODE (x
) == USE
5658 && ! (GET_CODE (XEXP (x
, 0)) == REG
5659 && REGNO (XEXP (x
, 0)) < FIRST_PSEUDO_REGISTER
))
5660 canon_reg (XEXP (x
, 0), NULL_RTX
);
5661 else if (GET_CODE (x
) == CALL
)
5663 canon_reg (x
, insn
);
5664 apply_change_group ();
5668 if (n_sets
== 1 && REG_NOTES (insn
) != 0)
5670 /* Store the equivalent value in SRC_EQV, if different. */
5671 rtx tem
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
5673 if (tem
&& ! rtx_equal_p (XEXP (tem
, 0), SET_SRC (sets
[0].rtl
)))
5674 src_eqv
= canon_reg (XEXP (tem
, 0), NULL_RTX
);
5677 /* Canonicalize sources and addresses of destinations.
5678 We do this in a separate pass to avoid problems when a MATCH_DUP is
5679 present in the insn pattern. In that case, we want to ensure that
5680 we don't break the duplicate nature of the pattern. So we will replace
5681 both operands at the same time. Otherwise, we would fail to find an
5682 equivalent substitution in the loop calling validate_change below.
5684 We used to suppress canonicalization of DEST if it appears in SRC,
5685 but we don't do this any more. */
5687 for (i
= 0; i
< n_sets
; i
++)
5689 rtx dest
= SET_DEST (sets
[i
].rtl
);
5690 rtx src
= SET_SRC (sets
[i
].rtl
);
5691 rtx
new = canon_reg (src
, insn
);
5693 if ((GET_CODE (new) == REG
&& GET_CODE (src
) == REG
5694 && ((REGNO (new) < FIRST_PSEUDO_REGISTER
)
5695 != (REGNO (src
) < FIRST_PSEUDO_REGISTER
)))
5696 || insn_n_dups
[recog_memoized (insn
)] > 0)
5697 validate_change (insn
, &SET_SRC (sets
[i
].rtl
), new, 1);
5699 SET_SRC (sets
[i
].rtl
) = new;
5701 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
5703 validate_change (insn
, &XEXP (dest
, 1),
5704 canon_reg (XEXP (dest
, 1), insn
), 1);
5705 validate_change (insn
, &XEXP (dest
, 2),
5706 canon_reg (XEXP (dest
, 2), insn
), 1);
5709 while (GET_CODE (dest
) == SUBREG
|| GET_CODE (dest
) == STRICT_LOW_PART
5710 || GET_CODE (dest
) == ZERO_EXTRACT
5711 || GET_CODE (dest
) == SIGN_EXTRACT
)
5712 dest
= XEXP (dest
, 0);
5714 if (GET_CODE (dest
) == MEM
)
5715 canon_reg (dest
, insn
);
5718 /* Now that we have done all the replacements, we can apply the change
5719 group and see if they all work. Note that this will cause some
5720 canonicalizations that would have worked individually not to be applied
5721 because some other canonicalization didn't work, but this should not
5724 apply_change_group ();
5726 /* Set sets[i].src_elt to the class each source belongs to.
5727 Detect assignments from or to volatile things
5728 and set set[i] to zero so they will be ignored
5729 in the rest of this function.
5731 Nothing in this loop changes the hash table or the register chains. */
5733 for (i
= 0; i
< n_sets
; i
++)
5735 register rtx src
, dest
;
5736 register rtx src_folded
;
5737 register struct table_elt
*elt
= 0, *p
;
5738 enum machine_mode mode
;
5741 rtx src_related
= 0;
5742 struct table_elt
*src_const_elt
= 0;
5743 int src_cost
= 10000, src_eqv_cost
= 10000, src_folded_cost
= 10000;
5744 int src_related_cost
= 10000, src_elt_cost
= 10000;
5745 /* Set non-zero if we need to call force_const_mem on with the
5746 contents of src_folded before using it. */
5747 int src_folded_force_flag
= 0;
5749 dest
= SET_DEST (sets
[i
].rtl
);
5750 src
= SET_SRC (sets
[i
].rtl
);
5752 /* If SRC is a constant that has no machine mode,
5753 hash it with the destination's machine mode.
5754 This way we can keep different modes separate. */
5756 mode
= GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
5757 sets
[i
].mode
= mode
;
5761 enum machine_mode eqvmode
= mode
;
5762 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5763 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
5765 hash_arg_in_memory
= 0;
5766 hash_arg_in_struct
= 0;
5767 src_eqv
= fold_rtx (src_eqv
, insn
);
5768 src_eqv_hash_code
= HASH (src_eqv
, eqvmode
);
5770 /* Find the equivalence class for the equivalent expression. */
5773 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash_code
, eqvmode
);
5775 src_eqv_volatile
= do_not_record
;
5776 src_eqv_in_memory
= hash_arg_in_memory
;
5777 src_eqv_in_struct
= hash_arg_in_struct
;
5780 /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
5781 value of the INNER register, not the destination. So it is not
5782 a legal substitution for the source. But save it for later. */
5783 if (GET_CODE (dest
) == STRICT_LOW_PART
)
5786 src_eqv_here
= src_eqv
;
5788 /* Simplify and foldable subexpressions in SRC. Then get the fully-
5789 simplified result, which may not necessarily be valid. */
5790 src_folded
= fold_rtx (src
, insn
);
5792 /* If storing a constant in a bitfield, pre-truncate the constant
5793 so we will be able to record it later. */
5794 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
5795 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
5797 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
5799 if (GET_CODE (src
) == CONST_INT
5800 && GET_CODE (width
) == CONST_INT
5801 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
5802 && (INTVAL (src
) & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
5804 = GEN_INT (INTVAL (src
) & (((HOST_WIDE_INT
) 1
5805 << INTVAL (width
)) - 1));
5808 /* Compute SRC's hash code, and also notice if it
5809 should not be recorded at all. In that case,
5810 prevent any further processing of this assignment. */
5812 hash_arg_in_memory
= 0;
5813 hash_arg_in_struct
= 0;
5816 sets
[i
].src_hash_code
= HASH (src
, mode
);
5817 sets
[i
].src_volatile
= do_not_record
;
5818 sets
[i
].src_in_memory
= hash_arg_in_memory
;
5819 sets
[i
].src_in_struct
= hash_arg_in_struct
;
5822 /* It is no longer clear why we used to do this, but it doesn't
5823 appear to still be needed. So let's try without it since this
5824 code hurts cse'ing widened ops. */
5825 /* If source is a perverse subreg (such as QI treated as an SI),
5826 treat it as volatile. It may do the work of an SI in one context
5827 where the extra bits are not being used, but cannot replace an SI
5829 if (GET_CODE (src
) == SUBREG
5830 && (GET_MODE_SIZE (GET_MODE (src
))
5831 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src
)))))
5832 sets
[i
].src_volatile
= 1;
5835 /* Locate all possible equivalent forms for SRC. Try to replace
5836 SRC in the insn with each cheaper equivalent.
5838 We have the following types of equivalents: SRC itself, a folded
5839 version, a value given in a REG_EQUAL note, or a value related
5842 Each of these equivalents may be part of an additional class
5843 of equivalents (if more than one is in the table, they must be in
5844 the same class; we check for this).
5846 If the source is volatile, we don't do any table lookups.
5848 We note any constant equivalent for possible later use in a
5851 if (!sets
[i
].src_volatile
)
5852 elt
= lookup (src
, sets
[i
].src_hash_code
, mode
);
5854 sets
[i
].src_elt
= elt
;
5856 if (elt
&& src_eqv_here
&& src_eqv_elt
)
5858 if (elt
->first_same_value
!= src_eqv_elt
->first_same_value
)
5860 /* The REG_EQUAL is indicating that two formerly distinct
5861 classes are now equivalent. So merge them. */
5862 merge_equiv_classes (elt
, src_eqv_elt
);
5863 src_eqv_hash_code
= HASH (src_eqv
, elt
->mode
);
5864 src_eqv_elt
= lookup (src_eqv
, src_eqv_hash_code
, elt
->mode
);
5870 else if (src_eqv_elt
)
5873 /* Try to find a constant somewhere and record it in `src_const'.
5874 Record its table element, if any, in `src_const_elt'. Look in
5875 any known equivalences first. (If the constant is not in the
5876 table, also set `sets[i].src_const_hash_code'). */
5878 for (p
= elt
->first_same_value
; p
; p
= p
->next_same_value
)
5882 src_const_elt
= elt
;
5887 && (CONSTANT_P (src_folded
)
5888 /* Consider (minus (label_ref L1) (label_ref L2)) as
5889 "constant" here so we will record it. This allows us
5890 to fold switch statements when an ADDR_DIFF_VEC is used. */
5891 || (GET_CODE (src_folded
) == MINUS
5892 && GET_CODE (XEXP (src_folded
, 0)) == LABEL_REF
5893 && GET_CODE (XEXP (src_folded
, 1)) == LABEL_REF
)))
5894 src_const
= src_folded
, src_const_elt
= elt
;
5895 else if (src_const
== 0 && src_eqv_here
&& CONSTANT_P (src_eqv_here
))
5896 src_const
= src_eqv_here
, src_const_elt
= src_eqv_elt
;
5898 /* If we don't know if the constant is in the table, get its
5899 hash code and look it up. */
5900 if (src_const
&& src_const_elt
== 0)
5902 sets
[i
].src_const_hash_code
= HASH (src_const
, mode
);
5903 src_const_elt
= lookup (src_const
, sets
[i
].src_const_hash_code
,
5907 sets
[i
].src_const
= src_const
;
5908 sets
[i
].src_const_elt
= src_const_elt
;
5910 /* If the constant and our source are both in the table, mark them as
5911 equivalent. Otherwise, if a constant is in the table but the source
5912 isn't, set ELT to it. */
5913 if (src_const_elt
&& elt
5914 && src_const_elt
->first_same_value
!= elt
->first_same_value
)
5915 merge_equiv_classes (elt
, src_const_elt
);
5916 else if (src_const_elt
&& elt
== 0)
5917 elt
= src_const_elt
;
5919 /* See if there is a register linearly related to a constant
5920 equivalent of SRC. */
5922 && (GET_CODE (src_const
) == CONST
5923 || (src_const_elt
&& src_const_elt
->related_value
!= 0)))
5925 src_related
= use_related_value (src_const
, src_const_elt
);
5928 struct table_elt
*src_related_elt
5929 = lookup (src_related
, HASH (src_related
, mode
), mode
);
5930 if (src_related_elt
&& elt
)
5932 if (elt
->first_same_value
5933 != src_related_elt
->first_same_value
)
5934 /* This can occur when we previously saw a CONST
5935 involving a SYMBOL_REF and then see the SYMBOL_REF
5936 twice. Merge the involved classes. */
5937 merge_equiv_classes (elt
, src_related_elt
);
5940 src_related_elt
= 0;
5942 else if (src_related_elt
&& elt
== 0)
5943 elt
= src_related_elt
;
5947 /* See if we have a CONST_INT that is already in a register in a
5950 if (src_const
&& src_related
== 0 && GET_CODE (src_const
) == CONST_INT
5951 && GET_MODE_CLASS (mode
) == MODE_INT
5952 && GET_MODE_BITSIZE (mode
) < BITS_PER_WORD
)
5954 enum machine_mode wider_mode
;
5956 for (wider_mode
= GET_MODE_WIDER_MODE (mode
);
5957 GET_MODE_BITSIZE (wider_mode
) <= BITS_PER_WORD
5958 && src_related
== 0;
5959 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
5961 struct table_elt
*const_elt
5962 = lookup (src_const
, HASH (src_const
, wider_mode
), wider_mode
);
5967 for (const_elt
= const_elt
->first_same_value
;
5968 const_elt
; const_elt
= const_elt
->next_same_value
)
5969 if (GET_CODE (const_elt
->exp
) == REG
)
5971 src_related
= gen_lowpart_if_possible (mode
,
5978 /* Another possibility is that we have an AND with a constant in
5979 a mode narrower than a word. If so, it might have been generated
5980 as part of an "if" which would narrow the AND. If we already
5981 have done the AND in a wider mode, we can use a SUBREG of that
5984 if (flag_expensive_optimizations
&& ! src_related
5985 && GET_CODE (src
) == AND
&& GET_CODE (XEXP (src
, 1)) == CONST_INT
5986 && GET_MODE_SIZE (mode
) < UNITS_PER_WORD
)
5988 enum machine_mode tmode
;
5989 rtx new_and
= gen_rtx (AND
, VOIDmode
, NULL_RTX
, XEXP (src
, 1));
5991 for (tmode
= GET_MODE_WIDER_MODE (mode
);
5992 GET_MODE_SIZE (tmode
) <= UNITS_PER_WORD
;
5993 tmode
= GET_MODE_WIDER_MODE (tmode
))
5995 rtx inner
= gen_lowpart_if_possible (tmode
, XEXP (src
, 0));
5996 struct table_elt
*larger_elt
;
6000 PUT_MODE (new_and
, tmode
);
6001 XEXP (new_and
, 0) = inner
;
6002 larger_elt
= lookup (new_and
, HASH (new_and
, tmode
), tmode
);
6003 if (larger_elt
== 0)
6006 for (larger_elt
= larger_elt
->first_same_value
;
6007 larger_elt
; larger_elt
= larger_elt
->next_same_value
)
6008 if (GET_CODE (larger_elt
->exp
) == REG
)
6011 = gen_lowpart_if_possible (mode
, larger_elt
->exp
);
6021 if (src
== src_folded
)
6024 /* At this point, ELT, if non-zero, points to a class of expressions
6025 equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
6026 and SRC_RELATED, if non-zero, each contain additional equivalent
6027 expressions. Prune these latter expressions by deleting expressions
6028 already in the equivalence class.
6030 Check for an equivalent identical to the destination. If found,
6031 this is the preferred equivalent since it will likely lead to
6032 elimination of the insn. Indicate this by placing it in
6035 if (elt
) elt
= elt
->first_same_value
;
6036 for (p
= elt
; p
; p
= p
->next_same_value
)
6038 enum rtx_code code
= GET_CODE (p
->exp
);
6040 /* If the expression is not valid, ignore it. Then we do not
6041 have to check for validity below. In most cases, we can use
6042 `rtx_equal_p', since canonicalization has already been done. */
6043 if (code
!= REG
&& ! exp_equiv_p (p
->exp
, p
->exp
, 1, 0))
6046 if (src
&& GET_CODE (src
) == code
&& rtx_equal_p (src
, p
->exp
))
6048 else if (src_folded
&& GET_CODE (src_folded
) == code
6049 && rtx_equal_p (src_folded
, p
->exp
))
6051 else if (src_eqv_here
&& GET_CODE (src_eqv_here
) == code
6052 && rtx_equal_p (src_eqv_here
, p
->exp
))
6054 else if (src_related
&& GET_CODE (src_related
) == code
6055 && rtx_equal_p (src_related
, p
->exp
))
6058 /* This is the same as the destination of the insns, we want
6059 to prefer it. Copy it to src_related. The code below will
6060 then give it a negative cost. */
6061 if (GET_CODE (dest
) == code
&& rtx_equal_p (p
->exp
, dest
))
6066 /* Find the cheapest valid equivalent, trying all the available
6067 possibilities. Prefer items not in the hash table to ones
6068 that are when they are equal cost. Note that we can never
6069 worsen an insn as the current contents will also succeed.
6070 If we find an equivalent identical to the destination, use it as best,
6071 since this insn will probably be eliminated in that case. */
6074 if (rtx_equal_p (src
, dest
))
6077 src_cost
= COST (src
);
6082 if (rtx_equal_p (src_eqv_here
, dest
))
6085 src_eqv_cost
= COST (src_eqv_here
);
6090 if (rtx_equal_p (src_folded
, dest
))
6091 src_folded_cost
= -1;
6093 src_folded_cost
= COST (src_folded
);
6098 if (rtx_equal_p (src_related
, dest
))
6099 src_related_cost
= -1;
6101 src_related_cost
= COST (src_related
);
6104 /* If this was an indirect jump insn, a known label will really be
6105 cheaper even though it looks more expensive. */
6106 if (dest
== pc_rtx
&& src_const
&& GET_CODE (src_const
) == LABEL_REF
)
6107 src_folded
= src_const
, src_folded_cost
= -1;
6109 /* Terminate loop when replacement made. This must terminate since
6110 the current contents will be tested and will always be valid. */
6115 /* Skip invalid entries. */
6116 while (elt
&& GET_CODE (elt
->exp
) != REG
6117 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
6118 elt
= elt
->next_same_value
;
6120 if (elt
) src_elt_cost
= elt
->cost
;
6122 /* Find cheapest and skip it for the next time. For items
6123 of equal cost, use this order:
6124 src_folded, src, src_eqv, src_related and hash table entry. */
6125 if (src_folded_cost
<= src_cost
6126 && src_folded_cost
<= src_eqv_cost
6127 && src_folded_cost
<= src_related_cost
6128 && src_folded_cost
<= src_elt_cost
)
6130 trial
= src_folded
, src_folded_cost
= 10000;
6131 if (src_folded_force_flag
)
6132 trial
= force_const_mem (mode
, trial
);
6134 else if (src_cost
<= src_eqv_cost
6135 && src_cost
<= src_related_cost
6136 && src_cost
<= src_elt_cost
)
6137 trial
= src
, src_cost
= 10000;
6138 else if (src_eqv_cost
<= src_related_cost
6139 && src_eqv_cost
<= src_elt_cost
)
6140 trial
= src_eqv_here
, src_eqv_cost
= 10000;
6141 else if (src_related_cost
<= src_elt_cost
)
6142 trial
= src_related
, src_related_cost
= 10000;
6145 trial
= copy_rtx (elt
->exp
);
6146 elt
= elt
->next_same_value
;
6147 src_elt_cost
= 10000;
6150 /* We don't normally have an insn matching (set (pc) (pc)), so
6151 check for this separately here. We will delete such an
6154 Tablejump insns contain a USE of the table, so simply replacing
6155 the operand with the constant won't match. This is simply an
6156 unconditional branch, however, and is therefore valid. Just
6157 insert the substitution here and we will delete and re-emit
6160 if (n_sets
== 1 && dest
== pc_rtx
6162 || (GET_CODE (trial
) == LABEL_REF
6163 && ! condjump_p (insn
))))
6165 /* If TRIAL is a label in front of a jump table, we are
6166 really falling through the switch (this is how casesi
6167 insns work), so we must branch around the table. */
6168 if (GET_CODE (trial
) == CODE_LABEL
6169 && NEXT_INSN (trial
) != 0
6170 && GET_CODE (NEXT_INSN (trial
)) == JUMP_INSN
6171 && (GET_CODE (PATTERN (NEXT_INSN (trial
))) == ADDR_DIFF_VEC
6172 || GET_CODE (PATTERN (NEXT_INSN (trial
))) == ADDR_VEC
))
6174 trial
= gen_rtx (LABEL_REF
, Pmode
, get_label_after (trial
));
6176 SET_SRC (sets
[i
].rtl
) = trial
;
6180 /* Look for a substitution that makes a valid insn. */
6181 else if (validate_change (insn
, &SET_SRC (sets
[i
].rtl
), trial
, 0))
6183 SET_SRC (sets
[i
].rtl
) = canon_reg (SET_SRC (sets
[i
].rtl
), insn
);
6187 /* If we previously found constant pool entries for
6188 constants and this is a constant, try making a
6189 pool entry. Put it in src_folded unless we already have done
6190 this since that is where it likely came from. */
6192 else if (constant_pool_entries_cost
6193 && CONSTANT_P (trial
)
6194 && (src_folded
== 0 || GET_CODE (src_folded
) != MEM
)
6195 && GET_MODE_CLASS (mode
) != MODE_CC
)
6197 src_folded_force_flag
= 1;
6199 src_folded_cost
= constant_pool_entries_cost
;
6203 src
= SET_SRC (sets
[i
].rtl
);
6205 /* In general, it is good to have a SET with SET_SRC == SET_DEST.
6206 However, there is an important exception: If both are registers
6207 that are not the head of their equivalence class, replace SET_SRC
6208 with the head of the class. If we do not do this, we will have
6209 both registers live over a portion of the basic block. This way,
6210 their lifetimes will likely abut instead of overlapping. */
6211 if (GET_CODE (dest
) == REG
6212 && REGNO_QTY_VALID_P (REGNO (dest
))
6213 && qty_mode
[reg_qty
[REGNO (dest
)]] == GET_MODE (dest
)
6214 && qty_first_reg
[reg_qty
[REGNO (dest
)]] != REGNO (dest
)
6215 && GET_CODE (src
) == REG
&& REGNO (src
) == REGNO (dest
)
6216 /* Don't do this if the original insn had a hard reg as
6218 && (GET_CODE (sets
[i
].src
) != REG
6219 || REGNO (sets
[i
].src
) >= FIRST_PSEUDO_REGISTER
))
6220 /* We can't call canon_reg here because it won't do anything if
6221 SRC is a hard register. */
6223 int first
= qty_first_reg
[reg_qty
[REGNO (src
)]];
6225 src
= SET_SRC (sets
[i
].rtl
)
6226 = first
>= FIRST_PSEUDO_REGISTER
? regno_reg_rtx
[first
]
6227 : gen_rtx (REG
, GET_MODE (src
), first
);
6229 /* If we had a constant that is cheaper than what we are now
6230 setting SRC to, use that constant. We ignored it when we
6231 thought we could make this into a no-op. */
6232 if (src_const
&& COST (src_const
) < COST (src
)
6233 && validate_change (insn
, &SET_SRC (sets
[i
].rtl
), src_const
, 0))
6237 /* If we made a change, recompute SRC values. */
6238 if (src
!= sets
[i
].src
)
6241 hash_arg_in_memory
= 0;
6242 hash_arg_in_struct
= 0;
6244 sets
[i
].src_hash_code
= HASH (src
, mode
);
6245 sets
[i
].src_volatile
= do_not_record
;
6246 sets
[i
].src_in_memory
= hash_arg_in_memory
;
6247 sets
[i
].src_in_struct
= hash_arg_in_struct
;
6248 sets
[i
].src_elt
= lookup (src
, sets
[i
].src_hash_code
, mode
);
6251 /* If this is a single SET, we are setting a register, and we have an
6252 equivalent constant, we want to add a REG_NOTE. We don't want
6253 to write a REG_EQUAL note for a constant pseudo since verifying that
6254 that pseudo hasn't been eliminated is a pain. Such a note also
6255 won't help anything. */
6256 if (n_sets
== 1 && src_const
&& GET_CODE (dest
) == REG
6257 && GET_CODE (src_const
) != REG
)
6259 rtx tem
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
6261 /* Record the actual constant value in a REG_EQUAL note, making
6262 a new one if one does not already exist. */
6264 XEXP (tem
, 0) = src_const
;
6266 REG_NOTES (insn
) = gen_rtx (EXPR_LIST
, REG_EQUAL
,
6267 src_const
, REG_NOTES (insn
));
6269 /* If storing a constant value in a register that
6270 previously held the constant value 0,
6271 record this fact with a REG_WAS_0 note on this insn.
6273 Note that the *register* is required to have previously held 0,
6274 not just any register in the quantity and we must point to the
6275 insn that set that register to zero.
6277 Rather than track each register individually, we just see if
6278 the last set for this quantity was for this register. */
6280 if (REGNO_QTY_VALID_P (REGNO (dest
))
6281 && qty_const
[reg_qty
[REGNO (dest
)]] == const0_rtx
)
6283 /* See if we previously had a REG_WAS_0 note. */
6284 rtx note
= find_reg_note (insn
, REG_WAS_0
, NULL_RTX
);
6285 rtx const_insn
= qty_const_insn
[reg_qty
[REGNO (dest
)]];
6287 if ((tem
= single_set (const_insn
)) != 0
6288 && rtx_equal_p (SET_DEST (tem
), dest
))
6291 XEXP (note
, 0) = const_insn
;
6293 REG_NOTES (insn
) = gen_rtx (INSN_LIST
, REG_WAS_0
,
6294 const_insn
, REG_NOTES (insn
));
6299 /* Now deal with the destination. */
6301 sets
[i
].inner_dest_loc
= &SET_DEST (sets
[0].rtl
);
6303 /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
6304 to the MEM or REG within it. */
6305 while (GET_CODE (dest
) == SIGN_EXTRACT
6306 || GET_CODE (dest
) == ZERO_EXTRACT
6307 || GET_CODE (dest
) == SUBREG
6308 || GET_CODE (dest
) == STRICT_LOW_PART
)
6310 sets
[i
].inner_dest_loc
= &XEXP (dest
, 0);
6311 dest
= XEXP (dest
, 0);
6314 sets
[i
].inner_dest
= dest
;
6316 if (GET_CODE (dest
) == MEM
)
6318 dest
= fold_rtx (dest
, insn
);
6320 /* Decide whether we invalidate everything in memory,
6321 or just things at non-fixed places.
6322 Writing a large aggregate must invalidate everything
6323 because we don't know how long it is. */
6324 note_mem_written (dest
, &writes_memory
);
6327 /* Compute the hash code of the destination now,
6328 before the effects of this instruction are recorded,
6329 since the register values used in the address computation
6330 are those before this instruction. */
6331 sets
[i
].dest_hash_code
= HASH (dest
, mode
);
6333 /* Don't enter a bit-field in the hash table
6334 because the value in it after the store
6335 may not equal what was stored, due to truncation. */
6337 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == ZERO_EXTRACT
6338 || GET_CODE (SET_DEST (sets
[i
].rtl
)) == SIGN_EXTRACT
)
6340 rtx width
= XEXP (SET_DEST (sets
[i
].rtl
), 1);
6342 if (src_const
!= 0 && GET_CODE (src_const
) == CONST_INT
6343 && GET_CODE (width
) == CONST_INT
6344 && INTVAL (width
) < HOST_BITS_PER_WIDE_INT
6345 && ! (INTVAL (src_const
)
6346 & ((HOST_WIDE_INT
) (-1) << INTVAL (width
))))
6347 /* Exception: if the value is constant,
6348 and it won't be truncated, record it. */
6352 /* This is chosen so that the destination will be invalidated
6353 but no new value will be recorded.
6354 We must invalidate because sometimes constant
6355 values can be recorded for bitfields. */
6356 sets
[i
].src_elt
= 0;
6357 sets
[i
].src_volatile
= 1;
6363 /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
6365 else if (n_sets
== 1 && dest
== pc_rtx
&& src
== pc_rtx
)
6367 PUT_CODE (insn
, NOTE
);
6368 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
6369 NOTE_SOURCE_FILE (insn
) = 0;
6370 cse_jumps_altered
= 1;
6371 /* One less use of the label this insn used to jump to. */
6372 --LABEL_NUSES (JUMP_LABEL (insn
));
6373 /* No more processing for this set. */
6377 /* If this SET is now setting PC to a label, we know it used to
6378 be a conditional or computed branch. So we see if we can follow
6379 it. If it was a computed branch, delete it and re-emit. */
6380 else if (dest
== pc_rtx
&& GET_CODE (src
) == LABEL_REF
)
6384 /* If this is not in the format for a simple branch and
6385 we are the only SET in it, re-emit it. */
6386 if (! simplejump_p (insn
) && n_sets
== 1)
6388 rtx
new = emit_jump_insn_before (gen_jump (XEXP (src
, 0)), insn
);
6389 JUMP_LABEL (new) = XEXP (src
, 0);
6390 LABEL_NUSES (XEXP (src
, 0))++;
6395 /* Now that we've converted this jump to an unconditional jump,
6396 there is dead code after it. Delete the dead code until we
6397 reach a BARRIER, the end of the function, or a label. Do
6398 not delete NOTEs except for NOTE_INSN_DELETED since later
6399 phases assume these notes are retained. */
6403 while (NEXT_INSN (p
) != 0
6404 && GET_CODE (NEXT_INSN (p
)) != BARRIER
6405 && GET_CODE (NEXT_INSN (p
)) != CODE_LABEL
)
6407 if (GET_CODE (NEXT_INSN (p
)) != NOTE
6408 || NOTE_LINE_NUMBER (NEXT_INSN (p
)) == NOTE_INSN_DELETED
)
6409 delete_insn (NEXT_INSN (p
));
6414 /* If we don't have a BARRIER immediately after INSN, put one there.
6415 Much code assumes that there are no NOTEs between a JUMP_INSN and
6418 if (NEXT_INSN (insn
) == 0
6419 || GET_CODE (NEXT_INSN (insn
)) != BARRIER
)
6420 emit_barrier_after (insn
);
6422 /* We might have two BARRIERs separated by notes. Delete the second
6425 if (p
!= insn
&& NEXT_INSN (p
) != 0
6426 && GET_CODE (NEXT_INSN (p
)) == BARRIER
)
6427 delete_insn (NEXT_INSN (p
));
6429 cse_jumps_altered
= 1;
6433 /* If destination is volatile, invalidate it and then do no further
6434 processing for this assignment. */
6436 else if (do_not_record
)
6438 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
6439 || GET_CODE (dest
) == MEM
)
6444 if (sets
[i
].rtl
!= 0 && dest
!= SET_DEST (sets
[i
].rtl
))
6445 sets
[i
].dest_hash_code
= HASH (SET_DEST (sets
[i
].rtl
), mode
);
6448 /* If setting CC0, record what it was set to, or a constant, if it
6449 is equivalent to a constant. If it is being set to a floating-point
6450 value, make a COMPARE with the appropriate constant of 0. If we
6451 don't do this, later code can interpret this as a test against
6452 const0_rtx, which can cause problems if we try to put it into an
6453 insn as a floating-point operand. */
6454 if (dest
== cc0_rtx
)
6456 this_insn_cc0
= src_const
&& mode
!= VOIDmode
? src_const
: src
;
6457 this_insn_cc0_mode
= mode
;
6458 if (GET_MODE_CLASS (mode
) == MODE_FLOAT
)
6459 this_insn_cc0
= gen_rtx (COMPARE
, VOIDmode
, this_insn_cc0
,
6465 /* Now enter all non-volatile source expressions in the hash table
6466 if they are not already present.
6467 Record their equivalence classes in src_elt.
6468 This way we can insert the corresponding destinations into
6469 the same classes even if the actual sources are no longer in them
6470 (having been invalidated). */
6472 if (src_eqv
&& src_eqv_elt
== 0 && sets
[0].rtl
!= 0 && ! src_eqv_volatile
6473 && ! rtx_equal_p (src_eqv
, SET_DEST (sets
[0].rtl
)))
6475 register struct table_elt
*elt
;
6476 register struct table_elt
*classp
= sets
[0].src_elt
;
6477 rtx dest
= SET_DEST (sets
[0].rtl
);
6478 enum machine_mode eqvmode
= GET_MODE (dest
);
6480 if (GET_CODE (dest
) == STRICT_LOW_PART
)
6482 eqvmode
= GET_MODE (SUBREG_REG (XEXP (dest
, 0)));
6485 if (insert_regs (src_eqv
, classp
, 0))
6486 src_eqv_hash_code
= HASH (src_eqv
, eqvmode
);
6487 elt
= insert (src_eqv
, classp
, src_eqv_hash_code
, eqvmode
);
6488 elt
->in_memory
= src_eqv_in_memory
;
6489 elt
->in_struct
= src_eqv_in_struct
;
6493 for (i
= 0; i
< n_sets
; i
++)
6494 if (sets
[i
].rtl
&& ! sets
[i
].src_volatile
6495 && ! rtx_equal_p (SET_SRC (sets
[i
].rtl
), SET_DEST (sets
[i
].rtl
)))
6497 if (GET_CODE (SET_DEST (sets
[i
].rtl
)) == STRICT_LOW_PART
)
6499 /* REG_EQUAL in setting a STRICT_LOW_PART
6500 gives an equivalent for the entire destination register,
6501 not just for the subreg being stored in now.
6502 This is a more interesting equivalence, so we arrange later
6503 to treat the entire reg as the destination. */
6504 sets
[i
].src_elt
= src_eqv_elt
;
6505 sets
[i
].src_hash_code
= src_eqv_hash_code
;
6509 /* Insert source and constant equivalent into hash table, if not
6511 register struct table_elt
*classp
= src_eqv_elt
;
6512 register rtx src
= sets
[i
].src
;
6513 register rtx dest
= SET_DEST (sets
[i
].rtl
);
6514 enum machine_mode mode
6515 = GET_MODE (src
) == VOIDmode
? GET_MODE (dest
) : GET_MODE (src
);
6517 if (sets
[i
].src_elt
== 0)
6519 register struct table_elt
*elt
;
6521 /* Note that these insert_regs calls cannot remove
6522 any of the src_elt's, because they would have failed to
6523 match if not still valid. */
6524 if (insert_regs (src
, classp
, 0))
6525 sets
[i
].src_hash_code
= HASH (src
, mode
);
6526 elt
= insert (src
, classp
, sets
[i
].src_hash_code
, mode
);
6527 elt
->in_memory
= sets
[i
].src_in_memory
;
6528 elt
->in_struct
= sets
[i
].src_in_struct
;
6529 sets
[i
].src_elt
= classp
= elt
;
6532 if (sets
[i
].src_const
&& sets
[i
].src_const_elt
== 0
6533 && src
!= sets
[i
].src_const
6534 && ! rtx_equal_p (sets
[i
].src_const
, src
))
6535 sets
[i
].src_elt
= insert (sets
[i
].src_const
, classp
,
6536 sets
[i
].src_const_hash_code
, mode
);
6539 else if (sets
[i
].src_elt
== 0)
6540 /* If we did not insert the source into the hash table (e.g., it was
6541 volatile), note the equivalence class for the REG_EQUAL value, if any,
6542 so that the destination goes into that class. */
6543 sets
[i
].src_elt
= src_eqv_elt
;
6545 invalidate_from_clobbers (&writes_memory
, x
);
6547 /* Some registers are invalidated by subroutine calls. Memory is
6548 invalidated by non-constant calls. */
6550 if (GET_CODE (insn
) == CALL_INSN
)
6552 static struct write_data everything
= {0, 1, 1, 1};
6554 if (! CONST_CALL_P (insn
))
6555 invalidate_memory (&everything
);
6556 invalidate_for_call ();
6559 /* Now invalidate everything set by this instruction.
6560 If a SUBREG or other funny destination is being set,
6561 sets[i].rtl is still nonzero, so here we invalidate the reg
6562 a part of which is being set. */
6564 for (i
= 0; i
< n_sets
; i
++)
6567 register rtx dest
= sets
[i
].inner_dest
;
6569 /* Needed for registers to remove the register from its
6570 previous quantity's chain.
6571 Needed for memory if this is a nonvarying address, unless
6572 we have just done an invalidate_memory that covers even those. */
6573 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
6574 || (! writes_memory
.all
&& ! cse_rtx_addr_varies_p (dest
)))
6578 /* Make sure registers mentioned in destinations
6579 are safe for use in an expression to be inserted.
6580 This removes from the hash table
6581 any invalid entry that refers to one of these registers.
6583 We don't care about the return value from mention_regs because
6584 we are going to hash the SET_DEST values unconditionally. */
6586 for (i
= 0; i
< n_sets
; i
++)
6587 if (sets
[i
].rtl
&& GET_CODE (SET_DEST (sets
[i
].rtl
)) != REG
)
6588 mention_regs (SET_DEST (sets
[i
].rtl
));
6590 /* We may have just removed some of the src_elt's from the hash table.
6591 So replace each one with the current head of the same class. */
6593 for (i
= 0; i
< n_sets
; i
++)
6596 if (sets
[i
].src_elt
&& sets
[i
].src_elt
->first_same_value
== 0)
6597 /* If elt was removed, find current head of same class,
6598 or 0 if nothing remains of that class. */
6600 register struct table_elt
*elt
= sets
[i
].src_elt
;
6602 while (elt
&& elt
->prev_same_value
)
6603 elt
= elt
->prev_same_value
;
6605 while (elt
&& elt
->first_same_value
== 0)
6606 elt
= elt
->next_same_value
;
6607 sets
[i
].src_elt
= elt
? elt
->first_same_value
: 0;
6611 /* Now insert the destinations into their equivalence classes. */
6613 for (i
= 0; i
< n_sets
; i
++)
6616 register rtx dest
= SET_DEST (sets
[i
].rtl
);
6617 register struct table_elt
*elt
;
6619 /* Don't record value if we are not supposed to risk allocating
6620 floating-point values in registers that might be wider than
6622 if ((flag_float_store
6623 && GET_CODE (dest
) == MEM
6624 && GET_MODE_CLASS (GET_MODE (dest
)) == MODE_FLOAT
)
6625 /* Don't record values of destinations set inside a libcall block
6626 since we might delete the libcall. Things should have been set
6627 up so we won't want to reuse such a value, but we play it safe
6630 /* If we didn't put a REG_EQUAL value or a source into the hash
6631 table, there is no point is recording DEST. */
6632 || sets
[i
].src_elt
== 0)
6635 /* STRICT_LOW_PART isn't part of the value BEING set,
6636 and neither is the SUBREG inside it.
6637 Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT. */
6638 if (GET_CODE (dest
) == STRICT_LOW_PART
)
6639 dest
= SUBREG_REG (XEXP (dest
, 0));
6641 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
)
6642 /* Registers must also be inserted into chains for quantities. */
6643 if (insert_regs (dest
, sets
[i
].src_elt
, 1))
6644 /* If `insert_regs' changes something, the hash code must be
6646 sets
[i
].dest_hash_code
= HASH (dest
, GET_MODE (dest
));
6648 elt
= insert (dest
, sets
[i
].src_elt
,
6649 sets
[i
].dest_hash_code
, GET_MODE (dest
));
6650 elt
->in_memory
= GET_CODE (sets
[i
].inner_dest
) == MEM
;
6653 /* This implicitly assumes a whole struct
6654 need not have MEM_IN_STRUCT_P.
6655 But a whole struct is *supposed* to have MEM_IN_STRUCT_P. */
6656 elt
->in_struct
= (MEM_IN_STRUCT_P (sets
[i
].inner_dest
)
6657 || sets
[i
].inner_dest
!= SET_DEST (sets
[i
].rtl
));
6660 /* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is no
6661 narrower than M2, and both M1 and M2 are the same number of words,
6662 we are also doing (set (reg:m2 foo) (subreg:m2 (bar:m1) 0)) so
6663 make that equivalence as well.
6665 However, BAR may have equivalences for which gen_lowpart_if_possible
6666 will produce a simpler value than gen_lowpart_if_possible applied to
6667 BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
6668 BAR's equivalences. If we don't get a simplified form, make
6669 the SUBREG. It will not be used in an equivalence, but will
6670 cause two similar assignments to be detected.
6672 Note the loop below will find SUBREG_REG (DEST) since we have
6673 already entered SRC and DEST of the SET in the table. */
6675 if (GET_CODE (dest
) == SUBREG
6676 && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))) / UNITS_PER_WORD
6677 == GET_MODE_SIZE (GET_MODE (dest
)) / UNITS_PER_WORD
)
6678 && (GET_MODE_SIZE (GET_MODE (dest
))
6679 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
6680 && sets
[i
].src_elt
!= 0)
6682 enum machine_mode new_mode
= GET_MODE (SUBREG_REG (dest
));
6683 struct table_elt
*elt
, *classp
= 0;
6685 for (elt
= sets
[i
].src_elt
->first_same_value
; elt
;
6686 elt
= elt
->next_same_value
)
6690 struct table_elt
*src_elt
;
6692 /* Ignore invalid entries. */
6693 if (GET_CODE (elt
->exp
) != REG
6694 && ! exp_equiv_p (elt
->exp
, elt
->exp
, 1, 0))
6697 new_src
= gen_lowpart_if_possible (new_mode
, elt
->exp
);
6699 new_src
= gen_rtx (SUBREG
, new_mode
, elt
->exp
, 0);
6701 src_hash
= HASH (new_src
, new_mode
);
6702 src_elt
= lookup (new_src
, src_hash
, new_mode
);
6704 /* Put the new source in the hash table is if isn't
6708 if (insert_regs (new_src
, classp
, 0))
6709 src_hash
= HASH (new_src
, new_mode
);
6710 src_elt
= insert (new_src
, classp
, src_hash
, new_mode
);
6711 src_elt
->in_memory
= elt
->in_memory
;
6712 src_elt
->in_struct
= elt
->in_struct
;
6714 else if (classp
&& classp
!= src_elt
->first_same_value
)
6715 /* Show that two things that we've seen before are
6716 actually the same. */
6717 merge_equiv_classes (src_elt
, classp
);
6719 classp
= src_elt
->first_same_value
;
6724 /* Special handling for (set REG0 REG1)
6725 where REG0 is the "cheapest", cheaper than REG1.
6726 After cse, REG1 will probably not be used in the sequel,
6727 so (if easily done) change this insn to (set REG1 REG0) and
6728 replace REG1 with REG0 in the previous insn that computed their value.
6729 Then REG1 will become a dead store and won't cloud the situation
6730 for later optimizations.
6732 Do not make this change if REG1 is a hard register, because it will
6733 then be used in the sequel and we may be changing a two-operand insn
6734 into a three-operand insn.
6736 Also do not do this if we are operating on a copy of INSN. */
6738 if (n_sets
== 1 && sets
[0].rtl
&& GET_CODE (SET_DEST (sets
[0].rtl
)) == REG
6739 && NEXT_INSN (PREV_INSN (insn
)) == insn
6740 && GET_CODE (SET_SRC (sets
[0].rtl
)) == REG
6741 && REGNO (SET_SRC (sets
[0].rtl
)) >= FIRST_PSEUDO_REGISTER
6742 && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets
[0].rtl
)))
6743 && (qty_first_reg
[reg_qty
[REGNO (SET_SRC (sets
[0].rtl
))]]
6744 == REGNO (SET_DEST (sets
[0].rtl
))))
6746 rtx prev
= PREV_INSN (insn
);
6747 while (prev
&& GET_CODE (prev
) == NOTE
)
6748 prev
= PREV_INSN (prev
);
6750 if (prev
&& GET_CODE (prev
) == INSN
&& GET_CODE (PATTERN (prev
)) == SET
6751 && SET_DEST (PATTERN (prev
)) == SET_SRC (sets
[0].rtl
))
6753 rtx dest
= SET_DEST (sets
[0].rtl
);
6754 rtx note
= find_reg_note (prev
, REG_EQUIV
, NULL_RTX
);
6756 validate_change (prev
, & SET_DEST (PATTERN (prev
)), dest
, 1);
6757 validate_change (insn
, & SET_DEST (sets
[0].rtl
),
6758 SET_SRC (sets
[0].rtl
), 1);
6759 validate_change (insn
, & SET_SRC (sets
[0].rtl
), dest
, 1);
6760 apply_change_group ();
6762 /* If REG1 was equivalent to a constant, REG0 is not. */
6764 PUT_REG_NOTE_KIND (note
, REG_EQUAL
);
6766 /* If there was a REG_WAS_0 note on PREV, remove it. Move
6767 any REG_WAS_0 note on INSN to PREV. */
6768 note
= find_reg_note (prev
, REG_WAS_0
, NULL_RTX
);
6770 remove_note (prev
, note
);
6772 note
= find_reg_note (insn
, REG_WAS_0
, NULL_RTX
);
6775 remove_note (insn
, note
);
6776 XEXP (note
, 1) = REG_NOTES (prev
);
6777 REG_NOTES (prev
) = note
;
6782 /* If this is a conditional jump insn, record any known equivalences due to
6783 the condition being tested. */
6785 last_jump_equiv_class
= 0;
6786 if (GET_CODE (insn
) == JUMP_INSN
6787 && n_sets
== 1 && GET_CODE (x
) == SET
6788 && GET_CODE (SET_SRC (x
)) == IF_THEN_ELSE
)
6789 record_jump_equiv (insn
, 0);
6792 /* If the previous insn set CC0 and this insn no longer references CC0,
6793 delete the previous insn. Here we use the fact that nothing expects CC0
6794 to be valid over an insn, which is true until the final pass. */
6795 if (prev_insn
&& GET_CODE (prev_insn
) == INSN
6796 && (tem
= single_set (prev_insn
)) != 0
6797 && SET_DEST (tem
) == cc0_rtx
6798 && ! reg_mentioned_p (cc0_rtx
, x
))
6800 PUT_CODE (prev_insn
, NOTE
);
6801 NOTE_LINE_NUMBER (prev_insn
) = NOTE_INSN_DELETED
;
6802 NOTE_SOURCE_FILE (prev_insn
) = 0;
6805 prev_insn_cc0
= this_insn_cc0
;
6806 prev_insn_cc0_mode
= this_insn_cc0_mode
;
6812 /* Store 1 in *WRITES_PTR for those categories of memory ref
6813 that must be invalidated when the expression WRITTEN is stored in.
6814 If WRITTEN is null, say everything must be invalidated. */
6817 note_mem_written (written
, writes_ptr
)
6819 struct write_data
*writes_ptr
;
6821 static struct write_data everything
= {0, 1, 1, 1};
6824 *writes_ptr
= everything
;
6825 else if (GET_CODE (written
) == MEM
)
6827 /* Pushing or popping the stack invalidates just the stack pointer. */
6828 rtx addr
= XEXP (written
, 0);
6829 if ((GET_CODE (addr
) == PRE_DEC
|| GET_CODE (addr
) == PRE_INC
6830 || GET_CODE (addr
) == POST_DEC
|| GET_CODE (addr
) == POST_INC
)
6831 && GET_CODE (XEXP (addr
, 0)) == REG
6832 && REGNO (XEXP (addr
, 0)) == STACK_POINTER_REGNUM
)
6837 else if (GET_MODE (written
) == BLKmode
)
6838 *writes_ptr
= everything
;
6839 else if (cse_rtx_addr_varies_p (written
))
6841 /* A varying address that is a sum indicates an array element,
6842 and that's just as good as a structure element
6843 in implying that we need not invalidate scalar variables. */
6844 if (!(MEM_IN_STRUCT_P (written
)
6845 || GET_CODE (XEXP (written
, 0)) == PLUS
))
6846 writes_ptr
->all
= 1;
6847 writes_ptr
->nonscalar
= 1;
6849 writes_ptr
->var
= 1;
6853 /* Perform invalidation on the basis of everything about an insn
6854 except for invalidating the actual places that are SET in it.
6855 This includes the places CLOBBERed, and anything that might
6856 alias with something that is SET or CLOBBERed.
6858 W points to the writes_memory for this insn, a struct write_data
6859 saying which kinds of memory references must be invalidated.
6860 X is the pattern of the insn. */
6863 invalidate_from_clobbers (w
, x
)
6864 struct write_data
*w
;
6867 /* If W->var is not set, W specifies no action.
6868 If W->all is set, this step gets all memory refs
6869 so they can be ignored in the rest of this function. */
6871 invalidate_memory (w
);
6875 if (reg_tick
[STACK_POINTER_REGNUM
] >= 0)
6876 reg_tick
[STACK_POINTER_REGNUM
]++;
6878 /* This should be *very* rare. */
6879 if (TEST_HARD_REG_BIT (hard_regs_in_table
, STACK_POINTER_REGNUM
))
6880 invalidate (stack_pointer_rtx
);
6883 if (GET_CODE (x
) == CLOBBER
)
6885 rtx ref
= XEXP (x
, 0);
6887 && (GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6888 || (GET_CODE (ref
) == MEM
&& ! w
->all
)))
6891 else if (GET_CODE (x
) == PARALLEL
)
6894 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
6896 register rtx y
= XVECEXP (x
, 0, i
);
6897 if (GET_CODE (y
) == CLOBBER
)
6899 rtx ref
= XEXP (y
, 0);
6901 &&(GET_CODE (ref
) == REG
|| GET_CODE (ref
) == SUBREG
6902 || (GET_CODE (ref
) == MEM
&& !w
->all
)))
6909 /* Process X, part of the REG_NOTES of an insn. Look at any REG_EQUAL notes
6910 and replace any registers in them with either an equivalent constant
6911 or the canonical form of the register. If we are inside an address,
6912 only do this if the address remains valid.
6914 OBJECT is 0 except when within a MEM in which case it is the MEM.
6916 Return the replacement for X. */
6919 cse_process_notes (x
, object
)
6923 enum rtx_code code
= GET_CODE (x
);
6924 char *fmt
= GET_RTX_FORMAT (code
);
6941 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), x
);
6946 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
6947 XEXP (x
, 0) = cse_process_notes (XEXP (x
, 0), NULL_RTX
);
6949 XEXP (x
, 1) = cse_process_notes (XEXP (x
, 1), NULL_RTX
);
6955 rtx
new = cse_process_notes (XEXP (x
, 0), object
);
6956 /* We don't substitute VOIDmode constants into these rtx,
6957 since they would impede folding. */
6958 if (GET_MODE (new) != VOIDmode
)
6959 validate_change (object
, &XEXP (x
, 0), new, 0);
6964 i
= reg_qty
[REGNO (x
)];
6966 /* Return a constant or a constant register. */
6967 if (REGNO_QTY_VALID_P (REGNO (x
))
6968 && qty_const
[i
] != 0
6969 && (CONSTANT_P (qty_const
[i
])
6970 || GET_CODE (qty_const
[i
]) == REG
))
6972 rtx
new = gen_lowpart_if_possible (GET_MODE (x
), qty_const
[i
]);
6977 /* Otherwise, canonicalize this register. */
6978 return canon_reg (x
, NULL_RTX
);
6981 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
6983 validate_change (object
, &XEXP (x
, i
),
6984 cse_process_notes (XEXP (x
, i
), object
), NULL_RTX
);
6989 /* Find common subexpressions between the end test of a loop and the beginning
6990 of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
6992 Often we have a loop where an expression in the exit test is used
6993 in the body of the loop. For example "while (*p) *q++ = *p++;".
6994 Because of the way we duplicate the loop exit test in front of the loop,
6995 however, we don't detect that common subexpression. This will be caught
6996 when global cse is implemented, but this is a quite common case.
6998 This function handles the most common cases of these common expressions.
6999 It is called after we have processed the basic block ending with the
7000 NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
7001 jumps to a label used only once. */
7004 cse_around_loop (loop_start
)
7009 struct table_elt
*p
;
7011 /* If the jump at the end of the loop doesn't go to the start, we don't
7013 for (insn
= PREV_INSN (loop_start
);
7014 insn
&& (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) >= 0);
7015 insn
= PREV_INSN (insn
))
7019 || GET_CODE (insn
) != NOTE
7020 || NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
)
7023 /* If the last insn of the loop (the end test) was an NE comparison,
7024 we will interpret it as an EQ comparison, since we fell through
7025 the loop. Any equivalences resulting from that comparison are
7026 therefore not valid and must be invalidated. */
7027 if (last_jump_equiv_class
)
7028 for (p
= last_jump_equiv_class
->first_same_value
; p
;
7029 p
= p
->next_same_value
)
7030 if (GET_CODE (p
->exp
) == MEM
|| GET_CODE (p
->exp
) == REG
7031 || GET_CODE (p
->exp
) == SUBREG
)
7032 invalidate (p
->exp
);
7034 /* Process insns starting after LOOP_START until we hit a CALL_INSN or
7035 a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
7037 The only thing we do with SET_DEST is invalidate entries, so we
7038 can safely process each SET in order. It is slightly less efficient
7039 to do so, but we only want to handle the most common cases. */
7041 for (insn
= NEXT_INSN (loop_start
);
7042 GET_CODE (insn
) != CALL_INSN
&& GET_CODE (insn
) != CODE_LABEL
7043 && ! (GET_CODE (insn
) == NOTE
7044 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
);
7045 insn
= NEXT_INSN (insn
))
7047 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7048 && (GET_CODE (PATTERN (insn
)) == SET
7049 || GET_CODE (PATTERN (insn
)) == CLOBBER
))
7050 cse_set_around_loop (PATTERN (insn
), insn
, loop_start
);
7051 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7052 && GET_CODE (PATTERN (insn
)) == PARALLEL
)
7053 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
7054 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == SET
7055 || GET_CODE (XVECEXP (PATTERN (insn
), 0, i
)) == CLOBBER
)
7056 cse_set_around_loop (XVECEXP (PATTERN (insn
), 0, i
), insn
,
7061 /* Variable used for communications between the next two routines. */
7063 static struct write_data skipped_writes_memory
;
7065 /* Process one SET of an insn that was skipped. We ignore CLOBBERs
7066 since they are done elsewhere. This function is called via note_stores. */
7069 invalidate_skipped_set (dest
, set
)
7073 if (GET_CODE (set
) == CLOBBER
7080 if (GET_CODE (dest
) == MEM
)
7081 note_mem_written (dest
, &skipped_writes_memory
);
7083 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == SUBREG
7084 || (! skipped_writes_memory
.all
&& ! cse_rtx_addr_varies_p (dest
)))
7088 /* Invalidate all insns from START up to the end of the function or the
7089 next label. This called when we wish to CSE around a block that is
7090 conditionally executed. */
7093 invalidate_skipped_block (start
)
7098 static struct write_data init
= {0, 0, 0, 0};
7099 static struct write_data everything
= {0, 1, 1, 1};
7101 for (insn
= start
; insn
&& GET_CODE (insn
) != CODE_LABEL
;
7102 insn
= NEXT_INSN (insn
))
7104 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7107 skipped_writes_memory
= init
;
7109 if (GET_CODE (insn
) == CALL_INSN
)
7111 invalidate_for_call ();
7112 skipped_writes_memory
= everything
;
7115 note_stores (PATTERN (insn
), invalidate_skipped_set
);
7116 invalidate_from_clobbers (&skipped_writes_memory
, PATTERN (insn
));
7120 /* Used for communication between the following two routines; contains a
7121 value to be checked for modification. */
7123 static rtx cse_check_loop_start_value
;
7125 /* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE,
7126 indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0. */
7129 cse_check_loop_start (x
, set
)
7133 if (cse_check_loop_start_value
== 0
7134 || GET_CODE (x
) == CC0
|| GET_CODE (x
) == PC
)
7137 if ((GET_CODE (x
) == MEM
&& GET_CODE (cse_check_loop_start_value
) == MEM
)
7138 || reg_overlap_mentioned_p (x
, cse_check_loop_start_value
))
7139 cse_check_loop_start_value
= 0;
7142 /* X is a SET or CLOBBER contained in INSN that was found near the start of
7143 a loop that starts with the label at LOOP_START.
7145 If X is a SET, we see if its SET_SRC is currently in our hash table.
7146 If so, we see if it has a value equal to some register used only in the
7147 loop exit code (as marked by jump.c).
7149 If those two conditions are true, we search backwards from the start of
7150 the loop to see if that same value was loaded into a register that still
7151 retains its value at the start of the loop.
7153 If so, we insert an insn after the load to copy the destination of that
7154 load into the equivalent register and (try to) replace our SET_SRC with that
7157 In any event, we invalidate whatever this SET or CLOBBER modifies. */
7160 cse_set_around_loop (x
, insn
, loop_start
)
7166 struct table_elt
*src_elt
;
7167 static struct write_data init
= {0, 0, 0, 0};
7168 struct write_data writes_memory
;
7170 writes_memory
= init
;
7172 /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
7173 are setting PC or CC0 or whose SET_SRC is already a register. */
7174 if (GET_CODE (x
) == SET
7175 && GET_CODE (SET_DEST (x
)) != PC
&& GET_CODE (SET_DEST (x
)) != CC0
7176 && GET_CODE (SET_SRC (x
)) != REG
)
7178 src_elt
= lookup (SET_SRC (x
),
7179 HASH (SET_SRC (x
), GET_MODE (SET_DEST (x
))),
7180 GET_MODE (SET_DEST (x
)));
7183 for (src_elt
= src_elt
->first_same_value
; src_elt
;
7184 src_elt
= src_elt
->next_same_value
)
7185 if (GET_CODE (src_elt
->exp
) == REG
&& REG_LOOP_TEST_P (src_elt
->exp
)
7186 && COST (src_elt
->exp
) < COST (SET_SRC (x
)))
7190 /* Look for an insn in front of LOOP_START that sets
7191 something in the desired mode to SET_SRC (x) before we hit
7192 a label or CALL_INSN. */
7194 for (p
= prev_nonnote_insn (loop_start
);
7195 p
&& GET_CODE (p
) != CALL_INSN
7196 && GET_CODE (p
) != CODE_LABEL
;
7197 p
= prev_nonnote_insn (p
))
7198 if ((set
= single_set (p
)) != 0
7199 && GET_CODE (SET_DEST (set
)) == REG
7200 && GET_MODE (SET_DEST (set
)) == src_elt
->mode
7201 && rtx_equal_p (SET_SRC (set
), SET_SRC (x
)))
7203 /* We now have to ensure that nothing between P
7204 and LOOP_START modified anything referenced in
7205 SET_SRC (x). We know that nothing within the loop
7206 can modify it, or we would have invalidated it in
7210 cse_check_loop_start_value
= SET_SRC (x
);
7211 for (q
= p
; q
!= loop_start
; q
= NEXT_INSN (q
))
7212 if (GET_RTX_CLASS (GET_CODE (q
)) == 'i')
7213 note_stores (PATTERN (q
), cse_check_loop_start
);
7215 /* If nothing was changed and we can replace our
7216 SET_SRC, add an insn after P to copy its destination
7217 to what we will be replacing SET_SRC with. */
7218 if (cse_check_loop_start_value
7219 && validate_change (insn
, &SET_SRC (x
),
7221 emit_insn_after (gen_move_insn (src_elt
->exp
,
7229 /* Now invalidate anything modified by X. */
7230 note_mem_written (SET_DEST (x
), &writes_memory
);
7232 if (writes_memory
.var
)
7233 invalidate_memory (&writes_memory
);
7235 /* See comment on similar code in cse_insn for explanation of these tests. */
7236 if (GET_CODE (SET_DEST (x
)) == REG
|| GET_CODE (SET_DEST (x
)) == SUBREG
7237 || (GET_CODE (SET_DEST (x
)) == MEM
&& ! writes_memory
.all
7238 && ! cse_rtx_addr_varies_p (SET_DEST (x
))))
7239 invalidate (SET_DEST (x
));
7242 /* Find the end of INSN's basic block and return its range,
7243 the total number of SETs in all the insns of the block, the last insn of the
7244 block, and the branch path.
7246 The branch path indicates which branches should be followed. If a non-zero
7247 path size is specified, the block should be rescanned and a different set
7248 of branches will be taken. The branch path is only used if
7249 FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
7251 DATA is a pointer to a struct cse_basic_block_data, defined below, that is
7252 used to describe the block. It is filled in with the information about
7253 the current block. The incoming structure's branch path, if any, is used
7254 to construct the output branch path. */
7256 /* Define maximum length of a branch path. */
7258 #define PATHLENGTH 20
7260 struct cse_basic_block_data
{
7261 /* Lowest CUID value of insns in block. */
7263 /* Highest CUID value of insns in block. */
7265 /* Total number of SETs in block. */
7267 /* Last insn in the block. */
7269 /* Size of current branch path, if any. */
7271 /* Current branch path, indicating which branches will be taken. */
7272 struct branch_path
{
7273 /* The branch insn. */
7275 /* Whether it should be taken or not. AROUND is the same as taken
7276 except that it is used when the destination label is not preceded
7278 enum taken
{TAKEN
, NOT_TAKEN
, AROUND
} status
;
7283 cse_end_of_basic_block (insn
, data
, follow_jumps
, after_loop
, skip_blocks
)
7285 struct cse_basic_block_data
*data
;
7292 int low_cuid
= INSN_CUID (insn
), high_cuid
= INSN_CUID (insn
);
7293 rtx next
= GET_RTX_CLASS (GET_CODE (insn
)) == 'i' ? insn
: next_real_insn (insn
);
7294 int path_size
= data
->path_size
;
7298 /* Update the previous branch path, if any. If the last branch was
7299 previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
7300 shorten the path by one and look at the previous branch. We know that
7301 at least one branch must have been taken if PATH_SIZE is non-zero. */
7302 while (path_size
> 0)
7304 if (data
->path
[path_size
- 1].status
!= NOT_TAKEN
)
7306 data
->path
[path_size
- 1].status
= NOT_TAKEN
;
7313 /* Scan to end of this basic block. */
7314 while (p
&& GET_CODE (p
) != CODE_LABEL
)
7316 /* Don't cse out the end of a loop. This makes a difference
7317 only for the unusual loops that always execute at least once;
7318 all other loops have labels there so we will stop in any case.
7319 Cse'ing out the end of the loop is dangerous because it
7320 might cause an invariant expression inside the loop
7321 to be reused after the end of the loop. This would make it
7322 hard to move the expression out of the loop in loop.c,
7323 especially if it is one of several equivalent expressions
7324 and loop.c would like to eliminate it.
7326 If we are running after loop.c has finished, we can ignore
7327 the NOTE_INSN_LOOP_END. */
7329 if (! after_loop
&& GET_CODE (p
) == NOTE
7330 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_LOOP_END
)
7333 /* Don't cse over a call to setjmp; on some machines (eg vax)
7334 the regs restored by the longjmp come from
7335 a later time than the setjmp. */
7336 if (GET_CODE (p
) == NOTE
7337 && NOTE_LINE_NUMBER (p
) == NOTE_INSN_SETJMP
)
7340 /* A PARALLEL can have lots of SETs in it,
7341 especially if it is really an ASM_OPERANDS. */
7342 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i'
7343 && GET_CODE (PATTERN (p
)) == PARALLEL
)
7344 nsets
+= XVECLEN (PATTERN (p
), 0);
7345 else if (GET_CODE (p
) != NOTE
)
7348 if (INSN_CUID (p
) > high_cuid
)
7349 high_cuid
= INSN_CUID (p
);
7350 if (INSN_CUID (p
) < low_cuid
)
7351 low_cuid
= INSN_CUID(p
);
7353 /* See if this insn is in our branch path. If it is and we are to
7355 if (path_entry
< path_size
&& data
->path
[path_entry
].branch
== p
)
7357 if (data
->path
[path_entry
].status
!= NOT_TAKEN
)
7360 /* Point to next entry in path, if any. */
7364 /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
7365 was specified, we haven't reached our maximum path length, there are
7366 insns following the target of the jump, this is the only use of the
7367 jump label, and the target label is preceded by a BARRIER.
7369 Alternatively, we can follow the jump if it branches around a
7370 block of code and there are no other branches into the block.
7371 In this case invalidate_skipped_block will be called to invalidate any
7372 registers set in the block when following the jump. */
7374 else if ((follow_jumps
|| skip_blocks
) && path_size
< PATHLENGTH
- 1
7375 && GET_CODE (p
) == JUMP_INSN
7376 && GET_CODE (PATTERN (p
)) == SET
7377 && GET_CODE (SET_SRC (PATTERN (p
))) == IF_THEN_ELSE
7378 && LABEL_NUSES (JUMP_LABEL (p
)) == 1
7379 && NEXT_INSN (JUMP_LABEL (p
)) != 0)
7381 for (q
= PREV_INSN (JUMP_LABEL (p
)); q
; q
= PREV_INSN (q
))
7382 if ((GET_CODE (q
) != NOTE
7383 || NOTE_LINE_NUMBER (q
) == NOTE_INSN_LOOP_END
7384 || NOTE_LINE_NUMBER (q
) == NOTE_INSN_SETJMP
)
7385 && (GET_CODE (q
) != CODE_LABEL
|| LABEL_NUSES (q
) != 0))
7388 /* If we ran into a BARRIER, this code is an extension of the
7389 basic block when the branch is taken. */
7390 if (follow_jumps
&& q
!= 0 && GET_CODE (q
) == BARRIER
)
7392 /* Don't allow ourself to keep walking around an
7393 always-executed loop. */
7394 if (next_real_insn (q
) == next
)
7400 /* Similarly, don't put a branch in our path more than once. */
7401 for (i
= 0; i
< path_entry
; i
++)
7402 if (data
->path
[i
].branch
== p
)
7405 if (i
!= path_entry
)
7408 data
->path
[path_entry
].branch
= p
;
7409 data
->path
[path_entry
++].status
= TAKEN
;
7411 /* This branch now ends our path. It was possible that we
7412 didn't see this branch the last time around (when the
7413 insn in front of the target was a JUMP_INSN that was
7414 turned into a no-op). */
7415 path_size
= path_entry
;
7418 /* Mark block so we won't scan it again later. */
7419 PUT_MODE (NEXT_INSN (p
), QImode
);
7421 /* Detect a branch around a block of code. */
7422 else if (skip_blocks
&& q
!= 0 && GET_CODE (q
) != CODE_LABEL
)
7426 if (next_real_insn (q
) == next
)
7432 for (i
= 0; i
< path_entry
; i
++)
7433 if (data
->path
[i
].branch
== p
)
7436 if (i
!= path_entry
)
7439 /* This is no_labels_between_p (p, q) with an added check for
7440 reaching the end of a function (in case Q precedes P). */
7441 for (tmp
= NEXT_INSN (p
); tmp
&& tmp
!= q
; tmp
= NEXT_INSN (tmp
))
7442 if (GET_CODE (tmp
) == CODE_LABEL
)
7447 data
->path
[path_entry
].branch
= p
;
7448 data
->path
[path_entry
++].status
= AROUND
;
7450 path_size
= path_entry
;
7453 /* Mark block so we won't scan it again later. */
7454 PUT_MODE (NEXT_INSN (p
), QImode
);
7461 data
->low_cuid
= low_cuid
;
7462 data
->high_cuid
= high_cuid
;
7463 data
->nsets
= nsets
;
7466 /* If all jumps in the path are not taken, set our path length to zero
7467 so a rescan won't be done. */
7468 for (i
= path_size
- 1; i
>= 0; i
--)
7469 if (data
->path
[i
].status
!= NOT_TAKEN
)
7473 data
->path_size
= 0;
7475 data
->path_size
= path_size
;
7477 /* End the current branch path. */
7478 data
->path
[path_size
].branch
= 0;
7481 static rtx
cse_basic_block ();
7483 /* Perform cse on the instructions of a function.
7484 F is the first instruction.
7485 NREGS is one plus the highest pseudo-reg number used in the instruction.
7487 AFTER_LOOP is 1 if this is the cse call done after loop optimization
7488 (only if -frerun-cse-after-loop).
7490 Returns 1 if jump_optimize should be redone due to simplifications
7491 in conditional jump instructions. */
7494 cse_main (f
, nregs
, after_loop
, file
)
7500 struct cse_basic_block_data val
;
7501 register rtx insn
= f
;
7504 cse_jumps_altered
= 0;
7505 constant_pool_entries_cost
= 0;
7512 all_minus_one
= (int *) alloca (nregs
* sizeof (int));
7513 consec_ints
= (int *) alloca (nregs
* sizeof (int));
7515 for (i
= 0; i
< nregs
; i
++)
7517 all_minus_one
[i
] = -1;
7521 reg_next_eqv
= (int *) alloca (nregs
* sizeof (int));
7522 reg_prev_eqv
= (int *) alloca (nregs
* sizeof (int));
7523 reg_qty
= (int *) alloca (nregs
* sizeof (int));
7524 reg_in_table
= (int *) alloca (nregs
* sizeof (int));
7525 reg_tick
= (int *) alloca (nregs
* sizeof (int));
7527 /* Discard all the free elements of the previous function
7528 since they are allocated in the temporarily obstack. */
7529 bzero (table
, sizeof table
);
7530 free_element_chain
= 0;
7531 n_elements_made
= 0;
7533 /* Find the largest uid. */
7536 uid_cuid
= (int *) alloca ((i
+ 1) * sizeof (int));
7537 bzero (uid_cuid
, (i
+ 1) * sizeof (int));
7539 /* Compute the mapping from uids to cuids.
7540 CUIDs are numbers assigned to insns, like uids,
7541 except that cuids increase monotonically through the code.
7542 Don't assign cuids to line-number NOTEs, so that the distance in cuids
7543 between two insns is not affected by -g. */
7545 for (insn
= f
, i
= 0; insn
; insn
= NEXT_INSN (insn
))
7547 if (GET_CODE (insn
) != NOTE
7548 || NOTE_LINE_NUMBER (insn
) < 0)
7549 INSN_CUID (insn
) = ++i
;
7551 /* Give a line number note the same cuid as preceding insn. */
7552 INSN_CUID (insn
) = i
;
7555 /* Initialize which registers are clobbered by calls. */
7557 CLEAR_HARD_REG_SET (regs_invalidated_by_call
);
7559 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
7560 if ((call_used_regs
[i
]
7561 /* Used to check !fixed_regs[i] here, but that isn't safe;
7562 fixed regs are still call-clobbered, and sched can get
7563 confused if they can "live across calls".
7565 The frame pointer is always preserved across calls. The arg
7566 pointer is if it is fixed. The stack pointer usually is, unless
7567 RETURN_POPS_ARGS, in which case an explicit CLOBBER
7568 will be present. If we are generating PIC code, the PIC offset
7569 table register is preserved across calls. */
7571 && i
!= STACK_POINTER_REGNUM
7572 && i
!= FRAME_POINTER_REGNUM
7573 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
7574 && ! (i
== ARG_POINTER_REGNUM
&& fixed_regs
[i
])
7576 #ifdef PIC_OFFSET_TABLE_REGNUM
7577 && ! (i
== PIC_OFFSET_TABLE_REGNUM
&& flag_pic
)
7581 SET_HARD_REG_BIT (regs_invalidated_by_call
, i
);
7583 /* Loop over basic blocks.
7584 Compute the maximum number of qty's needed for each basic block
7585 (which is 2 for each SET). */
7589 cse_end_of_basic_block (insn
, &val
, flag_cse_follow_jumps
, after_loop
,
7590 flag_cse_skip_blocks
);
7592 /* If this basic block was already processed or has no sets, skip it. */
7593 if (val
.nsets
== 0 || GET_MODE (insn
) == QImode
)
7595 PUT_MODE (insn
, VOIDmode
);
7596 insn
= (val
.last
? NEXT_INSN (val
.last
) : 0);
7601 cse_basic_block_start
= val
.low_cuid
;
7602 cse_basic_block_end
= val
.high_cuid
;
7603 max_qty
= val
.nsets
* 2;
7606 fprintf (file
, ";; Processing block from %d to %d, %d sets.\n",
7607 INSN_UID (insn
), val
.last
? INSN_UID (val
.last
) : 0,
7610 /* Make MAX_QTY bigger to give us room to optimize
7611 past the end of this basic block, if that should prove useful. */
7617 /* If this basic block is being extended by following certain jumps,
7618 (see `cse_end_of_basic_block'), we reprocess the code from the start.
7619 Otherwise, we start after this basic block. */
7620 if (val
.path_size
> 0)
7621 cse_basic_block (insn
, val
.last
, val
.path
, 0);
7624 int old_cse_jumps_altered
= cse_jumps_altered
;
7627 /* When cse changes a conditional jump to an unconditional
7628 jump, we want to reprocess the block, since it will give
7629 us a new branch path to investigate. */
7630 cse_jumps_altered
= 0;
7631 temp
= cse_basic_block (insn
, val
.last
, val
.path
, ! after_loop
);
7632 if (cse_jumps_altered
== 0
7633 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7636 cse_jumps_altered
|= old_cse_jumps_altered
;
7644 /* Tell refers_to_mem_p that qty_const info is not available. */
7647 if (max_elements_made
< n_elements_made
)
7648 max_elements_made
= n_elements_made
;
7650 return cse_jumps_altered
;
7653 /* Process a single basic block. FROM and TO and the limits of the basic
7654 block. NEXT_BRANCH points to the branch path when following jumps or
7655 a null path when not following jumps.
7657 AROUND_LOOP is non-zero if we are to try to cse around to the start of a
7658 loop. This is true when we are being called for the last time on a
7659 block and this CSE pass is before loop.c. */
7662 cse_basic_block (from
, to
, next_branch
, around_loop
)
7663 register rtx from
, to
;
7664 struct branch_path
*next_branch
;
7669 int in_libcall_block
= 0;
7671 /* Each of these arrays is undefined before max_reg, so only allocate
7672 the space actually needed and adjust the start below. */
7674 qty_first_reg
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7675 qty_last_reg
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7676 qty_mode
= (enum machine_mode
*) alloca ((max_qty
- max_reg
) * sizeof (enum machine_mode
));
7677 qty_const
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7678 qty_const_insn
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7680 = (enum rtx_code
*) alloca ((max_qty
- max_reg
) * sizeof (enum rtx_code
));
7681 qty_comparison_qty
= (int *) alloca ((max_qty
- max_reg
) * sizeof (int));
7682 qty_comparison_const
= (rtx
*) alloca ((max_qty
- max_reg
) * sizeof (rtx
));
7684 qty_first_reg
-= max_reg
;
7685 qty_last_reg
-= max_reg
;
7686 qty_mode
-= max_reg
;
7687 qty_const
-= max_reg
;
7688 qty_const_insn
-= max_reg
;
7689 qty_comparison_code
-= max_reg
;
7690 qty_comparison_qty
-= max_reg
;
7691 qty_comparison_const
-= max_reg
;
7695 /* TO might be a label. If so, protect it from being deleted. */
7696 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7699 for (insn
= from
; insn
!= to
; insn
= NEXT_INSN (insn
))
7701 register enum rtx_code code
;
7703 /* See if this is a branch that is part of the path. If so, and it is
7704 to be taken, do so. */
7705 if (next_branch
->branch
== insn
)
7707 enum taken status
= next_branch
++->status
;
7708 if (status
!= NOT_TAKEN
)
7710 if (status
== TAKEN
)
7711 record_jump_equiv (insn
, 1);
7713 invalidate_skipped_block (NEXT_INSN (insn
));
7715 /* Set the last insn as the jump insn; it doesn't affect cc0.
7716 Then follow this branch. */
7721 insn
= JUMP_LABEL (insn
);
7726 code
= GET_CODE (insn
);
7727 if (GET_MODE (insn
) == QImode
)
7728 PUT_MODE (insn
, VOIDmode
);
7730 if (GET_RTX_CLASS (code
) == 'i')
7732 /* Process notes first so we have all notes in canonical forms when
7733 looking for duplicate operations. */
7735 if (REG_NOTES (insn
))
7736 REG_NOTES (insn
) = cse_process_notes (REG_NOTES (insn
), NULL_RTX
);
7738 /* Track when we are inside in LIBCALL block. Inside such a block,
7739 we do not want to record destinations. The last insn of a
7740 LIBCALL block is not considered to be part of the block, since
7741 its destination is the result of the block and hence should be
7744 if (find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))
7745 in_libcall_block
= 1;
7746 else if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
7747 in_libcall_block
= 0;
7749 cse_insn (insn
, in_libcall_block
);
7752 /* If INSN is now an unconditional jump, skip to the end of our
7753 basic block by pretending that we just did the last insn in the
7754 basic block. If we are jumping to the end of our block, show
7755 that we can have one usage of TO. */
7757 if (simplejump_p (insn
))
7762 if (JUMP_LABEL (insn
) == to
)
7765 /* Maybe TO was deleted because the jump is unconditional.
7766 If so, there is nothing left in this basic block. */
7767 /* ??? Perhaps it would be smarter to set TO
7768 to whatever follows this insn,
7769 and pretend the basic block had always ended here. */
7770 if (INSN_DELETED_P (to
))
7773 insn
= PREV_INSN (to
);
7776 /* See if it is ok to keep on going past the label
7777 which used to end our basic block. Remember that we incremented
7778 the count of that label, so we decrement it here. If we made
7779 a jump unconditional, TO_USAGE will be one; in that case, we don't
7780 want to count the use in that jump. */
7782 if (to
!= 0 && NEXT_INSN (insn
) == to
7783 && GET_CODE (to
) == CODE_LABEL
&& --LABEL_NUSES (to
) == to_usage
)
7785 struct cse_basic_block_data val
;
7787 insn
= NEXT_INSN (to
);
7789 if (LABEL_NUSES (to
) == 0)
7792 /* Find the end of the following block. Note that we won't be
7793 following branches in this case. If TO was the last insn
7794 in the function, we are done. Similarly, if we deleted the
7795 insn after TO, it must have been because it was preceded by
7796 a BARRIER. In that case, we are done with this block because it
7797 has no continuation. */
7799 if (insn
== 0 || INSN_DELETED_P (insn
))
7804 cse_end_of_basic_block (insn
, &val
, 0, 0, 0);
7806 /* If the tables we allocated have enough space left
7807 to handle all the SETs in the next basic block,
7808 continue through it. Otherwise, return,
7809 and that block will be scanned individually. */
7810 if (val
.nsets
* 2 + next_qty
> max_qty
)
7813 cse_basic_block_start
= val
.low_cuid
;
7814 cse_basic_block_end
= val
.high_cuid
;
7817 /* Prevent TO from being deleted if it is a label. */
7818 if (to
!= 0 && GET_CODE (to
) == CODE_LABEL
)
7821 /* Back up so we process the first insn in the extension. */
7822 insn
= PREV_INSN (insn
);
7826 if (next_qty
> max_qty
)
7829 /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
7830 the previous insn is the only insn that branches to the head of a loop,
7831 we can cse into the loop. Don't do this if we changed the jump
7832 structure of a loop unless we aren't going to be following jumps. */
7834 if ((cse_jumps_altered
== 0
7835 || (flag_cse_follow_jumps
== 0 && flag_cse_skip_blocks
== 0))
7836 && around_loop
&& to
!= 0
7837 && GET_CODE (to
) == NOTE
&& NOTE_LINE_NUMBER (to
) == NOTE_INSN_LOOP_END
7838 && GET_CODE (PREV_INSN (to
)) == JUMP_INSN
7839 && JUMP_LABEL (PREV_INSN (to
)) != 0
7840 && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to
))) == 1)
7841 cse_around_loop (JUMP_LABEL (PREV_INSN (to
)));
7843 return to
? NEXT_INSN (to
) : 0;
7846 /* Count the number of times registers are used (not set) in X.
7847 COUNTS is an array in which we accumulate the count, INCR is how much
7848 we count each register usage. */
7851 count_reg_usage (x
, counts
, incr
)
7856 enum rtx_code code
= GET_CODE (x
);
7863 counts
[REGNO (x
)] += incr
;
7877 /* Unless we are setting a REG, count everything in SET_DEST. */
7878 if (GET_CODE (SET_DEST (x
)) != REG
)
7879 count_reg_usage (SET_DEST (x
), counts
, incr
);
7880 count_reg_usage (SET_SRC (x
), counts
, incr
);
7886 count_reg_usage (PATTERN (x
), counts
, incr
);
7888 /* Things used in a REG_EQUAL note aren't dead since loop may try to
7892 count_reg_usage (REG_NOTES (x
), counts
, incr
);
7897 if (REG_NOTE_KIND (x
) == REG_EQUAL
)
7898 count_reg_usage (XEXP (x
, 0), counts
, incr
);
7900 count_reg_usage (XEXP (x
, 1), counts
, incr
);
7904 fmt
= GET_RTX_FORMAT (code
);
7905 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
7908 count_reg_usage (XEXP (x
, i
), counts
, incr
);
7909 else if (fmt
[i
] == 'E')
7910 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7911 count_reg_usage (XVECEXP (x
, i
, j
), counts
, incr
);
7915 /* Scan all the insns and delete any that are dead; i.e., they store a register
7916 that is never used or they copy a register to itself.
7918 This is used to remove insns made obviously dead by cse. It improves the
7919 heuristics in loop since it won't try to move dead invariants out of loops
7920 or make givs for dead quantities. The remaining passes of the compilation
7921 are also sped up. */
7924 delete_dead_from_cse (insns
, nreg
)
7928 int *counts
= (int *) alloca (nreg
* sizeof (int));
7934 /* First count the number of times each register is used. */
7935 bzero (counts
, sizeof (int) * nreg
);
7936 for (insn
= next_real_insn (insns
); insn
; insn
= next_real_insn (insn
))
7937 count_reg_usage (insn
, counts
, 1);
7939 /* Go from the last insn to the first and delete insns that only set unused
7940 registers or copy a register to itself. As we delete an insn, remove
7941 usage counts for registers it uses. */
7942 for (insn
= prev_real_insn (get_last_insn ()); insn
; insn
= prev
)
7946 prev
= prev_real_insn (insn
);
7948 /* Don't delete any insns that are part of a libcall block.
7949 Flow or loop might get confused if we did that. Remember
7950 that we are scanning backwards. */
7951 if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
))
7956 else if (GET_CODE (PATTERN (insn
)) == SET
)
7958 if (GET_CODE (SET_DEST (PATTERN (insn
))) == REG
7959 && SET_DEST (PATTERN (insn
)) == SET_SRC (PATTERN (insn
)))
7963 else if (GET_CODE (SET_DEST (PATTERN (insn
))) == CC0
7964 && ! side_effects_p (SET_SRC (PATTERN (insn
)))
7965 && ((tem
= next_nonnote_insn (insn
)) == 0
7966 || GET_RTX_CLASS (GET_CODE (tem
)) != 'i'
7967 || ! reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
7970 else if (GET_CODE (SET_DEST (PATTERN (insn
))) != REG
7971 || REGNO (SET_DEST (PATTERN (insn
))) < FIRST_PSEUDO_REGISTER
7972 || counts
[REGNO (SET_DEST (PATTERN (insn
)))] != 0
7973 || side_effects_p (SET_SRC (PATTERN (insn
))))
7976 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
7977 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
7979 rtx elt
= XVECEXP (PATTERN (insn
), 0, i
);
7981 if (GET_CODE (elt
) == SET
)
7983 if (GET_CODE (SET_DEST (elt
)) == REG
7984 && SET_DEST (elt
) == SET_SRC (elt
))
7988 else if (GET_CODE (SET_DEST (elt
)) == CC0
7989 && ! side_effects_p (SET_SRC (elt
))
7990 && ((tem
= next_nonnote_insn (insn
)) == 0
7991 || GET_RTX_CLASS (GET_CODE (tem
)) != 'i'
7992 || ! reg_referenced_p (cc0_rtx
, PATTERN (tem
))))
7995 else if (GET_CODE (SET_DEST (elt
)) != REG
7996 || REGNO (SET_DEST (elt
)) < FIRST_PSEUDO_REGISTER
7997 || counts
[REGNO (SET_DEST (elt
))] != 0
7998 || side_effects_p (SET_SRC (elt
)))
8001 else if (GET_CODE (elt
) != CLOBBER
&& GET_CODE (elt
) != USE
)
8007 /* If this is a dead insn, delete it and show registers in it aren't
8012 count_reg_usage (insn
, counts
, -1);
8016 if (find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
))