?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix typos in comment
[official-gcc.git] / gcc / simplify-rtx.c
blob67f7babfc1ffd395b9e3c123fab119da0e3cebad
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 #endif
952
953 /* Convert (compare (gt (flags) 0) (lt (flags) 0)) to (flags). */
954 if (((GET_CODE (op0) == GT && GET_CODE (op1) == LT)
955 || (GET_CODE (op0) == GTU && GET_CODE (op1) == LTU))
956 && XEXP (op0, 1) == const0_rtx && XEXP (op1, 1) == const0_rtx)
957 {
958 rtx xop00 = XEXP (op0, 0);
959 rtx xop10 = XEXP (op1, 0);
960
961 #ifdef HAVE_cc0
962 if (GET_CODE (xop00) == CC0 && GET_CODE (xop10) == CC0)
963 #else
964 if (GET_CODE (xop00) == REG && GET_CODE (xop10) == REG
965 && GET_MODE (xop00) == GET_MODE (xop10)
966 && REGNO (xop00) == REGNO (xop10)
967 && GET_MODE_CLASS (GET_MODE (xop00)) == MODE_CC
968 && GET_MODE_CLASS (GET_MODE (xop10)) == MODE_CC)
969 #endif
970 return xop00;
971 }
972
973 break;
974 case MINUS:
975 /* None of these optimizations can be done for IEEE
976 floating point. */
977 if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
978 && FLOAT_MODE_P (mode) && ! flag_fast_math)
979 break;
980
981 /* We can't assume x-x is 0 even with non-IEEE floating point,
982 but since it is zero except in very strange circumstances, we
983 will treat it as zero with -ffast-math. */
984 if (rtx_equal_p (op0, op1)
985 && ! side_effects_p (op0)
986 && (! FLOAT_MODE_P (mode) || flag_fast_math))
987 return CONST0_RTX (mode);
988
989 /* Change subtraction from zero into negation. */
990 if (op0 == CONST0_RTX (mode))
991 return gen_rtx_NEG (mode, op1);
992
993 /* (-1 - a) is ~a. */
994 if (op0 == constm1_rtx)
995 return gen_rtx_NOT (mode, op1);
996
997 /* Subtracting 0 has no effect. */
998 if (op1 == CONST0_RTX (mode))
999 return op0;
1000
1001 /* See if this is something like X * C - X or vice versa or
1002 if the multiplication is written as a shift. If so, we can
1003 distribute and make a new multiply, shift, or maybe just
1004 have X (if C is 2 in the example above). But don't make
1005 real multiply if we didn't have one before. */
1006
1007 if (! FLOAT_MODE_P (mode))
1008 {
1009 HOST_WIDE_INT coeff0 = 1, coeff1 = 1;
1010 rtx lhs = op0, rhs = op1;
1011 int had_mult = 0;
1012
1013 if (GET_CODE (lhs) == NEG)
1014 coeff0 = -1, lhs = XEXP (lhs, 0);
1015 else if (GET_CODE (lhs) == MULT
1016 && GET_CODE (XEXP (lhs, 1)) == CONST_INT)
1017 {
1018 coeff0 = INTVAL (XEXP (lhs, 1)), lhs = XEXP (lhs, 0);
1019 had_mult = 1;
1020 }
1021 else if (GET_CODE (lhs) == ASHIFT
1022 && GET_CODE (XEXP (lhs, 1)) == CONST_INT
1023 && INTVAL (XEXP (lhs, 1)) >= 0
1024 && INTVAL (XEXP (lhs, 1)) < HOST_BITS_PER_WIDE_INT)
1025 {
1026 coeff0 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (lhs, 1));
1027 lhs = XEXP (lhs, 0);
1028 }
1029
1030 if (GET_CODE (rhs) == NEG)
1031 coeff1 = - 1, rhs = XEXP (rhs, 0);
1032 else if (GET_CODE (rhs) == MULT
1033 && GET_CODE (XEXP (rhs, 1)) == CONST_INT)
1034 {
1035 coeff1 = INTVAL (XEXP (rhs, 1)), rhs = XEXP (rhs, 0);
1036 had_mult = 1;
1037 }
1038 else if (GET_CODE (rhs) == ASHIFT
1039 && GET_CODE (XEXP (rhs, 1)) == CONST_INT
1040 && INTVAL (XEXP (rhs, 1)) >= 0
1041 && INTVAL (XEXP (rhs, 1)) < HOST_BITS_PER_WIDE_INT)
1042 {
1043 coeff1 = ((HOST_WIDE_INT) 1) << INTVAL (XEXP (rhs, 1));
1044 rhs = XEXP (rhs, 0);
1045 }
1046
1047 if (rtx_equal_p (lhs, rhs))
1048 {
1049 tem = simplify_gen_binary (MULT, mode, lhs,
1050 GEN_INT (coeff0 - coeff1));
1051 return (GET_CODE (tem) == MULT && ! had_mult) ? 0 : tem;
1052 }
1053 }
1054
1055 /* (a - (-b)) -> (a + b). */
1056 if (GET_CODE (op1) == NEG)
1057 return simplify_gen_binary (PLUS, mode, op0, XEXP (op1, 0));
1058
1059 /* If one of the operands is a PLUS or a MINUS, see if we can
1060 simplify this by the associative law.
1061 Don't use the associative law for floating point.
1062 The inaccuracy makes it nonassociative,
1063 and subtle programs can break if operations are associated. */
1064
1065 if (INTEGRAL_MODE_P (mode)
1066 && (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
1067 || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
1068 && (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
1069 return tem;
1070
1071 /* Don't let a relocatable value get a negative coeff. */
1072 if (GET_CODE (op1) == CONST_INT && GET_MODE (op0) != VOIDmode)
1073 return plus_constant (op0, - INTVAL (op1));
1074
1075 /* (x - (x & y)) -> (x & ~y) */
1076 if (GET_CODE (op1) == AND)
1077 {
1078 if (rtx_equal_p (op0, XEXP (op1, 0)))
1079 return simplify_gen_binary (AND, mode, op0,
1080 gen_rtx_NOT (mode, XEXP (op1, 1)));
1081 if (rtx_equal_p (op0, XEXP (op1, 1)))
1082 return simplify_gen_binary (AND, mode, op0,
1083 gen_rtx_NOT (mode, XEXP (op1, 0)));
1084 }
1085 break;
1086
1087 case MULT:
1088 if (op1 == constm1_rtx)
1089 {
1090 tem = simplify_unary_operation (NEG, mode, op0, mode);
1091
1092 return tem ? tem : gen_rtx_NEG (mode, op0);
1093 }
1094
1095 /* In IEEE floating point, x*0 is not always 0. */
1096 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1097 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1098 && op1 == CONST0_RTX (mode)
1099 && ! side_effects_p (op0))
1100 return op1;
1101
1102 /* In IEEE floating point, x*1 is not equivalent to x for nans.
1103 However, ANSI says we can drop signals,
1104 so we can do this anyway. */
1105 if (op1 == CONST1_RTX (mode))
1106 return op0;
1107
1108 /* Convert multiply by constant power of two into shift unless
1109 we are still generating RTL. This test is a kludge. */
1110 if (GET_CODE (op1) == CONST_INT
1111 && (val = exact_log2 (INTVAL (op1))) >= 0
1112 /* If the mode is larger than the host word size, and the
1113 uppermost bit is set, then this isn't a power of two due
1114 to implicit sign extension. */
1115 && (width <= HOST_BITS_PER_WIDE_INT
1116 || val != HOST_BITS_PER_WIDE_INT - 1)
1117 && ! rtx_equal_function_value_matters)
1118 return gen_rtx_ASHIFT (mode, op0, GEN_INT (val));
1119
1120 if (GET_CODE (op1) == CONST_DOUBLE
1121 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
1122 {
1123 REAL_VALUE_TYPE d;
1124 jmp_buf handler;
1125 int op1is2, op1ism1;
1126
1127 if (setjmp (handler))
1128 return 0;
1129
1130 set_float_handler (handler);
1131 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1132 op1is2 = REAL_VALUES_EQUAL (d, dconst2);
1133 op1ism1 = REAL_VALUES_EQUAL (d, dconstm1);
1134 set_float_handler (NULL_PTR);
1135
1136 /* x*2 is x+x and x*(-1) is -x */
1137 if (op1is2 && GET_MODE (op0) == mode)
1138 return gen_rtx_PLUS (mode, op0, copy_rtx (op0));
1139
1140 else if (op1ism1 && GET_MODE (op0) == mode)
1141 return gen_rtx_NEG (mode, op0);
1142 }
1143 break;
1144
1145 case IOR:
1146 if (op1 == const0_rtx)
1147 return op0;
1148 if (GET_CODE (op1) == CONST_INT
1149 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1150 return op1;
1151 if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1152 return op0;
1153 /* A | (~A) -> -1 */
1154 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1155 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1156 && ! side_effects_p (op0)
1157 && GET_MODE_CLASS (mode) != MODE_CC)
1158 return constm1_rtx;
1159 break;
1160
1161 case XOR:
1162 if (op1 == const0_rtx)
1163 return op0;
1164 if (GET_CODE (op1) == CONST_INT
1165 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1166 return gen_rtx_NOT (mode, op0);
1167 if (op0 == op1 && ! side_effects_p (op0)
1168 && GET_MODE_CLASS (mode) != MODE_CC)
1169 return const0_rtx;
1170 break;
1171
1172 case AND:
1173 if (op1 == const0_rtx && ! side_effects_p (op0))
1174 return const0_rtx;
1175 if (GET_CODE (op1) == CONST_INT
1176 && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
1177 return op0;
1178 if (op0 == op1 && ! side_effects_p (op0)
1179 && GET_MODE_CLASS (mode) != MODE_CC)
1180 return op0;
1181 /* A & (~A) -> 0 */
1182 if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
1183 || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
1184 && ! side_effects_p (op0)
1185 && GET_MODE_CLASS (mode) != MODE_CC)
1186 return const0_rtx;
1187 break;
1188
1189 case UDIV:
1190 /* Convert divide by power of two into shift (divide by 1 handled
1191 below). */
1192 if (GET_CODE (op1) == CONST_INT
1193 && (arg1 = exact_log2 (INTVAL (op1))) > 0)
1194 return gen_rtx_LSHIFTRT (mode, op0, GEN_INT (arg1));
1195
1196 /* ... fall through ... */
1197
1198 case DIV:
1199 if (op1 == CONST1_RTX (mode))
1200 return op0;
1201
1202 /* In IEEE floating point, 0/x is not always 0. */
1203 if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1204 || ! FLOAT_MODE_P (mode) || flag_fast_math)
1205 && op0 == CONST0_RTX (mode)
1206 && ! side_effects_p (op1))
1207 return op0;
1208
1209 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1210 /* Change division by a constant into multiplication. Only do
1211 this with -ffast-math until an expert says it is safe in
1212 general. */
1213 else if (GET_CODE (op1) == CONST_DOUBLE
1214 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
1215 && op1 != CONST0_RTX (mode)
1216 && flag_fast_math)
1217 {
1218 REAL_VALUE_TYPE d;
1219 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
1220
1221 if (! REAL_VALUES_EQUAL (d, dconst0))
1222 {
1223 #if defined (REAL_ARITHMETIC)
1224 REAL_ARITHMETIC (d, rtx_to_tree_code (DIV), dconst1, d);
1225 return gen_rtx_MULT (mode, op0,
1226 CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
1227 #else
1228 return
1229 gen_rtx_MULT (mode, op0,
1230 CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
1231 #endif
1232 }
1233 }
1234 #endif
1235 break;
1236
1237 case UMOD:
1238 /* Handle modulus by power of two (mod with 1 handled below). */
1239 if (GET_CODE (op1) == CONST_INT
1240 && exact_log2 (INTVAL (op1)) > 0)
1241 return gen_rtx_AND (mode, op0, GEN_INT (INTVAL (op1) - 1));
1242
1243 /* ... fall through ... */
1244
1245 case MOD:
1246 if ((op0 == const0_rtx || op1 == const1_rtx)
1247 && ! side_effects_p (op0) && ! side_effects_p (op1))
1248 return const0_rtx;
1249 break;
1250
1251 case ROTATERT:
1252 case ROTATE:
1253 /* Rotating ~0 always results in ~0. */
1254 if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_WIDE_INT
1255 && (unsigned HOST_WIDE_INT) INTVAL (op0) == GET_MODE_MASK (mode)
1256 && ! side_effects_p (op1))
1257 return op0;
1258
1259 /* ... fall through ... */
1260
1261 case ASHIFT:
1262 case ASHIFTRT:
1263 case LSHIFTRT:
1264 if (op1 == const0_rtx)
1265 return op0;
1266 if (op0 == const0_rtx && ! side_effects_p (op1))
1267 return op0;
1268 break;
1269
1270 case SMIN:
1271 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1272 && INTVAL (op1) == (HOST_WIDE_INT) 1 << (width -1)
1273 && ! side_effects_p (op0))
1274 return op1;
1275 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1276 return op0;
1277 break;
1278
1279 case SMAX:
1280 if (width <= HOST_BITS_PER_WIDE_INT && GET_CODE (op1) == CONST_INT
1281 && ((unsigned HOST_WIDE_INT) INTVAL (op1)
1282 == (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode) >> 1)
1283 && ! side_effects_p (op0))
1284 return op1;
1285 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1286 return op0;
1287 break;
1288
1289 case UMIN:
1290 if (op1 == const0_rtx && ! side_effects_p (op0))
1291 return op1;
1292 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1293 return op0;
1294 break;
1295
1296 case UMAX:
1297 if (op1 == constm1_rtx && ! side_effects_p (op0))
1298 return op1;
1299 else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
1300 return op0;
1301 break;
1302
1303 default:
1304 abort ();
1305 }
1306
1307 return 0;
1308 }
1309
1310 /* Get the integer argument values in two forms:
1311 zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S. */
1312
1313 arg0 = INTVAL (op0);
1314 arg1 = INTVAL (op1);
1315
1316 if (width < HOST_BITS_PER_WIDE_INT)
1317 {
1318 arg0 &= ((HOST_WIDE_INT) 1 << width) - 1;
1319 arg1 &= ((HOST_WIDE_INT) 1 << width) - 1;
1320
1321 arg0s = arg0;
1322 if (arg0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1323 arg0s |= ((HOST_WIDE_INT) (-1) << width);
1324
1325 arg1s = arg1;
1326 if (arg1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1327 arg1s |= ((HOST_WIDE_INT) (-1) << width);
1328 }
1329 else
1330 {
1331 arg0s = arg0;
1332 arg1s = arg1;
1333 }
1334
1335 /* Compute the value of the arithmetic. */
1336
1337 switch (code)
1338 {
1339 case PLUS:
1340 val = arg0s + arg1s;
1341 break;
1342
1343 case MINUS:
1344 val = arg0s - arg1s;
1345 break;
1346
1347 case MULT:
1348 val = arg0s * arg1s;
1349 break;
1350
1351 case DIV:
1352 if (arg1s == 0)
1353 return 0;
1354 val = arg0s / arg1s;
1355 break;
1356
1357 case MOD:
1358 if (arg1s == 0)
1359 return 0;
1360 val = arg0s % arg1s;
1361 break;
1362
1363 case UDIV:
1364 if (arg1 == 0)
1365 return 0;
1366 val = (unsigned HOST_WIDE_INT) arg0 / arg1;
1367 break;
1368
1369 case UMOD:
1370 if (arg1 == 0)
1371 return 0;
1372 val = (unsigned HOST_WIDE_INT) arg0 % arg1;
1373 break;
1374
1375 case AND:
1376 val = arg0 & arg1;
1377 break;
1378
1379 case IOR:
1380 val = arg0 | arg1;
1381 break;
1382
1383 case XOR:
1384 val = arg0 ^ arg1;
1385 break;
1386
1387 case LSHIFTRT:
1388 /* If shift count is undefined, don't fold it; let the machine do
1389 what it wants. But truncate it if the machine will do that. */
1390 if (arg1 < 0)
1391 return 0;
1392
1393 #ifdef SHIFT_COUNT_TRUNCATED
1394 if (SHIFT_COUNT_TRUNCATED)
1395 arg1 %= width;
1396 #endif
1397
1398 val = ((unsigned HOST_WIDE_INT) arg0) >> arg1;
1399 break;
1400
1401 case ASHIFT:
1402 if (arg1 < 0)
1403 return 0;
1404
1405 #ifdef SHIFT_COUNT_TRUNCATED
1406 if (SHIFT_COUNT_TRUNCATED)
1407 arg1 %= width;
1408 #endif
1409
1410 val = ((unsigned HOST_WIDE_INT) arg0) << arg1;
1411 break;
1412
1413 case ASHIFTRT:
1414 if (arg1 < 0)
1415 return 0;
1416
1417 #ifdef SHIFT_COUNT_TRUNCATED
1418 if (SHIFT_COUNT_TRUNCATED)
1419 arg1 %= width;
1420 #endif
1421
1422 val = arg0s >> arg1;
1423
1424 /* Bootstrap compiler may not have sign extended the right shift.
1425 Manually extend the sign to insure bootstrap cc matches gcc. */
1426 if (arg0s < 0 && arg1 > 0)
1427 val |= ((HOST_WIDE_INT) -1) << (HOST_BITS_PER_WIDE_INT - arg1);
1428
1429 break;
1430
1431 case ROTATERT:
1432 if (arg1 < 0)
1433 return 0;
1434
1435 arg1 %= width;
1436 val = ((((unsigned HOST_WIDE_INT) arg0) << (width - arg1))
1437 | (((unsigned HOST_WIDE_INT) arg0) >> arg1));
1438 break;
1439
1440 case ROTATE:
1441 if (arg1 < 0)
1442 return 0;
1443
1444 arg1 %= width;
1445 val = ((((unsigned HOST_WIDE_INT) arg0) << arg1)
1446 | (((unsigned HOST_WIDE_INT) arg0) >> (width - arg1)));
1447 break;
1448
1449 case COMPARE:
1450 /* Do nothing here. */
1451 return 0;
1452
1453 case SMIN:
1454 val = arg0s <= arg1s ? arg0s : arg1s;
1455 break;
1456
1457 case UMIN:
1458 val = ((unsigned HOST_WIDE_INT) arg0
1459 <= (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1460 break;
1461
1462 case SMAX:
1463 val = arg0s > arg1s ? arg0s : arg1s;
1464 break;
1465
1466 case UMAX:
1467 val = ((unsigned HOST_WIDE_INT) arg0
1468 > (unsigned HOST_WIDE_INT) arg1 ? arg0 : arg1);
1469 break;
1470
1471 default:
1472 abort ();
1473 }
1474
1475 val = trunc_int_for_mode (val, mode);
1476
1477 return GEN_INT (val);
1478 }
1479 \f
1480 /* Simplify a PLUS or MINUS, at least one of whose operands may be another
1481 PLUS or MINUS.
1482
1483 Rather than test for specific case, we do this by a brute-force method
1484 and do all possible simplifications until no more changes occur. Then
1485 we rebuild the operation. */
1486
1487 static rtx
1488 simplify_plus_minus (code, mode, op0, op1)
1489 enum rtx_code code;
1490 enum machine_mode mode;
1491 rtx op0, op1;
1492 {
1493 rtx ops[8];
1494 int negs[8];
1495 rtx result, tem;
1496 int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
1497 int first = 1, negate = 0, changed;
1498 int i, j;
1499
1500 bzero ((char *) ops, sizeof ops);
1501
1502 /* Set up the two operands and then expand them until nothing has been
1503 changed. If we run out of room in our array, give up; this should
1504 almost never happen. */
1505
1506 ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
1507
1508 changed = 1;
1509 while (changed)
1510 {
1511 changed = 0;
1512
1513 for (i = 0; i < n_ops; i++)
1514 switch (GET_CODE (ops[i]))
1515 {
1516 case PLUS:
1517 case MINUS:
1518 if (n_ops == 7)
1519 return 0;
1520
1521 ops[n_ops] = XEXP (ops[i], 1);
1522 negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
1523 ops[i] = XEXP (ops[i], 0);
1524 input_ops++;
1525 changed = 1;
1526 break;
1527
1528 case NEG:
1529 ops[i] = XEXP (ops[i], 0);
1530 negs[i] = ! negs[i];
1531 changed = 1;
1532 break;
1533
1534 case CONST:
1535 ops[i] = XEXP (ops[i], 0);
1536 input_consts++;
1537 changed = 1;
1538 break;
1539
1540 case NOT:
1541 /* ~a -> (-a - 1) */
1542 if (n_ops != 7)
1543 {
1544 ops[n_ops] = constm1_rtx;
1545 negs[n_ops++] = negs[i];
1546 ops[i] = XEXP (ops[i], 0);
1547 negs[i] = ! negs[i];
1548 changed = 1;
1549 }
1550 break;
1551
1552 case CONST_INT:
1553 if (negs[i])
1554 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
1555 break;
1556
1557 default:
1558 break;
1559 }
1560 }
1561
1562 /* If we only have two operands, we can't do anything. */
1563 if (n_ops <= 2)
1564 return 0;
1565
1566 /* Now simplify each pair of operands until nothing changes. The first
1567 time through just simplify constants against each other. */
1568
1569 changed = 1;
1570 while (changed)
1571 {
1572 changed = first;
1573
1574 for (i = 0; i < n_ops - 1; i++)
1575 for (j = i + 1; j < n_ops; j++)
1576 if (ops[i] != 0 && ops[j] != 0
1577 && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
1578 {
1579 rtx lhs = ops[i], rhs = ops[j];
1580 enum rtx_code ncode = PLUS;
1581
1582 if (negs[i] && ! negs[j])
1583 lhs = ops[j], rhs = ops[i], ncode = MINUS;
1584 else if (! negs[i] && negs[j])
1585 ncode = MINUS;
1586
1587 tem = simplify_binary_operation (ncode, mode, lhs, rhs);
1588 if (tem)
1589 {
1590 ops[i] = tem, ops[j] = 0;
1591 negs[i] = negs[i] && negs[j];
1592 if (GET_CODE (tem) == NEG)
1593 ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
1594
1595 if (GET_CODE (ops[i]) == CONST_INT && negs[i])
1596 ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
1597 changed = 1;
1598 }
1599 }
1600
1601 first = 0;
1602 }
1603
1604 /* Pack all the operands to the lower-numbered entries and give up if
1605 we didn't reduce the number of operands we had. Make sure we
1606 count a CONST as two operands. If we have the same number of
1607 operands, but have made more CONSTs than we had, this is also
1608 an improvement, so accept it. */
1609
1610 for (i = 0, j = 0; j < n_ops; j++)
1611 if (ops[j] != 0)
1612 {
1613 ops[i] = ops[j], negs[i++] = negs[j];
1614 if (GET_CODE (ops[j]) == CONST)
1615 n_consts++;
1616 }
1617
1618 if (i + n_consts > input_ops
1619 || (i + n_consts == input_ops && n_consts <= input_consts))
1620 return 0;
1621
1622 n_ops = i;
1623
1624 /* If we have a CONST_INT, put it last. */
1625 for (i = 0; i < n_ops - 1; i++)
1626 if (GET_CODE (ops[i]) == CONST_INT)
1627 {
1628 tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
1629 j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
1630 }
1631
1632 /* Put a non-negated operand first. If there aren't any, make all
1633 operands positive and negate the whole thing later. */
1634 for (i = 0; i < n_ops && negs[i]; i++)
1635 ;
1636
1637 if (i == n_ops)
1638 {
1639 for (i = 0; i < n_ops; i++)
1640 negs[i] = 0;
1641 negate = 1;
1642 }
1643 else if (i != 0)
1644 {
1645 tem = ops[0], ops[0] = ops[i], ops[i] = tem;
1646 j = negs[0], negs[0] = negs[i], negs[i] = j;
1647 }
1648
1649 /* Now make the result by performing the requested operations. */
1650 result = ops[0];
1651 for (i = 1; i < n_ops; i++)
1652 result = simplify_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
1653
1654 return negate ? gen_rtx_NEG (mode, result) : result;
1655 }
1656
1657 struct cfc_args
1658 {
1659 rtx op0, op1; /* Input */
1660 int equal, op0lt, op1lt; /* Output */
1661 };
1662
1663 static void
1664 check_fold_consts (data)
1665 PTR data;
1666 {
1667 struct cfc_args *args = (struct cfc_args *) data;
1668 REAL_VALUE_TYPE d0, d1;
1669
1670 REAL_VALUE_FROM_CONST_DOUBLE (d0, args->op0);
1671 REAL_VALUE_FROM_CONST_DOUBLE (d1, args->op1);
1672 args->equal = REAL_VALUES_EQUAL (d0, d1);
1673 args->op0lt = REAL_VALUES_LESS (d0, d1);
1674 args->op1lt = REAL_VALUES_LESS (d1, d0);
1675 }
1676
1677 /* Like simplify_binary_operation except used for relational operators.
1678 MODE is the mode of the operands, not that of the result. If MODE
1679 is VOIDmode, both operands must also be VOIDmode and we compare the
1680 operands in "infinite precision".
1681
1682 If no simplification is possible, this function returns zero. Otherwise,
1683 it returns either const_true_rtx or const0_rtx. */
1684
1685 rtx
1686 simplify_relational_operation (code, mode, op0, op1)
1687 enum rtx_code code;
1688 enum machine_mode mode;
1689 rtx op0, op1;
1690 {
1691 int equal, op0lt, op0ltu, op1lt, op1ltu;
1692 rtx tem;
1693
1694 /* If op0 is a compare, extract the comparison arguments from it. */
1695 if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
1696 op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
1697
1698 /* We can't simplify MODE_CC values since we don't know what the
1699 actual comparison is. */
1700 if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC
1701 #ifdef HAVE_cc0
1702 || op0 == cc0_rtx
1703 #endif
1704 )
1705 return 0;
1706
1707 /* Make sure the constant is second. */
1708 if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
1709 || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
1710 {
1711 tem = op0, op0 = op1, op1 = tem;
1712 code = swap_condition (code);
1713 }
1714
1715 /* For integer comparisons of A and B maybe we can simplify A - B and can
1716 then simplify a comparison of that with zero. If A and B are both either
1717 a register or a CONST_INT, this can't help; testing for these cases will
1718 prevent infinite recursion here and speed things up.
1719
1720 If CODE is an unsigned comparison, then we can never do this optimization,
1721 because it gives an incorrect result if the subtraction wraps around zero.
1722 ANSI C defines unsigned operations such that they never overflow, and
1723 thus such cases can not be ignored. */
1724
1725 if (INTEGRAL_MODE_P (mode) && op1 != const0_rtx
1726 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == CONST_INT)
1727 && (GET_CODE (op1) == REG || GET_CODE (op1) == CONST_INT))
1728 && 0 != (tem = simplify_binary_operation (MINUS, mode, op0, op1))
1729 && code != GTU && code != GEU && code != LTU && code != LEU)
1730 return simplify_relational_operation (signed_condition (code),
1731 mode, tem, const0_rtx);
1732
1733 /* For non-IEEE floating-point, if the two operands are equal, we know the
1734 result. */
1735 if (rtx_equal_p (op0, op1)
1736 && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1737 || ! FLOAT_MODE_P (GET_MODE (op0)) || flag_fast_math))
1738 equal = 1, op0lt = 0, op0ltu = 0, op1lt = 0, op1ltu = 0;
1739
1740 /* If the operands are floating-point constants, see if we can fold
1741 the result. */
1742 #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
1743 else if (GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
1744 && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
1745 {
1746 struct cfc_args args;
1747
1748 /* Setup input for check_fold_consts() */
1749 args.op0 = op0;
1750 args.op1 = op1;
1751
1752 if (do_float_handler(check_fold_consts, (PTR) &args) == 0)
1753 /* We got an exception from check_fold_consts() */
1754 return 0;
1755
1756 /* Receive output from check_fold_consts() */
1757 equal = args.equal;
1758 op0lt = op0ltu = args.op0lt;
1759 op1lt = op1ltu = args.op1lt;
1760 }
1761 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
1762
1763 /* Otherwise, see if the operands are both integers. */
1764 else if ((GET_MODE_CLASS (mode) == MODE_INT || mode == VOIDmode)
1765 && (GET_CODE (op0) == CONST_DOUBLE || GET_CODE (op0) == CONST_INT)
1766 && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
1767 {
1768 int width = GET_MODE_BITSIZE (mode);
1769 HOST_WIDE_INT l0s, h0s, l1s, h1s;
1770 unsigned HOST_WIDE_INT l0u, h0u, l1u, h1u;
1771
1772 /* Get the two words comprising each integer constant. */
1773 if (GET_CODE (op0) == CONST_DOUBLE)
1774 {
1775 l0u = l0s = CONST_DOUBLE_LOW (op0);
1776 h0u = h0s = CONST_DOUBLE_HIGH (op0);
1777 }
1778 else
1779 {
1780 l0u = l0s = INTVAL (op0);
1781 h0u = h0s = HWI_SIGN_EXTEND (l0s);
1782 }
1783
1784 if (GET_CODE (op1) == CONST_DOUBLE)
1785 {
1786 l1u = l1s = CONST_DOUBLE_LOW (op1);
1787 h1u = h1s = CONST_DOUBLE_HIGH (op1);
1788 }
1789 else
1790 {
1791 l1u = l1s = INTVAL (op1);
1792 h1u = h1s = HWI_SIGN_EXTEND (l1s);
1793 }
1794
1795 /* If WIDTH is nonzero and smaller than HOST_BITS_PER_WIDE_INT,
1796 we have to sign or zero-extend the values. */
1797 if (width != 0 && width <= HOST_BITS_PER_WIDE_INT)
1798 h0u = h1u = 0, h0s = HWI_SIGN_EXTEND (l0s), h1s = HWI_SIGN_EXTEND (l1s);
1799
1800 if (width != 0 && width < HOST_BITS_PER_WIDE_INT)
1801 {
1802 l0u &= ((HOST_WIDE_INT) 1 << width) - 1;
1803 l1u &= ((HOST_WIDE_INT) 1 << width) - 1;
1804
1805 if (l0s & ((HOST_WIDE_INT) 1 << (width - 1)))
1806 l0s |= ((HOST_WIDE_INT) (-1) << width);
1807
1808 if (l1s & ((HOST_WIDE_INT) 1 << (width - 1)))
1809 l1s |= ((HOST_WIDE_INT) (-1) << width);
1810 }
1811
1812 equal = (h0u == h1u && l0u == l1u);
1813 op0lt = (h0s < h1s || (h0s == h1s && l0u < l1u));
1814 op1lt = (h1s < h0s || (h1s == h0s && l1u < l0u));
1815 op0ltu = (h0u < h1u || (h0u == h1u && l0u < l1u));
1816 op1ltu = (h1u < h0u || (h1u == h0u && l1u < l0u));
1817 }
1818
1819 /* Otherwise, there are some code-specific tests we can make. */
1820 else
1821 {
1822 switch (code)
1823 {
1824 case EQ:
1825 /* References to the frame plus a constant or labels cannot
1826 be zero, but a SYMBOL_REF can due to #pragma weak. */
1827 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1828 || GET_CODE (op0) == LABEL_REF)
1829 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1830 /* On some machines, the ap reg can be 0 sometimes. */
1831 && op0 != arg_pointer_rtx
1832 #endif
1833 )
1834 return const0_rtx;
1835 break;
1836
1837 case NE:
1838 if (((NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
1839 || GET_CODE (op0) == LABEL_REF)
1840 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1841 && op0 != arg_pointer_rtx
1842 #endif
1843 )
1844 return const_true_rtx;
1845 break;
1846
1847 case GEU:
1848 /* Unsigned values are never negative. */
1849 if (op1 == const0_rtx)
1850 return const_true_rtx;
1851 break;
1852
1853 case LTU:
1854 if (op1 == const0_rtx)
1855 return const0_rtx;
1856 break;
1857
1858 case LEU:
1859 /* Unsigned values are never greater than the largest
1860 unsigned value. */
1861 if (GET_CODE (op1) == CONST_INT
1862 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1863 && INTEGRAL_MODE_P (mode))
1864 return const_true_rtx;
1865 break;
1866
1867 case GTU:
1868 if (GET_CODE (op1) == CONST_INT
1869 && (unsigned HOST_WIDE_INT) INTVAL (op1) == GET_MODE_MASK (mode)
1870 && INTEGRAL_MODE_P (mode))
1871 return const0_rtx;
1872 break;
1873
1874 default:
1875 break;
1876 }
1877
1878 return 0;
1879 }
1880
1881 /* If we reach here, EQUAL, OP0LT, OP0LTU, OP1LT, and OP1LTU are set
1882 as appropriate. */
1883 switch (code)
1884 {
1885 case EQ:
1886 return equal ? const_true_rtx : const0_rtx;
1887 case NE:
1888 return ! equal ? const_true_rtx : const0_rtx;
1889 case LT:
1890 return op0lt ? const_true_rtx : const0_rtx;
1891 case GT:
1892 return op1lt ? const_true_rtx : const0_rtx;
1893 case LTU:
1894 return op0ltu ? const_true_rtx : const0_rtx;
1895 case GTU:
1896 return op1ltu ? const_true_rtx : const0_rtx;
1897 case LE:
1898 return equal || op0lt ? const_true_rtx : const0_rtx;
1899 case GE:
1900 return equal || op1lt ? const_true_rtx : const0_rtx;
1901 case LEU:
1902 return equal || op0ltu ? const_true_rtx : const0_rtx;
1903 case GEU:
1904 return equal || op1ltu ? const_true_rtx : const0_rtx;
1905 default:
1906 abort ();
1907 }
1908 }
1909 \f
1910 /* Simplify CODE, an operation with result mode MODE and three operands,
1911 OP0, OP1, and OP2. OP0_MODE was the mode of OP0 before it became
1912 a constant. Return 0 if no simplifications is possible. */
1913
1914 rtx
1915 simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
1916 enum rtx_code code;
1917 enum machine_mode mode, op0_mode;
1918 rtx op0, op1, op2;
1919 {
1920 unsigned int width = GET_MODE_BITSIZE (mode);
1921
1922 /* VOIDmode means "infinite" precision. */
1923 if (width == 0)
1924 width = HOST_BITS_PER_WIDE_INT;
1925
1926 switch (code)
1927 {
1928 case SIGN_EXTRACT:
1929 case ZERO_EXTRACT:
1930 if (GET_CODE (op0) == CONST_INT
1931 && GET_CODE (op1) == CONST_INT
1932 && GET_CODE (op2) == CONST_INT
1933 && ((unsigned) INTVAL (op1) + (unsigned) INTVAL (op2) <= width)
1934 && width <= (unsigned) HOST_BITS_PER_WIDE_INT)
1935 {
1936 /* Extracting a bit-field from a constant */
1937 HOST_WIDE_INT val = INTVAL (op0);
1938
1939 if (BITS_BIG_ENDIAN)
1940 val >>= (GET_MODE_BITSIZE (op0_mode)
1941 - INTVAL (op2) - INTVAL (op1));
1942 else
1943 val >>= INTVAL (op2);
1944
1945 if (HOST_BITS_PER_WIDE_INT != INTVAL (op1))
1946 {
1947 /* First zero-extend. */
1948 val &= ((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1;
1949 /* If desired, propagate sign bit. */
1950 if (code == SIGN_EXTRACT
1951 && (val & ((HOST_WIDE_INT) 1 << (INTVAL (op1) - 1))))
1952 val |= ~ (((HOST_WIDE_INT) 1 << INTVAL (op1)) - 1);
1953 }
1954
1955 /* Clear the bits that don't belong in our mode,
1956 unless they and our sign bit are all one.
1957 So we get either a reasonable negative value or a reasonable
1958 unsigned value for this mode. */
1959 if (width < HOST_BITS_PER_WIDE_INT
1960 && ((val & ((HOST_WIDE_INT) (-1) << (width - 1)))
1961 != ((HOST_WIDE_INT) (-1) << (width - 1))))
1962 val &= ((HOST_WIDE_INT) 1 << width) - 1;
1963
1964 return GEN_INT (val);
1965 }
1966 break;
1967
1968 case IF_THEN_ELSE:
1969 if (GET_CODE (op0) == CONST_INT)
1970 return op0 != const0_rtx ? op1 : op2;
1971
1972 /* Convert a == b ? b : a to "a". */
1973 if (GET_CODE (op0) == NE && ! side_effects_p (op0)
1974 && rtx_equal_p (XEXP (op0, 0), op1)
1975 && rtx_equal_p (XEXP (op0, 1), op2))
1976 return op1;
1977 else if (GET_CODE (op0) == EQ && ! side_effects_p (op0)
1978 && rtx_equal_p (XEXP (op0, 1), op1)
1979 && rtx_equal_p (XEXP (op0, 0), op2))
1980 return op2;
1981 else if (GET_RTX_CLASS (GET_CODE (op0)) == '<' && ! side_effects_p (op0))
1982 {
1983 rtx temp
1984 = simplify_relational_operation (GET_CODE (op0), op0_mode,
1985 XEXP (op0, 0), XEXP (op0, 1));
1986
1987 /* See if any simplifications were possible. */
1988 if (temp == const0_rtx)
1989 return op2;
1990 else if (temp == const1_rtx)
1991 return op1;
1992 else if (temp)
1993 op0 = temp;
1994
1995 /* Look for happy constants in op1 and op2. */
1996 if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
1997 {
1998 HOST_WIDE_INT t = INTVAL (op1);
1999 HOST_WIDE_INT f = INTVAL (op2);
2000
2001 if (t == STORE_FLAG_VALUE && f == 0)
2002 code = GET_CODE (op0);
2003 else if (t == 0 && f == STORE_FLAG_VALUE
2004 && can_reverse_comparison_p (op0, NULL_RTX))
2005 code = reverse_condition (GET_CODE (op0));
2006 else
2007 break;
2008
2009 return gen_rtx_fmt_ee (code, mode, XEXP (op0, 0), XEXP (op0, 1));
2010 }
2011 }
2012 break;
2013
2014 default:
2015 abort ();
2016 }
2017
2018 return 0;
2019 }
2020
2021 /* Simplify X, an rtx expression.
2022
2023 Return the simplified expression or NULL if no simplifications
2024 were possible.
2025
2026 This is the preferred entry point into the simplification routines;
2027 however, we still allow passes to call the more specific routines.
2028
2029 Right now GCC has three (yes, three) major bodies of RTL simplficiation
2030 code that need to be unified.
2031
2032 1. fold_rtx in cse.c. This code uses various CSE specific
2033 information to aid in RTL simplification.
2034
2035 2. simplify_rtx in combine.c. Similar to fold_rtx, except that
2036 it uses combine specific information to aid in RTL
2037 simplification.
2038
2039 3. The routines in this file.
2040
2041
2042 Long term we want to only have one body of simplification code; to
2043 get to that state I recommend the following steps:
2044
2045 1. Pour over fold_rtx & simplify_rtx and move any simplifications
2046 which are not pass dependent state into these routines.
2047
2048 2. As code is moved by #1, change fold_rtx & simplify_rtx to
2049 use this routine whenever possible.
2050
2051 3. Allow for pass dependent state to be provided to these
2052 routines and add simplifications based on the pass dependent
2053 state. Remove code from cse.c & combine.c that becomes
2054 redundant/dead.
2055
2056 It will take time, but ultimately the compiler will be easier to
2057 maintain and improve. It's totally silly that when we add a
2058 simplification that it needs to be added to 4 places (3 for RTL
2059 simplification and 1 for tree simplification. */
2060
2061 rtx
2062 simplify_rtx (x)
2063 rtx x;
2064 {
2065 enum rtx_code code;
2066 enum machine_mode mode;
2067
2068 mode = GET_MODE (x);
2069 code = GET_CODE (x);
2070
2071 switch (GET_RTX_CLASS (code))
2072 {
2073 case '1':
2074 return simplify_unary_operation (code, mode,
2075 XEXP (x, 0), GET_MODE (XEXP (x, 0)));
2076 case '2':
2077 case 'c':
2078 return simplify_binary_operation (code, mode, XEXP (x, 0), XEXP (x, 1));
2079
2080 case '3':
2081 case 'b':
2082 return simplify_ternary_operation (code, mode, GET_MODE (XEXP (x, 0)),
2083 XEXP (x, 0), XEXP (x, 1), XEXP (x, 2));
2084
2085 case '<':
2086 return simplify_relational_operation (code, GET_MODE (XEXP (x, 0)),
2087 XEXP (x, 0), XEXP (x, 1));
2088 default:
2089 return NULL;
2090 }
2091 }
2092 \f
2093
2094 /* Allocate a struct elt_list and fill in its two elements with the
2095 arguments. */
2096
2097 static struct elt_list *
2098 new_elt_list (next, elt)
2099 struct elt_list *next;
2100 cselib_val *elt;
2101 {
2102 struct elt_list *el = empty_elt_lists;
2103
2104 if (el)
2105 empty_elt_lists = el->next;
2106 else
2107 el = (struct elt_list *) obstack_alloc (&cselib_obstack,
2108 sizeof (struct elt_list));
2109 el->next = next;
2110 el->elt = elt;
2111 return el;
2112 }
2113
2114 /* Allocate a struct elt_loc_list and fill in its two elements with the
2115 arguments. */
2116
2117 static struct elt_loc_list *
2118 new_elt_loc_list (next, loc)
2119 struct elt_loc_list *next;
2120 rtx loc;
2121 {
2122 struct elt_loc_list *el = empty_elt_loc_lists;
2123
2124 if (el)
2125 empty_elt_loc_lists = el->next;
2126 else
2127 el = (struct elt_loc_list *) obstack_alloc (&cselib_obstack,
2128 sizeof (struct elt_loc_list));
2129 el->next = next;
2130 el->loc = loc;
2131 el->setting_insn = cselib_current_insn;
2132 return el;
2133 }
2134
2135 /* The elt_list at *PL is no longer needed. Unchain it and free its
2136 storage. */
2137
2138 static void
2139 unchain_one_elt_list (pl)
2140 struct elt_list **pl;
2141 {
2142 struct elt_list *l = *pl;
2143
2144 *pl = l->next;
2145 l->next = empty_elt_lists;
2146 empty_elt_lists = l;
2147 }
2148
2149 /* Likewise for elt_loc_lists. */
2150
2151 static void
2152 unchain_one_elt_loc_list (pl)
2153 struct elt_loc_list **pl;
2154 {
2155 struct elt_loc_list *l = *pl;
2156
2157 *pl = l->next;
2158 l->next = empty_elt_loc_lists;
2159 empty_elt_loc_lists = l;
2160 }
2161
2162 /* Likewise for cselib_vals. This also frees the addr_list associated with
2163 V. */
2164
2165 static void
2166 unchain_one_value (v)
2167 cselib_val *v;
2168 {
2169 while (v->addr_list)
2170 unchain_one_elt_list (&v->addr_list);
2171
2172 v->u.next_free = empty_vals;
2173 empty_vals = v;
2174 }
2175
2176 /* Remove all entries from the hash table. Also used during
2177 initialization. */
2178
2179 static void
2180 clear_table ()
2181 {
2182 unsigned int i;
2183
2184 for (i = 0; i < cselib_nregs; i++)
2185 REG_VALUES (i) = 0;
2186
2187 htab_empty (hash_table);
2188 obstack_free (&cselib_obstack, cselib_startobj);
2189
2190 empty_vals = 0;
2191 empty_elt_lists = 0;
2192 empty_elt_loc_lists = 0;
2193 n_useless_values = 0;
2194
2195 next_unknown_value = 0;
2196 }
2197
2198 /* The equality test for our hash table. The first argument ENTRY is a table
2199 element (i.e. a cselib_val), while the second arg X is an rtx. */
2200
2201 static int
2202 entry_and_rtx_equal_p (entry, x_arg)
2203 const void *entry, *x_arg;
2204 {
2205 struct elt_loc_list *l;
2206 const cselib_val *v = (const cselib_val *) entry;
2207 rtx x = (rtx) x_arg;
2208
2209 /* We don't guarantee that distinct rtx's have different hash values,
2210 so we need to do a comparison. */
2211 for (l = v->locs; l; l = l->next)
2212 if (rtx_equal_for_cselib_p (l->loc, x))
2213 return 1;
2214
2215 return 0;
2216 }
2217
2218 /* The hash function for our hash table. The value is always computed with
2219 hash_rtx when adding an element; this function just extracts the hash
2220 value from a cselib_val structure. */
2221
2222 static unsigned int
2223 get_value_hash (entry)
2224 const void *entry;
2225 {
2226 const cselib_val *v = (const cselib_val *) entry;
2227 return v->value;
2228 }
2229
2230 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
2231 only return true for values which point to a cselib_val whose value
2232 element has been set to zero, which implies the cselib_val will be
2233 removed. */
2234
2235 int
2236 references_value_p (x, only_useless)
2237 rtx x;
2238 int only_useless;
2239 {
2240 enum rtx_code code = GET_CODE (x);
2241 const char *fmt = GET_RTX_FORMAT (code);
2242 int i, j;
2243
2244 if (GET_CODE (x) == VALUE
2245 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
2246 return 1;
2247
2248 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2249 {
2250 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
2251 return 1;
2252 else if (fmt[i] == 'E')
2253 for (j = 0; j < XVECLEN (x, i); j++)
2254 if (references_value_p (XVECEXP (x, i, j), only_useless))
2255 return 1;
2256 }
2257
2258 return 0;
2259 }
2260
2261 /* For all locations found in X, delete locations that reference useless
2262 values (i.e. values without any location). Called through
2263 htab_traverse. */
2264
2265 static int
2266 discard_useless_locs (x, info)
2267 void **x;
2268 void *info ATTRIBUTE_UNUSED;
2269 {
2270 cselib_val *v = (cselib_val *)*x;
2271 struct elt_loc_list **p = &v->locs;
2272 int had_locs = v->locs != 0;
2273
2274 while (*p)
2275 {
2276 if (references_value_p ((*p)->loc, 1))
2277 unchain_one_elt_loc_list (p);
2278 else
2279 p = &(*p)->next;
2280 }
2281
2282 if (had_locs && v->locs == 0)
2283 {
2284 n_useless_values++;
2285 values_became_useless = 1;
2286 }
2287 return 1;
2288 }
2289
2290 /* If X is a value with no locations, remove it from the hashtable. */
2291
2292 static int
2293 discard_useless_values (x, info)
2294 void **x;
2295 void *info ATTRIBUTE_UNUSED;
2296 {
2297 cselib_val *v = (cselib_val *)*x;
2298
2299 if (v->locs == 0)
2300 {
2301 htab_clear_slot (hash_table, x);
2302 unchain_one_value (v);
2303 n_useless_values--;
2304 }
2305
2306 return 1;
2307 }
2308
2309 /* Clean out useless values (i.e. those which no longer have locations
2310 associated with them) from the hash table. */
2311
2312 static void
2313 remove_useless_values ()
2314 {
2315 /* First pass: eliminate locations that reference the value. That in
2316 turn can make more values useless. */
2317 do
2318 {
2319 values_became_useless = 0;
2320 htab_traverse (hash_table, discard_useless_locs, 0);
2321 }
2322 while (values_became_useless);
2323
2324 /* Second pass: actually remove the values. */
2325 htab_traverse (hash_table, discard_useless_values, 0);
2326
2327 if (n_useless_values != 0)
2328 abort ();
2329 }
2330
2331 /* Return nonzero if we can prove that X and Y contain the same value, taking
2332 our gathered information into account. */
2333
2334 int
2335 rtx_equal_for_cselib_p (x, y)
2336 rtx x, y;
2337 {
2338 enum rtx_code code;
2339 const char *fmt;
2340 int i;
2341
2342 if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
2343 {
2344 cselib_val *e = cselib_lookup (x, VOIDmode, 0);
2345
2346 if (e)
2347 x = e->u.val_rtx;
2348 }
2349
2350 if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
2351 {
2352 cselib_val *e = cselib_lookup (y, VOIDmode, 0);
2353
2354 if (e)
2355 y = e->u.val_rtx;
2356 }
2357
2358 if (x == y)
2359 return 1;
2360
2361 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
2362 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
2363
2364 if (GET_CODE (x) == VALUE)
2365 {
2366 cselib_val *e = CSELIB_VAL_PTR (x);
2367 struct elt_loc_list *l;
2368
2369 for (l = e->locs; l; l = l->next)
2370 {
2371 rtx t = l->loc;
2372
2373 /* Avoid infinite recursion. */
2374 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2375 continue;
2376 else if (rtx_equal_for_cselib_p (t, y))
2377 return 1;
2378 }
2379
2380 return 0;
2381 }
2382
2383 if (GET_CODE (y) == VALUE)
2384 {
2385 cselib_val *e = CSELIB_VAL_PTR (y);
2386 struct elt_loc_list *l;
2387
2388 for (l = e->locs; l; l = l->next)
2389 {
2390 rtx t = l->loc;
2391
2392 if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
2393 continue;
2394 else if (rtx_equal_for_cselib_p (x, t))
2395 return 1;
2396 }
2397
2398 return 0;
2399 }
2400
2401 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
2402 return 0;
2403
2404 /* This won't be handled correctly by the code below. */
2405 if (GET_CODE (x) == LABEL_REF)
2406 return XEXP (x, 0) == XEXP (y, 0);
2407
2408 code = GET_CODE (x);
2409 fmt = GET_RTX_FORMAT (code);
2410
2411 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2412 {
2413 int j;
2414
2415 switch (fmt[i])
2416 {
2417 case 'w':
2418 if (XWINT (x, i) != XWINT (y, i))
2419 return 0;
2420 break;
2421
2422 case 'n':
2423 case 'i':
2424 if (XINT (x, i) != XINT (y, i))
2425 return 0;
2426 break;
2427
2428 case 'V':
2429 case 'E':
2430 /* Two vectors must have the same length. */
2431 if (XVECLEN (x, i) != XVECLEN (y, i))
2432 return 0;
2433
2434 /* And the corresponding elements must match. */
2435 for (j = 0; j < XVECLEN (x, i); j++)
2436 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
2437 XVECEXP (y, i, j)))
2438 return 0;
2439 break;
2440
2441 case 'e':
2442 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
2443 return 0;
2444 break;
2445
2446 case 'S':
2447 case 's':
2448 if (strcmp (XSTR (x, i), XSTR (y, i)))
2449 return 0;
2450 break;
2451
2452 case 'u':
2453 /* These are just backpointers, so they don't matter. */
2454 break;
2455
2456 case '0':
2457 case 't':
2458 break;
2459
2460 /* It is believed that rtx's at this level will never
2461 contain anything but integers and other rtx's,
2462 except for within LABEL_REFs and SYMBOL_REFs. */
2463 default:
2464 abort ();
2465 }
2466 }
2467 return 1;
2468 }
2469
2470 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
2471 For registers and memory locations, we look up their cselib_val structure
2472 and return its VALUE element.
2473 Possible reasons for return 0 are: the object is volatile, or we couldn't
2474 find a register or memory location in the table and CREATE is zero. If
2475 CREATE is nonzero, table elts are created for regs and mem.
2476 MODE is used in hashing for CONST_INTs only;
2477 otherwise the mode of X is used. */
2478
2479 static unsigned int
2480 hash_rtx (x, mode, create)
2481 rtx x;
2482 enum machine_mode mode;
2483 int create;
2484 {
2485 cselib_val *e;
2486 int i, j;
2487 enum rtx_code code;
2488 const char *fmt;
2489 unsigned int hash = 0;
2490
2491 /* repeat is used to turn tail-recursion into iteration. */
2492 repeat:
2493 code = GET_CODE (x);
2494 hash += (unsigned) code + (unsigned) GET_MODE (x);
2495
2496 switch (code)
2497 {
2498 case MEM:
2499 case REG:
2500 e = cselib_lookup (x, GET_MODE (x), create);
2501 if (! e)
2502 return 0;
2503
2504 hash += e->value;
2505 return hash;
2506
2507 case CONST_INT:
2508 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
2509 return hash ? hash : CONST_INT;
2510
2511 case CONST_DOUBLE:
2512 /* This is like the general case, except that it only counts
2513 the integers representing the constant. */
2514 hash += (unsigned) code + (unsigned) GET_MODE (x);
2515 if (GET_MODE (x) != VOIDmode)
2516 for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
2517 hash += XWINT (x, i);
2518 else
2519 hash += ((unsigned) CONST_DOUBLE_LOW (x)
2520 + (unsigned) CONST_DOUBLE_HIGH (x));
2521 return hash ? hash : CONST_DOUBLE;
2522
2523 /* Assume there is only one rtx object for any given label. */
2524 case LABEL_REF:
2525 hash
2526 += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
2527 return hash ? hash : LABEL_REF;
2528
2529 case SYMBOL_REF:
2530 hash
2531 += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
2532 return hash ? hash : SYMBOL_REF;
2533
2534 case PRE_DEC:
2535 case PRE_INC:
2536 case POST_DEC:
2537 case POST_INC:
2538 case PC:
2539 case CC0:
2540 case CALL:
2541 case UNSPEC_VOLATILE:
2542 return 0;
2543
2544 case ASM_OPERANDS:
2545 if (MEM_VOLATILE_P (x))
2546 return 0;
2547
2548 break;
2549
2550 default:
2551 break;
2552 }
2553
2554 i = GET_RTX_LENGTH (code) - 1;
2555 fmt = GET_RTX_FORMAT (code);
2556 for (; i >= 0; i--)
2557 {
2558 if (fmt[i] == 'e')
2559 {
2560 rtx tem = XEXP (x, i);
2561 unsigned int tem_hash;
2562
2563 /* If we are about to do the last recursive call
2564 needed at this level, change it into iteration.
2565 This function is called enough to be worth it. */
2566 if (i == 0)
2567 {
2568 x = tem;
2569 goto repeat;
2570 }
2571
2572 tem_hash = hash_rtx (tem, 0, create);
2573 if (tem_hash == 0)
2574 return 0;
2575
2576 hash += tem_hash;
2577 }
2578 else if (fmt[i] == 'E')
2579 for (j = 0; j < XVECLEN (x, i); j++)
2580 {
2581 unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
2582
2583 if (tem_hash == 0)
2584 return 0;
2585
2586 hash += tem_hash;
2587 }
2588 else if (fmt[i] == 's')
2589 {
2590 const unsigned char *p = (const unsigned char *) XSTR (x, i);
2591
2592 if (p)
2593 while (*p)
2594 hash += *p++;
2595 }
2596 else if (fmt[i] == 'i')
2597 hash += XINT (x, i);
2598 else if (fmt[i] == '0' || fmt[i] == 't')
2599 /* unused */;
2600 else
2601 abort ();
2602 }
2603
2604 return hash ? hash : 1 + GET_CODE (x);
2605 }
2606
2607 /* Create a new value structure for VALUE and initialize it. The mode of the
2608 value is MODE. */
2609
2610 static cselib_val *
2611 new_cselib_val (value, mode)
2612 unsigned int value;
2613 enum machine_mode mode;
2614 {
2615 cselib_val *e = empty_vals;
2616
2617 if (e)
2618 empty_vals = e->u.next_free;
2619 else
2620 e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
2621
2622 if (value == 0)
2623 abort ();
2624
2625 e->value = value;
2626 e->u.val_rtx = gen_rtx_VALUE (mode);
2627 CSELIB_VAL_PTR (e->u.val_rtx) = e;
2628 e->addr_list = 0;
2629 e->locs = 0;
2630 return e;
2631 }
2632
2633 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
2634 contains the data at this address. X is a MEM that represents the
2635 value. Update the two value structures to represent this situation. */
2636
2637 static void
2638 add_mem_for_addr (addr_elt, mem_elt, x)
2639 cselib_val *addr_elt, *mem_elt;
2640 rtx x;
2641 {
2642 rtx new;
2643 struct elt_loc_list *l;
2644
2645 /* Avoid duplicates. */
2646 for (l = mem_elt->locs; l; l = l->next)
2647 if (GET_CODE (l->loc) == MEM
2648 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
2649 return;
2650
2651 new = gen_rtx_MEM (GET_MODE (x), addr_elt->u.val_rtx);
2652 MEM_COPY_ATTRIBUTES (new, x);
2653
2654 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
2655 mem_elt->locs = new_elt_loc_list (mem_elt->locs, new);
2656 }
2657
2658 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
2659 If CREATE, make a new one if we haven't seen it before. */
2660
2661 static cselib_val *
2662 cselib_lookup_mem (x, create)
2663 rtx x;
2664 int create;
2665 {
2666 void **slot;
2667 cselib_val *addr;
2668 cselib_val *mem_elt;
2669 struct elt_list *l;
2670
2671 if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode
2672 || (FLOAT_MODE_P (GET_MODE (x)) && flag_float_store))
2673 return 0;
2674
2675 /* Look up the value for the address. */
2676 addr = cselib_lookup (XEXP (x, 0), GET_MODE (x), create);
2677 if (! addr)
2678 return 0;
2679
2680 /* Find a value that describes a value of our mode at that address. */
2681 for (l = addr->addr_list; l; l = l->next)
2682 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2683 return l->elt;
2684
2685 if (! create)
2686 return 0;
2687
2688 mem_elt = new_cselib_val (++next_unknown_value, GET_MODE (x));
2689 add_mem_for_addr (addr, mem_elt, x);
2690 slot = htab_find_slot_with_hash (hash_table, x, mem_elt->value, INSERT);
2691 *slot = mem_elt;
2692 return mem_elt;
2693 }
2694
2695 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2696 with VALUE expressions. This way, it becomes independent of changes
2697 to registers and memory.
2698 X isn't actually modified; if modifications are needed, new rtl is
2699 allocated. However, the return value can share rtl with X. */
2700
2701 static rtx
2702 cselib_subst_to_values (x)
2703 rtx x;
2704 {
2705 enum rtx_code code = GET_CODE (x);
2706 const char *fmt = GET_RTX_FORMAT (code);
2707 cselib_val *e;
2708 struct elt_list *l;
2709 rtx copy = x;
2710 int i;
2711
2712 switch (code)
2713 {
2714 case REG:
2715 for (l = REG_VALUES (REGNO (x)); l; l = l->next)
2716 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
2717 return l->elt->u.val_rtx;
2718
2719 abort ();
2720
2721 case MEM:
2722 e = cselib_lookup_mem (x, 0);
2723 if (! e)
2724 abort ();
2725 return e->u.val_rtx;
2726
2727 /* CONST_DOUBLEs must be special-cased here so that we won't try to
2728 look up the CONST_DOUBLE_MEM inside. */
2729 case CONST_DOUBLE:
2730 case CONST_INT:
2731 return x;
2732
2733 default:
2734 break;
2735 }
2736
2737 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2738 {
2739 if (fmt[i] == 'e')
2740 {
2741 rtx t = cselib_subst_to_values (XEXP (x, i));
2742
2743 if (t != XEXP (x, i) && x == copy)
2744 copy = shallow_copy_rtx (x);
2745
2746 XEXP (copy, i) = t;
2747 }
2748 else if (fmt[i] == 'E')
2749 {
2750 int j, k;
2751
2752 for (j = 0; j < XVECLEN (x, i); j++)
2753 {
2754 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
2755
2756 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
2757 {
2758 if (x == copy)
2759 copy = shallow_copy_rtx (x);
2760
2761 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
2762 for (k = 0; k < j; k++)
2763 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
2764 }
2765
2766 XVECEXP (copy, i, j) = t;
2767 }
2768 }
2769 }
2770
2771 return copy;
2772 }
2773
2774 /* Look up the rtl expression X in our tables and return the value it has.
2775 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
2776 we create a new one if possible, using mode MODE if X doesn't have a mode
2777 (i.e. because it's a constant). */
2778
2779 cselib_val *
2780 cselib_lookup (x, mode, create)
2781 rtx x;
2782 enum machine_mode mode;
2783 int create;
2784 {
2785 void **slot;
2786 cselib_val *e;
2787 unsigned int hashval;
2788
2789 if (GET_MODE (x) != VOIDmode)
2790 mode = GET_MODE (x);
2791
2792 if (GET_CODE (x) == VALUE)
2793 return CSELIB_VAL_PTR (x);
2794
2795 if (GET_CODE (x) == REG)
2796 {
2797 struct elt_list *l;
2798 unsigned int i = REGNO (x);
2799
2800 for (l = REG_VALUES (i); l; l = l->next)
2801 if (mode == GET_MODE (l->elt->u.val_rtx))
2802 return l->elt;
2803
2804 if (! create)
2805 return 0;
2806
2807 e = new_cselib_val (++next_unknown_value, GET_MODE (x));
2808 e->locs = new_elt_loc_list (e->locs, x);
2809 REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
2810 slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
2811 *slot = e;
2812 return e;
2813 }
2814
2815 if (GET_CODE (x) == MEM)
2816 return cselib_lookup_mem (x, create);
2817
2818 hashval = hash_rtx (x, mode, create);
2819 /* Can't even create if hashing is not possible. */
2820 if (! hashval)
2821 return 0;
2822
2823 slot = htab_find_slot_with_hash (hash_table, x, hashval,
2824 create ? INSERT : NO_INSERT);
2825 if (slot == 0)
2826 return 0;
2827
2828 e = (cselib_val *) *slot;
2829 if (e)
2830 return e;
2831
2832 e = new_cselib_val (hashval, mode);
2833
2834 /* We have to fill the slot before calling cselib_subst_to_values:
2835 the hash table is inconsistent until we do so, and
2836 cselib_subst_to_values will need to do lookups. */
2837 *slot = (void *) e;
2838 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
2839 return e;
2840 }
2841
2842 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2843 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2844 is used to determine how many hard registers are being changed. If MODE
2845 is VOIDmode, then only REGNO is being changed; this is used when
2846 invalidating call clobbered registers across a call. */
2847
2848 static void
2849 cselib_invalidate_regno (regno, mode)
2850 unsigned int regno;
2851 enum machine_mode mode;
2852 {
2853 unsigned int endregno;
2854 unsigned int i;
2855
2856 /* If we see pseudos after reload, something is _wrong_. */
2857 if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
2858 && reg_renumber[regno] >= 0)
2859 abort ();
2860
2861 /* Determine the range of registers that must be invalidated. For
2862 pseudos, only REGNO is affected. For hard regs, we must take MODE
2863 into account, and we must also invalidate lower register numbers
2864 if they contain values that overlap REGNO. */
2865 endregno = regno + 1;
2866 if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode)
2867 endregno = regno + HARD_REGNO_NREGS (regno, mode);
2868
2869 for (i = 0; i < endregno; i++)
2870 {
2871 struct elt_list **l = &REG_VALUES (i);
2872
2873 /* Go through all known values for this reg; if it overlaps the range
2874 we're invalidating, remove the value. */
2875 while (*l)
2876 {
2877 cselib_val *v = (*l)->elt;
2878 struct elt_loc_list **p;
2879 unsigned int this_last = i;
2880
2881 if (i < FIRST_PSEUDO_REGISTER)
2882 this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
2883
2884 if (this_last < regno)
2885 {
2886 l = &(*l)->next;
2887 continue;
2888 }
2889
2890 /* We have an overlap. */
2891 unchain_one_elt_list (l);
2892
2893 /* Now, we clear the mapping from value to reg. It must exist, so
2894 this code will crash intentionally if it doesn't. */
2895 for (p = &v->locs; ; p = &(*p)->next)
2896 {
2897 rtx x = (*p)->loc;
2898
2899 if (GET_CODE (x) == REG && REGNO (x) == i)
2900 {
2901 unchain_one_elt_loc_list (p);
2902 break;
2903 }
2904 }
2905 if (v->locs == 0)
2906 n_useless_values++;
2907 }
2908 }
2909 }
2910
2911 /* The memory at address MEM_BASE is being changed.
2912 Return whether this change will invalidate VAL. */
2913
2914 static int
2915 cselib_mem_conflict_p (mem_base, val)
2916 rtx mem_base;
2917 rtx val;
2918 {
2919 enum rtx_code code;
2920 const char *fmt;
2921 int i, j;
2922
2923 code = GET_CODE (val);
2924 switch (code)
2925 {
2926 /* Get rid of a few simple cases quickly. */
2927 case REG:
2928 case PC:
2929 case CC0:
2930 case SCRATCH:
2931 case CONST:
2932 case CONST_INT:
2933 case CONST_DOUBLE:
2934 case SYMBOL_REF:
2935 case LABEL_REF:
2936 return 0;
2937
2938 case MEM:
2939 if (GET_MODE (mem_base) == BLKmode
2940 || GET_MODE (val) == BLKmode
2941 || anti_dependence (val, mem_base))
2942 return 1;
2943
2944 /* The address may contain nested MEMs. */
2945 break;
2946
2947 default:
2948 break;
2949 }
2950
2951 fmt = GET_RTX_FORMAT (code);
2952 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2953 {
2954 if (fmt[i] == 'e')
2955 {
2956 if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
2957 return 1;
2958 }
2959 else if (fmt[i] == 'E')
2960 for (j = 0; j < XVECLEN (val, i); j++)
2961 if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
2962 return 1;
2963 }
2964
2965 return 0;
2966 }
2967
2968 /* For the value found in SLOT, walk its locations to determine if any overlap
2969 INFO (which is a MEM rtx). */
2970
2971 static int
2972 cselib_invalidate_mem_1 (slot, info)
2973 void **slot;
2974 void *info;
2975 {
2976 cselib_val *v = (cselib_val *) *slot;
2977 rtx mem_rtx = (rtx) info;
2978 struct elt_loc_list **p = &v->locs;
2979 int had_locs = v->locs != 0;
2980
2981 while (*p)
2982 {
2983 rtx x = (*p)->loc;
2984 cselib_val *addr;
2985 struct elt_list **mem_chain;
2986
2987 /* MEMs may occur in locations only at the top level; below
2988 that every MEM or REG is substituted by its VALUE. */
2989 if (GET_CODE (x) != MEM
2990 || ! cselib_mem_conflict_p (mem_rtx, x))
2991 {
2992 p = &(*p)->next;
2993 continue;
2994 }
2995
2996 /* This one overlaps. */
2997 /* We must have a mapping from this MEM's address to the
2998 value (E). Remove that, too. */
2999 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
3000 mem_chain = &addr->addr_list;
3001 for (;;)
3002 {
3003 if ((*mem_chain)->elt == v)
3004 {
3005 unchain_one_elt_list (mem_chain);
3006 break;
3007 }
3008
3009 mem_chain = &(*mem_chain)->next;
3010 }
3011
3012 unchain_one_elt_loc_list (p);
3013 }
3014
3015 if (had_locs && v->locs == 0)
3016 n_useless_values++;
3017
3018 return 1;
3019 }
3020
3021 /* Invalidate any locations in the table which are changed because of a
3022 store to MEM_RTX. If this is called because of a non-const call
3023 instruction, MEM_RTX is (mem:BLK const0_rtx). */
3024
3025 static void
3026 cselib_invalidate_mem (mem_rtx)
3027 rtx mem_rtx;
3028 {
3029 htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
3030 }
3031
3032 /* Invalidate DEST, which is being assigned to or clobbered. The second and
3033 the third parameter exist so that this function can be passed to
3034 note_stores; they are ignored. */
3035
3036 static void
3037 cselib_invalidate_rtx (dest, ignore, data)
3038 rtx dest;
3039 rtx ignore ATTRIBUTE_UNUSED;
3040 void *data ATTRIBUTE_UNUSED;
3041 {
3042 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
3043 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
3044 dest = XEXP (dest, 0);
3045
3046 if (GET_CODE (dest) == REG)
3047 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
3048 else if (GET_CODE (dest) == MEM)
3049 cselib_invalidate_mem (dest);
3050
3051 /* Some machines don't define AUTO_INC_DEC, but they still use push
3052 instructions. We need to catch that case here in order to
3053 invalidate the stack pointer correctly. Note that invalidating
3054 the stack pointer is different from invalidating DEST. */
3055 if (push_operand (dest, GET_MODE (dest)))
3056 cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
3057 }
3058
3059 /* Record the result of a SET instruction. DEST is being set; the source
3060 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
3061 describes its address. */
3062
3063 static void
3064 cselib_record_set (dest, src_elt, dest_addr_elt)
3065 rtx dest;
3066 cselib_val *src_elt, *dest_addr_elt;
3067 {
3068 int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
3069
3070 if (src_elt == 0 || side_effects_p (dest))
3071 return;
3072
3073 if (dreg >= 0)
3074 {
3075 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
3076 if (src_elt->locs == 0)
3077 n_useless_values--;
3078 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
3079 }
3080 else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
3081 {
3082 if (src_elt->locs == 0)
3083 n_useless_values--;
3084 add_mem_for_addr (dest_addr_elt, src_elt, dest);
3085 }
3086 }
3087
3088 /* Describe a single set that is part of an insn. */
3089 struct set
3090 {
3091 rtx src;
3092 rtx dest;
3093 cselib_val *src_elt;
3094 cselib_val *dest_addr_elt;
3095 };
3096
3097 /* There is no good way to determine how many elements there can be
3098 in a PARALLEL. Since it's fairly cheap, use a really large number. */
3099 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
3100
3101 /* Record the effects of any sets in INSN. */
3102 static void
3103 cselib_record_sets (insn)
3104 rtx insn;
3105 {
3106 int n_sets = 0;
3107 int i;
3108 struct set sets[MAX_SETS];
3109 rtx body = PATTERN (insn);
3110
3111 body = PATTERN (insn);
3112 /* Find all sets. */
3113 if (GET_CODE (body) == SET)
3114 {
3115 sets[0].src = SET_SRC (body);
3116 sets[0].dest = SET_DEST (body);
3117 n_sets = 1;
3118 }
3119 else if (GET_CODE (body) == PARALLEL)
3120 {
3121 /* Look through the PARALLEL and record the values being
3122 set, if possible. Also handle any CLOBBERs. */
3123 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3124 {
3125 rtx x = XVECEXP (body, 0, i);
3126
3127 if (GET_CODE (x) == SET)
3128 {
3129 sets[n_sets].src = SET_SRC (x);
3130 sets[n_sets].dest = SET_DEST (x);
3131 n_sets++;
3132 }
3133 }
3134 }
3135
3136 /* Look up the values that are read. Do this before invalidating the
3137 locations that are written. */
3138 for (i = 0; i < n_sets; i++)
3139 {
3140 sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (sets[i].dest),
3141 1);
3142 if (GET_CODE (sets[i].dest) == MEM)
3143 sets[i].dest_addr_elt = cselib_lookup (XEXP (sets[i].dest, 0), Pmode,
3144 1);
3145 else
3146 sets[i].dest_addr_elt = 0;
3147 }
3148
3149 /* Invalidate all locations written by this insn. Note that the elts we
3150 looked up in the previous loop aren't affected, just some of their
3151 locations may go away. */
3152 note_stores (body, cselib_invalidate_rtx, NULL);
3153
3154 /* Now enter the equivalences in our tables. */
3155 for (i = 0; i < n_sets; i++)
3156 cselib_record_set (sets[i].dest, sets[i].src_elt, sets[i].dest_addr_elt);
3157 }
3158
3159 /* Record the effects of INSN. */
3160
3161 void
3162 cselib_process_insn (insn)
3163 rtx insn;
3164 {
3165 int i;
3166 rtx x;
3167
3168 cselib_current_insn = insn;
3169
3170 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
3171 if (GET_CODE (insn) == CODE_LABEL
3172 || (GET_CODE (insn) == NOTE
3173 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3174 || (GET_CODE (insn) == INSN
3175 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
3176 && MEM_VOLATILE_P (PATTERN (insn))))
3177 {
3178 clear_table ();
3179 return;
3180 }
3181
3182 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3183 {
3184 cselib_current_insn = 0;
3185 return;
3186 }
3187
3188 /* If this is a call instruction, forget anything stored in a
3189 call clobbered register, or, if this is not a const call, in
3190 memory. */
3191 if (GET_CODE (insn) == CALL_INSN)
3192 {
3193 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3194 if (call_used_regs[i])
3195 cselib_invalidate_regno (i, VOIDmode);
3196
3197 if (! CONST_CALL_P (insn))
3198 cselib_invalidate_mem (callmem);
3199 }
3200
3201 cselib_record_sets (insn);
3202
3203 #ifdef AUTO_INC_DEC
3204 /* Clobber any registers which appear in REG_INC notes. We
3205 could keep track of the changes to their values, but it is
3206 unlikely to help. */
3207 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
3208 if (REG_NOTE_KIND (x) == REG_INC)
3209 cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
3210 #endif
3211
3212 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3213 after we have processed the insn. */
3214 if (GET_CODE (insn) == CALL_INSN)
3215 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3216 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3217 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
3218
3219 cselib_current_insn = 0;
3220
3221 if (n_useless_values > MAX_USELESS_VALUES)
3222 remove_useless_values ();
3223 }
3224
3225 /* Make sure our varrays are big enough. Not called from any cselib routines;
3226 it must be called by the user if it allocated new registers. */
3227
3228 void
3229 cselib_update_varray_sizes ()
3230 {
3231 unsigned int nregs = max_reg_num ();
3232
3233 if (nregs == cselib_nregs)
3234 return;
3235
3236 cselib_nregs = nregs;
3237 VARRAY_GROW (reg_values, nregs);
3238 }
3239
3240 /* Initialize cselib for one pass. The caller must also call
3241 init_alias_analysis. */
3242
3243 void
3244 cselib_init ()
3245 {
3246 /* These are only created once. */
3247 if (! callmem)
3248 {
3249 extern struct obstack permanent_obstack;
3250
3251 gcc_obstack_init (&cselib_obstack);
3252 cselib_startobj = obstack_alloc (&cselib_obstack, 0);
3253
3254 push_obstacks (&permanent_obstack, &permanent_obstack);
3255 callmem = gen_rtx_MEM (BLKmode, const0_rtx);
3256 pop_obstacks ();
3257 ggc_add_rtx_root (&callmem, 1);
3258 }
3259
3260 cselib_nregs = max_reg_num ();
3261 VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
3262 hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
3263 clear_table ();
3264 }
3265
3266 /* Called when the current user is done with cselib. */
3267
3268 void
3269 cselib_finish ()
3270 {
3271 clear_table ();
3272 htab_delete (hash_table);
3273 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org