1 /* RTL simplification functions for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
44 /* Simplification and canonicalization of RTL. */
46 /* Nonzero if X has the form (PLUS frame-pointer integer). We check for
47 virtual regs here because the simplify_*_operation routines are called
48 by integrate.c, which is called before virtual register instantiation.
50 ?!? FIXED_BASE_PLUS_P and NONZERO_BASE_PLUS_P need to move into
51 a header file so that their definitions can be shared with the
52 simplification routines in simplify-rtx.c. Until then, do not
53 change these macros without also changing the copy in simplify-rtx.c. */
55 #define FIXED_BASE_PLUS_P(X) \
56 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
57 || ((X) == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])\
58 || (X) == virtual_stack_vars_rtx \
59 || (X) == virtual_incoming_args_rtx \
60 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
61 && (XEXP (X, 0) == frame_pointer_rtx \
62 || XEXP (X, 0) == hard_frame_pointer_rtx \
63 || ((X) == arg_pointer_rtx \
64 && fixed_regs[ARG_POINTER_REGNUM]) \
65 || XEXP (X, 0) == virtual_stack_vars_rtx \
66 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
67 || GET_CODE (X) == ADDRESSOF)
69 /* Similar, but also allows reference to the stack pointer.
71 This used to include FIXED_BASE_PLUS_P, however, we can't assume that
72 arg_pointer_rtx by itself is nonzero, because on at least one machine,
73 the i960, the arg pointer is zero when it is unused. */
75 #define NONZERO_BASE_PLUS_P(X) \
76 ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx \
77 || (X) == virtual_stack_vars_rtx \
78 || (X) == virtual_incoming_args_rtx \
79 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
80 && (XEXP (X, 0) == frame_pointer_rtx \
81 || XEXP (X, 0) == hard_frame_pointer_rtx \
82 || ((X) == arg_pointer_rtx \
83 && fixed_regs[ARG_POINTER_REGNUM]) \
84 || XEXP (X, 0) == virtual_stack_vars_rtx \
85 || XEXP (X, 0) == virtual_incoming_args_rtx)) \
86 || (X) == stack_pointer_rtx \
87 || (X) == virtual_stack_dynamic_rtx \
88 || (X) == virtual_outgoing_args_rtx \
89 || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
90 && (XEXP (X, 0) == stack_pointer_rtx \
91 || XEXP (X, 0) == virtual_stack_dynamic_rtx \
92 || XEXP (X, 0) == virtual_outgoing_args_rtx)) \
93 || GET_CODE (X) == ADDRESSOF)
96 static rtx simplify_plus_minus PARAMS ((enum rtx_code,
97 enum machine_mode, rtx, rtx));
98 static void check_fold_consts PARAMS ((PTR));
99 static int entry_and_rtx_equal_p PARAMS ((const void *, const void *));
100 static unsigned int get_value_hash PARAMS ((const void *));
101 static struct elt_list *new_elt_list PARAMS ((struct elt_list *,
103 static struct elt_loc_list *new_elt_loc_list PARAMS ((struct elt_loc_list *,
105 static void unchain_one_value PARAMS ((cselib_val *));
106 static void unchain_one_elt_list PARAMS ((struct elt_list **));
107 static void unchain_one_elt_loc_list PARAMS ((struct elt_loc_list **));
108 static void clear_table PARAMS ((void));
109 static int discard_useless_locs PARAMS ((void **, void *));
110 static int discard_useless_values PARAMS ((void **, void *));
111 static void remove_useless_values PARAMS ((void));
112 static unsigned int hash_rtx PARAMS ((rtx, enum machine_mode, int));
113 static cselib_val *new_cselib_val PARAMS ((unsigned int,
115 static void add_mem_for_addr PARAMS ((cselib_val *, cselib_val *,
117 static cselib_val *cselib_lookup_mem PARAMS ((rtx, int));
118 static rtx cselib_subst_to_values PARAMS ((rtx));
119 static void cselib_invalidate_regno PARAMS ((unsigned int,
121 static int cselib_mem_conflict_p PARAMS ((rtx, rtx));
122 static int cselib_invalidate_mem_1 PARAMS ((void **, void *));
123 static void cselib_invalidate_mem PARAMS ((rtx));
124 static void cselib_invalidate_rtx PARAMS ((rtx, rtx, void *));
125 static void cselib_record_set PARAMS ((rtx, cselib_val *,
127 static void cselib_record_sets PARAMS ((rtx));
129 /* There are three ways in which cselib can look up an rtx:
130 - for a REG, the reg_values table (which is indexed by regno) is used
131 - for a MEM, we recursively look up its address and then follow the
132 addr_list of that value
133 - for everything else, we compute a hash value and go through the hash
134 table. Since different rtx's can still have the same hash value,
135 this involves walking the table entries for a given value and comparing
136 the locations of the entries with the rtx we are looking up. */
138 /* A table that enables us to look up elts by their value. */
139 static htab_t hash_table;
141 /* This is a global so we don't have to pass this through every function.
142 It is used in new_elt_loc_list to set SETTING_INSN. */
143 static rtx cselib_current_insn;
145 /* Every new unknown value gets a unique number. */
146 static unsigned int next_unknown_value;
148 /* The number of registers we had when the varrays were last resized. */
149 static unsigned int cselib_nregs;
151 /* Count values without known locations. Whenever this grows too big, we
152 remove these useless values from the table. */
153 static int n_useless_values;
155 /* Number of useless values before we remove them from the hash table. */
156 #define MAX_USELESS_VALUES 32
158 /* This table maps from register number to values. It does not contain
159 pointers to cselib_val structures, but rather elt_lists. The purpose is
160 to be able to refer to the same register in different modes. */
161 static varray_type reg_values;
162 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
164 /* We pass this to cselib_invalidate_mem to invalidate all of
165 memory for a non-const call instruction. */
168 /* Memory for our structures is allocated from this obstack. */
169 static struct obstack cselib_obstack;
171 /* Used to quickly free all memory. */
172 static char *cselib_startobj;
174 /* Caches for unused structures. */
175 static cselib_val *empty_vals;
176 static struct elt_list *empty_elt_lists;
177 static struct elt_loc_list *empty_elt_loc_lists;
179 /* Set by discard_useless_locs if it deleted the last location of any
181 static int values_became_useless;
183 /* Make a binary operation by properly ordering the operands and
184 seeing if the expression folds. */
187 simplify_gen_binary (code, mode, op0, op1)
189 enum machine_mode mode;
194 /* Put complex operands first and constants second if commutative. */
195 if (GET_RTX_CLASS (code) == 'c'
196 && ((CONSTANT_P (op0) && GET_CODE (op1) != CONST_INT)
197 || (GET_RTX_CLASS (GET_CODE (op0)) == 'o'
198 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')
199 || (GET_CODE (op0) == SUBREG
200 && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op0))) == 'o'
201 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')))
202 tem = op0, op0 = op1, op1 = tem;
204 /* If this simplifies, do it. */
205 tem = simplify_binary_operation (code, mode, op0, op1);
210 /* Handle addition and subtraction of CONST_INT specially. Otherwise,
211 just form the operation. */
213 if (code == PLUS && GET_CODE (op1) == CONST_INT
214 && GET_MODE (op0) != VOIDmode)
215 return plus_constant (op0, INTVAL (op1));
216 else if (code == MINUS && GET_CODE (op1) == CONST_INT
217 && GET_MODE (op0) != VOIDmode)
218 return plus_constant (op0, - INTVAL (op1));
220 return gen_rtx_fmt_ee (code, mode, op0, op1);
223 /* Try to simplify a unary operation CODE whose output mode is to be
224 MODE with input operand OP whose mode was originally OP_MODE.
225 Return zero if no simplification can be made. */
228 simplify_unary_operation (code, mode, op, op_mode)
230 enum machine_mode mode;
232 enum machine_mode op_mode;
234 unsigned int width = GET_MODE_BITSIZE (mode);
236 /* The order of these tests is critical so that, for example, we don't
237 check the wrong mode (input vs. output) for a conversion operation,
238 such as FIX. At some point, this should be simplified. */
240 #if !defined(REAL_IS_NOT_DOUBLE) || defined(REAL_ARITHMETIC)
242 if (code == FLOAT && GET_MODE (op) == VOIDmode
243 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
245 HOST_WIDE_INT hv, lv;
248 if (GET_CODE (op) == CONST_INT)
249 lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0;
251 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
253 #ifdef REAL_ARITHMETIC
254 REAL_VALUE_FROM_INT (d, lv, hv, mode);
259 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
260 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
261 d += (double) (unsigned HOST_WIDE_INT) (~ lv);
267 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
268 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
269 d += (double) (unsigned HOST_WIDE_INT) lv;
271 #endif /* REAL_ARITHMETIC */
272 d = real_value_truncate (mode, d);
273 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
275 else if (code == UNSIGNED_FLOAT && GET_MODE (op) == VOIDmode
276 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
278 HOST_WIDE_INT hv, lv;
281 if (GET_CODE (op) == CONST_INT)
282 lv = INTVAL (op), hv = INTVAL (op) < 0 ? -1 : 0;
284 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
286 if (op_mode == VOIDmode)
288 /* We don't know how to interpret negative-looking numbers in
289 this case, so don't try to fold those. */
293 else if (GET_MODE_BITSIZE (op_mode) >= HOST_BITS_PER_WIDE_INT * 2)
296 hv = 0, lv &= GET_MODE_MASK (op_mode);
298 #ifdef REAL_ARITHMETIC
299 REAL_VALUE_FROM_UNSIGNED_INT (d, lv, hv, mode);
302 d = (double) (unsigned HOST_WIDE_INT) hv;
303 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
304 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
305 d += (double) (unsigned HOST_WIDE_INT) lv;
306 #endif /* REAL_ARITHMETIC */
307 d = real_value_truncate (mode, d);
308 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
312 if (GET_CODE (op) == CONST_INT
313 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
315 register HOST_WIDE_INT arg0 = INTVAL (op);
316 register HOST_WIDE_INT val;
329 val = (arg0 >= 0 ? arg0 : - arg0);
333 /* Don't use ffs here. Instead, get low order bit and then its
334 number. If arg0 is zero, this will return 0, as desired. */
335 arg0 &= GET_MODE_MASK (mode);
336 val = exact_log2 (arg0 & (- arg0)) + 1;
344 if (op_mode == VOIDmode)
346 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
348 /* If we were really extending the mode,
349 we would have to distinguish between zero-extension
350 and sign-extension. */
351 if (width != GET_MODE_BITSIZE (op_mode))
355 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
356 val = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
362 if (op_mode == VOIDmode)
364 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
366 /* If we were really extending the mode,
367 we would have to distinguish between zero-extension
368 and sign-extension. */
369 if (width != GET_MODE_BITSIZE (op_mode))
373 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
376 = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
378 & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (op_mode) - 1)))
379 val -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
392 val = trunc_int_for_mode (val, mode);
394 return GEN_INT (val);
397 /* We can do some operations on integer CONST_DOUBLEs. Also allow
398 for a DImode operation on a CONST_INT. */
399 else if (GET_MODE (op) == VOIDmode && width <= HOST_BITS_PER_INT * 2
400 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
402 HOST_WIDE_INT l1, h1, lv, hv;
404 if (GET_CODE (op) == CONST_DOUBLE)
405 l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op);
407 l1 = INTVAL (op), h1 = l1 < 0 ? -1 : 0;
417 neg_double (l1, h1, &lv, &hv);
422 neg_double (l1, h1, &lv, &hv);
430 lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & (-h1)) + 1;
432 lv = exact_log2 (l1 & (-l1)) + 1;
436 /* This is just a change-of-mode, so do nothing. */
441 if (op_mode == VOIDmode
442 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
446 lv = l1 & GET_MODE_MASK (op_mode);
450 if (op_mode == VOIDmode
451 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
455 lv = l1 & GET_MODE_MASK (op_mode);
456 if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT
457 && (lv & ((HOST_WIDE_INT) 1
458 << (GET_MODE_BITSIZE (op_mode) - 1))) != 0)
459 lv -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
461 hv = (lv < 0) ? ~ (HOST_WIDE_INT) 0 : 0;
472 return immed_double_const (lv, hv, mode);
475 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
476 else if (GET_CODE (op) == CONST_DOUBLE
477 && GET_MODE_CLASS (mode) == MODE_FLOAT)
483 if (setjmp (handler))
484 /* There used to be a warning here, but that is inadvisable.
485 People may want to cause traps, and the natural way
486 to do it should not get a warning. */
489 set_float_handler (handler);
491 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
496 d = REAL_VALUE_NEGATE (d);
500 if (REAL_VALUE_NEGATIVE (d))
501 d = REAL_VALUE_NEGATE (d);
505 d = real_value_truncate (mode, d);
509 /* All this does is change the mode. */
513 d = REAL_VALUE_RNDZINT (d);
517 d = REAL_VALUE_UNSIGNED_RNDZINT (d);
527 x = CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
528 set_float_handler (NULL_PTR);
532 else if (GET_CODE (op) == CONST_DOUBLE
533 && GET_MODE_CLASS (GET_MODE (op)) == MODE_FLOAT
534 && GET_MODE_CLASS (mode) == MODE_INT
535 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
541 if (setjmp (handler))
544 set_float_handler (handler);
546 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
551 val = REAL_VALUE_FIX (d);
555 val = REAL_VALUE_UNSIGNED_FIX (d);
562 set_float_handler (NULL_PTR);
564 val = trunc_int_for_mode (val, mode);
566 return GEN_INT (val);
569 /* This was formerly used only for non-IEEE float.
570 eggert@twinsun.com says it is safe for IEEE also. */
573 /* There are some simplifications we can do even if the operands
579 /* (not (not X)) == X, similarly for NEG. */
580 if (GET_CODE (op) == code)
585 /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
586 becomes just the MINUS if its mode is MODE. This allows
587 folding switch statements on machines using casesi (such as
589 if (GET_CODE (op) == TRUNCATE
590 && GET_MODE (XEXP (op, 0)) == mode
591 && GET_CODE (XEXP (op, 0)) == MINUS
592 && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
593 && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
596 #ifdef POINTERS_EXTEND_UNSIGNED
597 if (! POINTERS_EXTEND_UNSIGNED
598 && mode == Pmode && GET_MODE (op) == ptr_mode
600 return convert_memory_address (Pmode, op);
604 #ifdef POINTERS_EXTEND_UNSIGNED
606 if (POINTERS_EXTEND_UNSIGNED
607 && mode == Pmode && GET_MODE (op) == ptr_mode
609 return convert_memory_address (Pmode, op);
621 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
622 and OP1. Return 0 if no simplification is possible.
624 Don't use this for relational operations such as EQ or LT.
625 Use simplify_relational_operation instead. */
628 simplify_binary_operation (code, mode, op0, op1)
630 enum machine_mode mode;
633 register HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
635 unsigned int width = GET_MODE_BITSIZE (mode);
638 /* Relational operations don't work here. We must know the mode
639 of the operands in order to do the comparison correctly.
640 Assuming a full word can give incorrect results.
641 Consider comparing 128 with -128 in QImode. */
643 if (GET_RTX_CLASS (code) == '<')
646 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
647 if (GET_MODE_CLASS (mode) == MODE_FLOAT
648 && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
649 && mode == GET_MODE (op0) && mode == GET_MODE (op1))
651 REAL_VALUE_TYPE f0, f1, value;
654 if (setjmp (handler))
657 set_float_handler (handler);
659 REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
660 REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
661 f0 = real_value_truncate (mode, f0);
662 f1 = real_value_truncate (mode, f1);
664 #ifdef REAL_ARITHMETIC
665 #ifndef REAL_INFINITY
666 if (code == DIV && REAL_VALUES_EQUAL (f1, dconst0))
669 REAL_ARITHMETIC (value, rtx_to_tree_code (code), f0, f1);
683 #ifndef REAL_INFINITY
690 value = MIN (f0, f1);
693 value = MAX (f0, f1);
700 value = real_value_truncate (mode, value);
701 set_float_handler (NULL_PTR);
702 return CONST_DOUBLE_FROM_REAL_VALUE (value, mode);
704 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
706 /* We can fold some multi-word operations. */
707 if (GET_MODE_CLASS (mode) == MODE_INT
708 && width == HOST_BITS_PER_WIDE_INT * 2
709 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
710 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
712 HOST_WIDE_INT l1, l2, h1, h2, lv, hv;
714 if (GET_CODE (op0) == CONST_DOUBLE)
715 l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0);
717 l1 = INTVAL (op0), h1 = l1 < 0 ? -1 : 0;
719 if (GET_CODE (op1) == CONST_DOUBLE)
720 l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1);
722 l2 = INTVAL (op1), h2 = l2 < 0 ? -1 : 0;
727 /* A - B == A + (-B). */
728 neg_double (l2, h2, &lv, &hv);
731 /* .. fall through ... */
734 add_double (l1, h1, l2, h2, &lv, &hv);
738 mul_double (l1, h1, l2, h2, &lv, &hv);
741 case DIV: case MOD: case UDIV: case UMOD:
742 /* We'd need to include tree.h to do this and it doesn't seem worth
747 lv = l1 & l2, hv = h1 & h2;
751 lv = l1 | l2, hv = h1 | h2;
755 lv = l1 ^ l2, hv = h1 ^ h2;
761 && ((unsigned HOST_WIDE_INT) l1
762 < (unsigned HOST_WIDE_INT) l2)))
771 && ((unsigned HOST_WIDE_INT) l1
772 > (unsigned HOST_WIDE_INT) l2)))
779 if ((unsigned HOST_WIDE_INT) h1 < (unsigned HOST_WIDE_INT) h2
781 && ((unsigned HOST_WIDE_INT) l1
782 < (unsigned HOST_WIDE_INT) l2)))
789 if ((unsigned HOST_WIDE_INT) h1 > (unsigned HOST_WIDE_INT) h2
791 && ((unsigned HOST_WIDE_INT) l1
792 > (unsigned HOST_WIDE_INT) l2)))
798 case LSHIFTRT: case ASHIFTRT:
800 case ROTATE: case ROTATERT:
801 #ifdef SHIFT_COUNT_TRUNCATED
802 if (SHIFT_COUNT_TRUNCATED)
803 l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0;
806 if (h2 != 0 || l2 < 0 || l2 >= GET_MODE_BITSIZE (mode))
809 if (code == LSHIFTRT || code == ASHIFTRT)
810 rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
812 else if (code == ASHIFT)
813 lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, 1);
814 else if (code == ROTATE)
815 lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
816 else /* code == ROTATERT */
817 rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
824 return immed_double_const (lv, hv, mode);
827 if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
828 || width > HOST_BITS_PER_WIDE_INT || width == 0)
830 /* Even if we can't compute a constant result,
831 there are some cases worth simplifying. */
836 /* In IEEE floating point, x+0 is not the same as x. Similarly
837 for the other optimizations below. */
838 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
839 && FLOAT_MODE_P (mode) && ! flag_fast_math)
842 if (op1 == CONST0_RTX (mode))
845 /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
846 if (GET_CODE (op0) == NEG)
847 return simplify_gen_binary (MINUS, mode, op1, XEXP (op0, 0));
848 else if (GET_CODE (op1) == NEG)
849 return simplify_gen_binary (MINUS, mode, op0, XEXP (op1, 0));
851 /* Handle both-operands-constant cases. We can only add
852 CONST_INTs to constants since the sum of relocatable symbols
853 can't be handled by most assemblers. Don't add CONST_INT
854 to CONST_INT since overflow won't be computed properly if wider
855 than HOST_BITS_PER_WIDE_INT. */
857 if (CONSTANT_P (op0) && GET_MODE (op0) != VOIDmode
858 && GET_CODE (op1) == CONST_INT)
859 return plus_constant (op0, INTVAL (op1));
860 else if (CONSTANT_P (op1) && GET_MODE (op1) != VOIDmode
861 && GET_CODE (op0) == CONST_INT)
862 return plus_constant (op1, INTVAL (op0));
864 /* See if this is something like X * C - X or vice versa or
865 if the multiplication is written as a shift. If so, we can
866 distribute and make a new multiply, shift, or maybe just
867 have X (if C is 2 in the example above). But don't make
868 real multiply if we didn't have one before. */
870 if (! FLOAT_MODE_P (mode))
872 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
873 rtx lhs = op0, rhs = op1;
876 if (GET_CODE (lhs) == NEG)
877 coeff0 = -1, lhs = XEXP (lhs, 0);
878 else if (GET_CODE (lhs) == MULT
879 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
881 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
884 else if (GET_CODE (lhs) == ASHIFT
885 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
886 && INTVAL (XEXP (lhs, 1)) >= 0
887 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
889 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
893 if (GET_CODE (rhs) == NEG)
894 coeff1 = -1, rhs = XEXP (rhs, 0);
895 else if (GET_CODE (rhs) == MULT
896 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
898 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
901 else if (GET_CODE (rhs) == ASHIFT
902 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
903 && INTVAL (XEXP (rhs, 1)) >= 0
904 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
906 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
910 if (rtx_equal_p (lhs, rhs))
912 tem = simplify_gen_binary (MULT, mode, lhs,
913 GEN_INT (coeff0 + coeff1));
914 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
918 /* If one of the operands is a PLUS or a MINUS, see if we can
919 simplify this by the associative law.
920 Don't use the associative law for floating point.
921 The inaccuracy makes it nonassociative,
922 and subtle programs can break if operations are associated. */
924 if (INTEGRAL_MODE_P (mode)
925 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
926 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
927 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
933 /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
934 using cc0, in which case we want to leave it as a COMPARE
935 so we can distinguish it from a register-register-copy.
937 In IEEE floating point, x-0 is not the same as x. */
939 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
940 || ! FLOAT_MODE_P (mode) || flag_fast_math)
941 && op1 == CONST0_RTX (mode))
944 /* Do nothing here. */
949 /* None of these optimizations can be done for IEEE
951 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
952 && FLOAT_MODE_P (mode) && ! flag_fast_math)
955 /* We can't assume x-x is 0 even with non-IEEE floating point,
956 but since it is zero except in very strange circumstances, we
957 will treat it as zero with -ffast-math. */
958 if (rtx_equal_p (op0, op1)
959 && ! side_effects_p (op0)
960 && (! FLOAT_MODE_P (mode) || flag_fast_math))
961 return CONST0_RTX (mode);
963 /* Change subtraction from zero into negation. */
964 if (op0 == CONST0_RTX (mode))
965 return gen_rtx_NEG (mode, op1);
967 /* (-1 - a) is ~a. */
968 if (op0 == constm1_rtx)
969 return gen_rtx_NOT (mode, op1);
971 /* Subtracting 0 has no effect. */
972 if (op1 == CONST0_RTX (mode))
975 /* See if this is something like X * C - X or vice versa or
976 if the multiplication is written as a shift. If so, we can
977 distribute and make a new multiply, shift, or maybe just
978 have X (if C is 2 in the example above). But don't make
979 real multiply if we didn't have one before. */
981 if (! FLOAT_MODE_P (mode))
983 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
984 rtx lhs = op0, rhs = op1;
987 if (GET_CODE (lhs) == NEG)
988 coeff0 = -1, lhs = XEXP (lhs, 0);
989 else if (GET_CODE (lhs) == MULT
990 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
992 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
995 else if (GET_CODE (lhs) == ASHIFT
996 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
997 && INTVAL (XEXP (lhs, 1)) >= 0
998 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
1000 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
1001 lhs = XEXP (lhs, 0);
1004 if (GET_CODE (rhs) == NEG)
1005 coeff1 = - 1, rhs = XEXP (rhs, 0);
1006 else if (GET_CODE (rhs) == MULT
1007 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
1009 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
1012 else if (GET_CODE (rhs) == ASHIFT
1013 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
1014 && INTVAL (XEXP (rhs, 1)) >= 0
1015 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
1017 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
1018 rhs = XEXP (rhs, 0);
1021 if (rtx_equal_p (lhs, rhs))
1023 tem = simplify_gen_binary (MULT, mode, lhs,
1024 GEN_INT (coeff0 - coeff1));
1025 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
1029 /* (a - (-b)) -> (a + b). */
1030 if (GET_CODE (op1) == NEG)
1031 return simplify_gen_binary (PLUS, mode, op0, XEXP (op1, 0));
1033 /* If one of the operands is a PLUS or a MINUS, see if we can
1034 simplify this by the associative law.
1035 Don't use the associative law for floating point.
1036 The inaccuracy makes it nonassociative,
1037 and subtle programs can break if operations are associated. */
1039 if (INTEGRAL_MODE_P (mode)
1040 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
1041 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
1042 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
1045 /* Don't let a relocatable value get a negative coeff. */
1046 if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode)
1047 return plus_constant (op0, - INTVAL (op1));
1049 /* (x - (x & y)) -> (x & ~y) */
1050 if (GET_CODE (op1) == AND)
1052 if (rtx_equal_p (op0, XEXP (op1, 0)))
1053 return simplify_gen_binary (AND, mode, op0,
1054 gen_rtx_NOT (mode, XEXP (op1, 1)));
1055 if (rtx_equal_p (op0, XEXP (op1, 1)))
1056 return simplify_gen_binary (AND, mode, op0,
1057 gen_rtx_NOT (mode, XEXP (op1, 0)));
1062 if (op1 == constm1_rtx)
1064 tem = simplify_unary_operation (NEG, mode, op0, mode);
1066 return tem ? tem : gen_rtx_NEG (mode, op0);
1069 /* In IEEE floating point, x*0 is not always 0. */
1070 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1071 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1072 && op1 == CONST0_RTX (mode)
1073 && ! side_effects_p (op0))
1076 /* In IEEE floating point, x*1 is not equivalent to x for nans.
1077 However, ANSI says we can drop signals,
1078 so we can do this anyway. */
1079 if (op1 == CONST1_RTX (mode))
1082 /* Convert multiply by constant power of two into shift unless
1083 we are still generating RTL. This test is a kludge. */
1084 if (GET_CODE (op1) == CONST_INT
1085 && (val = exact_log2 (INTVAL (op1))) >= 0
1086 /* If the mode is larger than the host word size, and the
1087 uppermost bit is set, then this isn't a power of two due
1088 to implicit sign extension. */
1089 && (width <= HOST_BITS_PER_WIDE_INT
1090 || val != HOST_BITS_PER_WIDE_INT - 1)
1091 && ! rtx_equal_function_value_matters)
1092 return gen_rtx_ASHIFT (mode, op0, GEN_INT (val));
1094 if (GET_CODE (op1) == CONST_DOUBLE
1095 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
1099 int op1is2, op1ism1;
1101 if (setjmp (handler))
1104 set_float_handler (handler);
1105 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1106 op1is2 = REAL_VALUES_EQUAL (d, dconst2);
1107 op1ism1 = REAL_VALUES_EQUAL (d, dconstm1);
1108 set_float_handler (NULL_PTR);
1110 /* x*2 is x+x and x*(-1) is -x */
1111 if (op1is2 && GET_MODE (op0) == mode)
1112 return gen_rtx_PLUS (mode, op0, copy_rtx (op0));
1114 else if (op1ism1 && GET_MODE (op0) == mode)
1115 return gen_rtx_NEG (mode, op0);
1120 if (op1 == const0_rtx)
1122 if (GET_CODE (op1) == CONST_INT
1123 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1125 if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1127 /* A | (~A) -> -1 */
1128 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1129 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1130 && ! side_effects_p (op0)
1131 && GET_MODE_CLASS (mode) != MODE_CC)
1136 if (op1 == const0_rtx)
1138 if (GET_CODE (op1) == CONST_INT
1139 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1140 return gen_rtx_NOT (mode, op0);
1141 if (op0 == op1 && ! side_effects_p (op0)
1142 && GET_MODE_CLASS (mode) != MODE_CC)
1147 if (op1 == const0_rtx && ! side_effects_p (op0))
1149 if (GET_CODE (op1) == CONST_INT
1150 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1152 if (op0 == op1 && ! side_effects_p (op0)
1153 && GET_MODE_CLASS (mode) != MODE_CC)
1156 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1157 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1158 && ! side_effects_p (op0)
1159 && GET_MODE_CLASS (mode) != MODE_CC)
1164 /* Convert divide by power of two into shift (divide by 1 handled
1166 if (GET_CODE (op1) == CONST_INT
1167 && (arg1 = exact_log2 (INTVAL (op1))) > 0)
1168 return gen_rtx_LSHIFTRT (mode, op0, GEN_INT (arg1));
1170 /* ... fall through ... */
1173 if (op1 == CONST1_RTX (mode))
1176 /* In IEEE floating point, 0/x is not always 0. */
1177 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1178 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1179 && op0 == CONST0_RTX (mode)
1180 && ! side_effects_p (op1))
1183 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1184 /* Change division by a constant into multiplication. Only do
1185 this with -ffast-math until an expert says it is safe in
1187 else if (GET_CODE (op1) == CONST_DOUBLE
1188 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
1189 && op1 != CONST0_RTX (mode)
1193 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1195 if (! REAL_VALUES_EQUAL (d, dconst0))
1197 #if defined (REAL_ARITHMETIC)
1198 REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d);
1199 return gen_rtx_MULT (mode, op0,
1200 CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
1203 gen_rtx_MULT (mode, op0,
1204 CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
1212 /* Handle modulus by power of two (mod with 1 handled below). */
1213 if (GET_CODE (op1) == CONST_INT
1214 && exact_log2 (INTVAL (op1)) > 0)
1215 return gen_rtx_AND (mode, op0, GEN_INT (INTVAL (op1) - 1));
1217 /* ... fall through ... */
1220 if ((op0 == const0_rtx || op1 == const1_rtx)
1221 && ! side_effects_p (op0) && ! side_effects_p (op1))
1227 /* Rotating ~0 always results in ~0. */
1228 if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT
1229 && (unsigned HOST_WIDE_INT) INTVAL (op0) == GET_MODE_MASK (mode)
1230 && ! side_effects_p (op1))
1233 /* ... fall through ... */
1238 if (op1 == const0_rtx)
1240 if (op0 == const0_rtx && ! side_effects_p (op1))
1245 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1246 && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1)
1247 && ! side_effects_p (op0))
1249 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1254 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1255 && ((unsigned HOST_WIDE_INT) INTVAL (op1)
1256 == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1)
1257 && ! side_effects_p (op0))
1259 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1264 if (op1 == const0_rtx && ! side_effects_p (op0))
1266 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1271 if (op1 == constm1_rtx && ! side_effects_p (op0))
1273 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1284 /* Get the integer argument values in two forms:
1285 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
1287 arg0 = INTVAL (op0);
1288 arg1 = INTVAL (op1);
1290 if (width < HOST_BITS_PER_WIDE_INT)
1292 arg0 &= ((HOST_WIDE_INT) 1 << width) - 1;
1293 arg1 &= ((HOST_WIDE_INT) 1 << width) - 1;
1296 if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1297 arg0s |= ((HOST_WIDE_INT) (-1) << width);
1300 if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1301 arg1s |= ((HOST_WIDE_INT) (-1) << width);
1309 /* Compute the value of the arithmetic. */
1314 val = arg0s + arg1s;
1318 val = arg0s - arg1s;
1322 val = arg0s * arg1s;
1328 val = arg0s / arg1s;
1334 val = arg0s % arg1s;
1340 val = (unsigned HOST_WIDE_INT) arg0 / arg1;
1346 val = (unsigned HOST_WIDE_INT) arg0 % arg1;
1362 /* If shift count is undefined, don't fold it; let the machine do
1363 what it wants. But truncate it if the machine will do that. */
1367 #ifdef SHIFT_COUNT_TRUNCATED
1368 if (SHIFT_COUNT_TRUNCATED)
1372 val = ((unsigned HOST_WIDE_INT) arg0) >> arg1;
1379 #ifdef SHIFT_COUNT_TRUNCATED
1380 if (SHIFT_COUNT_TRUNCATED)
1384 val = ((unsigned HOST_WIDE_INT) arg0) << arg1;
1391 #ifdef SHIFT_COUNT_TRUNCATED
1392 if (SHIFT_COUNT_TRUNCATED)
1396 val = arg0s >> arg1;
1398 /* Bootstrap compiler may not have sign extended the right shift.
1399 Manually extend the sign to insure bootstrap cc matches gcc. */
1400 if (arg0s < 0 && arg1 > 0)
1401 val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1);
1410 val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1))
1411 | (((unsigned HOST_WIDE_INT) arg0) >> arg1));
1419 val = ((((unsigned HOST_WIDE_INT) arg0) << arg1)
1420 | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1)));
1424 /* Do nothing here. */
1428 val = arg0s <= arg1s ? arg0s : arg1s;
1432 val = ((unsigned HOST_WIDE_INT) arg0
1433 <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1437 val = arg0s > arg1s ? arg0s : arg1s;
1441 val = ((unsigned HOST_WIDE_INT) arg0
1442 > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1449 val = trunc_int_for_mode (val, mode);
1451 return GEN_INT (val);
1454 /* Simplify a PLUS or MINUS, at least one of whose operands may be another
1457 Rather than test for specific case, we do this by a brute-force method
1458 and do all possible simplifications until no more changes occur. Then
1459 we rebuild the operation. */
1462 simplify_plus_minus (code, mode, op0, op1)
1464 enum machine_mode mode;
1470 int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
1471 int first = 1, negate = 0, changed;
1474 bzero ((char *) ops, sizeof ops);
1476 /* Set up the two operands and then expand them until nothing has been
1477 changed. If we run out of room in our array, give up; this should
1478 almost never happen. */
1480 ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
1487 for (i = 0; i < n_ops; i++)
1488 switch (GET_CODE (ops[i]))
1495 ops[n_ops] = XEXP (ops[i], 1);
1496 negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
1497 ops[i] = XEXP (ops[i], 0);
1503 ops[i] = XEXP (ops[i], 0);
1504 negs[i] = ! negs[i];
1509 ops[i] = XEXP (ops[i], 0);
1515 /* ~a -> (-a - 1) */
1518 ops[n_ops] = constm1_rtx;
1519 negs[n_ops++] = negs[i];
1520 ops[i] = XEXP (ops[i], 0);
1521 negs[i] = ! negs[i];
1528 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
1536 /* If we only have two operands, we can't do anything. */
1540 /* Now simplify each pair of operands until nothing changes. The first
1541 time through just simplify constants against each other. */
1548 for (i = 0; i < n_ops - 1; i++)
1549 for (j = i + 1; j < n_ops; j++)
1550 if (ops[i] != 0 && ops[j] != 0
1551 && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
1553 rtx lhs = ops[i], rhs = ops[j];
1554 enum rtx_code ncode = PLUS;
1556 if (negs[i] && ! negs[j])
1557 lhs = ops[j], rhs = ops[i], ncode = MINUS;
1558 else if (! negs[i] && negs[j])
1561 tem = simplify_binary_operation (ncode, mode, lhs, rhs);
1564 ops[i] = tem, ops[j] = 0;
1565 negs[i] = negs[i] && negs[j];
1566 if (GET_CODE (tem) == NEG)
1567 ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
1569 if (GET_CODE (ops[i]) == CONST_INT && negs[i])
1570 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
1578 /* Pack all the operands to the lower-numbered entries and give up if
1579 we didn't reduce the number of operands we had. Make sure we
1580 count a CONST as two operands. If we have the same number of
1581 operands, but have made more CONSTs than we had, this is also
1582 an improvement, so accept it. */
1584 for (i = 0, j = 0; j < n_ops; j++)
1587 ops[i] = ops[j], negs[i++] = negs[j];
1588 if (GET_CODE (ops[j]) == CONST)
1592 if (i + n_consts > input_ops
1593 || (i + n_consts == input_ops && n_consts <= input_consts))
1598 /* If we have a CONST_INT, put it last. */
1599 for (i = 0; i < n_ops - 1; i++)
1600 if (GET_CODE (ops[i]) == CONST_INT)
1602 tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
1603 j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
1606 /* Put a non-negated operand first. If there aren't any, make all
1607 operands positive and negate the whole thing later. */
1608 for (i = 0; i < n_ops && negs[i]; i++)
1613 for (i = 0; i < n_ops; i++)
1619 tem = ops[0], ops[0] = ops[i], ops[i] = tem;
1620 j = negs[0], negs[0] = negs[i], negs[i] = j;
1623 /* Now make the result by performing the requested operations. */
1625 for (i = 1; i < n_ops; i++)
1626 result = simplify_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
1628 return negate ? gen_rtx_NEG (mode, result) : result;
1633 rtx op0, op1; /* Input */
1634 int equal, op0lt, op1lt; /* Output */
1638 check_fold_consts (data)
1641 struct cfc_args *args = (struct cfc_args *) data;
1642 REAL_VALUE_TYPE d0, d1;
1644 REAL_VALUE_FROM_CONST_DOUBLE (d0, args->op0);
1645 REAL_VALUE_FROM_CONST_DOUBLE (d1, args->op1);
1646 args->equal = REAL_VALUES_EQUAL (d0, d1);
1647 args->op0lt = REAL_VALUES_LESS (d0, d1);
1648 args->op1lt = REAL_VALUES_LESS (d1, d0);
1651 /* Like simplify_binary_operation except used for relational operators.
1652 MODE is the mode of the operands, not that of the result. If MODE
1653 is VOIDmode, both operands must also be VOIDmode and we compare the
1654 operands in "infinite precision".
1656 If no simplification is possible, this function returns zero. Otherwise,
1657 it returns either const_true_rtx or const0_rtx. */
1660 simplify_relational_operation (code, mode, op0, op1)
1662 enum machine_mode mode;
1665 int equal, op0lt, op0ltu, op1lt, op1ltu;
1668 /* If op0 is a compare, extract the comparison arguments from it. */
1669 if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
1670 op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
1672 /* We can't simplify MODE_CC values since we don't know what the
1673 actual comparison is. */
1674 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC
1681 /* Make sure the constant is second. */
1682 if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
1683 || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
1685 tem = op0, op0 = op1, op1 = tem;
1686 code = swap_condition (code);
1689 /* For integer comparisons of A and B maybe we can simplify A - B and can
1690 then simplify a comparison of that with zero. If A and B are both either
1691 a register or a CONST_INT, this can't help; testing for these cases will
1692 prevent infinite recursion here and speed things up.
1694 If CODE is an unsigned comparison, then we can never do this optimization,
1695 because it gives an incorrect result if the subtraction wraps around zero.
1696 ANSI C defines unsigned operations such that they never overflow, and
1697 thus such cases can not be ignored. */
1699 if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx
1700 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT)
1701 && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT))
1702 && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1))
1703 && code != GTU && code != GEU && code != LTU && code != LEU)
1704 return simplify_relational_operation (signed_condition (code),
1705 mode, tem, const0_rtx);
1707 /* For non-IEEE floating-point, if the two operands are equal, we know the
1709 if (rtx_equal_p (op0, op1)
1710 && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1711 || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math))
1712 equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0;
1714 /* If the operands are floating-point constants, see if we can fold
1716 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1717 else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
1718 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
1720 struct cfc_args args;
1722 /* Setup input for check_fold_consts() */
1726 if (do_float_handler(check_fold_consts, (PTR) &args) == 0)
1727 /* We got an exception from check_fold_consts() */
1730 /* Receive output from check_fold_consts() */
1732 op0lt = op0ltu = args.op0lt;
1733 op1lt = op1ltu = args.op1lt;
1735 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1737 /* Otherwise, see if the operands are both integers. */
1738 else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode)
1739 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
1740 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
1742 int width = GET_MODE_BITSIZE (mode);
1743 HOST_WIDE_INT l0s, h0s, l1s, h1s;
1744 unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u;
1746 /* Get the two words comprising each integer constant. */
1747 if (GET_CODE (op0) == CONST_DOUBLE)
1749 l0u = l0s = CONST_DOUBLE_LOW (op0);
1750 h0u = h0s = CONST_DOUBLE_HIGH (op0);
1754 l0u = l0s = INTVAL (op0);
1755 h0u = h0s = l0s < 0 ? -1 : 0;
1758 if (GET_CODE (op1) == CONST_DOUBLE)
1760 l1u = l1s = CONST_DOUBLE_LOW (op1);
1761 h1u = h1s = CONST_DOUBLE_HIGH (op1);
1765 l1u = l1s = INTVAL (op1);
1766 h1u = h1s = l1s < 0 ? -1 : 0;
1769 /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT,
1770 we have to sign or zero-extend the values. */
1771 if (width != 0 && width <= HOST_BITS_PER_WIDE_INT)
1772 h0u = h1u = 0, h0s = l0s < 0 ? -1 : 0, h1s = l1s < 0 ? -1 : 0;
1774 if (width != 0 && width < HOST_BITS_PER_WIDE_INT)
1776 l0u &= ((HOST_WIDE_INT) 1 << width) - 1;
1777 l1u &= ((HOST_WIDE_INT) 1 << width) - 1;
1779 if (l0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1780 l0s |= ((HOST_WIDE_INT) (-1) << width);
1782 if (l1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1783 l1s |= ((HOST_WIDE_INT) (-1) << width);
1786 equal = (h0u == h1u && l0u == l1u);
1787 op0lt = (h0s < h1s || (h0s == h1s && l0s < l1s));
1788 op1lt = (h1s < h0s || (h1s == h0s && l1s < l0s));
1789 op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u));
1790 op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u));
1793 /* Otherwise, there are some code-specific tests we can make. */
1799 /* References to the frame plus a constant or labels cannot
1800 be zero, but a SYMBOL_REF can due to #pragma weak. */
1801 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1802 || GET_CODE (op0) == LABEL_REF)
1803 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1804 /* On some machines, the ap reg can be 0 sometimes. */
1805 && op0 != arg_pointer_rtx
1812 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1813 || GET_CODE (op0) == LABEL_REF)
1814 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1815 && op0 != arg_pointer_rtx
1818 return const_true_rtx;
1822 /* Unsigned values are never negative. */
1823 if (op1 == const0_rtx)
1824 return const_true_rtx;
1828 if (op1 == const0_rtx)
1833 /* Unsigned values are never greater than the largest
1835 if (GET_CODE (op1) == CONST_INT
1836 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1837 && INTEGRAL_MODE_P (mode))
1838 return const_true_rtx;
1842 if (GET_CODE (op1) == CONST_INT
1843 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1844 && INTEGRAL_MODE_P (mode))
1855 /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set
1860 return equal ? const_true_rtx : const0_rtx;
1862 return ! equal ? const_true_rtx : const0_rtx;
1864 return op0lt ? const_true_rtx : const0_rtx;
1866 return op1lt ? const_true_rtx : const0_rtx;
1868 return op0ltu ? const_true_rtx : const0_rtx;
1870 return op1ltu ? const_true_rtx : const0_rtx;
1872 return equal || op0lt ? const_true_rtx : const0_rtx;
1874 return equal || op1lt ? const_true_rtx : const0_rtx;
1876 return equal || op0ltu ? const_true_rtx : const0_rtx;
1878 return equal || op1ltu ? const_true_rtx : const0_rtx;
1884 /* Simplify CODE, an operation with result mode MODE and three operands,
1885 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
1886 a constant. Return 0 if no simplifications is possible. */
1889 simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
1891 enum machine_mode mode, op0_mode;
1894 unsigned int width = GET_MODE_BITSIZE (mode);
1896 /* VOIDmode means "infinite" precision. */
1898 width = HOST_BITS_PER_WIDE_INT;
1904 if (GET_CODE (op0) == CONST_INT
1905 && GET_CODE (op1) == CONST_INT
1906 && GET_CODE (op2) == CONST_INT
1907 && INTVAL (op1) + INTVAL (op2) <= GET_MODE_BITSIZE (op0_mode)
1908 && width <= HOST_BITS_PER_WIDE_INT)
1910 /* Extracting a bit-field from a constant */
1911 HOST_WIDE_INT val = INTVAL (op0);
1913 if (BITS_BIG_ENDIAN)
1914 val >>= (GET_MODE_BITSIZE (op0_mode)
1915 - INTVAL (op2) - INTVAL (op1));
1917 val >>= INTVAL (op2);
1919 if (HOST_BITS_PER_WIDE_INT != INTVAL (op1))
1921 /* First zero-extend. */
1922 val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1;
1923 /* If desired, propagate sign bit. */
1924 if (code == SIGN_EXTRACT
1925 && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1))))
1926 val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1);
1929 /* Clear the bits that don't belong in our mode,
1930 unless they and our sign bit are all one.
1931 So we get either a reasonable negative value or a reasonable
1932 unsigned value for this mode. */
1933 if (width < HOST_BITS_PER_WIDE_INT
1934 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
1935 != ((HOST_WIDE_INT) (-1) << (width - 1))))
1936 val &= ((HOST_WIDE_INT) 1 << width) - 1;
1938 return GEN_INT (val);
1943 if (GET_CODE (op0) == CONST_INT)
1944 return op0 != const0_rtx ? op1 : op2;
1946 /* Convert a == b ? b : a to "a". */
1947 if (GET_CODE (op0) == NE && ! side_effects_p (op0)
1948 && rtx_equal_p (XEXP (op0, 0), op1)
1949 && rtx_equal_p (XEXP (op0, 1), op2))
1951 else if (GET_CODE (op0) == EQ && ! side_effects_p (op0)
1952 && rtx_equal_p (XEXP (op0, 1), op1)
1953 && rtx_equal_p (XEXP (op0, 0), op2))
1955 else if (GET_RTX_CLASS (GET_CODE (op0)) == '<' && ! side_effects_p (op0))
1958 = simplify_relational_operation (GET_CODE (op0), op0_mode,
1959 XEXP (op0, 0), XEXP (op0, 1));
1961 /* See if any simplifications were possible. */
1962 if (temp == const0_rtx)
1964 else if (temp == const1_rtx)
1976 /* Simplify X, an rtx expression.
1978 Return the simplified expression or NULL if no simplifications
1981 This is the preferred entry point into the simplification routines;
1982 however, we still allow passes to call the more specific routines.
1984 Right now GCC has three (yes, three) major bodies of RTL simplficiation
1985 code that need to be unified.
1987 1. fold_rtx in cse.c. This code uses various CSE specific
1988 information to aid in RTL simplification.
1990 2. simplify_rtx in combine.c. Similar to fold_rtx, except that
1991 it uses combine specific information to aid in RTL
1994 3. The routines in this file.
1997 Long term we want to only have one body of simplification code; to
1998 get to that state I recommend the following steps:
2000 1. Pour over fold_rtx & simplify_rtx and move any simplifications
2001 which are not pass dependent state into these routines.
2003 2. As code is moved by #1, change fold_rtx & simplify_rtx to
2004 use this routine whenever possible.
2006 3. Allow for pass dependent state to be provided to these
2007 routines and add simplifications based on the pass dependent
2008 state. Remove code from cse.c & combine.c that becomes
2011 It will take time, but ultimately the compiler will be easier to
2012 maintain and improve. It's totally silly that when we add a
2013 simplification that it needs to be added to 4 places (3 for RTL
2014 simplification and 1 for tree simplification. */
2021 enum machine_mode mode;
2023 mode = GET_MODE (x);
2024 code = GET_CODE (x);
2026 switch (GET_RTX_CLASS (code))
2029 return simplify_unary_operation (code, mode,
2030 XEXP (x, 0), GET_MODE (XEXP (x, 0)));
2033 return simplify_binary_operation (code, mode, XEXP (x, 0), XEXP (x, 1));
2037 return simplify_ternary_operation (code, mode, GET_MODE (XEXP (x, 0)),
2038 XEXP (x, 0), XEXP (x, 1), XEXP (x, 2));
2041 return simplify_relational_operation (code, GET_MODE (XEXP (x, 0)),
2042 XEXP (x, 0), XEXP (x, 1));
2049 /* Allocate a struct elt_list and fill in its two elements with the
2052 static struct elt_list *
2053 new_elt_list (next, elt)
2054 struct elt_list *next;
2057 struct elt_list *el = empty_elt_lists;
2060 empty_elt_lists = el->next;
2062 el = (struct elt_list *) obstack_alloc (&cselib_obstack,
2063 sizeof (struct elt_list));
2069 /* Allocate a struct elt_loc_list and fill in its two elements with the
2072 static struct elt_loc_list *
2073 new_elt_loc_list (next, loc)
2074 struct elt_loc_list *next;
2077 struct elt_loc_list *el = empty_elt_loc_lists;
2080 empty_elt_loc_lists = el->next;
2082 el = (struct elt_loc_list *) obstack_alloc (&cselib_obstack,
2083 sizeof (struct elt_loc_list));
2086 el->setting_insn = cselib_current_insn;
2090 /* The elt_list at *PL is no longer needed. Unchain it and free its
2094 unchain_one_elt_list (pl)
2095 struct elt_list **pl;
2097 struct elt_list *l = *pl;
2100 l->next = empty_elt_lists;
2101 empty_elt_lists = l;
2104 /* Likewise for elt_loc_lists. */
2107 unchain_one_elt_loc_list (pl)
2108 struct elt_loc_list **pl;
2110 struct elt_loc_list *l = *pl;
2113 l->next = empty_elt_loc_lists;
2114 empty_elt_loc_lists = l;
2117 /* Likewise for cselib_vals. This also frees the addr_list associated with
2121 unchain_one_value (v)
2124 while (v->addr_list)
2125 unchain_one_elt_list (&v->addr_list);
2127 v->u.next_free = empty_vals;
2131 /* Remove all entries from the hash table. Also used during
2139 for (i = 0; i < cselib_nregs; i++)
2142 htab_empty (hash_table);
2143 obstack_free (&cselib_obstack, cselib_startobj);
2146 empty_elt_lists = 0;
2147 empty_elt_loc_lists = 0;
2148 n_useless_values = 0;
2150 next_unknown_value = 0;
2153 /* The equality test for our hash table. The first argument ENTRY is a table
2154 element (i.e. a cselib_val), while the second arg X is an rtx. */
2157 entry_and_rtx_equal_p (entry, x_arg)
2158 const void *entry, *x_arg;
2160 struct elt_loc_list *l;
2161 const cselib_val *v = (const cselib_val *) entry;
2162 rtx x = (rtx) x_arg;
2164 /* We don't guarantee that distinct rtx's have different hash values,
2165 so we need to do a comparison. */
2166 for (l = v->locs; l; l = l->next)
2167 if (rtx_equal_for_cselib_p (l->loc, x))
2173 /* The hash function for our hash table. The value is always computed with
2174 hash_rtx when adding an element; this function just extracts the hash
2175 value from a cselib_val structure. */
2178 get_value_hash (entry)
2181 const cselib_val *v = (const cselib_val *) entry;
2185 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
2186 only return true for values which point to a cselib_val whose value
2187 element has been set to zero, which implies the cselib_val will be
2191 references_value_p (x, only_useless)
2195 enum rtx_code code = GET_CODE (x);
2196 const char *fmt = GET_RTX_FORMAT (code);
2199 if (GET_CODE (x) == VALUE
2200 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
2203 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2205 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
2207 else if (fmt[i] == 'E')
2208 for (j = 0; j < XVECLEN (x, i); j++)
2209 if (references_value_p (XVECEXP (x, i, j), only_useless))
2216 /* For all locations found in X, delete locations that reference useless
2217 values (i.e. values without any location). Called through
2221 discard_useless_locs (x, info)
2223 void *info ATTRIBUTE_UNUSED;
2225 cselib_val *v = (cselib_val *)*x;
2226 struct elt_loc_list **p = &v->locs;
2227 int had_locs = v->locs != 0;
2231 if (references_value_p ((*p)->loc, 1))
2232 unchain_one_elt_loc_list (p);
2237 if (had_locs && v->locs == 0)
2240 values_became_useless = 1;
2245 /* If X is a value with no locations, remove it from the hashtable. */
2248 discard_useless_values (x, info)
2250 void *info ATTRIBUTE_UNUSED;
2252 cselib_val *v = (cselib_val *)*x;
2256 htab_clear_slot (hash_table, x);
2257 unchain_one_value (v);
2264 /* Clean out useless values (i.e. those which no longer have locations
2265 associated with them) from the hash table. */
2268 remove_useless_values ()
2270 /* First pass: eliminate locations that reference the value. That in
2271 turn can make more values useless. */
2274 values_became_useless = 0;
2275 htab_traverse (hash_table, discard_useless_locs, 0);
2277 while (values_became_useless);
2279 /* Second pass: actually remove the values. */
2280 htab_traverse (hash_table, discard_useless_values, 0);
2282 if (n_useless_values != 0)
2286 /* Return nonzero if we can prove that X and Y contain the same value, taking
2287 our gathered information into account. */
2290 rtx_equal_for_cselib_p (x, y)
2297 if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
2299 cselib_val *e = cselib_lookup (x, VOIDmode, 0);
2305 if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
2307 cselib_val *e = cselib_lookup (y, VOIDmode, 0);
2316 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
2317 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
2319 if (GET_CODE (x) == VALUE)
2321 cselib_val *e = CSELIB_VAL_PTR (x);
2322 struct elt_loc_list *l;
2324 for (l = e->locs; l; l = l->next)
2328 /* Avoid infinite recursion. */
2329 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2331 else if (rtx_equal_for_cselib_p (t, y))
2338 if (GET_CODE (y) == VALUE)
2340 cselib_val *e = CSELIB_VAL_PTR (y);
2341 struct elt_loc_list *l;
2343 for (l = e->locs; l; l = l->next)
2347 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2349 else if (rtx_equal_for_cselib_p (x, t))
2356 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
2359 /* This won't be handled correctly by the code below. */
2360 if (GET_CODE (x) == LABEL_REF)
2361 return XEXP (x, 0) == XEXP (y, 0);
2363 code = GET_CODE (x);
2364 fmt = GET_RTX_FORMAT (code);
2366 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2373 if (XWINT (x, i) != XWINT (y, i))
2379 if (XINT (x, i) != XINT (y, i))
2385 /* Two vectors must have the same length. */
2386 if (XVECLEN (x, i) != XVECLEN (y, i))
2389 /* And the corresponding elements must match. */
2390 for (j = 0; j < XVECLEN (x, i); j++)
2391 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
2397 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
2403 if (strcmp (XSTR (x, i), XSTR (y, i)))
2408 /* These are just backpointers, so they don't matter. */
2415 /* It is believed that rtx's at this level will never
2416 contain anything but integers and other rtx's,
2417 except for within LABEL_REFs and SYMBOL_REFs. */
2425 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
2426 For registers and memory locations, we look up their cselib_val structure
2427 and return its VALUE element.
2428 Possible reasons for return 0 are: the object is volatile, or we couldn't
2429 find a register or memory location in the table and CREATE is zero. If
2430 CREATE is nonzero, table elts are created for regs and mem.
2431 MODE is used in hashing for CONST_INTs only;
2432 otherwise the mode of X is used. */
2435 hash_rtx (x, mode, create)
2437 enum machine_mode mode;
2444 unsigned int hash = 0;
2446 /* repeat is used to turn tail-recursion into iteration. */
2448 code = GET_CODE (x);
2449 hash += (unsigned) code + (unsigned) GET_MODE (x);
2455 e = cselib_lookup (x, GET_MODE (x), create);
2463 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
2464 return hash ? hash : CONST_INT;
2467 /* This is like the general case, except that it only counts
2468 the integers representing the constant. */
2469 hash += (unsigned) code + (unsigned) GET_MODE (x);
2470 if (GET_MODE (x) != VOIDmode)
2471 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2472 hash += XWINT (x, i);
2474 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2475 + (unsigned) CONST_DOUBLE_HIGH (x));
2476 return hash ? hash : CONST_DOUBLE;
2478 /* Assume there is only one rtx object for any given label. */
2481 += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2482 return hash ? hash : LABEL_REF;
2486 += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2487 return hash ? hash : SYMBOL_REF;
2496 case UNSPEC_VOLATILE:
2500 if (MEM_VOLATILE_P (x))
2509 i = GET_RTX_LENGTH (code) - 1;
2510 fmt = GET_RTX_FORMAT (code);
2515 rtx tem = XEXP (x, i);
2516 unsigned int tem_hash;
2518 /* If we are about to do the last recursive call
2519 needed at this level, change it into iteration.
2520 This function is called enough to be worth it. */
2527 tem_hash = hash_rtx (tem, 0, create);
2533 else if (fmt[i] == 'E')
2534 for (j = 0; j < XVECLEN (x, i); j++)
2536 unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
2543 else if (fmt[i] == 's')
2545 const unsigned char *p = (const unsigned char *) XSTR (x, i);
2551 else if (fmt[i] == 'i')
2552 hash += XINT (x, i);
2553 else if (fmt[i] == '0' || fmt[i] == 't')
2559 return hash ? hash : 1 + GET_CODE (x);
2562 /* Create a new value structure for VALUE and initialize it. The mode of the
2566 new_cselib_val (value, mode)
2568 enum machine_mode mode;
2570 cselib_val *e = empty_vals;
2573 empty_vals = e->u.next_free;
2575 e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
2581 e->u.val_rtx = gen_rtx_VALUE (mode);
2582 CSELIB_VAL_PTR (e->u.val_rtx) = e;
2588 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
2589 contains the data at this address. X is a MEM that represents the
2590 value. Update the two value structures to represent this situation. */
2593 add_mem_for_addr (addr_elt, mem_elt, x)
2594 cselib_val *addr_elt, *mem_elt;
2598 struct elt_loc_list *l;
2600 /* Avoid duplicates. */
2601 for (l = mem_elt->locs; l; l = l->next)
2602 if (GET_CODE (l->loc) == MEM
2603 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
2606 new = gen_rtx_MEM (GET_MODE (x), addr_elt->u.val_rtx);
2607 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
2609 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
2610 MEM_COPY_ATTRIBUTES (new, x);
2612 mem_elt->locs = new_elt_loc_list (mem_elt->locs, new);
2615 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
2616 If CREATE, make a new one if we haven't seen it before. */
2619 cselib_lookup_mem (x, create)
2625 cselib_val *mem_elt;
2628 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode
2629 || (FLOAT_MODE_P (GET_MODE (x)) && flag_float_store))
2632 /* Look up the value for the address. */
2633 addr = cselib_lookup (XEXP (x, 0), GET_MODE (x), create);
2637 /* Find a value that describes a value of our mode at that address. */
2638 for (l = addr->addr_list; l; l = l->next)
2639 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2645 mem_elt = new_cselib_val (++next_unknown_value, GET_MODE (x));
2646 add_mem_for_addr (addr, mem_elt, x);
2647 slot = htab_find_slot_with_hash (hash_table, x, mem_elt->value, INSERT);
2652 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2653 with VALUE expressions. This way, it becomes independent of changes
2654 to registers and memory.
2655 X isn't actually modified; if modifications are needed, new rtl is
2656 allocated. However, the return value can share rtl with X. */
2659 cselib_subst_to_values (x)
2662 enum rtx_code code = GET_CODE (x);
2663 const char *fmt = GET_RTX_FORMAT (code);
2672 for (l = REG_VALUES (REGNO (x)); l; l = l->next)
2673 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2674 return l->elt->u.val_rtx;
2679 e = cselib_lookup_mem (x, 0);
2682 return e->u.val_rtx;
2684 /* CONST_DOUBLEs must be special-cased here so that we won't try to
2685 look up the CONST_DOUBLE_MEM inside. */
2694 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2698 rtx t = cselib_subst_to_values (XEXP (x, i));
2700 if (t != XEXP (x, i) && x == copy)
2701 copy = shallow_copy_rtx (x);
2705 else if (fmt[i] == 'E')
2709 for (j = 0; j < XVECLEN (x, i); j++)
2711 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
2713 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
2716 copy = shallow_copy_rtx (x);
2718 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
2719 for (k = 0; k < j; k++)
2720 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
2723 XVECEXP (copy, i, j) = t;
2731 /* Look up the rtl expression X in our tables and return the value it has.
2732 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
2733 we create a new one if possible, using mode MODE if X doesn't have a mode
2734 (i.e. because it's a constant). */
2737 cselib_lookup (x, mode, create)
2739 enum machine_mode mode;
2744 unsigned int hashval;
2746 if (GET_MODE (x) != VOIDmode)
2747 mode = GET_MODE (x);
2749 if (GET_CODE (x) == VALUE)
2750 return CSELIB_VAL_PTR (x);
2752 if (GET_CODE (x) == REG)
2755 unsigned int i = REGNO (x);
2757 for (l = REG_VALUES (i); l; l = l->next)
2758 if (mode == GET_MODE (l->elt->u.val_rtx))
2764 e = new_cselib_val (++next_unknown_value, GET_MODE (x));
2765 e->locs = new_elt_loc_list (e->locs, x);
2766 REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
2767 slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
2772 if (GET_CODE (x) == MEM)
2773 return cselib_lookup_mem (x, create);
2775 hashval = hash_rtx (x, mode, create);
2776 /* Can't even create if hashing is not possible. */
2780 slot = htab_find_slot_with_hash (hash_table, x, hashval,
2781 create ? INSERT : NO_INSERT);
2785 e = (cselib_val *) *slot;
2789 e = new_cselib_val (hashval, mode);
2791 /* We have to fill the slot before calling cselib_subst_to_values:
2792 the hash table is inconsistent until we do so, and
2793 cselib_subst_to_values will need to do lookups. */
2795 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
2799 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2800 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2801 is used to determine how many hard registers are being changed. If MODE
2802 is VOIDmode, then only REGNO is being changed; this is used when
2803 invalidating call clobbered registers across a call. */
2806 cselib_invalidate_regno (regno, mode)
2808 enum machine_mode mode;
2810 unsigned int endregno;
2813 /* If we see pseudos after reload, something is _wrong_. */
2814 if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
2815 && reg_renumber[regno] >= 0)
2818 /* Determine the range of registers that must be invalidated. For
2819 pseudos, only REGNO is affected. For hard regs, we must take MODE
2820 into account, and we must also invalidate lower register numbers
2821 if they contain values that overlap REGNO. */
2822 endregno = regno + 1;
2823 if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode)
2824 endregno = regno + HARD_REGNO_NREGS (regno, mode);
2826 for (i = 0; i < endregno; i++)
2828 struct elt_list **l = ®_VALUES (i);
2830 /* Go through all known values for this reg; if it overlaps the range
2831 we're invalidating, remove the value. */
2834 cselib_val *v = (*l)->elt;
2835 struct elt_loc_list **p;
2836 unsigned int this_last = i;
2838 if (i < FIRST_PSEUDO_REGISTER)
2839 this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
2841 if (this_last < regno)
2847 /* We have an overlap. */
2848 unchain_one_elt_list (l);
2850 /* Now, we clear the mapping from value to reg. It must exist, so
2851 this code will crash intentionally if it doesn't. */
2852 for (p = &v->locs; ; p = &(*p)->next)
2856 if (GET_CODE (x) == REG && REGNO (x) == i)
2858 unchain_one_elt_loc_list (p);
2868 /* The memory at address MEM_BASE is being changed.
2869 Return whether this change will invalidate VAL. */
2872 cselib_mem_conflict_p (mem_base, val)
2880 code = GET_CODE (val);
2883 /* Get rid of a few simple cases quickly. */
2896 if (GET_MODE (mem_base) == BLKmode
2897 || GET_MODE (val) == BLKmode
2898 || anti_dependence (val, mem_base))
2901 /* The address may contain nested MEMs. */
2908 fmt = GET_RTX_FORMAT (code);
2909 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2913 if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
2916 else if (fmt[i] == 'E')
2917 for (j = 0; j < XVECLEN (val, i); j++)
2918 if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
2925 /* For the value found in SLOT, walk its locations to determine if any overlap
2926 INFO (which is a MEM rtx). */
2929 cselib_invalidate_mem_1 (slot, info)
2933 cselib_val *v = (cselib_val *) *slot;
2934 rtx mem_rtx = (rtx) info;
2935 struct elt_loc_list **p = &v->locs;
2936 int had_locs = v->locs != 0;
2942 struct elt_list **mem_chain;
2944 /* MEMs may occur in locations only at the top level; below
2945 that every MEM or REG is substituted by its VALUE. */
2946 if (GET_CODE (x) != MEM
2947 || ! cselib_mem_conflict_p (mem_rtx, x))
2953 /* This one overlaps. */
2954 /* We must have a mapping from this MEM's address to the
2955 value (E). Remove that, too. */
2956 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
2957 mem_chain = &addr->addr_list;
2960 if ((*mem_chain)->elt == v)
2962 unchain_one_elt_list (mem_chain);
2966 mem_chain = &(*mem_chain)->next;
2969 unchain_one_elt_loc_list (p);
2972 if (had_locs && v->locs == 0)
2978 /* Invalidate any locations in the table which are changed because of a
2979 store to MEM_RTX. If this is called because of a non-const call
2980 instruction, MEM_RTX is (mem:BLK const0_rtx). */
2983 cselib_invalidate_mem (mem_rtx)
2986 htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
2989 /* Invalidate DEST, which is being assigned to or clobbered. The second and
2990 the third parameter exist so that this function can be passed to
2991 note_stores; they are ignored. */
2994 cselib_invalidate_rtx (dest, ignore, data)
2996 rtx ignore ATTRIBUTE_UNUSED;
2997 void *data ATTRIBUTE_UNUSED;
2999 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
3000 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
3001 dest = XEXP (dest, 0);
3003 if (GET_CODE (dest) == REG)
3004 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
3005 else if (GET_CODE (dest) == MEM)
3006 cselib_invalidate_mem (dest);
3008 /* Some machines don't define AUTO_INC_DEC, but they still use push
3009 instructions. We need to catch that case here in order to
3010 invalidate the stack pointer correctly. Note that invalidating
3011 the stack pointer is different from invalidating DEST. */
3012 if (push_operand (dest, GET_MODE (dest)))
3013 cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
3016 /* Record the result of a SET instruction. DEST is being set; the source
3017 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
3018 describes its address. */
3021 cselib_record_set (dest, src_elt, dest_addr_elt)
3023 cselib_val *src_elt, *dest_addr_elt;
3025 int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
3027 if (src_elt == 0 || side_effects_p (dest))
3032 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
3033 if (src_elt->locs == 0)
3035 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
3037 else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
3039 if (src_elt->locs == 0)
3041 add_mem_for_addr (dest_addr_elt, src_elt, dest);
3045 /* Describe a single set that is part of an insn. */
3050 cselib_val *src_elt;
3051 cselib_val *dest_addr_elt;
3054 /* There is no good way to determine how many elements there can be
3055 in a PARALLEL. Since it's fairly cheap, use a really large number. */
3056 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
3058 /* Record the effects of any sets in INSN. */
3060 cselib_record_sets (insn)
3065 struct set sets[MAX_SETS];
3066 rtx body = PATTERN (insn);
3068 body = PATTERN (insn);
3069 /* Find all sets. */
3070 if (GET_CODE (body) == SET)
3072 sets[0].src = SET_SRC (body);
3073 sets[0].dest = SET_DEST (body);
3076 else if (GET_CODE (body) == PARALLEL)
3078 /* Look through the PARALLEL and record the values being
3079 set, if possible. Also handle any CLOBBERs. */
3080 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3082 rtx x = XVECEXP (body, 0, i);
3084 if (GET_CODE (x) == SET)
3086 sets[n_sets].src = SET_SRC (x);
3087 sets[n_sets].dest = SET_DEST (x);
3093 /* Look up the values that are read. Do this before invalidating the
3094 locations that are written. */
3095 for (i = 0; i < n_sets; i++)
3097 sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (sets[i].dest),
3099 if (GET_CODE (sets[i].dest) == MEM)
3100 sets[i].dest_addr_elt = cselib_lookup (XEXP (sets[i].dest, 0), Pmode,
3103 sets[i].dest_addr_elt = 0;
3106 /* Invalidate all locations written by this insn. Note that the elts we
3107 looked up in the previous loop aren't affected, just some of their
3108 locations may go away. */
3109 note_stores (body, cselib_invalidate_rtx, NULL);
3111 /* Now enter the equivalences in our tables. */
3112 for (i = 0; i < n_sets; i++)
3113 cselib_record_set (sets[i].dest, sets[i].src_elt, sets[i].dest_addr_elt);
3116 /* Record the effects of INSN. */
3119 cselib_process_insn (insn)
3125 cselib_current_insn = insn;
3127 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
3128 if (GET_CODE (insn) == CODE_LABEL
3129 || (GET_CODE (insn) == NOTE
3130 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3131 || (GET_CODE (insn) == INSN
3132 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
3133 && MEM_VOLATILE_P (PATTERN (insn))))
3139 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3141 cselib_current_insn = 0;
3145 /* If this is a call instruction, forget anything stored in a
3146 call clobbered register, or, if this is not a const call, in
3148 if (GET_CODE (insn) == CALL_INSN)
3150 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3151 if (call_used_regs[i])
3152 cselib_invalidate_regno (i, VOIDmode);
3154 if (! CONST_CALL_P (insn))
3155 cselib_invalidate_mem (callmem);
3158 cselib_record_sets (insn);
3161 /* Clobber any registers which appear in REG_INC notes. We
3162 could keep track of the changes to their values, but it is
3163 unlikely to help. */
3164 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
3165 if (REG_NOTE_KIND (x) == REG_INC)
3166 cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
3169 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3170 after we have processed the insn. */
3171 if (GET_CODE (insn) == CALL_INSN)
3172 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3173 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3174 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
3176 cselib_current_insn = 0;
3178 if (n_useless_values > MAX_USELESS_VALUES)
3179 remove_useless_values ();
3182 /* Make sure our varrays are big enough. Not called from any cselib routines;
3183 it must be called by the user if it allocated new registers. */
3186 cselib_update_varray_sizes ()
3188 unsigned int nregs = max_reg_num ();
3190 if (nregs == cselib_nregs)
3193 cselib_nregs = nregs;
3194 VARRAY_GROW (reg_values, nregs);
3197 /* Initialize cselib for one pass. The caller must also call
3198 init_alias_analysis. */
3203 /* These are only created once. */
3206 extern struct obstack permanent_obstack;
3208 gcc_obstack_init (&cselib_obstack);
3209 cselib_startobj = obstack_alloc (&cselib_obstack, 0);
3211 push_obstacks (&permanent_obstack, &permanent_obstack);
3212 callmem = gen_rtx_MEM (BLKmode, const0_rtx);
3214 ggc_add_rtx_root (&callmem, 1);
3217 cselib_nregs = max_reg_num ();
3218 VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
3219 hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
3223 /* Called when the current user is done with cselib. */
3229 htab_delete (hash_table);