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 ((*lang_hooks.types.signed_or_unsigned_type)
1941 (unsignedp1, TREE_TYPE (primarg1)), primarg1);
1943 if (operand_equal_p (arg0, convert (type, primarg1), 0))
1950 /* See if ARG is an expression that is either a comparison or is performing
1951 arithmetic on comparisons. The comparisons must only be comparing
1952 two different values, which will be stored in *CVAL1 and *CVAL2; if
1953 they are non-zero it means that some operands have already been found.
1954 No variables may be used anywhere else in the expression except in the
1955 comparisons. If SAVE_P is true it means we removed a SAVE_EXPR around
1956 the expression and save_expr needs to be called with CVAL1 and CVAL2.
1958 If this is true, return 1. Otherwise, return zero. */
1961 twoval_comparison_p (arg, cval1, cval2, save_p)
1963 tree *cval1, *cval2;
1966 enum tree_code code = TREE_CODE (arg);
1967 char class = TREE_CODE_CLASS (code);
1969 /* We can handle some of the 'e' cases here. */
1970 if (class == 'e' && code == TRUTH_NOT_EXPR)
1972 else if (class == 'e'
1973 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
1974 || code == COMPOUND_EXPR))
1977 else if (class == 'e' && code == SAVE_EXPR && SAVE_EXPR_RTL (arg) == 0
1978 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
1980 /* If we've already found a CVAL1 or CVAL2, this expression is
1981 two complex to handle. */
1982 if (*cval1 || *cval2)
1992 return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
1995 return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
1996 && twoval_comparison_p (TREE_OPERAND (arg, 1),
1997 cval1, cval2, save_p));
2003 if (code == COND_EXPR)
2004 return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2005 cval1, cval2, save_p)
2006 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2007 cval1, cval2, save_p)
2008 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2009 cval1, cval2, save_p));
2013 /* First see if we can handle the first operand, then the second. For
2014 the second operand, we know *CVAL1 can't be zero. It must be that
2015 one side of the comparison is each of the values; test for the
2016 case where this isn't true by failing if the two operands
2019 if (operand_equal_p (TREE_OPERAND (arg, 0),
2020 TREE_OPERAND (arg, 1), 0))
2024 *cval1 = TREE_OPERAND (arg, 0);
2025 else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2027 else if (*cval2 == 0)
2028 *cval2 = TREE_OPERAND (arg, 0);
2029 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2034 if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2036 else if (*cval2 == 0)
2037 *cval2 = TREE_OPERAND (arg, 1);
2038 else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2050 /* ARG is a tree that is known to contain just arithmetic operations and
2051 comparisons. Evaluate the operations in the tree substituting NEW0 for
2052 any occurrence of OLD0 as an operand of a comparison and likewise for
2056 eval_subst (arg, old0, new0, old1, new1)
2058 tree old0, new0, old1, new1;
2060 tree type = TREE_TYPE (arg);
2061 enum tree_code code = TREE_CODE (arg);
2062 char class = TREE_CODE_CLASS (code);
2064 /* We can handle some of the 'e' cases here. */
2065 if (class == 'e' && code == TRUTH_NOT_EXPR)
2067 else if (class == 'e'
2068 && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2074 return fold (build1 (code, type,
2075 eval_subst (TREE_OPERAND (arg, 0),
2076 old0, new0, old1, new1)));
2079 return fold (build (code, type,
2080 eval_subst (TREE_OPERAND (arg, 0),
2081 old0, new0, old1, new1),
2082 eval_subst (TREE_OPERAND (arg, 1),
2083 old0, new0, old1, new1)));
2089 return eval_subst (TREE_OPERAND (arg, 0), old0, new0, old1, new1);
2092 return eval_subst (TREE_OPERAND (arg, 1), old0, new0, old1, new1);
2095 return fold (build (code, type,
2096 eval_subst (TREE_OPERAND (arg, 0),
2097 old0, new0, old1, new1),
2098 eval_subst (TREE_OPERAND (arg, 1),
2099 old0, new0, old1, new1),
2100 eval_subst (TREE_OPERAND (arg, 2),
2101 old0, new0, old1, new1)));
2105 /* fall through - ??? */
2109 tree arg0 = TREE_OPERAND (arg, 0);
2110 tree arg1 = TREE_OPERAND (arg, 1);
2112 /* We need to check both for exact equality and tree equality. The
2113 former will be true if the operand has a side-effect. In that
2114 case, we know the operand occurred exactly once. */
2116 if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2118 else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2121 if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2123 else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2126 return fold (build (code, type, arg0, arg1));
2134 /* Return a tree for the case when the result of an expression is RESULT
2135 converted to TYPE and OMITTED was previously an operand of the expression
2136 but is now not needed (e.g., we folded OMITTED * 0).
2138 If OMITTED has side effects, we must evaluate it. Otherwise, just do
2139 the conversion of RESULT to TYPE. */
2142 omit_one_operand (type, result, omitted)
2143 tree type, result, omitted;
2145 tree t = convert (type, result);
2147 if (TREE_SIDE_EFFECTS (omitted))
2148 return build (COMPOUND_EXPR, type, omitted, t);
2150 return non_lvalue (t);
2153 /* Similar, but call pedantic_non_lvalue instead of non_lvalue. */
2156 pedantic_omit_one_operand (type, result, omitted)
2157 tree type, result, omitted;
2159 tree t = convert (type, result);
2161 if (TREE_SIDE_EFFECTS (omitted))
2162 return build (COMPOUND_EXPR, type, omitted, t);
2164 return pedantic_non_lvalue (t);
2167 /* Return a simplified tree node for the truth-negation of ARG. This
2168 never alters ARG itself. We assume that ARG is an operation that
2169 returns a truth value (0 or 1). */
2172 invert_truthvalue (arg)
2175 tree type = TREE_TYPE (arg);
2176 enum tree_code code = TREE_CODE (arg);
2178 if (code == ERROR_MARK)
2181 /* If this is a comparison, we can simply invert it, except for
2182 floating-point non-equality comparisons, in which case we just
2183 enclose a TRUTH_NOT_EXPR around what we have. */
2185 if (TREE_CODE_CLASS (code) == '<')
2187 if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
2188 && !flag_unsafe_math_optimizations
2191 return build1 (TRUTH_NOT_EXPR, type, arg);
2193 return build (invert_tree_comparison (code), type,
2194 TREE_OPERAND (arg, 0), TREE_OPERAND (arg, 1));
2200 return convert (type, build_int_2 (integer_zerop (arg), 0));
2202 case TRUTH_AND_EXPR:
2203 return build (TRUTH_OR_EXPR, type,
2204 invert_truthvalue (TREE_OPERAND (arg, 0)),
2205 invert_truthvalue (TREE_OPERAND (arg, 1)));
2208 return build (TRUTH_AND_EXPR, type,
2209 invert_truthvalue (TREE_OPERAND (arg, 0)),
2210 invert_truthvalue (TREE_OPERAND (arg, 1)));
2212 case TRUTH_XOR_EXPR:
2213 /* Here we can invert either operand. We invert the first operand
2214 unless the second operand is a TRUTH_NOT_EXPR in which case our
2215 result is the XOR of the first operand with the inside of the
2216 negation of the second operand. */
2218 if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
2219 return build (TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
2220 TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
2222 return build (TRUTH_XOR_EXPR, type,
2223 invert_truthvalue (TREE_OPERAND (arg, 0)),
2224 TREE_OPERAND (arg, 1));
2226 case TRUTH_ANDIF_EXPR:
2227 return build (TRUTH_ORIF_EXPR, type,
2228 invert_truthvalue (TREE_OPERAND (arg, 0)),
2229 invert_truthvalue (TREE_OPERAND (arg, 1)));
2231 case TRUTH_ORIF_EXPR:
2232 return build (TRUTH_ANDIF_EXPR, type,
2233 invert_truthvalue (TREE_OPERAND (arg, 0)),
2234 invert_truthvalue (TREE_OPERAND (arg, 1)));
2236 case TRUTH_NOT_EXPR:
2237 return TREE_OPERAND (arg, 0);
2240 return build (COND_EXPR, type, TREE_OPERAND (arg, 0),
2241 invert_truthvalue (TREE_OPERAND (arg, 1)),
2242 invert_truthvalue (TREE_OPERAND (arg, 2)));
2245 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg, 0),
2246 invert_truthvalue (TREE_OPERAND (arg, 1)));
2248 case WITH_RECORD_EXPR:
2249 return build (WITH_RECORD_EXPR, type,
2250 invert_truthvalue (TREE_OPERAND (arg, 0)),
2251 TREE_OPERAND (arg, 1));
2253 case NON_LVALUE_EXPR:
2254 return invert_truthvalue (TREE_OPERAND (arg, 0));
2259 return build1 (TREE_CODE (arg), type,
2260 invert_truthvalue (TREE_OPERAND (arg, 0)));
2263 if (!integer_onep (TREE_OPERAND (arg, 1)))
2265 return build (EQ_EXPR, type, arg, convert (type, integer_zero_node));
2268 return build1 (TRUTH_NOT_EXPR, type, arg);
2270 case CLEANUP_POINT_EXPR:
2271 return build1 (CLEANUP_POINT_EXPR, type,
2272 invert_truthvalue (TREE_OPERAND (arg, 0)));
2277 if (TREE_CODE (TREE_TYPE (arg)) != BOOLEAN_TYPE)
2279 return build1 (TRUTH_NOT_EXPR, type, arg);
2282 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
2283 operands are another bit-wise operation with a common input. If so,
2284 distribute the bit operations to save an operation and possibly two if
2285 constants are involved. For example, convert
2286 (A | B) & (A | C) into A | (B & C)
2287 Further simplification will occur if B and C are constants.
2289 If this optimization cannot be done, 0 will be returned. */
2292 distribute_bit_expr (code, type, arg0, arg1)
2293 enum tree_code code;
2300 if (TREE_CODE (arg0) != TREE_CODE (arg1)
2301 || TREE_CODE (arg0) == code
2302 || (TREE_CODE (arg0) != BIT_AND_EXPR
2303 && TREE_CODE (arg0) != BIT_IOR_EXPR))
2306 if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
2308 common = TREE_OPERAND (arg0, 0);
2309 left = TREE_OPERAND (arg0, 1);
2310 right = TREE_OPERAND (arg1, 1);
2312 else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
2314 common = TREE_OPERAND (arg0, 0);
2315 left = TREE_OPERAND (arg0, 1);
2316 right = TREE_OPERAND (arg1, 0);
2318 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
2320 common = TREE_OPERAND (arg0, 1);
2321 left = TREE_OPERAND (arg0, 0);
2322 right = TREE_OPERAND (arg1, 1);
2324 else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
2326 common = TREE_OPERAND (arg0, 1);
2327 left = TREE_OPERAND (arg0, 0);
2328 right = TREE_OPERAND (arg1, 0);
2333 return fold (build (TREE_CODE (arg0), type, common,
2334 fold (build (code, type, left, right))));
2337 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
2338 starting at BITPOS. The field is unsigned if UNSIGNEDP is non-zero. */
2341 make_bit_field_ref (inner, type, bitsize, bitpos, unsignedp)
2344 int bitsize, bitpos;
2347 tree result = build (BIT_FIELD_REF, type, inner,
2348 size_int (bitsize), bitsize_int (bitpos));
2350 TREE_UNSIGNED (result) = unsignedp;
2355 /* Optimize a bit-field compare.
2357 There are two cases: First is a compare against a constant and the
2358 second is a comparison of two items where the fields are at the same
2359 bit position relative to the start of a chunk (byte, halfword, word)
2360 large enough to contain it. In these cases we can avoid the shift
2361 implicit in bitfield extractions.
2363 For constants, we emit a compare of the shifted constant with the
2364 BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
2365 compared. For two fields at the same position, we do the ANDs with the
2366 similar mask and compare the result of the ANDs.
2368 CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
2369 COMPARE_TYPE is the type of the comparison, and LHS and RHS
2370 are the left and right operands of the comparison, respectively.
2372 If the optimization described above can be done, we return the resulting
2373 tree. Otherwise we return zero. */
2376 optimize_bit_field_compare (code, compare_type, lhs, rhs)
2377 enum tree_code code;
2381 HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
2382 tree type = TREE_TYPE (lhs);
2383 tree signed_type, unsigned_type;
2384 int const_p = TREE_CODE (rhs) == INTEGER_CST;
2385 enum machine_mode lmode, rmode, nmode;
2386 int lunsignedp, runsignedp;
2387 int lvolatilep = 0, rvolatilep = 0;
2388 tree linner, rinner = NULL_TREE;
2392 /* Get all the information about the extractions being done. If the bit size
2393 if the same as the size of the underlying object, we aren't doing an
2394 extraction at all and so can do nothing. We also don't want to
2395 do anything if the inner expression is a PLACEHOLDER_EXPR since we
2396 then will no longer be able to replace it. */
2397 linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
2398 &lunsignedp, &lvolatilep);
2399 if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
2400 || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
2405 /* If this is not a constant, we can only do something if bit positions,
2406 sizes, and signedness are the same. */
2407 rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
2408 &runsignedp, &rvolatilep);
2410 if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
2411 || lunsignedp != runsignedp || offset != 0
2412 || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
2416 /* See if we can find a mode to refer to this field. We should be able to,
2417 but fail if we can't. */
2418 nmode = get_best_mode (lbitsize, lbitpos,
2419 const_p ? TYPE_ALIGN (TREE_TYPE (linner))
2420 : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
2421 TYPE_ALIGN (TREE_TYPE (rinner))),
2422 word_mode, lvolatilep || rvolatilep);
2423 if (nmode == VOIDmode)
2426 /* Set signed and unsigned types of the precision of this mode for the
2428 signed_type = (*lang_hooks.types.type_for_mode) (nmode, 0);
2429 unsigned_type = (*lang_hooks.types.type_for_mode) (nmode, 1);
2431 /* Compute the bit position and size for the new reference and our offset
2432 within it. If the new reference is the same size as the original, we
2433 won't optimize anything, so return zero. */
2434 nbitsize = GET_MODE_BITSIZE (nmode);
2435 nbitpos = lbitpos & ~ (nbitsize - 1);
2437 if (nbitsize == lbitsize)
2440 if (BYTES_BIG_ENDIAN)
2441 lbitpos = nbitsize - lbitsize - lbitpos;
2443 /* Make the mask to be used against the extracted field. */
2444 mask = build_int_2 (~0, ~0);
2445 TREE_TYPE (mask) = unsigned_type;
2446 force_fit_type (mask, 0);
2447 mask = convert (unsigned_type, mask);
2448 mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize), 0);
2449 mask = const_binop (RSHIFT_EXPR, mask,
2450 size_int (nbitsize - lbitsize - lbitpos), 0);
2453 /* If not comparing with constant, just rework the comparison
2455 return build (code, compare_type,
2456 build (BIT_AND_EXPR, unsigned_type,
2457 make_bit_field_ref (linner, unsigned_type,
2458 nbitsize, nbitpos, 1),
2460 build (BIT_AND_EXPR, unsigned_type,
2461 make_bit_field_ref (rinner, unsigned_type,
2462 nbitsize, nbitpos, 1),
2465 /* Otherwise, we are handling the constant case. See if the constant is too
2466 big for the field. Warn and return a tree of for 0 (false) if so. We do
2467 this not only for its own sake, but to avoid having to test for this
2468 error case below. If we didn't, we might generate wrong code.
2470 For unsigned fields, the constant shifted right by the field length should
2471 be all zero. For signed fields, the high-order bits should agree with
2476 if (! integer_zerop (const_binop (RSHIFT_EXPR,
2477 convert (unsigned_type, rhs),
2478 size_int (lbitsize), 0)))
2480 warning ("comparison is always %d due to width of bit-field",
2482 return convert (compare_type,
2484 ? integer_one_node : integer_zero_node));
2489 tree tem = const_binop (RSHIFT_EXPR, convert (signed_type, rhs),
2490 size_int (lbitsize - 1), 0);
2491 if (! integer_zerop (tem) && ! integer_all_onesp (tem))
2493 warning ("comparison is always %d due to width of bit-field",
2495 return convert (compare_type,
2497 ? integer_one_node : integer_zero_node));
2501 /* Single-bit compares should always be against zero. */
2502 if (lbitsize == 1 && ! integer_zerop (rhs))
2504 code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
2505 rhs = convert (type, integer_zero_node);
2508 /* Make a new bitfield reference, shift the constant over the
2509 appropriate number of bits and mask it with the computed mask
2510 (in case this was a signed field). If we changed it, make a new one. */
2511 lhs = make_bit_field_ref (linner, unsigned_type, nbitsize, nbitpos, 1);
2514 TREE_SIDE_EFFECTS (lhs) = 1;
2515 TREE_THIS_VOLATILE (lhs) = 1;
2518 rhs = fold (const_binop (BIT_AND_EXPR,
2519 const_binop (LSHIFT_EXPR,
2520 convert (unsigned_type, rhs),
2521 size_int (lbitpos), 0),
2524 return build (code, compare_type,
2525 build (BIT_AND_EXPR, unsigned_type, lhs, mask),
2529 /* Subroutine for fold_truthop: decode a field reference.
2531 If EXP is a comparison reference, we return the innermost reference.
2533 *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
2534 set to the starting bit number.
2536 If the innermost field can be completely contained in a mode-sized
2537 unit, *PMODE is set to that mode. Otherwise, it is set to VOIDmode.
2539 *PVOLATILEP is set to 1 if the any expression encountered is volatile;
2540 otherwise it is not changed.
2542 *PUNSIGNEDP is set to the signedness of the field.
2544 *PMASK is set to the mask used. This is either contained in a
2545 BIT_AND_EXPR or derived from the width of the field.
2547 *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
2549 Return 0 if this is not a component reference or is one that we can't
2550 do anything with. */
2553 decode_field_reference (exp, pbitsize, pbitpos, pmode, punsignedp,
2554 pvolatilep, pmask, pand_mask)
2556 HOST_WIDE_INT *pbitsize, *pbitpos;
2557 enum machine_mode *pmode;
2558 int *punsignedp, *pvolatilep;
2563 tree mask, inner, offset;
2565 unsigned int precision;
2567 /* All the optimizations using this function assume integer fields.
2568 There are problems with FP fields since the type_for_size call
2569 below can fail for, e.g., XFmode. */
2570 if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
2575 if (TREE_CODE (exp) == BIT_AND_EXPR)
2577 and_mask = TREE_OPERAND (exp, 1);
2578 exp = TREE_OPERAND (exp, 0);
2579 STRIP_NOPS (exp); STRIP_NOPS (and_mask);
2580 if (TREE_CODE (and_mask) != INTEGER_CST)
2584 inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
2585 punsignedp, pvolatilep);
2586 if ((inner == exp && and_mask == 0)
2587 || *pbitsize < 0 || offset != 0
2588 || TREE_CODE (inner) == PLACEHOLDER_EXPR)
2591 /* Compute the mask to access the bitfield. */
2592 unsigned_type = (*lang_hooks.types.type_for_size) (*pbitsize, 1);
2593 precision = TYPE_PRECISION (unsigned_type);
2595 mask = build_int_2 (~0, ~0);
2596 TREE_TYPE (mask) = unsigned_type;
2597 force_fit_type (mask, 0);
2598 mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2599 mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize), 0);
2601 /* Merge it with the mask we found in the BIT_AND_EXPR, if any. */
2603 mask = fold (build (BIT_AND_EXPR, unsigned_type,
2604 convert (unsigned_type, and_mask), mask));
2607 *pand_mask = and_mask;
2611 /* Return non-zero if MASK represents a mask of SIZE ones in the low-order
2615 all_ones_mask_p (mask, size)
2619 tree type = TREE_TYPE (mask);
2620 unsigned int precision = TYPE_PRECISION (type);
2623 tmask = build_int_2 (~0, ~0);
2624 TREE_TYPE (tmask) = (*lang_hooks.types.signed_type) (type);
2625 force_fit_type (tmask, 0);
2627 tree_int_cst_equal (mask,
2628 const_binop (RSHIFT_EXPR,
2629 const_binop (LSHIFT_EXPR, tmask,
2630 size_int (precision - size),
2632 size_int (precision - size), 0));
2635 /* Subroutine for fold_truthop: determine if an operand is simple enough
2636 to be evaluated unconditionally. */
2639 simple_operand_p (exp)
2642 /* Strip any conversions that don't change the machine mode. */
2643 while ((TREE_CODE (exp) == NOP_EXPR
2644 || TREE_CODE (exp) == CONVERT_EXPR)
2645 && (TYPE_MODE (TREE_TYPE (exp))
2646 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
2647 exp = TREE_OPERAND (exp, 0);
2649 return (TREE_CODE_CLASS (TREE_CODE (exp)) == 'c'
2651 && ! TREE_ADDRESSABLE (exp)
2652 && ! TREE_THIS_VOLATILE (exp)
2653 && ! DECL_NONLOCAL (exp)
2654 /* Don't regard global variables as simple. They may be
2655 allocated in ways unknown to the compiler (shared memory,
2656 #pragma weak, etc). */
2657 && ! TREE_PUBLIC (exp)
2658 && ! DECL_EXTERNAL (exp)
2659 /* Loading a static variable is unduly expensive, but global
2660 registers aren't expensive. */
2661 && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
2664 /* The following functions are subroutines to fold_range_test and allow it to
2665 try to change a logical combination of comparisons into a range test.
2668 X == 2 || X == 3 || X == 4 || X == 5
2672 (unsigned) (X - 2) <= 3
2674 We describe each set of comparisons as being either inside or outside
2675 a range, using a variable named like IN_P, and then describe the
2676 range with a lower and upper bound. If one of the bounds is omitted,
2677 it represents either the highest or lowest value of the type.
2679 In the comments below, we represent a range by two numbers in brackets
2680 preceded by a "+" to designate being inside that range, or a "-" to
2681 designate being outside that range, so the condition can be inverted by
2682 flipping the prefix. An omitted bound is represented by a "-". For
2683 example, "- [-, 10]" means being outside the range starting at the lowest
2684 possible value and ending at 10, in other words, being greater than 10.
2685 The range "+ [-, -]" is always true and hence the range "- [-, -]" is
2688 We set up things so that the missing bounds are handled in a consistent
2689 manner so neither a missing bound nor "true" and "false" need to be
2690 handled using a special case. */
2692 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
2693 of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
2694 and UPPER1_P are nonzero if the respective argument is an upper bound
2695 and zero for a lower. TYPE, if nonzero, is the type of the result; it
2696 must be specified for a comparison. ARG1 will be converted to ARG0's
2697 type if both are specified. */
2700 range_binop (code, type, arg0, upper0_p, arg1, upper1_p)
2701 enum tree_code code;
2704 int upper0_p, upper1_p;
2710 /* If neither arg represents infinity, do the normal operation.
2711 Else, if not a comparison, return infinity. Else handle the special
2712 comparison rules. Note that most of the cases below won't occur, but
2713 are handled for consistency. */
2715 if (arg0 != 0 && arg1 != 0)
2717 tem = fold (build (code, type != 0 ? type : TREE_TYPE (arg0),
2718 arg0, convert (TREE_TYPE (arg0), arg1)));
2720 return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
2723 if (TREE_CODE_CLASS (code) != '<')
2726 /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
2727 for neither. In real maths, we cannot assume open ended ranges are
2728 the same. But, this is computer arithmetic, where numbers are finite.
2729 We can therefore make the transformation of any unbounded range with
2730 the value Z, Z being greater than any representable number. This permits
2731 us to treat unbounded ranges as equal. */
2732 sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
2733 sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
2737 result = sgn0 == sgn1;
2740 result = sgn0 != sgn1;
2743 result = sgn0 < sgn1;
2746 result = sgn0 <= sgn1;
2749 result = sgn0 > sgn1;
2752 result = sgn0 >= sgn1;
2758 return convert (type, result ? integer_one_node : integer_zero_node);
2761 /* Given EXP, a logical expression, set the range it is testing into
2762 variables denoted by PIN_P, PLOW, and PHIGH. Return the expression
2763 actually being tested. *PLOW and *PHIGH will be made of the same type
2764 as the returned expression. If EXP is not a comparison, we will most
2765 likely not be returning a useful value and range. */
2768 make_range (exp, pin_p, plow, phigh)
2773 enum tree_code code;
2774 tree arg0 = NULL_TREE, arg1 = NULL_TREE, type = NULL_TREE;
2775 tree orig_type = NULL_TREE;
2777 tree low, high, n_low, n_high;
2779 /* Start with simply saying "EXP != 0" and then look at the code of EXP
2780 and see if we can refine the range. Some of the cases below may not
2781 happen, but it doesn't seem worth worrying about this. We "continue"
2782 the outer loop when we've changed something; otherwise we "break"
2783 the switch, which will "break" the while. */
2785 in_p = 0, low = high = convert (TREE_TYPE (exp), integer_zero_node);
2789 code = TREE_CODE (exp);
2791 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2793 arg0 = TREE_OPERAND (exp, 0);
2794 if (TREE_CODE_CLASS (code) == '<'
2795 || TREE_CODE_CLASS (code) == '1'
2796 || TREE_CODE_CLASS (code) == '2')
2797 type = TREE_TYPE (arg0);
2798 if (TREE_CODE_CLASS (code) == '2'
2799 || TREE_CODE_CLASS (code) == '<'
2800 || (TREE_CODE_CLASS (code) == 'e'
2801 && TREE_CODE_LENGTH (code) > 1))
2802 arg1 = TREE_OPERAND (exp, 1);
2805 /* Set ORIG_TYPE as soon as TYPE is non-null so that we do not
2806 lose a cast by accident. */
2807 if (type != NULL_TREE && orig_type == NULL_TREE)
2812 case TRUTH_NOT_EXPR:
2813 in_p = ! in_p, exp = arg0;
2816 case EQ_EXPR: case NE_EXPR:
2817 case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
2818 /* We can only do something if the range is testing for zero
2819 and if the second operand is an integer constant. Note that
2820 saying something is "in" the range we make is done by
2821 complementing IN_P since it will set in the initial case of
2822 being not equal to zero; "out" is leaving it alone. */
2823 if (low == 0 || high == 0
2824 || ! integer_zerop (low) || ! integer_zerop (high)
2825 || TREE_CODE (arg1) != INTEGER_CST)
2830 case NE_EXPR: /* - [c, c] */
2833 case EQ_EXPR: /* + [c, c] */
2834 in_p = ! in_p, low = high = arg1;
2836 case GT_EXPR: /* - [-, c] */
2837 low = 0, high = arg1;
2839 case GE_EXPR: /* + [c, -] */
2840 in_p = ! in_p, low = arg1, high = 0;
2842 case LT_EXPR: /* - [c, -] */
2843 low = arg1, high = 0;
2845 case LE_EXPR: /* + [-, c] */
2846 in_p = ! in_p, low = 0, high = arg1;
2854 /* If this is an unsigned comparison, we also know that EXP is
2855 greater than or equal to zero. We base the range tests we make
2856 on that fact, so we record it here so we can parse existing
2858 if (TREE_UNSIGNED (type) && (low == 0 || high == 0))
2860 if (! merge_ranges (&n_in_p, &n_low, &n_high, in_p, low, high,
2861 1, convert (type, integer_zero_node),
2865 in_p = n_in_p, low = n_low, high = n_high;
2867 /* If the high bound is missing, but we
2868 have a low bound, reverse the range so
2869 it goes from zero to the low bound minus 1. */
2870 if (high == 0 && low)
2873 high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
2874 integer_one_node, 0);
2875 low = convert (type, integer_zero_node);
2881 /* (-x) IN [a,b] -> x in [-b, -a] */
2882 n_low = range_binop (MINUS_EXPR, type,
2883 convert (type, integer_zero_node), 0, high, 1);
2884 n_high = range_binop (MINUS_EXPR, type,
2885 convert (type, integer_zero_node), 0, low, 0);
2886 low = n_low, high = n_high;
2892 exp = build (MINUS_EXPR, type, negate_expr (arg0),
2893 convert (type, integer_one_node));
2896 case PLUS_EXPR: case MINUS_EXPR:
2897 if (TREE_CODE (arg1) != INTEGER_CST)
2900 /* If EXP is signed, any overflow in the computation is undefined,
2901 so we don't worry about it so long as our computations on
2902 the bounds don't overflow. For unsigned, overflow is defined
2903 and this is exactly the right thing. */
2904 n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2905 type, low, 0, arg1, 0);
2906 n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
2907 type, high, 1, arg1, 0);
2908 if ((n_low != 0 && TREE_OVERFLOW (n_low))
2909 || (n_high != 0 && TREE_OVERFLOW (n_high)))
2912 /* Check for an unsigned range which has wrapped around the maximum
2913 value thus making n_high < n_low, and normalize it. */
2914 if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
2916 low = range_binop (PLUS_EXPR, type, n_high, 0,
2917 integer_one_node, 0);
2918 high = range_binop (MINUS_EXPR, type, n_low, 0,
2919 integer_one_node, 0);
2921 /* If the range is of the form +/- [ x+1, x ], we won't
2922 be able to normalize it. But then, it represents the
2923 whole range or the empty set, so make it
2925 if (tree_int_cst_equal (n_low, low)
2926 && tree_int_cst_equal (n_high, high))
2932 low = n_low, high = n_high;
2937 case NOP_EXPR: case NON_LVALUE_EXPR: case CONVERT_EXPR:
2938 if (TYPE_PRECISION (type) > TYPE_PRECISION (orig_type))
2941 if (! INTEGRAL_TYPE_P (type)
2942 || (low != 0 && ! int_fits_type_p (low, type))
2943 || (high != 0 && ! int_fits_type_p (high, type)))
2946 n_low = low, n_high = high;
2949 n_low = convert (type, n_low);
2952 n_high = convert (type, n_high);
2954 /* If we're converting from an unsigned to a signed type,
2955 we will be doing the comparison as unsigned. The tests above
2956 have already verified that LOW and HIGH are both positive.
2958 So we have to make sure that the original unsigned value will
2959 be interpreted as positive. */
2960 if (TREE_UNSIGNED (type) && ! TREE_UNSIGNED (TREE_TYPE (exp)))
2962 tree equiv_type = (*lang_hooks.types.type_for_mode)
2963 (TYPE_MODE (type), 1);
2966 /* A range without an upper bound is, naturally, unbounded.
2967 Since convert would have cropped a very large value, use
2968 the max value for the destination type. */
2970 = TYPE_MAX_VALUE (equiv_type) ? TYPE_MAX_VALUE (equiv_type)
2971 : TYPE_MAX_VALUE (type);
2973 high_positive = fold (build (RSHIFT_EXPR, type,
2974 convert (type, high_positive),
2975 convert (type, integer_one_node)));
2977 /* If the low bound is specified, "and" the range with the
2978 range for which the original unsigned value will be
2982 if (! merge_ranges (&n_in_p, &n_low, &n_high,
2984 1, convert (type, integer_zero_node),
2988 in_p = (n_in_p == in_p);
2992 /* Otherwise, "or" the range with the range of the input
2993 that will be interpreted as negative. */
2994 if (! merge_ranges (&n_in_p, &n_low, &n_high,
2996 1, convert (type, integer_zero_node),
3000 in_p = (in_p != n_in_p);
3005 low = n_low, high = n_high;
3015 /* If EXP is a constant, we can evaluate whether this is true or false. */
3016 if (TREE_CODE (exp) == INTEGER_CST)
3018 in_p = in_p == (integer_onep (range_binop (GE_EXPR, integer_type_node,
3020 && integer_onep (range_binop (LE_EXPR, integer_type_node,
3026 *pin_p = in_p, *plow = low, *phigh = high;
3030 /* Given a range, LOW, HIGH, and IN_P, an expression, EXP, and a result
3031 type, TYPE, return an expression to test if EXP is in (or out of, depending
3032 on IN_P) the range. */
3035 build_range_check (type, exp, in_p, low, high)
3041 tree etype = TREE_TYPE (exp);
3045 && (0 != (value = build_range_check (type, exp, 1, low, high))))
3046 return invert_truthvalue (value);
3048 else if (low == 0 && high == 0)
3049 return convert (type, integer_one_node);
3052 return fold (build (LE_EXPR, type, exp, high));
3055 return fold (build (GE_EXPR, type, exp, low));
3057 else if (operand_equal_p (low, high, 0))
3058 return fold (build (EQ_EXPR, type, exp, low));
3060 else if (TREE_UNSIGNED (etype) && integer_zerop (low))
3061 return build_range_check (type, exp, 1, 0, high);
3063 else if (integer_zerop (low))
3065 utype = (*lang_hooks.types.unsigned_type) (etype);
3066 return build_range_check (type, convert (utype, exp), 1, 0,
3067 convert (utype, high));
3070 else if (0 != (value = const_binop (MINUS_EXPR, high, low, 0))
3071 && ! TREE_OVERFLOW (value))
3072 return build_range_check (type,
3073 fold (build (MINUS_EXPR, etype, exp, low)),
3074 1, convert (etype, integer_zero_node), value);
3079 /* Given two ranges, see if we can merge them into one. Return 1 if we
3080 can, 0 if we can't. Set the output range into the specified parameters. */
3083 merge_ranges (pin_p, plow, phigh, in0_p, low0, high0, in1_p, low1, high1)
3087 tree low0, high0, low1, high1;
3095 int lowequal = ((low0 == 0 && low1 == 0)
3096 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3097 low0, 0, low1, 0)));
3098 int highequal = ((high0 == 0 && high1 == 0)
3099 || integer_onep (range_binop (EQ_EXPR, integer_type_node,
3100 high0, 1, high1, 1)));
3102 /* Make range 0 be the range that starts first, or ends last if they
3103 start at the same value. Swap them if it isn't. */
3104 if (integer_onep (range_binop (GT_EXPR, integer_type_node,
3107 && integer_onep (range_binop (GT_EXPR, integer_type_node,
3108 high1, 1, high0, 1))))
3110 temp = in0_p, in0_p = in1_p, in1_p = temp;
3111 tem = low0, low0 = low1, low1 = tem;
3112 tem = high0, high0 = high1, high1 = tem;
3115 /* Now flag two cases, whether the ranges are disjoint or whether the
3116 second range is totally subsumed in the first. Note that the tests
3117 below are simplified by the ones above. */
3118 no_overlap = integer_onep (range_binop (LT_EXPR, integer_type_node,
3119 high0, 1, low1, 0));
3120 subset = integer_onep (range_binop (LE_EXPR, integer_type_node,
3121 high1, 1, high0, 1));
3123 /* We now have four cases, depending on whether we are including or
3124 excluding the two ranges. */
3127 /* If they don't overlap, the result is false. If the second range
3128 is a subset it is the result. Otherwise, the range is from the start
3129 of the second to the end of the first. */
3131 in_p = 0, low = high = 0;
3133 in_p = 1, low = low1, high = high1;
3135 in_p = 1, low = low1, high = high0;
3138 else if (in0_p && ! in1_p)
3140 /* If they don't overlap, the result is the first range. If they are
3141 equal, the result is false. If the second range is a subset of the
3142 first, and the ranges begin at the same place, we go from just after
3143 the end of the first range to the end of the second. If the second
3144 range is not a subset of the first, or if it is a subset and both
3145 ranges end at the same place, the range starts at the start of the
3146 first range and ends just before the second range.
3147 Otherwise, we can't describe this as a single range. */
3149 in_p = 1, low = low0, high = high0;
3150 else if (lowequal && highequal)
3151 in_p = 0, low = high = 0;
3152 else if (subset && lowequal)
3154 in_p = 1, high = high0;
3155 low = range_binop (PLUS_EXPR, NULL_TREE, high1, 0,
3156 integer_one_node, 0);
3158 else if (! subset || highequal)
3160 in_p = 1, low = low0;
3161 high = range_binop (MINUS_EXPR, NULL_TREE, low1, 0,
3162 integer_one_node, 0);
3168 else if (! in0_p && in1_p)
3170 /* If they don't overlap, the result is the second range. If the second
3171 is a subset of the first, the result is false. Otherwise,
3172 the range starts just after the first range and ends at the
3173 end of the second. */
3175 in_p = 1, low = low1, high = high1;
3176 else if (subset || highequal)
3177 in_p = 0, low = high = 0;
3180 in_p = 1, high = high1;
3181 low = range_binop (PLUS_EXPR, NULL_TREE, high0, 1,
3182 integer_one_node, 0);
3188 /* The case where we are excluding both ranges. Here the complex case
3189 is if they don't overlap. In that case, the only time we have a
3190 range is if they are adjacent. If the second is a subset of the
3191 first, the result is the first. Otherwise, the range to exclude
3192 starts at the beginning of the first range and ends at the end of the
3196 if (integer_onep (range_binop (EQ_EXPR, integer_type_node,
3197 range_binop (PLUS_EXPR, NULL_TREE,
3199 integer_one_node, 1),
3201 in_p = 0, low = low0, high = high1;
3206 in_p = 0, low = low0, high = high0;
3208 in_p = 0, low = low0, high = high1;
3211 *pin_p = in_p, *plow = low, *phigh = high;
3215 /* EXP is some logical combination of boolean tests. See if we can
3216 merge it into some range test. Return the new tree if so. */
3219 fold_range_test (exp)
3222 int or_op = (TREE_CODE (exp) == TRUTH_ORIF_EXPR
3223 || TREE_CODE (exp) == TRUTH_OR_EXPR);
3224 int in0_p, in1_p, in_p;
3225 tree low0, low1, low, high0, high1, high;
3226 tree lhs = make_range (TREE_OPERAND (exp, 0), &in0_p, &low0, &high0);
3227 tree rhs = make_range (TREE_OPERAND (exp, 1), &in1_p, &low1, &high1);
3230 /* If this is an OR operation, invert both sides; we will invert
3231 again at the end. */
3233 in0_p = ! in0_p, in1_p = ! in1_p;
3235 /* If both expressions are the same, if we can merge the ranges, and we
3236 can build the range test, return it or it inverted. If one of the
3237 ranges is always true or always false, consider it to be the same
3238 expression as the other. */
3239 if ((lhs == 0 || rhs == 0 || operand_equal_p (lhs, rhs, 0))
3240 && merge_ranges (&in_p, &low, &high, in0_p, low0, high0,
3242 && 0 != (tem = (build_range_check (TREE_TYPE (exp),
3244 : rhs != 0 ? rhs : integer_zero_node,
3246 return or_op ? invert_truthvalue (tem) : tem;
3248 /* On machines where the branch cost is expensive, if this is a
3249 short-circuited branch and the underlying object on both sides
3250 is the same, make a non-short-circuit operation. */
3251 else if (BRANCH_COST >= 2
3252 && lhs != 0 && rhs != 0
3253 && (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3254 || TREE_CODE (exp) == TRUTH_ORIF_EXPR)
3255 && operand_equal_p (lhs, rhs, 0))
3257 /* If simple enough, just rewrite. Otherwise, make a SAVE_EXPR
3258 unless we are at top level or LHS contains a PLACEHOLDER_EXPR, in
3259 which cases we can't do this. */
3260 if (simple_operand_p (lhs))
3261 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3262 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3263 TREE_TYPE (exp), TREE_OPERAND (exp, 0),
3264 TREE_OPERAND (exp, 1));
3266 else if ((*lang_hooks.decls.global_bindings_p) () == 0
3267 && ! contains_placeholder_p (lhs))
3269 tree common = save_expr (lhs);
3271 if (0 != (lhs = build_range_check (TREE_TYPE (exp), common,
3272 or_op ? ! in0_p : in0_p,
3274 && (0 != (rhs = build_range_check (TREE_TYPE (exp), common,
3275 or_op ? ! in1_p : in1_p,
3277 return build (TREE_CODE (exp) == TRUTH_ANDIF_EXPR
3278 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR,
3279 TREE_TYPE (exp), lhs, rhs);
3286 /* Subroutine for fold_truthop: C is an INTEGER_CST interpreted as a P
3287 bit value. Arrange things so the extra bits will be set to zero if and
3288 only if C is signed-extended to its full width. If MASK is nonzero,
3289 it is an INTEGER_CST that should be AND'ed with the extra bits. */
3292 unextend (c, p, unsignedp, mask)
3298 tree type = TREE_TYPE (c);
3299 int modesize = GET_MODE_BITSIZE (TYPE_MODE (type));
3302 if (p == modesize || unsignedp)
3305 /* We work by getting just the sign bit into the low-order bit, then
3306 into the high-order bit, then sign-extend. We then XOR that value
3308 temp = const_binop (RSHIFT_EXPR, c, size_int (p - 1), 0);
3309 temp = const_binop (BIT_AND_EXPR, temp, size_int (1), 0);
3311 /* We must use a signed type in order to get an arithmetic right shift.
3312 However, we must also avoid introducing accidental overflows, so that
3313 a subsequent call to integer_zerop will work. Hence we must
3314 do the type conversion here. At this point, the constant is either
3315 zero or one, and the conversion to a signed type can never overflow.
3316 We could get an overflow if this conversion is done anywhere else. */
3317 if (TREE_UNSIGNED (type))
3318 temp = convert ((*lang_hooks.types.signed_type) (type), temp);
3320 temp = const_binop (LSHIFT_EXPR, temp, size_int (modesize - 1), 0);
3321 temp = const_binop (RSHIFT_EXPR, temp, size_int (modesize - p - 1), 0);
3323 temp = const_binop (BIT_AND_EXPR, temp, convert (TREE_TYPE (c), mask), 0);
3324 /* If necessary, convert the type back to match the type of C. */
3325 if (TREE_UNSIGNED (type))
3326 temp = convert (type, temp);
3328 return convert (type, const_binop (BIT_XOR_EXPR, c, temp, 0));
3331 /* Find ways of folding logical expressions of LHS and RHS:
3332 Try to merge two comparisons to the same innermost item.
3333 Look for range tests like "ch >= '0' && ch <= '9'".
3334 Look for combinations of simple terms on machines with expensive branches
3335 and evaluate the RHS unconditionally.
3337 For example, if we have p->a == 2 && p->b == 4 and we can make an
3338 object large enough to span both A and B, we can do this with a comparison
3339 against the object ANDed with the a mask.
3341 If we have p->a == q->a && p->b == q->b, we may be able to use bit masking
3342 operations to do this with one comparison.
3344 We check for both normal comparisons and the BIT_AND_EXPRs made this by
3345 function and the one above.
3347 CODE is the logical operation being done. It can be TRUTH_ANDIF_EXPR,
3348 TRUTH_AND_EXPR, TRUTH_ORIF_EXPR, or TRUTH_OR_EXPR.
3350 TRUTH_TYPE is the type of the logical operand and LHS and RHS are its
3353 We return the simplified tree or 0 if no optimization is possible. */
3356 fold_truthop (code, truth_type, lhs, rhs)
3357 enum tree_code code;
3358 tree truth_type, lhs, rhs;
3360 /* If this is the "or" of two comparisons, we can do something if
3361 the comparisons are NE_EXPR. If this is the "and", we can do something
3362 if the comparisons are EQ_EXPR. I.e.,
3363 (a->b == 2 && a->c == 4) can become (a->new == NEW).
3365 WANTED_CODE is this operation code. For single bit fields, we can
3366 convert EQ_EXPR to NE_EXPR so we need not reject the "wrong"
3367 comparison for one-bit fields. */
3369 enum tree_code wanted_code;
3370 enum tree_code lcode, rcode;
3371 tree ll_arg, lr_arg, rl_arg, rr_arg;
3372 tree ll_inner, lr_inner, rl_inner, rr_inner;
3373 HOST_WIDE_INT ll_bitsize, ll_bitpos, lr_bitsize, lr_bitpos;
3374 HOST_WIDE_INT rl_bitsize, rl_bitpos, rr_bitsize, rr_bitpos;
3375 HOST_WIDE_INT xll_bitpos, xlr_bitpos, xrl_bitpos, xrr_bitpos;
3376 HOST_WIDE_INT lnbitsize, lnbitpos, rnbitsize, rnbitpos;
3377 int ll_unsignedp, lr_unsignedp, rl_unsignedp, rr_unsignedp;
3378 enum machine_mode ll_mode, lr_mode, rl_mode, rr_mode;
3379 enum machine_mode lnmode, rnmode;
3380 tree ll_mask, lr_mask, rl_mask, rr_mask;
3381 tree ll_and_mask, lr_and_mask, rl_and_mask, rr_and_mask;
3382 tree l_const, r_const;
3383 tree lntype, rntype, result;
3384 int first_bit, end_bit;
3387 /* Start by getting the comparison codes. Fail if anything is volatile.
3388 If one operand is a BIT_AND_EXPR with the constant one, treat it as if
3389 it were surrounded with a NE_EXPR. */
3391 if (TREE_SIDE_EFFECTS (lhs) || TREE_SIDE_EFFECTS (rhs))
3394 lcode = TREE_CODE (lhs);
3395 rcode = TREE_CODE (rhs);
3397 if (lcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (lhs, 1)))
3398 lcode = NE_EXPR, lhs = build (NE_EXPR, truth_type, lhs, integer_zero_node);
3400 if (rcode == BIT_AND_EXPR && integer_onep (TREE_OPERAND (rhs, 1)))
3401 rcode = NE_EXPR, rhs = build (NE_EXPR, truth_type, rhs, integer_zero_node);
3403 if (TREE_CODE_CLASS (lcode) != '<' || TREE_CODE_CLASS (rcode) != '<')
3406 code = ((code == TRUTH_AND_EXPR || code == TRUTH_ANDIF_EXPR)
3407 ? TRUTH_AND_EXPR : TRUTH_OR_EXPR);
3409 ll_arg = TREE_OPERAND (lhs, 0);
3410 lr_arg = TREE_OPERAND (lhs, 1);
3411 rl_arg = TREE_OPERAND (rhs, 0);
3412 rr_arg = TREE_OPERAND (rhs, 1);
3414 /* If the RHS can be evaluated unconditionally and its operands are
3415 simple, it wins to evaluate the RHS unconditionally on machines
3416 with expensive branches. In this case, this isn't a comparison
3417 that can be merged. Avoid doing this if the RHS is a floating-point
3418 comparison since those can trap. */
3420 if (BRANCH_COST >= 2
3421 && ! FLOAT_TYPE_P (TREE_TYPE (rl_arg))
3422 && simple_operand_p (rl_arg)
3423 && simple_operand_p (rr_arg))
3424 return build (code, truth_type, lhs, rhs);
3426 /* See if the comparisons can be merged. Then get all the parameters for
3429 if ((lcode != EQ_EXPR && lcode != NE_EXPR)
3430 || (rcode != EQ_EXPR && rcode != NE_EXPR))
3434 ll_inner = decode_field_reference (ll_arg,
3435 &ll_bitsize, &ll_bitpos, &ll_mode,
3436 &ll_unsignedp, &volatilep, &ll_mask,
3438 lr_inner = decode_field_reference (lr_arg,
3439 &lr_bitsize, &lr_bitpos, &lr_mode,
3440 &lr_unsignedp, &volatilep, &lr_mask,
3442 rl_inner = decode_field_reference (rl_arg,
3443 &rl_bitsize, &rl_bitpos, &rl_mode,
3444 &rl_unsignedp, &volatilep, &rl_mask,
3446 rr_inner = decode_field_reference (rr_arg,
3447 &rr_bitsize, &rr_bitpos, &rr_mode,
3448 &rr_unsignedp, &volatilep, &rr_mask,
3451 /* It must be true that the inner operation on the lhs of each
3452 comparison must be the same if we are to be able to do anything.
3453 Then see if we have constants. If not, the same must be true for
3455 if (volatilep || ll_inner == 0 || rl_inner == 0
3456 || ! operand_equal_p (ll_inner, rl_inner, 0))
3459 if (TREE_CODE (lr_arg) == INTEGER_CST
3460 && TREE_CODE (rr_arg) == INTEGER_CST)
3461 l_const = lr_arg, r_const = rr_arg;
3462 else if (lr_inner == 0 || rr_inner == 0
3463 || ! operand_equal_p (lr_inner, rr_inner, 0))
3466 l_const = r_const = 0;
3468 /* If either comparison code is not correct for our logical operation,
3469 fail. However, we can convert a one-bit comparison against zero into
3470 the opposite comparison against that bit being set in the field. */
3472 wanted_code = (code == TRUTH_AND_EXPR ? EQ_EXPR : NE_EXPR);
3473 if (lcode != wanted_code)
3475 if (l_const && integer_zerop (l_const) && integer_pow2p (ll_mask))
3477 /* Make the left operand unsigned, since we are only interested
3478 in the value of one bit. Otherwise we are doing the wrong
3487 /* This is analogous to the code for l_const above. */
3488 if (rcode != wanted_code)
3490 if (r_const && integer_zerop (r_const) && integer_pow2p (rl_mask))
3499 /* See if we can find a mode that contains both fields being compared on
3500 the left. If we can't, fail. Otherwise, update all constants and masks
3501 to be relative to a field of that size. */
3502 first_bit = MIN (ll_bitpos, rl_bitpos);
3503 end_bit = MAX (ll_bitpos + ll_bitsize, rl_bitpos + rl_bitsize);
3504 lnmode = get_best_mode (end_bit - first_bit, first_bit,
3505 TYPE_ALIGN (TREE_TYPE (ll_inner)), word_mode,
3507 if (lnmode == VOIDmode)
3510 lnbitsize = GET_MODE_BITSIZE (lnmode);
3511 lnbitpos = first_bit & ~ (lnbitsize - 1);
3512 lntype = (*lang_hooks.types.type_for_size) (lnbitsize, 1);
3513 xll_bitpos = ll_bitpos - lnbitpos, xrl_bitpos = rl_bitpos - lnbitpos;
3515 if (BYTES_BIG_ENDIAN)
3517 xll_bitpos = lnbitsize - xll_bitpos - ll_bitsize;
3518 xrl_bitpos = lnbitsize - xrl_bitpos - rl_bitsize;
3521 ll_mask = const_binop (LSHIFT_EXPR, convert (lntype, ll_mask),
3522 size_int (xll_bitpos), 0);
3523 rl_mask = const_binop (LSHIFT_EXPR, convert (lntype, rl_mask),
3524 size_int (xrl_bitpos), 0);
3528 l_const = convert (lntype, l_const);
3529 l_const = unextend (l_const, ll_bitsize, ll_unsignedp, ll_and_mask);
3530 l_const = const_binop (LSHIFT_EXPR, l_const, size_int (xll_bitpos), 0);
3531 if (! integer_zerop (const_binop (BIT_AND_EXPR, l_const,
3532 fold (build1 (BIT_NOT_EXPR,
3536 warning ("comparison is always %d", wanted_code == NE_EXPR);
3538 return convert (truth_type,
3539 wanted_code == NE_EXPR
3540 ? integer_one_node : integer_zero_node);
3545 r_const = convert (lntype, r_const);
3546 r_const = unextend (r_const, rl_bitsize, rl_unsignedp, rl_and_mask);
3547 r_const = const_binop (LSHIFT_EXPR, r_const, size_int (xrl_bitpos), 0);
3548 if (! integer_zerop (const_binop (BIT_AND_EXPR, r_const,
3549 fold (build1 (BIT_NOT_EXPR,
3553 warning ("comparison is always %d", wanted_code == NE_EXPR);
3555 return convert (truth_type,
3556 wanted_code == NE_EXPR
3557 ? integer_one_node : integer_zero_node);
3561 /* If the right sides are not constant, do the same for it. Also,
3562 disallow this optimization if a size or signedness mismatch occurs
3563 between the left and right sides. */
3566 if (ll_bitsize != lr_bitsize || rl_bitsize != rr_bitsize
3567 || ll_unsignedp != lr_unsignedp || rl_unsignedp != rr_unsignedp
3568 /* Make sure the two fields on the right
3569 correspond to the left without being swapped. */
3570 || ll_bitpos - rl_bitpos != lr_bitpos - rr_bitpos)
3573 first_bit = MIN (lr_bitpos, rr_bitpos);
3574 end_bit = MAX (lr_bitpos + lr_bitsize, rr_bitpos + rr_bitsize);
3575 rnmode = get_best_mode (end_bit - first_bit, first_bit,
3576 TYPE_ALIGN (TREE_TYPE (lr_inner)), word_mode,
3578 if (rnmode == VOIDmode)
3581 rnbitsize = GET_MODE_BITSIZE (rnmode);
3582 rnbitpos = first_bit & ~ (rnbitsize - 1);
3583 rntype = (*lang_hooks.types.type_for_size) (rnbitsize, 1);
3584 xlr_bitpos = lr_bitpos - rnbitpos, xrr_bitpos = rr_bitpos - rnbitpos;
3586 if (BYTES_BIG_ENDIAN)
3588 xlr_bitpos = rnbitsize - xlr_bitpos - lr_bitsize;
3589 xrr_bitpos = rnbitsize - xrr_bitpos - rr_bitsize;
3592 lr_mask = const_binop (LSHIFT_EXPR, convert (rntype, lr_mask),
3593 size_int (xlr_bitpos), 0);
3594 rr_mask = const_binop (LSHIFT_EXPR, convert (rntype, rr_mask),
3595 size_int (xrr_bitpos), 0);
3597 /* Make a mask that corresponds to both fields being compared.
3598 Do this for both items being compared. If the operands are the
3599 same size and the bits being compared are in the same position
3600 then we can do this by masking both and comparing the masked
3602 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3603 lr_mask = const_binop (BIT_IOR_EXPR, lr_mask, rr_mask, 0);
3604 if (lnbitsize == rnbitsize && xll_bitpos == xlr_bitpos)
3606 lhs = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3607 ll_unsignedp || rl_unsignedp);
3608 if (! all_ones_mask_p (ll_mask, lnbitsize))
3609 lhs = build (BIT_AND_EXPR, lntype, lhs, ll_mask);
3611 rhs = make_bit_field_ref (lr_inner, rntype, rnbitsize, rnbitpos,
3612 lr_unsignedp || rr_unsignedp);
3613 if (! all_ones_mask_p (lr_mask, rnbitsize))
3614 rhs = build (BIT_AND_EXPR, rntype, rhs, lr_mask);
3616 return build (wanted_code, truth_type, lhs, rhs);
3619 /* There is still another way we can do something: If both pairs of
3620 fields being compared are adjacent, we may be able to make a wider
3621 field containing them both.
3623 Note that we still must mask the lhs/rhs expressions. Furthermore,
3624 the mask must be shifted to account for the shift done by
3625 make_bit_field_ref. */
3626 if ((ll_bitsize + ll_bitpos == rl_bitpos
3627 && lr_bitsize + lr_bitpos == rr_bitpos)
3628 || (ll_bitpos == rl_bitpos + rl_bitsize
3629 && lr_bitpos == rr_bitpos + rr_bitsize))
3633 lhs = make_bit_field_ref (ll_inner, lntype, ll_bitsize + rl_bitsize,
3634 MIN (ll_bitpos, rl_bitpos), ll_unsignedp);
3635 rhs = make_bit_field_ref (lr_inner, rntype, lr_bitsize + rr_bitsize,
3636 MIN (lr_bitpos, rr_bitpos), lr_unsignedp);
3638 ll_mask = const_binop (RSHIFT_EXPR, ll_mask,
3639 size_int (MIN (xll_bitpos, xrl_bitpos)), 0);
3640 lr_mask = const_binop (RSHIFT_EXPR, lr_mask,
3641 size_int (MIN (xlr_bitpos, xrr_bitpos)), 0);
3643 /* Convert to the smaller type before masking out unwanted bits. */
3645 if (lntype != rntype)
3647 if (lnbitsize > rnbitsize)
3649 lhs = convert (rntype, lhs);
3650 ll_mask = convert (rntype, ll_mask);
3653 else if (lnbitsize < rnbitsize)
3655 rhs = convert (lntype, rhs);
3656 lr_mask = convert (lntype, lr_mask);
3661 if (! all_ones_mask_p (ll_mask, ll_bitsize + rl_bitsize))
3662 lhs = build (BIT_AND_EXPR, type, lhs, ll_mask);
3664 if (! all_ones_mask_p (lr_mask, lr_bitsize + rr_bitsize))
3665 rhs = build (BIT_AND_EXPR, type, rhs, lr_mask);
3667 return build (wanted_code, truth_type, lhs, rhs);
3673 /* Handle the case of comparisons with constants. If there is something in
3674 common between the masks, those bits of the constants must be the same.
3675 If not, the condition is always false. Test for this to avoid generating
3676 incorrect code below. */
3677 result = const_binop (BIT_AND_EXPR, ll_mask, rl_mask, 0);
3678 if (! integer_zerop (result)
3679 && simple_cst_equal (const_binop (BIT_AND_EXPR, result, l_const, 0),
3680 const_binop (BIT_AND_EXPR, result, r_const, 0)) != 1)
3682 if (wanted_code == NE_EXPR)
3684 warning ("`or' of unmatched not-equal tests is always 1");
3685 return convert (truth_type, integer_one_node);
3689 warning ("`and' of mutually exclusive equal-tests is always 0");
3690 return convert (truth_type, integer_zero_node);
3694 /* Construct the expression we will return. First get the component
3695 reference we will make. Unless the mask is all ones the width of
3696 that field, perform the mask operation. Then compare with the
3698 result = make_bit_field_ref (ll_inner, lntype, lnbitsize, lnbitpos,
3699 ll_unsignedp || rl_unsignedp);
3701 ll_mask = const_binop (BIT_IOR_EXPR, ll_mask, rl_mask, 0);
3702 if (! all_ones_mask_p (ll_mask, lnbitsize))
3703 result = build (BIT_AND_EXPR, lntype, result, ll_mask);
3705 return build (wanted_code, truth_type, result,
3706 const_binop (BIT_IOR_EXPR, l_const, r_const, 0));
3709 /* Optimize T, which is a comparison of a MIN_EXPR or MAX_EXPR with a
3713 optimize_minmax_comparison (t)
3716 tree type = TREE_TYPE (t);
3717 tree arg0 = TREE_OPERAND (t, 0);
3718 enum tree_code op_code;
3719 tree comp_const = TREE_OPERAND (t, 1);
3721 int consts_equal, consts_lt;
3724 STRIP_SIGN_NOPS (arg0);
3726 op_code = TREE_CODE (arg0);
3727 minmax_const = TREE_OPERAND (arg0, 1);
3728 consts_equal = tree_int_cst_equal (minmax_const, comp_const);
3729 consts_lt = tree_int_cst_lt (minmax_const, comp_const);
3730 inner = TREE_OPERAND (arg0, 0);
3732 /* If something does not permit us to optimize, return the original tree. */
3733 if ((op_code != MIN_EXPR && op_code != MAX_EXPR)
3734 || TREE_CODE (comp_const) != INTEGER_CST
3735 || TREE_CONSTANT_OVERFLOW (comp_const)
3736 || TREE_CODE (minmax_const) != INTEGER_CST
3737 || TREE_CONSTANT_OVERFLOW (minmax_const))
3740 /* Now handle all the various comparison codes. We only handle EQ_EXPR
3741 and GT_EXPR, doing the rest with recursive calls using logical
3743 switch (TREE_CODE (t))
3745 case NE_EXPR: case LT_EXPR: case LE_EXPR:
3747 invert_truthvalue (optimize_minmax_comparison (invert_truthvalue (t)));
3751 fold (build (TRUTH_ORIF_EXPR, type,
3752 optimize_minmax_comparison
3753 (build (EQ_EXPR, type, arg0, comp_const)),
3754 optimize_minmax_comparison
3755 (build (GT_EXPR, type, arg0, comp_const))));
3758 if (op_code == MAX_EXPR && consts_equal)
3759 /* MAX (X, 0) == 0 -> X <= 0 */
3760 return fold (build (LE_EXPR, type, inner, comp_const));
3762 else if (op_code == MAX_EXPR && consts_lt)
3763 /* MAX (X, 0) == 5 -> X == 5 */
3764 return fold (build (EQ_EXPR, type, inner, comp_const));
3766 else if (op_code == MAX_EXPR)
3767 /* MAX (X, 0) == -1 -> false */
3768 return omit_one_operand (type, integer_zero_node, inner);
3770 else if (consts_equal)
3771 /* MIN (X, 0) == 0 -> X >= 0 */
3772 return fold (build (GE_EXPR, type, inner, comp_const));
3775 /* MIN (X, 0) == 5 -> false */
3776 return omit_one_operand (type, integer_zero_node, inner);
3779 /* MIN (X, 0) == -1 -> X == -1 */
3780 return fold (build (EQ_EXPR, type, inner, comp_const));
3783 if (op_code == MAX_EXPR && (consts_equal || consts_lt))
3784 /* MAX (X, 0) > 0 -> X > 0
3785 MAX (X, 0) > 5 -> X > 5 */
3786 return fold (build (GT_EXPR, type, inner, comp_const));
3788 else if (op_code == MAX_EXPR)
3789 /* MAX (X, 0) > -1 -> true */
3790 return omit_one_operand (type, integer_one_node, inner);
3792 else if (op_code == MIN_EXPR && (consts_equal || consts_lt))
3793 /* MIN (X, 0) > 0 -> false
3794 MIN (X, 0) > 5 -> false */
3795 return omit_one_operand (type, integer_zero_node, inner);
3798 /* MIN (X, 0) > -1 -> X > -1 */
3799 return fold (build (GT_EXPR, type, inner, comp_const));
3806 /* T is an integer expression that is being multiplied, divided, or taken a
3807 modulus (CODE says which and what kind of divide or modulus) by a
3808 constant C. See if we can eliminate that operation by folding it with
3809 other operations already in T. WIDE_TYPE, if non-null, is a type that
3810 should be used for the computation if wider than our type.
3812 For example, if we are dividing (X * 8) + (Y + 16) by 4, we can return
3813 (X * 2) + (Y + 4). We must, however, be assured that either the original
3814 expression would not overflow or that overflow is undefined for the type
3815 in the language in question.
3817 We also canonicalize (X + 7) * 4 into X * 4 + 28 in the hope that either
3818 the machine has a multiply-accumulate insn or that this is part of an
3819 addressing calculation.
3821 If we return a non-null expression, it is an equivalent form of the
3822 original computation, but need not be in the original type. */
3825 extract_muldiv (t, c, code, wide_type)
3828 enum tree_code code;
3831 tree type = TREE_TYPE (t);
3832 enum tree_code tcode = TREE_CODE (t);
3833 tree ctype = (wide_type != 0 && (GET_MODE_SIZE (TYPE_MODE (wide_type))
3834 > GET_MODE_SIZE (TYPE_MODE (type)))
3835 ? wide_type : type);
3837 int same_p = tcode == code;
3838 tree op0 = NULL_TREE, op1 = NULL_TREE;
3840 /* Don't deal with constants of zero here; they confuse the code below. */
3841 if (integer_zerop (c))
3844 if (TREE_CODE_CLASS (tcode) == '1')
3845 op0 = TREE_OPERAND (t, 0);
3847 if (TREE_CODE_CLASS (tcode) == '2')
3848 op0 = TREE_OPERAND (t, 0), op1 = TREE_OPERAND (t, 1);
3850 /* Note that we need not handle conditional operations here since fold
3851 already handles those cases. So just do arithmetic here. */
3855 /* For a constant, we can always simplify if we are a multiply
3856 or (for divide and modulus) if it is a multiple of our constant. */
3857 if (code == MULT_EXPR
3858 || integer_zerop (const_binop (TRUNC_MOD_EXPR, t, c, 0)))
3859 return const_binop (code, convert (ctype, t), convert (ctype, c), 0);
3862 case CONVERT_EXPR: case NON_LVALUE_EXPR: case NOP_EXPR:
3863 /* If op0 is an expression, and is unsigned, and the type is
3864 smaller than ctype, then we cannot widen the expression. */
3865 if ((TREE_CODE_CLASS (TREE_CODE (op0)) == '<'
3866 || TREE_CODE_CLASS (TREE_CODE (op0)) == '1'
3867 || TREE_CODE_CLASS (TREE_CODE (op0)) == '2'
3868 || TREE_CODE_CLASS (TREE_CODE (op0)) == 'e')
3869 && TREE_UNSIGNED (TREE_TYPE (op0))
3870 && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3871 && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
3872 && (GET_MODE_SIZE (TYPE_MODE (ctype))
3873 > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
3876 /* Pass the constant down and see if we can make a simplification. If
3877 we can, replace this expression with the inner simplification for
3878 possible later conversion to our or some other type. */
3879 if (0 != (t1 = extract_muldiv (op0, convert (TREE_TYPE (op0), c), code,
3880 code == MULT_EXPR ? ctype : NULL_TREE)))
3884 case NEGATE_EXPR: case ABS_EXPR:
3885 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
3886 return fold (build1 (tcode, ctype, convert (ctype, t1)));
3889 case MIN_EXPR: case MAX_EXPR:
3890 /* If widening the type changes the signedness, then we can't perform
3891 this optimization as that changes the result. */
3892 if (TREE_UNSIGNED (ctype) != TREE_UNSIGNED (type))
3895 /* MIN (a, b) / 5 -> MIN (a / 5, b / 5) */
3896 if ((t1 = extract_muldiv (op0, c, code, wide_type)) != 0
3897 && (t2 = extract_muldiv (op1, c, code, wide_type)) != 0)
3899 if (tree_int_cst_sgn (c) < 0)
3900 tcode = (tcode == MIN_EXPR ? MAX_EXPR : MIN_EXPR);
3902 return fold (build (tcode, ctype, convert (ctype, t1),
3903 convert (ctype, t2)));
3907 case WITH_RECORD_EXPR:
3908 if ((t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code, wide_type)) != 0)
3909 return build (WITH_RECORD_EXPR, TREE_TYPE (t1), t1,
3910 TREE_OPERAND (t, 1));
3914 /* If this has not been evaluated and the operand has no side effects,
3915 we can see if we can do something inside it and make a new one.
3916 Note that this test is overly conservative since we can do this
3917 if the only reason it had side effects is that it was another
3918 similar SAVE_EXPR, but that isn't worth bothering with. */
3919 if (SAVE_EXPR_RTL (t) == 0 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (t, 0))
3920 && 0 != (t1 = extract_muldiv (TREE_OPERAND (t, 0), c, code,
3923 t1 = save_expr (t1);
3924 if (SAVE_EXPR_PERSISTENT_P (t) && TREE_CODE (t1) == SAVE_EXPR)
3925 SAVE_EXPR_PERSISTENT_P (t1) = 1;
3926 if (is_pending_size (t))
3927 put_pending_size (t1);
3932 case LSHIFT_EXPR: case RSHIFT_EXPR:
3933 /* If the second operand is constant, this is a multiplication
3934 or floor division, by a power of two, so we can treat it that
3935 way unless the multiplier or divisor overflows. */
3936 if (TREE_CODE (op1) == INTEGER_CST
3937 /* const_binop may not detect overflow correctly,
3938 so check for it explicitly here. */
3939 && TYPE_PRECISION (TREE_TYPE (size_one_node)) > TREE_INT_CST_LOW (op1)
3940 && TREE_INT_CST_HIGH (op1) == 0
3941 && 0 != (t1 = convert (ctype,
3942 const_binop (LSHIFT_EXPR, size_one_node,
3944 && ! TREE_OVERFLOW (t1))
3945 return extract_muldiv (build (tcode == LSHIFT_EXPR
3946 ? MULT_EXPR : FLOOR_DIV_EXPR,
3947 ctype, convert (ctype, op0), t1),
3948 c, code, wide_type);
3951 case PLUS_EXPR: case MINUS_EXPR:
3952 /* See if we can eliminate the operation on both sides. If we can, we
3953 can return a new PLUS or MINUS. If we can't, the only remaining
3954 cases where we can do anything are if the second operand is a
3956 t1 = extract_muldiv (op0, c, code, wide_type);
3957 t2 = extract_muldiv (op1, c, code, wide_type);
3958 if (t1 != 0 && t2 != 0
3959 && (code == MULT_EXPR
3960 /* If not multiplication, we can only do this if either operand
3961 is divisible by c. */
3962 || multiple_of_p (ctype, op0, c)
3963 || multiple_of_p (ctype, op1, c)))
3964 return fold (build (tcode, ctype, convert (ctype, t1),
3965 convert (ctype, t2)));
3967 /* If this was a subtraction, negate OP1 and set it to be an addition.
3968 This simplifies the logic below. */
3969 if (tcode == MINUS_EXPR)
3970 tcode = PLUS_EXPR, op1 = negate_expr (op1);
3972 if (TREE_CODE (op1) != INTEGER_CST)
3975 /* If either OP1 or C are negative, this optimization is not safe for
3976 some of the division and remainder types while for others we need
3977 to change the code. */
3978 if (tree_int_cst_sgn (op1) < 0 || tree_int_cst_sgn (c) < 0)
3980 if (code == CEIL_DIV_EXPR)
3981 code = FLOOR_DIV_EXPR;
3982 else if (code == FLOOR_DIV_EXPR)
3983 code = CEIL_DIV_EXPR;
3984 else if (code != MULT_EXPR
3985 && code != CEIL_MOD_EXPR && code != FLOOR_MOD_EXPR)
3989 /* If it's a multiply or a division/modulus operation of a multiple
3990 of our constant, do the operation and verify it doesn't overflow. */
3991 if (code == MULT_EXPR
3992 || integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
3994 op1 = const_binop (code, convert (ctype, op1), convert (ctype, c), 0);
3995 if (op1 == 0 || TREE_OVERFLOW (op1))
4001 /* If we have an unsigned type is not a sizetype, we cannot widen
4002 the operation since it will change the result if the original
4003 computation overflowed. */
4004 if (TREE_UNSIGNED (ctype)
4005 && ! (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))
4009 /* If we were able to eliminate our operation from the first side,
4010 apply our operation to the second side and reform the PLUS. */
4011 if (t1 != 0 && (TREE_CODE (t1) != code || code == MULT_EXPR))
4012 return fold (build (tcode, ctype, convert (ctype, t1), op1));
4014 /* The last case is if we are a multiply. In that case, we can
4015 apply the distributive law to commute the multiply and addition
4016 if the multiplication of the constants doesn't overflow. */
4017 if (code == MULT_EXPR)
4018 return fold (build (tcode, ctype, fold (build (code, ctype,
4019 convert (ctype, op0),
4020 convert (ctype, c))),
4026 /* We have a special case here if we are doing something like
4027 (C * 8) % 4 since we know that's zero. */
4028 if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
4029 || code == FLOOR_MOD_EXPR || code == ROUND_MOD_EXPR)
4030 && TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
4031 && integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4032 return omit_one_operand (type, integer_zero_node, op0);
4034 /* ... fall through ... */
4036 case TRUNC_DIV_EXPR: case CEIL_DIV_EXPR: case FLOOR_DIV_EXPR:
4037 case ROUND_DIV_EXPR: case EXACT_DIV_EXPR:
4038 /* If we can extract our operation from the LHS, do so and return a
4039 new operation. Likewise for the RHS from a MULT_EXPR. Otherwise,
4040 do something only if the second operand is a constant. */
4042 && (t1 = extract_muldiv (op0, c, code, wide_type)) != 0)
4043 return fold (build (tcode, ctype, convert (ctype, t1),
4044 convert (ctype, op1)));
4045 else if (tcode == MULT_EXPR && code == MULT_EXPR
4046 && (t1 = extract_muldiv (op1, c, code, wide_type)) != 0)
4047 return fold (build (tcode, ctype, convert (ctype, op0),
4048 convert (ctype, t1)));
4049 else if (TREE_CODE (op1) != INTEGER_CST)
4052 /* If these are the same operation types, we can associate them
4053 assuming no overflow. */
4055 && 0 != (t1 = const_binop (MULT_EXPR, convert (ctype, op1),
4056 convert (ctype, c), 0))
4057 && ! TREE_OVERFLOW (t1))
4058 return fold (build (tcode, ctype, convert (ctype, op0), t1));
4060 /* If these operations "cancel" each other, we have the main
4061 optimizations of this pass, which occur when either constant is a
4062 multiple of the other, in which case we replace this with either an
4063 operation or CODE or TCODE.
4065 If we have an unsigned type that is not a sizetype, we cannot do
4066 this since it will change the result if the original computation
4068 if ((! TREE_UNSIGNED (ctype)
4069 || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
4070 && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR)
4071 || (tcode == MULT_EXPR
4072 && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR
4073 && code != FLOOR_MOD_EXPR && code != ROUND_MOD_EXPR)))
4075 if (integer_zerop (const_binop (TRUNC_MOD_EXPR, op1, c, 0)))
4076 return fold (build (tcode, ctype, convert (ctype, op0),
4078 const_binop (TRUNC_DIV_EXPR,
4080 else if (integer_zerop (const_binop (TRUNC_MOD_EXPR, c, op1, 0)))
4081 return fold (build (code, ctype, convert (ctype, op0),
4083 const_binop (TRUNC_DIV_EXPR,
4095 /* If T contains a COMPOUND_EXPR which was inserted merely to evaluate
4096 S, a SAVE_EXPR, return the expression actually being evaluated. Note
4097 that we may sometimes modify the tree. */
4100 strip_compound_expr (t, s)
4104 enum tree_code code = TREE_CODE (t);
4106 /* See if this is the COMPOUND_EXPR we want to eliminate. */
4107 if (code == COMPOUND_EXPR && TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR
4108 && TREE_OPERAND (TREE_OPERAND (t, 0), 0) == s)
4109 return TREE_OPERAND (t, 1);
4111 /* See if this is a COND_EXPR or a simple arithmetic operator. We
4112 don't bother handling any other types. */
4113 else if (code == COND_EXPR)
4115 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4116 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4117 TREE_OPERAND (t, 2) = strip_compound_expr (TREE_OPERAND (t, 2), s);
4119 else if (TREE_CODE_CLASS (code) == '1')
4120 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4121 else if (TREE_CODE_CLASS (code) == '<'
4122 || TREE_CODE_CLASS (code) == '2')
4124 TREE_OPERAND (t, 0) = strip_compound_expr (TREE_OPERAND (t, 0), s);
4125 TREE_OPERAND (t, 1) = strip_compound_expr (TREE_OPERAND (t, 1), s);
4131 /* Return a node which has the indicated constant VALUE (either 0 or
4132 1), and is of the indicated TYPE. */
4135 constant_boolean_node (value, type)
4139 if (type == integer_type_node)
4140 return value ? integer_one_node : integer_zero_node;
4141 else if (TREE_CODE (type) == BOOLEAN_TYPE)
4142 return (*lang_hooks.truthvalue_conversion) (value ? integer_one_node :
4146 tree t = build_int_2 (value, 0);
4148 TREE_TYPE (t) = type;
4153 /* Utility function for the following routine, to see how complex a nesting of
4154 COND_EXPRs can be. EXPR is the expression and LIMIT is a count beyond which
4155 we don't care (to avoid spending too much time on complex expressions.). */
4158 count_cond (expr, lim)
4164 if (TREE_CODE (expr) != COND_EXPR)
4169 ctrue = count_cond (TREE_OPERAND (expr, 1), lim - 1);
4170 cfalse = count_cond (TREE_OPERAND (expr, 2), lim - 1 - ctrue);
4171 return MIN (lim, 1 + ctrue + cfalse);
4174 /* Transform `a + (b ? x : y)' into `x ? (a + b) : (a + y)'.
4175 Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
4176 CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
4177 expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
4178 COND is the first argument to CODE; otherwise (as in the example
4179 given here), it is the second argument. TYPE is the type of the
4180 original expression. */
4183 fold_binary_op_with_conditional_arg (code, type, cond, arg, cond_first_p)
4184 enum tree_code code;
4190 tree test, true_value, false_value;
4191 tree lhs = NULL_TREE;
4192 tree rhs = NULL_TREE;
4193 /* In the end, we'll produce a COND_EXPR. Both arms of the
4194 conditional expression will be binary operations. The left-hand
4195 side of the expression to be executed if the condition is true
4196 will be pointed to by TRUE_LHS. Similarly, the right-hand side
4197 of the expression to be executed if the condition is true will be
4198 pointed to by TRUE_RHS. FALSE_LHS and FALSE_RHS are analogous --
4199 but apply to the expression to be executed if the conditional is
4205 /* These are the codes to use for the left-hand side and right-hand
4206 side of the COND_EXPR. Normally, they are the same as CODE. */
4207 enum tree_code lhs_code = code;
4208 enum tree_code rhs_code = code;
4209 /* And these are the types of the expressions. */
4210 tree lhs_type = type;
4211 tree rhs_type = type;
4215 true_rhs = false_rhs = &arg;
4216 true_lhs = &true_value;
4217 false_lhs = &false_value;
4221 true_lhs = false_lhs = &arg;
4222 true_rhs = &true_value;
4223 false_rhs = &false_value;
4226 if (TREE_CODE (cond) == COND_EXPR)
4228 test = TREE_OPERAND (cond, 0);
4229 true_value = TREE_OPERAND (cond, 1);
4230 false_value = TREE_OPERAND (cond, 2);
4231 /* If this operand throws an expression, then it does not make
4232 sense to try to perform a logical or arithmetic operation
4233 involving it. Instead of building `a + throw 3' for example,
4234 we simply build `a, throw 3'. */
4235 if (VOID_TYPE_P (TREE_TYPE (true_value)))
4237 lhs_code = COMPOUND_EXPR;
4239 lhs_type = void_type_node;
4241 if (VOID_TYPE_P (TREE_TYPE (false_value)))
4243 rhs_code = COMPOUND_EXPR;
4245 rhs_type = void_type_node;
4250 tree testtype = TREE_TYPE (cond);
4252 true_value = convert (testtype, integer_one_node);
4253 false_value = convert (testtype, integer_zero_node);
4256 /* If ARG is complex we want to make sure we only evaluate
4257 it once. Though this is only required if it is volatile, it
4258 might be more efficient even if it is not. However, if we
4259 succeed in folding one part to a constant, we do not need
4260 to make this SAVE_EXPR. Since we do this optimization
4261 primarily to see if we do end up with constant and this
4262 SAVE_EXPR interferes with later optimizations, suppressing
4263 it when we can is important.
4265 If we are not in a function, we can't make a SAVE_EXPR, so don't
4266 try to do so. Don't try to see if the result is a constant
4267 if an arm is a COND_EXPR since we get exponential behavior
4270 if (TREE_CODE (arg) != SAVE_EXPR && ! TREE_CONSTANT (arg)
4271 && (*lang_hooks.decls.global_bindings_p) () == 0
4272 && ((TREE_CODE (arg) != VAR_DECL
4273 && TREE_CODE (arg) != PARM_DECL)
4274 || TREE_SIDE_EFFECTS (arg)))
4276 if (TREE_CODE (true_value) != COND_EXPR)
4277 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4279 if (TREE_CODE (false_value) != COND_EXPR)
4280 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4282 if ((lhs == 0 || ! TREE_CONSTANT (lhs))
4283 && (rhs == 0 || !TREE_CONSTANT (rhs)))
4284 arg = save_expr (arg), lhs = rhs = 0;
4288 lhs = fold (build (lhs_code, lhs_type, *true_lhs, *true_rhs));
4290 rhs = fold (build (rhs_code, rhs_type, *false_lhs, *false_rhs));
4292 test = fold (build (COND_EXPR, type, test, lhs, rhs));
4294 if (TREE_CODE (arg) == SAVE_EXPR)
4295 return build (COMPOUND_EXPR, type,
4296 convert (void_type_node, arg),
4297 strip_compound_expr (test, arg));
4299 return convert (type, test);
4303 /* Subroutine of fold() that checks for the addition of +/- 0.0.
4305 If !NEGATE, return true if ADDEND is +/-0.0 and, for all X of type
4306 TYPE, X + ADDEND is the same as X. If NEGATE, return true if X -
4307 ADDEND is the same as X.
4309 X + 0 and X - 0 both give X when X is NaN, infinite, or non-zero
4310 and finite. The problematic cases are when X is zero, and its mode
4311 has signed zeros. In the case of rounding towards -infinity,
4312 X - 0 is not the same as X because 0 - 0 is -0. In other rounding
4313 modes, X + 0 is not the same as X because -0 + 0 is 0. */
4316 fold_real_zero_addition_p (type, addend, negate)
4320 if (!real_zerop (addend))
4323 /* Allow the fold if zeros aren't signed, or their sign isn't important. */
4324 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
4327 /* Treat x + -0 as x - 0 and x - -0 as x + 0. */
4328 if (TREE_CODE (addend) == REAL_CST
4329 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (addend)))
4332 /* The mode has signed zeros, and we have to honor their sign.
4333 In this situation, there is only one case we can return true for.
4334 X - 0 is the same as X unless rounding towards -infinity is
4336 return negate && !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type));
4340 /* Perform constant folding and related simplification of EXPR.
4341 The related simplifications include x*1 => x, x*0 => 0, etc.,
4342 and application of the associative law.
4343 NOP_EXPR conversions may be removed freely (as long as we
4344 are careful not to change the C type of the overall expression)
4345 We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
4346 but we can constant-fold them if they have constant operands. */
4353 tree t1 = NULL_TREE;
4355 tree type = TREE_TYPE (expr);
4356 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
4357 enum tree_code code = TREE_CODE (t);
4358 int kind = TREE_CODE_CLASS (code);
4360 /* WINS will be nonzero when the switch is done
4361 if all operands are constant. */
4364 /* Don't try to process an RTL_EXPR since its operands aren't trees.
4365 Likewise for a SAVE_EXPR that's already been evaluated. */
4366 if (code == RTL_EXPR || (code == SAVE_EXPR && SAVE_EXPR_RTL (t) != 0))
4369 /* Return right away if a constant. */
4373 #ifdef MAX_INTEGER_COMPUTATION_MODE
4374 check_max_integer_computation_mode (expr);
4377 if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
4381 /* Special case for conversion ops that can have fixed point args. */
4382 arg0 = TREE_OPERAND (t, 0);
4384 /* Don't use STRIP_NOPS, because signedness of argument type matters. */
4386 STRIP_SIGN_NOPS (arg0);
4388 if (arg0 != 0 && TREE_CODE (arg0) == COMPLEX_CST)
4389 subop = TREE_REALPART (arg0);
4393 if (subop != 0 && TREE_CODE (subop) != INTEGER_CST
4394 && TREE_CODE (subop) != REAL_CST
4396 /* Note that TREE_CONSTANT isn't enough:
4397 static var addresses are constant but we can't
4398 do arithmetic on them. */
4401 else if (IS_EXPR_CODE_CLASS (kind) || kind == 'r')
4403 int len = first_rtl_op (code);
4405 for (i = 0; i < len; i++)
4407 tree op = TREE_OPERAND (t, i);
4411 continue; /* Valid for CALL_EXPR, at least. */
4413 if (kind == '<' || code == RSHIFT_EXPR)
4415 /* Signedness matters here. Perhaps we can refine this
4417 STRIP_SIGN_NOPS (op);
4420 /* Strip any conversions that don't change the mode. */
4423 if (TREE_CODE (op) == COMPLEX_CST)
4424 subop = TREE_REALPART (op);
4428 if (TREE_CODE (subop) != INTEGER_CST
4429 && TREE_CODE (subop) != REAL_CST)
4430 /* Note that TREE_CONSTANT isn't enough:
4431 static var addresses are constant but we can't
4432 do arithmetic on them. */
4442 /* If this is a commutative operation, and ARG0 is a constant, move it
4443 to ARG1 to reduce the number of tests below. */
4444 if ((code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
4445 || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
4446 || code == BIT_AND_EXPR)
4447 && (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST))
4449 tem = arg0; arg0 = arg1; arg1 = tem;
4451 tem = TREE_OPERAND (t, 0); TREE_OPERAND (t, 0) = TREE_OPERAND (t, 1);
4452 TREE_OPERAND (t, 1) = tem;
4455 /* Now WINS is set as described above,
4456 ARG0 is the first operand of EXPR,
4457 and ARG1 is the second operand (if it has more than one operand).
4459 First check for cases where an arithmetic operation is applied to a
4460 compound, conditional, or comparison operation. Push the arithmetic
4461 operation inside the compound or conditional to see if any folding
4462 can then be done. Convert comparison to conditional for this purpose.
4463 The also optimizes non-constant cases that used to be done in
4466 Before we do that, see if this is a BIT_AND_EXPR or a BIT_IOR_EXPR,
4467 one of the operands is a comparison and the other is a comparison, a
4468 BIT_AND_EXPR with the constant 1, or a truth value. In that case, the
4469 code below would make the expression more complex. Change it to a
4470 TRUTH_{AND,OR}_EXPR. Likewise, convert a similar NE_EXPR to
4471 TRUTH_XOR_EXPR and an EQ_EXPR to the inversion of a TRUTH_XOR_EXPR. */
4473 if ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR
4474 || code == EQ_EXPR || code == NE_EXPR)
4475 && ((truth_value_p (TREE_CODE (arg0))
4476 && (truth_value_p (TREE_CODE (arg1))
4477 || (TREE_CODE (arg1) == BIT_AND_EXPR
4478 && integer_onep (TREE_OPERAND (arg1, 1)))))
4479 || (truth_value_p (TREE_CODE (arg1))
4480 && (truth_value_p (TREE_CODE (arg0))
4481 || (TREE_CODE (arg0) == BIT_AND_EXPR
4482 && integer_onep (TREE_OPERAND (arg0, 1)))))))
4484 t = fold (build (code == BIT_AND_EXPR ? TRUTH_AND_EXPR
4485 : code == BIT_IOR_EXPR ? TRUTH_OR_EXPR
4489 if (code == EQ_EXPR)
4490 t = invert_truthvalue (t);
4495 if (TREE_CODE_CLASS (code) == '1')
4497 if (TREE_CODE (arg0) == COMPOUND_EXPR)
4498 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4499 fold (build1 (code, type, TREE_OPERAND (arg0, 1))));
4500 else if (TREE_CODE (arg0) == COND_EXPR)
4502 t = fold (build (COND_EXPR, type, TREE_OPERAND (arg0, 0),
4503 fold (build1 (code, type, TREE_OPERAND (arg0, 1))),
4504 fold (build1 (code, type, TREE_OPERAND (arg0, 2)))));
4506 /* If this was a conversion, and all we did was to move into
4507 inside the COND_EXPR, bring it back out. But leave it if
4508 it is a conversion from integer to integer and the
4509 result precision is no wider than a word since such a
4510 conversion is cheap and may be optimized away by combine,
4511 while it couldn't if it were outside the COND_EXPR. Then return
4512 so we don't get into an infinite recursion loop taking the
4513 conversion out and then back in. */
4515 if ((code == NOP_EXPR || code == CONVERT_EXPR
4516 || code == NON_LVALUE_EXPR)
4517 && TREE_CODE (t) == COND_EXPR
4518 && TREE_CODE (TREE_OPERAND (t, 1)) == code
4519 && TREE_CODE (TREE_OPERAND (t, 2)) == code
4520 && (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))
4521 == TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 2), 0)))
4522 && ! (INTEGRAL_TYPE_P (TREE_TYPE (t))
4524 (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0))))
4525 && TYPE_PRECISION (TREE_TYPE (t)) <= BITS_PER_WORD))
4526 t = build1 (code, type,
4528 TREE_TYPE (TREE_OPERAND
4529 (TREE_OPERAND (t, 1), 0)),
4530 TREE_OPERAND (t, 0),
4531 TREE_OPERAND (TREE_OPERAND (t, 1), 0),
4532 TREE_OPERAND (TREE_OPERAND (t, 2), 0)));
4535 else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<')
4536 return fold (build (COND_EXPR, type, arg0,
4537 fold (build1 (code, type, integer_one_node)),
4538 fold (build1 (code, type, integer_zero_node))));
4540 else if (TREE_CODE_CLASS (code) == '2'
4541 || TREE_CODE_CLASS (code) == '<')
4543 if (TREE_CODE (arg1) == COMPOUND_EXPR)
4544 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4545 fold (build (code, type,
4546 arg0, TREE_OPERAND (arg1, 1))));
4547 else if ((TREE_CODE (arg1) == COND_EXPR
4548 || (TREE_CODE_CLASS (TREE_CODE (arg1)) == '<'
4549 && TREE_CODE_CLASS (code) != '<'))
4550 && (TREE_CODE (arg0) != COND_EXPR
4551 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4552 && (! TREE_SIDE_EFFECTS (arg0)
4553 || ((*lang_hooks.decls.global_bindings_p) () == 0
4554 && ! contains_placeholder_p (arg0))))
4556 fold_binary_op_with_conditional_arg (code, type, arg1, arg0,
4557 /*cond_first_p=*/0);
4558 else if (TREE_CODE (arg0) == COMPOUND_EXPR)
4559 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4560 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4561 else if ((TREE_CODE (arg0) == COND_EXPR
4562 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
4563 && TREE_CODE_CLASS (code) != '<'))
4564 && (TREE_CODE (arg1) != COND_EXPR
4565 || count_cond (arg0, 25) + count_cond (arg1, 25) <= 25)
4566 && (! TREE_SIDE_EFFECTS (arg1)
4567 || ((*lang_hooks.decls.global_bindings_p) () == 0
4568 && ! contains_placeholder_p (arg1))))
4570 fold_binary_op_with_conditional_arg (code, type, arg0, arg1,
4571 /*cond_first_p=*/1);
4573 else if (TREE_CODE_CLASS (code) == '<'
4574 && TREE_CODE (arg0) == COMPOUND_EXPR)
4575 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg0, 0),
4576 fold (build (code, type, TREE_OPERAND (arg0, 1), arg1)));
4577 else if (TREE_CODE_CLASS (code) == '<'
4578 && TREE_CODE (arg1) == COMPOUND_EXPR)
4579 return build (COMPOUND_EXPR, type, TREE_OPERAND (arg1, 0),
4580 fold (build (code, type, arg0, TREE_OPERAND (arg1, 1))));
4593 return fold (DECL_INITIAL (t));
4598 case FIX_TRUNC_EXPR:
4599 /* Other kinds of FIX are not handled properly by fold_convert. */
4601 if (TREE_TYPE (TREE_OPERAND (t, 0)) == TREE_TYPE (t))
4602 return TREE_OPERAND (t, 0);
4604 /* Handle cases of two conversions in a row. */
4605 if (TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
4606 || TREE_CODE (TREE_OPERAND (t, 0)) == CONVERT_EXPR)
4608 tree inside_type = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4609 tree inter_type = TREE_TYPE (TREE_OPERAND (t, 0));
4610 tree final_type = TREE_TYPE (t);
4611 int inside_int = INTEGRAL_TYPE_P (inside_type);
4612 int inside_ptr = POINTER_TYPE_P (inside_type);
4613 int inside_float = FLOAT_TYPE_P (inside_type);
4614 unsigned int inside_prec = TYPE_PRECISION (inside_type);
4615 int inside_unsignedp = TREE_UNSIGNED (inside_type);
4616 int inter_int = INTEGRAL_TYPE_P (inter_type);
4617 int inter_ptr = POINTER_TYPE_P (inter_type);
4618 int inter_float = FLOAT_TYPE_P (inter_type);
4619 unsigned int inter_prec = TYPE_PRECISION (inter_type);
4620 int inter_unsignedp = TREE_UNSIGNED (inter_type);
4621 int final_int = INTEGRAL_TYPE_P (final_type);
4622 int final_ptr = POINTER_TYPE_P (final_type);
4623 int final_float = FLOAT_TYPE_P (final_type);
4624 unsigned int final_prec = TYPE_PRECISION (final_type);
4625 int final_unsignedp = TREE_UNSIGNED (final_type);
4627 /* In addition to the cases of two conversions in a row
4628 handled below, if we are converting something to its own
4629 type via an object of identical or wider precision, neither
4630 conversion is needed. */
4631 if (TYPE_MAIN_VARIANT (inside_type) == TYPE_MAIN_VARIANT (final_type)
4632 && ((inter_int && final_int) || (inter_float && final_float))
4633 && inter_prec >= final_prec)
4634 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4636 /* Likewise, if the intermediate and final types are either both
4637 float or both integer, we don't need the middle conversion if
4638 it is wider than the final type and doesn't change the signedness
4639 (for integers). Avoid this if the final type is a pointer
4640 since then we sometimes need the inner conversion. Likewise if
4641 the outer has a precision not equal to the size of its mode. */
4642 if ((((inter_int || inter_ptr) && (inside_int || inside_ptr))
4643 || (inter_float && inside_float))
4644 && inter_prec >= inside_prec
4645 && (inter_float || inter_unsignedp == inside_unsignedp)
4646 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4647 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4649 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4651 /* If we have a sign-extension of a zero-extended value, we can
4652 replace that by a single zero-extension. */
4653 if (inside_int && inter_int && final_int
4654 && inside_prec < inter_prec && inter_prec < final_prec
4655 && inside_unsignedp && !inter_unsignedp)
4656 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4658 /* Two conversions in a row are not needed unless:
4659 - some conversion is floating-point (overstrict for now), or
4660 - the intermediate type is narrower than both initial and
4662 - the intermediate type and innermost type differ in signedness,
4663 and the outermost type is wider than the intermediate, or
4664 - the initial type is a pointer type and the precisions of the
4665 intermediate and final types differ, or
4666 - the final type is a pointer type and the precisions of the
4667 initial and intermediate types differ. */
4668 if (! inside_float && ! inter_float && ! final_float
4669 && (inter_prec > inside_prec || inter_prec > final_prec)
4670 && ! (inside_int && inter_int
4671 && inter_unsignedp != inside_unsignedp
4672 && inter_prec < final_prec)
4673 && ((inter_unsignedp && inter_prec > inside_prec)
4674 == (final_unsignedp && final_prec > inter_prec))
4675 && ! (inside_ptr && inter_prec != final_prec)
4676 && ! (final_ptr && inside_prec != inter_prec)
4677 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (final_type))
4678 && TYPE_MODE (final_type) == TYPE_MODE (inter_type))
4680 return convert (final_type, TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4683 if (TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
4684 && TREE_CONSTANT (TREE_OPERAND (TREE_OPERAND (t, 0), 1))
4685 /* Detect assigning a bitfield. */
4686 && !(TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == COMPONENT_REF
4687 && DECL_BIT_FIELD (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 1))))
4689 /* Don't leave an assignment inside a conversion
4690 unless assigning a bitfield. */
4691 tree prev = TREE_OPERAND (t, 0);
4692 TREE_OPERAND (t, 0) = TREE_OPERAND (prev, 1);
4693 /* First do the assignment, then return converted constant. */
4694 t = build (COMPOUND_EXPR, TREE_TYPE (t), prev, fold (t));
4700 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4703 return fold_convert (t, arg0);
4705 case VIEW_CONVERT_EXPR:
4706 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4707 return build1 (VIEW_CONVERT_EXPR, type,
4708 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4712 if (TREE_CODE (arg0) == CONSTRUCTOR)
4714 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4721 TREE_CONSTANT (t) = wins;
4727 if (TREE_CODE (arg0) == INTEGER_CST)
4729 unsigned HOST_WIDE_INT low;
4731 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4732 TREE_INT_CST_HIGH (arg0),
4734 t = build_int_2 (low, high);
4735 TREE_TYPE (t) = type;
4737 = (TREE_OVERFLOW (arg0)
4738 | force_fit_type (t, overflow && !TREE_UNSIGNED (type)));
4739 TREE_CONSTANT_OVERFLOW (t)
4740 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4742 else if (TREE_CODE (arg0) == REAL_CST)
4743 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4745 else if (TREE_CODE (arg0) == NEGATE_EXPR)
4746 return TREE_OPERAND (arg0, 0);
4748 /* Convert - (a - b) to (b - a) for non-floating-point. */
4749 else if (TREE_CODE (arg0) == MINUS_EXPR
4750 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
4751 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4752 TREE_OPERAND (arg0, 0));
4759 if (TREE_CODE (arg0) == INTEGER_CST)
4761 /* If the value is unsigned, then the absolute value is
4762 the same as the ordinary value. */
4763 if (TREE_UNSIGNED (type))
4765 /* Similarly, if the value is non-negative. */
4766 else if (INT_CST_LT (integer_minus_one_node, arg0))
4768 /* If the value is negative, then the absolute value is
4772 unsigned HOST_WIDE_INT low;
4774 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4775 TREE_INT_CST_HIGH (arg0),
4777 t = build_int_2 (low, high);
4778 TREE_TYPE (t) = type;
4780 = (TREE_OVERFLOW (arg0)
4781 | force_fit_type (t, overflow));
4782 TREE_CONSTANT_OVERFLOW (t)
4783 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4786 else if (TREE_CODE (arg0) == REAL_CST)
4788 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4789 t = build_real (type,
4790 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4793 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4794 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4798 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4799 return convert (type, arg0);
4800 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4801 return build (COMPLEX_EXPR, type,
4802 TREE_OPERAND (arg0, 0),
4803 negate_expr (TREE_OPERAND (arg0, 1)));
4804 else if (TREE_CODE (arg0) == COMPLEX_CST)
4805 return build_complex (type, TREE_REALPART (arg0),
4806 negate_expr (TREE_IMAGPART (arg0)));
4807 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4808 return fold (build (TREE_CODE (arg0), type,
4809 fold (build1 (CONJ_EXPR, type,
4810 TREE_OPERAND (arg0, 0))),
4811 fold (build1 (CONJ_EXPR,
4812 type, TREE_OPERAND (arg0, 1)))));
4813 else if (TREE_CODE (arg0) == CONJ_EXPR)
4814 return TREE_OPERAND (arg0, 0);
4820 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4821 ~ TREE_INT_CST_HIGH (arg0));
4822 TREE_TYPE (t) = type;
4823 force_fit_type (t, 0);
4824 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4825 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4827 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4828 return TREE_OPERAND (arg0, 0);
4832 /* A + (-B) -> A - B */
4833 if (TREE_CODE (arg1) == NEGATE_EXPR)
4834 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4835 /* (-A) + B -> B - A */
4836 if (TREE_CODE (arg0) == NEGATE_EXPR)
4837 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
4838 else if (! FLOAT_TYPE_P (type))
4840 if (integer_zerop (arg1))
4841 return non_lvalue (convert (type, arg0));
4843 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4844 with a constant, and the two constants have no bits in common,
4845 we should treat this as a BIT_IOR_EXPR since this may produce more
4847 if (TREE_CODE (arg0) == BIT_AND_EXPR
4848 && TREE_CODE (arg1) == BIT_AND_EXPR
4849 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4850 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4851 && integer_zerop (const_binop (BIT_AND_EXPR,
4852 TREE_OPERAND (arg0, 1),
4853 TREE_OPERAND (arg1, 1), 0)))
4855 code = BIT_IOR_EXPR;
4859 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4860 (plus (plus (mult) (mult)) (foo)) so that we can
4861 take advantage of the factoring cases below. */
4862 if ((TREE_CODE (arg0) == PLUS_EXPR
4863 && TREE_CODE (arg1) == MULT_EXPR)
4864 || (TREE_CODE (arg1) == PLUS_EXPR
4865 && TREE_CODE (arg0) == MULT_EXPR))
4867 tree parg0, parg1, parg, marg;
4869 if (TREE_CODE (arg0) == PLUS_EXPR)
4870 parg = arg0, marg = arg1;
4872 parg = arg1, marg = arg0;
4873 parg0 = TREE_OPERAND (parg, 0);
4874 parg1 = TREE_OPERAND (parg, 1);
4878 if (TREE_CODE (parg0) == MULT_EXPR
4879 && TREE_CODE (parg1) != MULT_EXPR)
4880 return fold (build (PLUS_EXPR, type,
4881 fold (build (PLUS_EXPR, type, parg0, marg)),
4883 if (TREE_CODE (parg0) != MULT_EXPR
4884 && TREE_CODE (parg1) == MULT_EXPR)
4885 return fold (build (PLUS_EXPR, type,
4886 fold (build (PLUS_EXPR, type, parg1, marg)),
4890 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4892 tree arg00, arg01, arg10, arg11;
4893 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
4895 /* (A * C) + (B * C) -> (A+B) * C.
4896 We are most concerned about the case where C is a constant,
4897 but other combinations show up during loop reduction. Since
4898 it is not difficult, try all four possibilities. */
4900 arg00 = TREE_OPERAND (arg0, 0);
4901 arg01 = TREE_OPERAND (arg0, 1);
4902 arg10 = TREE_OPERAND (arg1, 0);
4903 arg11 = TREE_OPERAND (arg1, 1);
4906 if (operand_equal_p (arg01, arg11, 0))
4907 same = arg01, alt0 = arg00, alt1 = arg10;
4908 else if (operand_equal_p (arg00, arg10, 0))
4909 same = arg00, alt0 = arg01, alt1 = arg11;
4910 else if (operand_equal_p (arg00, arg11, 0))
4911 same = arg00, alt0 = arg01, alt1 = arg10;
4912 else if (operand_equal_p (arg01, arg10, 0))
4913 same = arg01, alt0 = arg00, alt1 = arg11;
4915 /* No identical multiplicands; see if we can find a common
4916 power-of-two factor in non-power-of-two multiplies. This
4917 can help in multi-dimensional array access. */
4918 else if (TREE_CODE (arg01) == INTEGER_CST
4919 && TREE_CODE (arg11) == INTEGER_CST
4920 && TREE_INT_CST_HIGH (arg01) == 0
4921 && TREE_INT_CST_HIGH (arg11) == 0)
4923 HOST_WIDE_INT int01, int11, tmp;
4924 int01 = TREE_INT_CST_LOW (arg01);
4925 int11 = TREE_INT_CST_LOW (arg11);
4927 /* Move min of absolute values to int11. */
4928 if ((int01 >= 0 ? int01 : -int01)
4929 < (int11 >= 0 ? int11 : -int11))
4931 tmp = int01, int01 = int11, int11 = tmp;
4932 alt0 = arg00, arg00 = arg10, arg10 = alt0;
4933 alt0 = arg01, arg01 = arg11, arg11 = alt0;
4936 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
4938 alt0 = fold (build (MULT_EXPR, type, arg00,
4939 build_int_2 (int01 / int11, 0)));
4946 return fold (build (MULT_EXPR, type,
4947 fold (build (PLUS_EXPR, type, alt0, alt1)),
4952 /* See if ARG1 is zero and X + ARG1 reduces to X. */
4953 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
4954 return non_lvalue (convert (type, arg0));
4956 /* Likewise if the operands are reversed. */
4957 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
4958 return non_lvalue (convert (type, arg1));
4961 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
4962 is a rotate of A by C1 bits. */
4963 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
4964 is a rotate of A by B bits. */
4966 enum tree_code code0, code1;
4967 code0 = TREE_CODE (arg0);
4968 code1 = TREE_CODE (arg1);
4969 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
4970 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
4971 && operand_equal_p (TREE_OPERAND (arg0, 0),
4972 TREE_OPERAND (arg1, 0), 0)
4973 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
4975 tree tree01, tree11;
4976 enum tree_code code01, code11;
4978 tree01 = TREE_OPERAND (arg0, 1);
4979 tree11 = TREE_OPERAND (arg1, 1);
4980 STRIP_NOPS (tree01);
4981 STRIP_NOPS (tree11);
4982 code01 = TREE_CODE (tree01);
4983 code11 = TREE_CODE (tree11);
4984 if (code01 == INTEGER_CST
4985 && code11 == INTEGER_CST
4986 && TREE_INT_CST_HIGH (tree01) == 0
4987 && TREE_INT_CST_HIGH (tree11) == 0
4988 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
4989 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
4990 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
4991 code0 == LSHIFT_EXPR ? tree01 : tree11);
4992 else if (code11 == MINUS_EXPR)
4994 tree tree110, tree111;
4995 tree110 = TREE_OPERAND (tree11, 0);
4996 tree111 = TREE_OPERAND (tree11, 1);
4997 STRIP_NOPS (tree110);
4998 STRIP_NOPS (tree111);
4999 if (TREE_CODE (tree110) == INTEGER_CST
5000 && 0 == compare_tree_int (tree110,
5002 (TREE_TYPE (TREE_OPERAND
5004 && operand_equal_p (tree01, tree111, 0))
5005 return build ((code0 == LSHIFT_EXPR
5008 type, TREE_OPERAND (arg0, 0), tree01);
5010 else if (code01 == MINUS_EXPR)
5012 tree tree010, tree011;
5013 tree010 = TREE_OPERAND (tree01, 0);
5014 tree011 = TREE_OPERAND (tree01, 1);
5015 STRIP_NOPS (tree010);
5016 STRIP_NOPS (tree011);
5017 if (TREE_CODE (tree010) == INTEGER_CST
5018 && 0 == compare_tree_int (tree010,
5020 (TREE_TYPE (TREE_OPERAND
5022 && operand_equal_p (tree11, tree011, 0))
5023 return build ((code0 != LSHIFT_EXPR
5026 type, TREE_OPERAND (arg0, 0), tree11);
5032 /* In most languages, can't associate operations on floats through
5033 parentheses. Rather than remember where the parentheses were, we
5034 don't associate floats at all. It shouldn't matter much. However,
5035 associating multiplications is only very slightly inaccurate, so do
5036 that if -funsafe-math-optimizations is specified. */
5039 && (! FLOAT_TYPE_P (type)
5040 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5042 tree var0, con0, lit0, var1, con1, lit1;
5044 /* Split both trees into variables, constants, and literals. Then
5045 associate each group together, the constants with literals,
5046 then the result with variables. This increases the chances of
5047 literals being recombined later and of generating relocatable
5048 expressions for the sum of a constant and literal. */
5049 var0 = split_tree (arg0, code, &con0, &lit0, 0);
5050 var1 = split_tree (arg1, code, &con1, &lit1, code == MINUS_EXPR);
5052 /* Only do something if we found more than two objects. Otherwise,
5053 nothing has changed and we risk infinite recursion. */
5054 if (2 < ((var0 != 0) + (var1 != 0) + (con0 != 0) + (con1 != 0)
5055 + (lit0 != 0) + (lit1 != 0)))
5057 var0 = associate_trees (var0, var1, code, type);
5058 con0 = associate_trees (con0, con1, code, type);
5059 lit0 = associate_trees (lit0, lit1, code, type);
5060 con0 = associate_trees (con0, lit0, code, type);
5061 return convert (type, associate_trees (var0, con0, code, type));
5067 t1 = const_binop (code, arg0, arg1, 0);
5068 if (t1 != NULL_TREE)
5070 /* The return value should always have
5071 the same type as the original expression. */
5072 if (TREE_TYPE (t1) != TREE_TYPE (t))
5073 t1 = convert (TREE_TYPE (t), t1);
5080 /* A - (-B) -> A + B */
5081 if (TREE_CODE (arg1) == NEGATE_EXPR)
5082 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5083 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5084 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5086 fold (build (MINUS_EXPR, type,
5087 build_real (TREE_TYPE (arg1),
5088 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5089 TREE_OPERAND (arg0, 0)));
5091 if (! FLOAT_TYPE_P (type))
5093 if (! wins && integer_zerop (arg0))
5094 return negate_expr (convert (type, arg1));
5095 if (integer_zerop (arg1))
5096 return non_lvalue (convert (type, arg0));
5098 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5099 about the case where C is a constant, just try one of the
5100 four possibilities. */
5102 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5103 && operand_equal_p (TREE_OPERAND (arg0, 1),
5104 TREE_OPERAND (arg1, 1), 0))
5105 return fold (build (MULT_EXPR, type,
5106 fold (build (MINUS_EXPR, type,
5107 TREE_OPERAND (arg0, 0),
5108 TREE_OPERAND (arg1, 0))),
5109 TREE_OPERAND (arg0, 1)));
5112 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5113 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5114 return non_lvalue (convert (type, arg0));
5116 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5117 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5118 (-ARG1 + ARG0) reduces to -ARG1. */
5119 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5120 return negate_expr (convert (type, arg1));
5122 /* Fold &x - &x. This can happen from &x.foo - &x.
5123 This is unsafe for certain floats even in non-IEEE formats.
5124 In IEEE, it is unsafe because it does wrong for NaNs.
5125 Also note that operand_equal_p is always false if an operand
5128 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5129 && operand_equal_p (arg0, arg1, 0))
5130 return convert (type, integer_zero_node);
5135 /* (-A) * (-B) -> A * B */
5136 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5137 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5138 TREE_OPERAND (arg1, 0)));
5140 if (! FLOAT_TYPE_P (type))
5142 if (integer_zerop (arg1))
5143 return omit_one_operand (type, arg1, arg0);
5144 if (integer_onep (arg1))
5145 return non_lvalue (convert (type, arg0));
5147 /* (a * (1 << b)) is (a << b) */
5148 if (TREE_CODE (arg1) == LSHIFT_EXPR
5149 && integer_onep (TREE_OPERAND (arg1, 0)))
5150 return fold (build (LSHIFT_EXPR, type, arg0,
5151 TREE_OPERAND (arg1, 1)));
5152 if (TREE_CODE (arg0) == LSHIFT_EXPR
5153 && integer_onep (TREE_OPERAND (arg0, 0)))
5154 return fold (build (LSHIFT_EXPR, type, arg1,
5155 TREE_OPERAND (arg0, 1)));
5157 if (TREE_CODE (arg1) == INTEGER_CST
5158 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5160 return convert (type, tem);
5165 /* Maybe fold x * 0 to 0. The expressions aren't the same
5166 when x is NaN, since x * 0 is also NaN. Nor are they the
5167 same in modes with signed zeros, since multiplying a
5168 negative value by 0 gives -0, not +0. */
5169 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5170 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5171 && real_zerop (arg1))
5172 return omit_one_operand (type, arg1, arg0);
5173 /* In IEEE floating point, x*1 is not equivalent to x for snans.
5174 However, ANSI says we can drop signals,
5175 so we can do this anyway. */
5176 if (real_onep (arg1))
5177 return non_lvalue (convert (type, arg0));
5179 if (! wins && real_twop (arg1)
5180 && (*lang_hooks.decls.global_bindings_p) () == 0
5181 && ! contains_placeholder_p (arg0))
5183 tree arg = save_expr (arg0);
5184 return build (PLUS_EXPR, type, arg, arg);
5191 if (integer_all_onesp (arg1))
5192 return omit_one_operand (type, arg1, arg0);
5193 if (integer_zerop (arg1))
5194 return non_lvalue (convert (type, arg0));
5195 t1 = distribute_bit_expr (code, type, arg0, arg1);
5196 if (t1 != NULL_TREE)
5199 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5201 This results in more efficient code for machines without a NAND
5202 instruction. Combine will canonicalize to the first form
5203 which will allow use of NAND instructions provided by the
5204 backend if they exist. */
5205 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5206 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5208 return fold (build1 (BIT_NOT_EXPR, type,
5209 build (BIT_AND_EXPR, type,
5210 TREE_OPERAND (arg0, 0),
5211 TREE_OPERAND (arg1, 0))));
5214 /* See if this can be simplified into a rotate first. If that
5215 is unsuccessful continue in the association code. */
5219 if (integer_zerop (arg1))
5220 return non_lvalue (convert (type, arg0));
5221 if (integer_all_onesp (arg1))
5222 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5224 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5225 with a constant, and the two constants have no bits in common,
5226 we should treat this as a BIT_IOR_EXPR since this may produce more
5228 if (TREE_CODE (arg0) == BIT_AND_EXPR
5229 && TREE_CODE (arg1) == BIT_AND_EXPR
5230 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5231 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5232 && integer_zerop (const_binop (BIT_AND_EXPR,
5233 TREE_OPERAND (arg0, 1),
5234 TREE_OPERAND (arg1, 1), 0)))
5236 code = BIT_IOR_EXPR;
5240 /* See if this can be simplified into a rotate first. If that
5241 is unsuccessful continue in the association code. */
5246 if (integer_all_onesp (arg1))
5247 return non_lvalue (convert (type, arg0));
5248 if (integer_zerop (arg1))
5249 return omit_one_operand (type, arg1, arg0);
5250 t1 = distribute_bit_expr (code, type, arg0, arg1);
5251 if (t1 != NULL_TREE)
5253 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5254 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5255 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5258 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5260 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5261 && (~TREE_INT_CST_LOW (arg0)
5262 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5263 return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5265 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5266 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5269 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5271 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5272 && (~TREE_INT_CST_LOW (arg1)
5273 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5274 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5277 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5279 This results in more efficient code for machines without a NOR
5280 instruction. Combine will canonicalize to the first form
5281 which will allow use of NOR instructions provided by the
5282 backend if they exist. */
5283 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5284 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5286 return fold (build1 (BIT_NOT_EXPR, type,
5287 build (BIT_IOR_EXPR, type,
5288 TREE_OPERAND (arg0, 0),
5289 TREE_OPERAND (arg1, 0))));
5294 case BIT_ANDTC_EXPR:
5295 if (integer_all_onesp (arg0))
5296 return non_lvalue (convert (type, arg1));
5297 if (integer_zerop (arg0))
5298 return omit_one_operand (type, arg0, arg1);
5299 if (TREE_CODE (arg1) == INTEGER_CST)
5301 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5302 code = BIT_AND_EXPR;
5308 /* Don't touch a floating-point divide by zero unless the mode
5309 of the constant can represent infinity. */
5310 if (TREE_CODE (arg1) == REAL_CST
5311 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5312 && real_zerop (arg1))
5315 /* (-A) / (-B) -> A / B */
5316 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5317 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5318 TREE_OPERAND (arg1, 0)));
5320 /* In IEEE floating point, x/1 is not equivalent to x for snans.
5321 However, ANSI says we can drop signals, so we can do this anyway. */
5322 if (real_onep (arg1))
5323 return non_lvalue (convert (type, arg0));
5325 /* If ARG1 is a constant, we can convert this to a multiply by the
5326 reciprocal. This does not have the same rounding properties,
5327 so only do this if -funsafe-math-optimizations. We can actually
5328 always safely do it if ARG1 is a power of two, but it's hard to
5329 tell if it is or not in a portable manner. */
5330 if (TREE_CODE (arg1) == REAL_CST)
5332 if (flag_unsafe_math_optimizations
5333 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5335 return fold (build (MULT_EXPR, type, arg0, tem));
5336 /* Find the reciprocal if optimizing and the result is exact. */
5340 r = TREE_REAL_CST (arg1);
5341 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5343 tem = build_real (type, r);
5344 return fold (build (MULT_EXPR, type, arg0, tem));
5348 /* Convert A/B/C to A/(B*C). */
5349 if (flag_unsafe_math_optimizations
5350 && TREE_CODE (arg0) == RDIV_EXPR)
5352 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5353 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5356 /* Convert A/(B/C) to (A/B)*C. */
5357 if (flag_unsafe_math_optimizations
5358 && TREE_CODE (arg1) == RDIV_EXPR)
5360 return fold (build (MULT_EXPR, type,
5361 build (RDIV_EXPR, type, arg0,
5362 TREE_OPERAND (arg1, 0)),
5363 TREE_OPERAND (arg1, 1)));
5367 case TRUNC_DIV_EXPR:
5368 case ROUND_DIV_EXPR:
5369 case FLOOR_DIV_EXPR:
5371 case EXACT_DIV_EXPR:
5372 if (integer_onep (arg1))
5373 return non_lvalue (convert (type, arg0));
5374 if (integer_zerop (arg1))
5377 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5378 operation, EXACT_DIV_EXPR.
5380 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5381 At one time others generated faster code, it's not clear if they do
5382 after the last round to changes to the DIV code in expmed.c. */
5383 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5384 && multiple_of_p (type, arg0, arg1))
5385 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5387 if (TREE_CODE (arg1) == INTEGER_CST
5388 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5390 return convert (type, tem);
5395 case FLOOR_MOD_EXPR:
5396 case ROUND_MOD_EXPR:
5397 case TRUNC_MOD_EXPR:
5398 if (integer_onep (arg1))
5399 return omit_one_operand (type, integer_zero_node, arg0);
5400 if (integer_zerop (arg1))
5403 if (TREE_CODE (arg1) == INTEGER_CST
5404 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5406 return convert (type, tem);
5414 if (integer_zerop (arg1))
5415 return non_lvalue (convert (type, arg0));
5416 /* Since negative shift count is not well-defined,
5417 don't try to compute it in the compiler. */
5418 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5420 /* Rewrite an LROTATE_EXPR by a constant into an
5421 RROTATE_EXPR by a new constant. */
5422 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5424 TREE_SET_CODE (t, RROTATE_EXPR);
5425 code = RROTATE_EXPR;
5426 TREE_OPERAND (t, 1) = arg1
5429 convert (TREE_TYPE (arg1),
5430 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5432 if (tree_int_cst_sgn (arg1) < 0)
5436 /* If we have a rotate of a bit operation with the rotate count and
5437 the second operand of the bit operation both constant,
5438 permute the two operations. */
5439 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5440 && (TREE_CODE (arg0) == BIT_AND_EXPR
5441 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5442 || TREE_CODE (arg0) == BIT_IOR_EXPR
5443 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5444 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5445 return fold (build (TREE_CODE (arg0), type,
5446 fold (build (code, type,
5447 TREE_OPERAND (arg0, 0), arg1)),
5448 fold (build (code, type,
5449 TREE_OPERAND (arg0, 1), arg1))));
5451 /* Two consecutive rotates adding up to the width of the mode can
5453 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5454 && TREE_CODE (arg0) == RROTATE_EXPR
5455 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5456 && TREE_INT_CST_HIGH (arg1) == 0
5457 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5458 && ((TREE_INT_CST_LOW (arg1)
5459 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5460 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5461 return TREE_OPERAND (arg0, 0);
5466 if (operand_equal_p (arg0, arg1, 0))
5467 return omit_one_operand (type, arg0, arg1);
5468 if (INTEGRAL_TYPE_P (type)
5469 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5470 return omit_one_operand (type, arg1, arg0);
5474 if (operand_equal_p (arg0, arg1, 0))
5475 return omit_one_operand (type, arg0, arg1);
5476 if (INTEGRAL_TYPE_P (type)
5477 && TYPE_MAX_VALUE (type)
5478 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5479 return omit_one_operand (type, arg1, arg0);
5482 case TRUTH_NOT_EXPR:
5483 /* Note that the operand of this must be an int
5484 and its values must be 0 or 1.
5485 ("true" is a fixed value perhaps depending on the language,
5486 but we don't handle values other than 1 correctly yet.) */
5487 tem = invert_truthvalue (arg0);
5488 /* Avoid infinite recursion. */
5489 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5491 return convert (type, tem);
5493 case TRUTH_ANDIF_EXPR:
5494 /* Note that the operands of this must be ints
5495 and their values must be 0 or 1.
5496 ("true" is a fixed value perhaps depending on the language.) */
5497 /* If first arg is constant zero, return it. */
5498 if (integer_zerop (arg0))
5499 return convert (type, arg0);
5500 case TRUTH_AND_EXPR:
5501 /* If either arg is constant true, drop it. */
5502 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5503 return non_lvalue (convert (type, arg1));
5504 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5505 /* Preserve sequence points. */
5506 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5507 return non_lvalue (convert (type, arg0));
5508 /* If second arg is constant zero, result is zero, but first arg
5509 must be evaluated. */
5510 if (integer_zerop (arg1))
5511 return omit_one_operand (type, arg1, arg0);
5512 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5513 case will be handled here. */
5514 if (integer_zerop (arg0))
5515 return omit_one_operand (type, arg0, arg1);
5518 /* We only do these simplifications if we are optimizing. */
5522 /* Check for things like (A || B) && (A || C). We can convert this
5523 to A || (B && C). Note that either operator can be any of the four
5524 truth and/or operations and the transformation will still be
5525 valid. Also note that we only care about order for the
5526 ANDIF and ORIF operators. If B contains side effects, this
5527 might change the truth-value of A. */
5528 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5529 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5530 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5531 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5532 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5533 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5535 tree a00 = TREE_OPERAND (arg0, 0);
5536 tree a01 = TREE_OPERAND (arg0, 1);
5537 tree a10 = TREE_OPERAND (arg1, 0);
5538 tree a11 = TREE_OPERAND (arg1, 1);
5539 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5540 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5541 && (code == TRUTH_AND_EXPR
5542 || code == TRUTH_OR_EXPR));
5544 if (operand_equal_p (a00, a10, 0))
5545 return fold (build (TREE_CODE (arg0), type, a00,
5546 fold (build (code, type, a01, a11))));
5547 else if (commutative && operand_equal_p (a00, a11, 0))
5548 return fold (build (TREE_CODE (arg0), type, a00,
5549 fold (build (code, type, a01, a10))));
5550 else if (commutative && operand_equal_p (a01, a10, 0))
5551 return fold (build (TREE_CODE (arg0), type, a01,
5552 fold (build (code, type, a00, a11))));
5554 /* This case if tricky because we must either have commutative
5555 operators or else A10 must not have side-effects. */
5557 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5558 && operand_equal_p (a01, a11, 0))
5559 return fold (build (TREE_CODE (arg0), type,
5560 fold (build (code, type, a00, a10)),
5564 /* See if we can build a range comparison. */
5565 if (0 != (tem = fold_range_test (t)))
5568 /* Check for the possibility of merging component references. If our
5569 lhs is another similar operation, try to merge its rhs with our
5570 rhs. Then try to merge our lhs and rhs. */
5571 if (TREE_CODE (arg0) == code
5572 && 0 != (tem = fold_truthop (code, type,
5573 TREE_OPERAND (arg0, 1), arg1)))
5574 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5576 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5581 case TRUTH_ORIF_EXPR:
5582 /* Note that the operands of this must be ints
5583 and their values must be 0 or true.
5584 ("true" is a fixed value perhaps depending on the language.) */
5585 /* If first arg is constant true, return it. */
5586 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5587 return convert (type, arg0);
5589 /* If either arg is constant zero, drop it. */
5590 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5591 return non_lvalue (convert (type, arg1));
5592 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5593 /* Preserve sequence points. */
5594 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5595 return non_lvalue (convert (type, arg0));
5596 /* If second arg is constant true, result is true, but we must
5597 evaluate first arg. */
5598 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5599 return omit_one_operand (type, arg1, arg0);
5600 /* Likewise for first arg, but note this only occurs here for
5602 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5603 return omit_one_operand (type, arg0, arg1);
5606 case TRUTH_XOR_EXPR:
5607 /* If either arg is constant zero, drop it. */
5608 if (integer_zerop (arg0))
5609 return non_lvalue (convert (type, arg1));
5610 if (integer_zerop (arg1))
5611 return non_lvalue (convert (type, arg0));
5612 /* If either arg is constant true, this is a logical inversion. */
5613 if (integer_onep (arg0))
5614 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5615 if (integer_onep (arg1))
5616 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5625 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5627 /* (-a) CMP (-b) -> b CMP a */
5628 if (TREE_CODE (arg0) == NEGATE_EXPR
5629 && TREE_CODE (arg1) == NEGATE_EXPR)
5630 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5631 TREE_OPERAND (arg0, 0)));
5632 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5633 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5636 (swap_tree_comparison (code), type,
5637 TREE_OPERAND (arg0, 0),
5638 build_real (TREE_TYPE (arg1),
5639 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5640 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5641 /* a CMP (-0) -> a CMP 0 */
5642 if (TREE_CODE (arg1) == REAL_CST
5643 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5644 return fold (build (code, type, arg0,
5645 build_real (TREE_TYPE (arg1), dconst0)));
5648 /* If one arg is a constant integer, put it last. */
5649 if (TREE_CODE (arg0) == INTEGER_CST
5650 && TREE_CODE (arg1) != INTEGER_CST)
5652 TREE_OPERAND (t, 0) = arg1;
5653 TREE_OPERAND (t, 1) = arg0;
5654 arg0 = TREE_OPERAND (t, 0);
5655 arg1 = TREE_OPERAND (t, 1);
5656 code = swap_tree_comparison (code);
5657 TREE_SET_CODE (t, code);
5660 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5661 First, see if one arg is constant; find the constant arg
5662 and the other one. */
5664 tree constop = 0, varop = NULL_TREE;
5665 int constopnum = -1;
5667 if (TREE_CONSTANT (arg1))
5668 constopnum = 1, constop = arg1, varop = arg0;
5669 if (TREE_CONSTANT (arg0))
5670 constopnum = 0, constop = arg0, varop = arg1;
5672 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5674 /* This optimization is invalid for ordered comparisons
5675 if CONST+INCR overflows or if foo+incr might overflow.
5676 This optimization is invalid for floating point due to rounding.
5677 For pointer types we assume overflow doesn't happen. */
5678 if (POINTER_TYPE_P (TREE_TYPE (varop))
5679 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5680 && (code == EQ_EXPR || code == NE_EXPR)))
5683 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5684 constop, TREE_OPERAND (varop, 1)));
5686 /* Do not overwrite the current varop to be a preincrement,
5687 create a new node so that we won't confuse our caller who
5688 might create trees and throw them away, reusing the
5689 arguments that they passed to build. This shows up in
5690 the THEN or ELSE parts of ?: being postincrements. */
5691 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
5692 TREE_OPERAND (varop, 0),
5693 TREE_OPERAND (varop, 1));
5695 /* If VAROP is a reference to a bitfield, we must mask
5696 the constant by the width of the field. */
5697 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5698 && DECL_BIT_FIELD(TREE_OPERAND
5699 (TREE_OPERAND (varop, 0), 1)))
5702 = TREE_INT_CST_LOW (DECL_SIZE
5704 (TREE_OPERAND (varop, 0), 1)));
5705 tree mask, unsigned_type;
5706 unsigned int precision;
5707 tree folded_compare;
5709 /* First check whether the comparison would come out
5710 always the same. If we don't do that we would
5711 change the meaning with the masking. */
5712 if (constopnum == 0)
5713 folded_compare = fold (build (code, type, constop,
5714 TREE_OPERAND (varop, 0)));
5716 folded_compare = fold (build (code, type,
5717 TREE_OPERAND (varop, 0),
5719 if (integer_zerop (folded_compare)
5720 || integer_onep (folded_compare))
5721 return omit_one_operand (type, folded_compare, varop);
5723 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5724 precision = TYPE_PRECISION (unsigned_type);
5725 mask = build_int_2 (~0, ~0);
5726 TREE_TYPE (mask) = unsigned_type;
5727 force_fit_type (mask, 0);
5728 mask = const_binop (RSHIFT_EXPR, mask,
5729 size_int (precision - size), 0);
5730 newconst = fold (build (BIT_AND_EXPR,
5731 TREE_TYPE (varop), newconst,
5732 convert (TREE_TYPE (varop),
5736 t = build (code, type,
5737 (constopnum == 0) ? newconst : varop,
5738 (constopnum == 1) ? newconst : varop);
5742 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5744 if (POINTER_TYPE_P (TREE_TYPE (varop))
5745 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5746 && (code == EQ_EXPR || code == NE_EXPR)))
5749 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5750 constop, TREE_OPERAND (varop, 1)));
5752 /* Do not overwrite the current varop to be a predecrement,
5753 create a new node so that we won't confuse our caller who
5754 might create trees and throw them away, reusing the
5755 arguments that they passed to build. This shows up in
5756 the THEN or ELSE parts of ?: being postdecrements. */
5757 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
5758 TREE_OPERAND (varop, 0),
5759 TREE_OPERAND (varop, 1));
5761 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5762 && DECL_BIT_FIELD(TREE_OPERAND
5763 (TREE_OPERAND (varop, 0), 1)))
5766 = TREE_INT_CST_LOW (DECL_SIZE
5768 (TREE_OPERAND (varop, 0), 1)));
5769 tree mask, unsigned_type;
5770 unsigned int precision;
5771 tree folded_compare;
5773 if (constopnum == 0)
5774 folded_compare = fold (build (code, type, constop,
5775 TREE_OPERAND (varop, 0)));
5777 folded_compare = fold (build (code, type,
5778 TREE_OPERAND (varop, 0),
5780 if (integer_zerop (folded_compare)
5781 || integer_onep (folded_compare))
5782 return omit_one_operand (type, folded_compare, varop);
5784 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5785 precision = TYPE_PRECISION (unsigned_type);
5786 mask = build_int_2 (~0, ~0);
5787 TREE_TYPE (mask) = TREE_TYPE (varop);
5788 force_fit_type (mask, 0);
5789 mask = const_binop (RSHIFT_EXPR, mask,
5790 size_int (precision - size), 0);
5791 newconst = fold (build (BIT_AND_EXPR,
5792 TREE_TYPE (varop), newconst,
5793 convert (TREE_TYPE (varop),
5797 t = build (code, type,
5798 (constopnum == 0) ? newconst : varop,
5799 (constopnum == 1) ? newconst : varop);
5805 /* Change X >= CST to X > (CST - 1) if CST is positive. */
5806 if (TREE_CODE (arg1) == INTEGER_CST
5807 && TREE_CODE (arg0) != INTEGER_CST
5808 && tree_int_cst_sgn (arg1) > 0)
5810 switch (TREE_CODE (t))
5814 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5815 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5820 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5821 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5829 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
5830 a MINUS_EXPR of a constant, we can convert it into a comparison with
5831 a revised constant as long as no overflow occurs. */
5832 if ((code == EQ_EXPR || code == NE_EXPR)
5833 && TREE_CODE (arg1) == INTEGER_CST
5834 && (TREE_CODE (arg0) == PLUS_EXPR
5835 || TREE_CODE (arg0) == MINUS_EXPR)
5836 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5837 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
5838 ? MINUS_EXPR : PLUS_EXPR,
5839 arg1, TREE_OPERAND (arg0, 1), 0))
5840 && ! TREE_CONSTANT_OVERFLOW (tem))
5841 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5843 /* Similarly for a NEGATE_EXPR. */
5844 else if ((code == EQ_EXPR || code == NE_EXPR)
5845 && TREE_CODE (arg0) == NEGATE_EXPR
5846 && TREE_CODE (arg1) == INTEGER_CST
5847 && 0 != (tem = negate_expr (arg1))
5848 && TREE_CODE (tem) == INTEGER_CST
5849 && ! TREE_CONSTANT_OVERFLOW (tem))
5850 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5852 /* If we have X - Y == 0, we can convert that to X == Y and similarly
5853 for !=. Don't do this for ordered comparisons due to overflow. */
5854 else if ((code == NE_EXPR || code == EQ_EXPR)
5855 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
5856 return fold (build (code, type,
5857 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
5859 /* If we are widening one operand of an integer comparison,
5860 see if the other operand is similarly being widened. Perhaps we
5861 can do the comparison in the narrower type. */
5862 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
5863 && TREE_CODE (arg0) == NOP_EXPR
5864 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
5865 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
5866 && (TREE_TYPE (t1) == TREE_TYPE (tem)
5867 || (TREE_CODE (t1) == INTEGER_CST
5868 && int_fits_type_p (t1, TREE_TYPE (tem)))))
5869 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
5871 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
5872 constant, we can simplify it. */
5873 else if (TREE_CODE (arg1) == INTEGER_CST
5874 && (TREE_CODE (arg0) == MIN_EXPR
5875 || TREE_CODE (arg0) == MAX_EXPR)
5876 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5877 return optimize_minmax_comparison (t);
5879 /* If we are comparing an ABS_EXPR with a constant, we can
5880 convert all the cases into explicit comparisons, but they may
5881 well not be faster than doing the ABS and one comparison.
5882 But ABS (X) <= C is a range comparison, which becomes a subtraction
5883 and a comparison, and is probably faster. */
5884 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5885 && TREE_CODE (arg0) == ABS_EXPR
5886 && ! TREE_SIDE_EFFECTS (arg0)
5887 && (0 != (tem = negate_expr (arg1)))
5888 && TREE_CODE (tem) == INTEGER_CST
5889 && ! TREE_CONSTANT_OVERFLOW (tem))
5890 return fold (build (TRUTH_ANDIF_EXPR, type,
5891 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
5892 build (LE_EXPR, type,
5893 TREE_OPERAND (arg0, 0), arg1)));
5895 /* If this is an EQ or NE comparison with zero and ARG0 is
5896 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
5897 two operations, but the latter can be done in one less insn
5898 on machines that have only two-operand insns or on which a
5899 constant cannot be the first operand. */
5900 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5901 && TREE_CODE (arg0) == BIT_AND_EXPR)
5903 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5904 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5906 fold (build (code, type,
5907 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5909 TREE_TYPE (TREE_OPERAND (arg0, 0)),
5910 TREE_OPERAND (arg0, 1),
5911 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5912 convert (TREE_TYPE (arg0),
5915 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5916 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5918 fold (build (code, type,
5919 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5921 TREE_TYPE (TREE_OPERAND (arg0, 1)),
5922 TREE_OPERAND (arg0, 0),
5923 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5924 convert (TREE_TYPE (arg0),
5929 /* If this is an NE or EQ comparison of zero against the result of a
5930 signed MOD operation whose second operand is a power of 2, make
5931 the MOD operation unsigned since it is simpler and equivalent. */
5932 if ((code == NE_EXPR || code == EQ_EXPR)
5933 && integer_zerop (arg1)
5934 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5935 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5936 || TREE_CODE (arg0) == CEIL_MOD_EXPR
5937 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5938 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5939 && integer_pow2p (TREE_OPERAND (arg0, 1)))
5941 tree newtype = (*lang_hooks.types.unsigned_type) (TREE_TYPE (arg0));
5942 tree newmod = build (TREE_CODE (arg0), newtype,
5943 convert (newtype, TREE_OPERAND (arg0, 0)),
5944 convert (newtype, TREE_OPERAND (arg0, 1)));
5946 return build (code, type, newmod, convert (newtype, arg1));
5949 /* If this is an NE comparison of zero with an AND of one, remove the
5950 comparison since the AND will give the correct value. */
5951 if (code == NE_EXPR && integer_zerop (arg1)
5952 && TREE_CODE (arg0) == BIT_AND_EXPR
5953 && integer_onep (TREE_OPERAND (arg0, 1)))
5954 return convert (type, arg0);
5956 /* If we have (A & C) == C where C is a power of 2, convert this into
5957 (A & C) != 0. Similarly for NE_EXPR. */
5958 if ((code == EQ_EXPR || code == NE_EXPR)
5959 && TREE_CODE (arg0) == BIT_AND_EXPR
5960 && integer_pow2p (TREE_OPERAND (arg0, 1))
5961 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
5962 return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
5963 arg0, integer_zero_node);
5965 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
5966 and similarly for >= into !=. */
5967 if ((code == LT_EXPR || code == GE_EXPR)
5968 && TREE_UNSIGNED (TREE_TYPE (arg0))
5969 && TREE_CODE (arg1) == LSHIFT_EXPR
5970 && integer_onep (TREE_OPERAND (arg1, 0)))
5971 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5972 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5973 TREE_OPERAND (arg1, 1)),
5974 convert (TREE_TYPE (arg0), integer_zero_node));
5976 else if ((code == LT_EXPR || code == GE_EXPR)
5977 && TREE_UNSIGNED (TREE_TYPE (arg0))
5978 && (TREE_CODE (arg1) == NOP_EXPR
5979 || TREE_CODE (arg1) == CONVERT_EXPR)
5980 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
5981 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
5983 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
5984 convert (TREE_TYPE (arg0),
5985 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
5986 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
5987 convert (TREE_TYPE (arg0), integer_zero_node));
5989 /* Simplify comparison of something with itself. (For IEEE
5990 floating-point, we can only do some of these simplifications.) */
5991 if (operand_equal_p (arg0, arg1, 0))
5998 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
5999 return constant_boolean_node (1, type);
6001 TREE_SET_CODE (t, code);
6005 /* For NE, we can only do this simplification if integer. */
6006 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6008 /* ... fall through ... */
6011 return constant_boolean_node (0, type);
6017 /* An unsigned comparison against 0 can be simplified. */
6018 if (integer_zerop (arg1)
6019 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6020 || POINTER_TYPE_P (TREE_TYPE (arg1)))
6021 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6023 switch (TREE_CODE (t))
6027 TREE_SET_CODE (t, NE_EXPR);
6031 TREE_SET_CODE (t, EQ_EXPR);
6034 return omit_one_operand (type,
6035 convert (type, integer_one_node),
6038 return omit_one_operand (type,
6039 convert (type, integer_zero_node),
6046 /* Comparisons with the highest or lowest possible integer of
6047 the specified size will have known values and an unsigned
6048 <= 0x7fffffff can be simplified. */
6050 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
6052 if (TREE_CODE (arg1) == INTEGER_CST
6053 && ! TREE_CONSTANT_OVERFLOW (arg1)
6054 && width <= HOST_BITS_PER_WIDE_INT
6055 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6056 || POINTER_TYPE_P (TREE_TYPE (arg1))))
6058 if (TREE_INT_CST_HIGH (arg1) == 0
6059 && (TREE_INT_CST_LOW (arg1)
6060 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6061 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6062 switch (TREE_CODE (t))
6065 return omit_one_operand (type,
6066 convert (type, integer_zero_node),
6069 TREE_SET_CODE (t, EQ_EXPR);
6073 return omit_one_operand (type,
6074 convert (type, integer_one_node),
6077 TREE_SET_CODE (t, NE_EXPR);
6084 else if (TREE_INT_CST_HIGH (arg1) == -1
6085 && (TREE_INT_CST_LOW (arg1)
6086 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)))
6087 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6088 switch (TREE_CODE (t))
6091 return omit_one_operand (type,
6092 convert (type, integer_zero_node),
6095 TREE_SET_CODE (t, EQ_EXPR);
6099 return omit_one_operand (type,
6100 convert (type, integer_one_node),
6103 TREE_SET_CODE (t, NE_EXPR);
6110 else if (TREE_INT_CST_HIGH (arg1) == 0
6111 && (TREE_INT_CST_LOW (arg1)
6112 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6113 && TREE_UNSIGNED (TREE_TYPE (arg1))
6114 /* signed_type does not work on pointer types. */
6115 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6117 if (TREE_CODE (t) == LE_EXPR || TREE_CODE (t) == GT_EXPR)
6120 st0 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg0));
6121 st1 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg1));
6123 (build (TREE_CODE (t) == LE_EXPR ? GE_EXPR: LT_EXPR,
6124 type, convert (st0, arg0),
6125 convert (st1, integer_zero_node)));
6128 else if (TREE_INT_CST_HIGH (arg1) == 0
6129 && (TREE_INT_CST_LOW (arg1)
6130 == ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1)
6131 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6132 switch (TREE_CODE (t))
6135 return omit_one_operand (type,
6136 convert (type, integer_zero_node),
6139 TREE_SET_CODE (t, EQ_EXPR);
6143 return omit_one_operand (type,
6144 convert (type, integer_one_node),
6147 TREE_SET_CODE (t, NE_EXPR);
6156 /* If we are comparing an expression that just has comparisons
6157 of two integer values, arithmetic expressions of those comparisons,
6158 and constants, we can simplify it. There are only three cases
6159 to check: the two values can either be equal, the first can be
6160 greater, or the second can be greater. Fold the expression for
6161 those three values. Since each value must be 0 or 1, we have
6162 eight possibilities, each of which corresponds to the constant 0
6163 or 1 or one of the six possible comparisons.
6165 This handles common cases like (a > b) == 0 but also handles
6166 expressions like ((x > y) - (y > x)) > 0, which supposedly
6167 occur in macroized code. */
6169 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6171 tree cval1 = 0, cval2 = 0;
6174 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6175 /* Don't handle degenerate cases here; they should already
6176 have been handled anyway. */
6177 && cval1 != 0 && cval2 != 0
6178 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6179 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6180 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6181 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6182 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6183 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6184 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6186 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6187 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6189 /* We can't just pass T to eval_subst in case cval1 or cval2
6190 was the same as ARG1. */
6193 = fold (build (code, type,
6194 eval_subst (arg0, cval1, maxval, cval2, minval),
6197 = fold (build (code, type,
6198 eval_subst (arg0, cval1, maxval, cval2, maxval),
6201 = fold (build (code, type,
6202 eval_subst (arg0, cval1, minval, cval2, maxval),
6205 /* All three of these results should be 0 or 1. Confirm they
6206 are. Then use those values to select the proper code
6209 if ((integer_zerop (high_result)
6210 || integer_onep (high_result))
6211 && (integer_zerop (equal_result)
6212 || integer_onep (equal_result))
6213 && (integer_zerop (low_result)
6214 || integer_onep (low_result)))
6216 /* Make a 3-bit mask with the high-order bit being the
6217 value for `>', the next for '=', and the low for '<'. */
6218 switch ((integer_onep (high_result) * 4)
6219 + (integer_onep (equal_result) * 2)
6220 + integer_onep (low_result))
6224 return omit_one_operand (type, integer_zero_node, arg0);
6245 return omit_one_operand (type, integer_one_node, arg0);
6248 t = build (code, type, cval1, cval2);
6250 return save_expr (t);
6257 /* If this is a comparison of a field, we may be able to simplify it. */
6258 if ((TREE_CODE (arg0) == COMPONENT_REF
6259 || TREE_CODE (arg0) == BIT_FIELD_REF)
6260 && (code == EQ_EXPR || code == NE_EXPR)
6261 /* Handle the constant case even without -O
6262 to make sure the warnings are given. */
6263 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6265 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6269 /* If this is a comparison of complex values and either or both sides
6270 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6271 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6272 This may prevent needless evaluations. */
6273 if ((code == EQ_EXPR || code == NE_EXPR)
6274 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6275 && (TREE_CODE (arg0) == COMPLEX_EXPR
6276 || TREE_CODE (arg1) == COMPLEX_EXPR
6277 || TREE_CODE (arg0) == COMPLEX_CST
6278 || TREE_CODE (arg1) == COMPLEX_CST))
6280 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6281 tree real0, imag0, real1, imag1;
6283 arg0 = save_expr (arg0);
6284 arg1 = save_expr (arg1);
6285 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6286 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6287 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6288 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6290 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6293 fold (build (code, type, real0, real1)),
6294 fold (build (code, type, imag0, imag1))));
6297 /* Optimize comparisons of strlen vs zero to a compare of the
6298 first character of the string vs zero. To wit,
6299 strlen(ptr) == 0 => *ptr == 0
6300 strlen(ptr) != 0 => *ptr != 0
6301 Other cases should reduce to one of these two (or a constant)
6302 due to the return value of strlen being unsigned. */
6303 if ((code == EQ_EXPR || code == NE_EXPR)
6304 && integer_zerop (arg1)
6305 && TREE_CODE (arg0) == CALL_EXPR
6306 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6308 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6311 if (TREE_CODE (fndecl) == FUNCTION_DECL
6312 && DECL_BUILT_IN (fndecl)
6313 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6314 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6315 && (arglist = TREE_OPERAND (arg0, 1))
6316 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6317 && ! TREE_CHAIN (arglist))
6318 return fold (build (code, type,
6319 build1 (INDIRECT_REF, char_type_node,
6320 TREE_VALUE(arglist)),
6321 integer_zero_node));
6324 /* From here on, the only cases we handle are when the result is
6325 known to be a constant.
6327 To compute GT, swap the arguments and do LT.
6328 To compute GE, do LT and invert the result.
6329 To compute LE, swap the arguments, do LT and invert the result.
6330 To compute NE, do EQ and invert the result.
6332 Therefore, the code below must handle only EQ and LT. */
6334 if (code == LE_EXPR || code == GT_EXPR)
6336 tem = arg0, arg0 = arg1, arg1 = tem;
6337 code = swap_tree_comparison (code);
6340 /* Note that it is safe to invert for real values here because we
6341 will check below in the one case that it matters. */
6345 if (code == NE_EXPR || code == GE_EXPR)
6348 code = invert_tree_comparison (code);
6351 /* Compute a result for LT or EQ if args permit;
6352 otherwise return T. */
6353 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6355 if (code == EQ_EXPR)
6356 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6358 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6359 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6360 : INT_CST_LT (arg0, arg1)),
6364 #if 0 /* This is no longer useful, but breaks some real code. */
6365 /* Assume a nonexplicit constant cannot equal an explicit one,
6366 since such code would be undefined anyway.
6367 Exception: on sysvr4, using #pragma weak,
6368 a label can come out as 0. */
6369 else if (TREE_CODE (arg1) == INTEGER_CST
6370 && !integer_zerop (arg1)
6371 && TREE_CONSTANT (arg0)
6372 && TREE_CODE (arg0) == ADDR_EXPR
6374 t1 = build_int_2 (0, 0);
6376 /* Two real constants can be compared explicitly. */
6377 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6379 /* If either operand is a NaN, the result is false with two
6380 exceptions: First, an NE_EXPR is true on NaNs, but that case
6381 is already handled correctly since we will be inverting the
6382 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6383 or a GE_EXPR into a LT_EXPR, we must return true so that it
6384 will be inverted into false. */
6386 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6387 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6388 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6390 else if (code == EQ_EXPR)
6391 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6392 TREE_REAL_CST (arg1)),
6395 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6396 TREE_REAL_CST (arg1)),
6400 if (t1 == NULL_TREE)
6404 TREE_INT_CST_LOW (t1) ^= 1;
6406 TREE_TYPE (t1) = type;
6407 if (TREE_CODE (type) == BOOLEAN_TYPE)
6408 return (*lang_hooks.truthvalue_conversion) (t1);
6412 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6413 so all simple results must be passed through pedantic_non_lvalue. */
6414 if (TREE_CODE (arg0) == INTEGER_CST)
6415 return pedantic_non_lvalue
6416 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6417 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6418 return pedantic_omit_one_operand (type, arg1, arg0);
6420 /* If the second operand is zero, invert the comparison and swap
6421 the second and third operands. Likewise if the second operand
6422 is constant and the third is not or if the third operand is
6423 equivalent to the first operand of the comparison. */
6425 if (integer_zerop (arg1)
6426 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6427 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6428 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6429 TREE_OPERAND (t, 2),
6430 TREE_OPERAND (arg0, 1))))
6432 /* See if this can be inverted. If it can't, possibly because
6433 it was a floating-point inequality comparison, don't do
6435 tem = invert_truthvalue (arg0);
6437 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6439 t = build (code, type, tem,
6440 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6442 /* arg1 should be the first argument of the new T. */
6443 arg1 = TREE_OPERAND (t, 1);
6448 /* If we have A op B ? A : C, we may be able to convert this to a
6449 simpler expression, depending on the operation and the values
6450 of B and C. Signed zeros prevent all of these transformations,
6451 for reasons given above each one. */
6453 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6454 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6455 arg1, TREE_OPERAND (arg0, 1))
6456 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6458 tree arg2 = TREE_OPERAND (t, 2);
6459 enum tree_code comp_code = TREE_CODE (arg0);
6463 /* If we have A op 0 ? A : -A, consider applying the following
6466 A == 0? A : -A same as -A
6467 A != 0? A : -A same as A
6468 A >= 0? A : -A same as abs (A)
6469 A > 0? A : -A same as abs (A)
6470 A <= 0? A : -A same as -abs (A)
6471 A < 0? A : -A same as -abs (A)
6473 None of these transformations work for modes with signed
6474 zeros. If A is +/-0, the first two transformations will
6475 change the sign of the result (from +0 to -0, or vice
6476 versa). The last four will fix the sign of the result,
6477 even though the original expressions could be positive or
6478 negative, depending on the sign of A.
6480 Note that all these transformations are correct if A is
6481 NaN, since the two alternatives (A and -A) are also NaNs. */
6482 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6483 ? real_zerop (TREE_OPERAND (arg0, 1))
6484 : integer_zerop (TREE_OPERAND (arg0, 1)))
6485 && TREE_CODE (arg2) == NEGATE_EXPR
6486 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6494 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6497 return pedantic_non_lvalue (convert (type, arg1));
6500 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6501 arg1 = convert ((*lang_hooks.types.signed_type)
6502 (TREE_TYPE (arg1)), arg1);
6503 return pedantic_non_lvalue
6504 (convert (type, fold (build1 (ABS_EXPR,
6505 TREE_TYPE (arg1), arg1))));
6508 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6509 arg1 = convert ((lang_hooks.types.signed_type)
6510 (TREE_TYPE (arg1)), arg1);
6511 return pedantic_non_lvalue
6512 (negate_expr (convert (type,
6513 fold (build1 (ABS_EXPR,
6520 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6521 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6522 both transformations are correct when A is NaN: A != 0
6523 is then true, and A == 0 is false. */
6525 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6527 if (comp_code == NE_EXPR)
6528 return pedantic_non_lvalue (convert (type, arg1));
6529 else if (comp_code == EQ_EXPR)
6530 return pedantic_non_lvalue (convert (type, integer_zero_node));
6533 /* Try some transformations of A op B ? A : B.
6535 A == B? A : B same as B
6536 A != B? A : B same as A
6537 A >= B? A : B same as max (A, B)
6538 A > B? A : B same as max (B, A)
6539 A <= B? A : B same as min (A, B)
6540 A < B? A : B same as min (B, A)
6542 As above, these transformations don't work in the presence
6543 of signed zeros. For example, if A and B are zeros of
6544 opposite sign, the first two transformations will change
6545 the sign of the result. In the last four, the original
6546 expressions give different results for (A=+0, B=-0) and
6547 (A=-0, B=+0), but the transformed expressions do not.
6549 The first two transformations are correct if either A or B
6550 is a NaN. In the first transformation, the condition will
6551 be false, and B will indeed be chosen. In the case of the
6552 second transformation, the condition A != B will be true,
6553 and A will be chosen.
6555 The conversions to max() and min() are not correct if B is
6556 a number and A is not. The conditions in the original
6557 expressions will be false, so all four give B. The min()
6558 and max() versions would give a NaN instead. */
6559 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6560 arg2, TREE_OPERAND (arg0, 0)))
6562 tree comp_op0 = TREE_OPERAND (arg0, 0);
6563 tree comp_op1 = TREE_OPERAND (arg0, 1);
6564 tree comp_type = TREE_TYPE (comp_op0);
6566 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6567 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6573 return pedantic_non_lvalue (convert (type, arg2));
6575 return pedantic_non_lvalue (convert (type, arg1));
6578 /* In C++ a ?: expression can be an lvalue, so put the
6579 operand which will be used if they are equal first
6580 so that we can convert this back to the
6581 corresponding COND_EXPR. */
6582 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6583 return pedantic_non_lvalue
6584 (convert (type, fold (build (MIN_EXPR, comp_type,
6585 (comp_code == LE_EXPR
6586 ? comp_op0 : comp_op1),
6587 (comp_code == LE_EXPR
6588 ? comp_op1 : comp_op0)))));
6592 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6593 return pedantic_non_lvalue
6594 (convert (type, fold (build (MAX_EXPR, comp_type,
6595 (comp_code == GE_EXPR
6596 ? comp_op0 : comp_op1),
6597 (comp_code == GE_EXPR
6598 ? comp_op1 : comp_op0)))));
6605 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6606 we might still be able to simplify this. For example,
6607 if C1 is one less or one more than C2, this might have started
6608 out as a MIN or MAX and been transformed by this function.
6609 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6611 if (INTEGRAL_TYPE_P (type)
6612 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6613 && TREE_CODE (arg2) == INTEGER_CST)
6617 /* We can replace A with C1 in this case. */
6618 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6619 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6620 TREE_OPERAND (t, 2));
6624 /* If C1 is C2 + 1, this is min(A, C2). */
6625 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6626 && operand_equal_p (TREE_OPERAND (arg0, 1),
6627 const_binop (PLUS_EXPR, arg2,
6628 integer_one_node, 0), 1))
6629 return pedantic_non_lvalue
6630 (fold (build (MIN_EXPR, type, arg1, arg2)));
6634 /* If C1 is C2 - 1, this is min(A, C2). */
6635 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6636 && operand_equal_p (TREE_OPERAND (arg0, 1),
6637 const_binop (MINUS_EXPR, arg2,
6638 integer_one_node, 0), 1))
6639 return pedantic_non_lvalue
6640 (fold (build (MIN_EXPR, type, arg1, arg2)));
6644 /* If C1 is C2 - 1, this is max(A, C2). */
6645 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6646 && operand_equal_p (TREE_OPERAND (arg0, 1),
6647 const_binop (MINUS_EXPR, arg2,
6648 integer_one_node, 0), 1))
6649 return pedantic_non_lvalue
6650 (fold (build (MAX_EXPR, type, arg1, arg2)));
6654 /* If C1 is C2 + 1, this is max(A, C2). */
6655 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6656 && operand_equal_p (TREE_OPERAND (arg0, 1),
6657 const_binop (PLUS_EXPR, arg2,
6658 integer_one_node, 0), 1))
6659 return pedantic_non_lvalue
6660 (fold (build (MAX_EXPR, type, arg1, arg2)));
6669 /* If the second operand is simpler than the third, swap them
6670 since that produces better jump optimization results. */
6671 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
6672 || TREE_CODE (arg1) == SAVE_EXPR)
6673 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6674 || DECL_P (TREE_OPERAND (t, 2))
6675 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6677 /* See if this can be inverted. If it can't, possibly because
6678 it was a floating-point inequality comparison, don't do
6680 tem = invert_truthvalue (arg0);
6682 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6684 t = build (code, type, tem,
6685 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6687 /* arg1 should be the first argument of the new T. */
6688 arg1 = TREE_OPERAND (t, 1);
6693 /* Convert A ? 1 : 0 to simply A. */
6694 if (integer_onep (TREE_OPERAND (t, 1))
6695 && integer_zerop (TREE_OPERAND (t, 2))
6696 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6697 call to fold will try to move the conversion inside
6698 a COND, which will recurse. In that case, the COND_EXPR
6699 is probably the best choice, so leave it alone. */
6700 && type == TREE_TYPE (arg0))
6701 return pedantic_non_lvalue (arg0);
6703 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
6704 operation is simply A & 2. */
6706 if (integer_zerop (TREE_OPERAND (t, 2))
6707 && TREE_CODE (arg0) == NE_EXPR
6708 && integer_zerop (TREE_OPERAND (arg0, 1))
6709 && integer_pow2p (arg1)
6710 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6711 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6713 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6718 /* When pedantic, a compound expression can be neither an lvalue
6719 nor an integer constant expression. */
6720 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6722 /* Don't let (0, 0) be null pointer constant. */
6723 if (integer_zerop (arg1))
6724 return build1 (NOP_EXPR, type, arg1);
6725 return convert (type, arg1);
6729 return build_complex (type, arg0, arg1);
6733 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6735 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6736 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6737 TREE_OPERAND (arg0, 1));
6738 else if (TREE_CODE (arg0) == COMPLEX_CST)
6739 return TREE_REALPART (arg0);
6740 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6741 return fold (build (TREE_CODE (arg0), type,
6742 fold (build1 (REALPART_EXPR, type,
6743 TREE_OPERAND (arg0, 0))),
6744 fold (build1 (REALPART_EXPR,
6745 type, TREE_OPERAND (arg0, 1)))));
6749 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6750 return convert (type, integer_zero_node);
6751 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6752 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6753 TREE_OPERAND (arg0, 0));
6754 else if (TREE_CODE (arg0) == COMPLEX_CST)
6755 return TREE_IMAGPART (arg0);
6756 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6757 return fold (build (TREE_CODE (arg0), type,
6758 fold (build1 (IMAGPART_EXPR, type,
6759 TREE_OPERAND (arg0, 0))),
6760 fold (build1 (IMAGPART_EXPR, type,
6761 TREE_OPERAND (arg0, 1)))));
6764 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6766 case CLEANUP_POINT_EXPR:
6767 if (! has_cleanups (arg0))
6768 return TREE_OPERAND (t, 0);
6771 enum tree_code code0 = TREE_CODE (arg0);
6772 int kind0 = TREE_CODE_CLASS (code0);
6773 tree arg00 = TREE_OPERAND (arg0, 0);
6776 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6777 return fold (build1 (code0, type,
6778 fold (build1 (CLEANUP_POINT_EXPR,
6779 TREE_TYPE (arg00), arg00))));
6781 if (kind0 == '<' || kind0 == '2'
6782 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6783 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
6784 || code0 == TRUTH_XOR_EXPR)
6786 arg01 = TREE_OPERAND (arg0, 1);
6788 if (TREE_CONSTANT (arg00)
6789 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6790 && ! has_cleanups (arg00)))
6791 return fold (build (code0, type, arg00,
6792 fold (build1 (CLEANUP_POINT_EXPR,
6793 TREE_TYPE (arg01), arg01))));
6795 if (TREE_CONSTANT (arg01))
6796 return fold (build (code0, type,
6797 fold (build1 (CLEANUP_POINT_EXPR,
6798 TREE_TYPE (arg00), arg00)),
6806 /* Check for a built-in function. */
6807 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
6808 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
6810 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
6812 tree tmp = fold_builtin (expr);
6820 } /* switch (code) */
6823 /* Determine if first argument is a multiple of second argument. Return 0 if
6824 it is not, or we cannot easily determined it to be.
6826 An example of the sort of thing we care about (at this point; this routine
6827 could surely be made more general, and expanded to do what the *_DIV_EXPR's
6828 fold cases do now) is discovering that
6830 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6836 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
6838 This code also handles discovering that
6840 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6842 is a multiple of 8 so we don't have to worry about dealing with a
6845 Note that we *look* inside a SAVE_EXPR only to determine how it was
6846 calculated; it is not safe for fold to do much of anything else with the
6847 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
6848 at run time. For example, the latter example above *cannot* be implemented
6849 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
6850 evaluation time of the original SAVE_EXPR is not necessarily the same at
6851 the time the new expression is evaluated. The only optimization of this
6852 sort that would be valid is changing
6854 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6858 SAVE_EXPR (I) * SAVE_EXPR (J)
6860 (where the same SAVE_EXPR (J) is used in the original and the
6861 transformed version). */
6864 multiple_of_p (type, top, bottom)
6869 if (operand_equal_p (top, bottom, 0))
6872 if (TREE_CODE (type) != INTEGER_TYPE)
6875 switch (TREE_CODE (top))
6878 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6879 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6883 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6884 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6887 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
6891 op1 = TREE_OPERAND (top, 1);
6892 /* const_binop may not detect overflow correctly,
6893 so check for it explicitly here. */
6894 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
6895 > TREE_INT_CST_LOW (op1)
6896 && TREE_INT_CST_HIGH (op1) == 0
6897 && 0 != (t1 = convert (type,
6898 const_binop (LSHIFT_EXPR, size_one_node,
6900 && ! TREE_OVERFLOW (t1))
6901 return multiple_of_p (type, t1, bottom);
6906 /* Can't handle conversions from non-integral or wider integral type. */
6907 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6908 || (TYPE_PRECISION (type)
6909 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6912 /* .. fall through ... */
6915 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6918 if (TREE_CODE (bottom) != INTEGER_CST
6919 || (TREE_UNSIGNED (type)
6920 && (tree_int_cst_sgn (top) < 0
6921 || tree_int_cst_sgn (bottom) < 0)))
6923 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6931 /* Return true if `t' is known to be non-negative. */
6934 tree_expr_nonnegative_p (t)
6937 switch (TREE_CODE (t))
6943 return tree_int_cst_sgn (t) >= 0;
6944 case TRUNC_DIV_EXPR:
6946 case FLOOR_DIV_EXPR:
6947 case ROUND_DIV_EXPR:
6948 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6949 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6950 case TRUNC_MOD_EXPR:
6952 case FLOOR_MOD_EXPR:
6953 case ROUND_MOD_EXPR:
6954 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6956 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
6957 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
6959 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6961 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6962 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6964 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6965 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6967 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6969 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6971 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6972 case NON_LVALUE_EXPR:
6973 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6975 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
6978 if (truth_value_p (TREE_CODE (t)))
6979 /* Truth values evaluate to 0 or 1, which is nonnegative. */
6982 /* We don't know sign of `t', so be conservative and return false. */
6987 /* Return true if `r' is known to be non-negative.
6988 Only handles constants at the moment. */
6991 rtl_expr_nonnegative_p (r)
6994 switch (GET_CODE (r))
6997 return INTVAL (r) >= 0;
7000 if (GET_MODE (r) == VOIDmode)
7001 return CONST_DOUBLE_HIGH (r) >= 0;
7009 units = CONST_VECTOR_NUNITS (r);
7011 for (i = 0; i < units; ++i)
7013 elt = CONST_VECTOR_ELT (r, i);
7014 if (!rtl_expr_nonnegative_p (elt))
7023 /* These are always nonnegative. */