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 int simple_operand_p PARAMS ((tree));
90 static tree range_binop PARAMS ((enum tree_code, tree, tree, int,
92 static tree make_range PARAMS ((tree, int *, tree *, tree *));
93 static tree build_range_check PARAMS ((tree, tree, int, tree, tree));
94 static int merge_ranges PARAMS ((int *, tree *, tree *, int, tree, tree,
96 static tree fold_range_test PARAMS ((tree));
97 static tree unextend PARAMS ((tree, int, int, tree));
98 static tree fold_truthop PARAMS ((enum tree_code, tree, tree, tree));
99 static tree optimize_minmax_comparison PARAMS ((tree));
100 static tree extract_muldiv PARAMS ((tree, tree, enum tree_code, tree));
101 static tree strip_compound_expr PARAMS ((tree, tree));
102 static int multiple_of_p PARAMS ((tree, tree, tree));
103 static tree constant_boolean_node PARAMS ((int, tree));
104 static int count_cond PARAMS ((tree, int));
105 static tree fold_binary_op_with_conditional_arg
106 PARAMS ((enum tree_code, tree, tree, tree, int));
107 static bool fold_real_zero_addition_p PARAMS ((tree, tree, int));
110 #define BRANCH_COST 1
113 #if defined(HOST_EBCDIC)
114 /* bit 8 is significant in EBCDIC */
115 #define CHARMASK 0xff
117 #define CHARMASK 0x7f
120 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
121 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
122 and SUM1. Then this yields nonzero if overflow occurred during the
125 Overflow occurs if A and B have the same sign, but A and SUM differ in
126 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
128 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
130 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
131 We do that by representing the two-word integer in 4 words, with only
132 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
133 number. The value of the word is LOWPART + HIGHPART * BASE. */
136 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
137 #define HIGHPART(x) \
138 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
139 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
141 /* Unpack a two-word integer into 4 words.
142 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
143 WORDS points to the array of HOST_WIDE_INTs. */
146 encode (words, low, hi)
147 HOST_WIDE_INT *words;
148 unsigned HOST_WIDE_INT low;
151 words[0] = LOWPART (low);
152 words[1] = HIGHPART (low);
153 words[2] = LOWPART (hi);
154 words[3] = HIGHPART (hi);
157 /* Pack an array of 4 words into a two-word integer.
158 WORDS points to the array of words.
159 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
162 decode (words, low, hi)
163 HOST_WIDE_INT *words;
164 unsigned HOST_WIDE_INT *low;
167 *low = words[0] + words[1] * BASE;
168 *hi = words[2] + words[3] * BASE;
171 /* Make the integer constant T valid for its type by setting to 0 or 1 all
172 the bits in the constant that don't belong in the type.
174 Return 1 if a signed overflow occurs, 0 otherwise. If OVERFLOW is
175 nonzero, a signed overflow has already occurred in calculating T, so
178 Make the real constant T valid for its type by calling CHECK_FLOAT_VALUE,
182 force_fit_type (t, overflow)
186 unsigned HOST_WIDE_INT low;
190 if (TREE_CODE (t) == REAL_CST)
192 #ifdef CHECK_FLOAT_VALUE
193 CHECK_FLOAT_VALUE (TYPE_MODE (TREE_TYPE (t)), TREE_REAL_CST (t),
199 else if (TREE_CODE (t) != INTEGER_CST)
202 low = TREE_INT_CST_LOW (t);
203 high = TREE_INT_CST_HIGH (t);
205 if (POINTER_TYPE_P (TREE_TYPE (t)))
208 prec = TYPE_PRECISION (TREE_TYPE (t));
210 /* First clear all bits that are beyond the type's precision. */
212 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
214 else if (prec > HOST_BITS_PER_WIDE_INT)
215 TREE_INT_CST_HIGH (t)
216 &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
219 TREE_INT_CST_HIGH (t) = 0;
220 if (prec < HOST_BITS_PER_WIDE_INT)
221 TREE_INT_CST_LOW (t) &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
224 /* Unsigned types do not suffer sign extension or overflow unless they
226 if (TREE_UNSIGNED (TREE_TYPE (t))
227 && ! (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
228 && TYPE_IS_SIZETYPE (TREE_TYPE (t))))
231 /* If the value's sign bit is set, extend the sign. */
232 if (prec != 2 * HOST_BITS_PER_WIDE_INT
233 && (prec > HOST_BITS_PER_WIDE_INT
234 ? 0 != (TREE_INT_CST_HIGH (t)
236 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
237 : 0 != (TREE_INT_CST_LOW (t)
238 & ((unsigned HOST_WIDE_INT) 1 << (prec - 1)))))
240 /* Value is negative:
241 set to 1 all the bits that are outside this type's precision. */
242 if (prec > HOST_BITS_PER_WIDE_INT)
243 TREE_INT_CST_HIGH (t)
244 |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
247 TREE_INT_CST_HIGH (t) = -1;
248 if (prec < HOST_BITS_PER_WIDE_INT)
249 TREE_INT_CST_LOW (t) |= ((unsigned HOST_WIDE_INT) (-1) << prec);
253 /* Return nonzero if signed overflow occurred. */
255 ((overflow | (low ^ TREE_INT_CST_LOW (t)) | (high ^ TREE_INT_CST_HIGH (t)))
259 /* Add two doubleword integers with doubleword result.
260 Each argument is given as two `HOST_WIDE_INT' pieces.
261 One argument is L1 and H1; the other, L2 and H2.
262 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
265 add_double (l1, h1, l2, h2, lv, hv)
266 unsigned HOST_WIDE_INT l1, l2;
267 HOST_WIDE_INT h1, h2;
268 unsigned HOST_WIDE_INT *lv;
271 unsigned HOST_WIDE_INT l;
275 h = h1 + h2 + (l < l1);
279 return OVERFLOW_SUM_SIGN (h1, h2, h);
282 /* Negate a doubleword integer with doubleword result.
283 Return nonzero if the operation overflows, assuming it's signed.
284 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
285 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
288 neg_double (l1, h1, lv, hv)
289 unsigned HOST_WIDE_INT l1;
291 unsigned HOST_WIDE_INT *lv;
298 return (*hv & h1) < 0;
308 /* Multiply two doubleword integers with doubleword result.
309 Return nonzero if the operation overflows, assuming it's signed.
310 Each argument is given as two `HOST_WIDE_INT' pieces.
311 One argument is L1 and H1; the other, L2 and H2.
312 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
315 mul_double (l1, h1, l2, h2, lv, hv)
316 unsigned HOST_WIDE_INT l1, l2;
317 HOST_WIDE_INT h1, h2;
318 unsigned HOST_WIDE_INT *lv;
321 HOST_WIDE_INT arg1[4];
322 HOST_WIDE_INT arg2[4];
323 HOST_WIDE_INT prod[4 * 2];
324 unsigned HOST_WIDE_INT carry;
326 unsigned HOST_WIDE_INT toplow, neglow;
327 HOST_WIDE_INT tophigh, neghigh;
329 encode (arg1, l1, h1);
330 encode (arg2, l2, h2);
332 memset ((char *) prod, 0, sizeof prod);
334 for (i = 0; i < 4; i++)
337 for (j = 0; j < 4; j++)
340 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
341 carry += arg1[i] * arg2[j];
342 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
344 prod[k] = LOWPART (carry);
345 carry = HIGHPART (carry);
350 decode (prod, lv, hv); /* This ignores prod[4] through prod[4*2-1] */
352 /* Check for overflow by calculating the top half of the answer in full;
353 it should agree with the low half's sign bit. */
354 decode (prod + 4, &toplow, &tophigh);
357 neg_double (l2, h2, &neglow, &neghigh);
358 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
362 neg_double (l1, h1, &neglow, &neghigh);
363 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
365 return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
368 /* Shift the doubleword integer in L1, H1 left by COUNT places
369 keeping only PREC bits of result.
370 Shift right if COUNT is negative.
371 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
372 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
375 lshift_double (l1, h1, count, prec, lv, hv, arith)
376 unsigned HOST_WIDE_INT l1;
377 HOST_WIDE_INT h1, count;
379 unsigned HOST_WIDE_INT *lv;
383 unsigned HOST_WIDE_INT signmask;
387 rshift_double (l1, h1, -count, prec, lv, hv, arith);
391 #ifdef SHIFT_COUNT_TRUNCATED
392 if (SHIFT_COUNT_TRUNCATED)
396 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
398 /* Shifting by the host word size is undefined according to the
399 ANSI standard, so we must handle this as a special case. */
403 else if (count >= HOST_BITS_PER_WIDE_INT)
405 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
410 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
411 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
415 /* Sign extend all bits that are beyond the precision. */
417 signmask = -((prec > HOST_BITS_PER_WIDE_INT
418 ? (*hv >> (prec - HOST_BITS_PER_WIDE_INT - 1))
419 : (*lv >> (prec - 1))) & 1);
421 if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
423 else if (prec >= HOST_BITS_PER_WIDE_INT)
425 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
426 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
431 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
432 *lv |= signmask << prec;
436 /* Shift the doubleword integer in L1, H1 right by COUNT places
437 keeping only PREC bits of result. COUNT must be positive.
438 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
439 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
442 rshift_double (l1, h1, count, prec, lv, hv, arith)
443 unsigned HOST_WIDE_INT l1;
444 HOST_WIDE_INT h1, count;
446 unsigned HOST_WIDE_INT *lv;
450 unsigned HOST_WIDE_INT signmask;
453 ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
456 #ifdef SHIFT_COUNT_TRUNCATED
457 if (SHIFT_COUNT_TRUNCATED)
461 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
463 /* Shifting by the host word size is undefined according to the
464 ANSI standard, so we must handle this as a special case. */
468 else if (count >= HOST_BITS_PER_WIDE_INT)
471 *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
475 *hv = (unsigned HOST_WIDE_INT) h1 >> count;
477 | ((unsigned HOST_WIDE_INT) h1 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
480 /* Zero / sign extend all bits that are beyond the precision. */
482 if (count >= (HOST_WIDE_INT)prec)
487 else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
489 else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
491 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
492 *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
497 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
498 *lv |= signmask << (prec - count);
502 /* Rotate the doubleword integer in L1, H1 left by COUNT places
503 keeping only PREC bits of result.
504 Rotate right if COUNT is negative.
505 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
508 lrotate_double (l1, h1, count, prec, lv, hv)
509 unsigned HOST_WIDE_INT l1;
510 HOST_WIDE_INT h1, count;
512 unsigned HOST_WIDE_INT *lv;
515 unsigned HOST_WIDE_INT s1l, s2l;
516 HOST_WIDE_INT s1h, s2h;
522 lshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
523 rshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
528 /* Rotate the doubleword integer in L1, H1 left by COUNT places
529 keeping only PREC bits of result. COUNT must be positive.
530 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
533 rrotate_double (l1, h1, count, prec, lv, hv)
534 unsigned HOST_WIDE_INT l1;
535 HOST_WIDE_INT h1, count;
537 unsigned HOST_WIDE_INT *lv;
540 unsigned HOST_WIDE_INT s1l, s2l;
541 HOST_WIDE_INT s1h, s2h;
547 rshift_double (l1, h1, count, prec, &s1l, &s1h, 0);
548 lshift_double (l1, h1, prec - count, prec, &s2l, &s2h, 0);
553 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
554 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
555 CODE is a tree code for a kind of division, one of
556 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
558 It controls how the quotient is rounded to an integer.
559 Return nonzero if the operation overflows.
560 UNS nonzero says do unsigned division. */
563 div_and_round_double (code, uns,
564 lnum_orig, hnum_orig, lden_orig, hden_orig,
565 lquo, hquo, lrem, hrem)
568 unsigned HOST_WIDE_INT lnum_orig; /* num == numerator == dividend */
569 HOST_WIDE_INT hnum_orig;
570 unsigned HOST_WIDE_INT lden_orig; /* den == denominator == divisor */
571 HOST_WIDE_INT hden_orig;
572 unsigned HOST_WIDE_INT *lquo, *lrem;
573 HOST_WIDE_INT *hquo, *hrem;
576 HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
577 HOST_WIDE_INT den[4], quo[4];
579 unsigned HOST_WIDE_INT work;
580 unsigned HOST_WIDE_INT carry = 0;
581 unsigned HOST_WIDE_INT lnum = lnum_orig;
582 HOST_WIDE_INT hnum = hnum_orig;
583 unsigned HOST_WIDE_INT lden = lden_orig;
584 HOST_WIDE_INT hden = hden_orig;
587 if (hden == 0 && lden == 0)
588 overflow = 1, lden = 1;
590 /* calculate quotient sign and convert operands to unsigned. */
596 /* (minimum integer) / (-1) is the only overflow case. */
597 if (neg_double (lnum, hnum, &lnum, &hnum)
598 && ((HOST_WIDE_INT) lden & hden) == -1)
604 neg_double (lden, hden, &lden, &hden);
608 if (hnum == 0 && hden == 0)
609 { /* single precision */
611 /* This unsigned division rounds toward zero. */
617 { /* trivial case: dividend < divisor */
618 /* hden != 0 already checked. */
625 memset ((char *) quo, 0, sizeof quo);
627 memset ((char *) num, 0, sizeof num); /* to zero 9th element */
628 memset ((char *) den, 0, sizeof den);
630 encode (num, lnum, hnum);
631 encode (den, lden, hden);
633 /* Special code for when the divisor < BASE. */
634 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
636 /* hnum != 0 already checked. */
637 for (i = 4 - 1; i >= 0; i--)
639 work = num[i] + carry * BASE;
640 quo[i] = work / lden;
646 /* Full double precision division,
647 with thanks to Don Knuth's "Seminumerical Algorithms". */
648 int num_hi_sig, den_hi_sig;
649 unsigned HOST_WIDE_INT quo_est, scale;
651 /* Find the highest non-zero divisor digit. */
652 for (i = 4 - 1;; i--)
659 /* Insure that the first digit of the divisor is at least BASE/2.
660 This is required by the quotient digit estimation algorithm. */
662 scale = BASE / (den[den_hi_sig] + 1);
664 { /* scale divisor and dividend */
666 for (i = 0; i <= 4 - 1; i++)
668 work = (num[i] * scale) + carry;
669 num[i] = LOWPART (work);
670 carry = HIGHPART (work);
675 for (i = 0; i <= 4 - 1; i++)
677 work = (den[i] * scale) + carry;
678 den[i] = LOWPART (work);
679 carry = HIGHPART (work);
680 if (den[i] != 0) den_hi_sig = i;
687 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
689 /* Guess the next quotient digit, quo_est, by dividing the first
690 two remaining dividend digits by the high order quotient digit.
691 quo_est is never low and is at most 2 high. */
692 unsigned HOST_WIDE_INT tmp;
694 num_hi_sig = i + den_hi_sig + 1;
695 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
696 if (num[num_hi_sig] != den[den_hi_sig])
697 quo_est = work / den[den_hi_sig];
701 /* Refine quo_est so it's usually correct, and at most one high. */
702 tmp = work - quo_est * den[den_hi_sig];
704 && (den[den_hi_sig - 1] * quo_est
705 > (tmp * BASE + num[num_hi_sig - 2])))
708 /* Try QUO_EST as the quotient digit, by multiplying the
709 divisor by QUO_EST and subtracting from the remaining dividend.
710 Keep in mind that QUO_EST is the I - 1st digit. */
713 for (j = 0; j <= den_hi_sig; j++)
715 work = quo_est * den[j] + carry;
716 carry = HIGHPART (work);
717 work = num[i + j] - LOWPART (work);
718 num[i + j] = LOWPART (work);
719 carry += HIGHPART (work) != 0;
722 /* If quo_est was high by one, then num[i] went negative and
723 we need to correct things. */
724 if (num[num_hi_sig] < carry)
727 carry = 0; /* add divisor back in */
728 for (j = 0; j <= den_hi_sig; j++)
730 work = num[i + j] + den[j] + carry;
731 carry = HIGHPART (work);
732 num[i + j] = LOWPART (work);
735 num [num_hi_sig] += carry;
738 /* Store the quotient digit. */
743 decode (quo, lquo, hquo);
746 /* if result is negative, make it so. */
748 neg_double (*lquo, *hquo, lquo, hquo);
750 /* compute trial remainder: rem = num - (quo * den) */
751 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
752 neg_double (*lrem, *hrem, lrem, hrem);
753 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
758 case TRUNC_MOD_EXPR: /* round toward zero */
759 case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
763 case FLOOR_MOD_EXPR: /* round toward negative infinity */
764 if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
767 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
775 case CEIL_MOD_EXPR: /* round toward positive infinity */
776 if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
778 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
786 case ROUND_MOD_EXPR: /* round to closest integer */
788 unsigned HOST_WIDE_INT labs_rem = *lrem;
789 HOST_WIDE_INT habs_rem = *hrem;
790 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
791 HOST_WIDE_INT habs_den = hden, htwice;
793 /* Get absolute values */
795 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
797 neg_double (lden, hden, &labs_den, &habs_den);
799 /* If (2 * abs (lrem) >= abs (lden)) */
800 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
801 labs_rem, habs_rem, <wice, &htwice);
803 if (((unsigned HOST_WIDE_INT) habs_den
804 < (unsigned HOST_WIDE_INT) htwice)
805 || (((unsigned HOST_WIDE_INT) habs_den
806 == (unsigned HOST_WIDE_INT) htwice)
807 && (labs_den < ltwice)))
811 add_double (*lquo, *hquo,
812 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
815 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
827 /* compute true remainder: rem = num - (quo * den) */
828 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
829 neg_double (*lrem, *hrem, lrem, hrem);
830 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
834 /* Given T, an expression, return the negation of T. Allow for T to be
835 null, in which case return null. */
847 type = TREE_TYPE (t);
850 switch (TREE_CODE (t))
854 if (! TREE_UNSIGNED (type)
855 && 0 != (tem = fold (build1 (NEGATE_EXPR, type, t)))
856 && ! TREE_OVERFLOW (tem))
861 return convert (type, TREE_OPERAND (t, 0));
864 /* - (A - B) -> B - A */
865 if (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
866 return convert (type,
867 fold (build (MINUS_EXPR, TREE_TYPE (t),
869 TREE_OPERAND (t, 0))));
876 return convert (type, fold (build1 (NEGATE_EXPR, TREE_TYPE (t), t)));
879 /* Split a tree IN into a constant, literal and variable parts that could be
880 combined with CODE to make IN. "constant" means an expression with
881 TREE_CONSTANT but that isn't an actual constant. CODE must be a
882 commutative arithmetic operation. Store the constant part into *CONP,
883 the literal in &LITP and return the variable part. If a part isn't
884 present, set it to null. If the tree does not decompose in this way,
885 return the entire tree as the variable part and the other parts as null.
887 If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR. In that
888 case, we negate an operand that was subtracted. If NEGATE_P is true, we
889 are negating all of IN.
891 If IN is itself a literal or constant, return it as appropriate.
893 Note that we do not guarantee that any of the three values will be the
894 same type as IN, but they will have the same signedness and mode. */
897 split_tree (in, code, conp, litp, negate_p)
908 /* Strip any conversions that don't change the machine mode or signedness. */
909 STRIP_SIGN_NOPS (in);
911 if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST)
913 else if (TREE_CODE (in) == code
914 || (! FLOAT_TYPE_P (TREE_TYPE (in))
915 /* We can associate addition and subtraction together (even
916 though the C standard doesn't say so) for integers because
917 the value is not affected. For reals, the value might be
918 affected, so we can't. */
919 && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
920 || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
922 tree op0 = TREE_OPERAND (in, 0);
923 tree op1 = TREE_OPERAND (in, 1);
924 int neg1_p = TREE_CODE (in) == MINUS_EXPR;
925 int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
927 /* First see if either of the operands is a literal, then a constant. */
928 if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
929 *litp = op0, op0 = 0;
930 else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST)
931 *litp = op1, neg_litp_p = neg1_p, op1 = 0;
933 if (op0 != 0 && TREE_CONSTANT (op0))
934 *conp = op0, op0 = 0;
935 else if (op1 != 0 && TREE_CONSTANT (op1))
936 *conp = op1, neg_conp_p = neg1_p, op1 = 0;
938 /* If we haven't dealt with either operand, this is not a case we can
939 decompose. Otherwise, VAR is either of the ones remaining, if any. */
940 if (op0 != 0 && op1 != 0)
945 var = op1, neg_var_p = neg1_p;
947 /* Now do any needed negations. */
948 if (neg_litp_p) *litp = negate_expr (*litp);
949 if (neg_conp_p) *conp = negate_expr (*conp);
950 if (neg_var_p) var = negate_expr (var);
952 else if (TREE_CONSTANT (in))
959 var = negate_expr (var);
960 *conp = negate_expr (*conp);
961 *litp = negate_expr (*litp);
967 /* Re-associate trees split by the above function. T1 and T2 are either
968 expressions to associate or null. Return the new expression, if any. If
969 we build an operation, do it in TYPE and with CODE, except if CODE is a
970 MINUS_EXPR, in which case we use PLUS_EXPR since split_tree will already
971 have taken care of the negations. */
974 associate_trees (t1, t2, code, type)
984 if (code == MINUS_EXPR)
987 /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
988 try to fold this since we will have infinite recursion. But do
989 deal with any NEGATE_EXPRs. */
990 if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
991 || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
993 if (TREE_CODE (t1) == NEGATE_EXPR)
994 return build (MINUS_EXPR, type, convert (type, t2),
995 convert (type, TREE_OPERAND (t1, 0)));
996 else if (TREE_CODE (t2) == NEGATE_EXPR)
997 return build (MINUS_EXPR, type, convert (type, t1),
998 convert (type, TREE_OPERAND (t2, 0)));
1000 return build (code, type, convert (type, t1), convert (type, t2));
1003 return fold (build (code, type, convert (type, t1), convert (type, t2)));
1006 /* Combine two integer constants ARG1 and ARG2 under operation CODE
1007 to produce a new constant.
1009 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1012 int_const_binop (code, arg1, arg2, notrunc)
1013 enum tree_code code;
1017 unsigned HOST_WIDE_INT int1l, int2l;
1018 HOST_WIDE_INT int1h, int2h;
1019 unsigned HOST_WIDE_INT low;
1021 unsigned HOST_WIDE_INT garbagel;
1022 HOST_WIDE_INT garbageh;
1024 tree type = TREE_TYPE (arg1);
1025 int uns = TREE_UNSIGNED (type);
1027 = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1029 int no_overflow = 0;
1031 int1l = TREE_INT_CST_LOW (arg1);
1032 int1h = TREE_INT_CST_HIGH (arg1);
1033 int2l = TREE_INT_CST_LOW (arg2);
1034 int2h = TREE_INT_CST_HIGH (arg2);
1039 low = int1l | int2l, hi = int1h | int2h;
1043 low = int1l ^ int2l, hi = int1h ^ int2h;
1047 low = int1l & int2l, hi = int1h & int2h;
1050 case BIT_ANDTC_EXPR:
1051 low = int1l & ~int2l, hi = int1h & ~int2h;
1057 /* It's unclear from the C standard whether shifts can overflow.
1058 The following code ignores overflow; perhaps a C standard
1059 interpretation ruling is needed. */
1060 lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1068 lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1073 overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
1077 neg_double (int2l, int2h, &low, &hi);
1078 add_double (int1l, int1h, low, hi, &low, &hi);
1079 overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
1083 overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
1086 case TRUNC_DIV_EXPR:
1087 case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1088 case EXACT_DIV_EXPR:
1089 /* This is a shortcut for a common special case. */
1090 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1091 && ! TREE_CONSTANT_OVERFLOW (arg1)
1092 && ! TREE_CONSTANT_OVERFLOW (arg2)
1093 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1095 if (code == CEIL_DIV_EXPR)
1098 low = int1l / int2l, hi = 0;
1102 /* ... fall through ... */
1104 case ROUND_DIV_EXPR:
1105 if (int2h == 0 && int2l == 1)
1107 low = int1l, hi = int1h;
1110 if (int1l == int2l && int1h == int2h
1111 && ! (int1l == 0 && int1h == 0))
1116 overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
1117 &low, &hi, &garbagel, &garbageh);
1120 case TRUNC_MOD_EXPR:
1121 case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1122 /* This is a shortcut for a common special case. */
1123 if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
1124 && ! TREE_CONSTANT_OVERFLOW (arg1)
1125 && ! TREE_CONSTANT_OVERFLOW (arg2)
1126 && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
1128 if (code == CEIL_MOD_EXPR)
1130 low = int1l % int2l, hi = 0;
1134 /* ... fall through ... */
1136 case ROUND_MOD_EXPR:
1137 overflow = div_and_round_double (code, uns,
1138 int1l, int1h, int2l, int2h,
1139 &garbagel, &garbageh, &low, &hi);
1145 low = (((unsigned HOST_WIDE_INT) int1h
1146 < (unsigned HOST_WIDE_INT) int2h)
1147 || (((unsigned HOST_WIDE_INT) int1h
1148 == (unsigned HOST_WIDE_INT) int2h)
1151 low = (int1h < int2h
1152 || (int1h == int2h && int1l < int2l));
1154 if (low == (code == MIN_EXPR))
1155 low = int1l, hi = int1h;
1157 low = int2l, hi = int2h;
1164 /* If this is for a sizetype, can be represented as one (signed)
1165 HOST_WIDE_INT word, and doesn't overflow, use size_int since it caches
1168 && ((hi == 0 && (HOST_WIDE_INT) low >= 0)
1169 || (hi == -1 && (HOST_WIDE_INT) low < 0))
1170 && overflow == 0 && ! TREE_OVERFLOW (arg1) && ! TREE_OVERFLOW (arg2))
1171 return size_int_type_wide (low, type);
1174 t = build_int_2 (low, hi);
1175 TREE_TYPE (t) = TREE_TYPE (arg1);
1180 ? (!uns || is_sizetype) && overflow
1181 : (force_fit_type (t, (!uns || is_sizetype) && overflow)
1183 | TREE_OVERFLOW (arg1)
1184 | TREE_OVERFLOW (arg2));
1186 /* If we're doing a size calculation, unsigned arithmetic does overflow.
1187 So check if force_fit_type truncated the value. */
1189 && ! TREE_OVERFLOW (t)
1190 && (TREE_INT_CST_HIGH (t) != hi
1191 || TREE_INT_CST_LOW (t) != low))
1192 TREE_OVERFLOW (t) = 1;
1194 TREE_CONSTANT_OVERFLOW (t) = (TREE_OVERFLOW (t)
1195 | TREE_CONSTANT_OVERFLOW (arg1)
1196 | TREE_CONSTANT_OVERFLOW (arg2));
1200 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1201 constant. We assume ARG1 and ARG2 have the same data type, or at least
1202 are the same kind of constant and the same machine mode.
1204 If NOTRUNC is nonzero, do not truncate the result to fit the data type. */
1207 const_binop (code, arg1, arg2, notrunc)
1208 enum tree_code code;
1215 if (TREE_CODE (arg1) == INTEGER_CST)
1216 return int_const_binop (code, arg1, arg2, notrunc);
1218 if (TREE_CODE (arg1) == REAL_CST)
1222 REAL_VALUE_TYPE value;
1225 d1 = TREE_REAL_CST (arg1);
1226 d2 = TREE_REAL_CST (arg2);
1228 /* If either operand is a NaN, just return it. Otherwise, set up
1229 for floating-point trap; we return an overflow. */
1230 if (REAL_VALUE_ISNAN (d1))
1232 else if (REAL_VALUE_ISNAN (d2))
1235 REAL_ARITHMETIC (value, code, d1, d2);
1237 t = build_real (TREE_TYPE (arg1),
1238 real_value_truncate (TYPE_MODE (TREE_TYPE (arg1)),
1242 = (force_fit_type (t, 0)
1243 | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1244 TREE_CONSTANT_OVERFLOW (t)
1246 | TREE_CONSTANT_OVERFLOW (arg1)
1247 | TREE_CONSTANT_OVERFLOW (arg2);
1250 if (TREE_CODE (arg1) == COMPLEX_CST)
1252 tree type = TREE_TYPE (arg1);
1253 tree r1 = TREE_REALPART (arg1);
1254 tree i1 = TREE_IMAGPART (arg1);
1255 tree r2 = TREE_REALPART (arg2);
1256 tree i2 = TREE_IMAGPART (arg2);
1262 t = build_complex (type,
1263 const_binop (PLUS_EXPR, r1, r2, notrunc),
1264 const_binop (PLUS_EXPR, i1, i2, notrunc));
1268 t = build_complex (type,
1269 const_binop (MINUS_EXPR, r1, r2, notrunc),
1270 const_binop (MINUS_EXPR, i1, i2, notrunc));
1274 t = build_complex (type,
1275 const_binop (MINUS_EXPR,
1276 const_binop (MULT_EXPR,
1278 const_binop (MULT_EXPR,
1281 const_binop (PLUS_EXPR,
1282 const_binop (MULT_EXPR,
1284 const_binop (MULT_EXPR,
1292 = const_binop (PLUS_EXPR,
1293 const_binop (MULT_EXPR, r2, r2, notrunc),
1294 const_binop (MULT_EXPR, i2, i2, notrunc),
1297 t = build_complex (type,
1299 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1300 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1301 const_binop (PLUS_EXPR,
1302 const_binop (MULT_EXPR, r1, r2,
1304 const_binop (MULT_EXPR, i1, i2,
1307 magsquared, notrunc),
1309 (INTEGRAL_TYPE_P (TREE_TYPE (r1))
1310 ? TRUNC_DIV_EXPR : RDIV_EXPR,
1311 const_binop (MINUS_EXPR,
1312 const_binop (MULT_EXPR, i1, r2,
1314 const_binop (MULT_EXPR, r1, i2,
1317 magsquared, notrunc));
1329 /* These are the hash table functions for the hash table of INTEGER_CST
1330 nodes of a sizetype. */
1332 /* Return the hash code code X, an INTEGER_CST. */
1340 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
1341 ^ (hashval_t) ((long) TREE_TYPE (t) >> 3)
1342 ^ (TREE_OVERFLOW (t) << 20));
1345 /* Return non-zero if the value represented by *X (an INTEGER_CST tree node)
1346 is the same as that given by *Y, which is the same. */
1356 return (TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
1357 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt)
1358 && TREE_TYPE (xt) == TREE_TYPE (yt)
1359 && TREE_OVERFLOW (xt) == TREE_OVERFLOW (yt));
1362 /* Return an INTEGER_CST with value whose low-order HOST_BITS_PER_WIDE_INT
1363 bits are given by NUMBER and of the sizetype represented by KIND. */
1366 size_int_wide (number, kind)
1367 HOST_WIDE_INT number;
1368 enum size_type_kind kind;
1370 return size_int_type_wide (number, sizetype_tab[(int) kind]);
1373 /* Likewise, but the desired type is specified explicitly. */
1376 size_int_type_wide (number, type)
1377 HOST_WIDE_INT number;
1380 static htab_t size_htab = 0;
1381 static tree new_const = 0;
1386 size_htab = htab_create (1024, size_htab_hash, size_htab_eq, NULL);
1387 ggc_add_deletable_htab (size_htab, NULL, NULL);
1388 new_const = make_node (INTEGER_CST);
1389 ggc_add_tree_root (&new_const, 1);
1392 /* Adjust NEW_CONST to be the constant we want. If it's already in the
1393 hash table, we return the value from the hash table. Otherwise, we
1394 place that in the hash table and make a new node for the next time. */
1395 TREE_INT_CST_LOW (new_const) = number;
1396 TREE_INT_CST_HIGH (new_const) = number < 0 ? -1 : 0;
1397 TREE_TYPE (new_const) = type;
1398 TREE_OVERFLOW (new_const) = TREE_CONSTANT_OVERFLOW (new_const)
1399 = force_fit_type (new_const, 0);
1401 slot = htab_find_slot (size_htab, new_const, INSERT);
1406 *slot = (PTR) new_const;
1407 new_const = make_node (INTEGER_CST);
1411 return (tree) *slot;
1414 /* Combine operands OP1 and OP2 with arithmetic operation CODE. CODE
1415 is a tree code. The type of the result is taken from the operands.
1416 Both must be the same type integer type and it must be a size type.
1417 If the operands are constant, so is the result. */
1420 size_binop (code, arg0, arg1)
1421 enum tree_code code;
1424 tree type = TREE_TYPE (arg0);
1426 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1427 || type != TREE_TYPE (arg1))
1430 /* Handle the special case of two integer constants faster. */
1431 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1433 /* And some specific cases even faster than that. */
1434 if (code == PLUS_EXPR && integer_zerop (arg0))
1436 else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1437 && integer_zerop (arg1))
1439 else if (code == MULT_EXPR && integer_onep (arg0))
1442 /* Handle general case of two integer constants. */
1443 return int_const_binop (code, arg0, arg1, 0);
1446 if (arg0 == error_mark_node || arg1 == error_mark_node)
1447 return error_mark_node;
1449 return fold (build (code, type, arg0, arg1));
1452 /* Given two values, either both of sizetype or both of bitsizetype,
1453 compute the difference between the two values. Return the value
1454 in signed type corresponding to the type of the operands. */
1457 size_diffop (arg0, arg1)
1460 tree type = TREE_TYPE (arg0);
1463 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1464 || type != TREE_TYPE (arg1))
1467 /* If the type is already signed, just do the simple thing. */
1468 if (! TREE_UNSIGNED (type))
1469 return size_binop (MINUS_EXPR, arg0, arg1);
1471 ctype = (type == bitsizetype || type == ubitsizetype
1472 ? sbitsizetype : ssizetype);
1474 /* If either operand is not a constant, do the conversions to the signed
1475 type and subtract. The hardware will do the right thing with any
1476 overflow in the subtraction. */
1477 if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1478 return size_binop (MINUS_EXPR, convert (ctype, arg0),
1479 convert (ctype, arg1));
1481 /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1482 Otherwise, subtract the other way, convert to CTYPE (we know that can't
1483 overflow) and negate (which can't either). Special-case a result
1484 of zero while we're here. */
1485 if (tree_int_cst_equal (arg0, arg1))
1486 return convert (ctype, integer_zero_node);
1487 else if (tree_int_cst_lt (arg1, arg0))
1488 return convert (ctype, size_binop (MINUS_EXPR, arg0, arg1));
1490 return size_binop (MINUS_EXPR, convert (ctype, integer_zero_node),
1491 convert (ctype, size_binop (MINUS_EXPR, arg1, arg0)));
1495 /* Given T, a tree representing type conversion of ARG1, a constant,
1496 return a constant tree representing the result of conversion. */
1499 fold_convert (t, arg1)
1503 tree type = TREE_TYPE (t);
1506 if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))
1508 if (TREE_CODE (arg1) == INTEGER_CST)
1510 /* If we would build a constant wider than GCC supports,
1511 leave the conversion unfolded. */
1512 if (TYPE_PRECISION (type) > 2 * HOST_BITS_PER_WIDE_INT)
1515 /* If we are trying to make a sizetype for a small integer, use
1516 size_int to pick up cached types to reduce duplicate nodes. */
1517 if (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1518 && !TREE_CONSTANT_OVERFLOW (arg1)
1519 && compare_tree_int (arg1, 10000) < 0)
1520 return size_int_type_wide (TREE_INT_CST_LOW (arg1), type);
1522 /* Given an integer constant, make new constant with new type,
1523 appropriately sign-extended or truncated. */
1524 t = build_int_2 (TREE_INT_CST_LOW (arg1),
1525 TREE_INT_CST_HIGH (arg1));
1526 TREE_TYPE (t) = type;
1527 /* Indicate an overflow if (1) ARG1 already overflowed,
1528 or (2) force_fit_type indicates an overflow.
1529 Tell force_fit_type that an overflow has already occurred
1530 if ARG1 is a too-large unsigned value and T is signed.
1531 But don't indicate an overflow if converting a pointer. */
1533 = ((force_fit_type (t,
1534 (TREE_INT_CST_HIGH (arg1) < 0
1535 && (TREE_UNSIGNED (type)
1536 < TREE_UNSIGNED (TREE_TYPE (arg1)))))
1537 && ! POINTER_TYPE_P (TREE_TYPE (arg1)))
1538 || TREE_OVERFLOW (arg1));
1539 TREE_CONSTANT_OVERFLOW (t)
1540 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1542 else if (TREE_CODE (arg1) == REAL_CST)
1544 /* Don't initialize these, use assignments.
1545 Initialized local aggregates don't work on old compilers. */
1549 tree type1 = TREE_TYPE (arg1);
1552 x = TREE_REAL_CST (arg1);
1553 l = real_value_from_int_cst (type1, TYPE_MIN_VALUE (type));
1555 no_upper_bound = (TYPE_MAX_VALUE (type) == NULL);
1556 if (!no_upper_bound)
1557 u = real_value_from_int_cst (type1, TYPE_MAX_VALUE (type));
1559 /* See if X will be in range after truncation towards 0.
1560 To compensate for truncation, move the bounds away from 0,
1561 but reject if X exactly equals the adjusted bounds. */
1562 REAL_ARITHMETIC (l, MINUS_EXPR, l, dconst1);
1563 if (!no_upper_bound)
1564 REAL_ARITHMETIC (u, PLUS_EXPR, u, dconst1);
1565 /* If X is a NaN, use zero instead and show we have an overflow.
1566 Otherwise, range check. */
1567 if (REAL_VALUE_ISNAN (x))
1568 overflow = 1, x = dconst0;
1569 else if (! (REAL_VALUES_LESS (l, x)
1571 && REAL_VALUES_LESS (x, u)))
1575 HOST_WIDE_INT low, high;
1576 REAL_VALUE_TO_INT (&low, &high, x);
1577 t = build_int_2 (low, high);
1579 TREE_TYPE (t) = type;
1581 = TREE_OVERFLOW (arg1) | force_fit_type (t, overflow);
1582 TREE_CONSTANT_OVERFLOW (t)
1583 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1585 TREE_TYPE (t) = type;
1587 else if (TREE_CODE (type) == REAL_TYPE)
1589 if (TREE_CODE (arg1) == INTEGER_CST)
1590 return build_real_from_int_cst (type, arg1);
1591 if (TREE_CODE (arg1) == REAL_CST)
1593 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
1596 TREE_TYPE (arg1) = type;
1600 t = build_real (type,
1601 real_value_truncate (TYPE_MODE (type),
1602 TREE_REAL_CST (arg1)));
1605 = TREE_OVERFLOW (arg1) | force_fit_type (t, 0);
1606 TREE_CONSTANT_OVERFLOW (t)
1607 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg1);
1611 TREE_CONSTANT (t) = 1;
1615 /* Return an expr equal to X but certainly not valid as an lvalue. */
1623 /* These things are certainly not lvalues. */
1624 if (TREE_CODE (x) == NON_LVALUE_EXPR
1625 || TREE_CODE (x) == INTEGER_CST
1626 || TREE_CODE (x) == REAL_CST
1627 || TREE_CODE (x) == STRING_CST
1628 || TREE_CODE (x) == ADDR_EXPR)
1631 result = build1 (NON_LVALUE_EXPR, TREE_TYPE (x), x);
1632 TREE_CONSTANT (result) = TREE_CONSTANT (x);
1636 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
1637 Zero means allow extended lvalues. */
1639 int pedantic_lvalues;
1641 /* When pedantic, return an expr equal to X but certainly not valid as a
1642 pedantic lvalue. Otherwise, return X. */
1645 pedantic_non_lvalue (x)
1648 if (pedantic_lvalues)
1649 return non_lvalue (x);
1654 /* Given a tree comparison code, return the code that is the logical inverse
1655 of the given code. It is not safe to do this for floating-point
1656 comparisons, except for NE_EXPR and EQ_EXPR. */
1658 static enum tree_code
1659 invert_tree_comparison (code)
1660 enum tree_code code;
1681 /* Similar, but return the comparison that results if the operands are
1682 swapped. This is safe for floating-point. */
1684 static enum tree_code
1685 swap_tree_comparison (code)
1686 enum tree_code code;
1706 /* Return nonzero if CODE is a tree code that represents a truth value. */
1709 truth_value_p (code)
1710 enum tree_code code;
1712 return (TREE_CODE_CLASS (code) == '<'
1713 || code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR
1714 || code == TRUTH_OR_EXPR || code == TRUTH_ORIF_EXPR
1715 || code == TRUTH_XOR_EXPR || code == TRUTH_NOT_EXPR);
1718 /* Return nonzero if two operands are necessarily equal.
1719 If ONLY_CONST is non-zero, only return non-zero for constants.
1720 This function tests whether the operands are indistinguishable;
1721 it does not test whether they are equal using C's == operation.
1722 The distinction is important for IEEE floating point, because
1723 (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
1724 (2) two NaNs may be indistinguishable, but NaN!=NaN. */
1727 operand_equal_p (arg0, arg1, only_const)
1731 /* If both types don't have the same signedness, then we can't consider
1732 them equal. We must check this before the STRIP_NOPS calls
1733 because they may change the signedness of the arguments. */
1734 if (TREE_UNSIGNED (TREE_TYPE (arg0)) != TREE_UNSIGNED (TREE_TYPE (arg1)))
1740 if (TREE_CODE (arg0) != TREE_CODE (arg1)
1741 /* This is needed for conversions and for COMPONENT_REF.
1742 Might as well play it safe and always test this. */
1743 || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
1744 || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
1745 || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
1748 /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
1749 We don't care about side effects in that case because the SAVE_EXPR
1750 takes care of that for us. In all other cases, two expressions are
1751 equal if they have no side effects. If we have two identical
1752 expressions with side effects that should be treated the same due
1753 to the only side effects being identical SAVE_EXPR's, that will
1754 be detected in the recursive calls below. */
1755 if (arg0 == arg1 && ! only_const
1756 && (TREE_CODE (arg0) == SAVE_EXPR
1757 || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
1760 /* Next handle constant cases, those for which we can return 1 even
1761 if ONLY_CONST is set. */
1762 if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
1763 switch (TREE_CODE (arg0))
1766 return (! TREE_CONSTANT_OVERFLOW (arg0)
1767 && ! TREE_CONSTANT_OVERFLOW (arg1)
1768 && tree_int_cst_equal (arg0, arg1));
1771 return (! TREE_CONSTANT_OVERFLOW (arg0)
1772 && ! TREE_CONSTANT_OVERFLOW (arg1)
1773 && REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
1774 TREE_REAL_CST (arg1)));
1780 if (TREE_CONSTANT_OVERFLOW (arg0)
1781 || TREE_CONSTANT_OVERFLOW (arg1))
1784 v1 = TREE_VECTOR_CST_ELTS (arg0);
1785 v2 = TREE_VECTOR_CST_ELTS (arg1);
1788 if (!operand_equal_p (v1, v2, only_const))
1790 v1 = TREE_CHAIN (v1);
1791 v2 = TREE_CHAIN (v2);
1798 return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
1800 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
1804 return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
1805 && ! memcmp (TREE_STRING_POINTER (arg0),
1806 TREE_STRING_POINTER (arg1),
1807 TREE_STRING_LENGTH (arg0)));
1810 return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
1819 switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
1822 /* Two conversions are equal only if signedness and modes match. */
1823 if ((TREE_CODE (arg0) == NOP_EXPR || TREE_CODE (arg0) == CONVERT_EXPR)
1824 && (TREE_UNSIGNED (TREE_TYPE (arg0))
1825 != TREE_UNSIGNED (TREE_TYPE (arg1))))
1828 return operand_equal_p (TREE_OPERAND (arg0, 0),
1829 TREE_OPERAND (arg1, 0), 0);
1833 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0)
1834 && operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1),
1838 /* For commutative ops, allow the other order. */
1839 return ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MULT_EXPR
1840 || TREE_CODE (arg0) == MIN_EXPR || TREE_CODE (arg0) == MAX_EXPR
1841 || TREE_CODE (arg0) == BIT_IOR_EXPR
1842 || TREE_CODE (arg0) == BIT_XOR_EXPR
1843 || TREE_CODE (arg0) == BIT_AND_EXPR
1844 || TREE_CODE (arg0) == NE_EXPR || TREE_CODE (arg0) == EQ_EXPR)
1845 && operand_equal_p (TREE_OPERAND (arg0, 0),
1846 TREE_OPERAND (arg1, 1), 0)
1847 && operand_equal_p (TREE_OPERAND (arg0, 1),
1848 TREE_OPERAND (arg1, 0), 0));
1851 /* If either of the pointer (or reference) expressions we are dereferencing
1852 contain a side effect, these cannot be equal. */
1853 if (TREE_SIDE_EFFECTS (arg0)
1854 || TREE_SIDE_EFFECTS (arg1))
1857 switch (TREE_CODE (arg0))
1860 return operand_equal_p (TREE_OPERAND (arg0, 0),
1861 TREE_OPERAND (arg1, 0), 0);
1865 case ARRAY_RANGE_REF:
1866 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1867 TREE_OPERAND (arg1, 0), 0)
1868 && operand_equal_p (TREE_OPERAND (arg0, 1),
1869 TREE_OPERAND (arg1, 1), 0));
1872 return (operand_equal_p (TREE_OPERAND (arg0, 0),
1873 TREE_OPERAND (arg1, 0), 0)
1874 && operand_equal_p (TREE_OPERAND (arg0, 1),
1875 TREE_OPERAND (arg1, 1), 0)
1876 && operand_equal_p (TREE_OPERAND (arg0, 2),
1877 TREE_OPERAND (arg1, 2), 0));
1883 if (TREE_CODE (arg0) == RTL_EXPR)
1884 return rtx_equal_p (RTL_EXPR_RTL (arg0), RTL_EXPR_RTL (arg1));
1892 /* Similar to operand_equal_p, but see if ARG0 might have been made by
1893 shorten_compare from ARG1 when ARG1 was being compared with OTHER.
1895 When in doubt, return 0. */
1898 operand_equal_for_comparison_p (arg0, arg1, other)
1902 int unsignedp1, unsignedpo;
1903 tree primarg0, primarg1, primother;
1904 unsigned int correct_width;
1906 if (operand_equal_p (arg0, arg1, 0))
1909 if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
1910 || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
1913 /* Discard any conversions that don't change the modes of ARG0 and ARG1
1914 and see if the inner values are the same. This removes any
1915 signedness comparison, which doesn't matter here. */
1916 primarg0 = arg0, primarg1 = arg1;
1917 STRIP_NOPS (primarg0);
1918 STRIP_NOPS (primarg1);
1919 if (operand_equal_p (primarg0, primarg1, 0))
1922 /* Duplicate what shorten_compare does to ARG1 and see if that gives the
1923 actual comparison operand, ARG0.
1925 First throw away any conversions to wider types
1926 already present in the operands. */
1928 primarg1 = get_narrower (arg1, &unsignedp1);
1929 primother = get_narrower (other, &unsignedpo);
1931 correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
1932 if (unsignedp1 == unsignedpo
1933 && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
1934 && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
1936 tree type = TREE_TYPE (arg0);
1938 /* Make sure shorter operand is extended the right way
1939 to match the longer operand. */
1940 primarg1 = convert (signed_or_unsigned_type (unsignedp1,
1941 TREE_TYPE (primarg1)),
1944 if (operand_equal_p (arg0, convert (type, primarg1), 0))
1951 /* See if ARG is an expression that is either a comparison or is performing
1952 arithmetic on comparisons. The comparisons must only be comparing
1953 two different values, which will be stored in *CVAL1 and *CVAL2; if
1954 they are non-zero it means that some operands have already been found.
1955 No variables may be used anywhere else in the expression except in the
1956 comparisons. If SAVE_P is true it means we removed a SAVE_EXPR around
1957 the expression and save_expr needs to be called with CVAL1 and CVAL2.
1959 If this is true, return 1. Otherwise, return zero. */
1962 twoval_comparison_p (arg, cval1, cval2, save_p)
1964 tree *cval1, *cval2;
1967 enum tree_code code = TREE_CODE (arg);
1968 char class = TREE_CODE_CLASS (code);
1970 /* We can handle some of the 'e' cases here. */
1971 if (class == 'e' && code == TRUTH_NOT_EXPR)
1973 else if (class == 'e'
1974 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
1975 || code == COMPOUND_EXPR))
1978 else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
1979 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
1981 /* If we've already found a CVAL1 or CVAL2, this expression is
1982 two complex to handle. */
1983 if (*cval1 || *cval2)
1993 return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
1996 return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
1997 && twoval_comparison_p (TREE_OPERAND (arg, 1),
1998 cval1, cval2, save_p));
2004 if (code == COND_EXPR)
2005 return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2006 cval1, cval2, save_p)
2007 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2008 cval1, cval2, save_p)
2009 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2010 cval1, cval2, save_p));
2014 /* First see if we can handle the first operand, then the second. For
2015 the second operand, we know *CVAL1 can't be zero. It must be that
2016 one side of the comparison is each of the values; test for the
2017 case where this isn't true by failing if the two operands
2020 if (operand_equal_p (TREE_OPERAND (arg, 0),
2021 TREE_OPERAND (arg, 1), 0))
2025 *cval1 = TREE_OPERAND (arg, 0);
2026 else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2028 else if (*cval2 == 0)
2029 *cval2 = TREE_OPERAND (arg, 0);
2030 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2035 if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2037 else if (*cval2 == 0)
2038 *cval2 = TREE_OPERAND (arg, 1);
2039 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2051 /* ARG is a tree that is known to contain just arithmetic operations and
2052 comparisons. Evaluate the operations in the tree substituting NEW0 for
2053 any occurrence of OLD0 as an operand of a comparison and likewise for
2057 eval_subst (arg, old0, new0, old1, new1)
2059 tree old0, new0, old1, new1;
2061 tree type = TREE_TYPE (arg);
2062 enum tree_code code = TREE_CODE (arg);
2063 char class = TREE_CODE_CLASS (code);
2065 /* We can handle some of the 'e' cases here. */
2066 if (class == 'e' && code == TRUTH_NOT_EXPR)
2068 else if (class == 'e'
2069 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2075 return fold (build1 (code, type,
2076 eval_subst (TREE_OPERAND (arg, 0),
2077 old0, new0, old1, new1)));
2080 return fold (build (code, type,
2081 eval_subst (TREE_OPERAND (arg, 0),
2082 old0, new0, old1, new1),
2083 eval_subst (TREE_OPERAND (arg, 1),
2084 old0, new0, old1, new1)));
2090 return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2093 return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2096 return fold (build (code, type,
2097 eval_subst (TREE_OPERAND (arg, 0),
2098 old0, new0, old1, new1),
2099 eval_subst (TREE_OPERAND (arg, 1),
2100 old0, new0, old1, new1),
2101 eval_subst (TREE_OPERAND (arg, 2),
2102 old0, new0, old1, new1)));
2106 /* fall through - ??? */
2110 tree arg0 = TREE_OPERAND (arg, 0);
2111 tree arg1 = TREE_OPERAND (arg, 1);
2113 /* We need to check both for exact equality and tree equality. The
2114 former will be true if the operand has a side-effect. In that
2115 case, we know the operand occurred exactly once. */
2117 if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2119 else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2122 if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2124 else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2127 return fold (build (code, type, arg0, arg1));
2135 /* Return a tree for the case when the result of an expression is RESULT
2136 converted to TYPE and OMITTED was previously an operand of the expression
2137 but is now not needed (e.g., we folded OMITTED * 0).
2139 If OMITTED has side effects, we must evaluate it. Otherwise, just do
2140 the conversion of RESULT to TYPE. */
2143 omit_one_operand (type, result, omitted)
2144 tree type, result, omitted;
2146 tree t = convert (type, result);
2148 if (TREE_SIDE_EFFECTS (omitted))
2149 return build (COMPOUND_EXPR, type, omitted, t);
2151 return non_lvalue (t);
2154 /* Similar, but call pedantic_non_lvalue instead of non_lvalue. */
2157 pedantic_omit_one_operand (type, result, omitted)
2158 tree type, result, omitted;
2160 tree t = convert (type, result);
2162 if (TREE_SIDE_EFFECTS (omitted))
2163 return build (COMPOUND_EXPR, type, omitted, t);
2165 return pedantic_non_lvalue (t);
2168 /* Return a simplified tree node for the truth-negation of ARG. This
2169 never alters ARG itself. We assume that ARG is an operation that
2170 returns a truth value (0 or 1). */
2173 invert_truthvalue (arg)
2176 tree type = TREE_TYPE (arg);
2177 enum tree_code code = TREE_CODE (arg);
2179 if (code == ERROR_MARK)
2182 /* If this is a comparison, we can simply invert it, except for
2183 floating-point non-equality comparisons, in which case we just
2184 enclose a TRUTH_NOT_EXPR around what we have. */
2186 if (TREE_CODE_CLASS (code) == '<')
2188 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2189 && !flag_unsafe_math_optimizations
2192 return build1 (TRUTH_NOT_EXPR, type, arg);
2194 return build (invert_tree_comparison (code), type,
2195 TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2201 return convert (type, build_int_2 (integer_zerop (arg), 0));
2203 case TRUTH_AND_EXPR:
2204 return build (TRUTH_OR_EXPR, type,
2205 invert_truthvalue (TREE_OPERAND (arg, 0)),
2206 invert_truthvalue (TREE_OPERAND (arg, 1)));
2209 return build (TRUTH_AND_EXPR, type,
2210 invert_truthvalue (TREE_OPERAND (arg, 0)),
2211 invert_truthvalue (TREE_OPERAND (arg, 1)));
2213 case TRUTH_XOR_EXPR:
2214 /* Here we can invert either operand. We invert the first operand
2215 unless the second operand is a TRUTH_NOT_EXPR in which case our
2216 result is the XOR of the first operand with the inside of the
2217 negation of the second operand. */
2219 if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2220 return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2221 TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2223 return build (TRUTH_XOR_EXPR, type,
2224 invert_truthvalue (TREE_OPERAND (arg, 0)),
2225 TREE_OPERAND (arg, 1));
2227 case TRUTH_ANDIF_EXPR:
2228 return build (TRUTH_ORIF_EXPR, type,
2229 invert_truthvalue (TREE_OPERAND (arg, 0)),
2230 invert_truthvalue (TREE_OPERAND (arg, 1)));
2232 case TRUTH_ORIF_EXPR:
2233 return build (TRUTH_ANDIF_EXPR, type,
2234 invert_truthvalue (TREE_OPERAND (arg, 0)),
2235 invert_truthvalue (TREE_OPERAND (arg, 1)));
2237 case TRUTH_NOT_EXPR:
2238 return TREE_OPERAND (arg, 0);
2241 return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2242 invert_truthvalue (TREE_OPERAND (arg, 1)),
2243 invert_truthvalue (TREE_OPERAND (arg, 2)));
2246 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2247 invert_truthvalue (TREE_OPERAND (arg, 1)));
2249 case WITH_RECORD_EXPR:
2250 return build (WITH_RECORD_EXPR, type,
2251 invert_truthvalue (TREE_OPERAND (arg, 0)),
2252 TREE_OPERAND (arg, 1));
2254 case NON_LVALUE_EXPR:
2255 return invert_truthvalue (TREE_OPERAND (arg, 0));
2260 return build1 (TREE_CODE (arg), type,
2261 invert_truthvalue (TREE_OPERAND (arg, 0)));
2264 if (!integer_onep (TREE_OPERAND (arg, 1)))
2266 return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2269 return build1 (TRUTH_NOT_EXPR, type, arg);
2271 case CLEANUP_POINT_EXPR:
2272 return build1 (CLEANUP_POINT_EXPR, type,
2273 invert_truthvalue (TREE_OPERAND (arg, 0)));
2278 if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2280 return build1 (TRUTH_NOT_EXPR, type, arg);
2283 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2284 operands are another bit-wise operation with a common input. If so,
2285 distribute the bit operations to save an operation and possibly two if
2286 constants are involved. For example, convert
2287 (A | B) & (A | C) into A | (B & C)
2288 Further simplification will occur if B and C are constants.
2290 If this optimization cannot be done, 0 will be returned. */
2293 distribute_bit_expr (code, type, arg0, arg1)
2294 enum tree_code code;
2301 if (TREE_CODE (arg0) != TREE_CODE (arg1)
2302 || TREE_CODE (arg0) == code
2303 || (TREE_CODE (arg0) != BIT_AND_EXPR
2304 && TREE_CODE (arg0) != BIT_IOR_EXPR))
2307 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2309 common = TREE_OPERAND (arg0, 0);
2310 left = TREE_OPERAND (arg0, 1);
2311 right = TREE_OPERAND (arg1, 1);
2313 else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2315 common = TREE_OPERAND (arg0, 0);
2316 left = TREE_OPERAND (arg0, 1);
2317 right = TREE_OPERAND (arg1, 0);
2319 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2321 common = TREE_OPERAND (arg0, 1);
2322 left = TREE_OPERAND (arg0, 0);
2323 right = TREE_OPERAND (arg1, 1);
2325 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2327 common = TREE_OPERAND (arg0, 1);
2328 left = TREE_OPERAND (arg0, 0);
2329 right = TREE_OPERAND (arg1, 0);
2334 return fold (build (TREE_CODE (arg0), type, common,
2335 fold (build (code, type, left, right))));
2338 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2339 starting at BITPOS. The field is unsigned if UNSIGNEDP is non-zero. */
2342 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2345 int bitsize, bitpos;
2348 tree result = build (BIT_FIELD_REF, type, inner,
2349 size_int (bitsize), bitsize_int (bitpos));
2351 TREE_UNSIGNED (result) = unsignedp;
2356 /* Optimize a bit-field compare.
2358 There are two cases: First is a compare against a constant and the
2359 second is a comparison of two items where the fields are at the same
2360 bit position relative to the start of a chunk (byte, halfword, word)
2361 large enough to contain it. In these cases we can avoid the shift
2362 implicit in bitfield extractions.
2364 For constants, we emit a compare of the shifted constant with the
2365 BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2366 compared. For two fields at the same position, we do the ANDs with the
2367 similar mask and compare the result of the ANDs.
2369 CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2370 COMPARE_TYPE is the type of the comparison, and LHS and RHS
2371 are the left and right operands of the comparison, respectively.
2373 If the optimization described above can be done, we return the resulting
2374 tree. Otherwise we return zero. */
2377 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2378 enum tree_code code;
2382 HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2383 tree type = TREE_TYPE (lhs);
2384 tree signed_type, unsigned_type;
2385 int const_p = TREE_CODE (rhs) == INTEGER_CST;
2386 enum machine_mode lmode, rmode, nmode;
2387 int lunsignedp, runsignedp;
2388 int lvolatilep = 0, rvolatilep = 0;
2389 tree linner, rinner = NULL_TREE;
2393 /* Get all the information about the extractions being done. If the bit size
2394 if the same as the size of the underlying object, we aren't doing an
2395 extraction at all and so can do nothing. We also don't want to
2396 do anything if the inner expression is a PLACEHOLDER_EXPR since we
2397 then will no longer be able to replace it. */
2398 linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2399 &lunsignedp, &lvolatilep);
2400 if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2401 || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2406 /* If this is not a constant, we can only do something if bit positions,
2407 sizes, and signedness are the same. */
2408 rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2409 &runsignedp, &rvolatilep);
2411 if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2412 || lunsignedp != runsignedp || offset != 0
2413 || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2417 /* See if we can find a mode to refer to this field. We should be able to,
2418 but fail if we can't. */
2419 nmode = get_best_mode (lbitsize, lbitpos,
2420 const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2421 : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2422 TYPE_ALIGN (TREE_TYPE (rinner))),
2423 word_mode, lvolatilep || rvolatilep);
2424 if (nmode == VOIDmode)
2427 /* Set signed and unsigned types of the precision of this mode for the
2429 signed_type = (*lang_hooks.types.type_for_mode) (nmode, 0);
2430 unsigned_type = (*lang_hooks.types.type_for_mode) (nmode, 1);
2432 /* Compute the bit position and size for the new reference and our offset
2433 within it. If the new reference is the same size as the original, we
2434 won't optimize anything, so return zero. */
2435 nbitsize = GET_MODE_BITSIZE (nmode);
2436 nbitpos = lbitpos & ~ (nbitsize - 1);
2438 if (nbitsize == lbitsize)
2441 if (BYTES_BIG_ENDIAN)
2442 lbitpos = nbitsize - lbitsize - lbitpos;
2444 /* Make the mask to be used against the extracted field. */
2445 mask = build_int_2 (~0, ~0);
2446 TREE_TYPE (mask) = unsigned_type;
2447 force_fit_type (mask, 0);
2448 mask = convert (unsigned_type, mask);
2449 mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2450 mask = const_binop (RSHIFT_EXPR, mask,
2451 size_int (nbitsize - lbitsize - lbitpos), 0);
2454 /* If not comparing with constant, just rework the comparison
2456 return build (code, compare_type,
2457 build (BIT_AND_EXPR, unsigned_type,
2458 make_bit_field_ref (linner, unsigned_type,
2459 nbitsize, nbitpos, 1),
2461 build (BIT_AND_EXPR, unsigned_type,
2462 make_bit_field_ref (rinner, unsigned_type,
2463 nbitsize, nbitpos, 1),
2466 /* Otherwise, we are handling the constant case. See if the constant is too
2467 big for the field. Warn and return a tree of for 0 (false) if so. We do
2468 this not only for its own sake, but to avoid having to test for this
2469 error case below. If we didn't, we might generate wrong code.
2471 For unsigned fields, the constant shifted right by the field length should
2472 be all zero. For signed fields, the high-order bits should agree with
2477 if (! integer_zerop (const_binop (RSHIFT_EXPR,
2478 convert (unsigned_type, rhs),
2479 size_int (lbitsize), 0)))
2481 warning ("comparison is always %d due to width of bit-field",
2483 return convert (compare_type,
2485 ? integer_one_node : integer_zero_node));
2490 tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2491 size_int (lbitsize - 1), 0);
2492 if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2494 warning ("comparison is always %d due to width of bit-field",
2496 return convert (compare_type,
2498 ? integer_one_node : integer_zero_node));
2502 /* Single-bit compares should always be against zero. */
2503 if (lbitsize == 1 && ! integer_zerop (rhs))
2505 code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2506 rhs = convert (type, integer_zero_node);
2509 /* Make a new bitfield reference, shift the constant over the
2510 appropriate number of bits and mask it with the computed mask
2511 (in case this was a signed field). If we changed it, make a new one. */
2512 lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2515 TREE_SIDE_EFFECTS (lhs) = 1;
2516 TREE_THIS_VOLATILE (lhs) = 1;
2519 rhs = fold (const_binop (BIT_AND_EXPR,
2520 const_binop (LSHIFT_EXPR,
2521 convert (unsigned_type, rhs),
2522 size_int (lbitpos), 0),
2525 return build (code, compare_type,
2526 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2530 /* Subroutine for fold_truthop: decode a field reference.
2532 If EXP is a comparison reference, we return the innermost reference.
2534 *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2535 set to the starting bit number.
2537 If the innermost field can be completely contained in a mode-sized
2538 unit, *PMODE is set to that mode. Otherwise, it is set to VOIDmode.
2540 *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2541 otherwise it is not changed.
2543 *PUNSIGNEDP is set to the signedness of the field.
2545 *PMASK is set to the mask used. This is either contained in a
2546 BIT_AND_EXPR or derived from the width of the field.
2548 *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2550 Return 0 if this is not a component reference or is one that we can't
2551 do anything with. */
2554 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2555 pvolatilep, pmask, pand_mask)
2557 HOST_WIDE_INT *pbitsize, *pbitpos;
2558 enum machine_mode *pmode;
2559 int *punsignedp, *pvolatilep;
2564 tree mask, inner, offset;
2566 unsigned int precision;
2568 /* All the optimizations using this function assume integer fields.
2569 There are problems with FP fields since the type_for_size call
2570 below can fail for, e.g., XFmode. */
2571 if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2576 if (TREE_CODE (exp) == BIT_AND_EXPR)
2578 and_mask = TREE_OPERAND (exp, 1);
2579 exp = TREE_OPERAND (exp, 0);
2580 STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2581 if (TREE_CODE (and_mask) != INTEGER_CST)
2585 inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2586 punsignedp, pvolatilep);
2587 if ((inner == exp && and_mask == 0)
2588 || *pbitsize < 0 || offset != 0
2589 || TREE_CODE (inner) == PLACEHOLDER_EXPR)
2592 /* Compute the mask to access the bitfield. */
2593 unsigned_type = (*lang_hooks.types.type_for_size) (*pbitsize, 1);
2594 precision = TYPE_PRECISION (unsigned_type);
2596 mask = build_int_2 (~0, ~0);
2597 TREE_TYPE (mask) = unsigned_type;
2598 force_fit_type (mask, 0);
2599 mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2600 mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2602 /* Merge it with the mask we found in the BIT_AND_EXPR, if any. */
2604 mask = fold (build (BIT_AND_EXPR, unsigned_type,
2605 convert (unsigned_type, and_mask), mask));
2608 *pand_mask = and_mask;
2612 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2616 all_ones_mask_p (mask, size)
2620 tree type = TREE_TYPE (mask);
2621 unsigned int precision = TYPE_PRECISION (type);
2624 tmask = build_int_2 (~0, ~0);
2625 TREE_TYPE (tmask) = signed_type (type);
2626 force_fit_type (tmask, 0);
2628 tree_int_cst_equal (mask,
2629 const_binop (RSHIFT_EXPR,
2630 const_binop (LSHIFT_EXPR, tmask,
2631 size_int (precision - size),
2633 size_int (precision - size), 0));
2636 /* Subroutine for fold_truthop: determine if an operand is simple enough
2637 to be evaluated unconditionally. */
2640 simple_operand_p (exp)
2643 /* Strip any conversions that don't change the machine mode. */
2644 while ((TREE_CODE (exp) == NOP_EXPR
2645 || TREE_CODE (exp) == CONVERT_EXPR)
2646 && (TYPE_MODE (TREE_TYPE (exp))
2647 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2648 exp = TREE_OPERAND (exp, 0);
2650 return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2652 && ! TREE_ADDRESSABLE (exp)
2653 && ! TREE_THIS_VOLATILE (exp)
2654 && ! DECL_NONLOCAL (exp)
2655 /* Don't regard global variables as simple. They may be
2656 allocated in ways unknown to the compiler (shared memory,
2657 #pragma weak, etc). */
2658 && ! TREE_PUBLIC (exp)
2659 && ! DECL_EXTERNAL (exp)
2660 /* Loading a static variable is unduly expensive, but global
2661 registers aren't expensive. */
2662 && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2665 /* The following functions are subroutines to fold_range_test and allow it to
2666 try to change a logical combination of comparisons into a range test.
2669 X == 2 || X == 3 || X == 4 || X == 5
2673 (unsigned) (X - 2) <= 3
2675 We describe each set of comparisons as being either inside or outside
2676 a range, using a variable named like IN_P, and then describe the
2677 range with a lower and upper bound. If one of the bounds is omitted,
2678 it represents either the highest or lowest value of the type.
2680 In the comments below, we represent a range by two numbers in brackets
2681 preceded by a "+" to designate being inside that range, or a "-" to
2682 designate being outside that range, so the condition can be inverted by
2683 flipping the prefix. An omitted bound is represented by a "-". For
2684 example, "- [-, 10]" means being outside the range starting at the lowest
2685 possible value and ending at 10, in other words, being greater than 10.
2686 The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2689 We set up things so that the missing bounds are handled in a consistent
2690 manner so neither a missing bound nor "true" and "false" need to be
2691 handled using a special case. */
2693 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2694 of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2695 and UPPER1_P are nonzero if the respective argument is an upper bound
2696 and zero for a lower. TYPE, if nonzero, is the type of the result; it
2697 must be specified for a comparison. ARG1 will be converted to ARG0's
2698 type if both are specified. */
2701 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2702 enum tree_code code;
2705 int upper0_p, upper1_p;
2711 /* If neither arg represents infinity, do the normal operation.
2712 Else, if not a comparison, return infinity. Else handle the special
2713 comparison rules. Note that most of the cases below won't occur, but
2714 are handled for consistency. */
2716 if (arg0 != 0 && arg1 != 0)
2718 tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2719 arg0, convert (TREE_TYPE (arg0), arg1)));
2721 return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2724 if (TREE_CODE_CLASS (code) != '<')
2727 /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2728 for neither. In real maths, we cannot assume open ended ranges are
2729 the same. But, this is computer arithmetic, where numbers are finite.
2730 We can therefore make the transformation of any unbounded range with
2731 the value Z, Z being greater than any representable number. This permits
2732 us to treat unbounded ranges as equal. */
2733 sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2734 sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2738 result = sgn0 == sgn1;
2741 result = sgn0 != sgn1;
2744 result = sgn0 < sgn1;
2747 result = sgn0 <= sgn1;
2750 result = sgn0 > sgn1;
2753 result = sgn0 >= sgn1;
2759 return convert (type, result ? integer_one_node : integer_zero_node);
2762 /* Given EXP, a logical expression, set the range it is testing into
2763 variables denoted by PIN_P, PLOW, and PHIGH. Return the expression
2764 actually being tested. *PLOW and *PHIGH will be made of the same type
2765 as the returned expression. If EXP is not a comparison, we will most
2766 likely not be returning a useful value and range. */
2769 make_range (exp, pin_p, plow, phigh)
2774 enum tree_code code;
2775 tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
2776 tree orig_type = NULL_TREE;
2778 tree low, high, n_low, n_high;
2780 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2781 and see if we can refine the range. Some of the cases below may not
2782 happen, but it doesn't seem worth worrying about this. We "continue"
2783 the outer loop when we've changed something; otherwise we "break"
2784 the switch, which will "break" the while. */
2786 in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2790 code = TREE_CODE (exp);
2792 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2794 arg0 = TREE_OPERAND (exp, 0);
2795 if (TREE_CODE_CLASS (code) == '<'
2796 || TREE_CODE_CLASS (code) == '1'
2797 || TREE_CODE_CLASS (code) == '2')
2798 type = TREE_TYPE (arg0);
2799 if (TREE_CODE_CLASS (code) == '2'
2800 || TREE_CODE_CLASS (code) == '<'
2801 || (TREE_CODE_CLASS (code) == 'e'
2802 && TREE_CODE_LENGTH (code) > 1))
2803 arg1 = TREE_OPERAND (exp, 1);
2806 /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
2807 lose a cast by accident. */
2808 if (type != NULL_TREE && orig_type == NULL_TREE)
2813 case TRUTH_NOT_EXPR:
2814 in_p = ! in_p, exp = arg0;
2817 case EQ_EXPR: case NE_EXPR:
2818 case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2819 /* We can only do something if the range is testing for zero
2820 and if the second operand is an integer constant. Note that
2821 saying something is "in" the range we make is done by
2822 complementing IN_P since it will set in the initial case of
2823 being not equal to zero; "out" is leaving it alone. */
2824 if (low == 0 || high == 0
2825 || ! integer_zerop (low) || ! integer_zerop (high)
2826 || TREE_CODE (arg1) != INTEGER_CST)
2831 case NE_EXPR: /* - [c, c] */
2834 case EQ_EXPR: /* + [c, c] */
2835 in_p = ! in_p, low = high = arg1;
2837 case GT_EXPR: /* - [-, c] */
2838 low = 0, high = arg1;
2840 case GE_EXPR: /* + [c, -] */
2841 in_p = ! in_p, low = arg1, high = 0;
2843 case LT_EXPR: /* - [c, -] */
2844 low = arg1, high = 0;
2846 case LE_EXPR: /* + [-, c] */
2847 in_p = ! in_p, low = 0, high = arg1;
2855 /* If this is an unsigned comparison, we also know that EXP is
2856 greater than or equal to zero. We base the range tests we make
2857 on that fact, so we record it here so we can parse existing
2859 if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2861 if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2862 1, convert (type, integer_zero_node),
2866 in_p = n_in_p, low = n_low, high = n_high;
2868 /* If the high bound is missing, but we
2869 have a low bound, reverse the range so
2870 it goes from zero to the low bound minus 1. */
2871 if (high == 0 && low)
2874 high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2875 integer_one_node, 0);
2876 low = convert (type, integer_zero_node);
2882 /* (-x) IN [a,b] -> x in [-b, -a] */
2883 n_low = range_binop (MINUS_EXPR, type,
2884 convert (type, integer_zero_node), 0, high, 1);
2885 n_high = range_binop (MINUS_EXPR, type,
2886 convert (type, integer_zero_node), 0, low, 0);
2887 low = n_low, high = n_high;
2893 exp = build (MINUS_EXPR, type, negate_expr (arg0),
2894 convert (type, integer_one_node));
2897 case PLUS_EXPR: case MINUS_EXPR:
2898 if (TREE_CODE (arg1) != INTEGER_CST)
2901 /* If EXP is signed, any overflow in the computation is undefined,
2902 so we don't worry about it so long as our computations on
2903 the bounds don't overflow. For unsigned, overflow is defined
2904 and this is exactly the right thing. */
2905 n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2906 type, low, 0, arg1, 0);
2907 n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2908 type, high, 1, arg1, 0);
2909 if ((n_low != 0 && TREE_OVERFLOW (n_low))
2910 || (n_high != 0 && TREE_OVERFLOW (n_high)))
2913 /* Check for an unsigned range which has wrapped around the maximum
2914 value thus making n_high < n_low, and normalize it. */
2915 if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
2917 low = range_binop (PLUS_EXPR, type, n_high, 0,
2918 integer_one_node, 0);
2919 high = range_binop (MINUS_EXPR, type, n_low, 0,
2920 integer_one_node, 0);
2922 /* If the range is of the form +/- [ x+1, x ], we won't
2923 be able to normalize it. But then, it represents the
2924 whole range or the empty set, so make it
2926 if (tree_int_cst_equal (n_low, low)
2927 && tree_int_cst_equal (n_high, high))
2933 low = n_low, high = n_high;
2938 case NOP_EXPR: case NON_LVALUE_EXPR: case CONVERT_EXPR:
2939 if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
2942 if (! INTEGRAL_TYPE_P (type)
2943 || (low != 0 && ! int_fits_type_p (low, type))
2944 || (high != 0 && ! int_fits_type_p (high, type)))
2947 n_low = low, n_high = high;
2950 n_low = convert (type, n_low);
2953 n_high = convert (type, n_high);
2955 /* If we're converting from an unsigned to a signed type,
2956 we will be doing the comparison as unsigned. The tests above
2957 have already verified that LOW and HIGH are both positive.
2959 So we have to make sure that the original unsigned value will
2960 be interpreted as positive. */
2961 if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
2963 tree equiv_type = (*lang_hooks.types.type_for_mode)
2964 (TYPE_MODE (type), 1);
2967 /* A range without an upper bound is, naturally, unbounded.
2968 Since convert would have cropped a very large value, use
2969 the max value for the destination type. */
2971 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
2972 : TYPE_MAX_VALUE (type);
2974 high_positive = fold (build (RSHIFT_EXPR, type,
2975 convert (type, high_positive),
2976 convert (type, integer_one_node)));
2978 /* If the low bound is specified, "and" the range with the
2979 range for which the original unsigned value will be
2983 if (! merge_ranges (&n_in_p, &n_low, &n_high,
2985 1, convert (type, integer_zero_node),
2989 in_p = (n_in_p == in_p);
2993 /* Otherwise, "or" the range with the range of the input
2994 that will be interpreted as negative. */
2995 if (! merge_ranges (&n_in_p, &n_low, &n_high,
2997 1, convert (type, integer_zero_node),
3001 in_p = (in_p != n_in_p);
3006 low = n_low, high = n_high;
3016 /* If EXP is a constant, we can evaluate whether this is true or false. */
3017 if (TREE_CODE (exp) == INTEGER_CST)
3019 in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3021 && integer_onep (range_binop (LE_EXPR, integer_type_node,
3027 *pin_p = in_p, *plow = low, *phigh = high;
3031 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3032 type, TYPE, return an expression to test if EXP is in (or out of, depending
3033 on IN_P) the range. */
3036 build_range_check (type, exp, in_p, low, high)
3042 tree etype = TREE_TYPE (exp);
3046 && (0 != (value = build_range_check (type, exp, 1, low, high))))
3047 return invert_truthvalue (value);
3049 else if (low == 0 && high == 0)
3050 return convert (type, integer_one_node);
3053 return fold (build (LE_EXPR, type, exp, high));
3056 return fold (build (GE_EXPR, type, exp, low));
3058 else if (operand_equal_p (low, high, 0))
3059 return fold (build (EQ_EXPR, type, exp, low));
3061 else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3062 return build_range_check (type, exp, 1, 0, high);
3064 else if (integer_zerop (low))
3066 utype = unsigned_type (etype);
3067 return build_range_check (type, convert (utype, exp), 1, 0,
3068 convert (utype, high));
3071 else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3072 && ! TREE_OVERFLOW (value))
3073 return build_range_check (type,
3074 fold (build (MINUS_EXPR, etype, exp, low)),
3075 1, convert (etype, integer_zero_node), value);
3080 /* Given two ranges, see if we can merge them into one. Return 1 if we
3081 can, 0 if we can't. Set the output range into the specified parameters. */
3084 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3088 tree low0, high0, low1, high1;
3096 int lowequal = ((low0 == 0 && low1 == 0)
3097 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3098 low0, 0, low1, 0)));
3099 int highequal = ((high0 == 0 && high1 == 0)
3100 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3101 high0, 1, high1, 1)));
3103 /* Make range 0 be the range that starts first, or ends last if they
3104 start at the same value. Swap them if it isn't. */
3105 if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3108 && integer_onep (range_binop (GT_EXPR, integer_type_node,
3109 high1, 1, high0, 1))))
3111 temp = in0_p, in0_p = in1_p, in1_p = temp;
3112 tem = low0, low0 = low1, low1 = tem;
3113 tem = high0, high0 = high1, high1 = tem;
3116 /* Now flag two cases, whether the ranges are disjoint or whether the
3117 second range is totally subsumed in the first. Note that the tests
3118 below are simplified by the ones above. */
3119 no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3120 high0, 1, low1, 0));
3121 subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3122 high1, 1, high0, 1));
3124 /* We now have four cases, depending on whether we are including or
3125 excluding the two ranges. */
3128 /* If they don't overlap, the result is false. If the second range
3129 is a subset it is the result. Otherwise, the range is from the start
3130 of the second to the end of the first. */
3132 in_p = 0, low = high = 0;
3134 in_p = 1, low = low1, high = high1;
3136 in_p = 1, low = low1, high = high0;
3139 else if (in0_p && ! in1_p)
3141 /* If they don't overlap, the result is the first range. If they are
3142 equal, the result is false. If the second range is a subset of the
3143 first, and the ranges begin at the same place, we go from just after
3144 the end of the first range to the end of the second. If the second
3145 range is not a subset of the first, or if it is a subset and both
3146 ranges end at the same place, the range starts at the start of the
3147 first range and ends just before the second range.
3148 Otherwise, we can't describe this as a single range. */
3150 in_p = 1, low = low0, high = high0;
3151 else if (lowequal && highequal)
3152 in_p = 0, low = high = 0;
3153 else if (subset && lowequal)
3155 in_p = 1, high = high0;
3156 low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3157 integer_one_node, 0);
3159 else if (! subset || highequal)
3161 in_p = 1, low = low0;
3162 high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3163 integer_one_node, 0);
3169 else if (! in0_p && in1_p)
3171 /* If they don't overlap, the result is the second range. If the second
3172 is a subset of the first, the result is false. Otherwise,
3173 the range starts just after the first range and ends at the
3174 end of the second. */
3176 in_p = 1, low = low1, high = high1;
3177 else if (subset || highequal)
3178 in_p = 0, low = high = 0;
3181 in_p = 1, high = high1;
3182 low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3183 integer_one_node, 0);
3189 /* The case where we are excluding both ranges. Here the complex case
3190 is if they don't overlap. In that case, the only time we have a
3191 range is if they are adjacent. If the second is a subset of the
3192 first, the result is the first. Otherwise, the range to exclude
3193 starts at the beginning of the first range and ends at the end of the
3197 if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3198 range_binop (PLUS_EXPR, NULL_TREE,
3200 integer_one_node, 1),
3202 in_p = 0, low = low0, high = high1;
3207 in_p = 0, low = low0, high = high0;
3209 in_p = 0, low = low0, high = high1;
3212 *pin_p = in_p, *plow = low, *phigh = high;
3216 /* EXP is some logical combination of boolean tests. See if we can
3217 merge it into some range test. Return the new tree if so. */
3220 fold_range_test (exp)
3223 int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3224 || TREE_CODE (exp) == TRUTH_OR_EXPR);
3225 int in0_p, in1_p, in_p;
3226 tree low0, low1, low, high0, high1, high;
3227 tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3228 tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3231 /* If this is an OR operation, invert both sides; we will invert
3232 again at the end. */
3234 in0_p = ! in0_p, in1_p = ! in1_p;
3236 /* If both expressions are the same, if we can merge the ranges, and we
3237 can build the range test, return it or it inverted. If one of the
3238 ranges is always true or always false, consider it to be the same
3239 expression as the other. */
3240 if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3241 && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3243 && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3245 : rhs != 0 ? rhs : integer_zero_node,
3247 return or_op ? invert_truthvalue (tem) : tem;
3249 /* On machines where the branch cost is expensive, if this is a
3250 short-circuited branch and the underlying object on both sides
3251 is the same, make a non-short-circuit operation. */
3252 else if (BRANCH_COST >= 2
3253 && lhs != 0 && rhs != 0
3254 && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3255 || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3256 && operand_equal_p (lhs, rhs, 0))
3258 /* If simple enough, just rewrite. Otherwise, make a SAVE_EXPR
3259 unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3260 which cases we can't do this. */
3261 if (simple_operand_p (lhs))
3262 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3263 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3264 TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3265 TREE_OPERAND (exp, 1));
3267 else if ((*lang_hooks.decls.global_bindings_p) () == 0
3268 && ! contains_placeholder_p (lhs))
3270 tree common = save_expr (lhs);
3272 if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3273 or_op ? ! in0_p : in0_p,
3275 && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3276 or_op ? ! in1_p : in1_p,
3278 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3279 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3280 TREE_TYPE (exp), lhs, rhs);
3287 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3288 bit value. Arrange things so the extra bits will be set to zero if and
3289 only if C is signed-extended to its full width. If MASK is nonzero,
3290 it is an INTEGER_CST that should be AND'ed with the extra bits. */
3293 unextend (c, p, unsignedp, mask)
3299 tree type = TREE_TYPE (c);
3300 int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3303 if (p == modesize || unsignedp)
3306 /* We work by getting just the sign bit into the low-order bit, then
3307 into the high-order bit, then sign-extend. We then XOR that value
3309 temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3310 temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3312 /* We must use a signed type in order to get an arithmetic right shift.
3313 However, we must also avoid introducing accidental overflows, so that
3314 a subsequent call to integer_zerop will work. Hence we must
3315 do the type conversion here. At this point, the constant is either
3316 zero or one, and the conversion to a signed type can never overflow.
3317 We could get an overflow if this conversion is done anywhere else. */
3318 if (TREE_UNSIGNED (type))
3319 temp = convert (signed_type (type), temp);
3321 temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3322 temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3324 temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3325 /* If necessary, convert the type back to match the type of C. */
3326 if (TREE_UNSIGNED (type))
3327 temp = convert (type, temp);
3329 return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3332 /* Find ways of folding logical expressions of LHS and RHS:
3333 Try to merge two comparisons to the same innermost item.
3334 Look for range tests like "ch >= '0' && ch <= '9'".
3335 Look for combinations of simple terms on machines with expensive branches
3336 and evaluate the RHS unconditionally.
3338 For example, if we have p->a == 2 && p->b == 4 and we can make an
3339 object large enough to span both A and B, we can do this with a comparison
3340 against the object ANDed with the a mask.
3342 If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3343 operations to do this with one comparison.
3345 We check for both normal comparisons and the BIT_AND_EXPRs made this by
3346 function and the one above.
3348 CODE is the logical operation being done. It can be TRUTH_ANDIF_EXPR,
3349 TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3351 TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3354 We return the simplified tree or 0 if no optimization is possible. */
3357 fold_truthop (code, truth_type, lhs, rhs)
3358 enum tree_code code;
3359 tree truth_type, lhs, rhs;
3361 /* If this is the "or" of two comparisons, we can do something if
3362 the comparisons are NE_EXPR. If this is the "and", we can do something
3363 if the comparisons are EQ_EXPR. I.e.,
3364 (a->b == 2 && a->c == 4) can become (a->new == NEW).
3366 WANTED_CODE is this operation code. For single bit fields, we can
3367 convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3368 comparison for one-bit fields. */
3370 enum tree_code wanted_code;
3371 enum tree_code lcode, rcode;
3372 tree ll_arg, lr_arg, rl_arg, rr_arg;
3373 tree ll_inner, lr_inner, rl_inner, rr_inner;
3374 HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3375 HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3376 HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3377 HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3378 int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3379 enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3380 enum machine_mode lnmode, rnmode;
3381 tree ll_mask, lr_mask, rl_mask, rr_mask;
3382 tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3383 tree l_const, r_const;
3384 tree lntype, rntype, result;
3385 int first_bit, end_bit;
3388 /* Start by getting the comparison codes. Fail if anything is volatile.
3389 If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3390 it were surrounded with a NE_EXPR. */
3392 if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3395 lcode = TREE_CODE (lhs);
3396 rcode = TREE_CODE (rhs);
3398 if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3399 lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3401 if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3402 rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3404 if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3407 code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3408 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3410 ll_arg = TREE_OPERAND (lhs, 0);
3411 lr_arg = TREE_OPERAND (lhs, 1);
3412 rl_arg = TREE_OPERAND (rhs, 0);
3413 rr_arg = TREE_OPERAND (rhs, 1);
3415 /* If the RHS can be evaluated unconditionally and its operands are
3416 simple, it wins to evaluate the RHS unconditionally on machines
3417 with expensive branches. In this case, this isn't a comparison
3418 that can be merged. Avoid doing this if the RHS is a floating-point
3419 comparison since those can trap. */
3421 if (BRANCH_COST >= 2
3422 && ! FLOAT_TYPE_P (TREE_TYPE (rl_arg))
3423 && simple_operand_p (rl_arg)
3424 && simple_operand_p (rr_arg))
3425 return build (code, truth_type, lhs, rhs);
3427 /* See if the comparisons can be merged. Then get all the parameters for
3430 if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3431 || (rcode != EQ_EXPR && rcode != NE_EXPR))
3435 ll_inner = decode_field_reference (ll_arg,
3436 &ll_bitsize, &ll_bitpos, &ll_mode,
3437 &ll_unsignedp, &volatilep, &ll_mask,
3439 lr_inner = decode_field_reference (lr_arg,
3440 &lr_bitsize, &lr_bitpos, &lr_mode,
3441 &lr_unsignedp, &volatilep, &lr_mask,
3443 rl_inner = decode_field_reference (rl_arg,
3444 &rl_bitsize, &rl_bitpos, &rl_mode,
3445 &rl_unsignedp, &volatilep, &rl_mask,
3447 rr_inner = decode_field_reference (rr_arg,
3448 &rr_bitsize, &rr_bitpos, &rr_mode,
3449 &rr_unsignedp, &volatilep, &rr_mask,
3452 /* It must be true that the inner operation on the lhs of each
3453 comparison must be the same if we are to be able to do anything.
3454 Then see if we have constants. If not, the same must be true for
3456 if (volatilep || ll_inner == 0 || rl_inner == 0
3457 || ! operand_equal_p (ll_inner, rl_inner, 0))
3460 if (TREE_CODE (lr_arg) == INTEGER_CST
3461 && TREE_CODE (rr_arg) == INTEGER_CST)
3462 l_const = lr_arg, r_const = rr_arg;
3463 else if (lr_inner == 0 || rr_inner == 0
3464 || ! operand_equal_p (lr_inner, rr_inner, 0))
3467 l_const = r_const = 0;
3469 /* If either comparison code is not correct for our logical operation,
3470 fail. However, we can convert a one-bit comparison against zero into
3471 the opposite comparison against that bit being set in the field. */
3473 wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3474 if (lcode != wanted_code)
3476 if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3478 /* Make the left operand unsigned, since we are only interested
3479 in the value of one bit. Otherwise we are doing the wrong
3488 /* This is analogous to the code for l_const above. */
3489 if (rcode != wanted_code)
3491 if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3500 /* See if we can find a mode that contains both fields being compared on
3501 the left. If we can't, fail. Otherwise, update all constants and masks
3502 to be relative to a field of that size. */
3503 first_bit = MIN (ll_bitpos, rl_bitpos);
3504 end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3505 lnmode = get_best_mode (end_bit - first_bit, first_bit,
3506 TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3508 if (lnmode == VOIDmode)
3511 lnbitsize = GET_MODE_BITSIZE (lnmode);
3512 lnbitpos = first_bit & ~ (lnbitsize - 1);
3513 lntype = (*lang_hooks.types.type_for_size) (lnbitsize, 1);
3514 xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3516 if (BYTES_BIG_ENDIAN)
3518 xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3519 xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3522 ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3523 size_int (xll_bitpos), 0);
3524 rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3525 size_int (xrl_bitpos), 0);
3529 l_const = convert (lntype, l_const);
3530 l_const = unextend (l_const, ll_bitsize, ll_unsignedp, ll_and_mask);
3531 l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3532 if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3533 fold (build1 (BIT_NOT_EXPR,
3537 warning ("comparison is always %d", wanted_code == NE_EXPR);
3539 return convert (truth_type,
3540 wanted_code == NE_EXPR
3541 ? integer_one_node : integer_zero_node);
3546 r_const = convert (lntype, r_const);
3547 r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3548 r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3549 if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3550 fold (build1 (BIT_NOT_EXPR,
3554 warning ("comparison is always %d", wanted_code == NE_EXPR);
3556 return convert (truth_type,
3557 wanted_code == NE_EXPR
3558 ? integer_one_node : integer_zero_node);
3562 /* If the right sides are not constant, do the same for it. Also,
3563 disallow this optimization if a size or signedness mismatch occurs
3564 between the left and right sides. */
3567 if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3568 || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3569 /* Make sure the two fields on the right
3570 correspond to the left without being swapped. */
3571 || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3574 first_bit = MIN (lr_bitpos, rr_bitpos);
3575 end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3576 rnmode = get_best_mode (end_bit - first_bit, first_bit,
3577 TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3579 if (rnmode == VOIDmode)
3582 rnbitsize = GET_MODE_BITSIZE (rnmode);
3583 rnbitpos = first_bit & ~ (rnbitsize - 1);
3584 rntype = (*lang_hooks.types.type_for_size) (rnbitsize, 1);
3585 xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3587 if (BYTES_BIG_ENDIAN)
3589 xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3590 xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3593 lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3594 size_int (xlr_bitpos), 0);
3595 rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3596 size_int (xrr_bitpos), 0);
3598 /* Make a mask that corresponds to both fields being compared.
3599 Do this for both items being compared. If the operands are the
3600 same size and the bits being compared are in the same position
3601 then we can do this by masking both and comparing the masked
3603 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3604 lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3605 if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3607 lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3608 ll_unsignedp || rl_unsignedp);
3609 if (! all_ones_mask_p (ll_mask, lnbitsize))
3610 lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3612 rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3613 lr_unsignedp || rr_unsignedp);
3614 if (! all_ones_mask_p (lr_mask, rnbitsize))
3615 rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3617 return build (wanted_code, truth_type, lhs, rhs);
3620 /* There is still another way we can do something: If both pairs of
3621 fields being compared are adjacent, we may be able to make a wider
3622 field containing them both.
3624 Note that we still must mask the lhs/rhs expressions. Furthermore,
3625 the mask must be shifted to account for the shift done by
3626 make_bit_field_ref. */
3627 if ((ll_bitsize + ll_bitpos == rl_bitpos
3628 && lr_bitsize + lr_bitpos == rr_bitpos)
3629 || (ll_bitpos == rl_bitpos + rl_bitsize
3630 && lr_bitpos == rr_bitpos + rr_bitsize))
3634 lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3635 MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3636 rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3637 MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3639 ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3640 size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3641 lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3642 size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3644 /* Convert to the smaller type before masking out unwanted bits. */
3646 if (lntype != rntype)
3648 if (lnbitsize > rnbitsize)
3650 lhs = convert (rntype, lhs);
3651 ll_mask = convert (rntype, ll_mask);
3654 else if (lnbitsize < rnbitsize)
3656 rhs = convert (lntype, rhs);
3657 lr_mask = convert (lntype, lr_mask);
3662 if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
3663 lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3665 if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
3666 rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
3668 return build (wanted_code, truth_type, lhs, rhs);
3674 /* Handle the case of comparisons with constants. If there is something in
3675 common between the masks, those bits of the constants must be the same.
3676 If not, the condition is always false. Test for this to avoid generating
3677 incorrect code below. */
3678 result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3679 if (! integer_zerop (result)
3680 && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3681 const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3683 if (wanted_code == NE_EXPR)
3685 warning ("`or' of unmatched not-equal tests is always 1");
3686 return convert (truth_type, integer_one_node);
3690 warning ("`and' of mutually exclusive equal-tests is always 0");
3691 return convert (truth_type, integer_zero_node);
3695 /* Construct the expression we will return. First get the component
3696 reference we will make. Unless the mask is all ones the width of
3697 that field, perform the mask operation. Then compare with the
3699 result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3700 ll_unsignedp || rl_unsignedp);
3702 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3703 if (! all_ones_mask_p (ll_mask, lnbitsize))
3704 result = build (BIT_AND_EXPR, lntype, result, ll_mask);
3706 return build (wanted_code, truth_type, result,
3707 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3710 /* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
3714 optimize_minmax_comparison (t)
3717 tree type = TREE_TYPE (t);
3718 tree arg0 = TREE_OPERAND (t, 0);
3719 enum tree_code op_code;
3720 tree comp_const = TREE_OPERAND (t, 1);
3722 int consts_equal, consts_lt;
3725 STRIP_SIGN_NOPS (arg0);
3727 op_code = TREE_CODE (arg0);
3728 minmax_const = TREE_OPERAND (arg0, 1);
3729 consts_equal = tree_int_cst_equal (minmax_const, comp_const);
3730 consts_lt = tree_int_cst_lt (minmax_const, comp_const);
3731 inner = TREE_OPERAND (arg0, 0);
3733 /* If something does not permit us to optimize, return the original tree. */
3734 if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
3735 || TREE_CODE (comp_const) != INTEGER_CST
3736 || TREE_CONSTANT_OVERFLOW (comp_const)
3737 || TREE_CODE (minmax_const) != INTEGER_CST
3738 || TREE_CONSTANT_OVERFLOW (minmax_const))
3741 /* Now handle all the various comparison codes. We only handle EQ_EXPR
3742 and GT_EXPR, doing the rest with recursive calls using logical
3744 switch (TREE_CODE (t))
3746 case NE_EXPR: case LT_EXPR: case LE_EXPR:
3748 invert_truthvalue (optimize_minmax_comparison (invert_truthvalue (t)));
3752 fold (build (TRUTH_ORIF_EXPR, type,
3753 optimize_minmax_comparison
3754 (build (EQ_EXPR, type, arg0, comp_const)),
3755 optimize_minmax_comparison
3756 (build (GT_EXPR, type, arg0, comp_const))));
3759 if (op_code == MAX_EXPR && consts_equal)
3760 /* MAX (X, 0) == 0 -> X <= 0 */
3761 return fold (build (LE_EXPR, type, inner, comp_const));
3763 else if (op_code == MAX_EXPR && consts_lt)
3764 /* MAX (X, 0) == 5 -> X == 5 */
3765 return fold (build (EQ_EXPR, type, inner, comp_const));
3767 else if (op_code == MAX_EXPR)
3768 /* MAX (X, 0) == -1 -> false */
3769 return omit_one_operand (type, integer_zero_node, inner);
3771 else if (consts_equal)
3772 /* MIN (X, 0) == 0 -> X >= 0 */
3773 return fold (build (GE_EXPR, type, inner, comp_const));
3776 /* MIN (X, 0) == 5 -> false */
3777 return omit_one_operand (type, integer_zero_node, inner);
3780 /* MIN (X, 0) == -1 -> X == -1 */
3781 return fold (build (EQ_EXPR, type, inner, comp_const));
3784 if (op_code == MAX_EXPR && (consts_equal || consts_lt))
3785 /* MAX (X, 0) > 0 -> X > 0
3786 MAX (X, 0) > 5 -> X > 5 */
3787 return fold (build (GT_EXPR, type, inner, comp_const));
3789 else if (op_code == MAX_EXPR)
3790 /* MAX (X, 0) > -1 -> true */
3791 return omit_one_operand (type, integer_one_node, inner);
3793 else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
3794 /* MIN (X, 0) > 0 -> false
3795 MIN (X, 0) > 5 -> false */
3796 return omit_one_operand (type, integer_zero_node, inner);
3799 /* MIN (X, 0) > -1 -> X > -1 */
3800 return fold (build (GT_EXPR, type, inner, comp_const));
3807 /* T is an integer expression that is being multiplied, divided, or taken a
3808 modulus (CODE says which and what kind of divide or modulus) by a
3809 constant C. See if we can eliminate that operation by folding it with
3810 other operations already in T. WIDE_TYPE, if non-null, is a type that
3811 should be used for the computation if wider than our type.
3813 For example, if we are dividing (X * 8) + (Y + 16) by 4, we can return
3814 (X * 2) + (Y + 4). We must, however, be assured that either the original
3815 expression would not overflow or that overflow is undefined for the type
3816 in the language in question.
3818 We also canonicalize (X + 7) * 4 into X * 4 + 28 in the hope that either
3819 the machine has a multiply-accumulate insn or that this is part of an
3820 addressing calculation.
3822 If we return a non-null expression, it is an equivalent form of the
3823 original computation, but need not be in the original type. */
3826 extract_muldiv (t, c, code, wide_type)
3829 enum tree_code code;
3832 tree type = TREE_TYPE (t);
3833 enum tree_code tcode = TREE_CODE (t);
3834 tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type))
3835 > GET_MODE_SIZE (TYPE_MODE (type)))
3836 ? wide_type : type);
3838 int same_p = tcode == code;
3839 tree op0 = NULL_TREE, op1 = NULL_TREE;
3841 /* Don't deal with constants of zero here; they confuse the code below. */
3842 if (integer_zerop (c))
3845 if (TREE_CODE_CLASS (tcode) == '1')
3846 op0 = TREE_OPERAND (t, 0);
3848 if (TREE_CODE_CLASS (tcode) == '2')
3849 op0 = TREE_OPERAND (t, 0), op1 = TREE_OPERAND (t, 1);
3851 /* Note that we need not handle conditional operations here since fold
3852 already handles those cases. So just do arithmetic here. */
3856 /* For a constant, we can always simplify if we are a multiply
3857 or (for divide and modulus) if it is a multiple of our constant. */
3858 if (code == MULT_EXPR
3859 || integer_zerop (const_binop (TRUNC_MOD_EXPR, t, c, 0)))
3860 return const_binop (code, convert (ctype, t), convert (ctype, c), 0);
3863 case CONVERT_EXPR: case NON_LVALUE_EXPR: case NOP_EXPR:
3864 /* If op0 is an expression, and is unsigned, and the type is
3865 smaller than ctype, then we cannot widen the expression. */
3866 if ((TREE_CODE_CLASS (TREE_CODE (op0)) == '<'
3867 || TREE_CODE_CLASS (TREE_CODE (op0)) == '1'
3868 || TREE_CODE_CLASS (TREE_CODE (op0)) == '2'
3869 || TREE_CODE_CLASS (TREE_CODE (op0)) == 'e')
3870 && TREE_UNSIGNED (TREE_TYPE (op0))
3871 && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3872 && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
3873 && (GET_MODE_SIZE (TYPE_MODE (ctype))
3874 > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
3877 /* Pass the constant down and see if we can make a simplification. If
3878 we can, replace this expression with the inner simplification for
3879 possible later conversion to our or some other type. */
3880 if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
3881 code == MULT_EXPR ? ctype : NULL_TREE)))
3885 case NEGATE_EXPR: case ABS_EXPR:
3886 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
3887 return fold (build1 (tcode, ctype, convert (ctype, t1)));
3890 case MIN_EXPR: case MAX_EXPR:
3891 /* If widening the type changes the signedness, then we can't perform
3892 this optimization as that changes the result. */
3893 if (TREE_UNSIGNED (ctype) != TREE_UNSIGNED (type))
3896 /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
3897 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
3898 && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
3900 if (tree_int_cst_sgn (c) < 0)
3901 tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
3903 return fold (build (tcode, ctype, convert (ctype, t1),
3904 convert (ctype, t2)));
3908 case WITH_RECORD_EXPR:
3909 if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
3910 return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
3911 TREE_OPERAND (t, 1));
3915 /* If this has not been evaluated and the operand has no side effects,
3916 we can see if we can do something inside it and make a new one.
3917 Note that this test is overly conservative since we can do this
3918 if the only reason it had side effects is that it was another
3919 similar SAVE_EXPR, but that isn't worth bothering with. */
3920 if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
3921 && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
3924 t1 = save_expr (t1);
3925 if (SAVE_EXPR_PERSISTENT_P (t) && TREE_CODE (t1) == SAVE_EXPR)
3926 SAVE_EXPR_PERSISTENT_P (t1) = 1;
3927 if (is_pending_size (t))
3928 put_pending_size (t1);
3933 case LSHIFT_EXPR: case RSHIFT_EXPR:
3934 /* If the second operand is constant, this is a multiplication
3935 or floor division, by a power of two, so we can treat it that
3936 way unless the multiplier or divisor overflows. */
3937 if (TREE_CODE (op1) == INTEGER_CST
3938 /* const_binop may not detect overflow correctly,
3939 so check for it explicitly here. */
3940 && TYPE_PRECISION (TREE_TYPE (size_one_node)) > TREE_INT_CST_LOW (op1)
3941 && TREE_INT_CST_HIGH (op1) == 0
3942 && 0 != (t1 = convert (ctype,
3943 const_binop (LSHIFT_EXPR, size_one_node,
3945 && ! TREE_OVERFLOW (t1))
3946 return extract_muldiv (build (tcode == LSHIFT_EXPR
3947 ? MULT_EXPR : FLOOR_DIV_EXPR,
3948 ctype, convert (ctype, op0), t1),
3949 c, code, wide_type);
3952 case PLUS_EXPR: case MINUS_EXPR:
3953 /* See if we can eliminate the operation on both sides. If we can, we
3954 can return a new PLUS or MINUS. If we can't, the only remaining
3955 cases where we can do anything are if the second operand is a
3957 t1 = extract_muldiv (op0, c, code, wide_type);
3958 t2 = extract_muldiv (op1, c, code, wide_type);
3959 if (t1 != 0 && t2 != 0
3960 && (code == MULT_EXPR
3961 /* If not multiplication, we can only do this if either operand
3962 is divisible by c. */
3963 || multiple_of_p (ctype, op0, c)
3964 || multiple_of_p (ctype, op1, c)))
3965 return fold (build (tcode, ctype, convert (ctype, t1),
3966 convert (ctype, t2)));
3968 /* If this was a subtraction, negate OP1 and set it to be an addition.
3969 This simplifies the logic below. */
3970 if (tcode == MINUS_EXPR)
3971 tcode = PLUS_EXPR, op1 = negate_expr (op1);
3973 if (TREE_CODE (op1) != INTEGER_CST)
3976 /* If either OP1 or C are negative, this optimization is not safe for
3977 some of the division and remainder types while for others we need
3978 to change the code. */
3979 if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
3981 if (code == CEIL_DIV_EXPR)
3982 code = FLOOR_DIV_EXPR;
3983 else if (code == FLOOR_DIV_EXPR)
3984 code = CEIL_DIV_EXPR;
3985 else if (code != MULT_EXPR
3986 && code != CEIL_MOD_EXPR && code != FLOOR_MOD_EXPR)
3990 /* If it's a multiply or a division/modulus operation of a multiple
3991 of our constant, do the operation and verify it doesn't overflow. */
3992 if (code == MULT_EXPR
3993 || integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
3995 op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
3996 if (op1 == 0 || TREE_OVERFLOW (op1))
4002 /* If we have an unsigned type is not a sizetype, we cannot widen
4003 the operation since it will change the result if the original
4004 computation overflowed. */
4005 if (TREE_UNSIGNED (ctype)
4006 && ! (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))
4010 /* If we were able to eliminate our operation from the first side,
4011 apply our operation to the second side and reform the PLUS. */
4012 if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
4013 return fold (build (tcode, ctype, convert (ctype, t1), op1));
4015 /* The last case is if we are a multiply. In that case, we can
4016 apply the distributive law to commute the multiply and addition
4017 if the multiplication of the constants doesn't overflow. */
4018 if (code == MULT_EXPR)
4019 return fold (build (tcode, ctype, fold (build (code, ctype,
4020 convert (ctype, op0),
4021 convert (ctype, c))),
4027 /* We have a special case here if we are doing something like
4028 (C * 8) % 4 since we know that's zero. */
4029 if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
4030 || code == FLOOR_MOD_EXPR || code == ROUND_MOD_EXPR)
4031 && TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
4032 && integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4033 return omit_one_operand (type, integer_zero_node, op0);
4035 /* ... fall through ... */
4037 case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR:
4038 case ROUND_DIV_EXPR: case EXACT_DIV_EXPR:
4039 /* If we can extract our operation from the LHS, do so and return a
4040 new operation. Likewise for the RHS from a MULT_EXPR. Otherwise,
4041 do something only if the second operand is a constant. */
4043 && (t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4044 return fold (build (tcode, ctype, convert (ctype, t1),
4045 convert (ctype, op1)));
4046 else if (tcode == MULT_EXPR && code == MULT_EXPR
4047 && (t1 = extract_muldiv (op1, c, code, wide_type)) != 0)
4048 return fold (build (tcode, ctype, convert (ctype, op0),
4049 convert (ctype, t1)));
4050 else if (TREE_CODE (op1) != INTEGER_CST)
4053 /* If these are the same operation types, we can associate them
4054 assuming no overflow. */
4056 && 0 != (t1 = const_binop (MULT_EXPR, convert (ctype, op1),
4057 convert (ctype, c), 0))
4058 && ! TREE_OVERFLOW (t1))
4059 return fold (build (tcode, ctype, convert (ctype, op0), t1));
4061 /* If these operations "cancel" each other, we have the main
4062 optimizations of this pass, which occur when either constant is a
4063 multiple of the other, in which case we replace this with either an
4064 operation or CODE or TCODE.
4066 If we have an unsigned type that is not a sizetype, we cannot do
4067 this since it will change the result if the original computation
4069 if ((! TREE_UNSIGNED (ctype)
4070 || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
4071 && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR)
4072 || (tcode == MULT_EXPR
4073 && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR
4074 && code != FLOOR_MOD_EXPR && code != ROUND_MOD_EXPR)))
4076 if (integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4077 return fold (build (tcode, ctype, convert (ctype, op0),
4079 const_binop (TRUNC_DIV_EXPR,
4081 else if (integer_zerop (const_binop (TRUNC_MOD_EXPR, c, op1, 0)))
4082 return fold (build (code, ctype, convert (ctype, op0),
4084 const_binop (TRUNC_DIV_EXPR,
4096 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4097 S, a SAVE_EXPR, return the expression actually being evaluated. Note
4098 that we may sometimes modify the tree. */
4101 strip_compound_expr (t, s)
4105 enum tree_code code = TREE_CODE (t);
4107 /* See if this is the COMPOUND_EXPR we want to eliminate. */
4108 if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4109 && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4110 return TREE_OPERAND (t, 1);
4112 /* See if this is a COND_EXPR or a simple arithmetic operator. We
4113 don't bother handling any other types. */
4114 else if (code == COND_EXPR)
4116 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4117 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4118 TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4120 else if (TREE_CODE_CLASS (code) == '1')
4121 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4122 else if (TREE_CODE_CLASS (code) == '<'
4123 || TREE_CODE_CLASS (code) == '2')
4125 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4126 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4132 /* Return a node which has the indicated constant VALUE (either 0 or
4133 1), and is of the indicated TYPE. */
4136 constant_boolean_node (value, type)
4140 if (type == integer_type_node)
4141 return value ? integer_one_node : integer_zero_node;
4142 else if (TREE_CODE (type) == BOOLEAN_TYPE)
4143 return truthvalue_conversion (value ? integer_one_node :
4147 tree t = build_int_2 (value, 0);
4149 TREE_TYPE (t) = type;
4154 /* Utility function for the following routine, to see how complex a nesting of
4155 COND_EXPRs can be. EXPR is the expression and LIMIT is a count beyond which
4156 we don't care (to avoid spending too much time on complex expressions.). */
4159 count_cond (expr, lim)
4165 if (TREE_CODE (expr) != COND_EXPR)
4170 ctrue = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4171 cfalse = count_cond (TREE_OPERAND (expr, 2), lim - 1 - ctrue);
4172 return MIN (lim, 1 + ctrue + cfalse);
4175 /* Transform `a + (b ? x : y)' into `x ? (a + b) : (a + y)'.
4176 Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
4177 CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
4178 expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
4179 COND is the first argument to CODE; otherwise (as in the example
4180 given here), it is the second argument. TYPE is the type of the
4181 original expression. */
4184 fold_binary_op_with_conditional_arg (code, type, cond, arg, cond_first_p)
4185 enum tree_code code;
4191 tree test, true_value, false_value;
4192 tree lhs = NULL_TREE;
4193 tree rhs = NULL_TREE;
4194 /* In the end, we'll produce a COND_EXPR. Both arms of the
4195 conditional expression will be binary operations. The left-hand
4196 side of the expression to be executed if the condition is true
4197 will be pointed to by TRUE_LHS. Similarly, the right-hand side
4198 of the expression to be executed if the condition is true will be
4199 pointed to by TRUE_RHS. FALSE_LHS and FALSE_RHS are analogous --
4200 but apply to the expression to be executed if the conditional is
4206 /* These are the codes to use for the left-hand side and right-hand
4207 side of the COND_EXPR. Normally, they are the same as CODE. */
4208 enum tree_code lhs_code = code;
4209 enum tree_code rhs_code = code;
4210 /* And these are the types of the expressions. */
4211 tree lhs_type = type;
4212 tree rhs_type = type;
4216 true_rhs = false_rhs = &arg;
4217 true_lhs = &true_value;
4218 false_lhs = &false_value;
4222 true_lhs = false_lhs = &arg;
4223 true_rhs = &true_value;
4224 false_rhs = &false_value;
4227 if (TREE_CODE (cond) == COND_EXPR)
4229 test = TREE_OPERAND (cond, 0);
4230 true_value = TREE_OPERAND (cond, 1);
4231 false_value = TREE_OPERAND (cond, 2);
4232 /* If this operand throws an expression, then it does not make
4233 sense to try to perform a logical or arithmetic operation
4234 involving it. Instead of building `a + throw 3' for example,
4235 we simply build `a, throw 3'. */
4236 if (VOID_TYPE_P (TREE_TYPE (true_value)))
4238 lhs_code = COMPOUND_EXPR;
4240 lhs_type = void_type_node;
4242 if (VOID_TYPE_P (TREE_TYPE (false_value)))
4244 rhs_code = COMPOUND_EXPR;
4246 rhs_type = void_type_node;
4251 tree testtype = TREE_TYPE (cond);
4253 true_value = convert (testtype, integer_one_node);
4254 false_value = convert (testtype, integer_zero_node);
4257 /* If ARG is complex we want to make sure we only evaluate
4258 it once. Though this is only required if it is volatile, it
4259 might be more efficient even if it is not. However, if we
4260 succeed in folding one part to a constant, we do not need
4261 to make this SAVE_EXPR. Since we do this optimization
4262 primarily to see if we do end up with constant and this
4263 SAVE_EXPR interferes with later optimizations, suppressing
4264 it when we can is important.
4266 If we are not in a function, we can't make a SAVE_EXPR, so don't
4267 try to do so. Don't try to see if the result is a constant
4268 if an arm is a COND_EXPR since we get exponential behavior
4271 if (TREE_CODE (arg) != SAVE_EXPR && ! TREE_CONSTANT (arg)
4272 && (*lang_hooks.decls.global_bindings_p) () == 0
4273 && ((TREE_CODE (arg) != VAR_DECL
4274 && TREE_CODE (arg) != PARM_DECL)
4275 || TREE_SIDE_EFFECTS (arg)))
4277 if (TREE_CODE (true_value) != COND_EXPR)
4278 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4280 if (TREE_CODE (false_value) != COND_EXPR)
4281 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4283 if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4284 && (rhs == 0 || !TREE_CONSTANT (rhs)))
4285 arg = save_expr (arg), lhs = rhs = 0;
4289 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4291 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4293 test = fold (build (COND_EXPR, type, test, lhs, rhs));
4295 if (TREE_CODE (arg) == SAVE_EXPR)
4296 return build (COMPOUND_EXPR, type,
4297 convert (void_type_node, arg),
4298 strip_compound_expr (test, arg));
4300 return convert (type, test);
4304 /* Subroutine of fold() that checks for the addition of +/- 0.0.
4306 If !NEGATE, return true if ADDEND is +/-0.0 and, for all X of type
4307 TYPE, X + ADDEND is the same as X. If NEGATE, return true if X -
4308 ADDEND is the same as X.
4310 X + 0 and X - 0 both give X when X is NaN, infinite, or non-zero
4311 and finite. The problematic cases are when X is zero, and its mode
4312 has signed zeros. In the case of rounding towards -infinity,
4313 X - 0 is not the same as X because 0 - 0 is -0. In other rounding
4314 modes, X + 0 is not the same as X because -0 + 0 is 0. */
4317 fold_real_zero_addition_p (type, addend, negate)
4321 if (!real_zerop (addend))
4324 /* Allow the fold if zeros aren't signed, or their sign isn't important. */
4325 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
4328 /* Treat x + -0 as x - 0 and x - -0 as x + 0. */
4329 if (TREE_CODE (addend) == REAL_CST
4330 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (addend)))
4333 /* The mode has signed zeros, and we have to honor their sign.
4334 In this situation, there is only one case we can return true for.
4335 X - 0 is the same as X unless rounding towards -infinity is
4337 return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
4341 /* Perform constant folding and related simplification of EXPR.
4342 The related simplifications include x*1 => x, x*0 => 0, etc.,
4343 and application of the associative law.
4344 NOP_EXPR conversions may be removed freely (as long as we
4345 are careful not to change the C type of the overall expression)
4346 We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4347 but we can constant-fold them if they have constant operands. */
4354 tree t1 = NULL_TREE;
4356 tree type = TREE_TYPE (expr);
4357 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4358 enum tree_code code = TREE_CODE (t);
4359 int kind = TREE_CODE_CLASS (code);
4361 /* WINS will be nonzero when the switch is done
4362 if all operands are constant. */
4365 /* Don't try to process an RTL_EXPR since its operands aren't trees.
4366 Likewise for a SAVE_EXPR that's already been evaluated. */
4367 if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t) != 0))
4370 /* Return right away if a constant. */
4374 #ifdef MAX_INTEGER_COMPUTATION_MODE
4375 check_max_integer_computation_mode (expr);
4378 if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4382 /* Special case for conversion ops that can have fixed point args. */
4383 arg0 = TREE_OPERAND (t, 0);
4385 /* Don't use STRIP_NOPS, because signedness of argument type matters. */
4387 STRIP_SIGN_NOPS (arg0);
4389 if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4390 subop = TREE_REALPART (arg0);
4394 if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4395 && TREE_CODE (subop) != REAL_CST
4397 /* Note that TREE_CONSTANT isn't enough:
4398 static var addresses are constant but we can't
4399 do arithmetic on them. */
4402 else if (IS_EXPR_CODE_CLASS (kind) || kind == 'r')
4404 int len = first_rtl_op (code);
4406 for (i = 0; i < len; i++)
4408 tree op = TREE_OPERAND (t, i);
4412 continue; /* Valid for CALL_EXPR, at least. */
4414 if (kind == '<' || code == RSHIFT_EXPR)
4416 /* Signedness matters here. Perhaps we can refine this
4418 STRIP_SIGN_NOPS (op);
4421 /* Strip any conversions that don't change the mode. */
4424 if (TREE_CODE (op) == COMPLEX_CST)
4425 subop = TREE_REALPART (op);
4429 if (TREE_CODE (subop) != INTEGER_CST
4430 && TREE_CODE (subop) != REAL_CST)
4431 /* Note that TREE_CONSTANT isn't enough:
4432 static var addresses are constant but we can't
4433 do arithmetic on them. */
4443 /* If this is a commutative operation, and ARG0 is a constant, move it
4444 to ARG1 to reduce the number of tests below. */
4445 if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4446 || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4447 || code == BIT_AND_EXPR)
4448 && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4450 tem = arg0; arg0 = arg1; arg1 = tem;
4452 tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4453 TREE_OPERAND (t, 1) = tem;
4456 /* Now WINS is set as described above,
4457 ARG0 is the first operand of EXPR,
4458 and ARG1 is the second operand (if it has more than one operand).
4460 First check for cases where an arithmetic operation is applied to a
4461 compound, conditional, or comparison operation. Push the arithmetic
4462 operation inside the compound or conditional to see if any folding
4463 can then be done. Convert comparison to conditional for this purpose.
4464 The also optimizes non-constant cases that used to be done in
4467 Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
4468 one of the operands is a comparison and the other is a comparison, a
4469 BIT_AND_EXPR with the constant 1, or a truth value. In that case, the
4470 code below would make the expression more complex. Change it to a
4471 TRUTH_{AND,OR}_EXPR. Likewise, convert a similar NE_EXPR to
4472 TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR. */
4474 if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4475 || code == EQ_EXPR || code == NE_EXPR)
4476 && ((truth_value_p (TREE_CODE (arg0))
4477 && (truth_value_p (TREE_CODE (arg1))
4478 || (TREE_CODE (arg1) == BIT_AND_EXPR
4479 && integer_onep (TREE_OPERAND (arg1, 1)))))
4480 || (truth_value_p (TREE_CODE (arg1))
4481 && (truth_value_p (TREE_CODE (arg0))
4482 || (TREE_CODE (arg0) == BIT_AND_EXPR
4483 && integer_onep (TREE_OPERAND (arg0, 1)))))))
4485 t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4486 : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4490 if (code == EQ_EXPR)
4491 t = invert_truthvalue (t);
4496 if (TREE_CODE_CLASS (code) == '1')
4498 if (TREE_CODE (arg0) == COMPOUND_EXPR)
4499 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4500 fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4501 else if (TREE_CODE (arg0) == COND_EXPR)
4503 t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4504 fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4505 fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4507 /* If this was a conversion, and all we did was to move into
4508 inside the COND_EXPR, bring it back out. But leave it if
4509 it is a conversion from integer to integer and the
4510 result precision is no wider than a word since such a
4511 conversion is cheap and may be optimized away by combine,
4512 while it couldn't if it were outside the COND_EXPR. Then return
4513 so we don't get into an infinite recursion loop taking the
4514 conversion out and then back in. */
4516 if ((code == NOP_EXPR || code == CONVERT_EXPR
4517 || code == NON_LVALUE_EXPR)
4518 && TREE_CODE (t) == COND_EXPR
4519 && TREE_CODE (TREE_OPERAND (t, 1)) == code
4520 && TREE_CODE (TREE_OPERAND (t, 2)) == code
4521 && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4522 == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4523 && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4525 (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))))
4526 && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4527 t = build1 (code, type,
4529 TREE_TYPE (TREE_OPERAND
4530 (TREE_OPERAND (t, 1), 0)),
4531 TREE_OPERAND (t, 0),
4532 TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4533 TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4536 else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4537 return fold (build (COND_EXPR, type, arg0,
4538 fold (build1 (code, type, integer_one_node)),
4539 fold (build1 (code, type, integer_zero_node))));
4541 else if (TREE_CODE_CLASS (code) == '2'
4542 || TREE_CODE_CLASS (code) == '<')
4544 if (TREE_CODE (arg1) == COMPOUND_EXPR)
4545 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4546 fold (build (code, type,
4547 arg0, TREE_OPERAND (arg1, 1))));
4548 else if ((TREE_CODE (arg1) == COND_EXPR
4549 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4550 && TREE_CODE_CLASS (code) != '<'))
4551 && (TREE_CODE (arg0) != COND_EXPR
4552 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4553 && (! TREE_SIDE_EFFECTS (arg0)
4554 || ((*lang_hooks.decls.global_bindings_p) () == 0
4555 && ! contains_placeholder_p (arg0))))
4557 fold_binary_op_with_conditional_arg (code, type, arg1, arg0,
4558 /*cond_first_p=*/0);
4559 else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4560 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4561 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4562 else if ((TREE_CODE (arg0) == COND_EXPR
4563 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4564 && TREE_CODE_CLASS (code) != '<'))
4565 && (TREE_CODE (arg1) != COND_EXPR
4566 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4567 && (! TREE_SIDE_EFFECTS (arg1)
4568 || ((*lang_hooks.decls.global_bindings_p) () == 0
4569 && ! contains_placeholder_p (arg1))))
4571 fold_binary_op_with_conditional_arg (code, type, arg0, arg1,
4572 /*cond_first_p=*/1);
4574 else if (TREE_CODE_CLASS (code) == '<'
4575 && TREE_CODE (arg0) == COMPOUND_EXPR)
4576 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4577 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4578 else if (TREE_CODE_CLASS (code) == '<'
4579 && TREE_CODE (arg1) == COMPOUND_EXPR)
4580 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4581 fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4594 return fold (DECL_INITIAL (t));
4599 case FIX_TRUNC_EXPR:
4600 /* Other kinds of FIX are not handled properly by fold_convert. */
4602 if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4603 return TREE_OPERAND (t, 0);
4605 /* Handle cases of two conversions in a row. */
4606 if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4607 || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4609 tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4610 tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4611 tree final_type = TREE_TYPE (t);
4612 int inside_int = INTEGRAL_TYPE_P (inside_type);
4613 int inside_ptr = POINTER_TYPE_P (inside_type);
4614 int inside_float = FLOAT_TYPE_P (inside_type);
4615 unsigned int inside_prec = TYPE_PRECISION (inside_type);
4616 int inside_unsignedp = TREE_UNSIGNED (inside_type);
4617 int inter_int = INTEGRAL_TYPE_P (inter_type);
4618 int inter_ptr = POINTER_TYPE_P (inter_type);
4619 int inter_float = FLOAT_TYPE_P (inter_type);
4620 unsigned int inter_prec = TYPE_PRECISION (inter_type);
4621 int inter_unsignedp = TREE_UNSIGNED (inter_type);
4622 int final_int = INTEGRAL_TYPE_P (final_type);
4623 int final_ptr = POINTER_TYPE_P (final_type);
4624 int final_float = FLOAT_TYPE_P (final_type);
4625 unsigned int final_prec = TYPE_PRECISION (final_type);
4626 int final_unsignedp = TREE_UNSIGNED (final_type);
4628 /* In addition to the cases of two conversions in a row
4629 handled below, if we are converting something to its own
4630 type via an object of identical or wider precision, neither
4631 conversion is needed. */
4632 if (TYPE_MAIN_VARIANT (inside_type) == TYPE_MAIN_VARIANT (final_type)
4633 && ((inter_int && final_int) || (inter_float && final_float))
4634 && inter_prec >= final_prec)
4635 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4637 /* Likewise, if the intermediate and final types are either both
4638 float or both integer, we don't need the middle conversion if
4639 it is wider than the final type and doesn't change the signedness
4640 (for integers). Avoid this if the final type is a pointer
4641 since then we sometimes need the inner conversion. Likewise if
4642 the outer has a precision not equal to the size of its mode. */
4643 if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4644 || (inter_float && inside_float))
4645 && inter_prec >= inside_prec
4646 && (inter_float || inter_unsignedp == inside_unsignedp)
4647 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4648 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4650 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4652 /* If we have a sign-extension of a zero-extended value, we can
4653 replace that by a single zero-extension. */
4654 if (inside_int && inter_int && final_int
4655 && inside_prec < inter_prec && inter_prec < final_prec
4656 && inside_unsignedp && !inter_unsignedp)
4657 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4659 /* Two conversions in a row are not needed unless:
4660 - some conversion is floating-point (overstrict for now), or
4661 - the intermediate type is narrower than both initial and
4663 - the intermediate type and innermost type differ in signedness,
4664 and the outermost type is wider than the intermediate, or
4665 - the initial type is a pointer type and the precisions of the
4666 intermediate and final types differ, or
4667 - the final type is a pointer type and the precisions of the
4668 initial and intermediate types differ. */
4669 if (! inside_float && ! inter_float && ! final_float
4670 && (inter_prec > inside_prec || inter_prec > final_prec)
4671 && ! (inside_int && inter_int
4672 && inter_unsignedp != inside_unsignedp
4673 && inter_prec < final_prec)
4674 && ((inter_unsignedp && inter_prec > inside_prec)
4675 == (final_unsignedp && final_prec > inter_prec))
4676 && ! (inside_ptr && inter_prec != final_prec)
4677 && ! (final_ptr && inside_prec != inter_prec)
4678 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4679 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4681 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4684 if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4685 && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4686 /* Detect assigning a bitfield. */
4687 && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4688 && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4690 /* Don't leave an assignment inside a conversion
4691 unless assigning a bitfield. */
4692 tree prev = TREE_OPERAND (t, 0);
4693 TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4694 /* First do the assignment, then return converted constant. */
4695 t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4701 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4704 return fold_convert (t, arg0);
4706 case VIEW_CONVERT_EXPR:
4707 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4708 return build1 (VIEW_CONVERT_EXPR, type,
4709 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4713 if (TREE_CODE (arg0) == CONSTRUCTOR)
4715 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4722 TREE_CONSTANT (t) = wins;
4728 if (TREE_CODE (arg0) == INTEGER_CST)
4730 unsigned HOST_WIDE_INT low;
4732 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4733 TREE_INT_CST_HIGH (arg0),
4735 t = build_int_2 (low, high);
4736 TREE_TYPE (t) = type;
4738 = (TREE_OVERFLOW (arg0)
4739 | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4740 TREE_CONSTANT_OVERFLOW (t)
4741 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4743 else if (TREE_CODE (arg0) == REAL_CST)
4744 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4746 else if (TREE_CODE (arg0) == NEGATE_EXPR)
4747 return TREE_OPERAND (arg0, 0);
4749 /* Convert - (a - b) to (b - a) for non-floating-point. */
4750 else if (TREE_CODE (arg0) == MINUS_EXPR
4751 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
4752 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4753 TREE_OPERAND (arg0, 0));
4760 if (TREE_CODE (arg0) == INTEGER_CST)
4762 /* If the value is unsigned, then the absolute value is
4763 the same as the ordinary value. */
4764 if (TREE_UNSIGNED (type))
4766 /* Similarly, if the value is non-negative. */
4767 else if (INT_CST_LT (integer_minus_one_node, arg0))
4769 /* If the value is negative, then the absolute value is
4773 unsigned HOST_WIDE_INT low;
4775 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4776 TREE_INT_CST_HIGH (arg0),
4778 t = build_int_2 (low, high);
4779 TREE_TYPE (t) = type;
4781 = (TREE_OVERFLOW (arg0)
4782 | force_fit_type (t, overflow));
4783 TREE_CONSTANT_OVERFLOW (t)
4784 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4787 else if (TREE_CODE (arg0) == REAL_CST)
4789 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4790 t = build_real (type,
4791 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4794 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4795 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4799 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4800 return convert (type, arg0);
4801 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4802 return build (COMPLEX_EXPR, type,
4803 TREE_OPERAND (arg0, 0),
4804 negate_expr (TREE_OPERAND (arg0, 1)));
4805 else if (TREE_CODE (arg0) == COMPLEX_CST)
4806 return build_complex (type, TREE_REALPART (arg0),
4807 negate_expr (TREE_IMAGPART (arg0)));
4808 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4809 return fold (build (TREE_CODE (arg0), type,
4810 fold (build1 (CONJ_EXPR, type,
4811 TREE_OPERAND (arg0, 0))),
4812 fold (build1 (CONJ_EXPR,
4813 type, TREE_OPERAND (arg0, 1)))));
4814 else if (TREE_CODE (arg0) == CONJ_EXPR)
4815 return TREE_OPERAND (arg0, 0);
4821 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4822 ~ TREE_INT_CST_HIGH (arg0));
4823 TREE_TYPE (t) = type;
4824 force_fit_type (t, 0);
4825 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4826 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4828 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4829 return TREE_OPERAND (arg0, 0);
4833 /* A + (-B) -> A - B */
4834 if (TREE_CODE (arg1) == NEGATE_EXPR)
4835 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4836 /* (-A) + B -> B - A */
4837 if (TREE_CODE (arg0) == NEGATE_EXPR)
4838 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
4839 else if (! FLOAT_TYPE_P (type))
4841 if (integer_zerop (arg1))
4842 return non_lvalue (convert (type, arg0));
4844 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4845 with a constant, and the two constants have no bits in common,
4846 we should treat this as a BIT_IOR_EXPR since this may produce more
4848 if (TREE_CODE (arg0) == BIT_AND_EXPR
4849 && TREE_CODE (arg1) == BIT_AND_EXPR
4850 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4851 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4852 && integer_zerop (const_binop (BIT_AND_EXPR,
4853 TREE_OPERAND (arg0, 1),
4854 TREE_OPERAND (arg1, 1), 0)))
4856 code = BIT_IOR_EXPR;
4860 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4861 (plus (plus (mult) (mult)) (foo)) so that we can
4862 take advantage of the factoring cases below. */
4863 if ((TREE_CODE (arg0) == PLUS_EXPR
4864 && TREE_CODE (arg1) == MULT_EXPR)
4865 || (TREE_CODE (arg1) == PLUS_EXPR
4866 && TREE_CODE (arg0) == MULT_EXPR))
4868 tree parg0, parg1, parg, marg;
4870 if (TREE_CODE (arg0) == PLUS_EXPR)
4871 parg = arg0, marg = arg1;
4873 parg = arg1, marg = arg0;
4874 parg0 = TREE_OPERAND (parg, 0);
4875 parg1 = TREE_OPERAND (parg, 1);
4879 if (TREE_CODE (parg0) == MULT_EXPR
4880 && TREE_CODE (parg1) != MULT_EXPR)
4881 return fold (build (PLUS_EXPR, type,
4882 fold (build (PLUS_EXPR, type, parg0, marg)),
4884 if (TREE_CODE (parg0) != MULT_EXPR
4885 && TREE_CODE (parg1) == MULT_EXPR)
4886 return fold (build (PLUS_EXPR, type,
4887 fold (build (PLUS_EXPR, type, parg1, marg)),
4891 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4893 tree arg00, arg01, arg10, arg11;
4894 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
4896 /* (A * C) + (B * C) -> (A+B) * C.
4897 We are most concerned about the case where C is a constant,
4898 but other combinations show up during loop reduction. Since
4899 it is not difficult, try all four possibilities. */
4901 arg00 = TREE_OPERAND (arg0, 0);
4902 arg01 = TREE_OPERAND (arg0, 1);
4903 arg10 = TREE_OPERAND (arg1, 0);
4904 arg11 = TREE_OPERAND (arg1, 1);
4907 if (operand_equal_p (arg01, arg11, 0))
4908 same = arg01, alt0 = arg00, alt1 = arg10;
4909 else if (operand_equal_p (arg00, arg10, 0))
4910 same = arg00, alt0 = arg01, alt1 = arg11;
4911 else if (operand_equal_p (arg00, arg11, 0))
4912 same = arg00, alt0 = arg01, alt1 = arg10;
4913 else if (operand_equal_p (arg01, arg10, 0))
4914 same = arg01, alt0 = arg00, alt1 = arg11;
4916 /* No identical multiplicands; see if we can find a common
4917 power-of-two factor in non-power-of-two multiplies. This
4918 can help in multi-dimensional array access. */
4919 else if (TREE_CODE (arg01) == INTEGER_CST
4920 && TREE_CODE (arg11) == INTEGER_CST
4921 && TREE_INT_CST_HIGH (arg01) == 0
4922 && TREE_INT_CST_HIGH (arg11) == 0)
4924 HOST_WIDE_INT int01, int11, tmp;
4925 int01 = TREE_INT_CST_LOW (arg01);
4926 int11 = TREE_INT_CST_LOW (arg11);
4928 /* Move min of absolute values to int11. */
4929 if ((int01 >= 0 ? int01 : -int01)
4930 < (int11 >= 0 ? int11 : -int11))
4932 tmp = int01, int01 = int11, int11 = tmp;
4933 alt0 = arg00, arg00 = arg10, arg10 = alt0;
4934 alt0 = arg01, arg01 = arg11, arg11 = alt0;
4937 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
4939 alt0 = fold (build (MULT_EXPR, type, arg00,
4940 build_int_2 (int01 / int11, 0)));
4947 return fold (build (MULT_EXPR, type,
4948 fold (build (PLUS_EXPR, type, alt0, alt1)),
4953 /* See if ARG1 is zero and X + ARG1 reduces to X. */
4954 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
4955 return non_lvalue (convert (type, arg0));
4957 /* Likewise if the operands are reversed. */
4958 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
4959 return non_lvalue (convert (type, arg1));
4962 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
4963 is a rotate of A by C1 bits. */
4964 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
4965 is a rotate of A by B bits. */
4967 enum tree_code code0, code1;
4968 code0 = TREE_CODE (arg0);
4969 code1 = TREE_CODE (arg1);
4970 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4971 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4972 && operand_equal_p (TREE_OPERAND (arg0, 0),
4973 TREE_OPERAND (arg1, 0), 0)
4974 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4976 tree tree01, tree11;
4977 enum tree_code code01, code11;
4979 tree01 = TREE_OPERAND (arg0, 1);
4980 tree11 = TREE_OPERAND (arg1, 1);
4981 STRIP_NOPS (tree01);
4982 STRIP_NOPS (tree11);
4983 code01 = TREE_CODE (tree01);
4984 code11 = TREE_CODE (tree11);
4985 if (code01 == INTEGER_CST
4986 && code11 == INTEGER_CST
4987 && TREE_INT_CST_HIGH (tree01) == 0
4988 && TREE_INT_CST_HIGH (tree11) == 0
4989 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4990 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4991 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4992 code0 == LSHIFT_EXPR ? tree01 : tree11);
4993 else if (code11 == MINUS_EXPR)
4995 tree tree110, tree111;
4996 tree110 = TREE_OPERAND (tree11, 0);
4997 tree111 = TREE_OPERAND (tree11, 1);
4998 STRIP_NOPS (tree110);
4999 STRIP_NOPS (tree111);
5000 if (TREE_CODE (tree110) == INTEGER_CST
5001 && 0 == compare_tree_int (tree110,
5003 (TREE_TYPE (TREE_OPERAND
5005 && operand_equal_p (tree01, tree111, 0))
5006 return build ((code0 == LSHIFT_EXPR
5009 type, TREE_OPERAND (arg0, 0), tree01);
5011 else if (code01 == MINUS_EXPR)
5013 tree tree010, tree011;
5014 tree010 = TREE_OPERAND (tree01, 0);
5015 tree011 = TREE_OPERAND (tree01, 1);
5016 STRIP_NOPS (tree010);
5017 STRIP_NOPS (tree011);
5018 if (TREE_CODE (tree010) == INTEGER_CST
5019 && 0 == compare_tree_int (tree010,
5021 (TREE_TYPE (TREE_OPERAND
5023 && operand_equal_p (tree11, tree011, 0))
5024 return build ((code0 != LSHIFT_EXPR
5027 type, TREE_OPERAND (arg0, 0), tree11);
5033 /* In most languages, can't associate operations on floats through
5034 parentheses. Rather than remember where the parentheses were, we
5035 don't associate floats at all. It shouldn't matter much. However,
5036 associating multiplications is only very slightly inaccurate, so do
5037 that if -funsafe-math-optimizations is specified. */
5040 && (! FLOAT_TYPE_P (type)
5041 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5043 tree var0, con0, lit0, var1, con1, lit1;
5045 /* Split both trees into variables, constants, and literals. Then
5046 associate each group together, the constants with literals,
5047 then the result with variables. This increases the chances of
5048 literals being recombined later and of generating relocatable
5049 expressions for the sum of a constant and literal. */
5050 var0 = split_tree (arg0, code, &con0, &lit0, 0);
5051 var1 = split_tree (arg1, code, &con1, &lit1, code == MINUS_EXPR);
5053 /* Only do something if we found more than two objects. Otherwise,
5054 nothing has changed and we risk infinite recursion. */
5055 if (2 < ((var0 != 0) + (var1 != 0) + (con0 != 0) + (con1 != 0)
5056 + (lit0 != 0) + (lit1 != 0)))
5058 var0 = associate_trees (var0, var1, code, type);
5059 con0 = associate_trees (con0, con1, code, type);
5060 lit0 = associate_trees (lit0, lit1, code, type);
5061 con0 = associate_trees (con0, lit0, code, type);
5062 return convert (type, associate_trees (var0, con0, code, type));
5068 t1 = const_binop (code, arg0, arg1, 0);
5069 if (t1 != NULL_TREE)
5071 /* The return value should always have
5072 the same type as the original expression. */
5073 if (TREE_TYPE (t1) != TREE_TYPE (t))
5074 t1 = convert (TREE_TYPE (t), t1);
5081 /* A - (-B) -> A + B */
5082 if (TREE_CODE (arg1) == NEGATE_EXPR)
5083 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5084 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5085 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5087 fold (build (MINUS_EXPR, type,
5088 build_real (TREE_TYPE (arg1),
5089 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5090 TREE_OPERAND (arg0, 0)));
5092 if (! FLOAT_TYPE_P (type))
5094 if (! wins && integer_zerop (arg0))
5095 return negate_expr (convert (type, arg1));
5096 if (integer_zerop (arg1))
5097 return non_lvalue (convert (type, arg0));
5099 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5100 about the case where C is a constant, just try one of the
5101 four possibilities. */
5103 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5104 && operand_equal_p (TREE_OPERAND (arg0, 1),
5105 TREE_OPERAND (arg1, 1), 0))
5106 return fold (build (MULT_EXPR, type,
5107 fold (build (MINUS_EXPR, type,
5108 TREE_OPERAND (arg0, 0),
5109 TREE_OPERAND (arg1, 0))),
5110 TREE_OPERAND (arg0, 1)));
5113 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5114 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5115 return non_lvalue (convert (type, arg0));
5117 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5118 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5119 (-ARG1 + ARG0) reduces to -ARG1. */
5120 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5121 return negate_expr (convert (type, arg1));
5123 /* Fold &x - &x. This can happen from &x.foo - &x.
5124 This is unsafe for certain floats even in non-IEEE formats.
5125 In IEEE, it is unsafe because it does wrong for NaNs.
5126 Also note that operand_equal_p is always false if an operand
5129 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5130 && operand_equal_p (arg0, arg1, 0))
5131 return convert (type, integer_zero_node);
5136 /* (-A) * (-B) -> A * B */
5137 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5138 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5139 TREE_OPERAND (arg1, 0)));
5141 if (! FLOAT_TYPE_P (type))
5143 if (integer_zerop (arg1))
5144 return omit_one_operand (type, arg1, arg0);
5145 if (integer_onep (arg1))
5146 return non_lvalue (convert (type, arg0));
5148 /* (a * (1 << b)) is (a << b) */
5149 if (TREE_CODE (arg1) == LSHIFT_EXPR
5150 && integer_onep (TREE_OPERAND (arg1, 0)))
5151 return fold (build (LSHIFT_EXPR, type, arg0,
5152 TREE_OPERAND (arg1, 1)));
5153 if (TREE_CODE (arg0) == LSHIFT_EXPR
5154 && integer_onep (TREE_OPERAND (arg0, 0)))
5155 return fold (build (LSHIFT_EXPR, type, arg1,
5156 TREE_OPERAND (arg0, 1)));
5158 if (TREE_CODE (arg1) == INTEGER_CST
5159 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5161 return convert (type, tem);
5166 /* Maybe fold x * 0 to 0. The expressions aren't the same
5167 when x is NaN, since x * 0 is also NaN. Nor are they the
5168 same in modes with signed zeros, since multiplying a
5169 negative value by 0 gives -0, not +0. */
5170 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5171 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5172 && real_zerop (arg1))
5173 return omit_one_operand (type, arg1, arg0);
5174 /* In IEEE floating point, x*1 is not equivalent to x for snans.
5175 However, ANSI says we can drop signals,
5176 so we can do this anyway. */
5177 if (real_onep (arg1))
5178 return non_lvalue (convert (type, arg0));
5180 if (! wins && real_twop (arg1)
5181 && (*lang_hooks.decls.global_bindings_p) () == 0
5182 && ! contains_placeholder_p (arg0))
5184 tree arg = save_expr (arg0);
5185 return build (PLUS_EXPR, type, arg, arg);
5192 if (integer_all_onesp (arg1))
5193 return omit_one_operand (type, arg1, arg0);
5194 if (integer_zerop (arg1))
5195 return non_lvalue (convert (type, arg0));
5196 t1 = distribute_bit_expr (code, type, arg0, arg1);
5197 if (t1 != NULL_TREE)
5200 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5202 This results in more efficient code for machines without a NAND
5203 instruction. Combine will canonicalize to the first form
5204 which will allow use of NAND instructions provided by the
5205 backend if they exist. */
5206 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5207 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5209 return fold (build1 (BIT_NOT_EXPR, type,
5210 build (BIT_AND_EXPR, type,
5211 TREE_OPERAND (arg0, 0),
5212 TREE_OPERAND (arg1, 0))));
5215 /* See if this can be simplified into a rotate first. If that
5216 is unsuccessful continue in the association code. */
5220 if (integer_zerop (arg1))
5221 return non_lvalue (convert (type, arg0));
5222 if (integer_all_onesp (arg1))
5223 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5225 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5226 with a constant, and the two constants have no bits in common,
5227 we should treat this as a BIT_IOR_EXPR since this may produce more
5229 if (TREE_CODE (arg0) == BIT_AND_EXPR
5230 && TREE_CODE (arg1) == BIT_AND_EXPR
5231 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5232 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5233 && integer_zerop (const_binop (BIT_AND_EXPR,
5234 TREE_OPERAND (arg0, 1),
5235 TREE_OPERAND (arg1, 1), 0)))
5237 code = BIT_IOR_EXPR;
5241 /* See if this can be simplified into a rotate first. If that
5242 is unsuccessful continue in the association code. */
5247 if (integer_all_onesp (arg1))
5248 return non_lvalue (convert (type, arg0));
5249 if (integer_zerop (arg1))
5250 return omit_one_operand (type, arg1, arg0);
5251 t1 = distribute_bit_expr (code, type, arg0, arg1);
5252 if (t1 != NULL_TREE)
5254 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5255 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5256 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5259 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5261 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5262 && (~TREE_INT_CST_LOW (arg0)
5263 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5264 return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5266 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5267 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5270 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5272 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5273 && (~TREE_INT_CST_LOW (arg1)
5274 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5275 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5278 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5280 This results in more efficient code for machines without a NOR
5281 instruction. Combine will canonicalize to the first form
5282 which will allow use of NOR instructions provided by the
5283 backend if they exist. */
5284 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5285 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5287 return fold (build1 (BIT_NOT_EXPR, type,
5288 build (BIT_IOR_EXPR, type,
5289 TREE_OPERAND (arg0, 0),
5290 TREE_OPERAND (arg1, 0))));
5295 case BIT_ANDTC_EXPR:
5296 if (integer_all_onesp (arg0))
5297 return non_lvalue (convert (type, arg1));
5298 if (integer_zerop (arg0))
5299 return omit_one_operand (type, arg0, arg1);
5300 if (TREE_CODE (arg1) == INTEGER_CST)
5302 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5303 code = BIT_AND_EXPR;
5309 /* Don't touch a floating-point divide by zero unless the mode
5310 of the constant can represent infinity. */
5311 if (TREE_CODE (arg1) == REAL_CST
5312 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5313 && real_zerop (arg1))
5316 /* (-A) / (-B) -> A / B */
5317 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5318 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5319 TREE_OPERAND (arg1, 0)));
5321 /* In IEEE floating point, x/1 is not equivalent to x for snans.
5322 However, ANSI says we can drop signals, so we can do this anyway. */
5323 if (real_onep (arg1))
5324 return non_lvalue (convert (type, arg0));
5326 /* If ARG1 is a constant, we can convert this to a multiply by the
5327 reciprocal. This does not have the same rounding properties,
5328 so only do this if -funsafe-math-optimizations. We can actually
5329 always safely do it if ARG1 is a power of two, but it's hard to
5330 tell if it is or not in a portable manner. */
5331 if (TREE_CODE (arg1) == REAL_CST)
5333 if (flag_unsafe_math_optimizations
5334 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5336 return fold (build (MULT_EXPR, type, arg0, tem));
5337 /* Find the reciprocal if optimizing and the result is exact. */
5341 r = TREE_REAL_CST (arg1);
5342 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5344 tem = build_real (type, r);
5345 return fold (build (MULT_EXPR, type, arg0, tem));
5349 /* Convert A/B/C to A/(B*C). */
5350 if (flag_unsafe_math_optimizations
5351 && TREE_CODE (arg0) == RDIV_EXPR)
5353 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5354 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5357 /* Convert A/(B/C) to (A/B)*C. */
5358 if (flag_unsafe_math_optimizations
5359 && TREE_CODE (arg1) == RDIV_EXPR)
5361 return fold (build (MULT_EXPR, type,
5362 build (RDIV_EXPR, type, arg0,
5363 TREE_OPERAND (arg1, 0)),
5364 TREE_OPERAND (arg1, 1)));
5368 case TRUNC_DIV_EXPR:
5369 case ROUND_DIV_EXPR:
5370 case FLOOR_DIV_EXPR:
5372 case EXACT_DIV_EXPR:
5373 if (integer_onep (arg1))
5374 return non_lvalue (convert (type, arg0));
5375 if (integer_zerop (arg1))
5378 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5379 operation, EXACT_DIV_EXPR.
5381 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5382 At one time others generated faster code, it's not clear if they do
5383 after the last round to changes to the DIV code in expmed.c. */
5384 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5385 && multiple_of_p (type, arg0, arg1))
5386 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5388 if (TREE_CODE (arg1) == INTEGER_CST
5389 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5391 return convert (type, tem);
5396 case FLOOR_MOD_EXPR:
5397 case ROUND_MOD_EXPR:
5398 case TRUNC_MOD_EXPR:
5399 if (integer_onep (arg1))
5400 return omit_one_operand (type, integer_zero_node, arg0);
5401 if (integer_zerop (arg1))
5404 if (TREE_CODE (arg1) == INTEGER_CST
5405 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5407 return convert (type, tem);
5415 if (integer_zerop (arg1))
5416 return non_lvalue (convert (type, arg0));
5417 /* Since negative shift count is not well-defined,
5418 don't try to compute it in the compiler. */
5419 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5421 /* Rewrite an LROTATE_EXPR by a constant into an
5422 RROTATE_EXPR by a new constant. */
5423 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5425 TREE_SET_CODE (t, RROTATE_EXPR);
5426 code = RROTATE_EXPR;
5427 TREE_OPERAND (t, 1) = arg1
5430 convert (TREE_TYPE (arg1),
5431 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5433 if (tree_int_cst_sgn (arg1) < 0)
5437 /* If we have a rotate of a bit operation with the rotate count and
5438 the second operand of the bit operation both constant,
5439 permute the two operations. */
5440 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5441 && (TREE_CODE (arg0) == BIT_AND_EXPR
5442 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5443 || TREE_CODE (arg0) == BIT_IOR_EXPR
5444 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5445 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5446 return fold (build (TREE_CODE (arg0), type,
5447 fold (build (code, type,
5448 TREE_OPERAND (arg0, 0), arg1)),
5449 fold (build (code, type,
5450 TREE_OPERAND (arg0, 1), arg1))));
5452 /* Two consecutive rotates adding up to the width of the mode can
5454 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5455 && TREE_CODE (arg0) == RROTATE_EXPR
5456 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5457 && TREE_INT_CST_HIGH (arg1) == 0
5458 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5459 && ((TREE_INT_CST_LOW (arg1)
5460 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5461 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5462 return TREE_OPERAND (arg0, 0);
5467 if (operand_equal_p (arg0, arg1, 0))
5468 return omit_one_operand (type, arg0, arg1);
5469 if (INTEGRAL_TYPE_P (type)
5470 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5471 return omit_one_operand (type, arg1, arg0);
5475 if (operand_equal_p (arg0, arg1, 0))
5476 return omit_one_operand (type, arg0, arg1);
5477 if (INTEGRAL_TYPE_P (type)
5478 && TYPE_MAX_VALUE (type)
5479 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5480 return omit_one_operand (type, arg1, arg0);
5483 case TRUTH_NOT_EXPR:
5484 /* Note that the operand of this must be an int
5485 and its values must be 0 or 1.
5486 ("true" is a fixed value perhaps depending on the language,
5487 but we don't handle values other than 1 correctly yet.) */
5488 tem = invert_truthvalue (arg0);
5489 /* Avoid infinite recursion. */
5490 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5492 return convert (type, tem);
5494 case TRUTH_ANDIF_EXPR:
5495 /* Note that the operands of this must be ints
5496 and their values must be 0 or 1.
5497 ("true" is a fixed value perhaps depending on the language.) */
5498 /* If first arg is constant zero, return it. */
5499 if (integer_zerop (arg0))
5500 return convert (type, arg0);
5501 case TRUTH_AND_EXPR:
5502 /* If either arg is constant true, drop it. */
5503 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5504 return non_lvalue (convert (type, arg1));
5505 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5506 /* Preserve sequence points. */
5507 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5508 return non_lvalue (convert (type, arg0));
5509 /* If second arg is constant zero, result is zero, but first arg
5510 must be evaluated. */
5511 if (integer_zerop (arg1))
5512 return omit_one_operand (type, arg1, arg0);
5513 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5514 case will be handled here. */
5515 if (integer_zerop (arg0))
5516 return omit_one_operand (type, arg0, arg1);
5519 /* We only do these simplifications if we are optimizing. */
5523 /* Check for things like (A || B) && (A || C). We can convert this
5524 to A || (B && C). Note that either operator can be any of the four
5525 truth and/or operations and the transformation will still be
5526 valid. Also note that we only care about order for the
5527 ANDIF and ORIF operators. If B contains side effects, this
5528 might change the truth-value of A. */
5529 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5530 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5531 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5532 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5533 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5534 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5536 tree a00 = TREE_OPERAND (arg0, 0);
5537 tree a01 = TREE_OPERAND (arg0, 1);
5538 tree a10 = TREE_OPERAND (arg1, 0);
5539 tree a11 = TREE_OPERAND (arg1, 1);
5540 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5541 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5542 && (code == TRUTH_AND_EXPR
5543 || code == TRUTH_OR_EXPR));
5545 if (operand_equal_p (a00, a10, 0))
5546 return fold (build (TREE_CODE (arg0), type, a00,
5547 fold (build (code, type, a01, a11))));
5548 else if (commutative && operand_equal_p (a00, a11, 0))
5549 return fold (build (TREE_CODE (arg0), type, a00,
5550 fold (build (code, type, a01, a10))));
5551 else if (commutative && operand_equal_p (a01, a10, 0))
5552 return fold (build (TREE_CODE (arg0), type, a01,
5553 fold (build (code, type, a00, a11))));
5555 /* This case if tricky because we must either have commutative
5556 operators or else A10 must not have side-effects. */
5558 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5559 && operand_equal_p (a01, a11, 0))
5560 return fold (build (TREE_CODE (arg0), type,
5561 fold (build (code, type, a00, a10)),
5565 /* See if we can build a range comparison. */
5566 if (0 != (tem = fold_range_test (t)))
5569 /* Check for the possibility of merging component references. If our
5570 lhs is another similar operation, try to merge its rhs with our
5571 rhs. Then try to merge our lhs and rhs. */
5572 if (TREE_CODE (arg0) == code
5573 && 0 != (tem = fold_truthop (code, type,
5574 TREE_OPERAND (arg0, 1), arg1)))
5575 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5577 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5582 case TRUTH_ORIF_EXPR:
5583 /* Note that the operands of this must be ints
5584 and their values must be 0 or true.
5585 ("true" is a fixed value perhaps depending on the language.) */
5586 /* If first arg is constant true, return it. */
5587 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5588 return convert (type, arg0);
5590 /* If either arg is constant zero, drop it. */
5591 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5592 return non_lvalue (convert (type, arg1));
5593 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5594 /* Preserve sequence points. */
5595 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5596 return non_lvalue (convert (type, arg0));
5597 /* If second arg is constant true, result is true, but we must
5598 evaluate first arg. */
5599 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5600 return omit_one_operand (type, arg1, arg0);
5601 /* Likewise for first arg, but note this only occurs here for
5603 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5604 return omit_one_operand (type, arg0, arg1);
5607 case TRUTH_XOR_EXPR:
5608 /* If either arg is constant zero, drop it. */
5609 if (integer_zerop (arg0))
5610 return non_lvalue (convert (type, arg1));
5611 if (integer_zerop (arg1))
5612 return non_lvalue (convert (type, arg0));
5613 /* If either arg is constant true, this is a logical inversion. */
5614 if (integer_onep (arg0))
5615 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5616 if (integer_onep (arg1))
5617 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5626 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5628 /* (-a) CMP (-b) -> b CMP a */
5629 if (TREE_CODE (arg0) == NEGATE_EXPR
5630 && TREE_CODE (arg1) == NEGATE_EXPR)
5631 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5632 TREE_OPERAND (arg0, 0)));
5633 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5634 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5637 (swap_tree_comparison (code), type,
5638 TREE_OPERAND (arg0, 0),
5639 build_real (TREE_TYPE (arg1),
5640 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5641 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5642 /* a CMP (-0) -> a CMP 0 */
5643 if (TREE_CODE (arg1) == REAL_CST
5644 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5645 return fold (build (code, type, arg0,
5646 build_real (TREE_TYPE (arg1), dconst0)));
5649 /* If one arg is a constant integer, put it last. */
5650 if (TREE_CODE (arg0) == INTEGER_CST
5651 && TREE_CODE (arg1) != INTEGER_CST)
5653 TREE_OPERAND (t, 0) = arg1;
5654 TREE_OPERAND (t, 1) = arg0;
5655 arg0 = TREE_OPERAND (t, 0);
5656 arg1 = TREE_OPERAND (t, 1);
5657 code = swap_tree_comparison (code);
5658 TREE_SET_CODE (t, code);
5661 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5662 First, see if one arg is constant; find the constant arg
5663 and the other one. */
5665 tree constop = 0, varop = NULL_TREE;
5666 int constopnum = -1;
5668 if (TREE_CONSTANT (arg1))
5669 constopnum = 1, constop = arg1, varop = arg0;
5670 if (TREE_CONSTANT (arg0))
5671 constopnum = 0, constop = arg0, varop = arg1;
5673 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5675 /* This optimization is invalid for ordered comparisons
5676 if CONST+INCR overflows or if foo+incr might overflow.
5677 This optimization is invalid for floating point due to rounding.
5678 For pointer types we assume overflow doesn't happen. */
5679 if (POINTER_TYPE_P (TREE_TYPE (varop))
5680 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5681 && (code == EQ_EXPR || code == NE_EXPR)))
5684 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5685 constop, TREE_OPERAND (varop, 1)));
5687 /* Do not overwrite the current varop to be a preincrement,
5688 create a new node so that we won't confuse our caller who
5689 might create trees and throw them away, reusing the
5690 arguments that they passed to build. This shows up in
5691 the THEN or ELSE parts of ?: being postincrements. */
5692 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
5693 TREE_OPERAND (varop, 0),
5694 TREE_OPERAND (varop, 1));
5696 /* If VAROP is a reference to a bitfield, we must mask
5697 the constant by the width of the field. */
5698 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5699 && DECL_BIT_FIELD(TREE_OPERAND
5700 (TREE_OPERAND (varop, 0), 1)))
5703 = TREE_INT_CST_LOW (DECL_SIZE
5705 (TREE_OPERAND (varop, 0), 1)));
5706 tree mask, unsigned_type;
5707 unsigned int precision;
5708 tree folded_compare;
5710 /* First check whether the comparison would come out
5711 always the same. If we don't do that we would
5712 change the meaning with the masking. */
5713 if (constopnum == 0)
5714 folded_compare = fold (build (code, type, constop,
5715 TREE_OPERAND (varop, 0)));
5717 folded_compare = fold (build (code, type,
5718 TREE_OPERAND (varop, 0),
5720 if (integer_zerop (folded_compare)
5721 || integer_onep (folded_compare))
5722 return omit_one_operand (type, folded_compare, varop);
5724 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5725 precision = TYPE_PRECISION (unsigned_type);
5726 mask = build_int_2 (~0, ~0);
5727 TREE_TYPE (mask) = unsigned_type;
5728 force_fit_type (mask, 0);
5729 mask = const_binop (RSHIFT_EXPR, mask,
5730 size_int (precision - size), 0);
5731 newconst = fold (build (BIT_AND_EXPR,
5732 TREE_TYPE (varop), newconst,
5733 convert (TREE_TYPE (varop),
5737 t = build (code, type,
5738 (constopnum == 0) ? newconst : varop,
5739 (constopnum == 1) ? newconst : varop);
5743 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5745 if (POINTER_TYPE_P (TREE_TYPE (varop))
5746 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5747 && (code == EQ_EXPR || code == NE_EXPR)))
5750 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5751 constop, TREE_OPERAND (varop, 1)));
5753 /* Do not overwrite the current varop to be a predecrement,
5754 create a new node so that we won't confuse our caller who
5755 might create trees and throw them away, reusing the
5756 arguments that they passed to build. This shows up in
5757 the THEN or ELSE parts of ?: being postdecrements. */
5758 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
5759 TREE_OPERAND (varop, 0),
5760 TREE_OPERAND (varop, 1));
5762 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5763 && DECL_BIT_FIELD(TREE_OPERAND
5764 (TREE_OPERAND (varop, 0), 1)))
5767 = TREE_INT_CST_LOW (DECL_SIZE
5769 (TREE_OPERAND (varop, 0), 1)));
5770 tree mask, unsigned_type;
5771 unsigned int precision;
5772 tree folded_compare;
5774 if (constopnum == 0)
5775 folded_compare = fold (build (code, type, constop,
5776 TREE_OPERAND (varop, 0)));
5778 folded_compare = fold (build (code, type,
5779 TREE_OPERAND (varop, 0),
5781 if (integer_zerop (folded_compare)
5782 || integer_onep (folded_compare))
5783 return omit_one_operand (type, folded_compare, varop);
5785 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5786 precision = TYPE_PRECISION (unsigned_type);
5787 mask = build_int_2 (~0, ~0);
5788 TREE_TYPE (mask) = TREE_TYPE (varop);
5789 force_fit_type (mask, 0);
5790 mask = const_binop (RSHIFT_EXPR, mask,
5791 size_int (precision - size), 0);
5792 newconst = fold (build (BIT_AND_EXPR,
5793 TREE_TYPE (varop), newconst,
5794 convert (TREE_TYPE (varop),
5798 t = build (code, type,
5799 (constopnum == 0) ? newconst : varop,
5800 (constopnum == 1) ? newconst : varop);
5806 /* Change X >= CST to X > (CST - 1) if CST is positive. */
5807 if (TREE_CODE (arg1) == INTEGER_CST
5808 && TREE_CODE (arg0) != INTEGER_CST
5809 && tree_int_cst_sgn (arg1) > 0)
5811 switch (TREE_CODE (t))
5815 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5816 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5821 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5822 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5830 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
5831 a MINUS_EXPR of a constant, we can convert it into a comparison with
5832 a revised constant as long as no overflow occurs. */
5833 if ((code == EQ_EXPR || code == NE_EXPR)
5834 && TREE_CODE (arg1) == INTEGER_CST
5835 && (TREE_CODE (arg0) == PLUS_EXPR
5836 || TREE_CODE (arg0) == MINUS_EXPR)
5837 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5838 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
5839 ? MINUS_EXPR : PLUS_EXPR,
5840 arg1, TREE_OPERAND (arg0, 1), 0))
5841 && ! TREE_CONSTANT_OVERFLOW (tem))
5842 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5844 /* Similarly for a NEGATE_EXPR. */
5845 else if ((code == EQ_EXPR || code == NE_EXPR)
5846 && TREE_CODE (arg0) == NEGATE_EXPR
5847 && TREE_CODE (arg1) == INTEGER_CST
5848 && 0 != (tem = negate_expr (arg1))
5849 && TREE_CODE (tem) == INTEGER_CST
5850 && ! TREE_CONSTANT_OVERFLOW (tem))
5851 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5853 /* If we have X - Y == 0, we can convert that to X == Y and similarly
5854 for !=. Don't do this for ordered comparisons due to overflow. */
5855 else if ((code == NE_EXPR || code == EQ_EXPR)
5856 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
5857 return fold (build (code, type,
5858 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
5860 /* If we are widening one operand of an integer comparison,
5861 see if the other operand is similarly being widened. Perhaps we
5862 can do the comparison in the narrower type. */
5863 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
5864 && TREE_CODE (arg0) == NOP_EXPR
5865 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
5866 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
5867 && (TREE_TYPE (t1) == TREE_TYPE (tem)
5868 || (TREE_CODE (t1) == INTEGER_CST
5869 && int_fits_type_p (t1, TREE_TYPE (tem)))))
5870 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
5872 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
5873 constant, we can simplify it. */
5874 else if (TREE_CODE (arg1) == INTEGER_CST
5875 && (TREE_CODE (arg0) == MIN_EXPR
5876 || TREE_CODE (arg0) == MAX_EXPR)
5877 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5878 return optimize_minmax_comparison (t);
5880 /* If we are comparing an ABS_EXPR with a constant, we can
5881 convert all the cases into explicit comparisons, but they may
5882 well not be faster than doing the ABS and one comparison.
5883 But ABS (X) <= C is a range comparison, which becomes a subtraction
5884 and a comparison, and is probably faster. */
5885 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5886 && TREE_CODE (arg0) == ABS_EXPR
5887 && ! TREE_SIDE_EFFECTS (arg0)
5888 && (0 != (tem = negate_expr (arg1)))
5889 && TREE_CODE (tem) == INTEGER_CST
5890 && ! TREE_CONSTANT_OVERFLOW (tem))
5891 return fold (build (TRUTH_ANDIF_EXPR, type,
5892 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
5893 build (LE_EXPR, type,
5894 TREE_OPERAND (arg0, 0), arg1)));
5896 /* If this is an EQ or NE comparison with zero and ARG0 is
5897 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
5898 two operations, but the latter can be done in one less insn
5899 on machines that have only two-operand insns or on which a
5900 constant cannot be the first operand. */
5901 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5902 && TREE_CODE (arg0) == BIT_AND_EXPR)
5904 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5905 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5907 fold (build (code, type,
5908 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5910 TREE_TYPE (TREE_OPERAND (arg0, 0)),
5911 TREE_OPERAND (arg0, 1),
5912 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5913 convert (TREE_TYPE (arg0),
5916 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5917 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5919 fold (build (code, type,
5920 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5922 TREE_TYPE (TREE_OPERAND (arg0, 1)),
5923 TREE_OPERAND (arg0, 0),
5924 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5925 convert (TREE_TYPE (arg0),
5930 /* If this is an NE or EQ comparison of zero against the result of a
5931 signed MOD operation whose second operand is a power of 2, make
5932 the MOD operation unsigned since it is simpler and equivalent. */
5933 if ((code == NE_EXPR || code == EQ_EXPR)
5934 && integer_zerop (arg1)
5935 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5936 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5937 || TREE_CODE (arg0) == CEIL_MOD_EXPR
5938 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5939 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5940 && integer_pow2p (TREE_OPERAND (arg0, 1)))
5942 tree newtype = unsigned_type (TREE_TYPE (arg0));
5943 tree newmod = build (TREE_CODE (arg0), newtype,
5944 convert (newtype, TREE_OPERAND (arg0, 0)),
5945 convert (newtype, TREE_OPERAND (arg0, 1)));
5947 return build (code, type, newmod, convert (newtype, arg1));
5950 /* If this is an NE comparison of zero with an AND of one, remove the
5951 comparison since the AND will give the correct value. */
5952 if (code == NE_EXPR && integer_zerop (arg1)
5953 && TREE_CODE (arg0) == BIT_AND_EXPR
5954 && integer_onep (TREE_OPERAND (arg0, 1)))
5955 return convert (type, arg0);
5957 /* If we have (A & C) == C where C is a power of 2, convert this into
5958 (A & C) != 0. Similarly for NE_EXPR. */
5959 if ((code == EQ_EXPR || code == NE_EXPR)
5960 && TREE_CODE (arg0) == BIT_AND_EXPR
5961 && integer_pow2p (TREE_OPERAND (arg0, 1))
5962 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5963 return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5964 arg0, integer_zero_node);
5966 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5967 and similarly for >= into !=. */
5968 if ((code == LT_EXPR || code == GE_EXPR)
5969 && TREE_UNSIGNED (TREE_TYPE (arg0))
5970 && TREE_CODE (arg1) == LSHIFT_EXPR
5971 && integer_onep (TREE_OPERAND (arg1, 0)))
5972 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5973 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5974 TREE_OPERAND (arg1, 1)),
5975 convert (TREE_TYPE (arg0), integer_zero_node));
5977 else if ((code == LT_EXPR || code == GE_EXPR)
5978 && TREE_UNSIGNED (TREE_TYPE (arg0))
5979 && (TREE_CODE (arg1) == NOP_EXPR
5980 || TREE_CODE (arg1) == CONVERT_EXPR)
5981 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5982 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5984 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5985 convert (TREE_TYPE (arg0),
5986 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5987 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5988 convert (TREE_TYPE (arg0), integer_zero_node));
5990 /* Simplify comparison of something with itself. (For IEEE
5991 floating-point, we can only do some of these simplifications.) */
5992 if (operand_equal_p (arg0, arg1, 0))
5999 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
6000 return constant_boolean_node (1, type);
6002 TREE_SET_CODE (t, code);
6006 /* For NE, we can only do this simplification if integer. */
6007 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6009 /* ... fall through ... */
6012 return constant_boolean_node (0, type);
6018 /* An unsigned comparison against 0 can be simplified. */
6019 if (integer_zerop (arg1)
6020 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6021 || POINTER_TYPE_P (TREE_TYPE (arg1)))
6022 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6024 switch (TREE_CODE (t))
6028 TREE_SET_CODE (t, NE_EXPR);
6032 TREE_SET_CODE (t, EQ_EXPR);
6035 return omit_one_operand (type,
6036 convert (type, integer_one_node),
6039 return omit_one_operand (type,
6040 convert (type, integer_zero_node),
6047 /* Comparisons with the highest or lowest possible integer of
6048 the specified size will have known values and an unsigned
6049 <= 0x7fffffff can be simplified. */
6051 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
6053 if (TREE_CODE (arg1) == INTEGER_CST
6054 && ! TREE_CONSTANT_OVERFLOW (arg1)
6055 && width <= HOST_BITS_PER_WIDE_INT
6056 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6057 || POINTER_TYPE_P (TREE_TYPE (arg1))))
6059 if (TREE_INT_CST_HIGH (arg1) == 0
6060 && (TREE_INT_CST_LOW (arg1)
6061 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6062 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6063 switch (TREE_CODE (t))
6066 return omit_one_operand (type,
6067 convert (type, integer_zero_node),
6070 TREE_SET_CODE (t, EQ_EXPR);
6074 return omit_one_operand (type,
6075 convert (type, integer_one_node),
6078 TREE_SET_CODE (t, NE_EXPR);
6085 else if (TREE_INT_CST_HIGH (arg1) == -1
6086 && (TREE_INT_CST_LOW (arg1)
6087 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)))
6088 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6089 switch (TREE_CODE (t))
6092 return omit_one_operand (type,
6093 convert (type, integer_zero_node),
6096 TREE_SET_CODE (t, EQ_EXPR);
6100 return omit_one_operand (type,
6101 convert (type, integer_one_node),
6104 TREE_SET_CODE (t, NE_EXPR);
6111 else if (TREE_INT_CST_HIGH (arg1) == 0
6112 && (TREE_INT_CST_LOW (arg1)
6113 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6114 && TREE_UNSIGNED (TREE_TYPE (arg1))
6115 /* signed_type does not work on pointer types. */
6116 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6117 switch (TREE_CODE (t))
6120 return fold (build (GE_EXPR, type,
6121 convert (signed_type (TREE_TYPE (arg0)),
6123 convert (signed_type (TREE_TYPE (arg1)),
6124 integer_zero_node)));
6126 return fold (build (LT_EXPR, type,
6127 convert (signed_type (TREE_TYPE (arg0)),
6129 convert (signed_type (TREE_TYPE (arg1)),
6130 integer_zero_node)));
6136 else if (TREE_INT_CST_HIGH (arg1) == 0
6137 && (TREE_INT_CST_LOW (arg1)
6138 == ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1)
6139 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6140 switch (TREE_CODE (t))
6143 return omit_one_operand (type,
6144 convert (type, integer_zero_node),
6147 TREE_SET_CODE (t, EQ_EXPR);
6151 return omit_one_operand (type,
6152 convert (type, integer_one_node),
6155 TREE_SET_CODE (t, NE_EXPR);
6164 /* If we are comparing an expression that just has comparisons
6165 of two integer values, arithmetic expressions of those comparisons,
6166 and constants, we can simplify it. There are only three cases
6167 to check: the two values can either be equal, the first can be
6168 greater, or the second can be greater. Fold the expression for
6169 those three values. Since each value must be 0 or 1, we have
6170 eight possibilities, each of which corresponds to the constant 0
6171 or 1 or one of the six possible comparisons.
6173 This handles common cases like (a > b) == 0 but also handles
6174 expressions like ((x > y) - (y > x)) > 0, which supposedly
6175 occur in macroized code. */
6177 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6179 tree cval1 = 0, cval2 = 0;
6182 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6183 /* Don't handle degenerate cases here; they should already
6184 have been handled anyway. */
6185 && cval1 != 0 && cval2 != 0
6186 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6187 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6188 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6189 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6190 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6191 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6192 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6194 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6195 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6197 /* We can't just pass T to eval_subst in case cval1 or cval2
6198 was the same as ARG1. */
6201 = fold (build (code, type,
6202 eval_subst (arg0, cval1, maxval, cval2, minval),
6205 = fold (build (code, type,
6206 eval_subst (arg0, cval1, maxval, cval2, maxval),
6209 = fold (build (code, type,
6210 eval_subst (arg0, cval1, minval, cval2, maxval),
6213 /* All three of these results should be 0 or 1. Confirm they
6214 are. Then use those values to select the proper code
6217 if ((integer_zerop (high_result)
6218 || integer_onep (high_result))
6219 && (integer_zerop (equal_result)
6220 || integer_onep (equal_result))
6221 && (integer_zerop (low_result)
6222 || integer_onep (low_result)))
6224 /* Make a 3-bit mask with the high-order bit being the
6225 value for `>', the next for '=', and the low for '<'. */
6226 switch ((integer_onep (high_result) * 4)
6227 + (integer_onep (equal_result) * 2)
6228 + integer_onep (low_result))
6232 return omit_one_operand (type, integer_zero_node, arg0);
6253 return omit_one_operand (type, integer_one_node, arg0);
6256 t = build (code, type, cval1, cval2);
6258 return save_expr (t);
6265 /* If this is a comparison of a field, we may be able to simplify it. */
6266 if ((TREE_CODE (arg0) == COMPONENT_REF
6267 || TREE_CODE (arg0) == BIT_FIELD_REF)
6268 && (code == EQ_EXPR || code == NE_EXPR)
6269 /* Handle the constant case even without -O
6270 to make sure the warnings are given. */
6271 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6273 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6277 /* If this is a comparison of complex values and either or both sides
6278 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6279 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6280 This may prevent needless evaluations. */
6281 if ((code == EQ_EXPR || code == NE_EXPR)
6282 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6283 && (TREE_CODE (arg0) == COMPLEX_EXPR
6284 || TREE_CODE (arg1) == COMPLEX_EXPR
6285 || TREE_CODE (arg0) == COMPLEX_CST
6286 || TREE_CODE (arg1) == COMPLEX_CST))
6288 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6289 tree real0, imag0, real1, imag1;
6291 arg0 = save_expr (arg0);
6292 arg1 = save_expr (arg1);
6293 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6294 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6295 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6296 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6298 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6301 fold (build (code, type, real0, real1)),
6302 fold (build (code, type, imag0, imag1))));
6305 /* Optimize comparisons of strlen vs zero to a compare of the
6306 first character of the string vs zero. To wit,
6307 strlen(ptr) == 0 => *ptr == 0
6308 strlen(ptr) != 0 => *ptr != 0
6309 Other cases should reduce to one of these two (or a constant)
6310 due to the return value of strlen being unsigned. */
6311 if ((code == EQ_EXPR || code == NE_EXPR)
6312 && integer_zerop (arg1)
6313 && TREE_CODE (arg0) == CALL_EXPR
6314 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6316 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6319 if (TREE_CODE (fndecl) == FUNCTION_DECL
6320 && DECL_BUILT_IN (fndecl)
6321 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6322 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6323 && (arglist = TREE_OPERAND (arg0, 1))
6324 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6325 && ! TREE_CHAIN (arglist))
6326 return fold (build (code, type,
6327 build1 (INDIRECT_REF, char_type_node,
6328 TREE_VALUE(arglist)),
6329 integer_zero_node));
6332 /* From here on, the only cases we handle are when the result is
6333 known to be a constant.
6335 To compute GT, swap the arguments and do LT.
6336 To compute GE, do LT and invert the result.
6337 To compute LE, swap the arguments, do LT and invert the result.
6338 To compute NE, do EQ and invert the result.
6340 Therefore, the code below must handle only EQ and LT. */
6342 if (code == LE_EXPR || code == GT_EXPR)
6344 tem = arg0, arg0 = arg1, arg1 = tem;
6345 code = swap_tree_comparison (code);
6348 /* Note that it is safe to invert for real values here because we
6349 will check below in the one case that it matters. */
6353 if (code == NE_EXPR || code == GE_EXPR)
6356 code = invert_tree_comparison (code);
6359 /* Compute a result for LT or EQ if args permit;
6360 otherwise return T. */
6361 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6363 if (code == EQ_EXPR)
6364 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6366 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6367 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6368 : INT_CST_LT (arg0, arg1)),
6372 #if 0 /* This is no longer useful, but breaks some real code. */
6373 /* Assume a nonexplicit constant cannot equal an explicit one,
6374 since such code would be undefined anyway.
6375 Exception: on sysvr4, using #pragma weak,
6376 a label can come out as 0. */
6377 else if (TREE_CODE (arg1) == INTEGER_CST
6378 && !integer_zerop (arg1)
6379 && TREE_CONSTANT (arg0)
6380 && TREE_CODE (arg0) == ADDR_EXPR
6382 t1 = build_int_2 (0, 0);
6384 /* Two real constants can be compared explicitly. */
6385 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6387 /* If either operand is a NaN, the result is false with two
6388 exceptions: First, an NE_EXPR is true on NaNs, but that case
6389 is already handled correctly since we will be inverting the
6390 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6391 or a GE_EXPR into a LT_EXPR, we must return true so that it
6392 will be inverted into false. */
6394 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6395 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6396 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6398 else if (code == EQ_EXPR)
6399 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6400 TREE_REAL_CST (arg1)),
6403 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6404 TREE_REAL_CST (arg1)),
6408 if (t1 == NULL_TREE)
6412 TREE_INT_CST_LOW (t1) ^= 1;
6414 TREE_TYPE (t1) = type;
6415 if (TREE_CODE (type) == BOOLEAN_TYPE)
6416 return truthvalue_conversion (t1);
6420 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6421 so all simple results must be passed through pedantic_non_lvalue. */
6422 if (TREE_CODE (arg0) == INTEGER_CST)
6423 return pedantic_non_lvalue
6424 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6425 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6426 return pedantic_omit_one_operand (type, arg1, arg0);
6428 /* If the second operand is zero, invert the comparison and swap
6429 the second and third operands. Likewise if the second operand
6430 is constant and the third is not or if the third operand is
6431 equivalent to the first operand of the comparison. */
6433 if (integer_zerop (arg1)
6434 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6435 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6436 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6437 TREE_OPERAND (t, 2),
6438 TREE_OPERAND (arg0, 1))))
6440 /* See if this can be inverted. If it can't, possibly because
6441 it was a floating-point inequality comparison, don't do
6443 tem = invert_truthvalue (arg0);
6445 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6447 t = build (code, type, tem,
6448 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6450 /* arg1 should be the first argument of the new T. */
6451 arg1 = TREE_OPERAND (t, 1);
6456 /* If we have A op B ? A : C, we may be able to convert this to a
6457 simpler expression, depending on the operation and the values
6458 of B and C. Signed zeros prevent all of these transformations,
6459 for reasons given above each one. */
6461 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6462 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6463 arg1, TREE_OPERAND (arg0, 1))
6464 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6466 tree arg2 = TREE_OPERAND (t, 2);
6467 enum tree_code comp_code = TREE_CODE (arg0);
6471 /* If we have A op 0 ? A : -A, consider applying the following
6474 A == 0? A : -A same as -A
6475 A != 0? A : -A same as A
6476 A >= 0? A : -A same as abs (A)
6477 A > 0? A : -A same as abs (A)
6478 A <= 0? A : -A same as -abs (A)
6479 A < 0? A : -A same as -abs (A)
6481 None of these transformations work for modes with signed
6482 zeros. If A is +/-0, the first two transformations will
6483 change the sign of the result (from +0 to -0, or vice
6484 versa). The last four will fix the sign of the result,
6485 even though the original expressions could be positive or
6486 negative, depending on the sign of A.
6488 Note that all these transformations are correct if A is
6489 NaN, since the two alternatives (A and -A) are also NaNs. */
6490 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6491 ? real_zerop (TREE_OPERAND (arg0, 1))
6492 : integer_zerop (TREE_OPERAND (arg0, 1)))
6493 && TREE_CODE (arg2) == NEGATE_EXPR
6494 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6502 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6505 return pedantic_non_lvalue (convert (type, arg1));
6508 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6509 arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6510 return pedantic_non_lvalue
6511 (convert (type, fold (build1 (ABS_EXPR,
6512 TREE_TYPE (arg1), arg1))));
6515 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6516 arg1 = convert (signed_type (TREE_TYPE (arg1)), arg1);
6517 return pedantic_non_lvalue
6518 (negate_expr (convert (type,
6519 fold (build1 (ABS_EXPR,
6526 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6527 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6528 both transformations are correct when A is NaN: A != 0
6529 is then true, and A == 0 is false. */
6531 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6533 if (comp_code == NE_EXPR)
6534 return pedantic_non_lvalue (convert (type, arg1));
6535 else if (comp_code == EQ_EXPR)
6536 return pedantic_non_lvalue (convert (type, integer_zero_node));
6539 /* Try some transformations of A op B ? A : B.
6541 A == B? A : B same as B
6542 A != B? A : B same as A
6543 A >= B? A : B same as max (A, B)
6544 A > B? A : B same as max (B, A)
6545 A <= B? A : B same as min (A, B)
6546 A < B? A : B same as min (B, A)
6548 As above, these transformations don't work in the presence
6549 of signed zeros. For example, if A and B are zeros of
6550 opposite sign, the first two transformations will change
6551 the sign of the result. In the last four, the original
6552 expressions give different results for (A=+0, B=-0) and
6553 (A=-0, B=+0), but the transformed expressions do not.
6555 The first two transformations are correct if either A or B
6556 is a NaN. In the first transformation, the condition will
6557 be false, and B will indeed be chosen. In the case of the
6558 second transformation, the condition A != B will be true,
6559 and A will be chosen.
6561 The conversions to max() and min() are not correct if B is
6562 a number and A is not. The conditions in the original
6563 expressions will be false, so all four give B. The min()
6564 and max() versions would give a NaN instead. */
6565 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6566 arg2, TREE_OPERAND (arg0, 0)))
6568 tree comp_op0 = TREE_OPERAND (arg0, 0);
6569 tree comp_op1 = TREE_OPERAND (arg0, 1);
6570 tree comp_type = TREE_TYPE (comp_op0);
6572 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6573 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6579 return pedantic_non_lvalue (convert (type, arg2));
6581 return pedantic_non_lvalue (convert (type, arg1));
6584 /* In C++ a ?: expression can be an lvalue, so put the
6585 operand which will be used if they are equal first
6586 so that we can convert this back to the
6587 corresponding COND_EXPR. */
6588 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6589 return pedantic_non_lvalue
6590 (convert (type, fold (build (MIN_EXPR, comp_type,
6591 (comp_code == LE_EXPR
6592 ? comp_op0 : comp_op1),
6593 (comp_code == LE_EXPR
6594 ? comp_op1 : comp_op0)))));
6598 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6599 return pedantic_non_lvalue
6600 (convert (type, fold (build (MAX_EXPR, comp_type,
6601 (comp_code == GE_EXPR
6602 ? comp_op0 : comp_op1),
6603 (comp_code == GE_EXPR
6604 ? comp_op1 : comp_op0)))));
6611 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6612 we might still be able to simplify this. For example,
6613 if C1 is one less or one more than C2, this might have started
6614 out as a MIN or MAX and been transformed by this function.
6615 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6617 if (INTEGRAL_TYPE_P (type)
6618 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6619 && TREE_CODE (arg2) == INTEGER_CST)
6623 /* We can replace A with C1 in this case. */
6624 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6625 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6626 TREE_OPERAND (t, 2));
6630 /* If C1 is C2 + 1, this is min(A, C2). */
6631 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6632 && operand_equal_p (TREE_OPERAND (arg0, 1),
6633 const_binop (PLUS_EXPR, arg2,
6634 integer_one_node, 0), 1))
6635 return pedantic_non_lvalue
6636 (fold (build (MIN_EXPR, type, arg1, arg2)));
6640 /* If C1 is C2 - 1, this is min(A, C2). */
6641 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6642 && operand_equal_p (TREE_OPERAND (arg0, 1),
6643 const_binop (MINUS_EXPR, arg2,
6644 integer_one_node, 0), 1))
6645 return pedantic_non_lvalue
6646 (fold (build (MIN_EXPR, type, arg1, arg2)));
6650 /* If C1 is C2 - 1, this is max(A, C2). */
6651 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6652 && operand_equal_p (TREE_OPERAND (arg0, 1),
6653 const_binop (MINUS_EXPR, arg2,
6654 integer_one_node, 0), 1))
6655 return pedantic_non_lvalue
6656 (fold (build (MAX_EXPR, type, arg1, arg2)));
6660 /* If C1 is C2 + 1, this is max(A, C2). */
6661 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6662 && operand_equal_p (TREE_OPERAND (arg0, 1),
6663 const_binop (PLUS_EXPR, arg2,
6664 integer_one_node, 0), 1))
6665 return pedantic_non_lvalue
6666 (fold (build (MAX_EXPR, type, arg1, arg2)));
6675 /* If the second operand is simpler than the third, swap them
6676 since that produces better jump optimization results. */
6677 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
6678 || TREE_CODE (arg1) == SAVE_EXPR)
6679 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6680 || DECL_P (TREE_OPERAND (t, 2))
6681 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6683 /* See if this can be inverted. If it can't, possibly because
6684 it was a floating-point inequality comparison, don't do
6686 tem = invert_truthvalue (arg0);
6688 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6690 t = build (code, type, tem,
6691 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6693 /* arg1 should be the first argument of the new T. */
6694 arg1 = TREE_OPERAND (t, 1);
6699 /* Convert A ? 1 : 0 to simply A. */
6700 if (integer_onep (TREE_OPERAND (t, 1))
6701 && integer_zerop (TREE_OPERAND (t, 2))
6702 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6703 call to fold will try to move the conversion inside
6704 a COND, which will recurse. In that case, the COND_EXPR
6705 is probably the best choice, so leave it alone. */
6706 && type == TREE_TYPE (arg0))
6707 return pedantic_non_lvalue (arg0);
6709 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
6710 operation is simply A & 2. */
6712 if (integer_zerop (TREE_OPERAND (t, 2))
6713 && TREE_CODE (arg0) == NE_EXPR
6714 && integer_zerop (TREE_OPERAND (arg0, 1))
6715 && integer_pow2p (arg1)
6716 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6717 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6719 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6724 /* When pedantic, a compound expression can be neither an lvalue
6725 nor an integer constant expression. */
6726 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6728 /* Don't let (0, 0) be null pointer constant. */
6729 if (integer_zerop (arg1))
6730 return build1 (NOP_EXPR, type, arg1);
6731 return convert (type, arg1);
6735 return build_complex (type, arg0, arg1);
6739 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6741 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6742 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6743 TREE_OPERAND (arg0, 1));
6744 else if (TREE_CODE (arg0) == COMPLEX_CST)
6745 return TREE_REALPART (arg0);
6746 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6747 return fold (build (TREE_CODE (arg0), type,
6748 fold (build1 (REALPART_EXPR, type,
6749 TREE_OPERAND (arg0, 0))),
6750 fold (build1 (REALPART_EXPR,
6751 type, TREE_OPERAND (arg0, 1)))));
6755 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6756 return convert (type, integer_zero_node);
6757 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6758 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6759 TREE_OPERAND (arg0, 0));
6760 else if (TREE_CODE (arg0) == COMPLEX_CST)
6761 return TREE_IMAGPART (arg0);
6762 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6763 return fold (build (TREE_CODE (arg0), type,
6764 fold (build1 (IMAGPART_EXPR, type,
6765 TREE_OPERAND (arg0, 0))),
6766 fold (build1 (IMAGPART_EXPR, type,
6767 TREE_OPERAND (arg0, 1)))));
6770 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6772 case CLEANUP_POINT_EXPR:
6773 if (! has_cleanups (arg0))
6774 return TREE_OPERAND (t, 0);
6777 enum tree_code code0 = TREE_CODE (arg0);
6778 int kind0 = TREE_CODE_CLASS (code0);
6779 tree arg00 = TREE_OPERAND (arg0, 0);
6782 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6783 return fold (build1 (code0, type,
6784 fold (build1 (CLEANUP_POINT_EXPR,
6785 TREE_TYPE (arg00), arg00))));
6787 if (kind0 == '<' || kind0 == '2'
6788 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6789 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
6790 || code0 == TRUTH_XOR_EXPR)
6792 arg01 = TREE_OPERAND (arg0, 1);
6794 if (TREE_CONSTANT (arg00)
6795 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6796 && ! has_cleanups (arg00)))
6797 return fold (build (code0, type, arg00,
6798 fold (build1 (CLEANUP_POINT_EXPR,
6799 TREE_TYPE (arg01), arg01))));
6801 if (TREE_CONSTANT (arg01))
6802 return fold (build (code0, type,
6803 fold (build1 (CLEANUP_POINT_EXPR,
6804 TREE_TYPE (arg00), arg00)),
6812 /* Check for a built-in function. */
6813 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
6814 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
6816 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
6818 tree tmp = fold_builtin (expr);
6826 } /* switch (code) */
6829 /* Determine if first argument is a multiple of second argument. Return 0 if
6830 it is not, or we cannot easily determined it to be.
6832 An example of the sort of thing we care about (at this point; this routine
6833 could surely be made more general, and expanded to do what the *_DIV_EXPR's
6834 fold cases do now) is discovering that
6836 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6842 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
6844 This code also handles discovering that
6846 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6848 is a multiple of 8 so we don't have to worry about dealing with a
6851 Note that we *look* inside a SAVE_EXPR only to determine how it was
6852 calculated; it is not safe for fold to do much of anything else with the
6853 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
6854 at run time. For example, the latter example above *cannot* be implemented
6855 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
6856 evaluation time of the original SAVE_EXPR is not necessarily the same at
6857 the time the new expression is evaluated. The only optimization of this
6858 sort that would be valid is changing
6860 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6864 SAVE_EXPR (I) * SAVE_EXPR (J)
6866 (where the same SAVE_EXPR (J) is used in the original and the
6867 transformed version). */
6870 multiple_of_p (type, top, bottom)
6875 if (operand_equal_p (top, bottom, 0))
6878 if (TREE_CODE (type) != INTEGER_TYPE)
6881 switch (TREE_CODE (top))
6884 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6885 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6889 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6890 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6893 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
6897 op1 = TREE_OPERAND (top, 1);
6898 /* const_binop may not detect overflow correctly,
6899 so check for it explicitly here. */
6900 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
6901 > TREE_INT_CST_LOW (op1)
6902 && TREE_INT_CST_HIGH (op1) == 0
6903 && 0 != (t1 = convert (type,
6904 const_binop (LSHIFT_EXPR, size_one_node,
6906 && ! TREE_OVERFLOW (t1))
6907 return multiple_of_p (type, t1, bottom);
6912 /* Can't handle conversions from non-integral or wider integral type. */
6913 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6914 || (TYPE_PRECISION (type)
6915 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6918 /* .. fall through ... */
6921 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6924 if (TREE_CODE (bottom) != INTEGER_CST
6925 || (TREE_UNSIGNED (type)
6926 && (tree_int_cst_sgn (top) < 0
6927 || tree_int_cst_sgn (bottom) < 0)))
6929 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6937 /* Return true if `t' is known to be non-negative. */
6940 tree_expr_nonnegative_p (t)
6943 switch (TREE_CODE (t))
6949 return tree_int_cst_sgn (t) >= 0;
6950 case TRUNC_DIV_EXPR:
6952 case FLOOR_DIV_EXPR:
6953 case ROUND_DIV_EXPR:
6954 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6955 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6956 case TRUNC_MOD_EXPR:
6958 case FLOOR_MOD_EXPR:
6959 case ROUND_MOD_EXPR:
6960 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6962 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
6963 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
6965 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6967 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6968 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6970 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6971 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6973 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6975 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6977 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6978 case NON_LVALUE_EXPR:
6979 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6981 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
6984 if (truth_value_p (TREE_CODE (t)))
6985 /* Truth values evaluate to 0 or 1, which is nonnegative. */
6988 /* We don't know sign of `t', so be conservative and return false. */
6993 /* Return true if `r' is known to be non-negative.
6994 Only handles constants at the moment. */
6997 rtl_expr_nonnegative_p (r)
7000 switch (GET_CODE (r))
7003 return INTVAL (r) >= 0;
7006 if (GET_MODE (r) == VOIDmode)
7007 return CONST_DOUBLE_HIGH (r) >= 0;
7015 units = CONST_VECTOR_NUNITS (r);
7017 for (i = 0; i < units; ++i)
7019 elt = CONST_VECTOR_ELT (r, i);
7020 if (!rtl_expr_nonnegative_p (elt))
7029 /* These are always nonnegative. */