?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update version
[official-gcc.git] / gcc / simplify-rtx.c
blob0bb071023fc5a7ece508de1cfaa1221f5f3a3d70
1 /* RTL simplification functions for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
4
5 This file is part of GNU CC.
6
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)
10 any later version.
11
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.
16
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. */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include <setjmp.h>
26
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "regs.h"
30 #include "hard-reg-set.h"
31 #include "flags.h"
32 #include "real.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "function.h"
36 #include "expr.h"
37 #include "toplev.h"
38 #include "output.h"
39 #include "ggc.h"
40 #include "obstack.h"
41 #include "hashtab.h"
42 #include "cselib.h"
43
44 /* Simplification and canonicalization of RTL. */
45
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.
49
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. */
54
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)
68
69 /* Similar, but also allows reference to the stack pointer.
70
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. */
74
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)
94
95 /* Much code operates on (low, high) pairs; the low value is an
96 unsigned wide int, the high value a signed wide int. We
97 occasionally need to sign extend from low to high as if low were a
98 signed wide int. */
99 #define HWI_SIGN_EXTEND(low) \
100 ((((HOST_WIDE_INT) low) < 0) ? ((HOST_WIDE_INT) -1) : ((HOST_WIDE_INT) 0))
101
102 static rtx simplify_plus_minus PARAMS ((enum rtx_code,
103 enum machine_mode, rtx, rtx));
104 static void check_fold_consts PARAMS ((PTR));
105 static int entry_and_rtx_equal_p PARAMS ((const void *, const void *));
106 static unsigned int get_value_hash PARAMS ((const void *));
107 static struct elt_list *new_elt_list PARAMS ((struct elt_list *,
108 cselib_val *));
109 static struct elt_loc_list *new_elt_loc_list PARAMS ((struct elt_loc_list *,
110 rtx));
111 static void unchain_one_value PARAMS ((cselib_val *));
112 static void unchain_one_elt_list PARAMS ((struct elt_list **));
113 static void unchain_one_elt_loc_list PARAMS ((struct elt_loc_list **));
114 static void clear_table PARAMS ((int));
115 static int discard_useless_locs PARAMS ((void **, void *));
116 static int discard_useless_values PARAMS ((void **, void *));
117 static void remove_useless_values PARAMS ((void));
118 static rtx wrap_constant PARAMS ((enum machine_mode, rtx));
119 static unsigned int hash_rtx PARAMS ((rtx, enum machine_mode, int));
120 static cselib_val *new_cselib_val PARAMS ((unsigned int,
121 enum machine_mode));
122 static void add_mem_for_addr PARAMS ((cselib_val *, cselib_val *,
123 rtx));
124 static cselib_val *cselib_lookup_mem PARAMS ((rtx, int));
125 static rtx cselib_subst_to_values PARAMS ((rtx));
126 static void cselib_invalidate_regno PARAMS ((unsigned int,
127 enum machine_mode));
128 static int cselib_mem_conflict_p PARAMS ((rtx, rtx));
129 static int cselib_invalidate_mem_1 PARAMS ((void **, void *));
130 static void cselib_invalidate_mem PARAMS ((rtx));
131 static void cselib_invalidate_rtx PARAMS ((rtx, rtx, void *));
132 static void cselib_record_set PARAMS ((rtx, cselib_val *,
133 cselib_val *));
134 static void cselib_record_sets PARAMS ((rtx));
135
136 /* There are three ways in which cselib can look up an rtx:
137 - for a REG, the reg_values table (which is indexed by regno) is used
138 - for a MEM, we recursively look up its address and then follow the
139 addr_list of that value
140 - for everything else, we compute a hash value and go through the hash
141 table. Since different rtx's can still have the same hash value,
142 this involves walking the table entries for a given value and comparing
143 the locations of the entries with the rtx we are looking up. */
144
145 /* A table that enables us to look up elts by their value. */
146 static htab_t hash_table;
147
148 /* This is a global so we don't have to pass this through every function.
149 It is used in new_elt_loc_list to set SETTING_INSN. */
150 static rtx cselib_current_insn;
151
152 /* Every new unknown value gets a unique number. */
153 static unsigned int next_unknown_value;
154
155 /* The number of registers we had when the varrays were last resized. */
156 static unsigned int cselib_nregs;
157
158 /* Count values without known locations. Whenever this grows too big, we
159 remove these useless values from the table. */
160 static int n_useless_values;
161
162 /* Number of useless values before we remove them from the hash table. */
163 #define MAX_USELESS_VALUES 32
164
165 /* This table maps from register number to values. It does not contain
166 pointers to cselib_val structures, but rather elt_lists. The purpose is
167 to be able to refer to the same register in different modes. */
168 static varray_type reg_values;
169 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
170
171 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
172 in clear_table() for fast emptying. */
173 static varray_type used_regs;
174
175 /* We pass this to cselib_invalidate_mem to invalidate all of
176 memory for a non-const call instruction. */
177 static rtx callmem;
178
179 /* Memory for our structures is allocated from this obstack. */
180 static struct obstack cselib_obstack;
181
182 /* Used to quickly free all memory. */
183 static char *cselib_startobj;
184
185 /* Caches for unused structures. */
186 static cselib_val *empty_vals;
187 static struct elt_list *empty_elt_lists;
188 static struct elt_loc_list *empty_elt_loc_lists;
189
190 /* Set by discard_useless_locs if it deleted the last location of any
191 value. */
192 static int values_became_useless;
193 \f
194 /* Make a binary operation by properly ordering the operands and
195 seeing if the expression folds. */
196
197 rtx
198 simplify_gen_binary (code, mode, op0, op1)
199 enum rtx_code code;
200 enum machine_mode mode;
201 rtx op0, op1;
202 {
203 rtx tem;
204
205 /* Put complex operands first and constants second if commutative. */
206 if (GET_RTX_CLASS (code) == 'c'
207 && ((CONSTANT_P (op0) && GET_CODE (op1) != CONST_INT)
208 || (GET_RTX_CLASS (GET_CODE (op0)) == 'o'
209 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')
210 || (GET_CODE (op0) == SUBREG
211 && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op0))) == 'o'
212 && GET_RTX_CLASS (GET_CODE (op1)) != 'o')))
213 tem = op0, op0 = op1, op1 = tem;
214
215 /* If this simplifies, do it. */
216 tem = simplify_binary_operation (code, mode, op0, op1);
217
218 if (tem)
219 return tem;
220
221 /* Handle addition and subtraction of CONST_INT specially. Otherwise,
222 just form the operation. */
223
224 if (code == PLUS && GET_CODE (op1) == CONST_INT
225 && GET_MODE (op0) != VOIDmode)
226 return plus_constant (op0, INTVAL (op1));
227 else if (code == MINUS && GET_CODE (op1) == CONST_INT
228 && GET_MODE (op0) != VOIDmode)
229 return plus_constant (op0, - INTVAL (op1));
230 else
231 return gen_rtx_fmt_ee (code, mode, op0, op1);
232 }
233 \f
234 /* Try to simplify a unary operation CODE whose output mode is to be
235 MODE with input operand OP whose mode was originally OP_MODE.
236 Return zero if no simplification can be made. */
237
238 rtx
239 simplify_unary_operation (code, mode, op, op_mode)
240 enum rtx_code code;
241 enum machine_mode mode;
242 rtx op;
243 enum machine_mode op_mode;
244 {
245 unsigned int width = GET_MODE_BITSIZE (mode);
246
247 /* The order of these tests is critical so that, for example, we don't
248 check the wrong mode (input vs. output) for a conversion operation,
249 such as FIX. At some point, this should be simplified. */
250
251 #if !defined(REAL_IS_NOT_DOUBLE) || defined(REAL_ARITHMETIC)
252
253 if (code == FLOAT && GET_MODE (op) == VOIDmode
254 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
255 {
256 HOST_WIDE_INT hv, lv;
257 REAL_VALUE_TYPE d;
258
259 if (GET_CODE (op) == CONST_INT)
260 lv = INTVAL (op), hv = HWI_SIGN_EXTEND (lv);
261 else
262 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
263
264 #ifdef REAL_ARITHMETIC
265 REAL_VALUE_FROM_INT (d, lv, hv, mode);
266 #else
267 if (hv < 0)
268 {
269 d = (double) (~ hv);
270 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
271 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
272 d += (double) (unsigned HOST_WIDE_INT) (~ lv);
273 d = (- d - 1.0);
274 }
275 else
276 {
277 d = (double) hv;
278 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
279 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
280 d += (double) (unsigned HOST_WIDE_INT) lv;
281 }
282 #endif /* REAL_ARITHMETIC */
283 d = real_value_truncate (mode, d);
284 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
285 }
286 else if (code == UNSIGNED_FLOAT && GET_MODE (op) == VOIDmode
287 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
288 {
289 HOST_WIDE_INT hv, lv;
290 REAL_VALUE_TYPE d;
291
292 if (GET_CODE (op) == CONST_INT)
293 lv = INTVAL (op), hv = HWI_SIGN_EXTEND (lv);
294 else
295 lv = CONST_DOUBLE_LOW (op), hv = CONST_DOUBLE_HIGH (op);
296
297 if (op_mode == VOIDmode)
298 {
299 /* We don't know how to interpret negative-looking numbers in
300 this case, so don't try to fold those. */
301 if (hv < 0)
302 return 0;
303 }
304 else if (GET_MODE_BITSIZE (op_mode) >= HOST_BITS_PER_WIDE_INT * 2)
305 ;
306 else
307 hv = 0, lv &= GET_MODE_MASK (op_mode);
308
309 #ifdef REAL_ARITHMETIC
310 REAL_VALUE_FROM_UNSIGNED_INT (d, lv, hv, mode);
311 #else
312
313 d = (double) (unsigned HOST_WIDE_INT) hv;
314 d *= ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
315 * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
316 d += (double) (unsigned HOST_WIDE_INT) lv;
317 #endif /* REAL_ARITHMETIC */
318 d = real_value_truncate (mode, d);
319 return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
320 }
321 #endif
322
323 if (GET_CODE (op) == CONST_INT
324 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
325 {
326 register HOST_WIDE_INT arg0 = INTVAL (op);
327 register HOST_WIDE_INT val;
328
329 switch (code)
330 {
331 case NOT:
332 val = ~ arg0;
333 break;
334
335 case NEG:
336 val = - arg0;
337 break;
338
339 case ABS:
340 val = (arg0 >= 0 ? arg0 : - arg0);
341 break;
342
343 case FFS:
344 /* Don't use ffs here. Instead, get low order bit and then its
345 number. If arg0 is zero, this will return 0, as desired. */
346 arg0 &= GET_MODE_MASK (mode);
347 val = exact_log2 (arg0 & (- arg0)) + 1;
348 break;
349
350 case TRUNCATE:
351 val = arg0;
352 break;
353
354 case ZERO_EXTEND:
355 if (op_mode == VOIDmode)
356 op_mode = mode;
357 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
358 {
359 /* If we were really extending the mode,
360 we would have to distinguish between zero-extension
361 and sign-extension. */
362 if (width != GET_MODE_BITSIZE (op_mode))
363 abort ();
364 val = arg0;
365 }
366 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
367 val = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
368 else
369 return 0;
370 break;
371
372 case SIGN_EXTEND:
373 if (op_mode == VOIDmode)
374 op_mode = mode;
375 if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_WIDE_INT)
376 {
377 /* If we were really extending the mode,
378 we would have to distinguish between zero-extension
379 and sign-extension. */
380 if (width != GET_MODE_BITSIZE (op_mode))
381 abort ();
382 val = arg0;
383 }
384 else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT)
385 {
386 val
387 = arg0 & ~((HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (op_mode));
388 if (val
389 & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (op_mode) - 1)))
390 val -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
391 }
392 else
393 return 0;
394 break;
395
396 case SQRT:
397 case FLOAT_EXTEND:
398 case FLOAT_TRUNCATE:
399 return 0;
400
401 default:
402 abort ();
403 }
404
405 val = trunc_int_for_mode (val, mode);
406
407 return GEN_INT (val);
408 }
409
410 /* We can do some operations on integer CONST_DOUBLEs. Also allow
411 for a DImode operation on a CONST_INT. */
412 else if (GET_MODE (op) == VOIDmode && width <= HOST_BITS_PER_INT * 2
413 && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
414 {
415 unsigned HOST_WIDE_INT l1, lv;
416 HOST_WIDE_INT h1, hv;
417
418 if (GET_CODE (op) == CONST_DOUBLE)
419 l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op);
420 else
421 l1 = INTVAL (op), h1 = HWI_SIGN_EXTEND (l1);
422
423 switch (code)
424 {
425 case NOT:
426 lv = ~ l1;
427 hv = ~ h1;
428 break;
429
430 case NEG:
431 neg_double (l1, h1, &lv, &hv);
432 break;
433
434 case ABS:
435 if (h1 < 0)
436 neg_double (l1, h1, &lv, &hv);
437 else
438 lv = l1, hv = h1;
439 break;
440
441 case FFS:
442 hv = 0;
443 if (l1 == 0)
444 lv = HOST_BITS_PER_WIDE_INT + exact_log2 (h1 & (-h1)) + 1;
445 else
446 lv = exact_log2 (l1 & (-l1)) + 1;
447 break;
448
449 case TRUNCATE:
450 /* This is just a change-of-mode, so do nothing. */
451 lv = l1, hv = h1;
452 break;
453
454 case ZERO_EXTEND:
455 if (op_mode == VOIDmode
456 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
457 return 0;
458
459 hv = 0;
460 lv = l1 & GET_MODE_MASK (op_mode);
461 break;
462
463 case SIGN_EXTEND:
464 if (op_mode == VOIDmode
465 || GET_MODE_BITSIZE (op_mode) > HOST_BITS_PER_WIDE_INT)
466 return 0;
467 else
468 {
469 lv = l1 & GET_MODE_MASK (op_mode);
470 if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_WIDE_INT
471 && (lv & ((HOST_WIDE_INT) 1
472 << (GET_MODE_BITSIZE (op_mode) - 1))) != 0)
473 lv -= (HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (op_mode);
474
475 hv = HWI_SIGN_EXTEND (lv);
476 }
477 break;
478
479 case SQRT:
480 return 0;
481
482 default:
483 return 0;
484 }
485
486 return immed_double_const (lv, hv, mode);
487 }
488
489 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
490 else if (GET_CODE (op) == CONST_DOUBLE
491 && GET_MODE_CLASS (mode) == MODE_FLOAT)
492 {
493 REAL_VALUE_TYPE d;
494 jmp_buf handler;
495 rtx x;
496
497 if (setjmp (handler))
498 /* There used to be a warning here, but that is inadvisable.
499 People may want to cause traps, and the natural way
500 to do it should not get a warning. */
501 return 0;
502
503 set_float_handler (handler);
504
505 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
506
507 switch (code)
508 {
509 case NEG:
510 d = REAL_VALUE_NEGATE (d);
511 break;
512
513 case ABS:
514 if (REAL_VALUE_NEGATIVE (d))
515 d = REAL_VALUE_NEGATE (d);
516 break;
517
518 case FLOAT_TRUNCATE:
519 d = real_value_truncate (mode, d);
520 break;
521
522 case FLOAT_EXTEND:
523 /* All this does is change the mode. */
524 break;
525
526 case FIX:
527 d = REAL_VALUE_RNDZINT (d);
528 break;
529
530 case UNSIGNED_FIX:
531 d = REAL_VALUE_UNSIGNED_RNDZINT (d);
532 break;
533
534 case SQRT:
535 return 0;
536
537 default:
538 abort ();
539 }
540
541 x = CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
542 set_float_handler (NULL_PTR);
543 return x;
544 }
545
546 else if (GET_CODE (op) == CONST_DOUBLE
547 && GET_MODE_CLASS (GET_MODE (op)) == MODE_FLOAT
548 && GET_MODE_CLASS (mode) == MODE_INT
549 && width <= HOST_BITS_PER_WIDE_INT && width > 0)
550 {
551 REAL_VALUE_TYPE d;
552 jmp_buf handler;
553 HOST_WIDE_INT val;
554
555 if (setjmp (handler))
556 return 0;
557
558 set_float_handler (handler);
559
560 REAL_VALUE_FROM_CONST_DOUBLE (d, op);
561
562 switch (code)
563 {
564 case FIX:
565 val = REAL_VALUE_FIX (d);
566 break;
567
568 case UNSIGNED_FIX:
569 val = REAL_VALUE_UNSIGNED_FIX (d);
570 break;
571
572 default:
573 abort ();
574 }
575
576 set_float_handler (NULL_PTR);
577
578 val = trunc_int_for_mode (val, mode);
579
580 return GEN_INT (val);
581 }
582 #endif
583 /* This was formerly used only for non-IEEE float.
584 eggert@twinsun.com says it is safe for IEEE also. */
585 else
586 {
587 enum rtx_code reversed;
588 /* There are some simplifications we can do even if the operands
589 aren't constant. */
590 switch (code)
591 {
592 case NOT:
593 /* (not (not X)) == X. */
594 if (GET_CODE (op) == NOT)
595 return XEXP (op, 0);
596
597 /* (not (eq X Y)) == (ne X Y), etc. */
598 if (mode == BImode && GET_RTX_CLASS (GET_CODE (op)) == '<'
599 && ((reversed = reversed_comparison_code (op, NULL_RTX))
600 != UNKNOWN))
601 return gen_rtx_fmt_ee (reversed,
602 op_mode, XEXP (op, 0), XEXP (op, 1));
603 break;
604
605 case NEG:
606 /* (neg (neg X)) == X. */
607 if (GET_CODE (op) == NEG)
608 return XEXP (op, 0);
609 break;
610
611 case SIGN_EXTEND:
612 /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
613 becomes just the MINUS if its mode is MODE. This allows
614 folding switch statements on machines using casesi (such as
615 the Vax). */
616 if (GET_CODE (op) == TRUNCATE
617 && GET_MODE (XEXP (op, 0)) == mode
618 && GET_CODE (XEXP (op, 0)) == MINUS
619 && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
620 && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
621 return XEXP (op, 0);
622
623 #ifdef POINTERS_EXTEND_UNSIGNED
624 if (! POINTERS_EXTEND_UNSIGNED
625 && mode == Pmode && GET_MODE (op) == ptr_mode
626 && (CONSTANT_P (op)
627 || (GET_CODE (op) == SUBREG
628 && GET_CODE (SUBREG_REG (op)) == REG
629 && REG_POINTER (SUBREG_REG (op))
630 && GET_MODE (SUBREG_REG (op)) == Pmode)))
631 return convert_memory_address (Pmode, op);
632 #endif
633 break;
634
635 #ifdef POINTERS_EXTEND_UNSIGNED
636 case ZERO_EXTEND:
637 if (POINTERS_EXTEND_UNSIGNED
638 && mode == Pmode && GET_MODE (op) == ptr_mode
639 && (CONSTANT_P (op)
640 || (GET_CODE (op) == SUBREG
641 && GET_CODE (SUBREG_REG (op)) == REG
642 && REG_POINTER (SUBREG_REG (op))
643 && GET_MODE (SUBREG_REG (op)) == Pmode)))
644 return convert_memory_address (Pmode, op);
645 break;
646 #endif
647
648 default:
649 break;
650 }
651
652 return 0;
653 }
654 }
655 \f
656 /* Simplify a binary operation CODE with result mode MODE, operating on OP0
657 and OP1. Return 0 if no simplification is possible.
658
659 Don't use this for relational operations such as EQ or LT.
660 Use simplify_relational_operation instead. */
661
662 rtx
663 simplify_binary_operation (code, mode, op0, op1)
664 enum rtx_code code;
665 enum machine_mode mode;
666 rtx op0, op1;
667 {
668 register HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
669 HOST_WIDE_INT val;
670 unsigned int width = GET_MODE_BITSIZE (mode);
671 rtx tem;
672
673 /* Relational operations don't work here. We must know the mode
674 of the operands in order to do the comparison correctly.
675 Assuming a full word can give incorrect results.
676 Consider comparing 128 with -128 in QImode. */
677
678 if (GET_RTX_CLASS (code) == '<')
679 abort ();
680
681 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
682 if (GET_MODE_CLASS (mode) == MODE_FLOAT
683 && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
684 && mode == GET_MODE (op0) && mode == GET_MODE (op1))
685 {
686 REAL_VALUE_TYPE f0, f1, value;
687 jmp_buf handler;
688
689 if (setjmp (handler))
690 return 0;
691
692 set_float_handler (handler);
693
694 REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
695 REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
696 f0 = real_value_truncate (mode, f0);
697 f1 = real_value_truncate (mode, f1);
698
699 #ifdef REAL_ARITHMETIC
700 #ifndef REAL_INFINITY
701 if (code == DIV && REAL_VALUES_EQUAL (f1, dconst0))
702 return 0;
703 #endif
704 REAL_ARITHMETIC (value, rtx_to_tree_code (code), f0, f1);
705 #else
706 switch (code)
707 {
708 case PLUS:
709 value = f0 + f1;
710 break;
711 case MINUS:
712 value = f0 - f1;
713 break;
714 case MULT:
715 value = f0 * f1;
716 break;
717 case DIV:
718 #ifndef REAL_INFINITY
719 if (f1 == 0)
720 return 0;
721 #endif
722 value = f0 / f1;
723 break;
724 case SMIN:
725 value = MIN (f0, f1);
726 break;
727 case SMAX:
728 value = MAX (f0, f1);
729 break;
730 default:
731 abort ();
732 }
733 #endif
734
735 value = real_value_truncate (mode, value);
736 set_float_handler (NULL_PTR);
737 return CONST_DOUBLE_FROM_REAL_VALUE (value, mode);
738 }
739 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
740
741 /* We can fold some multi-word operations. */
742 if (GET_MODE_CLASS (mode) == MODE_INT
743 && width == HOST_BITS_PER_WIDE_INT * 2
744 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
745 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
746 {
747 unsigned HOST_WIDE_INT l1, l2, lv;
748 HOST_WIDE_INT h1, h2, hv;
749
750 if (GET_CODE (op0) == CONST_DOUBLE)
751 l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0);
752 else
753 l1 = INTVAL (op0), h1 = HWI_SIGN_EXTEND (l1);
754
755 if (GET_CODE (op1) == CONST_DOUBLE)
756 l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1);
757 else
758 l2 = INTVAL (op1), h2 = HWI_SIGN_EXTEND (l2);
759
760 switch (code)
761 {
762 case MINUS:
763 /* A - B == A + (-B). */
764 neg_double (l2, h2, &lv, &hv);
765 l2 = lv, h2 = hv;
766
767 /* .. fall through ... */
768
769 case PLUS:
770 add_double (l1, h1, l2, h2, &lv, &hv);
771 break;
772
773 case MULT:
774 mul_double (l1, h1, l2, h2, &lv, &hv);
775 break;
776
777 case DIV: case MOD: case UDIV: case UMOD:
778 /* We'd need to include tree.h to do this and it doesn't seem worth
779 it. */
780 return 0;
781
782 case AND:
783 lv = l1 & l2, hv = h1 & h2;
784 break;
785
786 case IOR:
787 lv = l1 | l2, hv = h1 | h2;
788 break;
789
790 case XOR:
791 lv = l1 ^ l2, hv = h1 ^ h2;
792 break;
793
794 case SMIN:
795 if (h1 < h2
796 || (h1 == h2
797 && ((unsigned HOST_WIDE_INT) l1
798 < (unsigned HOST_WIDE_INT) l2)))
799 lv = l1, hv = h1;
800 else
801 lv = l2, hv = h2;
802 break;
803
804 case SMAX:
805 if (h1 > h2
806 || (h1 == h2
807 && ((unsigned HOST_WIDE_INT) l1
808 > (unsigned HOST_WIDE_INT) l2)))
809 lv = l1, hv = h1;
810 else
811 lv = l2, hv = h2;
812 break;
813
814 case UMIN:
815 if ((unsigned HOST_WIDE_INT) h1 < (unsigned HOST_WIDE_INT) h2
816 || (h1 == h2
817 && ((unsigned HOST_WIDE_INT) l1
818 < (unsigned HOST_WIDE_INT) l2)))
819 lv = l1, hv = h1;
820 else
821 lv = l2, hv = h2;
822 break;
823
824 case UMAX:
825 if ((unsigned HOST_WIDE_INT) h1 > (unsigned HOST_WIDE_INT) h2
826 || (h1 == h2
827 && ((unsigned HOST_WIDE_INT) l1
828 > (unsigned HOST_WIDE_INT) l2)))
829 lv = l1, hv = h1;
830 else
831 lv = l2, hv = h2;
832 break;
833
834 case LSHIFTRT: case ASHIFTRT:
835 case ASHIFT:
836 case ROTATE: case ROTATERT:
837 #ifdef SHIFT_COUNT_TRUNCATED
838 if (SHIFT_COUNT_TRUNCATED)
839 l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0;
840 #endif
841
842 if (h2 != 0 || l2 >= GET_MODE_BITSIZE (mode))
843 return 0;
844
845 if (code == LSHIFTRT || code == ASHIFTRT)
846 rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
847 code == ASHIFTRT);
848 else if (code == ASHIFT)
849 lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv, 1);
850 else if (code == ROTATE)
851 lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
852 else /* code == ROTATERT */
853 rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
854 break;
855
856 default:
857 return 0;
858 }
859
860 return immed_double_const (lv, hv, mode);
861 }
862
863 if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
864 || width > HOST_BITS_PER_WIDE_INT || width == 0)
865 {
866 /* Even if we can't compute a constant result,
867 there are some cases worth simplifying. */
868
869 switch (code)
870 {
871 case PLUS:
872 /* In IEEE floating point, x+0 is not the same as x. Similarly
873 for the other optimizations below. */
874 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
875 && FLOAT_MODE_P (mode) && ! flag_fast_math)
876 break;
877
878 if (op1 == CONST0_RTX (mode))
879 return op0;
880
881 /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
882 if (GET_CODE (op0) == NEG)
883 return simplify_gen_binary (MINUS, mode, op1, XEXP (op0, 0));
884 else if (GET_CODE (op1) == NEG)
885 return simplify_gen_binary (MINUS, mode, op0, XEXP (op1, 0));
886
887 /* Handle both-operands-constant cases. We can only add
888 CONST_INTs to constants since the sum of relocatable symbols
889 can't be handled by most assemblers. Don't add CONST_INT
890 to CONST_INT since overflow won't be computed properly if wider
891 than HOST_BITS_PER_WIDE_INT. */
892
893 if (CONSTANT_P (op0) && GET_MODE (op0) != VOIDmode
894 && GET_CODE (op1) == CONST_INT)
895 return plus_constant (op0, INTVAL (op1));
896 else if (CONSTANT_P (op1) && GET_MODE (op1) != VOIDmode
897 && GET_CODE (op0) == CONST_INT)
898 return plus_constant (op1, INTVAL (op0));
899
900 /* See if this is something like X * C - X or vice versa or
901 if the multiplication is written as a shift. If so, we can
902 distribute and make a new multiply, shift, or maybe just
903 have X (if C is 2 in the example above). But don't make
904 real multiply if we didn't have one before. */
905
906 if (! FLOAT_MODE_P (mode))
907 {
908 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
909 rtx lhs = op0, rhs = op1;
910 int had_mult = 0;
911
912 if (GET_CODE (lhs) == NEG)
913 coeff0 = -1, lhs = XEXP (lhs, 0);
914 else if (GET_CODE (lhs) == MULT
915 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
916 {
917 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
918 had_mult = 1;
919 }
920 else if (GET_CODE (lhs) == ASHIFT
921 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
922 && INTVAL (XEXP (lhs, 1)) >= 0
923 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
924 {
925 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
926 lhs = XEXP (lhs, 0);
927 }
928
929 if (GET_CODE (rhs) == NEG)
930 coeff1 = -1, rhs = XEXP (rhs, 0);
931 else if (GET_CODE (rhs) == MULT
932 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
933 {
934 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
935 had_mult = 1;
936 }
937 else if (GET_CODE (rhs) == ASHIFT
938 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
939 && INTVAL (XEXP (rhs, 1)) >= 0
940 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
941 {
942 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
943 rhs = XEXP (rhs, 0);
944 }
945
946 if (rtx_equal_p (lhs, rhs))
947 {
948 tem = simplify_gen_binary (MULT, mode, lhs,
949 GEN_INT (coeff0 + coeff1));
950 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
951 }
952 }
953
954 /* If one of the operands is a PLUS or a MINUS, see if we can
955 simplify this by the associative law.
956 Don't use the associative law for floating point.
957 The inaccuracy makes it nonassociative,
958 and subtle programs can break if operations are associated. */
959
960 if (INTEGRAL_MODE_P (mode)
961 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
962 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
963 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
964 return tem;
965 break;
966
967 case COMPARE:
968 #ifdef HAVE_cc0
969 /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
970 using cc0, in which case we want to leave it as a COMPARE
971 so we can distinguish it from a register-register-copy.
972
973 In IEEE floating point, x-0 is not the same as x. */
974
975 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
976 || ! FLOAT_MODE_P (mode) || flag_fast_math)
977 && op1 == CONST0_RTX (mode))
978 return op0;
979 #endif
980
981 /* Convert (compare (gt (flags) 0) (lt (flags) 0)) to (flags). */
982 if (((GET_CODE (op0) == GT && GET_CODE (op1) == LT)
983 || (GET_CODE (op0) == GTU && GET_CODE (op1) == LTU))
984 && XEXP (op0, 1) == const0_rtx && XEXP (op1, 1) == const0_rtx)
985 {
986 rtx xop00 = XEXP (op0, 0);
987 rtx xop10 = XEXP (op1, 0);
988
989 #ifdef HAVE_cc0
990 if (GET_CODE (xop00) == CC0 && GET_CODE (xop10) == CC0)
991 #else
992 if (GET_CODE (xop00) == REG && GET_CODE (xop10) == REG
993 && GET_MODE (xop00) == GET_MODE (xop10)
994 && REGNO (xop00) == REGNO (xop10)
995 && GET_MODE_CLASS (GET_MODE (xop00)) == MODE_CC
996 && GET_MODE_CLASS (GET_MODE (xop10)) == MODE_CC)
997 #endif
998 return xop00;
999 }
1000
1001 break;
1002 case MINUS:
1003 /* None of these optimizations can be done for IEEE
1004 floating point. */
1005 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
1006 && FLOAT_MODE_P (mode) && ! flag_fast_math)
1007 break;
1008
1009 /* We can't assume x-x is 0 even with non-IEEE floating point,
1010 but since it is zero except in very strange circumstances, we
1011 will treat it as zero with -ffast-math. */
1012 if (rtx_equal_p (op0, op1)
1013 && ! side_effects_p (op0)
1014 && (! FLOAT_MODE_P (mode) || flag_fast_math))
1015 return CONST0_RTX (mode);
1016
1017 /* Change subtraction from zero into negation. */
1018 if (op0 == CONST0_RTX (mode))
1019 return gen_rtx_NEG (mode, op1);
1020
1021 /* (-1 - a) is ~a. */
1022 if (op0 == constm1_rtx)
1023 return gen_rtx_NOT (mode, op1);
1024
1025 /* Subtracting 0 has no effect. */
1026 if (op1 == CONST0_RTX (mode))
1027 return op0;
1028
1029 /* See if this is something like X * C - X or vice versa or
1030 if the multiplication is written as a shift. If so, we can
1031 distribute and make a new multiply, shift, or maybe just
1032 have X (if C is 2 in the example above). But don't make
1033 real multiply if we didn't have one before. */
1034
1035 if (! FLOAT_MODE_P (mode))
1036 {
1037 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
1038 rtx lhs = op0, rhs = op1;
1039 int had_mult = 0;
1040
1041 if (GET_CODE (lhs) == NEG)
1042 coeff0 = -1, lhs = XEXP (lhs, 0);
1043 else if (GET_CODE (lhs) == MULT
1044 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
1045 {
1046 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
1047 had_mult = 1;
1048 }
1049 else if (GET_CODE (lhs) == ASHIFT
1050 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
1051 && INTVAL (XEXP (lhs, 1)) >= 0
1052 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
1053 {
1054 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
1055 lhs = XEXP (lhs, 0);
1056 }
1057
1058 if (GET_CODE (rhs) == NEG)
1059 coeff1 = - 1, rhs = XEXP (rhs, 0);
1060 else if (GET_CODE (rhs) == MULT
1061 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
1062 {
1063 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
1064 had_mult = 1;
1065 }
1066 else if (GET_CODE (rhs) == ASHIFT
1067 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
1068 && INTVAL (XEXP (rhs, 1)) >= 0
1069 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
1070 {
1071 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
1072 rhs = XEXP (rhs, 0);
1073 }
1074
1075 if (rtx_equal_p (lhs, rhs))
1076 {
1077 tem = simplify_gen_binary (MULT, mode, lhs,
1078 GEN_INT (coeff0 - coeff1));
1079 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
1080 }
1081 }
1082
1083 /* (a - (-b)) -> (a + b). */
1084 if (GET_CODE (op1) == NEG)
1085 return simplify_gen_binary (PLUS, mode, op0, XEXP (op1, 0));
1086
1087 /* If one of the operands is a PLUS or a MINUS, see if we can
1088 simplify this by the associative law.
1089 Don't use the associative law for floating point.
1090 The inaccuracy makes it nonassociative,
1091 and subtle programs can break if operations are associated. */
1092
1093 if (INTEGRAL_MODE_P (mode)
1094 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
1095 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
1096 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
1097 return tem;
1098
1099 /* Don't let a relocatable value get a negative coeff. */
1100 if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode)
1101 return plus_constant (op0, - INTVAL (op1));
1102
1103 /* (x - (x & y)) -> (x & ~y) */
1104 if (GET_CODE (op1) == AND)
1105 {
1106 if (rtx_equal_p (op0, XEXP (op1, 0)))
1107 return simplify_gen_binary (AND, mode, op0,
1108 gen_rtx_NOT (mode, XEXP (op1, 1)));
1109 if (rtx_equal_p (op0, XEXP (op1, 1)))
1110 return simplify_gen_binary (AND, mode, op0,
1111 gen_rtx_NOT (mode, XEXP (op1, 0)));
1112 }
1113 break;
1114
1115 case MULT:
1116 if (op1 == constm1_rtx)
1117 {
1118 tem = simplify_unary_operation (NEG, mode, op0, mode);
1119
1120 return tem ? tem : gen_rtx_NEG (mode, op0);
1121 }
1122
1123 /* In IEEE floating point, x*0 is not always 0. */
1124 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1125 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1126 && op1 == CONST0_RTX (mode)
1127 && ! side_effects_p (op0))
1128 return op1;
1129
1130 /* In IEEE floating point, x*1 is not equivalent to x for nans.
1131 However, ANSI says we can drop signals,
1132 so we can do this anyway. */
1133 if (op1 == CONST1_RTX (mode))
1134 return op0;
1135
1136 /* Convert multiply by constant power of two into shift unless
1137 we are still generating RTL. This test is a kludge. */
1138 if (GET_CODE (op1) == CONST_INT
1139 && (val = exact_log2 (INTVAL (op1))) >= 0
1140 /* If the mode is larger than the host word size, and the
1141 uppermost bit is set, then this isn't a power of two due
1142 to implicit sign extension. */
1143 && (width <= HOST_BITS_PER_WIDE_INT
1144 || val != HOST_BITS_PER_WIDE_INT - 1)
1145 && ! rtx_equal_function_value_matters)
1146 return gen_rtx_ASHIFT (mode, op0, GEN_INT (val));
1147
1148 if (GET_CODE (op1) == CONST_DOUBLE
1149 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
1150 {
1151 REAL_VALUE_TYPE d;
1152 jmp_buf handler;
1153 int op1is2, op1ism1;
1154
1155 if (setjmp (handler))
1156 return 0;
1157
1158 set_float_handler (handler);
1159 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1160 op1is2 = REAL_VALUES_EQUAL (d, dconst2);
1161 op1ism1 = REAL_VALUES_EQUAL (d, dconstm1);
1162 set_float_handler (NULL_PTR);
1163
1164 /* x*2 is x+x and x*(-1) is -x */
1165 if (op1is2 && GET_MODE (op0) == mode)
1166 return gen_rtx_PLUS (mode, op0, copy_rtx (op0));
1167
1168 else if (op1ism1 && GET_MODE (op0) == mode)
1169 return gen_rtx_NEG (mode, op0);
1170 }
1171 break;
1172
1173 case IOR:
1174 if (op1 == const0_rtx)
1175 return op0;
1176 if (GET_CODE (op1) == CONST_INT
1177 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1178 return op1;
1179 if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1180 return op0;
1181 /* A | (~A) -> -1 */
1182 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1183 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1184 && ! side_effects_p (op0)
1185 && GET_MODE_CLASS (mode) != MODE_CC)
1186 return constm1_rtx;
1187 break;
1188
1189 case XOR:
1190 if (op1 == const0_rtx)
1191 return op0;
1192 if (GET_CODE (op1) == CONST_INT
1193 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1194 return gen_rtx_NOT (mode, op0);
1195 if (op0 == op1 && ! side_effects_p (op0)
1196 && GET_MODE_CLASS (mode) != MODE_CC)
1197 return const0_rtx;
1198 break;
1199
1200 case AND:
1201 if (op1 == const0_rtx && ! side_effects_p (op0))
1202 return const0_rtx;
1203 if (GET_CODE (op1) == CONST_INT
1204 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1205 return op0;
1206 if (op0 == op1 && ! side_effects_p (op0)
1207 && GET_MODE_CLASS (mode) != MODE_CC)
1208 return op0;
1209 /* A & (~A) -> 0 */
1210 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1211 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1212 && ! side_effects_p (op0)
1213 && GET_MODE_CLASS (mode) != MODE_CC)
1214 return const0_rtx;
1215 break;
1216
1217 case UDIV:
1218 /* Convert divide by power of two into shift (divide by 1 handled
1219 below). */
1220 if (GET_CODE (op1) == CONST_INT
1221 && (arg1 = exact_log2 (INTVAL (op1))) > 0)
1222 return gen_rtx_LSHIFTRT (mode, op0, GEN_INT (arg1));
1223
1224 /* ... fall through ... */
1225
1226 case DIV:
1227 if (op1 == CONST1_RTX (mode))
1228 return op0;
1229
1230 /* In IEEE floating point, 0/x is not always 0. */
1231 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1232 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1233 && op0 == CONST0_RTX (mode)
1234 && ! side_effects_p (op1))
1235 return op0;
1236
1237 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1238 /* Change division by a constant into multiplication. Only do
1239 this with -ffast-math until an expert says it is safe in
1240 general. */
1241 else if (GET_CODE (op1) == CONST_DOUBLE
1242 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
1243 && op1 != CONST0_RTX (mode)
1244 && flag_fast_math)
1245 {
1246 REAL_VALUE_TYPE d;
1247 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1248
1249 if (! REAL_VALUES_EQUAL (d, dconst0))
1250 {
1251 #if defined (REAL_ARITHMETIC)
1252 REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d);
1253 return gen_rtx_MULT (mode, op0,
1254 CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
1255 #else
1256 return
1257 gen_rtx_MULT (mode, op0,
1258 CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
1259 #endif
1260 }
1261 }
1262 #endif
1263 break;
1264
1265 case UMOD:
1266 /* Handle modulus by power of two (mod with 1 handled below). */
1267 if (GET_CODE (op1) == CONST_INT
1268 && exact_log2 (INTVAL (op1)) > 0)
1269 return gen_rtx_AND (mode, op0, GEN_INT (INTVAL (op1) - 1));
1270
1271 /* ... fall through ... */
1272
1273 case MOD:
1274 if ((op0 == const0_rtx || op1 == const1_rtx)
1275 && ! side_effects_p (op0) && ! side_effects_p (op1))
1276 return const0_rtx;
1277 break;
1278
1279 case ROTATERT:
1280 case ROTATE:
1281 /* Rotating ~0 always results in ~0. */
1282 if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT
1283 && (unsigned HOST_WIDE_INT) INTVAL (op0) == GET_MODE_MASK (mode)
1284 && ! side_effects_p (op1))
1285 return op0;
1286
1287 /* ... fall through ... */
1288
1289 case ASHIFT:
1290 case ASHIFTRT:
1291 case LSHIFTRT:
1292 if (op1 == const0_rtx)
1293 return op0;
1294 if (op0 == const0_rtx && ! side_effects_p (op1))
1295 return op0;
1296 break;
1297
1298 case SMIN:
1299 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1300 && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1)
1301 && ! side_effects_p (op0))
1302 return op1;
1303 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1304 return op0;
1305 break;
1306
1307 case SMAX:
1308 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1309 && ((unsigned HOST_WIDE_INT) INTVAL (op1)
1310 == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1)
1311 && ! side_effects_p (op0))
1312 return op1;
1313 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1314 return op0;
1315 break;
1316
1317 case UMIN:
1318 if (op1 == const0_rtx && ! side_effects_p (op0))
1319 return op1;
1320 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1321 return op0;
1322 break;
1323
1324 case UMAX:
1325 if (op1 == constm1_rtx && ! side_effects_p (op0))
1326 return op1;
1327 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1328 return op0;
1329 break;
1330
1331 default:
1332 abort ();
1333 }
1334
1335 return 0;
1336 }
1337
1338 /* Get the integer argument values in two forms:
1339 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
1340
1341 arg0 = INTVAL (op0);
1342 arg1 = INTVAL (op1);
1343
1344 if (width < HOST_BITS_PER_WIDE_INT)
1345 {
1346 arg0 &= ((HOST_WIDE_INT) 1 << width) - 1;
1347 arg1 &= ((HOST_WIDE_INT) 1 << width) - 1;
1348
1349 arg0s = arg0;
1350 if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1351 arg0s |= ((HOST_WIDE_INT) (-1) << width);
1352
1353 arg1s = arg1;
1354 if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1355 arg1s |= ((HOST_WIDE_INT) (-1) << width);
1356 }
1357 else
1358 {
1359 arg0s = arg0;
1360 arg1s = arg1;
1361 }
1362
1363 /* Compute the value of the arithmetic. */
1364
1365 switch (code)
1366 {
1367 case PLUS:
1368 val = arg0s + arg1s;
1369 break;
1370
1371 case MINUS:
1372 val = arg0s - arg1s;
1373 break;
1374
1375 case MULT:
1376 val = arg0s * arg1s;
1377 break;
1378
1379 case DIV:
1380 if (arg1s == 0
1381 || (arg0s == (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)
1382 && arg1s == -1))
1383 return 0;
1384 val = arg0s / arg1s;
1385 break;
1386
1387 case MOD:
1388 if (arg1s == 0
1389 || (arg0s == (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)
1390 && arg1s == -1))
1391 return 0;
1392 val = arg0s % arg1s;
1393 break;
1394
1395 case UDIV:
1396 if (arg1 == 0
1397 || (arg0s == (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)
1398 && arg1s == -1))
1399 return 0;
1400 val = (unsigned HOST_WIDE_INT) arg0 / arg1;
1401 break;
1402
1403 case UMOD:
1404 if (arg1 == 0
1405 || (arg0s == (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)
1406 && arg1s == -1))
1407 return 0;
1408 val = (unsigned HOST_WIDE_INT) arg0 % arg1;
1409 break;
1410
1411 case AND:
1412 val = arg0 & arg1;
1413 break;
1414
1415 case IOR:
1416 val = arg0 | arg1;
1417 break;
1418
1419 case XOR:
1420 val = arg0 ^ arg1;
1421 break;
1422
1423 case LSHIFTRT:
1424 /* If shift count is undefined, don't fold it; let the machine do
1425 what it wants. But truncate it if the machine will do that. */
1426 if (arg1 < 0)
1427 return 0;
1428
1429 #ifdef SHIFT_COUNT_TRUNCATED
1430 if (SHIFT_COUNT_TRUNCATED)
1431 arg1 %= width;
1432 #endif
1433
1434 val = ((unsigned HOST_WIDE_INT) arg0) >> arg1;
1435 break;
1436
1437 case ASHIFT:
1438 if (arg1 < 0)
1439 return 0;
1440
1441 #ifdef SHIFT_COUNT_TRUNCATED
1442 if (SHIFT_COUNT_TRUNCATED)
1443 arg1 %= width;
1444 #endif
1445
1446 val = ((unsigned HOST_WIDE_INT) arg0) << arg1;
1447 break;
1448
1449 case ASHIFTRT:
1450 if (arg1 < 0)
1451 return 0;
1452
1453 #ifdef SHIFT_COUNT_TRUNCATED
1454 if (SHIFT_COUNT_TRUNCATED)
1455 arg1 %= width;
1456 #endif
1457
1458 val = arg0s >> arg1;
1459
1460 /* Bootstrap compiler may not have sign extended the right shift.
1461 Manually extend the sign to insure bootstrap cc matches gcc. */
1462 if (arg0s < 0 && arg1 > 0)
1463 val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1);
1464
1465 break;
1466
1467 case ROTATERT:
1468 if (arg1 < 0)
1469 return 0;
1470
1471 arg1 %= width;
1472 val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1))
1473 | (((unsigned HOST_WIDE_INT) arg0) >> arg1));
1474 break;
1475
1476 case ROTATE:
1477 if (arg1 < 0)
1478 return 0;
1479
1480 arg1 %= width;
1481 val = ((((unsigned HOST_WIDE_INT) arg0) << arg1)
1482 | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1)));
1483 break;
1484
1485 case COMPARE:
1486 /* Do nothing here. */
1487 return 0;
1488
1489 case SMIN:
1490 val = arg0s <= arg1s ? arg0s : arg1s;
1491 break;
1492
1493 case UMIN:
1494 val = ((unsigned HOST_WIDE_INT) arg0
1495 <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1496 break;
1497
1498 case SMAX:
1499 val = arg0s > arg1s ? arg0s : arg1s;
1500 break;
1501
1502 case UMAX:
1503 val = ((unsigned HOST_WIDE_INT) arg0
1504 > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1505 break;
1506
1507 default:
1508 abort ();
1509 }
1510
1511 val = trunc_int_for_mode (val, mode);
1512
1513 return GEN_INT (val);
1514 }
1515 \f
1516 /* Simplify a PLUS or MINUS, at least one of whose operands may be another
1517 PLUS or MINUS.
1518
1519 Rather than test for specific case, we do this by a brute-force method
1520 and do all possible simplifications until no more changes occur. Then
1521 we rebuild the operation. */
1522
1523 static rtx
1524 simplify_plus_minus (code, mode, op0, op1)
1525 enum rtx_code code;
1526 enum machine_mode mode;
1527 rtx op0, op1;
1528 {
1529 rtx ops[8];
1530 int negs[8];
1531 rtx result, tem;
1532 int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
1533 int first = 1, negate = 0, changed;
1534 int i, j;
1535
1536 memset ((char *) ops, 0, sizeof ops);
1537
1538 /* Set up the two operands and then expand them until nothing has been
1539 changed. If we run out of room in our array, give up; this should
1540 almost never happen. */
1541
1542 ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
1543
1544 changed = 1;
1545 while (changed)
1546 {
1547 changed = 0;
1548
1549 for (i = 0; i < n_ops; i++)
1550 switch (GET_CODE (ops[i]))
1551 {
1552 case PLUS:
1553 case MINUS:
1554 if (n_ops == 7)
1555 return 0;
1556
1557 ops[n_ops] = XEXP (ops[i], 1);
1558 negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
1559 ops[i] = XEXP (ops[i], 0);
1560 input_ops++;
1561 changed = 1;
1562 break;
1563
1564 case NEG:
1565 ops[i] = XEXP (ops[i], 0);
1566 negs[i] = ! negs[i];
1567 changed = 1;
1568 break;
1569
1570 case CONST:
1571 ops[i] = XEXP (ops[i], 0);
1572 input_consts++;
1573 changed = 1;
1574 break;
1575
1576 case NOT:
1577 /* ~a -> (-a - 1) */
1578 if (n_ops != 7)
1579 {
1580 ops[n_ops] = constm1_rtx;
1581 negs[n_ops++] = negs[i];
1582 ops[i] = XEXP (ops[i], 0);
1583 negs[i] = ! negs[i];
1584 changed = 1;
1585 }
1586 break;
1587
1588 case CONST_INT:
1589 if (negs[i])
1590 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
1591 break;
1592
1593 default:
1594 break;
1595 }
1596 }
1597
1598 /* If we only have two operands, we can't do anything. */
1599 if (n_ops <= 2)
1600 return 0;
1601
1602 /* Now simplify each pair of operands until nothing changes. The first
1603 time through just simplify constants against each other. */
1604
1605 changed = 1;
1606 while (changed)
1607 {
1608 changed = first;
1609
1610 for (i = 0; i < n_ops - 1; i++)
1611 for (j = i + 1; j < n_ops; j++)
1612 if (ops[i] != 0 && ops[j] != 0
1613 && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
1614 {
1615 rtx lhs = ops[i], rhs = ops[j];
1616 enum rtx_code ncode = PLUS;
1617
1618 if (negs[i] && ! negs[j])
1619 lhs = ops[j], rhs = ops[i], ncode = MINUS;
1620 else if (! negs[i] && negs[j])
1621 ncode = MINUS;
1622
1623 tem = simplify_binary_operation (ncode, mode, lhs, rhs);
1624 if (tem)
1625 {
1626 ops[i] = tem, ops[j] = 0;
1627 negs[i] = negs[i] && negs[j];
1628 if (GET_CODE (tem) == NEG)
1629 ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
1630
1631 if (GET_CODE (ops[i]) == CONST_INT && negs[i])
1632 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
1633 changed = 1;
1634 }
1635 }
1636
1637 first = 0;
1638 }
1639
1640 /* Pack all the operands to the lower-numbered entries and give up if
1641 we didn't reduce the number of operands we had. Make sure we
1642 count a CONST as two operands. If we have the same number of
1643 operands, but have made more CONSTs than we had, this is also
1644 an improvement, so accept it. */
1645
1646 for (i = 0, j = 0; j < n_ops; j++)
1647 if (ops[j] != 0)
1648 {
1649 ops[i] = ops[j], negs[i++] = negs[j];
1650 if (GET_CODE (ops[j]) == CONST)
1651 n_consts++;
1652 }
1653
1654 if (i + n_consts > input_ops
1655 || (i + n_consts == input_ops && n_consts <= input_consts))
1656 return 0;
1657
1658 n_ops = i;
1659
1660 /* If we have a CONST_INT, put it last. */
1661 for (i = 0; i < n_ops - 1; i++)
1662 if (GET_CODE (ops[i]) == CONST_INT)
1663 {
1664 tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
1665 j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
1666 }
1667
1668 /* Put a non-negated operand first. If there aren't any, make all
1669 operands positive and negate the whole thing later. */
1670 for (i = 0; i < n_ops && negs[i]; i++)
1671 ;
1672
1673 if (i == n_ops)
1674 {
1675 for (i = 0; i < n_ops; i++)
1676 negs[i] = 0;
1677 negate = 1;
1678 }
1679 else if (i != 0)
1680 {
1681 tem = ops[0], ops[0] = ops[i], ops[i] = tem;
1682 j = negs[0], negs[0] = negs[i], negs[i] = j;
1683 }
1684
1685 /* Now make the result by performing the requested operations. */
1686 result = ops[0];
1687 for (i = 1; i < n_ops; i++)
1688 result = simplify_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
1689
1690 return negate ? gen_rtx_NEG (mode, result) : result;
1691 }
1692
1693 struct cfc_args
1694 {
1695 rtx op0, op1; /* Input */
1696 int equal, op0lt, op1lt; /* Output */
1697 int unordered;
1698 };
1699
1700 static void
1701 check_fold_consts (data)
1702 PTR data;
1703 {
1704 struct cfc_args *args = (struct cfc_args *) data;
1705 REAL_VALUE_TYPE d0, d1;
1706
1707 /* We may possibly raise an exception while reading the value. */
1708 args->unordered = 1;
1709 REAL_VALUE_FROM_CONST_DOUBLE (d0, args->op0);
1710 REAL_VALUE_FROM_CONST_DOUBLE (d1, args->op1);
1711
1712 /* Comparisons of Inf versus Inf are ordered. */
1713 if (REAL_VALUE_ISNAN (d0)
1714 || REAL_VALUE_ISNAN (d1))
1715 return;
1716 args->equal = REAL_VALUES_EQUAL (d0, d1);
1717 args->op0lt = REAL_VALUES_LESS (d0, d1);
1718 args->op1lt = REAL_VALUES_LESS (d1, d0);
1719 args->unordered = 0;
1720 }
1721
1722 /* Like simplify_binary_operation except used for relational operators.
1723 MODE is the mode of the operands, not that of the result. If MODE
1724 is VOIDmode, both operands must also be VOIDmode and we compare the
1725 operands in "infinite precision".
1726
1727 If no simplification is possible, this function returns zero. Otherwise,
1728 it returns either const_true_rtx or const0_rtx. */
1729
1730 rtx
1731 simplify_relational_operation (code, mode, op0, op1)
1732 enum rtx_code code;
1733 enum machine_mode mode;
1734 rtx op0, op1;
1735 {
1736 int equal, op0lt, op0ltu, op1lt, op1ltu;
1737 rtx tem;
1738
1739 if (mode == VOIDmode
1740 && (GET_MODE (op0) != VOIDmode
1741 || GET_MODE (op1) != VOIDmode))
1742 abort ();
1743
1744 /* If op0 is a compare, extract the comparison arguments from it. */
1745 if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
1746 op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
1747
1748 /* We can't simplify MODE_CC values since we don't know what the
1749 actual comparison is. */
1750 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC
1751 #ifdef HAVE_cc0
1752 || op0 == cc0_rtx
1753 #endif
1754 )
1755 return 0;
1756
1757 /* Make sure the constant is second. */
1758 if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
1759 || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
1760 {
1761 tem = op0, op0 = op1, op1 = tem;
1762 code = swap_condition (code);
1763 }
1764
1765 /* For integer comparisons of A and B maybe we can simplify A - B and can
1766 then simplify a comparison of that with zero. If A and B are both either
1767 a register or a CONST_INT, this can't help; testing for these cases will
1768 prevent infinite recursion here and speed things up.
1769
1770 If CODE is an unsigned comparison, then we can never do this optimization,
1771 because it gives an incorrect result if the subtraction wraps around zero.
1772 ANSI C defines unsigned operations such that they never overflow, and
1773 thus such cases can not be ignored. */
1774
1775 if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx
1776 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT)
1777 && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT))
1778 && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1))
1779 && code != GTU && code != GEU && code != LTU && code != LEU)
1780 return simplify_relational_operation (signed_condition (code),
1781 mode, tem, const0_rtx);
1782
1783 if (flag_fast_math && code == ORDERED)
1784 return const_true_rtx;
1785
1786 if (flag_fast_math && code == UNORDERED)
1787 return const0_rtx;
1788
1789 /* For non-IEEE floating-point, if the two operands are equal, we know the
1790 result. */
1791 if (rtx_equal_p (op0, op1)
1792 && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1793 || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math))
1794 equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0;
1795
1796 /* If the operands are floating-point constants, see if we can fold
1797 the result. */
1798 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1799 else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
1800 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
1801 {
1802 struct cfc_args args;
1803
1804 /* Setup input for check_fold_consts() */
1805 args.op0 = op0;
1806 args.op1 = op1;
1807
1808
1809 if (!do_float_handler(check_fold_consts, (PTR) &args))
1810 args.unordered = 1;
1811
1812 if (args.unordered)
1813 switch (code)
1814 {
1815 case UNEQ:
1816 case UNLT:
1817 case UNGT:
1818 case UNLE:
1819 case UNGE:
1820 case NE:
1821 case UNORDERED:
1822 return const_true_rtx;
1823 case EQ:
1824 case LT:
1825 case GT:
1826 case LE:
1827 case GE:
1828 case LTGT:
1829 case ORDERED:
1830 return const0_rtx;
1831 default:
1832 return 0;
1833 }
1834
1835 /* Receive output from check_fold_consts() */
1836 equal = args.equal;
1837 op0lt = op0ltu = args.op0lt;
1838 op1lt = op1ltu = args.op1lt;
1839 }
1840 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1841
1842 /* Otherwise, see if the operands are both integers. */
1843 else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode)
1844 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
1845 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
1846 {
1847 int width = GET_MODE_BITSIZE (mode);
1848 HOST_WIDE_INT l0s, h0s, l1s, h1s;
1849 unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u;
1850
1851 /* Get the two words comprising each integer constant. */
1852 if (GET_CODE (op0) == CONST_DOUBLE)
1853 {
1854 l0u = l0s = CONST_DOUBLE_LOW (op0);
1855 h0u = h0s = CONST_DOUBLE_HIGH (op0);
1856 }
1857 else
1858 {
1859 l0u = l0s = INTVAL (op0);
1860 h0u = h0s = HWI_SIGN_EXTEND (l0s);
1861 }
1862
1863 if (GET_CODE (op1) == CONST_DOUBLE)
1864 {
1865 l1u = l1s = CONST_DOUBLE_LOW (op1);
1866 h1u = h1s = CONST_DOUBLE_HIGH (op1);
1867 }
1868 else
1869 {
1870 l1u = l1s = INTVAL (op1);
1871 h1u = h1s = HWI_SIGN_EXTEND (l1s);
1872 }
1873
1874 /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT,
1875 we have to sign or zero-extend the values. */
1876 if (width != 0 && width < HOST_BITS_PER_WIDE_INT)
1877 {
1878 l0u &= ((HOST_WIDE_INT) 1 << width) - 1;
1879 l1u &= ((HOST_WIDE_INT) 1 << width) - 1;
1880
1881 if (l0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1882 l0s |= ((HOST_WIDE_INT) (-1) << width);
1883
1884 if (l1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1885 l1s |= ((HOST_WIDE_INT) (-1) << width);
1886 }
1887 if (width != 0 && width <= HOST_BITS_PER_WIDE_INT)
1888 h0u = h1u = 0, h0s = HWI_SIGN_EXTEND (l0s), h1s = HWI_SIGN_EXTEND (l1s);
1889
1890 equal = (h0u == h1u && l0u == l1u);
1891 op0lt = (h0s < h1s || (h0s == h1s && l0u < l1u));
1892 op1lt = (h1s < h0s || (h1s == h0s && l1u < l0u));
1893 op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u));
1894 op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u));
1895 }
1896
1897 /* Otherwise, there are some code-specific tests we can make. */
1898 else
1899 {
1900 switch (code)
1901 {
1902 case EQ:
1903 /* References to the frame plus a constant or labels cannot
1904 be zero, but a SYMBOL_REF can due to #pragma weak. */
1905 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1906 || GET_CODE (op0) == LABEL_REF)
1907 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1908 /* On some machines, the ap reg can be 0 sometimes. */
1909 && op0 != arg_pointer_rtx
1910 #endif
1911 )
1912 return const0_rtx;
1913 break;
1914
1915 case NE:
1916 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1917 || GET_CODE (op0) == LABEL_REF)
1918 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1919 && op0 != arg_pointer_rtx
1920 #endif
1921 )
1922 return const_true_rtx;
1923 break;
1924
1925 case GEU:
1926 /* Unsigned values are never negative. */
1927 if (op1 == const0_rtx)
1928 return const_true_rtx;
1929 break;
1930
1931 case LTU:
1932 if (op1 == const0_rtx)
1933 return const0_rtx;
1934 break;
1935
1936 case LEU:
1937 /* Unsigned values are never greater than the largest
1938 unsigned value. */
1939 if (GET_CODE (op1) == CONST_INT
1940 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1941 && INTEGRAL_MODE_P (mode))
1942 return const_true_rtx;
1943 break;
1944
1945 case GTU:
1946 if (GET_CODE (op1) == CONST_INT
1947 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1948 && INTEGRAL_MODE_P (mode))
1949 return const0_rtx;
1950 break;
1951
1952 default:
1953 break;
1954 }
1955
1956 return 0;
1957 }
1958
1959 /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set
1960 as appropriate. */
1961 switch (code)
1962 {
1963 case EQ:
1964 case UNEQ:
1965 return equal ? const_true_rtx : const0_rtx;
1966 case NE:
1967 case LTGT:
1968 return ! equal ? const_true_rtx : const0_rtx;
1969 case LT:
1970 case UNLT:
1971 return op0lt ? const_true_rtx : const0_rtx;
1972 case GT:
1973 case UNGT:
1974 return op1lt ? const_true_rtx : const0_rtx;
1975 case LTU:
1976 return op0ltu ? const_true_rtx : const0_rtx;
1977 case GTU:
1978 return op1ltu ? const_true_rtx : const0_rtx;
1979 case LE:
1980 case UNLE:
1981 return equal || op0lt ? const_true_rtx : const0_rtx;
1982 case GE:
1983 case UNGE:
1984 return equal || op1lt ? const_true_rtx : const0_rtx;
1985 case LEU:
1986 return equal || op0ltu ? const_true_rtx : const0_rtx;
1987 case GEU:
1988 return equal || op1ltu ? const_true_rtx : const0_rtx;
1989 case ORDERED:
1990 return const_true_rtx;
1991 case UNORDERED:
1992 return const0_rtx;
1993 default:
1994 abort ();
1995 }
1996 }
1997 \f
1998 /* Simplify CODE, an operation with result mode MODE and three operands,
1999 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
2000 a constant. Return 0 if no simplifications is possible. */
2001
2002 rtx
2003 simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
2004 enum rtx_code code;
2005 enum machine_mode mode, op0_mode;
2006 rtx op0, op1, op2;
2007 {
2008 unsigned int width = GET_MODE_BITSIZE (mode);
2009
2010 /* VOIDmode means "infinite" precision. */
2011 if (width == 0)
2012 width = HOST_BITS_PER_WIDE_INT;
2013
2014 switch (code)
2015 {
2016 case SIGN_EXTRACT:
2017 case ZERO_EXTRACT:
2018 if (GET_CODE (op0) == CONST_INT
2019 && GET_CODE (op1) == CONST_INT
2020 && GET_CODE (op2) == CONST_INT
2021 && ((unsigned) INTVAL (op1) + (unsigned) INTVAL (op2) <= width)
2022 && width <= (unsigned) HOST_BITS_PER_WIDE_INT)
2023 {
2024 /* Extracting a bit-field from a constant */
2025 HOST_WIDE_INT val = INTVAL (op0);
2026
2027 if (BITS_BIG_ENDIAN)
2028 val >>= (GET_MODE_BITSIZE (op0_mode)
2029 - INTVAL (op2) - INTVAL (op1));
2030 else
2031 val >>= INTVAL (op2);
2032
2033 if (HOST_BITS_PER_WIDE_INT != INTVAL (op1))
2034 {
2035 /* First zero-extend. */
2036 val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1;
2037 /* If desired, propagate sign bit. */
2038 if (code == SIGN_EXTRACT
2039 && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1))))
2040 val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1);
2041 }
2042
2043 /* Clear the bits that don't belong in our mode,
2044 unless they and our sign bit are all one.
2045 So we get either a reasonable negative value or a reasonable
2046 unsigned value for this mode. */
2047 if (width < HOST_BITS_PER_WIDE_INT
2048 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
2049 != ((HOST_WIDE_INT) (-1) << (width - 1))))
2050 val &= ((HOST_WIDE_INT) 1 << width) - 1;
2051
2052 return GEN_INT (val);
2053 }
2054 break;
2055
2056 case IF_THEN_ELSE:
2057 if (GET_CODE (op0) == CONST_INT)
2058 return op0 != const0_rtx ? op1 : op2;
2059
2060 /* Convert a == b ? b : a to "a". */
2061 if (GET_CODE (op0) == NE && ! side_effects_p (op0)
2062 && (! FLOAT_MODE_P (mode) || flag_fast_math)
2063 && rtx_equal_p (XEXP (op0, 0), op1)
2064 && rtx_equal_p (XEXP (op0, 1), op2))
2065 return op1;
2066 else if (GET_CODE (op0) == EQ && ! side_effects_p (op0)
2067 && (! FLOAT_MODE_P (mode) || flag_fast_math)
2068 && rtx_equal_p (XEXP (op0, 1), op1)
2069 && rtx_equal_p (XEXP (op0, 0), op2))
2070 return op2;
2071 else if (GET_RTX_CLASS (GET_CODE (op0)) == '<' && ! side_effects_p (op0))
2072 {
2073 enum machine_mode cmp_mode = (GET_MODE (XEXP (op0, 0)) == VOIDmode
2074 ? GET_MODE (XEXP (op0, 1))
2075 : GET_MODE (XEXP (op0, 0)));
2076 rtx temp;
2077 if (cmp_mode == VOIDmode)
2078 cmp_mode = op0_mode;
2079 temp = simplify_relational_operation (GET_CODE (op0), cmp_mode,
2080 XEXP (op0, 0), XEXP (op0, 1));
2081
2082 /* See if any simplifications were possible. */
2083 if (temp == const0_rtx)
2084 return op2;
2085 else if (temp == const1_rtx)
2086 return op1;
2087 else if (temp)
2088 op0 = temp;
2089
2090 /* Look for happy constants in op1 and op2. */
2091 if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
2092 {
2093 HOST_WIDE_INT t = INTVAL (op1);
2094 HOST_WIDE_INT f = INTVAL (op2);
2095
2096 if (t == STORE_FLAG_VALUE && f == 0)
2097 code = GET_CODE (op0);
2098 else if (t == 0 && f == STORE_FLAG_VALUE)
2099 {
2100 enum rtx_code tmp;
2101 tmp = reversed_comparison_code (op0, NULL_RTX);
2102 if (tmp == UNKNOWN)
2103 break;
2104 code = tmp;
2105 }
2106 else
2107 break;
2108
2109 return gen_rtx_fmt_ee (code, mode, XEXP (op0, 0), XEXP (op0, 1));
2110 }
2111 }
2112 break;
2113
2114 default:
2115 abort ();
2116 }
2117
2118 return 0;
2119 }
2120
2121 /* Simplify X, an rtx expression.
2122
2123 Return the simplified expression or NULL if no simplifications
2124 were possible.
2125
2126 This is the preferred entry point into the simplification routines;
2127 however, we still allow passes to call the more specific routines.
2128
2129 Right now GCC has three (yes, three) major bodies of RTL simplficiation
2130 code that need to be unified.
2131
2132 1. fold_rtx in cse.c. This code uses various CSE specific
2133 information to aid in RTL simplification.
2134
2135 2. simplify_rtx in combine.c. Similar to fold_rtx, except that
2136 it uses combine specific information to aid in RTL
2137 simplification.
2138
2139 3. The routines in this file.
2140
2141
2142 Long term we want to only have one body of simplification code; to
2143 get to that state I recommend the following steps:
2144
2145 1. Pour over fold_rtx & simplify_rtx and move any simplifications
2146 which are not pass dependent state into these routines.
2147
2148 2. As code is moved by #1, change fold_rtx & simplify_rtx to
2149 use this routine whenever possible.
2150
2151 3. Allow for pass dependent state to be provided to these
2152 routines and add simplifications based on the pass dependent
2153 state. Remove code from cse.c & combine.c that becomes
2154 redundant/dead.
2155
2156 It will take time, but ultimately the compiler will be easier to
2157 maintain and improve. It's totally silly that when we add a
2158 simplification that it needs to be added to 4 places (3 for RTL
2159 simplification and 1 for tree simplification. */
2160
2161 rtx
2162 simplify_rtx (x)
2163 rtx x;
2164 {
2165 enum rtx_code code;
2166 enum machine_mode mode;
2167
2168 mode = GET_MODE (x);
2169 code = GET_CODE (x);
2170
2171 switch (GET_RTX_CLASS (code))
2172 {
2173 case '1':
2174 return simplify_unary_operation (code, mode,
2175 XEXP (x, 0), GET_MODE (XEXP (x, 0)));
2176 case '2':
2177 case 'c':
2178 return simplify_binary_operation (code, mode, XEXP (x, 0), XEXP (x, 1));
2179
2180 case '3':
2181 case 'b':
2182 return simplify_ternary_operation (code, mode, GET_MODE (XEXP (x, 0)),
2183 XEXP (x, 0), XEXP (x, 1), XEXP (x, 2));
2184
2185 case '<':
2186 return simplify_relational_operation (code,
2187 (GET_MODE (XEXP (x, 0)) != VOIDmode
2188 ? GET_MODE (XEXP (x, 0))
2189 : GET_MODE (XEXP (x, 1))),
2190 XEXP (x, 0), XEXP (x, 1));
2191 default:
2192 return NULL;
2193 }
2194 }
2195 \f
2196
2197 /* Allocate a struct elt_list and fill in its two elements with the
2198 arguments. */
2199
2200 static struct elt_list *
2201 new_elt_list (next, elt)
2202 struct elt_list *next;
2203 cselib_val *elt;
2204 {
2205 struct elt_list *el = empty_elt_lists;
2206
2207 if (el)
2208 empty_elt_lists = el->next;
2209 else
2210 el = (struct elt_list *) obstack_alloc (&cselib_obstack,
2211 sizeof (struct elt_list));
2212 el->next = next;
2213 el->elt = elt;
2214 return el;
2215 }
2216
2217 /* Allocate a struct elt_loc_list and fill in its two elements with the
2218 arguments. */
2219
2220 static struct elt_loc_list *
2221 new_elt_loc_list (next, loc)
2222 struct elt_loc_list *next;
2223 rtx loc;
2224 {
2225 struct elt_loc_list *el = empty_elt_loc_lists;
2226
2227 if (el)
2228 empty_elt_loc_lists = el->next;
2229 else
2230 el = (struct elt_loc_list *) obstack_alloc (&cselib_obstack,
2231 sizeof (struct elt_loc_list));
2232 el->next = next;
2233 el->loc = loc;
2234 el->setting_insn = cselib_current_insn;
2235 return el;
2236 }
2237
2238 /* The elt_list at *PL is no longer needed. Unchain it and free its
2239 storage. */
2240
2241 static void
2242 unchain_one_elt_list (pl)
2243 struct elt_list **pl;
2244 {
2245 struct elt_list *l = *pl;
2246
2247 *pl = l->next;
2248 l->next = empty_elt_lists;
2249 empty_elt_lists = l;
2250 }
2251
2252 /* Likewise for elt_loc_lists. */
2253
2254 static void
2255 unchain_one_elt_loc_list (pl)
2256 struct elt_loc_list **pl;
2257 {
2258 struct elt_loc_list *l = *pl;
2259
2260 *pl = l->next;
2261 l->next = empty_elt_loc_lists;
2262 empty_elt_loc_lists = l;
2263 }
2264
2265 /* Likewise for cselib_vals. This also frees the addr_list associated with
2266 V. */
2267
2268 static void
2269 unchain_one_value (v)
2270 cselib_val *v;
2271 {
2272 while (v->addr_list)
2273 unchain_one_elt_list (&v->addr_list);
2274
2275 v->u.next_free = empty_vals;
2276 empty_vals = v;
2277 }
2278
2279 /* Remove all entries from the hash table. Also used during
2280 initialization. If CLEAR_ALL isn't set, then only clear the entries
2281 which are known to have been used. */
2282
2283 static void
2284 clear_table (clear_all)
2285 int clear_all;
2286 {
2287 unsigned int i;
2288
2289 if (clear_all)
2290 for (i = 0; i < cselib_nregs; i++)
2291 REG_VALUES (i) = 0;
2292 else
2293 for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++)
2294 REG_VALUES (VARRAY_UINT (used_regs, i)) = 0;
2295
2296 VARRAY_POP_ALL (used_regs);
2297
2298 htab_empty (hash_table);
2299 obstack_free (&cselib_obstack, cselib_startobj);
2300
2301 empty_vals = 0;
2302 empty_elt_lists = 0;
2303 empty_elt_loc_lists = 0;
2304 n_useless_values = 0;
2305
2306 next_unknown_value = 0;
2307 }
2308
2309 /* The equality test for our hash table. The first argument ENTRY is a table
2310 element (i.e. a cselib_val), while the second arg X is an rtx. We know
2311 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
2312 CONST of an appropriate mode. */
2313
2314 static int
2315 entry_and_rtx_equal_p (entry, x_arg)
2316 const void *entry, *x_arg;
2317 {
2318 struct elt_loc_list *l;
2319 const cselib_val *v = (const cselib_val *) entry;
2320 rtx x = (rtx) x_arg;
2321 enum machine_mode mode = GET_MODE (x);
2322
2323 if (GET_CODE (x) == CONST_INT
2324 || (mode == VOIDmode && GET_CODE (x) == CONST_DOUBLE))
2325 abort ();
2326 if (mode != GET_MODE (v->u.val_rtx))
2327 return 0;
2328
2329 /* Unwrap X if necessary. */
2330 if (GET_CODE (x) == CONST
2331 && (GET_CODE (XEXP (x, 0)) == CONST_INT
2332 || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
2333 x = XEXP (x, 0);
2334
2335 /* We don't guarantee that distinct rtx's have different hash values,
2336 so we need to do a comparison. */
2337 for (l = v->locs; l; l = l->next)
2338 if (rtx_equal_for_cselib_p (l->loc, x))
2339 return 1;
2340
2341 return 0;
2342 }
2343
2344 /* The hash function for our hash table. The value is always computed with
2345 hash_rtx when adding an element; this function just extracts the hash
2346 value from a cselib_val structure. */
2347
2348 static unsigned int
2349 get_value_hash (entry)
2350 const void *entry;
2351 {
2352 const cselib_val *v = (const cselib_val *) entry;
2353 return v->value;
2354 }
2355
2356 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
2357 only return true for values which point to a cselib_val whose value
2358 element has been set to zero, which implies the cselib_val will be
2359 removed. */
2360
2361 int
2362 references_value_p (x, only_useless)
2363 rtx x;
2364 int only_useless;
2365 {
2366 enum rtx_code code = GET_CODE (x);
2367 const char *fmt = GET_RTX_FORMAT (code);
2368 int i, j;
2369
2370 if (GET_CODE (x) == VALUE
2371 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
2372 return 1;
2373
2374 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2375 {
2376 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
2377 return 1;
2378 else if (fmt[i] == 'E')
2379 for (j = 0; j < XVECLEN (x, i); j++)
2380 if (references_value_p (XVECEXP (x, i, j), only_useless))
2381 return 1;
2382 }
2383
2384 return 0;
2385 }
2386
2387 /* For all locations found in X, delete locations that reference useless
2388 values (i.e. values without any location). Called through
2389 htab_traverse. */
2390
2391 static int
2392 discard_useless_locs (x, info)
2393 void **x;
2394 void *info ATTRIBUTE_UNUSED;
2395 {
2396 cselib_val *v = (cselib_val *)*x;
2397 struct elt_loc_list **p = &v->locs;
2398 int had_locs = v->locs != 0;
2399
2400 while (*p)
2401 {
2402 if (references_value_p ((*p)->loc, 1))
2403 unchain_one_elt_loc_list (p);
2404 else
2405 p = &(*p)->next;
2406 }
2407
2408 if (had_locs && v->locs == 0)
2409 {
2410 n_useless_values++;
2411 values_became_useless = 1;
2412 }
2413 return 1;
2414 }
2415
2416 /* If X is a value with no locations, remove it from the hashtable. */
2417
2418 static int
2419 discard_useless_values (x, info)
2420 void **x;
2421 void *info ATTRIBUTE_UNUSED;
2422 {
2423 cselib_val *v = (cselib_val *)*x;
2424
2425 if (v->locs == 0)
2426 {
2427 htab_clear_slot (hash_table, x);
2428 unchain_one_value (v);
2429 n_useless_values--;
2430 }
2431
2432 return 1;
2433 }
2434
2435 /* Clean out useless values (i.e. those which no longer have locations
2436 associated with them) from the hash table. */
2437
2438 static void
2439 remove_useless_values ()
2440 {
2441 /* First pass: eliminate locations that reference the value. That in
2442 turn can make more values useless. */
2443 do
2444 {
2445 values_became_useless = 0;
2446 htab_traverse (hash_table, discard_useless_locs, 0);
2447 }
2448 while (values_became_useless);
2449
2450 /* Second pass: actually remove the values. */
2451 htab_traverse (hash_table, discard_useless_values, 0);
2452
2453 if (n_useless_values != 0)
2454 abort ();
2455 }
2456
2457 /* Return nonzero if we can prove that X and Y contain the same value, taking
2458 our gathered information into account. */
2459
2460 int
2461 rtx_equal_for_cselib_p (x, y)
2462 rtx x, y;
2463 {
2464 enum rtx_code code;
2465 const char *fmt;
2466 int i;
2467
2468 if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
2469 {
2470 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
2471
2472 if (e)
2473 x = e->u.val_rtx;
2474 }
2475
2476 if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
2477 {
2478 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
2479
2480 if (e)
2481 y = e->u.val_rtx;
2482 }
2483
2484 if (x == y)
2485 return 1;
2486
2487 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
2488 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
2489
2490 if (GET_CODE (x) == VALUE)
2491 {
2492 cselib_val *e = CSELIB_VAL_PTR (x);
2493 struct elt_loc_list *l;
2494
2495 for (l = e->locs; l; l = l->next)
2496 {
2497 rtx t = l->loc;
2498
2499 /* Avoid infinite recursion. */
2500 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2501 continue;
2502 else if (rtx_equal_for_cselib_p (t, y))
2503 return 1;
2504 }
2505
2506 return 0;
2507 }
2508
2509 if (GET_CODE (y) == VALUE)
2510 {
2511 cselib_val *e = CSELIB_VAL_PTR (y);
2512 struct elt_loc_list *l;
2513
2514 for (l = e->locs; l; l = l->next)
2515 {
2516 rtx t = l->loc;
2517
2518 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2519 continue;
2520 else if (rtx_equal_for_cselib_p (x, t))
2521 return 1;
2522 }
2523
2524 return 0;
2525 }
2526
2527 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
2528 return 0;
2529
2530 /* This won't be handled correctly by the code below. */
2531 if (GET_CODE (x) == LABEL_REF)
2532 return XEXP (x, 0) == XEXP (y, 0);
2533
2534 code = GET_CODE (x);
2535 fmt = GET_RTX_FORMAT (code);
2536
2537 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2538 {
2539 int j;
2540
2541 switch (fmt[i])
2542 {
2543 case 'w':
2544 if (XWINT (x, i) != XWINT (y, i))
2545 return 0;
2546 break;
2547
2548 case 'n':
2549 case 'i':
2550 if (XINT (x, i) != XINT (y, i))
2551 return 0;
2552 break;
2553
2554 case 'V':
2555 case 'E':
2556 /* Two vectors must have the same length. */
2557 if (XVECLEN (x, i) != XVECLEN (y, i))
2558 return 0;
2559
2560 /* And the corresponding elements must match. */
2561 for (j = 0; j < XVECLEN (x, i); j++)
2562 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
2563 XVECEXP (y, i, j)))
2564 return 0;
2565 break;
2566
2567 case 'e':
2568 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
2569 return 0;
2570 break;
2571
2572 case 'S':
2573 case 's':
2574 if (strcmp (XSTR (x, i), XSTR (y, i)))
2575 return 0;
2576 break;
2577
2578 case 'u':
2579 /* These are just backpointers, so they don't matter. */
2580 break;
2581
2582 case '0':
2583 case 't':
2584 break;
2585
2586 /* It is believed that rtx's at this level will never
2587 contain anything but integers and other rtx's,
2588 except for within LABEL_REFs and SYMBOL_REFs. */
2589 default:
2590 abort ();
2591 }
2592 }
2593 return 1;
2594 }
2595
2596 /* We need to pass down the mode of constants through the hash table
2597 functions. For that purpose, wrap them in a CONST of the appropriate
2598 mode. */
2599 static rtx
2600 wrap_constant (mode, x)
2601 enum machine_mode mode;
2602 rtx x;
2603 {
2604 if (GET_CODE (x) != CONST_INT
2605 && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
2606 return x;
2607 if (mode == VOIDmode)
2608 abort ();
2609 return gen_rtx_CONST (mode, x);
2610 }
2611
2612 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
2613 For registers and memory locations, we look up their cselib_val structure
2614 and return its VALUE element.
2615 Possible reasons for return 0 are: the object is volatile, or we couldn't
2616 find a register or memory location in the table and CREATE is zero. If
2617 CREATE is nonzero, table elts are created for regs and mem.
2618 MODE is used in hashing for CONST_INTs only;
2619 otherwise the mode of X is used. */
2620
2621 static unsigned int
2622 hash_rtx (x, mode, create)
2623 rtx x;
2624 enum machine_mode mode;
2625 int create;
2626 {
2627 cselib_val *e;
2628 int i, j;
2629 enum rtx_code code;
2630 const char *fmt;
2631 unsigned int hash = 0;
2632
2633 /* repeat is used to turn tail-recursion into iteration. */
2634 repeat:
2635 code = GET_CODE (x);
2636 hash += (unsigned) code + (unsigned) GET_MODE (x);
2637
2638 switch (code)
2639 {
2640 case MEM:
2641 case REG:
2642 e = cselib_lookup (x, GET_MODE (x), create);
2643 if (! e)
2644 return 0;
2645
2646 return e->value;
2647
2648 case CONST_INT:
2649 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
2650 return hash ? hash : (unsigned int) CONST_INT;
2651
2652 case CONST_DOUBLE:
2653 /* This is like the general case, except that it only counts
2654 the integers representing the constant. */
2655 hash += (unsigned) code + (unsigned) GET_MODE (x);
2656 if (GET_MODE (x) != VOIDmode)
2657 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2658 hash += XWINT (x, i);
2659 else
2660 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2661 + (unsigned) CONST_DOUBLE_HIGH (x));
2662 return hash ? hash : (unsigned int) CONST_DOUBLE;
2663
2664 /* Assume there is only one rtx object for any given label. */
2665 case LABEL_REF:
2666 hash
2667 += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2668 return hash ? hash : (unsigned int) LABEL_REF;
2669
2670 case SYMBOL_REF:
2671 hash
2672 += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2673 return hash ? hash : (unsigned int) SYMBOL_REF;
2674
2675 case PRE_DEC:
2676 case PRE_INC:
2677 case POST_DEC:
2678 case POST_INC:
2679 case POST_MODIFY:
2680 case PRE_MODIFY:
2681 case PC:
2682 case CC0:
2683 case CALL:
2684 case UNSPEC_VOLATILE:
2685 return 0;
2686
2687 case ASM_OPERANDS:
2688 if (MEM_VOLATILE_P (x))
2689 return 0;
2690
2691 break;
2692
2693 default:
2694 break;
2695 }
2696
2697 i = GET_RTX_LENGTH (code) - 1;
2698 fmt = GET_RTX_FORMAT (code);
2699 for (; i >= 0; i--)
2700 {
2701 if (fmt[i] == 'e')
2702 {
2703 rtx tem = XEXP (x, i);
2704 unsigned int tem_hash;
2705
2706 /* If we are about to do the last recursive call
2707 needed at this level, change it into iteration.
2708 This function is called enough to be worth it. */
2709 if (i == 0)
2710 {
2711 x = tem;
2712 goto repeat;
2713 }
2714
2715 tem_hash = hash_rtx (tem, 0, create);
2716 if (tem_hash == 0)
2717 return 0;
2718
2719 hash += tem_hash;
2720 }
2721 else if (fmt[i] == 'E')
2722 for (j = 0; j < XVECLEN (x, i); j++)
2723 {
2724 unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
2725
2726 if (tem_hash == 0)
2727 return 0;
2728
2729 hash += tem_hash;
2730 }
2731 else if (fmt[i] == 's')
2732 {
2733 const unsigned char *p = (const unsigned char *) XSTR (x, i);
2734
2735 if (p)
2736 while (*p)
2737 hash += *p++;
2738 }
2739 else if (fmt[i] == 'i')
2740 hash += XINT (x, i);
2741 else if (fmt[i] == '0' || fmt[i] == 't')
2742 /* unused */;
2743 else
2744 abort ();
2745 }
2746
2747 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
2748 }
2749
2750 /* Create a new value structure for VALUE and initialize it. The mode of the
2751 value is MODE. */
2752
2753 static cselib_val *
2754 new_cselib_val (value, mode)
2755 unsigned int value;
2756 enum machine_mode mode;
2757 {
2758 cselib_val *e = empty_vals;
2759
2760 if (e)
2761 empty_vals = e->u.next_free;
2762 else
2763 e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
2764
2765 if (value == 0)
2766 abort ();
2767
2768 e->value = value;
2769 e->u.val_rtx = gen_rtx_VALUE (mode);
2770 CSELIB_VAL_PTR (e->u.val_rtx) = e;
2771 e->addr_list = 0;
2772 e->locs = 0;
2773 return e;
2774 }
2775
2776 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
2777 contains the data at this address. X is a MEM that represents the
2778 value. Update the two value structures to represent this situation. */
2779
2780 static void
2781 add_mem_for_addr (addr_elt, mem_elt, x)
2782 cselib_val *addr_elt, *mem_elt;
2783 rtx x;
2784 {
2785 rtx new;
2786 struct elt_loc_list *l;
2787
2788 /* Avoid duplicates. */
2789 for (l = mem_elt->locs; l; l = l->next)
2790 if (GET_CODE (l->loc) == MEM
2791 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
2792 return;
2793
2794 new = gen_rtx_MEM (GET_MODE (x), addr_elt->u.val_rtx);
2795 MEM_COPY_ATTRIBUTES (new, x);
2796
2797 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
2798 mem_elt->locs = new_elt_loc_list (mem_elt->locs, new);
2799 }
2800
2801 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
2802 If CREATE, make a new one if we haven't seen it before. */
2803
2804 static cselib_val *
2805 cselib_lookup_mem (x, create)
2806 rtx x;
2807 int create;
2808 {
2809 enum machine_mode mode = GET_MODE (x);
2810 void **slot;
2811 cselib_val *addr;
2812 cselib_val *mem_elt;
2813 struct elt_list *l;
2814
2815 if (MEM_VOLATILE_P (x) || mode == BLKmode
2816 || (FLOAT_MODE_P (mode) && flag_float_store))
2817 return 0;
2818
2819 /* Look up the value for the address. */
2820 addr = cselib_lookup (XEXP (x, 0), mode, create);
2821 if (! addr)
2822 return 0;
2823
2824 /* Find a value that describes a value of our mode at that address. */
2825 for (l = addr->addr_list; l; l = l->next)
2826 if (GET_MODE (l->elt->u.val_rtx) == mode)
2827 return l->elt;
2828
2829 if (! create)
2830 return 0;
2831
2832 mem_elt = new_cselib_val (++next_unknown_value, mode);
2833 add_mem_for_addr (addr, mem_elt, x);
2834 slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
2835 mem_elt->value, INSERT);
2836 *slot = mem_elt;
2837 return mem_elt;
2838 }
2839
2840 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2841 with VALUE expressions. This way, it becomes independent of changes
2842 to registers and memory.
2843 X isn't actually modified; if modifications are needed, new rtl is
2844 allocated. However, the return value can share rtl with X. */
2845
2846 static rtx
2847 cselib_subst_to_values (x)
2848 rtx x;
2849 {
2850 enum rtx_code code = GET_CODE (x);
2851 const char *fmt = GET_RTX_FORMAT (code);
2852 cselib_val *e;
2853 struct elt_list *l;
2854 rtx copy = x;
2855 int i;
2856
2857 switch (code)
2858 {
2859 case REG:
2860 for (l = REG_VALUES (REGNO (x)); l; l = l->next)
2861 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2862 return l->elt->u.val_rtx;
2863
2864 abort ();
2865
2866 case MEM:
2867 e = cselib_lookup_mem (x, 0);
2868 if (! e)
2869 abort ();
2870 return e->u.val_rtx;
2871
2872 /* CONST_DOUBLEs must be special-cased here so that we won't try to
2873 look up the CONST_DOUBLE_MEM inside. */
2874 case CONST_DOUBLE:
2875 case CONST_INT:
2876 return x;
2877
2878 default:
2879 break;
2880 }
2881
2882 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2883 {
2884 if (fmt[i] == 'e')
2885 {
2886 rtx t = cselib_subst_to_values (XEXP (x, i));
2887
2888 if (t != XEXP (x, i) && x == copy)
2889 copy = shallow_copy_rtx (x);
2890
2891 XEXP (copy, i) = t;
2892 }
2893 else if (fmt[i] == 'E')
2894 {
2895 int j, k;
2896
2897 for (j = 0; j < XVECLEN (x, i); j++)
2898 {
2899 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
2900
2901 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
2902 {
2903 if (x == copy)
2904 copy = shallow_copy_rtx (x);
2905
2906 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
2907 for (k = 0; k < j; k++)
2908 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
2909 }
2910
2911 XVECEXP (copy, i, j) = t;
2912 }
2913 }
2914 }
2915
2916 return copy;
2917 }
2918
2919 /* Look up the rtl expression X in our tables and return the value it has.
2920 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
2921 we create a new one if possible, using mode MODE if X doesn't have a mode
2922 (i.e. because it's a constant). */
2923
2924 cselib_val *
2925 cselib_lookup (x, mode, create)
2926 rtx x;
2927 enum machine_mode mode;
2928 int create;
2929 {
2930 void **slot;
2931 cselib_val *e;
2932 unsigned int hashval;
2933
2934 if (GET_MODE (x) != VOIDmode)
2935 mode = GET_MODE (x);
2936
2937 if (GET_CODE (x) == VALUE)
2938 return CSELIB_VAL_PTR (x);
2939
2940 if (GET_CODE (x) == REG)
2941 {
2942 struct elt_list *l;
2943 unsigned int i = REGNO (x);
2944
2945 for (l = REG_VALUES (i); l; l = l->next)
2946 if (mode == GET_MODE (l->elt->u.val_rtx))
2947 return l->elt;
2948
2949 if (! create)
2950 return 0;
2951
2952 e = new_cselib_val (++next_unknown_value, GET_MODE (x));
2953 e->locs = new_elt_loc_list (e->locs, x);
2954 if (REG_VALUES (i) == 0)
2955 VARRAY_PUSH_UINT (used_regs, i);
2956 REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
2957 slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
2958 *slot = e;
2959 return e;
2960 }
2961
2962 if (GET_CODE (x) == MEM)
2963 return cselib_lookup_mem (x, create);
2964
2965 hashval = hash_rtx (x, mode, create);
2966 /* Can't even create if hashing is not possible. */
2967 if (! hashval)
2968 return 0;
2969
2970 slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
2971 hashval, create ? INSERT : NO_INSERT);
2972 if (slot == 0)
2973 return 0;
2974
2975 e = (cselib_val *) *slot;
2976 if (e)
2977 return e;
2978
2979 e = new_cselib_val (hashval, mode);
2980
2981 /* We have to fill the slot before calling cselib_subst_to_values:
2982 the hash table is inconsistent until we do so, and
2983 cselib_subst_to_values will need to do lookups. */
2984 *slot = (void *) e;
2985 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
2986 return e;
2987 }
2988
2989 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2990 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2991 is used to determine how many hard registers are being changed. If MODE
2992 is VOIDmode, then only REGNO is being changed; this is used when
2993 invalidating call clobbered registers across a call. */
2994
2995 static void
2996 cselib_invalidate_regno (regno, mode)
2997 unsigned int regno;
2998 enum machine_mode mode;
2999 {
3000 unsigned int endregno;
3001 unsigned int i;
3002
3003 /* If we see pseudos after reload, something is _wrong_. */
3004 if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
3005 && reg_renumber[regno] >= 0)
3006 abort ();
3007
3008 /* Determine the range of registers that must be invalidated. For
3009 pseudos, only REGNO is affected. For hard regs, we must take MODE
3010 into account, and we must also invalidate lower register numbers
3011 if they contain values that overlap REGNO. */
3012 endregno = regno + 1;
3013 if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode)
3014 endregno = regno + HARD_REGNO_NREGS (regno, mode);
3015
3016 for (i = 0; i < endregno; i++)
3017 {
3018 struct elt_list **l = &REG_VALUES (i);
3019
3020 /* Go through all known values for this reg; if it overlaps the range
3021 we're invalidating, remove the value. */
3022 while (*l)
3023 {
3024 cselib_val *v = (*l)->elt;
3025 struct elt_loc_list **p;
3026 unsigned int this_last = i;
3027
3028 if (i < FIRST_PSEUDO_REGISTER)
3029 this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
3030
3031 if (this_last < regno)
3032 {
3033 l = &(*l)->next;
3034 continue;
3035 }
3036
3037 /* We have an overlap. */
3038 unchain_one_elt_list (l);
3039
3040 /* Now, we clear the mapping from value to reg. It must exist, so
3041 this code will crash intentionally if it doesn't. */
3042 for (p = &v->locs; ; p = &(*p)->next)
3043 {
3044 rtx x = (*p)->loc;
3045
3046 if (GET_CODE (x) == REG && REGNO (x) == i)
3047 {
3048 unchain_one_elt_loc_list (p);
3049 break;
3050 }
3051 }
3052 if (v->locs == 0)
3053 n_useless_values++;
3054 }
3055 }
3056 }
3057
3058 /* The memory at address MEM_BASE is being changed.
3059 Return whether this change will invalidate VAL. */
3060
3061 static int
3062 cselib_mem_conflict_p (mem_base, val)
3063 rtx mem_base;
3064 rtx val;
3065 {
3066 enum rtx_code code;
3067 const char *fmt;
3068 int i, j;
3069
3070 code = GET_CODE (val);
3071 switch (code)
3072 {
3073 /* Get rid of a few simple cases quickly. */
3074 case REG:
3075 case PC:
3076 case CC0:
3077 case SCRATCH:
3078 case CONST:
3079 case CONST_INT:
3080 case CONST_DOUBLE:
3081 case SYMBOL_REF:
3082 case LABEL_REF:
3083 return 0;
3084
3085 case MEM:
3086 if (GET_MODE (mem_base) == BLKmode
3087 || GET_MODE (val) == BLKmode
3088 || anti_dependence (val, mem_base))
3089 return 1;
3090
3091 /* The address may contain nested MEMs. */
3092 break;
3093
3094 default:
3095 break;
3096 }
3097
3098 fmt = GET_RTX_FORMAT (code);
3099 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3100 {
3101 if (fmt[i] == 'e')
3102 {
3103 if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
3104 return 1;
3105 }
3106 else if (fmt[i] == 'E')
3107 for (j = 0; j < XVECLEN (val, i); j++)
3108 if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
3109 return 1;
3110 }
3111
3112 return 0;
3113 }
3114
3115 /* For the value found in SLOT, walk its locations to determine if any overlap
3116 INFO (which is a MEM rtx). */
3117
3118 static int
3119 cselib_invalidate_mem_1 (slot, info)
3120 void **slot;
3121 void *info;
3122 {
3123 cselib_val *v = (cselib_val *) *slot;
3124 rtx mem_rtx = (rtx) info;
3125 struct elt_loc_list **p = &v->locs;
3126 int had_locs = v->locs != 0;
3127
3128 while (*p)
3129 {
3130 rtx x = (*p)->loc;
3131 cselib_val *addr;
3132 struct elt_list **mem_chain;
3133
3134 /* MEMs may occur in locations only at the top level; below
3135 that every MEM or REG is substituted by its VALUE. */
3136 if (GET_CODE (x) != MEM
3137 || ! cselib_mem_conflict_p (mem_rtx, x))
3138 {
3139 p = &(*p)->next;
3140 continue;
3141 }
3142
3143 /* This one overlaps. */
3144 /* We must have a mapping from this MEM's address to the
3145 value (E). Remove that, too. */
3146 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
3147 mem_chain = &addr->addr_list;
3148 for (;;)
3149 {
3150 if ((*mem_chain)->elt == v)
3151 {
3152 unchain_one_elt_list (mem_chain);
3153 break;
3154 }
3155
3156 mem_chain = &(*mem_chain)->next;
3157 }
3158
3159 unchain_one_elt_loc_list (p);
3160 }
3161
3162 if (had_locs && v->locs == 0)
3163 n_useless_values++;
3164
3165 return 1;
3166 }
3167
3168 /* Invalidate any locations in the table which are changed because of a
3169 store to MEM_RTX. If this is called because of a non-const call
3170 instruction, MEM_RTX is (mem:BLK const0_rtx). */
3171
3172 static void
3173 cselib_invalidate_mem (mem_rtx)
3174 rtx mem_rtx;
3175 {
3176 htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
3177 }
3178
3179 /* Invalidate DEST, which is being assigned to or clobbered. The second and
3180 the third parameter exist so that this function can be passed to
3181 note_stores; they are ignored. */
3182
3183 static void
3184 cselib_invalidate_rtx (dest, ignore, data)
3185 rtx dest;
3186 rtx ignore ATTRIBUTE_UNUSED;
3187 void *data ATTRIBUTE_UNUSED;
3188 {
3189 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
3190 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
3191 dest = XEXP (dest, 0);
3192
3193 if (GET_CODE (dest) == REG)
3194 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
3195 else if (GET_CODE (dest) == MEM)
3196 cselib_invalidate_mem (dest);
3197
3198 /* Some machines don't define AUTO_INC_DEC, but they still use push
3199 instructions. We need to catch that case here in order to
3200 invalidate the stack pointer correctly. Note that invalidating
3201 the stack pointer is different from invalidating DEST. */
3202 if (push_operand (dest, GET_MODE (dest)))
3203 cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
3204 }
3205
3206 /* Record the result of a SET instruction. DEST is being set; the source
3207 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
3208 describes its address. */
3209
3210 static void
3211 cselib_record_set (dest, src_elt, dest_addr_elt)
3212 rtx dest;
3213 cselib_val *src_elt, *dest_addr_elt;
3214 {
3215 int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
3216
3217 if (src_elt == 0 || side_effects_p (dest))
3218 return;
3219
3220 if (dreg >= 0)
3221 {
3222 if (REG_VALUES (dreg) == 0)
3223 VARRAY_PUSH_UINT (used_regs, dreg);
3224
3225 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
3226 if (src_elt->locs == 0)
3227 n_useless_values--;
3228 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
3229 }
3230 else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
3231 {
3232 if (src_elt->locs == 0)
3233 n_useless_values--;
3234 add_mem_for_addr (dest_addr_elt, src_elt, dest);
3235 }
3236 }
3237
3238 /* Describe a single set that is part of an insn. */
3239 struct set
3240 {
3241 rtx src;
3242 rtx dest;
3243 cselib_val *src_elt;
3244 cselib_val *dest_addr_elt;
3245 };
3246
3247 /* There is no good way to determine how many elements there can be
3248 in a PARALLEL. Since it's fairly cheap, use a really large number. */
3249 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
3250
3251 /* Record the effects of any sets in INSN. */
3252 static void
3253 cselib_record_sets (insn)
3254 rtx insn;
3255 {
3256 int n_sets = 0;
3257 int i;
3258 struct set sets[MAX_SETS];
3259 rtx body = PATTERN (insn);
3260
3261 body = PATTERN (insn);
3262 /* Find all sets. */
3263 if (GET_CODE (body) == SET)
3264 {
3265 sets[0].src = SET_SRC (body);
3266 sets[0].dest = SET_DEST (body);
3267 n_sets = 1;
3268 }
3269 else if (GET_CODE (body) == PARALLEL)
3270 {
3271 /* Look through the PARALLEL and record the values being
3272 set, if possible. Also handle any CLOBBERs. */
3273 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3274 {
3275 rtx x = XVECEXP (body, 0, i);
3276
3277 if (GET_CODE (x) == SET)
3278 {
3279 sets[n_sets].src = SET_SRC (x);
3280 sets[n_sets].dest = SET_DEST (x);
3281 n_sets++;
3282 }
3283 }
3284 }
3285
3286 /* Look up the values that are read. Do this before invalidating the
3287 locations that are written. */
3288 for (i = 0; i < n_sets; i++)
3289 {
3290 rtx dest = sets[i].dest;
3291
3292 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
3293 the low part after invalidating any knowledge about larger modes. */
3294 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
3295 sets[i].dest = dest = XEXP (dest, 0);
3296
3297 /* We don't know how to record anything but REG or MEM. */
3298 if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
3299 {
3300 sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (dest), 1);
3301 if (GET_CODE (dest) == MEM)
3302 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
3303 else
3304 sets[i].dest_addr_elt = 0;
3305 }
3306 }
3307
3308 /* Invalidate all locations written by this insn. Note that the elts we
3309 looked up in the previous loop aren't affected, just some of their
3310 locations may go away. */
3311 note_stores (body, cselib_invalidate_rtx, NULL);
3312
3313 /* Now enter the equivalences in our tables. */
3314 for (i = 0; i < n_sets; i++)
3315 {
3316 rtx dest = sets[i].dest;
3317 if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
3318 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
3319 }
3320 }
3321
3322 /* Record the effects of INSN. */
3323
3324 void
3325 cselib_process_insn (insn)
3326 rtx insn;
3327 {
3328 int i;
3329 rtx x;
3330
3331 cselib_current_insn = insn;
3332
3333 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
3334 if (GET_CODE (insn) == CODE_LABEL
3335 || (GET_CODE (insn) == NOTE
3336 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3337 || (GET_CODE (insn) == INSN
3338 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
3339 && MEM_VOLATILE_P (PATTERN (insn))))
3340 {
3341 clear_table (0);
3342 return;
3343 }
3344
3345 if (! INSN_P (insn))
3346 {
3347 cselib_current_insn = 0;
3348 return;
3349 }
3350
3351 /* If this is a call instruction, forget anything stored in a
3352 call clobbered register, or, if this is not a const call, in
3353 memory. */
3354 if (GET_CODE (insn) == CALL_INSN)
3355 {
3356 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3357 if (call_used_regs[i])
3358 cselib_invalidate_regno (i, VOIDmode);
3359
3360 if (! CONST_CALL_P (insn))
3361 cselib_invalidate_mem (callmem);
3362 }
3363
3364 cselib_record_sets (insn);
3365
3366 #ifdef AUTO_INC_DEC
3367 /* Clobber any registers which appear in REG_INC notes. We
3368 could keep track of the changes to their values, but it is
3369 unlikely to help. */
3370 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
3371 if (REG_NOTE_KIND (x) == REG_INC)
3372 cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
3373 #endif
3374
3375 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3376 after we have processed the insn. */
3377 if (GET_CODE (insn) == CALL_INSN)
3378 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3379 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3380 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
3381
3382 cselib_current_insn = 0;
3383
3384 if (n_useless_values > MAX_USELESS_VALUES)
3385 remove_useless_values ();
3386 }
3387
3388 /* Make sure our varrays are big enough. Not called from any cselib routines;
3389 it must be called by the user if it allocated new registers. */
3390
3391 void
3392 cselib_update_varray_sizes ()
3393 {
3394 unsigned int nregs = max_reg_num ();
3395
3396 if (nregs == cselib_nregs)
3397 return;
3398
3399 cselib_nregs = nregs;
3400 VARRAY_GROW (reg_values, nregs);
3401 VARRAY_GROW (used_regs, nregs);
3402 }
3403
3404 /* Initialize cselib for one pass. The caller must also call
3405 init_alias_analysis. */
3406
3407 void
3408 cselib_init ()
3409 {
3410 /* These are only created once. */
3411 if (! callmem)
3412 {
3413 gcc_obstack_init (&cselib_obstack);
3414 cselib_startobj = obstack_alloc (&cselib_obstack, 0);
3415
3416 callmem = gen_rtx_MEM (BLKmode, const0_rtx);
3417 ggc_add_rtx_root (&callmem, 1);
3418 }
3419
3420 cselib_nregs = max_reg_num ();
3421 VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
3422 VARRAY_UINT_INIT (used_regs, cselib_nregs, "used_regs");
3423 hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
3424 clear_table (1);
3425 }
3426
3427 /* Called when the current user is done with cselib. */
3428
3429 void
3430 cselib_finish ()
3431 {
3432 clear_table (0);
3433 VARRAY_FREE (reg_values);
3434 VARRAY_FREE (used_regs);
3435 htab_delete (hash_table);
3436 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org