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));
4699 /* Convert (T)(x & c) into (T)x & (T)c, if c is an integer
4700 constants (if x has signed type, the sign bit cannot be set
4701 in c). This folds extension into the BIT_AND_EXPR. */
4702 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
4703 && TREE_CODE (TREE_OPERAND (t, 0)) == BIT_AND_EXPR
4704 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST)
4706 tree and = TREE_OPERAND (t, 0);
4707 tree and0 = TREE_OPERAND (and, 0), and1 = TREE_OPERAND (and, 1);
4710 if (TREE_UNSIGNED (TREE_TYPE (and))
4711 || (TYPE_PRECISION (TREE_TYPE (t))
4712 <= TYPE_PRECISION (TREE_TYPE (and))))
4714 else if (TYPE_PRECISION (TREE_TYPE (and1))
4715 <= HOST_BITS_PER_WIDE_INT
4716 && host_integerp (and1, 1))
4718 unsigned HOST_WIDE_INT cst;
4720 cst = tree_low_cst (and1, 1);
4721 cst &= (HOST_WIDE_INT) -1
4722 << (TYPE_PRECISION (TREE_TYPE (and1)) - 1);
4723 change = (cst == 0);
4724 #ifdef LOAD_EXTEND_OP
4726 && (LOAD_EXTEND_OP (TYPE_MODE (TREE_TYPE (and0)))
4729 tree uns = unsigned_type (TREE_TYPE (and0));
4730 and0 = convert (uns, and0);
4731 and1 = convert (uns, and1);
4736 return fold (build (BIT_AND_EXPR, TREE_TYPE (t),
4737 convert (TREE_TYPE (t), and0),
4738 convert (TREE_TYPE (t), and1)));
4743 TREE_CONSTANT (t) = TREE_CONSTANT (arg0);
4746 return fold_convert (t, arg0);
4748 case VIEW_CONVERT_EXPR:
4749 if (TREE_CODE (TREE_OPERAND (t, 0)) == VIEW_CONVERT_EXPR)
4750 return build1 (VIEW_CONVERT_EXPR, type,
4751 TREE_OPERAND (TREE_OPERAND (t, 0), 0));
4755 if (TREE_CODE (arg0) == CONSTRUCTOR)
4757 tree m = purpose_member (arg1, CONSTRUCTOR_ELTS (arg0));
4764 TREE_CONSTANT (t) = wins;
4770 if (TREE_CODE (arg0) == INTEGER_CST)
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 && !TREE_UNSIGNED (type)));
4782 TREE_CONSTANT_OVERFLOW (t)
4783 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4785 else if (TREE_CODE (arg0) == REAL_CST)
4786 t = build_real (type, REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4788 else if (TREE_CODE (arg0) == NEGATE_EXPR)
4789 return TREE_OPERAND (arg0, 0);
4791 /* Convert - (a - b) to (b - a) for non-floating-point. */
4792 else if (TREE_CODE (arg0) == MINUS_EXPR
4793 && (! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations))
4794 return build (MINUS_EXPR, type, TREE_OPERAND (arg0, 1),
4795 TREE_OPERAND (arg0, 0));
4802 if (TREE_CODE (arg0) == INTEGER_CST)
4804 /* If the value is unsigned, then the absolute value is
4805 the same as the ordinary value. */
4806 if (TREE_UNSIGNED (type))
4808 /* Similarly, if the value is non-negative. */
4809 else if (INT_CST_LT (integer_minus_one_node, arg0))
4811 /* If the value is negative, then the absolute value is
4815 unsigned HOST_WIDE_INT low;
4817 int overflow = neg_double (TREE_INT_CST_LOW (arg0),
4818 TREE_INT_CST_HIGH (arg0),
4820 t = build_int_2 (low, high);
4821 TREE_TYPE (t) = type;
4823 = (TREE_OVERFLOW (arg0)
4824 | force_fit_type (t, overflow));
4825 TREE_CONSTANT_OVERFLOW (t)
4826 = TREE_OVERFLOW (t) | TREE_CONSTANT_OVERFLOW (arg0);
4829 else if (TREE_CODE (arg0) == REAL_CST)
4831 if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (arg0)))
4832 t = build_real (type,
4833 REAL_VALUE_NEGATE (TREE_REAL_CST (arg0)));
4836 else if (TREE_CODE (arg0) == ABS_EXPR || TREE_CODE (arg0) == NEGATE_EXPR)
4837 return build1 (ABS_EXPR, type, TREE_OPERAND (arg0, 0));
4841 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
4842 return convert (type, arg0);
4843 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
4844 return build (COMPLEX_EXPR, type,
4845 TREE_OPERAND (arg0, 0),
4846 negate_expr (TREE_OPERAND (arg0, 1)));
4847 else if (TREE_CODE (arg0) == COMPLEX_CST)
4848 return build_complex (type, TREE_REALPART (arg0),
4849 negate_expr (TREE_IMAGPART (arg0)));
4850 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
4851 return fold (build (TREE_CODE (arg0), type,
4852 fold (build1 (CONJ_EXPR, type,
4853 TREE_OPERAND (arg0, 0))),
4854 fold (build1 (CONJ_EXPR,
4855 type, TREE_OPERAND (arg0, 1)))));
4856 else if (TREE_CODE (arg0) == CONJ_EXPR)
4857 return TREE_OPERAND (arg0, 0);
4863 t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
4864 ~ TREE_INT_CST_HIGH (arg0));
4865 TREE_TYPE (t) = type;
4866 force_fit_type (t, 0);
4867 TREE_OVERFLOW (t) = TREE_OVERFLOW (arg0);
4868 TREE_CONSTANT_OVERFLOW (t) = TREE_CONSTANT_OVERFLOW (arg0);
4870 else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
4871 return TREE_OPERAND (arg0, 0);
4875 /* A + (-B) -> A - B */
4876 if (TREE_CODE (arg1) == NEGATE_EXPR)
4877 return fold (build (MINUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
4878 /* (-A) + B -> B - A */
4879 if (TREE_CODE (arg0) == NEGATE_EXPR)
4880 return fold (build (MINUS_EXPR, type, arg1, TREE_OPERAND (arg0, 0)));
4881 else if (! FLOAT_TYPE_P (type))
4883 if (integer_zerop (arg1))
4884 return non_lvalue (convert (type, arg0));
4886 /* If we are adding two BIT_AND_EXPR's, both of which are and'ing
4887 with a constant, and the two constants have no bits in common,
4888 we should treat this as a BIT_IOR_EXPR since this may produce more
4890 if (TREE_CODE (arg0) == BIT_AND_EXPR
4891 && TREE_CODE (arg1) == BIT_AND_EXPR
4892 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
4893 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
4894 && integer_zerop (const_binop (BIT_AND_EXPR,
4895 TREE_OPERAND (arg0, 1),
4896 TREE_OPERAND (arg1, 1), 0)))
4898 code = BIT_IOR_EXPR;
4902 /* Reassociate (plus (plus (mult) (foo)) (mult)) as
4903 (plus (plus (mult) (mult)) (foo)) so that we can
4904 take advantage of the factoring cases below. */
4905 if ((TREE_CODE (arg0) == PLUS_EXPR
4906 && TREE_CODE (arg1) == MULT_EXPR)
4907 || (TREE_CODE (arg1) == PLUS_EXPR
4908 && TREE_CODE (arg0) == MULT_EXPR))
4910 tree parg0, parg1, parg, marg;
4912 if (TREE_CODE (arg0) == PLUS_EXPR)
4913 parg = arg0, marg = arg1;
4915 parg = arg1, marg = arg0;
4916 parg0 = TREE_OPERAND (parg, 0);
4917 parg1 = TREE_OPERAND (parg, 1);
4921 if (TREE_CODE (parg0) == MULT_EXPR
4922 && TREE_CODE (parg1) != MULT_EXPR)
4923 return fold (build (PLUS_EXPR, type,
4924 fold (build (PLUS_EXPR, type, parg0, marg)),
4926 if (TREE_CODE (parg0) != MULT_EXPR
4927 && TREE_CODE (parg1) == MULT_EXPR)
4928 return fold (build (PLUS_EXPR, type,
4929 fold (build (PLUS_EXPR, type, parg1, marg)),
4933 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR)
4935 tree arg00, arg01, arg10, arg11;
4936 tree alt0 = NULL_TREE, alt1 = NULL_TREE, same;
4938 /* (A * C) + (B * C) -> (A+B) * C.
4939 We are most concerned about the case where C is a constant,
4940 but other combinations show up during loop reduction. Since
4941 it is not difficult, try all four possibilities. */
4943 arg00 = TREE_OPERAND (arg0, 0);
4944 arg01 = TREE_OPERAND (arg0, 1);
4945 arg10 = TREE_OPERAND (arg1, 0);
4946 arg11 = TREE_OPERAND (arg1, 1);
4949 if (operand_equal_p (arg01, arg11, 0))
4950 same = arg01, alt0 = arg00, alt1 = arg10;
4951 else if (operand_equal_p (arg00, arg10, 0))
4952 same = arg00, alt0 = arg01, alt1 = arg11;
4953 else if (operand_equal_p (arg00, arg11, 0))
4954 same = arg00, alt0 = arg01, alt1 = arg10;
4955 else if (operand_equal_p (arg01, arg10, 0))
4956 same = arg01, alt0 = arg00, alt1 = arg11;
4958 /* No identical multiplicands; see if we can find a common
4959 power-of-two factor in non-power-of-two multiplies. This
4960 can help in multi-dimensional array access. */
4961 else if (TREE_CODE (arg01) == INTEGER_CST
4962 && TREE_CODE (arg11) == INTEGER_CST
4963 && TREE_INT_CST_HIGH (arg01) == 0
4964 && TREE_INT_CST_HIGH (arg11) == 0)
4966 HOST_WIDE_INT int01, int11, tmp;
4967 int01 = TREE_INT_CST_LOW (arg01);
4968 int11 = TREE_INT_CST_LOW (arg11);
4970 /* Move min of absolute values to int11. */
4971 if ((int01 >= 0 ? int01 : -int01)
4972 < (int11 >= 0 ? int11 : -int11))
4974 tmp = int01, int01 = int11, int11 = tmp;
4975 alt0 = arg00, arg00 = arg10, arg10 = alt0;
4976 alt0 = arg01, arg01 = arg11, arg11 = alt0;
4979 if (exact_log2 (int11) > 0 && int01 % int11 == 0)
4981 alt0 = fold (build (MULT_EXPR, type, arg00,
4982 build_int_2 (int01 / int11, 0)));
4989 return fold (build (MULT_EXPR, type,
4990 fold (build (PLUS_EXPR, type, alt0, alt1)),
4995 /* See if ARG1 is zero and X + ARG1 reduces to X. */
4996 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 0))
4997 return non_lvalue (convert (type, arg0));
4999 /* Likewise if the operands are reversed. */
5000 else if (fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5001 return non_lvalue (convert (type, arg1));
5004 /* (A << C1) + (A >> C2) if A is unsigned and C1+C2 is the size of A
5005 is a rotate of A by C1 bits. */
5006 /* (A << B) + (A >> (Z - B)) if A is unsigned and Z is the size of A
5007 is a rotate of A by B bits. */
5009 enum tree_code code0, code1;
5010 code0 = TREE_CODE (arg0);
5011 code1 = TREE_CODE (arg1);
5012 if (((code0 == RSHIFT_EXPR && code1 == LSHIFT_EXPR)
5013 || (code1 == RSHIFT_EXPR && code0 == LSHIFT_EXPR))
5014 && operand_equal_p (TREE_OPERAND (arg0, 0),
5015 TREE_OPERAND (arg1, 0), 0)
5016 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5018 tree tree01, tree11;
5019 enum tree_code code01, code11;
5021 tree01 = TREE_OPERAND (arg0, 1);
5022 tree11 = TREE_OPERAND (arg1, 1);
5023 STRIP_NOPS (tree01);
5024 STRIP_NOPS (tree11);
5025 code01 = TREE_CODE (tree01);
5026 code11 = TREE_CODE (tree11);
5027 if (code01 == INTEGER_CST
5028 && code11 == INTEGER_CST
5029 && TREE_INT_CST_HIGH (tree01) == 0
5030 && TREE_INT_CST_HIGH (tree11) == 0
5031 && ((TREE_INT_CST_LOW (tree01) + TREE_INT_CST_LOW (tree11))
5032 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)))))
5033 return build (LROTATE_EXPR, type, TREE_OPERAND (arg0, 0),
5034 code0 == LSHIFT_EXPR ? tree01 : tree11);
5035 else if (code11 == MINUS_EXPR)
5037 tree tree110, tree111;
5038 tree110 = TREE_OPERAND (tree11, 0);
5039 tree111 = TREE_OPERAND (tree11, 1);
5040 STRIP_NOPS (tree110);
5041 STRIP_NOPS (tree111);
5042 if (TREE_CODE (tree110) == INTEGER_CST
5043 && 0 == compare_tree_int (tree110,
5045 (TREE_TYPE (TREE_OPERAND
5047 && operand_equal_p (tree01, tree111, 0))
5048 return build ((code0 == LSHIFT_EXPR
5051 type, TREE_OPERAND (arg0, 0), tree01);
5053 else if (code01 == MINUS_EXPR)
5055 tree tree010, tree011;
5056 tree010 = TREE_OPERAND (tree01, 0);
5057 tree011 = TREE_OPERAND (tree01, 1);
5058 STRIP_NOPS (tree010);
5059 STRIP_NOPS (tree011);
5060 if (TREE_CODE (tree010) == INTEGER_CST
5061 && 0 == compare_tree_int (tree010,
5063 (TREE_TYPE (TREE_OPERAND
5065 && operand_equal_p (tree11, tree011, 0))
5066 return build ((code0 != LSHIFT_EXPR
5069 type, TREE_OPERAND (arg0, 0), tree11);
5075 /* In most languages, can't associate operations on floats through
5076 parentheses. Rather than remember where the parentheses were, we
5077 don't associate floats at all. It shouldn't matter much. However,
5078 associating multiplications is only very slightly inaccurate, so do
5079 that if -funsafe-math-optimizations is specified. */
5082 && (! FLOAT_TYPE_P (type)
5083 || (flag_unsafe_math_optimizations && code == MULT_EXPR)))
5085 tree var0, con0, lit0, var1, con1, lit1;
5087 /* Split both trees into variables, constants, and literals. Then
5088 associate each group together, the constants with literals,
5089 then the result with variables. This increases the chances of
5090 literals being recombined later and of generating relocatable
5091 expressions for the sum of a constant and literal. */
5092 var0 = split_tree (arg0, code, &con0, &lit0, 0);
5093 var1 = split_tree (arg1, code, &con1, &lit1, code == MINUS_EXPR);
5095 /* Only do something if we found more than two objects. Otherwise,
5096 nothing has changed and we risk infinite recursion. */
5097 if (2 < ((var0 != 0) + (var1 != 0) + (con0 != 0) + (con1 != 0)
5098 + (lit0 != 0) + (lit1 != 0)))
5100 var0 = associate_trees (var0, var1, code, type);
5101 con0 = associate_trees (con0, con1, code, type);
5102 lit0 = associate_trees (lit0, lit1, code, type);
5103 con0 = associate_trees (con0, lit0, code, type);
5104 return convert (type, associate_trees (var0, con0, code, type));
5110 t1 = const_binop (code, arg0, arg1, 0);
5111 if (t1 != NULL_TREE)
5113 /* The return value should always have
5114 the same type as the original expression. */
5115 if (TREE_TYPE (t1) != TREE_TYPE (t))
5116 t1 = convert (TREE_TYPE (t), t1);
5123 /* A - (-B) -> A + B */
5124 if (TREE_CODE (arg1) == NEGATE_EXPR)
5125 return fold (build (PLUS_EXPR, type, arg0, TREE_OPERAND (arg1, 0)));
5126 /* (-A) - CST -> (-CST) - A for floating point (what about ints ?) */
5127 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5129 fold (build (MINUS_EXPR, type,
5130 build_real (TREE_TYPE (arg1),
5131 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1))),
5132 TREE_OPERAND (arg0, 0)));
5134 if (! FLOAT_TYPE_P (type))
5136 if (! wins && integer_zerop (arg0))
5137 return negate_expr (convert (type, arg1));
5138 if (integer_zerop (arg1))
5139 return non_lvalue (convert (type, arg0));
5141 /* (A * C) - (B * C) -> (A-B) * C. Since we are most concerned
5142 about the case where C is a constant, just try one of the
5143 four possibilities. */
5145 if (TREE_CODE (arg0) == MULT_EXPR && TREE_CODE (arg1) == MULT_EXPR
5146 && operand_equal_p (TREE_OPERAND (arg0, 1),
5147 TREE_OPERAND (arg1, 1), 0))
5148 return fold (build (MULT_EXPR, type,
5149 fold (build (MINUS_EXPR, type,
5150 TREE_OPERAND (arg0, 0),
5151 TREE_OPERAND (arg1, 0))),
5152 TREE_OPERAND (arg0, 1)));
5155 /* See if ARG1 is zero and X - ARG1 reduces to X. */
5156 else if (fold_real_zero_addition_p (TREE_TYPE (arg0), arg1, 1))
5157 return non_lvalue (convert (type, arg0));
5159 /* (ARG0 - ARG1) is the same as (-ARG1 + ARG0). So check whether
5160 ARG0 is zero and X + ARG0 reduces to X, since that would mean
5161 (-ARG1 + ARG0) reduces to -ARG1. */
5162 else if (!wins && fold_real_zero_addition_p (TREE_TYPE (arg1), arg0, 0))
5163 return negate_expr (convert (type, arg1));
5165 /* Fold &x - &x. This can happen from &x.foo - &x.
5166 This is unsafe for certain floats even in non-IEEE formats.
5167 In IEEE, it is unsafe because it does wrong for NaNs.
5168 Also note that operand_equal_p is always false if an operand
5171 if ((! FLOAT_TYPE_P (type) || flag_unsafe_math_optimizations)
5172 && operand_equal_p (arg0, arg1, 0))
5173 return convert (type, integer_zero_node);
5178 /* (-A) * (-B) -> A * B */
5179 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5180 return fold (build (MULT_EXPR, type, TREE_OPERAND (arg0, 0),
5181 TREE_OPERAND (arg1, 0)));
5183 if (! FLOAT_TYPE_P (type))
5185 if (integer_zerop (arg1))
5186 return omit_one_operand (type, arg1, arg0);
5187 if (integer_onep (arg1))
5188 return non_lvalue (convert (type, arg0));
5190 /* (a * (1 << b)) is (a << b) */
5191 if (TREE_CODE (arg1) == LSHIFT_EXPR
5192 && integer_onep (TREE_OPERAND (arg1, 0)))
5193 return fold (build (LSHIFT_EXPR, type, arg0,
5194 TREE_OPERAND (arg1, 1)));
5195 if (TREE_CODE (arg0) == LSHIFT_EXPR
5196 && integer_onep (TREE_OPERAND (arg0, 0)))
5197 return fold (build (LSHIFT_EXPR, type, arg1,
5198 TREE_OPERAND (arg0, 1)));
5200 if (TREE_CODE (arg1) == INTEGER_CST
5201 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5203 return convert (type, tem);
5208 /* Maybe fold x * 0 to 0. The expressions aren't the same
5209 when x is NaN, since x * 0 is also NaN. Nor are they the
5210 same in modes with signed zeros, since multiplying a
5211 negative value by 0 gives -0, not +0. */
5212 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0)))
5213 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0)))
5214 && real_zerop (arg1))
5215 return omit_one_operand (type, arg1, arg0);
5216 /* In IEEE floating point, x*1 is not equivalent to x for snans.
5217 However, ANSI says we can drop signals,
5218 so we can do this anyway. */
5219 if (real_onep (arg1))
5220 return non_lvalue (convert (type, arg0));
5222 if (! wins && real_twop (arg1)
5223 && (*lang_hooks.decls.global_bindings_p) () == 0
5224 && ! contains_placeholder_p (arg0))
5226 tree arg = save_expr (arg0);
5227 return build (PLUS_EXPR, type, arg, arg);
5234 if (integer_all_onesp (arg1))
5235 return omit_one_operand (type, arg1, arg0);
5236 if (integer_zerop (arg1))
5237 return non_lvalue (convert (type, arg0));
5238 t1 = distribute_bit_expr (code, type, arg0, arg1);
5239 if (t1 != NULL_TREE)
5242 /* Convert (or (not arg0) (not arg1)) to (not (and (arg0) (arg1))).
5244 This results in more efficient code for machines without a NAND
5245 instruction. Combine will canonicalize to the first form
5246 which will allow use of NAND instructions provided by the
5247 backend if they exist. */
5248 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5249 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5251 return fold (build1 (BIT_NOT_EXPR, type,
5252 build (BIT_AND_EXPR, type,
5253 TREE_OPERAND (arg0, 0),
5254 TREE_OPERAND (arg1, 0))));
5257 /* See if this can be simplified into a rotate first. If that
5258 is unsuccessful continue in the association code. */
5262 if (integer_zerop (arg1))
5263 return non_lvalue (convert (type, arg0));
5264 if (integer_all_onesp (arg1))
5265 return fold (build1 (BIT_NOT_EXPR, type, arg0));
5267 /* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
5268 with a constant, and the two constants have no bits in common,
5269 we should treat this as a BIT_IOR_EXPR since this may produce more
5271 if (TREE_CODE (arg0) == BIT_AND_EXPR
5272 && TREE_CODE (arg1) == BIT_AND_EXPR
5273 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5274 && TREE_CODE (TREE_OPERAND (arg1, 1)) == INTEGER_CST
5275 && integer_zerop (const_binop (BIT_AND_EXPR,
5276 TREE_OPERAND (arg0, 1),
5277 TREE_OPERAND (arg1, 1), 0)))
5279 code = BIT_IOR_EXPR;
5283 /* See if this can be simplified into a rotate first. If that
5284 is unsuccessful continue in the association code. */
5289 if (integer_all_onesp (arg1))
5290 return non_lvalue (convert (type, arg0));
5291 if (integer_zerop (arg1))
5292 return omit_one_operand (type, arg1, arg0);
5293 t1 = distribute_bit_expr (code, type, arg0, arg1);
5294 if (t1 != NULL_TREE)
5296 /* Simplify ((int)c & 0x377) into (int)c, if c is unsigned char. */
5297 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == NOP_EXPR
5298 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg1, 0))))
5301 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg1, 0)));
5303 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5304 && (~TREE_INT_CST_LOW (arg0)
5305 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5306 return build1 (NOP_EXPR, type, TREE_OPERAND (arg1, 0));
5308 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) == NOP_EXPR
5309 && TREE_UNSIGNED (TREE_TYPE (TREE_OPERAND (arg0, 0))))
5312 = TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg0, 0)));
5314 if (prec < BITS_PER_WORD && prec < HOST_BITS_PER_WIDE_INT
5315 && (~TREE_INT_CST_LOW (arg1)
5316 & (((HOST_WIDE_INT) 1 << prec) - 1)) == 0)
5317 return build1 (NOP_EXPR, type, TREE_OPERAND (arg0, 0));
5320 /* Convert (and (not arg0) (not arg1)) to (not (or (arg0) (arg1))).
5322 This results in more efficient code for machines without a NOR
5323 instruction. Combine will canonicalize to the first form
5324 which will allow use of NOR instructions provided by the
5325 backend if they exist. */
5326 if (TREE_CODE (arg0) == BIT_NOT_EXPR
5327 && TREE_CODE (arg1) == BIT_NOT_EXPR)
5329 return fold (build1 (BIT_NOT_EXPR, type,
5330 build (BIT_IOR_EXPR, type,
5331 TREE_OPERAND (arg0, 0),
5332 TREE_OPERAND (arg1, 0))));
5337 case BIT_ANDTC_EXPR:
5338 if (integer_all_onesp (arg0))
5339 return non_lvalue (convert (type, arg1));
5340 if (integer_zerop (arg0))
5341 return omit_one_operand (type, arg0, arg1);
5342 if (TREE_CODE (arg1) == INTEGER_CST)
5344 arg1 = fold (build1 (BIT_NOT_EXPR, type, arg1));
5345 code = BIT_AND_EXPR;
5351 /* Don't touch a floating-point divide by zero unless the mode
5352 of the constant can represent infinity. */
5353 if (TREE_CODE (arg1) == REAL_CST
5354 && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (arg1)))
5355 && real_zerop (arg1))
5358 /* (-A) / (-B) -> A / B */
5359 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == NEGATE_EXPR)
5360 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5361 TREE_OPERAND (arg1, 0)));
5363 /* In IEEE floating point, x/1 is not equivalent to x for snans.
5364 However, ANSI says we can drop signals, so we can do this anyway. */
5365 if (real_onep (arg1))
5366 return non_lvalue (convert (type, arg0));
5368 /* If ARG1 is a constant, we can convert this to a multiply by the
5369 reciprocal. This does not have the same rounding properties,
5370 so only do this if -funsafe-math-optimizations. We can actually
5371 always safely do it if ARG1 is a power of two, but it's hard to
5372 tell if it is or not in a portable manner. */
5373 if (TREE_CODE (arg1) == REAL_CST)
5375 if (flag_unsafe_math_optimizations
5376 && 0 != (tem = const_binop (code, build_real (type, dconst1),
5378 return fold (build (MULT_EXPR, type, arg0, tem));
5379 /* Find the reciprocal if optimizing and the result is exact. */
5383 r = TREE_REAL_CST (arg1);
5384 if (exact_real_inverse (TYPE_MODE(TREE_TYPE(arg0)), &r))
5386 tem = build_real (type, r);
5387 return fold (build (MULT_EXPR, type, arg0, tem));
5391 /* Convert A/B/C to A/(B*C). */
5392 if (flag_unsafe_math_optimizations
5393 && TREE_CODE (arg0) == RDIV_EXPR)
5395 return fold (build (RDIV_EXPR, type, TREE_OPERAND (arg0, 0),
5396 build (MULT_EXPR, type, TREE_OPERAND (arg0, 1),
5399 /* Convert A/(B/C) to (A/B)*C. */
5400 if (flag_unsafe_math_optimizations
5401 && TREE_CODE (arg1) == RDIV_EXPR)
5403 return fold (build (MULT_EXPR, type,
5404 build (RDIV_EXPR, type, arg0,
5405 TREE_OPERAND (arg1, 0)),
5406 TREE_OPERAND (arg1, 1)));
5410 case TRUNC_DIV_EXPR:
5411 case ROUND_DIV_EXPR:
5412 case FLOOR_DIV_EXPR:
5414 case EXACT_DIV_EXPR:
5415 if (integer_onep (arg1))
5416 return non_lvalue (convert (type, arg0));
5417 if (integer_zerop (arg1))
5420 /* If arg0 is a multiple of arg1, then rewrite to the fastest div
5421 operation, EXACT_DIV_EXPR.
5423 Note that only CEIL_DIV_EXPR and FLOOR_DIV_EXPR are rewritten now.
5424 At one time others generated faster code, it's not clear if they do
5425 after the last round to changes to the DIV code in expmed.c. */
5426 if ((code == CEIL_DIV_EXPR || code == FLOOR_DIV_EXPR)
5427 && multiple_of_p (type, arg0, arg1))
5428 return fold (build (EXACT_DIV_EXPR, type, arg0, arg1));
5430 if (TREE_CODE (arg1) == INTEGER_CST
5431 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5433 return convert (type, tem);
5438 case FLOOR_MOD_EXPR:
5439 case ROUND_MOD_EXPR:
5440 case TRUNC_MOD_EXPR:
5441 if (integer_onep (arg1))
5442 return omit_one_operand (type, integer_zero_node, arg0);
5443 if (integer_zerop (arg1))
5446 if (TREE_CODE (arg1) == INTEGER_CST
5447 && 0 != (tem = extract_muldiv (TREE_OPERAND (t, 0), arg1,
5449 return convert (type, tem);
5457 if (integer_zerop (arg1))
5458 return non_lvalue (convert (type, arg0));
5459 /* Since negative shift count is not well-defined,
5460 don't try to compute it in the compiler. */
5461 if (TREE_CODE (arg1) == INTEGER_CST && tree_int_cst_sgn (arg1) < 0)
5463 /* Rewrite an LROTATE_EXPR by a constant into an
5464 RROTATE_EXPR by a new constant. */
5465 if (code == LROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST)
5467 TREE_SET_CODE (t, RROTATE_EXPR);
5468 code = RROTATE_EXPR;
5469 TREE_OPERAND (t, 1) = arg1
5472 convert (TREE_TYPE (arg1),
5473 build_int_2 (GET_MODE_BITSIZE (TYPE_MODE (type)), 0)),
5475 if (tree_int_cst_sgn (arg1) < 0)
5479 /* If we have a rotate of a bit operation with the rotate count and
5480 the second operand of the bit operation both constant,
5481 permute the two operations. */
5482 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5483 && (TREE_CODE (arg0) == BIT_AND_EXPR
5484 || TREE_CODE (arg0) == BIT_ANDTC_EXPR
5485 || TREE_CODE (arg0) == BIT_IOR_EXPR
5486 || TREE_CODE (arg0) == BIT_XOR_EXPR)
5487 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5488 return fold (build (TREE_CODE (arg0), type,
5489 fold (build (code, type,
5490 TREE_OPERAND (arg0, 0), arg1)),
5491 fold (build (code, type,
5492 TREE_OPERAND (arg0, 1), arg1))));
5494 /* Two consecutive rotates adding up to the width of the mode can
5496 if (code == RROTATE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5497 && TREE_CODE (arg0) == RROTATE_EXPR
5498 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5499 && TREE_INT_CST_HIGH (arg1) == 0
5500 && TREE_INT_CST_HIGH (TREE_OPERAND (arg0, 1)) == 0
5501 && ((TREE_INT_CST_LOW (arg1)
5502 + TREE_INT_CST_LOW (TREE_OPERAND (arg0, 1)))
5503 == (unsigned int) GET_MODE_BITSIZE (TYPE_MODE (type))))
5504 return TREE_OPERAND (arg0, 0);
5509 if (operand_equal_p (arg0, arg1, 0))
5510 return omit_one_operand (type, arg0, arg1);
5511 if (INTEGRAL_TYPE_P (type)
5512 && operand_equal_p (arg1, TYPE_MIN_VALUE (type), 1))
5513 return omit_one_operand (type, arg1, arg0);
5517 if (operand_equal_p (arg0, arg1, 0))
5518 return omit_one_operand (type, arg0, arg1);
5519 if (INTEGRAL_TYPE_P (type)
5520 && TYPE_MAX_VALUE (type)
5521 && operand_equal_p (arg1, TYPE_MAX_VALUE (type), 1))
5522 return omit_one_operand (type, arg1, arg0);
5525 case TRUTH_NOT_EXPR:
5526 /* Note that the operand of this must be an int
5527 and its values must be 0 or 1.
5528 ("true" is a fixed value perhaps depending on the language,
5529 but we don't handle values other than 1 correctly yet.) */
5530 tem = invert_truthvalue (arg0);
5531 /* Avoid infinite recursion. */
5532 if (TREE_CODE (tem) == TRUTH_NOT_EXPR)
5534 return convert (type, tem);
5536 case TRUTH_ANDIF_EXPR:
5537 /* Note that the operands of this must be ints
5538 and their values must be 0 or 1.
5539 ("true" is a fixed value perhaps depending on the language.) */
5540 /* If first arg is constant zero, return it. */
5541 if (integer_zerop (arg0))
5542 return convert (type, arg0);
5543 case TRUTH_AND_EXPR:
5544 /* If either arg is constant true, drop it. */
5545 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5546 return non_lvalue (convert (type, arg1));
5547 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1)
5548 /* Preserve sequence points. */
5549 && (code != TRUTH_ANDIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5550 return non_lvalue (convert (type, arg0));
5551 /* If second arg is constant zero, result is zero, but first arg
5552 must be evaluated. */
5553 if (integer_zerop (arg1))
5554 return omit_one_operand (type, arg1, arg0);
5555 /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
5556 case will be handled here. */
5557 if (integer_zerop (arg0))
5558 return omit_one_operand (type, arg0, arg1);
5561 /* We only do these simplifications if we are optimizing. */
5565 /* Check for things like (A || B) && (A || C). We can convert this
5566 to A || (B && C). Note that either operator can be any of the four
5567 truth and/or operations and the transformation will still be
5568 valid. Also note that we only care about order for the
5569 ANDIF and ORIF operators. If B contains side effects, this
5570 might change the truth-value of A. */
5571 if (TREE_CODE (arg0) == TREE_CODE (arg1)
5572 && (TREE_CODE (arg0) == TRUTH_ANDIF_EXPR
5573 || TREE_CODE (arg0) == TRUTH_ORIF_EXPR
5574 || TREE_CODE (arg0) == TRUTH_AND_EXPR
5575 || TREE_CODE (arg0) == TRUTH_OR_EXPR)
5576 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)))
5578 tree a00 = TREE_OPERAND (arg0, 0);
5579 tree a01 = TREE_OPERAND (arg0, 1);
5580 tree a10 = TREE_OPERAND (arg1, 0);
5581 tree a11 = TREE_OPERAND (arg1, 1);
5582 int commutative = ((TREE_CODE (arg0) == TRUTH_OR_EXPR
5583 || TREE_CODE (arg0) == TRUTH_AND_EXPR)
5584 && (code == TRUTH_AND_EXPR
5585 || code == TRUTH_OR_EXPR));
5587 if (operand_equal_p (a00, a10, 0))
5588 return fold (build (TREE_CODE (arg0), type, a00,
5589 fold (build (code, type, a01, a11))));
5590 else if (commutative && operand_equal_p (a00, a11, 0))
5591 return fold (build (TREE_CODE (arg0), type, a00,
5592 fold (build (code, type, a01, a10))));
5593 else if (commutative && operand_equal_p (a01, a10, 0))
5594 return fold (build (TREE_CODE (arg0), type, a01,
5595 fold (build (code, type, a00, a11))));
5597 /* This case if tricky because we must either have commutative
5598 operators or else A10 must not have side-effects. */
5600 else if ((commutative || ! TREE_SIDE_EFFECTS (a10))
5601 && operand_equal_p (a01, a11, 0))
5602 return fold (build (TREE_CODE (arg0), type,
5603 fold (build (code, type, a00, a10)),
5607 /* See if we can build a range comparison. */
5608 if (0 != (tem = fold_range_test (t)))
5611 /* Check for the possibility of merging component references. If our
5612 lhs is another similar operation, try to merge its rhs with our
5613 rhs. Then try to merge our lhs and rhs. */
5614 if (TREE_CODE (arg0) == code
5615 && 0 != (tem = fold_truthop (code, type,
5616 TREE_OPERAND (arg0, 1), arg1)))
5617 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5619 if ((tem = fold_truthop (code, type, arg0, arg1)) != 0)
5624 case TRUTH_ORIF_EXPR:
5625 /* Note that the operands of this must be ints
5626 and their values must be 0 or true.
5627 ("true" is a fixed value perhaps depending on the language.) */
5628 /* If first arg is constant true, return it. */
5629 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5630 return convert (type, arg0);
5632 /* If either arg is constant zero, drop it. */
5633 if (TREE_CODE (arg0) == INTEGER_CST && integer_zerop (arg0))
5634 return non_lvalue (convert (type, arg1));
5635 if (TREE_CODE (arg1) == INTEGER_CST && integer_zerop (arg1)
5636 /* Preserve sequence points. */
5637 && (code != TRUTH_ORIF_EXPR || ! TREE_SIDE_EFFECTS (arg0)))
5638 return non_lvalue (convert (type, arg0));
5639 /* If second arg is constant true, result is true, but we must
5640 evaluate first arg. */
5641 if (TREE_CODE (arg1) == INTEGER_CST && ! integer_zerop (arg1))
5642 return omit_one_operand (type, arg1, arg0);
5643 /* Likewise for first arg, but note this only occurs here for
5645 if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
5646 return omit_one_operand (type, arg0, arg1);
5649 case TRUTH_XOR_EXPR:
5650 /* If either arg is constant zero, drop it. */
5651 if (integer_zerop (arg0))
5652 return non_lvalue (convert (type, arg1));
5653 if (integer_zerop (arg1))
5654 return non_lvalue (convert (type, arg0));
5655 /* If either arg is constant true, this is a logical inversion. */
5656 if (integer_onep (arg0))
5657 return non_lvalue (convert (type, invert_truthvalue (arg1)));
5658 if (integer_onep (arg1))
5659 return non_lvalue (convert (type, invert_truthvalue (arg0)));
5668 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
5670 /* (-a) CMP (-b) -> b CMP a */
5671 if (TREE_CODE (arg0) == NEGATE_EXPR
5672 && TREE_CODE (arg1) == NEGATE_EXPR)
5673 return fold (build (code, type, TREE_OPERAND (arg1, 0),
5674 TREE_OPERAND (arg0, 0)));
5675 /* (-a) CMP CST -> a swap(CMP) (-CST) */
5676 if (TREE_CODE (arg0) == NEGATE_EXPR && TREE_CODE (arg1) == REAL_CST)
5679 (swap_tree_comparison (code), type,
5680 TREE_OPERAND (arg0, 0),
5681 build_real (TREE_TYPE (arg1),
5682 REAL_VALUE_NEGATE (TREE_REAL_CST (arg1)))));
5683 /* IEEE doesn't distinguish +0 and -0 in comparisons. */
5684 /* a CMP (-0) -> a CMP 0 */
5685 if (TREE_CODE (arg1) == REAL_CST
5686 && REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (arg1)))
5687 return fold (build (code, type, arg0,
5688 build_real (TREE_TYPE (arg1), dconst0)));
5691 /* If one arg is a constant integer, put it last. */
5692 if (TREE_CODE (arg0) == INTEGER_CST
5693 && TREE_CODE (arg1) != INTEGER_CST)
5695 TREE_OPERAND (t, 0) = arg1;
5696 TREE_OPERAND (t, 1) = arg0;
5697 arg0 = TREE_OPERAND (t, 0);
5698 arg1 = TREE_OPERAND (t, 1);
5699 code = swap_tree_comparison (code);
5700 TREE_SET_CODE (t, code);
5703 /* Convert foo++ == CONST into ++foo == CONST + INCR.
5704 First, see if one arg is constant; find the constant arg
5705 and the other one. */
5707 tree constop = 0, varop = NULL_TREE;
5708 int constopnum = -1;
5710 if (TREE_CONSTANT (arg1))
5711 constopnum = 1, constop = arg1, varop = arg0;
5712 if (TREE_CONSTANT (arg0))
5713 constopnum = 0, constop = arg0, varop = arg1;
5715 if (constop && TREE_CODE (varop) == POSTINCREMENT_EXPR)
5717 /* This optimization is invalid for ordered comparisons
5718 if CONST+INCR overflows or if foo+incr might overflow.
5719 This optimization is invalid for floating point due to rounding.
5720 For pointer types we assume overflow doesn't happen. */
5721 if (POINTER_TYPE_P (TREE_TYPE (varop))
5722 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5723 && (code == EQ_EXPR || code == NE_EXPR)))
5726 = fold (build (PLUS_EXPR, TREE_TYPE (varop),
5727 constop, TREE_OPERAND (varop, 1)));
5729 /* Do not overwrite the current varop to be a preincrement,
5730 create a new node so that we won't confuse our caller who
5731 might create trees and throw them away, reusing the
5732 arguments that they passed to build. This shows up in
5733 the THEN or ELSE parts of ?: being postincrements. */
5734 varop = build (PREINCREMENT_EXPR, TREE_TYPE (varop),
5735 TREE_OPERAND (varop, 0),
5736 TREE_OPERAND (varop, 1));
5738 /* If VAROP is a reference to a bitfield, we must mask
5739 the constant by the width of the field. */
5740 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5741 && DECL_BIT_FIELD(TREE_OPERAND
5742 (TREE_OPERAND (varop, 0), 1)))
5745 = TREE_INT_CST_LOW (DECL_SIZE
5747 (TREE_OPERAND (varop, 0), 1)));
5748 tree mask, unsigned_type;
5749 unsigned int precision;
5750 tree folded_compare;
5752 /* First check whether the comparison would come out
5753 always the same. If we don't do that we would
5754 change the meaning with the masking. */
5755 if (constopnum == 0)
5756 folded_compare = fold (build (code, type, constop,
5757 TREE_OPERAND (varop, 0)));
5759 folded_compare = fold (build (code, type,
5760 TREE_OPERAND (varop, 0),
5762 if (integer_zerop (folded_compare)
5763 || integer_onep (folded_compare))
5764 return omit_one_operand (type, folded_compare, varop);
5766 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5767 precision = TYPE_PRECISION (unsigned_type);
5768 mask = build_int_2 (~0, ~0);
5769 TREE_TYPE (mask) = unsigned_type;
5770 force_fit_type (mask, 0);
5771 mask = const_binop (RSHIFT_EXPR, mask,
5772 size_int (precision - size), 0);
5773 newconst = fold (build (BIT_AND_EXPR,
5774 TREE_TYPE (varop), newconst,
5775 convert (TREE_TYPE (varop),
5779 t = build (code, type,
5780 (constopnum == 0) ? newconst : varop,
5781 (constopnum == 1) ? newconst : varop);
5785 else if (constop && TREE_CODE (varop) == POSTDECREMENT_EXPR)
5787 if (POINTER_TYPE_P (TREE_TYPE (varop))
5788 || (! FLOAT_TYPE_P (TREE_TYPE (varop))
5789 && (code == EQ_EXPR || code == NE_EXPR)))
5792 = fold (build (MINUS_EXPR, TREE_TYPE (varop),
5793 constop, TREE_OPERAND (varop, 1)));
5795 /* Do not overwrite the current varop to be a predecrement,
5796 create a new node so that we won't confuse our caller who
5797 might create trees and throw them away, reusing the
5798 arguments that they passed to build. This shows up in
5799 the THEN or ELSE parts of ?: being postdecrements. */
5800 varop = build (PREDECREMENT_EXPR, TREE_TYPE (varop),
5801 TREE_OPERAND (varop, 0),
5802 TREE_OPERAND (varop, 1));
5804 if (TREE_CODE (TREE_OPERAND (varop, 0)) == COMPONENT_REF
5805 && DECL_BIT_FIELD(TREE_OPERAND
5806 (TREE_OPERAND (varop, 0), 1)))
5809 = TREE_INT_CST_LOW (DECL_SIZE
5811 (TREE_OPERAND (varop, 0), 1)));
5812 tree mask, unsigned_type;
5813 unsigned int precision;
5814 tree folded_compare;
5816 if (constopnum == 0)
5817 folded_compare = fold (build (code, type, constop,
5818 TREE_OPERAND (varop, 0)));
5820 folded_compare = fold (build (code, type,
5821 TREE_OPERAND (varop, 0),
5823 if (integer_zerop (folded_compare)
5824 || integer_onep (folded_compare))
5825 return omit_one_operand (type, folded_compare, varop);
5827 unsigned_type = (*lang_hooks.types.type_for_size)(size, 1);
5828 precision = TYPE_PRECISION (unsigned_type);
5829 mask = build_int_2 (~0, ~0);
5830 TREE_TYPE (mask) = TREE_TYPE (varop);
5831 force_fit_type (mask, 0);
5832 mask = const_binop (RSHIFT_EXPR, mask,
5833 size_int (precision - size), 0);
5834 newconst = fold (build (BIT_AND_EXPR,
5835 TREE_TYPE (varop), newconst,
5836 convert (TREE_TYPE (varop),
5840 t = build (code, type,
5841 (constopnum == 0) ? newconst : varop,
5842 (constopnum == 1) ? newconst : varop);
5848 /* Change X >= CST to X > (CST - 1) if CST is positive. */
5849 if (TREE_CODE (arg1) == INTEGER_CST
5850 && TREE_CODE (arg0) != INTEGER_CST
5851 && tree_int_cst_sgn (arg1) > 0)
5853 switch (TREE_CODE (t))
5857 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5858 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5863 arg1 = const_binop (MINUS_EXPR, arg1, integer_one_node, 0);
5864 t = build (code, type, TREE_OPERAND (t, 0), arg1);
5872 /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
5873 a MINUS_EXPR of a constant, we can convert it into a comparison with
5874 a revised constant as long as no overflow occurs. */
5875 if ((code == EQ_EXPR || code == NE_EXPR)
5876 && TREE_CODE (arg1) == INTEGER_CST
5877 && (TREE_CODE (arg0) == PLUS_EXPR
5878 || TREE_CODE (arg0) == MINUS_EXPR)
5879 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
5880 && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
5881 ? MINUS_EXPR : PLUS_EXPR,
5882 arg1, TREE_OPERAND (arg0, 1), 0))
5883 && ! TREE_CONSTANT_OVERFLOW (tem))
5884 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5886 /* Similarly for a NEGATE_EXPR. */
5887 else if ((code == EQ_EXPR || code == NE_EXPR)
5888 && TREE_CODE (arg0) == NEGATE_EXPR
5889 && TREE_CODE (arg1) == INTEGER_CST
5890 && 0 != (tem = negate_expr (arg1))
5891 && TREE_CODE (tem) == INTEGER_CST
5892 && ! TREE_CONSTANT_OVERFLOW (tem))
5893 return fold (build (code, type, TREE_OPERAND (arg0, 0), tem));
5895 /* If we have X - Y == 0, we can convert that to X == Y and similarly
5896 for !=. Don't do this for ordered comparisons due to overflow. */
5897 else if ((code == NE_EXPR || code == EQ_EXPR)
5898 && integer_zerop (arg1) && TREE_CODE (arg0) == MINUS_EXPR)
5899 return fold (build (code, type,
5900 TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
5902 /* If we are widening one operand of an integer comparison,
5903 see if the other operand is similarly being widened. Perhaps we
5904 can do the comparison in the narrower type. */
5905 else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
5906 && TREE_CODE (arg0) == NOP_EXPR
5907 && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
5908 && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
5909 && (TREE_TYPE (t1) == TREE_TYPE (tem)
5910 || (TREE_CODE (t1) == INTEGER_CST
5911 && int_fits_type_p (t1, TREE_TYPE (tem)))))
5912 return fold (build (code, type, tem, convert (TREE_TYPE (tem), t1)));
5914 /* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
5915 constant, we can simplify it. */
5916 else if (TREE_CODE (arg1) == INTEGER_CST
5917 && (TREE_CODE (arg0) == MIN_EXPR
5918 || TREE_CODE (arg0) == MAX_EXPR)
5919 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
5920 return optimize_minmax_comparison (t);
5922 /* If we are comparing an ABS_EXPR with a constant, we can
5923 convert all the cases into explicit comparisons, but they may
5924 well not be faster than doing the ABS and one comparison.
5925 But ABS (X) <= C is a range comparison, which becomes a subtraction
5926 and a comparison, and is probably faster. */
5927 else if (code == LE_EXPR && TREE_CODE (arg1) == INTEGER_CST
5928 && TREE_CODE (arg0) == ABS_EXPR
5929 && ! TREE_SIDE_EFFECTS (arg0)
5930 && (0 != (tem = negate_expr (arg1)))
5931 && TREE_CODE (tem) == INTEGER_CST
5932 && ! TREE_CONSTANT_OVERFLOW (tem))
5933 return fold (build (TRUTH_ANDIF_EXPR, type,
5934 build (GE_EXPR, type, TREE_OPERAND (arg0, 0), tem),
5935 build (LE_EXPR, type,
5936 TREE_OPERAND (arg0, 0), arg1)));
5938 /* If this is an EQ or NE comparison with zero and ARG0 is
5939 (1 << foo) & bar, convert it to (bar >> foo) & 1. Both require
5940 two operations, but the latter can be done in one less insn
5941 on machines that have only two-operand insns or on which a
5942 constant cannot be the first operand. */
5943 if (integer_zerop (arg1) && (code == EQ_EXPR || code == NE_EXPR)
5944 && TREE_CODE (arg0) == BIT_AND_EXPR)
5946 if (TREE_CODE (TREE_OPERAND (arg0, 0)) == LSHIFT_EXPR
5947 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 0), 0)))
5949 fold (build (code, type,
5950 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5952 TREE_TYPE (TREE_OPERAND (arg0, 0)),
5953 TREE_OPERAND (arg0, 1),
5954 TREE_OPERAND (TREE_OPERAND (arg0, 0), 1)),
5955 convert (TREE_TYPE (arg0),
5958 else if (TREE_CODE (TREE_OPERAND (arg0, 1)) == LSHIFT_EXPR
5959 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg0, 1), 0)))
5961 fold (build (code, type,
5962 build (BIT_AND_EXPR, TREE_TYPE (arg0),
5964 TREE_TYPE (TREE_OPERAND (arg0, 1)),
5965 TREE_OPERAND (arg0, 0),
5966 TREE_OPERAND (TREE_OPERAND (arg0, 1), 1)),
5967 convert (TREE_TYPE (arg0),
5972 /* If this is an NE or EQ comparison of zero against the result of a
5973 signed MOD operation whose second operand is a power of 2, make
5974 the MOD operation unsigned since it is simpler and equivalent. */
5975 if ((code == NE_EXPR || code == EQ_EXPR)
5976 && integer_zerop (arg1)
5977 && ! TREE_UNSIGNED (TREE_TYPE (arg0))
5978 && (TREE_CODE (arg0) == TRUNC_MOD_EXPR
5979 || TREE_CODE (arg0) == CEIL_MOD_EXPR
5980 || TREE_CODE (arg0) == FLOOR_MOD_EXPR
5981 || TREE_CODE (arg0) == ROUND_MOD_EXPR)
5982 && integer_pow2p (TREE_OPERAND (arg0, 1)))
5984 tree newtype = (*lang_hooks.types.unsigned_type) (TREE_TYPE (arg0));
5985 tree newmod = build (TREE_CODE (arg0), newtype,
5986 convert (newtype, TREE_OPERAND (arg0, 0)),
5987 convert (newtype, TREE_OPERAND (arg0, 1)));
5989 return build (code, type, newmod, convert (newtype, arg1));
5992 /* If this is an NE comparison of zero with an AND of one, remove the
5993 comparison since the AND will give the correct value. */
5994 if (code == NE_EXPR && integer_zerop (arg1)
5995 && TREE_CODE (arg0) == BIT_AND_EXPR
5996 && integer_onep (TREE_OPERAND (arg0, 1)))
5997 return convert (type, arg0);
5999 /* If we have (A & C) == C where C is a power of 2, convert this into
6000 (A & C) != 0. Similarly for NE_EXPR. */
6001 if ((code == EQ_EXPR || code == NE_EXPR)
6002 && TREE_CODE (arg0) == BIT_AND_EXPR
6003 && integer_pow2p (TREE_OPERAND (arg0, 1))
6004 && operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
6005 return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
6006 arg0, integer_zero_node);
6008 /* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
6009 and similarly for >= into !=. */
6010 if ((code == LT_EXPR || code == GE_EXPR)
6011 && TREE_UNSIGNED (TREE_TYPE (arg0))
6012 && TREE_CODE (arg1) == LSHIFT_EXPR
6013 && integer_onep (TREE_OPERAND (arg1, 0)))
6014 return build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6015 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6016 TREE_OPERAND (arg1, 1)),
6017 convert (TREE_TYPE (arg0), integer_zero_node));
6019 else if ((code == LT_EXPR || code == GE_EXPR)
6020 && TREE_UNSIGNED (TREE_TYPE (arg0))
6021 && (TREE_CODE (arg1) == NOP_EXPR
6022 || TREE_CODE (arg1) == CONVERT_EXPR)
6023 && TREE_CODE (TREE_OPERAND (arg1, 0)) == LSHIFT_EXPR
6024 && integer_onep (TREE_OPERAND (TREE_OPERAND (arg1, 0), 0)))
6026 build (code == LT_EXPR ? EQ_EXPR : NE_EXPR, type,
6027 convert (TREE_TYPE (arg0),
6028 build (RSHIFT_EXPR, TREE_TYPE (arg0), arg0,
6029 TREE_OPERAND (TREE_OPERAND (arg1, 0), 1))),
6030 convert (TREE_TYPE (arg0), integer_zero_node));
6032 /* Simplify comparison of something with itself. (For IEEE
6033 floating-point, we can only do some of these simplifications.) */
6034 if (operand_equal_p (arg0, arg1, 0))
6041 if (! FLOAT_TYPE_P (TREE_TYPE (arg0)))
6042 return constant_boolean_node (1, type);
6044 TREE_SET_CODE (t, code);
6048 /* For NE, we can only do this simplification if integer. */
6049 if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
6051 /* ... fall through ... */
6054 return constant_boolean_node (0, type);
6060 /* An unsigned comparison against 0 can be simplified. */
6061 if (integer_zerop (arg1)
6062 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6063 || POINTER_TYPE_P (TREE_TYPE (arg1)))
6064 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6066 switch (TREE_CODE (t))
6070 TREE_SET_CODE (t, NE_EXPR);
6074 TREE_SET_CODE (t, EQ_EXPR);
6077 return omit_one_operand (type,
6078 convert (type, integer_one_node),
6081 return omit_one_operand (type,
6082 convert (type, integer_zero_node),
6089 /* Comparisons with the highest or lowest possible integer of
6090 the specified size will have known values and an unsigned
6091 <= 0x7fffffff can be simplified. */
6093 int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
6095 if (TREE_CODE (arg1) == INTEGER_CST
6096 && ! TREE_CONSTANT_OVERFLOW (arg1)
6097 && width <= HOST_BITS_PER_WIDE_INT
6098 && (INTEGRAL_TYPE_P (TREE_TYPE (arg1))
6099 || POINTER_TYPE_P (TREE_TYPE (arg1))))
6101 if (TREE_INT_CST_HIGH (arg1) == 0
6102 && (TREE_INT_CST_LOW (arg1)
6103 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6104 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6105 switch (TREE_CODE (t))
6108 return omit_one_operand (type,
6109 convert (type, integer_zero_node),
6112 TREE_SET_CODE (t, EQ_EXPR);
6116 return omit_one_operand (type,
6117 convert (type, integer_one_node),
6120 TREE_SET_CODE (t, NE_EXPR);
6127 else if (TREE_INT_CST_HIGH (arg1) == -1
6128 && (TREE_INT_CST_LOW (arg1)
6129 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)))
6130 && ! TREE_UNSIGNED (TREE_TYPE (arg1)))
6131 switch (TREE_CODE (t))
6134 return omit_one_operand (type,
6135 convert (type, integer_zero_node),
6138 TREE_SET_CODE (t, EQ_EXPR);
6142 return omit_one_operand (type,
6143 convert (type, integer_one_node),
6146 TREE_SET_CODE (t, NE_EXPR);
6153 else if (TREE_INT_CST_HIGH (arg1) == 0
6154 && (TREE_INT_CST_LOW (arg1)
6155 == ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1)
6156 && TREE_UNSIGNED (TREE_TYPE (arg1))
6157 /* signed_type does not work on pointer types. */
6158 && INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
6160 if (TREE_CODE (t) == LE_EXPR || TREE_CODE (t) == GT_EXPR)
6163 st0 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg0));
6164 st1 = (*lang_hooks.types.signed_type) (TREE_TYPE (arg1));
6166 (build (TREE_CODE (t) == LE_EXPR ? GE_EXPR: LT_EXPR,
6167 type, convert (st0, arg0),
6168 convert (st1, integer_zero_node)));
6171 else if (TREE_INT_CST_HIGH (arg1) == 0
6172 && (TREE_INT_CST_LOW (arg1)
6173 == ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1)
6174 && TREE_UNSIGNED (TREE_TYPE (arg1)))
6175 switch (TREE_CODE (t))
6178 return omit_one_operand (type,
6179 convert (type, integer_zero_node),
6182 TREE_SET_CODE (t, EQ_EXPR);
6186 return omit_one_operand (type,
6187 convert (type, integer_one_node),
6190 TREE_SET_CODE (t, NE_EXPR);
6199 /* If we are comparing an expression that just has comparisons
6200 of two integer values, arithmetic expressions of those comparisons,
6201 and constants, we can simplify it. There are only three cases
6202 to check: the two values can either be equal, the first can be
6203 greater, or the second can be greater. Fold the expression for
6204 those three values. Since each value must be 0 or 1, we have
6205 eight possibilities, each of which corresponds to the constant 0
6206 or 1 or one of the six possible comparisons.
6208 This handles common cases like (a > b) == 0 but also handles
6209 expressions like ((x > y) - (y > x)) > 0, which supposedly
6210 occur in macroized code. */
6212 if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg0) != INTEGER_CST)
6214 tree cval1 = 0, cval2 = 0;
6217 if (twoval_comparison_p (arg0, &cval1, &cval2, &save_p)
6218 /* Don't handle degenerate cases here; they should already
6219 have been handled anyway. */
6220 && cval1 != 0 && cval2 != 0
6221 && ! (TREE_CONSTANT (cval1) && TREE_CONSTANT (cval2))
6222 && TREE_TYPE (cval1) == TREE_TYPE (cval2)
6223 && INTEGRAL_TYPE_P (TREE_TYPE (cval1))
6224 && TYPE_MAX_VALUE (TREE_TYPE (cval1))
6225 && TYPE_MAX_VALUE (TREE_TYPE (cval2))
6226 && ! operand_equal_p (TYPE_MIN_VALUE (TREE_TYPE (cval1)),
6227 TYPE_MAX_VALUE (TREE_TYPE (cval2)), 0))
6229 tree maxval = TYPE_MAX_VALUE (TREE_TYPE (cval1));
6230 tree minval = TYPE_MIN_VALUE (TREE_TYPE (cval1));
6232 /* We can't just pass T to eval_subst in case cval1 or cval2
6233 was the same as ARG1. */
6236 = fold (build (code, type,
6237 eval_subst (arg0, cval1, maxval, cval2, minval),
6240 = fold (build (code, type,
6241 eval_subst (arg0, cval1, maxval, cval2, maxval),
6244 = fold (build (code, type,
6245 eval_subst (arg0, cval1, minval, cval2, maxval),
6248 /* All three of these results should be 0 or 1. Confirm they
6249 are. Then use those values to select the proper code
6252 if ((integer_zerop (high_result)
6253 || integer_onep (high_result))
6254 && (integer_zerop (equal_result)
6255 || integer_onep (equal_result))
6256 && (integer_zerop (low_result)
6257 || integer_onep (low_result)))
6259 /* Make a 3-bit mask with the high-order bit being the
6260 value for `>', the next for '=', and the low for '<'. */
6261 switch ((integer_onep (high_result) * 4)
6262 + (integer_onep (equal_result) * 2)
6263 + integer_onep (low_result))
6267 return omit_one_operand (type, integer_zero_node, arg0);
6288 return omit_one_operand (type, integer_one_node, arg0);
6291 t = build (code, type, cval1, cval2);
6293 return save_expr (t);
6300 /* If this is a comparison of a field, we may be able to simplify it. */
6301 if ((TREE_CODE (arg0) == COMPONENT_REF
6302 || TREE_CODE (arg0) == BIT_FIELD_REF)
6303 && (code == EQ_EXPR || code == NE_EXPR)
6304 /* Handle the constant case even without -O
6305 to make sure the warnings are given. */
6306 && (optimize || TREE_CODE (arg1) == INTEGER_CST))
6308 t1 = optimize_bit_field_compare (code, type, arg0, arg1);
6312 /* If this is a comparison of complex values and either or both sides
6313 are a COMPLEX_EXPR or COMPLEX_CST, it is best to split up the
6314 comparisons and join them with a TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR.
6315 This may prevent needless evaluations. */
6316 if ((code == EQ_EXPR || code == NE_EXPR)
6317 && TREE_CODE (TREE_TYPE (arg0)) == COMPLEX_TYPE
6318 && (TREE_CODE (arg0) == COMPLEX_EXPR
6319 || TREE_CODE (arg1) == COMPLEX_EXPR
6320 || TREE_CODE (arg0) == COMPLEX_CST
6321 || TREE_CODE (arg1) == COMPLEX_CST))
6323 tree subtype = TREE_TYPE (TREE_TYPE (arg0));
6324 tree real0, imag0, real1, imag1;
6326 arg0 = save_expr (arg0);
6327 arg1 = save_expr (arg1);
6328 real0 = fold (build1 (REALPART_EXPR, subtype, arg0));
6329 imag0 = fold (build1 (IMAGPART_EXPR, subtype, arg0));
6330 real1 = fold (build1 (REALPART_EXPR, subtype, arg1));
6331 imag1 = fold (build1 (IMAGPART_EXPR, subtype, arg1));
6333 return fold (build ((code == EQ_EXPR ? TRUTH_ANDIF_EXPR
6336 fold (build (code, type, real0, real1)),
6337 fold (build (code, type, imag0, imag1))));
6340 /* Optimize comparisons of strlen vs zero to a compare of the
6341 first character of the string vs zero. To wit,
6342 strlen(ptr) == 0 => *ptr == 0
6343 strlen(ptr) != 0 => *ptr != 0
6344 Other cases should reduce to one of these two (or a constant)
6345 due to the return value of strlen being unsigned. */
6346 if ((code == EQ_EXPR || code == NE_EXPR)
6347 && integer_zerop (arg1)
6348 && TREE_CODE (arg0) == CALL_EXPR
6349 && TREE_CODE (TREE_OPERAND (arg0, 0)) == ADDR_EXPR)
6351 tree fndecl = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
6354 if (TREE_CODE (fndecl) == FUNCTION_DECL
6355 && DECL_BUILT_IN (fndecl)
6356 && DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD
6357 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STRLEN
6358 && (arglist = TREE_OPERAND (arg0, 1))
6359 && TREE_CODE (TREE_TYPE (TREE_VALUE (arglist))) == POINTER_TYPE
6360 && ! TREE_CHAIN (arglist))
6361 return fold (build (code, type,
6362 build1 (INDIRECT_REF, char_type_node,
6363 TREE_VALUE(arglist)),
6364 integer_zero_node));
6367 /* From here on, the only cases we handle are when the result is
6368 known to be a constant.
6370 To compute GT, swap the arguments and do LT.
6371 To compute GE, do LT and invert the result.
6372 To compute LE, swap the arguments, do LT and invert the result.
6373 To compute NE, do EQ and invert the result.
6375 Therefore, the code below must handle only EQ and LT. */
6377 if (code == LE_EXPR || code == GT_EXPR)
6379 tem = arg0, arg0 = arg1, arg1 = tem;
6380 code = swap_tree_comparison (code);
6383 /* Note that it is safe to invert for real values here because we
6384 will check below in the one case that it matters. */
6388 if (code == NE_EXPR || code == GE_EXPR)
6391 code = invert_tree_comparison (code);
6394 /* Compute a result for LT or EQ if args permit;
6395 otherwise return T. */
6396 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
6398 if (code == EQ_EXPR)
6399 t1 = build_int_2 (tree_int_cst_equal (arg0, arg1), 0);
6401 t1 = build_int_2 ((TREE_UNSIGNED (TREE_TYPE (arg0))
6402 ? INT_CST_LT_UNSIGNED (arg0, arg1)
6403 : INT_CST_LT (arg0, arg1)),
6407 #if 0 /* This is no longer useful, but breaks some real code. */
6408 /* Assume a nonexplicit constant cannot equal an explicit one,
6409 since such code would be undefined anyway.
6410 Exception: on sysvr4, using #pragma weak,
6411 a label can come out as 0. */
6412 else if (TREE_CODE (arg1) == INTEGER_CST
6413 && !integer_zerop (arg1)
6414 && TREE_CONSTANT (arg0)
6415 && TREE_CODE (arg0) == ADDR_EXPR
6417 t1 = build_int_2 (0, 0);
6419 /* Two real constants can be compared explicitly. */
6420 else if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
6422 /* If either operand is a NaN, the result is false with two
6423 exceptions: First, an NE_EXPR is true on NaNs, but that case
6424 is already handled correctly since we will be inverting the
6425 result for NE_EXPR. Second, if we had inverted a LE_EXPR
6426 or a GE_EXPR into a LT_EXPR, we must return true so that it
6427 will be inverted into false. */
6429 if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg0))
6430 || REAL_VALUE_ISNAN (TREE_REAL_CST (arg1)))
6431 t1 = build_int_2 (invert && code == LT_EXPR, 0);
6433 else if (code == EQ_EXPR)
6434 t1 = build_int_2 (REAL_VALUES_EQUAL (TREE_REAL_CST (arg0),
6435 TREE_REAL_CST (arg1)),
6438 t1 = build_int_2 (REAL_VALUES_LESS (TREE_REAL_CST (arg0),
6439 TREE_REAL_CST (arg1)),
6443 if (t1 == NULL_TREE)
6447 TREE_INT_CST_LOW (t1) ^= 1;
6449 TREE_TYPE (t1) = type;
6450 if (TREE_CODE (type) == BOOLEAN_TYPE)
6451 return (*lang_hooks.truthvalue_conversion) (t1);
6455 /* Pedantic ANSI C says that a conditional expression is never an lvalue,
6456 so all simple results must be passed through pedantic_non_lvalue. */
6457 if (TREE_CODE (arg0) == INTEGER_CST)
6458 return pedantic_non_lvalue
6459 (TREE_OPERAND (t, (integer_zerop (arg0) ? 2 : 1)));
6460 else if (operand_equal_p (arg1, TREE_OPERAND (expr, 2), 0))
6461 return pedantic_omit_one_operand (type, arg1, arg0);
6463 /* If the second operand is zero, invert the comparison and swap
6464 the second and third operands. Likewise if the second operand
6465 is constant and the third is not or if the third operand is
6466 equivalent to the first operand of the comparison. */
6468 if (integer_zerop (arg1)
6469 || (TREE_CONSTANT (arg1) && ! TREE_CONSTANT (TREE_OPERAND (t, 2)))
6470 || (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6471 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6472 TREE_OPERAND (t, 2),
6473 TREE_OPERAND (arg0, 1))))
6475 /* See if this can be inverted. If it can't, possibly because
6476 it was a floating-point inequality comparison, don't do
6478 tem = invert_truthvalue (arg0);
6480 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6482 t = build (code, type, tem,
6483 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6485 /* arg1 should be the first argument of the new T. */
6486 arg1 = TREE_OPERAND (t, 1);
6491 /* If we have A op B ? A : C, we may be able to convert this to a
6492 simpler expression, depending on the operation and the values
6493 of B and C. Signed zeros prevent all of these transformations,
6494 for reasons given above each one. */
6496 if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
6497 && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
6498 arg1, TREE_OPERAND (arg0, 1))
6499 && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
6501 tree arg2 = TREE_OPERAND (t, 2);
6502 enum tree_code comp_code = TREE_CODE (arg0);
6506 /* If we have A op 0 ? A : -A, consider applying the following
6509 A == 0? A : -A same as -A
6510 A != 0? A : -A same as A
6511 A >= 0? A : -A same as abs (A)
6512 A > 0? A : -A same as abs (A)
6513 A <= 0? A : -A same as -abs (A)
6514 A < 0? A : -A same as -abs (A)
6516 None of these transformations work for modes with signed
6517 zeros. If A is +/-0, the first two transformations will
6518 change the sign of the result (from +0 to -0, or vice
6519 versa). The last four will fix the sign of the result,
6520 even though the original expressions could be positive or
6521 negative, depending on the sign of A.
6523 Note that all these transformations are correct if A is
6524 NaN, since the two alternatives (A and -A) are also NaNs. */
6525 if ((FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg0, 1)))
6526 ? real_zerop (TREE_OPERAND (arg0, 1))
6527 : integer_zerop (TREE_OPERAND (arg0, 1)))
6528 && TREE_CODE (arg2) == NEGATE_EXPR
6529 && operand_equal_p (TREE_OPERAND (arg2, 0), arg1, 0))
6537 (convert (TREE_TYPE (TREE_OPERAND (t, 1)),
6540 return pedantic_non_lvalue (convert (type, arg1));
6543 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6544 arg1 = convert ((*lang_hooks.types.signed_type)
6545 (TREE_TYPE (arg1)), arg1);
6546 return pedantic_non_lvalue
6547 (convert (type, fold (build1 (ABS_EXPR,
6548 TREE_TYPE (arg1), arg1))));
6551 if (TREE_UNSIGNED (TREE_TYPE (arg1)))
6552 arg1 = convert ((lang_hooks.types.signed_type)
6553 (TREE_TYPE (arg1)), arg1);
6554 return pedantic_non_lvalue
6555 (negate_expr (convert (type,
6556 fold (build1 (ABS_EXPR,
6563 /* A != 0 ? A : 0 is simply A, unless A is -0. Likewise
6564 A == 0 ? A : 0 is always 0 unless A is -0. Note that
6565 both transformations are correct when A is NaN: A != 0
6566 is then true, and A == 0 is false. */
6568 if (integer_zerop (TREE_OPERAND (arg0, 1)) && integer_zerop (arg2))
6570 if (comp_code == NE_EXPR)
6571 return pedantic_non_lvalue (convert (type, arg1));
6572 else if (comp_code == EQ_EXPR)
6573 return pedantic_non_lvalue (convert (type, integer_zero_node));
6576 /* Try some transformations of A op B ? A : B.
6578 A == B? A : B same as B
6579 A != B? A : B same as A
6580 A >= B? A : B same as max (A, B)
6581 A > B? A : B same as max (B, A)
6582 A <= B? A : B same as min (A, B)
6583 A < B? A : B same as min (B, A)
6585 As above, these transformations don't work in the presence
6586 of signed zeros. For example, if A and B are zeros of
6587 opposite sign, the first two transformations will change
6588 the sign of the result. In the last four, the original
6589 expressions give different results for (A=+0, B=-0) and
6590 (A=-0, B=+0), but the transformed expressions do not.
6592 The first two transformations are correct if either A or B
6593 is a NaN. In the first transformation, the condition will
6594 be false, and B will indeed be chosen. In the case of the
6595 second transformation, the condition A != B will be true,
6596 and A will be chosen.
6598 The conversions to max() and min() are not correct if B is
6599 a number and A is not. The conditions in the original
6600 expressions will be false, so all four give B. The min()
6601 and max() versions would give a NaN instead. */
6602 if (operand_equal_for_comparison_p (TREE_OPERAND (arg0, 1),
6603 arg2, TREE_OPERAND (arg0, 0)))
6605 tree comp_op0 = TREE_OPERAND (arg0, 0);
6606 tree comp_op1 = TREE_OPERAND (arg0, 1);
6607 tree comp_type = TREE_TYPE (comp_op0);
6609 /* Avoid adding NOP_EXPRs in case this is an lvalue. */
6610 if (TYPE_MAIN_VARIANT (comp_type) == TYPE_MAIN_VARIANT (type))
6616 return pedantic_non_lvalue (convert (type, arg2));
6618 return pedantic_non_lvalue (convert (type, arg1));
6621 /* In C++ a ?: expression can be an lvalue, so put the
6622 operand which will be used if they are equal first
6623 so that we can convert this back to the
6624 corresponding COND_EXPR. */
6625 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6626 return pedantic_non_lvalue
6627 (convert (type, fold (build (MIN_EXPR, comp_type,
6628 (comp_code == LE_EXPR
6629 ? comp_op0 : comp_op1),
6630 (comp_code == LE_EXPR
6631 ? comp_op1 : comp_op0)))));
6635 if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (arg1))))
6636 return pedantic_non_lvalue
6637 (convert (type, fold (build (MAX_EXPR, comp_type,
6638 (comp_code == GE_EXPR
6639 ? comp_op0 : comp_op1),
6640 (comp_code == GE_EXPR
6641 ? comp_op1 : comp_op0)))));
6648 /* If this is A op C1 ? A : C2 with C1 and C2 constant integers,
6649 we might still be able to simplify this. For example,
6650 if C1 is one less or one more than C2, this might have started
6651 out as a MIN or MAX and been transformed by this function.
6652 Only good for INTEGER_TYPEs, because we need TYPE_MAX_VALUE. */
6654 if (INTEGRAL_TYPE_P (type)
6655 && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
6656 && TREE_CODE (arg2) == INTEGER_CST)
6660 /* We can replace A with C1 in this case. */
6661 arg1 = convert (type, TREE_OPERAND (arg0, 1));
6662 t = build (code, type, TREE_OPERAND (t, 0), arg1,
6663 TREE_OPERAND (t, 2));
6667 /* If C1 is C2 + 1, this is min(A, C2). */
6668 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6669 && operand_equal_p (TREE_OPERAND (arg0, 1),
6670 const_binop (PLUS_EXPR, arg2,
6671 integer_one_node, 0), 1))
6672 return pedantic_non_lvalue
6673 (fold (build (MIN_EXPR, type, arg1, arg2)));
6677 /* If C1 is C2 - 1, this is min(A, C2). */
6678 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6679 && operand_equal_p (TREE_OPERAND (arg0, 1),
6680 const_binop (MINUS_EXPR, arg2,
6681 integer_one_node, 0), 1))
6682 return pedantic_non_lvalue
6683 (fold (build (MIN_EXPR, type, arg1, arg2)));
6687 /* If C1 is C2 - 1, this is max(A, C2). */
6688 if (! operand_equal_p (arg2, TYPE_MIN_VALUE (type), 1)
6689 && operand_equal_p (TREE_OPERAND (arg0, 1),
6690 const_binop (MINUS_EXPR, arg2,
6691 integer_one_node, 0), 1))
6692 return pedantic_non_lvalue
6693 (fold (build (MAX_EXPR, type, arg1, arg2)));
6697 /* If C1 is C2 + 1, this is max(A, C2). */
6698 if (! operand_equal_p (arg2, TYPE_MAX_VALUE (type), 1)
6699 && operand_equal_p (TREE_OPERAND (arg0, 1),
6700 const_binop (PLUS_EXPR, arg2,
6701 integer_one_node, 0), 1))
6702 return pedantic_non_lvalue
6703 (fold (build (MAX_EXPR, type, arg1, arg2)));
6712 /* If the second operand is simpler than the third, swap them
6713 since that produces better jump optimization results. */
6714 if ((TREE_CONSTANT (arg1) || DECL_P (arg1)
6715 || TREE_CODE (arg1) == SAVE_EXPR)
6716 && ! (TREE_CONSTANT (TREE_OPERAND (t, 2))
6717 || DECL_P (TREE_OPERAND (t, 2))
6718 || TREE_CODE (TREE_OPERAND (t, 2)) == SAVE_EXPR))
6720 /* See if this can be inverted. If it can't, possibly because
6721 it was a floating-point inequality comparison, don't do
6723 tem = invert_truthvalue (arg0);
6725 if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
6727 t = build (code, type, tem,
6728 TREE_OPERAND (t, 2), TREE_OPERAND (t, 1));
6730 /* arg1 should be the first argument of the new T. */
6731 arg1 = TREE_OPERAND (t, 1);
6736 /* Convert A ? 1 : 0 to simply A. */
6737 if (integer_onep (TREE_OPERAND (t, 1))
6738 && integer_zerop (TREE_OPERAND (t, 2))
6739 /* If we try to convert TREE_OPERAND (t, 0) to our type, the
6740 call to fold will try to move the conversion inside
6741 a COND, which will recurse. In that case, the COND_EXPR
6742 is probably the best choice, so leave it alone. */
6743 && type == TREE_TYPE (arg0))
6744 return pedantic_non_lvalue (arg0);
6746 /* Look for expressions of the form A & 2 ? 2 : 0. The result of this
6747 operation is simply A & 2. */
6749 if (integer_zerop (TREE_OPERAND (t, 2))
6750 && TREE_CODE (arg0) == NE_EXPR
6751 && integer_zerop (TREE_OPERAND (arg0, 1))
6752 && integer_pow2p (arg1)
6753 && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
6754 && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
6756 return pedantic_non_lvalue (convert (type, TREE_OPERAND (arg0, 0)));
6761 /* When pedantic, a compound expression can be neither an lvalue
6762 nor an integer constant expression. */
6763 if (TREE_SIDE_EFFECTS (arg0) || pedantic)
6765 /* Don't let (0, 0) be null pointer constant. */
6766 if (integer_zerop (arg1))
6767 return build1 (NOP_EXPR, type, arg1);
6768 return convert (type, arg1);
6772 return build_complex (type, arg0, arg1);
6776 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6778 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6779 return omit_one_operand (type, TREE_OPERAND (arg0, 0),
6780 TREE_OPERAND (arg0, 1));
6781 else if (TREE_CODE (arg0) == COMPLEX_CST)
6782 return TREE_REALPART (arg0);
6783 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6784 return fold (build (TREE_CODE (arg0), type,
6785 fold (build1 (REALPART_EXPR, type,
6786 TREE_OPERAND (arg0, 0))),
6787 fold (build1 (REALPART_EXPR,
6788 type, TREE_OPERAND (arg0, 1)))));
6792 if (TREE_CODE (TREE_TYPE (arg0)) != COMPLEX_TYPE)
6793 return convert (type, integer_zero_node);
6794 else if (TREE_CODE (arg0) == COMPLEX_EXPR)
6795 return omit_one_operand (type, TREE_OPERAND (arg0, 1),
6796 TREE_OPERAND (arg0, 0));
6797 else if (TREE_CODE (arg0) == COMPLEX_CST)
6798 return TREE_IMAGPART (arg0);
6799 else if (TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
6800 return fold (build (TREE_CODE (arg0), type,
6801 fold (build1 (IMAGPART_EXPR, type,
6802 TREE_OPERAND (arg0, 0))),
6803 fold (build1 (IMAGPART_EXPR, type,
6804 TREE_OPERAND (arg0, 1)))));
6807 /* Pull arithmetic ops out of the CLEANUP_POINT_EXPR where
6809 case CLEANUP_POINT_EXPR:
6810 if (! has_cleanups (arg0))
6811 return TREE_OPERAND (t, 0);
6814 enum tree_code code0 = TREE_CODE (arg0);
6815 int kind0 = TREE_CODE_CLASS (code0);
6816 tree arg00 = TREE_OPERAND (arg0, 0);
6819 if (kind0 == '1' || code0 == TRUTH_NOT_EXPR)
6820 return fold (build1 (code0, type,
6821 fold (build1 (CLEANUP_POINT_EXPR,
6822 TREE_TYPE (arg00), arg00))));
6824 if (kind0 == '<' || kind0 == '2'
6825 || code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR
6826 || code0 == TRUTH_AND_EXPR || code0 == TRUTH_OR_EXPR
6827 || code0 == TRUTH_XOR_EXPR)
6829 arg01 = TREE_OPERAND (arg0, 1);
6831 if (TREE_CONSTANT (arg00)
6832 || ((code0 == TRUTH_ANDIF_EXPR || code0 == TRUTH_ORIF_EXPR)
6833 && ! has_cleanups (arg00)))
6834 return fold (build (code0, type, arg00,
6835 fold (build1 (CLEANUP_POINT_EXPR,
6836 TREE_TYPE (arg01), arg01))));
6838 if (TREE_CONSTANT (arg01))
6839 return fold (build (code0, type,
6840 fold (build1 (CLEANUP_POINT_EXPR,
6841 TREE_TYPE (arg00), arg00)),
6849 /* Check for a built-in function. */
6850 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR
6851 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (expr, 0), 0))
6853 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (expr, 0), 0)))
6855 tree tmp = fold_builtin (expr);
6863 } /* switch (code) */
6866 /* Determine if first argument is a multiple of second argument. Return 0 if
6867 it is not, or we cannot easily determined it to be.
6869 An example of the sort of thing we care about (at this point; this routine
6870 could surely be made more general, and expanded to do what the *_DIV_EXPR's
6871 fold cases do now) is discovering that
6873 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6879 when we know that the two SAVE_EXPR (J * 8) nodes are the same node.
6881 This code also handles discovering that
6883 SAVE_EXPR (I) * SAVE_EXPR (J * 8)
6885 is a multiple of 8 so we don't have to worry about dealing with a
6888 Note that we *look* inside a SAVE_EXPR only to determine how it was
6889 calculated; it is not safe for fold to do much of anything else with the
6890 internals of a SAVE_EXPR, since it cannot know when it will be evaluated
6891 at run time. For example, the latter example above *cannot* be implemented
6892 as SAVE_EXPR (I) * J or any variant thereof, since the value of J at
6893 evaluation time of the original SAVE_EXPR is not necessarily the same at
6894 the time the new expression is evaluated. The only optimization of this
6895 sort that would be valid is changing
6897 SAVE_EXPR (I) * SAVE_EXPR (SAVE_EXPR (J) * 8)
6901 SAVE_EXPR (I) * SAVE_EXPR (J)
6903 (where the same SAVE_EXPR (J) is used in the original and the
6904 transformed version). */
6907 multiple_of_p (type, top, bottom)
6912 if (operand_equal_p (top, bottom, 0))
6915 if (TREE_CODE (type) != INTEGER_TYPE)
6918 switch (TREE_CODE (top))
6921 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6922 || multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6926 return (multiple_of_p (type, TREE_OPERAND (top, 0), bottom)
6927 && multiple_of_p (type, TREE_OPERAND (top, 1), bottom));
6930 if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
6934 op1 = TREE_OPERAND (top, 1);
6935 /* const_binop may not detect overflow correctly,
6936 so check for it explicitly here. */
6937 if (TYPE_PRECISION (TREE_TYPE (size_one_node))
6938 > TREE_INT_CST_LOW (op1)
6939 && TREE_INT_CST_HIGH (op1) == 0
6940 && 0 != (t1 = convert (type,
6941 const_binop (LSHIFT_EXPR, size_one_node,
6943 && ! TREE_OVERFLOW (t1))
6944 return multiple_of_p (type, t1, bottom);
6949 /* Can't handle conversions from non-integral or wider integral type. */
6950 if ((TREE_CODE (TREE_TYPE (TREE_OPERAND (top, 0))) != INTEGER_TYPE)
6951 || (TYPE_PRECISION (type)
6952 < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
6955 /* .. fall through ... */
6958 return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
6961 if (TREE_CODE (bottom) != INTEGER_CST
6962 || (TREE_UNSIGNED (type)
6963 && (tree_int_cst_sgn (top) < 0
6964 || tree_int_cst_sgn (bottom) < 0)))
6966 return integer_zerop (const_binop (TRUNC_MOD_EXPR,
6974 /* Return true if `t' is known to be non-negative. */
6977 tree_expr_nonnegative_p (t)
6980 switch (TREE_CODE (t))
6986 return tree_int_cst_sgn (t) >= 0;
6987 case TRUNC_DIV_EXPR:
6989 case FLOOR_DIV_EXPR:
6990 case ROUND_DIV_EXPR:
6991 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
6992 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
6993 case TRUNC_MOD_EXPR:
6995 case FLOOR_MOD_EXPR:
6996 case ROUND_MOD_EXPR:
6997 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
6999 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
7000 && tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
7002 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7004 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7005 && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7007 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
7008 || tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7010 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7012 return tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
7014 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7015 case NON_LVALUE_EXPR:
7016 return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
7018 return rtl_expr_nonnegative_p (RTL_EXPR_RTL (t));
7021 if (truth_value_p (TREE_CODE (t)))
7022 /* Truth values evaluate to 0 or 1, which is nonnegative. */
7025 /* We don't know sign of `t', so be conservative and return false. */
7030 /* Return true if `r' is known to be non-negative.
7031 Only handles constants at the moment. */
7034 rtl_expr_nonnegative_p (r)
7037 switch (GET_CODE (r))
7040 return INTVAL (r) >= 0;
7043 if (GET_MODE (r) == VOIDmode)
7044 return CONST_DOUBLE_HIGH (r) >= 0;
7052 units = CONST_VECTOR_NUNITS (r);
7054 for (i = 0; i < units; ++i)
7056 elt = CONST_VECTOR_ELT (r, i);
7057 if (!rtl_expr_nonnegative_p (elt))
7066 /* These are always nonnegative. */