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