1 /* Fold a constant sub-tree into a single node for C-compiler
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /*@@ This file should be rewritten to use an arbitrary precision
23 @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
24 @@ Perhaps the routines could also be used for bc/dc, and made a lib.
25 @@ The routines that translate from the ap rep should
26 @@ warn if precision et. al. is lost.
27 @@ This would also make life easier when this technology is used
28 @@ for cross-compilers. */
30 /* The entry points in this file are fold, size_int_wide, size_binop
33 fold takes a tree as argument and returns a simplified tree.
35 size_binop takes a tree code for an arithmetic operation
36 and two operands that are trees, and produces a tree for the
37 result, assuming the type comes from `sizetype'.
39 size_int takes an integer value, and creates a tree constant
40 with type from `sizetype'.
42 force_fit_type takes a constant and prior overflow indicator, and
43 forces the value to fit the type. It returns an overflow indicator. */
55 #include "langhooks.h"
57 static void encode PARAMS ((HOST_WIDE_INT *,
58 unsigned HOST_WIDE_INT,
60 static void decode PARAMS ((HOST_WIDE_INT *,
61 unsigned HOST_WIDE_INT *,
63 static tree negate_expr PARAMS ((tree));
64 static tree split_tree PARAMS ((tree, enum tree_code, tree *, tree *,
66 static tree associate_trees PARAMS ((tree, tree, enum tree_code, tree));
67 static tree int_const_binop PARAMS ((enum tree_code, tree, tree, int));
68 static tree const_binop PARAMS ((enum tree_code, tree, tree, int));
69 static hashval_t size_htab_hash PARAMS ((const void *));
70 static int size_htab_eq PARAMS ((const void *, const void *));
71 static tree fold_convert PARAMS ((tree, tree));
72 static enum tree_code invert_tree_comparison PARAMS ((enum tree_code));
73 static enum tree_code swap_tree_comparison PARAMS ((enum tree_code));
74 static int truth_value_p PARAMS ((enum tree_code));
75 static int operand_equal_for_comparison_p PARAMS ((tree, tree, tree));
76 static int twoval_comparison_p PARAMS ((tree, tree *, tree *, int *));
77 static tree eval_subst PARAMS ((tree, tree, tree, tree, tree));
78 static tree omit_one_operand PARAMS ((tree, tree, tree));
79 static tree pedantic_omit_one_operand PARAMS ((tree, tree, tree));
80 static tree distribute_bit_expr PARAMS ((enum tree_code, tree, tree, tree));
81 static tree make_bit_field_ref PARAMS ((tree, tree, int, int, int));
82 static tree optimize_bit_field_compare PARAMS ((enum tree_code, tree,
84 static tree decode_field_reference PARAMS ((tree, HOST_WIDE_INT *,
86 enum machine_mode *, int *,
87 int *, tree *, tree *));
88 static int all_ones_mask_p PARAMS ((tree, int));
89 static tree sign_bit_p PARAMS ((tree, tree));
90 static int simple_operand_p PARAMS ((tree));
91 static tree range_binop PARAMS ((enum tree_code, tree, tree, int,
93 static tree make_range PARAMS ((tree, int *, tree *, tree *));
94 static tree build_range_check PARAMS ((tree, tree, int, tree, tree));
95 static int merge_ranges PARAMS ((int *, tree *, tree *, int, tree, tree,
97 static tree fold_range_test PARAMS ((tree));
98 static tree unextend PARAMS ((tree, int, int, tree));
99 static tree fold_truthop PARAMS ((enum tree_code, tree, tree, tree));
100 static tree optimize_minmax_comparison PARAMS ((tree));
101 static tree extract_muldiv PARAMS ((tree, tree, enum tree_code, tree));
102 static tree strip_compound_expr PARAMS ((tree, tree));
103 static int multiple_of_p PARAMS ((tree, tree, tree));
104 static tree constant_boolean_node PARAMS ((int, tree));
105 static int count_cond PARAMS ((tree, int));
106 static tree fold_binary_op_with_conditional_arg
107 PARAMS ((enum tree_code, tree, tree, tree, int));
108 static bool fold_real_zero_addition_p PARAMS ((tree, tree, int));
110 #if defined(HOST_EBCDIC)
111 /* bit 8 is significant in EBCDIC */
112 #define CHARMASK 0xff
114 #define CHARMASK 0x7f
117 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
118 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
119 and SUM1. Then this yields nonzero if overflow occurred during the
122 Overflow occurs if A and B have the same sign, but A and SUM differ in
123 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
125 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
127 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
128 We do that by representing the two-word integer in 4 words, with only
129 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
130 number. The value of the word is LOWPART + HIGHPART * BASE. */
133 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
134 #define HIGHPART(x) \
135 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
136 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
138 /* Unpack a two-word integer into 4 words.
139 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
140 WORDS points to the array of HOST_WIDE_INTs. */
143 encode (words, low, hi)
144 HOST_WIDE_INT *words;
145 unsigned HOST_WIDE_INT low;
148 words[0] = LOWPART (low);
149 words[1] = HIGHPART (low);
150 words[2] = LOWPART (hi);
151 words[3] = HIGHPART (hi);
154 /* Pack an array of 4 words into a two-word integer.
155 WORDS points to the array of words.
156 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
159 decode (words, low, hi)
160 HOST_WIDE_INT *words;
161 unsigned HOST_WIDE_INT *low;
164 *low = words[0] + words[1] * BASE;
165 *hi = words[2] + words[3] * BASE;
168 /* Make the integer constant T valid for its type by setting to 0 or 1 all
169 the bits in the constant that don't belong in the type.
171 Return 1 if a signed overflow occurs, 0 otherwise. If OVERFLOW is
172 nonzero, a signed overflow has already occurred in calculating T, so
175 Make the real constant T valid for its type by calling CHECK_FLOAT_VALUE,
179 force_fit_type (t, overflow)
183 unsigned HOST_WIDE_INT low;
187 if (TREE_CODE (t) == REAL_CST)
189 #ifdef CHECK_FLOAT_VALUE
190 CHECK_FLOAT_VALUE (TYPE_MODE (TREE_TYPE (t)), TREE_REAL_CST (t),
196 else if (TREE_CODE (t) != INTEGER_CST)
199 low = TREE_INT_CST_LOW (t);
200 high = TREE_INT_CST_HIGH (t);
202 if (POINTER_TYPE_P (TREE_TYPE (t)))
205 prec = TYPE_PRECISION (TREE_TYPE (t));
207 /* First clear all bits that are beyond the type's precision. */
209 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
211 else if (prec > HOST_BITS_PER_WIDE_INT)
212 TREE_INT_CST_HIGH (t)
213 &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
216 TREE_INT_CST_HIGH (t) = 0;
217 if (prec < HOST_BITS_PER_WIDE_INT)
218 TREE_INT_CST_LOW (t) &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
221 /* Unsigned types do not suffer sign extension or overflow unless they
223 if (TREE_UNSIGNED (TREE_TYPE (t))
224 && ! (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
225 && TYPE_IS_SIZETYPE (TREE_TYPE (t))))
228 /* If the value's sign bit is set, extend the sign. */
229 if (prec != 2 * HOST_BITS_PER_WIDE_INT
230 && (prec > HOST_BITS_PER_WIDE_INT
231 ? 0 != (TREE_INT_CST_HIGH (t)
233 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
234 : 0 != (TREE_INT_CST_LOW (t)
235 & ((unsigned HOST_WIDE_INT) 1 << (prec - 1)))))
237 /* Value is negative:
238 set to 1 all the bits that are outside this type's precision. */
239 if (prec > HOST_BITS_PER_WIDE_INT)
240 TREE_INT_CST_HIGH (t)
241 |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
244 TREE_INT_CST_HIGH (t) = -1;
245 if (prec < HOST_BITS_PER_WIDE_INT)
246 TREE_INT_CST_LOW (t) |= ((unsigned HOST_WIDE_INT) (-1) << prec);
250 /* Return nonzero if signed overflow occurred. */
252 ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
256 /* Add two doubleword integers with doubleword result.
257 Each argument is given as two `HOST_WIDE_INT' pieces.
258 One argument is L1 and H1; the other, L2 and H2.
259 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
262 add_double (l1, h1, l2, h2, lv, hv)
263 unsigned HOST_WIDE_INT l1, l2;
264 HOST_WIDE_INT h1, h2;
265 unsigned HOST_WIDE_INT *lv;
268 unsigned HOST_WIDE_INT l;
272 h = h1 + h2 + (l < l1);
276 return OVERFLOW_SUM_SIGN (h1, h2, h);
279 /* Negate a doubleword integer with doubleword result.
280 Return nonzero if the operation overflows, assuming it's signed.
281 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
282 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
285 neg_double (l1, h1, lv, hv)
286 unsigned HOST_WIDE_INT l1;
288 unsigned HOST_WIDE_INT *lv;
295 return (*hv & h1) < 0;
305 /* Multiply two doubleword integers with doubleword result.
306 Return nonzero if the operation overflows, assuming it's signed.
307 Each argument is given as two `HOST_WIDE_INT' pieces.
308 One argument is L1 and H1; the other, L2 and H2.
309 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
312 mul_double (l1, h1, l2, h2, lv, hv)
313 unsigned HOST_WIDE_INT l1, l2;
314 HOST_WIDE_INT h1, h2;
315 unsigned HOST_WIDE_INT *lv;
318 HOST_WIDE_INT arg1[4];
319 HOST_WIDE_INT arg2[4];
320 HOST_WIDE_INT prod[4 * 2];
321 unsigned HOST_WIDE_INT carry;
323 unsigned HOST_WIDE_INT toplow, neglow;
324 HOST_WIDE_INT tophigh, neghigh;
326 encode (arg1, l1, h1);
327 encode (arg2, l2, h2);
329 memset ((char *) prod, 0, sizeof prod);
331 for (i = 0; i < 4; i++)
334 for (j = 0; j < 4; j++)
337 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
338 carry += arg1[i] * arg2[j];
339 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
341 prod[k] = LOWPART (carry);
342 carry = HIGHPART (carry);
347 decode (prod, lv, hv); /* This ignores prod[4] through prod[4*2-1] */
349 /* Check for overflow by calculating the top half of the answer in full;
350 it should agree with the low half's sign bit. */
351 decode (prod + 4, &toplow, &tophigh);
354 neg_double (l2, h2, &neglow, &neghigh);
355 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
359 neg_double (l1, h1, &neglow, &neghigh);
360 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
362 return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
365 /* Shift the doubleword integer in L1, H1 left by COUNT places
366 keeping only PREC bits of result.
367 Shift right if COUNT is negative.
368 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
369 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
372 lshift_double (l1, h1, count, prec, lv, hv, arith)
373 unsigned HOST_WIDE_INT l1;
374 HOST_WIDE_INT h1, count;
376 unsigned HOST_WIDE_INT *lv;
380 unsigned HOST_WIDE_INT signmask;
384 rshift_double (l1, h1, -count, prec, lv, hv, arith);
388 #ifdef SHIFT_COUNT_TRUNCATED
389 if (SHIFT_COUNT_TRUNCATED)
393 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
395 /* Shifting by the host word size is undefined according to the
396 ANSI standard, so we must handle this as a special case. */
400 else if (count >= HOST_BITS_PER_WIDE_INT)
402 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
407 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
408 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
412 /* Sign extend all bits that are beyond the precision. */
414 signmask = -((prec > HOST_BITS_PER_WIDE_INT
415 ? ((unsigned HOST_WIDE_INT) *hv
416 >> (prec - HOST_BITS_PER_WIDE_INT - 1))
417 : (*lv >> (prec - 1))) & 1);
419 if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
421 else if (prec >= HOST_BITS_PER_WIDE_INT)
423 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
424 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
429 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
430 *lv |= signmask << prec;
434 /* Shift the doubleword integer in L1, H1 right by COUNT places
435 keeping only PREC bits of result. COUNT must be positive.
436 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
437 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
440 rshift_double (l1, h1, count, prec, lv, hv, arith)
441 unsigned HOST_WIDE_INT l1;
442 HOST_WIDE_INT h1, count;
444 unsigned HOST_WIDE_INT *lv;
448 unsigned HOST_WIDE_INT signmask;
451 ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
454 #ifdef SHIFT_COUNT_TRUNCATED
455 if (SHIFT_COUNT_TRUNCATED)
459 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
461 /* Shifting by the host word size is undefined according to the
462 ANSI standard, so we must handle this as a special case. */
466 else if (count >= HOST_BITS_PER_WIDE_INT)
469 *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
473 *hv = (unsigned HOST_WIDE_INT) h1 >> count;
475 | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
478 /* Zero / sign extend all bits that are beyond the precision. */
480 if (count >= (HOST_WIDE_INT)prec)
485 else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
487 else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
489 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
490 *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
495 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
496 *lv |= signmask << (prec - count);
500 /* Rotate the doubleword integer in L1, H1 left by COUNT places
501 keeping only PREC bits of result.
502 Rotate right if COUNT is negative.
503 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
506 lrotate_double (l1, h1, count, prec, lv, hv)
507 unsigned HOST_WIDE_INT l1;
508 HOST_WIDE_INT h1, count;
510 unsigned HOST_WIDE_INT *lv;
513 unsigned HOST_WIDE_INT s1l, s2l;
514 HOST_WIDE_INT s1h, s2h;
520 lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
521 rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
526 /* Rotate the doubleword integer in L1, H1 left by COUNT places
527 keeping only PREC bits of result. COUNT must be positive.
528 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
531 rrotate_double (l1, h1, count, prec, lv, hv)
532 unsigned HOST_WIDE_INT l1;
533 HOST_WIDE_INT h1, count;
535 unsigned HOST_WIDE_INT *lv;
538 unsigned HOST_WIDE_INT s1l, s2l;
539 HOST_WIDE_INT s1h, s2h;
545 rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
546 lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
551 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
552 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
553 CODE is a tree code for a kind of division, one of
554 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
556 It controls how the quotient is rounded to an integer.
557 Return nonzero if the operation overflows.
558 UNS nonzero says do unsigned division. */
561 div_and_round_double (code, uns,
562 lnum_orig, hnum_orig, lden_orig, hden_orig,
563 lquo, hquo, lrem, hrem)
566 unsigned HOST_WIDE_INT lnum_orig; /* num == numerator == dividend */
567 HOST_WIDE_INT hnum_orig;
568 unsigned HOST_WIDE_INT lden_orig; /* den == denominator == divisor */
569 HOST_WIDE_INT hden_orig;
570 unsigned HOST_WIDE_INT *lquo, *lrem;
571 HOST_WIDE_INT *hquo, *hrem;
574 HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
575 HOST_WIDE_INT den[4], quo[4];
577 unsigned HOST_WIDE_INT work;
578 unsigned HOST_WIDE_INT carry = 0;
579 unsigned HOST_WIDE_INT lnum = lnum_orig;
580 HOST_WIDE_INT hnum = hnum_orig;
581 unsigned HOST_WIDE_INT lden = lden_orig;
582 HOST_WIDE_INT hden = hden_orig;
585 if (hden == 0 && lden == 0)
586 overflow = 1, lden = 1;
588 /* calculate quotient sign and convert operands to unsigned. */
594 /* (minimum integer) / (-1) is the only overflow case. */
595 if (neg_double (lnum, hnum, &lnum, &hnum)
596 && ((HOST_WIDE_INT) lden & hden) == -1)
602 neg_double (lden, hden, &lden, &hden);
606 if (hnum == 0 && hden == 0)
607 { /* single precision */
609 /* This unsigned division rounds toward zero. */
615 { /* trivial case: dividend < divisor */
616 /* hden != 0 already checked. */
623 memset ((char *) quo, 0, sizeof quo);
625 memset ((char *) num, 0, sizeof num); /* to zero 9th element */
626 memset ((char *) den, 0, sizeof den);
628 encode (num, lnum, hnum);
629 encode (den, lden, hden);
631 /* Special code for when the divisor < BASE. */
632 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
634 /* hnum != 0 already checked. */
635 for (i = 4 - 1; i >= 0; i--)
637 work = num[i] + carry * BASE;
638 quo[i] = work / lden;
644 /* Full double precision division,
645 with thanks to Don Knuth's "Seminumerical Algorithms". */
646 int num_hi_sig, den_hi_sig;
647 unsigned HOST_WIDE_INT quo_est, scale;
649 /* Find the highest non-zero divisor digit. */
650 for (i = 4 - 1;; i--)
657 /* Insure that the first digit of the divisor is at least BASE/2.
658 This is required by the quotient digit estimation algorithm. */
660 scale = BASE / (den[den_hi_sig] + 1);
662 { /* scale divisor and dividend */
664 for (i = 0; i <= 4 - 1; i++)
666 work = (num[i] * scale) + carry;
667 num[i] = LOWPART (work);
668 carry = HIGHPART (work);
673 for (i = 0; i <= 4 - 1; i++)
675 work = (den[i] * scale) + carry;
676 den[i] = LOWPART (work);
677 carry = HIGHPART (work);
678 if (den[i] != 0) den_hi_sig = i;
685 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
687 /* Guess the next quotient digit, quo_est, by dividing the first
688 two remaining dividend digits by the high order quotient digit.
689 quo_est is never low and is at most 2 high. */
690 unsigned HOST_WIDE_INT tmp;
692 num_hi_sig = i + den_hi_sig + 1;
693 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
694 if (num[num_hi_sig] != den[den_hi_sig])
695 quo_est = work / den[den_hi_sig];
699 /* Refine quo_est so it's usually correct, and at most one high. */
700 tmp = work - quo_est * den[den_hi_sig];
702 && (den[den_hi_sig - 1] * quo_est
703 > (tmp * BASE + num[num_hi_sig - 2])))
706 /* Try QUO_EST as the quotient digit, by multiplying the
707 divisor by QUO_EST and subtracting from the remaining dividend.
708 Keep in mind that QUO_EST is the I - 1st digit. */
711 for (j = 0; j <= den_hi_sig; j++)
713 work = quo_est * den[j] + carry;
714 carry = HIGHPART (work);
715 work = num[i + j] - LOWPART (work);
716 num[i + j] = LOWPART (work);
717 carry += HIGHPART (work) != 0;
720 /* If quo_est was high by one, then num[i] went negative and
721 we need to correct things. */
722 if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
725 carry = 0; /* add divisor back in */
726 for (j = 0; j <= den_hi_sig; j++)
728 work = num[i + j] + den[j] + carry;
729 carry = HIGHPART (work);
730 num[i + j] = LOWPART (work);
733 num [num_hi_sig] += carry;
736 /* Store the quotient digit. */
741 decode (quo, lquo, hquo);
744 /* if result is negative, make it so. */
746 neg_double (*lquo, *hquo, lquo, hquo);
748 /* compute trial remainder: rem = num - (quo * den) */
749 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
750 neg_double (*lrem, *hrem, lrem, hrem);
751 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
756 case TRUNC_MOD_EXPR: /* round toward zero */
757 case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
761 case FLOOR_MOD_EXPR: /* round toward negative infinity */
762 if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
765 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
773 case CEIL_MOD_EXPR: /* round toward positive infinity */
774 if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
776 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
784 case ROUND_MOD_EXPR: /* round to closest integer */
786 unsigned HOST_WIDE_INT labs_rem = *lrem;
787 HOST_WIDE_INT habs_rem = *hrem;
788 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
789 HOST_WIDE_INT habs_den = hden, htwice;
791 /* Get absolute values */
793 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
795 neg_double (lden, hden, &labs_den, &habs_den);
797 /* If (2 * abs (lrem) >= abs (lden)) */
798 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
799 labs_rem, habs_rem, <wice, &htwice);
801 if (((unsigned HOST_WIDE_INT) habs_den
802 < (unsigned HOST_WIDE_INT) htwice)
803 || (((unsigned HOST_WIDE_INT) habs_den
804 == (unsigned HOST_WIDE_INT) htwice)
805 && (labs_den < ltwice)))
809 add_double (*lquo, *hquo,
810 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
813 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
825 /* compute true remainder: rem = num - (quo * den) */
826 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
827 neg_double (*lrem, *hrem, lrem, hrem);
828 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
832 /* Given T, an expression, return the negation of T. Allow for T to be
833 null, in which case return null. */
845 type = TREE_TYPE (t);
848 switch (TREE_CODE (t))
852 if (! TREE_UNSIGNED (type)
853 && 0 != (tem = fold (build1 (NEGATE_EXPR, type, t)))
854 && ! TREE_OVERFLOW (tem))
859 return convert (type, TREE_OPERAND (t, 0));
862 /* - (A - B) -> B - A */
863 if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
864 return convert (type,
865 fold (build (MINUS_EXPR, TREE_TYPE (t),
867 TREE_OPERAND (t, 0))));
874 return convert (type, fold (build1 (NEGATE_EXPR, TREE_TYPE (t), t)));
877 /* Split a tree IN into a constant, literal and variable parts that could be
878 combined with CODE to make IN. "constant" means an expression with
879 TREE_CONSTANT but that isn't an actual constant. CODE must be a
880 commutative arithmetic operation. Store the constant part into *CONP,
881 the literal in *LITP and return the variable part. If a part isn't
882 present, set it to null. If the tree does not decompose in this way,
883 return the entire tree as the variable part and the other parts as null.
885 If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR. In that
886 case, we negate an operand that was subtracted. Except if it is a
887 literal for which we use *MINUS_LITP instead.
889 If NEGATE_P is true, we are negating all of IN, again except a literal
890 for which we use *MINUS_LITP instead.
892 If IN is itself a literal or constant, return it as appropriate.
894 Note that we do not guarantee that any of the three values will be the
895 same type as IN, but they will have the same signedness and mode. */
898 split_tree (in, code, conp, litp, minus_litp, negate_p)
901 tree *conp, *litp, *minus_litp;
910 /* Strip any conversions that don't change the machine mode or signedness. */
911 STRIP_SIGN_NOPS (in);
913 if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
915 else if (TREE_CODE (in) == code
916 || (! FLOAT_TYPE_P (TREE_TYPE (in))
917 /* We can associate addition and subtraction together (even
918 though the C standard doesn't say so) for integers because
919 the value is not affected. For reals, the value might be
920 affected, so we can't. */
921 && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
922 || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
924 tree op0 = TREE_OPERAND (in, 0);
925 tree op1 = TREE_OPERAND (in, 1);
926 int neg1_p = TREE_CODE (in) == MINUS_EXPR;
927 int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
929 /* First see if either of the operands is a literal, then a constant. */
930 if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
931 *litp = op0, op0 = 0;
932 else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
933 *litp = op1, neg_litp_p = neg1_p, op1 = 0;
935 if (op0 != 0 && TREE_CONSTANT (op0))
936 *conp = op0, op0 = 0;
937 else if (op1 != 0 && TREE_CONSTANT (op1))
938 *conp = op1, neg_conp_p = neg1_p, op1 = 0;
940 /* If we haven't dealt with either operand, this is not a case we can
941 decompose. Otherwise, VAR is either of the ones remaining, if any. */
942 if (op0 != 0 && op1 != 0)
947 var = op1, neg_var_p = neg1_p;
949 /* Now do any needed negations. */
951 *minus_litp = *litp, *litp = 0;
953 *conp = negate_expr (*conp);
955 var = negate_expr (var);
957 else if (TREE_CONSTANT (in))
965 *minus_litp = *litp, *litp = 0;
966 else if (*minus_litp)
967 *litp = *minus_litp, *minus_litp = 0;
968 *conp = negate_expr (*conp);
969 var = negate_expr (var);
975 /* Re-associate trees split by the above function. T1 and T2 are either
976 expressions to associate or null. Return the new expression, if any. If
977 we build an operation, do it in TYPE and with CODE. */
980 associate_trees (t1, t2, code, type)
990 /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
991 try to fold this since we will have infinite recursion. But do
992 deal with any NEGATE_EXPRs. */
993 if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
994 || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
996 if (TREE_CODE (t1) == NEGATE_EXPR)
997 return build (MINUS_EXPR, type, convert (type, t2),
998 convert (type, TREE_OPERAND (t1, 0)));
999 else if (TREE_CODE (t2) == NEGATE_EXPR)
1000 return build (MINUS_EXPR, type, convert (type, t1),
1001 convert (type, TREE_OPERAND (t2, 0)));
1003 return build (code, type, convert (type, t1), convert (type, t2));
1006 return fold (build (code, type, convert (type, t1), convert (type, t2)));
1009 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1010 to produce a new constant.
1012 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1015 int_const_binop (code, arg1, arg2, notrunc)
1016 enum tree_code code;
1020 unsigned HOST_WIDE_INT int1l, int2l;
1021 HOST_WIDE_INT int1h, int2h;
1022 unsigned HOST_WIDE_INT low;
1024 unsigned HOST_WIDE_INT garbagel;
1025 HOST_WIDE_INT garbageh;
1027 tree type = TREE_TYPE (arg1);
1028 int uns = TREE_UNSIGNED (type);
1030 = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1032 int no_overflow = 0;
1034 int1l = TREE_INT_CST_LOW (arg1);
1035 int1h = TREE_INT_CST_HIGH (arg1);
1036 int2l = TREE_INT_CST_LOW (arg2);
1037 int2h = TREE_INT_CST_HIGH (arg2);
1042 low = int1l | int2l, hi = int1h | int2h;
1046 low = int1l ^ int2l, hi = int1h ^ int2h;
1050 low = int1l & int2l, hi = int1h & int2h;
1053 case BIT_ANDTC_EXPR:
1054 low = int1l & ~int2l, hi = int1h & ~int2h;
1060 /* It's unclear from the C standard whether shifts can overflow.
1061 The following code ignores overflow; perhaps a C standard
1062 interpretation ruling is needed. */
1063 lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1071 lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1076 overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1080 neg_double (int2l, int2h, &low, &hi);
1081 add_double (int1l, int1h, low, hi, &low, &hi);
1082 overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1086 overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1089 case TRUNC_DIV_EXPR:
1090 case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1091 case EXACT_DIV_EXPR:
1092 /* This is a shortcut for a common special case. */
1093 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1094 && ! TREE_CONSTANT_OVERFLOW (arg1)
1095 && ! TREE_CONSTANT_OVERFLOW (arg2)
1096 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1098 if (code == CEIL_DIV_EXPR)
1101 low = int1l / int2l, hi = 0;
1105 /* ... fall through ... */
1107 case ROUND_DIV_EXPR:
1108 if (int2h == 0 && int2l == 1)
1110 low = int1l, hi = int1h;
1113 if (int1l == int2l && int1h == int2h
1114 && ! (int1l == 0 && int1h == 0))
1119 overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1120 &low, &hi, &garbagel, &garbageh);
1123 case TRUNC_MOD_EXPR:
1124 case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1125 /* This is a shortcut for a common special case. */
1126 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1127 && ! TREE_CONSTANT_OVERFLOW (arg1)
1128 && ! TREE_CONSTANT_OVERFLOW (arg2)
1129 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1131 if (code == CEIL_MOD_EXPR)
1133 low = int1l % int2l, hi = 0;
1137 /* ... fall through ... */
1139 case ROUND_MOD_EXPR:
1140 overflow = div_and_round_double (code, uns,
1141 int1l, int1h, int2l, int2h,
1142 &garbagel, &garbageh, &low, &hi);
1148 low = (((unsigned HOST_WIDE_INT) int1h
1149 < (unsigned HOST_WIDE_INT) int2h)
1150 || (((unsigned HOST_WIDE_INT) int1h
1151 == (unsigned HOST_WIDE_INT) int2h)
1154 low = (int1h < int2h
1155 || (int1h == int2h && int1l < int2l));
1157 if (low == (code == MIN_EXPR))
1158 low = int1l, hi = int1h;
1160 low = int2l, hi = int2h;
1167 /* If this is for a sizetype, can be represented as one (signed)
1168 HOST_WIDE_INT word, and doesn't overflow, use size_int since it caches
1171 && ((hi == 0 && (HOST_WIDE_INT) low >= 0)
1172 || (hi == -1 && (HOST_WIDE_INT) low < 0))
1173 && overflow == 0 && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1174 return size_int_type_wide (low, type);
1177 t = build_int_2 (low, hi);
1178 TREE_TYPE (t) = TREE_TYPE (arg1);
1183 ? (!uns || is_sizetype) && overflow
1184 : (force_fit_type (t, (!uns || is_sizetype) && overflow)
1186 | TREE_OVERFLOW (arg1)
1187 | TREE_OVERFLOW (arg2));
1189 /* If we're doing a size calculation, unsigned arithmetic does overflow.
1190 So check if force_fit_type truncated the value. */
1192 && ! TREE_OVERFLOW (t)
1193 && (TREE_INT_CST_HIGH (t) != hi
1194 || TREE_INT_CST_LOW (t) != low))
1195 TREE_OVERFLOW (t) = 1;
1197 TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1198 | TREE_CONSTANT_OVERFLOW (arg1)
1199 | TREE_CONSTANT_OVERFLOW (arg2));
1203 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1204 constant. We assume ARG1 and ARG2 have the same data type, or at least
1205 are the same kind of constant and the same machine mode.
1207 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1210 const_binop (code, arg1, arg2, notrunc)
1211 enum tree_code code;
1218 if (TREE_CODE (arg1) == INTEGER_CST)
1219 return int_const_binop (code, arg1, arg2, notrunc);
1221 if (TREE_CODE (arg1) == REAL_CST)
1225 REAL_VALUE_TYPE value;
1228 d1 = TREE_REAL_CST (arg1);
1229 d2 = TREE_REAL_CST (arg2);
1231 /* If either operand is a NaN, just return it. Otherwise, set up
1232 for floating-point trap; we return an overflow. */
1233 if (REAL_VALUE_ISNAN (d1))
1235 else if (REAL_VALUE_ISNAN (d2))
1238 REAL_ARITHMETIC (value, code, d1, d2);
1240 t = build_real (TREE_TYPE (arg1),
1241 real_value_truncate (TYPE_MODE (TREE_TYPE (arg1)),
1245 = (force_fit_type (t, 0)
1246 | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1247 TREE_CONSTANT_OVERFLOW (t)
1249 | TREE_CONSTANT_OVERFLOW (arg1)
1250 | TREE_CONSTANT_OVERFLOW (arg2);
1253 if (TREE_CODE (arg1) == COMPLEX_CST)
1255 tree type = TREE_TYPE (arg1);
1256 tree r1 = TREE_REALPART (arg1);
1257 tree i1 = TREE_IMAGPART (arg1);
1258 tree r2 = TREE_REALPART (arg2);
1259 tree i2 = TREE_IMAGPART (arg2);
1265 t = build_complex (type,
1266 const_binop (PLUS_EXPR, r1, r2, notrunc),
1267 const_binop (PLUS_EXPR, i1, i2, notrunc));
1271 t = build_complex (type,
1272 const_binop (MINUS_EXPR, r1, r2, notrunc),
1273 const_binop (MINUS_EXPR, i1, i2, notrunc));
1277 t = build_complex (type,
1278 const_binop (MINUS_EXPR,
1279 const_binop (MULT_EXPR,
1281 const_binop (MULT_EXPR,
1284 const_binop (PLUS_EXPR,
1285 const_binop (MULT_EXPR,
1287 const_binop (MULT_EXPR,
1295 = const_binop (PLUS_EXPR,
1296 const_binop (MULT_EXPR, r2, r2, notrunc),
1297 const_binop (MULT_EXPR, i2, i2, notrunc),
1300 t = build_complex (type,
1302 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1303 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1304 const_binop (PLUS_EXPR,
1305 const_binop (MULT_EXPR, r1, r2,
1307 const_binop (MULT_EXPR, i1, i2,
1310 magsquared, notrunc),
1312 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1313 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1314 const_binop (MINUS_EXPR,
1315 const_binop (MULT_EXPR, i1, r2,
1317 const_binop (MULT_EXPR, r1, i2,
1320 magsquared, notrunc));
1332 /* These are the hash table functions for the hash table of INTEGER_CST
1333 nodes of a sizetype. */
1335 /* Return the hash code code X, an INTEGER_CST. */
1343 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
1344 ^ (hashval_t) ((long) TREE_TYPE (t) >> 3)
1345 ^ (TREE_OVERFLOW (t) << 20));
1348 /* Return non-zero if the value represented by *X (an INTEGER_CST tree node)
1349 is the same as that given by *Y, which is the same. */
1359 return (TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
1360 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt)
1361 && TREE_TYPE (xt) == TREE_TYPE (yt)
1362 && TREE_OVERFLOW (xt) == TREE_OVERFLOW (yt));
1365 /* Return an INTEGER_CST with value whose low-order HOST_BITS_PER_WIDE_INT
1366 bits are given by NUMBER and of the sizetype represented by KIND. */
1369 size_int_wide (number, kind)
1370 HOST_WIDE_INT number;
1371 enum size_type_kind kind;
1373 return size_int_type_wide (number, sizetype_tab[(int) kind]);
1376 /* Likewise, but the desired type is specified explicitly. */
1379 size_int_type_wide (number, type)
1380 HOST_WIDE_INT number;
1383 static htab_t size_htab = 0;
1384 static tree new_const = 0;
1389 size_htab = htab_create (1024, size_htab_hash, size_htab_eq, NULL);
1390 ggc_add_deletable_htab (size_htab, NULL, NULL);
1391 new_const = make_node (INTEGER_CST);
1392 ggc_add_tree_root (&new_const, 1);
1395 /* Adjust NEW_CONST to be the constant we want. If it's already in the
1396 hash table, we return the value from the hash table. Otherwise, we
1397 place that in the hash table and make a new node for the next time. */
1398 TREE_INT_CST_LOW (new_const) = number;
1399 TREE_INT_CST_HIGH (new_const) = number < 0 ? -1 : 0;
1400 TREE_TYPE (new_const) = type;
1401 TREE_OVERFLOW (new_const) = TREE_CONSTANT_OVERFLOW (new_const)
1402 = force_fit_type (new_const, 0);
1404 slot = htab_find_slot (size_htab, new_const, INSERT);
1409 *slot = (PTR) new_const;
1410 new_const = make_node (INTEGER_CST);
1414 return (tree) *slot;
1417 /* Combine operands OP1 and OP2 with arithmetic operation CODE. CODE
1418 is a tree code. The type of the result is taken from the operands.
1419 Both must be the same type integer type and it must be a size type.
1420 If the operands are constant, so is the result. */
1423 size_binop (code, arg0, arg1)
1424 enum tree_code code;
1427 tree type = TREE_TYPE (arg0);
1429 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1430 || type != TREE_TYPE (arg1))
1433 /* Handle the special case of two integer constants faster. */
1434 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1436 /* And some specific cases even faster than that. */
1437 if (code == PLUS_EXPR && integer_zerop (arg0))
1439 else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1440 && integer_zerop (arg1))
1442 else if (code == MULT_EXPR && integer_onep (arg0))
1445 /* Handle general case of two integer constants. */
1446 return int_const_binop (code, arg0, arg1, 0);
1449 if (arg0 == error_mark_node || arg1 == error_mark_node)
1450 return error_mark_node;
1452 return fold (build (code, type, arg0, arg1));
1455 /* Given two values, either both of sizetype or both of bitsizetype,
1456 compute the difference between the two values. Return the value
1457 in signed type corresponding to the type of the operands. */
1460 size_diffop (arg0, arg1)
1463 tree type = TREE_TYPE (arg0);
1466 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1467 || type != TREE_TYPE (arg1))
1470 /* If the type is already signed, just do the simple thing. */
1471 if (! TREE_UNSIGNED (type))
1472 return size_binop (MINUS_EXPR, arg0, arg1);
1474 ctype = (type == bitsizetype || type == ubitsizetype
1475 ? sbitsizetype : ssizetype);
1477 /* If either operand is not a constant, do the conversions to the signed
1478 type and subtract. The hardware will do the right thing with any
1479 overflow in the subtraction. */
1480 if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1481 return size_binop (MINUS_EXPR, convert (ctype, arg0),
1482 convert (ctype, arg1));
1484 /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1485 Otherwise, subtract the other way, convert to CTYPE (we know that can't
1486 overflow) and negate (which can't either). Special-case a result
1487 of zero while we're here. */
1488 if (tree_int_cst_equal (arg0, arg1))
1489 return convert (ctype, integer_zero_node);
1490 else if (tree_int_cst_lt (arg1, arg0))
1491 return convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1493 return size_binop (MINUS_EXPR, convert (ctype, integer_zero_node),
1494 convert (ctype, size_binop (MINUS_EXPR, arg1, arg0)));
1498 /* Given T, a tree representing type conversion of ARG1, a constant,
1499 return a constant tree representing the result of conversion. */
1502 fold_convert (t, arg1)
1506 tree type = TREE_TYPE (t);
1509 if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1511 if (TREE_CODE (arg1) == INTEGER_CST)
1513 /* If we would build a constant wider than GCC supports,
1514 leave the conversion unfolded. */
1515 if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1518 /* If we are trying to make a sizetype for a small integer, use
1519 size_int to pick up cached types to reduce duplicate nodes. */
1520 if (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1521 && !TREE_CONSTANT_OVERFLOW (arg1)
1522 && compare_tree_int (arg1, 10000) < 0)
1523 return size_int_type_wide (TREE_INT_CST_LOW (arg1), type);
1525 /* Given an integer constant, make new constant with new type,
1526 appropriately sign-extended or truncated. */
1527 t = build_int_2 (TREE_INT_CST_LOW (arg1),
1528 TREE_INT_CST_HIGH (arg1));
1529 TREE_TYPE (t) = type;
1530 /* Indicate an overflow if (1) ARG1 already overflowed,
1531 or (2) force_fit_type indicates an overflow.
1532 Tell force_fit_type that an overflow has already occurred
1533 if ARG1 is a too-large unsigned value and T is signed.
1534 But don't indicate an overflow if converting a pointer. */
1536 = ((force_fit_type (t,
1537 (TREE_INT_CST_HIGH (arg1) < 0
1538 && (TREE_UNSIGNED (type)
1539 < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1540 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1541 || TREE_OVERFLOW (arg1));
1542 TREE_CONSTANT_OVERFLOW (t)
1543 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1545 else if (TREE_CODE (arg1) == REAL_CST)
1547 /* Don't initialize these, use assignments.
1548 Initialized local aggregates don't work on old compilers. */
1552 tree type1 = TREE_TYPE (arg1);
1555 x = TREE_REAL_CST (arg1);
1556 l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1558 no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1559 if (!no_upper_bound)
1560 u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1562 /* See if X will be in range after truncation towards 0.
1563 To compensate for truncation, move the bounds away from 0,
1564 but reject if X exactly equals the adjusted bounds. */
1565 REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1566 if (!no_upper_bound)
1567 REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1568 /* If X is a NaN, use zero instead and show we have an overflow.
1569 Otherwise, range check. */
1570 if (REAL_VALUE_ISNAN (x))
1571 overflow = 1, x = dconst0;
1572 else if (! (REAL_VALUES_LESS (l, x)
1574 && REAL_VALUES_LESS (x, u)))
1578 HOST_WIDE_INT low, high;
1579 REAL_VALUE_TO_INT (&low, &high, x);
1580 t = build_int_2 (low, high);
1582 TREE_TYPE (t) = type;
1584 = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1585 TREE_CONSTANT_OVERFLOW (t)
1586 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1588 TREE_TYPE (t) = type;
1590 else if (TREE_CODE (type) == REAL_TYPE)
1592 if (TREE_CODE (arg1) == INTEGER_CST)
1593 return build_real_from_int_cst (type, arg1);
1594 if (TREE_CODE (arg1) == REAL_CST)
1596 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1599 TREE_TYPE (arg1) = type;
1603 t = build_real (type,
1604 real_value_truncate (TYPE_MODE (type),
1605 TREE_REAL_CST (arg1)));
1608 = TREE_OVERFLOW (arg1) | force_fit_type (t, 0);
1609 TREE_CONSTANT_OVERFLOW (t)
1610 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1614 TREE_CONSTANT (t) = 1;
1618 /* Return an expr equal to X but certainly not valid as an lvalue. */
1626 /* These things are certainly not lvalues. */
1627 if (TREE_CODE (x) == NON_LVALUE_EXPR
1628 || TREE_CODE (x) == INTEGER_CST
1629 || TREE_CODE (x) == REAL_CST
1630 || TREE_CODE (x) == STRING_CST
1631 || TREE_CODE (x) == ADDR_EXPR)
1634 result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1635 TREE_CONSTANT (result) = TREE_CONSTANT (x);
1639 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1640 Zero means allow extended lvalues. */
1642 int pedantic_lvalues;
1644 /* When pedantic, return an expr equal to X but certainly not valid as a
1645 pedantic lvalue. Otherwise, return X. */
1648 pedantic_non_lvalue (x)
1651 if (pedantic_lvalues)
1652 return non_lvalue (x);
1657 /* Given a tree comparison code, return the code that is the logical inverse
1658 of the given code. It is not safe to do this for floating-point
1659 comparisons, except for NE_EXPR and EQ_EXPR. */
1661 static enum tree_code
1662 invert_tree_comparison (code)
1663 enum tree_code code;
1684 /* Similar, but return the comparison that results if the operands are
1685 swapped. This is safe for floating-point. */
1687 static enum tree_code
1688 swap_tree_comparison (code)
1689 enum tree_code code;
1709 /* Return nonzero if CODE is a tree code that represents a truth value. */
1712 truth_value_p (code)
1713 enum tree_code code;
1715 return (TREE_CODE_CLASS (code) == '<'
1716 || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
1717 || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
1718 || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
1721 /* Return nonzero if two operands are necessarily equal.
1722 If ONLY_CONST is non-zero, only return non-zero for constants.
1723 This function tests whether the operands are indistinguishable;
1724 it does not test whether they are equal using C's == operation.
1725 The distinction is important for IEEE floating point, because
1726 (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1727 (2) two NaNs may be indistinguishable, but NaN!=NaN. */
1730 operand_equal_p (arg0, arg1, only_const)
1734 /* If both types don't have the same signedness, then we can't consider
1735 them equal. We must check this before the STRIP_NOPS calls
1736 because they may change the signedness of the arguments. */
1737 if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1743 if (TREE_CODE (arg0) != TREE_CODE (arg1)
1744 /* This is needed for conversions and for COMPONENT_REF.
1745 Might as well play it safe and always test this. */
1746 || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
1747 || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
1748 || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1751 /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1752 We don't care about side effects in that case because the SAVE_EXPR
1753 takes care of that for us. In all other cases, two expressions are
1754 equal if they have no side effects. If we have two identical
1755 expressions with side effects that should be treated the same due
1756 to the only side effects being identical SAVE_EXPR's, that will
1757 be detected in the recursive calls below. */
1758 if (arg0 == arg1 && ! only_const
1759 && (TREE_CODE (arg0) == SAVE_EXPR
1760 || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
1763 /* Next handle constant cases, those for which we can return 1 even
1764 if ONLY_CONST is set. */
1765 if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
1766 switch (TREE_CODE (arg0))
1769 return (! TREE_CONSTANT_OVERFLOW (arg0)
1770 && ! TREE_CONSTANT_OVERFLOW (arg1)
1771 && tree_int_cst_equal (arg0, arg1));
1774 return (! TREE_CONSTANT_OVERFLOW (arg0)
1775 && ! TREE_CONSTANT_OVERFLOW (arg1)
1776 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
1777 TREE_REAL_CST (arg1)));
1783 if (TREE_CONSTANT_OVERFLOW (arg0)
1784 || TREE_CONSTANT_OVERFLOW (arg1))
1787 v1 = TREE_VECTOR_CST_ELTS (arg0);
1788 v2 = TREE_VECTOR_CST_ELTS (arg1);
1791 if (!operand_equal_p (v1, v2, only_const))
1793 v1 = TREE_CHAIN (v1);
1794 v2 = TREE_CHAIN (v2);
1801 return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
1803 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
1807 return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
1808 && ! memcmp (TREE_STRING_POINTER (arg0),
1809 TREE_STRING_POINTER (arg1),
1810 TREE_STRING_LENGTH (arg0)));
1813 return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
1822 switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1825 /* Two conversions are equal only if signedness and modes match. */
1826 if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1827 && (TREE_UNSIGNED (TREE_TYPE (arg0))
1828 != TREE_UNSIGNED (TREE_TYPE (arg1))))
1831 return operand_equal_p (TREE_OPERAND (arg0, 0),
1832 TREE_OPERAND (arg1, 0), 0);
1836 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
1837 && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
1841 /* For commutative ops, allow the other order. */
1842 return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
1843 || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
1844 || TREE_CODE (arg0) == BIT_IOR_EXPR
1845 || TREE_CODE (arg0) == BIT_XOR_EXPR
1846 || TREE_CODE (arg0) == BIT_AND_EXPR
1847 || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
1848 && operand_equal_p (TREE_OPERAND (arg0, 0),
1849 TREE_OPERAND (arg1, 1), 0)
1850 && operand_equal_p (TREE_OPERAND (arg0, 1),
1851 TREE_OPERAND (arg1, 0), 0));
1854 /* If either of the pointer (or reference) expressions we are dereferencing
1855 contain a side effect, these cannot be equal. */
1856 if (TREE_SIDE_EFFECTS (arg0)
1857 || TREE_SIDE_EFFECTS (arg1))
1860 switch (TREE_CODE (arg0))
1863 return operand_equal_p (TREE_OPERAND (arg0, 0),
1864 TREE_OPERAND (arg1, 0), 0);
1868 case ARRAY_RANGE_REF:
1869 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1870 TREE_OPERAND (arg1, 0), 0)
1871 && operand_equal_p (TREE_OPERAND (arg0, 1),
1872 TREE_OPERAND (arg1, 1), 0));
1875 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1876 TREE_OPERAND (arg1, 0), 0)
1877 && operand_equal_p (TREE_OPERAND (arg0, 1),
1878 TREE_OPERAND (arg1, 1), 0)
1879 && operand_equal_p (TREE_OPERAND (arg0, 2),
1880 TREE_OPERAND (arg1, 2), 0));
1886 if (TREE_CODE (arg0) == RTL_EXPR)
1887 return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
1895 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1896 shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1898 When in doubt, return 0. */
1901 operand_equal_for_comparison_p (arg0, arg1, other)
1905 int unsignedp1, unsignedpo;
1906 tree primarg0, primarg1, primother;
1907 unsigned int correct_width;
1909 if (operand_equal_p (arg0, arg1, 0))
1912 if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1913 || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1916 /* Discard any conversions that don't change the modes of ARG0 and ARG1
1917 and see if the inner values are the same. This removes any
1918 signedness comparison, which doesn't matter here. */
1919 primarg0 = arg0, primarg1 = arg1;
1920 STRIP_NOPS (primarg0);
1921 STRIP_NOPS (primarg1);
1922 if (operand_equal_p (primarg0, primarg1, 0))
1925 /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1926 actual comparison operand, ARG0.
1928 First throw away any conversions to wider types
1929 already present in the operands. */
1931 primarg1 = get_narrower (arg1, &unsignedp1);
1932 primother = get_narrower (other, &unsignedpo);
1934 correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
1935 if (unsignedp1 == unsignedpo
1936 && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
1937 && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
1939 tree type = TREE_TYPE (arg0);
1941 /* Make sure shorter operand is extended the right way
1942 to match the longer operand. */
1943 primarg1 = convert ((*lang_hooks.types.signed_or_unsigned_type)
1944 (unsignedp1, TREE_TYPE (primarg1)), primarg1);
1946 if (operand_equal_p (arg0, convert (type, primarg1), 0))
1953 /* See if ARG is an expression that is either a comparison or is performing
1954 arithmetic on comparisons. The comparisons must only be comparing
1955 two different values, which will be stored in *CVAL1 and *CVAL2; if
1956 they are non-zero it means that some operands have already been found.
1957 No variables may be used anywhere else in the expression except in the
1958 comparisons. If SAVE_P is true it means we removed a SAVE_EXPR around
1959 the expression and save_expr needs to be called with CVAL1 and CVAL2.
1961 If this is true, return 1. Otherwise, return zero. */
1964 twoval_comparison_p (arg, cval1, cval2, save_p)
1966 tree *cval1, *cval2;
1969 enum tree_code code = TREE_CODE (arg);
1970 char class = TREE_CODE_CLASS (code);
1972 /* We can handle some of the 'e' cases here. */
1973 if (class == 'e' && code == TRUTH_NOT_EXPR)
1975 else if (class == 'e'
1976 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
1977 || code == COMPOUND_EXPR))
1980 else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
1981 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
1983 /* If we've already found a CVAL1 or CVAL2, this expression is
1984 two complex to handle. */
1985 if (*cval1 || *cval2)
1995 return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
1998 return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
1999 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2000 cval1, cval2, save_p));
2006 if (code == COND_EXPR)
2007 return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2008 cval1, cval2, save_p)
2009 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2010 cval1, cval2, save_p)
2011 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2012 cval1, cval2, save_p));
2016 /* First see if we can handle the first operand, then the second. For
2017 the second operand, we know *CVAL1 can't be zero. It must be that
2018 one side of the comparison is each of the values; test for the
2019 case where this isn't true by failing if the two operands
2022 if (operand_equal_p (TREE_OPERAND (arg, 0),
2023 TREE_OPERAND (arg, 1), 0))
2027 *cval1 = TREE_OPERAND (arg, 0);
2028 else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2030 else if (*cval2 == 0)
2031 *cval2 = TREE_OPERAND (arg, 0);
2032 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2037 if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2039 else if (*cval2 == 0)
2040 *cval2 = TREE_OPERAND (arg, 1);
2041 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2053 /* ARG is a tree that is known to contain just arithmetic operations and
2054 comparisons. Evaluate the operations in the tree substituting NEW0 for
2055 any occurrence of OLD0 as an operand of a comparison and likewise for
2059 eval_subst (arg, old0, new0, old1, new1)
2061 tree old0, new0, old1, new1;
2063 tree type = TREE_TYPE (arg);
2064 enum tree_code code = TREE_CODE (arg);
2065 char class = TREE_CODE_CLASS (code);
2067 /* We can handle some of the 'e' cases here. */
2068 if (class == 'e' && code == TRUTH_NOT_EXPR)
2070 else if (class == 'e'
2071 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2077 return fold (build1 (code, type,
2078 eval_subst (TREE_OPERAND (arg, 0),
2079 old0, new0, old1, new1)));
2082 return fold (build (code, type,
2083 eval_subst (TREE_OPERAND (arg, 0),
2084 old0, new0, old1, new1),
2085 eval_subst (TREE_OPERAND (arg, 1),
2086 old0, new0, old1, new1)));
2092 return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2095 return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2098 return fold (build (code, type,
2099 eval_subst (TREE_OPERAND (arg, 0),
2100 old0, new0, old1, new1),
2101 eval_subst (TREE_OPERAND (arg, 1),
2102 old0, new0, old1, new1),
2103 eval_subst (TREE_OPERAND (arg, 2),
2104 old0, new0, old1, new1)));
2108 /* fall through - ??? */
2112 tree arg0 = TREE_OPERAND (arg, 0);
2113 tree arg1 = TREE_OPERAND (arg, 1);
2115 /* We need to check both for exact equality and tree equality. The
2116 former will be true if the operand has a side-effect. In that
2117 case, we know the operand occurred exactly once. */
2119 if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2121 else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2124 if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2126 else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2129 return fold (build (code, type, arg0, arg1));
2137 /* Return a tree for the case when the result of an expression is RESULT
2138 converted to TYPE and OMITTED was previously an operand of the expression
2139 but is now not needed (e.g., we folded OMITTED * 0).
2141 If OMITTED has side effects, we must evaluate it. Otherwise, just do
2142 the conversion of RESULT to TYPE. */
2145 omit_one_operand (type, result, omitted)
2146 tree type, result, omitted;
2148 tree t = convert (type, result);
2150 if (TREE_SIDE_EFFECTS (omitted))
2151 return build (COMPOUND_EXPR, type, omitted, t);
2153 return non_lvalue (t);
2156 /* Similar, but call pedantic_non_lvalue instead of non_lvalue. */
2159 pedantic_omit_one_operand (type, result, omitted)
2160 tree type, result, omitted;
2162 tree t = convert (type, result);
2164 if (TREE_SIDE_EFFECTS (omitted))
2165 return build (COMPOUND_EXPR, type, omitted, t);
2167 return pedantic_non_lvalue (t);
2170 /* Return a simplified tree node for the truth-negation of ARG. This
2171 never alters ARG itself. We assume that ARG is an operation that
2172 returns a truth value (0 or 1). */
2175 invert_truthvalue (arg)
2178 tree type = TREE_TYPE (arg);
2179 enum tree_code code = TREE_CODE (arg);
2181 if (code == ERROR_MARK)
2184 /* If this is a comparison, we can simply invert it, except for
2185 floating-point non-equality comparisons, in which case we just
2186 enclose a TRUTH_NOT_EXPR around what we have. */
2188 if (TREE_CODE_CLASS (code) == '<')
2190 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2191 && !flag_unsafe_math_optimizations
2194 return build1 (TRUTH_NOT_EXPR, type, arg);
2196 return build (invert_tree_comparison (code), type,
2197 TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2203 return convert (type, build_int_2 (integer_zerop (arg), 0));
2205 case TRUTH_AND_EXPR:
2206 return build (TRUTH_OR_EXPR, type,
2207 invert_truthvalue (TREE_OPERAND (arg, 0)),
2208 invert_truthvalue (TREE_OPERAND (arg, 1)));
2211 return build (TRUTH_AND_EXPR, type,
2212 invert_truthvalue (TREE_OPERAND (arg, 0)),
2213 invert_truthvalue (TREE_OPERAND (arg, 1)));
2215 case TRUTH_XOR_EXPR:
2216 /* Here we can invert either operand. We invert the first operand
2217 unless the second operand is a TRUTH_NOT_EXPR in which case our
2218 result is the XOR of the first operand with the inside of the
2219 negation of the second operand. */
2221 if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2222 return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2223 TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2225 return build (TRUTH_XOR_EXPR, type,
2226 invert_truthvalue (TREE_OPERAND (arg, 0)),
2227 TREE_OPERAND (arg, 1));
2229 case TRUTH_ANDIF_EXPR:
2230 return build (TRUTH_ORIF_EXPR, type,
2231 invert_truthvalue (TREE_OPERAND (arg, 0)),
2232 invert_truthvalue (TREE_OPERAND (arg, 1)));
2234 case TRUTH_ORIF_EXPR:
2235 return build (TRUTH_ANDIF_EXPR, type,
2236 invert_truthvalue (TREE_OPERAND (arg, 0)),
2237 invert_truthvalue (TREE_OPERAND (arg, 1)));
2239 case TRUTH_NOT_EXPR:
2240 return TREE_OPERAND (arg, 0);
2243 return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2244 invert_truthvalue (TREE_OPERAND (arg, 1)),
2245 invert_truthvalue (TREE_OPERAND (arg, 2)));
2248 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2249 invert_truthvalue (TREE_OPERAND (arg, 1)));
2251 case WITH_RECORD_EXPR:
2252 return build (WITH_RECORD_EXPR, type,
2253 invert_truthvalue (TREE_OPERAND (arg, 0)),
2254 TREE_OPERAND (arg, 1));
2256 case NON_LVALUE_EXPR:
2257 return invert_truthvalue (TREE_OPERAND (arg, 0));
2262 return build1 (TREE_CODE (arg), type,
2263 invert_truthvalue (TREE_OPERAND (arg, 0)));
2266 if (!integer_onep (TREE_OPERAND (arg, 1)))
2268 return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2271 return build1 (TRUTH_NOT_EXPR, type, arg);
2273 case CLEANUP_POINT_EXPR:
2274 return build1 (CLEANUP_POINT_EXPR, type,
2275 invert_truthvalue (TREE_OPERAND (arg, 0)));
2280 if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2282 return build1 (TRUTH_NOT_EXPR, type, arg);
2285 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2286 operands are another bit-wise operation with a common input. If so,
2287 distribute the bit operations to save an operation and possibly two if
2288 constants are involved. For example, convert
2289 (A | B) & (A | C) into A | (B & C)
2290 Further simplification will occur if B and C are constants.
2292 If this optimization cannot be done, 0 will be returned. */
2295 distribute_bit_expr (code, type, arg0, arg1)
2296 enum tree_code code;
2303 if (TREE_CODE (arg0) != TREE_CODE (arg1)
2304 || TREE_CODE (arg0) == code
2305 || (TREE_CODE (arg0) != BIT_AND_EXPR
2306 && TREE_CODE (arg0) != BIT_IOR_EXPR))
2309 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2311 common = TREE_OPERAND (arg0, 0);
2312 left = TREE_OPERAND (arg0, 1);
2313 right = TREE_OPERAND (arg1, 1);
2315 else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2317 common = TREE_OPERAND (arg0, 0);
2318 left = TREE_OPERAND (arg0, 1);
2319 right = TREE_OPERAND (arg1, 0);
2321 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2323 common = TREE_OPERAND (arg0, 1);
2324 left = TREE_OPERAND (arg0, 0);
2325 right = TREE_OPERAND (arg1, 1);
2327 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2329 common = TREE_OPERAND (arg0, 1);
2330 left = TREE_OPERAND (arg0, 0);
2331 right = TREE_OPERAND (arg1, 0);
2336 return fold (build (TREE_CODE (arg0), type, common,
2337 fold (build (code, type, left, right))));
2340 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2341 starting at BITPOS. The field is unsigned if UNSIGNEDP is non-zero. */
2344 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2347 int bitsize, bitpos;
2350 tree result = build (BIT_FIELD_REF, type, inner,
2351 size_int (bitsize), bitsize_int (bitpos));
2353 TREE_UNSIGNED (result) = unsignedp;
2358 /* Optimize a bit-field compare.
2360 There are two cases: First is a compare against a constant and the
2361 second is a comparison of two items where the fields are at the same
2362 bit position relative to the start of a chunk (byte, halfword, word)
2363 large enough to contain it. In these cases we can avoid the shift
2364 implicit in bitfield extractions.
2366 For constants, we emit a compare of the shifted constant with the
2367 BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2368 compared. For two fields at the same position, we do the ANDs with the
2369 similar mask and compare the result of the ANDs.
2371 CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2372 COMPARE_TYPE is the type of the comparison, and LHS and RHS
2373 are the left and right operands of the comparison, respectively.
2375 If the optimization described above can be done, we return the resulting
2376 tree. Otherwise we return zero. */
2379 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2380 enum tree_code code;
2384 HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2385 tree type = TREE_TYPE (lhs);
2386 tree signed_type, unsigned_type;
2387 int const_p = TREE_CODE (rhs) == INTEGER_CST;
2388 enum machine_mode lmode, rmode, nmode;
2389 int lunsignedp, runsignedp;
2390 int lvolatilep = 0, rvolatilep = 0;
2391 tree linner, rinner = NULL_TREE;
2395 /* Get all the information about the extractions being done. If the bit size
2396 if the same as the size of the underlying object, we aren't doing an
2397 extraction at all and so can do nothing. We also don't want to
2398 do anything if the inner expression is a PLACEHOLDER_EXPR since we
2399 then will no longer be able to replace it. */
2400 linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2401 &lunsignedp, &lvolatilep);
2402 if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2403 || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2408 /* If this is not a constant, we can only do something if bit positions,
2409 sizes, and signedness are the same. */
2410 rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2411 &runsignedp, &rvolatilep);
2413 if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2414 || lunsignedp != runsignedp || offset != 0
2415 || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2419 /* See if we can find a mode to refer to this field. We should be able to,
2420 but fail if we can't. */
2421 nmode = get_best_mode (lbitsize, lbitpos,
2422 const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2423 : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2424 TYPE_ALIGN (TREE_TYPE (rinner))),
2425 word_mode, lvolatilep || rvolatilep);
2426 if (nmode == VOIDmode)
2429 /* Set signed and unsigned types of the precision of this mode for the
2431 signed_type = (*lang_hooks.types.type_for_mode) (nmode, 0);
2432 unsigned_type = (*lang_hooks.types.type_for_mode) (nmode, 1);
2434 /* Compute the bit position and size for the new reference and our offset
2435 within it. If the new reference is the same size as the original, we
2436 won't optimize anything, so return zero. */
2437 nbitsize = GET_MODE_BITSIZE (nmode);
2438 nbitpos = lbitpos & ~ (nbitsize - 1);
2440 if (nbitsize == lbitsize)
2443 if (BYTES_BIG_ENDIAN)
2444 lbitpos = nbitsize - lbitsize - lbitpos;
2446 /* Make the mask to be used against the extracted field. */
2447 mask = build_int_2 (~0, ~0);
2448 TREE_TYPE (mask) = unsigned_type;
2449 force_fit_type (mask, 0);
2450 mask = convert (unsigned_type, mask);
2451 mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2452 mask = const_binop (RSHIFT_EXPR, mask,
2453 size_int (nbitsize - lbitsize - lbitpos), 0);
2456 /* If not comparing with constant, just rework the comparison
2458 return build (code, compare_type,
2459 build (BIT_AND_EXPR, unsigned_type,
2460 make_bit_field_ref (linner, unsigned_type,
2461 nbitsize, nbitpos, 1),
2463 build (BIT_AND_EXPR, unsigned_type,
2464 make_bit_field_ref (rinner, unsigned_type,
2465 nbitsize, nbitpos, 1),
2468 /* Otherwise, we are handling the constant case. See if the constant is too
2469 big for the field. Warn and return a tree of for 0 (false) if so. We do
2470 this not only for its own sake, but to avoid having to test for this
2471 error case below. If we didn't, we might generate wrong code.
2473 For unsigned fields, the constant shifted right by the field length should
2474 be all zero. For signed fields, the high-order bits should agree with
2479 if (! integer_zerop (const_binop (RSHIFT_EXPR,
2480 convert (unsigned_type, rhs),
2481 size_int (lbitsize), 0)))
2483 warning ("comparison is always %d due to width of bit-field",
2485 return convert (compare_type,
2487 ? integer_one_node : integer_zero_node));
2492 tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2493 size_int (lbitsize - 1), 0);
2494 if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2496 warning ("comparison is always %d due to width of bit-field",
2498 return convert (compare_type,
2500 ? integer_one_node : integer_zero_node));
2504 /* Single-bit compares should always be against zero. */
2505 if (lbitsize == 1 && ! integer_zerop (rhs))
2507 code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2508 rhs = convert (type, integer_zero_node);
2511 /* Make a new bitfield reference, shift the constant over the
2512 appropriate number of bits and mask it with the computed mask
2513 (in case this was a signed field). If we changed it, make a new one. */
2514 lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2517 TREE_SIDE_EFFECTS (lhs) = 1;
2518 TREE_THIS_VOLATILE (lhs) = 1;
2521 rhs = fold (const_binop (BIT_AND_EXPR,
2522 const_binop (LSHIFT_EXPR,
2523 convert (unsigned_type, rhs),
2524 size_int (lbitpos), 0),
2527 return build (code, compare_type,
2528 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2532 /* Subroutine for fold_truthop: decode a field reference.
2534 If EXP is a comparison reference, we return the innermost reference.
2536 *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2537 set to the starting bit number.
2539 If the innermost field can be completely contained in a mode-sized
2540 unit, *PMODE is set to that mode. Otherwise, it is set to VOIDmode.
2542 *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2543 otherwise it is not changed.
2545 *PUNSIGNEDP is set to the signedness of the field.
2547 *PMASK is set to the mask used. This is either contained in a
2548 BIT_AND_EXPR or derived from the width of the field.
2550 *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2552 Return 0 if this is not a component reference or is one that we can't
2553 do anything with. */
2556 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2557 pvolatilep, pmask, pand_mask)
2559 HOST_WIDE_INT *pbitsize, *pbitpos;
2560 enum machine_mode *pmode;
2561 int *punsignedp, *pvolatilep;
2566 tree mask, inner, offset;
2568 unsigned int precision;
2570 /* All the optimizations using this function assume integer fields.
2571 There are problems with FP fields since the type_for_size call
2572 below can fail for, e.g., XFmode. */
2573 if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2578 if (TREE_CODE (exp) == BIT_AND_EXPR)
2580 and_mask = TREE_OPERAND (exp, 1);
2581 exp = TREE_OPERAND (exp, 0);
2582 STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2583 if (TREE_CODE (and_mask) != INTEGER_CST)
2587 inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2588 punsignedp, pvolatilep);
2589 if ((inner == exp && and_mask == 0)
2590 || *pbitsize < 0 || offset != 0
2591 || TREE_CODE (inner) == PLACEHOLDER_EXPR)
2594 /* Compute the mask to access the bitfield. */
2595 unsigned_type = (*lang_hooks.types.type_for_size) (*pbitsize, 1);
2596 precision = TYPE_PRECISION (unsigned_type);
2598 mask = build_int_2 (~0, ~0);
2599 TREE_TYPE (mask) = unsigned_type;
2600 force_fit_type (mask, 0);
2601 mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2602 mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2604 /* Merge it with the mask we found in the BIT_AND_EXPR, if any. */
2606 mask = fold (build (BIT_AND_EXPR, unsigned_type,
2607 convert (unsigned_type, and_mask), mask));
2610 *pand_mask = and_mask;
2614 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2618 all_ones_mask_p (mask, size)
2622 tree type = TREE_TYPE (mask);
2623 unsigned int precision = TYPE_PRECISION (type);
2626 tmask = build_int_2 (~0, ~0);
2627 TREE_TYPE (tmask) = (*lang_hooks.types.signed_type) (type);
2628 force_fit_type (tmask, 0);
2630 tree_int_cst_equal (mask,
2631 const_binop (RSHIFT_EXPR,
2632 const_binop (LSHIFT_EXPR, tmask,
2633 size_int (precision - size),
2635 size_int (precision - size), 0));
2638 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
2639 represents the sign bit of EXP's type. If EXP represents a sign
2640 or zero extension, also test VAL against the unextended type.
2641 The return value is the (sub)expression whose sign bit is VAL,
2642 or NULL_TREE otherwise. */
2645 sign_bit_p (exp, val)
2649 unsigned HOST_WIDE_INT lo;
2654 /* Tree EXP must have a integral type. */
2655 t = TREE_TYPE (exp);
2656 if (! INTEGRAL_TYPE_P (t))
2659 /* Tree VAL must be an integer constant. */
2660 if (TREE_CODE (val) != INTEGER_CST
2661 || TREE_CONSTANT_OVERFLOW (val))
2664 width = TYPE_PRECISION (t);
2665 if (width > HOST_BITS_PER_WIDE_INT)
2667 hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
2673 lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
2676 if (TREE_INT_CST_HIGH (val) == hi && TREE_INT_CST_LOW (val) == lo)
2679 /* Handle extension from a narrower type. */
2680 if (TREE_CODE (exp) == NOP_EXPR
2681 && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
2682 return sign_bit_p (TREE_OPERAND (exp, 0), val);
2687 /* Subroutine for fold_truthop: determine if an operand is simple enough
2688 to be evaluated unconditionally. */
2691 simple_operand_p (exp)
2694 /* Strip any conversions that don't change the machine mode. */
2695 while ((TREE_CODE (exp) == NOP_EXPR
2696 || TREE_CODE (exp) == CONVERT_EXPR)
2697 && (TYPE_MODE (TREE_TYPE (exp))
2698 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2699 exp = TREE_OPERAND (exp, 0);
2701 return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2703 && ! TREE_ADDRESSABLE (exp)
2704 && ! TREE_THIS_VOLATILE (exp)
2705 && ! DECL_NONLOCAL (exp)
2706 /* Don't regard global variables as simple. They may be
2707 allocated in ways unknown to the compiler (shared memory,
2708 #pragma weak, etc). */
2709 && ! TREE_PUBLIC (exp)
2710 && ! DECL_EXTERNAL (exp)
2711 /* Loading a static variable is unduly expensive, but global
2712 registers aren't expensive. */
2713 && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2716 /* The following functions are subroutines to fold_range_test and allow it to
2717 try to change a logical combination of comparisons into a range test.
2720 X == 2 || X == 3 || X == 4 || X == 5
2724 (unsigned) (X - 2) <= 3
2726 We describe each set of comparisons as being either inside or outside
2727 a range, using a variable named like IN_P, and then describe the
2728 range with a lower and upper bound. If one of the bounds is omitted,
2729 it represents either the highest or lowest value of the type.
2731 In the comments below, we represent a range by two numbers in brackets
2732 preceded by a "+" to designate being inside that range, or a "-" to
2733 designate being outside that range, so the condition can be inverted by
2734 flipping the prefix. An omitted bound is represented by a "-". For
2735 example, "- [-, 10]" means being outside the range starting at the lowest
2736 possible value and ending at 10, in other words, being greater than 10.
2737 The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2740 We set up things so that the missing bounds are handled in a consistent
2741 manner so neither a missing bound nor "true" and "false" need to be
2742 handled using a special case. */
2744 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2745 of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2746 and UPPER1_P are nonzero if the respective argument is an upper bound
2747 and zero for a lower. TYPE, if nonzero, is the type of the result; it
2748 must be specified for a comparison. ARG1 will be converted to ARG0's
2749 type if both are specified. */
2752 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2753 enum tree_code code;
2756 int upper0_p, upper1_p;
2762 /* If neither arg represents infinity, do the normal operation.
2763 Else, if not a comparison, return infinity. Else handle the special
2764 comparison rules. Note that most of the cases below won't occur, but
2765 are handled for consistency. */
2767 if (arg0 != 0 && arg1 != 0)
2769 tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2770 arg0, convert (TREE_TYPE (arg0), arg1)));
2772 return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2775 if (TREE_CODE_CLASS (code) != '<')
2778 /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2779 for neither. In real maths, we cannot assume open ended ranges are
2780 the same. But, this is computer arithmetic, where numbers are finite.
2781 We can therefore make the transformation of any unbounded range with
2782 the value Z, Z being greater than any representable number. This permits
2783 us to treat unbounded ranges as equal. */
2784 sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2785 sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2789 result = sgn0 == sgn1;
2792 result = sgn0 != sgn1;
2795 result = sgn0 < sgn1;
2798 result = sgn0 <= sgn1;
2801 result = sgn0 > sgn1;
2804 result = sgn0 >= sgn1;
2810 return convert (type, result ? integer_one_node : integer_zero_node);
2813 /* Given EXP, a logical expression, set the range it is testing into
2814 variables denoted by PIN_P, PLOW, and PHIGH. Return the expression
2815 actually being tested. *PLOW and *PHIGH will be made of the same type
2816 as the returned expression. If EXP is not a comparison, we will most
2817 likely not be returning a useful value and range. */
2820 make_range (exp, pin_p, plow, phigh)
2825 enum tree_code code;
2826 tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
2827 tree orig_type = NULL_TREE;
2829 tree low, high, n_low, n_high;
2831 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2832 and see if we can refine the range. Some of the cases below may not
2833 happen, but it doesn't seem worth worrying about this. We "continue"
2834 the outer loop when we've changed something; otherwise we "break"
2835 the switch, which will "break" the while. */
2837 in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2841 code = TREE_CODE (exp);
2843 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2845 arg0 = TREE_OPERAND (exp, 0);
2846 if (TREE_CODE_CLASS (code) == '<'
2847 || TREE_CODE_CLASS (code) == '1'
2848 || TREE_CODE_CLASS (code) == '2')
2849 type = TREE_TYPE (arg0);
2850 if (TREE_CODE_CLASS (code) == '2'
2851 || TREE_CODE_CLASS (code) == '<'
2852 || (TREE_CODE_CLASS (code) == 'e'
2853 && TREE_CODE_LENGTH (code) > 1))
2854 arg1 = TREE_OPERAND (exp, 1);
2857 /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
2858 lose a cast by accident. */
2859 if (type != NULL_TREE && orig_type == NULL_TREE)
2864 case TRUTH_NOT_EXPR:
2865 in_p = ! in_p, exp = arg0;
2868 case EQ_EXPR: case NE_EXPR:
2869 case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2870 /* We can only do something if the range is testing for zero
2871 and if the second operand is an integer constant. Note that
2872 saying something is "in" the range we make is done by
2873 complementing IN_P since it will set in the initial case of
2874 being not equal to zero; "out" is leaving it alone. */
2875 if (low == 0 || high == 0
2876 || ! integer_zerop (low) || ! integer_zerop (high)
2877 || TREE_CODE (arg1) != INTEGER_CST)
2882 case NE_EXPR: /* - [c, c] */
2885 case EQ_EXPR: /* + [c, c] */
2886 in_p = ! in_p, low = high = arg1;
2888 case GT_EXPR: /* - [-, c] */
2889 low = 0, high = arg1;
2891 case GE_EXPR: /* + [c, -] */
2892 in_p = ! in_p, low = arg1, high = 0;
2894 case LT_EXPR: /* - [c, -] */
2895 low = arg1, high = 0;
2897 case LE_EXPR: /* + [-, c] */
2898 in_p = ! in_p, low = 0, high = arg1;
2906 /* If this is an unsigned comparison, we also know that EXP is
2907 greater than or equal to zero. We base the range tests we make
2908 on that fact, so we record it here so we can parse existing
2910 if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2912 if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2913 1, convert (type, integer_zero_node),
2917 in_p = n_in_p, low = n_low, high = n_high;
2919 /* If the high bound is missing, but we
2920 have a low bound, reverse the range so
2921 it goes from zero to the low bound minus 1. */
2922 if (high == 0 && low)
2925 high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2926 integer_one_node, 0);
2927 low = convert (type, integer_zero_node);
2933 /* (-x) IN [a,b] -> x in [-b, -a] */
2934 n_low = range_binop (MINUS_EXPR, type,
2935 convert (type, integer_zero_node), 0, high, 1);
2936 n_high = range_binop (MINUS_EXPR, type,
2937 convert (type, integer_zero_node), 0, low, 0);
2938 low = n_low, high = n_high;
2944 exp = build (MINUS_EXPR, type, negate_expr (arg0),
2945 convert (type, integer_one_node));
2948 case PLUS_EXPR: case MINUS_EXPR:
2949 if (TREE_CODE (arg1) != INTEGER_CST)
2952 /* If EXP is signed, any overflow in the computation is undefined,
2953 so we don't worry about it so long as our computations on
2954 the bounds don't overflow. For unsigned, overflow is defined
2955 and this is exactly the right thing. */
2956 n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2957 type, low, 0, arg1, 0);
2958 n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2959 type, high, 1, arg1, 0);
2960 if ((n_low != 0 && TREE_OVERFLOW (n_low))
2961 || (n_high != 0 && TREE_OVERFLOW (n_high)))
2964 /* Check for an unsigned range which has wrapped around the maximum
2965 value thus making n_high < n_low, and normalize it. */
2966 if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
2968 low = range_binop (PLUS_EXPR, type, n_high, 0,
2969 integer_one_node, 0);
2970 high = range_binop (MINUS_EXPR, type, n_low, 0,
2971 integer_one_node, 0);
2973 /* If the range is of the form +/- [ x+1, x ], we won't
2974 be able to normalize it. But then, it represents the
2975 whole range or the empty set, so make it
2977 if (tree_int_cst_equal (n_low, low)
2978 && tree_int_cst_equal (n_high, high))
2984 low = n_low, high = n_high;
2989 case NOP_EXPR: case NON_LVALUE_EXPR: case CONVERT_EXPR:
2990 if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
2993 if (! INTEGRAL_TYPE_P (type)
2994 || (low != 0 && ! int_fits_type_p (low, type))
2995 || (high != 0 && ! int_fits_type_p (high, type)))
2998 n_low = low, n_high = high;
3001 n_low = convert (type, n_low);
3004 n_high = convert (type, n_high);
3006 /* If we're converting from an unsigned to a signed type,
3007 we will be doing the comparison as unsigned. The tests above
3008 have already verified that LOW and HIGH are both positive.
3010 So we have to make sure that the original unsigned value will
3011 be interpreted as positive. */
3012 if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
3014 tree equiv_type = (*lang_hooks.types.type_for_mode)
3015 (TYPE_MODE (type), 1);
3018 /* A range without an upper bound is, naturally, unbounded.
3019 Since convert would have cropped a very large value, use
3020 the max value for the destination type. */
3022 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
3023 : TYPE_MAX_VALUE (type);
3025 high_positive = fold (build (RSHIFT_EXPR, type,
3026 convert (type, high_positive),
3027 convert (type, integer_one_node)));
3029 /* If the low bound is specified, "and" the range with the
3030 range for which the original unsigned value will be
3034 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3036 1, convert (type, integer_zero_node),
3040 in_p = (n_in_p == in_p);
3044 /* Otherwise, "or" the range with the range of the input
3045 that will be interpreted as negative. */
3046 if (! merge_ranges (&n_in_p, &n_low, &n_high,
3048 1, convert (type, integer_zero_node),
3052 in_p = (in_p != n_in_p);
3057 low = n_low, high = n_high;
3067 /* If EXP is a constant, we can evaluate whether this is true or false. */
3068 if (TREE_CODE (exp) == INTEGER_CST)
3070 in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3072 && integer_onep (range_binop (LE_EXPR, integer_type_node,
3078 *pin_p = in_p, *plow = low, *phigh = high;
3082 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3083 type, TYPE, return an expression to test if EXP is in (or out of, depending
3084 on IN_P) the range. */
3087 build_range_check (type, exp, in_p, low, high)
3093 tree etype = TREE_TYPE (exp);
3097 && (0 != (value = build_range_check (type, exp, 1, low, high))))
3098 return invert_truthvalue (value);
3100 if (low == 0 && high == 0)
3101 return convert (type, integer_one_node);
3104 return fold (build (LE_EXPR, type, exp, high));
3107 return fold (build (GE_EXPR, type, exp, low));
3109 if (operand_equal_p (low, high, 0))
3110 return fold (build (EQ_EXPR, type, exp, low));
3112 if (integer_zerop (low))
3114 if (! TREE_UNSIGNED (etype))
3116 etype = (*lang_hooks.types.unsigned_type) (etype);
3117 high = convert (etype, high);
3118 exp = convert (etype, exp);
3120 return build_range_check (type, exp, 1, 0, high);
3123 /* Optimize (c>=1) && (c<=127) into (signed char)c > 0. */
3124 if (integer_onep (low) && TREE_CODE (high) == INTEGER_CST)
3126 unsigned HOST_WIDE_INT lo;
3130 prec = TYPE_PRECISION (etype);
3131 if (prec <= HOST_BITS_PER_WIDE_INT)
3134 lo = ((unsigned HOST_WIDE_INT) 1 << (prec - 1)) - 1;
3138 hi = ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)) - 1;
3139 lo = (unsigned HOST_WIDE_INT) -1;
3142 if (TREE_INT_CST_HIGH (high) == hi && TREE_INT_CST_LOW (high) == lo)
3144 if (TREE_UNSIGNED (etype))
3146 etype = (*lang_hooks.types.signed_type) (etype);
3147 exp = convert (etype, exp);
3149 return fold (build (GT_EXPR, type, exp,
3150 convert (etype, integer_zero_node)));
3154 if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3155 && ! TREE_OVERFLOW (value))
3156 return build_range_check (type,
3157 fold (build (MINUS_EXPR, etype, exp, low)),
3158 1, convert (etype, integer_zero_node), value);
3163 /* Given two ranges, see if we can merge them into one. Return 1 if we
3164 can, 0 if we can't. Set the output range into the specified parameters. */
3167 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3171 tree low0, high0, low1, high1;
3179 int lowequal = ((low0 == 0 && low1 == 0)
3180 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3181 low0, 0, low1, 0)));
3182 int highequal = ((high0 == 0 && high1 == 0)
3183 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3184 high0, 1, high1, 1)));
3186 /* Make range 0 be the range that starts first, or ends last if they
3187 start at the same value. Swap them if it isn't. */
3188 if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3191 && integer_onep (range_binop (GT_EXPR, integer_type_node,
3192 high1, 1, high0, 1))))
3194 temp = in0_p, in0_p = in1_p, in1_p = temp;
3195 tem = low0, low0 = low1, low1 = tem;
3196 tem = high0, high0 = high1, high1 = tem;
3199 /* Now flag two cases, whether the ranges are disjoint or whether the
3200 second range is totally subsumed in the first. Note that the tests
3201 below are simplified by the ones above. */
3202 no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3203 high0, 1, low1, 0));
3204 subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3205 high1, 1, high0, 1));
3207 /* We now have four cases, depending on whether we are including or
3208 excluding the two ranges. */
3211 /* If they don't overlap, the result is false. If the second range
3212 is a subset it is the result. Otherwise, the range is from the start
3213 of the second to the end of the first. */
3215 in_p = 0, low = high = 0;
3217 in_p = 1, low = low1, high = high1;
3219 in_p = 1, low = low1, high = high0;
3222 else if (in0_p && ! in1_p)
3224 /* If they don't overlap, the result is the first range. If they are
3225 equal, the result is false. If the second range is a subset of the
3226 first, and the ranges begin at the same place, we go from just after
3227 the end of the first range to the end of the second. If the second
3228 range is not a subset of the first, or if it is a subset and both
3229 ranges end at the same place, the range starts at the start of the
3230 first range and ends just before the second range.
3231 Otherwise, we can't describe this as a single range. */
3233 in_p = 1, low = low0, high = high0;
3234 else if (lowequal && highequal)
3235 in_p = 0, low = high = 0;
3236 else if (subset && lowequal)
3238 in_p = 1, high = high0;
3239 low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3240 integer_one_node, 0);
3242 else if (! subset || highequal)
3244 in_p = 1, low = low0;
3245 high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3246 integer_one_node, 0);
3252 else if (! in0_p && in1_p)
3254 /* If they don't overlap, the result is the second range. If the second
3255 is a subset of the first, the result is false. Otherwise,
3256 the range starts just after the first range and ends at the
3257 end of the second. */
3259 in_p = 1, low = low1, high = high1;
3260 else if (subset || highequal)
3261 in_p = 0, low = high = 0;
3264 in_p = 1, high = high1;
3265 low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3266 integer_one_node, 0);
3272 /* The case where we are excluding both ranges. Here the complex case
3273 is if they don't overlap. In that case, the only time we have a
3274 range is if they are adjacent. If the second is a subset of the
3275 first, the result is the first. Otherwise, the range to exclude
3276 starts at the beginning of the first range and ends at the end of the
3280 if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3281 range_binop (PLUS_EXPR, NULL_TREE,
3283 integer_one_node, 1),
3285 in_p = 0, low = low0, high = high1;
3290 in_p = 0, low = low0, high = high0;
3292 in_p = 0, low = low0, high = high1;
3295 *pin_p = in_p, *plow = low, *phigh = high;
3299 /* EXP is some logical combination of boolean tests. See if we can
3300 merge it into some range test. Return the new tree if so. */
3303 fold_range_test (exp)
3306 int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3307 || TREE_CODE (exp) == TRUTH_OR_EXPR);
3308 int in0_p, in1_p, in_p;
3309 tree low0, low1, low, high0, high1, high;
3310 tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3311 tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3314 /* If this is an OR operation, invert both sides; we will invert
3315 again at the end. */
3317 in0_p = ! in0_p, in1_p = ! in1_p;
3319 /* If both expressions are the same, if we can merge the ranges, and we
3320 can build the range test, return it or it inverted. If one of the
3321 ranges is always true or always false, consider it to be the same
3322 expression as the other. */
3323 if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3324 && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3326 && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3328 : rhs != 0 ? rhs : integer_zero_node,
3330 return or_op ? invert_truthvalue (tem) : tem;
3332 /* On machines where the branch cost is expensive, if this is a
3333 short-circuited branch and the underlying object on both sides
3334 is the same, make a non-short-circuit operation. */
3335 else if (BRANCH_COST >= 2
3336 && lhs != 0 && rhs != 0
3337 && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3338 || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3339 && operand_equal_p (lhs, rhs, 0))
3341 /* If simple enough, just rewrite. Otherwise, make a SAVE_EXPR
3342 unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3343 which cases we can't do this. */
3344 if (simple_operand_p (lhs))
3345 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3346 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3347 TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3348 TREE_OPERAND (exp, 1));
3350 else if ((*lang_hooks.decls.global_bindings_p) () == 0
3351 && ! contains_placeholder_p (lhs))
3353 tree common = save_expr (lhs);
3355 if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3356 or_op ? ! in0_p : in0_p,
3358 && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3359 or_op ? ! in1_p : in1_p,
3361 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3362 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3363 TREE_TYPE (exp), lhs, rhs);
3370 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3371 bit value. Arrange things so the extra bits will be set to zero if and
3372 only if C is signed-extended to its full width. If MASK is nonzero,
3373 it is an INTEGER_CST that should be AND'ed with the extra bits. */
3376 unextend (c, p, unsignedp, mask)
3382 tree type = TREE_TYPE (c);
3383 int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3386 if (p == modesize || unsignedp)
3389 /* We work by getting just the sign bit into the low-order bit, then
3390 into the high-order bit, then sign-extend. We then XOR that value
3392 temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3393 temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3395 /* We must use a signed type in order to get an arithmetic right shift.
3396 However, we must also avoid introducing accidental overflows, so that
3397 a subsequent call to integer_zerop will work. Hence we must
3398 do the type conversion here. At this point, the constant is either
3399 zero or one, and the conversion to a signed type can never overflow.
3400 We could get an overflow if this conversion is done anywhere else. */
3401 if (TREE_UNSIGNED (type))
3402 temp = convert ((*lang_hooks.types.signed_type) (type), temp);
3404 temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3405 temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3407 temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3408 /* If necessary, convert the type back to match the type of C. */
3409 if (TREE_UNSIGNED (type))
3410 temp = convert (type, temp);
3412 return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3415 /* Find ways of folding logical expressions of LHS and RHS:
3416 Try to merge two comparisons to the same innermost item.
3417 Look for range tests like "ch >= '0' && ch <= '9'".
3418 Look for combinations of simple terms on machines with expensive branches
3419 and evaluate the RHS unconditionally.
3421 For example, if we have p->a == 2 && p->b == 4 and we can make an
3422 object large enough to span both A and B, we can do this with a comparison
3423 against the object ANDed with the a mask.
3425 If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3426 operations to do this with one comparison.
3428 We check for both normal comparisons and the BIT_AND_EXPRs made this by
3429 function and the one above.
3431 CODE is the logical operation being done. It can be TRUTH_ANDIF_EXPR,
3432 TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3434 TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3437 We return the simplified tree or 0 if no optimization is possible. */
3440 fold_truthop (code, truth_type, lhs, rhs)
3441 enum tree_code code;
3442 tree truth_type, lhs, rhs;
3444 /* If this is the "or" of two comparisons, we can do something if
3445 the comparisons are NE_EXPR. If this is the "and", we can do something
3446 if the comparisons are EQ_EXPR. I.e.,
3447 (a->b == 2 && a->c == 4) can become (a->new == NEW).
3449 WANTED_CODE is this operation code. For single bit fields, we can
3450 convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3451 comparison for one-bit fields. */
3453 enum tree_code wanted_code;
3454 enum tree_code lcode, rcode;
3455 tree ll_arg, lr_arg, rl_arg, rr_arg;
3456 tree ll_inner, lr_inner, rl_inner, rr_inner;
3457 HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3458 HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3459 HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3460 HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3461 int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3462 enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3463 enum machine_mode lnmode, rnmode;
3464 tree ll_mask, lr_mask, rl_mask, rr_mask;
3465 tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3466 tree l_const, r_const;
3467 tree lntype, rntype, result;
3468 int first_bit, end_bit;
3471 /* Start by getting the comparison codes. Fail if anything is volatile.
3472 If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3473 it were surrounded with a NE_EXPR. */
3475 if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3478 lcode = TREE_CODE (lhs);
3479 rcode = TREE_CODE (rhs);
3481 if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3482 lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3484 if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3485 rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3487 if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3490 code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3491 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3493 ll_arg = TREE_OPERAND (lhs, 0);
3494 lr_arg = TREE_OPERAND (lhs, 1);
3495 rl_arg = TREE_OPERAND (rhs, 0);
3496 rr_arg = TREE_OPERAND (rhs, 1);
3498 /* If the RHS can be evaluated unconditionally and its operands are
3499 simple, it wins to evaluate the RHS unconditionally on machines
3500 with expensive branches. In this case, this isn't a comparison
3501 that can be merged. Avoid doing this if the RHS is a floating-point
3502 comparison since those can trap. */
3504 if (BRANCH_COST >= 2
3505 && ! FLOAT_TYPE_P (TREE_TYPE (rl_arg))
3506 && simple_operand_p (rl_arg)
3507 && simple_operand_p (rr_arg))
3508 return build (code, truth_type, lhs, rhs);
3510 /* See if the comparisons can be merged. Then get all the parameters for
3513 if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3514 || (rcode != EQ_EXPR && rcode != NE_EXPR))
3518 ll_inner = decode_field_reference (ll_arg,
3519 &ll_bitsize, &ll_bitpos, &ll_mode,
3520 &ll_unsignedp, &volatilep, &ll_mask,
3522 lr_inner = decode_field_reference (lr_arg,
3523 &lr_bitsize, &lr_bitpos, &lr_mode,
3524 &lr_unsignedp, &volatilep, &lr_mask,
3526 rl_inner = decode_field_reference (rl_arg,
3527 &rl_bitsize, &rl_bitpos, &rl_mode,
3528 &rl_unsignedp, &volatilep, &rl_mask,
3530 rr_inner = decode_field_reference (rr_arg,
3531 &rr_bitsize, &rr_bitpos, &rr_mode,
3532 &rr_unsignedp, &volatilep, &rr_mask,
3535 /* It must be true that the inner operation on the lhs of each
3536 comparison must be the same if we are to be able to do anything.
3537 Then see if we have constants. If not, the same must be true for
3539 if (volatilep || ll_inner == 0 || rl_inner == 0
3540 || ! operand_equal_p (ll_inner, rl_inner, 0))
3543 if (TREE_CODE (lr_arg) == INTEGER_CST
3544 && TREE_CODE (rr_arg) == INTEGER_CST)
3545 l_const = lr_arg, r_const = rr_arg;
3546 else if (lr_inner == 0 || rr_inner == 0
3547 || ! operand_equal_p (lr_inner, rr_inner, 0))
3550 l_const = r_const = 0;
3552 /* If either comparison code is not correct for our logical operation,
3553 fail. However, we can convert a one-bit comparison against zero into
3554 the opposite comparison against that bit being set in the field. */
3556 wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3557 if (lcode != wanted_code)
3559 if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3561 /* Make the left operand unsigned, since we are only interested
3562 in the value of one bit. Otherwise we are doing the wrong
3571 /* This is analogous to the code for l_const above. */
3572 if (rcode != wanted_code)
3574 if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3583 /* See if we can find a mode that contains both fields being compared on
3584 the left. If we can't, fail. Otherwise, update all constants and masks
3585 to be relative to a field of that size. */
3586 first_bit = MIN (ll_bitpos, rl_bitpos);
3587 end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3588 lnmode = get_best_mode (end_bit - first_bit, first_bit,
3589 TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3591 if (lnmode == VOIDmode)
3594 lnbitsize = GET_MODE_BITSIZE (lnmode);
3595 lnbitpos = first_bit & ~ (lnbitsize - 1);
3596 lntype = (*lang_hooks.types.type_for_size) (lnbitsize, 1);
3597 xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3599 if (BYTES_BIG_ENDIAN)
3601 xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3602 xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3605 ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3606 size_int (xll_bitpos), 0);
3607 rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3608 size_int (xrl_bitpos), 0);
3612 l_const = convert (lntype, l_const);
3613 l_const = unextend (l_const, ll_bitsize, ll_unsignedp, ll_and_mask);
3614 l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3615 if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3616 fold (build1 (BIT_NOT_EXPR,
3620 warning ("comparison is always %d", wanted_code == NE_EXPR);
3622 return convert (truth_type,
3623 wanted_code == NE_EXPR
3624 ? integer_one_node : integer_zero_node);
3629 r_const = convert (lntype, r_const);
3630 r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3631 r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3632 if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3633 fold (build1 (BIT_NOT_EXPR,
3637 warning ("comparison is always %d", wanted_code == NE_EXPR);
3639 return convert (truth_type,
3640 wanted_code == NE_EXPR
3641 ? integer_one_node : integer_zero_node);
3645 /* If the right sides are not constant, do the same for it. Also,
3646 disallow this optimization if a size or signedness mismatch occurs
3647 between the left and right sides. */
3650 if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3651 || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3652 /* Make sure the two fields on the right
3653 correspond to the left without being swapped. */
3654 || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3657 first_bit = MIN (lr_bitpos, rr_bitpos);
3658 end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3659 rnmode = get_best_mode (end_bit - first_bit, first_bit,
3660 TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3662 if (rnmode == VOIDmode)
3665 rnbitsize = GET_MODE_BITSIZE (rnmode);
3666 rnbitpos = first_bit & ~ (rnbitsize - 1);
3667 rntype = (*lang_hooks.types.type_for_size) (rnbitsize, 1);
3668 xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3670 if (BYTES_BIG_ENDIAN)
3672 xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3673 xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3676 lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3677 size_int (xlr_bitpos), 0);
3678 rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3679 size_int (xrr_bitpos), 0);
3681 /* Make a mask that corresponds to both fields being compared.
3682 Do this for both items being compared. If the operands are the
3683 same size and the bits being compared are in the same position
3684 then we can do this by masking both and comparing the masked
3686 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3687 lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3688 if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3690 lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3691 ll_unsignedp || rl_unsignedp);
3692 if (! all_ones_mask_p (ll_mask, lnbitsize))
3693 lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3695 rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3696 lr_unsignedp || rr_unsignedp);
3697 if (! all_ones_mask_p (lr_mask, rnbitsize))
3698 rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3700 return build (wanted_code, truth_type, lhs, rhs);
3703 /* There is still another way we can do something: If both pairs of
3704 fields being compared are adjacent, we may be able to make a wider
3705 field containing them both.
3707 Note that we still must mask the lhs/rhs expressions. Furthermore,
3708 the mask must be shifted to account for the shift done by
3709 make_bit_field_ref. */
3710 if ((ll_bitsize + ll_bitpos == rl_bitpos
3711 && lr_bitsize + lr_bitpos == rr_bitpos)
3712 || (ll_bitpos == rl_bitpos + rl_bitsize
3713 && lr_bitpos == rr_bitpos + rr_bitsize))
3717 lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3718 MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3719 rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3720 MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3722 ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3723 size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3724 lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3725 size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3727 /* Convert to the smaller type before masking out unwanted bits. */
3729 if (lntype != rntype)
3731 if (lnbitsize > rnbitsize)
3733 lhs = convert (rntype, lhs);
3734 ll_mask = convert (rntype, ll_mask);
3737 else if (lnbitsize < rnbitsize)
3739 rhs = convert (lntype, rhs);
3740 lr_mask = convert (lntype, lr_mask);
3745 if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
3746 lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3748 if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
3749 rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
3751 return build (wanted_code, truth_type, lhs, rhs);
3757 /* Handle the case of comparisons with constants. If there is something in
3758 common between the masks, those bits of the constants must be the same.
3759 If not, the condition is always false. Test for this to avoid generating
3760 incorrect code below. */
3761 result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3762 if (! integer_zerop (result)
3763 && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3764 const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3766 if (wanted_code == NE_EXPR)
3768 warning ("`or' of unmatched not-equal tests is always 1");
3769 return convert (truth_type, integer_one_node);
3773 warning ("`and' of mutually exclusive equal-tests is always 0");
3774 return convert (truth_type, integer_zero_node);
3778 /* Construct the expression we will return. First get the component
3779 reference we will make. Unless the mask is all ones the width of
3780 that field, perform the mask operation. Then compare with the
3782 result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3783 ll_unsignedp || rl_unsignedp);
3785 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3786 if (! all_ones_mask_p (ll_mask, lnbitsize))
3787 result = build (BIT_AND_EXPR, lntype, result, ll_mask);
3789 return build (wanted_code, truth_type, result,
3790 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3793 /* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
3797 optimize_minmax_comparison (t)
3800 tree type = TREE_TYPE (t);
3801 tree arg0 = TREE_OPERAND (t, 0);
3802 enum tree_code op_code;
3803 tree comp_const = TREE_OPERAND (t, 1);
3805 int consts_equal, consts_lt;
3808 STRIP_SIGN_NOPS (arg0);
3810 op_code = TREE_CODE (arg0);
3811 minmax_const = TREE_OPERAND (arg0, 1);
3812 consts_equal = tree_int_cst_equal (minmax_const, comp_const);
3813 consts_lt = tree_int_cst_lt (minmax_const, comp_const);
3814 inner = TREE_OPERAND (arg0, 0);
3816 /* If something does not permit us to optimize, return the original tree. */
3817 if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
3818 || TREE_CODE (comp_const) != INTEGER_CST
3819 || TREE_CONSTANT_OVERFLOW (comp_const)
3820 || TREE_CODE (minmax_const) != INTEGER_CST
3821 || TREE_CONSTANT_OVERFLOW (minmax_const))
3824 /* Now handle all the various comparison codes. We only handle EQ_EXPR
3825 and GT_EXPR, doing the rest with recursive calls using logical
3827 switch (TREE_CODE (t))
3829 case NE_EXPR: case LT_EXPR: case LE_EXPR:
3831 invert_truthvalue (optimize_minmax_comparison (invert_truthvalue (t)));
3835 fold (build (TRUTH_ORIF_EXPR, type,
3836 optimize_minmax_comparison
3837 (build (EQ_EXPR, type, arg0, comp_const)),
3838 optimize_minmax_comparison
3839 (build (GT_EXPR, type, arg0, comp_const))));
3842 if (op_code == MAX_EXPR && consts_equal)
3843 /* MAX (X, 0) == 0 -> X <= 0 */
3844 return fold (build (LE_EXPR, type, inner, comp_const));
3846 else if (op_code == MAX_EXPR && consts_lt)
3847 /* MAX (X, 0) == 5 -> X == 5 */
3848 return fold (build (EQ_EXPR, type, inner, comp_const));
3850 else if (op_code == MAX_EXPR)
3851 /* MAX (X, 0) == -1 -> false */
3852 return omit_one_operand (type, integer_zero_node, inner);
3854 else if (consts_equal)
3855 /* MIN (X, 0) == 0 -> X >= 0 */
3856 return fold (build (GE_EXPR, type, inner, comp_const));
3859 /* MIN (X, 0) == 5 -> false */
3860 return omit_one_operand (type, integer_zero_node, inner);
3863 /* MIN (X, 0) == -1 -> X == -1 */
3864 return fold (build (EQ_EXPR, type, inner, comp_const));
3867 if (op_code == MAX_EXPR && (consts_equal || consts_lt))
3868 /* MAX (X, 0) > 0 -> X > 0
3869 MAX (X, 0) > 5 -> X > 5 */
3870 return fold (build (GT_EXPR, type, inner, comp_const));
3872 else if (op_code == MAX_EXPR)
3873 /* MAX (X, 0) > -1 -> true */
3874 return omit_one_operand (type, integer_one_node, inner);
3876 else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
3877 /* MIN (X, 0) > 0 -> false
3878 MIN (X, 0) > 5 -> false */
3879 return omit_one_operand (type, integer_zero_node, inner);
3882 /* MIN (X, 0) > -1 -> X > -1 */
3883 return fold (build (GT_EXPR, type, inner, comp_const));
3890 /* T is an integer expression that is being multiplied, divided, or taken a
3891 modulus (CODE says which and what kind of divide or modulus) by a
3892 constant C. See if we can eliminate that operation by folding it with
3893 other operations already in T. WIDE_TYPE, if non-null, is a type that
3894 should be used for the computation if wider than our type.
3896 For example, if we are dividing (X * 8) + (Y * 16) by 4, we can return
3897 (X * 2) + (Y * 4). We must, however, be assured that either the original
3898 expression would not overflow or that overflow is undefined for the type
3899 in the language in question.
3901 We also canonicalize (X + 7) * 4 into X * 4 + 28 in the hope that either
3902 the machine has a multiply-accumulate insn or that this is part of an
3903 addressing calculation.
3905 If we return a non-null expression, it is an equivalent form of the
3906 original computation, but need not be in the original type. */
3909 extract_muldiv (t, c, code, wide_type)
3912 enum tree_code code;
3915 tree type = TREE_TYPE (t);
3916 enum tree_code tcode = TREE_CODE (t);
3917 tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type))
3918 > GET_MODE_SIZE (TYPE_MODE (type)))
3919 ? wide_type : type);
3921 int same_p = tcode == code;
3922 tree op0 = NULL_TREE, op1 = NULL_TREE;
3924 /* Don't deal with constants of zero here; they confuse the code below. */
3925 if (integer_zerop (c))
3928 if (TREE_CODE_CLASS (tcode) == '1')
3929 op0 = TREE_OPERAND (t, 0);
3931 if (TREE_CODE_CLASS (tcode) == '2')
3932 op0 = TREE_OPERAND (t, 0), op1 = TREE_OPERAND (t, 1);
3934 /* Note that we need not handle conditional operations here since fold
3935 already handles those cases. So just do arithmetic here. */
3939 /* For a constant, we can always simplify if we are a multiply
3940 or (for divide and modulus) if it is a multiple of our constant. */
3941 if (code == MULT_EXPR
3942 || integer_zerop (const_binop (TRUNC_MOD_EXPR, t, c, 0)))
3943 return const_binop (code, convert (ctype, t), convert (ctype, c), 0);
3946 case CONVERT_EXPR: case NON_LVALUE_EXPR: case NOP_EXPR:
3947 /* If op0 is an expression, and is unsigned, and the type is
3948 smaller than ctype, then we cannot widen the expression. */
3949 if ((TREE_CODE_CLASS (TREE_CODE (op0)) == '<'
3950 || TREE_CODE_CLASS (TREE_CODE (op0)) == '1'
3951 || TREE_CODE_CLASS (TREE_CODE (op0)) == '2'
3952 || TREE_CODE_CLASS (TREE_CODE (op0)) == 'e')
3953 && TREE_UNSIGNED (TREE_TYPE (op0))
3954 && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3955 && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
3956 && (GET_MODE_SIZE (TYPE_MODE (ctype))
3957 > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
3960 /* Pass the constant down and see if we can make a simplification. If
3961 we can, replace this expression with the inner simplification for
3962 possible later conversion to our or some other type. */
3963 if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
3964 code == MULT_EXPR ? ctype : NULL_TREE)))
3968 case NEGATE_EXPR: case ABS_EXPR:
3969 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
3970 return fold (build1 (tcode, ctype, convert (ctype, t1)));
3973 case MIN_EXPR: case MAX_EXPR:
3974 /* If widening the type changes the signedness, then we can't perform
3975 this optimization as that changes the result. */
3976 if (TREE_UNSIGNED (ctype) != TREE_UNSIGNED (type))
3979 /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
3980 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
3981 && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
3983 if (tree_int_cst_sgn (c) < 0)
3984 tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
3986 return fold (build (tcode, ctype, convert (ctype, t1),
3987 convert (ctype, t2)));
3991 case WITH_RECORD_EXPR:
3992 if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
3993 return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
3994 TREE_OPERAND (t, 1));
3998 /* If this has not been evaluated and the operand has no side effects,
3999 we can see if we can do something inside it and make a new one.
4000 Note that this test is overly conservative since we can do this
4001 if the only reason it had side effects is that it was another
4002 similar SAVE_EXPR, but that isn't worth bothering with. */
4003 if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
4004 && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
4007 t1 = save_expr (t1);
4008 if (SAVE_EXPR_PERSISTENT_P (t) && TREE_CODE (t1) == SAVE_EXPR)
4009 SAVE_EXPR_PERSISTENT_P (t1) = 1;
4010 if (is_pending_size (t))
4011 put_pending_size (t1);
4016 case LSHIFT_EXPR: case RSHIFT_EXPR:
4017 /* If the second operand is constant, this is a multiplication
4018 or floor division, by a power of two, so we can treat it that
4019 way unless the multiplier or divisor overflows. */
4020 if (TREE_CODE (op1) == INTEGER_CST
4021 /* const_binop may not detect overflow correctly,
4022 so check for it explicitly here. */
4023 && TYPE_PRECISION (TREE_TYPE (size_one_node)) > TREE_INT_CST_LOW (op1)
4024 && TREE_INT_CST_HIGH (op1) == 0
4025 && 0 != (t1 = convert (ctype,
4026 const_binop (LSHIFT_EXPR, size_one_node,
4028 && ! TREE_OVERFLOW (t1))
4029 return extract_muldiv (build (tcode == LSHIFT_EXPR
4030 ? MULT_EXPR : FLOOR_DIV_EXPR,
4031 ctype, convert (ctype, op0), t1),
4032 c, code, wide_type);
4035 case PLUS_EXPR: case MINUS_EXPR:
4036 /* See if we can eliminate the operation on both sides. If we can, we
4037 can return a new PLUS or MINUS. If we can't, the only remaining
4038 cases where we can do anything are if the second operand is a
4040 t1 = extract_muldiv (op0, c, code, wide_type);
4041 t2 = extract_muldiv (op1, c, code, wide_type);
4042 if (t1 != 0 && t2 != 0
4043 && (code == MULT_EXPR
4044 /* If not multiplication, we can only do this if either operand
4045 is divisible by c. */
4046 || multiple_of_p (ctype, op0, c)
4047 || multiple_of_p (ctype, op1, c)))
4048 return fold (build (tcode, ctype, convert (ctype, t1),
4049 convert (ctype, t2)));
4051 /* If this was a subtraction, negate OP1 and set it to be an addition.
4052 This simplifies the logic below. */
4053 if (tcode == MINUS_EXPR)
4054 tcode = PLUS_EXPR, op1 = negate_expr (op1);
4056 if (TREE_CODE (op1) != INTEGER_CST)
4059 /* If either OP1 or C are negative, this optimization is not safe for
4060 some of the division and remainder types while for others we need
4061 to change the code. */
4062 if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
4064 if (code == CEIL_DIV_EXPR)
4065 code = FLOOR_DIV_EXPR;
4066 else if (code == FLOOR_DIV_EXPR)
4067 code = CEIL_DIV_EXPR;
4068 else if (code != MULT_EXPR
4069 && code != CEIL_MOD_EXPR && code != FLOOR_MOD_EXPR)
4073 /* If it's a multiply or a division/modulus operation of a multiple
4074 of our constant, do the operation and verify it doesn't overflow. */
4075 if (code == MULT_EXPR
4076 || integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4078 op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
4079 if (op1 == 0 || TREE_OVERFLOW (op1))
4085 /* If we have an unsigned type is not a sizetype, we cannot widen
4086 the operation since it will change the result if the original
4087 computation overflowed. */
4088 if (TREE_UNSIGNED (ctype)
4089 && ! (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))
4093 /* If we were able to eliminate our operation from the first side,
4094 apply our operation to the second side and reform the PLUS. */
4095 if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
4096 return fold (build (tcode, ctype, convert (ctype, t1), op1));
4098 /* The last case is if we are a multiply. In that case, we can
4099 apply the distributive law to commute the multiply and addition
4100 if the multiplication of the constants doesn't overflow. */
4101 if (code == MULT_EXPR)
4102 return fold (build (tcode, ctype, fold (build (code, ctype,
4103 convert (ctype, op0),
4104 convert (ctype, c))),
4110 /* We have a special case here if we are doing something like
4111 (C * 8) % 4 since we know that's zero. */
4112 if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
4113 || code == FLOOR_MOD_EXPR || code == ROUND_MOD_EXPR)
4114 && TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
4115 && integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4116 return omit_one_operand (type, integer_zero_node, op0);
4118 /* ... fall through ... */
4120 case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR:
4121 case ROUND_DIV_EXPR: case EXACT_DIV_EXPR:
4122 /* If we can extract our operation from the LHS, do so and return a
4123 new operation. Likewise for the RHS from a MULT_EXPR. Otherwise,
4124 do something only if the second operand is a constant. */
4126 && (t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4127 return fold (build (tcode, ctype, convert (ctype, t1),
4128 convert (ctype, op1)));
4129 else if (tcode == MULT_EXPR && code == MULT_EXPR
4130 && (t1 = extract_muldiv (op1, c, code, wide_type)) != 0)
4131 return fold (build (tcode, ctype, convert (ctype, op0),
4132 convert (ctype, t1)));
4133 else if (TREE_CODE (op1) != INTEGER_CST)
4136 /* If these are the same operation types, we can associate them
4137 assuming no overflow. */
4139 && 0 != (t1 = const_binop (MULT_EXPR, convert (ctype, op1),
4140 convert (ctype, c), 0))
4141 && ! TREE_OVERFLOW (t1))
4142 return fold (build (tcode, ctype, convert (ctype, op0), t1));
4144 /* If these operations "cancel" each other, we have the main
4145 optimizations of this pass, which occur when either constant is a
4146 multiple of the other, in which case we replace this with either an
4147 operation or CODE or TCODE.
4149 If we have an unsigned type that is not a sizetype, we cannot do
4150 this since it will change the result if the original computation
4152 if ((! TREE_UNSIGNED (ctype)
4153 || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
4154 && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR)
4155 || (tcode == MULT_EXPR
4156 && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR
4157 && code != FLOOR_MOD_EXPR && code != ROUND_MOD_EXPR)))
4159 if (integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4160 return fold (build (tcode, ctype, convert (ctype, op0),
4162 const_binop (TRUNC_DIV_EXPR,
4164 else if (integer_zerop (const_binop (TRUNC_MOD_EXPR, c, op1, 0)))
4165 return fold (build (code, ctype, convert (ctype, op0),
4167 const_binop (TRUNC_DIV_EXPR,
4179 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4180 S, a SAVE_EXPR, return the expression actually being evaluated. Note
4181 that we may sometimes modify the tree. */
4184 strip_compound_expr (t, s)
4188 enum tree_code code = TREE_CODE (t);
4190 /* See if this is the COMPOUND_EXPR we want to eliminate. */
4191 if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4192 && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4193 return TREE_OPERAND (t, 1);
4195 /* See if this is a COND_EXPR or a simple arithmetic operator. We
4196 don't bother handling any other types. */
4197 else if (code == COND_EXPR)
4199 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4200 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4201 TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4203 else if (TREE_CODE_CLASS (code) == '1')
4204 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4205 else if (TREE_CODE_CLASS (code) == '<'
4206 || TREE_CODE_CLASS (code) == '2')
4208 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4209 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4215 /* Return a node which has the indicated constant VALUE (either 0 or
4216 1), and is of the indicated TYPE. */
4219 constant_boolean_node (value, type)
4223 if (type == integer_type_node)
4224 return value ? integer_one_node : integer_zero_node;
4225 else if (TREE_CODE (type) == BOOLEAN_TYPE)
4226 return (*lang_hooks.truthvalue_conversion) (value ? integer_one_node :
4230 tree t = build_int_2 (value, 0);
4232 TREE_TYPE (t) = type;
4237 /* Utility function for the following routine, to see how complex a nesting of
4238 COND_EXPRs can be. EXPR is the expression and LIMIT is a count beyond which
4239 we don't care (to avoid spending too much time on complex expressions.). */
4242 count_cond (expr, lim)
4248 if (TREE_CODE (expr) != COND_EXPR)
4253 ctrue = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4254 cfalse = count_cond (TREE_OPERAND (expr, 2), lim - 1 - ctrue);
4255 return MIN (lim, 1 + ctrue + cfalse);
4258 /* Transform `a + (b ? x : y)' into `b ? (a + x) : (a + y)'.
4259 Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
4260 CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
4261 expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
4262 COND is the first argument to CODE; otherwise (as in the example
4263 given here), it is the second argument. TYPE is the type of the
4264 original expression. */
4267 fold_binary_op_with_conditional_arg (code, type, cond, arg, cond_first_p)
4268 enum tree_code code;
4274 tree test, true_value, false_value;
4275 tree lhs = NULL_TREE;
4276 tree rhs = NULL_TREE;
4277 /* In the end, we'll produce a COND_EXPR. Both arms of the
4278 conditional expression will be binary operations. The left-hand
4279 side of the expression to be executed if the condition is true
4280 will be pointed to by TRUE_LHS. Similarly, the right-hand side
4281 of the expression to be executed if the condition is true will be
4282 pointed to by TRUE_RHS. FALSE_LHS and FALSE_RHS are analogous --
4283 but apply to the expression to be executed if the conditional is
4289 /* These are the codes to use for the left-hand side and right-hand
4290 side of the COND_EXPR. Normally, they are the same as CODE. */
4291 enum tree_code lhs_code = code;
4292 enum tree_code rhs_code = code;
4293 /* And these are the types of the expressions. */
4294 tree lhs_type = type;
4295 tree rhs_type = type;
4299 true_rhs = false_rhs = &arg;
4300 true_lhs = &true_value;
4301 false_lhs = &false_value;
4305 true_lhs = false_lhs = &arg;
4306 true_rhs = &true_value;
4307 false_rhs = &false_value;
4310 if (TREE_CODE (cond) == COND_EXPR)
4312 test = TREE_OPERAND (cond, 0);
4313 true_value = TREE_OPERAND (cond, 1);
4314 false_value = TREE_OPERAND (cond, 2);
4315 /* If this operand throws an expression, then it does not make
4316 sense to try to perform a logical or arithmetic operation
4317 involving it. Instead of building `a + throw 3' for example,
4318 we simply build `a, throw 3'. */
4319 if (VOID_TYPE_P (TREE_TYPE (true_value)))
4321 lhs_code = COMPOUND_EXPR;
4323 lhs_type = void_type_node;
4325 if (VOID_TYPE_P (TREE_TYPE (false_value)))
4327 rhs_code = COMPOUND_EXPR;
4329 rhs_type = void_type_node;
4334 tree testtype = TREE_TYPE (cond);
4336 true_value = convert (testtype, integer_one_node);
4337 false_value = convert (testtype, integer_zero_node);
4340 /* If ARG is complex we want to make sure we only evaluate
4341 it once. Though this is only required if it is volatile, it
4342 might be more efficient even if it is not. However, if we
4343 succeed in folding one part to a constant, we do not need
4344 to make this SAVE_EXPR. Since we do this optimization
4345 primarily to see if we do end up with constant and this
4346 SAVE_EXPR interferes with later optimizations, suppressing
4347 it when we can is important.
4349 If we are not in a function, we can't make a SAVE_EXPR, so don't
4350 try to do so. Don't try to see if the result is a constant
4351 if an arm is a COND_EXPR since we get exponential behavior
4354 if (TREE_CODE (arg) != SAVE_EXPR && ! TREE_CONSTANT (arg)
4355 && (*lang_hooks.decls.global_bindings_p) () == 0
4356 && ((TREE_CODE (arg) != VAR_DECL
4357 && TREE_CODE (arg) != PARM_DECL)
4358 || TREE_SIDE_EFFECTS (arg)))
4360 if (TREE_CODE (true_value) != COND_EXPR)
4361 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4363 if (TREE_CODE (false_value) != COND_EXPR)
4364 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4366 if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4367 && (rhs == 0 || !TREE_CONSTANT (rhs)))
4368 arg = save_expr (arg), lhs = rhs = 0;
4372 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4374 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4376 test = fold (build (COND_EXPR, type, test, lhs, rhs));
4378 if (TREE_CODE (arg) == SAVE_EXPR)
4379 return build (COMPOUND_EXPR, type,
4380 convert (void_type_node, arg),
4381 strip_compound_expr (test, arg));
4383 return convert (type, test);
4387 /* Subroutine of fold() that checks for the addition of +/- 0.0.
4389 If !NEGATE, return true if ADDEND is +/-0.0 and, for all X of type
4390 TYPE, X + ADDEND is the same as X. If NEGATE, return true if X -
4391 ADDEND is the same as X.
4393 X + 0 and X - 0 both give X when X is NaN, infinite, or non-zero
4394 and finite. The problematic cases are when X is zero, and its mode
4395 has signed zeros. In the case of rounding towards -infinity,
4396 X - 0 is not the same as X because 0 - 0 is -0. In other rounding
4397 modes, X + 0 is not the same as X because -0 + 0 is 0. */
4400 fold_real_zero_addition_p (type, addend, negate)
4404 if (!real_zerop (addend))
4407 /* Allow the fold if zeros aren't signed, or their sign isn't important. */
4408 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
4411 /* Treat x + -0 as x - 0 and x - -0 as x + 0. */
4412 if (TREE_CODE (addend) == REAL_CST
4413 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (addend)))
4416 /* The mode has signed zeros, and we have to honor their sign.
4417 In this situation, there is only one case we can return true for.
4418 X - 0 is the same as X unless rounding towards -infinity is
4420 return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
4424 /* Perform constant folding and related simplification of EXPR.
4425 The related simplifications include x*1 => x, x*0 => 0, etc.,
4426 and application of the associative law.
4427 NOP_EXPR conversions may be removed freely (as long as we
4428 are careful not to change the C type of the overall expression)
4429 We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4430 but we can constant-fold them if they have constant operands. */
4437 tree t1 = NULL_TREE;
4439 tree type = TREE_TYPE (expr);
4440 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4441 enum tree_code code = TREE_CODE (t);
4442 int kind = TREE_CODE_CLASS (code);
4444 /* WINS will be nonzero when the switch is done
4445 if all operands are constant. */
4448 /* Don't try to process an RTL_EXPR since its operands aren't trees.
4449 Likewise for a SAVE_EXPR that's already been evaluated. */
4450 if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t) != 0))
4453 /* Return right away if a constant. */
4457 #ifdef MAX_INTEGER_COMPUTATION_MODE
4458 check_max_integer_computation_mode (expr);
4461 if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4465 /* Special case for conversion ops that can have fixed point args. */
4466 arg0 = TREE_OPERAND (t, 0);
4468 /* Don't use STRIP_NOPS, because signedness of argument type matters. */
4470 STRIP_SIGN_NOPS (arg0);
4472 if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4473 subop = TREE_REALPART (arg0);
4477 if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4478 && TREE_CODE (subop) != REAL_CST
4480 /* Note that TREE_CONSTANT isn't enough:
4481 static var addresses are constant but we can't
4482 do arithmetic on them. */
4485 else if (IS_EXPR_CODE_CLASS (kind) || kind == 'r')
4487 int len = first_rtl_op (code);
4489 for (i = 0; i < len; i++)
4491 tree op = TREE_OPERAND (t, i);
4495 continue; /* Valid for CALL_EXPR, at least. */
4497 if (kind == '<' || code == RSHIFT_EXPR)
4499 /* Signedness matters here. Perhaps we can refine this
4501 STRIP_SIGN_NOPS (op);
4504 /* Strip any conversions that don't change the mode. */
4507 if (TREE_CODE (op) == COMPLEX_CST)
4508 subop = TREE_REALPART (op);
4512 if (TREE_CODE (subop) != INTEGER_CST
4513 && TREE_CODE (subop) != REAL_CST)
4514 /* Note that TREE_CONSTANT isn't enough:
4515 static var addresses are constant but we can't
4516 do arithmetic on them. */
4526 /* If this is a commutative operation, and ARG0 is a constant, move it
4527 to ARG1 to reduce the number of tests below. */
4528 if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4529 || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4530 || code == BIT_AND_EXPR)
4531 && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4533 tem = arg0; arg0 = arg1; arg1 = tem;
4535 tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4536 TREE_OPERAND (t, 1) = tem;
4539 /* Now WINS is set as described above,
4540 ARG0 is the first operand of EXPR,
4541 and ARG1 is the second operand (if it has more than one operand).
4543 First check for cases where an arithmetic operation is applied to a
4544 compound, conditional, or comparison operation. Push the arithmetic
4545 operation inside the compound or conditional to see if any folding
4546 can then be done. Convert comparison to conditional for this purpose.
4547 The also optimizes non-constant cases that used to be done in
4550 Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
4551 one of the operands is a comparison and the other is a comparison, a
4552 BIT_AND_EXPR with the constant 1, or a truth value. In that case, the
4553 code below would make the expression more complex. Change it to a
4554 TRUTH_{AND,OR}_EXPR. Likewise, convert a similar NE_EXPR to
4555 TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR. */
4557 if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4558 || code == EQ_EXPR || code == NE_EXPR)
4559 && ((truth_value_p (TREE_CODE (arg0))
4560 && (truth_value_p (TREE_CODE (arg1))
4561 || (TREE_CODE (arg1) == BIT_AND_EXPR
4562 && integer_onep (TREE_OPERAND (arg1, 1)))))
4563 || (truth_value_p (TREE_CODE (arg1))
4564 && (truth_value_p (TREE_CODE (arg0))
4565 || (TREE_CODE (arg0) == BIT_AND_EXPR
4566 && integer_onep (TREE_OPERAND (arg0, 1)))))))
4568 t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4569 : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4573 if (code == EQ_EXPR)
4574 t = invert_truthvalue (t);
4579 if (TREE_CODE_CLASS (code) == '1')
4581 if (TREE_CODE (arg0) == COMPOUND_EXPR)
4582 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4583 fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4584 else if (TREE_CODE (arg0) == COND_EXPR)
4586 t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4587 fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4588 fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4590 /* If this was a conversion, and all we did was to move into
4591 inside the COND_EXPR, bring it back out. But leave it if
4592 it is a conversion from integer to integer and the
4593 result precision is no wider than a word since such a
4594 conversion is cheap and may be optimized away by combine,
4595 while it couldn't if it were outside the COND_EXPR. Then return
4596 so we don't get into an infinite recursion loop taking the
4597 conversion out and then back in. */
4599 if ((code == NOP_EXPR || code == CONVERT_EXPR
4600 || code == NON_LVALUE_EXPR)
4601 && TREE_CODE (t) == COND_EXPR
4602 && TREE_CODE (TREE_OPERAND (t, 1)) == code
4603 && TREE_CODE (TREE_OPERAND (t, 2)) == code
4604 && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4605 == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4606 && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4608 (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))))
4609 && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4610 t = build1 (code, type,
4612 TREE_TYPE (TREE_OPERAND
4613 (TREE_OPERAND (t, 1), 0)),
4614 TREE_OPERAND (t, 0),
4615 TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4616 TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4619 else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4620 return fold (build (COND_EXPR, type, arg0,
4621 fold (build1 (code, type, integer_one_node)),
4622 fold (build1 (code, type, integer_zero_node))));
4624 else if (TREE_CODE_CLASS (code) == '2'
4625 || TREE_CODE_CLASS (code) == '<')
4627 if (TREE_CODE (arg1) == COMPOUND_EXPR)
4628 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4629 fold (build (code, type,
4630 arg0, TREE_OPERAND (arg1, 1))));
4631 else if ((TREE_CODE (arg1) == COND_EXPR
4632 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4633 && TREE_CODE_CLASS (code) != '<'))
4634 && (TREE_CODE (arg0) != COND_EXPR
4635 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4636 && (! TREE_SIDE_EFFECTS (arg0)
4637 || ((*lang_hooks.decls.global_bindings_p) () == 0
4638 && ! contains_placeholder_p (arg0))))
4640 fold_binary_op_with_conditional_arg (code, type, arg1, arg0,
4641 /*cond_first_p=*/0);
4642 else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4643 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4644 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4645 else if ((TREE_CODE (arg0) == COND_EXPR
4646 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4647 && TREE_CODE_CLASS (code) != '<'))
4648 && (TREE_CODE (arg1) != COND_EXPR
4649 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4650 && (! TREE_SIDE_EFFECTS (arg1)
4651 || ((*lang_hooks.decls.global_bindings_p) () == 0
4652 && ! contains_placeholder_p (arg1))))
4654 fold_binary_op_with_conditional_arg (code, type, arg0, arg1,
4655 /*cond_first_p=*/1);
4657 else if (TREE_CODE_CLASS (code) == '<'
4658 && TREE_CODE (arg0) == COMPOUND_EXPR)
4659 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4660 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4661 else if (TREE_CODE_CLASS (code) == '<'
4662 && TREE_CODE (arg1) == COMPOUND_EXPR)
4663 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4664 fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4677 return fold (DECL_INITIAL (t));
4682 case FIX_TRUNC_EXPR:
4683 /* Other kinds of FIX are not handled properly by fold_convert. */
4685 if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4686 return TREE_OPERAND (t, 0);
4688 /* Handle cases of two conversions in a row. */
4689 if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4690 || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4692 tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4693 tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4694 tree final_type = TREE_TYPE (t);
4695 int inside_int = INTEGRAL_TYPE_P (inside_type);
4696 int inside_ptr = POINTER_TYPE_P (inside_type);
4697 int inside_float = FLOAT_TYPE_P (inside_type);
4698 unsigned int inside_prec = TYPE_PRECISION (inside_type);
4699 int inside_unsignedp = TREE_UNSIGNED (inside_type);
4700 int inter_int = INTEGRAL_TYPE_P (inter_type);
4701 int inter_ptr = POINTER_TYPE_P (inter_type);
4702 int inter_float = FLOAT_TYPE_P (inter_type);
4703 unsigned int inter_prec = TYPE_PRECISION (inter_type);
4704 int inter_unsignedp = TREE_UNSIGNED (inter_type);
4705 int final_int = INTEGRAL_TYPE_P (final_type);
4706 int final_ptr = POINTER_TYPE_P (final_type);
4707 int final_float = FLOAT_TYPE_P (final_type);
4708 unsigned int final_prec = TYPE_PRECISION (final_type);
4709 int final_unsignedp = TREE_UNSIGNED (final_type);
4711 /* In addition to the cases of two conversions in a row
4712 handled below, if we are converting something to its own
4713 type via an object of identical or wider precision, neither
4714 conversion is needed. */
4715 if (TYPE_MAIN_VARIANT (inside_type) == TYPE_MAIN_VARIANT (final_type)
4716 && ((inter_int && final_int) || (inter_float && final_float))
4717 && inter_prec >= final_prec)
4718 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4720 /* Likewise, if the intermediate and final types are either both
4721 float or both integer, we don't need the middle conversion if
4722 it is wider than the final type and doesn't change the signedness
4723 (for integers). Avoid this if the final type is a pointer
4724 since then we sometimes need the inner conversion. Likewise if
4725 the outer has a precision not equal to the size of its mode. */
4726 if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4727 || (inter_float && inside_float))
4728 && inter_prec >= inside_prec
4729 && (inter_float || inter_unsignedp == inside_unsignedp)
4730 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4731 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4733 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4735 /* If we have a sign-extension of a zero-extended value, we can
4736 replace that by a single zero-extension. */
4737 if (inside_int && inter_int && final_int
4738 && inside_prec < inter_prec && inter_prec < final_prec
4739 && inside_unsignedp && !inter_unsignedp)
4740 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4742 /* Two conversions in a row are not needed unless:
4743 - some conversion is floating-point (overstrict for now), or
4744 - the intermediate type is narrower than both initial and
4746 - the intermediate type and innermost type differ in signedness,
4747 and the outermost type is wider than the intermediate, or
4748 - the initial type is a pointer type and the precisions of the
4749 intermediate and final types differ, or
4750 - the final type is a pointer type and the precisions of the
4751 initial and intermediate types differ. */
4752 if (! inside_float && ! inter_float && ! final_float
4753 && (inter_prec > inside_prec || inter_prec > final_prec)
4754 && ! (inside_int && inter_int
4755 && inter_unsignedp != inside_unsignedp
4756 && inter_prec < final_prec)
4757 && ((inter_unsignedp && inter_prec > inside_prec)
4758 == (final_unsignedp && final_prec > inter_prec))
4759 && ! (inside_ptr && inter_prec != final_prec)
4760 && ! (final_ptr && inside_prec != inter_prec)
4761 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4762 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4764 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4767 if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4768 && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4769 /* Detect assigning a bitfield. */
4770 && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4771 && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4773 /* Don't leave an assignment inside a conversion
4774 unless assigning a bitfield. */
4775 tree prev = TREE_OPERAND (t, 0);
4776 TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4777 /* First do the assignment, then return converted constant. */
4778 t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4783 /* Convert (T)(x & c) into (T)x & (T)c, if c is an integer
4784 constants (if x has signed type, the sign bit cannot be set
4785 in c). This folds extension into the BIT_AND_EXPR. */
4786 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
4787 && TREE_CODE (TREE_TYPE (t)) != BOOLEAN_TYPE
4788 && TREE_CODE (TREE_OPERAND (t, 0)) == BIT_AND_EXPR
4789 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST)
4791 tree and = TREE_OPERAND (t, 0);
4792 tree and0 = TREE_OPERAND (and, 0), and1 = TREE_OPERAND (and, 1);
4795 if (TREE_UNSIGNED (TREE_TYPE (and))
4796 || (TYPE_PRECISION (TREE_TYPE (t))
4797 <= TYPE_PRECISION (TREE_TYPE (and))))
4799 else if (TYPE_PRECISION (TREE_TYPE (and1))
4800 <= HOST_BITS_PER_WIDE_INT
4801 && host_integerp (and1, 1))
4803 unsigned HOST_WIDE_INT cst;
4805 cst = tree_low_cst (and1, 1);
4806 cst &= (HOST_WIDE_INT) -1
4807 << (TYPE_PRECISION (TREE_TYPE (and1)) - 1);
4808 change = (cst == 0);
4809 #ifdef LOAD_EXTEND_OP
4811 && (LOAD_EXTEND_OP (TYPE_MODE (TREE_TYPE (and0)))
4814 tree uns = (*lang_hooks.types.unsigned_type) (TREE_TYPE (and0));
4815 and0 = convert (uns, and0);
4816 and1 = convert (uns, and1);
4821 return fold (build (BIT_AND_EXPR, TREE_TYPE (t),
4822 convert (TREE_TYPE (t), and0),
4823 convert (TREE_TYPE (t), and1)));
4828 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4831 return fold_convert (t, arg0);
4833 case VIEW_CONVERT_EXPR:
4834 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4835 return build1 (VIEW_CONVERT_EXPR, type,
4836 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4840 if (TREE_CODE (arg0) == CONSTRUCTOR)
4842 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4849 TREE_CONSTANT (t) = wins;
4855 if (TREE_CODE (arg0) == INTEGER_CST)
4857 unsigned HOST_WIDE_INT low;
4859 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4860 TREE_INT_CST_HIGH (arg0),
4862 t = build_int_2 (low, high);
4863 TREE_TYPE (t) = type;
4865 = (TREE_OVERFLOW (arg0)
4866 | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4867 TREE_CONSTANT_OVERFLOW (t)
4868 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4870 else if (TREE_CODE (arg0) == REAL_CST)
4871 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4873 else if (TREE_CODE (arg0) == NEGATE_EXPR)
4874 return TREE_OPERAND (arg0, 0);
4876 /* Convert - (a - b) to (b - a) for non-floating-point. */
4877 else if (TREE_CODE (arg0) == MINUS_EXPR
4878 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
4879 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4880 TREE_OPERAND (arg0, 0));
4887 if (TREE_CODE (arg0) == INTEGER_CST)
4889 /* If the value is unsigned, then the absolute value is
4890 the same as the ordinary value. */
4891 if (TREE_UNSIGNED (type))
4893 /* Similarly, if the value is non-negative. */
4894 else if (INT_CST_LT (integer_minus_one_node, arg0))
4896 /* If the value is negative, then the absolute value is
4900 unsigned HOST_WIDE_INT low;
4902 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4903 TREE_INT_CST_HIGH (arg0),
4905 t = build_int_2 (low, high);
4906 TREE_TYPE (t) = type;
4908 = (TREE_OVERFLOW (arg0)
4909 | force_fit_type (t, overflow));
4910 TREE_CONSTANT_OVERFLOW (t)
4911 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4914 else if (TREE_CODE (arg0) == REAL_CST)
4916 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4917 t = build_real (type,
4918 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4921 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4922 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4926 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4927 return convert (type, arg0);
4928 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4929 return build (COMPLEX_EXPR, type,
4930 TREE_OPERAND (arg0, 0),
4931 negate_expr (TREE_OPERAND (arg0, 1)));
4932 else if (TREE_CODE (arg0) == COMPLEX_CST)
4933 return build_complex (type, TREE_REALPART (arg0),
4934 negate_expr (TREE_IMAGPART (arg0)));
4935 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4936 return fold (build (TREE_CODE (arg0), type,
4937 fold (build1 (CONJ_EXPR, type,
4938 TREE_OPERAND (arg0, 0))),
4939 fold (build1 (CONJ_EXPR,
4940 type, TREE_OPERAND (arg0, 1)))));
4941 else if (TREE_CODE (arg0) == CONJ_EXPR)
4942 return TREE_OPERAND (arg0, 0);
4948 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4949 ~ TREE_INT_CST_HIGH (arg0));
4950 TREE_TYPE (t) = type;
4951 force_fit_type (t, 0);
4952 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4953 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4955 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4956 return TREE_OPERAND (arg0, 0);
4960 /* A + (-B) -> A - B */
4961 if (TREE_CODE (arg1) == NEGATE_EXPR)
4962 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4963 /* (-A) + B -> B - A */
4964 if (TREE_CODE (arg0) == NEGATE_EXPR)
4965 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
4966 else if (! FLOAT_TYPE_P (type))
4968 if (integer_zerop (arg1))
4969 return non_lvalue (convert (type, arg0));
4971 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4972 with a constant, and the two constants have no bits in common,
4973 we should treat this as a BIT_IOR_EXPR since this may produce more
4975 if (TREE_CODE (arg0) == BIT_AND_EXPR
4976 && TREE_CODE (arg1) == BIT_AND_EXPR
4977 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4978 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4979 && integer_zerop (const_binop (BIT_AND_EXPR,
4980 TREE_OPERAND (arg0, 1),
4981 TREE_OPERAND (arg1, 1), 0)))
4983 code = BIT_IOR_EXPR;
4987 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4988 (plus (plus (mult) (mult)) (foo)) so that we can
4989 take advantage of the factoring cases below. */
4990 if ((TREE_CODE (arg0) == PLUS_EXPR
4991 && TREE_CODE (arg1) == MULT_EXPR)
4992 || (TREE_CODE (arg1) == PLUS_EXPR
4993 && TREE_CODE (arg0) == MULT_EXPR))
4995 tree parg0, parg1, parg, marg;
4997 if (TREE_CODE (arg0) == PLUS_EXPR)
4998 parg = arg0, marg = arg1;
5000 parg = arg1, marg = arg0;
5001 parg0 = TREE_OPERAND (parg, 0);
5002 parg1 = TREE_OPERAND (parg, 1);
5006 if (TREE_CODE (parg0) == MULT_EXPR
5007 && TREE_CODE (parg1) != MULT_EXPR)
5008 return fold (build (PLUS_EXPR, type,
5009 fold (build (PLUS_EXPR, type, parg0, marg)),
5011 if (TREE_CODE (parg0) != MULT_EXPR
5012 && TREE_CODE (parg1) == MULT_EXPR)
5013 return fold (build (PLUS_EXPR, type,
5014 fold (build (PLUS_EXPR, type, parg1, marg)),
5018 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
5020 tree arg00, arg01, arg10, arg11;
5021 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
5023 /* (A * C) + (B * C) -> (A+B) * C.
5024 We are most concerned about the case where C is a constant,
5025 but other combinations show up during loop reduction. Since
5026 it is not difficult, try all four possibilities. */
5028 arg00 = TREE_OPERAND (arg0, 0);
5029 arg01 = TREE_OPERAND (arg0, 1);
5030 arg10 = TREE_OPERAND (arg1, 0);
5031 arg11 = TREE_OPERAND (arg1, 1);
5034 if (operand_equal_p (arg01, arg11, 0))
5035 same = arg01, alt0 = arg00, alt1 = arg10;
5036 else if (operand_equal_p (arg00, arg10, 0))
5037 same = arg00, alt0 = arg01, alt1 = arg11;
5038 else if (operand_equal_p (arg00, arg11, 0))
5039 same = arg00, alt0 = arg01, alt1 = arg10;
5040 else if (operand_equal_p (arg01, arg10, 0))
5041 same = arg01, alt0 = arg00, alt1 = arg11;
5043 /* No identical multiplicands; see if we can find a common
5044 power-of-two factor in non-power-of-two multiplies. This
5045 can help in multi-dimensional array access. */
5046 else if (TREE_CODE (arg01) == INTEGER_CST
5047 && TREE_CODE (arg11) == INTEGER_CST
5048 && TREE_INT_CST_HIGH (arg01) == 0
5049 && TREE_INT_CST_HIGH (arg11) == 0)
5051 HOST_WIDE_INT int01, int11, tmp;
5052 int01 = TREE_INT_CST_LOW (arg01);
5053 int11 = TREE_INT_CST_LOW (arg11);
5055 /* Move min of absolute values to int11. */
5056 if ((int01 >= 0 ? int01 : -int01)
5057 < (int11 >= 0 ? int11 : -int11))
5059 tmp = int01, int01 = int11, int11 = tmp;
5060 alt0 = arg00, arg00 = arg10, arg10 = alt0;
5061 alt0 = arg01, arg01 = arg11, arg11 = alt0;
5064 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
5066 alt0 = fold (build (MULT_EXPR, type, arg00,
5067 build_int_2 (int01 / int11, 0)));
5074 return fold (build (MULT_EXPR, type,
5075 fold (build (PLUS_EXPR, type, alt0, alt1)),
5080 /* See if ARG1 is zero and X + ARG1 reduces to X. */
5081 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
5082 return non_lvalue (convert (type, arg0));
5084 /* Likewise if the operands are reversed. */
5085 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5086 return non_lvalue (convert (type, arg1));
5089 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
5090 is a rotate of A by C1 bits. */
5091 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
5092 is a rotate of A by B bits. */
5094 enum tree_code code0, code1;
5095 code0 = TREE_CODE (arg0);
5096 code1 = TREE_CODE (arg1);
5097 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5098 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5099 && operand_equal_p (TREE_OPERAND (arg0, 0),
5100 TREE_OPERAND (arg1, 0), 0)
5101 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5103 tree tree01, tree11;
5104 enum tree_code code01, code11;
5106 tree01 = TREE_OPERAND (arg0, 1);
5107 tree11 = TREE_OPERAND (arg1, 1);
5108 STRIP_NOPS (tree01);
5109 STRIP_NOPS (tree11);
5110 code01 = TREE_CODE (tree01);
5111 code11 = TREE_CODE (tree11);
5112 if (code01 == INTEGER_CST
5113 && code11 == INTEGER_CST
5114 && TREE_INT_CST_HIGH (tree01) == 0
5115 && TREE_INT_CST_HIGH (tree11) == 0
5116 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5117 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5118 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5119 code0 == LSHIFT_EXPR ? tree01 : tree11);
5120 else if (code11 == MINUS_EXPR)
5122 tree tree110, tree111;
5123 tree110 = TREE_OPERAND (tree11, 0);
5124 tree111 = TREE_OPERAND (tree11, 1);
5125 STRIP_NOPS (tree110);
5126 STRIP_NOPS (tree111);
5127 if (TREE_CODE (tree110) == INTEGER_CST
5128 && 0 == compare_tree_int (tree110,
5130 (TREE_TYPE (TREE_OPERAND
5132 && operand_equal_p (tree01, tree111, 0))
5133 return build ((code0 == LSHIFT_EXPR
5136 type, TREE_OPERAND (arg0, 0), tree01);
5138 else if (code01 == MINUS_EXPR)
5140 tree tree010, tree011;
5141 tree010 = TREE_OPERAND (tree01, 0);
5142 tree011 = TREE_OPERAND (tree01, 1);
5143 STRIP_NOPS (tree010);
5144 STRIP_NOPS (tree011);
5145 if (TREE_CODE (tree010) == INTEGER_CST
5146 && 0 == compare_tree_int (tree010,
5148 (TREE_TYPE (TREE_OPERAND
5150 && operand_equal_p (tree11, tree011, 0))
5151 return build ((code0 != LSHIFT_EXPR
5154 type, TREE_OPERAND (arg0, 0), tree11);
5160 /* In most languages, can't associate operations on floats through
5161 parentheses. Rather than remember where the parentheses were, we
5162 don't associate floats at all. It shouldn't matter much. However,
5163 associating multiplications is only very slightly inaccurate, so do
5164 that if -funsafe-math-optimizations is specified. */
5167 && (! FLOAT_TYPE_P (type)
5168 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5170 tree var0, con0, lit0, minus_lit0;
5171 tree var1, con1, lit1, minus_lit1;
5173 /* Split both trees into variables, constants, and literals. Then
5174 associate each group together, the constants with literals,
5175 then the result with variables. This increases the chances of
5176 literals being recombined later and of generating relocatable
5177 expressions for the sum of a constant and literal. */
5178 var0 = split_tree (arg0, code, &con0, &lit0, &minus_lit0, 0);
5179 var1 = split_tree (arg1, code, &con1, &lit1, &minus_lit1,
5180 code == MINUS_EXPR);
5182 /* Only do something if we found more than two objects. Otherwise,
5183 nothing has changed and we risk infinite recursion. */
5184 if (2 < ((var0 != 0) + (var1 != 0)
5185 + (con0 != 0) + (con1 != 0)
5186 + (lit0 != 0) + (lit1 != 0)
5187 + (minus_lit0 != 0) + (minus_lit1 != 0)))
5189 /* Recombine MINUS_EXPR operands by using PLUS_EXPR. */
5190 if (code == MINUS_EXPR)
5193 var0 = associate_trees (var0, var1, code, type);
5194 con0 = associate_trees (con0, con1, code, type);
5195 lit0 = associate_trees (lit0, lit1, code, type);
5196 minus_lit0 = associate_trees (minus_lit0, minus_lit1, code, type);
5198 /* Preserve the MINUS_EXPR if the negative part of the literal is
5199 greater than the positive part. Otherwise, the multiplicative
5200 folding code (i.e extract_muldiv) may be fooled in case
5201 unsigned constants are substracted, like in the following
5202 example: ((X*2 + 4) - 8U)/2. */
5203 if (minus_lit0 && lit0)
5205 if (tree_int_cst_lt (lit0, minus_lit0))
5207 minus_lit0 = associate_trees (minus_lit0, lit0,
5213 lit0 = associate_trees (lit0, minus_lit0,
5221 return convert (type, associate_trees (var0, minus_lit0,
5225 con0 = associate_trees (con0, minus_lit0,
5227 return convert (type, associate_trees (var0, con0,
5232 con0 = associate_trees (con0, lit0, code, type);
5233 return convert (type, associate_trees (var0, con0, code, type));
5239 t1 = const_binop (code, arg0, arg1, 0);
5240 if (t1 != NULL_TREE)
5242 /* The return value should always have
5243 the same type as the original expression. */
5244 if (TREE_TYPE (t1) != TREE_TYPE (t))
5245 t1 = convert (TREE_TYPE (t), t1);
5252 /* A - (-B) -> A + B */
5253 if (TREE_CODE (arg1) == NEGATE_EXPR)
5254 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5255 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5256 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5258 fold (build (MINUS_EXPR, type,
5259 build_real (TREE_TYPE (arg1),
5260 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5261 TREE_OPERAND (arg0, 0)));
5263 if (! FLOAT_TYPE_P (type))
5265 if (! wins && integer_zerop (arg0))
5266 return negate_expr (convert (type, arg1));
5267 if (integer_zerop (arg1))
5268 return non_lvalue (convert (type, arg0));
5270 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5271 about the case where C is a constant, just try one of the
5272 four possibilities. */
5274 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5275 && operand_equal_p (TREE_OPERAND (arg0, 1),
5276 TREE_OPERAND (arg1, 1), 0))
5277 return fold (build (MULT_EXPR, type,
5278 fold (build (MINUS_EXPR, type,
5279 TREE_OPERAND (arg0, 0),
5280 TREE_OPERAND (arg1, 0))),
5281 TREE_OPERAND (arg0, 1)));
5284 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5285 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5286 return non_lvalue (convert (type, arg0));
5288 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5289 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5290 (-ARG1 + ARG0) reduces to -ARG1. */
5291 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5292 return negate_expr (convert (type, arg1));
5294 /* Fold &x - &x. This can happen from &x.foo - &x.
5295 This is unsafe for certain floats even in non-IEEE formats.
5296 In IEEE, it is unsafe because it does wrong for NaNs.
5297 Also note that operand_equal_p is always false if an operand
5300 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5301 && operand_equal_p (arg0, arg1, 0))
5302 return convert (type, integer_zero_node);
5307 /* (-A) * (-B) -> A * B */
5308 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5309 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5310 TREE_OPERAND (arg1, 0)));
5312 if (! FLOAT_TYPE_P (type))
5314 if (integer_zerop (arg1))
5315 return omit_one_operand (type, arg1, arg0);
5316 if (integer_onep (arg1))
5317 return non_lvalue (convert (type, arg0));
5319 /* (a * (1 << b)) is (a << b) */
5320 if (TREE_CODE (arg1) == LSHIFT_EXPR
5321 && integer_onep (TREE_OPERAND (arg1, 0)))
5322 return fold (build (LSHIFT_EXPR, type, arg0,
5323 TREE_OPERAND (arg1, 1)));
5324 if (TREE_CODE (arg0) == LSHIFT_EXPR
5325 && integer_onep (TREE_OPERAND (arg0, 0)))
5326 return fold (build (LSHIFT_EXPR, type, arg1,
5327 TREE_OPERAND (arg0, 1)));
5329 if (TREE_CODE (arg1) == INTEGER_CST
5330 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5332 return convert (type, tem);
5337 /* Maybe fold x * 0 to 0. The expressions aren't the same
5338 when x is NaN, since x * 0 is also NaN. Nor are they the
5339 same in modes with signed zeros, since multiplying a
5340 negative value by 0 gives -0, not +0. */
5341 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5342 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5343 && real_zerop (arg1))
5344 return omit_one_operand (type, arg1, arg0);
5345 /* In IEEE floating point, x*1 is not equivalent to x for snans.
5346 However, ANSI says we can drop signals,
5347 so we can do this anyway. */
5348 if (real_onep (arg1))
5349 return non_lvalue (convert (type, arg0));
5351 if (! wins && real_twop (arg1)
5352 && (*lang_hooks.decls.global_bindings_p) () == 0
5353 && ! contains_placeholder_p (arg0))
5355 tree arg = save_expr (arg0);
5356 return build (PLUS_EXPR, type, arg, arg);
5363 if (integer_all_onesp (arg1))
5364 return omit_one_operand (type, arg1, arg0);
5365 if (integer_zerop (arg1))
5366 return non_lvalue (convert (type, arg0));
5367 t1 = distribute_bit_expr (code, type, arg0, arg1);
5368 if (t1 != NULL_TREE)
5371 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5373 This results in more efficient code for machines without a NAND
5374 instruction. Combine will canonicalize to the first form
5375 which will allow use of NAND instructions provided by the
5376 backend if they exist. */
5377 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5378 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5380 return fold (build1 (BIT_NOT_EXPR, type,
5381 build (BIT_AND_EXPR, type,
5382 TREE_OPERAND (arg0, 0),
5383 TREE_OPERAND (arg1, 0))));
5386 /* See if this can be simplified into a rotate first. If that
5387 is unsuccessful continue in the association code. */
5391 if (integer_zerop (arg1))
5392 return non_lvalue (convert (type, arg0));
5393 if (integer_all_onesp (arg1))
5394 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5396 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5397 with a constant, and the two constants have no bits in common,
5398 we should treat this as a BIT_IOR_EXPR since this may produce more
5400 if (TREE_CODE (arg0) == BIT_AND_EXPR
5401 && TREE_CODE (arg1) == BIT_AND_EXPR
5402 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5403 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5404 && integer_zerop (const_binop (BIT_AND_EXPR,
5405 TREE_OPERAND (arg0, 1),
5406 TREE_OPERAND (arg1, 1), 0)))
5408 code = BIT_IOR_EXPR;
5412 /* See if this can be simplified into a rotate first. If that
5413 is unsuccessful continue in the association code. */
5418 if (integer_all_onesp (arg1))
5419 return non_lvalue (convert (type, arg0));
5420 if (integer_zerop (arg1))
5421 return omit_one_operand (type, arg1, arg0);
5422 t1 = distribute_bit_expr (code, type, arg0, arg1);
5423 if (t1 != NULL_TREE)
5425 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5426 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5427 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5430 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5432 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5433 && (~TREE_INT_CST_LOW (arg1)
5434 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5435 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5438 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5440 This results in more efficient code for machines without a NOR
5441 instruction. Combine will canonicalize to the first form
5442 which will allow use of NOR instructions provided by the
5443 backend if they exist. */
5444 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5445 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5447 return fold (build1 (BIT_NOT_EXPR, type,
5448 build (BIT_IOR_EXPR, type,
5449 TREE_OPERAND (arg0, 0),
5450 TREE_OPERAND (arg1, 0))));
5455 case BIT_ANDTC_EXPR:
5456 if (integer_all_onesp (arg0))
5457 return non_lvalue (convert (type, arg1));
5458 if (integer_zerop (arg0))
5459 return omit_one_operand (type, arg0, arg1);
5460 if (TREE_CODE (arg1) == INTEGER_CST)
5462 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5463 code = BIT_AND_EXPR;
5469 /* Don't touch a floating-point divide by zero unless the mode
5470 of the constant can represent infinity. */
5471 if (TREE_CODE (arg1) == REAL_CST
5472 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5473 && real_zerop (arg1))
5476 /* (-A) / (-B) -> A / B */
5477 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5478 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5479 TREE_OPERAND (arg1, 0)));
5481 /* In IEEE floating point, x/1 is not equivalent to x for snans.
5482 However, ANSI says we can drop signals, so we can do this anyway. */
5483 if (real_onep (arg1))
5484 return non_lvalue (convert (type, arg0));
5486 /* If ARG1 is a constant, we can convert this to a multiply by the
5487 reciprocal. This does not have the same rounding properties,
5488 so only do this if -funsafe-math-optimizations. We can actually
5489 always safely do it if ARG1 is a power of two, but it's hard to
5490 tell if it is or not in a portable manner. */
5491 if (TREE_CODE (arg1) == REAL_CST)
5493 if (flag_unsafe_math_optimizations
5494 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5496 return fold (build (MULT_EXPR, type, arg0, tem));
5497 /* Find the reciprocal if optimizing and the result is exact. */
5501 r = TREE_REAL_CST (arg1);
5502 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5504 tem = build_real (type, r);
5505 return fold (build (MULT_EXPR, type, arg0, tem));
5509 /* Convert A/B/C to A/(B*C). */
5510 if (flag_unsafe_math_optimizations
5511 && TREE_CODE (arg0) == RDIV_EXPR)
5513 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5514 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5517 /* Convert A/(B/C) to (A/B)*C. */
5518 if (flag_unsafe_math_optimizations
5519 && TREE_CODE (arg1) == RDIV_EXPR)
5521 return fold (build (MULT_EXPR, type,
5522 build (RDIV_EXPR, type, arg0,
5523 TREE_OPERAND (arg1, 0)),
5524 TREE_OPERAND (arg1, 1)));
5528 case TRUNC_DIV_EXPR:
5529 case ROUND_DIV_EXPR:
5530 case FLOOR_DIV_EXPR:
5532 case EXACT_DIV_EXPR:
5533 if (integer_onep (arg1))
5534 return non_lvalue (convert (type, arg0));
5535 if (integer_zerop (arg1))
5538 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5539 operation, EXACT_DIV_EXPR.
5541 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5542 At one time others generated faster code, it's not clear if they do
5543 after the last round to changes to the DIV code in expmed.c. */
5544 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5545 && multiple_of_p (type, arg0, arg1))
5546 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5548 if (TREE_CODE (arg1) == INTEGER_CST
5549 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5551 return convert (type, tem);
5556 case FLOOR_MOD_EXPR:
5557 case ROUND_MOD_EXPR:
5558 case TRUNC_MOD_EXPR:
5559 if (integer_onep (arg1))
5560 return omit_one_operand (type, integer_zero_node, arg0);
5561 if (integer_zerop (arg1))
5564 if (TREE_CODE (arg1) == INTEGER_CST
5565 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5567 return convert (type, tem);
5575 if (integer_zerop (arg1))
5576 return non_lvalue (convert (type, arg0));
5577 /* Since negative shift count is not well-defined,
5578 don't try to compute it in the compiler. */
5579 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5581 /* Rewrite an LROTATE_EXPR by a constant into an
5582 RROTATE_EXPR by a new constant. */
5583 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5585 TREE_SET_CODE (t, RROTATE_EXPR);
5586 code = RROTATE_EXPR;
5587 TREE_OPERAND (t, 1) = arg1
5590 convert (TREE_TYPE (arg1),
5591 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5593 if (tree_int_cst_sgn (arg1) < 0)
5597 /* If we have a rotate of a bit operation with the rotate count and
5598 the second operand of the bit operation both constant,
5599 permute the two operations. */
5600 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5601 && (TREE_CODE (arg0) == BIT_AND_EXPR
5602 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5603 || TREE_CODE (arg0) == BIT_IOR_EXPR
5604 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5605 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5606 return fold (build (TREE_CODE (arg0), type,
5607 fold (build (code, type,
5608 TREE_OPERAND (arg0, 0), arg1)),
5609 fold (build (code, type,
5610 TREE_OPERAND (arg0, 1), arg1))));
5612 /* Two consecutive rotates adding up to the width of the mode can
5614 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5615 && TREE_CODE (arg0) == RROTATE_EXPR
5616 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5617 && TREE_INT_CST_HIGH (arg1) == 0
5618 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5619 && ((TREE_INT_CST_LOW (arg1)
5620 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5621 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5622 return TREE_OPERAND (arg0, 0);
5627 if (operand_equal_p (arg0, arg1, 0))
5628 return omit_one_operand (type, arg0, arg1);
5629 if (INTEGRAL_TYPE_P (type)
5630 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5631 return omit_one_operand (type, arg1, arg0);
5635 if (operand_equal_p (arg0, arg1, 0))
5636 return omit_one_operand (type, arg0, arg1);
5637 if (INTEGRAL_TYPE_P (type)
5638 && TYPE_MAX_VALUE (type)
5639 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5640 return omit_one_operand (type, arg1, arg0);
5643 case TRUTH_NOT_EXPR:
5644 /* Note that the operand of this must be an int
5645 and its values must be 0 or 1.
5646 ("true" is a fixed value perhaps depending on the language,
5647 but we don't handle values other than 1 correctly yet.) */
5648 tem = invert_truthvalue (arg0);
5649 /* Avoid infinite recursion. */
5650 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5652 return convert (type, tem);
5654 case TRUTH_ANDIF_EXPR:
5655 /* Note that the operands of this must be ints
5656 and their values must be 0 or 1.
5657 ("true" is a fixed value perhaps depending on the language.) */
5658 /* If first arg is constant zero, return it. */
5659 if (integer_zerop (arg0))
5660 return convert (type, arg0);
5661 case TRUTH_AND_EXPR:
5662 /* If either arg is constant true, drop it. */
5663 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5664 return non_lvalue (convert (type, arg1));
5665 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5666 /* Preserve sequence points. */
5667 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5668 return non_lvalue (convert (type, arg0));
5669 /* If second arg is constant zero, result is zero, but first arg
5670 must be evaluated. */
5671 if (integer_zerop (arg1))
5672 return omit_one_operand (type, arg1, arg0);
5673 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5674 case will be handled here. */
5675 if (integer_zerop (arg0))
5676 return omit_one_operand (type, arg0, arg1);
5679 /* We only do these simplifications if we are optimizing. */
5683 /* Check for things like (A || B) && (A || C). We can convert this
5684 to A || (B && C). Note that either operator can be any of the four
5685 truth and/or operations and the transformation will still be
5686 valid. Also note that we only care about order for the
5687 ANDIF and ORIF operators. If B contains side effects, this
5688 might change the truth-value of A. */
5689 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5690 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5691 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5692 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5693 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5694 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5696 tree a00 = TREE_OPERAND (arg0, 0);
5697 tree a01 = TREE_OPERAND (arg0, 1);
5698 tree a10 = TREE_OPERAND (arg1, 0);
5699 tree a11 = TREE_OPERAND (arg1, 1);
5700 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5701 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5702 && (code == TRUTH_AND_EXPR
5703 || code == TRUTH_OR_EXPR));
5705 if (operand_equal_p (a00, a10, 0))
5706 return fold (build (TREE_CODE (arg0), type, a00,
5707 fold (build (code, type, a01, a11))));
5708 else if (commutative && operand_equal_p (a00, a11, 0))
5709 return fold (build (TREE_CODE (arg0), type, a00,
5710 fold (build (code, type, a01, a10))));
5711 else if (commutative && operand_equal_p (a01, a10, 0))
5712 return fold (build (TREE_CODE (arg0), type, a01,
5713 fold (build (code, type, a00, a11))));
5715 /* This case if tricky because we must either have commutative
5716 operators or else A10 must not have side-effects. */
5718 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5719 && operand_equal_p (a01, a11, 0))
5720 return fold (build (TREE_CODE (arg0), type,
5721 fold (build (code, type, a00, a10)),
5725 /* See if we can build a range comparison. */
5726 if (0 != (tem = fold_range_test (t)))
5729 /* Check for the possibility of merging component references. If our
5730 lhs is another similar operation, try to merge its rhs with our
5731 rhs. Then try to merge our lhs and rhs. */
5732 if (TREE_CODE (arg0) == code
5733 && 0 != (tem = fold_truthop (code, type,
5734 TREE_OPERAND (arg0, 1), arg1)))
5735 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5737 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5742 case TRUTH_ORIF_EXPR:
5743 /* Note that the operands of this must be ints
5744 and their values must be 0 or true.
5745 ("true" is a fixed value perhaps depending on the language.) */
5746 /* If first arg is constant true, return it. */
5747 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5748 return convert (type, arg0);
5750 /* If either arg is constant zero, drop it. */
5751 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5752 return non_lvalue (convert (type, arg1));
5753 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5754 /* Preserve sequence points. */
5755 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5756 return non_lvalue (convert (type, arg0));
5757 /* If second arg is constant true, result is true, but we must
5758 evaluate first arg. */
5759 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5760 return omit_one_operand (type, arg1, arg0);
5761 /* Likewise for first arg, but note this only occurs here for
5763 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5764 return omit_one_operand (type, arg0, arg1);
5767 case TRUTH_XOR_EXPR:
5768 /* If either arg is constant zero, drop it. */
5769 if (integer_zerop (arg0))
5770 return non_lvalue (convert (type, arg1));
5771 if (integer_zerop (arg1))
5772 return non_lvalue (convert (type, arg0));
5773 /* If either arg is constant true, this is a logical inversion. */
5774 if (integer_onep (arg0))
5775 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5776 if (integer_onep (arg1))
5777 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5786 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5788 /* (-a) CMP (-b) -> b CMP a */
5789 if (TREE_CODE (arg0) == NEGATE_EXPR
5790 && TREE_CODE (arg1) == NEGATE_EXPR)
5791 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5792 TREE_OPERAND (arg0, 0)));
5793 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5794 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5797 (swap_tree_comparison (code), type,
5798 TREE_OPERAND (arg0, 0),
5799 build_real (TREE_TYPE (arg1),
5800 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5801 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5802 /* a CMP (-0) -> a CMP 0 */
5803 if (TREE_CODE (arg1) == REAL_CST
5804 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5805 return fold (build (code, type, arg0,
5806 build_real (TREE_TYPE (arg1), dconst0)));
5809 /* If one arg is a constant integer, put it last. */
5810 if (TREE_CODE (arg0) == INTEGER_CST
5811 && TREE_CODE (arg1) != INTEGER_CST)
5813 TREE_OPERAND (t, 0) = arg1;
5814 TREE_OPERAND (t, 1) = arg0;
5815 arg0 = TREE_OPERAND (t, 0);
5816 arg1 = TREE_OPERAND (t, 1);
5817 code = swap_tree_comparison (code);
5818 TREE_SET_CODE (t, code);
5821 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5822 First, see if one arg is constant; find the constant arg
5823 and the other one. */
5825 tree constop = 0, varop = NULL_TREE;
5826 int constopnum = -1;
5828 if (TREE_CONSTANT (arg1))
5829 constopnum = 1, constop = arg1, varop = arg0;
5830 if (TREE_CONSTANT (arg0))
5831 constopnum = 0, constop = arg0, varop = arg1;
5833 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5835 /* This optimization is invalid for ordered comparisons
5836 if CONST+INCR overflows or if foo+incr might overflow.
5837 This optimization is invalid for floating point due to rounding.
5838 For pointer types we assume overflow doesn't happen. */
5839 if (POINTER_TYPE_P (TREE_TYPE (varop))
5840 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5841 && (code == EQ_EXPR || code == NE_EXPR)))
5844 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5845 constop, TREE_OPERAND (varop, 1)));
5847 /* Do not overwrite the current varop to be a preincrement,
5848 create a new node so that we won't confuse our caller who
5849 might create trees and throw them away, reusing the
5850 arguments that they passed to build. This shows up in
5851 the THEN or ELSE parts of ?: being postincrements. */
5852 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
5853 TREE_OPERAND (varop, 0),
5854 TREE_OPERAND (varop, 1));
5856 /* If VAROP is a reference to a bitfield, we must mask
5857 the constant by the width of the field. */
5858 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5859 && DECL_BIT_FIELD(TREE_OPERAND
5860 (TREE_OPERAND (varop, 0), 1)))
5863 = TREE_INT_CST_LOW (DECL_SIZE
5865 (TREE_OPERAND (varop, 0), 1)));
5866 tree mask, unsigned_type;
5867 unsigned int precision;
5868 tree folded_compare;
5870 /* First check whether the comparison would come out
5871 always the same. If we don't do that we would
5872 change the meaning with the masking. */
5873 if (constopnum == 0)
5874 folded_compare = fold (build (code, type, constop,
5875 TREE_OPERAND (varop, 0)));
5877 folded_compare = fold (build (code, type,
5878 TREE_OPERAND (varop, 0),
5880 if (integer_zerop (folded_compare)
5881 || integer_onep (folded_compare))
5882 return omit_one_operand (type, folded_compare, varop);
5884 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5885 precision = TYPE_PRECISION (unsigned_type);
5886 mask = build_int_2 (~0, ~0);
5887 TREE_TYPE (mask) = unsigned_type;
5888 force_fit_type (mask, 0);
5889 mask = const_binop (RSHIFT_EXPR, mask,
5890 size_int (precision - size), 0);
5891 newconst = fold (build (BIT_AND_EXPR,
5892 TREE_TYPE (varop), newconst,
5893 convert (TREE_TYPE (varop),
5897 t = build (code, type,
5898 (constopnum == 0) ? newconst : varop,
5899 (constopnum == 1) ? newconst : varop);
5903 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5905 if (POINTER_TYPE_P (TREE_TYPE (varop))
5906 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5907 && (code == EQ_EXPR || code == NE_EXPR)))
5910 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5911 constop, TREE_OPERAND (varop, 1)));
5913 /* Do not overwrite the current varop to be a predecrement,
5914 create a new node so that we won't confuse our caller who
5915 might create trees and throw them away, reusing the
5916 arguments that they passed to build. This shows up in
5917 the THEN or ELSE parts of ?: being postdecrements. */
5918 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
5919 TREE_OPERAND (varop, 0),
5920 TREE_OPERAND (varop, 1));
5922 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5923 && DECL_BIT_FIELD(TREE_OPERAND
5924 (TREE_OPERAND (varop, 0), 1)))
5927 = TREE_INT_CST_LOW (DECL_SIZE
5929 (TREE_OPERAND (varop, 0), 1)));
5930 tree mask, unsigned_type;
5931 unsigned int precision;
5932 tree folded_compare;
5934 if (constopnum == 0)
5935 folded_compare = fold (build (code, type, constop,
5936 TREE_OPERAND (varop, 0)));
5938 folded_compare = fold (build (code, type,
5939 TREE_OPERAND (varop, 0),
5941 if (integer_zerop (folded_compare)
5942 || integer_onep (folded_compare))
5943 return omit_one_operand (type, folded_compare, varop);
5945 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5946 precision = TYPE_PRECISION (unsigned_type);
5947 mask = build_int_2 (~0, ~0);
5948 TREE_TYPE (mask) = TREE_TYPE (varop);
5949 force_fit_type (mask, 0);
5950 mask = const_binop (RSHIFT_EXPR, mask,
5951 size_int (precision - size), 0);
5952 newconst = fold (build (BIT_AND_EXPR,
5953 TREE_TYPE (varop), newconst,
5954 convert (TREE_TYPE (varop),
5958 t = build (code, type,
5959 (constopnum == 0) ? newconst : varop,
5960 (constopnum == 1) ? newconst : varop);
5966 /* Comparisons with the highest or lowest possible integer of
5967 the specified size will have known values and an unsigned
5968 <= 0x7fffffff can be simplified. */
5970 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
5972 if (TREE_CODE (arg1) == INTEGER_CST
5973 && ! TREE_CONSTANT_OVERFLOW (arg1)
5974 && width <= HOST_BITS_PER_WIDE_INT
5975 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
5976 || POINTER_TYPE_P (TREE_TYPE (arg1))))
5978 if (TREE_INT_CST_HIGH (arg1) == 0
5979 && (TREE_INT_CST_LOW (arg1)
5980 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
5981 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
5982 switch (TREE_CODE (t))
5985 return omit_one_operand (type,
5986 convert (type, integer_zero_node),
5989 TREE_SET_CODE (t, EQ_EXPR);
5993 return omit_one_operand (type,
5994 convert (type, integer_one_node),
5997 TREE_SET_CODE (t, NE_EXPR);
6004 else if (TREE_INT_CST_HIGH (arg1) == -1
6005 && (TREE_INT_CST_LOW (arg1)
6006 == ((unsigned HOST_WIDE_INT) -1 << (width - 1)))
6007 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6008 switch (TREE_CODE (t))
6011 return omit_one_operand (type,
6012 convert (type, integer_zero_node),
6015 TREE_SET_CODE (t, EQ_EXPR);
6019 return omit_one_operand (type,
6020 convert (type, integer_one_node),
6023 TREE_SET_CODE (t, NE_EXPR);
6030 else if (TREE_INT_CST_HIGH (arg1) == 0
6031 && (TREE_INT_CST_LOW (arg1)
6032 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6033 && TREE_UNSIGNED (TREE_TYPE (arg1))
6034 /* signed_type does not work on pointer types. */
6035 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6037 if (TREE_CODE (t) == LE_EXPR || TREE_CODE (t) == GT_EXPR)
6040 st0 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg0));
6041 st1 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg1));
6043 (build (TREE_CODE (t) == LE_EXPR ? GE_EXPR: LT_EXPR,
6044 type, convert (st0, arg0),
6045 convert (st1, integer_zero_node)));
6048 else if (TREE_INT_CST_HIGH (arg1) == 0
6049 && (TREE_INT_CST_LOW (arg1)
6050 == ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1)
6051 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6052 switch (TREE_CODE (t))
6055 return omit_one_operand (type,
6056 convert (type, integer_zero_node),
6059 TREE_SET_CODE (t, EQ_EXPR);
6063 return omit_one_operand (type,
6064 convert (type, integer_one_node),
6067 TREE_SET_CODE (t, NE_EXPR);
6076 /* Change X >= C to X > C-1 and X < C to X <= C-1 if C is positive. */
6077 if (TREE_CODE (arg1) == INTEGER_CST
6078 && TREE_CODE (arg0) != INTEGER_CST
6079 && tree_int_cst_sgn (arg1) > 0)
6081 switch (TREE_CODE (t))
6085 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6086 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6091 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
6092 t = build (code, type, TREE_OPERAND (t, 0), arg1);
6100 /* An unsigned comparison against 0 can be simplified. */
6101 if (integer_zerop (arg1)
6102 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6103 || POINTER_TYPE_P (TREE_TYPE (arg1)))
6104 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6106 switch (TREE_CODE (t))
6110 TREE_SET_CODE (t, NE_EXPR);
6114 TREE_SET_CODE (t, EQ_EXPR);
6117 return omit_one_operand (type,
6118 convert (type, integer_one_node),
6121 return omit_one_operand (type,
6122 convert (type, integer_zero_node),
6129 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
6130 a MINUS_EXPR of a constant, we can convert it into a comparison with
6131 a revised constant as long as no overflow occurs. */
6132 if ((code == EQ_EXPR || code == NE_EXPR)
6133 && TREE_CODE (arg1) == INTEGER_CST
6134 && (TREE_CODE (arg0) == PLUS_EXPR
6135 || TREE_CODE (arg0) == MINUS_EXPR)
6136 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6137 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
6138 ? MINUS_EXPR : PLUS_EXPR,
6139 arg1, TREE_OPERAND (arg0, 1), 0))
6140 && ! TREE_CONSTANT_OVERFLOW (tem))
6141 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6143 /* Similarly for a NEGATE_EXPR. */
6144 else if ((code == EQ_EXPR || code == NE_EXPR)
6145 && TREE_CODE (arg0) == NEGATE_EXPR
6146 && TREE_CODE (arg1) == INTEGER_CST
6147 && 0 != (tem = negate_expr (arg1))
6148 && TREE_CODE (tem) == INTEGER_CST
6149 && ! TREE_CONSTANT_OVERFLOW (tem))
6150 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
6152 /* If we have X - Y == 0, we can convert that to X == Y and similarly
6153 for !=. Don't do this for ordered comparisons due to overflow. */
6154 else if ((code == NE_EXPR || code == EQ_EXPR)
6155 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
6156 return fold (build (code, type,
6157 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
6159 /* If we are widening one operand of an integer comparison,
6160 see if the other operand is similarly being widened. Perhaps we
6161 can do the comparison in the narrower type. */
6162 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
6163 && TREE_CODE (arg0) == NOP_EXPR
6164 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
6165 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
6166 && (TREE_TYPE (t1) == TREE_TYPE (tem)
6167 || (TREE_CODE (t1) == INTEGER_CST
6168 && int_fits_type_p (t1, TREE_TYPE (tem)))))
6169 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
6171 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
6172 constant, we can simplify it. */
6173 else if (TREE_CODE (arg1) == INTEGER_CST
6174 && (TREE_CODE (arg0) == MIN_EXPR
6175 || TREE_CODE (arg0) == MAX_EXPR)
6176 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
6177 return optimize_minmax_comparison (t);
6179 /* If we are comparing an ABS_EXPR with a constant, we can
6180 convert all the cases into explicit comparisons, but they may
6181 well not be faster than doing the ABS and one comparison.
6182 But ABS (X) <= C is a range comparison, which becomes a subtraction
6183 and a comparison, and is probably faster. */
6184 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
6185 && TREE_CODE (arg0) == ABS_EXPR
6186 && ! TREE_SIDE_EFFECTS (arg0)
6187 && (0 != (tem = negate_expr (arg1)))
6188 && TREE_CODE (tem) == INTEGER_CST
6189 && ! TREE_CONSTANT_OVERFLOW (tem))
6190 return fold (build (TRUTH_ANDIF_EXPR, type,
6191 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
6192 build (LE_EXPR, type,
6193 TREE_OPERAND (arg0, 0), arg1)));
6195 /* If this is an EQ or NE comparison with zero and ARG0 is
6196 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
6197 two operations, but the latter can be done in one less insn
6198 on machines that have only two-operand insns or on which a
6199 constant cannot be the first operand. */
6200 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
6201 && TREE_CODE (arg0) == BIT_AND_EXPR)
6203 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
6204 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
6206 fold (build (code, type,
6207 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6209 TREE_TYPE (TREE_OPERAND (arg0, 0)),
6210 TREE_OPERAND (arg0, 1),
6211 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
6212 convert (TREE_TYPE (arg0),
6215 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
6216 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
6218 fold (build (code, type,
6219 build (BIT_AND_EXPR, TREE_TYPE (arg0),
6221 TREE_TYPE (TREE_OPERAND (arg0, 1)),
6222 TREE_OPERAND (arg0, 0),
6223 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
6224 convert (TREE_TYPE (arg0),
6229 /* If this is an NE or EQ comparison of zero against the result of a
6230 signed MOD operation whose second operand is a power of 2, make
6231 the MOD operation unsigned since it is simpler and equivalent. */
6232 if ((code == NE_EXPR || code == EQ_EXPR)
6233 && integer_zerop (arg1)
6234 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
6235 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
6236 || TREE_CODE (arg0) == CEIL_MOD_EXPR
6237 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
6238 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
6239 && integer_pow2p (TREE_OPERAND (arg0, 1)))
6241 tree newtype = (*lang_hooks.types.unsigned_type) (TREE_TYPE (arg0));
6242 tree newmod = build (TREE_CODE (arg0), newtype,
6243 convert (newtype, TREE_OPERAND (arg0, 0)),
6244 convert (newtype, TREE_OPERAND (arg0, 1)));
6246 return build (code, type, newmod, convert (newtype, arg1));
6249 /* If this is an NE comparison of zero with an AND of one, remove the
6250 comparison since the AND will give the correct value. */
6251 if (code == NE_EXPR && integer_zerop (arg1)
6252 && TREE_CODE (arg0) == BIT_AND_EXPR
6253 && integer_onep (TREE_OPERAND (arg0, 1)))
6254 return convert (type, arg0);
6256 /* If we have (A & C) == C where C is a power of 2, convert this into
6257 (A & C) != 0. Similarly for NE_EXPR. */
6258 if ((code == EQ_EXPR || code == NE_EXPR)
6259 && TREE_CODE (arg0) == BIT_AND_EXPR
6260 && integer_pow2p (TREE_OPERAND (arg0, 1))
6261 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
6262 return fold (build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
6263 arg0, integer_zero_node));
6265 /* If we have (A & C) != 0 where C is the sign bit of A, convert
6266 this into A < 0. Similarly for (A & C) == 0 into A >= 0. */
6267 if ((code == EQ_EXPR || code == NE_EXPR)
6268 && TREE_CODE (arg0) == BIT_AND_EXPR
6269 && integer_zerop (arg1))
6271 tree arg00 = sign_bit_p (TREE_OPERAND (arg0, 0),
6272 TREE_OPERAND (arg0, 1));
6273 if (arg00 != NULL_TREE)
6275 tree stype = (*lang_hooks.types.signed_type) (TREE_TYPE (arg00));
6276 return fold (build (code == EQ_EXPR ? GE_EXPR : LT_EXPR, type,
6277 convert (stype, arg00),
6278 convert (stype, integer_zero_node)));
6282 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
6283 and similarly for >= into !=. */
6284 if ((code == LT_EXPR || code == GE_EXPR)
6285 && TREE_UNSIGNED (TREE_TYPE (arg0))
6286 && TREE_CODE (arg1) == LSHIFT_EXPR
6287 && integer_onep (TREE_OPERAND (arg1, 0)))
6288 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6289 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6290 TREE_OPERAND (arg1, 1)),
6291 convert (TREE_TYPE (arg0), integer_zero_node));
6293 else if ((code == LT_EXPR || code == GE_EXPR)
6294 && TREE_UNSIGNED (TREE_TYPE (arg0))
6295 && (TREE_CODE (arg1) == NOP_EXPR
6296 || TREE_CODE (arg1) == CONVERT_EXPR)
6297 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
6298 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
6300 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6301 convert (TREE_TYPE (arg0),
6302 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6303 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
6304 convert (TREE_TYPE (arg0), integer_zero_node));
6306 /* Simplify comparison of something with itself. (For IEEE
6307 floating-point, we can only do some of these simplifications.) */
6308 if (operand_equal_p (arg0, arg1, 0))
6315 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
6316 return constant_boolean_node (1, type);
6318 TREE_SET_CODE (t, code);
6322 /* For NE, we can only do this simplification if integer. */
6323 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6325 /* ... fall through ... */
6328 return constant_boolean_node (0, type);
6334 /* If we are comparing an expression that just has comparisons
6335 of two integer values, arithmetic expressions of those comparisons,
6336 and constants, we can simplify it. There are only three cases
6337 to check: the two values can either be equal, the first can be
6338 greater, or the second can be greater. Fold the expression for
6339 those three values. Since each value must be 0 or 1, we have
6340 eight possibilities, each of which corresponds to the constant 0
6341 or 1 or one of the six possible comparisons.
6343 This handles common cases like (a > b) == 0 but also handles
6344 expressions like ((x > y) - (y > x)) > 0, which supposedly
6345 occur in macroized code. */
6347 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6349 tree cval1 = 0, cval2 = 0;
6352 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6353 /* Don't handle degenerate cases here; they should already
6354 have been handled anyway. */
6355 && cval1 != 0 && cval2 != 0
6356 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6357 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6358 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6359 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6360 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6361 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6362 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6364 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6365 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6367 /* We can't just pass T to eval_subst in case cval1 or cval2
6368 was the same as ARG1. */
6371 = fold (build (code, type,
6372 eval_subst (arg0, cval1, maxval, cval2, minval),
6375 = fold (build (code, type,
6376 eval_subst (arg0, cval1, maxval, cval2, maxval),
6379 = fold (build (code, type,
6380 eval_subst (arg0, cval1, minval, cval2, maxval),
6383 /* All three of these results should be 0 or 1. Confirm they
6384 are. Then use those values to select the proper code
6387 if ((integer_zerop (high_result)
6388 || integer_onep (high_result))
6389 && (integer_zerop (equal_result)
6390 || integer_onep (equal_result))
6391 && (integer_zerop (low_result)
6392 || integer_onep (low_result)))
6394 /* Make a 3-bit mask with the high-order bit being the
6395 value for `>', the next for '=', and the low for '<'. */
6396 switch ((integer_onep (high_result) * 4)
6397 + (integer_onep (equal_result) * 2)
6398 + integer_onep (low_result))
6402 return omit_one_operand (type, integer_zero_node, arg0);
6423 return omit_one_operand (type, integer_one_node, arg0);
6426 t = build (code, type, cval1, cval2);
6428 return save_expr (t);
6435 /* If this is a comparison of a field, we may be able to simplify it. */
6436 if ((TREE_CODE (arg0) == COMPONENT_REF
6437 || TREE_CODE (arg0) == BIT_FIELD_REF)
6438 && (code == EQ_EXPR || code == NE_EXPR)
6439 /* Handle the constant case even without -O
6440 to make sure the warnings are given. */
6441 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6443 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6447 /* If this is a comparison of complex values and either or both sides
6448 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6449 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6450 This may prevent needless evaluations. */
6451 if ((code == EQ_EXPR || code == NE_EXPR)
6452 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6453 && (TREE_CODE (arg0) == COMPLEX_EXPR
6454 || TREE_CODE (arg1) == COMPLEX_EXPR
6455 || TREE_CODE (arg0) == COMPLEX_CST
6456 || TREE_CODE (arg1) == COMPLEX_CST))
6458 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6459 tree real0, imag0, real1, imag1;
6461 arg0 = save_expr (arg0);
6462 arg1 = save_expr (arg1);
6463 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6464 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6465 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6466 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6468 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6471 fold (build (code, type, real0, real1)),
6472 fold (build (code, type, imag0, imag1))));
6475 /* Optimize comparisons of strlen vs zero to a compare of the
6476 first character of the string vs zero. To wit,
6477 strlen(ptr) == 0 => *ptr == 0
6478 strlen(ptr) != 0 => *ptr != 0
6479 Other cases should reduce to one of these two (or a constant)
6480 due to the return value of strlen being unsigned. */
6481 if ((code == EQ_EXPR || code == NE_EXPR)
6482 && integer_zerop (arg1)
6483 && TREE_CODE (arg0) == CALL_EXPR
6484 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6486 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6489 if (TREE_CODE (fndecl) == FUNCTION_DECL
6490 && DECL_BUILT_IN (fndecl)
6491 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6492 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6493 && (arglist = TREE_OPERAND (arg0, 1))
6494 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6495 && ! TREE_CHAIN (arglist))
6496 return fold (build (code, type,
6497 build1 (INDIRECT_REF, char_type_node,
6498 TREE_VALUE(arglist)),
6499 integer_zero_node));
6502 /* From here on, the only cases we handle are when the result is
6503 known to be a constant.
6505 To compute GT, swap the arguments and do LT.
6506 To compute GE, do LT and invert the result.
6507 To compute LE, swap the arguments, do LT and invert the result.
6508 To compute NE, do EQ and invert the result.
6510 Therefore, the code below must handle only EQ and LT. */
6512 if (code == LE_EXPR || code == GT_EXPR)
6514 tem = arg0, arg0 = arg1, arg1 = tem;
6515 code = swap_tree_comparison (code);
6518 /* Note that it is safe to invert for real values here because we
6519 will check below in the one case that it matters. */
6523 if (code == NE_EXPR || code == GE_EXPR)
6526 code = invert_tree_comparison (code);
6529 /* Compute a result for LT or EQ if args permit;
6530 otherwise return T. */
6531 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6533 if (code == EQ_EXPR)
6534 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6536 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6537 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6538 : INT_CST_LT (arg0, arg1)),
6542 #if 0 /* This is no longer useful, but breaks some real code. */
6543 /* Assume a nonexplicit constant cannot equal an explicit one,
6544 since such code would be undefined anyway.
6545 Exception: on sysvr4, using #pragma weak,
6546 a label can come out as 0. */
6547 else if (TREE_CODE (arg1) == INTEGER_CST
6548 && !integer_zerop (arg1)
6549 && TREE_CONSTANT (arg0)
6550 && TREE_CODE (arg0) == ADDR_EXPR
6552 t1 = build_int_2 (0, 0);
6554 /* Two real constants can be compared explicitly. */
6555 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6557 /* If either operand is a NaN, the result is false with two
6558 exceptions: First, an NE_EXPR is true on NaNs, but that case
6559 is already handled correctly since we will be inverting the
6560 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6561 or a GE_EXPR into a LT_EXPR, we must return true so that it
6562 will be inverted into false. */
6564 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6565 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6566 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6568 else if (code == EQ_EXPR)
6569 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6570 TREE_REAL_CST (arg1)),
6573 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6574 TREE_REAL_CST (arg1)),
6578 if (t1 == NULL_TREE)
6582 TREE_INT_CST_LOW (t1) ^= 1;
6584 TREE_TYPE (t1) = type;
6585 if (TREE_CODE (type) == BOOLEAN_TYPE)
6586 return (*lang_hooks.truthvalue_conversion) (t1);
6590 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6591 so all simple results must be passed through pedantic_non_lvalue. */
6592 if (TREE_CODE (arg0) == INTEGER_CST)
6593 return pedantic_non_lvalue
6594 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6595 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6596 return pedantic_omit_one_operand (type, arg1, arg0);
6598 /* If the second operand is zero, invert the comparison and swap
6599 the second and third operands. Likewise if the second operand
6600 is constant and the third is not or if the third operand is
6601 equivalent to the first operand of the comparison. */
6603 if (integer_zerop (arg1)
6604 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6605 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6606 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6607 TREE_OPERAND (t, 2),
6608 TREE_OPERAND (arg0, 1))))
6610 /* See if this can be inverted. If it can't, possibly because
6611 it was a floating-point inequality comparison, don't do
6613 tem = invert_truthvalue (arg0);
6615 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6617 t = build (code, type, tem,
6618 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6620 /* arg1 should be the first argument of the new T. */
6621 arg1 = TREE_OPERAND (t, 1);
6626 /* If we have A op B ? A : C, we may be able to convert this to a
6627 simpler expression, depending on the operation and the values
6628 of B and C. Signed zeros prevent all of these transformations,
6629 for reasons given above each one. */
6631 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6632 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6633 arg1, TREE_OPERAND (arg0, 1))
6634 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6636 tree arg2 = TREE_OPERAND (t, 2);
6637 enum tree_code comp_code = TREE_CODE (arg0);
6641 /* If we have A op 0 ? A : -A, consider applying the following
6644 A == 0? A : -A same as -A
6645 A != 0? A : -A same as A
6646 A >= 0? A : -A same as abs (A)
6647 A > 0? A : -A same as abs (A)
6648 A <= 0? A : -A same as -abs (A)
6649 A < 0? A : -A same as -abs (A)
6651 None of these transformations work for modes with signed
6652 zeros. If A is +/-0, the first two transformations will
6653 change the sign of the result (from +0 to -0, or vice
6654 versa). The last four will fix the sign of the result,
6655 even though the original expressions could be positive or
6656 negative, depending on the sign of A.
6658 Note that all these transformations are correct if A is
6659 NaN, since the two alternatives (A and -A) are also NaNs. */
6660 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6661 ? real_zerop (TREE_OPERAND (arg0, 1))
6662 : integer_zerop (TREE_OPERAND (arg0, 1)))
6663 && TREE_CODE (arg2) == NEGATE_EXPR
6664 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6672 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6675 return pedantic_non_lvalue (convert (type, arg1));
6678 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6679 arg1 = convert ((*lang_hooks.types.signed_type)
6680 (TREE_TYPE (arg1)), arg1);
6681 return pedantic_non_lvalue
6682 (convert (type, fold (build1 (ABS_EXPR,
6683 TREE_TYPE (arg1), arg1))));
6686 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6687 arg1 = convert ((lang_hooks.types.signed_type)
6688 (TREE_TYPE (arg1)), arg1);
6689 return pedantic_non_lvalue
6690 (negate_expr (convert (type,
6691 fold (build1 (ABS_EXPR,
6698 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6699 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6700 both transformations are correct when A is NaN: A != 0
6701 is then true, and A == 0 is false. */
6703 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6705 if (comp_code == NE_EXPR)
6706 return pedantic_non_lvalue (convert (type, arg1));
6707 else if (comp_code == EQ_EXPR)
6708 return pedantic_non_lvalue (convert (type, integer_zero_node));
6711 /* Try some transformations of A op B ? A : B.
6713 A == B? A : B same as B
6714 A != B? A : B same as A
6715 A >= B? A : B same as max (A, B)
6716 A > B? A : B same as max (B, A)
6717 A <= B? A : B same as min (A, B)
6718 A < B? A : B same as min (B, A)
6720 As above, these transformations don't work in the presence
6721 of signed zeros. For example, if A and B are zeros of
6722 opposite sign, the first two transformations will change
6723 the sign of the result. In the last four, the original
6724 expressions give different results for (A=+0, B=-0) and
6725 (A=-0, B=+0), but the transformed expressions do not.
6727 The first two transformations are correct if either A or B
6728 is a NaN. In the first transformation, the condition will
6729 be false, and B will indeed be chosen. In the case of the
6730 second transformation, the condition A != B will be true,
6731 and A will be chosen.
6733 The conversions to max() and min() are not correct if B is
6734 a number and A is not. The conditions in the original
6735 expressions will be false, so all four give B. The min()
6736 and max() versions would give a NaN instead. */
6737 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6738 arg2, TREE_OPERAND (arg0, 0)))
6740 tree comp_op0 = TREE_OPERAND (arg0, 0);
6741 tree comp_op1 = TREE_OPERAND (arg0, 1);
6742 tree comp_type = TREE_TYPE (comp_op0);
6744 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6745 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6751 return pedantic_non_lvalue (convert (type, arg2));
6753 return pedantic_non_lvalue (convert (type, arg1));
6756 /* In C++ a ?: expression can be an lvalue, so put the
6757 operand which will be used if they are equal first
6758 so that we can convert this back to the
6759 corresponding COND_EXPR. */
6760 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6761 return pedantic_non_lvalue
6762 (convert (type, fold (build (MIN_EXPR, comp_type,
6763 (comp_code == LE_EXPR
6764 ? comp_op0 : comp_op1),
6765 (comp_code == LE_EXPR
6766 ? comp_op1 : comp_op0)))));
6770 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6771 return pedantic_non_lvalue
6772 (convert (type, fold (build (MAX_EXPR, comp_type,
6773 (comp_code == GE_EXPR
6774 ? comp_op0 : comp_op1),
6775 (comp_code == GE_EXPR
6776 ? comp_op1 : comp_op0)))));
6783 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6784 we might still be able to simplify this. For example,
6785 if C1 is one less or one more than C2, this might have started
6786 out as a MIN or MAX and been transformed by this function.
6787 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6789 if (INTEGRAL_TYPE_P (type)
6790 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6791 && TREE_CODE (arg2) == INTEGER_CST)
6795 /* We can replace A with C1 in this case. */
6796 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6797 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6798 TREE_OPERAND (t, 2));
6802 /* If C1 is C2 + 1, this is min(A, C2). */
6803 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6804 && operand_equal_p (TREE_OPERAND (arg0, 1),
6805 const_binop (PLUS_EXPR, arg2,
6806 integer_one_node, 0), 1))
6807 return pedantic_non_lvalue
6808 (fold (build (MIN_EXPR, type, arg1, arg2)));
6812 /* If C1 is C2 - 1, this is min(A, C2). */
6813 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6814 && operand_equal_p (TREE_OPERAND (arg0, 1),
6815 const_binop (MINUS_EXPR, arg2,
6816 integer_one_node, 0), 1))
6817 return pedantic_non_lvalue
6818 (fold (build (MIN_EXPR, type, arg1, arg2)));
6822 /* If C1 is C2 - 1, this is max(A, C2). */
6823 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6824 && operand_equal_p (TREE_OPERAND (arg0, 1),
6825 const_binop (MINUS_EXPR, arg2,
6826 integer_one_node, 0), 1))
6827 return pedantic_non_lvalue
6828 (fold (build (MAX_EXPR, type, arg1, arg2)));
6832 /* If C1 is C2 + 1, this is max(A, C2). */
6833 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6834 && operand_equal_p (TREE_OPERAND (arg0, 1),
6835 const_binop (PLUS_EXPR, arg2,
6836 integer_one_node, 0), 1))
6837 return pedantic_non_lvalue
6838 (fold (build (MAX_EXPR, type, arg1, arg2)));
6847 /* If the second operand is simpler than the third, swap them
6848 since that produces better jump optimization results. */
6849 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
6850 || TREE_CODE (arg1) == SAVE_EXPR)
6851 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6852 || DECL_P (TREE_OPERAND (t, 2))
6853 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6855 /* See if this can be inverted. If it can't, possibly because
6856 it was a floating-point inequality comparison, don't do
6858 tem = invert_truthvalue (arg0);
6860 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6862 t = build (code, type, tem,
6863 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6865 /* arg1 should be the first argument of the new T. */
6866 arg1 = TREE_OPERAND (t, 1);
6871 /* Convert A ? 1 : 0 to simply A. */
6872 if (integer_onep (TREE_OPERAND (t, 1))
6873 && integer_zerop (TREE_OPERAND (t, 2))
6874 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6875 call to fold will try to move the conversion inside
6876 a COND, which will recurse. In that case, the COND_EXPR
6877 is probably the best choice, so leave it alone. */
6878 && type == TREE_TYPE (arg0))
6879 return pedantic_non_lvalue (arg0);
6881 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
6882 operation is simply A & 2. */
6884 if (integer_zerop (TREE_OPERAND (t, 2))
6885 && TREE_CODE (arg0) == NE_EXPR
6886 && integer_zerop (TREE_OPERAND (arg0, 1))
6887 && integer_pow2p (arg1)
6888 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6889 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6891 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6896 /* When pedantic, a compound expression can be neither an lvalue
6897 nor an integer constant expression. */
6898 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6900 /* Don't let (0, 0) be null pointer constant. */
6901 if (integer_zerop (arg1))
6902 return build1 (NOP_EXPR, type, arg1);
6903 return convert (type, arg1);
6907 return build_complex (type, arg0, arg1);
6911 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6913 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6914 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6915 TREE_OPERAND (arg0, 1));
6916 else if (TREE_CODE (arg0) == COMPLEX_CST)
6917 return TREE_REALPART (arg0);
6918 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6919 return fold (build (TREE_CODE (arg0), type,
6920 fold (build1 (REALPART_EXPR, type,
6921 TREE_OPERAND (arg0, 0))),
6922 fold (build1 (REALPART_EXPR,
6923 type, TREE_OPERAND (arg0, 1)))));
6927 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6928 return convert (type, integer_zero_node);
6929 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6930 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6931 TREE_OPERAND (arg0, 0));
6932 else if (TREE_CODE (arg0) == COMPLEX_CST)
6933 return TREE_IMAGPART (arg0);
6934 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6935 return fold (build (TREE_CODE (arg0), type,
6936 fold (build1 (IMAGPART_EXPR, type,
6937 TREE_OPERAND (arg0, 0))),
6938 fold (build1 (IMAGPART_EXPR, type,
6939 TREE_OPERAND (arg0, 1)))));
6942 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6944 case CLEANUP_POINT_EXPR:
6945 if (! has_cleanups (arg0))
6946 return TREE_OPERAND (t, 0);
6949 enum tree_code code0 = TREE_CODE (arg0);
6950 int kind0 = TREE_CODE_CLASS (code0);
6951 tree arg00 = TREE_OPERAND (arg0, 0);
6954 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6955 return fold (build1 (code0, type,
6956 fold (build1 (CLEANUP_POINT_EXPR,
6957 TREE_TYPE (arg00), arg00))));
6959 if (kind0 == '<' || kind0 == '2'
6960 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6961 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
6962 || code0 == TRUTH_XOR_EXPR)
6964 arg01 = TREE_OPERAND (arg0, 1);
6966 if (TREE_CONSTANT (arg00)
6967 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6968 && ! has_cleanups (arg00)))
6969 return fold (build (code0, type, arg00,
6970 fold (build1 (CLEANUP_POINT_EXPR,
6971 TREE_TYPE (arg01), arg01))));
6973 if (TREE_CONSTANT (arg01))
6974 return fold (build (code0, type,
6975 fold (build1 (CLEANUP_POINT_EXPR,
6976 TREE_TYPE (arg00), arg00)),
6984 /* Check for a built-in function. */
6985 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
6986 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
6988 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
6990 tree tmp = fold_builtin (expr);
6998 } /* switch (code) */
7001 /* Determine if first argument is a multiple of second argument. Return 0 if
7002 it is not, or we cannot easily determined it to be.
7004 An example of the sort of thing we care about (at this point; this routine
7005 could surely be made more general, and expanded to do what the *_DIV_EXPR's
7006 fold cases do now) is discovering that
7008 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7014 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
7016 This code also handles discovering that
7018 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
7020 is a multiple of 8 so we don't have to worry about dealing with a
7023 Note that we *look* inside a SAVE_EXPR only to determine how it was
7024 calculated; it is not safe for fold to do much of anything else with the
7025 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
7026 at run time. For example, the latter example above *cannot* be implemented
7027 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
7028 evaluation time of the original SAVE_EXPR is not necessarily the same at
7029 the time the new expression is evaluated. The only optimization of this
7030 sort that would be valid is changing
7032 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
7036 SAVE_EXPR (I) * SAVE_EXPR (J)
7038 (where the same SAVE_EXPR (J) is used in the original and the
7039 transformed version). */
7042 multiple_of_p (type, top, bottom)
7047 if (operand_equal_p (top, bottom, 0))
7050 if (TREE_CODE (type) != INTEGER_TYPE)
7053 switch (TREE_CODE (top))
7056 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7057 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7061 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
7062 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
7065 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
7069 op1 = TREE_OPERAND (top, 1);
7070 /* const_binop may not detect overflow correctly,
7071 so check for it explicitly here. */
7072 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
7073 > TREE_INT_CST_LOW (op1)
7074 && TREE_INT_CST_HIGH (op1) == 0
7075 && 0 != (t1 = convert (type,
7076 const_binop (LSHIFT_EXPR, size_one_node,
7078 && ! TREE_OVERFLOW (t1))
7079 return multiple_of_p (type, t1, bottom);
7084 /* Can't handle conversions from non-integral or wider integral type. */
7085 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
7086 || (TYPE_PRECISION (type)
7087 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
7090 /* .. fall through ... */
7093 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
7096 if (TREE_CODE (bottom) != INTEGER_CST
7097 || (TREE_UNSIGNED (type)
7098 && (tree_int_cst_sgn (top) < 0
7099 || tree_int_cst_sgn (bottom) < 0)))
7101 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
7109 /* Return true if `t' is known to be non-negative. */
7112 tree_expr_nonnegative_p (t)
7115 switch (TREE_CODE (t))
7121 return tree_int_cst_sgn (t) >= 0;
7122 case TRUNC_DIV_EXPR:
7124 case FLOOR_DIV_EXPR:
7125 case ROUND_DIV_EXPR:
7126 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7127 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7128 case TRUNC_MOD_EXPR:
7130 case FLOOR_MOD_EXPR:
7131 case ROUND_MOD_EXPR:
7132 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7134 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
7135 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
7137 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7139 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7140 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7142 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7143 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7145 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7147 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7149 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7150 case NON_LVALUE_EXPR:
7151 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7153 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
7156 if (truth_value_p (TREE_CODE (t)))
7157 /* Truth values evaluate to 0 or 1, which is nonnegative. */
7160 /* We don't know sign of `t', so be conservative and return false. */
7165 /* Return true if `r' is known to be non-negative.
7166 Only handles constants at the moment. */
7169 rtl_expr_nonnegative_p (r)
7172 switch (GET_CODE (r))
7175 return INTVAL (r) >= 0;
7178 if (GET_MODE (r) == VOIDmode)
7179 return CONST_DOUBLE_HIGH (r) >= 0;
7187 units = CONST_VECTOR_NUNITS (r);
7189 for (i = 0; i < units; ++i)
7191 elt = CONST_VECTOR_ELT (r, i);
7192 if (!rtl_expr_nonnegative_p (elt))
7201 /* These are always nonnegative. */